CRC-32 的位运算与查表

假设一个 gzip 流本应恢复出 AB，但数据损坏让结果变成 AC。gzip 尾部带有发送者对原始未压缩字节计算的 CRC-32。接收者对恢复的字节计算同样的 32 位摘要，再比较两个数。摘要不同，就检测到了损坏；相同则不能排除所有可能的损坏。CRC-32 提供这项完整性检查，本身不压缩或恢复字节。

一次更新接收已有 CRC、可读字节区间及其长度，返回计入这段字节后的 CRC。新序列从零开始。如果第一次提供 A，第二次提供 B，就把第一次返回值直接传入第二次。如果两个缓冲区各自独立计算过校验和，则需要另一种操作和 B 的长度，才能连接两个摘要。

下面先让一个字节经过简单的位运算，再介绍解释它的多项式语言。接着就能看清：为什么 C 用表代替反复的位步骤，用交织的字计算减少长串逐字节依赖。每种优化都必须得到同一校验和。

反射寄存器

计算需要用少量状态概括已经处理过的所有字节。这个状态保存在一个 32 位工作值中，称为寄存器 r。每一步把它右移，移出最低位。如果移出的位为一，还要把常量 0xedb88320 XOR 到右移结果中。XOR 是按位异或：相同的位得到零，不同的位得到一，没有进位。式子里的 >> 1 表示右移一位，r & 1 只保留最低位，用来判断它是否为一。0x 是十六进制常量的前缀。把这样一步称为 T：

T(r) = (r >> 1) XOR 修正值
修正值 = 0xedb88320，当 r 的最低位为 1
修正值 = 0，当 r 的最低位为 0

消耗下一个字节时，把其值记作 b，先将它 XOR 到寄存器的低八位，再应用八次 T。字节的最低有效位先进入计算。这就是反射位约定：计算向低位推进。

公开的运行中校验和是内部寄存器的按位取反值：每个零变成一，每个一变成零。新公开校验和从 0 开始，因此工作寄存器从 ffffffff 开始。函数先对传入校验和取反，处理字节，再对结果取反。调用者将返回值直接传给下一次更新；再次自行取反会改变计算。

这个常量由 CRC 的多项式规则决定。可以把寄存器各位看成只能取零或一的系数，此时多项式加法就是 XOR。这种算术称为 GF(2)。CRC 多项式的次数为 32，最高项 x^32 在保存的常量中隐含不写。连接独立分块时会用到这种解释；理解单字节计算只需要上面的右移和 XOR 规则。

一个字节

对 ASCII A，b = 0x41。从公开校验和零开始，内部寄存器为 ffffffff。XOR 字节后得到 ffffffbe，再执行八个位步骤：

第一步移出的位为零，因此只右移。下一步先把 7fffffdf 右移为 3fffffef，再 XOR edb88320，得到 d2477ccf。对第八步的结果取反，得到公开 CRC d3d99e8b。

现在让第一个缓冲区在 A 后结束。返回的 d3d99e8b 就包含继续计算所需的全部状态。把它传给处理 B 的下一次更新，得到 AB 的 CRC 30694c07。从零独立处理 B 则得到 4ad0cf31，这个数本身没有 A 的贡献。独立递推与固定版本 C 函数在这些例子上相符。这核对了展示数值，不覆盖全部输入。

字节表

每个字节都执行八次右移和条件 XOR，有许多重复工作。低字节的贡献只有 256 种可能，可以预先算出，存入称为 table 的数组。下面，i 是其中一个字节值，T⁸ 表示执行八次位步骤，byte_step 表示消耗一个字节后的工作寄存器：

table[i] = T⁸(i)
byte_step(r,b) = (r >> 8) XOR table[(r XOR b) & 255]

寄存器的高 24 位向下移动，表则提供低字节对应的多项式贡献。之所以可以拆开算，是因为这些步骤保持 XOR：先把两数 XOR 再推进，等于分别推进后再 XOR。对 A，索引为 be，table[be] = 2cd99e8b。与 00ffffff XOR，仍然得到 2c266174。

在 C 中，buf 指向下一个输入字节，len 是剩余字节数，crc_table 是这张有 256 个条目的表，局部变量 crc 保存内部寄存器。计算过程中，它与公开校验和值不同。实际使用表的字节尾循环，来自固定版本 crc32.c 的 934–940 行：

    while (len) {
        len--;
        crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
    }

    /* Return the CRC, post-conditioned. */
    return crc ^ 0xffffffff;

len 是剩余字节数；循环条件确认还有字节，才减计数并读取。*buf++ 读出该字节，再前进指针；XOR 和 & 0xff 形成 0 到 255 范围内的表索引。crc >> 8 把旧寄存器的高位移下来，^ 再合入表中贡献。返回语句翻转低 32 位，恢复公开约定。之前的第 635 行已执行 crc = (~crc) & 0xffffffff，所以循环里的局部 crc 是工作寄存器，而不是公开值。

get_crc_table 暴露这张字节表。条目描述内部寄存器更新，不包含公开接口的取反。返回的存储是静态只读的；该指针不授权读取相邻交织表、写入条目或释放数组。

字与交织

查表去掉了内部八个位步骤，但每个新字节仍需要上一个寄存器值。为了让多项工作独立推进，所选默认分支把输入按每八字节分组，称为一个“字”，读取时把它看成 64 位整数。实现保留五个交错的运行中值，称为交织通道：每条通道有自己的寄存器，每隔五个字处理一次。从初始对齐字节之后的第一个字开始，给各字从零编号：第零通道处理位置 0、5、10……；第一通道处理 1、6、11……，以此类推。

这些是有间隔的子序列。相应表计入相邻通道字之间的多项式距离。第零通道接收预处理后的传入寄存器 (~crc) & 0xffffffff，其余通道从零开始。它们不是连续五个分块的普通校验和。最终块代码通过字递推，按原始字节顺序合并这些贡献。

这个分支不能仅凭还有一个字就安全进入。C 中，N 是通道数，W 是每个字的字节数。640–650 行的入口和对齐循环先要求 len >= N * W + W - 1，再逐字节处理，直到 ((z_size_t)buf & (W - 1)) == 0。对 N=5,W=8，阈值为 5×8 + 8−1 = 47 字节。这里的对齐要求输入地址是八的倍数，掩码 W - 1 用来检查地址的低三位。最多处理七个字节就能到达这样的地址，至少留下一个 40 字节块。

一块包含每条通道各一个字，因此占 N × W = 40 字节。C 计数器 blks 表示还剩多少完整块，其中包含最后一个留给合并的块。第 710 行的块循环使用 while (--blks)，只处理最后一块之前的所有块。独立代码处理最后一块及其合并。提前保留至少一块，才能避免第一次前减下溢。之后剩余不足 40 个字节，由展开的字节尾部和逐字节循环处理。

要在 C 中看见这些独立依赖，可以沿小端分支的第零通道读下去。words 是按八字节的字寻址的输入指针；crc0 是第零通道的运行中寄存器，word0 暂存它与下一个输入字的 XOR。crc_braid_table 为字内部的每个字节位置准备一行，k 选择其中的位置。下面选取第 712 行、728–732 行和 748–765 行中属于该通道的语句。省略了夹在中间的其他通道语句及其预处理条件，这不是完整循环：

                word0 = crc0 ^ words[0];

                words += N;

                crc0 = crc_braid_table[0][word0 & 0xff];

                for (k = 1; k < W; k++) {
                    crc0 ^= crc_braid_table[k][(word0 >> (k << 3)) & 0xff];
                }

words[0] 读取分给第零通道的下一个字；word0 把它与该通道原来的 crc0 混合。源码相邻各行对 words[1] 到 words[4]、crc1 到 crc4 做同样的事。五个字全部读出之后，words += N 才把公共指针推进到下一块。每条通道更新只依赖自己的旧值和输入字，因此不必等待另一条通道刚算出的 CRC。

具体看地址路径：把第一个对齐字节的偏移称为 q。在所选 N=5,W=8 下，第零通道先读取 q…q+7，第一通道读取 q+8…q+15，第四通道读取 q+32…q+39。words 前进五个字，就是 40 字节。若还有下一次普通迭代，第零通道接着读 q+40…q+47，第一通道读 q+48…q+55。同一通道相邻两次取字相隔 40 字节，并不是紧挨着的八字节段。

第一次查表处理 word0 的第零个字节位置。k 循环通过右移 8 到 56 位，提取位置 1 到 7，分别查表，再把贡献 XOR 到 crc0。在这个小端路径上，低字节对应所读字中最早的输入字节。表行 k 表示字内部的字节位置，不是通道编号；各通道使用相同各行。交织表已经计入同通道两次取字的间距，与普通单字节表不同。最后，772–780 行的末块合并通过 crc_word 依次合入第零到第四通道，在字节尾循环之前恢复成一个寄存器。

这样的组织暴露了相互独立的通道依赖，并分摊循环工作。字的端序和地址对齐仍是选择、解释实际读取的一部分。所选证明模型按目标端序组装相同字节；C 转换和 ABI 对应关系需要各自审查。

多项式算子

如果两个工作单元独立计算了 A、B，又丢弃了字节，该怎样连接？不能把第二个 CRC 当作 B 的数据，拿去更新第一个 CRC。需要先把 A 的贡献推进到 B 占据的字节位置之后，再用 XOR 合入两个贡献。

对于一般的先 X 后 Y，用 n 表示 Y 的长度。CRC(X)、CRC(Y) 表示各自从零开始独立计算的公开校验和，X ++ Y 表示连接。用 T⁸ⁿ 表示执行前面的位步骤 8n 次，即让一个 32 位值前进 n 个零字节，不带公开接口取反。于是：

CRC(X ++ Y) = T⁸ⁿ(CRC(X)) XOR CRC(Y)

在这个连接恒等式中，初始和最终取反的项相互抵消。不能通过对 n 个零字节调用公开更新函数来实现 T⁸ⁿ，因为那次调用会包含它自己的取反约定。

当 X=A、Y=B 时，T⁸(d3d99e8b) = 7ab98336。与 B 独立计算的 4ad0cf31 XOR，得到 30694c07，即 AB 的 CRC。

前进操作保持 XOR，可以用二进制矩阵表示，也可以用模 CRC 多项式的乘法表示。无论采用哪种表示，保存的是“把已有贡献向后推进指定长度”这一操作，不是第二段的数据或校验和。

所选源码使用多项式乘法。954–960 行的生成器调用 x2nmodp(len2, 3)：len2 是 Y 的字节长度，辅助函数要计算代表前进这么多字节的幂。第二个参数选择每个长度单位包含的位步骤数；3 选中每字节八个位步骤，因为 2^3 = 8。

184–194 行的辅助函数每次检查长度的一位。x2n_table 中的幂由反复平方得到；长度位为一时，辅助函数乘入对应的幂，然后右移长度，转到下一个幂。这样不必遍历 n 个字节，就能算出 x^(8n) 的算子。

例如第二段有 13 字节，13 = 8 + 4 + 1。实现选取推进 8、4、1 字节的三个预计算操作，把它们组合起来，效果等于推进 13 字节，也就是 104 个零输入位。它无需真的循环 104 次。这说明长度的二进制位为什么足以驱动计算；预计算表和乘法是否确实实现了这些操作，仍由证明建立。

在这种反射乘法表示中，乘法单位元是 0x80000000：与它相乘表示“尚未推进”。这里的乘法是前面介绍的多项式乘法，不是普通整数乘法。

校验和入口

crc32_z 使用 z_size_t 字节计数，在所选构建中为 64 位；crc32 使用 32 位计数。crc32_combine 和 crc32_combine64 接受独立校验和与 Y 的有符号长度。

许多第二分块长度相同时，可用 crc32_combine_gen 或 crc32_combine_gen64 一次生成算子，再通过 crc32_combine_op 复用。算子由生成函数产生是一项定义域要求，不是只要任意非零整数即可。

负长度生成零，并让组合调用返回零。真正的空 Y 的 CRC 为零，会保持 X 的校验和。若长度为零而参数是任意标量，实现则返回两者低 32 位的 XOR。NULL 更新查询即使长度非零也返回零。证明章节 区分这些精确 API 情况与校验和连接，并解释内存视图假设。