Skip to content
zit Artifact [57429c29f4]
Login

Artifact [57429c29f4]

Check-ins Using Download Hex

Artifact 57429c29f4a67a9bfaebad8d5826471f9ff26cfd085c5424bf8e0fccba376bb4:

//! 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");

/// 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;
        // 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));
    }
}