- [Previous] segment | [Sub-ToC] for this document | Main [Table 'O Contents]
- Chapter 17) A Catalog of Parameter Sets for Standards
- Chapter 18) An Implementation of the Model Algorithm
- Chapter 19) Roll Your Own Table-Driven Implementation
- Chapter 20) Generating A Lookup Table
- Chapter 21) Summary
- Chapter 22) Corrections
- Chapter 23) Glossary
- Chapter 24) References
- Chapter 25) References I Have Detected But Haven't Yet Sighted
- [
**This is the last segment**]

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:

- crcmodel.h (Header File) (0KB)
- crcmodel.c (C src) (0KB)

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:

- crctable.c (0KB)

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

**CHECKSUM**- 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.
**CRC**- 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.
**G**- This symbol is used in this document to represent the Poly.
**MESSAGE**- 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.
**POLY**- This is my friendly term for the polynomial of a CRC.
**POLYNOMIAL**- The "polynomial" of a CRC algorithm is simply the divisor in the division implementing the CRC algorithm.
**REFLECT**- A binary number is reflected by swapping all of its bits around the central point. For example, 1101 is the reflection of 1011.
**ROCKSOFT(tm) MODEL CRC ALGORITHM**- 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.
**WIDTH**- 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.

- [Griffiths87] Griffiths, G., Carlyle Stones, G., "The Tea-Leaf Reader Algorithm: An Efficient Implementation of CRC-16 and CRC-32", Communications of the ACM, 30(7), pp.617-620. Comment: This paper describes a high-speed table-driven implementation of CRC algorithms. The technique seems to be a touch messy, and is superceded by the Sarwete algorithm.
- [Knuth81] Knuth, D.E., "The Art of Computer Programming", Volume 2: Seminumerical Algorithms, Section 4.6.
- [Nelson 91] Nelson, M., "The Data Compression Book", M&T Books, (501
Galveston Drive, Redwood City, CA 94063), 1991, ISBN: 1-55851-214-4.
**Comment:**If you want to see a real implementation of a real 32-bit checksum algorithm, look on pages 440, and 446-448. - [Sarwate88] Sarwate, D.V., "Computation of Cyclic Redundancy Checks
via Table Look-Up", Communications of the ACM, 31(8), pp.1008-1013.
**Comment:**This paper describes a high-speed table-driven implementation for CRC algorithms that is superior to the tea-leaf algorithm. Although this paper describes the technique used by most modern CRC implementations, I found the appendix of this paper (where all the good stuff is) difficult to understand. - [Tanenbaum81] Tanenbaum, A.S., "Computer Networks", Prentice Hall, 1981, ISBN: 0-13-164699-0. Comment: Section 3.5.3 on pages 128 to 132 provides a very clear description of CRC codes. However, it does not describe table-driven implementation techniques.

- Boudreau, Steen, "Cyclic Redundancy Checking by Program," AFIPS Proceedings, Vol. 39, 1971.
- Davies, Barber, "Computer Networks and Their Protocols," J. Wiley & Sons, 1979.
- Higginson, Kirstein, "On the Computation of Cyclic Redundancy Checks by Program," The Computer Journal (British), Vol. 16, No. 1, Feb 1973.
- McNamara, J. E., "Technical Aspects of Data Communication," 2nd Edition, Digital Press, Bedford, Massachusetts, 1982.
- Marton and Frambs, "A Cyclic Redundancy Checking (CRC) Algorithm," Honeywell Computer Journal, Vol. 5, No. 3, 1971.
- Nelson M., "File verification using CRC", Dr Dobbs Journal, May 1992, pp.64-67.
- Ramabadran T.V., Gaitonde S.S., "A tutorial on CRC computations", IEEE Micro, Aug 1988.
- Schwaderer W.D., "CRC Calculation", April 85 PC Tech Journal, pp.118-133.
- Ward R.K, Tabandeh M., "Error Correction and Detection, A Geometric Approach" The Computer Journal, Vol. 27, No. 3, 1984, pp.246-253.
- Wecker, S., "A Table-Lookup Algorithm for Software Computation of Cyclic Redundancy Check (CRC)," Digital Equipment Corporation memorandum, 1974.