CRCs are based on the theory of cyclic error-correcting codes. The use of systematic cyclic codes, which encode messages by adding a fixed-length check value, for the purpose of error detection in communication networks was first proposed by W. Wesley Peterson in 1961.[1] Cyclic codes are not only simple to implement but have the benefit of being particularly well suited for the detection of burst errors, contiguous sequences of erroneous data symbols in messages. This is important because burst errors are common transmission errors in many communication channels, including magnetic and optical storage devices. Typically, an n-bit CRC, applied to a data block of arbitrary length, will detect any single error burst not longer than n bits, and will detect a fraction 1-2-n of all longer error bursts.
Specification of a CRC code requires definition of a so-called generator polynomial. This polynomial resembles the divisor in a polynomial long division, which takes the message as the dividend and in which the quotient is discarded and the remainder becomes the result, with the important distinction that the polynomial coefficients are calculated according to the carry-less arithmetic of a finite field. The length of the remainder is always less than the length of the generator polynomial, which therefore determines how long the result can be.
In practice, all commonly used CRCs employ the finite field GF(2). This is the field of two elements, usually called 0 and 1, comfortably matching computer architecture. The rest of this article will discuss only these binary CRCs, but the principles are more general.
The simplest error-detection system, the parity bit, is in fact a trivial 1-bit CRC: it uses the generator polynomial x+1.
Here you are a simple but complete implementation of the crc computation algorithm:
crc.h
/**********************************************************************
*
* Filename: crc.h
*
* Description: A header file describing the various CRC standards.
*
* Notes:
*
*
* Copyright (c) 2000 by Michael Barr. This software is placed into
* the public domain and may be used for any purpose. However, this
* notice must not be changed or removed and no warranty is either
* expressed or implied by its publication or distribution.
**********************************************************************/
#ifndef _crc_h
#define _crc_h
#define FALSE 0
#define TRUE !FALSE
/*
* Select the CRC standard from the list that follows.
*/
#define CRC_CCITT
#if defined(CRC_CCITT)
typedef unsigned short crc;
#define CRC_NAME "CRC-CCITT"
#define POLYNOMIAL 0x1021
#define INITIAL_REMAINDER 0xFFFF
#define FINAL_XOR_VALUE 0x0000
#define REFLECT_DATA FALSE
#define REFLECT_REMAINDER FALSE
#define CHECK_VALUE 0x29B1
#elif defined(CRC16)
typedef unsigned short crc;
#define CRC_NAME "CRC-16"
#define POLYNOMIAL 0x8005
#define INITIAL_REMAINDER 0x0000
#define FINAL_XOR_VALUE 0x0000
#define REFLECT_DATA TRUE
#define REFLECT_REMAINDER TRUE
#define CHECK_VALUE 0xBB3D
#elif defined(CRC32)
typedef unsigned long crc;
#define CRC_NAME "CRC-32"
#define POLYNOMIAL 0x04C11DB7
#define INITIAL_REMAINDER 0xFFFFFFFF
#define FINAL_XOR_VALUE 0xFFFFFFFF
#define REFLECT_DATA TRUE
#define REFLECT_REMAINDER TRUE
#define CHECK_VALUE 0xCBF43926
#else
#error "One of CRC_CCITT, CRC16, or CRC32 must be #define'd."
#endif
void crcInit(void);
crc crcSlow(unsigned char const message[], int nBytes);
crc crcFast(unsigned char const message[], int nBytes);
#endif /* _crc_h */
crc.c
/**********************************************************************
*
* Filename: crc.c
*
* Description: Slow and fast implementations of the CRC standards.
*
* Notes: The parameters for each supported CRC standard are
* defined in the header file crc.h. The implementations
* here should stand up to further additions to that list.
*
*
* Copyright (c) 2000 by Michael Barr. This software is placed into
* the public domain and may be used for any purpose. However, this
* notice must not be changed or removed and no warranty is either
* expressed or implied by its publication or distribution.
**********************************************************************/
#include "crc.h"
/*
* Derive parameters from the standard-specific parameters in crc.h.
*/
#define WIDTH (8 * sizeof(crc))
#define TOPBIT (1 << (WIDTH – 1))
#if (REFLECT_DATA == TRUE)
#undef REFLECT_DATA
#define REFLECT_DATA(X) ((unsigned char) reflect((X), 8))
#else
#undef REFLECT_DATA
#define REFLECT_DATA(X) (X)
#endif
#if (REFLECT_REMAINDER == TRUE)
#undef REFLECT_REMAINDER
#define REFLECT_REMAINDER(X) ((crc) reflect((X), WIDTH))
#else
#undef REFLECT_REMAINDER
#define REFLECT_REMAINDER(X) (X)
#endif
/*********************************************************************
*
* Function: reflect()
*
* Description: Reorder the bits of a binary sequence, by reflecting
* them about the middle position.
*
* Notes: No checking is done that nBits <= 32.
*
* Returns: The reflection of the original data.
*
*********************************************************************/
static unsigned long
reflect(unsigned long data, unsigned char nBits)
{
unsigned long reflection = 0x00000000;
unsigned char bit;
/*
* Reflect the data about the center bit.
*/
for (bit = 0; bit < nBits; ++bit)
{
/*
* If the LSB bit is set, set the reflection of it.
*/
if (data & 0x01)
{
reflection |= (1 << ((nBits – 1) – bit));
}
data = (data >> 1);
return (reflection);
} /* reflect() */
/*********************************************************************
*
* Function: crcSlow()
*
* Description: Compute the CRC of a given message.
*
* Notes:
*
* Returns: The CRC of the message.
*
*********************************************************************/
crc
crcSlow(unsigned char const message[], int nBytes)
{
crc remainder = INITIAL_REMAINDER;
int byte;
unsigned char bit;
/*
* Perform modulo-2 division, a byte at a time.
*/
for (byte = 0; byte < nBytes; ++byte)
{
/*
* Bring the next byte into the remainder.
*/
remainder ^= (REFLECT_DATA(message[byte]) << (WIDTH – 8));
/*
* Perform modulo-2 division, a bit at a time.
*/
for (bit = 8; bit > 0; —bit)
{
/*
* Try to divide the current data bit.
*/
if (remainder & TOPBIT)
{
remainder = (remainder << 1) ^ POLYNOMIAL;
}
else
{
remainder = (remainder << 1);
}
}
}
/*
* The final remainder is the CRC result.
*/
return (REFLECT_REMAINDER(remainder) ^ FINAL_XOR_VALUE);
} /* crcSlow() */
crc crcTable[256];
/*********************************************************************
*
* Function: crcInit()
*
* Description: Populate the partial CRC lookup table.
*
* Notes: This function must be rerun any time the CRC standard
* is changed. If desired, it can be run "offline" and
* the table results stored in an embedded system's ROM.
*
* Returns: None defined.
*
*********************************************************************/
void
crcInit(void)
{
crc remainder;
int dividend;
unsigned char bit;
/*
* Compute the remainder of each possible dividend.
*/
for (dividend = 0; dividend < 256; ++dividend)
{
/*
* Start with the dividend followed by zeros.
*/
remainder = dividend << (WIDTH – 8);
/*
* Perform modulo-2 division, a bit at a time.
*/
for (bit = 8; bit > 0; —bit)
{
/*
* Try to divide the current data bit.
*/
if (remainder & TOPBIT)
{
remainder = (remainder << 1) ^ POLYNOMIAL;
}
else
{
remainder = (remainder << 1);
}
}
/*
* Store the result into the table.
*/
crcTable[dividend] = remainder;
}
} /* crcInit() */
/*********************************************************************
*
* Function: crcFast()
*
* Description: Compute the CRC of a given message.
*
* Notes: crcInit() must be called first.
*
* Returns: The CRC of the message.
*
*********************************************************************/
crc
crcFast(unsigned char const message[], int nBytes)
{
crc remainder = INITIAL_REMAINDER;
unsigned char data;
int byte;
/*
* Divide the message by the polynomial, a byte at a time.
*/
for (byte = 0; byte < nBytes; ++byte)
{
data = REFLECT_DATA(message[byte]) ^ (remainder >> (WIDTH – 8));
remainder = crcTable[data] ^ (remainder << 8);
}
/*
* The final remainder is the CRC.
*/
return (REFLECT_REMAINDER(remainder) ^ FINAL_XOR_VALUE);
} /* crcFast() */
Gg1