Cyclic redundancy check 32 checksum

From CodeCodex

Revision as of 07:55, 16 December 2006 by 71.197.105.227 (Talk)

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

Pseudocode

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
}

C

#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 = (unsigned long *)malloc(sizeof(unsigned long) * 256);

        // Was the allocation succesfull?
        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
        if ( crc_table ) { 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 succesfull?
            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 ) ;
}