文档介绍：CRC校验算法CRC(CyclicRedundancyCheck)循环冗余校验是常用的数据校验方法,讲CRC算法的文章很多,之所以还要写这篇,是想换一个方法介绍CRC算法,希望能让大家更容易理解CRC算法。先说说什么是数据校验。数据在传输过程(比如通过网线在两台计算机间传文件)中,由于传输信道的原因,可能会有误码现象(比如说发送数字5但接收方收到的却是6),如何发现误码呢?方法是发送额外的数据让接收方校验是否正确,这就是数据校验。最容易想到的校验方法是和校验,就是将传送的数据(按字节方式)加起来计算出数据的总和,并将总和传给接收方,接收方收到数据后也计算总和,并与收到的总和比较看是否相同。如果传输中出现误码,那么总和一般不会相同,从而知道有误码产生,可以让发送方再发送一遍数据。CRC校验也是添加额外数据做为校验码,这就是CRC校验码,那么CRC校验码是如何得到的呢?非常简单,CRC校验码就是将数据除以某个固定的数(比如ANSI-CRC16中,这个数是0x18005),所得到的余数就是CRC校验码。那这里就有一个问题,我们传送的是一串字节数据,而不是一个数据,怎么将一串数字变成一个数据呢?这也很简单,比如说2个字节B1,B2,那么对应的数就是(B1<<8)+B2;如果是3个字节B1,B2,B3,那么对应的数就是((B1<<16)+(B2<<8)+B3),比如数字是0x01,0x02,0x03,那么对应的数字就是0x10203;依次类推。如果字节数很多,那么对应的数就非常非常大,不过幸好CRC只需要得到余数,而不需要得到商。从上面介绍的原理我们可以大致知道CRC校验的准确率,在CRC8中出现了误码但没发现的概率是1/256,CRC16的概率是1/65536,而CRC32的概率则是1/2^32,那已经是非常小了,所以一般在数据不多的情况下用CRC16校验就可以了,而在整个文件的校验中一般用CRC32校验。这里还有个问题,如果被除数比除数小,那么余数就是被除数本身,比如说只要传一个字节,那么它的CRC就是它自己,为避免这种情况,在做除法之前先将它移位,使它大于除数,那么移多少位呢?这就与所选的固定除数有关了,左移位数比除数的位数少1,下面是常用标准中的除数:CRC8:多项式是X8+X5+X4+1,对应的数字是0x131,左移8位CRC12:多项式是X12+X11+X3+X2+1,对应的数字是0x180D,ITTCRC16:多项式是X16+X12+X5+1,对应的数字是0x11021,左移16位ANSICRC16:多项式是X16+X15+X2+1,对应的数字是0x18005,左移16位CRC32:多项式是X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1,对应数字是0x104C11DB7,左移32因此,在得到字节串对应的数字后,再将数字左移M位(比如ANSI-CRC16是左移16位),就得到了被除数。好了,现在被除数和除数都有了,那么就要开始做除法求CRC校验码了。CRC除法的计算过程与我们笔算除法类似,首先是被除数与除数高位对齐后,被除数减去除数,得到了差,除数再与差的最高位对齐,进行减法,然后再对齐再减,直到差比除数小,这个差就是余数。不过和普通减法有差别的是,CRC的加(减)法是不进(借)位的,比如10减01,它的结果是11,而不是借位减法得到的01,因此,实际上CRC的加法和减法所得的结果是一样的,比如10加01的结果是11,10减01的结果也是11,这其实就是异或操作。虽然说了这么多也不一定能说清楚,我们还是看一段CRC除法求余程序吧:/*这段程序是求数据0x880000除以0x11021的余数*//*这段程序其实也就是求字节0x88的CRC16校验码,因为0x88左移16位是0x880000*/unsignedshortcrc16_div(){unsignedlongdata=0x880000;itt16=0x11021;/*这是比较值,被除数与它比较看是否需要减去除数注意,这里只需要与0x10000比较就可以了,而不需要与除数0x18005比较,这样可以少很多计算而且余数的范围就在0-0xFFFF之间,而不是0-0x18004之间了*/unsignedlongcmp_value=0x10000;itt16<<=7;/*左移7位,与被除数最高位对齐*/cmp_value<<=7;/*左移7位,与被除数最高位对齐*/while(cmp_value>=0x10000)/*循环直到差数比cmp_value小*/{if((data&cmp_value)!=0)/*最高位为1,则减去除数*/{data^=ccitt16;/*做CRC的减法,就是异或操作*/}else/*最高位为0,不