crc.txt

Many crc routine in C

If all this seems a bit unclear, don't worry, because we're going to
sort it all out "real soon now". Just one more section to go before
that.


13. Initial and Final Values
----------------------------
In addition to the complexity already seen, CRC algorithms differ from
each other in two other regards:

   * The initial value of the register.

   * The value to be XORed with the final register value.

For example, the "CRC32" algorithm initializes its register to
FFFFFFFF and XORs the final register value with FFFFFFFF.

Most CRC algorithms initialize their register to zero. However, some
initialize it to a non-zero value. In theory (i.e. with no assumptions
about the message), the initial value has no affect on the strength of
the CRC algorithm, the initial value merely providing a fixed starting
point from which the register value can progress. However, in
practice, some messages are more likely than others, and it is wise to
initialize the CRC algorithm register to a value that does not have
"blind spots" that are likely to occur in practice. By "blind spot" is
meant a sequence of message bytes that do not result in the register
changing its value. In particular, any CRC algorithm that initializes
its register to zero will have a blind spot of zero when it starts up
and will be unable to "count" a leading run of zero bytes. As a
leading run of zero bytes is quite common in real messages, it is wise
to initialize the algorithm register to a non-zero value.


14. Defining Algorithms Absolutely
----------------------------------
At this point we have covered all the different aspects of
table-driven CRC algorithms. As there are so many variations on these
algorithms, it is worth trying to establish a nomenclature for them.
This section attempts to do that.

We have seen that CRC algorithms vary in:

   * Width of the poly (polynomial).
   * Value of the poly.
   * Initial value for the register.
   * Whether the bits of each byte are reflected before being processed.
   * Whether the algorithm feeds input bytes through the register or
     xors them with a byte from one end and then straight into the table.
   * Whether the final register value should be reversed (as in reflected
     versions).
   * Value to XOR with the final register value.

In order to be able to talk about particular CRC algorithms, we need
to be able to define them more precisely than this. For this reason, the
next section attempts to provide a well-defined parameterized model
for CRC algorithms. To refer to a particular algorithm, we need then
simply specify the algorithm in terms of parameters to the model.


15. A Parameterized Model For CRC Algorithms
--------------------------------------------
In this section we define a precise parameterized model CRC algorithm
which, for want of a better name, we will call the "Rocksoft^tm Model
CRC Algorithm" (and why not? Rocksoft^tm could do with some free
advertising :-).

The most important aspect of the model algorithm is that it focusses
exclusively on functionality, ignoring all implementation details. The
aim of the exercise is to construct a way of referring precisely to
particular CRC algorithms, regardless of how confusingly they are
implemented. To this end, the model must be as simple and precise as
possible, with as little confusion as possible.

The Rocksoft^tm Model CRC Algorithm is based essentially on the DIRECT
TABLE ALGORITHM specified earlier. However, the algorithm has to be
further parameterized to enable it to behave in the same way as some
of the messier algorithms out in the real world.

To enable the algorithm to behave like reflected algorithms, we
provide a boolean option to reflect the input bytes, and a boolean
option to specify whether to reflect the output checksum value. By
framing reflection as an input/output transformation, we avoid the
confusion of having to mentally map the parameters of reflected and
non-reflected algorithms.

An extra parameter allows the algorithm's register to be initialized
to a particular value. A further parameter is XORed with the final
value before it is returned.

By putting all these pieces together we end up with the parameters of
the algorithm:

   NAME: This is a name given to the algorithm. A string value.

   WIDTH: This is the width of the algorithm expressed in bits. This
   is one less than the width of the Poly.

   POLY: This parameter is the poly. This is a binary value that
   should be specified as a hexadecimal number. The top bit of the
   poly should be omitted. For example, if the poly is 10110, you
   should specify 06. An important aspect of this parameter is that it
   represents the unreflected poly; the bottom bit of this parameter
   is always the LSB of the divisor during the division regardless of
   whether the algorithm being modelled is reflected.

   INIT: This parameter specifies the initial value of the register
   when the algorithm starts. This is the value that is to be assigned
   to the register in the direct table algorithm. In the table
   algorithm, we may think of the register always commencing with the
   value zero, and this value being XORed into the register after the
   N'th bit iteration. This parameter should be specified as a
   hexadecimal number.

   REFIN: This is a boolean parameter. If it is FALSE, input bytes are
   processed with bit 7 being treated as the most significant bit
   (MSB) and bit 0 being treated as the least significant bit. If this
   parameter is FALSE, each byte is reflected before being processed.

   REFOUT: This is a boolean parameter. If it is set to FALSE, the
   final value in the register is fed into the XOROUT stage directly,
   otherwise, if this parameter is TRUE, the final register value is
   reflected first.

   XOROUT: This is an W-bit value that should be specified as a
   hexadecimal number. It is XORed to the final register value (after
   the REFOUT) stage before the value is returned as the official
   checksum.

   CHECK: This field is not strictly part of the definition, and, in
   the event of an inconsistency between this field and the other
   field, the other fields take precedence. This field is a check
   value that can be used as a weak validator of implementations of
   the algorithm. The field contains the checksum obtained when the
   ASCII string "123456789" is fed through the specified algorithm
   (i.e. 313233... (hexadecimal)).

With these parameters defined, the model can now be used to specify a
particular CRC algorithm exactly. Here is an example specification for
a popular form of the CRC-16 algorithm.

   Name   : "CRC-16"
   Width  : 16
   Poly   : 8005
   Init   : 0000
   RefIn  : True
   RefOut : True
   XorOut : 0000
   Check  : BB3D


16. 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


17. 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).

/****************************************************************************/
/*                             Start of crcmodel.h                          */
/****************************************************************************/
/*                                                                          */
/* Author : Ross Williams ([e-mail].).                    */
/* Date   : 3 June 1993.                                                    */
/* Status : Public domain.                                                  */
/*                                                                          */
/* Description : This is the header (.h) file for the reference             */
/* implementation of the Rocksoft^tm Model CRC Algorithm. For more          */
/* information on the Rocksoft^tm Model CRC Algorithm, see the document     */
/* titled "A Painless Guide to CRC Error Detection Algorithms" by Ross      */
/* Williams ([e-mail].). This document is likely to be in */
/* "ftp.adelaide.edu.au/pub/rocksoft".                                      */
/*                                                                          */
/* Note: Rocksoft is a trademark of Rocksoft Pty Ltd, Adelaide, Australia.  */
/*                                                                          */
/****************************************************************************/
/*                                                                          */
/* How to Use This Package                                                  */
/* -----------------------                                                  */
/* Step 1: Declare a variable of type cm_t. Declare another variable        */
/*         (p_cm say) of type p_cm_t and initialize it to point to the first*/
/*         variable (e.g. p_cm_t p_cm = &cm_t).                             */
/*                                                                          */
/* Step 2: Assign values to the parameter fields of the structure.          */
/*         If you don't know what to assign, see the document cited earlier.*/
/*         For example:                                                     */
/*            p_cm->cm_width = 16;                                          */
/*            p_cm->cm_poly  = 0x8005L;                                     */
/*            p_cm->cm_init  = 0L;                                          */
/*            p_cm->cm_refin = TRUE;                                        */
/*            p_cm->cm_refot = TRUE;                                        */
/*            p_cm->cm_xorot = 0L;                                          */
/*         Note: Poly is specified without its top bit (18005 becomes 8005).*/
/*         Note: Width is one bit less than the raw poly width.             */
/*                                                                          */
/* Step 3: Initialize the instance with a call cm_ini(p_cm);                */
/*                                                                          */
/* Step 4: Process zero or more message bytes by placing zero or more       */
/*         successive calls to cm_nxt. Example: cm_nxt(p_cm,ch);            */
/*                                                                          */
/* Step 5: Extract the CRC value at any time by calling crc = cm_crc(p_cm); */
/*         If the CRC is a 16-bit value, it will be in the bottom 16 bits.  */
/*                                                                          */
/****************************************************************************/
/*                                                                          */
/* Design Notes                                                             */
/* ------------                                                             */
/* PORTABILITY: This package has been coded very conservatively so that     */
/* it will run on as many machines as possible. For example, all external   */
/* identifiers have been restricted to 6 characters and all internal ones to*/
/* 8 characters. The prefix cm (for Crc Model) is used as an attempt to     */
/* avoid namespace collisions. This package is endian independent.          */
/*                                                                          */
/* EFFICIENCY: This package (and its interface) is not designed for         */
/* speed. The purpose of this package is to act as a well-defined reference */
/* model for the specification of CRC algorithms. If you want speed, cook up*/
/* a specific table-driven implementation as described in the document cited*/
/* abo