快速幺半群 CRC32 哈希计算

在并行和增量CRC 中描述的单调半群哈希在某些场景中很有用。一个 幺半群 哈希需要定义一个二元操作，可以将两个片段的哈希值结合起来，并且结合的结果，与连接这两个片段后再哈希是等价的。此外，还需要有一个单位元，当与任何哈希值结合时，会返回相同的哈希值。

然而，原始帖子中描述的朴素算法并没有达到现代硬件的极限。

为了更清楚地说明这一点，我们从快速幺半群 CRC32 计算的核心抽象开始说起。

type t
val fold_bytes: [u8] → t
val combine: t → t → t
val identity: t

我们使用 fold_bytes: [u8] → t 而不是 from_byte: u8 → t 。虽然后一种形式上更为通用，但许多架构支持硬件 CRC32 计算，这使得 fold_bytes 更有效率。

关于抽象类型 t，一个合理的表示方法需要包括两个多项式，每个多项式都按位存储到一个 32 位整数中。

两个多项式分别为标准的 CRC32 值和多项式 \( x^n \bmod p \) , 后者用于编码长度 \( n \)。

type r32 = u32 (* r32 表示一个 32 位的位反射多项式 *)
type t = {
  crc: r32
  len: r32
}

为该类型定义相应的 fold_bytes 操作非常直接。

let fold_bytes data  =
  let crc = crc32 data in
  let len = xnmodp @@ length data in
  { crc, len }

这里，crc32 和 xnmodp 都是用于常规 CRC32 计算的基本原语。

可以在 Fast CRC32 找到这两个原语的最出色实现。

根据原始帖子，结合操作定义为：

let combine m n =
  let crc = addp32 (mulp32 m.crc n.len) n.crc in
  let len = mulp32 m.len n.len in
  { crc, len }

这次我们使用了两个基本操作：addp32 （32 位多项式相加）和 mulp32（32 位多项式相乘并模 P）。

对于多项式的加法，只是简单的 xor。然而，多项式乘法更为复杂。虽然有相应的硬件指令（x86-64 的 clmul 和 AArch64 的 pmull），在得到加宽后的乘积后，结果必须对 CRC32 多项式 P 取模。这一运算本身未被硬件加速。

作为背景， 2021 年的 CPU 上的伽罗瓦域运算指令建议使用 crc32 指令进行取模。

然而，也可以选择了另外一种方法，明确地使用如下等式对结果进行模运算。

\[S \bmod P = (((S * (T / P)) \bmod T) * P) / T\]

(这个方法仍然来自 @cosrix)

按照我在 Questions on multiplication over GF(2^32) when implementing monoid CRC32 中描述的步骤，有如下代码（在 aarch64 架构上）：

uint64x2_t clmul_lo(uint64x2_t a, uint64x2_t b) {
  uint64x2_t r;
  __asm("pmull %0.1q, %1.1d, %2.1d\n" : "=w"(r) : "w"(a), "w"(b));
  return r;
}

uint64x2_t clmul_hi_e(uint64x2_t a, uint64x2_t b, uint64x2_t c) {
  uint64x2_t r;
  __asm("pmull2 %0.1q, %2.2d, %3.2d\neor %0.16b, %0.16b, %1.16b\n"
        : "=w"(r), "+w"(c)
        : "w"(a), "w"(b));
  return r;
}

uint32_t clmulr32(uint32_t a, uint32_t b) {
  uint64x2_t aa = vdupq_n_u64(a), bb = vdupq_n_u64(b);
  uint64x2_t j = vshlq_u64(clmul_lo(aa, bb), vdupq_n_s64(1));
  uint64x2_t k;
  {
    static const uint64_t __attribute__((align(16)))
                k_[] = {0x90d3d871bd4e27e2ull};
    k = vld1q_dup_u64(k_);
  }
  uint64x2_t l = clmul_lo(j, k);
  {
    static const uint64_t __attribute__((align(16)))
        k_[] = {0xfffffffe00000000ull, (uint64_t)-1ll};
    k = vld1q_u64(k_);
  }
  uint64x2_t n = vandq_u64(l, k);
  {
    static const uint64_t __attribute__((align(16)))
        k_[] = {0x82f63b7880000000ull};
    k = vld1q_dup_u64(k_);
  }
  uint64x2_t hi = clmul_lo(n, k);
  uint64x2_t shl = vextq_u64(hi, vdupq_n_u64(0), 1);
  uint64x2_t r = clmul_hi_e(n, k, shl);
  return (uint32_t)vgetq_lane_u64(r, 0);
}

基准数据显示这对我应用程序来说足够高效。现在，让我们总结一下快速幺半群 CRC32 哈希的最后一部分，单位元的定义。

let identity = {
  crc = 0,
  len = 0x80000000
}