Cyclic Checksum (slib)

5.8 Cyclic Checksum

(require 'crc) Cyclic Redundancy Checks using Galois field GF(2) polynomial arithmetic are used for error detection in many data transmission and storage applications.

The generator polynomials for various CRC protocols are availble from many sources. But the polynomial is just one of many parameters which must match in order for a CRC implementation to interoperate with existing systems:

the byte-order and bit-order of the data stream;
whether the CRC or its inverse is being calculated;
the initial CRC value; and
whether and where the CRC value is appended (inverted or non-inverted) to the data stream.

The performance of a particular CRC polynomial over packets of given sizes varies widely. In terms of the probability of undetected errors, some uses of extant CRC polynomials are suboptimal by several orders of magnitude.

If you are considering CRC for a new application, consult the following article to find the optimum CRC polynomial for your range of data lengths:

Philip Koopman and Tridib Chakravarty,
“Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks”,
The International Conference on Dependable Systems and Networks, DSN-2004.

http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

There is even some controversy over the polynomials themselves.

Constant: crc-32-polynomial ¶

For CRC-32, http://www2.sis.pitt.edu/~jkabara/tele-2100/lect08.html gives x^32+x^26+x^23+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x^1+1.

But http://www.cs.ncl.ac.uk/people/harry.whitfield/home.formal/CRCs.html, http://duchon.umuc.edu/Web_Pages/duchon/99_f_cm435/ShiftRegister.htm, http://spinroot.com/spin/Doc/Book91_PDF/ch3.pdf, http://www.erg.abdn.ac.uk/users/gorry/course/dl-pages/crc.html, http://www.rad.com/networks/1994/err_con/crc_most.htm, and http://www.gpfn.sk.ca/~rhg/csc8550s02/crc.html, http://www.nobugconsulting.ro/crc.php give x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1.

SLIB crc-32-polynomial uses the latter definition.

Constant: crc-ccitt-polynomial ¶: http://www.math.grin.edu/~rebelsky/Courses/CS364/2000S/Outlines/outline.12.html, http://duchon.umuc.edu/Web_Pages/duchon/99_f_cm435/ShiftRegister.htm, http://www.cs.ncl.ac.uk/people/harry.whitfield/home.formal/CRCs.html, http://www2.sis.pitt.edu/~jkabara/tele-2100/lect08.html, and http://www.gpfn.sk.ca/~rhg/csc8550s02/crc.html give CRC-CCITT: x^16+x^12+x^5+1.

Constant: crc-16-polynomial ¶: http://www.math.grin.edu/~rebelsky/Courses/CS364/2000S/Outlines/outline.12.html, http://duchon.umuc.edu/Web_Pages/duchon/99_f_cm435/ShiftRegister.htm, http://www.cs.ncl.ac.uk/people/harry.whitfield/home.formal/CRCs.html, http://www.gpfn.sk.ca/~rhg/csc8550s02/crc.html, and http://www.usb.org/developers/data/crcdes.pdf give CRC-16: x^16+x^15+x^2+1.

Constant: crc-12-polynomial ¶

http://www.math.grin.edu/~rebelsky/Courses/CS364/2000S/Outlines/outline.12.html, http://www.cs.ncl.ac.uk/people/harry.whitfield/home.formal/CRCs.html, http://www.it.iitb.ac.in/it605/lectures/link/node4.html, and http://spinroot.com/spin/Doc/Book91_PDF/ch3.pdf give CRC-12: x^12+x^11+x^3+x^2+1.

But http://www.ffldusoe.edu/Faculty/Denenberg/Topics/Networks/Error_Detection_Correction/crc.html, http://duchon.umuc.edu/Web_Pages/duchon/99_f_cm435/ShiftRegister.htm, http://www.eng.uwi.tt/depts/elec/staff/kimal/errorcc.html, http://www.ee.uwa.edu.au/~roberto/teach/itc314/java/CRC/, http://www.gpfn.sk.ca/~rhg/csc8550s02/crc.html, and http://www.efg2.com/Lab/Mathematics/CRC.htm give CRC-12: x^12+x^11+x^3+x^2+x+1.

These differ in bit 1 and calculations using them return different values. With citations near evenly split, it is hard to know which is correct. Thanks to Philip Koopman for breaking the tie in favor of the latter (#xC07).

Constant: crc-10-polynomial ¶: http://www.math.grin.edu/~rebelsky/Courses/CS364/2000S/Outlines/outline.12.html gives CRC-10: x^10+x^9+x^5+x^4+1; but http://cell-relay.indiana.edu/cell-relay/publications/software/CRC/crc10.html, http://www.it.iitb.ac.in/it605/lectures/link/node4.html, http://www.gpfn.sk.ca/~rhg/csc8550s02/crc.html, http://www.techfest.com/networking/atm/atm.htm, http://www.protocols.com/pbook/atmcell2.htm, and http://www.nobugconsulting.ro/crc.php give CRC-10: x^10+x^9+x^5+x^4+x+1.

Constant: crc-08-polynomial ¶: http://www.math.grin.edu/~rebelsky/Courses/CS364/2000S/Outlines/outline.12.html, http://www.cs.ncl.ac.uk/people/harry.whitfield/home.formal/CRCs.html, http://www.it.iitb.ac.in/it605/lectures/link/node4.html, and http://www.nobugconsulting.ro/crc.php give CRC-8: x^8+x^2+x^1+1

Constant: atm-hec-polynomial ¶: http://cell-relay.indiana.edu/cell-relay/publications/software/CRC/32bitCRC.tutorial.html and http://www.gpfn.sk.ca/~rhg/csc8550s02/crc.html give ATM HEC: x^8+x^2+x+1.

Constant: dowcrc-polynomial ¶: http://www.cs.ncl.ac.uk/people/harry.whitfield/home.formal/CRCs.html gives DOWCRC: x^8+x^5+x^4+1.

Constant: usb-token-polynomial ¶: http://www.usb.org/developers/data/crcdes.pdf and http://www.nobugconsulting.ro/crc.php give USB-token: x^5+x^2+1.

Each of these polynomial constants is a string of ‘1’s and ‘0’s, the exponent of each power of x in descending order.

Function: crc:make-table poly ¶

poly must be string of ‘1’s and ‘0’s beginning with ‘1’ and having length greater than 8. crc:make-table returns a vector of 256 integers, such that:

(set! crc
      (logxor (ash (logand (+ -1 (ash 1 (- deg 8))) crc) 8)
              (vector-ref crc-table
                          (logxor (ash crc (- 8 deg)) byte))))

will compute the crc with the 8 additional bits in byte; where crc is the previous accumulated CRC value, deg is the degree of poly, and crc-table is the vector returned by crc:make-table.

If the implementation does not support deg-bit integers, then crc:make-table returns #f.

Function: cksum file ¶

Computes the P1003.2/D11.2 (POSIX.2) 32-bit checksum of file.

(require 'crc)
(cksum (in-vicinity (library-vicinity) "ratize.scm"))
⇒ 157103930

Function: cksum port ¶: Computes the checksum of the bytes read from port until the end-of-file.

cksum-string, which returns the P1003.2/D11.2 (POSIX.2) 32-bit checksum of the bytes in str, can be defined as follows:

(require 'string-port)
(define (cksum-string str) (call-with-input-string str cksum))

Function: crc16 file ¶: Computes the USB data-packet (16-bit) CRC of file.

Function: crc16 port ¶

Computes the USB data-packet (16-bit) CRC of the bytes read from port until the end-of-file.

crc16 calculates the same values as the crc16.pl program given in http://www.usb.org/developers/data/crcdes.pdf.

Function: crc5 file ¶: Computes the USB token (5-bit) CRC of file.

Function: crc5 port ¶

Computes the USB token (5-bit) CRC of the bytes read from port until the end-of-file.

crc5 calculates the same values as the crc5.pl program given in http://www.usb.org/developers/data/crcdes.pdf.