Contents:
At this point, I would like to give a list of the specifications for commonly used CRC algorithms. However, most of the algorithms that I have come into contact with so far are specified in such a vague way that this has not been possible. What I can provide is a list of polys for various CRC standards I have heard of:
X25 standard : 1021 [CRC-CCITT, ADCCP, SDLC/HDLC] X25 reversed : 0811 CRC16 standard : 8005 CRC16 reversed : 4003 [LHA] CRC32 : 04C11DB7 [PKZIP, AUTODIN II, Ethernet, FDDI]
I would be interested in hearing from anyone out there who can tie down the complete set of model parameters for any of these standards.
However, a program that was kicking around seemed to imply the following specifications. Can anyone confirm or deny them (or provide the check values (which I couldn't be bothered coding up and calculating)).
Name : "CRC-16/CITT" Width : 16 Poly : 1021 Init : FFFF RefIn : False RefOut : False XorOut : 0000 Check : ? Name : "XMODEM" Width : 16 Poly : 8408 Init : 0000 RefIn : True RefOut : True XorOut : 0000 Check : ? Name : "ARC" Width : 16 Poly : 8005 Init : 0000 RefIn : True RefOut : True XorOut : 0000 Check : ?
Here is the specification for the CRC-32 algorithm which is reportedly used in PKZip, AUTODIN II, Ethernet, and FDDI.
Name : "CRC-32" Width : 32 Poly : 04C11DB7 Init : FFFFFFFF RefIn : True RefOut : True XorOut : FFFFFFFF Check : CBF43926
Here is an implementation of the model algorithm in the C programming language. The implementation consists of a header file (.h) and an implementation file (.c). If you're reading this document in a sequential scroller, you can skip this code by searching for the string "Roll Your Own".
To ensure that the following code is working, configure it for the CRC-16 and CRC-32 algorithms given above and ensure that they produce the specified "check" checksum when fed the test string "123456789" (see earlier).
Link to C program:
Despite all the fuss I've made about understanding and defining CRC algorithms, the mechanics of their high-speed implementation remains trivial. There are really only two forms: normal and reflected. Normal shifts to the left and covers the case of algorithms with Refin=FALSE and Refot=FALSE. Reflected shifts to the right and covers algorithms with both those parameters true. (If you want one parameter true and the other false, you'll have to figure it out for yourself!) The polynomial is embedded in the lookup table (to be discussed). The other parameters, Init and XorOt can be coded as macros. Here is the 32-bit normal form (the 16-bit form is similar).
unsigned long crc_normal ();
unsigned long crc_normal (blk_adr,blk_len)
unsigned char *blk_adr;
unsigned long blk_len;
{
unsigned long crc = INIT;
while (blk_len--)
crc = crctable[((crc>>24) ^ *blk_adr++) & 0xFFL] ^ (crc << 8);
return crc ^ XOROT;
}
Here is the reflected form:
unsigned long crc_reflected ();
unsigned long crc_reflected (blk_adr,blk_len)
unsigned char *blk_adr;
unsigned long blk_len;
{
unsigned long crc = INIT_REFLECTED;
while (blk_len--)
crc = crctable[(crc ^ *blk_adr++) & 0xFFL] ^ (crc >> 8));
return crc ^ XOROT;
}
Note: I have carefully checked the above two code fragments, but I haven't actually compiled or tested them. This shouldn't matter to you, as, no matter WHAT you code, you will always be able to tell if you have got it right by running whatever you have created against the reference model given earlier. The code fragments above are really just a rough guide. The reference model is the definitive guide.
Note: If you don't care much about speed, just use the reference model code!
The only component missing from the normal and reversed code fragments in the previous section is the lookup table. The lookup table can be computed at run time using the cm_tab function of the model package given earlier, or can be pre-computed and inserted into the C program. In either case, it should be noted that the lookup table depends only on the POLY and RefIn (and RefOt) parameters. Basically, the polynomial determines the table, but you can generate a reflected table too if you want to use the reflected form above.
The following program generates any desired 16-bit or 32-bit lookup table. Skip to the word "Summary" if you want to skip over this code.
Link to C program:
This document has provided a detailed explanation of CRC algorithms explaining their theory and stepping through increasingly sophisticated implementations ranging from simple bit shifting through to byte-at-a-time table-driven implementations. The various implementations of different CRC algorithms that make them confusing to deal with have been explained. A parameterized model algorithm has been described that can be used to precisely define a particular CRC algorithm, and a reference implementation provided. Finally, a program to generate CRC tables has been provided.
If you think that any part of this document is unclear or incorrect, or have any other information, or suggestions on how this document could be improved, please context the author. In particular, I would like to hear from anyone who can provide Rocksoft(tm) Model CRC Algorithm parameters for standard algorithms out there.
E-Mail me, Ross N. Williams, at ross@guest.adelaide.edu.au