Applicable Uses of the XOR Operator

November 4, 2018 by eclair   (0) Comments

Today I’m here to talk about my love affair with the logical Exclusive-Or (XOR). Some pronounce is “ex-or”, others pronounce it “ZOR”. Either way, I am dedicating my time this year to blogging about bit manipulation. I do this in hope that some soul out there, digging up boolean algebra topics like I did, will stumble across my work. I hope I can provide engaging material to somebody out there, who shares in my fascination with bit manipulation.

As a primer, for those of you who are unfamiliar with boolean algebra, or for those who need a refresher:

What is the logical XOR?

An XOR is an operator. There are operators in arithmetic that you’re definitely familiar with. 
+, −, ÷, ×

The addition operator +, takes two inputs, and yields one result.

The XOR operator has two inputs, and one output as well. This is a common way that XOR is represented: ⊕

Rather than accepting base 10 values (1,2,3,…9), it accepts inputs that are either true or false. Each input will be either a 1 or a 0.

The rules for an XOR operator are simple.

Now we will move onto the interesting stuff. I’ll go over some use-cases of the XOR in computing.

___________________________________________________________________

1. CHECKSUM (Network Security)
2. RAID Drive Backups (Systems)

___________________________________________________________________

Case 1. Checksum

What is a checksum?

Its a method of confirming the integrity of a file, after it has been in transit. A checksum is a mathematical output that will help you confirm whether or not a file has been corrupted or tampered with.

Suppose you have a file, it could be an mp3, a jpg or even an executable. The file needs to transfer from a local machine to a remote machine. If the receiver wanted to ensure this was a trusted file, we can confirm its integrity through a checksum. Every file is composed of unique binary data. If even a single character is missing, or changed from the original string of binary data, the entire file is corrupted.

When a file is being transferred from server A to server B, its cut into blocks, sent over piece by piece, then re-attached at its destination. To ensure each block is not corrupted, a checksum function is ran on it, generating a unique CHECKSUM. All of these ASCII symbols are then interpreted in base 2 (1’s and 0’s), and each chunk is XOR-ed together.

What is the outcome?

This gives us a XOR result, or a unique checksum string of 1’s and 0’s. When the file is reattached and written to disk on the other server, it can reference the checksum generated by the source server, to ensure it hasn’t been corrupted. In the above example, if the file had not been corrupted during transit (downloading), the checksum of your downloaded copy would’ve been identical to the checksum of the original file on the server.

Case 2. RAID Drive Backups

Nowadays, nearly every household has an external hard drive, and backs up computer files in some manner. You can never predict what will happen tomorrow, so its better to safe than sorry and backup your files.

A standard user will make a 1:1 backup, meaning for every set of files, you will create one backup on a form of external memory.

But what happens when you are in the business of data warehousing, and are responsible for thousands of hard drives? The naive solution would be to create one backup for every one set of user files. Thus for 300 hard drives, you will create 300 backups. This works, but it will become very expensive, very quickly.

Let’s go over a thought experiment. What if I told you that instead of purchasing N disk drives to back up N servers (filled at capacity), we could do it in < N? I’m here to introduce an industry-standard hard disk configuration known as RAID 5.

For simplicity’s sake, lets pretend we have very tiny disks, which have a capacity of 8 bytes each. Each disk is nearly full, and holds a single text file.

Here are the three files:

Thanks to the magical property of XOR, all three of these server’s contents can be recovered through, not three backup hard drives, but one single parity drive. The XOR will work in a similar fashion to the checksum we covered in the previous case. When we XOR together the contents of the three hard drives, we get the following:

Tomorrow, a disk failure happens with server 2. The contents of server 2 have gone missing. How do we recover it? We crack open the parity disk, which contains the XOR of the three servers. Hidden inside “01101001 00100111 01101101 00111111 01100111 01101001 01100101 01101000 00001010” is the original content of the destroyed server.

How do we fish back out the data of server 2 from this parity disk? The key to retrieving it is to use server 1 and server 3, its partners in creating the parity disk.

We will XOR together the binary data of:

• File 1
• File 3
• Parity Disk

To obtain the original contents of:

• File 2

The rest is all mathematical.

File 1 ⊕ File 3 ⊕ Parity Disk == Recovered Data

Using these seemingly mysterious properties of XOR, we have managed to recover the contents of server 2.

Assuming in a world with minimal complications, we don’t lose more than 1 input disk at a time, out of these groups of 3 servers, we could backup an entire data center of 300 disks, using only 100, as opposed to 300. We could do even less than 100, if we wanted to risk it at XOR more disks together, etc. But keep in mind, one fault of RAID5 is that if you lose more than 1 disk in a grouping, the parity disk will become useless. There are some other recovery solutions you can architect in the event of a disaster, but thats a conversation for a future article, when I move into a systems architecture discussion. 🙂

If you’re interested in more bit manipulation content, I’ll have some future posts coming up! More surprises yet to come…

-Claire Y. Li, Computer Scientist