nish/compress/checksum

The two checksums the compressed formats carry: CRC-32 (ISO 3309, the polynomial gzip's trailer uses, RFC 1952 §8) and Adler-32 (zlib's trailer, RFC 1950 §9).

import {
  Crc32,
  adler32,
  adler32Update,
  crc32,
} from "nish/compress/checksum";
import { Crc32 } from "nish/compress/checksum";

const crc = new Crc32(); // the tables, once
let c: u32 = crc.update(toU32(0), body, 0, 100);
c = crc.update(c, body, 100, toI32(body.length) - 100); // the same as one call
Keep a `Crc32`

A module's only state is zero-filled storage, so CRC-32's tables live in a Crc32 object: build one and keep it, because building it is 4,096 table entries (about ten microseconds) and an update of a 5 KB body is under one. crc32 is the one-off convenience that builds a table for one call.

CRC-32 is slicing-by-8

eight 256-entry tables, eight bytes per step with one table read per byte and no dependency between the reads of a step (Kounavis and Berry, "A Systematic Approach to Building High Performance Software-based CRC Generators", 2005). From 80 bytes on it is also braided five ways (Kadatch and Jenkins, 2010), so five steps are in flight at once; the braids have a second set of eight tables. Adler-32 defers its two modulo reductions to once every 5,552 bytes, the most that cannot overflow 32 bits (RFC 1950 §9 and zlib's NMAX).

Neither is a cryptographic hash

both detect accidental corruption only. Written from the specifications, not ported from another implementation.

What is unchecked

The table reads in update are nish:unsafe's uncheckedGet: every index is a byte plus a multiple of 256 below 2,048, and both tables are built here at exactly that length and never replaced, which is the whole proof. The input window is checked once, before the loop.

Functions

adler32

The Adler-32 of buf[off .. off + len). A window outside buf panics.

const adler32: (buf: u8[], off: i32, len: i32) => u32
bufu8[]required

The array that holds the bytes to checksum.

offi32required

Where in buf the bytes start.

leni32required

How many bytes to checksum; 0 answers 1.

returnsu32

The Adler-32 of the window, the value zlib's trailer carries.

adler32Update

The Adler-32 of the bytes adler was the Adler-32 of, followed by buf[off .. off + len) (RFC 1950 §9). Start a new checksum from 1. A window outside buf panics.

const adler32Update: (
  adler: u32,
  buf: u8[],
  off: i32,
  len: i32,
) => u32
adleru32required

The Adler-32 of the bytes before this window, as the last call answered it, or 1 to start a new checksum.

bufu8[]required

The array that holds the bytes to add.

offi32required

Where in buf the bytes start.

leni32required

How many bytes to add; 0 answers adler unchanged.

returnsu32

The Adler-32 of everything so far, to pass as adler to the next call, or to use as the finished checksum.

crc32

The CRC-32 of buf[off .. off + len). It builds a Crc32 for the one call, which costs about as much as checksumming 5 KB: keep a Crc32 for anything repeated. A window outside buf panics.

const crc32: (buf: u8[], off: i32, len: i32) => u32
bufu8[]required

The array that holds the bytes to checksum.

offi32required

Where in buf the bytes start.

leni32required

How many bytes to checksum; 0 answers 0.

returnsu32

The CRC-32 of the window, the value gzip's trailer carries.

Classes

Crc32

CRC-32's lookup tables, built once and read by every update. The object holds nothing else, so one may be shared by every compressor and reader in a thread, and by threads that only read it.

class Crc32
Member
new Crc32() Builds the eight tables and their braided form.
update(crc: u32, buf: u8[], off: i32, len: i32): u32 The CRC-32 of the bytes crc was the CRC of, followed by buf[off .. off + len). Start a new checksum from 0. A window outside buf panics. Neither the object nor buf is changed.