CRC那些不得不说的事

On by in 学至乎没而后止

关于 CRC 相关内容，有遗忘，也有学到新东西，遂写下此文，记录于此

CRC原理

CRC（Cyclic Redundancy Check），是循环冗余校验码，主要用于传输数据的正确性校验。说简单点，就是原始 k 位数据后面添加一个 r 位的冗余码，构成 n=k+r 位数据

CRC 是基于 GF(2) 的多项式的计算。可以证明存在一个最高次幂为 n-k=r 的多项式 G(x) ，根据 G(x) 可以生成 k 位信息的校验码，而 G(x) 叫做这个 CRC 码的生成多项式（Poly），也叫生成项

根据 k 值的不同，就产生了不同的CRC码的生成多项式，常见的有

  • $CRC16 =x^{16}+x^{15}+x^5+1$
  • $CRC16-CCITT =x^{16}+x^{12}+x^5+1$
  • $CRC32 =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$

其中，一般 zip 和 rar 会用 CRC32

实现算法

根据 CRC 的原理，可以得到它的基本算法流程：

  • 将 $k$ 位数据转成对应的 $GF(2)$ 多项式 $M(x)$
  • 将多项式 $M(x)$ 左移 $r$位，形成多项式 $M'(x)= M(x)*x^r$
  • 用多项式 $M'(x)$ 除以生成项 $G(x)$得到的余数多项式 $R(x)$ ，余数多项式对应的数值就是校验码
  • 发送方通过指定的 $CRC$ 多项式产生 $r$ 位的 $CRC$ 校验码，形成添加了校验码的数据
  • 接收方则通过该 $CRC$ 多项式来验证收到的添加校验码的数据的 $CRC$ 校验码是否为0

直接法（MSB）

上面的思路是人可以理解的思路，为了电脑能够实现，直接计算法的思路就是每次取一部分数据计算

由于是 GF(2) 上的除法，所以每次都是消 1 的过程，那么生成项的高位就可以不用，生成项 Poly 为 r+1 位 ，所以只需要设计一个 r 位寄存器

伪算法如下：

set register=r*0; //设置寄存器为r个0
移位 M << r;      // 在原始数据M后面添加r个0
while( 还有剩余原始数据要处理) {
    从 M 的左边（高位）读1位数据到 resgiser 低位
    将 regitser 左移1位
    if (regitser 左移的是 1){
        register = register xor Poly 
    }  
}

反向算法（LSB）

在大多数硬件系统的传输中，普遍先发送 LSB（least significant bit）。于是出现了反向校验算法。顾名思义，就是将左边的数据看作低位，右边的数据看作高位

伪算法如下：

set register=r*0; //设置寄存器为r个0
while( 还有剩余原始数据要处理) {
    从 M 的左边（低位）读1位数据到 resgiser 低位
    将 regitser 左移1位
    if (读取的 M 是 1){
        register = register xor 逆向Poly 
    }  
}

查表法

数据量大的时候，直接法速度比较慢，查表法便得到了应用。下面便以一个例子来说明查表法的由来

以 $G(x)=x^4+x^3+1$ (即为11001) 为例，设原数据为 1011，有以下计算过程：

    B1      B2
1 0 1 1 | 0 0 0 0
1 1 0 0 | 1 0 0 0       --->a1
-----------------
  1 1 1 | 1 0 0 0
  1 1 0 | 0 1 0 0       --->a2
  ---------------
    0 1 | 1 1 0 0
    0 0 | 0 0 0 0       --->a3
    -------------
      1 | 1 1 0 0
      1 | 1 0 0 1       --->a4
      -----------
          0 1 0 1       --->CRC

可以看到经过 4 次迭代，B1 被移除。同时显然 CRC = a1 ^ a2 ^ a3 ^ a4 ^ B2 ，定义 A = a1 ^ a2 ^ a3 ^ a4，显然 A 只与 B1 有关，且 CRC = A ^ B2

所以当 B1 被移除后，只需要知道 A 的值，就能计算出 CRC，于是计算时可以一次移除 4位。于此同时 A 的值便是查表法中的表

根据上面的计算，由于 B2 为 0，因此 A = CRC。同时可以观察到对于 A 的计算，便是对 B1 块求 CRC 校验值的过程。所以对于表的计算就是对移除数据求 CRC

下面以单字节查表的 CRC32为例，了解算法的具体实现

直接查表法：
实现代码如下：

unsigned int r=0;
while(len--){
    r = (r<<8 | *p++) ^ table[ (r>>24) & 0xff ];
}
// for循环的目的是给计算的数据进行补0操作
for(i=0; i<W/8; i++){
    r = (r<<8) ^ table[ (r>>24) & 0xff ];
}

算法流程:

  • 对 32 位寄存器 r 移除高字节，用于查表
  • 寄存器 r 的其余 3 字节拼接上数据字节
  • 将两者异或得到结果，持续直到计算完

可以用图来帮助理解代码：

            CRC寄存器
          3   2   1   0
        +---------------+  （移入1字节）
    +--<|   |   |   |   | <-----------msg
    |   +---------------+
（移出1字节）     ^
    |           |(XOR)
    |   +---------------+
    |   |               |
    +-->|     TABLE     |
        |               |
        +---------------+

改进查表法：
由上图可知，寄存器 r 最开始 4 字节的移动其实没有意义，因为任何值与 0 异或都不改变

同时根据算法，数据第一个字节查表时，整个有效的 CRC计算才算开始，最后一个字节查表时，整个有效的 CRC 计算才算结束

所以实现代码如下：

unsigned int r=0;
while(len--){
    r = (r<<8) ^ table[ (r>>24) ^ *p++ ];
}

算法流程:

  • 对 32 位寄存器 r 移除高字节，用高字节和数据字节异或，查表
  • 寄存器 r 的其余 3 字节左移 1 字节
  • 将两者异或得到结果，持续直到计算完

可以用图来帮助理解代码：

            CRC寄存器
    +--<msg
    |     3   2   1   0
    |   +---------------+
    +--<|   |   |   |   | 
    |   +---------------+
（移出1字节）     ^
    |           |(XOR)
    |   +---------------+
    |   |               |
    +-->|     TABLE     |
        |               |
        +---------------+

数据字节还没加入时，CRC 中相当于存了叠加态，等该加入数据字节时，直接利用 CRC 最高字节的叠加态和数据字节异或直接查表

反向改进查表法：

需要将message的移动方向逆向，在计算表时，所使用的的除数多项式也得将顺序调转。所以实现代码如下：

unsigned int r=0;
while(len--){
    r = (r>>8) ^ table[ (r ^ *p++) & 0xff ];
}

算法流程:

  • 对 32 位寄存器 r 移除低字节，用低字节和数据字节异或，查表
  • 寄存器 r 的其余 3 字节右移 1 字节
  • 将两者异或得到结果，持续直到计算完

可以用图来帮助理解代码：

            CRC寄存器
                      msg>----+
          3   2   1   0       |
        +---------------+     |
        |   |   |   |   |>----+
        +---------------+     | 
                ^        （移出1字节）
                |(XOR)        |
        +---------------+     |
        |               |     |
        |     TABLE     |<----+
        |               |
        +---------------+

一般来讲，目前的 CRC 实现算法都是反向改进查表法。由于考虑到数据存在 0x00 数据，寄存器用 0xFFFFFFFF 进行初始化，就可以避免异或结果为 0的情况

四字节序列算法

针对 CRC32 的反向改进查表法，由于寄存器右移 8位，寄存器的高 8 位只由表中数据决定

r = (r>>8) ^ table[ (r ^ *p++) & 0xff ];

通过这种特点，可以找到一个四字节序列并将其附加到任何消息中，并获得任何所需的结果CRC散列

原理

下列过程显示了 CRC 算法如何将散列转换为所需的 CRC:AA BB CC DD。xx 值为添加四字节序列之前的消息的 CRC。

        CRC寄存器
    xx  xx  xx  xx
    00  xx  xx  xx
    DD3 ??  ??  ??  添加第一个字节
    --------------
    DD3 ??  ??  ??
    00  DD3 ??  ??
    CC2 ??  ??  ??  添加第二个字节
    --------------
    CC2 DD2 ??  ??
    00  CC2 DD2 ??
    BB1 ??  ??  ??  添加第三个字节
    --------------
    BB1 CC1 DD1 ??
    00  BB1 CC1 DD1
    AA  ??  ??  ??  添加第四个字节
    --------------
    AA  BB  CC  DD

所以需要最终查找到table中最高字节为别为 AA 、BB1 、CC2 、DD3 的索引（即为添加的四字节序列）

首先根据上述过程可以定义如下

初始化：
CRC   = AA  BB  CC  DD
CRC11 = BB1 CC1 DD1 00
CRC22 = CC2 DD2 00  00
CRC33 = DD3 00  00  00

四次迭代之间的关系：
CRC11 = (CRC   ^ T[i3]) << 8 
CRC22 = (CRC11 ^ T[i2]) << 8
CRC33 = (CRC22 ^ T[i1]) << 8 

求解：
CRC   >> 24 == AA
CRC11 >> 24 == BB1
CRC22 >> 24 == CC2
CRC33 >> 24 == DD3
满足等式的i3,i2,i1,i0索引

所以根据上述问题，可以得到一个快速查找四字节序列的方法

  • 建立一个索引表，根据查表法中表的值的高字节做索引，表的索引做值
  • 根据上述等式，每次计算 CRC，CRC11，CRC22，CRC33，并取高字节查索引表，得到逆向的四字节序列，翻转即可

由于可以快速查找到 CRC 对应的四字节序列，那么对于五字节、六字节来说，只需先添加一字节或者两字节，再利用四字节序列算法，也可以快速的得到。更多的字节出现的冲突更多，一般也没什么意义

应用

快速计算 CRC32 对应的 4，5，6 字节，可以用于加密 ZIP 中短文本的明文获取（需要限制添加的字节和四字节序列都在可打印字符中）

具体的实现可以见https://github.com/fromhex/gocrc32

参考

https://python.iitter.com/other/35811.html
https://www.cnblogs.com/masonzhang/p/10261855.html
http://www.danielvik.com/2010/10/calculating-reverse-crc.html
http://www.danielvik.com/2012/01/finding-reverse-crc-patch-with-readable.html
https://github.com/theonlypwner/crc32
tag(s): CRC
show comments
Edit with markdown