CRC programming help needed, CRC32 conversion from the .NET class to C

Question

Code(written in C):

unsigned long chksum_crc32 (unsigned char *block, unsigned int length)
{
   register unsigned long crc;
   unsigned long i;

   crc = 0xFFFFFFFF;
   for (i = 0; i < length; i++)
   {
      crc = ((crc >> 8) & 0x00FFFFFF) ^ crc_tab[(crc ^ *block++) & 0xFF];
   }
   return (crc ^ 0xFFFFFFFF);
}


/* chksum_crc32gentab() --      to a global crc_tab[256], this one will
 *              calculate the crcTable for crc32-checksums.
 *              it is generated to the polynom [..]
 */

void chksum_crc32gentab ()
{
   unsigned long crc, poly;
   int i, j;

   poly = 0xEDB88320L;
   for (i = 0; i < 256; i++)
   {
      crc = i;
      for (j = 8; j > 0; j--)
      {
         if (crc & 1)
         {
            crc = (crc >> 1) ^ poly;
         }
         else
         {
            crc >>= 1;
         }
      }
      crc_tab[i] = crc;
   }
}

For starters; I know how CRC works, first the divisor is calculated with a specified polynomial, then this FCS(frame check sequence) is appended to the data set and sent to the end users system. Once the transfer is finished, the FCS is checked with the same polynomial used to calculate the FCS, and if the remainder of the data with that divisor is zero, then you know the data is correct.

I do not understand the implementation of these two functions. From what I have learned, the function chksum_crc32gentab() generates all the possible hex values the checksum could take with the 32 bit CRC polynomial. One thing I dont get is how poly = 0xEDB88320L; is equivelent to a polynomial. I don't understand the logic in the bottom of this function either. For example, the conditional if (crc & 1), does this mean that for every bit in crc that is 1, compute, otherwise shift right one bit?

I also do not understand chksum_crc32(unsigned char *block, unsigned int length);. Does this function just take in a string of bytes and convert them to the proper crc value computed with the table?. I guess I am confused about the logic it uses within the for loop.

If anyone understands this code an explanation would be great; this does work for the crc32 conversion from the .net class, an example of how data is converted then used by these functions would be something like: (C# source)

      MemoryStream ms = new MemoryStream(System.Text.Encoding.Default.GetBytes(input));

            foreach (byte b in crc32.ComputeHash(ms))
                hash += b.ToString("x2").ToLower();

Here is the original site and project the C code was taken from. http://www.codeproject.com/Articles/35134/How-to-calculate-CRC-in-C

Any explanation would help

Answer 1

Or just google it... Second hit is: http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/libkern/crc32.c

Backporting it from C#'s the hard way to do it, most of these algorithms are already in C.

Answer 2

In CRC calculations, binary polynomials, which are sums of x^n with either a 0 or 1 coefficient, are represented simply as binary words where the position of the 0 or 1 indicates which power of x it is a coefficient of.

0xEDB88320L represents the coefficients of the CRC32 polynomial as 1's where there is an x^n term (except for the x^32 term, which is left out). The CRC32 polynomial (why oh why doesn't stackoverflow have TeX equations like math.stackexchange -- I can't write decent equations here! sigh, sorry for the rant ...) 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

Because of how this CRC is defined with respect to bit-ordering, the lowest coefficients are in the highest bits. So the first E in the hex constant above is 1110 representing (in order from left to right in the bits), 1 + x + x^2.

You can find the construction in the crc32.c source file of zlib, from which a snippet is shown here:

static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};

    /* make exclusive-or pattern from polynomial (0xedb88320UL) */
    poly = 0;
    for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++)
        poly |= (z_crc_t)1 << (31 - p[n]);

    /* generate a crc for every 8-bit value */
    for (n = 0; n < 256; n++) {
        c = (z_crc_t)n;
        for (k = 0; k < 8; k++)
            c = c & 1 ? poly ^ (c >> 1) : c >> 1;
        crc_table[0][n] = c;
    }

The if (crc & 1) or c & 1 ? above looks at the low bit of the CRC at each step before it is shifted away. That is effectively a carry bit for the polynomial subtraction operation, so if it is a one, the polynomial is subtracted (exclusive-ored) from the shifted down polynomial in the CRC (multiplied by x). The CRC is shifted down whether the low bit is 1 or not.

The chksum_crc32() function that you show indeed computes the CRC on the provided block of data. It is the standard table-based approach for CRC calculations on strings of bytes, which indexes the table by the exclusive-or of the data byte and the low byte of the CRC. This does the same thing as shifting in a bit at a time and applying the polynomial for 1 bits, but does it in one step instead of eight. The CRC is effectively multiplied by x^8 (the >> 8), and is exclusive-ored with the effect of exclusive-oring with the polynomial 0 to 8 times at various shifted locations depending on the index value. It is simply a speed trick using a pre-computed table.

You can find even more extreme speed tricks used in zlib's crc32.c that uses larger tables and processes more data a time.