linux-imx

=================================

brief tutorial on CRC computation

=================================

​

A CRC is a long-division remainder.  You add the CRC to the message,

and the whole thing (message+CRC) is a multiple of the given

CRC polynomial.  To check the CRC, you can either check that the

CRC matches the recomputed value, *or* you can check that the

remainder computed on the message+CRC is 0.  This latter approach

is used by a lot of hardware implementations, and is why so many

protocols put the end-of-frame flag after the CRC.

​

It's actually the same long division you learned in school, except that:

​

- We're working in binary, so the digits are only 0 and 1, and

- When dividing polynomials, there are no carries.  Rather than add and

  subtract, we just xor.  Thus, we tend to get a bit sloppy about

  the difference between adding and subtracting.

​

Like all division, the remainder is always smaller than the divisor.

To produce a 32-bit CRC, the divisor is actually a 33-bit CRC polynomial.

Since it's 33 bits long, bit 32 is always going to be set, so usually the

CRC is written in hex with the most significant bit omitted.  (If you're

familiar with the IEEE 754 floating-point format, it's the same idea.)

​

Note that a CRC is computed over a string of *bits*, so you have

to decide on the endianness of the bits within each byte.  To get

the best error-detecting properties, this should correspond to the

order they're actually sent.  For example, standard RS-232 serial is

little-endian; the most significant bit (sometimes used for parity)

is sent last.  And when appending a CRC word to a message, you should

do it in the right order, matching the endianness.

​

Just like with ordinary division, you proceed one digit (bit) at a time.

Each step of the division you take one more digit (bit) of the dividend

and append it to the current remainder.  Then you figure out the

appropriate multiple of the divisor to subtract to being the remainder

back into range.  In binary, this is easy - it has to be either 0 or 1,

and to make the XOR cancel, it's just a copy of bit 32 of the remainder.

​

When computing a CRC, we don't care about the quotient, so we can

throw the quotient bit away, but subtract the appropriate multiple of

the polynomial from the remainder and we're back to where we started,

ready to process the next bit.

​

A big-endian CRC written this way would be coded like::

​

    for (i = 0; i < input_bits; i++) {

        multiple = remainder & 0x80000000 ? CRCPOLY : 0;

        remainder = (remainder << 1 | next_input_bit()) ^ multiple;

    }

​

Notice how, to get at bit 32 of the shifted remainder, we look

at bit 31 of the remainder *before* shifting it.

​

But also notice how the next_input_bit() bits we're shifting into

the remainder don't actually affect any decision-making until

32 bits later.  Thus, the first 32 cycles of this are pretty boring.

Also, to add the CRC to a message, we need a 32-bit-long hole for it at

the end, so we have to add 32 extra cycles shifting in zeros at the

end of every message.

​

These details lead to a standard trick: rearrange merging in the