CRC RevEng

[ Home | Up | Prev | Next | Disclaimer ]

Summary of the CRC Catalogue

Legend

Evidence classes

I

Primary documents. Evidence from a standards document (official or de facto) defining a protocol that uses the CRC algorithm.

II

Implementations. A widely-available implementation that can calculate CRCs for any desired message.

III

Secondary documents. Evidence from documents other than standards documents.

IV

Codewords. Valid message-CRC pairs from any source. Trivial codewords are simple sums of the algorithm parameters and/or simple multiples of the generator polynomial, and show insufficient calculation complexity to validate an algorithm. These are collected in the Catalogue only for illustration.

Model classes

Attested

The algorithm is evidenced by its definition in a primary document, plus one or more of the following:

• A worked example in a primary document
• A widely-available implementation that can calculate CRCs for any desired message
• Two or more published non-trivial codewords
• An almost identical attested algorithm definition in the same primary document (notwithstanding this clause), plus one non-trivial codeword published anywhere.

Confirmed

The algorithm is evidenced by a widely-available implementation that can calculate CRCs for any desired message.

Academic

It has not been confirmed that CRCs are actually calculated in the field according to this record.

Third-party

All parameters and codewords originate from unofficial sources.

Model parameters

width

The number of bit cells in the linear feedback shift register; the degree of the generator polynomial, less one.

poly

The generator polynomial that sets the feedback tap positions of the shift register. poly is written in the hexadecimal, direct notation found in MSB-first code. The least significant bit corresponds to the inward end of the shift register, and is always set. The highest-order term is omitted.

init

The settings of the bit cells at the start of each calculation, before reading the first message bit. init is written in the hexadecimal, direct notation found in MSB-first code. The least significant bit corresponds to the inward end of the shift register.

refin

If equal to false, specifies that the characters of the message are read bit-by-bit, most significant bit (MSB) first; if equal to true, the characters are read bit-by-bit, least significant bit (LSB) first. Each sampled message bit is then XORed with the bit being simultaneously shifted out of the register at the most significant end, and the result is passed to the feedback taps.

refout

If equal to false, specifies that the contents of the register after reading the last message bit are unreflected before presentation; if equal to true, it specifies that they are reflected, character-by-character, before presentation. For the purpose of this definition, the reflection is performed by swapping the content of each cell with that of the cell an equal distance from the opposite end of the register; the characters of the CRC are then true images of parts of the reflected register, the character containing the original MSB always appearing first.

xorout

The XOR value applied to the contents of the register after the last message bit has been read and after the optional reflection. xorout is written in hexadecimal notation, having the same endianness as the CRC such that its true image appears in the characters of the CRC.

check

The contents of the register after initialising, reading the UTF-8 string "123456789" (as 8-bit characters), optionally reflecting, and applying the final XOR.

residue

The contents of the register after initialising, reading an error-free codeword and optionally reflecting the register (if refout=true), but not applying the final XOR. This is mathematically equivalent to initialising the register with the xorout parameter, reflecting it as described (if refout=true), reading as many zero bits as there are cells in the register, and reflecting the result (if refin=true). The residue of a crossed-endian model is calculated assuming that the characters of the received CRC are specially reflected before submitting the codeword.

name

The name assigned to the model in this Catalogue.

Model notes

Unique effective solution of codeword set

This model is the only one at the specified width that solves all the codewords listed in the model entry. Equivalent forms of the model may exist (differing in Init, XorOut and Residue values) but they produce identical CRCs at all message lengths. (If (x + 1)ⁿ appears in the factorisation of G(x), then there shall be 2ⁿ − 1 equivalent forms.)

References

Robert Bosch GmbH (September 1991), CAN 2.0 Specification.

• https://github.com/ThrowTheSwitch/pcan-ruby/raw/master/doc/can2spec.pdf

Dipl. Inf. Johann N. Löfflmann (30 July 2006), Jacksum. CRC and hash calculator in Java.

• https://jacksum.net/en/index.html

Thomas Pircher (5 November 2022), pycrc. Python based parametrised CRC calculator and C code generator.

• https://pycrc.org/

William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling (1992), Numerical recipes in C: The art of scientific computing. 2nd ed. Cambridge: Cambridge University Press. ISBN 0-521-43108-5

Dr Ross N. Williams (19 August 1993), "A Painless Guide to CRC Error Detection Algorithms" (courtesy of the Internet Archive).

• https://web.archive.org/web/20190527220400/http://www.ross.net/crc/download/crc_v3.txt
• https://web.archive.org/web/20190523182111/http://www.wolfgang-ehrhardt.de/crc_v3.html

Useful links

Lammert Bies (August 2011), "On-line CRC calculation and free library".

• https://www.lammertbies.nl/comm/info/crc-calculation

Lammert Bies, "Error detection and correction" Web forum (courtesy of the Internet Archive).

• https://web.archive.org/web/20170702024257/https://www.lammertbies.nl/forum/viewforum.php?f=11

Jonathan Graham Harston (21–23 June 2011), "Source Code for Calculating CRCs".

• https://mdfs.net/Info/Comp/Comms/CRCs.htm
• https://mdfs.net/Info/Comp/Comms/CRC16.htm
• https://mdfs.net/Info/Comp/Comms/CRC32.htm

PicList MassMind, "Cyclic Redundancy Check error detection".

• https://web.archive.org/web/20230121021528/http://www.piclist.com/techref/method/error/crc.htm

Tom Torfs, IOCCC winning entry, 1998, CRC generator.

• https://www.ioccc.org/years.html#1998_tomtorfs

Disclaimer

Every effort has been made to ensure accuracy, however there may be occasional errors or omissions. All trademarks and registered trademarks are the intellectual property of their respective owners. The code and documentation included in this document are supplied without warranty, not even the implied warranties of merchantability or fitness for a particular purpose. In no event shall the author or his suppliers be liable for any loss, damage, injury or death, of any nature and howsoever caused, arising from the use of, or failure, inability or unwillingness to use, this software or documentation.

[ Top of page ]

Appendix A

Map of common 16-bit CRC algorithms.

Appendix B

Cross-reference of generator polynomials to Professor Koopman's CRC Polynomial Zoo.

Legend: < Lexically greater than its reciprocal in the Reflected column. *< Lexically greater than its reciprocal listed in the Zoo and in the Reflected column. = Palindromic polynomial. (*o) Multiple of (x + 1). (*p) Primitive polynomial. (*op) Product of a primitive polynomial and (x + 1).

Greg Cook,
https://reveng.sourceforge.io/crc-catalogue/legend.htm Last updated 29 August 2024
Links last verified 20 July 2023

 Hosting by

[ Top of page ]