//! CRC-32/ISO-HDLC, bit-identical to `std.hash.Crc32`, consuming eight bytes
//! per iteration instead of one.
//!
//! No RFC section stands behind this file: it is not a format, it is the
//! checksum the storage engine's formats are already defined in terms of.
//! `logstore.zig`'s four on-disk checksums (file header over bytes [0,60), the
//! 6-byte frame prefix, the 18+hash_len frame header, and the whole frame with
//! its align-8 pad excluded), `repocache.zig`'s image self-checksum,
//! `bisect.zig`'s session trailer and `undo.zig`'s journal trailer are all
//! CRC-32/ISO-HDLC. This file changes the instruction count, never the value:
//! the output is a frozen part of those formats, so a divergence at any length
//! would not degrade — it would orphan every `.zit` file already written and
//! turn a pending undo into unrecoverable data loss.
//!
//! WHY it exists at all: `std.hash.Crc32` is the generic `Crc(u32, ...)` in
//! `std/hash/crc/impl.zig`, which walks one byte per iteration through one
//! 256-entry table — measured at ~348 MB/s here, which is ~93% of a repository
//! open (a 416 MB store opens in 1.31 s, of which ~1.20 s is that loop). std
//! offers no faster variant to switch to: `std.hash.crc.Crc32WithPoly` and
//! `Crc32SmallWithPoly` are re-exported at `std/hash/crc.zig:6-8` but `impl.zig`
//! declares neither, so those names are dangling in Zig 0.16. Vendoring is the
//! only path.
//!
//! TECHNIQUE — slicing-by-N, from Michael E. Kounavis and Frank L. Berry,
//! "Novel Table Lookup-Based Algorithms for High-Performance CRC Generation"
//! (IEEE Transactions on Computers 57(11), 2008; first published by Intel as
//! "A Systematic Approach to Building High Performance Software-Based CRC
//! Generators", ISCC 2005), generalized and analysed by Andrew Kadatch and Bob
//! Jenkins in "Everything we know about CRC but afraid to forget" (2010) and
//! implemented in their crcutil library. The insight is that the byte-at-a-time
//! recurrence is linear over GF(2), so the contribution of a byte at distance k
//! from the end of a block can be precomputed into its own 256-entry table;
//! eight such tables let eight bytes fold in one dependency step rather than
//! eight serial ones. Nothing here is novel — this is their algorithm
//! transcribed, and its correctness argument is theirs.
const std = @import("std");
const builtin = @import("builtin");
/// Whether this target folds bytes with one instruction instead of eight table
/// lookups.
///
/// ARMv8's `crc32b/h/w/x` implement CRC-32/ISO-HDLC -- the SAME generator this
/// file is defined in terms of (0x04C11DB7, reflected 0xEDB88320) -- in the
/// same reflected register convention `update` already keeps. So this changes
/// the instruction count and never the value, which the module doc above says
/// every edit here must preserve.
///
/// Deliberately aarch64-only. x86_64's SSE4.2 `crc32` instruction is
/// CRC-32C/Castagnoli, a DIFFERENT generator: reaching for it because the
/// mnemonic matches would silently produce a different checksum and orphan
/// every `.zit` already written. The portable route there is PCLMULQDQ
/// carry-less folding, a different algorithm again and not attempted here --
/// x86_64 keeps the table path, which is why that path stays load-bearing
/// rather than becoming a fallback nobody runs.
const hardware = builtin.cpu.arch == .aarch64 and
std.Target.aarch64.featureSetHas(builtin.cpu.features, .crc);
/// CRC-32/ISO-HDLC (a.k.a. CRC-32, PKZIP, zlib crc32) in reflected form: the
/// generator 0x04C11DB7 bit-reversed. `std.hash.Crc32` builds exactly this
/// constant via `@bitReverse` and this file hardcodes it, so the two tables are
/// the same table.
const reflected_polynomial: u32 = 0xEDB88320;
/// Bytes folded per main-loop iteration, and therefore the number of 256-entry
/// tables. Eight, not sixteen: sixteen measured ~26% faster in isolation, but
/// doubles the table to 16 KiB — half of a typical x86_64 32 KiB L1 data cache,
/// which the scan must share with its own chunk buffer and everything else
/// `scanOneFrame` touches. Eight keeps the table at 8 KiB and already removes
/// ~82% of the checksum cost; the remainder is not worth an L1 footprint that
/// only benchmarks well in isolation.
///
/// This is NOT a one-constant knob, and `update` pins that with a comptime
/// assert. The fold there is hand-unrolled to exactly eight bytes and names
/// `tables[7]..tables[0]` literally, so raising this alone would double the
/// `.rodata` to the 16 KiB the paragraph above rejects while still folding only
/// eight bytes per iteration — a pure pessimization, and an invisible one: the
/// *output* stays correct, so every test in this tree still passes. Revisiting
/// the trade means rewriting the fold body and this constant together.
const slices: usize = 8;
/// The slicing tables. `tables[0]` is the ordinary byte-at-a-time table, bit for
/// bit the one `std.hash.Crc32` generates. `tables[k]` is `tables[0]` advanced k
/// further byte positions: entry i of one table is the entry the previous table
/// would reach after shifting one more byte through the register. Generated at
/// comptime, so this is 8 KiB of `.rodata` and no initialization at run time.
const tables: [slices][256]u32 = blk: {
// 256 entries x 8 shift steps to build tables[0], plus 7 x 256 derivations.
// Measured minimum accepted quota is 8000 (4000 fails); 20000 leaves
// headroom for a wider fold, should the fold body in `update` ever be
// rewritten for one.
@setEvalBranchQuota(20_000);
var t: [slices][256]u32 = undefined;
for (&t[0], 0..) |*entry, i| {
var crc: u32 = i;
var bit: usize = 0;
while (bit < 8) : (bit += 1) crc = (crc >> 1) ^ ((crc & 1) * reflected_polynomial);
entry.* = crc;
}
var s: usize = 1;
while (s < slices) : (s += 1) {
for (&t[s], 0..) |*entry, i| {
const prev = t[s - 1][i];
entry.* = (prev >> 8) ^ t[0][prev & 0xFF];
}
}
// Cheap comptime pins on the generated table, so a mistyped polynomial or a
// broken derivation is a compile error rather than a corrupt repository.
// tables[0][0x80] is the reflected polynomial itself (one shift of the top
// bit); every table's entry 0 is 0 because the zero polynomial stays zero.
std.debug.assert(t[0][0x80] == reflected_polynomial);
for (t) |slice_table| std.debug.assert(slice_table[0] == 0);
break :blk t;
};
/// Drop-in for `std.hash.Crc32`: same four-call surface (`init`, `update`,
/// `final`, `hash`), same register semantics.
///
/// The register invariant that makes the swap safe: after any prefix of bytes,
/// `crc` holds exactly the value std's `Crc32` would hold — R0 = 0xFFFFFFFF,
/// R(n+1) = tables[0][(Rn ^ b) & 0xFF] ^ (Rn >> 8). Agreeing on `final()` is not
/// enough: `logstore.zig`'s `scanOneFrame` and `readFrameAt` resume the same
/// register across separately-read buffers, so agreement must hold at every byte
/// boundary, at every chunk length, from every intermediate register value.
/// Slicing-by-8 satisfies this because it is an algebraic rewrite of that same
/// recurrence, not an approximation of it.
pub const Crc32 = struct {
/// The reflected register, pre-final-xor. 0xFFFFFFFF at init: std computes
/// `@bitReverse(@as(u32, 0xFFFFFFFF))`, which is the same value.
crc: u32,
pub fn init() Crc32 {
return .{ .crc = 0xFFFFFFFF };
}
/// Folds `bytes` into the register: eight bytes per iteration while eight
/// remain, then byte-at-a-time for the 0..7-byte tail.
///
/// The tail is not a rare case here — it is most of the call sites. The
/// frame prefix checksum is exactly 6 bytes and is the single most
/// frequently executed update in the store; a frame header window is 19..50;
/// `scanOneFrame`'s seed is 22 + hash_len (23..54, never a multiple of 8 for
/// any hash zit uses). Only the 4 KiB payload chunks and the whole-image
/// checksums reach the fast path in bulk — and those are the bytes that
/// dominate, which is the whole point.
pub fn update(self: *Crc32, bytes: []const u8) void {
// The fold below is hand-unrolled to eight bytes and eight literally
// named tables, so the width and `slices` must move together. Without
// this pin, raising `slices` alone compiles, keeps folding eight bytes,
// doubles the table, and passes every test in the tree — the failure is
// a silent pessimization no gate can report, because the checksum
// values never change. Comptime, so it costs nothing at run time.
comptime std.debug.assert(slices == 8);
var crc = self.crc;
var rest = bytes;
// `@inComptime` because this file's own golden vectors are folded at
// COMPTIME, where inline asm cannot run. Comptime evaluation therefore
// takes the table path -- which is what keeps those vectors a CHECK on
// the hardware path rather than a restatement of it.
if (comptime hardware) if (!@inComptime()) {
// One `crc32x` per eight bytes. The register chains through the
// instruction instead of through eight table loads, so the fold is
// latency-bound on a 3-cycle instruction rather than on L1.
while (rest.len >= 8) {
const v = std.mem.readInt(u64, rest[0..8], .little);
crc = asm ("crc32x %[out:w], %[in:w], %[val:x]"
: [out] "=r" (-> u32),
: [in] "r" (crc),
[val] "r" (v),
);
rest = rest[8..];
}
std.debug.assert(rest.len < 8);
for (rest) |byte| {
crc = asm ("crc32b %[out:w], %[in:w], %[val:w]"
: [out] "=r" (-> u32),
: [in] "r" (crc),
[val] "r" (byte),
);
}
self.crc = crc;
return;
};
// Bounded: `rest` shrinks by exactly 8 each iteration, so the trip count
// is bytes.len / 8 and cannot be influenced by the data.
while (rest.len >= 8) {
// The register XORs into the LOW four bytes only. That is the whole
// trick: it concentrates the register dependency on the *earliest*
// bytes, so the four high bytes' table lookups do not wait on it and
// all eight loads can issue in parallel.
//
// `readInt(..., .little)` is doing double duty — an unaligned-safe
// load (call sites hand in allocator-owned slices at arbitrary
// alignment) and an endianness normaliser, so a big-endian target
// folds the same bytes in the same order. It is the same primitive
// `logstore.zig` already uses for every on-disk field.
const low = std.mem.readInt(u32, rest[0..4], .little) ^ crc;
const high = std.mem.readInt(u32, rest[4..8], .little);
// The table index DESCENDS as the byte position advances, and that
// direction is the whole correctness argument: `tables[k]` advances
// a byte k further positions, and the earliest byte of the block
// (`low & 0xFF`) is the one that must travel the remaining seven
// positions to reach the block's end — so it takes `tables[7]`,
// while the last byte (`high >> 24`) has none left to travel and
// takes `tables[0]`. Reversing this ordering still produces a
// self-consistent checksum that agrees with itself at every length,
// and would pass every test in this tree that does not diff against
// std. It is the single easiest way to silently orphan the store.
//
// `low >> 24` and `high >> 24` need no `& 0xFF`: a u32 shifted right
// 24 already fits a u8. Masking them would be dead work, and their
// absence here is deliberate rather than an omission.
crc = tables[7][low & 0xFF] ^
tables[6][(low >> 8) & 0xFF] ^
tables[5][(low >> 16) & 0xFF] ^
tables[4][low >> 24] ^
tables[3][high & 0xFF] ^
tables[2][(high >> 8) & 0xFF] ^
tables[1][(high >> 16) & 0xFF] ^
tables[0][high >> 24];
rest = rest[8..];
}
// Pins the exact handoff between the two loops. A future edit that
// changes the fold width without changing the guard lands here.
std.debug.assert(rest.len < 8);
for (rest) |byte| crc = tables[0][(crc ^ byte) & 0xFF] ^ (crc >> 8);
self.crc = crc;
}
/// std's `final()` reduces to this one xor for this algorithm: `reflect_in`
/// and `reflect_out` are both true, so its `@bitReverse` branch and its
/// width-shift branch are both dead, leaving `crc ^ xor_output`.
pub fn final(self: Crc32) u32 {
return self.crc ^ 0xFFFFFFFF;
}
pub fn hash(bytes: []const u8) u32 {
var c = Crc32.init();
c.update(bytes);
return c.final();
}
};
/// The checksum of `a ++ b` from `crc_a = hash(a)`, `crc_b = hash(b)` and
/// `b.len` alone, without the bytes: what lets a writer stream a body whose
/// header it learns last and still checksum header-first. O(log len_b).
///
/// TECHNIQUE -- Mark Adler's `crc32_combine` (zlib `crc32.c`, the
/// `multmodp`/`x2nmodp` form of zlib 1.2.12): appending n zero bytes
/// multiplies the register by x^(8n) modulo the generator, and the
/// pre/post-conditioning of the two operands cancels to a plain xor.
pub fn combine(crc_a: u32, crc_b: u32, len_b: u64) u32 {
// x^8, the factor of one zero byte, as a reflected polynomial (x^0 is the
// top bit).
var x2k: u32 = 1 << 30; // x^1
for (0..3) |_| x2k = multModP(x2k, x2k);
var p: u32 = 1 << 31; // x^0
var n = len_b;
while (n != 0) : (n >>= 1) {
if (n & 1 != 0) p = multModP(x2k, p);
x2k = multModP(x2k, x2k);
}
return multModP(p, crc_a) ^ crc_b;
}
/// a * b modulo the generator, both reflected. `a` is a power of x, never 0.
fn multModP(a: u32, b_in: u32) u32 {
std.debug.assert(a != 0);
var b = b_in;
var m: u32 = 1 << 31;
var p: u32 = 0;
while (true) {
if (a & m != 0) {
p ^= b;
if (a & (m - 1) == 0) break;
}
m >>= 1;
b = if (b & 1 != 0) (b >> 1) ^ reflected_polynomial else b >> 1;
}
return p;
}
// ---------------------------------------------------------------------------
// Tests.
//
// `std.hash.Crc32` is referenced here permanently, as the live differential
// oracle. It costs 1 KiB of table in the test binary and is the only thing that
// can catch a resume bug at a chunk boundary this file did not think to name.
// ---------------------------------------------------------------------------
/// The catalogue check value for CRC-32/ISO-HDLC (the CRC of "123456789").
/// Pinned as a literal because every other checksum test in this tree is
/// self-consistent — it recomputes the expectation with the function under test,
/// or asserts only that a deliberate bitflip is *detected*. An implementation
/// that is internally consistent but numerically shifted passes all of those and
/// silently orphans every repository on disk. This constant and the golden table
/// below are the only things in the tree that can catch that.
const catalogue_check: u32 = 0xCBF43926;
comptime {
// Proven at compile time for the one input the standards catalogue pins, so
// a broken table cannot even link — on every target, including the ones no
// test here ever runs on.
std.debug.assert(Crc32.hash("123456789") == catalogue_check);
std.debug.assert(Crc32.hash("") == 0);
}
test "crc32: matches the CRC-32/ISO-HDLC catalogue check value" {
try std.testing.expectEqual(catalogue_check, Crc32.hash("123456789"));
try std.testing.expectEqual(@as(u32, 0), Crc32.hash(""));
}
/// A golden table frozen as literals, derived from an OUTSIDE oracle (Python's
/// `zlib.crc32`) rather than from this file or from std. The differential tests
/// below compare against whatever std currently IS; this one compares against
/// what CRC-32/ISO-HDLC has always been -- the value actually written into every
/// existing repository. It is the test that survives std changing under us, and
/// the only one an implementation that is internally consistent but numerically
/// shifted cannot satisfy.
///
/// Never re-capture these from the implementation under test. If they fail, the
/// implementation is wrong or the generator below moved; re-deriving them from
/// whatever the tree currently computes would silently re-baseline the one test
/// that can catch a shift.
const golden = [_]struct { len: usize, crc: u32 }{
.{ .len = 0, .crc = 0x00000000 },
.{ .len = 1, .crc = 0xCFB5FFE9 },
.{ .len = 2, .crc = 0x34AE0673 },
.{ .len = 3, .crc = 0x503EB54A },
.{ .len = 4, .crc = 0xE58AEAC8 },
.{ .len = 5, .crc = 0x07872483 },
.{ .len = 6, .crc = 0x960145DA },
.{ .len = 7, .crc = 0x5DF17037 },
.{ .len = 8, .crc = 0xEF878B2A },
.{ .len = 9, .crc = 0x71516872 },
.{ .len = 10, .crc = 0x74CFE982 },
.{ .len = 11, .crc = 0x06CD1086 },
.{ .len = 12, .crc = 0x26D097CC },
.{ .len = 13, .crc = 0xA023589F },
.{ .len = 14, .crc = 0xBA7F7F2D },
.{ .len = 15, .crc = 0xB3D36F21 },
.{ .len = 16, .crc = 0xC1DDA4B4 },
.{ .len = 31, .crc = 0x529ACA5D },
.{ .len = 32, .crc = 0x7F37FD01 },
.{ .len = 33, .crc = 0x38A89F49 },
.{ .len = 60, .crc = 0x89CA7735 },
.{ .len = 63, .crc = 0x5722C6E9 },
.{ .len = 64, .crc = 0x09EE049D },
.{ .len = 65, .crc = 0x5503A25B },
.{ .len = 127, .crc = 0xFB7C28EC },
.{ .len = 128, .crc = 0x89273DB8 },
.{ .len = 129, .crc = 0x55836B62 },
.{ .len = 255, .crc = 0x1F4EA111 },
.{ .len = 256, .crc = 0x0D7D4EEF },
.{ .len = 257, .crc = 0x92D099A5 },
.{ .len = 511, .crc = 0xB12A332E },
.{ .len = 512, .crc = 0x296789DB },
.{ .len = 513, .crc = 0x1AFCD984 },
.{ .len = 1023, .crc = 0xED744C0C },
.{ .len = 1024, .crc = 0xAB332365 },
.{ .len = 1025, .crc = 0xB074C171 },
.{ .len = 2047, .crc = 0x3C05EC24 },
.{ .len = 2048, .crc = 0x66355456 },
.{ .len = 2049, .crc = 0x74D88DBE },
.{ .len = 4095, .crc = 0xF5978AE6 },
.{ .len = 4096, .crc = 0xB747A1C1 },
};
/// The seed the golden buffer is generated from. Changing it, or the recurrence
/// in `fillGolden`, invalidates every literal above -- so both are named here
/// rather than inlined.
const golden_seed: u64 = 0x9E37_79B9_7F4A_7C15;
/// The golden buffer's generator, deliberately written out here instead of using
/// `std.Random`. `DefaultPrng` is an ALIAS (Xoshiro256++ today, Xoroshiro128+
/// before) and upstream has re-pointed it before. If it moves again a
/// std-generated buffer changes and all 41 literals fail at once -- which is
/// indistinguishable from a real CRC regression, and the natural repair under
/// time pressure is to re-capture them from the current implementation: exactly
/// the circular capture this table exists to prevent. An in-file LCG has no
/// upstream to move. Constants are Knuth's MMIX multiplier and increment; the
/// high bits are taken because an LCG's low bits are its weak ones.
fn fillGolden(buf: []u8) void {
var x: u64 = golden_seed;
for (buf) |*b| {
x = x *% 6364136223846793005 +% 1442695040888963407;
b.* = @truncate(x >> 33);
}
}
test "crc32: matches golden values derived from an outside oracle" {
var buf: [4096]u8 = undefined;
fillGolden(&buf);
for (golden) |g| {
try std.testing.expectEqual(g.crc, Crc32.hash(buf[0..g.len]));
}
}
test "crc32: bit-identical to std.hash.Crc32 at every length across two chunk boundaries" {
// 8200 crosses scanOneFrame's 4096-byte chunk size twice, so every
// (full blocks, tail length) pair the scan can produce is covered.
var buf: [8200]u8 = undefined;
var prng = std.Random.DefaultPrng.init(0x2CB1_9AF3);
prng.random().bytes(&buf);
for (0..buf.len + 1) |len| {
try std.testing.expectEqual(std.hash.Crc32.hash(buf[0..len]), Crc32.hash(buf[0..len]));
}
}
test "crc32: bit-identical from every start alignment" {
// The bulk call sites hand in allocator-owned slices at arbitrary alignment
// (repocache's image, encodeFrame's whole-frame buffer), so the unaligned
// 4-byte loads in the fold must not change the answer.
var buf: [700]u8 = undefined;
var prng = std.Random.DefaultPrng.init(0x51D3_0F17);
prng.random().bytes(&buf);
for (0..64) |offset| {
for (0..600) |len| {
const s = buf[offset..][0..len];
try std.testing.expectEqual(std.hash.Crc32.hash(s), Crc32.hash(s));
}
}
}
test "crc32: the register itself is identical at every split point" {
// The property `final()` equality alone cannot check: two updates must
// compose exactly, from any intermediate register value. Compares `.crc`,
// the pre-final-xor register, because that is what `scanOneFrame` carries
// across preads.
var buf: [300]u8 = undefined;
var prng = std.Random.DefaultPrng.init(0x7E44_C210);
prng.random().bytes(&buf);
for (0..buf.len + 1) |split| {
var mine = Crc32.init();
var theirs = std.hash.Crc32.init();
mine.update(buf[0..split]);
theirs.update(buf[0..split]);
try std.testing.expectEqual(theirs.crc, mine.crc);
mine.update(buf[split..]);
theirs.update(buf[split..]);
try std.testing.expectEqual(theirs.crc, mine.crc);
try std.testing.expectEqual(theirs.final(), mine.final());
}
}
test "crc32: bit-identical under scanOneFrame's exact chunking, every hash_len" {
// Replays the streaming shape of logstore.scanOneFrame: one seed update of
// 22 + hash_len, then 4096-byte chunks, then a payload_len % 4096 tail.
// payload_len == 0 is included: there the loop body never runs at all and
// only the seed update happens.
var buf: [70_000]u8 = undefined;
var prng = std.Random.DefaultPrng.init(0x1AF0_9C63);
prng.random().bytes(&buf);
const payload_lens = [_]usize{ 0, 1, 7, 8, 4095, 4096, 4097, 8191, 8192, 8193, 12_288, 65_535 };
var hash_len: usize = 1;
while (hash_len <= 32) : (hash_len += 1) {
const seed_len = 22 + hash_len;
for (payload_lens) |payload_len| {
std.debug.assert(seed_len + payload_len <= buf.len);
var mine = Crc32.init();
var theirs = std.hash.Crc32.init();
mine.update(buf[0..seed_len]);
theirs.update(buf[0..seed_len]);
var remaining = payload_len;
var pos = seed_len;
while (remaining > 0) {
const take = @min(remaining, 4096);
mine.update(buf[pos..][0..take]);
theirs.update(buf[pos..][0..take]);
pos += take;
remaining -= take;
}
try std.testing.expectEqual(theirs.final(), mine.final());
}
}
}
test "crc32: bit-identical under randomized multi-update chunk splittings" {
var buf: [8200]u8 = undefined;
var prng = std.Random.DefaultPrng.init(0x39B5_7DE1);
const rand = prng.random();
rand.bytes(&buf);
for (0..20_000) |_| {
const total = rand.uintAtMost(usize, buf.len);
var mine = Crc32.init();
var theirs = std.hash.Crc32.init();
var offset: usize = 0;
while (offset < total) {
const take = @min(total - offset, rand.uintAtMost(usize, 200));
mine.update(buf[offset..][0..take]);
theirs.update(buf[offset..][0..take]);
offset += take;
// A zero-length update is legal and must be a no-op; step forward a
// byte so the loop still terminates.
if (take == 0) {
mine.update(buf[offset..][0..1]);
theirs.update(buf[offset..][0..1]);
offset += 1;
}
}
try std.testing.expectEqual(theirs.final(), mine.final());
}
}
test "crc32: bit-identical over the exact frame windows the log writes" {
// The four fixed-width windows logstore.zig checksums, pinned by name so a
// regression names the format field it broke rather than a bare length.
var buf: [64]u8 = undefined;
var prng = std.Random.DefaultPrng.init(0x6D21_88AF);
prng.random().bytes(&buf);
// Frame prefix: len u32 | flags u8 | hash_len u8. The hottest update.
try std.testing.expectEqual(std.hash.Crc32.hash(buf[0..6]), Crc32.hash(buf[0..6]));
// File header: bytes [0, 60), checksum stored at [60, 64).
try std.testing.expectEqual(std.hash.Crc32.hash(buf[0..60]), Crc32.hash(buf[0..60]));
// Frame header: 18 + hash_len, for every hash width the store can carry.
for ([_]usize{ 16, 20, 32 }) |hash_len| {
const window = buf[0 .. 18 + hash_len];
try std.testing.expectEqual(std.hash.Crc32.hash(window), Crc32.hash(window));
}
}
// The hardware path must agree with the table path at EVERY length, not only
// at the golden vectors' lengths. The two differ in where the eight-byte fold
// stops and the byte tail begins, so a disagreement would appear at particular
// residues mod 8 and nowhere else -- exactly the shape a spot check misses.
//
// This file's contract is that the VALUE never changes: these checksums are
// frozen parts of the `.zit` on-disk formats, and a divergence at any length
// would orphan every store already written. So the reference below is a plain
// bit-at-a-time recurrence written out here, independent of `update` and of
// its tables, and both `Crc32` and std are held against it.
test "crc32: the hardware path is bit-identical to the table path at every length" {
var buf: [1024]u8 = undefined;
fillGolden(&buf);
const reference = struct {
fn hash(bytes: []const u8) u32 {
var crc: u32 = 0xFFFFFFFF;
for (bytes) |b| {
crc ^= b;
var k: usize = 0;
while (k < 8) : (k += 1) {
crc = if (crc & 1 != 0) (crc >> 1) ^ reflected_polynomial else crc >> 1;
}
}
return crc ^ 0xFFFFFFFF;
}
}.hash;
// Every length 0..1024 covers all eight residues mod 8 many times over,
// including the 0..7 lengths that never enter the fold at all.
var len: usize = 0;
while (len <= buf.len) : (len += 1) {
const want = reference(buf[0..len]);
try std.testing.expectEqual(want, Crc32.hash(buf[0..len]));
try std.testing.expectEqual(want, std.hash.Crc32.hash(buf[0..len]));
}
// Chunked updates must fold to the same register as one call: the store
// checksums payloads in 4 KiB pieces, so a path correct only for
// single-shot input would corrupt exactly the largest artifacts.
var split = Crc32.init();
split.update(buf[0..7]); // shorter than the fold width
split.update(buf[7..8]); // leaves the register mid-word
split.update(buf[8..333]);
split.update(buf[333..]);
try std.testing.expectEqual(Crc32.hash(&buf), split.final());
}
test "crc32: combine joins two checksums into the checksum of the concatenation" {
var prng = std.Random.DefaultPrng.init(0x7a17c0b1);
const rand = prng.random();
var buf: [3000]u8 = undefined;
rand.bytes(&buf);
const cuts = [_]usize{ 0, 1, 7, 8, 9, 50, 255, 256, 1024, 2999, 3000 };
for (cuts) |cut| {
const a = buf[0..cut];
const b = buf[cut..];
try std.testing.expectEqual(Crc32.hash(&buf), combine(Crc32.hash(a), Crc32.hash(b), b.len));
}
// A second operand far longer than any buffer: the length enters only
// through its bits, so a long zero run checks the squaring chain.
const zeros: [4096]u8 = @splat(0);
var whole = Crc32.init();
whole.update("head");
for (0..64) |_| whole.update(&zeros);
var tail = Crc32.init();
for (0..64) |_| tail.update(&zeros);
try std.testing.expectEqual(whole.final(), combine(Crc32.hash("head"), tail.final(), 64 * zeros.len));
}