CRC 原理

CRC 是一种用于检测数据传输错误或数据损坏的算法。

CRC-n-XX 其中 n 表示 CRC 的位宽，XX 表示 CRC 的标准名。例如：

1. CRC-64-ECMA-182: 表示 ECMA-182 标准的 64 位 CRC。
2. CRC-64-ISO: 表示 ISO 3309 (HDLC) 标准的 64 位 CRC。

数据完整性 Data integrity

Firstly, as there is no authentication, an attacker can edit a message and recompute the CRC without the substitution being detected.

没有身份验证，攻击者可以编辑message来骗过 CRC 校验，怎么编辑我也不知道。

Secondly, unlike cryptographic hash functions, CRC is an easily reversible function, which makes it unsuitable for use in digital signatures.

CRC 函数可逆，不适用于数字签名。

Thirdly, CRC satisfies a relation similar to that of a linear function (or more accurately, an affine function): $CRC(x \oplus y) = CRC(x) \oplus CRC(y) \oplus c$

计算过程 Computation

1. 首先将多项式系数以二进制形式表示。
2. 获取message的二进制编码
3. 填充 n(多项式长度) 个 0 到 message二进制编码的末尾。
4. 设置初始值，通常全部为 0。除非特定的协议要求其他的值。
5. 从最高位开始，逐位进行异或$\oplus$运算，如果最高为 0 则不进行运算，直接跳过。
6. 直到message的二进制编码的末尾，也就是倒数第 n+1 位。
7. 这样就会将message二进制编码的左边全部归零，只剩下右侧 n 位可以为非零。
8. 这剩余的 n 位就是 CRC 的值。除非某些特定的规范有后续操作。
9. 将 CRC 的值加到message二进制编码的末尾，然后重新进行步骤 5~8，会得到全零。

The most significant bit of a polynomial is always 1, and is not shown in the hex representations. 计算的时候是使用的多项式编码，是需要转为二进制并在最高为加 1 的，例如 CRC-8 的多项式编码是0x07，但是真正计算的时候用的是二进制编码 100000111。

举例，message=11010011101100，3 位 CRC 编码CRC-3的多项式为$x^3+x+1$，系数编码为1011，那么计算过程如下：

11010011101100 000 <--- 右侧填充3位0
1011               <--- divisor (4 bits) = x^3 + x + 1
------------------
01100011101100 000
 1011
------------------
00111011101100 000
  1011
------------------
00010111101100 000
   1011
------------------
00000001101100 000 <--- 前面的最高位为0，所以不进行运算，直接跳过了
       1011
------------------
00000000110100 000
        1011
------------------
00000000011000 000
         1011
------------------
00000000001110 000
          1011
------------------
00000000000101 000
           101 1
-----------------
00000000000000 100 <--- 余数 (3 bits) 此时dividend全部为零

此时 CRC 的值为 100。想要验证，只需要将 CRC 的值加到message二进制编码的末尾，然后重新进行步骤 5~8，会得到全零。

11010011101100 100 <--- 右侧填充CRC值
1011               <--- divisor
01100011101100 100
 1011
00111011101100 100
......
00000000001110 100
          1011
00000000000101 100
           101 1
------------------
00000000000000 000

接下来演示一个实际的例子： 对字符 a 计算 CRC-8 的值，多项式编码为0x07，CRC 初始值为 0x00，那么计算过程如下：

1. 首先获取字符 a 的字节码：01100001
2. 获取多项式0x07的二进制编码： 100000111
3. 填补 8 位 0，开始异或计算

01100001 00000000
 1000001 11
------------------
00100000 11000000
  100000 111
------------------
00000000 00100000

out: 00100000 => 20

如果有结果反转的话就是： reflect out: 00000100 => 04

多项式 Polynomial

Specification of a CRC code requires definition of a so-called generator polynomial. This polynomial becomes the divisor in a polynomial long division, which takes the message as the dividend and in which the quotient is discarded and the remainder becomes the result.

CRC 的多项式可以是任意的，但常用的几个多项式如下：

name	标准	多项式编码(HEX)	多项式
CRC-8	DVB-S2	0xD5	$x^8 + x^7 + x^6 + x^4 + x^2 + 1$
CRC-16-CCITT	HDLC FCS,Bluetooth...	0x1021	$x^{16}+x^{12}+x^{5}+1$
CRC-32	ISO,IEEE,ITU...	0x04C11DB7	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1$
CRC-64-ECMA	ECMA-182	0x42F0E1EBA9EA3693	$x^{64}+x^{62}+x^{57}+x^{55}+x^{54}+x^{53}+x^{52}+x^{47}+x^{46}+x^{45}+x^{40}+x^{39}+x^{38}+x^{37}+x^{35}+x^{33}+x^{32}+x^{31}+x^{29}+x^{27}+x^{24}+x^{23}+x^{22}+x^{21}+x^{19}+x^{17}+x^{13}+x^{12}+x^{10}+x^9+x^7+x^4+x+1$
CRC-64-ISO	ISO 3309	0x000000000000001B	$x^{64}+x^4+x^3+x+1$

位宽 Bit Width

Number of bits of CRC check result. Supports 8-bit, 16-bit, 32-bit, and 64-bit.

位宽表示校验结果的位数，例如 CRC-8、CRC-16、CRC-32、CRC-64，分别表示校验结果位的位数为：8、16、32、64。

多项式编码 Polynomial Formula(HEX)

The abbreviation of the generated formula, expressed in hexadecimal. Ignore the highest "1".

生成的编码通常是 16 进制，由于 bit 限制，需要忽略最高位的 1。例如：

CRC-3 的多项式$x^3+x+1$，对应二进制为1011，但是 CRC-3 只有 3 位校验位，则忽略最高位的 1，所以对应 16 进制编码则表示为0x3

CRC-8 同理：多项式为$x^8+x^2+x+1$，对应二进制为 100000111，但是只有 8 为校验位，所以忽略最高位的 1，对应 16 进制编码为0x7

• CRC-64-ECMA-182: 0x42F0E1EBA9EA3693

其他处理

有一些标准中会定义一些额外的计算，例如反向处理或位反转、结果反转、生成多项式反转等。

输入反转 Reflect In

在进行 CRC 计算之前，对输入数据的每个字节进行反转。

输出反转 Reflect Out

在输出 CRC 结果之前，对 CRC 数据的每个字节进行反转。

初始值 Initial Value

定义校验位的初始值，这样在计算的时候就不是在message后补零了，而是用初始值去填充。

我原本以为初始值是 crc 的初始值，是我错了。其实简单来说就是对数据进行一次异或初始化使用的值，然后再进行 crc 计算。 例如：对字符串"aa"计算 crc8，多项式为 0x07，初始值为 0xFF，那么计算过程如下：

# 首先对数据进行一次初始化
01100001 01100001
11111111          <- 初始值
-----------------
10011110 01100001

# 然后开始计算
10011110 01100001 00000000
10000011 1                 <- 多项式
--------------------------
00011101 11100001 00000000
   10000 0111
--------------------------
00001101 10010001 00000000
    1000 00111
--------------------------
00000101 10101001 00000000
     100 000111
--------------------------
00000001 10110101 00000000
       1 00000111
--------------------------
00000000 10110010 00000000
         10000011 1
--------------------------
00000000 00110001 10000000
           100000 111
--------------------------
00000000 00010001 01100000
            10000 0111
--------------------------
00000000 00000001 00010000
                1 00000111
--------------------------
00000000 00000000 00010111

所以结果为 0x17

结果异或 XOR Out

在 CRC 计算结束后，一些标准规定要对最终的 CRC 值与指定的值进行异或操作。

通常在没有特别说明的情况下，是结果与 0xFFFFFFFF 进行异或。

例如上面的例子中，计算"aa"的 crc 值，多项式 0x07，初始值为 0xFF，如果加上一条：结果异或值：0xFF。 那么最终结果应该为：0x17 ^ 0xFF = 0xE8

字节顺序 Bit Order

定义是以大端字节序（big-endian）还是小端字节序（little-endian）处理输入数据。、

举个例子： 例如存在某个字节编码AB12CD

如果规范定义的是大端字节序，则会转化为CDAB12；如果小端字节序，则会转化为12ABCD；

我认为字节顺序的定义一般是硬件传输层面的被动结果，而不是 CRC 计算上的主动处理。

当然如果需要在不同硬件层面去验证文件的 CRC，那确实需要考虑字节序的问题。

计算优化 Optimization

Another common optimization uses a lookup table indexed by highest order coefficients of rem to process more than one bit of dividend per iteration.

多位计算，能够优化每次迭代的位数，并且能够快速查找结果。

Using a 256-entry table is usually most convenient, but other sizes can be used. In small microcontrollers, using a 16-entry table to process four bits at a time gives a useful speed improvement while keeping the table small. On computers with ample storage, a 65536-entry table can be used to process 16 bits at a time.

预算表的大小可以选择，有时 16 条的预算表能够兼顾表小的同时有效的提升速度。或者 665536 条的预算表能够一次处理 16 位的计算。

The software to generate the tables is so small and fast that it is usually faster to compute them on program startup than to load precomputed tables from storage.

计算预算表的程序又小又快，没必要专门存储预先算好的预算表。

接下来演示，使用 8 位 CRC 预算表计算 message 为 aaa 的 CRC-8 的值, CRC 多项式为0x07： 首先正常的计算过程如下：

01100001 01100001 01100001 00000000 <- 末尾补0
 1000001 11                         <- 残值A=11000000
-----------------------------------
00100000 10100001 01100001 00000000
  100000 111                        <- 残值B=11100000
-----------------------------------
00000000 01000001 01100001 00000000
          1000001 11
-----------------------------------
00000000 00000000 10100001 00000000
                  10000011 1
-----------------------------------
00000000 00000000 00100010 10000000
                    100000 111
-----------------------------------
00000000 00000000 00000010 01100000
                        10 0000111
-----------------------------------
00000000 00000000 00000000 01101110

out： 01101110 -> 0x6E

为了更加直观的感受，我将上面的message编码按照 8 位分组

当第一组计算完成的时候，会决定第二组的值。

第二组的初始值为 01100001，而在计算第一组的时候，会有这两个残值11000000,11100000出现，所以第二组的最终值是 11000000 ^ 11100000 ^ 01100001 = 01000001。

为了方便理解，这里用符号代替，将第二组初始值设置 C=01100001，将计算第一组留下的残值设置为 A=11000000,B=11100000，所以第二组的最终值为 A ^ B ^ C。 其中 A ^ B = 00100000，正好是第一组编码的 CRC 值。 所以只需要将前一组的 CRC 值和当前字符进行异或运算，然后用此值查表就得到了下一组的值。

所以现在定义一个预算表 tables，其中用来存放所有 8 位编码的 CRC 值。其中关键预算表如下:

{
  "01100001": 00100000,
  "01000001": 11000000,
  "10100001": 01101110
}

此时我们就不再需要逐位进行运算了，只需要 8 位一步的查表就行，例如：

01100001 01100001 01100001 00000000 <- 第一组查表得 第二组的值
00000000 00100000
------------------------------------
00000000 01000001 01100001 00000000 <- 第二组查表得 第三组的值
         00000000 11000000
------------------------------------
00000000 00000000 10100001 00000000 <- 第三组查表得 最终的CRC值
                  00000000 01101110
------------------------------------

out: 01101110 -> 0x6E

总体来说，预算表的长度是你分组的位数 n 决定的为$2^n$，预算值为你 CRC 的长度，因为其本身就是每组编码的 CRC 值。

预算表是将 从 0 到 $2^n-1$ 编码的 CRC 值都提前算出来，然后在遍历 message 编码分组时，直接查表得到下一组值，循环直到最后一组。

参考资料 External Links

1. CRC
2. Computation of CRC