6.3.2 Cyclic Redundancy Codes
A cyclic redundancy code (CRC) is a specific checksum algorithm that is designed to detect the most common data errors. The theory behind the CRC is quite mathematical and beyond the scope of this book. However, cyclic redundancy codes are frequently useful in embedded applications that require the storage or transmission of large blocks of data. What follows is a brief explanation of the CRC technique and some source code that shows how it can be done in C. Thankfully, you don't need to understand why CRCs detect data errors — or even how they are implemented — to take advantage of their ability to detect errors.
Here's a very brief explanation of the mathematics. When computing a CRC, you consider the set of data to be a very long string of 1's and 0's (called the message). This binary string is divided — in a rather peculiar way — by a smaller fixed binary string called the generator polynomial. The remainder of this binary long division is the CRC checksum. By carefully selecting the generator polynomial for certain desirable mathematical properties, you can use the resulting checksum to detect most (but never all) errors within the message. The strongest of these generator polynomials are able to detect all single and double bit errors, and all odd-length strings of consecutive error bits. In addition, greater than 99.99% of all burst errors — defined as a sequence of bits that has one error at each end — can be detected. Together, these types of errors account for a large percentage of the possible errors within any stored or transmitted binary message.
Those generator polynomials with the very best error-detection capabilities are frequently adopted as international standards. Three such standards are parameterized in Table 6-4. Associated with each standard are its width (in bits), the generator polynomial, a binary representation of the polynomial called the divisor, an initial value for the remainder, and a value to XOR (exclusive or) with the final remainder.[15]
Table 6-4. International Standard Generator Polynomials
| CCITT | CRC16 | CRC32 | |
|---|---|---|---|
| Checksum size (width) | 16 bits | 16 bits | 32 bits |
| Generator polynomial | x16+x^1^2+x5+1 | x16+x15+x^2+1 | x^3^2+x26+x^2^3+ x^2^2+x16+ x^1^2+x^1^1+x^1o+x8+x7+x5+x4+x^2+x^1+1 |
| Divisor (polynomial) | 0x1021 | 0x8005 | 0x04C11DB7 |
| Initial remainder | 0xFFFF | 0x0000 | 0xFFFFFFFF |
| Final XOR value | 0x0000 | 0x0000 | 0xFFFFFFFF |
The code that follows can be used to compute any CRC formula that has a similar set of parameters.[16]
To make this as easy as possible, I have defined all of the CRC parameters as constants. To change to the CRC16 standard, simply change the values of the three constants. For CRC32, change the three constants and redefine width as type unsignedlong.
/*
* The CRC parameters. Currently configured for CCITT.
* Simply modify these to switch to another CRC standard.
*/
#define POLYNOMIAL 0x1021
#define INITIAL_REMAINDER 0xFFFF
#define FINAL_XOR_VALUE 0x0000
/*
* The width of the CRC calculation and result.
* Modify the typedef for an 8 or 32-bit CRC standard.
*/
typedef unsigned short width;
#define WIDTH (8 * sizeof(width))
#define TOPBIT (1 << (WIDTH – 1))
The function crcInit should be called first. It implements the peculiar binary division required by the CRC algorithm. It will precompute the remainder for each of the 256 possible values of a byte of the message data. These intermediate results are stored in a global lookup table that can be used by the crcCompute function. By doing it this way, the CRC of a large message can be computed a byte at a time rather than bit by bit. This reduces the CRC calculation time significantly.
/*
* An array containing the pre-computed intermediate result for each
* possible byte of input. This is used to speed up the computation.
*/
width crcTable[256];
/**********************************************************************
*
* Function: crcInit()
*
* Description: Initialize the CRC lookup table. This table is used
* by crcCompute() to make CRC computation faster.
*
* Notes: The mod-2 binary long division is implemented here.
*
* Returns: None defined.
*
**********************************************************************/
void crcInit(void) {
width remainder;
width dividend;
int bit;
/*
* Perform binary long division, a bit at a time.
*/
for (dividend = 0; dividend < 256; dividend++) {
/*
* Initialize the remainder.
*/
remainder = dividend << (WIDTH – 8);
/*
* Shift and XOR with the polynomial.
*/
for (bit = 0; bit < 8; bit++) {
/*
* Try to divide the current data bit.
*/
if (remainder & TOPBIT) {
remainder = (remainder << 1) ^ POLYNOMIAL;
} else {
remainder = remainder << 1;
}
}
/*
* Save the result in the table.
*/
crcTable[dividend] = remainder;
}
} /* crcInit() */
Finally, we arrive at the actual workhorse routine, crcCompute. This is a routine that you can call over and over from your application to compute and verify CRC checksums. An additional benefit of splitting the computation between crcInit and crcCompute is that the crcInit function need not be executed on the embedded system. Instead, this function can be run in advance — on any computer — to produce the contents of the lookup table. The values in the table can then be stored in ROM (requiring only 256 bytes of storage) and referenced over and over by crcCompute.
/**********************************************************************
*
* Function: crcCompute()
*
* Description: Compute the CRC checksum of a binary message block.
*
* Notes: This function expects that crcInit() has been called
* first to initialize the CRC lookup table.
*
* Returns: The CRC of the data.
*
**********************************************************************/
width crcCompute(unsigned char * message, unsigned int nBytes) {
unsigned int offset;
unsigned char byte;
width remainder = INITIAL_REMAINDER;
/*
* Divide the message by the polynomial, a byte at a time.
*/
for (offset = 0; offset < nBytes; offset++) {
byte = (remainder >> (WIDTH – 8)) ^ message[offset];
remainder = crcTable[byte] ^ (remainder << 8);
}
/*
* The final remainder is the CRC result.
*/
return (remainder ^ FINAL_XOR_VALUE);
} /* crcCompute() */