CRC64实现全解析：从逐位算法到查表法与硬件加速

在接触CRC64的实现时，很多人第一反应是“这不就是查个表、算个校验和嘛”。真上手之后才发现，同样叫CRC64，换一套参数、调一下输入输出反射，结果能差到十万八千里。这篇是CRC推导系列的第八篇，我把CRC64从逐位实现、查表法、切片法到硬件加速的实现路径完整过一遍，顺带把工程里最容易踩的坑一起列出来。适合正在读CRC源码、准备自己写校验库、或者排查CRC64结果对不上的开发者。

1. 从五个参数认识 CRC64 的“性格”

CRC64并不是一个唯一的算法，而是一个由五个参数共同决定的家族。你随便打开一份协议文档，里面写“使用CRC64校验”，如果不把那几个参数写全，基本等于没说。因为这五个参数但凡有一个不一样，同一份数据的校验值就是另一个数。

1.1 生成多项式：那个看起来不像多项式的整数

CRC的数学本质是GF(2)上的多项式除法，64位CRC就是让消息多项式除以一个64次生成多项式，余数就是校验值。

因为最高位一定是1，所以几乎所有规范在表示生成多项式的时候都把这个固定位省掉。这就是为什么你会看到0x42F0E1EBA9EA3693这种64位常数，它实际对应的是一个65位的多项式，最高位的那个x^64项被隐去了。

这个常数用MSB表示法写出来是0x42F0E1EBA9EA3693，在反射场景下要用它的位倒序版本：

0x42F0E1EBA9EA3693 -> 0xC96C5795D7870F42

很多人在写反射型CRC时直接拿原多项式往代码里塞，结果第一步就错了。反射型CRC的反馈多项式不是原多项式，而是原多项式逐位倒序后的那一长串。

1.2 初始值、输入反射、输出反射、结果异或

其余四个参数的作用可以这样理解：

init看着像一个初值，但在CRC的除法模型里，它等价于把消息前面先拼了一段固定数据。refin和refout经常成对出现，它们对应的是硬件移位寄存器的数据进出方向。xorout则是为了把全0和全1这种特殊状态也纳入校验范围。

举两个最常见的组合：

• 归档场景常用参数：poly=0x42F0E1EBA9EA3693，init=0，refin=false，refout=false，xorout=0
• 流式压缩场景常用参数：poly=0x42F0E1EBA9EA3693，init=0xFFFFFFFFFFFFFFFF，refin=true，refout=true，xorout=0xFFFFFFFFFFFFFFFF

两个变体生成多项式一样，但因为初值、反射和异或输出不同，对测试字符串"123456789"算出来的check值分别是0x6C40DF5F0B497347和0x995DC9D79A1FBD0A。不知道这一点，看到两个库算出来的CRC64不一样就以为某个库有bug，是新手最常犯的误会。

2. 最朴素的逐位实现：先把原理跑通

先写最慢但最容易验证的逐位版本。它不追求性能，唯一目的是确认你对参数和算法方向的理解是对的。这个版本也是后面所有优化版本的“参照物”。

2.1 非反射型：MSB-first逐位算法

非反射型CRC适合用MSB-first写法，也就是从字节的最高位开始一位一位处理。以归档场景那套参数为例：

#include <stdint.h> #include <stddef.h> #define POLY_MSB UINT64_C(0x42F0E1EBA9EA3693) uint64_t crc64_msb_raw(uint64_t crc, const uint8_t *data, size_t len) { for (size_t i = 0; i < len; i++) { crc ^= (uint64_t)data[i] << 56; for (int bit = 0; bit < 8; bit++) { if (crc & UINT64_C(0x8000000000000000)) { crc = (crc << 1) ^ POLY_MSB; } else { crc = crc << 1; } } } return crc; }

调用时先令crc = init，也就是全0；全部数据处理完后返回的原始状态再和xorout异或。归档参数的xorout恰好是0，所以可以省掉最后一步。

这里的crc ^= (uint64_t)data[i] << 56是关键：MSB-first把输入字节放到寄存器最高字节位置，从最高位开始做反馈。你可以想象成把新数据“顶”进寄存器顶部，然后一步一步往下挤。

2.2 反射型：LSB-first逐位算法

反射型CRC反过来，数据从LSB方向进入。先写一个返回原始状态的逐位函数，用反射多项式参与反馈：

#define POLY_LSB UINT64_C(0xC96C5795D7870F42) uint64_t crc64_lsb_raw(uint64_t crc, const uint8_t *data, size_t len) { for (size_t i = 0; i < len; i++) { crc ^= data[i]; for (int bit = 0; bit < 8; bit++) { if (crc & UINT64_C(1)) { crc = (crc >> 1) ^ POLY_LSB; } else { crc = crc >> 1; } } } return crc; }

反射型变体的完整计算流程是：

uint64_t crc64_reflected(const uint8_t *data, size_t len) { uint64_t crc = UINT64_C(0xFFFFFFFFFFFFFFFF); crc = crc64_lsb_raw(crc, data, len); return crc ^ UINT64_C(0xFFFFFFFFFFFFFFFF); }

注意我没把init和xorout合进crc64_lsb_raw，就是刻意保留“原始状态”和“最终输出”两个概念。很多实现为了省事，把init和xorout直接写死在函数里，结果在做流式分段计算时非常被动。

2.3 用check值验证理解没有跑偏

CRC领域的通用测试字符串是9字节的"123456789"。逐位版验证如下：

// 归档场景参数，MSB-first assert(crc64_msb_raw(0, (const uint8_t *)"123456789", 9) == UINT64_C(0x6C40DF5F0B497347)); // 流式压缩场景参数，LSB-first uint64_t raw = crc64_lsb_raw(UINT64_C(0xFFFFFFFFFFFFFFFF), (const uint8_t *)"123456789", 9); assert((raw ^ UINT64_C(0xFFFFFFFFFFFFFFFF)) == UINT64_C(0x995DC9D79A1FBD0A));

如果check值对不上，优先检查两个地方：一是init有没有在调用前给对，二是最后xorout是在输出时才做，不是每段都做。

3. 查表法与表的方向：从每字节8次迭代到1次查表

逐位版本能跑通逻辑，但性能完全不能用于生产。每处理一个字节要做8次移位和判断，再加上循环和内存访问，吞吐量很难看。查表法的思路是：把某个8位组合对CRC寄存器的全部影响提前算出来，运行时用一次查表替代8次迭代。

3.1 非反射型查表

MSB-first查表的核心是构造一张256项的64位表。表里第i项可以理解为“把字节i推进寄存器后，寄存器会变成什么状态”。

生成表和更新逻辑：

static uint64_t table_msb[256]; void crc64_init_table_msb(uint64_t poly) { for (int i = 0; i < 256; i++) { uint64_t crc = (uint64_t)i << 56; for (int bit = 0; bit < 8; bit++) { crc = (crc & UINT64_C(0x8000000000000000)) ? (crc << 1) ^ poly : (crc << 1); } table_msb[i] = crc; } } uint64_t crc64_msb_update(uint64_t crc, const uint8_t *data, size_t len) { for (size_t i = 0; i < len; i++) { crc = (crc << 8) ^ table_msb[(crc >> 56) ^ data[i]]; } return crc; }

更新式里的(crc >> 56) ^ data[i]是取CRC寄存器的最高字节和新数据字节异或，作为表索引。然后整个寄存器左移8位，再异或查表结果。

3.2 反射型查表

反射型查表的表生成方向完全不同。它把i作为初始状态的最低字节做逐位迭代：

static uint64_t table_lsb[256]; void crc64_init_table_lsb(uint64_t poly) { for (int i = 0; i < 256; i++) { uint64_t crc = (uint64_t)i; for (int bit = 0; bit < 8; bit++) { crc = (crc & UINT64_C(1)) ? (crc >> 1) ^ poly : (crc >> 1); } table_lsb[i] = crc; } } uint64_t crc64_lsb_update(uint64_t crc, const uint8_t *data, size_t len) { for (size_t i = 0; i < len; i++) { uint8_t idx = (uint8_t)(crc ^ data[i]); crc = table_lsb[idx] ^ (crc >> 8); } return crc; }

这里有一个非常容易踩的坑：反射型表必须用反射多项式生成，更新时索引要取CRC寄存器低字节和新数据的异或。如果你把这个更新式用在非反射型CRC上，或者用原多项式生成反射型表，结果必然对不上check值。

我个人的习惯是：写完查表法后，先跑一批随机数据和逐位版对比，再跑check值。两个都过了，才敢说表的方向没问题。

3.3 查表法的性能量级

8位查表法每个字节只做一次查表、一次异或、一次移位，相比逐位版每字节8次迭代已经是一个大的跨越。实测时，在我常用的一台普通x86-64工作站上，1MB随机数据大概是：

具体数字跟编译器、缓冲区大小、CPU型号关系很大，别拿我这组数当绝对标准。但性能排序基本不会有变化。

4. 切片法与专用指令：从软件流水到硬件加速

查表法已经能满足大部分场景，但如果你要给一个TB级文件做校验，或者把CRC打进数据通路里，1GB/s可能还是不够。这时候有两类加速思路。

4.1 slice-by-8 为什么能更快

slice-by-8这个名字误导过不少人，它不是一次处理8个bit，而是一次处理8个字节。实现时会准备8张256项的64位表，每张表对应被处理的8个字节里的某一个位置。计算时一次读入8个字节，把它们和CRC寄存器搅在一起，分别从8张表里取结果并异或。

这样做最大的收益不是减少查表次数，而是打破了逐字节计算时的串行依赖。8次查表和异或之间是相互独立的，现代CPU的多个执行单元可以同时处理，流水线利用率高很多。与此同时，一次读取64位数据对内存总线也更友好。

slice-by-8的索引顺序特别容易写反，而且不同实现里表的排列方式可能不一样。我的建议是不要背代码，直接用一个思路：先把逐位版或8位查表版作为基准，再用随机数据做全量对比。slice-by-8写对了，两个版本在几十万组随机数据上必须完全一致。

4.2 零字节推进与寄存器折叠

无论查表法还是slice-by-8，背后都会用到“让CRC寄存器推进N个零字节”这个概念。你不需要真的去处理N个零，而是可以预计算“推进8个零字节”的变换表，然后把寄存器状态往这个变换上推。这就是slice-by-N表能够一层层展开的原因。

这个概念在做分段校验时也很有用。假设你算完一段数据的CRC状态，想模拟它后面再追加若干字节零，直接用零推进变换即可，不需要真的拿内存去跑。

4.3 硬件乘法指令：把CRC变成多项式乘法

再往上走，某些现代CPU提供carry-less multiply这一类指令。它的思路是把消息分块，先通过多项式乘法把高位块“折叠”到低位，大幅减少需要逐位归约的字节数。这不再是一字节一字节地查表，而是按照64位甚至128位为单位折叠消息。

要注意的是，硬件加速代码平台相关性很强，指令序列、对齐要求、剩余的尾部字节处理都有讲究。我个人建议是先用软件实现跑通并验证check值，再考虑硬件指令；如果一上来就调硬件指令，出了问题很难判断是算法理解错了还是指令序列写错了。

5. 常见CRC64变体参数对照与选型建议

既然CRC64不是单一算法，选型时必须把参数固化下来。下面两组参数分别对应归档场景和流式压缩场景里最常见的两种变体：

除了这两组，还有一种常见做法是把0x1B这个低位数多项式作为生成多项式，反射后变成0xD800000000000000再做LSB表。这种变体在不少标准库里也有实现，但不同实现之间的init和xorout可能不一样，不能只看poly就断定结果一致。

选型时我有几条实际经验：

• 新协议里不要只写“CRC64”，必须把poly、init、refin、refout、xorout五项参数全部写清楚。如果不想写全，至少写清楚check值是多少。
• 如果数据要在多个平台之间互通，优先选反射型变体。反射型在8位单片机上的表更新代码是(crc >> 8) ^ table[crc & 0xFF]，对低端平台更友好，很多软件库默认也是按反射型写的。
• 如果只是本地文件完整性校验，并不需要和外部协议互通，那用哪组参数都行，但代码里必须写明参数，避免三个月后自己都忘了。
• CRC64不具备抗碰撞攻击能力，别有用心的人可以故意构造两个数据让它们的CRC64相同。它适合做误码检测，不适合做防篡改指纹。

6. 工程里最容易翻车的几个CRC64细节

这一节整理的是我在实际项目里真实遇到过的坑，每一个都会导致“看起来没问题但结果就是不对”。

6.1 流式分段计算时，init和xorout放错位置

处理大文件时不可能一次性加载完，通常要分段调用update。正确的结构是这样的：

uint64_t crc = init; while (read_chunk(buf)) { crc = crc64_lsb_update(crc, buf, bytes_read); } uint64_t result = crc ^ xorout;

常见错误有两个：

• 每段算完都执行xorout，然后再把结果喂给下一段update。对于init和xorout都是全1的变体，这样做会破坏中间状态。
• 流式开始时没有给crc赋init，而是一上来就设成0，导致第一段数据开头少了一段初始状态的预处理。

6.2 空数据的CRC不等于0

很多人默认“没有数据，校验值肯定就是0”。但按CRC的定义，空消息的校验值是：

空消息CRC = init ^ xorout

对归档变体，init=0且xorout=0，空消息CRC确实是0。但对init=全1、xorout=全1的流式压缩变体，空消息CRC也恰好是0，容易掩盖问题。还有一些变体init是全1但xorout是0，空消息CRC就会是全1，也就是0xFFFFFFFFFFFFFFFF。

如果你的程序要校验一个可能为空的字段，先把空消息这个case的期望值写进测试用例。

6.3 refout和CPU大小端是两回事

refin、refout描述的是“位方向”，不是“字节序”。一个常见误区是：既然refin=true，干脆把输入数据直接按小端整数读进64位寄存器，再丢给非反射算法处理。实际上反射是指每个字节内部的位倒序，不是把整个64位整数倒着读。

正确的做法是严格按照字节流喂给update函数。如果协议规定数据在网络字节序中传输，你要做的是先按字节序转换，再走CRC计算逻辑，不能指望refin帮你自动处理大小端。

6.4 查表方向搞反

这个问题我在文章里强调过，实践中仍然最容易出现。验证方法不复杂：用一个check值和一个随机数据集的逐位版结果做基准，拿查表版去对。不要只测一个固定字符串，因为某些数据可能碰巧让两种错误算法得出相同结果。

6.5 两块独立计算的CRC不能简单拼接

假设你分别对数据段A和数据段B算了CRC，现在想知道A和B拼接后的CRC，直接把两个CRC值做异或或者按字节拼起来都是不对的。

如果必须在分段场景下组合，安全做法是保留上一段的中间状态，继续把后续数据喂进去。如果两个进程完全独立计算后需要合并结果，那就需要在GF(2)上计算“零块推进”变换，也就是把第一段CRC状态推进第二段长度个零字节，再与第二段结果异或。只有先把init和xorout折算成原始线性状态，这个公式才成立；带着终态异或直接套公式，一定会错。

6.6 最后一个建议：维护一个验证脚本

我在写各种CRC64实现时，会固定放一个验证函数，每次改动实现后先跑check值，再用随机数据对比老的实现。验证函数优先级高于性能测试。很多次手写slice-by-8版本时，索引顺序只要错一个字节，性能再高也不能用，而check值能第一时间把它揪出来。

CRC64的实现路径并不神秘，从逐位版到查表版再到硬件加速，每一步都是同一套数学原理在工程上换了个计算方式。理解了五个参数的作用，再守住“测试向量先行”这条底线，自己实现一套可用的CRC64并没有想象中那么难。