Chapter 17) A Catalog of Parameter Sets for Standards

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

Chapter 18) An Implementation of the Model Algorithm

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:

Chapter 19) Roll Your Own Table-Driven Implementation

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!

Chapter 20) Generating A Lookup Table

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:

Chapter 21) Summary

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.

Chapter 22) Corrections

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

Chapter 23) Glossary

A number that has been calculated as a function of some message. The literal interpretation of this word "Check-Sum" indicates that the function should involve simply adding up the bytes in the message. Perhaps this was what early checksums were. Today, however, although more sophisticated formulae are used, the term "checksum" is still used.
This stands for "Cyclic Redundancy Code". Whereas the term "checksum" seems to be used to refer to any non-cryptographic checking information unit, the term "CRC" seems to be reserved only for algorithms that are based on the "polynomial" division idea.
This symbol is used in this document to represent the Poly.
The input data being checksummed. This is usually structured as a sequence of bytes. Whether the top bit or the bottom bit of each byte is treated as the most significant or least significant is a parameter of CRC algorithms.
This is my friendly term for the polynomial of a CRC.
The "polynomial" of a CRC algorithm is simply the divisor in the division implementing the CRC algorithm.
A binary number is reflected by swapping all of its bits around the central point. For example, 1101 is the reflection of 1011.
A parameterized algorithm whose purpose is to act as a solid reference for describing CRC algorithms. Typically CRC algorithms are specified by quoting a polynomial. However, in order to construct a precise implementation, one also needs to know initialization values and so on.
The width of a CRC algorithm is the width of its polynomical minus one. For example, if the polynomial is 11010, the width would be 4 bits. The width is usually set to be a multiple of 8 bits.

Chapter 24) References

Chapter 25) References I Have Detected But Haven't Yet Sighted

Please check attribution section for Author of this document! This article was written by filipg@repairfaq.org [mailto]. The most recent version is available on the WWW server http://www.repairfaq.org/filipg/ [Copyright] [Disclaimer]