CRC-32 impl

This program is free software.  You can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.

Author

© 2013 Jörg Seebohn

See http://www.riccibitti.com/crcguide.htm.

The input data is converted to a single large binary number.  Then it is divided by the 33 bit number 0x104C11DB7 and the reversed remainder xored with UINT32_MAX becomes the result of CRC-32 computation.

The first byte of the data is the most significant byte of the binary number.  But the bits of the bytes are reversed.  Bit 0 of the first byte is therefore the most significant bit of the number.  The next bit is bit 1 from the first byte.  The 9th bit is bit 0 from the second data byte and so on.

Then the number is divided by the divisor 0x104C11DB7 (polynomial).  The calculation is done modulo 2 on every bit.  This means adding or subtracting two integer values is the same as xoring the two values.  All carry bits are ignored.

Add / Sub Example

  0b1101      0b1101
+ 0b1001    - 0b1001
---------   ---------
  0b0100      0b0100

Both operations result in the same value.  So there is no higher than relation between two numbers if the index of their most significant 1 bit is the same.

Example

The first step is to reverse the bits of every byte and put the bits together as one binary large number: Original data: 0b111111110101010100110011 Reversed data: 0b111111111010101011001100 0x104C11DB7 == 0b100000100110000010001110110110111

Division: (111111111010101011001100 (+ 32 0 bits)) / 100000100110000010001110110110111 = (ignored)
         - 100000100110000010001110110110111
           -------------------------------------
           011111011100101001000010110110111 (remainder)
         -  100000100110000010001110110110111
           -------------------------------------
            011110011111010000001011011011001 (remainder)
         -   100000100110000010001110110110111
           ...

Once the remainder is calculated it is reversed and then xored with 0xffffffff.

To speed up the calculation we consider only one byte value at a time and set all following bits to 0.  After we have calculated the 32-bit remainder of this single byte we subtract it (xor) from the follwing bytes.  This works only cause of subtraction being the xor operation.  Cause (data xor remainder) is the same as (data xor (0 xor remainder)).

Division: (1111111100000000000000000 (+ 32 0 bits)) / 100000100110000010001110110110111 = (ignored)
         - 100000100110000010001110110110111
           -------------------------------------
          ...
                   XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX (remainder)

           000000001010101011001100
         -         XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
         --------------------------------------------
                   YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY
         -         100000100110000010001110110110111
         --------------------------------------------
           ...

To speed things up we do not reverse the input bytes but we can reverse the value of the divisor 0x104C11DB7.  The resulting remainder is theirefore already reversed so we do not need to reverse it before returning it as the final value.

The next thing is to precompute the remainder of every possible input byte and store it in the tabe s_precomputed_crc32.

As a last note.  The CRC-32 computation uses the value 0xffffffff as initialization value for the first remainder.