FAQ:I need a CRC algorithm

From Data Compression Wiki

As its name implies (Cyclic Redundancy Check) a crc adds redundancy whereas the topic of this group is to remove it. Yet this question comes up often in comp.compression.

The file ftp://ftp.rocksoft.com/clients/rocksoft/papers/ is a pretty comprehensive description of the whole CRC concept, including a C program.

See also:

• Schwaderer W.D., "CRC Calculation", April 85 PC Tech Journal, pp.118-133.
• "Calculating CRCs by Bits and Bytes", BYTE Magazine, September 1986
• Ramabadran T.V., Gaitonde S.S., "A tutorial on CRC computations", IEEE Micro, Aug 1988.
• the source of all archivers, such as the file makecrc.c in the Info-ZIP sources (see FAQ:What_is_this_.xxx_file_type?#.zip)

For the related topic of Reed-Solomon encoding, see the Error Correcting Codes Home Page http://hideki.iis.u-tokyo.ac.jp/~robert/codes.html

The following C code (by Rob Warnock <rpw3@sgi.com>) does CRC-32 in BigEndian/BigEndian byte/bit order. That is, the data is sent most significant byte first, and each of the bits within a byte is sent most significant bit first, as in FDDI. You will need to twiddle with it to do Ethernet CRC, i.e., BigEndian/LittleEndian byte/bit order. [Left as an exercise for the reader.]

The CRCs this code generates agree with the vendor-supplied Verilog models of several of the popular FDDI "MAC" chips.

u_long crc32_table[256];
/* Initialized first time "crc32()" is called. If you prefer, you can
 * statically initialize it at compile time. [Another exercise.]
 */

u_long crc32(u_char *buf, int len)
{
    u_char *p;
    u_long  crc;

    if (!crc32_table[1])    /* if not already done, */
        init_crc32();   /* build table */
    crc = 0xffffffff;       /* preload shift register, per CRC-32 spec */
    for (p = buf; len > 0; ++p, --len)
        crc = (crc << 8) ^ crc32_table[(crc >> 24) ^ *p];
    return ~crc;            /* transmit complement, per CRC-32 spec */
}

/*
 * Build auxiliary table for parallel byte-at-a-time CRC-32.
 */
#define CRC32_POLY 0x04c11db7     /* AUTODIN II, Ethernet, & FDDI */

init_crc32()
{
    int i, j;
    u_long c;

    for (i = 0; i < 256; ++i) {
        for (c = i << 24, j = 8; j > 0; --j)
            c = c & 0x80000000 ? (c << 1) ^ CRC32_POLY : (c << 1);
        crc32_table[i] = c;
    }
}