CRC算法详解与c源码.docx

CRC计算方法详解与c源码 循环冗余码（CRC，cyclic redundancy code）校验技术是一种十分有效的数据传输错误检测技术，能检验一位错、双位错、所有的奇数错、所有长度小于或等于所用的生成多项式长度的错误，在通信系统、控制系统中得到广泛运用。 计算CRC校验码和验证报文是否有误，总是由计算机实时地完成的，手工计算仅仅用于说明CRC校验码的生成原理。由于实时性的要求，必须使用快捷的计算机计算方法。CRC校验原理 在k位信息码后再拼接r位的校验码，报文编码长度为n位，因此，这种编码又叫（n，k）码。对于一个给定的（n，k）码，可以证明,存在一个最高次幂为n=k+r的多项式G(x)，存在且仅存在一个R次多项式G(x)，使得。其中:m(x)为k次信息多项式，r(x)为r-1次校验多项式，g(x)称为生成多项式：。发送方通过指定的G(x)产生r位的CRC校验码，接收方则通过该G(x)来验证收到的报文码的CRC校验码是否为0。 假设发送信息用信息多项式C(X)表示，将C(x)左移r位，则可表示成C(x)*2r，这样C(x)的右边就会空出r位校验码的位置，做除法（模2除），得到的余数R就是校验码。发送的CRC编码是,验证接收到的报文编码是否至正确，依然是做模2除：。CRC的生成多项式 生成多项式的选取应满足以下条件： a、生成多项式的最高位和最低位必须为1。 b、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做模2除后，应该使余数不为0。 c、不同位发生错误时，应该使余数不同。 d、对余数继续做模2除，应使余数循环。 主要的生成多项式G(x)有以下几种：名称生成多项式数值式简记式标准引用CRC-16x16+x15+x2+10x180058005IBM SDLCCRC-CCITTx16+x12+x5+10X110210x1021ISO HDLC，ITU X.25，V.34/V.41/V.42，PPP-FCSCRC-32注*0X104C11DB70x04C11DB7ZIP，RAR，IEEE 802 LAN/FDDI，IEEE1394，PPP-FCS注* x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 下表中的生成多项式G(x)也常见的：名称生成多项式数值式简记式标准引用CRC-4x4+x+10x130x3ITU G.704CRC-8x8+x5+x4+10x1310x31CRC-8x8+x2+x1+10x1070x07CRC-8x8+x6+x4+x3+x2+x10x15E0x5ECRC-12x12+x11+x3+x2+x+10x180F0x80FCRC-32c注*0X11EDC6F410x1EDC6F41SCTP注* x32+x28+x27+x26+x25+x23+x22+x20+x19+x18+x14+x13+x11+x10+x9+x8+x6+1CRC校验码的手工计算 CRC的手工计算，就是按普通的二进制竖式除法的格式做模2除法。由于我们需要的是余数，不必关心商的大小，所以，可以不用写出商，而直接进行一次次移位和模2减。具体计算过程是： a. 在信息码后面加上r（即CRC校验码的位数）个0，作为被除数，让除数（即生成多项式）的最高位1，对齐被除数的最高位1。 b. 做模二减：如果被除数最高位为1，减生成多项式，余数作为中间余数，否则，不减。 c. 生成多项式右移1位。 e. 反复进行步骤b，c，直到余数与a中添加的r个0在位置上对齐，该余数就是最终余数，即信息码的CRC校验码。16位CRC校验码的计算机 本节使用的生成多项式为G16= x16+x12+x5+1=0x11021。在计算机程序中，因为16位rcr校验码的生成多项式总宽度为17，而最高位为1，故多占用一个8位寄存器。然而，在模2除的过程中，多项式的最高位1总是与被除数（或中间余数）的最左边的1对齐，而相异或的结果总是为0。这样，在程序中可以把生成多项式的最高位1去掉，而只包含后面的16位，例如，将0x11021简化为0x1021,称做生成多项式简化式。 用左移位模2除求余数时，在异或前，检查被除数（或中间余数）的最高位否为1，如果为1，被除数（或中间余数）左移1位，与生成多项式简化式异或；如果为0，被除数（或中间余数）左移1位，不做其它操作。总的移位次数为“被除数的位数-除数（生成多项式简化式）的位数”。 1 模拟手工移位计算相 设n个字节信息数据Bn-1，Bn-2，.，B1，B0，用生成多项式CRC16-CCITT计算crc。 1设置一个32bit的变量，例如crc0。Bn-1，Bn-2，Bn-3，Bn-4依次放入crc0。如果n4，后面的字节为0。 2Crc0左移1位，检查移出位，如果为1，crc与生成多项式简化式异或，结果存入crc。如果不为1，则不做异或。 3上一步重复8次后，右端空出1个字节的位置，将下一个信息字节补入。 4重复2，3两步，直到信息数据全部取完。crc右移16位，crc中的内容即为CRC校验杩。/f1 仿手工，逐位移位unsigned short f1(unsigned char *mess,unsigned int len) unsigned int crc0=0; unsigned int div=0x1021*0x10000; unsigned int i,j; for(j=0;j4;j+) /crc0中至少填入4个信息字节 crc0=crc08; /信息字节数少于4时，用0补齐 if(jlen) crc0=crc0*mess; mess+; for(j=0;jlen;j+) /左移位（len8)次 for(i=0;i8;i+) /逐位异或 if(crc0&0x80000000)!=0) crc0=crc01; crc0=crc0div; else crc0=crc01; if(j+416; return crc0; /将32位数变为16位数 2 根据前k 位信息码的CRC校验码移位计算前k+1位信息码的CRC校验码 计算前k位信息码mk的crc校验码： 。式中，rk即为前k位信息码mk的crc校验码。 若在前k位信息码之后的一位为bi，计算mk+1的crc校验码： 。 按位移位计算mk+1的crc校验码的方法可表述为：(的余数)+(的余数)。求的余数，只需要进行1次左移位除，求的余数，采用查表的方法，默认0的余数为0，1的余数为0x1021。/f2 根据前n位的crc码计算前n+1位的crc码，逐位移位unsigned short f2(unsigned char *mess,unsigned len) unsigned int crc0=0; unsigned char i; while(len-!=0) for(i=0x80;i!=0;i=1) /0的余数为0,1的余数为1021 if(crc0&0x8000)!=0) /先求的余数 crc0=1; crc0=0x1021; else crc0=1; if(*mess&i)!=0) crc0=0x1021; /再加上的余数 mess+; return crc0; 3 根据前k 字节信息码的CRC校验码移位计算前k+1字节信息码的CRC校验码 计算前k字节信息码的crc校验码： 。式中，Rk即为前k字节信息码Mk的crc校验码。 若在前k字节信息码之后的一字节为Mi，计算Mk+1的crc校验码： 。 按字节移位计算Mk+1的crc校验码的方法表述为：，左移位除8次。/f3 根据前n字节的crc码计算前n+1字节的crc码，逐位移位unsigned short f3(unsigned char *mess,unsigned len) unsigned short crc0=0; unsigned short i; while(len-) crc0=crc0*mess1) /8次移位除 if(crc0&0x8000)!=0) crc0=crc01; crc0=crc00x1021; else crc0=crc01; mess+; return crc0; 4 根据前k 字节信息码的CRC校验码查表计算前k+1字节信息码的CRC校验码 计算前k字节信息码的crc校验码： Rk即为前k字节信息码Mk的crc校验码。 。 将Rk分解为高字节（高8位）和低字节（低8位）两部分 如果在Mk之后增加一个字节Mi，则k+1个字节的数据序列可以表示为：，计算Mk+1的CRC校验码： 。 / 按查字节表计算mk+1的crc校验码的语言表述为：(Rkh8+mi)查字节表+Rk8/f4 根据前n字节的crc码计算前n+1字节的crc码，按字节查表unsigned short f4(unsigned char *mess,unsigned len) unsigned short crc0=0; unsigned short crc; unsigned short i; for(i=0;i8)*mess; /对异或结果从表中查余数，得本次中间余数 crc0=crc(crc08); /与本次中间余数异或，得本次余数 mess+; return crc0; 5 根据前k 字节信息码的CRC校验码按高低半字节查表计算前k+1字节信息码的CRC校验码 已求得。 对上式继续变换： 。 查高低半字节表计算mk+1的crc校验码的语言表述为：查h表+查l表+。/f5 根据前n字节的crc码计算前n+1字节的crc码，分别按高低半字节查表unsigned short f5(unsigned char *mess,unsigned len) unsigned short crc0=0; unsigned short crc; unsigned short i; for(i=0;i8)*mess; /前次余数高字节与本次数据异或 crc0=remBh4(crc&0xf0)4remBl4crc&0x0f(crc08); /2个余数与前次余数低字节异或 mess+; return crc0; 6 根据前k 半字节信息码的CRC校验码查表计算前k+1半字节信息码的CRC校验码 计算前k半字节信息码的crc校验码： 。 Rk为16bit余数，即为CRC校验码。 如果在Mk之后增加一个半字节Mi，则k+1个半字节的数据序列可以表示为：，计算Mk+1的CRC校验码： 。 / 查半字节表计算mk+1的crc校验码的语言表述为：查半字节表+()。示例程序中，每次取1个字节，所以分两次分别计算前半字节和后半字节。/f6 根据前n半字节的crc码计算前n+1半字节的crc码，按低半字节查表unsigned short f6(unsigned char *mess,unsigned int len) unsigned short crc0=0; unsigned char crc0_m; unsigned char i; for(i=0;i12); /得到前次余数的最高4位 crc0=crc04); /相加后得本次中间余数 /一个字节的低半字节 crc0_m=(unsigned char)(crc012); /得到本次中间余数的最高4位 crc0=crc04; /本次中间余数右移4位，使最低4位为0 crc0=crc0rem05crc0_m(*mess&0x0f); /相加后得本次余数 mess+; return crc0; 7 余数表计算 计算余数表采用仿手工算法，以单字节数0-255为索引的crc-ccitt的余数表，其256项，512个字节。余数用printf函数输出到开发环境的不i/o窗口，将余数表复制下来，在函数中建立一个常量数组，将余数表粘贴到数组中。另一个比较好的办法是，建立一个头文件，例如crc_32.h，在其中建立一个常量数组，将余数表粘贴到数组中。unsigned short crc01(void) unsigned short remain; unsigned short i,j; for(j=0;j256;j+) remain=j8; for(i=0;i8;i+) if(remain&0x8000)!=0) remain=1; remain=0x1021; else remain=1; printf(0x%04x, ,remain); /16进制输出，4位宽度，不足4位左端补0 if(j+1)%8=0) printf(n); return 0;32位CRC校验码的计算机计算 32位CRC校验码的算法与16位CRC校验码的算法以及c源码，同出一辙，差别在于crc校验码的位数不同，因而在公式推导和程序的变量设置上略有不同。鉴于计算32位校验码的实际情况，相应于6位crc校验码的f1-f6，以下仅给出f1，f3，f4，3个公式的推导的示例程序。G32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1=0x104C11DB7。 1 模拟手工移位计算/f1 仿手工，逐位移位unsigned long hand(unsigned char *byt,unsigned int len) unsigned char buff_ch=0; unsigned long crc=0; unsigned int i,j; for(j=0;j4;j+) /data中至少填入4个信息字节 crc=8; /信息字节数少于4时，用0补齐 if(jlen) crc=*byt; byt+; if(jlen) buff_ch=*byt; byt+; for(j=0;jlen;j+) /左移位（len8)次 for(i=0;i8;i+) /逐位异或 if(crc&0x80000000)!=0) crc=1; if(buff_ch&0x80)!=0) crc=0x00000001; crc= 0x04C11DB7; else crc=1; if(buff_ch&0x80)!=0) crc=0x00000001; buff_ch=1; if(j+5len) /信息字节是否已经读取完毕 buff_ch=*byt; /未完则继续读取 byt+; return crc; 2 根据前k 字节信息码的CRC校验码移位计算前k+1字节信息码的CRC校验码 计算前k字节信息码的crc校验码： 。 式中Rk即为前k字节信息码Mk的crc校验码。 若在前k字节信息码之后的一字节为Mi，计算Mk+1的crc校验码： 。 按字节移位计算Mk+1的crc校验码方法表述为：，左移位除8次。即，单字节的Mi与4字节的Rk的最高位字节相异或，然后，进行左移位除8次。/f3unsigned long f3(unsigned char *mess,unsigned int len) unsigned long crc0=0; unsigned long i; while(len-) crc0=crc0(*mess24); for(i=0;i8;i+) if(crc0&0x80000000)!=0) crc0=1; crc0=0x04C11DB7; else crc0=1; mess+; return crc0; 4 根据前k 字节信息码的CRC校验码查表计算前k+1字节信息码的CRC校验码 为了计算32bit的CRC码，应将Mk向左移32位，再除以33bit的生成多项