CRC32 implementation
The basic concept of a CRC is that you treat your bit-string abcdefg... as a ludicrously long polynomial M=a+bx+cx^2+dx^3+... over Z[2]. You then take a modulus polynomial P, and compute the remainder of M on division by P. Thus, an erroneous message N will only have the same CRC if the difference E = M-N is an exact multiple of P. (Note that as we are working over Z[2], M-N = N-M = M+N; but that's not very important.)
What makes the CRC good is choosing P to have good properties:
The CRC32 standard polynomial is
x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x^1+x^0
In fact, we don't compute M mod P; we compute Mx^32 mod P.
The concrete implementation of the CRC is this: we maintain at all times a 32-bit word which is the current remainder of the polynomial mod P. Whenever we receive an extra bit, we multiply the existing remainder by x, add (XOR) the x^32 term thus generated to the new x^32 term caused by the incoming bit, and remove the resulting combined x^32 term if present by replacing it with (P-x^32).
Bit 0 of the word is the x^31 term and bit 31 is the x^0 term. Thus, multiplying by x means shifting right. So the actual algorithm goes like this:
x32term = (crcword & 1) ^ newbit;
crcword = (crcword >> 1) ^ (x32term 0xEDB88320);
In practice, we pre-compute what will happen to crcword on any given sequence of eight incoming bits, and store that in a table which we then use at run-time to do the job:
outgoingplusnew = (crcword & 0xFF) ^ newbyte;
crcword = (crcword >> 8) ^ table[outgoingplusnew];
where table[outgoingplusnew] is computed by setting crcword=0 and then iterating the first code fragment eight times (taking the incoming byte low bit first).
Note that all shifts are rightward and thus no assumption is made about exact word length! (Although word length must be at _least_ 32 bits, but ANSI C guarantees this for `unsigned long' anyway.)
What makes the CRC good is choosing P to have good properties:
- If its first and last terms are both nonzero then it cannot be a factor of any single term x^i. Therefore if M and N differ by exactly one bit their CRCs will guaranteeably be distinct.
- If it has a prime (irreducible) factor with three terms then it cannot divide a polynomial of the form x^i(1+x^j). Therefore if M and N differ by exactly _two_ bits they will have different CRCs.
- If it has a factor (x+1) then it cannot divide a polynomial with an odd number of terms. Therefore if M and N differ by _any odd_ number of bits they will have different CRCs.
- If the error term E is of the form x^iB(x) where B(x) has order less than P (i.e. a short _burst_ of errors) then P cannot divide E (since no polynomial can divide a shorter one), so any such error burst will be spotted.
The CRC32 standard polynomial is
x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x^1+x^0
In fact, we don't compute M mod P; we compute Mx^32 mod P.
The concrete implementation of the CRC is this: we maintain at all times a 32-bit word which is the current remainder of the polynomial mod P. Whenever we receive an extra bit, we multiply the existing remainder by x, add (XOR) the x^32 term thus generated to the new x^32 term caused by the incoming bit, and remove the resulting combined x^32 term if present by replacing it with (P-x^32).
Bit 0 of the word is the x^31 term and bit 31 is the x^0 term. Thus, multiplying by x means shifting right. So the actual algorithm goes like this:
x32term = (crcword & 1) ^ newbit;
crcword = (crcword >> 1) ^ (x32term 0xEDB88320);
In practice, we pre-compute what will happen to crcword on any given sequence of eight incoming bits, and store that in a table which we then use at run-time to do the job:
outgoingplusnew = (crcword & 0xFF) ^ newbyte;
crcword = (crcword >> 8) ^ table[outgoingplusnew];
where table[outgoingplusnew] is computed by setting crcword=0 and then iterating the first code fragment eight times (taking the incoming byte low bit first).
Note that all shifts are rightward and thus no assumption is made about exact word length! (Although word length must be at _least_ 32 bits, but ANSI C guarantees this for `unsigned long' anyway.)
posted by Ajitesh Kumar at 1:36 AM
0 comments
