一、CRC概念

1.什么是CRC？

CRC(循环冗余校验和)是一种纠错技术，代表循环冗余校验和。

数据通信领域最常用的错误校验码之一，其信息字段和校验字段长度可以任意指定，但要求通信双方定义的CRC标准一致。它主要用于检测或检查数据传输或存储后可能出现的错误。下图说明了它的用法：

在数据传输的过程中，无论传输系统的设计有多完善，总会出现错误，可能导致链路上传输的一帧或多帧被破坏(出现误码，0变成1或1变成0)，使接收端接收到错误的数据。

为了尽可能提高接收方接收到的数据的准确性，需要在接收方接收之前对数据进行错误检测，只有检测结果正确，接收方才能真正接受数据。检测的方式有很多种，比如奇偶校验,因特网校验和循环冗余校验.

2.使用方法概述

循环冗余校验是一种用于验证通信链路上数字传输准确性的计算方法(数据位和奇偶校验位之间约定的关系是通过某种数学运算建立的)。

发送者的计算机使用公式来计算包含在传输数据中的信息的值，并将该值附加到传输数据。接收者的计算机对相同的数据执行相同的计算，应该得到相同的结果。

如果两次CRC结果不一致，说明传输有错误，接收计算机可以要求发送计算机重新发送数据。

3.应用广泛

CRC是最著名的错误检测方法。CRC的全称是循环冗余校验，其特点是检错能力强，开销低，易于编码器和检测电路实现。从它的检错能力来看，它发现不了错误的概率只有0.0047%以下。

在性能和开销上，远远优于奇偶校验、算术和校验。

因此，在数据存储和数据通信领域，CRC无处不在：著名通信协议X.25的FCS(帧检错序列)使用CRC-CCITT，WinRAR，NERO，ARJ，LHA等压缩工具软件使用CRC32，磁盘驱动器使用CRC16进行读写，常见的图像存储格式GIF和TIFF也使用CRC作为检错手段。

二、CRC名称的定义

这里我们需要知道几个组成部分或计算概念：多项式公式、多项式缩写、数据宽度、初始值、结果的异或值、输入值的反演、输出值的反演、参数模型。

1、多项式公式

CRC的标准除数一般用多项式(或二项式)公式表示。如下图所示，除数11011(poly值为0x1b)的二项式为G(X)=X4 X3 X 1，X的指数表示该位上的数据为1(最低位为0)。

特别注意这里的位数。除数的位数是二项式1的最高次方(4 ^ 1=5)，这个很重要。

2、多项式简记式

通过对CRC的基本理解，我们知道多项式的首尾必须是1，而这个1在下一次计算中的位置必须是0，于是我们省略了前面的1，于是出现了一个叫做速记公式的东西。上例中除数11011的速记公式是1011，很多看过CRC高级语言源代码的人都会知道，对于CRC_16标准，G (x)=这个用法后面会解释。

3、数据宽度

数据宽度是指CRC校验码的长度(二进制数字)。知道CRC的运算概念和多项式，就能理解这个概念。CRC长度总是比除数小1，这与缩写长度一致。

以上三个数据是我们经常可以用到的基础数据。

4、初始值与结果异或值

在某些标准中规定了初始值，所以在进行上述二项式运算之前，需要将待计算的数据与初始值的最低字节进行异或，然后用多项式进行计算。

但是如果结果XOR值不为零，我们需要将计算出的CRC结果值与结果XOR值再次进行XOR运算，最后的值就是我们需要的CRC校验码。

这里可以看出，初始值和结果值的位数应该与数据宽度一致。

5、输入值反转与输出值反转

输入值反演是指在计算之前先对二项式进行反演，然后用新的值和数据进行计算。对于G(X)=X16 X15 X2 1(16#18005)，正值为1100000000000000101，负值为10100000000000011。

输出值反转是反转最终的CRC结果。

通常输入值反转后的结果值也会反转，所以这两个选项一般是同向的。只有在网上的CRC计算器里才能看到正反自由选择的存在。

三、常见的CRC算法

虽然CRC可以任意定义二项式、数据长度等。没有统一的标准，整个计算会变得很麻烦。但实际上，不同的厂商往往使用不同的标准算法。以下是一些国际通用的模型表：

常用模型表

四、CRC校验算法前置知识

在学习CRC校验算法之前，先回顾一下CRC涉及的主要算法。

1.异或

异或表示差为1，同为0，运算符号为0。

pre>0^0=00^1=11^1=01^0=1

异或运算存在如下几个规律，需要了解。

0^x=x即0异或任何数等于任何数1^x=~x即1异或任何数等于任何数取反x^x=0即任何数与自己异或，结果为0a^b=b^a交换律a^(b^c)=(a^b)^c结合律

2.模2加法

模2加法相对于普通的算术加法，主要的区别在模2加法，不做进位处理。具体结果如下。0+0=00+1=11+1=01+0=1我们发现模2加法的计算结果，同异或运算结果一模一样。进一步推演，我们会发现，异或运算的5个规律，同样适合于模2加法。这里，就不在一一列举了。

3.模2减法

模2减法相对于普通的算术减法，主要的区别在模2减法，不做借位处理。具体结果如下。0-0=00-1=11-1=01-0=1我们发现模2减法的计算结果，同模2加法，以及异或的运算结果一模一样。进一步推演，我们会发现，异或运算的5个规律，同样适合于模2减法。这里，就不在一一列举了。

4.模2除法

模2除法相对于普通的算术除法，主要的区别在模2除法，它既不向上位借位，也不比较除数和被除数的相同位数值的大小，只要以相同位数进行相除即可。

五、CRC原理

CRC原理：在K位信息码（目标发送数据）后再拼接R位校验码，使整个编码长度为N位，因此这种编码也叫（N,K）码。

通俗的说，就是在需要发送的信息后面附加一个数（即校验码），生成一个新的发送数据发送给接收端。这个数据要求能够使生成的新数据被一个特定的数整除。这里的整除需要引入模2除法的概念。

那么，CRC校验的具体做法就是

（1）选定一个标准除数（K位二进制数据串）

（2）在要发送的数据（m位）后面加上K-1位0，然后将这个新数（M+K-1位）以模2除法的方式除以上面这个标准除数，所得到的余数也就是该数据的CRC校验码（注：余数必须比除数少且只少一位，不够就补0）

（3）将这个校验码附在原m位数据后面，构成新的M+K-1位数据，发送给接收端。

（4）接收端将接收到的数据除以标准除数，如果余数为0则认为数据正确。

注意：CRC校验中有两个关键点：

一是要预先确定一个发送端和接收端都用来作为除数的二进制比特串（或多项式）；

二是把原始帧与上面选定的除进行二进制除法运算，计算出FCS。

前者可以随机选择，也可按国际上通行的标准选择，但最高位和最低位必须均为“1”

六、循环冗余的计算

实例：

由于CRC-32、CRC-16、CCITT和CRC-4的编码过程基本一致，只有位数和生成多项式不一样，下面就举例，来说明CRC校验码生成过程。

对于数据11100101（16#E5），以指定除数11011求它的CRC校验码，其过程如下：

使用上面计算的校验和和消息数据，可以创建要传输的码字。

有时候，我们需要填充checksum到制定的位置，这就涉及到字节序问题，建议用memcpy()进行拷贝。

七、代码实现

实现算法参考网络相关代码，进行整理并验证，可直接使用。crc.c

/**一口Linux*2021.6.21*version:1.0.0*/#include"crc.h"#include<stdio.h>typedefenum{REF_4BIT=4,REF_5BIT=5,REF_6BIT=6,REF_7BIT=7,REF_8BIT=8,REF_16BIT=16,REF_32BIT=32}REFLECTED_MODE;uint32_tReflectedData(uint32_tdata,REFLECTED_MODEmode){data=((data&0xffff0000)>>16)|((data&0x0000ffff)<<16);data=((data&0xff00ff00)>>8)|((data&0x00ff00ff)<<8);data=((data&0xf0f0f0f0)>>4)|((data&0x0f0f0f0f)<<4);data=((data&0xcccccccc)>>2)|((data&0x33333333)<<2);data=((data&0xaaaaaaaa)>>1)|((data&0x55555555)<<1);switch(mode){caseREF_32BIT:returndata;caseREF_16BIT:return(data>>16)&0xffff;caseREF_8BIT:return(data>>24)&0xff;caseREF_7BIT:return(data>>25)&0x7f;caseREF_6BIT:return(data>>26)&0x7f;caseREF_5BIT:return(data>>27)&0x1f;caseREF_4BIT:return(data>>28)&0x0f;}return0;}uint8_tCheckCrc4(uint8_tpoly,uint8_tinit,boolrefIn,boolrefOut,uint8_txorOut,constuint8_t*buffer,uint32_tlength){uint8_ti;uint8_tcrc;if(refIn==true){crc=init;poly=ReflectedData(poly,REF_4BIT);while(length--){crc^=*buffer++;for(i=0;i<8;i++){if(crc&0x01){crc>>=1;crc^=poly;}else{crc>>=1;}}}returncrc^xorOut;}else{crc=init<<4;poly<<=4;while(length--){crc^=*buffer++;for(i=0;i<8;i++){if(crc&0x80){crc<<=1;crc^=poly;}else{crc<<=1;}}}return(crc>>4)^xorOut;}}uint8_tCheckCrc5(uint8_tpoly,uint8_tinit,boolrefIn,boolrefOut,uint8_txorOut,constuint8_t*buffer,uint32_tlength){uint8_ti;uint8_tcrc;if(refIn==true){crc=init;poly=ReflectedData(poly,REF_5BIT);while(length--){crc^=*buffer++;for(i=0;i<8;i++){if(crc&0x01){crc>>=1;crc^=poly;}else{crc>>=1;}}}returncrc^xorOut;}else{crc=init<<3;poly<<=3;while(length--){crc^=*buffer++;for(i=0;i<8;i++){if(crc&0x80){crc<<=1;crc^=poly;}else{crc<<=1;}}}return(crc>>3)^xorOut;}}uint8_tCheckCrc6(uint8_tpoly,uint8_tinit,boolrefIn,boolrefOut,uint8_txorOut,constuint8_t*buffer,uint32_tlength){uint8_ti;uint8_tcrc;if(refIn==true){crc=init;poly=ReflectedData(poly,REF_6BIT);while(length--){crc^=*buffer++;for(i=0;i<8;i++){if(crc&0x01){crc>>=1;crc^=poly;}else{crc>>=1;}}}returncrc^xorOut;}else{crc=init<<2;poly<<=2;while(length--){crc^=*buffer++;for(i=0;i<8;i++){if(crc&0x80){crc<<=1;crc^=poly;}else{crc<<=1;}}}return(crc>>2)^xorOut;}}uint8_tCheckCrc7(uint8_tpoly,uint8_tinit,boolrefIn,boolrefOut,uint8_txorOut,constuint8_t*buffer,uint32_tlength){uint8_ti;uint8_tcrc;if(refIn==true){crc=init;poly=ReflectedData(poly,REF_7BIT);while(length--){crc^=*buffer++;for(i=0;i<8;i++){if(crc&0x01){crc>>=1;crc^=poly;}else{crc>>=1;}}}returncrc^xorOut;}else{crc=init<<1;poly<<=1;while(length--){crc^=*buffer++;for(i=0;i<8;i++){if(crc&0x80){crc<<=1;crc^=poly;}else{crc<<=1;}}}return(crc>>1)^xorOut;}}uint8_tCheckCrc8(uint8_tpoly,uint8_tinit,boolrefIn,boolrefOut,uint8_txorOut,constuint8_t*buffer,uint32_tlength){uint32_ti=0;uint8_tcrc=init;while(length--){if(refIn==true){crc^=ReflectedData(*buffer++,REF_8BIT);}else{crc^=*buffer++;}for(i=0;i<8;i++){if(crc&0x80){crc<<=1;crc^=poly;}else{crc<<=1;}}}if(refOut==true){crc=ReflectedData(crc,REF_8BIT);}returncrc^xorOut;}uint16_tCheckCrc16(uint16_tpoly,uint16_tinit,boolrefIn,boolrefOut,uint16_txorOut,constuint8_t*buffer,uint32_tlength){uint32_ti=0;uint16_tcrc=init;while(length--){if(refIn==true){crc^=ReflectedData(*buffer++,REF_8BIT)<<8;}else{crc^=(*buffer++)<<8;}for(i=0;i<8;i++){if(crc&0x8000){crc<<=1;crc^=poly;}else{crc<<=1;}}}if(refOut==true){crc=ReflectedData(crc,REF_16BIT);}returncrc^xorOut;}uint32_tCheckCrc32(uint32_tpoly,uint32_tinit,boolrefIn,boolrefOut,uint32_txorOut,constuint8_t*buffer,uint32_tlength){uint32_ti=0;uint32_tcrc=init;while(length--){if(refIn==true){crc^=ReflectedData(*buffer++,REF_8BIT)<<24;}else{crc^=(*buffer++)<<24;}for(i=0;i<8;i++){if(crc&0x80000000){crc<<=1;crc^=poly;}else{crc<<=1;}}}if(refOut==true){crc=ReflectedData(crc,REF_32BIT);}returncrc^xorOut;}uint32_tCrcCheck(CRC_TypecrcType,constuint8_t*buffer,uint32_tlength){switch(crcType.width){case4:returnCheckCrc4(crcType.poly,crcType.init,crcType.refIn,crcType.refOut,crcType.xorOut,buffer,length);case5:returnCheckCrc5(crcType.poly,crcType.init,crcType.refIn,crcType.refOut,crcType.xorOut,buffer,length);case6:returnCheckCrc6(crcType.poly,crcType.init,crcType.refIn,crcType.refOut,crcType.xorOut,buffer,length);case7:returnCheckCrc7(crcType.poly,crcType.init,crcType.refIn,crcType.refOut,crcType.xorOut,buffer,length);case8:returnCheckCrc8(crcType.poly,crcType.init,crcType.refIn,crcType.refOut,crcType.xorOut,buffer,length);case16:returnCheckCrc16(crcType.poly,crcType.init,crcType.refIn,crcType.refOut,crcType.xorOut,buffer,length);case32:returnCheckCrc32(crcType.poly,crcType.init,crcType.refIn,crcType.refOut,crcType.xorOut,buffer,length);}return0;}

crc.h

/**一口Linux*2021.6.21*version:1.0.0*/#ifndef__CRC_H__#define__CRC_H__#include<stdint.h>#include<stdbool.h>typedefstruct{uint8_twidth;uint32_tpoly;uint32_tinit;boolrefIn;boolrefOut;uint32_txorOut;}CRC_Type;uint32_tCrcCheck(CRC_TypecrcType,constuint8_t*buffer,uint32_tlength);#endif

main.c

/**一口Linux*2021.6.21*version:1.0.0*/#include<stdio.h>#include<stdint.h>#include<stdbool.h>#include"crc.h"#defineLENGTH8constuint8_tdata[3][LENGTH]={{0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08},{0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80},{0xfe,0xfd,0xfb,0xf7,0xef,0xdf,0xbf,0x7f}};typedefstruct{CRC_TypecrcType;uint32_tresult[3];}CRC_Test;CRC_Testcrc4_ITU={{4,0x03,0x00,true,true,0x00},{0x0f,0x0a,0x0e}};CRC_Testcrc5_EPC={{5,0x09,0x09,false,false,0x00},{0x00,0x0c,0x17}};CRC_Testcrc5_ITU={{5,0x15,0x00,true,true,0x00},{0x16,0x0a,0x17}};CRC_Testcrc5_USB={{5,0x05,0x1f,true,true,0x1f},{0x10,0x09,0x17}};CRC_Testcrc6_ITU={{6,0x03,0x00,true,true,0x00},{0x1d,0x30,0x00}};CRC_Testcrc7_MMC={{7,0x09,0x00,false,false,0x00},{0x57,0x30,0x5b}};CRC_Testcrc8={{8,0x07,0x00,false,false,0x00},{0x3e,0xe1,0x36}};CRC_Testcrc8_ITU={{8,0x07,0x00,false,false,0x55},{0x6b,0xb4,0x63}};CRC_Testcrc8_ROHC={{8,0x07,0xff,true,true,0x00},{0x6b,0x78,0x93}};CRC_Testcrc8_MAXIM={{8,0x31,0x00,true,true,0x00},{0x83,0x60,0xa9}};CRC_Testcrc16_IBM={{16,0x8005,0x0000,true,true,0x0000},{0xc4f0,0x2337,0xa776}};CRC_Testcrc16_MAXIM={{16,0x8005,0x0000,true,true,0xffff},{0x3b0f,0xdcc8,0x5889}};CRC_Testcrc16_USB={{16,0x8005,0xffff,true,true,0xffff},{0x304f,0xd788,0x53c9}};CRC_Testcrc16_MODBUS={{16,0x8005,0xffff,true,true,0x0000},{0xcfb0,0x2877,0xac36}};CRC_Testcrc16_CCITT={{16,0x1021,0x0000,true,true,0x0000},{0xeea7,0xfe7c,0x7919}};CRC_Testcrc16_CCITT_FALSE={{16,0x1021,0xffff,false,false,0x0000},{0x4792,0x13a7,0xb546}};CRC_Testcrc16_X25={{16,0x1021,0xffff,true,true,0xffff},{0x6dd5,0x7d0f,0xfa6a}};CRC_Testcrc16_XMODEM={{16,0x1021,0x0000,false,false,0x0000},{0x76ac,0x2299,0x8478}};CRC_Testcrc16_DNP={{16,0x3D65,0x0000,true,true,0xffff},{0x7bda,0x0535,0x08c4}};CRC_Testcrc32={{32,0x04c11db7,0xffffffff,true,true,0xffffffff},{0x3fca88c5,0xe0631a53,0xa4051a26}};CRC_Testcrc32_MPEG2={{32,0x4c11db7,0xffffffff,false,false,0x00000000},{0x14dbbdd8,0x6509b4b6,0xcb09d294}};voidCrcTest(CRC_TestcrcTest){uint32_ti;for(i=0;i<3;i++){printf("%08x\t%08x\r\n",CrcCheck(crcTest.crcType,data[i],LENGTH),crcTest.result[i]);}printf("\r\n");}intmain(void){CrcTest(crc4_ITU);CrcTest(crc5_EPC);CrcTest(crc5_ITU);CrcTest(crc5_USB);CrcTest(crc6_ITU);CrcTest(crc7_MMC);CrcTest(crc8);CrcTest(crc8_ITU);CrcTest(crc8_ROHC);CrcTest(crc8_MAXIM);CrcTest(crc16_IBM);CrcTest(crc16_MAXIM);CrcTest(crc16_USB);CrcTest(crc16_MODBUS);CrcTest(crc16_CCITT);CrcTest(crc16_CCITT_FALSE);CrcTest(crc16_X25);CrcTest(crc16_XMODEM);CrcTest(crc16_DNP);CrcTest(crc32);CrcTest(crc32_MPEG2);return0;}

注意

不同的CRC算法，对00H或FFH数据流的计算结果不一样，部分算法存在校验结果也为00H或FFH的情况（也就意味着存储空间处于初始化状态时：全0或全1，CRC校验反而是正确的），在应用中需要注意避免。

-END-

文章来源于一口Linux，作者土豆居士。如有侵权请联系删除。