上周同事解压一份安装包跑到一半屏幕跳出gzig:stdin: invalid compressed data --crc error他的第一反应是文件没下全重下三遍报错一次不差。同一天下午另一位朋友的千兆板子在百兆链路下跑得稳稳当当一切到千兆PHY 的接收统计里 hardware CRC error 计数器就开始往上窜。两个场景看起来八竿子打不着——一个是压缩包一个是网口——但卡在同一个东西上CRC循环冗余校验。CRC 大概是嵌入式、网络、存储、文件格式这些领域里最人尽皆知但没几个人真懂的算法。说它人尽皆知是因为几乎每个协议里都有它Modbus、CAN、以太网 FCS、PNG、gzip、Flash 里的 ECC 校验区随手一抓一大把说没几个人真懂是因为大部分人只做过两件事从网上复制一段查表法代码或者打开一个 crc 校验计算器在线页面输入数据、选个模式、对一下结果。至于那段表是怎么来的、为什么有时候差 1 个字节就全错、为什么同样的数据两个工具算出来不一样基本靠猜。这篇东西想把直接计算法和查表法这两条路从头到尾摊开讲清楚多项式除法在二进制世界里到底怎么走、逐位实现为什么长成那样、256 项的查表是怎么从直接法里榨出来的、参数模型那六个开关各自管什么、以及在真实项目里怎么用 check 值把问题一层层剥开。适合刚接触协议栈的同学也适合写了几年代码但从没自己生成过 CRC 表的老手——表里的数字对不上的那种抓狂大家应该都体会过。1. CRC 不是加密也不是求和先把它的数学模型摆正1.1 从一条 gzip 报错说起回到开头那个--crc error。gzip 的格式很简单头部若干字节中间是压缩数据最后 8 个字节是尾部——其中 4 字节是原始数据的 CRC-32 值另外 4 字节是原始数据的长度。解压的时候解压器会把还原出来的每一个字节喂给一个 CRC-32 计算器等全部数据吐完把算出来的值和尾部记录的值比一下对不上就报 crc error。这个设计有个很关键的性质它不是在检查压缩数据有没有坏而是在检查解压结果对不对。也就是说如果压缩数据本身在传输中翻了几位解压出来的字节流大概率完全变样CRC 直接不匹配但还有一种更阴的情况——某段数据被改坏了解压器仍然能正常吐出字节只是内容错了这时候 CRC 就是最后一道防线。所以看到 crc error第一反应不该是下载没下全而是原始文件或者传输链路出了问题需要从源文件和传输两端去查。顺带说一句gzip 用的 CRC-32 和以太网帧尾 FCS 用的 CRC-32参数是完全一样的多项式0x04C11DB7初始值0xFFFFFFFF输入输出都按位反射最后再异或0xFFFFFFFF。同一个算法在两个完全不同的领域用了三十多年这也从侧面说明它有多耐用。1.2 模 2 除法没有进位的除法CRC 的本质是把一串二进制位看成一个多项式的系数。比如数据1101就对应多项式x³ x² 1——最左边那位是最高次项。这个映射不神秘只是把比特和多项式系数对应起来方便用代数工具分析。接下来是核心动作模 2 除法。普通除法里 112 会进位模 2 除法里加法就是异或110没有进位也没有借位除法的每一步就是如果当前余数的最高位是 1就异或一下除数然后左移一位。举个例子取一个 4 位的生成多项式10011也就是x⁴ x 1数据用1101。先给数据后面补 4 个 0补几个 0 由多项式宽度决定4 位就补 4 个得到被除数11010000然后拿10011去做模 2 除法11010的最高位是 1异或10011得01001去掉前导 0 变成1001拉下一位0得到10010最高位是 1异或10011得00001拉下一位0得到00010最高位是 1继续约简最终剩下0100。所以这个 4 位 CRC 的余数是0100也就是0x4。这个结果我用后面要讲的逐位代码又验算了一遍一模一样。整个过程没有乘除只有移位和异或——这就是为什么 CRC 在硬件里只需要几个触发器加几个异或门就能实现成本低到几乎可以忽略。有个更省事的等价算法叫寄存器法维护一个宽度等于多项式位宽的寄存器初始值设为init每来一个数据位先把寄存器左移一位、把新位塞到最低位然后看移出去的那一位是不是 1是 1 就异或多项式。这个写法和长除法看起来不一样但结果完全等价而且更适合写成代码。后面讲直接计算法时我用的就是这个形式。1.3 CRC 的能力边界为什么它能抓住突发错误很多人以为 CRC 就是个加强版校验和其实两者的数学结构差得挺远。简单的累加和两个字节一个加 1 一个减 1 就抵消了CRC 是多项式除法取余任何一位翻转都会让余数产生一个几乎不可能被另一处翻转抵消掉的偏移。从理论上讲一个宽度为 n 的 CRC 能保证检出所有长度不超过 n 的单比特错误、所有长度不超过 n 的双比特错误以及所有奇数个错误前提是生成多项式里含有x1这个因子。对于更长的突发错误检出的概率大约是1 - 2^(-n)。16 位 CRC 漏检率约 1/6553632 位约 1/43 亿这就是为什么以太网选择 32 位——两千字节的帧43 亿分之一的漏检概率基本可以当零看。但必须强调一句CRC 是查错用的不是防篡改用。它没有密钥攻击者想改数据顺便改 CRC成本比改数据本身高不了多少。凡是需要防篡改的场景得用哈希或消息认证码别拿 CRC 顶上。我在项目里见过有人用 CRC 当数据完整性签名这是纯粹的概念误用。1.4 六个参数CRC 其实是一族算法初学者最容易掉的坑是以为CRC只有一个算法。实际上它是一族算法由六个参数共同定义width位宽8、16、32、64 都常见poly生成多项式比如0x1021、0x04C11DB7init寄存器的初始值全 0、全 F 都有refin输入数据按位反射即字节内的比特顺序反过来还是按原序refout输出结果要不要反射xorout最终结果要不要再异或一个常量。这六个参数只要有任何一个不同同一个数据算出来的结果就完全不同而且这种不同不是差一点点是彻底没关系。后面第 4 节我会专门讲怎么用这六个参数把结果对不上的问题定位到具体哪个环节。这里先记住一句话报 CRC 不匹配的时候第一个要确认的不是数据对不对而是两边用的是不是同一个参数模型。2. 直接计算法把每一位的移位异或写在明面上2.1 手推一个字节0x31 在 CRC-8 下的 8 次迭代理论讲完我们拿最小可用的例子走一遍。选 CRC-8多项式0x07也就是x⁸ x² x 1初始值 0不反射。这种配置在 SMBus 之类的地方很常见。以字节0x31字符1为例直接计算法的过程是把当前寄存器值和这个字节异或然后重复 8 次看最高位、左移、按需异或多项式。迭代进入时的值最高位移一位后异或多项式后起始0x31 ^ 0x00 0x31---10x31 (0011 0001)00x620x6220x62 (0110 0010)00xC40xC430xC4 (1100 0100)10x880x8F40x8F (1000 1111)10x1E0x1950x19 (0001 1001)00x320x3260x32 (0011 0010)00x640x6470x64 (0110 0100)00xC80xC880xC8 (1100 1000)10x900x97最终结果是0x97。这个推导过程建议你自己拿纸笔再走一遍尤其是第 3 步和第 4 步——那两步最高位是 1所以先左移再异或顺序不能反。很多人在纸上推的时候会写成先异或再左移结果必然对不上。2.2 MSB-first 逐位实现的代码长什么样把上面的手工过程翻译成代码就是所谓的逐位直接计算法。Python 版本适合验证和理解C 版本适合上机def crc_bitwise_msb(data, poly, width, init0, xorout0): 非反射MSB-first逐位 CRC data: bytes poly: 生成多项式未反射形式例如 CRC-8 的 0x07、CRC-16/CCITT 的 0x1021 width: 位宽例如 8 / 16 / 32 mask (1 width) - 1 topbit 1 (width - 1) crc init mask for byte in data: # 把字节对齐到寄存器的高 8 位后异或 crc ^ (byte (width - 8)) mask for _ in range(8): if crc topbit: crc ((crc 1) ^ poly) mask else: crc (crc 1) mask return (crc ^ xorout) mask注意crc ^ (byte (width - 8)) mask这一行。8 位 CRC 时移位量是 0等价于直接异或16 位时左移 8 位也就是把字节放到寄存器的高半部分。为什么要放高位因为下面 8 次迭代是从最高位开始约简的数据必须和当前余数的最高位对齐否则异或在错误的位上结果就废了。还有一个细节data里的字节是按什么顺序喂进去的。协议里通常是先发第一个字节那代码里就先处理第一个字节不要自作聪明地倒过来。我见过有人在 SPI Flash 的 CRC 校验里把数据段倒序传入查了两天才发现是调用方的问题。2.3 反射版本LSB-first 和那个反着写的多项式上面那套是高位优先。但现实中大量协议用的是低位优先——Modbus RTU、很多串口协议、以太网的 FCS都是先处理字节的最低位。这个模式叫反射reflected实现上跟 MSB-first 有个镜像关系def crc_bitwise_lsb(data, rpoly, width, init0, xorout0): 反射LSB-first逐位 CRC rpoly: 反射后的生成多项式例如 CRC-16/MODBUS 的 0xA001、CRC-32 的 0xEDB88320 mask (1 width) - 1 crc init mask for byte in data: crc ^ byte # 异或在最低 8 位 for _ in range(8): if crc 1: # 看最低位不是最高位 crc (crc 1) ^ rpoly else: crc 1 return (crc ^ xorout) mask对比一下两版代码的区别一个是一个是一个看最高位一个看最低位一个把字节挪到高 8 位再异或一个直接异或在低 8 位。这不是随便写的而是把整个多项式除法镜像过来的结果——最高位变最低位左移变右移多项式也相应地按位反过来。关于rpoly这里先给个数感CRC-32 的多项式是0x04C11DB7反射以后是0xEDB88320也就是 zlib、PNG 里到处能看到的那个魔数。CRC-16/MODBUS 用0x8005反射后是0xA001。这两个数在反射算法里不是另一种多项式而是同一个多项式的镜像表示后面 4.3 节会专门澄清这个误解的低级错误版本。2.4 直接法到底慢在哪直接法的可读性非常好几乎是把数学定义直译成代码适合做参考实现。但它的性能确实不客气每处理一个字节内层循环要跑 8 次每次都有一次移位、一次按位与、一次条件判断和可能的异或。算笔账处理 1 MB 数据外层 100 万次内层 800 万次。每次迭代哪怕只花 3 个时钟周期也是 2400 万个周期跑在 100 MHz 的 MCU 上就是 0.24 秒。如果这段代码在中断里、或者数据量变成 100 MB那就完全不可接受。更麻烦的是分支预测——if的结果取决于数据本身随机数据的命中率大概一半一半现代流水线最讨厌这种情况。所以直接计算法的定位应该很明确用来理解、用来生成查表、用来做单元测试的对照组但不要放进量产代码的主路径。我个人的习惯是在项目里同时保留两份实现逐位的那份只用来跑测试向量查表的那份才上线。两者结果必须完全一致一旦不一致就说明表生成逻辑或者参数配错了。3. 查表法用 256 项换掉 8 次循环3.1 查表法成立的前提——异或的线性查表法能把 8 次迭代压成一次靠的是 CRC 对异或的线性性质。用数学语言说对任意两个多项式A和B(A ⊕ B)除以生成多项式G的余数等于A除以G的余数异或B除以G的余数。这条性质在模 2 运算下天然成立因为加法就是异或整个运算是线性的。套到代码里一个字节有 256 种取值每种取值对寄存器的影响是固定的。既然影响可以叠加那就可以提前把这 256 种影响全部算出来存成一张表。运行时只要算出当前寄存器的高 8 位异或上这个字节等于什么拿这个值去查表再异或回寄存器就完成了一个字节的处理。经典 CRC 表只有 256 项8 位表就是 256 字节16 位表是 512 字节32 位表是 1024 字节占用小得可以忽略。顺带说一个有意思的类比查表法计算温度。热电偶和热电阻的输出和温度之间关系是非线性的单片机上直接解多项式很费劲所以工程师会预先做好一张电压值到温度的分段表运行的时候查表加线性插值。CRC 查表法是完全一样的思路——把运行时要做的复杂计算提前挪到编译期或者启动阶段去做用存储换时间。这个思路在嵌入式里几乎无处不在理解了 CRC 的查表理解别的查表也会顺很多。3.2 表的生成把 256 个单字节消息各跑一遍直接法表的生成逻辑其实很直观对每一个可能的字节值i假设当前寄存器清零来一个字节 i按直接法完整跑 8 次迭代得到的结果就是table[i]。非反射版本是这样写的def make_table_msb(poly, width): 生成非反射MSB-first方式的 256 项表 mask (1 width) - 1 topbit 1 (width - 1) table [] for i in range(256): crc (i (width - 8)) mask # 把 i 放到高位 for _ in range(8): if crc topbit: crc ((crc 1) ^ poly) mask else: crc (crc 1) mask table.append(crc) return table注意这里的循环里没有crc ^ byte那一步因为i本身就是要处理的字节直接当成初始值放进去就行。反射版本更简洁def make_table_lsb(rpoly, width): 生成反射LSB-first方式的 256 项表 table [] for i in range(256): crc i for _ in range(8): if crc 1: crc (crc 1) ^ rpoly else: crc 1 table.append(crc) return table这里不需要掩码因为每次都是右移结果不会超出位宽。用 CRC-16/MODBUS 的参数rpoly 0xA001跑一遍表的前 8 项应该是0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241。这是个很好的自检点如果你的表头跟这个不一样说明反射多项式或者移位方向错了不用往下走先把这一步对齐。还有个容易踩的坑表是在编译期用 const 数组写死还是在运行时算一遍。两种做法都对但各有代价。写死数组的好处是启动零开销、可以放 Flash 不占 RAM坏处是不好维护改一次多项式就得重新生成整张表。运行时生成的好处是灵活坏处是要多占 256 到 1024 字节的 RAM还多了一段初始化时间。我一般是在 PC 端跑脚本生成 C 数组把打印结果粘进头文件两边都兼顾。3.3 一次查表的更新公式以及为什么它长得不一样有了表逐字节的处理就变成了两行def crc_table_lsb(data, table, width, init0, xorout0): 反射查表法 mask (1 width) - 1 crc init mask for byte in data: crc (crc 8) ^ table[(crc ^ byte) 0xFF] return (crc ^ xorout) mask def crc_table_msb(data, table, width, init0, xorout0): 非反射查表法 mask (1 width) - 1 shift width - 8 crc init mask for byte in data: crc ((crc 8) ^ table[((crc shift) ^ byte) 0xFF]) mask return (crc ^ xorout) mask反射版和 MSB 版看起来差得挺多但逻辑是对称的。反射版里crc ^ byte的低 8 位正是接下来 8 次迭代要处理的那部分查表取出来的是这部分的等效影响异或到右移 8 位之后的寄存器上。MSB 版里crc shift取的就是寄存器高 8 位异或上当前字节同样去查表。两者都只需要一次查表、一次移位、一次异或。这里有个特别常见的写法错误MSB 版里写成table[((crc ^ byte) shift) 0xFF]。这样写在高位宽比如 32 位时可能侥幸对得上结果因为它取的是不同位置的位查出来的表项完全是另一个值于是结果随机错误。判断方法很简单——拿一个 CRC-32 的标准测试向量跑一遍如果不对先检查索引表达式里是crc shift还是crc 0xFF。C 语言版本以 CRC-16/MODBUS 为例#include stdint.h #include stddef.h static const uint16_t crc16_modbus_table[256] { 0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241, /* ... 其余 248 项由脚本生成 ... */ }; uint16_t crc16_modbus(const uint8_t *data, size_t len) { uint16_t crc 0xFFFF; /* init */ for (size_t i 0; i len; i) { crc (uint16_t)((crc 8) ^ crc16_modbus_table[(crc ^ data[i]) 0xFF]); } return crc; /* xorout 0直接返回 */ }这段代码在 Cortex-M0 上处理 1 MB 数据大概几毫秒级比逐位实现快将近一个数量级而表只占 512 字节 Flash。绝大多数嵌入式项目用这个方案就足够了。3.4 半字节表与双字节表内存和速度之间的滑杆256 项并不是唯一选择它只是最常用的一个平衡点。按同样的思路可以做出一整个家族4 位半字节表16 项一次处理半个字节速度比逐位快约 2 倍表只有 16 项32 位 CRC 也才 64 字节非常适合 RAM 极其紧张的 MCU比如一些 8 位单片机8 位字节表256 项一次处理一个字节是最主流的选择双字节表65536 项一次处理两个字节速度再快一档但 32 位 CRC 的表要占 256 KB基本只能放 PC 端切片法slice-by-N不是简单的 N 字节表而是用 N 张 256 项的表并行处理 N 个字节下一小节细说。选哪个不是拍脑袋决定的得看两个约束Flash/RAM 预算以及目标吞吐量。如果每秒只需要校验几百字节的串口数据逐位实现都够用没必要为了看起来专业塞一张表进去如果是几 MB/s 的存储校验字节表是起步不够就上切片法如果单片机的 Flash 比 CPU 还金贵半字节表反而是最理性的选择。我在一个 8 位单片机的项目里就干过这事整个固件只有 8 KB塞一张 512 字节的表要占 6% 的 Flash最后用 16 项的半字节表砍到 32 字节速度仍然比逐位快两倍多完全满足需求。选型的时候先量一下预算和需求再决定表的粒度别默认 256 项就是唯一答案。4. 结果对不上时先查参数模型再查代码4.1 六个开关一个都不能错前面提过的六个参数实际调试的时候要逐个确认。我习惯按这个顺序排查width 和 poly 对不对。这两个通常由协议规定先去翻规范文档别靠猜。比如 CRC-16 常见的有两种多项式0x8005IBM/Modbus 系和0x1021CCITT 系用错了结果没有任何相似性。poly 是原始形式还是反射形式。反射算法要吃反射后的多项式0x8005得换成0xA001。init 是多少。0x0000、0xFFFF、0xFFFFFFFF是最常见的三种。有些国产芯片的 CRC 外设默认是0xFFFFFFFF改都改不了。refin / refout 是不是都开了。这两个绝大多数情况下是同时开或同时关但也有个别算法只反射输入不反射输出遇到这种就得小心。xorout 需不需要。以太网和 zlib 的 CRC-32 都要异或0xFFFFFFFF而 Modbus 不需要。数据范围。CRC 算的是哪一段字节包不包含头部、长度字段、结束符这是实际项目里最高频的错误来源比参数配错还常见。第 6 条值得多说两句。Modbus RTU 的 CRC 只算功能码和数据不算地址后的...等等实际上它算的是从站地址到数据末尾的全部内容不含 CRC 自身。I2C 的 SMBus PEC 只算地址之后的字节。以太网 FCS 算的是从目的 MAC 到载荷结尾而且不算前导码和 FCS 本身。这些算哪一段的细节文档里往往一句话带过但对结果的影响是决定性的。4.2 常用 CRC 参数与 check 值对照表业界有个约定俗成的做法用 ASCII 字符串1234567899 个字节0x31到0x39作为标准测试输入算出来的 CRC 值叫check 值。只要你的实现在这个输入上算出的值和标准表一致参数模型就基本没问题了。下面这张表是我调试时最常翻的名称widthpolyinitrefinrefoutxoroutcheckCRC-880x070x00falsefalse0x000xF4CRC-8/MAXIM-DOW80x310x00truetrue0x000xA1CRC-16/ARC (IBM)160x80050x0000truetrue0x00000xBB3DCRC-16/MODBUS160x80050xFFFFtruetrue0x00000x4B37CRC-16/CCITT-FALSE160x10210xFFFFfalsefalse0x00000x29B1CRC-16/XMODEM160x10210x0000falsefalse0x00000x31C3CRC-32 (Ethernet/zlib)320x04C11DB70xFFFFFFFFtruetrue0xFFFFFFFF0xCBF43926CRC-32/MPEG-2320x04C11DB70xFFFFFFFFfalsefalse0x000000000x0376E6E7CRC-32C (Castagnoli)320x1EDC6F410xFFFFFFFFtruetrue0xFFFFFFFF0xE3069283注意 CRC-32 和 CRC-32/MPEG-2 这两行——多项式完全一样初始值也一样只差在反不反射和最终异或不异或。而这两个算法的 check 值0xCBF43926和0x0376E6E7毫无关系。这就是我强调先查参数再查代码的原因参数错了你再怎么盯着代码看也找不到 bug因为代码可能是对的。反射多项式的对应关系也整理一下省得每次手推原始多项式位宽反射后0x0780xE00x3180x8C0x8005160xA0010x1021160x84080x04C11DB7320xEDB883200x1EDC6F41320x82F63B784.3 反射多项式不是多项式取反这一点值得单独拿出来说因为它坑过太多人。反射reflect和取反invert是两回事取反是把每一位翻转0x8005变成0x7FFA反射是把整个比特序列首尾颠倒0x80051000 0000 0000 0101变成0xA0011010 0000 0000 0001。两个操作看起来只差一点点但结果完全不同。更麻烦的是光看 16 进制的值根本看不出来你写的是反射还是取反只能二进制展开一位一位数。我的做法是在代码注释里直接把反射前后的二进制写出来比如/* CRC-16/MODBUS: poly 0x8005 (1000 0000 0000 0101) * rpoly 0xA001 (1010 0000 0000 0001) */这样下次自己或者同事回头改代码一眼就能核对不用再推一遍。另一个相关的坑是位宽的截断。反射一个 16 位多项式时0x8005的最高位第 15 位实际上是生成多项式的x¹⁶项在计算中默认存在但不参与异或一旦反射的时候没有正确对齐到 16 位0xA001可能被算成别的值。所以用脚本按位宽做反射最保险def reflect(value, width): 把 width 位宽的整数按位反射 result 0 for _ in range(width): result (result 1) | (value 1) value 1 return result print(hex(reflect(0x8005, 16))) # 0xa001 print(hex(reflect(0x04C11DB7, 32))) # 0xedb883204.4 用 check 值把问题分层定位在实际排查中我一般用三层测试来切分问题第一层单字节测试。用一个字节0x31跑逐位实现和手推结果比。CRC-8 的例子我们前面推过结果是0x97。如果你手推的和代码跑的不一致那就是逐位实现本身有问题——多半是移位方向、判断位、掩码这三处之一。第二层check 值测试。用123456789跑查表法和 4.2 节的表比。如果逐位实现通过、查表法没通过问题一定在表的生成或者索引表达式上因为两条路走的是同一个数学定义。这时候把表的前 8 项打印出来对一下基本就能定位。第三层真实报文测试。拿一段真实的协议报文和协议规范里给的示例比对。这一层主要抓的是数据范围搞错了这类问题——比如多算了或者少算了一个字节。这三层按顺序走下来绝大多数问题在 10 分钟内能定位。最怕的是跳过前两层直接拿真实报文对着调那样参数问题和实现问题纠缠在一起改一处不知道对不对很容易越改越乱。4.5 在线计算器结果不一样多半是选项选错了网上那些 crc 校验计算器在线工具挺好用但用的时候一定要把参数选全。我见过好几次计算器和代码结果不一致的争论最后发现是计算器默认选了 CRC-16/CCITT-FALSE而代码里用的是 CRC-16/XMODEM——两者的区别只是初始值0xFFFF和0x0000但结果差了十万八千里。用在线工具的正确姿势是先把你的协议里规定的六个参数填进去再输入123456789看看工具输出的 check 值和标准表是否一致。如果工具给你的结果和标准表对不上那说明你在工具里填的参数有问题这时候再拿工具去算真实数据结果当然也是错的。工具本身很少出错错的是输入。另外提醒一句有些在线工具默认会做文本模式/HEX 模式的转换。输入123456789时文本模式处理的是 9 个 ASCII 字节HEX 模式可能把它当成 9 个字节0x12 0x34 ...——完全不同。这个坑在算通信报文的时候特别容易踩报文是十六进制串结果被当成 ASCII 文本处理了一遍。5. 把 CRC 从能算做到够快5.1 三种实现的量级差异把参数模型确认清楚之后剩下的就是性能问题。三种实现的差异大概是这样逐位实现每字节 8 次迭代查表实现每字节 1 次查表加 2 次位运算切片法每字节的位运算次数进一步摊薄到 1/4 或 1/8。在同样数据量下查表法相对逐位法通常有 5 到 10 倍的提升切片法再快 1.5 到 3 倍而硬件加速跟软件完全不在一个量级。具体数字跟平台强相关我这边不做绝对承诺但有一个判断是稳的只要数据量超过几十 KB、或者处于高速数据通道上逐位实现就一定不该出现在主路径上。你在 PC 上跑几 KB 可能感觉不到但在 100 MHz 的单片机上处理一帧几 KB 的固件升级包逐位实现能明显拖慢整包校验的时间。5.2 切片法一次咀嚼 4 个字节切片法slice-by-N的思路跟双字节大表不一样。它不是把表扩大到 65536 项而是用 N 张 256 项的表来并行处理 N 个字节。做法的关键点在于CRC 是线性的处理 4 个字节可以拆成 4 个独立贡献的异或叠加。以反射版 CRC-32 的 slice-by-4 为例先用标准表推导出三张派生的表def build_slice_tables(table): 由标准 256 项表推导 slice-by-4 需要的 4 张表 tables [table] for _ in range(1, 4): prev tables[-1] cur [0] * 256 for i in range(256): cur[i] (prev[i] 8) ^ table[prev[i] 0xFF] tables.append(cur) return tables # tables[0] 是标准表tables[3] 是提前 3 个字节的贡献推导逻辑是tables[k][i]表示如果某个表项的影响再往后传播 k 个字节它会变成什么。有了这四张表处理时一次取 4 个字节拼成一个 32 位字异或进当前 CRC然后一次性完成。def crc_slice4(data, tables, init0xFFFFFFFF, xorout0xFFFFFFFF): crc init n len(data) ~3 for i in range(0, n, 4): word int.from_bytes(data[i:i4], little) # 反射算法按小端拼字 crc ^ word crc (tables[3][crc 0xFF] ^ tables[2][(crc 8) 0xFF] ^ tables[1][(crc 16) 0xFF] ^ tables[0][(crc 24) 0xFF]) for i in range(n, len(data)): crc (crc 8) ^ tables[0][(crc ^ data[i]) 0xFF] return crc ^ xorout这里有两个容易出错的点。第一拼字要用小端——反射算法是低位优先的第 0 个字节应该落在最低 8 位。用大端拼字结果会全错而且错得非常随机。第二尾部不足 4 字节的部分必须用标准表逐字节补完而且要在主循环之后调用tables[0]不能用别的表。slice-by-8 的思路完全一样只是表从 4 张变成 8 张一次处理 8 字节。代价是表从 1 KB 涨到 8 KB对 Flash 紧张的设备来说未必划算。5.3 硬件 CRC指令和外设的正确打开方式如果你的平台支持硬件 CRC那基本没有理由不用。几条常见路线x86 的 SSE4.2 指令集_mm_crc32_u8、_mm_crc32_u32、_mm_crc32_u64这几条内建函数硬件直接算一条指令处理 8 个字节速度是软件的上百倍量级。前提是你得用支持它的编译选项并且代码里做运行时的 CPU 特性探测。ARMv8 的 CRC 扩展__crc32b、__crc32h、__crc32w、__crc32d这组内建函数Cortex-A 系列上基本都有用法和 x86 那套类似。MCU 自带的 CRC 外设很多 Cortex-M 芯片集成一个 CRC 单元喂数据进去读结果完全不占 CPU。FPGACRC 就是几个异或门加触发器一个时钟一个字节甚至更多做通信协议的时候顺手就集成了。但硬件 CRC 有个绕不开的坑见下一节。5.4 硬件 CRC32C 和软件 CRC-32 不兼容这个坑这是我最想强调的一条。x86 的_mm_crc32_*系列和 ARM 的__crc32*系列算的都是CRC-32CCastagnoli多项式是0x1EDC6F41不是以太网和 zlib 用的那个0x04C11DB7。两者的 check 值分别是0xE3069283和0xCBF43926完全不一样。这意味着你如果拿硬件指令去替换原来的软件 CRC-32结果会和协议要求的不匹配接收方会认为所有数据都坏了。这不是 bug是用错了算法。解决办法只有两个——要么协议本身允许用 CRC-32C要么老老实实回到软件查表加上切片法。MCU 自带的 CRC 外设也有类似问题而且更隐蔽不少型号的多项式是固化在硬件里的寄存器只能改初始值和数据格式不能改多项式。有些外设还要求以 32 位字为单位喂数据字节流得先拼成字这时候字节序又成了一道坎。我的建议是用硬件 CRC 之前先拿123456789跑一遍看看它算出来的 check 值是什么。如果和你需要的算法对上直接用对不上看看寄存器能不能配都配不了就老老实实走软件。6. 千兆链路报一堆硬件 CRC 错误别急着改 CRC 代码6.1 物理层 CRC 和协议层 CRC 是两码事回到开头那个场景。朋友看到日志里刷屏的 hardware CRC error第一反应是去翻自己写的那段 CRC-32 校验代码怀疑是不是算法写错了。这是个典型的误判——网口报的 CRC 错误跟你代码里的 CRC 函数基本没关系。以太网的帧尾有一个 4 字节的 FCS 字段用的是标准的 CRC-32参数和 zlib 完全一致。发送方算好 FCS 附在帧尾接收方的 PHY/MAC 硬件在收帧时实时计算对不上就把这个帧丢掉同时把统计计数器加一。所以hardware CRC error这个计数器的含义是链路上收到的帧帧尾的 FCS 校验没通过。它反映的是物理层的信号质量问题不是你软件里 CRC 实现的问题。这一点分清楚之后排查方向就完全不一样了不需要去看那段 CRC 函数而是要去看信号为什么在传输过程中被破坏了。6.2 百兆正常、千兆异常的典型排查顺序百兆能跑、千兆报错这个现象本身就很有信息量。100BASE-TX 只用两对线一对发一对收而 1000BASE-T 要四对线全部用上、同时双向收发每一对线 250 Mbps还要做回声消除和串扰消除。这对线缆的带宽、阻抗一致性、回波损耗、连接器质量、时钟抖动的要求都高了一个台阶。所以百兆能过、千兆过不了的常见原因大多集中在物理层而不是逻辑层。我一般按这个顺序往下查先看错误计数的分布。是所有端口都在涨还是特定端口是持续线性增长还是偶发几次是重负载下才有还是链路空闲时也涨如果是空闲时也涨那基本可以排除负载相关的因素往时钟、供电、配置方向想。换线。这一步最简单也最有效。注意网线的类别千兆至少要 Cat5e用只接了 4 芯的老线或者分线插座百兆能通、千兆必然出问题甚至协商不上。水晶头压接不良也会导致某几对线的插损偏大。换端口和对端设备。排除是本地 PHY 的问题还是对端的问题也是对调一下就能知道的事。看 PHY 的链路状态寄存器。很多 PHY 会给出均衡器的收敛状态、信噪比估计、符号错误计数、伪载波计数这些信息。如果 symbol error 也在涨基本坐实是信号质量问题如果只有 CRC 错误涨符号错误不涨那可能是更上游的问题。查参考时钟。千兆对 PHY 的参考时钟频偏和抖动比百兆敏感得多。晶振本身没问题不代表时钟走线没问题——走线长了、被别的信号串扰了抖动就可能超标。我遇到过一例是时钟走线旁边走了一根高摆率的开关信号串过去之后千兆必挂、百兆无事。查供电和 PCB。PHY 的模拟电源纹波、去耦电容的位置、差分对的等长和阻抗控制这些在百兆下余量够、在千兆下就不够了。如果是自研板子用示波器或者网络分析仪看一下眼图是最直接的。6.3 实测中容易被忽略的几个点分享几条我在实际项目里踩过的经验都是文档上不太会写的。第一条统计计数器要分清读的是哪一层。PHY 芯片内部有自己的一套统计寄存器MAC 里也有一套有些交换芯片还有第三套。三套的计数口径不完全一样比如 PHY 报的是接收时 FCS 校验失败的帧数MAC 报的可能是被丢弃的帧数两者会有出入。排查的时候一定要确认自己读的是哪个寄存器、定义是什么不然容易得出错误结论。第二条CRC 错误计数和流量强度对比着看。如果错误数随流量近似线性增长通常说明这是一个概率性的信号问题比如信噪比刚好卡在门限附近如果错误数是突发的一簇一簇的更可能是外部干扰或者接触不良。这两种模式的排查方向完全不同前者要调硬件参数后者要查连接器和环境。第三条别忽略线序。千兆以太网要求四对线全部按标准线序连接。如果线序错了百兆能自动协商成功因为它只需要两对千兆要么协商不上要么勉强协商上但错误率极高。这个问题在手工做的线缆上特别常见。第四条重启就好了往往不是玄学。有些千兆链路错误是均衡器收敛失败导致的重新协商一次可能就收敛到正确的抽头上了。这种重启就好、过段时间又坏的模式基本可以判定是信号余量不足不是软件问题。第五条硬件 CRC 外设和链路 CRC 错误完全是两码事。有些芯片会把链路收帧 CRC 错误和内部数据通路的 CRC 校验失败都归到类似的计数器名字下读寄存器之前一定要翻手册看清楚定义。我就因为看错了寄存器的位定义白查了两天。7. 几个我觉得值得记下来的经验写到这里把前面散落的一些判断收一收都是这几年实际动手踩出来的。关于实现选择我的默认策略是先用逐位实现把参数模型跑通再用脚本生成查表最后根据吞吐需求决定是否上切片法或者硬件。这个顺序不要颠倒因为逐位实现是最容易对照数学定义检查的一旦它和 check 值对上了后面所有优化都是在它的基础上等价变换出问题的概率小得多。关于调试check 值123456789是第一顺位的工具。任何一次 CRC 对不上先别去翻代码先把这个测试跑一遍。跑通了说明参数模型没问题问题在数据范围或者调用方式上跑不通说明参数模型就错了那就去 4.2 节的表里对参数一个一个核。关于动手表一定要自己写脚本生成一遍。哪怕最后是从网上抄的代码也要自己生成一次表和你抄的代码里那张表逐项比对。这一步花不了五分钟但能省掉后面好几小时的怀疑人生。我在一个项目里就靠这个发现抄来的表里有一项被打错了一位——肉眼绝对看不出来跑起来就是偶发失败。关于查表法算温度那类场景思路是通用的凡是运行时计算复杂、输入取值有限的地方都可以考虑预计算。CRC 是 256 项温度标定表可能就是几十段线性段本质上是同一件事。最后一个建议如果你正在调一条千兆链路的 CRC 错误先把我的 CRC 代码写错了这个念头放一边。链路层的 CRC 是硬件干的你写的代码在它的上游或者下游两者基本不会互相影响。把示波器、网线和水晶头找出来比盯着代码看有用得多。
上周同事解压一份安装包跑到一半屏幕跳出gzig:stdin: invalid compressed data --crc error他的第一反应是文件没下全重下三遍报错一次不差。同一天下午另一位朋友的千兆板子在百兆链路下跑得稳稳当当一切到千兆PHY 的接收统计里 hardware CRC error 计数器就开始往上窜。两个场景看起来八竿子打不着——一个是压缩包一个是网口——但卡在同一个东西上CRC循环冗余校验。CRC 大概是嵌入式、网络、存储、文件格式这些领域里最人尽皆知但没几个人真懂的算法。说它人尽皆知是因为几乎每个协议里都有它Modbus、CAN、以太网 FCS、PNG、gzip、Flash 里的 ECC 校验区随手一抓一大把说没几个人真懂是因为大部分人只做过两件事从网上复制一段查表法代码或者打开一个 crc 校验计算器在线页面输入数据、选个模式、对一下结果。至于那段表是怎么来的、为什么有时候差 1 个字节就全错、为什么同样的数据两个工具算出来不一样基本靠猜。这篇东西想把直接计算法和查表法这两条路从头到尾摊开讲清楚多项式除法在二进制世界里到底怎么走、逐位实现为什么长成那样、256 项的查表是怎么从直接法里榨出来的、参数模型那六个开关各自管什么、以及在真实项目里怎么用 check 值把问题一层层剥开。适合刚接触协议栈的同学也适合写了几年代码但从没自己生成过 CRC 表的老手——表里的数字对不上的那种抓狂大家应该都体会过。1. CRC 不是加密也不是求和先把它的数学模型摆正1.1 从一条 gzip 报错说起回到开头那个--crc error。gzip 的格式很简单头部若干字节中间是压缩数据最后 8 个字节是尾部——其中 4 字节是原始数据的 CRC-32 值另外 4 字节是原始数据的长度。解压的时候解压器会把还原出来的每一个字节喂给一个 CRC-32 计算器等全部数据吐完把算出来的值和尾部记录的值比一下对不上就报 crc error。这个设计有个很关键的性质它不是在检查压缩数据有没有坏而是在检查解压结果对不对。也就是说如果压缩数据本身在传输中翻了几位解压出来的字节流大概率完全变样CRC 直接不匹配但还有一种更阴的情况——某段数据被改坏了解压器仍然能正常吐出字节只是内容错了这时候 CRC 就是最后一道防线。所以看到 crc error第一反应不该是下载没下全而是原始文件或者传输链路出了问题需要从源文件和传输两端去查。顺带说一句gzip 用的 CRC-32 和以太网帧尾 FCS 用的 CRC-32参数是完全一样的多项式0x04C11DB7初始值0xFFFFFFFF输入输出都按位反射最后再异或0xFFFFFFFF。同一个算法在两个完全不同的领域用了三十多年这也从侧面说明它有多耐用。1.2 模 2 除法没有进位的除法CRC 的本质是把一串二进制位看成一个多项式的系数。比如数据1101就对应多项式x³ x² 1——最左边那位是最高次项。这个映射不神秘只是把比特和多项式系数对应起来方便用代数工具分析。接下来是核心动作模 2 除法。普通除法里 112 会进位模 2 除法里加法就是异或110没有进位也没有借位除法的每一步就是如果当前余数的最高位是 1就异或一下除数然后左移一位。举个例子取一个 4 位的生成多项式10011也就是x⁴ x 1数据用1101。先给数据后面补 4 个 0补几个 0 由多项式宽度决定4 位就补 4 个得到被除数11010000然后拿10011去做模 2 除法11010的最高位是 1异或10011得01001去掉前导 0 变成1001拉下一位0得到10010最高位是 1异或10011得00001拉下一位0得到00010最高位是 1继续约简最终剩下0100。所以这个 4 位 CRC 的余数是0100也就是0x4。这个结果我用后面要讲的逐位代码又验算了一遍一模一样。整个过程没有乘除只有移位和异或——这就是为什么 CRC 在硬件里只需要几个触发器加几个异或门就能实现成本低到几乎可以忽略。有个更省事的等价算法叫寄存器法维护一个宽度等于多项式位宽的寄存器初始值设为init每来一个数据位先把寄存器左移一位、把新位塞到最低位然后看移出去的那一位是不是 1是 1 就异或多项式。这个写法和长除法看起来不一样但结果完全等价而且更适合写成代码。后面讲直接计算法时我用的就是这个形式。1.3 CRC 的能力边界为什么它能抓住突发错误很多人以为 CRC 就是个加强版校验和其实两者的数学结构差得挺远。简单的累加和两个字节一个加 1 一个减 1 就抵消了CRC 是多项式除法取余任何一位翻转都会让余数产生一个几乎不可能被另一处翻转抵消掉的偏移。从理论上讲一个宽度为 n 的 CRC 能保证检出所有长度不超过 n 的单比特错误、所有长度不超过 n 的双比特错误以及所有奇数个错误前提是生成多项式里含有x1这个因子。对于更长的突发错误检出的概率大约是1 - 2^(-n)。16 位 CRC 漏检率约 1/6553632 位约 1/43 亿这就是为什么以太网选择 32 位——两千字节的帧43 亿分之一的漏检概率基本可以当零看。但必须强调一句CRC 是查错用的不是防篡改用。它没有密钥攻击者想改数据顺便改 CRC成本比改数据本身高不了多少。凡是需要防篡改的场景得用哈希或消息认证码别拿 CRC 顶上。我在项目里见过有人用 CRC 当数据完整性签名这是纯粹的概念误用。1.4 六个参数CRC 其实是一族算法初学者最容易掉的坑是以为CRC只有一个算法。实际上它是一族算法由六个参数共同定义width位宽8、16、32、64 都常见poly生成多项式比如0x1021、0x04C11DB7init寄存器的初始值全 0、全 F 都有refin输入数据按位反射即字节内的比特顺序反过来还是按原序refout输出结果要不要反射xorout最终结果要不要再异或一个常量。这六个参数只要有任何一个不同同一个数据算出来的结果就完全不同而且这种不同不是差一点点是彻底没关系。后面第 4 节我会专门讲怎么用这六个参数把结果对不上的问题定位到具体哪个环节。这里先记住一句话报 CRC 不匹配的时候第一个要确认的不是数据对不对而是两边用的是不是同一个参数模型。2. 直接计算法把每一位的移位异或写在明面上2.1 手推一个字节0x31 在 CRC-8 下的 8 次迭代理论讲完我们拿最小可用的例子走一遍。选 CRC-8多项式0x07也就是x⁸ x² x 1初始值 0不反射。这种配置在 SMBus 之类的地方很常见。以字节0x31字符1为例直接计算法的过程是把当前寄存器值和这个字节异或然后重复 8 次看最高位、左移、按需异或多项式。迭代进入时的值最高位移一位后异或多项式后起始0x31 ^ 0x00 0x31---10x31 (0011 0001)00x620x6220x62 (0110 0010)00xC40xC430xC4 (1100 0100)10x880x8F40x8F (1000 1111)10x1E0x1950x19 (0001 1001)00x320x3260x32 (0011 0010)00x640x6470x64 (0110 0100)00xC80xC880xC8 (1100 1000)10x900x97最终结果是0x97。这个推导过程建议你自己拿纸笔再走一遍尤其是第 3 步和第 4 步——那两步最高位是 1所以先左移再异或顺序不能反。很多人在纸上推的时候会写成先异或再左移结果必然对不上。2.2 MSB-first 逐位实现的代码长什么样把上面的手工过程翻译成代码就是所谓的逐位直接计算法。Python 版本适合验证和理解C 版本适合上机def crc_bitwise_msb(data, poly, width, init0, xorout0): 非反射MSB-first逐位 CRC data: bytes poly: 生成多项式未反射形式例如 CRC-8 的 0x07、CRC-16/CCITT 的 0x1021 width: 位宽例如 8 / 16 / 32 mask (1 width) - 1 topbit 1 (width - 1) crc init mask for byte in data: # 把字节对齐到寄存器的高 8 位后异或 crc ^ (byte (width - 8)) mask for _ in range(8): if crc topbit: crc ((crc 1) ^ poly) mask else: crc (crc 1) mask return (crc ^ xorout) mask注意crc ^ (byte (width - 8)) mask这一行。8 位 CRC 时移位量是 0等价于直接异或16 位时左移 8 位也就是把字节放到寄存器的高半部分。为什么要放高位因为下面 8 次迭代是从最高位开始约简的数据必须和当前余数的最高位对齐否则异或在错误的位上结果就废了。还有一个细节data里的字节是按什么顺序喂进去的。协议里通常是先发第一个字节那代码里就先处理第一个字节不要自作聪明地倒过来。我见过有人在 SPI Flash 的 CRC 校验里把数据段倒序传入查了两天才发现是调用方的问题。2.3 反射版本LSB-first 和那个反着写的多项式上面那套是高位优先。但现实中大量协议用的是低位优先——Modbus RTU、很多串口协议、以太网的 FCS都是先处理字节的最低位。这个模式叫反射reflected实现上跟 MSB-first 有个镜像关系def crc_bitwise_lsb(data, rpoly, width, init0, xorout0): 反射LSB-first逐位 CRC rpoly: 反射后的生成多项式例如 CRC-16/MODBUS 的 0xA001、CRC-32 的 0xEDB88320 mask (1 width) - 1 crc init mask for byte in data: crc ^ byte # 异或在最低 8 位 for _ in range(8): if crc 1: # 看最低位不是最高位 crc (crc 1) ^ rpoly else: crc 1 return (crc ^ xorout) mask对比一下两版代码的区别一个是一个是一个看最高位一个看最低位一个把字节挪到高 8 位再异或一个直接异或在低 8 位。这不是随便写的而是把整个多项式除法镜像过来的结果——最高位变最低位左移变右移多项式也相应地按位反过来。关于rpoly这里先给个数感CRC-32 的多项式是0x04C11DB7反射以后是0xEDB88320也就是 zlib、PNG 里到处能看到的那个魔数。CRC-16/MODBUS 用0x8005反射后是0xA001。这两个数在反射算法里不是另一种多项式而是同一个多项式的镜像表示后面 4.3 节会专门澄清这个误解的低级错误版本。2.4 直接法到底慢在哪直接法的可读性非常好几乎是把数学定义直译成代码适合做参考实现。但它的性能确实不客气每处理一个字节内层循环要跑 8 次每次都有一次移位、一次按位与、一次条件判断和可能的异或。算笔账处理 1 MB 数据外层 100 万次内层 800 万次。每次迭代哪怕只花 3 个时钟周期也是 2400 万个周期跑在 100 MHz 的 MCU 上就是 0.24 秒。如果这段代码在中断里、或者数据量变成 100 MB那就完全不可接受。更麻烦的是分支预测——if的结果取决于数据本身随机数据的命中率大概一半一半现代流水线最讨厌这种情况。所以直接计算法的定位应该很明确用来理解、用来生成查表、用来做单元测试的对照组但不要放进量产代码的主路径。我个人的习惯是在项目里同时保留两份实现逐位的那份只用来跑测试向量查表的那份才上线。两者结果必须完全一致一旦不一致就说明表生成逻辑或者参数配错了。3. 查表法用 256 项换掉 8 次循环3.1 查表法成立的前提——异或的线性查表法能把 8 次迭代压成一次靠的是 CRC 对异或的线性性质。用数学语言说对任意两个多项式A和B(A ⊕ B)除以生成多项式G的余数等于A除以G的余数异或B除以G的余数。这条性质在模 2 运算下天然成立因为加法就是异或整个运算是线性的。套到代码里一个字节有 256 种取值每种取值对寄存器的影响是固定的。既然影响可以叠加那就可以提前把这 256 种影响全部算出来存成一张表。运行时只要算出当前寄存器的高 8 位异或上这个字节等于什么拿这个值去查表再异或回寄存器就完成了一个字节的处理。经典 CRC 表只有 256 项8 位表就是 256 字节16 位表是 512 字节32 位表是 1024 字节占用小得可以忽略。顺带说一个有意思的类比查表法计算温度。热电偶和热电阻的输出和温度之间关系是非线性的单片机上直接解多项式很费劲所以工程师会预先做好一张电压值到温度的分段表运行的时候查表加线性插值。CRC 查表法是完全一样的思路——把运行时要做的复杂计算提前挪到编译期或者启动阶段去做用存储换时间。这个思路在嵌入式里几乎无处不在理解了 CRC 的查表理解别的查表也会顺很多。3.2 表的生成把 256 个单字节消息各跑一遍直接法表的生成逻辑其实很直观对每一个可能的字节值i假设当前寄存器清零来一个字节 i按直接法完整跑 8 次迭代得到的结果就是table[i]。非反射版本是这样写的def make_table_msb(poly, width): 生成非反射MSB-first方式的 256 项表 mask (1 width) - 1 topbit 1 (width - 1) table [] for i in range(256): crc (i (width - 8)) mask # 把 i 放到高位 for _ in range(8): if crc topbit: crc ((crc 1) ^ poly) mask else: crc (crc 1) mask table.append(crc) return table注意这里的循环里没有crc ^ byte那一步因为i本身就是要处理的字节直接当成初始值放进去就行。反射版本更简洁def make_table_lsb(rpoly, width): 生成反射LSB-first方式的 256 项表 table [] for i in range(256): crc i for _ in range(8): if crc 1: crc (crc 1) ^ rpoly else: crc 1 table.append(crc) return table这里不需要掩码因为每次都是右移结果不会超出位宽。用 CRC-16/MODBUS 的参数rpoly 0xA001跑一遍表的前 8 项应该是0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241。这是个很好的自检点如果你的表头跟这个不一样说明反射多项式或者移位方向错了不用往下走先把这一步对齐。还有个容易踩的坑表是在编译期用 const 数组写死还是在运行时算一遍。两种做法都对但各有代价。写死数组的好处是启动零开销、可以放 Flash 不占 RAM坏处是不好维护改一次多项式就得重新生成整张表。运行时生成的好处是灵活坏处是要多占 256 到 1024 字节的 RAM还多了一段初始化时间。我一般是在 PC 端跑脚本生成 C 数组把打印结果粘进头文件两边都兼顾。3.3 一次查表的更新公式以及为什么它长得不一样有了表逐字节的处理就变成了两行def crc_table_lsb(data, table, width, init0, xorout0): 反射查表法 mask (1 width) - 1 crc init mask for byte in data: crc (crc 8) ^ table[(crc ^ byte) 0xFF] return (crc ^ xorout) mask def crc_table_msb(data, table, width, init0, xorout0): 非反射查表法 mask (1 width) - 1 shift width - 8 crc init mask for byte in data: crc ((crc 8) ^ table[((crc shift) ^ byte) 0xFF]) mask return (crc ^ xorout) mask反射版和 MSB 版看起来差得挺多但逻辑是对称的。反射版里crc ^ byte的低 8 位正是接下来 8 次迭代要处理的那部分查表取出来的是这部分的等效影响异或到右移 8 位之后的寄存器上。MSB 版里crc shift取的就是寄存器高 8 位异或上当前字节同样去查表。两者都只需要一次查表、一次移位、一次异或。这里有个特别常见的写法错误MSB 版里写成table[((crc ^ byte) shift) 0xFF]。这样写在高位宽比如 32 位时可能侥幸对得上结果因为它取的是不同位置的位查出来的表项完全是另一个值于是结果随机错误。判断方法很简单——拿一个 CRC-32 的标准测试向量跑一遍如果不对先检查索引表达式里是crc shift还是crc 0xFF。C 语言版本以 CRC-16/MODBUS 为例#include stdint.h #include stddef.h static const uint16_t crc16_modbus_table[256] { 0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241, /* ... 其余 248 项由脚本生成 ... */ }; uint16_t crc16_modbus(const uint8_t *data, size_t len) { uint16_t crc 0xFFFF; /* init */ for (size_t i 0; i len; i) { crc (uint16_t)((crc 8) ^ crc16_modbus_table[(crc ^ data[i]) 0xFF]); } return crc; /* xorout 0直接返回 */ }这段代码在 Cortex-M0 上处理 1 MB 数据大概几毫秒级比逐位实现快将近一个数量级而表只占 512 字节 Flash。绝大多数嵌入式项目用这个方案就足够了。3.4 半字节表与双字节表内存和速度之间的滑杆256 项并不是唯一选择它只是最常用的一个平衡点。按同样的思路可以做出一整个家族4 位半字节表16 项一次处理半个字节速度比逐位快约 2 倍表只有 16 项32 位 CRC 也才 64 字节非常适合 RAM 极其紧张的 MCU比如一些 8 位单片机8 位字节表256 项一次处理一个字节是最主流的选择双字节表65536 项一次处理两个字节速度再快一档但 32 位 CRC 的表要占 256 KB基本只能放 PC 端切片法slice-by-N不是简单的 N 字节表而是用 N 张 256 项的表并行处理 N 个字节下一小节细说。选哪个不是拍脑袋决定的得看两个约束Flash/RAM 预算以及目标吞吐量。如果每秒只需要校验几百字节的串口数据逐位实现都够用没必要为了看起来专业塞一张表进去如果是几 MB/s 的存储校验字节表是起步不够就上切片法如果单片机的 Flash 比 CPU 还金贵半字节表反而是最理性的选择。我在一个 8 位单片机的项目里就干过这事整个固件只有 8 KB塞一张 512 字节的表要占 6% 的 Flash最后用 16 项的半字节表砍到 32 字节速度仍然比逐位快两倍多完全满足需求。选型的时候先量一下预算和需求再决定表的粒度别默认 256 项就是唯一答案。4. 结果对不上时先查参数模型再查代码4.1 六个开关一个都不能错前面提过的六个参数实际调试的时候要逐个确认。我习惯按这个顺序排查width 和 poly 对不对。这两个通常由协议规定先去翻规范文档别靠猜。比如 CRC-16 常见的有两种多项式0x8005IBM/Modbus 系和0x1021CCITT 系用错了结果没有任何相似性。poly 是原始形式还是反射形式。反射算法要吃反射后的多项式0x8005得换成0xA001。init 是多少。0x0000、0xFFFF、0xFFFFFFFF是最常见的三种。有些国产芯片的 CRC 外设默认是0xFFFFFFFF改都改不了。refin / refout 是不是都开了。这两个绝大多数情况下是同时开或同时关但也有个别算法只反射输入不反射输出遇到这种就得小心。xorout 需不需要。以太网和 zlib 的 CRC-32 都要异或0xFFFFFFFF而 Modbus 不需要。数据范围。CRC 算的是哪一段字节包不包含头部、长度字段、结束符这是实际项目里最高频的错误来源比参数配错还常见。第 6 条值得多说两句。Modbus RTU 的 CRC 只算功能码和数据不算地址后的...等等实际上它算的是从站地址到数据末尾的全部内容不含 CRC 自身。I2C 的 SMBus PEC 只算地址之后的字节。以太网 FCS 算的是从目的 MAC 到载荷结尾而且不算前导码和 FCS 本身。这些算哪一段的细节文档里往往一句话带过但对结果的影响是决定性的。4.2 常用 CRC 参数与 check 值对照表业界有个约定俗成的做法用 ASCII 字符串1234567899 个字节0x31到0x39作为标准测试输入算出来的 CRC 值叫check 值。只要你的实现在这个输入上算出的值和标准表一致参数模型就基本没问题了。下面这张表是我调试时最常翻的名称widthpolyinitrefinrefoutxoroutcheckCRC-880x070x00falsefalse0x000xF4CRC-8/MAXIM-DOW80x310x00truetrue0x000xA1CRC-16/ARC (IBM)160x80050x0000truetrue0x00000xBB3DCRC-16/MODBUS160x80050xFFFFtruetrue0x00000x4B37CRC-16/CCITT-FALSE160x10210xFFFFfalsefalse0x00000x29B1CRC-16/XMODEM160x10210x0000falsefalse0x00000x31C3CRC-32 (Ethernet/zlib)320x04C11DB70xFFFFFFFFtruetrue0xFFFFFFFF0xCBF43926CRC-32/MPEG-2320x04C11DB70xFFFFFFFFfalsefalse0x000000000x0376E6E7CRC-32C (Castagnoli)320x1EDC6F410xFFFFFFFFtruetrue0xFFFFFFFF0xE3069283注意 CRC-32 和 CRC-32/MPEG-2 这两行——多项式完全一样初始值也一样只差在反不反射和最终异或不异或。而这两个算法的 check 值0xCBF43926和0x0376E6E7毫无关系。这就是我强调先查参数再查代码的原因参数错了你再怎么盯着代码看也找不到 bug因为代码可能是对的。反射多项式的对应关系也整理一下省得每次手推原始多项式位宽反射后0x0780xE00x3180x8C0x8005160xA0010x1021160x84080x04C11DB7320xEDB883200x1EDC6F41320x82F63B784.3 反射多项式不是多项式取反这一点值得单独拿出来说因为它坑过太多人。反射reflect和取反invert是两回事取反是把每一位翻转0x8005变成0x7FFA反射是把整个比特序列首尾颠倒0x80051000 0000 0000 0101变成0xA0011010 0000 0000 0001。两个操作看起来只差一点点但结果完全不同。更麻烦的是光看 16 进制的值根本看不出来你写的是反射还是取反只能二进制展开一位一位数。我的做法是在代码注释里直接把反射前后的二进制写出来比如/* CRC-16/MODBUS: poly 0x8005 (1000 0000 0000 0101) * rpoly 0xA001 (1010 0000 0000 0001) */这样下次自己或者同事回头改代码一眼就能核对不用再推一遍。另一个相关的坑是位宽的截断。反射一个 16 位多项式时0x8005的最高位第 15 位实际上是生成多项式的x¹⁶项在计算中默认存在但不参与异或一旦反射的时候没有正确对齐到 16 位0xA001可能被算成别的值。所以用脚本按位宽做反射最保险def reflect(value, width): 把 width 位宽的整数按位反射 result 0 for _ in range(width): result (result 1) | (value 1) value 1 return result print(hex(reflect(0x8005, 16))) # 0xa001 print(hex(reflect(0x04C11DB7, 32))) # 0xedb883204.4 用 check 值把问题分层定位在实际排查中我一般用三层测试来切分问题第一层单字节测试。用一个字节0x31跑逐位实现和手推结果比。CRC-8 的例子我们前面推过结果是0x97。如果你手推的和代码跑的不一致那就是逐位实现本身有问题——多半是移位方向、判断位、掩码这三处之一。第二层check 值测试。用123456789跑查表法和 4.2 节的表比。如果逐位实现通过、查表法没通过问题一定在表的生成或者索引表达式上因为两条路走的是同一个数学定义。这时候把表的前 8 项打印出来对一下基本就能定位。第三层真实报文测试。拿一段真实的协议报文和协议规范里给的示例比对。这一层主要抓的是数据范围搞错了这类问题——比如多算了或者少算了一个字节。这三层按顺序走下来绝大多数问题在 10 分钟内能定位。最怕的是跳过前两层直接拿真实报文对着调那样参数问题和实现问题纠缠在一起改一处不知道对不对很容易越改越乱。4.5 在线计算器结果不一样多半是选项选错了网上那些 crc 校验计算器在线工具挺好用但用的时候一定要把参数选全。我见过好几次计算器和代码结果不一致的争论最后发现是计算器默认选了 CRC-16/CCITT-FALSE而代码里用的是 CRC-16/XMODEM——两者的区别只是初始值0xFFFF和0x0000但结果差了十万八千里。用在线工具的正确姿势是先把你的协议里规定的六个参数填进去再输入123456789看看工具输出的 check 值和标准表是否一致。如果工具给你的结果和标准表对不上那说明你在工具里填的参数有问题这时候再拿工具去算真实数据结果当然也是错的。工具本身很少出错错的是输入。另外提醒一句有些在线工具默认会做文本模式/HEX 模式的转换。输入123456789时文本模式处理的是 9 个 ASCII 字节HEX 模式可能把它当成 9 个字节0x12 0x34 ...——完全不同。这个坑在算通信报文的时候特别容易踩报文是十六进制串结果被当成 ASCII 文本处理了一遍。5. 把 CRC 从能算做到够快5.1 三种实现的量级差异把参数模型确认清楚之后剩下的就是性能问题。三种实现的差异大概是这样逐位实现每字节 8 次迭代查表实现每字节 1 次查表加 2 次位运算切片法每字节的位运算次数进一步摊薄到 1/4 或 1/8。在同样数据量下查表法相对逐位法通常有 5 到 10 倍的提升切片法再快 1.5 到 3 倍而硬件加速跟软件完全不在一个量级。具体数字跟平台强相关我这边不做绝对承诺但有一个判断是稳的只要数据量超过几十 KB、或者处于高速数据通道上逐位实现就一定不该出现在主路径上。你在 PC 上跑几 KB 可能感觉不到但在 100 MHz 的单片机上处理一帧几 KB 的固件升级包逐位实现能明显拖慢整包校验的时间。5.2 切片法一次咀嚼 4 个字节切片法slice-by-N的思路跟双字节大表不一样。它不是把表扩大到 65536 项而是用 N 张 256 项的表来并行处理 N 个字节。做法的关键点在于CRC 是线性的处理 4 个字节可以拆成 4 个独立贡献的异或叠加。以反射版 CRC-32 的 slice-by-4 为例先用标准表推导出三张派生的表def build_slice_tables(table): 由标准 256 项表推导 slice-by-4 需要的 4 张表 tables [table] for _ in range(1, 4): prev tables[-1] cur [0] * 256 for i in range(256): cur[i] (prev[i] 8) ^ table[prev[i] 0xFF] tables.append(cur) return tables # tables[0] 是标准表tables[3] 是提前 3 个字节的贡献推导逻辑是tables[k][i]表示如果某个表项的影响再往后传播 k 个字节它会变成什么。有了这四张表处理时一次取 4 个字节拼成一个 32 位字异或进当前 CRC然后一次性完成。def crc_slice4(data, tables, init0xFFFFFFFF, xorout0xFFFFFFFF): crc init n len(data) ~3 for i in range(0, n, 4): word int.from_bytes(data[i:i4], little) # 反射算法按小端拼字 crc ^ word crc (tables[3][crc 0xFF] ^ tables[2][(crc 8) 0xFF] ^ tables[1][(crc 16) 0xFF] ^ tables[0][(crc 24) 0xFF]) for i in range(n, len(data)): crc (crc 8) ^ tables[0][(crc ^ data[i]) 0xFF] return crc ^ xorout这里有两个容易出错的点。第一拼字要用小端——反射算法是低位优先的第 0 个字节应该落在最低 8 位。用大端拼字结果会全错而且错得非常随机。第二尾部不足 4 字节的部分必须用标准表逐字节补完而且要在主循环之后调用tables[0]不能用别的表。slice-by-8 的思路完全一样只是表从 4 张变成 8 张一次处理 8 字节。代价是表从 1 KB 涨到 8 KB对 Flash 紧张的设备来说未必划算。5.3 硬件 CRC指令和外设的正确打开方式如果你的平台支持硬件 CRC那基本没有理由不用。几条常见路线x86 的 SSE4.2 指令集_mm_crc32_u8、_mm_crc32_u32、_mm_crc32_u64这几条内建函数硬件直接算一条指令处理 8 个字节速度是软件的上百倍量级。前提是你得用支持它的编译选项并且代码里做运行时的 CPU 特性探测。ARMv8 的 CRC 扩展__crc32b、__crc32h、__crc32w、__crc32d这组内建函数Cortex-A 系列上基本都有用法和 x86 那套类似。MCU 自带的 CRC 外设很多 Cortex-M 芯片集成一个 CRC 单元喂数据进去读结果完全不占 CPU。FPGACRC 就是几个异或门加触发器一个时钟一个字节甚至更多做通信协议的时候顺手就集成了。但硬件 CRC 有个绕不开的坑见下一节。5.4 硬件 CRC32C 和软件 CRC-32 不兼容这个坑这是我最想强调的一条。x86 的_mm_crc32_*系列和 ARM 的__crc32*系列算的都是CRC-32CCastagnoli多项式是0x1EDC6F41不是以太网和 zlib 用的那个0x04C11DB7。两者的 check 值分别是0xE3069283和0xCBF43926完全不一样。这意味着你如果拿硬件指令去替换原来的软件 CRC-32结果会和协议要求的不匹配接收方会认为所有数据都坏了。这不是 bug是用错了算法。解决办法只有两个——要么协议本身允许用 CRC-32C要么老老实实回到软件查表加上切片法。MCU 自带的 CRC 外设也有类似问题而且更隐蔽不少型号的多项式是固化在硬件里的寄存器只能改初始值和数据格式不能改多项式。有些外设还要求以 32 位字为单位喂数据字节流得先拼成字这时候字节序又成了一道坎。我的建议是用硬件 CRC 之前先拿123456789跑一遍看看它算出来的 check 值是什么。如果和你需要的算法对上直接用对不上看看寄存器能不能配都配不了就老老实实走软件。6. 千兆链路报一堆硬件 CRC 错误别急着改 CRC 代码6.1 物理层 CRC 和协议层 CRC 是两码事回到开头那个场景。朋友看到日志里刷屏的 hardware CRC error第一反应是去翻自己写的那段 CRC-32 校验代码怀疑是不是算法写错了。这是个典型的误判——网口报的 CRC 错误跟你代码里的 CRC 函数基本没关系。以太网的帧尾有一个 4 字节的 FCS 字段用的是标准的 CRC-32参数和 zlib 完全一致。发送方算好 FCS 附在帧尾接收方的 PHY/MAC 硬件在收帧时实时计算对不上就把这个帧丢掉同时把统计计数器加一。所以hardware CRC error这个计数器的含义是链路上收到的帧帧尾的 FCS 校验没通过。它反映的是物理层的信号质量问题不是你软件里 CRC 实现的问题。这一点分清楚之后排查方向就完全不一样了不需要去看那段 CRC 函数而是要去看信号为什么在传输过程中被破坏了。6.2 百兆正常、千兆异常的典型排查顺序百兆能跑、千兆报错这个现象本身就很有信息量。100BASE-TX 只用两对线一对发一对收而 1000BASE-T 要四对线全部用上、同时双向收发每一对线 250 Mbps还要做回声消除和串扰消除。这对线缆的带宽、阻抗一致性、回波损耗、连接器质量、时钟抖动的要求都高了一个台阶。所以百兆能过、千兆过不了的常见原因大多集中在物理层而不是逻辑层。我一般按这个顺序往下查先看错误计数的分布。是所有端口都在涨还是特定端口是持续线性增长还是偶发几次是重负载下才有还是链路空闲时也涨如果是空闲时也涨那基本可以排除负载相关的因素往时钟、供电、配置方向想。换线。这一步最简单也最有效。注意网线的类别千兆至少要 Cat5e用只接了 4 芯的老线或者分线插座百兆能通、千兆必然出问题甚至协商不上。水晶头压接不良也会导致某几对线的插损偏大。换端口和对端设备。排除是本地 PHY 的问题还是对端的问题也是对调一下就能知道的事。看 PHY 的链路状态寄存器。很多 PHY 会给出均衡器的收敛状态、信噪比估计、符号错误计数、伪载波计数这些信息。如果 symbol error 也在涨基本坐实是信号质量问题如果只有 CRC 错误涨符号错误不涨那可能是更上游的问题。查参考时钟。千兆对 PHY 的参考时钟频偏和抖动比百兆敏感得多。晶振本身没问题不代表时钟走线没问题——走线长了、被别的信号串扰了抖动就可能超标。我遇到过一例是时钟走线旁边走了一根高摆率的开关信号串过去之后千兆必挂、百兆无事。查供电和 PCB。PHY 的模拟电源纹波、去耦电容的位置、差分对的等长和阻抗控制这些在百兆下余量够、在千兆下就不够了。如果是自研板子用示波器或者网络分析仪看一下眼图是最直接的。6.3 实测中容易被忽略的几个点分享几条我在实际项目里踩过的经验都是文档上不太会写的。第一条统计计数器要分清读的是哪一层。PHY 芯片内部有自己的一套统计寄存器MAC 里也有一套有些交换芯片还有第三套。三套的计数口径不完全一样比如 PHY 报的是接收时 FCS 校验失败的帧数MAC 报的可能是被丢弃的帧数两者会有出入。排查的时候一定要确认自己读的是哪个寄存器、定义是什么不然容易得出错误结论。第二条CRC 错误计数和流量强度对比着看。如果错误数随流量近似线性增长通常说明这是一个概率性的信号问题比如信噪比刚好卡在门限附近如果错误数是突发的一簇一簇的更可能是外部干扰或者接触不良。这两种模式的排查方向完全不同前者要调硬件参数后者要查连接器和环境。第三条别忽略线序。千兆以太网要求四对线全部按标准线序连接。如果线序错了百兆能自动协商成功因为它只需要两对千兆要么协商不上要么勉强协商上但错误率极高。这个问题在手工做的线缆上特别常见。第四条重启就好了往往不是玄学。有些千兆链路错误是均衡器收敛失败导致的重新协商一次可能就收敛到正确的抽头上了。这种重启就好、过段时间又坏的模式基本可以判定是信号余量不足不是软件问题。第五条硬件 CRC 外设和链路 CRC 错误完全是两码事。有些芯片会把链路收帧 CRC 错误和内部数据通路的 CRC 校验失败都归到类似的计数器名字下读寄存器之前一定要翻手册看清楚定义。我就因为看错了寄存器的位定义白查了两天。7. 几个我觉得值得记下来的经验写到这里把前面散落的一些判断收一收都是这几年实际动手踩出来的。关于实现选择我的默认策略是先用逐位实现把参数模型跑通再用脚本生成查表最后根据吞吐需求决定是否上切片法或者硬件。这个顺序不要颠倒因为逐位实现是最容易对照数学定义检查的一旦它和 check 值对上了后面所有优化都是在它的基础上等价变换出问题的概率小得多。关于调试check 值123456789是第一顺位的工具。任何一次 CRC 对不上先别去翻代码先把这个测试跑一遍。跑通了说明参数模型没问题问题在数据范围或者调用方式上跑不通说明参数模型就错了那就去 4.2 节的表里对参数一个一个核。关于动手表一定要自己写脚本生成一遍。哪怕最后是从网上抄的代码也要自己生成一次表和你抄的代码里那张表逐项比对。这一步花不了五分钟但能省掉后面好几小时的怀疑人生。我在一个项目里就靠这个发现抄来的表里有一项被打错了一位——肉眼绝对看不出来跑起来就是偶发失败。关于查表法算温度那类场景思路是通用的凡是运行时计算复杂、输入取值有限的地方都可以考虑预计算。CRC 是 256 项温度标定表可能就是几十段线性段本质上是同一件事。最后一个建议如果你正在调一条千兆链路的 CRC 错误先把我的 CRC 代码写错了这个念头放一边。链路层的 CRC 是硬件干的你写的代码在它的上游或者下游两者基本不会互相影响。把示波器、网线和水晶头找出来比盯着代码看有用得多。
