CRC 循环冗余校验的代码实现网上能搜到的版本一抓一大把但真正能一次跑对的不多。我这两年做串口协议、固件镜像校验和存储元数据校验反复跟 CRC 打交道最深的体会是查表算法本身只有四五行代码出错的地方几乎从来不在那个循环里而是藏在表怎么生成、参数怎么配、字节序怎么排这些看起来不起眼的角落。这篇文章不打算复述课本上的多项式除法而是把从逐位移位版本一路推到 256 项查表版本的完整过程摊开讲——一张表里每个元素到底代表什么、反射参数为什么能让输入字节天然倒着走、半字节表和 slicing-by-8 各自在什么场景下更划算。看完应该能拿到一份可以直接抄进项目的实现并且知道怎么用123456789这个标准向量去回测它到底对不对。1. CRC 到底在算什么从 GF(2) 多项式除法到移位寄存器1.1 把数据当成多项式除以一个约定好的生成多项式理解 CRC 最快的方式是忘掉校验两个字先把它当成一次小学竖式除法。一串比特1101可以看成一个多项式x³ x² 1每一位就是对应次幂的系数。CRC 的做法是把这串比特末尾补上 r 个零r 是生成多项式的次数然后除以一个通信双方事先约定好的生成多项式最后的余数就是校验值。这个除法特殊在两点系数只有 0 和 1运算在 GF(2) 域上做加法和减法都是异或。没有进位没有借位所以竖式除法可以简化成对齐最高位、异或、继续。举个能心算的例子数据1101生成多项式1011即x³ x 1r 3补三个零得到1101000。第一步最高位是 1用1011对齐异或得0110000继续对齐下一个 1 异或得0011100再到0001010最后一次得0000001。余数是001这就是 3 位 CRC发送出去的就是1101001。接收端把收到的 8 位整串再除以1011余数为 0 就认为没出错。生成多项式的选法有讲究不是随便挑一个就行。含(x 1)因子的多项式能检出所有奇数个比特翻转的错误次数为 r 的多项式能检出所有长度不超过 r 的连续突发错误。CRC-32 用的0x04C11DB7就含有(x1)因子所以它对单比特错、奇数位错、短突发错的覆盖是有理论保证的这也是它被以太网、压缩格式大量采用的原因。1.2 逐位移位版不写除法也能得到余数真去实现长除法没必要。观察一下上面每一步的动作就会发现整个过程可以用一个寄存器模拟把当前字节推到寄存器的最高位然后看最高位是不是 1是 1 就左移一位并异或生成多项式是 0 就只左移。代码短到可以背下来#include stdint.h #include stddef.h /* CRC-16/CCITT-FALSE: poly0x1021 init0xFFFF refinno refoutno xorout0x0000 */ uint16_t crc16_bitwise(const uint8_t *buf, size_t len) { uint16_t crc 0xFFFFu; /* init 值先填进寄存器 */ for (size_t i 0; i len; i) { crc ^ (uint16_t)buf[i] 8; /* 把待处理字节顶到最高 8 位 */ for (int b 0; b 8; b) { if (crc 0x8000u) crc (uint16_t)((crc 1) ^ 0x1021u); else crc (uint16_t)(crc 1); } } return crc; /* xorout 为 0直接返回 */ }这段代码的正确性很好验证随便挑个在线计算器输入同一串数据就能对上。但它有个明显问题每个字节要循环 8 次每次都有一个依赖前一次结果的分支。在现代 CPU 上这会带来分支预测失败和流水线气泡实测吞吐大概只有每字节 8 到 20 个时钟周期。对于几 KB 的配置数据无所谓但对于几 MB 的固件镜像或者高速采样的数据流这就成了瓶颈。1.3 反射参数为什么输入字节要倒着喂在看查表实现之前必须先把这个反直觉的参数说清楚否则后面一定会绕晕。串口这类硬件是低比特先发的也就是一个字节里 bit0 先上线路而前面推导的长除法是从最高位开始的。为了让硬件实现简单协议设计者干脆规定每个输入字节先按位倒序再送进那个从高位开始的移位寄存器这就是refin true。同理最后寄存器里剩下的值也可能需要倒序输出那就是refout true。这两个参数看着别扭却有一个非常实用的性质当refin和refout都为真时用反射版的算法实现可以一次把两次倒序都抵消掉输入字节不用真的去反转最终结果也不用反转直接就得对。CRC-32/ISO-HDLC、CRC-16/MODBUS、CRC-16/ARC 这些最常用的型号全都属于这一类所以工程里遇到的绝大多数情况写反射版就够了。如果两者不相等比如refin true, refout false你就得在最后多做一次位反转这一点后面第 3 节还会再强调。2. 256 项查表的由来一次吃掉 8 个比特的推导过程2.1 把 8 次移位折叠成一张表逐位移位版本的循环体只有两个动作判断最高位、异或一个常量。既然每个字节固定做 8 次而且这 8 次的输入只取决于当前寄存器最高 8 位异或进来的字节和剩下的低位那就有机会把中间过程固化下来。GF(2) 上的运算全是线性的异或的叠加性允许我们把贡献拆开高 8 位产生的贡献可以预处理低 24 位只是简单地往右挪两者最后异或回一起。对 32 位、高位在前的实现更新公式是crc (crc 8) ^ table[((crc 24) ^ byte) 0xFF];table有 256 项table[i]的定义非常明确把 i 放到寄存器最高 8 位其余位为 0老老实实跑 8 次逐位移位得到的结果就是table[i]。换句话说这张表是逐位移位算法的快照它没有引入任何新数学只是把 8 次移位的结果提前算好了。一个字节一次查表循环体退化成一次取模、一次移位、一次异或没有分支编译器能把它排成流水线实测吞吐通常能到每字节 1 到 3 个时钟周期。表本身 1 KB放进 L1 缓存绰绰有余。2.2 反射版的公式和它对应的建表方式反射版的更新公式是把上面那个式子沿着比特顺序镜像过来crc (crc 8) ^ table[(crc ^ byte) 0xFF];注意这里的差别索引只看低 8 位寄存器往右移参与运算是异或而不是移位取高位。建表方式也跟着变——不是把 i 放到高位而是直接把 i 当作初始寄存器跑 8 次看最低位、右移、异或uint32_t crc i; for (int b 0; b 8; b) crc (crc 1u) ? ((crc 1) ^ POLY_REFL) : (crc 1); table[i] crc;这里最容易踩的坑就是POLY_REFL它必须是原始生成多项式按位反转之后的值而不是原值。CRC-32 的0x04C11DB7反转后是0xEDB88320CRC-16 系列常见的0x8005反转后是0xA001CRC-8 的0x31反转后是0x8C。我见过太多人拿着0x04C11DB7去建反射表所有项都算得出来、程序也不崩就是校验结果永远对不上排查半天才发现是这一处。2.3 用 Python 生成 C 数组别手抄产品代码里把建表放在运行时做完全没问题256 × 8 2048 次迭代启动阶段几微秒的事。但如果你想要只读的常量表放在 Flash 里或者干脆想在编译期就定下来用脚本生成一段 C 代码是最省事的。下面这段 Python 可以直接跑输出就是一份可以粘贴的数组POLY_REFL 0xEDB88320 # CRC-32/ISO-HDLC 的 0x04C11DB7 按 32 位反转 def gen_table_reflected(poly_refl, width): mask (1 width) - 1 tab [] for i in range(256): crc i for _ in range(8): crc (crc 1) ^ poly_refl if crc 1 else crc 1 tab.append(crc mask) return tab def emit_c_array(tab, width, name, per_line4): hexw width // 4 # 32 位 - 8 个十六进制字符 print(static const uint%d_t %s[256] { % (width, name)) for row in range(0, 256, per_line): cells [0x%0*X, % (hexw, tab[i]) for i in range(row, row per_line)] print( .join(cells)) print(};) emit_c_array(gen_table_reflected(POLY_REFL, 32), 32, crc32_table)同一条脚本改两个参数就能生成 CRC-16 的表宽度 16、多项式0xA001非常省心。顺便说一句Python 里没有定宽整数所以每一轮移位之后都要靠mask或者 0xFFFFFFFF把高位截掉否则就是无限精度整数在跑结果一定是错的——这是从 C 思维切到 Python 思维时最容易忽略的一点。3. 五个参数摆平init、refin、refout、xorout 与 poly 的工程化落地3.1 参数模型与型号对照表一个完整的 CRC 型号由五个参数确定宽度、生成多项式 poly、寄存器初值 init、输入是否反射 refin、输出是否反射 refout、结果是否异或一个常量 xorout严格说是六个宽度也算一个。只要这六个参数对上任何实现算出来的值都应该一样。下面这张表是我做交叉验证时常用的几个型号最后一列是123456789这九个 ASCII 字节的标准校验值用来验证实现正确性非常方便型号宽度polyinitrefinrefoutxorout123456789校验值CRC-8/ATM80x070x00否否0x000xF4CRC-8/MAXIM-DOW80x31反射 0x8C0x00是是0x000xA1CRC-16/ARC160x8005反射 0xA0010x0000是是0x00000xBB3DCRC-16/MODBUS160x8005反射 0xA0010xFFFF是是0x00000x4B37CRC-16/CCITT-FALSE160x10210xFFFF否否0x00000x29B1CRC-16/XMODEM160x10210x0000否否0x00000x31C3CRC-32/ISO-HDLC320x04C11DB7反射 0xEDB883200xFFFFFFFF是是0xFFFFFFFF0xCBF43926CRC-32C/Castagnoli320x1EDC6F41反射 0x82F63B780xFFFFFFFF是是0xFFFFFFFF0xE3069283这张表里藏着一条判断经验只要refin和refout相同就优先用反射版实现两者都为真或者高位在前的实现两者都为假不需要额外的位反转步骤。真正麻烦的是refin ! refout的组合比如 CRC-16/X-25 是refin refout true但xorout 0xFFFF处理起来只需要在 return 之前多异或一次逻辑上还是干净的。3.2 反射版 CRC-32 与 CRC-16 的完整实现下面这份 CRC-32/ISO-HDLC 的实现可以直接抄它是 zlib、PNG、gzip 都在用的那个型号。注意几个细节表用static const放在函数外避免每次调用重建移位在uint32_t上做不存在1 31那种有符号整数的未定义行为返回前把 xorout 异或掉#include stdint.h #include stddef.h /* CRC-32/ISO-HDLC: poly0x04C11DB7(refl 0xEDB88320) init0xFFFFFFFF xorout0xFFFFFFFF */ static const uint32_t crc32_table[256] { /* 这里填入 gen_table_reflected(0xEDB88320, 32) 生成的 256 项 */ }; uint32_t crc32_iso_hdlc(const uint8_t *buf, size_t len) { uint32_t crc 0xFFFFFFFFu; for (size_t i 0; i len; i) crc (crc 8) ^ crc32_table[(crc ^ buf[i]) 0xFFu]; return crc ^ 0xFFFFFFFFu; }CRC-16/MODBUS 除了宽度和 xorout 不同结构一模一样这类协议校验特别适合做成宏或者代码生成避免同一套逻辑手写三四遍/* CRC-16/MODBUS: poly0x8005(refl 0xA001) init0xFFFF xorout0x0000 */ static const uint16_t crc16_modbus_table[256] { /* gen_table_reflected(0xA001, 16) 的输出 */ }; uint16_t crc16_modbus(const uint8_t *buf, size_t len) { uint16_t crc 0xFFFFu; for (size_t i 0; i len; i) crc (uint16_t)((crc 8) ^ crc16_modbus_table[(crc ^ buf[i]) 0xFFu]); return crc; }注意(uint16_t)这个强制转换不能省。在 32 位机器上crc 8会提升为int和uint16_t的表项异或之后高位是干净的但语义上显式转换一下更清楚也避免了在别的位宽平台上出现意外。3.3 init 为什么不用 0以及校验值该放在报文的哪一头很多人第一次自己定协议时会把 init 设成 0觉得这样最直观。这么做的问题是如果消息以若干个 0x00 字节开头这些字节对寄存器毫无影响前导零完全得不到保护。一个极端例子是消息00 00 00 01它的 CRC 和01的 CRC 是一样的接收端把前面的零丢掉一个也检查不出来。把 init 设成全 10xFFFF 或 0xFFFFFFFF就等价于在消息前面拼了一串固定的非零比特前导零也能被覆盖。另一个反复出问题的地方是校验值写进报文的字节序。Modbus RTU 的规定是先发低字节再发高字节也就是常说的小端而初学者最容易按crc 8、crc 0xFF的顺序发出去结果对方接收端一直报错。写报文的时候建议用显式的字节写入别用memcpy把uint16_t直接拷进去frame[i] (uint8_t)(crc 0xFF); /* 低字节在前Modbus 约定 */ frame[i] (uint8_t)((crc 8) 0xFF);用memcpy的问题是它拷贝的是内存布局在小端机器上恰好等于低字节在前换到大端平台行为就变了。而显式移位写入无论平台如何结果都一样这种可移植性在一次写、到处编译的嵌入式代码里非常值得。4. 校验值对不对标准向量回测与几个真实踩过的坑4.1 用123456789做回归测试CRC 界的通用约定是拿 ASCII 字符串123456789这九个字节当标准输入各型号的期望值可以查表。这个约定最大的好处是短容易手工验证也几乎被所有在线计算器支持。把它写成单元测试非常划算#include string.h #include assert.h static void test_crc_vectors(void) { const uint8_t *v (const uint8_t *)123456789; /* 9 字节不含结尾 \0 */ assert(crc32_iso_hdlc(v, 9) 0xCBF43926u); assert(crc16_modbus(v, 9) 0x4B37u); }这里有个高频翻车点sizeof(123456789)是 10把结尾的\0也算进去了。用strlen()拿长度、或者写死 9都可以唯独别用sizeof。同理如果你是从文本文件里读内容再算 CRC要弄清楚文件末尾有没有换行符、前面有没有 BOM——这两个字节的差别足以让校验值和计算器对不上而你会盯着算法看半天。4.2 三个把我卡住的坑第一个坑是 Java 和 Python 里的字节符号问题。Java 的byte是有符号的buf[i]可能是个负数直接拿去当数组下标会抛异常拿去异或会把高位全部污染。必须写成table[(crc ^ b) 0xFF]。Python 则反过来没有溢出概念crc 8之后不需要掩码但左移之后必须掩码否则会越滚越大。我见过一个 Python 实现跑小数据全对、跑大数据就错原因就是漏了 0xFFFFFFFF。第二个坑是表被反复重建。有人把建表代码写进函数体却没有加static每次调用都重新算 256 项性能直接回到逐位移位那个档次还有人加了static但在多线程环境里第一次调用就并发进来两个线程同时往同一张表里写。稳妥的做法是编译期生成常量表或者用一次性的初始化保护C11 的call_once、C 的std::once_flag、RTOS 里的启动钩子别指望第一次调用一定是单线程这种假设长期成立。第三个坑是长度算错。这一点在自定义协议里特别常见算 CRC 的范围应该只包含需要保护的那些字段而长度字段本身、填充字段、CRC 字段都不要包含进去。我在调试一个固件升级协议时接收端一直拒绝合法报文最后发现发送端算 CRC 时把长度字段也算进去了接收端不算两边就此各说各话。这种事一旦发生最省时间的做法不是在代码里翻而是把发送端和接收端各自参与计算的字节序列打印成十六进制并排比对。4.3 和在线计算器对不上时的排查顺序排查这种问题我固定按这个顺序走基本能在十分钟内定位先确认参与计算的数据本身一致打十六进制逐字节比对注意换行和 BOM再确认长度一致然后确认型号参数尤其是init和xorout这两个参数至少在位、全 1 两种取值之间换一遍试试接着确认 poly 是不是用反了反射表必须配反转后的 poly最后才怀疑字节序和写入顺序。按这个顺序走的好处是每一步都能用打印直接验证不需要去改算法本身避免了越改越乱。还有一个很实用的手段拿一段很短的输入比如单个字节 0x00 和 0x01分别跑自己的实现和参考实现对比中间状态。输入越短出错的环节越少定位越快。我通常会临时加一个逐字节打印寄存器值的调试宏跑完两个字节就能看出是从第一步就偏了还是最后一步 xorout 漏了。5. 省 Flash 还是省 CPU半字节表、slicing-by-8 与硬件 CRC 的取舍5.1 16 项半字节表把 512 字节压到 32 字节在 Flash 只有几十 KB 的小单片机上CRC-16 的 256 项表要占 512 字节有时候确实心疼。这时候可以退一步用半字节表只有 16 项、32 字节代价是每个字节查两次表。实现长这样/* CRC-16/MODBUS 半字节表版本表只占 32 字节 */ uint16_t crc16_modbus_nibble(const uint8_t *buf, size_t len) { static const uint16_t tab[16] { 0x0000, 0xCC01, 0xD801, 0x1400, 0xF001, 0x3C00, 0x2800, 0xE401, 0xA001, 0x6C00, 0x7800, 0xB401, 0x5000, 0x9C01, 0x8801, 0x4400 }; uint16_t crc 0xFFFFu; for (size_t i 0; i len; i) { crc ^ buf[i]; crc (uint16_t)((crc 4) ^ tab[crc 0x0Fu]); crc (uint16_t)((crc 4) ^ tab[crc 0x0Fu]); } return crc; }这张 16 项的小表有个很有意思的性质其中的项和 256 项大表里的值是同一套数学的不同截断所以在同一型号下两者算出的结果完全一致。我第一次换成半字节表时专门跑了 10 万组随机数据的对比测试确认逐字节结果相同才敢上线。速度上大约比 256 项表慢 30% 到 60%但对一个每秒只处理几百字节的 Modbus 从机来说完全无感。5.2 slicing-by-4 和 slicing-by-8多表并行的原理与代价如果瓶颈在 CPU 而不是 Flash方向就反过来了。slicing-by-8 的思路很巧妙既然一次处理一个字节已经用了一张表那一次性处理 8 个字节呢把 8 张表排好让 8 个字节的贡献各自独立地查表异或进来最后合并。因为 GF(2) 运算是线性的这种拆分在数学上完全成立。代价是 8 张表、8 KB 的常量数据而且对短数据反而不划算——启动和收尾的代码变长处理几十字节的小报文可能还更慢。我的经验是数据量超过 1 KB、而且这段逻辑真的在性能剖析里排到前面才考虑上 slicing-by-8否则单表版本已经足够。很多时候真正拖慢程序的不是 CRC 本身而是围着它做的那堆缓冲区拷贝。5.3 硬件 CRC 与指令加速能用但不一定对得上你的型号现在很多 Cortex-M 芯片自带 CRC 外设配置好多项式和一个初始值把数据按字写进去就能出结果基本上不占 CPU 时间。x86 上有 SSE4.2 的crc32指令ARMv8 有一组 CRC 指令。但这里有个必须提前确认的点硬件单元支持的多项式和参数往往是固定的。比如常见的芯片 CRC 外设只支持 32 位0x04C11DB7那一套设置要它算 Modbus 的 CRC-16 就完全没法对上只能老老实实用查表。所以我的做法是先确定协议要求哪个型号再去翻芯片手册看硬件单元支不支持这个型号、参数范围够不够。如果恰好能对上用硬件加速是最省电的方案对不上就别硬凑用 256 项表的软件实现性能通常也完全够用。另外提醒一个容易忽视的细节硬件 CRC 外设和软件实现之间的验证一定要做交叉比对尤其是在初始化顺序、数据写入位宽按字节写还是按字写、大小端解释这几处很容易出现单独看都对接起来就是错的情况。我通常会写一个测试用例用同一段123456789分别过软件和硬件两条路径两者结果一致才认为配置成功。最后分享一个我自己一直在用的老办法不管项目最终用哪种实现我都会在代码仓库里保留一份最笨的逐位移位版本专门用来做参照。新写的查表版、半字节版、甚至硬件加速版测试用例里一律跟这份笨实现对比随机数据。这份代码跑得慢但它逻辑短到不可能写错用来当标准答案再合适不过。