How is the CRC32 checksum calculated?

Question

Maybe I just don’t see it, but CRC32 seems either too complicated or not adequately explained wherever I am on the Internet.

I understand that this is the remainder of the arithmetic division of the message value, not based on hyphenation, divided by a polynomial (generator), but the actual implementation of this eludes me.

I read the "Painless Guide to CRC Error Detection Algorithms" and I must say that it was not painless. It fits the theory pretty well, but the author never comes to the simple "that's it." He says what these parameters are for the standard CRC32 algorithm, but he neglects to clearly state how you approach him.

The part that gets me is when he says “that's all”, and then adds: “Oh, by the way, it can be changed or can start from other initial conditions”, and does not give a clear answer about what the final path is. CRC32 checksum calculation taking into account all the changes that he just added.

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

I tried 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 it seems to generate values ​​that are incompatible with the values ​​that I found elsewhere on the Internet. I could use the values ​​that I found on the Internet, but I want to understand how they were created.

Any help in figuring out these incredibly confusing numbers would be greatly appreciated.

Answer 1

Polynomial for CRC32:

x ³² + x ²⁶ + x ²³ + x ²² + x ¹⁶ + x ¹² + x ¹¹ + x ¹⁰ + x ⁸ + x ⁷ + x ⁵ + x ⁴ + x ² + x + 1

• Wikipedia
• CRC calculation

Or in hexadecimal and binary:

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

The largest member (x ³² ) is usually not written explicitly, so it can be represented in hexadecimal just like

0x 04 C1 1D B7

Feel free to count 1 and 0, but you will find that they coincide with the polynomial, where 1 is bit 0 (or first bit) and x is bit 1 (or second bit).

Why is this polynomial? Because there must be a standard defined by a polynomial, and the standard has been set by IEEE 802.3. It is also extremely difficult to find a polynomial that efficiently detects various bit errors.

You can think of CRC-32 as a series of “Binary hyphenation-free arithmetic” or basically “XOR and shift operations”. This is technically called polynomial arithmetic.

• CRC Primer, Chapter 5

To better understand this, think about 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 that x is base 2, then we get:

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

• CRC primer Chp.5

What for? Since 3x ^ 3 is 11x ^ 11 (but we only need 1 or 0 preliminary digits), so we transfer:

 =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 have changed the rules so that it’s mod 2. Thus, any binary polynomial mod 2 is just addition without hyphenation or XOR. So, our original equation looks like this:

 =( 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 it is beyond my ability as a linear programmer. If you are an experienced CS student or engineer, I challenge to break it. Everyone will benefit from this analysis.

So, to work through a complete example:

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

Now we will split the extended message into 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,,.,,.... -----,,.,,.... 10011,.,,.... 10011,.,,.... -----,.,,.... 00001.,,.... 00000.,,.... -----.,,.... 00010,,.... 00000,,.... -----,,.... 00101,.... 00000,.... -----,.... 01011.... 00000.... -----.... 10110... 10011... -----... 01010.. 00000.. -----.. 10100. 10011. -----. 01110 00000 ----- 1110 = Remainder = THE CHECKSUM!!!! 

The division gives the quotient that we discard and the remainder, which is the calculated checksum. This ends the calculation. Typically, the checksum is then added to the message and the result is transmitted. In this case, the transfer will be: 11010110111110.

• CRC Primer, Chapter 7

Use only a 32-bit number as a divisor, and use the entire stream as a dividend. Throw away the quotient and leave the rest. Attach the remainder at the end of your message and you will have CRC32.

Average guy review:

  QUOTIENT ---------- DIVISOR ) DIVIDEND = 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 from DIVISOR. Go to step 2.

(Note that the stream must be divided by 32 bits, or it must be supplemented. For example, the 8-bit ANSI stream must be supplemented. Also, at the end of the stream, separation is stopped.)

Answer 2

CRC is pretty simple; you take a polynomial represented as bits and data and divide the polynomial into data (or you present the data as a polynomial and do the same). The remainder that lies between 0 and the polynomial is CRC. Your code is a little difficult to understand, partly because it is incomplete: temp and testcrc are not declared, so it is not clear what is indexed and how much data is executed through the algorithm.

A way to understand CRC is to try to compute a few using a short piece of data (16 bits or so) with a short polynomial - 4 bits each. If you practice this path, you will really understand how you can code it.

If you do this often, CRC computes quite slowly in software. Hardware computing is much more efficient and requires only a few gates.

Answer 3

For IEEE802.3, CRC-32. Think of the whole message as a sequential bit stream, add 32 zeros to the end of the message. Then you MUST expand the bits of EVERY byte of the message and make 1 pad of the first 32 bits. Now divide by the polynomial CRC-32, 0x104C11DB7. Finally, you must 1 pad the 32-bit remainder of this division, bit-reverse each of the 4 bytes of the remainder. This becomes a 32-bit CRC that is appended to the end of the message.

The reason for this strange procedure is that the first Ethernet implementations will serialize the message one byte at a time and transmit the least significant bit of each byte first. The serial bitstream then went through the serial CRC-32 shift register, which was simply augmented and sent to the wire after the message was completed. The reason to supplement the first 32 bits of the message is because you are not getting a zero CRC, even if the message was zero.

Answer 4

In addition to Wikipedia's Cyclic Redundancy Check and CRC Calculation , I found an article called Reverse CRC - Theory and Practice ^* to be a good reference.

There are three approaches to calculating CRC: an algebraic approach, a bit-oriented approach, and a table-based approach. In Reversible CRC - Theory and Practice ^* each of these three algorithms / approaches is explained in the theory, followed in the APPENDIX by an implementation for CRC32 in the C programming language.

^{* PDF link
CRC reversal - theory and practice.
HU Berlin Public Report
SAR-PR-2006-05
May 2006
Authors:
Martin Stigg, Henrik Ploetz, Wolf Muller, Jens-Peter Redlich}

Answer 5

I spent some time trying to uncover the answer to this question, and finally published a CRC-32 tutorial : CRC-32 hash tutorial - AutoHotkey Community

In this example, from it I will demonstrate how to calculate the CRC-32 hash for the ASCII string 'abc':

 calculate the CRC-32 hash for the ASCII string 'abc': inputs: dividend: binary for 'abc': 0b011000010110001001100011 = 0x616263 polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7 011000010110001001100011 reverse bits in each byte: 100001100100011011000110 append 32 0 bits: 10000110010001101100011000000000000000000000000000000000 XOR the first 4 bytes with 0xFFFFFFFF: 01111001101110010011100111111111000000000000000000000000 'CRC division': 01111001101110010011100111111111000000000000000000000000 100000100110000010001110110110111 --------------------------------- 111000100010010111111010010010110 100000100110000010001110110110111 --------------------------------- 110000001000101011101001001000010 100000100110000010001110110110111 --------------------------------- 100001011101010011001111111101010 100000100110000010001110110110111 --------------------------------- 111101101000100000100101110100000 100000100110000010001110110110111 --------------------------------- 111010011101000101010110000101110 100000100110000010001110110110111 --------------------------------- 110101110110001110110001100110010 100000100110000010001110110110111 --------------------------------- 101010100000011001111110100001010 100000100110000010001110110110111 --------------------------------- 101000011001101111000001011110100 100000100110000010001110110110111 --------------------------------- 100011111110110100111110100001100 100000100110000010001110110110111 --------------------------------- 110110001101101100000101110110000 100000100110000010001110110110111 --------------------------------- 101101010111011100010110000001110 100000100110000010001110110110111 --------------------------------- 110111000101111001100011011100100 100000100110000010001110110110111 --------------------------------- 10111100011111011101101101010011 remainder: 0b10111100011111011101101101010011 = 0xBC7DDB53 XOR the remainder with 0xFFFFFFFF: 0b01000011100000100010010010101100 = 0x438224AC reverse bits: 0b00110101001001000100000111000010 = 0x352441C2 thus the CRC-32 hash for the ASCII string 'abc' is 0x352441C2