SIMD 秒算 CRC：64 字节并行，CPU 周期省 90%

houseme
14 Nov, 2025

Photos provided by Unsplash OR Pexels

SIMD 加速 CRC 计算的完整原理

—— 深入解读 crc-fast v1.8.0 是如何做到 100GiB/s+ 的

一、传统 CRC 计算为什么慢？

经典位级/字节级 CRC（Sarwate 算法）每处理 1 字节需要：

8 次移位 + 8 次条件异或（反射时更复杂）
大量分支和内存访问 → 每字节 > 30 个时钟周期

即使是“表驱动”字节算法（1 次查表 + 1 次异或），在现代 CPU 上也只能达到 ~8–15 GiB/s，因为：

查表有缓存延迟
每 1 字节只能启动 1 次运算，流水线利用率低

二、SIMD 加速 CRC 的核心思想（Intel 2010 白皮书）

论文标题：
《Fast CRC Computation for Generic Polynomials Using PCLMULQDQ Instruction》
核心突破：把“多项式模运算”变成“矩阵乘法 + 模运算”，而矩阵乘法可以用 Carry-less Multiplication（无进位乘法） 完美加速！

关键数学等价变换

设当前 CRC 寄存器为 R，多项式为 P，待处理数据块为 M（长度固定，如 64 字节）

传统：
R’ = (R << 8×n ⊕ M) mod P

SIMD 加速公式（折叠 Fold）：

R' = R × X^(8×n)  ⊕  M_low × X^(8×m)  ⊕  M_high   (mod P)

其中所有 × 都是 GF(2) 上的无进位乘法 → 刚好对应 CPU 的 PCLMULQDQ 指令！

三、crc-fast 实际采用的 8-at-a-time 折叠策略（最快实现）

crc-fast 不是论文里的 4-at-a-time，而是更激进的 8 倍折叠（一次处理 64 字节）：

输入数据分成 8 个 8 字节块： D0 D1 D2 D3 D4 D5 D6 D7
当前寄存器：R

最终结果 =
    Fold8(R  ⊕ D7) ⊕
    Fold7(D6)      ⊕
    Fold6(D5)      ⊕
    Fold5(D4)      ⊕
    Fold4(D3)      ⊕
    Fold3(D2)      ⊕
    Fold2(D1)      ⊕
    Fold1(D0)

每一步 FoldN 只需要 2–3 条 PCLMULQDQ + 几条 XOR！

四、各平台具体指令对照表（crc-fast 实际使用）

平台	关键指令	说明	crc-fast 实现位置
x86_64	PCLMULQDQ	64-bit 无进位乘法	src/arch/x86_64/pclmulqdq.rs
x86_64 (AVX512)	VPCLMULQDQ	512-bit 向量无进位乘法，一次折叠更多	src/arch/x86_64/avx512.rs
aarch64	PMULL / PMULL2 (ARMv8 Crypto)	64-bit 多项式乘法	src/arch/aarch64/pmull.rs
x86 (32-bit)	SSE + PCLMULQDQ	降级使用 128-bit 向量	src/arch/x86/sse.rs

五、完整 8× 折叠算法伪代码（精华）

// 伪代码，实际在汇编/intrinsic 中实现
fn fold_8x(crc: u64, block64: &[u8; 64]) -> u64 {
    let mut x = _mm512_loadu_si512(block64);        // 加载 64 字节
    let mut r = crc.to_le_bytes();                  // 当前寄存器

    // 预计算常数：X^(512), X^(1024), X^(1536)...（编译期生成）
    let k1 = X_512;   let k2 = X_1024;  let k3 = X_1536;  ...

    // 8 次无进位乘 + Barrett Reduction（模 P(x)）
    r = clmul_fold(r, x.lo(), k1);
    r = clmul_fold(r, x.hi(), k2);
    // ... 继续 6 次

    barrett_reduction(r, poly)   // 最后一次模多项式（64→32 位）
}

Barrett Reduction：把 128-bit 中间结果快速折回到 32/64 bit，比传统移位快 10 倍。

六、crc-fast 的分层加速策略（自动选择最快路径）

输入数据长度 > 16KB
     ↓
CPU 支持 AVX-512 + VPCLMULQDQ → 512-bit 8× 折叠（最快，>100GiB/s）
     ↓ 否
CPU 支持 AVX2 + PCLMULQDQ    → 256-bit 4× 折叠（~60GiB/s）
     ↓ 否
CPU 支持 SSE4.1 + PCLMULQDQ   → 128-bit 2× 折叠
     ↓ 否
ARM64 PMULL                  → 128-bit NEON 折叠
     ↓ 否
回退到 64-bit 纯软件 3-way 展开（仍然比传统表驱动快 5–10 倍）

运行 crc-fast 自带的 arch-check 二进制即可看到你的 CPU 实际使用的路径：

$ cargo run --bin arch-check --release
Detected best implementation: x86_64_avx512_vpclmulqdq
Theoretical max throughput: 128 GiB/s (estimated)

七、实测性能对比（2025 年主流 CPU）

CPU	实现方式	CRC-32 吞吐量	CRC-64 吞吐量
Intel i9-13900K	AVX-512 VPCLMULQDQ	115–130 GiB/s	58–65 GiB/s
AMD Ryzen 9 7950X	AVX-512 VPCLMULQDQ	120+ GiB/s	60+ GiB/s
Apple M2 Max	ARMv8 PMULL (NEON)	45–55 GiB/s	35–45 GiB/s
Intel Xeon (无 AVX512)	AVX2 PCLMULQDQ	45–60 GiB/s	28–35 GiB/s
传统 crc32fast	硬件 CRC32 指令（单核）	20–30 GiB/s	不支持