const POLY: u32 = 0x82F6_3B78;
const TABLES: [[u32; 256]; 8] = build_tables();
const fn build_tables() -> [[u32; 256]; 8] {
let mut tables = [[0u32; 256]; 8];
let mut n = 0usize;
while n < 256 {
let mut crc = n as u32;
let mut bit = 0;
while bit < 8 {
crc = if crc & 1 != 0 {
POLY ^ (crc >> 1)
} else {
crc >> 1
};
bit += 1;
}
tables[0][n] = crc;
n += 1;
}
let mut k = 1usize;
while k < 8 {
let mut n = 0usize;
while n < 256 {
let prev = tables[k - 1][n];
tables[k][n] = (prev >> 8) ^ tables[0][(prev & 0xff) as usize];
n += 1;
}
k += 1;
}
tables
}
#[must_use]
pub fn crc32c(seed: u32, data: &[u8]) -> u32 {
let [t0, t1, t2, t3, t4, t5, t6, t7] = &TABLES;
let (words, tail) = data.as_chunks::<8>();
let mut crc = seed;
for word in words {
let low = crc ^ crate::bytes::get_u32(word, 0);
crc = t7[(low & 0xff) as usize]
^ t6[((low >> 8) & 0xff) as usize]
^ t5[((low >> 16) & 0xff) as usize]
^ t4[(low >> 24) as usize]
^ t3[usize::from(word[4])]
^ t2[usize::from(word[5])]
^ t1[usize::from(word[6])]
^ t0[usize::from(word[7])];
}
for &byte in tail {
crc = (crc >> 8) ^ t0[((crc ^ u32::from(byte)) & 0xff) as usize];
}
crc
}
#[cfg(test)]
mod tests {
use super::*;
fn bitwise(seed: u32, data: &[u8]) -> u32 {
let mut crc = seed;
for &byte in data {
crc ^= u32::from(byte);
for _ in 0..8 {
crc = if crc & 1 != 0 {
POLY ^ (crc >> 1)
} else {
crc >> 1
};
}
}
crc
}
fn noise(len: usize, mut state: u64) -> Vec<u8> {
(0..len)
.map(|_| {
state = state
.wrapping_mul(6_364_136_223_846_793_005)
.wrapping_add(1_442_695_040_888_963_407);
(state >> 56) as u8
})
.collect()
}
#[test]
fn matches_the_standard_check_value() {
assert_eq!(crc32c(!0, b"123456789") ^ !0, 0xE306_9283);
}
#[test]
fn empty_input_returns_the_seed() {
assert_eq!(crc32c(0, b""), 0);
assert_eq!(crc32c(0xdead_beef, b""), 0xdead_beef);
}
#[test]
fn continuation_equals_a_single_pass() {
let whole = crc32c(!0, b"ferrosys");
let split = crc32c(crc32c(!0, b"ferro"), b"sys");
assert_eq!(whole, split);
}
#[test]
fn known_seed_over_a_single_zero_byte() {
assert_eq!(crc32c(0, &[0]), TABLES[0][0]);
assert_eq!(crc32c(0, &[0]), 0);
}
#[test]
fn every_table_is_its_byte_followed_by_that_many_zero_bytes() {
for (k, table) in TABLES.iter().enumerate() {
for byte in 0..=255u8 {
let mut message = vec![0u8; k + 1];
message[0] = byte;
assert_eq!(table[usize::from(byte)], bitwise(0, &message), "table {k}");
}
}
}
#[test]
fn every_length_and_alignment_matches_the_bitwise_definition() {
let bytes = noise(4096 + 8, 0x5eed);
for start in 0..8 {
for len in 0..80 {
let data = &bytes[start..start + len];
for seed in [0, !0, 0x1234_5678] {
assert_eq!(
crc32c(seed, data),
bitwise(seed, data),
"start {start}, length {len}, seed {seed:#x}"
);
}
}
}
assert_eq!(crc32c(!0, &bytes[3..4099]), bitwise(!0, &bytes[3..4099]));
}
}