Cyclic redundancy check 32 checksum

From CodeCodex

A cyclic redundancy check (CRC) is a type of hash function used to produce a checksum - which is a small, fixed number of bits - against a block of data, such as a packet of network traffic or a block of a computer file. The checksum is used to detect errors after transmission or storage. A CRC is computed and appended before transmission or storage, and verified afterwards by recipient to confirm that no changes occurred on transit. CRCs are popular because they are simple to implement in binary hardware, are easy to analyze mathematically, and are particularly good at detecting common errors caused by noise in transmission channels.

Implementations[edit]

Pseudocode[edit]

Since a CRC is fundamentally bit-oriented, the order that you assign to bits in bytes matters. You can do it big-endian:

function crc(bit array bitString[1..len], int polynomial) {
    shiftRegister := initial value // commonly all 0 bits or all 1 bits
    for i from 1 to len {
        if most significant bit of shiftRegister xor bitString[i] = 1 {
            shiftRegister := (shiftRegister left shift 1) xor polynomial
        } else {
            shiftRegister := (shiftRegister left shift 1)
        }
    }
    return shiftRegister
}

Or you can do it little-endian. This turns out to be more convenient in practice, and matches the order of bits sent over RS-232 (so the CRC burst error detection property holds):

function crc(bit array bitString[1..len], int polynomial) {
    shiftRegister := initial value // commonly all 0 bits or all 1 bits
    for i from 1 to len {
        if (least significant bit of shiftRegister) xor bitString[i] = 1 {
            shiftRegister := (shiftRegister right shift 1) xor polynomial
        } else {
            shiftRegister := (shiftRegister right shift 1)
        }
    }
    return shiftRegister
}

There are two convenient optimizations:

  • The bit bitString[i] can be simply XORed into the shiftRegister before the test. It gets shifted away in the next step anyway.
  • The above can be thought of as looking up entry (shiftRegister & 1) in a two-entry table whose entries are 0 and polynomial You can do multiple bits at the same time with a larger table.

C[edit]

#include <stdio.h>

static unsigned long *get_crc_table( unsigned long *crc_table )
{
    // First call to this function? Or after freeing the memory?
    if ( !crc_table )
    {
        // Allocate memory
        crc_table = malloc(sizeof(unsigned long) * 256);

        // Was the allocation successful?
        if ( crc_table )
        {
            // Generate the crc table
            unsigned long crc ;
            int i, j ;

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

    // Return the new pointer
    return crc_table ;
}

unsigned long get_crc32(const char *file)
{
    static unsigned long *crc_table = NULL;
    unsigned long crc = 0;

    // Called with '0'?
    if (!file)
    {
        // If we have a crc table, delete it from memory
        free(crc_table);

        // Set it to a null pointer, the have it (re)created on next calls to this
        // function
        crc_table = NULL;
    }
    else
    {
        // Get the crc table, on first call, generate, otherwise do nothing
        crc_table = get_crc_table( crc_table ) ;
        
        // Do we have a crc table?
        if ( crc_table )
        {
            // Open the file for reading
            FILE *fp = fopen(file, "r");

            // Was the file open successful?
            if (fp)
            {
                // Calculate the checksum
                int ch;
                
                crc = 0xFFFFFFFFUL;
                while ((ch = getc(fp)) != EOF)
                    { crc = (crc>>8) ^ crc_table[ (crc^ch) & 0xFF ]; }

                crc ^= 0xFFFFFFFFUL ;

                // Close the file
                fclose(fp);
            }
        }
    }

    // Return the checksum result
    return crc ;
}