用查表发实现crc16校验怎么实现

1）将上次计算出的CRC校验码右移一个字节；

（2）将移出的这个字节与新的要校验的字节进行XOR 运算；

（3）用运算出的值在预先生成码表中进行索引，获取对应的值（称为余式）；

（4）用获取的值与第（1）步右移后的值进行XOR 运算；

（5）如果要校验的数据已经处理完，则第（4）步的结果就是最终的CRC校验码。如果还有数据 要进行处理，则再转到第（1）步运行。

CRC32=CRC_32_Tbl[(CRC32^((unsigned__int8*)p)[i])&0xff]^(CRC32>>8)

怎么样？简单吧。

CRC，一种基于有限域GF(2)的多项式环的Hash算法。在GF(2)中，多项式系数只有0、1，加减运算等同于异或(XOR)运算，乘除运算与一般多项式运算一致（合并同类项时需要注意为XOR运算）

在GF(2)中，多项式系数只有0、1，加减运算等同于异或(XOR)运算，乘除运算与一般多项式运算一致（合并同类项时需要注意为XOR运算）。在CRC-n算法中，有M(x)·x n =Q(x)·G(x)+R(x)，M(x)为m位的数据，G(x)为一个GF(2)的n+1项的生成多项式(Poly)，M(x)·x n 则是通过在数据M(x)后添加n个0形成的对应的m+n位多项式，而R(x)即为M(x)·x n 除以G(x)的n位余数——即CRC校验码，Q(x)为商，直接丢弃。通过比较两次计算产生的Signature是否一致判断故障的发生

假定M(x)=11100110，G(x)=x 3 + x + 1，其中n=3，则M(x)·x n =11100110000，将G(x)多项式中的各项系数取出，按降幂排列所对应的数据Poly=1011，然后对其进行除法运算：

所得n位余数即为CRC——100

根据定义可以建立一个简单的CRC实现算法，模型如下图所示：

1)建立一个长度为r的CRC Register，并初始化为0

2)在M(x)后添加r个0形成M(x)·x n

3)将CRC Register左移一位，将M(x)·x n 的MSB移入CRC Register的Bit 0

4)第3步中的从CRC Register移出的数，如果是1，则计算，CRC Register=Poly XOR CRC Register

5)重复第3步，直到M(x)·x n 全部移入CRC Register

6)CRC Register即为CRC校验值

根据定义所建立的算法模型存在明显缺陷，按位移动处理效率低下，为此我们探索如何实现更大处理单元的算法。这次我们以CRC-32为例，按照前面的算法思路构建的模型如下图所示：

设CRC Register中的Byte 3依次为：t7 t6 t5 t4 t3 t2 t1 t0，Poly中的Bit31-Bit24依次为：g7 g6 g5 g4 g3 g2 g1 g0，根据1.3.2可知，在第1次迭代中，CRC Register的MSB:t7将会决定Poly与CRC Register的异或，如果t7=1，这就会发生，反之就不会发生在第2次迭代中，CRC Register的MSB:t6 XOR (t7*g7) 将会决定本次Poly与CRC Register的异或是否发生，即t7、t6控制第2XOR *** 作；同理，在第3次迭代中，CRC Register的MSB也是通过t7、t6、t5决定，即t7、t6、t5控制第3次XOR *** 作。故我们可以得出下述结论：k次以后的迭代的最高位的值，可以由寄存器的前k位计算得到。根据这个结论，我们可以一次性取出CRC Register的Byte 3，提前计算出8次迭代后的寄存器余式，因为高位终将会在迭代中被移出，我们只需要关心余式即可。同时XOR运算满足结合律：A XOR B XOR C = A XOR (B XOR C)

上图即为Byte 3全部迭代移出的示意图，根据结合律可以看出，我们可以依据Byte 3直接确定8次异或的与否及Poly的偏移量，从而提前计算出不同偏移量的Poly间XOR的值，令其为A，易知A的高8位和Byte 3一定相等，Reg向左移出btye3，从M(x)·x n 读取一个byte放在byte 0，最后将A的低32位与Reg完成XOR *** 作。为避免与字节边界发生冲突，我们采用字节的整数倍——字节（1 byte）、字（2 byte）、双字（4 byte），故一般不采用4bit作为处理单元。由于一个字节的取值是有限的——256种，我们只要提前计算一个字节全部的A值保存到表中。运行时以byte值为索引，直接从表里取出即可

至此我们完成基于1 byte为处理单元的Table Driven，算法模型如下图所示：

1)建立一个长度为r的CRC Register，并初始化为0

2)在M(x)后添加r个0形成M(x)·x n

3)将CRC Register左移一个byte，从M(x)·x n 读入一个byte至CRC Register的byte 0中

4)以第3步中的从CRC Register移出的byte为index，从表中取出对应的n位宽的值，将该值与CRC Register进行XOR

5)重复第3步，直到M(x)·x n 全部移入CRC Register6) CRC Register即为CRC校验值

在上述的两种算法中，我们每次都需要在M(x)后添加n个0，其并不参与运算，目的只是为了将M(x)的全部推入CRC Register而已，并且在有些情境下在M(x)后添0 *** 作并不总是能够实现的，故通过改进计算步骤有了直接表法，避免了对原始数据的添0 *** 作

算法流程，算法模型如下图所示：

1)建立一个长度为r的CRC Register，按照Init值对其初始化

2)将CRC Register左移一个byte，从M(x)左移一个byte，两者进行XOR

3)第2步中XOR后的值作为index，从表中取出对应的n位宽的值，将该值与CRC Register进行XOR

4)重复第2步，直到M(x)全部取出

5)CRC Register即为CRC校验值

在Direct Table算法中，当RefIn、RefOut为True，每次都需要对数据做颠倒 *** 作，很麻烦。为此产生了Reflected Direct Table算法，该算法改变了CRC Register的移动方向，而不需要对M(x)做任何处理，按字节顺序读取即可，算法模型如下图所示

算法流程如下：

1)建立一个长度为r的CRC Register，按照Init值对其初始化

2)将CRC Register右移一个byte，从M(x)左移一个byte，两者进行XOR

3)第2步中XOR后的值作为index，从表中取出对应的n位宽的值，将该值与CRC Register进行XOR

4)重复第2步，直到M(x)全部取出

5)CRC Register即为CRC校验值

Name: CRC标准

Width: 生成的CRC的位宽

Poly: 生成多项式，一般采用十六进制简记，长度为width+1，由于其最高位恒为1，故记法中不体现出来（例如：x 16 +x 12 +x 5 +1记为0x1021）

Init: 初始值，如果数据前添加了若干个前导零，在前述算法中，一般是检测不到的，故通过改变CRC Register中的预设值，以实现对该类型错误的检测。在Direct Table算法中用Init初始化CRC Register即可，在Table Driven算法中，不可以直接用Init初始化CRC Register，因为其等同于在原始数据前插入了Init，必须要先把CRC Register设为0，等M(x)·x n 移动n/8次后，即CRC Register的预设值0全部移出时，再将Init值异或进CRC Register。完成Init *** 作

Xorout: 结果异或值，所有计算完成后将CRC Register与Xorout进行异或作，作为最后的校验值

RefIn: 输入反转，这是一个布尔值，如果为False，则每个字节内的位顺序保持不变，即Bit 7为MSB，Bit0为LSB。如果为True，则将需要每个字节内的位顺序颠倒，即Bit 7为LSB，Bit0为MSB。这个约定在硬件CRC中是合理的，因为在串口通讯中硬件一般默认先发送字节的Bit 0，最后发送Bit 7

RefOut: 输出反转，这是一个布尔值，如果为False，则在计算结束后，直接进入Xorout环节，如果为True，则在计算结束后，将CRC Register进行颠倒后，再进入Xorout环节。注意，和RefIn颠倒字节内的位顺序不同的是，这个是将CRC Register的值作为一个整体颠倒，即Bit n到Bit0进行颠倒

针对常见常用的下述CRC给出了实现方法，以供参考

---