Explain XOR tricks succinctly with two properties Change detector, toggler

Posted on by
Reply

Most teaching materials on XOR starts from its straight definition then a bunch of recipes for exploiting XOR. It is not convenient to remember and not intuitive to come up with new tricks on our own. Instead, I’d like to describe XOR as two intuitive operations:

  1. Change detector (The logic definition itself)
  2. Toggling light switches (Flipping twice undoes it)

The second interpretation (toggling) is actually way more powerful and easy to remember than the first interpretation (definition).

With the toggling interpretation, you don’t have to think hard to come up with the four algebraic properties:

  1. Associativity and commutativity: we only care about whether the individual light switches (bits) are flipped odd (flipped) or even (not-flipped) number of times at the end of the day. When it happens in what order does not matter.
  2. Identity: flipping NONE of the switches (a mask of all 0) leaves it alone
  3. Inverse: pick only the switches that are already turned on (using itself as mask) and flip them (xor) guarantees to turn everything off (0)

The XOR swap trick can be constructed by exploiting the fact that flipping the same switch twice (at any point) reverts it back to where it started:

x y
Start x_0 y_0
Mix y_0 with x_0 x_1 = x_0 \oplus y_0 No info is lost, still have y_0 somewhere to undo if we wish.
The incumbent y_0 is used to cancel the y_0 inside x_1 to recover x_0 \begin{array}{rcl} y_2 & = & y_0 \oplus x_1 \\ & = & y_0 \oplus (x_0 \oplus y_0)\\ & = & x_0 \end{array} Since y_0 is already saved (mixed with) x_1, we don’t have to worry about losing it as long as we get to our main goal of putting x_0 in y, which will be used as a recovery key later.
Now use the x_0 stored in y_2 to unmix x_1 to recover y_0 \begin{array}{rcl} x_3 & = & x_1 \oplus y_2 \\ & = & (x_0 \oplus y_0) \oplus x_0\\ & = & y_0 \end{array}

Note that this trick is obsolete for modern computer architecture because

  • it enforces strict dependence that kills any predictive pipeline (speedup) in modern computer architecture, and
  • will yield zero all the time if you try to swap with itself in-place (same memory location), which is wrong because you expect the swap to do nothing.

Adding a check for the degenerate case (self-swap) slows the program down even further, making it worse than using a temporary storage for swapping. Therefore there’s no good reason to use it unless you have an exotic use case.

This is mainly used as a teaching device (or homework problem) to teach that XOR-ing even instances of the same variable in the chain cancels it.

 

Loading

Malware deleting TrustedInstaller.exe, therefore crippling Windows

Posted on by
Reply

My sister’s computer is was infected with a bunch of stubborn malware. Even after cleaning the offending files, a lot of things won’t wouldn’t work.

Windows Update, run sfc /scannow, or DISM /Online /Cleanup-Image fails with unknown reasons, which I found it somehow related to “Windows Module Installer” service not running.

I saw something weird in services.msc: “Windows Module Installer” doesn’t exist, but I know the underlying name is “TrustedIntaller” and noticed a service named as such is there, but it cannot be started, nor there are any descriptive information.

So I searched registry for “TrustedInstaller” and got to its entry. I noticed these two:

[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\services\TrustedInstaller]
"DisplayName"="@%SystemRoot%\\servicing\\TrustedInstaller.exe,-100"
"Description"="@%SystemRoot%\\servicing\\TrustedInstaller.exe,-101"

It means the meaningful names and descriptions I saw on services.msc are generated by calling the underlying  service executable file with switches. I checked my “C:\Windows\servicing” and found that “TrustedInstaller.exe” is not there at all! Of course you cannot start a service where the file does not exist at the promised path (ImagePath).

I searched the hard drive and found only one instance of the file stored somewhere (like C:\Windows\winsxs\x86_microsoft-windows-trustedinstaller_31bf3856ad364e35_6.1.7600.16385_none_90e389a7ae7a4b6c) and I tried to move the file to “C:\Windows\servicing”. However the ownership and permissions to write to “C:\Windows\servicing” goes to “TrustedInstaller” account, not “Administrator”, so I took the ownership, gave Administrator full rights, then move the file over.

Everything worked after that! Just the mere trick of deleting TrustedInstaller.exe is enough to make the user miserable trying to clean the system up! “sfc /scannow” or the like requires TrustedInstaller/WIM to be working in the first place, so you cannot use it to repair TrustedInstaller/WIM problems.

Loading

Floppy Disk Drive Ribbon Cable Orientation

Posted on by
Reply

Hooking up a floppy drive after a decade of disuse today, I followed the notch/key on the connector/cable but it turns out to be incorrect! Turns out I should do the opposite, forcing the key to the side without the notch, by force (or trim the key)!

So stick with the conventional wisdom that the ribbon’s pin 1 (marked) should always stay close to the power connector, regardless of whether it’s IDE or FDD (3.5″ or 5.25″), EVEN IF FOOLPROOF MECHANISMS TELLS YOU OTHERWISE!

 

 

 

Loading