CRC 校验查表法的内在原理

CRC 余数的计算

设 CRC 多项式为 $C$。

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

表中数据为单字节(8 bit)的 CRC 余数。将被除数多项式每八位为一组，设为 $B_1{x}^8+B_0{x}^0$。

其中 $B_1,B_0$ 是 $x$ 进制的八位数。

已知 $B_1{x}^{32}\mathrm{m}\mathrm{o}\mathrm{d}C=R_1$，$R_1$ 为 32 位的余数。

注意下文中的 $\Gamma x^{32}\mathrm{m}\mathrm{o}\mathrm{d}C$ 均可以直接查表获得（以 $\Gamma$ 为 CRC 表的索引）。

求 $(B_1{x}^8+B_0{x}^0)x^{32}\mathrm{m}\mathrm{o}\mathrm{d}C$ 的值：

等价于 $(B_1{x}^{40}+B_0{x}^{32})\mathrm{m}\mathrm{o}\mathrm{d}C=(R_1{x}^8+B_0{x}^{32})\mathrm{m}\mathrm{o}\mathrm{d}C$，

令 $R_1={\gamma }_{1,4}{x}^{24}+{\gamma }_{1,3}{x}^{16}+{\gamma }_{1,2}{x}^8+{\gamma }_{1,1}{x}^0$，其中 ${\gamma }_{1,i}(i=1,2,3)$ 为 8 位数。

所以：
$$\begin{array}{rl}& (B_1{x}^{40}+B_0{x}^{32})\mathrm{m}\mathrm{o}\mathrm{d}C\\ & =((B_1{x}^{32}\mathrm{m}\mathrm{o}\mathrm{d}C)x^8+B_0{x}^{32})\mathrm{m}\mathrm{o}\mathrm{d}C\\ & =(R_1{x}^8+B_0{x}^{32})\mathrm{m}\mathrm{o}\mathrm{d}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})\mathrm{m}\mathrm{o}\mathrm{d}C\\ & =(({\gamma }_{1,4}+B_0)x^{32}+{\gamma }_{1,3}{x}^{24}+{\gamma }_{1,2}{x}^{16}+{\gamma }_{1,1}{x}^8)\mathrm{m}\mathrm{o}\mathrm{d}C\\ & =(({\gamma }_{1,4}+B_0)x^{32}\mathrm{m}\mathrm{o}\mathrm{d}C+{\gamma }_{1,3}{x}^{24}+{\gamma }_{1,2}{x}^{16}+{\gamma }_{1,1}{x}^8)\mathrm{m}\mathrm{o}\mathrm{d}C\end{array}$$
注意到最后一个等式中的被除数已经是 32 位数了，所以可得：
$$\begin{array}{rl}& (B_1{x}^{40}+B_0{x}^{32})\mathrm{m}\mathrm{o}\mathrm{d}C\\ & =(({\gamma }_{1,4}+B_0)x^{32}\mathrm{m}\mathrm{o}\mathrm{d}C+{\gamma }_{1,3}{x}^{24}+{\gamma }_{1,2}{x}^{16}+{\gamma }_{1,1}{x}^8)\mathrm{m}\mathrm{o}\mathrm{d}C\\ & =({\gamma }_{1,4}+B_0)x^{32}\mathrm{m}\mathrm{o}\mathrm{d}C+{\gamma }_{1,3}{x}^{24}+{\gamma }_{1,2}{x}^{16}+{\gamma }_{1,1}{x}^8\end{array}$$
其中 $({\gamma }_{1,4}+B_0)x^{32}\mathrm{m}\mathrm{o}\mathrm{d}C$ 可以通过查表获得。转换成代码：

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

rem leftshift 8 对应 ${\gamma }_{1,3}{x}^{24}+{\gamma }_{1,2}{x}^{16}+{\gamma }_{1,1}{x}^8$，bytes[i] xor leftmost 8 bits of rem 对应 ${\gamma }_{1,4}+B_0$，crc_table[bytes[i] xor leftmost 8 bits of rem] 则对应 $({\gamma }_{1,4}+B_0)x^{32}\mathrm{m}\mathrm{o}\mathrm{d}C$。

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

设被除数为 $B_{n-1}{x}^{8(n-1)}+\cdots +B_1{x}^8+B_0{x}^0$。

根据 CRC 算法，左移 32 位，也就是求 $B_{n-1}{x}^{8(n-1)+32}+\cdots +B_1{x}^{40}+B_0{x}^{32}\mathrm{m}\mathrm{o}\mathrm{d}C$

令$P_{n-1}=B_{n-1}{x}^{8(n-1)+32}+P_{n-2}$ ，其中 $P_{n-2}=B_{n-2}{x}^{8(n-2)+32}+B_{n-3}{x}^{8(n-3)+32}+\cdots B_0{x}^{32}$

则
$$\begin{array}{rl}& 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}\mathrm{m}\mathrm{o}\mathrm{d}C\\ & =(B_{n-1}{x}^{8(n-1)+32}+P_{n-2})\mathrm{m}\mathrm{o}\mathrm{d}C\\ & =(B_{n-1}{x}^{8(n-1)+32}\mathrm{m}\mathrm{o}\mathrm{d}C+P_{n-2})\mathrm{m}\mathrm{o}\mathrm{d}C\\ & =((B_{n-1}{x}^{32}\mathrm{m}\mathrm{o}\mathrm{d}C)x^{8(n-1)}+P_{n-2})\mathrm{m}\mathrm{o}\mathrm{d}C\end{array}$$
其中 $B_{n-1}{x}^{32}\mathrm{m}\mathrm{o}\mathrm{d}C$ 可以通过查表获取，其结果为一个 32 位的数字设为 ${\gamma }_{n-1,4}{x}^{24}+{\gamma }_{n-1,3}{x}^{16}+{\gamma }_{n-1,2}{x}^8+{\gamma }_{n-1,1}{x}^0$，其中 ${\gamma }_{n-1,i}(i=1,2,3,4)$ 为 8 位的数字。

所以可得：
$$\begin{array}{rl}{R}_{n-1}=P_{n-1}\mathrm{m}\mathrm{o}\mathrm{d}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}\mathrm{m}\mathrm{o}\mathrm{d}C\\ & =((B_{n-1}{x}^{32}\mathrm{m}\mathrm{o}\mathrm{d}C)x^{8(n-1)}+P_{n-2})\mathrm{m}\mathrm{o}\mathrm{d}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})\mathrm{m}\mathrm{o}\mathrm{d}C\end{array}$$
最后一个等式的被除数实际上是一个 $n-2$ 阶的多项式（八个数字为一个单位，附加的 4 个 8 位数不算在内）

可得关系式：
$$\{\begin{array}{l}{P}_{n-1}\mathrm{m}\mathrm{o}\mathrm{d}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})\mathrm{m}\mathrm{o}\mathrm{d}C\\ P_0\mathrm{m}\mathrm{o}\mathrm{d}C=B_0{x}^{32}\mathrm{m}\mathrm{o}\mathrm{d}C\end{array}$$
可以直接将递归式展开：
$$\begin{array}{rl}& P_0\mathrm{m}\mathrm{o}\mathrm{d}C=B_0{x}^{32}\mathrm{m}\mathrm{o}\mathrm{d}C\\ & P_1\mathrm{m}\mathrm{o}\mathrm{d}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)\mathrm{m}\mathrm{o}\mathrm{d}C\\ & P_2\mathrm{m}\mathrm{o}\mathrm{d}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)\mathrm{m}\mathrm{o}\mathrm{d}C\\ & \cdots \end{array}$$

如果使用递归函数：

// parameter bytes is append with 4 empty bytes;
fn crc_remainder(bytes: mut Vec<u8>) -> u32 {
let mut remainder:u32 = match bytes.pop {
Some(b_n_1) => crc_table[b_n_1],
None => 0,
};
let mut new_bytes: Vec<u8> = vec![remainder >> 24, remainder >> 16 & 0xff, remainder >> 8 & 0xff, remainder & 0xff];
let mut i = 0;
while let Some(top) = bytes.top() {
new_bytes[i] ^= top;
i += 1;
}
if i <= 4 {
return new_bytes[0] << 24 | new_bytes[1] << 16 | new_bytes[2] << 8 | new_bytes[3];
}
new_bytes.append(bytes);
return crc_remainder(new_bytes);
}

这种递归式主要缺点在于修改了原始数据，而且内存调整非常消耗资源。而尾调用可以很容易的修改为循环结构。为了不修改原始数据，可以使用移位寄存器，用来保存 $({\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}$ 的前四个字节。另外前导 $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
}

前四次移位实际上没有任何效果，只是将移位寄存器填满，如果将前面的递推关系改写成下面这种形式：
$$\begin{array}{rl}{R}_{n-1}=P_{n-1}\mathrm{m}\mathrm{o}\mathrm{d}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}\mathrm{m}\mathrm{o}\mathrm{d}C\\ & =((B_{n-1}{x}^{32}\mathrm{m}\mathrm{o}\mathrm{d}C)x^{8(n-1)}+P_{n-2})\mathrm{m}\mathrm{o}\mathrm{d}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})\mathrm{m}\mathrm{o}\mathrm{d}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})\mathrm{m}\mathrm{o}\mathrm{d}C\end{array}$$
则有：

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);
i += 1;
}
}

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

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

如果严格按照上面递推关系式编写代码，如下所示：

fn crc_remainder(bytes: &[u8]) -> u32 {
if bytes.len == 0 {
return 0;
}
let mut shift_register:u32 = crc_table[bytes[0]]; // 递推关系式第二行、第三行等式
let mut i = 1;
while i < bytes.len {
// 上式中的最后一个等式。
shift_register ^= bytes[i] << 24;
// 将最后一个等式中的被除数作为 P_{n-2}，将下一个循环提前。递推关系式的第二、三行。
shift_register = crc_table[shift_register >> 24] ^ (shift_register << 8);
i += 1;
}
}

和上一个代码片段在操作步骤上实际上是等价的。

CRC 表的生成

如果按字节索引，实际上就是生成 $[0,255]$ 范围内所有整型的 CRC 余数，单字节可以直接移位处理计算。值得注意的是: $(B_1+B_2)\mathrm{m}\mathrm{o}\mathrm{d}C=(B_1\mathrm{m}\mathrm{o}\mathrm{d}C+B_2\mathrm{m}\mathrm{o}\mathrm{d}C)\mathrm{m}\mathrm{o}\mathrm{d}C$ ，由于我们实施的是无进位加法，所以 $B_1\mathrm{m}\mathrm{o}\mathrm{d}C+B_2\mathrm{m}\mathrm{o}\mathrm{d}C$ 的位数是小于 $C$ 的，从而 $(B_1+B_2)\mathrm{m}\mathrm{o}\mathrm{d}C=B_1\mathrm{m}\mathrm{o}\mathrm{d}C+B_2\mathrm{m}\mathrm{o}\mathrm{d}C$。

也就是说，我们计算了 $a,b\in [0,255]$ 的 CRC 余数，那么就可以直接通过 $(B_1+B_2)\mathrm{m}\mathrm{o}\mathrm{d}C=B_1\mathrm{m}\mathrm{o}\mathrm{d}C+B_2\mathrm{m}\mathrm{o}\mathrm{d}C$ 关系获取到 $c=a+b\in [0,255]$ 的 CRC 余数，这是一个加快生成 CRC 表的技巧。

需要注意的是这里的加法在编码的时候要变成异或。

前文也提到过这一点。

设最高阶为 $n$ 的多项式集合为 $P_n$，那么 P n + 1 = { a n + 1 x n + 1 + p n ∣ ∀ p n ∈ P n } P_{n+1} = {a_{n+1}x^{n+1} + p_{n}mid forall p_nin P_{n}} Pn+1​={an+1​xn+1+pn​∣∀pn​∈Pn​} ，这是一个递归定义（而且是尾递归可以用循环体优化）。

P 0 = { 0 } P_0={0} P0​={0} 是递归定义的初始条件。 也就是说我们只需要求出 $a_k{x}^k(k=1,2,3\cdots )$ 的 $\mathrm{m}\mathrm{o}\mathrm{d}C$ 的余数，就可以通过递归式求出 $P_k$ 中所有多项式 $\mathrm{m}\mathrm{o}\mathrm{d}C$ 的余数。

转换成二进制，求 8 bit 中所有数值的 CRC 余数，实际上我们只需要求出 $0,1,2,4,8,16,32,64,128$ 的 CRC 余数即可。（$0$ 的 CRC 余数即为 $0$，该数值的 CRC 余数无需通过移位计算。）

由 $x^{n+1}{x}^{32}\mathrm{m}\mathrm{o}\mathrm{d}C=((x^n{x}^{32}\mathrm{m}\mathrm{o}\mathrm{d}C)x)\mathrm{m}\mathrm{o}\mathrm{d}C$ ，而 $(x^n{x}^{32}\mathrm{m}\mathrm{o}\mathrm{d}C)x$ 的阶数是小于等于 $C$ 的阶数的。如果等于 $C$ 的阶数，则结果等于 $(x^n{x}^{32}\mathrm{m}\mathrm{o}\mathrm{d}C)x-C$，如果小于 $C$ 的阶数，则结果为 $(x^n{x}^{32}\mathrm{m}\mathrm{o}\mathrm{d}C)x$。也就是说我们计算了 $2^n\mathrm{m}\mathrm{o}\mathrm{d}C$ 之后，观察其最高位是否为 1；如果是 1，则 $+C$，否则 $+0$。

注意 $C$ 是 33 位，且最高位为 $1$，所以 CRC-32 多项式一般将最高位省略，用 32 个 bit 来表示 33 个 bit。

二进制无进位加法等同于无进位减法，均表示为异或操作。所以 $(x^n{x}^{32}\mathrm{m}\mathrm{o}\mathrm{d}C)x-C=(x^n{x}^{32}\mathrm{m}\mathrm{o}\mathrm{d}C)x+C$

利用该方法，我们可以通过 8 次移位便可以将 $1,2,4,8,16,32,64,128$ 的 CRC 余数计算出来，而无需将每一个数值当作一个 8 bit 的字节来进行计算。耗时约等于原来的 $\frac{1}{8}$。

总耗时大概是 8 次移位和最多 256 次的异或操作。所以表格的生成是相当快速的，甚至可以在运行时进行。

bit 序和 CRC 多项式的逆转

• to-do

带有初始值的 CRC 求余

• to-do

最后

以上就是微笑老师为你收集整理的CRC 校验查表法的内在原理的全部内容，希望文章能够帮你解决CRC 校验查表法的内在原理所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。