I know this subject has been up a number of times, but can someone please explain in english (that is, not code) how to calculate the CRC32 value of any given data chunk? I don't mind in-depth mathematical explanations, but I just can't understand pure optimized code when I don't know anything at all about this CRC32 thing.
Posted on 2003-08-26 14:12:09 by Hugin
The basic unoptimized CRC algorithm looks something like this...
crc := SEED

while reading bitstream
shift crc left 1 bit
if input_bit != shifted_out_bit then
crc := crc xor POLYNOMIAL
In hardware, it can be calculated with a circular shift register modified with XOR gates.

The pseudo-code probably explains CRC best. SEED and POLYNOMIAL are specified by whoever dictates the CRC to be used. Bit order of the input is also specified by the CRC dictator. In serial I/O, there is only one order -- the order in which the bits are received/transmitted.

As an example, for USB, one of the CRCs is 16-bit, its seed is all 1's, and the polynomial is X^16 + X^15 + X^2 + 1. The polynomial is translated to a binary number based on the powers of X. So the USB polynomial is a 16-bit number with a 1-bit in positions 0, 2, and 15. The extra "carry out" bit (16) is always specified but never used.
Posted on 2003-08-27 19:26:29 by tenkey
Thank you, this certainly got me started. After understanding the basic concepts, I found this great article on CRCs and the theory behind them:


Check it out.
Posted on 2003-09-01 00:44:11 by Hugin