Technology

madler/crcany: Compute any CRC, a bit at a time, a byte at a time, and a word at a time.

Synopsis

crcany is a suite of programs that generalize CRC calculations, and that
generate C code to compute and combine CRCs efficiently. Any CRC can be
computed given the set of parameters that describe it. Those parameters are
provided in the form as used by Greg Cook’s catalog of over one-hundred CRCs,
found at https://reveng.sourceforge.io/crc-catalogue/all.htm . That set of
parameters were first defined by Ross Williams in his excellent tutorial on
CRCs, which can be found at http://zlib.net/crc_v3.txt .

crcany can compute a CRC in three different ways. First, computing a bit at a
time, as would be done in a hardware shift-register implementation. Second,
computing the CRC a byte at a time, first using the bit-at-a-time algorithm to
create a table of the 256 CRCs of all byte values. Third, using the byte-wise
table to generate another n-1 tables, where n is the number of bytes in the
word, to enable computing a CRC a word at a time. The word-wise approach has
two flavors, one for little-endian machines, and one for big-endian machines.

crcany can combine CRCs efficiently. Given only the CRCs of two sequences of
bytes, and the length of the second sequence, the CRC of the two sequences
concatenated can be computed efficiently.

crcany can generate C code in .c and .h files for one or a series of CRC
definitions. By default, code is generated for the machine being run on (i.e.
with respect to the lengths of the integer types and their endianess). Code can
optionally be generated for 32-bit or 64-bit words, and for big-endian or
little-endian. Code can be generated for any CRC whose width is less than or
equal to the maximum integer size.

The bit-wise calculation can be done on CRCs up to twice the word length, e.g.
128 bits on machines with 64-bit integers. The byte and word-wise calculations
can be done on CRCs up to the word size, e.g. up to 64-bit CRCs using 64-bit
integers. CRC code can be generated for CRCs up to 64 bits in length.

Motivation

Provide once and for all a definitive reference for how to compute and combine
any CRC with any of bit, byte, or word-at-a-time algorithms, on any big or
little-endian architecture.

Installation

This will compile the crcany, crctest, crcall, crcadd, and mincrc executables:

Test

Test the calculation of CRCs and the generation of CRC code using the list of
all catalogued CRCs:

A Brief Tour of the Components

Callable routines:

  • model.[ch] — define a particular CRC, read a CRC description from a file
  • crc.[ch] — compute a CRC using the given model, combine CRCs
  • crcdbl.[ch] — compute a CRC longer than 64 bits, up to 128 bits in length
  • crcgen.[ch] — generate C code to efficiently calculate a CRC

Executables:

  • crcany.c — compute a CRC by name (from the catalogue) on the provided data
  • crcall.c — generate C code and test code for all provided CRC definitions
  • crcadd.c — generate C code only for all provided CRC definitions
  • crctest.c — test the code generated by crcall
  • mincrc.c — maximally abbreviate the provided CRC definitions
  • getcrcs — scrape Greg Cook’s site for all of the CRC definitions

Information:

  • README.md — this file
  • Makefile — generate and test code for all CRCs in allcrcs-abbrev.txt
  • allcrcs.txt — all of the CRC definitions, one per line, from Greg Cook’s catalogue
  • allcrcs-abbrev.txt — allcrcs.txt abbreviated
  • allcrcs/ — directory with a copy of Greg Cook’s catalogue

License

This code is under the zlib license, permitting free commercial use.

Related Articles

Back to top button