Artifact 5ca5369bc091b829ba240d1e7209098bc6dbe1d7cc8d14106f2224ec0a1df3b7:
- File
src/crc32.zig
— part of check-in
[b82aacc805]
at
2026-08-24 17:53:32
on branch crc-hardware-143
— crc32: fold with ARMv8's crc32 instruction where the target has it
Checksumming was half the cost of opening a repository: 18.8ms of a 37ms `ls` on a 302MB store, across the two sidecars (26.3MB derived-state image at 13.5ms, 9.7MB log index at 5.3ms). Both measured by doubling the work and taking the delta, so the number is the checksum and not its neighbours.
ARMv8's crc32b/crc32x implement CRC-32/ISO-HDLC -- the same generator this file is already defined in terms of, in the same reflected convention -- so this is an instruction-count change and never a value change, which is what the module doc says every edit here must be. tcl opens in 24.5ms against 38.5ms, output byte-identical.
aarch64 only, deliberately. x86_64's SSE4.2 crc32 instruction is CRC-32C/Castagnoli, a DIFFERENT generator; taking it because the mnemonic matches would orphan every store already written. x86_64 keeps the table path, which stays load-bearing rather than becoming a fallback nobody runs.
The new test recomputes CRC-32 as a plain bit-at-a-time recurrence, independent of update and its tables, and holds both paths to it at every length 0..1024 -- all eight residues mod 8, including the lengths below the fold width. The two paths differ only in where the fold stops and the tail begins, so a divergence would appear at particular residues and nowhere else, which is the shape a spot check misses. Chunked updates are pinned too: the store checksums payloads in 4 KiB pieces, so a path correct only for single-shot input would corrupt exactly the largest artifacts.
Refs #143 (user: dmestas, size: 26149) [annotate] [blame] [check-ins using] [more...]
//! 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(); } }; // --------------------------------------------------------------------------- // 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()); }