How is a CRC32 checksum calculated?


C Problem Overview

Maybe I'm just not seeing it, but CRC32 seems either needlessly complicated, or insufficiently explained anywhere I could find on the web.

I understand that it is the remainder from a non-carry-based arithmetic division of the message value, divided by the (generator) polynomial, but the actual implementation of it escapes me.

I've read A Painless Guide To CRC Error Detection Algorithms, and I must say it was not painless. It goes over the theory rather well, but the author never gets to a simple "this is it." He does say what the parameters are for the standard CRC32 algorithm, but he neglects to lay out clearly how you get to it.

The part that gets me is when he says "this is it" and then adds on, "oh by the way, it can be reversed or started with different initial conditions," and doesn't give a clear answer of what the final way of calculating a CRC32 checksum given all of the changes he just added.

  • Is there a simpler explanation of how CRC32 is calculated?

I attempted to code in C how the table is formed:

for (i = 0; i < 256; i++)
    temp = i;

    for (j = 0; j < 8; j++)
        if (temp & 1)
            temp >>= 1;
            temp ^= 0xEDB88320;
        else {temp >>= 1;}
    testcrc[i] = temp;

but this seems to generate values inconsistent with values I have found elsewhere on the Internet. I could use the values I found online, but I want to understand how they were created.

Any help in clearing up these incredibly confusing numbers would be very appreciated.

C Solutions

Solution 1 - C

The polynomial for CRC32 is:

> > > x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

Or in hex and binary:

> 0x 01 04 C1 1D B7
> 1 0000 0100 1100 0001 0001 1101 1011 0111

The highest term (x32) is usually not explicitly written, so it can instead be represented in hex just as

> 0x 04 C1 1D B7

Feel free to count the 1s and 0s, but you'll find they match up with the polynomial, where 1 is bit 0 (or the first bit) and x is bit 1 (or the second bit).

Why this polynomial? Because there needs to be a standard given polynomial and the standard was set by IEEE 802.3. Also it is extremely difficult to find a polynomial that detects different bit errors effectively.

You can think of the CRC-32 as a series of "Binary Arithmetic with No Carries", or basically "XOR and shift operations". This is technically called Polynomial Arithmetic.

To better understand it, think of this multiplication:

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
 + x^5 + x^3 + x^2
 + x^3 + x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

If we assume x is base 2 then we get:

x^7 + x^3 + x^2 + x^1 + x^0

Why? Because 3x^3 is 11x^11 (but we need only 1 or 0 pre digit) so we carry over:

=1x^110 + 1x^101 + 1x^100          + 11x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^100 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^101          + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^110                   + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^111                            + 1x^11 + 1x^10 + 1x^1 + x^0

But mathematicians changed the rules so that it is mod 2. So basically any binary polynomial mod 2 is just addition without carry or XORs. So our original equation looks like:

=( 1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0 ) MOD 2
=( 1x^110 + 1x^101 + 1x^100 +  1x^11 + 1x^10 + 1x^1 + x^0 )
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 (or that original number we had)

I know this is a leap of faith but this is beyond my capability as a line-programmer. If you are a hard-core CS-student or engineer I challenge to break this down. Everyone will benefit from this analysis.

So to work out a full example:

   Original message                : 1101011011
   Polynomial of (W)idth 4         :      10011
   Message after appending W zeros : 11010110110000

Now we divide the augmented Message by the Poly using CRC arithmetic. This is the same division as before:

            1100001010 = Quotient (nobody cares about the quotient)
10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
=Poly   10011,,.,,....
                  1110 = Remainder = THE CHECKSUM!!!!

The division yields a quotient, which we throw away, and a remainder, which is the calculated checksum. This ends the calculation. Usually, the checksum is then appended to the message and the result transmitted. In this case the transmission would be: 11010110111110.

Only use a 32-bit number as your divisor and use your entire stream as your dividend. Throw out the quotient and keep the remainder. Tack the remainder on the end of your message and you have a CRC32.

Average guy review:

                 = REMAINDER
  1. Take the first 32 bits.
  2. Shift bits
  3. If 32 bits are less than DIVISOR, go to step 2.
  4. XOR 32 bits by DIVISOR. Go to step 2.

(Note that the stream has to be dividable by 32 bits or it should be padded. For example, an 8-bit ANSI stream would have to be padded. Also at the end of the stream, the division is halted.)

Solution 2 - C

For IEEE802.3, CRC-32. Think of the entire message as a serial bit stream, append 32 zeros to the end of the message. Next, you MUST reverse the bits of EVERY byte of the message and do a 1's complement the first 32 bits. Now divide by the CRC-32 polynomial, 0x104C11DB7. Finally, you must 1's complement the 32-bit remainder of this division bit-reverse each of the 4 bytes of the remainder. This becomes the 32-bit CRC that is appended to the end of the message.

The reason for this strange procedure is that the first Ethernet implementations would serialize the message one byte at a time and transmit the least significant bit of every byte first. The serial bit stream then went through a serial CRC-32 shift register computation, which was simply complemented and sent out on the wire after the message was completed. The reason for complementing the first 32 bits of the message is so that you don't get an all zero CRC even if the message was all zeros.

Solution 3 - C

I published a tutorial on CRC-32 hashes, here: CRC-32 hash tutorial - AutoHotkey Community

In this example from it, I demonstrate how to calculate the CRC-32 hash for the 'ANSI' (1 byte per character) string 'abc':

calculate the CRC-32 hash for the 'ANSI' string 'abc':

dividend: binary for 'abc': 0b011000010110001001100011 = 0x616263
polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7

start with the 3 bytes 'abc':
61 62 63 (as hex)
01100001 01100010 01100011 (as bin)

reverse the bits in each byte:
10000110 01000110 11000110

append 32 0 bits:

XOR (exclusive or) the first 4 bytes with 0xFFFFFFFF:
(i.e. flip the first 32 bits:)

next we will perform 'CRC division':

a simple description of 'CRC division':
we put a 33-bit box around the start of a binary number,
start of process:
if the first bit is 1, we XOR the number with the polynomial,
if the first bit is 0, we do nothing,
we then move the 33-bit box right by 1 bit,
if we have reached the end of the number,
then the 33-bit box contains the 'remainder',
otherwise we go back to 'start of process'

note: every time we perform a XOR, the number begins with a 1 bit,
and the polynomial always begins with a 1 bit,
1 XORed with 1 gives 0, so the resulting number will always begin with a 0 bit

'CRC division':
'divide' by the polynomial 0x104C11DB7:

we obtain the 32-bit remainder:
0b10111100011111011101101101010011 = 0xBC7DDB53

note: the remainder is a 32-bit number, it may start with a 1 bit or a 0 bit

XOR the remainder with 0xFFFFFFFF:
(i.e. flip the 32 bits:)
0b01000011100000100010010010101100 = 0x438224AC

reverse bits:
bit-reverse the 4 bytes (32 bits), treating them as one entity:
(e.g. 'abcdefgh ijklmnop qrstuvwx yzABCDEF'
to 'FEDCBAzy xwvutsrq ponmlkji hgfedcba':)
0b00110101001001000100000111000010 = 0x352441C2

thus the CRC-32 hash for the 'ANSI' string 'abc' is: 0x352441C2

Solution 4 - C

A CRC is pretty simple; you take a polynomial represented as bits and the data, and divide the polynomial into the data (or you represent the data as a polynomial and do the same thing). The remainder, which is between 0 and the polynomial is the CRC. Your code is a bit hard to understand, partly because it's incomplete: temp and testcrc are not declared, so it's unclear what's being indexed, and how much data is running through the algorithm.

The way to understand CRCs is to try to compute a few using a short piece of data (16 bits or so) with a short polynomial -- 4 bits, perhaps. If you practice this way, you'll really understand how you might go about coding it.

If you're doing it frequently, a CRC is quite slow to compute in software. Hardware computation is much more efficient, and requires just a few gates.

Solution 5 - C

In addition to the Wikipedia Cyclic redundancy check and Computation of CRC articles, I found a paper entitled Reversing CRC - Theory and Practice* to be a good reference.

There are essentially three approaches for computing a CRC: an algebraic approach, a bit-oriented approach, and a table-driven approach. In Reversing CRC - Theory and Practice*, each of these three algorithms/approaches is explained in theory accompanied in the APPENDIX by an implementation for the CRC32 in the C programming language.

* PDF Link
Reversing CRC – Theory and Practice.
HU Berlin Public Report
May 2006
Martin Stigge, Henryk Plötz, Wolf Müller, Jens-Peter Redlich

Solution 6 - C

Then there is always Rosetta Code, which shows crc32 implemented in dozens of computer languages. and has links to many explanations and implementations.

Solution 7 - C

In order to reduce crc32 to taking the reminder you need to:

  1. Invert bits on each byte
  2. xor first four bytes with 0xFF (this is to avoid errors on the leading 0s)
  3. Add padding at the end (this is to make the last 4 bytes take part in the hash)
  4. Compute the reminder
  5. Reverse the bits again
  6. xor the result again.

In code this is:

func CRC32 (file []byte) uint32 {
	for i , v := range(file) {
		file[i] = bits.Reverse8(v)
	for i := 0; i < 4; i++ {
		file[i] ^= 0xFF

	// Add padding
	file = append(file, []byte{0, 0, 0, 0}...)
	newReminder := bits.Reverse32(reminderIEEE(file))

	return newReminder ^ 0xFFFFFFFF

where reminderIEEE is the pure reminder on GF(2)[x]


All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionaquanarView Question on Stackoverflow
Solution 1 - Cuser295190View Answer on Stackoverflow
Solution 2 - CPavlo BobrekView Answer on Stackoverflow
Solution 3 - CvafylecView Answer on Stackoverflow
Solution 4 - CWhirlWindView Answer on Stackoverflow
Solution 5 - CjschmierView Answer on Stackoverflow
Solution 6 - Cdon brightView Answer on Stackoverflow
Solution 7 - CGabriel FurstenheimView Answer on Stackoverflow