Durand’s Home Page

Generating 32 bit CRC Checksums

The following method demonstrates a technique for generating 32 bit (4 byte) CRC values for any file. I’ve seen various techniques for doing this and some don’t work or don’t comply with the standard. The technique below generates values equivalent to WinZip.

nb: A lot of the code on this page I just coded straight into the html document so I don’t expect it to compile but you can fix the little errors as an exercise.

Reflection

First of all, reflection is a requirement of the CRC standard. This means that the values used should be reflected and so an 8 bit value will have bit 0 swapped with bit 7, bit 1 swapped with bit 6, 2 with 5, etc. Example: 11010000b ?> 00001011b

So let’s define a function that does this for us:

          // value - the value to be reflected
          // size - the size of the value ( char = 8 )
          unsigned long reflect( unsigned long value, int size )
          {
             unsigned long new;
             unsigned long old;
             int i;

             new = 0;
             old = value;

             for(int i = 1; i < (size + 1); i++)
             {
               if ((old & 1) == 1)
                 new = new | (1 << (size - i));

               old = old >> 1;
             }

             return new;
          }

WinZip,PkZip,Ethernet CRC polynomial = 0x04c11db7

CRC Lookup Table

In order to speed things up, we can generate a little table beforehand so that we don’t have to recalculate our values whenever we need them. Here. Let’s do that.

         unsigned long CRC_Table[256];
         unsigned long poly = 0x04c11db7;

         void Generate_Lookup_Table()
         {
           int i, j;

           for(i = 0; i < 256; i++)
           {
              CRC_Table[i] = reflect(i,  << 24;
              for (j = 0; j < 8; j++)
                  CRC_Table[i] = (CRC_Table[i] << 1)
                               ^ (CRC_Table[i] & (1 << 31) ?
                                 poly : 0);
              CRC_Table[i] = reflect(CRC_Table[i], 32);
           }
         }

Calculating the CRC of a char buffer

Now, let’s assume you have a nice little stretch of memory that you would like to find the CRC value of and use it to validate it later. The stretch of memory is unsigned, chars and we know the length of it.

We first start off with a CRC value of 0xFFFFFFFF and step through the buffer, char by char, doing a little calculation until we reach the end. The calculation is nice and simple: (crc >> ^ CRC_Table[ (crc & 0xFF) ^ *buffer++ ]; Once that is done, we just XOR the crc value with 0xFFFFFFFF again and return it.

I don’t know if I explained that very well. Let’s demonstrate it in the code.

         unsigned long bufferCRC( unsigned char *buf, unsigned long size)
         {
           unsigned long crc;
           unsigned long len;
           unsigned char * buffer;

           crc = 0xFFFFFFFF;
           buffer = buf;
           len = size;

           while (len--)
              crc = (crc >>  ^ CRC_Table[ (crc & 0xFF) ^ *buffer++];

           return (crc ^ 0xFFFFFFFF);
         }

Calculating the CRC of a file

Okay, so this is the easy part now. We already know how to calculate the CRC of a buffer. All that we need to do is expand this to a file and this is really simple. We just need to load the file into a buffer and then calculate the CRC of that buffer which, indirectly (in a very direct way), returns the CRC of the file. You can do this. I don’t know the file calls off the top of my head. It’s easy. Obviously, you can improve on this technique a lot according to your requirements.

Summary

• Generate the CRC lookup table.
• Open the file and load it into memory.
• Calculate the CRC of the file buffer.

References

• Create Window Programming Section – A huge thanks to this site as I’ve mostly just reproduced their page in my own words. As time goes by I’ll change this page to suit my style more and the two sources will diverge a lot more.