const POLY: u32 = 0x82F6_3B78;
const LONG: usize = 8192;
const SHORT: usize = 256;
#[inline]
#[must_use]
pub fn crc32c(data: &[u8]) -> u32 {
crc32c_append(0, data)
}
#[inline]
#[must_use]
pub fn crc32c_append(crc: u32, data: &[u8]) -> u32 {
!update(!crc, data)
}
#[inline]
fn update(reg: u32, data: &[u8]) -> u32 {
#[cfg(target_arch = "x86_64")]
{
if std::arch::is_x86_feature_detected!("sse4.2") {
return unsafe { x86::update(reg, data) };
}
}
#[cfg(target_arch = "aarch64")]
{
if std::arch::is_aarch64_feature_detected!("crc") {
return unsafe { arm::update(reg, data) };
}
}
portable::update(reg, data)
}
const fn mult_mod_p(a: u32, mut b: u32) -> u32 {
let mut m: u32 = 1 << 31;
let mut p: u32 = 0;
loop {
if a & m != 0 {
p ^= b;
if a & (m - 1) == 0 {
break;
}
}
m >>= 1;
b = if b & 1 != 0 { (b >> 1) ^ POLY } else { b >> 1 };
if m == 0 {
break;
}
}
p
}
const fn x_pow_8n(bytes: usize) -> u32 {
let mut x2n = [0u32; 64];
let mut p: u32 = 1 << 30;
x2n[0] = p;
let mut k = 1;
while k < 64 {
p = mult_mod_p(p, p);
x2n[k] = p;
k += 1;
}
let mut result: u32 = 1 << 31; let mut n = bytes;
let mut idx = 3;
while n != 0 {
if n & 1 != 0 {
result = mult_mod_p(x2n[idx], result);
}
n >>= 1;
idx += 1;
}
result
}
const fn shift_table(bytes: usize) -> [[u32; 256]; 4] {
let op = x_pow_8n(bytes);
let mut t = [[0u32; 256]; 4];
let mut n = 0;
while n < 256 {
let v = n as u32;
t[0][n] = mult_mod_p(op, v);
t[1][n] = mult_mod_p(op, v << 8);
t[2][n] = mult_mod_p(op, v << 16);
t[3][n] = mult_mod_p(op, v << 24);
n += 1;
}
t
}
#[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
static SHIFT_LONG: [[u32; 256]; 4] = shift_table(LONG);
#[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
static SHIFT_SHORT: [[u32; 256]; 4] = shift_table(SHORT);
#[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
#[inline(always)]
fn shift(table: &[[u32; 256]; 4], reg: u32) -> u32 {
table[0][(reg & 0xFF) as usize]
^ table[1][((reg >> 8) & 0xFF) as usize]
^ table[2][((reg >> 16) & 0xFF) as usize]
^ table[3][(reg >> 24) as usize]
}
#[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
#[inline(always)]
fn le_u64(bytes: &[u8]) -> u64 {
let mut word = [0u8; 8];
word.copy_from_slice(&bytes[..8]);
u64::from_le_bytes(word)
}
macro_rules! interleaved_update {
($feature:literal, $crc64:path, $crc8:path) => {
#[target_feature(enable = $feature)]
#[allow(unused_unsafe)]
pub(super) unsafe fn update(mut reg: u32, mut data: &[u8]) -> u32 {
while data.len() >= 3 * super::LONG {
let (mut r1, mut r2) = (0u32, 0u32);
let (a, rest) = data.split_at(super::LONG);
let (b, rest) = rest.split_at(super::LONG);
let (c, rest) = rest.split_at(super::LONG);
for i in (0..super::LONG).step_by(8) {
unsafe {
reg = $crc64(reg, super::le_u64(&a[i..]));
r1 = $crc64(r1, super::le_u64(&b[i..]));
r2 = $crc64(r2, super::le_u64(&c[i..]));
}
}
reg = super::shift(&super::SHIFT_LONG, reg) ^ r1;
reg = super::shift(&super::SHIFT_LONG, reg) ^ r2;
data = rest;
}
while data.len() >= 3 * super::SHORT {
let (mut r1, mut r2) = (0u32, 0u32);
let (a, rest) = data.split_at(super::SHORT);
let (b, rest) = rest.split_at(super::SHORT);
let (c, rest) = rest.split_at(super::SHORT);
for i in (0..super::SHORT).step_by(8) {
unsafe {
reg = $crc64(reg, super::le_u64(&a[i..]));
r1 = $crc64(r1, super::le_u64(&b[i..]));
r2 = $crc64(r2, super::le_u64(&c[i..]));
}
}
reg = super::shift(&super::SHIFT_SHORT, reg) ^ r1;
reg = super::shift(&super::SHIFT_SHORT, reg) ^ r2;
data = rest;
}
let mut words = data.chunks_exact(8);
for w in &mut words {
reg = unsafe { $crc64(reg, super::le_u64(w)) };
}
for &byte in words.remainder() {
reg = unsafe { $crc8(reg, byte) };
}
reg
}
};
}
#[cfg(target_arch = "x86_64")]
mod x86 {
#[inline]
#[target_feature(enable = "sse4.2")]
#[allow(unused_unsafe)]
unsafe fn crc64(reg: u32, word: u64) -> u32 {
unsafe { std::arch::x86_64::_mm_crc32_u64(u64::from(reg), word) as u32 }
}
#[inline]
#[target_feature(enable = "sse4.2")]
#[allow(unused_unsafe)]
unsafe fn crc8(reg: u32, byte: u8) -> u32 {
unsafe { std::arch::x86_64::_mm_crc32_u8(reg, byte) }
}
interleaved_update!("sse4.2", crc64, crc8);
}
#[cfg(target_arch = "aarch64")]
mod arm {
#[inline]
#[target_feature(enable = "crc")]
#[allow(unused_unsafe)]
unsafe fn crc64(reg: u32, word: u64) -> u32 {
unsafe { std::arch::aarch64::__crc32cd(reg, word) }
}
#[inline]
#[target_feature(enable = "crc")]
#[allow(unused_unsafe)]
unsafe fn crc8(reg: u32, byte: u8) -> u32 {
unsafe { std::arch::aarch64::__crc32cb(reg, byte) }
}
interleaved_update!("crc", crc64, crc8);
}
pub(crate) mod portable {
use super::POLY;
static TABLES: [[u32; 256]; 8] = build_tables();
const fn build_tables() -> [[u32; 256]; 8] {
let mut t = [[0u32; 256]; 8];
let mut n = 0;
while n < 256 {
let mut c = n as u32;
let mut k = 0;
while k < 8 {
c = if c & 1 != 0 { (c >> 1) ^ POLY } else { c >> 1 };
k += 1;
}
t[0][n] = c;
n += 1;
}
let mut n = 0;
while n < 256 {
let mut k = 1;
while k < 8 {
let prev = t[k - 1][n];
t[k][n] = (prev >> 8) ^ t[0][(prev & 0xFF) as usize];
k += 1;
}
n += 1;
}
t
}
pub(crate) fn update(mut reg: u32, data: &[u8]) -> u32 {
let mut chunks = data.chunks_exact(8);
for c in &mut chunks {
let lo = reg ^ u32::from_le_bytes([c[0], c[1], c[2], c[3]]);
reg = TABLES[7][(lo & 0xFF) as usize]
^ TABLES[6][((lo >> 8) & 0xFF) as usize]
^ TABLES[5][((lo >> 16) & 0xFF) as usize]
^ TABLES[4][(lo >> 24) as usize]
^ TABLES[3][c[4] as usize]
^ TABLES[2][c[5] as usize]
^ TABLES[1][c[6] as usize]
^ TABLES[0][c[7] as usize];
}
for &b in chunks.remainder() {
reg = (reg >> 8) ^ TABLES[0][((reg ^ u32::from(b)) & 0xFF) as usize];
}
reg
}
}
#[cfg(test)]
mod tests {
use super::*;
fn reference(data: &[u8]) -> u32 {
!portable::update(!0, data)
}
fn bitwise(data: &[u8]) -> u32 {
let mut reg = !0u32;
for &b in data {
reg ^= u32::from(b);
for _ in 0..8 {
reg = if reg & 1 != 0 {
(reg >> 1) ^ POLY
} else {
reg >> 1
};
}
}
!reg
}
#[test]
fn test_crc32c_check_value_matches_standard() {
assert_eq!(crc32c(b"123456789"), 0xE306_9283);
}
#[test]
fn test_crc32c_rfc3720_vectors_match() {
assert_eq!(crc32c(&[0u8; 32]), 0x8A91_36AA);
assert_eq!(crc32c(&[0xFFu8; 32]), 0x62A8_AB43);
let inc: Vec<u8> = (0u8..32).collect();
assert_eq!(crc32c(&inc), 0x46DD_794E);
let dec: Vec<u8> = (0u8..32).rev().collect();
assert_eq!(crc32c(&dec), 0x113F_DB5C);
}
#[test]
fn test_crc32c_empty_is_zero() {
assert_eq!(crc32c(&[]), 0);
}
#[test]
fn test_crc32c_every_length_and_offset_matches_bitwise() {
let mut seed = 0x9E37_79B9_7F4A_7C15u64;
let buf: Vec<u8> = (0..(3 * LONG + 3 * SHORT + 64))
.map(|_| {
seed ^= seed << 13;
seed ^= seed >> 7;
seed ^= seed << 17;
seed as u8
})
.collect();
let lens = [
0,
1,
7,
8,
9,
63,
64,
255,
3 * SHORT - 1,
3 * SHORT,
3 * SHORT + 1,
3 * LONG - 1,
3 * LONG,
3 * LONG + 1,
3 * LONG + 3 * SHORT + 9,
];
for off in 0..9 {
for &len in &lens {
if off + len > buf.len() {
continue;
}
let s = &buf[off..off + len];
let want = bitwise(s);
assert_eq!(crc32c(s), want, "dispatch off={off} len={len}");
assert_eq!(reference(s), want, "portable off={off} len={len}");
}
}
}
#[test]
fn test_crc32c_append_equals_whole_for_every_split() {
let data: Vec<u8> = (0..1000u32).map(|i| (i * 31 + 7) as u8).collect();
let whole = crc32c(&data);
for split in [0, 1, 7, 8, 100, 768, 999, 1000] {
let (a, b) = data.split_at(split);
assert_eq!(crc32c_append(crc32c(a), b), whole, "split {split}");
}
}
#[test]
fn test_shift_table_equals_appending_zero_bytes() {
for reg in [0u32, 1, 0xDEAD_BEEF, 0xFFFF_FFFF, 0x8000_0001] {
let via_zeros = portable::update(reg, &[0u8; SHORT]);
#[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
assert_eq!(shift(&SHIFT_SHORT, reg), via_zeros);
let _ = via_zeros;
}
}
}