#checksum #crc #rolling #crc32 #crc64

rolling-dual-crc

Rolling CRC with 32-bit CRC32C and 64-bit CRC64/XZ

1 unstable release

0.1.0 Dec 10, 2021

#1854 in Algorithms

MIT license

57KB
811 lines

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

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
  • crc64fast
  • fast
    • Use both of those crates.

Methods/functions which support hardware acceleration:

Method / Function crc32c crc64fast
DualCrc::checksum32 X -
DualCrc::checksum64 - X
DualCrc::checksum X X
DualCrc::update X -
RollingDualCrc::new X X

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

Method / Function window size ns MiB/s ns fast MiB/s fast
RollingDualCrc::new 1 kiB 26 000 38 28 000 35
RollingDualCrc::new 32 kiB 58 000 540 40 000 790
RollingDualCrc::new 1024 kiB 1 100 000 920 430 000 2300
RollingDualCrc::roll 1 kiB 4 240 4 240
RollingDualCrc::roll 32 kiB 4 240 4 240
RollingDualCrc::roll 1024 kiB 4 240 4 240

Compute checksums in one go / iteratively

Method / Function data size ns MiB/s ns fast MiB/s fast
DualCrc::checksum32 1 kiB 400 2400 66 15000
DualCrc::checksum64 1 kiB 580 1700 310 3200
DualCrc::checksum 1 kiB 1000 980 370 2600
DualCrc::update 1 kiB 1000 980 660 1500

Lookup table sizes

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

Method / Function bytes/iter Total table size C32 C64 Roll Zeros
DualCrc::checksum32 8 8 kiB 8x - - -
DualCrc::checksum64 8 16 kiB - 8x - -
DualCrc::checksum 8 24 kiB 8x 8x - -
DualCrc::update 8 24 kiB 8x 8x - -
RollingDualCrc::new 8 27.75 kiB 8x 8x X* X
RollingDualCrc::roll 1 6 kiB 1x 1x X -
RollingDualCrc::roll_slice 1 6 kiB 1x 1x X -
Zeros::new N/A 0.75 kiB - - - X
  • 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

Dependencies

~0–350KB