CRC checksums
README.md

nox-crc #

CRCs and Internet checksums for OCaml, computed with the CPU's CRC instructions where it has them.

Link protocols check every frame. CCSDS transfer frames end with a CRC-16, AX.25 and the Bundle Protocol use its X.25 variant, storage formats use CRC-32C, and IP, UDP and TCP headers carry the RFC 1071 Internet checksum. nox-crc computes all of these, as well as CRC-32 and Adler-32. Each function takes a string or a range of a bytes buffer. The CRC-16 and Internet checksum functions also take a rope, so a frame built from several buffers is checked without copying it. Two CRC-32 or CRC-32C values of adjacent ranges can be combined into the value of the whole. When one 16-bit word of a packet changes, its Internet checksum can be updated in constant time (RFC 1624). Native code, js_of_ocaml and wasm_of_ocaml all give the same results.

Contents #

Installation #

Install with opam:

$ opam install nox-crc

If opam cannot find the package, it may not yet be released in the public opam-repository. Add the overlay repository, then install it:

$ opam repo add samoht https://tangled.org/gazagnaire.org/opam-overlay.git
$ opam update
$ opam install nox-crc

The package installs the library nox-crc, whose module is Crc. It needs OCaml 4.14 or later. The 32-bit checksums are returned as Optint.t, from optint, so they are exact on targets where int has 31 bits.

Usage #

The 16-bit checksums are ints and the 32-bit ones Optint.t. Each CRC gives its standard check value on "123456789":

# Printf.sprintf "0x%04X" (Crc.crc16_ccitt "123456789");;
- : string = "0x29B1"
# Printf.sprintf "0x%04X" (Crc.crc16_x25 "123456789");;
- : string = "0x906E"
# Printf.sprintf "0x%08lX" (Optint.to_int32 (Crc.crc32 "123456789"));;
- : string = "0xCBF43926"
# Printf.sprintf "0x%08lX" (Optint.to_int32 (Crc.crc32c "123456789"));;
- : string = "0xE3069283"

Each checksum has a _bytes variant that reads a range of a bytes buffer, given by offset and length:

# let buf = Bytes.of_string "Hello, world!";;
val buf : bytes = Bytes.of_string "Hello, world!"
# Crc.crc16_ccitt_bytes buf 7 5 = Crc.crc16_ccitt "world";;
- : bool = true

crc32_combine gives the CRC-32 of two adjacent ranges from their two CRC-32s and the length of the second, without reading the bytes again:

# Optint.equal
    (Crc.crc32_combine (Crc.crc32 "Hello, ") (Crc.crc32 "world!") 6)
    (Crc.crc32 "Hello, world!");;
- : bool = true

The Internet checksum of an IPv4 header whose checksum field is zero is the value to store there, and the checksum of a header that carries it is zero:

# let header = "\x45\x00\x00\x1c\x00\x00\x00\x00\x40\x11\x00\x00\x0a\x00\x00\x01\x0a\x00\x00\x02";;
val header : string =
  "E\000\000\028\000\000\000\000@\017\000\000\n\000\000\001\n\000\000\002"
# Printf.sprintf "0x%04X" (Crc.internet_checksum header);;
- : string = "0x66CF"
# let stored = Bytes.of_string header in
  Bytes.set_uint16_be stored 10 (Crc.internet_checksum header);
  Crc.internet_checksum_bytes stored 0 20;;
- : int = 0

Algorithms #

A CRC reads the message as a polynomial over GF(2), with one coefficient per bit. It divides that polynomial by a fixed generator polynomial, and the remainder is the check value. The register starts at the Init value, and the result is XORed with XOR Out at the end. A reflected CRC (Reflect = Yes) takes each byte least significant bit first, which is the order a serial line sends it in. Its polynomial is usually written bit-reversed, and the table below does the same, so the rows use two notations. 0xEDB88320 is the textbook 0x04C11DB7 reversed, and 0x82F63B78 is CRC-32C's 0x1EDC6F41 reversed; in normal form the first four polynomials are 0x1021, 0x1021, 0x04C11DB7 and 0x1EDC6F41. Each CRC below uses these parameters and gives the standard check value:

Algorithm Polynomial Init Reflect XOR Out Check ("123456789") Standard
CRC-16-CCITT 0x1021 0xFFFF No None 0x29B1 ITU-T V.41, CCSDS FECF
CRC-16-X.25 0x1021 0xFFFF Yes 0xFFFF 0x906E ITU-T X.25, RFC 9171
CRC-32 0xEDB88320 0xFFFFFFFF Yes 0xFFFFFFFF 0xCBF43926 ISO 3309, ITU-T V.42
CRC-32C 0x82F63B78 0xFFFFFFFF Yes 0xFFFFFFFF 0xE3069283 RFC 3720 (iSCSI)
CRC-32 Proximity-1 0x00A00805 0x00000000 No None 0x51693C0C CCSDS 211.2-B-3 annex C

Besides the CRCs, the library computes the Internet checksum (RFC 1071) and Adler-32 (RFC 1950).

crc32_combine works because a CRC is linear over GF(2). The CRC of a followed by b equals the CRC of a run through |b| zero bytes, XORed with the CRC of b. Running a 32-bit register through one zero bit is a fixed 32 × 32 bit matrix, and the function raises it to the power 8|b| by repeated squaring. The cost is O(log |b|) products of 32 × 32 bit matrices, the same method as zlib's crc32_combine.

The tests check each CRC against the vectors of ITU-T V.41, ISO 3309 and RFC 3720 section 12.1. The fuzz tests check that the string and bytes variants agree and that the hardware path gives the same answer as the software one.

Performance #

The library chooses one of three implementations at run time. The throughput figures below are orders of magnitude and were not measured on this release. Run bench/ to measure them on your machine.

Tier Strategy CRC-32C throughput When
Hardware SSE4.2 / ARM CRC intrinsics ~15-30 GB/s x86_64 with SSE4.2, aarch64
Slicing-by-8 8 x 256-entry tables ~1-4 GB/s Software fallback (native, jsoo, wasm)
Byte-at-a-time 256-entry table ~300 MB/s CRC-16 variants

At build time, dune-configurator decides whether the C stubs use the CRC instructions, and at run time a CPUID check decides whether to call them; Crc.has_hardware_crc says which way it went. On x86_64, SSE4.2 speeds up CRC-32C. On ARM, the CRC extension speeds up both CRC-32 and CRC-32C. All other targets, js_of_ocaml and wasm_of_ocaml included, run the slicing-by-8 code.

API #

lib/crc.mli is the reference, which dune build @doc renders with odoc. It has one group per checksum: crc16_ccitt, crc16_x25, crc32, crc32c, crc32_proximity1, internet_checksum and adler32, each with its _bytes variant and, where it applies, _rope, _update and _combine. internet_replace16 updates an Internet checksum for one changed 16-bit word (RFC 1624).

License #

ISC. See LICENSE.md.