Off the Goolag (2): Low cost shared hosting

For absolutely privacy, avoid using email (say, talk on Signal instead). Unless it’s inter-server mail in zero-knowledge encrypted providers like ProtonMail that also encrypt the message headers (meta-data, especially who’s sending to who), expect determined people with enough social engineering or authority can see it naked. It’s the same deal as snail mail where people in the post office can see what’s written on the envelope.

For big files like photos and typical cloud storage, which you should self-host these at home anyway. If you are worried about slow internet connection and downtime, you can pay for Zero-Knowledge cloud storage (which the server owners don’t have the master keys to your files) to add redundancy.

The next step down is to self-host your email, contacts, calendar, tasks (productivity suite) which you physically own so nobody can peek into it as long as you guard your home.

Hosting these services from home might be more work and risks (downtime), especially when it’s possible that your ISP’s IP address block is on the spammer’s list or if your ISP blocks the ports needed. The less secure alternative is to pay for extremely cheap shared web hosting services (we are talking about <$4/mo regular price and <$2 for the first year) which

  • you can make as many email accounts as you wanted
  • each email account comes with contacts, calendar, tasks as a bundle
  • use your own domain name
  • also host your own webpage and wordpress site

With Google, Microsoft, Apple and other big providers, they have big security teams to protect your data from hackers, but because of their centralized nature, it’s much more rewarding for hackers to breach one big provider than going after little accounts spread across different servers and IPs. Unless you are a high profile person or expect to be specifically targeted, you are better off managing your own productivity suite’s hosting/storage.

More importantly, it feels creepy when Google harvest my email and suggest I allow them to automatically register my appointment on my calendar. Random staff might not be reading our emails, but bots are and god knows what else they can do just by updating their code if they someday want to turn on us. They’ve become so powerful that with enough bankroll, they can make our politicians look the other way so there’s no way to stop them if we become dependent on their platforms.


cPanel

The instructions below assumes your shared hosting provider adopted cPanel as the account management interface which you have access to.

Like Google, your Gmail (email) account is also your account for a variety of productivity services (contacts, calendar, tasks). You can set it up by logging into cPanel, often https://(your server here)/cpanel.

There are a few naming conventions in cPanel that are different from Google’s ecosystem:

  • Login name is your ENTIRE email address because you can have different domains attached to the same hosting storage so you must enter the domain name after the @ sign for it to tell the accounts apart

Email

In modern times, I’d stick with IMAP for email (which is enabled by default in cPanel). Since Google would like to keep you in their ecosystem as much as possible, IMAP is not enabled by default for Gmail.

Webmail

Web email interface (you have a choice between Horde or RoundCube) is at port 2096. You can access it by

https://{name or IP to the shared host server assigned by your provider}:2096

or

https://{name or IP to the shared host server assigned by your provider}/webmail
(which will redirect you to port 2096 above)

In most cases, your domain name attached to the hosting points to the actual underlying shared hosting server assigned by your provider. I’d prefer not to use the underlying server address/IP because it might change when you move between hosting plans.

Also, per security design, WebMail doesn’t warn you when you enter non-existent email addresses (login). I’ll just silently loop you back to the login page again without explanation if you got any part of the login or password wrong.

DavX5 for calendar/tasks (CalDAV) and contacts (CardDAV)

In Android, calendar and contacts (also known as address book) are stored in a standard place shared by apps that picks them up from the system (email storage is per app, since POP3 and IMAP itself already does things very differently)

The default Calendar/Contacts app made it look like you have to use Google Calendar/Contacts to set up an online account (by default it came with Device/Local and Google accounts as option), but you can inject CalDAV/CardDAV accounts into the Android’s calendar/contacts system with an app called DAVx5.

The App is FREE if you download it from F-droid but costs $5.99 if you download it from Google Play. It’s not a loophole, but the authors want people to move away from Google Play and use F-droid, a Free-and-Open-Source (FOSS) app store.

DAVx5 works in a little unusual way that accounts are NOT added through calendar/contacts app but instead you register your CalDAV/CardDAV accounts, select the folders to sync, SYNC IT, then each sync’ed FOLDER (you hear me right) will show up as standard Android Accounts (just like Google/Samsung Accounts) which will work with any standard Calendar/Contacts app. All management (add/removal) happens in DAVx5.

When you set up an CalDAV/CardDAV account, remember NOT to use the first option “Login with email address”! You must enter the URL which points to Port 2080 of the shared hosting server

If you forget to enter the port number, the account will be set up with CalDAV/WebCAL, without CardDAV!

Select “Groups are separate vCards“:

Help - Davx5 (Davdroid): How do I use the Posteo address book and the  Posteo calendar on Android devices? - posteo.de
https://posteo.de/en/help/synchronising-contacts-and-calendar-entries-with-the-address-book-and-calendar-using-davdroid-android

Basically CardDAV is just a folder storing each contact as VCF (vCARD) file and CalDAV is just a folder storing each event/task as an ICS file. Basically it’s just a primitive HTTP file manager hosted with HTTPS login and apps are supposed to find the folder using a consistent naming scheme.

 1 total views

Freshtomato for Netgear (Nighthawk) R7000

Netgear R7000 supports these major forms of firmware

  • DD-WRT (Powerful, but very messy web interface that are sometimes non-intuitively organized)
  • FreshTomato (Powerful. I wouldn’t say easy to use but mortal souls can understand it)
  • XWRT-Vortex (Easy to use AsusWRT Merlin web interface adapted for non-Asus routers)

There are other forms of Tomato that support R7000 but only FreshTomato is actively maintained as of late 2021.

However updating it from stock firmware to FreshTomato has some model-specific quirks (that you cannot extrapolate from general procedures for other models)

First of all. You cannot update directly to the latest firmware. There’s a bootstrap (intermediate) firmware called INITIAL (usually downloaded from ‘Netgear R-series initial files’ folder) that must be installed (upgraded from stock firmware to) FIRST so the router is ready to accept the latest/full firmware.

Here’s the model specific quirk: the default login/password is non-standard for R7000! It’s not root/admin (unless you press the button to reset the NVRAM)! It’s admin/@newdig!

After logging into the bootstrap/INITIAL freshtomato with the password above, upgrade the firmware to the latest (the one intended) and choose clear NVRAM along the way. The default login/password will be root/admin as standard for freshtomato.

 2 total views

Off the Goolag (1): Android (AOSP)

App Stores

The first thing to worry about after a fresh install is getting the Apps you need. I’d recommend installing all these app stores to start with:

  • F-droid (Only free and open source, privacy-respecting and community verified apps. Some paid apps on Google Play such as DavX and FairMail is free on F-droid to promote it! Note that sometimes the F-droid repository might be a little behind)
  • Aptoide (App writers self-publishes app under community scrutiny, which sometimes let you download geoblocked app. Fairly updated but not as updated as Auora. The apps are not tightly guarded as F-droid)
  • Auora (It’s a proxy to downloading the APK from Google Play store without letting Google track you. It’s anonymous account is international, which makes the search for the basic apps very difficult as it’s seeing a worldwide scope. You can have Auora sign in with a disposable Google account for apps that are relevant to your regions. Remember to disable your Google Play if installed and have Google Play links open with Auora.)

Yalp store is outdated and not actively maintained. Google Play store proxies needs to constantly fight with Google’s changes so they need to be updated frequently. Just stick with Auora for now.

Install Island (Sandboxing apps)

This is the very first app you need to install after you get F-droid or Auora. This app is a must even if your phone is not DeGoogled. A lot of apps asks for more permissions than they actually needed, but sometimes we are stuck with using them (like required at work).

The solution is to create a sandbox (another copy/instance of the app) that has a different space for app data and they cannot see your actual call logs, contact list, photos, etc even if you gave them the permission to do so. It’s called an ‘Island’ and the native space is called ‘Mainland’.

Putting an app in Island (work mode) doesn’t protect you from other access requests such as location, etc. Nonetheless the mainland and island app has their own data space (i.e. you have to configure it twice as if the apps are freshly installed) so they can have two sets of settings and application permissions.

Apps installed through the Island instance of the App Stores / Browsers above will stay in Island mode. Apps installed through Mainland instance of the App Stores will stay in Mainland mode. They are totally separate as intended. You can clone the APK/app between Island and Mainland through the Island App.

Note that some VPN clients will have a split personality (which is a good thing) between Mainland and Island! This means you get to have a group of apps that’s on VPN and a group of apps that’s on the direct network without managing them one by one with split tunneling!

Also note that the Island won’t be able to access external storage like SD cards. It’s by design so that Island apps are trapped in their own virtual space so they cannot snoop around your personal data even if you gave them the permissions (demanded during installation)

Browsers: Brave + DuckDuckGo

DuckDuckGo (sometimes the permissions and default app lunching do not work correctly with it. I use DuckDuckGo first whenever it doesn’t break)

Brave (based on Chromium). Replaces Chrome. It has a chain sync feature that syncs passwords, bookmarks, etc like Google Chrome does but WITHOUT AN ACCOUNT. As long as you have one device with Brave connected to the Internet and you did the steps to match the devices, they will sync up.

Keyboard: MS Swift Keyboard

I speak 5 languages and found Microsoft Swift on screen keyboard having nice IME (Input Method Engine) for all of them and also have an intuitive interface that’s not clumsy to use. I prefer it over Gboard and AOSP that came with LineageOS). I do not log in to Microsoft Swift and share data with them (the petty convenience of sharing the clipboard is just not worth it).

NON-CLOUD based Email client: Fairmail / MailDroid

Email is a huge topic which I’ll discuss in a separate post as it often come as a bundle with contact list, task lists, calendars, and taking notes.

Do NOT use free apps that sends your credentials to the provider‘s BACK-END SERVERS which you don’t own and manage, such as BlueMail if you are doing all these to protect your privacy (you might as well use Google if you do that)! NextCloud is OK as long as you host it.

K-9 mail client is promising but I do not like it implicitly forcing you to log in through Google’s web interface to set it up instead of doing the traditional IMAP setup if you use Gmail.

Fairmail has a lot of extra steps during setup because it let you customize the heck out of it and by default (out of the box), it protects you from tracking images and malicious HTML dingleberries out of the box (which hurts readability).

MailDroid is is supported by in-app advertisements (you can remove ads with Pro version). It’s more intuitive than Fairmail and K-9. It automatically detects Gmail’s IMAP settings (not Google OAuth2 login) correctly, but doesn’t autodetect does not work with namecheap’s cPanel mail while Fairmail does.

I don’t use Aqua Mail because the free version do not allow multiple accounts like MailDroid does.

K-@ Mail feels like Gmail. Support multiple accounts. Also autodetect Gmail IMAP correctly but not cPanel email correctly like Maildroid. IMAP Folders do not work correctly for either Gmail/cPanel (it shows nothing): the folder button (bottom left) shows generic Inbox/Draft/Outbox/Sent/Trash/{Folder list} which do not match the IMAP folders. “Folder list” shows the IMAP folders, but when I clicked on them it shows nothing.

Just because of the non-working IMAP folders, I chose to not use K-@ Mail and stick with MailDroid.

I personally like Fairmail because the interface wastes no visual space showing all my IMAP folders. MailDroid is visually pleasing but the folder panel took up too much white space and I cannot tuck away the special (local) folders in the side panel.

Chat: Signal, VoIP: Telegram

Fascist book now requires data sharing with Whatsapp, so people in Hong Kong who don’t trust the fascist Chinese Communist Party regime is dropping it like a hot potato.

Signal App do not keep a master key on your message (if you lose the key, you lock yourself out and there’s no recovery) and is my preferred app for chat. Although Telegram’s owner has a good track record of protecting political dissidents (that’s why it was used in 2019 Hong Kong Protests), it’s not fully open source and the owner still has the master key. Telegram is still way better than Whatsapp but for full privacy I stick with Signal App.

Signal App’s voice over IP is a little weak and it can break up easily on spotty network connection. Telegram is much better in terms of voice quality so I basically use Telegram as a VoIP phone and leave the chats to Signal.

 4 total views

Off the Goolag Applelago! (0) – Introduction

Privacy: detaching identity (fingerprinting) from activities!

The new idea of privacy is not hiding what you normally do (legal) perfectly, but to make it difficult for automation to uniquely identify and match you so your habit doesn’t get observed and stereotyped. For example, I love fried chicken and watermelon, but I don’t want to see advertisements for malt liquor.

Apple’s ecosystem is tightly controlled, so the uniqueness is guaranteed. If you use Apple products, you are totally at the mercy of Apple Inc AND their employees (whom you didn’t hire) honoring their legal, contractual and moral obligations. It’s by design: Apple limits what you can do within their imaginations so they can limit the scope of what kinds of thing that can possibly go wrong. The side effect is customers are giving away their freedoms to authoritarians for convenience and promised protections.

Therefore my exploration of escaping the Goolag Applelago do not consider Apple products. They can turn into Chinese Communist Party dictatorship at a flip of a switch when they’ve became so powerful that they are above law. Given how they bankroll the lobbyists and how close they are to ChiCom/CCP, it’s a more realistic threat than most think.

Operating system: AOSP

I don’t have a Pixel so I cannot try CalyxOS and GrapheneOS. For usability, it’s most practical to have Android-Open Source Projects builds that does not contain proprietary Google apps. Many proprietary Google services are built in stock ROM, so these AOSP builds either remove them or replace them with MicroG (which do not track users) so apps that depends on the proprietary Google Play Services will still run.

So far I’ve tried these OS that supports a wide range of old phones:

I’m least impressed by the performance of /e/. It’s very laggy compared to the rest to the extent it’s close to the Stock ROM. The concept is good that it tries to have a tightly integrated user experience (including Cloud) to replace Google’s ecosystem, but the apps that came out of the box is primitive. “Apps” is a nice package installer that gives a bit more access to common apps that’s a little less than Auora OSS (but easier to find) and a lot more than F-droid. That’s the only good thing I can say about it for now.

NanoDroid came with a lot of well-designed, excellent privacy-respecting open source apps that is eye opening (I’ll discuss it in later posts). They have a few more apps pre-installed than what I wanted, so I went with LineageOS + microG so I can pick-and-choose my apps.

The official LineageOS comes without these Google’s proprietary infrastructure, so either you install proprietary Gapps through TWRP (one of the universal bootloaders to install LineageOS and the like), which defeats DeGoogling, or painfully install microG on top of it. I decided to go with the latter.

The phone works A LOT FASTER (fluid user experience) with LineageOS than the bloated crap that came with Stock ROM.

WARNING: Things to watch out while mucking with Android OS upgrades/changes

Absolutely back up your files (apps, photos, videos, downloads, settings, etc) to external drive or cloud storage first! Do NOT trust any of the doc that your OS might work after an ‘upgrade’. It doesn’t. The AOSP builders did not spend much time thinking of migration issues (these are boring thankless menial work that nobody wants to do it for free, so don’t get your hopes up).

You MUST ALWAYS assume that you’ll have to factory reset your device, which I recently learned the hard way by losing data because I formatted the SD card as internal storage (called adoptable storage) in LineageOS 15.1 then unwittingly deleted the encryption key to the SD card while factory resetting the device because the /data and /system partitions are not in a compatible state with the new 18.1 (or even 16.0)!

Some maintainers are not very fond of adoptable storage so they don’t put much thought into it hoping it’ll go away. Adoptable storage a useful feature but it’s full of traps (fragile) so it’s best to avoid it altogether unless you swear to not upgrade your LineageOS and assume the SD card will live and die with the device.

 6 total views

GUI Paradigms (1): Redux (Flutter/React) translated to MATLAB

For GUI development, we often start with controls (or widgets) that user interact with and it’ll emit/run the callback function we registered for the event when the event happens.

Most of the time we just want to read the state/properties of certain controls, process them, and update other controls to show the result. Model-View-Controller (MVC) puts strict boundaries between interaction, data processing and display.

The most common schematic for MVC is a circle showing the cycle of Controller->Model->View, but in practice, it’s the controller that’s the brains. The view can simultaneously accept user interactions, such as a editable text box or a list. The model usually don’t directly update the view directly on its own like the idealized diagram.

MVC with User Action
From https://www.educative.io/blog/mvc-tutorial

With MVC, basically we are concentrating the control’s callbacks to the controller object instead of just letting each control’s callback interact with the data store (model) and view in an unstructured way.


When learning Flutter, I was exposed to the Redux pattern (which came from React). Because the tutorials was designed around the language features of Dart, the documentation kind of obscured the essence of the idea (why do we want to do this) as it dwelt on the framework (structure can be refactored into a package). The docs talked a lot about boundaries but wasn’t clearly why they have to be meticulously observed, which I’ll get to later.

The core inspiration in Redux/BLoC is taking advantage of the concept of ‘listening to a data object for changes’ (instead of UI controls/widget events)!

Instead of having the UI control’s callback directly change other UI control’s state (e.g. for display), we design a state vector/dictionary/struct/class that holds contents (state variables) that we care. It doesn’t have to map 1-1 to input events or 1-1 to output display controls.

When an user interaction (input) event emitted a callback, the control’s callback do whatever it needs to produce the value(s) for the relevant state variable(s) and change the state vector. The changed state vector will trigger the listener that scans for what needs to be updated to reflect the new state and change the states of the appropriate view UI controls.

This way the input UI controls’ callbacks do not have to micromanage what output UI controls to update, so it can focus on the business logic that generates the content pool that will be picked up by the view UI controls to display the results. In Redux, you are free to design your state variables to match more closely to the input data from UI controls or output/view controls’ state. I personally prefer a state vector design that is closer to the output view than input controls.


The intuition above is not the complete/exact Redux, especially with Dart/Flutter/React. We also have to to keep the state in ONE place and make the order of state changes (thus behavior) predictable!

  • Actions and reducers are separate. Every input control fires a event (action signal) and we’ll wait until the reducers (registered to the actions) to pick it up during dispatch() instead of jumping on it. This way there’s only ONE place that can change states. Leave all the side effects in the control callback where you generate the action. No side effects (like changing other controls) allowed in reducers!
  • Reducers do not update the state in place (it’s read only). Always generate a new state vector to replace the old one (for performance, we’ll replace the state vector if we verified the contents actually changed). This will make timing predictable (you are stepping through state changes one by one)

In Javascript, there isn’t really a listener actively listening state variable changes. Dispatch (which will be called every time the user interacts using control) just runs through all the listeners registered at the very end after it has dispatched all the reducers. In MATLAB, you can optionally set the state vector to be Observable and attach the change listener callback instead of explicitly calling it within dispatch.

https://gist.github.com/gaearon/ffd88b0e4f00b22c3159

Here is an example of a MATLAB class that captures the spirit of Redux. I added a 2 second delay to emulate long operations and used enableDisableFig() to avoid dealing with queuing user interactions while it’s going through a long operation.

classdef ReduxStoreDemo < handle

    % Should be made private later
    properties (SetAccess = private, SetObservable)
        state % {count}
    end
        
    methods (Static)
        % Made static so reducer cannot call dispatch and indirectly do
        % side effect or create loops
        function state = reducer(state, action)        
            % Can use str2fun(action) here or use a function map
            switch action
                case 'increment'
                    fprintf('Wait 2 secs before incrementing\n');
                    pause(2)
                    state.count = state.count + 1;
                    fprintf('Incremented\n');
            end                
        end        
    end
    
    % We keep all the side-effect generating operations (such as
    % temporarily changing states in the GUI) in dispatch() so
    % there's only ONE PLACE where state can change
    methods
        function dispatch(obj, action, src, evt)
            % Disable all figures during an interaction
            figures = findobj(groot, 'type', 'figure');
            old_fig_states = arrayfun(@(f) enableDisableFig(f, 'off'), figures);      
            src.String = 'Wait ...';
            
                new_state = ReduxStoreDemo.reducer(obj.state, action);
                
                % Don't waste cycles updating nops 
                if( ~isequal(new_state, obj.state) )
                    % MATLAB already have listeners attached.
                    % So no need to scan listeners like React Redux            
                    obj.state = new_state;
                end                
                
            % Re-enable figure obj.controls after it's done
            arrayfun(@(f, os) enableDisableFig(f, os), figures, old_fig_states);                        
            src.String = 'Increment';
        end
    end
    
    methods
        function obj = ReduxStoreDemo()
            figure();            
            obj.state.count = 0;                        
            
            h_1x  = uicontrol('style', 'text', 'String', '1x Box', ...
                              'Units', 'Normalized', ...
                              'Position', [0.1 0.3, 0.2, 0.1], ...
                              'HorizontalAlignment', 'left');                          
            addlistener(obj, 'state', ...
                        'PostSet', @(varargin) obj.update_count_1x( h_1x , varargin{:})); 
                        
            uicontrol('style', 'pushbutton', 'String', 'Increment', ...
                      'Units', 'Normalized', ...
                      'Position', [0.1 0.1, 0.15, 0.1], ...
                      'Callback', @(varargin) obj.dispatch('increment', varargin{:}));                             
            
            % Force trigger the listeners to reflect the initial state
            obj.state = obj.state;
        end
    end
    
    %% These are 'renders' registered when the uiobj.controls are created
    % Should stick to reading off the state. Do not call dispatch here
    % (just leave it for the next action to pick up the consequentials)
    methods
        % The (src, event) is useless for listeners because it's not the 
        % uicontrol handle but the state property's metainfo (access modifiers, etc)
        function update_count_1x(obj, hObj, varargin)            
            hObj.String = num2str(obj.state.count);
        end        
    end
    
end

 4 total views

An easy way to remember Euclid GCD algorithm: laying tiles

I was a little embarrassed that I’ve never came across Euclid’s GCD algorithm until years after I graduated with Math and Engineering degrees. The descriptions I found online (especially Wikipedia) are convoluted and confusing, and the mechanical description of the algorithm does not shine light to any intuition. Then there comes proofs and abstract algebra properties that even after I followed the reasoning, I’d soon forget after I stop looking at it in a few weeks.

Just by staring at one simple description of the algorithm:

The classic algorithm for computing the GCD, known as Euclid’s algorithm, goes as follows: Let m and n be variables containing the two numbers, divide m by n. Save the divisor in m, and save the remainder in n. If n is 0, then stop: m contains the GCD. Otherwise repeat the process, starting with division of m by n.

K.N. King’s C++ Programming (Chapter 6 Exercise 2)

I reversed engineered one line of reasoning how one could come up with the Euclid GCD on his own. Turns out there is one twist/angle that most traditional explanations glossed over: quotients do NOT matter and WHY it does NOT matter!

It goes back to what GCD(a,b) stands for: greatest common divisor. You are looking for the largest factor that simultaneously divides a and b evenly. If you rethink in terms of multiplication, you are finding the biggest tile size c that can simultaneously cover a and b without gaps:

Find c s.t. a = pc and b= qc where p,q are integers.

Imagine you are a lazy and cheap contractor who have unlimited tile samples of all sizes to try before making a large order:

  • [Goal] you have to cover with two floors with potentially different sizes a and b gaplessly
  • [Constraint: divisible] your customer won’t let you cut (fractional) tiles because it’s ugly
  • [Constraint: common denominator] you can only order ONE tile size to take advantage of bulk discounts
  • [Objective: greatest] more tiles means more work to lay it, so you want to shop for the biggest tile size that does the job.

For simplicity of the argument, we also assume the divisor b is the smaller number. If b is the bigger number, the roles will reverse in the next round because the remainder from dividing by a larger number is the dividend itself, which becomes the divisor in the next round while the old divisor (the larger number) becomes the dividend.

For relatively prime pairs, the algorithm will eventually stop with a GCD of 1 because 1 divides all integers.

Here’s the analog of Euclid algorithm:

  • start out with 1 big tile covering the entire smaller floor b
  • see if we can cover a without gaps using big tiles of size b
  • if yes, we are done. b, the macro-tile is your GCD (perfect-sized tile).
  • if there are gaps (non-zero remainder), pick a tile-size that covers the ugly gap (the remainder becomes the divisor), then repeat the same process above over the last tile size b (the divisor becomes the dividend) until there are no gaps (remainder become zero).

The algorithm is taking advantage of the fact the remainder is smaller than the last tile size (divisor) so we can rewrite the last tile size in multiples of the remainder (old gap) plus the new gap. By the time the new gap divides the last tile size, all numbers before that can be written as multiples of it (i.e. the last gap evenly divides all the numbers in the chain all the way up to b and a).

Let’s start with a simple case GCD(a=50, b=15) that terminates early:

50 (dividend) = 15+15+15 (divisor) + 5 (remainder)

We focus on the last tile 15 and write it in terms of the old remainder 5:

15 = (5+5+5) + 0

Since the new remainder is 0, the old remainder 5 divides the last tile 15. Since we are dividing a in terms of the remainder 5, we have

\begin{aligned}
b &= 15 \\
&= (5+5+5) \\
&= 3r \\
\\
a &= 50 \\
& = (15 + 15 + 15) + 5\\
& = 3b + r\\
&= (5+5+5) + (5+5+5) + (5+5+5) + 5\\
&= 3(3r)+r \\
& = 10r
\end{aligned}

So both a and b can be written in terms of integer multiples of r right before the algorithm stops.


GCD(50, 18) takes a few more steps:

\begin{aligned}
b &= 18\\
a &= 50\\
&= (18 + 18) + 14\\
&=2b + r\\
r &= 14 \\
\\
b_1 &= r = 14\\
a_1 &= b = 18\\
&= (14) + 4\\
&= b_1 + r_1\\
r_1 &= 4\\
\\
b_2 &=r_1 = 4\\
a_2 &= b_1 = 14\\
&= (4+4+4)+2\\
&= 3b_2 + r_2\\
r_2 &= 2\\
\\
b_3 &= r_2 = 2\\
a_3 &= b_2 = 4\\
&=(2+2) + 0\\
r_3 &= 0\\

\end{aligned}

The algorithms stops at r_3=0 which means we successfully divided the last tile a_3 with r_2 (logistically stored in b_3) with no gaps left. r_2 (or b_3 is therefore the greatest common factor (divisor) that are shared by all the numbers involved all the way up to a and b.

This is the beauty of Euclid’s GCD algorithm: once the gap (remainder) is sliced small enough to evenly divide the tile (divisor) right before it, every term before it be can written in terms of integer multiples of the last number that divides the last tile without gap (no more remainder).

In our example, 4, 14, 18, 50 can be written as a multiple of 2, aka r_2 because integer multiples of numbers that are already integer multiples of r_2 can be written in terms of a larger integer multiple of r_2. This is why quotients do not matter in the Euclid GCD algorithm:

\begin{aligned}
b_2 &= 2r_2\\
4 &= (2+2) \\
\\
b_1 &= 3b_2 + r_2\\
&= 3(2r_2) + r_2\\
& = 7r_2\\
14 &= [(4+4+4)+2] \\
&=  [(2+2)+(2+2)+(2+2)+2] \\

\\
b &= b_1 + r_1\\
&=7r_2 + 2r_2\\
&=9r_2\\
18 &= 14 + 4 \\
&=  [(4+4+4)+2] + 4 \\
&=  [(2+2)+(2+2)+(2+2)+2]+[(2+2)] \\
\\
a &= 2b + r\\
&=2(9r_2) + 7r_2\\
&= 25r_2\\
50 & = 18 + 18 + 14 \\
&= [(2+2)+(2+2)+(2+2)+2]+[(2+2)] \cdots \\
&+ [(2+2)+(2+2)+(2+2)+2]+[(2+2)] \cdots \\
&+ [(2+2)+(2+2)+(2+2)+2]
\end {aligned}

The spirit of the algorithm is that every time we see a gap, we fill it with a small tile that’s exactly the gap size, and attempt to replace the last tile by covering it in terms of the new smaller tile (that was used to fill the gap). We are recursively slicing the last tile with the gaps produced until there are no gaps left. Once you find the GCD tile, you can replace all the bigger tiles before in terms of it with no gaps.

There’s an interesting perspective of using the Euclid GCD algorithm to solve Diophantine Equations (integer written as a linear combination of integers with integer coefficients): turns if x=1 in c=ax-by is the same as writing a = by+r. We can flip the sign of y by saying substituting y'=-y.

 10 total views

Rationale Behind C++ Commandments (5) – OOP design

The idea of bundling code and program into a layout (classes) and injecting it with different data (objects) leads to a ‘new’ way (newer than C) of organizing our programs through the worldview of objects.

Every unit is seen as

  • a state: all member variables
  • possible actions: methods = member functions.

that is ready to interact with other objects.


Encapsulation (through access control)

The first improvement upon OOP is privacy (data encapsulation). You can have finer controls of what to share and with who. In C++, your options are:

  • public: everybody
  • private: only within yourself (internal use)
  • protected: only shared with descendants (inheritance discussed below)

Granting certain class as friend (anywhere in the class declaration with friend class F) exposes the non-public sections specifically to the friend F. This is often a ‘loophole’ to access control that finds few legitimate uses other than testing.

friend functions are traditionally used in binary (2-input) operator overloading, but the modern wisdom is to screw it and just leave it out there as free functions!

protected has very few good uses other than preventing heap delete through base pointer non-polymorphically (child destructor not called: BAD) by making the base destructor non-public (i.e. meaning it’d be impossible to have base objects on stack) while letting the child chain the parent’s destructor (child can’t access it if it’s marked as private).

protected member variables are almost always a bad idea.


Inheritance

The second improvement is to allow classes to build on top of existing ones. What gets interesting (and difficult) is when the child ‘improve’ on the parent by either by replacing what they have (member variables) and what they do (methods) with their own.

Static data members inherit REFERENCES to the parent!

Inheritance AT LEAST always inherits an interface (can optionally inherit implementation).

Base implementation MUST NOT be inheritedpure virtual methods
Base implementation inherited by defaultvirtual
Base implementation MUST be inheritednon-virtual (and not shadow it)

Shadowing

Whenever the member (function or variable) name is used in any form (even with different argument types or signatures), the parent member with the same name will be hidden. The behavior is called shadowing, and it applies unless you’ve overridden ALL versions (signatures) of virutal parent methods which shares the same function name mentioned in child.

  • Any non-overriden method with the same name as the parent appearing in the child will shadow all parent methods with the same name regardless of whether they are declared virtual and overriden at child.
  • You can unhide parent methods with the same name (but different signature) by using Parent::f(..) declared at the child class.
  • Shadowing implies there’s always one parent version and one child version stored separately under all conditions {static or non-static}x{function or variable}
  • Static members don’t really ‘shadow’ because there’s only one global storage for each (parent and child) if you declare the same variable name again in the child. There’s nothing to hide because you cannot cast or slice a namespace! With static members, you have to be explicit about which class you are calling from with SRO like Parent::var or Child::var so there’s no potential for ambiguities.

Overriding

Just like C, C++ uses static binding that takes the programmer’s word for it for their declared types, especially through handles. Overriding is a concept only needed when you plan to upcast your objects (child accessed through pointer/reference) to handle a broader class of objects but intend to the underlying object’s own version (usually child) of the methods (especially destructors) called by default.

We do this by declaring the parent method virtual and implement the child versions (must be of the same function signature). Overriding only make sense for non-static methods because

  • data members cannot be overridden (it’d confusing if it’s possible. We down-delegate functions/behavior but not the data/state). It’s better off hiding data members behind getters/setters to declare the intention.
  • static members and methods behaves like static variable/functions (living in .data or .bss) using namespaces, so we can only refer to them with SRO by the class names like Parent::f() and Child::a, not a class type like Parent p; p.f() and Child c; c.a. There’s no object c for you to upcast to Parent so there’s place for polymorphic behavior.

Overriding involves leaving clues in objects so the upcasted references can figure out the correct methods of the underlying objects to call. In C++ it’s done with having a vtable (pointers to overridable methods, often stored in .rodata with string literals) for each class in the hierarchy and each object contains a pointer to the vtable that matches its underlying class.

[38] virtual only applies to methods’ signatures (function name and the data types in the argument list). vtable do not keep track of argument’s default values (if assigned) for efficiency (it’ll always read the static upcast, aka parent methods’ default values).


Classes (after considering inheritance)

Design relationships

  • class behaves through public methods
  • Inheritance at least always inherits an interface
  • IS-A relationship is done with public-inheritance
  • … (incomplete, will update later)

 5 total views

Rationale Behind C++ Commandments (4) – Method Signature System

Function signature system, which allows users to use the same function name in different functions as long as they differ in the combination of

  • input arguments types
  • const modifiers counts as a different input argument type
  • object const-ness (whether it’s const-method or not) – this only make sense with classes

and C++ will figure out what to call by matching the call with the available combinations (signatures).

C does not allow the same function name to be used in different places, so under the hood, it’s done through name mangling (generating a unique ‘under-the-hood’ function name based on the signature). This mechanism has a lot of implications that a professional programmer should observe:

  • since C does not mangle its names in the object code, they’ll need to be wrapped around with extern “C” block in a C++ program so C++ won’t pervert (mangle) their function names with input arguments.
  • [24] parameter defaulting might be ambiguous with another function that does not have the said parameter (the compiler will cry about it)
  • [26] access controls/levels must play no part in resolving signatures because access level must not change the meaning of a program!

C++ resolve function overloading using signatures within its local namespace. Function overloading works for both

  • free functions (free functions are at the root namespace), as well as
  • classes (the name of the class itself is the namespace)

 8 total views

Rationale Behind C++ Commandments (3) – Classes came from emulating POD data types through struct and namespaces

In structured programming (like C and C++), the building abstractions is program (functions) and data (variables).

Under the hood, especially in von-Neumann architecture’s perspective, functions and variables are both just data (a stream of numbers) that can be moved and manipulated the same way just like data. It’s all up to how the program designer and the hardware choose to give meaning to the bit stream.


Namespaces

In C, we can only scope our variables 3 ways: global, static (stays within same file/translation unit) and local. Sharing variables across functions in different translation units can only be done through

  • globals (pollutes namespace and it’s difficult to keep track of who is doing what to the variables and the state at any time)
  • passing (the more solid way that gives tighter control and clearer data flow, but managing how to pass many variables in many places is messy, even with struct syntax)

Bundling program with data gives a new way to tightly control the scope of variables: you can specify a group functions allowed to share the same set of variables in the bundle WITHOUT PASSING arguments.

The toolchain modified to recognize the user-defined scope boundaries which bundles program and data into packages, thus reducing root namespace pollution. The is implemented as namespace keyword in C++

Organizing with namespaces is basically justifying the mentality of using globals (in place of passing variables around intended functions) except it’s in a more controlled manner to keep the damages at bay. The same nasty things with gloabls can still appear if we didn’t design the namespace boundaries tightly so certain functions have access to variables that’s not intended for it.

Therefore, namespaces works nearly identical to a super-simple purely static class (see below) except you lose inheritance and access modifiers in classes in exchange for allowing anonymous namespaces.

Basically namespaces + structs + inheritance + encapsulation (access modifiers) = classes


Classes

Classes extends the idea of namespaces by allowing objects (each assigned their own storage space for the variables following the same variable layout) to be instantiated, so they behave like POD (Plain Old Data) in C. We should observe that when overloading operators

  • [15] allow (a=b)=c chaining by returning *this for operator=
  • [21] disallow rvalue assignment (a+b)=c by returning const object

In the most primitive form (no dynamic binding and types, aka virtuals and RTTI), function (method) info is not stored within instantiated objects as the compiler will sort out what classes/namespace they belong to. So it screams struct in C!

C struct is what makes (instantiates) objects from classes!

Note that C structs do not allow ‘static fields’ because static members is solely a construct of namespaces idea in C++! C++ has chosen to expand structs to be synonymous to classes that defaults to private access (if not specified) so code written as C structs behaves as expected in C++.

 9 total views

‘Static classes’ are unlike instantiable (object-bearing) classes in many ways

Technically there’s no static class in C, but a class with all members and functions declared static.

Static classes are like namespaces in many ways. Because no object is constructed (it’s just holding a bunch of variables and functions in the free space), a lot of features and syntax with regular classes do not make sense with static classes.

Because no objects are instantiated

  • No constructors or destructors (no objects to make/destroy)
  • No operator overloading (you need an instantiation to pass arguments to operator methods)
  • No overriding because there are no objects for you to upcast
    (nor there’s an object to store the vtable from the virtual keyword)!

Static members and methods are treated as free objects scoped by namespaces

  • Like C, static members variables live in .bss (not explicitly initialized ones will be zero-initialized) or .data (initialized) sections, not on stack/heap!
    Exception: static const int is internally seen as enum, which the compiler uses it to plug values in the code instead of allocating space for it.
  • Therefore the syntax is pretty much like free static/global variables
  • No constructor to build member variables within the class definition, so they must be defined OUTSIDE the class definition at the top level (just like static/globals), with a SRO (scope resolution operator).
  • Static methods acts like (and function overloads the same way as) free functions.
    That’s why we often use static methods for helpers.

Namespaces has no access modifiers (public/protected/private/friend), but in return only namespaces can be unnamed/anonymous (which behaves as private)!

Namespaces cannot be inherited, but static classes can!

  • Inherited members ARE REFERENCES to the parent!
    There’s no extra copies of underlying data if that member is successfully inherited (not shadowed)!
  • Members (function or variables) can only be shadowed in the child (never overridden since it’s not an object), which creates a NEW stack variable and hid the reference to the parent member

Static class’s inheritance behavior is the same across static classes object-bearing classes! It’s actually more explicit with static members as you’ll need two declarations outside the classes if you shadow.

I am pointing this out to show that inheriting static classes IS NOT cloning namespaces! Static classes behaves as if it’s just ONE CHILD object created on the .bss/.data section (the section for static variables).

This means unlike object-bearing classes, the static class Parent cannot exist on its own if its children are defined!

C++ rules are almost always sensible and coherent; but when combined, sometimes the implications could be surprising on the first sight! When we try to extrapolate expected behaviors in C++, very often we have to think not in terms of the convenient syntax, but the implications of its ground rules (a lot of them stems from C)!

 18 total views