- OCaml 86%
- C 8%
- Python 3%
- JavaScript 1%
- WebAssembly 1%
- 1 more language <1%
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.