How is a CRC32 checksum calculated?

Question

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 the gist of it is that it is the remainder from a non-carry based arithmitic division of the message value, divided by the 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 CRC-32 algorithm is, but he neglects to actually 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.

Anyway, besides that, does somebody have a simple explanation of how it is calculated. I attempted to code in C how the table is formed, and it is included below:

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, but I wanted to understand how they arrived at them.

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

Answer 1

CRC-32 is described in ISO 3309. For some sampe code see http://www.w3.org/TR/PNG-CRCAppendix.html

Answer 2

Start here: http://en.wikipedia.org/wiki/Cyclic_redundancy_check

Answer 3

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.

Answer 4

Wikipedia has a pretty good reference on various ways of implementing CRC checks.