CODEWITHSUNDEEP
crccrc32
Rolando
Rolando

Reputation: 62596

How does 0x04C11DB7L represent a polynomial?

I was looking at CRC, and stumbled upon: https://www.naaccr.org/wp-content/uploads/2017/12/C-API-Implementation-CRC32.c

I understand CRC needs to have a 'magic' polynomial to generate lookup tables for CRC. I see that the parameter for 'Poly-nomial' is:

0x04C11DB7L

How does this value represent a polynomial?

Upvotes: 1

Views: 5422

Answers (2)

Georgii Firsov
Georgii Firsov

Reputation: 306

As for me, it is quite elegant way to represent a polynomial. It works in the following way:

You have a hexadecimal number, e.g. 0x04C11DB7. It can be converted into the binary number: 0b100110000010001110110110111.

Let's consider each bit to be a coefficient before the corresponding power of x. The least significant bit corresponds to the 0'th power (i.e. term 1). In addition, the greatest power is omitted in binary representation, in our case hex-number is 32 bits long, hence 32'nd power of x is omitted.

Now we can write down the polynomial that is represented via 0x04C11DB7:

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

Upvotes: 5

IMSoP
IMSoP

Reputation: 97648

The constant you mention appears in the source as part of this comment:

/* The following CRC lookup table was generated automagically    */
/* by the Rocksoft^tm Model CRC Algorithm Table Generation       */
/* Program V1.0 using the following model parameters:            */
/*                                                               */
/*    Width   : 4 bytes.                                         */
/*    Poly    : 0x04C11DB7L                                      */
/*    Reverse : TRUE.                                            */
/*                                                               */
/* For more information on the Rocksoft^tm Model CRC Algorithm,  */
/* see the document titled "A Painless Guide to CRC Error        */
/* Detection Algorithms" by Ross Williams                        */

Plugging that paper name and author into a search engine turned up the author's "CRC Pitstop" website (gloriously untouched since 1996!) which hosts a copy of the paper in question.

It describes the "polynomial arithmetic" that CRC algorithms use, but then points out that you don't actually have to understand that part of the theory to understand or implement the arithmetic itself.

The key operation is actually just a special form of division, the free parameter which needs to be chosen is the divisor, and the checksum is the remainder after dividing the input by that parameter.

The use of "Poly" as the parameter name in the table generation algorithm turns out not to be a general abbreviation, but a deliberate choice of term to downplay the role of polynomial arithmetic:

To perform a CRC calculation, we need to choose a divisor. In maths marketing speak the divisor is called the "generator polynomial" or simply the "polynomial", and is a key parameter of any CRC algorithm. It would probably be more friendly to call the divisor something else, but the poly talk is so deeply ingrained in the field that it would now be confusing to avoid it. As a compromise, we will refer to the CRC polynomial as the "poly". Just think of this number as a sort of parrot. "Hello poly!"

So, far from being "a magic polynomial used to derive the lookup tables", the parameter is simply a number which you're going to use in a division operation. As the paper goes on to describe, the lookup tables are simply a way of optimising the long division - essentially, the values are various copies of the "poly" bit-shifted and XOR'd against one another to handle multiple bits of the input at once.

Upvotes: 4

Related Questions