CRC32C checksums

Deep dive

How it works

In: a byte buffer and the previous CRC (0 for a fresh one) · Out: a 32-bit checksum · State: none between calls except the 32-bit CRC you pass back in (software variant: a 1 KiB table) · Cost: O(n); order of 8-11 GB/s per stream with hardware instructions.

1. State c = !init (init is 0 for a fresh CRC, so c = 0xFFFFFFFF).
2. For each byte: c = T[(c ^ b) & 0xFF] ^ (c >> 8), where T[i] is i shifted through 8 rounds of c = (c & 1) ? (c >> 1) ^ 0x82F63B78 : c >> 1. This is the reflected, LSB-first form.
3. Result !c. To continue a CRC over more data, start from !previous_result.
4. Hardware: crc32 r64, r/m64 (x86) and crc32cx (AArch64) apply 8 bytes to the state in one instruction. Both have a latency of order of 3 cycles at 1 per cycle throughput, so a single dependent chain runs at about 8 B / 3 cycles.
5. Faster: split the buffer into 3 independent streams to fill the pipeline, then merge the CRCs. Merging multiplies by x^(8·len) mod P with carry-less multiply (PCLMULQDQ / PMULL) or precomputed shift tables. This reaches close to 8 B/cycle.

Code

Table fallback built at compile time, SSE4.2 and ARMv8 hardware paths with runtime detection, a streaming API and the LevelDB mask. Tests cover the standard check value and the RFC 3720 all-zeros vector.

// CRC-32C (Castagnoli): reflected polynomial 0x82F63B78, init and final XOR 0xFFFFFFFF.
#[cfg(target_arch = "aarch64")]
use std::arch::aarch64::{__crc32cb, __crc32cd};
#[cfg(target_arch = "x86_64")]
use std::arch::x86_64::{_mm_crc32_u64, _mm_crc32_u8};

const POLY: u32 = 0x82F6_3B78; // bit-reversed 0x1EDC6F41

/// 256-entry table for byte-at-a-time software CRC, built at compile time.
const TABLE: [u32; 256] = {
    let mut t = [0u32; 256];
    let mut i = 0;
    while i < 256 {
        let mut c = i as u32;
        let mut k = 0;
        while k < 8 { c = if c & 1 != 0 { (c >> 1) ^ POLY } else { c >> 1 }; k += 1; }
        t[i] = c;
        i += 1;
    }
    t
};

/// Portable fallback, order of 0.5 GB/s. `crc` is the raw (un-inverted) running state.
fn update_sw(mut crc: u32, data: &[u8]) -> u32 {
    for &b in data { crc = TABLE[((crc ^ b as u32) & 0xFF) as usize] ^ (crc >> 8); }
    crc
}

#[cfg(target_arch = "x86_64")]
#[target_feature(enable = "sse4.2")]
unsafe fn update_hw(crc: u32, data: &[u8]) -> u32 {
    let mut c = crc as u64;
    let mut words = data.chunks_exact(8);
    for w in &mut words {
        c = _mm_crc32_u64(c, u64::from_le_bytes(w.try_into().unwrap())); // 8 bytes, 3-cycle latency
    }
    let mut c = c as u32;
    for &b in words.remainder() { c = _mm_crc32_u8(c, b); }
    c
}

#[cfg(target_arch = "aarch64")]
#[target_feature(enable = "crc")]
unsafe fn update_hw(crc: u32, data: &[u8]) -> u32 {
    let mut c = crc;
    let mut words = data.chunks_exact(8);
    for w in &mut words { c = __crc32cd(c, u64::from_le_bytes(w.try_into().unwrap())); }
    for &b in words.remainder() { c = __crc32cb(c, b); }
    c
}

fn has_hw() -> bool {
    #[cfg(target_arch = "x86_64")]
    return is_x86_feature_detected!("sse4.2");
    #[cfg(target_arch = "aarch64")]
    return std::arch::is_aarch64_feature_detected!("crc");
    #[allow(unreachable_code)]
    false
}

/// Streaming API: crc32c_append(crc32c_append(0, a), b) == crc32c(a ++ b).
pub fn crc32c_append(crc: u32, data: &[u8]) -> u32 {
    let state = !crc; // undo the previous final XOR
    #[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
    if has_hw() { return !unsafe { update_hw(state, data) }; } // safe: feature checked
    !update_sw(state, data)
}

pub fn crc32c(data: &[u8]) -> u32 { crc32c_append(0, data) }

/// LevelDB/RocksDB/Snappy-framing mask: storing the CRC of data that itself contains
/// CRCs is weak, so stored values are rotated and offset.
pub fn mask(crc: u32) -> u32 { crc.rotate_right(15).wrapping_add(0xA282_EAD8) }
pub fn unmask(m: u32) -> u32 { m.wrapping_sub(0xA282_EAD8).rotate_left(15) }

fn main() {
    assert_eq!(crc32c(b"123456789"), 0xE306_9283); // standard check value
    assert_eq!(crc32c(b""), 0);
    assert_eq!(crc32c(&[0u8; 32]), 0x8A91_36AA);   // RFC 3720 B.4 test vector
    let data: Vec<u8> = (0..100_003u32).map(|i| (i * 31 + 7) as u8).collect();
    let sw = !update_sw(!0, &data);
    assert_eq!(crc32c(&data), sw);
    assert_eq!(crc32c_append(crc32c(&data[..777]), &data[777..]), sw);
    assert_eq!(unmask(mask(sw)), sw);
    let big = vec![0xA5u8; 64 << 20];
    let t = std::time::Instant::now();
    let h = std::hint::black_box(crc32c(&big));
    println!("ok, {:.1} GB/s", big.len() as f64 / t.elapsed().as_secs_f64() / 1e9);
    assert_eq!(h, !update_sw(!0, &big));
}

Complexity and constants

• Byte table (1 KiB): order of 0.5 GB/s, one table load per byte. Slicing-by-8 (8 KiB of tables): order of 2-3 GB/s.
• Hardware, one stream: order of 8-11 GB/s at 3.5-4.5 GHz. Three interleaved streams + combine: order of 20-30 GB/s per core.
• Undetected random corruption: probability 2⁻³² per block, for errors outside the guaranteed-detected classes. For many-MB blocks, or when 2⁻³² across billions of blocks is too much, use CRC-64 or a 128-bit hash.

Efficiency

• Cost: byte table order of 0.5 GB/s (one table load per byte); slicing-by-8 order of 2-3 GB/s; one hardware stream order of 8-11 GB/s at 3.5-4.5 GHz; three interleaved streams plus combine order of 20-30 GB/s per core. Tables cost 1 KiB (byte) or 8 KiB (slicing-by-8). One dependent chain is bound by the order-of-3-cycle instruction latency, the interleaved version by load and memory bandwidth.
• Levers:
  • hardware crc32 / crc32cx — order of 0.5 → 8-11 GB/s (figures above) — x86 with SSE4.2, ARMv8 with CRC
  • 3 independent streams, merged by carry-less multiply (PCLMULQDQ/PMULL) — order of 8-11 → 20-30 GB/s per core (figures above) — buffers of a few KiB and up
  • compute the CRC while the data is hot in cache — saves a second pass over memory — checksum next to a copy or compression
  • CRC-64 or a 128-bit hash — undetected-error chance beyond 2⁻³² per block — many-MB blocks or billions of blocks
• Naive → standard → state of the art:
• naive: byte-at-a-time table · order of 0.5 GB/s
• standard: slicing-by-8, or one hardware stream · order of 2-3 GB/s, order of 8-11 GB/s
• state of the art: three hardware streams with carry-less-multiply combine · order of 20-30 GB/s per core

Implementation notes

• Checksum the header fields too (length, type, sequence), not just the payload. Otherwise a corrupted length passes. See length-prefix framing.
• Store the CRC at a fixed position and compute over the record with that field excluded or zeroed. Be consistent about endianness (little-endian is the convention).
• Masking (LevelDB, RocksDB, Snappy framing): rotr(crc, 15) + 0xA282EAD8. The CRC of data that contains its own CRC is degenerate, so stored values are masked.
• Torn-write detection: one CRC per 4 KiB sector or per record catches partial writes after power loss (fsync and direct I/O).
• crc32c(a ‖ b) can be computed from crc32c(a), crc32c(b) and len(b) (zlib's crc32_combine technique). This lets you checksum parts in parallel.
• AArch64 offers both __crc32cd (Castagnoli) and __crc32d (IEEE). x86 has only Castagnoli in hardware. IEEE CRC-32 on x86 needs PCLMULQDQ folding.
• Rust: _mm_crc32_u64 needs sse4.2. __crc32cd needs the crc target feature, which all Apple M-series and most ARMv8 server cores have.

Pitfalls

• Mixing up CRC-32 (IEEE, 0xEDB88320 reflected) and CRC-32C (0x82F63B78). Both are "crc32" in library names.
• Forgetting the final XOR or the init value. Then crc("") isn't 0 and streaming breaks. Test against 0xE3069283.
• Skipping the check on read "for speed": the check costs order of 0.1 ms per MB, and reading corrupt data costs much more.
• Using a CRC as a hash-table hash: good bit mixing is not its goal, and low bits correlate on structured keys.

Variants and alternatives

In production

iSCSI (RFC 3720), SCTP (RFC 4960), NVMe/TCP data digests, ext4 metadata_csum, XFS v5 metadata, Btrfs (default checksum), Ceph BlueStore, LevelDB/RocksDB block checksums (masked), Kafka record batches (format v2), Google Cloud Storage object checksums.

Implementations

Sources

• Guy Castagnoli, Stefan Bräuer, Martin Herrmann, Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits, IEEE Transactions on Communications, 1993.
• Philip Koopman, 32-Bit Cyclic Redundancy Codes for Internet Applications, DSN, 2002. paper
• Vinodh Gopal et al., Fast CRC Computation for iSCSI Polynomial Using CRC32 Instruction, Intel white paper, 2011.
• J. Satran et al., Internet Small Computer Systems Interface (iSCSI), RFC 3720, 2004 (appendix B.4 test vectors). RFC