rolling-dual-crc

A library for computing 32-bit CRC-32C and 64-bit CRC-64/XZ checksums, featuring:

• RollingDualCrc for computing checksums in a rolling window that moves through the input data.
• DualCrc for computing checksums in one go or iteratively.
  • Zeros for efficient handling of long 0u8 sequences.
• Software implementation using lookup tables.
• Optional hardware acceleration for some operations using crc32c and crc64fast crates.
• No unsafe by default.
• No dependencies by default.

Supported CRC algorithms

• 32-bit CRC-32C (Castagnoli)
  • known as CRC_32_ISCSI in crc crate and CRC-32/ISCSI in Catalogue of parametrised CRC algorithms
• 64-bit CRC-64/XZ
  • known as CRC_64_XZ in crc crate and CRC-64/XZ in Catalogue of parametrised CRC algorithms
  • often misidentified as CRC-64/ECMA-182

Usage

Compute checksums in a rolling window

RollingDualCrc::new sets the size of the rolling window and its initial contents. After that each roll appends the given byte to the window and removes first byte of the window, rolling the window forward one byte and then recomputes checksums for the new window.

roll is a fast constant time Θ(1) operation which doesn't depend on the size of the window.

use rolling_dual_crc::RollingDualCrc;

let mut crc = RollingDualCrc::new("abc");

// checksums of "abc"
assert_eq!(crc.get32(), 0x364B3FB7);
assert_eq!(crc.get64(), 0x2CD8094A1A277627);

crc.roll(b'd');
// checksums of "bcd"
assert_eq!(crc.get32(), 0x1B0D0358);
assert_eq!(crc.get64(), 0x0557EA6AA1219070);

crc.roll(b'e');
// checksums of "cde"
assert_eq!(crc.get32(), 0x364ADB60);
assert_eq!(crc.get64(), 0xB534844A0AD06B72);

Compute checksums in one go

use rolling_dual_crc::DualCrc;

assert_eq!(DualCrc::checksum32("Hello, world!"), 0xC8A106E5);
assert_eq!(DualCrc::checksum64("Hello, world!"), 0x8E59E143665877C4);

Compute checksums iteratively

use rolling_dual_crc::DualCrc;

let mut crc = DualCrc::new();
crc.update("Hello");
crc.update(", world!");
assert_eq!(crc.get32(), 0xC8A106E5);
assert_eq!(crc.get64(), 0x8E59E143665877C4);

See Zeros for an example of handling long 0u8 sequences.

Feature flags

Feature flags enable hardware acceleration for some checksum calculations. While this crate itself doesn't use any unsafe code, these dependencies do use unsafe since that is necessary for hardware acceleration.

• crc32c
  • Use crc32c crate for some CRC-32C computations.
• crc64fast
  • Use crc64fast crate for some CRC-64/XZ computations.
• fast
  • Use both of those crates.

Methods/functions which support hardware acceleration:

Benchmarks

• These benchmarks are from cargo bench main and cargo bench main --features fast with 3.4 GHz i5-3570K (Ivy Bridge, 3rd gen.).
• See Zeros for advanced benchmarks of handling long 0u8 sequences.

Compute checksums in a rolling window

Compute checksums in one go / iteratively

Lookup table sizes

Default implementation (i.e. without any feature flags) processes 1 or 8 bytes at a time using lookup tables.

• C32: global 8 * 1 kiB tables for computing CRC-32C
• C64: global 8 * 2 kiB tables for computing CRC-64/XZ
• Roll: local 1 + 2 kiB tables for rolling CRC-32C and CRC-64/XZ
• Zeros: global 0.25 + 0.50 kiB tables for creating Zeros

*) creates the local tables

Safety

This crate itself doesn't use any unsafe code. This is enforced by #![forbid(unsafe_code)].

If you enable hardware acceleration with feature flags, then those dependencies do use unsafe code.

Credits

This crate is based on

• public domain rolling-crc by Igor Pavlov, Bulat Ziganshin and Bart Massey
• stackoverflow answer by rcgldr about efficiently appending 0s to CRC
• slicing-by-8 examples at Fast CRC32 by Stephan Brumme