ldeflate/src/crc32.rs
//! 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"
);
}
}
}