• 背景：使用1k-Xmodel协议传输数据，对数据进行crc校验

概念：什么是CRC

Cyclic Redundancy Check循环冗余检验：是基于数据计算一组效验码，用于核对数据传输过程中是否被更改或传输错误。 作用：可以将二进制流通过多项式的形式表现出来。

举例

如 100 1100 1101 1011 可以用多项式 g(x) =X^14 + x^11 + X^10 + x^7 + x^6 +x^4 +x^3 + x +1表示。

g(x) 称为阶为14的多项式。如果每一阶都存在的话应该有15项 [14+1]。其中g(k) 表示多项式中第k位的值，k从0开始算，从右往左。如g6 表示 表示从右往左第六位的值，其值为1. 将g(x) * m位即在二进制流后面添加m个0， 再除以m阶多项式h(x),h(x)可以自定义，也可以参照crc通行标准 得到余项位m-1阶多项式r。则r就是该二进制流的crc校验和。 注：m的取值通常为8，16，32，64等，此时便称为crc-8校验、crc-16校验...

计算过程

该过程以crc-8, h(x) = x^8 + x^5 +1举例说明。进行校验的数据为101011110101001左边是高位。

1. 在数据低位添加8个0，此时数据变为 101011110101001 0000 0000。
2. 1010 0111 1010 0010 0000 000 除以 1001 0000 1

第10步得到的余数R=00111010就是crc-8的校验和。 通过观察上面的计算过程可以得到在计算结果中，只有左边第一位是1的情况下再去除以h(x)，为0的情况是直接跳过此次迭代。 而h(x)的首位一定是1，因此h(x)可以简化为0010 0001, 00不可以省略.

查表法

• 什么是查表法？
• 表中的数据是怎么计算出来的？

上面的计算过程演示了单独的数据的一个crc校验。在处理数据流的过程中，如果每一个数据都这么计算都这这么计算效率不高，因此可以把范围内的所有数据的校验和计算出来放入表中。直接在表中取值极客。

查表法：事先将要查的值的计算出来，并填入表中，在后续计算过程中，根据表中数据查找计算即可。

crc-m的表是如何计算的:

1. 初始化一个m位的寄存器，填入初始值：全为0或者全为1
2. 将0~每一次移出的bit的个数的平方个数据依次与寄存器的低位异或
3. 将结果放入寄存器高位补0，并移动寄存器向低位移动一位，(数据对应的就是向高位移动一位)。此时根据移出位是0还是1判断是否继续移出，是0则继续移出，是1则运算，直到移动8位后。寄存器中的值就是填入表中的值

直白一点：假设每一次移出的数有8个bit，则表就是00000000-11111111中的每个值对h(x)多项式的校验和即crc值. 例子：crc-8,左边高位,初始值均为0，多项式x^8+x^2+1为例 以左边为高位，右边为低位的crc-校验称之为crc的正向校验 以左低右高称为crc的反向校验，此时不仅要校验的数据要反转，多项式也要反转。100000101反转为101000001.

  // 生成crc-16 的表
public static void generateCrcTable() {
    // 2 ^8 = 256;
    for (int i = 0; i < 256; i++) {
        // 初始化寄存器
        int crc = 0x0000;
        // 将值右移
        crc = crc ^ i << 8;
        for (int j = 0; j < 8; j++) {
        // 寄存器最高位是否为1 是右移一位 和 多项式0x1021异或运算得到校验值 否则 右移一位
            crc = (crc & 0x8000) == 0x8000 ? (crc << 1) ^ 0x1021 : crc << 1;
        }
        System.out.print(Integer.toHexString(crc & 0xffff) + " ");

        if (i> 0 && i % 15 == 0 ){
            System.out.println("");
        }
    }
}

多项式如下：

获取值的crc校验如下

public static int getCrc(int[] arr) {
    int crc = 0x0000;
    for (int j : arr) {
        crc = (crc << 8) ^ crc16_table[((crc >> 8) ^ j ) & 0xff] ;
    }
    return crc & 0xffff ;
}

参考链接

1. crc查表法-表的由来
2. crc-算法原理
3. CRC校验查表法详解