Not long ago, I came over this piece of code. It computes CRC-16 (CCITT polynomial) exquisitely and efficiently. Let’s explore how it works!
u16 update_crc(u16 crc, u8 data) {
data ^= crc >> 8;
data ^= data >> 4;
return (crc << 8) ^ ((u16)data << 12) ^ ((u16)data << 5) ^ (u16)data;
}
Cyclic redundancy check (CRC) is a method of detecting errors in digital communication. You send a checksum along with the data; if the data gets corrupted, the checksum will be wrong.
When dealing with CRC, we represent all numbers as polynomials:
\[0b1011 = 2^3 + 2^1 + 2^0\]Since numers are represented as polynomials, we can divide two numbers using polynomial division.
\[\frac{0b1011}{0b10} = \frac{2^3 + 2^1 + 2^0}{2^1}\]We don’t use regular arithmetic when we carry out the polynomial division. Instead, we use something called finite field arithmetic. There is a lot of information about this topic, so I won’t go into depth. The rules are:
Let’s look at an example of a polynomial division. For clarity, I will not write out the polynomials. The exponent should be inferred from the position of the bit.
6543210 (position / exponent)
1011000 / 1001 = 1010
1001
-------
010000
0000
------
10000
1001
-----
0010
0000
----
010
Now I will focus on CRC-16; however, the concepts are transferable to CRC-8 and CRC-32.
First, we add 2 trailing bytes of zero to our message. Then we divide the message by a fixed number called the CRC polynomial. This will yield a quotient and a remainder. Suppose we subtract the remainder from the original message. In that case, we will end up with something perfectly divisible by our CRC polynomial. This is what we do in CRC.
In the following example, I will use 0b11101000 as the data and 0b10001000000100001 as the CRC polynomial. Keep in mind that the data is padded with 2 bytes.
11101000 00000000 00000000 / 10001000000100001
10001000 00010000 1
--------------------------
1100000 00010000 10000000
1000100 00001000 01
-------------------------
100100 00011000 11000000
100010 00000100 001
------------------------
00110 00011100 11100000
100 01000000 100001
---------------------
10 01011100 01100100
10 00100000 0100001
--------------------
01111100 00100110 (remainder)
Now, if we subtract the remainder from the message, we get something perfectly divisible.
11101000 00000000 00000000 (message)
- 0 01111100 00100110 (remainder)
----------------------------
= 11101000 01111100 00100110
Let’s verify that the remainder is zero.
11101000 01111100 00100110 / 10001000000100001
10001000 00010000 1
--------------------------
1100000 01101100 10100110
1000100 00001000 01
-------------------------
100100 01100100 11100110
100010 00000100 001
------------------------
00110 01100000 11000110
100 01000000 100001
---------------------
10 00100000 01000010
10 00100000 0100001
--------------------
00000000 00000000 Yeyy!
The previous example does only support one byte of data. What happens if we have a stream of bytes? I will explain this by comparing two examples.
Consider a message containing two bytes. The first example will compute the CRC based on the first byte, and the second example computes the CRC based on both bytes.
11101000 00000000 00000000 / 10001000000100001
10001000 00010000 1
--------------------------
1100000 00010000 10000000
1000100 00001000 01
-------------------------
100100 00011000 11000000
100010 00000100 001
------------------------
00110 00011100 11100000
100 01000000 100001
---------------------
10 01011100 01100100
10 00100000 0100001
--------------------
01111100 00100110 (remainder #1)
11101000 10101011 00000000 00000000 / 10001000000100001
10001000 00010000 1
-----------------------------------
1100000 10111011 10000000 00000000
1000100 00001000 01
----------------------------------
100100 10110011 11000000 00000000
100010 00000100 001
---------------------------------
00110 10110111 11100000 00000000
100 01000000 100001
------------------------------
10 11110111 01100100 00000000
10 00100000 0100001
-----------------------------
11010111 00100110 00000000 (remainder after first byte #2)
10001000 00010000 1
--------------------------
1011111 00110110 10000000
1000100 00001000 01
-------------------------
011011 00111110 11000000
10001 00000010 00011
-----------------------
1010 00111100 11010000
1000 10000001 00001
----------------------
010 10111101 11011000
10 00100000 0100001
--------------------
10011101 10011010 (remainder after second byte #3)
The goal is to find the last remainder based on the first remainder and the second data byte.
First some observations:
We see that the second data byte has to be xored into the upper byte in remainder #1 to obtain remainder #2. Here is the general appreach to compute the CRC one byte at the time.
11101000 00000000 00000000 / 10001000000100001
10001000 00010000 1
--------------------------
1100000 00010000 10000000
1000100 00001000 01
-------------------------
100100 00011000 11000000
100010 00000100 001
------------------------
00110 00011100 11100000
100 01000000 100001
---------------------
10 01011100 01100100
10 00100000 0100001
--------------------
01111100 00100110 (remainder #1)
xor 10101011 (xor the with the next data byte)
= 11010111 00100110 (remainder #2)
-> 11010111 00000000 (xor in 00100110 at the end instead)
11010111 00000000 00000000 / 10001000000100001
10001000 00010000 1
--------------------------
1011111 00010000 10000000
1000100 00001000 01
-------------------------
011011 00011000 11000000
10001 00000010 0001
-----------------------
1010 00011010 11010000
1000 10000001 00001
----------------------
010 10011011 11011000
10 00100000 0100001
--------------------
10111011 10011010
xor 00100110 (xor the remaining 00100110)
= 10011101 10011010 Yeyy!
In other words, we start by doing the xor adjustment. Then, we compute
aaaaaaaa 00000000 00000000 % 10001000000100001
and then we do a final xor adjustment.
As we have seen, we want to do the following computation as fast as possible.
aaaaaaaa 00000000 00000000 % 10001000000100001
We start by finding the result of the division. I don’t bother to write out all the zeros, since it does not change the result. Note that xn ^ yn = zn.
x3 x2 x1 x0 y3 y2 y1 y0 0 0 ... / 10001000000100001 = x3 x2 x1 x0 z3 z2 z1 z0
x3 x3
-----------------------
x2 x1 x0 z3 y2 y1 y0
x2 x2
--------------------
x1 x0 z3 z2 y1 y0
x1 x1
-----------------
x0 z3 z2 z1 y0
x0 x0
--------------
z3 z2 z1 z0
z3
-----------
z2 z1 z0
z2
--------
z1 z0
z1
-----
z0
z0
--
As you see, the qoutient is know without carrying out the division. This is how we computeh the quotient in C code.
u8 data = random();
u8 quotient = data ^ (data >> 4);
Now let’s look at how we are going to use this quotient. We know
\[\frac{data - remainder}{divisor} = quotient\]Rewriting yields
\[(quotient * divisor) + remainder = data\]Since we are using finite field math, the plus becomes XOR. We also know that the last 16-bits of data is zero.
\[(quotient * divisor)\ xor\ remainder = aaaaaaaa\ 00000000\ 00000000\]This is only true if
\[(quotient * divisor)\ \&\ 0xFFFF == remainder\]In other words we can find the remainder by multiplying the quotient with the CRC polynomial.
10001000000100001 * xxxxxxxx (quotient)
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
------------------------
Sum = xor these fields
This can be written in C like this:
u16 remainder = ((u16)quotient << 12) ^ ((u16)quotient << 5) ^ (u16)quotient;
Combining all this should explain the code in the start of the post. Hopefully :)