Racket

crc: CRC catalogue and engine for automotive and embedded use🔗ℹ

turinglambdaai <turinglambdaai@users.noreply.github.com>

package: crc

This package provides a generic CRC engine (any width from 1 to 64 bits, with or without input/output reflection and final XOR) plus a catalogue of 21 ready-made parameter sets weighted towards automotive and embedded use: the CAN and CAN FD frame CRCs, AUTOSAR E2E profiles, SAE J1850, and the usual general-purpose algorithms.

Parameters, names and check values follow the public RevEng CRC catalogue; every catalogue entry’s check value — the CRC of the 9-byte ASCII string 123456789 — is asserted by the test suite, so the engine and the presets cannot silently drift apart.

1 Catalogue🔗ℹ

procedure
(all-crcs) → (listof crc-params?)

Every preset in the catalogue.

procedure
(crc-by-name name) → (or/c crc-params? #f)
name : symbol?

Looks up a preset by name, e.g. (crc-by-name 'crc-15/can).

The catalogue currently contains:

Name	Width	Poly	Init	Refin	Refout	Xorout	Check
crc-8/smbus	8	0x07	0x00	no	no	0x00	0xF4
crc-8/autosar	8	0x2F	0xFF	no	no	0xFF	0xDF
crc-8/sae-j1850	8	0x1D	0xFF	no	no	0xFF	0x4B
crc-8/maxim	8	0x31	0x00	yes	yes	0x00	0xA1
crc-8/dvb-s2	8	0xD5	0x00	no	no	0x00	0xBC
crc-8/rohc	8	0x07	0xFF	yes	yes	0x00	0xD0
crc-8/itu	8	0x07	0x00	no	no	0x55	0xA1
crc-15/can	15	0x4599	0x0000	no	no	0x0000	0x059E
crc-16/ccitt-false	16	0x1021	0xFFFF	no	no	0x0000	0x29B1
crc-16/xmodem	16	0x1021	0x0000	no	no	0x0000	0x31C3
crc-16/kermit	16	0x1021	0x0000	yes	yes	0x0000	0x2189
crc-16/modbus	16	0x8005	0xFFFF	yes	yes	0x0000	0x4B37
crc-16/usb	16	0x8005	0xFFFF	yes	yes	0xFFFF	0xB4C8
crc-16/x-25	16	0x1021	0xFFFF	yes	yes	0xFFFF	0x906E
crc-16/genibus	16	0x1021	0xFFFF	no	no	0xFFFF	0xD64E
crc-17/can-fd	17	0x1685B	0x00000	no	no	0x00000	0x04F03
crc-21/can-fd	21	0x102899	0x000000	no	no	0x000000	0x0ED841
crc-32	32	0x04C11DB7	0xFFFFFFFF	yes	yes	0xFFFFFFFF	0xCBF43926
crc-32/bzip2	32	0x04C11DB7	0xFFFFFFFF	no	no	0xFFFFFFFF	0xFC891918
crc-32c	32	0x1EDC6F41	0xFFFFFFFF	yes	yes	0xFFFFFFFF	0xE3069283
crc-32/autosar	32	0xF4ACFB13	0xFFFFFFFF	yes	yes	0xFFFFFFFF	0x1697D06A

Each preset is also exported as a binding of the same name (crc-15/can, crc-32, …).

2 Engine🔗ℹ

struct
(struct crc-params ( name
width
poly
init
refin
refout
xorout
check
table))
  name : symbol?
  width : (integer-in 1 64)
  poly : exact-nonnegative-integer?
  init : exact-nonnegative-integer?
  refin : boolean?
  refout : boolean?
  xorout : exact-nonnegative-integer?
  check : exact-nonnegative-integer?
  table : (or/c #f (vectorof exact-nonnegative-integer?))

One CRC algorithm definition. poly and init are in normal (unreflected) form, exactly as the catalogue writes them. table is an internal lookup cache for byte-aligned widths; leave it alone.

procedure
(make-crc-params name
width
poly
init
refin
refout
xorout
check) → crc-params?
  name : symbol?
  width : (integer-in 1 64)
  poly : exact-nonnegative-integer?
  init : exact-nonnegative-integer?
  refin : boolean?
  refout : boolean?
  xorout : exact-nonnegative-integer?
  check : exact-nonnegative-integer?

Defines a custom algorithm. check should be the CRC of 123456789; the test suite treats catalogue check values as golden vectors, and your own values can be asserted the same way.

procedure
(crc-compute p data) → exact-nonnegative-integer?
p : crc-params?
data : bytes?

Computes the CRC of data as an integer no larger than (sub1 (expt 2 (crc-params-width p))).

procedure
(crc-begin p) → exact-nonnegative-integer?
p : crc-params?

Starts an incremental computation: returns the raw CRC register (init in working order, before any output transformation).

procedure
(crc-extend p reg data [start end]) → exact-nonnegative-integer?
  p : crc-params?
  reg : exact-nonnegative-integer?
  data : bytes?
  start : exact-nonnegative-integer? = 0
  end : exact-nonnegative-integer? = (bytes-length data)

Folds data[start,end) into the raw register reg and returns the new register. Registers are plain integers, so partial computations can be stored and resumed freely.

procedure
(crc-result p reg) → exact-nonnegative-integer?
p : crc-params?
reg : exact-nonnegative-integer?

Finishes an incremental computation: applies refout/xorout and returns the final CRC value.

procedure
(crc-input-port p in) → exact-nonnegative-integer?
p : crc-params?
in : (or/c input-port? #f)

Computes the CRC of everything read from in (default (current-input-port)), reading in 64 KiB chunks.

procedure
(crc-digest p data) → bytes?
p : crc-params?
data : bytes?

Computes the CRC and returns it as a big-endian byte string of the minimal whole number of bytes needed for the width.

procedure
(crc-reflect value width) → exact-nonnegative-integer?
value : exact-nonnegative-integer?
width : (integer-in 1 64)

Reverses the low width bits of value.

procedure
(crc-compute/bitwise p data) → exact-nonnegative-integer?
p : crc-params?
data : bytes?

The table-free reference implementation; byte-aligned widths normally take the table path, so this serves as an independent cross-check in tests.

3 Example🔗ℹ

(require crc)

(crc-compute crc-32 #"123456789")
(crc-compute crc-15/can #"123456789")
(crc-digest crc-16/modbus #"payload")

(define p (make-crc-params 'my-crc 16 4129 65535 #f #f 32773 0xD64E))
(crc-compute p #"123456789")

Incremental computation over a stream:

(for/fold ([reg (crc-begin crc-32)])
([chunk (in-producer read-chunk eof)])
(crc-extend crc-32 reg chunk))

4 Performance🔗ℹ

Reflected 32-bit algorithms (crc-32, crc-32c) run a slicing-by-8 kernel; other byte-aligned widths use a per-byte lookup table. On a typical laptop the CRC-32 path processes on the order of a gigabyte per second.