您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168939

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

CRC 校验查表法的内在原理

设 CRC 多项式为 C C C

先只说明两个字节的情况(最高有效位在左侧),大于两个字节(16 位数)的可以类推。注意下文中的所有加法都是无进位加法,也就是二进制中的异或。

表中数据为单字节(8 bit)的 CRC 余数。将被除数多项式每八位为一组,设为 B 1 x 8 + B 0 x 0 B_{1} x^8 + B_0x^0 B1x8+B0x0

其中 B 1 , B 0 B_{1}, B_0 B1,B0 x x x 进制的八位数。

已知 B 1 x 32   m o d   C = R 1 B_{1} x^{32} \bmod C= R_1 B1x32modC=R1 R 1 R_1 R1 为 32 位的余数。

( B 1 x 8 + B 0 x 0 ) x 32   m o d   C (B_{1} x^8 + B_{0}x^0)x^{32} \bmod C (B1x8+B0x0)x32modC 的值:

等价于 ( B 1 x 40 + B 0 x 32 )   m o d   C = ( R 1 x 8 + B 0 x 32 )   m o d   C (B_{1} x^{40} + B_{0} x^{32}) \bmod C = (R_1 x^8 + B_{0}x^{32}) \bmod C (B1x40+B0x32)modC=(R1x8+B0x32)modC

R 1 = γ 1 , 4 x 24 + γ 1 , 3 x 16 + γ 1 , 2 x 8 + γ 1 , 1 x 0 R_1 = \gamma_{1,4} x^{24} + \gamma_{1,3} x^{16} + \gamma_{1,2} x^{8} + \gamma_{1,1}x^0 R1=γ1,4x24+γ1,3x16+γ1,2x8+γ1,1x0,其中 γ 1 , i   ( i = 1 , 2 , 3 ) \gamma_{1,i}\ (i=1,2,3) γ1,i (i=1,2,3) 为 8 位数。

所以:
( B 1 x 40 + B 0 x 32 )   m o d   C = ( ( B 1 x 32   m o d   C ) x 8 + B 0 x 32 )   m o d   C = ( R 1 x 8 + B 0 x 32 )   m o d   C = ( γ 1 , 4 x 32 + γ 1 , 3 x 24 + γ 1 , 2 x 16 + γ 1 , 1 x 8 + B 0 x 32 )   m o d   C = ( ( γ 1 , 4 + B 0 ) x 32 + γ 1 , 3 x 24 + γ 1 , 2 x 16 + γ 1 , 1 x 8 )   m o d   C = ( ( γ 1 , 4 + B 0 ) x 32   m o d   C + γ 1 , 3 x 24 + γ 1 , 2 x 16 + γ 1 , 1 x 8 )   m o d   C \begin{aligned} &(B_1 x^{40} + B_0x^{32}) \bmod C \\ &= ((B_1 x^{32} \bmod C) x^8 + B_0x^{32})\bmod C \\ &= (R_1 x^8 + B_{0}x^{32}) \bmod C \\ &=(\gamma_{1,4} x^{32} + \gamma_{1,3} x^{24} + \gamma_{1,2} x^{16} + \gamma_{1,1} x^8 + B_{0} x^{32}) \bmod C \\ &= ((\gamma_{1,4} + B_{0}) x^{32} + \gamma_{1,3} x^{24} + \gamma_{1,2} x^{16} + \gamma_{1,1} x^8) \bmod C \\ &= ((\gamma_{1,4} + B_{0}) x^{32} \bmod C + \gamma_{1,3} x^{24} + \gamma_{1,2} x^{16} + \gamma_{1,1} x^8)\bmod C \end{aligned} (B1x40+B0x32)modC=((B1x32modC)x8+B0x32)modC=(R1x8+B0x32)modC=(γ1,4x32+γ1,3x24+γ1,2x16+γ1,1x8+B0x32)modC=((γ1,4+B0)x32+γ1,3x24+γ1,2x16+γ1,1x8)modC=((γ1,4+B0)x32modC+γ1,3x24+γ1,2x16+γ1,1x8)modC
注意到最后一个等式中的被除数已经是 32 位数了,所以可得:
( R 1 x 8 + B 0 x 32 )   m o d   C = ( ( γ 1 , 4 + B 0 ) x 32   m o d   C + γ 1 , 3 x 24 + γ 1 , 2 x 16 + γ 1 , 1 x 8 )   m o d   C = ( γ 1 , 4 + B 0 ) x 32   m o d   C + γ 1 , 3 x 24 + γ 1 , 2 x 16 + γ 1 , 1 x 8 \begin{aligned} &(R_1 x^8 + B_{0}x^{32}) \bmod C \\ &= ((\gamma_{1,4} + B_{0}) x^{32} \bmod C + \gamma_{1,3} x^{24} + \gamma_{1,2} x^{16} + \gamma_{1,1} x^8)\bmod C \\ &= (\gamma_{1,4} + B_{0}) x^{32} \bmod C + \gamma_{1,3} x^{24} + \gamma_{1,2} x^{16} + \gamma_{1,1} x^8 \end{aligned} (R1x8+B0x32)modC=((γ1,4+B0)x32modC+γ1,3x24+γ1,2x16+γ1,1x8)modC=(γ1,4+B0)x32modC+γ1,3x24+γ1,2x16+γ1,1x8
其中 ( γ 1 , 4 + B 0 ) x 32   m o d   C (\gamma_{1,4} + B_{0}) x^{32} \bmod C (γ1,4+B0)x32modC 可以通过查表获得。转换成代码:

rem = (rem leftshift 8) xor crc_table[bytes[i] xor leftmost 8 bits of rem]

现在处理大于 16 位数的情况:

设被除数为 B n − 1 x 8 ( n − 1 ) + ⋯ + B 1 x 8 + B 0 x 0 B_{n-1} x^{8(n-1)} + \cdots + B_1 x^8 + B_0 x^0 Bn1x8(n1)++B1x8+B0x0

根据 CRC 算法,左移 32 位,也就是求 B n − 1 x 8 ( n − 1 ) + 32 + ⋯ + B 1 x 40 + B 0 x 32   m o d   C B_{n-1} x^{8(n-1)+32} + \cdots + B_1 x^{40} + B_0 x^{32} \bmod C Bn1x8(n1)+32++B1x40+B0x32modC

P n − 1 = B n − 1 x 8 ( n − 1 ) + 32 + P n − 2 P_{n-1}=B_{n-1} x^{8(n-1) + 32} + P_{n-2} Pn1=Bn1x8(n1)+32+Pn2 ,其中 P n − 2 = B n − 2 x 8 ( n − 2 ) + 32 + B n − 3 x 8 ( n − 3 ) + 32 + ⋯ B 0 x 32 P_{n-2}=B_{n-2} x ^{8(n-2) + 32} + B_{n-3}x^{8(n-3) + 32} + \cdots B_0 x^{32} Pn2=Bn2x8(n2)+32+Bn3x8(n3)+32+B0x32


B n − 1 x 8 ( n − 1 ) + 32 + B n − 2 x 8 ( n − 2 ) + 32 + ⋯ + B 1 x 40 + B 0 x 32   m o d   C = ( B n − 1 x 8 ( n − 1 ) + 32 + P n − 2 )   m o d   C = ( B n − 1 x 8 ( n − 1 ) + 32   m o d   C + P n − 2 )   m o d   C = ( ( B n − 1 x 32   m o d   C ) x 8 ( n − 1 ) + P n − 2 )   m o d   C \begin{aligned} & B_{n-1} x^{8(n-1)+32} + B_{n-2} x^{8(n-2)+32} + \cdots + B_1 x^{40} + B_0 x^{32} \bmod C \\ &= (B_{n-1} x^{8(n-1) + 32} + P_{n-2}) \bmod C \\ &= (B_{n-1}x^{8(n-1) + 32} \bmod C + P_{n-2}) \bmod C \\ &= ((B_{n-1} x^{32} \bmod C)x^{8(n-1)} + P_{n-2}) \bmod C \end{aligned} Bn1x8(n1)+32+Bn2x8(n2)+32++B1x40+B0x32modC=(Bn1x8(n1)+32+Pn2)modC=(Bn1x8(n1)+32modC+Pn2)modC=((Bn1x32modC)x8(n1)+Pn2)modC
其中 B n − 1 x 32   m o d   C B_{n-1} x^{32} \bmod C Bn1x32modC 可以通过查表获取,其结果为一个 32 位的数字设为 γ n − 1 , 4 x 24 + γ n − 1 , 3 x 16 + γ n − 1 , 2 x 8 + γ n − 1 , 1 x 0 \gamma_{n-1,4} x^{24} + \gamma_{n-1,3}x^{16} + \gamma_{n-1,2} x^8 + \gamma_{n-1,1}x^0 γn1,4x24+γn1,3x16+γn1,2x8+γn1,1x0,其中 γ n − 1 , i   ( i = 1 , 2 , 3 , 4 ) \gamma_{n-1,i}\ (i=1,2,3,4) γn1,i (i=1,2,3,4) 为 8 位的数字。

所以可得:
R n − 1 = P n − 1   m o d   C = B n − 1 x 8 ( n − 1 ) + 32 + B n − 2 x 8 ( n − 2 ) + 32 + ⋯ + B 2 x 40 + B 1 x 32   m o d   C = ( ( B n − 1 x 32   m o d   C ) x 8 ( n − 1 ) + P n − 2 )   m o d   C = ( ( γ n − 1 , 4 x 24 + γ n − 1 , 3 x 16 + γ n − 1 , 2 x 8 + γ n − 1 , 1 x 0 ) x 8 ( n − 1 ) + P n − 2 )   m o d   C \begin{aligned} R_{n-1} = P_{n-1}\bmod C &= B_{n-1} x^{8(n-1)+32} + B_{n-2} x^{8(n-2)+32} + \cdots + B_2 x^{40} + B_1 x^{32} \bmod C \\ &= ((B_{n-1} x^{32} \bmod C)x^{8(n-1)} + P_{n-2}) \bmod C \\ &= ((\gamma_{n-1,4} x^{24} + \gamma_{n-1,3}x^{16} + \gamma_{n-1,2} x^8 + \gamma_{n-1,1}x^0) x^{8(n-1)}+ P_{n-2}) \bmod C \\ \end{aligned} Rn1=Pn1modC=Bn1x8(n1)+32+Bn2x8(n2)+32++B2x40+B1x32modC=((Bn1x32modC)x8(n1)+Pn2)modC=((γn1,4x24+γn1,3x16+γn1,2x8+γn1,1x0)x8(n1)+Pn2)modC
最后一个等式的被除数实际上是一个 n − 2 n-2 n2 阶的多项式(八个数字为一个单位,附加的 4 个 8 位数不算在内)

可得关系式:
{ P n − 1   m o d   C = ( ( γ n − 1 , 4 x 24 + γ n − 1 , 3 x 16 + γ n − 1 , 2 x 8 + γ n − 1 , 1 x 0 ) x 8 ( n − 1 ) + P n − 2 )   m o d   C P 0   m o d   C = B 0 x 32   m o d   C \begin{cases} P_{n-1} \bmod C = ((\gamma_{n-1,4} x^{24} + \gamma_{n-1,3}x^{16} + \gamma_{n-1,2} x^8 + \gamma_{n-1,1}x^0) x^{8(n-1)}+ P_{n-2}) \bmod C \\ P_0 \bmod C= B_0 x^{32} \bmod C\\ \end{cases} {Pn1modC=((γn1,4x24+γn1,3x16+γn1,2x8+γn1,1x0)x8(n1)+Pn2)modCP0modC=B0x32modC
可以直接将递归式展开:
P 0   m o d   C = B 0 x 32   m o d   C P 1   m o d   C = ( ( γ 1 , 4 x 24 + γ 1 , 3 x 16 + γ 1 , 2 x 8 + γ 1 , 1 x 0 ) x 8 + P 0 )   m o d   C P 2   m o d   C = ( ( γ 2 , 4 x 24 + γ 2 , 3 x 16 + γ 2 , 2 x 8 + γ 2 , 1 x 0 ) x 16 + P 1 )   m o d   C ⋯ \begin{aligned} &P_0 \bmod C= B_0 x^{32} \bmod C \\ &P_{1} \bmod C = ((\gamma_{1,4} x^{24} + \gamma_{1,3}x^{16} + \gamma_{1,2} x^8 + \gamma_{1,1}x^0) x^{8}+ P_{0}) \bmod C \\ &P_{2} \bmod C= ((\gamma_{2,4} x^{24} + \gamma_{2,3}x^{16} + \gamma_{2,2} x^8 + \gamma_{2,1}x^0) x^{16}+ P_{1}) \bmod C \\ &\cdots \end{aligned} P0modC=B0x32modCP1modC=((γ1,4x24+γ1,3x16+γ1,2x8+γ1,1x0)x8+P0)modCP2modC=((γ2,4x24+γ2,3x16+γ2,2x8+γ2,1x0)x16+P1)modC

以上的递归式只能用于理解查表法的过程。直接转换为代码并不太方便,为了代码方便可以使用移位寄存器,用来保存 ( γ n − 1 , 4 x 24 + γ n − 1 , 3 x 16 + γ n − 1 , 2 x 8 + γ n − 1 , 1 x 0 ) x 8 ( n − 1 ) + P n − 2 (\gamma_{n-1,4} x^{24} + \gamma_{n-1,3}x^{16} + \gamma_{n-1,2} x^8 + \gamma_{n-1,1}x^0) x^{8(n-1)}+ P_{n-2} (γn1,4x24+γn1,3x16+γn1,2x8+γn1,1x0)x8(n1)+Pn2 的前四个字节。另外前导 0 0 0 并不影响结果。

fn crc_remain(bytes: &[u8]) -> u32 {
    let mut shift_register:u32 = 0;
	let mut i = 0;
    while i < bytes.len {
		shift_register = (shift_register << 8) | bytes[i];
        shift_register = (shift_register << 8) ^ crc_table[shift_register >> 24];
        i += 1;
    }
    shift_register
}

前四次移位实际上没有任何效果,只是将移位寄存器填满,如果将前面的递推关系改写成下面这种形式:
R n − 1 = P n − 1   m o d   C = B n − 1 x 8 ( n − 1 ) + 32 + B n − 2 x 8 ( n − 2 ) + 32 + ⋯ + B 2 x 40 + B 1 x 32   m o d   C = ( ( B n − 1 x 32   m o d   C ) x 8 ( n − 1 ) + P n − 2 )   m o d   C = ( ( γ n − 1 , 4 x 24 + γ n − 1 , 3 x 16 + γ n − 1 , 2 x 8 + γ n − 1 , 1 x 0 ) x 8 ( n − 1 ) + P n − 2 )   m o d   C = ( ( ( γ n − 1 , 4 + B n − 2 ) x 24 + γ n − 1 , 3 x 16 + γ n − 1 , 2 x 8 + γ n − 1 , 1 x 0 ) x 8 ( n − 1 ) + P n − 3 )   m o d   C \begin{aligned} R_{n-1} = P_{n-1}\bmod C &= B_{n-1} x^{8(n-1)+32} + B_{n-2} x^{8(n-2)+32} + \cdots + B_2 x^{40} + B_1 x^{32} \bmod C \\ &= ((B_{n-1} x^{32} \bmod C)x^{8(n-1)} + P_{n-2}) \bmod C \\ &= ((\gamma_{n-1,4} x^{24} + \gamma_{n-1,3}x^{16} + \gamma_{n-1,2} x^8 + \gamma_{n-1,1}x^0) x^{8(n-1)}+ P_{n-2}) \bmod C \\ & = (((\gamma_{n-1,4} + B_{n-2}) x^{24} + \gamma_{n-1,3}x^{16} + \gamma_{n-1,2} x^8 + \gamma_{n-1,1}x^0) x^{8(n-1)} + P_{n-3}) \bmod C \end{aligned} Rn1=Pn1modC=Bn1x8(n1)+32+Bn2x8(n2)+32++B2x40+B1x32modC=((Bn1x32modC)x8(n1)+Pn2)modC=((γn1,4x24+γn1,3x16+γn1,2x8+γn1,1x0)x8(n1)+Pn2)modC=(((γn1,4+Bn2)x24+γn1,3x16+γn1,2x8+γn1,1x0)x8(n1)+Pn3)modC
则有:

fn crc_remainder(bytes: &[u8]) -> u32 {
    let mut shift_register:u32 = 0;
    let mut i = 0;
    while i < bytes.len {
        shift_register ^= bytes[i] << 24; // 上式中的最后一个等式
        shift_register = crc_table[shift_register >> 24] ^ (shift_register << 8);
    }
}

这实际上就是开头所讲的:

rem = (rem leftshift 8) xor crc_table[bytes[i] xor leftmost 8 bits of rem]

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进