1. 从标准到实现：CRC32到底是谁在定规则

CRC32差不多是每个做通信、存储、网络协议的开发者都绕不过去的东西，也是校验和里面被讨论最多的一种。在“CRC推导”这个系列里，前面几篇我们已经把CRC的数学原理、多项式除法模型和常见参数化配置都捋了一遍，这篇专门聊CRC32的实现层面：从最慢的逐位计算，到工业界最常用的查表法，再到为了榨干带宽而生的Slice-by-8并行算法，并给出手写可用的代码。

先明确一件事：当我们说“CRC32”时，默认指的是IEEE 802.3定义的那个CRC32，也叫CRC-32/ISO-HDLC。它的参数是固定的多项式0x04C11DB7，初始值0xFFFFFFFF，输入数据不反转，输出结果要再异或0xFFFFFFFF。这几个参数少一个，算出来的结果就对不上。很多人在网上抄CRC代码翻车，往往不是移位逻辑写错，而是初始值和最终异或忘了处理。

在真正写实现之前，我建议你把CRC32当作一个“除法取余”的过程：把数据看成一个巨大的二进制数，对它做模二除法，除数是多项式，余数就是校验值。为什么初始值不是0？因为如果数据前面有一串0，直接算余数会是0，这会让某些误码场景失效。初始值全1相当于在数据前面补了32个1，把这些“前导零”的干扰消掉。结果异或0xFFFFFFFF则是一种“白化”处理，保证全0的数据也能产生非0的校验值。

这些规则理解透了，再看各种实现，你会发现它们本质上是同一件事的不同计算顺序。

2. 逐位实现：最慢但最能讲清原理的版本

2.1 按位右移的教科书写法

CRC32计算时，处理的顺序是从数据的最高位开始。由于多项式是0x04C11DB7，二进制表示是00000100 11000001 00011101 10110111，最高位是第32位（bit 32）。为了编程方便，大家通常把多项式去掉最高的那个1，保留低32位，记作0x04C11DB7，在移位运算中检测的是寄存器最高位（bit 31）是否溢出。

最朴素的做法是逐bit处理。伪代码逻辑如下：

每个bit进来，先看当前寄存器最高位是1还是0，然后寄存器左移一位，把新的数据bit填充到最低位。如果刚才最高位是1，就异或上多项式（去掉最高位的那个1）。这个过程本质上就是二进制长除法，只是每次只处理一位。

我见过不少刚接触CRC的人会纠结一个问题：为什么不是先移位再判断？其实两种写法都可以，只要你保证“异或的时机”和“数据bit进入的位置”对应正确。标准做法是：先判断旧最高位，再左移，再决定是否异或。如果你把顺序搞反，结果就错了。

下面给出一个可以直接用的C实现，处理单字节时逐bit处理，方便对照推导过程：

#include <stdint.h> uint32_t crc32_bitwise(const uint8_t *data, size_t len) { uint32_t crc = 0xFFFFFFFFu; for (size_t i = 0; i < len; i++) { crc ^= data[i]; for (int j = 0; j < 8; j++) { if (crc & 0x80000000u) { crc = (crc << 1) ^ 0x04C11DB7u; } else { crc <<= 1; } } } return crc ^ 0xFFFFFFFFu; }

注意这里把数据字节直接异或到crc的低8位（即crc ^= data[i]），再循环8次。之所以能这样简化，是因为逐bit算法的本质是：每输入一个bit，crc的bit31和该bit先异或，然后左移并与多项式异或。把整个字节先异或进去，和逐bit输进去是等效的，因为异或满足交换律和结合律。

2.2 一次处理一位的代价有多大

逐位算法的优点是代码短、逻辑直白，初学CRC推导时用它验证“多项式除法”模型非常合适。缺点也很明显：每个字节要循环8次，每比特都是移位和条件分支，而且这个分支高度依赖数据，CPU分支预测几乎必然失效。

实测下来（在2020年前后的x86平台上），逐位算1MB数据大概需要几十毫秒级别。具体数字会因编译器优化和CPU微架构差异而变，但量级不会太好看。对于大多数嵌入式单片机、低速通信协议（如Modbus、I2C、SPI采集），逐位实现已经足够；但只要数据吞吐量上到几十KB/s以上，逐位算法就会变成瓶颈。

这也是查表法存在的理由：既然每一bit都要做一次“移位+条件异或”，那不如用一个字节（8bit）为单位，把所有可能输入组合的结果提前算好，运算时直接查表。

3. 查表法是怎么“用空间换时间”的

3.1 查表的核心思想：把8次循环变成一次查表

查表法的基础建立在线性移位上。观察逐位算法：处理一个字节时，寄存器状态经过了8次左移和条件异或。把多项式运算看作一个线性变换，那么一个字节输入后的净效果只取决于两个因素：进入字节前的寄存器高位状态，以及新字节的值。

更直白的说法是：我们可以把“喂入一个字节”这个动作，拆成“这个字节对寄存器产生的影响”。由于CRC运算是线性的，字节对结果的贡献可以预先计算。

最常见的是按字节查表（table-driven byte-wise）。以右移版本为例，处理每个字节时，先把crc的高8位取出来，与数据字节异或得到索引，然后用查表值替换crc的高8位，同时crc低24位左移8位。公式化表达是：

crc = (crc << 8) ^ table[((crc >> 24) ^ data[i]) & 0xFF];

这个table表有256个32位元素，每一项的含义是：当寄存器高8位是某个值、并且与数据字节异或后，对这个组合进行8次CRC移位的结果。生成表的代码如下：

uint32_t crc32_table[256]; void crc32_init_table() { for (int i = 0; i < 256; i++) { uint32_t c = (uint32_t)i; for (int j = 0; j < 8; j++) { if (c & 0x80000000u) { c = (c << 1) ^ 0x04C11DB7u; } else { c <<= 1; } } crc32_table[i] = c; } }

生成表的过程本身就是一个逐位计算，只是这个计算在初始化时执行一次，运行时再也不会重复。之后每一字节只需要一次查表和三次移位、一次异或，速度自然快了一个数量级。查表法处理1MB数据，在普通桌面上通常是0.1ms级别，比逐位快几十倍。

3.2 左移项目和右移项目怎么选表

上面给出的是右移表，它对应的是标准CRC32（RefIn=0，RefOut=0），也就是数据从最高位输入，寄存器右移，多项式用正常顺序。但实际工程里有大量协义用的是反射CRC，比如CRC32/PHP、CRC32/BZIP2就是反射版本。此时输入数据最低位先进，寄存器左移，多项式也要反转。这种场景需要另一张表。

左移版本的逐位逻辑是：寄存器右移（注意方向不同），多项式反转。以CRC32为例，反射多项式是0xEDB88320（0x04C11DB7位反转后的低32位）。逐byte查表公式是：

crc = (crc >> 8) ^ table[(crc ^ data[i]) & 0xFF];

对应的表生成代码是把左移逐位过程换成右移，并异或0xEDB88320：

uint32_t crc32_ref_table[256]; void crc32_init_ref_table() { uint32_t poly = 0xEDB88320; for (int i = 0; i < 256; i++) { uint32_t c = (uint32_t)i; for (int j = 0; j < 8; j++) { if (c & 0x00000001u) { c = (c >> 1) ^ poly; } else { c >>= 1; } } crc32_ref_table[i] = c; } }

很多开发者在移植代码时，直接把常见开源库里的表拿来用，却不核对多项式方向和自己的协议是否匹配。比如一些网上的代码用的是0x04C11DB7，另一些用0xEDB88320，两者算出来的CRC是完全不同的。最简单的判断方法：把你协议里的测试向量（如空数据的CRC值）放进实现的函数里跑一下，对不上就说明表的方向选错了。

3.3 双查表：用两张表减少一次移位

纯查表法每处理一个字节，仍然需要若干次移位和异或。还能不能更快？可以，用双表或多表。

双表的思想是：既然表中的值可以直接和crc异或，那么把“索引取字节”和“高字节更新”拆开，两张表分别放“当前字节的影响”和“寄存器高字节的影响”。这种写法每处理4个字节可以省掉几次移位，但代码可读性下降很多。除非你的目标平台极其孱弱，否则我建议直接用Slice-by-4或Slice-by-8，效果更好，思路也统一。

4. Slice-by-4 和 Slice-by-8：把内存带宽吃满的并行实现

4.1 为什么一次处理多字节还能保持线性

查表法每处理一字节，需要依赖上一个字节的处理结果，这形成了一条串行依赖链。CPU虽然支持流水线，但单条依赖链限制了每秒能处理的字节数。Slice-by-N算法通过同时处理多个字节，打破部分依赖链，实现吞吐量成倍提升。

它的原理建立在CRC的线性可分性上：对于多个连续字节，可以把这个块拆成若干条“流”，每条流独立查表，最后再合并。数学基础是：

CRC的移位和异或都是线性的，所以一个字节块[b0, b1, b2, b3]对寄存器的贡献，可以分解为各字节独立作用后异或的结果。

以Slice-by-4为例，它同时处理4个字节。先将寄存器按字节拆成四段，四个表分别对应一个字节位置的贡献。每个表的索引分别由crc的某个字节和输入数据的某个字节异或得到。更新时，四个表值一起异或到寄存器上。这样每处理4个字节，只需要4次查表和4次异或，且这4次查表彼此独立，CPU可以乱序执行，流水线利用率大大提升。

4.2 Slice-by-8的实现细节与注意事项

Slice-by-8在Slice-by-4基础上进一步提升，一次处理8个字节。它需要8张表，每张表256个32位值，合计8KB内存（256×4×8=8192字节）。现代CPU的L1缓存通常是32KB以上，8KB完全放得下，这也是一般建议使用Slice-by-8而不是更大Slice的原因之一。

下面给出一个基于标准CRC32（非反射）的Slice-by-8示例。这个代码处理的是按大端序连续数据块，输入是32位数据块指针。

#include <stdint.h> extern uint32_t crc32_slice8_table[8][256]; static inline uint32_t crc32_slice8_byte(uint32_t crc, const uint8_t *data) { crc ^= *data; crc = crc32_slice8_table[0][crc & 0xFF] ^ crc32_slice8_table[1][(crc >> 8) & 0xFF] ^ crc32_slice8_table[2][(crc >> 16) & 0xFF] ^ crc32_slice8_table[3][(crc >> 24) & 0xFF]; return crc; } uint32_t crc32_slice8(const uint8_t *data, size_t len, uint32_t crc) { crc = 0xFFFFFFFFu; while (len >= 8) { uint32_t v0 = ((uint32_t)data[0] << 24) | ((uint32_t)data[1] << 16) | ((uint32_t)data[2] << 8) | data[3]; uint32_t v1 = ((uint32_t)data[4] << 24) | ((uint32_t)data[5] << 16) | ((uint32_t)data[6] << 8) | data[7]; crc = crc32_slice8_table[7][(v0 ^ crc) & 0xFF] ^ crc32_slice8_table[6][((v0 ^ crc) >> 8) & 0xFF] ^ crc32_slice8_table[5][((v0 ^ crc) >> 16) & 0xFF] ^ crc32_slice8_table[4][((v0 ^ crc) >> 24) & 0xFF] ^ crc32_slice8_table[3][(v1 >> 24) & 0xFF] ^ crc32_slice8_table[2][(v1 >> 16) & 0xFF] ^ crc32_slice8_table[1][(v1 >> 8) & 0xFF] ^ crc32_slice8_table[0][v1 & 0xFF]; data += 8; len -= 8; } while (len--) { crc = (crc << 8) ^ crc32_slice8_table[0][((crc >> 24) ^ *data++) & 0xFF]; } return crc ^ 0xFFFFFFFFu; }

注意这里表的下标顺序和异或顺序不是随便排的，它来源于“每个字节在块中的位置对结果的影响”不同。不同Slice-by-8实现可能表顺序不一样，但核心都一样：把当前寄存器和两个32位数据合起来拆成8个索引，分别查8张表，最后异或。

4.3 表的生成方法

Slice-by-8的表不是8个独立的原始逐位表，而是由基础表派生而来。生成思路如下：

• 先用反射版的逐位算法生成0号表（256项，每项表示单个字节在寄存器低8位时的贡献）。
• 1号表由0号表“高8位左移8位后的贡献”组合得到，以此类推。但实际上更通用的做法是：对每个可能的字节值，计算它在一个64位块中处于不同位置时的效果，即分别计算bytes[i] << (24 - 8*i)等移位后做CRC的结果。

我建议你不要手推表，直接用现成计算器或脚本生成后打印成数组。下面是用Python生成标准CRC32 Slice-by-8表的方法：

def crc32_slice8_tables(): tables = [] for i in range(8): table = [] for val in range(256): c = val << (8 * (7 - i)) for _ in range(8): if c & 0x80000000: c = (c << 1) ^ 0x04C11DB7 else: c <<= 1 table.append(c & 0xFFFFFFFF) tables.append(table) return tables

这个Python生成方式对应的是非反射式的Slice-by-8。生成的表用于crc32_slice8函数。如果协议是反射式的，你把移位方向和多├0xEDB88320替换掉即可。重点是理解：每个表对应一个输入字节在所有字节流中的位置贡献，而不是简单的“逐字节查表”表。

5. 反射与非反射、字节序这些“看不见”的坑

5.1 RefIn/RefOut到底翻转了什么

CRC参数中，RefIn表示输入数据在参与计算前是否按位反转，RefOut表示最终结果是否按位反转。IEEE 802.3标准里这两个参数都是False（也就是不反转）。而很多现代协议（如ZIP、PNG里的CRC32）恰恰相反，RefIn=1，RefOut=1。

反射版本的计算逻辑，在数学上等价于把数据倒序后使用正常版本，再对结果倒序。但在代码实现上，反射版本比正常版本更常见，因为它处理小端架构的数据时更自然——数据字节不变，只是位序反过来。

举个例子：数据0x31，正常CRC32是把bit7（最高位）当作第一个参与运算的bit；反射CRC则是把bit0（最低位）当作第一个。对于协议双方，必须采用相同的反射设置，否则校验值必然不匹配。这是最典型的问题源。

5.2 字节序的坑：查表法的数据排列

即使同一套算法，处理多字节数据时，也要明确“数据字节怎么组合成数值”。在Slice-by-8中，我们使用大端拼装：data[0]是最高字节，data[7]是最低字节。这是为了方便和crc寄存器的对齐。如果平台是小端，直接读32位数再强转，结果会变成按小端顺序组合的数值，导致算法错误。

所以最稳妥的方式：用字节指针逐字节读取，并手动组装成你期望的整数。不要图省事直接*(uint32_t*)data，因为这块内存在不同平台上对齐和字节序都可能出问题，而且严格别名规则下这是未定义行为。写CRC代码要稳，就永远用memcpy或字节组装。

5.3 处理末尾字节的顺序

当你用Slice-by-8时，数据长度不一定刚好是8的倍数。处理剩余字节时，必须从数据的开头方向继续算，也就是用逐字节查表法按顺序处理剩下的部分。

很多人在这踩坑：把剩余字节直接倒序处理了，或者是先取尾部8字节，结果后面的字节顺序反了。正确的做法是向前（后续）逐一处理，而不是从尾部回退。

6. 实测对比与选型建议：你的项目适合哪一种

6.1 性能与内存的典型数据

我在一个模拟项目里测过几种实现，处理1MB随机数据，编译器与平台是x86-64，O2优化。数据大致如下：

需要说明的是，这些数据仅供量级参考，不同CPU差异很大。更重要的是趋势：查表法的收益巨大，而Slice-by-8相比单表是4倍左右提升，且表的体积只多7KB。对于现代系统，8KB放在L1 Cache里，几乎没有额外cache压力。对于只有几KB RAM的MCU，Slice-by-8就不现实了，单表或半字节表（256个4bit项，128字节）才是稳妥选择。

6.2 嵌入式场景的折中方案

嵌入式环境如果内存紧张，可以使用半字节查表（nibble table），每表16项，一次处理4bit。速度比逐位快一半，内存极小。很多老代码用这种方案。如果你用的是Cortex-M系列，其实单表查表法已经完全够用，因为MCU主频不太高，但CRC运算速率通常也不是瓶颈。

如果MCU硬件自带CRC外设，那么软件实现可以退居二线。硬件CRC模块通常只支持特定多项式，且不能配置反射参数，使用前要仔细看手册。如果模块参数与你的协议不匹配，宁可用软件实现，也不要去硬适配。

6.3 我实际使用的选型思路

我个人的习惯是：

• 验证算法正确性：写逐位版本，配合几个已知测试向量去验证。
• 项目正式用：网络协议栈、文件解析之类的，直接用Slice-by-8，表用静态数组初始化。
• 资源受限：MCU内存小于8KB时，用单表或半字节表。
• 追求极致：x86平台可以直接用硬件CRC32指令（SSE4.2的crc32指令），但那已经超出了“实现”的讨论范畴，而且指令是针对特定多项式的，可移植性要谨慎。

另外建议：所有CRCT实现，在投入使用前，一定要用0x12345678这类很有规律的测试向量去跑一下，拿标准在线计算器的结果做对照。我踩过最隐晦的坑是：单表版本对着某个数据算对了，但换成长数据且长度不是4的倍数时，错了。原因是剩余字节处理时没有做初始值的合并，导致多算了几个零字节。所以测试向量要覆盖长短不一的数据，至少包含0字节、1字节、4字节、8字节、9字节这几种。

7. 从一个巧妙的小技巧说起：用CRC32 and 0xFFFFFFFF独立处理剩余字节

Slice-by-8的代码中，最后剩余字节的逐字节循环会创建一个小的串行依赖。一个不大常见但值得一提的技巧是：我们可以用一张独立的“剩余字节表”把剩余字节也并行化。具体做法是把剩余字节分成两组，用两张表分别处理，最后合并。不过这种优化收益有限，因为剩余字节通常很少，最后循环最多执行7次。除非你对数据长度有严格的模值要求，否则不值得为此增加代码复杂度。

我更喜欢的一个小技巧是：在循环中先把所有长度>=8的数据块处理完，再根据剩余长度len & 7分别处理1、2、3...7字节。用switch或跳转表可以减少逐字节循环中的判断开销。这个优化在数据长度经常刚好不是8的倍数时有一定效果，但对于现代CPU的乱序执行，收益很小。写了也权当是一种乐趣。

7.1 CRC32在文件校验里的一个额外坑

很多人用CRC32校验文件时，会把整个文件算完再和预存值比较。注意有些工具（比如某些压缩包里的CRC）存储的是“原始数据的CRC”，有些则是“原始数据加上若干元数据后的CRC”。这导致同样的文件，用不同工具算出来的CRC可能不一致。这跟实现无关，而是协议定义问题。在写代码时，务必确认你的函数是不是只处理原始数据，别把你自己的代码里做的额外变换（比如加入长度字段）也算进去。

7.2 关于初始化值与最终异或的再次提醒

不同语言的标准库行为也不同。例如一些语言的标准库算出来的CRC32是已经做过最终异或的，而底层C库的某些实现却要求你手动做。这个差异非常容易让你在跨语言联调时怀疑人生。我曾经花了一个晚上，才意识到不是算法错了，而是C函数返回值没有做最终异或，其他语言却做了。所以文档里明确标注“函数返回的是原始余数还是最终校验值”非常重要。

8. 如何写出一个任何人都能验证的CRC32实现

最后，如果你要写一个串行化的、清晰的CRC32实现用于教学或移植，我给一个完全自包含、不含任何表的版本。它虽然慢，但对照参考实现极容易排错：

#include <stdint.h> #include <stddef.h> static uint32_t crc32_bitwise_reflect(const uint8_t *data, size_t len) { uint32_t crc = 0xFFFFFFFFu; for (size_t i = 0; i < len; i++) { crc ^= data[i]; for (int j = 0; j < 8; j++) { if (crc & 1) { crc = (crc >> 1) ^ 0xEDB88320u; } else { crc >>= 1; } } } return crc ^ 0xFFFFFFFFu; }

注意这段用的是反射多项式0xEDB88320，它处理的是最常见的“标准CRC32”，和ZIP、PNG等一致。为什么这里用反射版本？因为网络上流传的“标准CRC32”多半指反射版。如果你想验证，可以用在线工具计算字符串"123456789"的CRC32，反射版标准结果是0xCBF43926。拿这个向量去测，对上了就说明环境没问题。

这个简洁版本的价值在于：你完全可以用它去生成查表法的表，或者用它去校验Slice-by-8的结果。我每写一个优化版本，一定会先跑一遍这个串行版本，确保加表、加并行以后没有改变算法语义。

CRC32的实现并没有那么复杂，但细节藏在参数配置、移位方向、表生成和剩余字节处理这些地方。你只要吃透推导的原理，写什么版本都不会心虚。这篇就聊到这里，下一篇我准备聊CRC的校验强度分析和碰撞概率，算是从另一个角度继续深入CRC。