crc.txt

CRC16的源程序

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


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

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

A. Glossary
-----------
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.

B. References
-------------
[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.


C. References I Have Detected But Haven't Yet Sighted
-----------------------------------------------------
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 E