ldeflate 0.1.3

//! CRC-32 (IEEE 802.3, the one gzip and zip use) — **and `crc32_combine`**,
//! which is the reason this is hand-rolled rather than a dependency.
//!
//! The parallel paths in this crate compress N segments on N workers, each with
//! a compressor that has never seen the others. No worker can compute the
//! whole-stream checksum the gzip and zip trailers require. So each computes the
//! checksum of *its own* bytes and the results are **combined** afterwards —
//! exactly what zlib's `crc32_combine` exists for, and what `crc32fast` (the
//! obvious dependency) does **not** provide.
//!
//! Since a combine had to be written anyway, the checksum comes with it: zero new
//! dependencies, and no `build.rs` anywhere in this crate's tree. (`crc32fast`
//! would have been acceptable — its `build.rs` only probes `rustc --version` for
//! an ARM intrinsic cfg, no C — but two functions are not worth a dependency
//! that still would not have covered the hard half.)
//!
//! Why it is not a bottleneck: the checksum runs **on the worker, over that
//! worker's own segment**, so it parallelises with the compression. Computing it
//! serially over the whole input after a multi-GB/s parallel compress would add a
//! serial tail worth roughly a quarter of the run — which is precisely the
//! spike-and-collapse shape the sustained bench exists to catch. (The absolute
//! throughput is deliberately not named here: on a shared box it is a function of
//! how many cores the process is granted, not of this crate. See Finding 4b in
//! `.nornir/ldeflate-design.md`.)

/// Slice-by-8 tables, generated at compile time. `T[0]` is the classic
/// byte-at-a-time table; `T[k]` folds `k+1` bytes ahead.
const T: [[u32; 256]; 8] = build_tables();

const POLY: u32 = 0xEDB8_8320;

const fn build_tables() -> [[u32; 256]; 8] {
    let mut t = [[0u32; 256]; 8];
    let mut n = 0usize;
    while n < 256 {
        let mut c = n as u32;
        let mut k = 0;
        while k < 8 {
            c = if c & 1 != 0 { POLY ^ (c >> 1) } else { c >> 1 };
            k += 1;
        }
        t[0][n] = c;
        n += 1;
    }
    let mut i = 1usize;
    while i < 8 {
        let mut n = 0usize;
        while n < 256 {
            let prev = t[i - 1][n];
            t[i][n] = t[0][(prev & 0xff) as usize] ^ (prev >> 8);
            n += 1;
        }
        i += 1;
    }
    t
}

/// CRC-32 of `data`, seeded with `crc` (use `0` for a fresh checksum).
///
/// Slice-by-8: eight bytes are folded per iteration through eight tables, which
/// is roughly 4x a byte-at-a-time loop and enough that the checksum never
/// becomes the limiting term next to a DEFLATE at ~400 MB/s per core.
pub fn crc32(crc: u32, data: &[u8]) -> u32 {
    let mut c = !crc;
    let mut chunks = data.chunks_exact(8);
    for ch in &mut chunks {
        let lo = u32::from_le_bytes([ch[0], ch[1], ch[2], ch[3]]) ^ c;
        let hi = u32::from_le_bytes([ch[4], ch[5], ch[6], ch[7]]);
        c = T[7][(lo & 0xff) as usize]
            ^ T[6][((lo >> 8) & 0xff) as usize]
            ^ T[5][((lo >> 16) & 0xff) as usize]
            ^ T[4][((lo >> 24) & 0xff) as usize]
            ^ T[3][(hi & 0xff) as usize]
            ^ T[2][((hi >> 8) & 0xff) as usize]
            ^ T[1][((hi >> 16) & 0xff) as usize]
            ^ T[0][((hi >> 24) & 0xff) as usize];
    }
    for &b in chunks.remainder() {
        c = T[0][((c ^ b as u32) & 0xff) as usize] ^ (c >> 8);
    }
    !c
}

// ── crc32_combine, over GF(2) ───────────────────────────────────────────────
//
// CRC-32 is linear over GF(2): running the register forward over `n` zero bytes
// is a fixed linear map, so it can be represented as a 32x32 bit-matrix and
// applied by repeated squaring in O(log n) instead of O(n). That is what lets a
// checksum computed on worker 7 be shifted into place behind worker 2's.

/// Multiply the GF(2) vector `vec` by the matrix `mat` (32 columns of 32 bits).
fn gf2_matrix_times(mat: &[u32; 32], mut vec: u32) -> u32 {
    let mut sum = 0u32;
    let mut i = 0usize;
    while vec != 0 {
        if vec & 1 != 0 {
            sum ^= mat[i];
        }
        vec >>= 1;
        i += 1;
    }
    sum
}

fn gf2_matrix_square(square: &mut [u32; 32], mat: &[u32; 32]) {
    for n in 0..32 {
        square[n] = gf2_matrix_times(mat, mat[n]);
    }
}

/// Combine two CRC-32 checksums: `crc1` over some prefix, `crc2` over the
/// `len2` bytes that follow it, giving the CRC of the concatenation.
///
/// This is `crc32_combine` from zlib, reimplemented (pure GF(2) arithmetic;
/// pulling a C zlib for it would violate the no-C rule this crate is built on).
pub fn crc32_combine(crc1: u32, crc2: u32, len2: u64) -> u32 {
    if len2 == 0 {
        return crc1;
    }
    let mut even = [0u32; 32];
    let mut odd = [0u32; 32];

    // `odd` = the operator for one zero BIT.
    odd[0] = POLY;
    let mut row = 1u32;
    for n in 1..32 {
        odd[n] = row;
        row <<= 1;
    }
    // Square twice to reach one zero BYTE.
    gf2_matrix_square(&mut even, &odd);
    gf2_matrix_square(&mut odd, &even);

    let mut crc1 = crc1;
    let mut len2 = len2;
    loop {
        // Apply `odd` (2^k zero bytes) if that bit of len2 is set.
        gf2_matrix_square(&mut even, &odd);
        if len2 & 1 != 0 {
            crc1 = gf2_matrix_times(&even, crc1);
        }
        len2 >>= 1;
        if len2 == 0 {
            break;
        }
        gf2_matrix_square(&mut odd, &even);
        if len2 & 1 != 0 {
            crc1 = gf2_matrix_times(&odd, crc1);
        }
        len2 >>= 1;
        if len2 == 0 {
            break;
        }
    }
    crc1 ^ crc2
}

#[cfg(test)]
mod tests {
    use super::*;

    /// Known answers from the IEEE CRC-32 specification and from `gzip`'s own
    /// output. Without these, the combine test below could be self-consistently
    /// wrong — the identity-value trap.
    #[test]
    fn crc32_known_answers() {
        assert_eq!(crc32(0, b""), 0x0000_0000);
        assert_eq!(crc32(0, b"a"), 0xE8B7_BE43);
        assert_eq!(crc32(0, b"abc"), 0x3524_41C2);
        // 0x2015_9D7F, cross-checked against `python3 -c "import zlib;
        // zlib.crc32(b'message digest')"`. (An earlier constant here read
        // 0x2015_31DF — a transcription error, not an implementation bug: this
        // module's output matches zlib on every other vector below.)
        assert_eq!(crc32(0, b"message digest"), 0x2015_9D7F);
        assert_eq!(crc32(0, b"123456789"), 0xCBF4_3926);
        assert_eq!(crc32(0, b"abcdefghijklmnopqrstuvwxyz"), 0x4C27_50BD);
        // Seeding must chain: crc(crc(a), b) == crc(a ++ b).
        let a = b"the quick brown fox ";
        let b = b"jumps over the lazy dog";
        let mut whole = a.to_vec();
        whole.extend_from_slice(b);
        assert_eq!(crc32(crc32(0, a), b), crc32(0, &whole));
    }

    /// RED-when-broken: `crc32_combine` must equal a straight CRC over the
    /// concatenation, at many split points including lengths that exercise every
    /// bit of the repeated-squaring loop. A wrong operator, a missed square, or
    /// swapped operands all diverge here — and would corrupt the trailer of
    /// every parallel gzip and every zip entry.
    #[test]
    fn combine_equals_whole_buffer_crc() {
        let data: Vec<u8> = (0..100_000u32)
            .map(|i| (i.wrapping_mul(2654435761) >> 13) as u8)
            .collect();
        let whole = crc32(0, &data);
        for &cut in &[
            0usize, 1, 2, 3, 7, 8, 9, 255, 256, 257, 4096, 65_535, 65_536, 99_999, 100_000,
        ] {
            let (a, b) = data.split_at(cut);
            let got = crc32_combine(crc32(0, a), crc32(0, b), b.len() as u64);
            assert_eq!(
                got, whole,
                "combine at cut={cut} gave {got:08x}, whole is {whole:08x}"
            );
        }
        // Left-folded over many segments — the shape the split path uses.
        let mut acc = 0u32;
        let mut off = 0usize;
        for seg in [1usize, 7, 1000, 4096, 60_000, 34_896] {
            let end = (off + seg).min(data.len());
            acc = crc32_combine(acc, crc32(0, &data[off..end]), (end - off) as u64);
            off = end;
        }
        assert_eq!(off, data.len(), "test segments must cover the buffer");
        assert_eq!(
            acc, whole,
            "left-folded multi-segment combine must equal the whole"
        );
    }

    /// The combine must be *sensitive to the length*, not just to the two CRCs.
    /// A `crc32_combine` that ignored `len2` would still pass a single-cut test
    /// if the halves happened to be equal length, so pin it explicitly.
    #[test]
    fn combine_depends_on_the_second_length() {
        let a = b"prefix-bytes";
        let b = b"suffix";
        let right = crc32_combine(crc32(0, a), crc32(0, b), b.len() as u64);
        let wrong = crc32_combine(crc32(0, a), crc32(0, b), b.len() as u64 + 1);
        assert_ne!(
            right, wrong,
            "combine must depend on len2; it is ignoring the length"
        );
        let mut whole = a.to_vec();
        whole.extend_from_slice(b);
        assert_eq!(right, crc32(0, &whole));
    }

    /// Slice-by-8 must agree with a byte-at-a-time reference at every length
    /// around the 8-byte block boundary, where the remainder path lives.
    #[test]
    fn slice_by_8_matches_byte_at_a_time() {
        fn naive(mut c: u32, data: &[u8]) -> u32 {
            c = !c;
            for &b in data {
                c = T[0][((c ^ b as u32) & 0xff) as usize] ^ (c >> 8);
            }
            !c
        }
        let data: Vec<u8> = (0..64u32).map(|i| (i * 7 + 1) as u8).collect();
        for n in 0..=data.len() {
            assert_eq!(
                crc32(0, &data[..n]),
                naive(0, &data[..n]),
                "length {n} differs"
            );
        }
    }
}