Lib.rs

› 算法
#checksum #rolling #crc #crc32 #lookup-tables #crc64

rolling-dual-crc

带有32位CRC32C和64位CRC64/XZ的滚动CRC

由Markus Laire所有。

1个不稳定版本

0.1.0 2021年12月10日

1783 in 算法

MIT许可证

57KB
811 行

rolling-dual-crc

一个用于计算32位CRC-32C和64位CRC-64/XZ校验和的库，具有

  • RollingDualCrc，用于在滚动窗口中计算校验和。
  • DualCrc，用于一次性或迭代计算校验和。
    • Zeros，用于高效处理长的0u8序列。
  • 使用查找表进行软件实现。
  • 可选使用crc32c和crc64fast包进行某些操作的硬件加速。
  • 默认没有unsafe。
  • 默认没有依赖。

支持的CRC算法

用法

在滚动窗口中计算校验和

RollingDualCrc::new 设置滚动窗口的大小及其初始内容。之后，每个 roll 将给定的字节追加到窗口，并移除窗口的第一个字节，使窗口向前滚动一个字节，然后重新计算新窗口的校验和。

roll 是一个快速常数时间 Θ(1) 操作，它不依赖于窗口的大小。

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);

一次性计算校验和

use rolling_dual_crc::DualCrc;

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

迭代计算校验和

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);

有关处理长 0u8 序列的示例，请参阅 Zeros。

功能标志

功能标志启用了某些校验和计算的硬件加速。虽然此 crate 本身不使用任何 unsafe 代码，但这些依赖项确实使用了 unsafe，因为这是硬件加速所必需的。

  • crc32c
  • crc64fast
  • fast
    • 使用这两个 crate。

支持硬件加速的方法/函数

方法 / 函数 crc32c crc64fast
DualCrc::checksum32 X -
DualCrc::checksum64 - X
DualCrc::checksum X X
DualCrc::update X -
RollingDualCrc::new X X

基准测试

  • 这些基准测试来自 cargo bench main 和 cargo bench main --features fast，在 3.4 GHz i5-3570K (Ivy Bridge，第三代) 上进行。
  • 有关处理长 0u8 序列的高级基准测试，请参阅 Zeros。

在滚动窗口中计算校验和

方法 / 函数 窗口大小 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

一次性 / 迭代计算校验和

方法 / 函数 数据大小 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

查找表大小

默认实现（即没有任何 功能标志）一次处理 1 或 8 字节，使用查找表。

方法 / 函数 字节/迭代 总表大小 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 不适用 0.75 kiB - - - X
  • C32：全局8 * 1 kiB表，用于计算CRC-32C
  • C64：全局8 * 2 kiB表，用于计算CRC-64/XZ
  • Roll：局部1 + 2 kiB表，用于滚动计算CRC-32C和CRC-64/XZ
  • Zeros：全局0.25 + 0.50 kiB表，用于创建Zeros

*) 创建本地表

安全性

本crate自身不使用任何unsafe代码。这是通过#![forbid(unsafe_code)]强制执行的。

如果您使用功能标志启用硬件加速，那么这些依赖项将使用unsafe代码。

致谢

本crate基于

  • 公有领域rolling-crc，由Igor Pavlov、Bulat Ziganshin和Bart Massey创建
  • 关于高效向CRC添加0s的Stack Overflow答案，作者为rcgldr
  • 在Fast CRC32中关于按8分割的示例，作者为Stephan Brumme

依赖项

~0–355KB