我学习CRC32、CRC16、CRC原理和算法的总结(与WINRAR结果一致)

我学习CRC32、CRC16、CRC原理和算法的总结（与WINRAR结果一致）wxleasyland([e-mail])2010年9月2日比较愚钝，学了CRC校验好几天，很痛苦的过程，现终于有眉目了，总结一下。国外版的“轻松无痛苦学习CRC指南”，在（为什么好的资料都是老外写的？）我的英文有限，这种专业性太强的文章，很多都看不太明白，所以没办法翻译，靠参考国内的翻译和自己瞎琢磨的。国内的翻译比较不全，而且有点误导，能看英文的还是看英文吧，国内版资料比较零散，可参考：://://我结合国内资料和英文原版进行总结，达到和WINRAR一样的CRC32计算结果。一、CRC原理可参考=15计算CRC的过程，就是用一个特殊的“除法”，来得到余数，这个余数就是CRC。它不是真正的算术上的除法！过程和算术除法过程一样，只是加减运算变成了XOR（异或）运算！算术上的除法：120÷9＝13余3，120是被除数，9是除数，13是商，3是余数。念作120除以9，或者9除120，或者9去除120！（除法的过程就不写了）这个除法计算机当然会做，但是做起来很麻烦，因为减法有借位，很耗时间和指令!所以，计算CRC也是除法，但是用XOR来代替减法，这就简单多了！CRC的除法：120÷9＝14余6，商、余数和算术除法不一定相同！！因为除法用的是XOR，而不是真正的减法。以二进制模拟这个计算过程：1110商为1110，即14，商有4位，表示进行了4次XOR________1001/1111000被除数120是1111000，除数9是10011001^----1100第一次XOR后得到011，加入下一位0。最高位的0可以消掉了，这样最高位是1,所以下个商是11001^----1010第二次XOR后得到0101，加入下一位0。最高位的0可以消掉了，这样最高位是1,所以下个商是11001^----0110第三次XOR后得到0011，加入下一位0。最高位的0可以消掉了，这样最高位是0,所以下个商是00000^----110-最后一次XOR后得到0110，最高位的0可以消掉了，得到余数为110，即6注意，余数不是0110，而是110，因为最前面那个0已经被XOR后消掉了！可见，除法（XOR）的目的是逐步消掉最高位的1或0！由于过程是XOR的，所以商是没有意义的，我们不要。我们要的是余数。余数110是1111000的CRC吗？不是！余数110是1111（即十进制15）的CRC！！！为什么？因为CRC是和数据一起传送的，所以数据后面要加上CRC。数据1111加上CRC110后，变成1111110，再传送。接收机收到1111110后，除以除数1001，余数为000，正确；如果余数不为0，则说明传送的数据有误！这样完成CRC校验。即发送端要发送1111，先在1111后加000，变成1111000，再除以1001得到余数110，这个110就是CRC，将110加到数据后面，变成1111110，发送出去。接收端收到1111110，用它除以1001，计算得余数为000，就说明收到的数据正确。所以原始数据后面要先扩展出3位0，以容纳CRC值！会发现，在上面的除法过程中，这3位0，能保证所有的4个数据位在除法时都能够被处理到！不然做一次除法就到结果了，那是不对的。这个概念后面要用到。所以，实际上，数据是1111，CRC是110。对于除数1001，我们叫它生成多项式，即生成项，或POLY，即g(x)。数据1111根据POLY1001，计算得到CRC110。如果POLY不是1001，而是1011，那得到的CRC也是不同的！所以生成项不同，得到的CRC也不同。要预先定义好POLY，发送端和接收端要用一样的POLY！二、生成项上面例子中，生成项是1001，共4位比特，最高位的1，实际上在除法的每次XOR时，都要消掉，所以这个1可不做参考，后3位001才是最重要的！001有3位，所以得到的余数也是3位，因为最后一次除法XOR时，最高位消掉了。所以CRC就是3位比特的。CRC是3比特，表示它的宽度W＝3。也就是说，原始数据后面要加上W=3比特的0进行扩展！生成项的最低位也必须是1，这是规定的。生成项1001，就等效于g(x)=x2+1生成项也可以倒过来写，即颠倒过来，写成1001，这里倒过来的值是一样的。再如CRC32的生成项是：100000100110000010001110110110111（33个比特）即g(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1颠倒过来，就可以写成111011011011100010000011001000001一般生成项简写时不写最高位的1，故生成项是0x04C11DB7，颠倒后的生成项是0xEDB88320CRC32的生成项是33比特，最高位是消掉的，即CRC值是32比特（4个字节），即宽度W=32，就是说，在计算前，原始数据后面要先扩展W=32个比特0，即4个0x00字节。注意：我看到网上CRC32的POLY有0x04C10DB7这个值的，它和正规的POLY值不同，需要注意！颠倒过来，即是镜像，为什么要颠倒，后述。三、直接计算法StraightforwardCRCImplementation“直接计算法”就是直接模拟上面的除法的过程，来得到余数即CRC！上面的例子中，除数是4位，但最高位是要一直消掉的，所以我们只需要一个3位的寄存器就好了。计算过程：待测数据后扩展W=3个比特0，变成1111000；寄存器初始化置0；先在寄存器中移入数据111；寄存器左移一位，并且右边移入下一位数据1。这样最高位1移出，由于最高位是1，故本次的商是1，要用除数1001来进行XOR，最高位肯定XOR得0，故不管它，只要用低3位001来进行XOR就可以，即001对寄存器进行XOR，寄存器中得到110，即第一次XOR后的结果（相当于是数据1111与生成项1001进行了一次XOR，并把最高位0消掉了）。如果移出的最高位是0，则用0000来进行XOR（0XOR后，得到的还是原值）。一直重复这个过程，就能得到最后余数了。总共处理次数＝商的位数＝待测数据的位数－生成项位数＋1＋宽度W＝待测数据的位数＝4次。我们假设待测数据是1101011011，生成项是10011，假设有一个4bits的寄存器，通过反复的移位和进行CRC的除法，最终该寄存器中的值就是我们所要求的余数。3210Bits+---+---+---+---+Pop--|||||-----Augmentedmessage（已加0扩张的原始数据）+---+---+---+---+10011=ThePoly生成项依据这个模型，我们得到了一个最最简单的算法：把register中的值置0.把原始的数据后添加w个0.While(还有剩余没有处理的数据)Begin把register中的值左移一位，读入一个新的数据并置于register最低位的位置。If(如果上一步的左移操作中的移出的一位是1)register=registerXORPoly.End实际上就是模拟XOR除法的过程，即被测数据一位一位放到寄存器中来做除法。比如生成项是10011，则生成的余数是4位XXXX，所以寄存器是4位。待测数据是1101011011，后面加上0000，即扩张4位，以容纳余数。只要与生成项的0011做XOR就好了，最高位经过XOR肯定出0，可不用最高位。过程如下：待测数据先移4位即1101到寄存器中，准备开始除法。第1次除法：寄存器中是1101，先从寄存器移出最高位1，移进下一位待测数据位0，则寄存器中是1010，由于移出的位是1，则需要与生成项的0011做XOR，得到1001，即做了第1次除法后，寄存器中是1001，这个就是余数。第2次除法：寄存器中是1001，从寄存器移出最高位1，移进下一位待测数据位1，则寄存器中是0011，由于移出的位是1，则需要与生成项的0011做XOR，得到0000，即做了第2次除法后，寄存器中是0000，这个就是余数。第3次除法：寄存器中是0000，从寄存器移出最高位0，移进下一位待测数据位1，则寄存器中是0001，由于移出的位是0，则需要不做XOR，直接下一步移位。也可以等同于：本次的商是0,0*生成项＝0，即是0000与寄存器做XOR，得到寄存器的数不变，还是0001，即做了第3次除法后，寄存器中是0001，这个就是余数。第4次除法：寄存器中是0001，从寄存器移出最高位0，移进下一位待测数据位0，则寄存器中是0010，由于移出的位是0，则需要不做XOR，直接下一步移位。第5次除法：移位，不用做XOR，得到寄存器中是0101第6次除法：移位，不用做XOR，得到寄存器中是1011第7次除法：移位，移出的位是1，又要与生成项做XOR了一直做下去。。。。。。直到最后，寄存器中的就是整个计算后的余数了。即CRC值。注意：这个算法，计算出的CRC32值,与WINRAR计算出来的不一样，为什么？算法是正确的，不用怀疑！只是CRC32正式算法还涉及到数据颠倒和初始化预置值等，后述。程序实现：程序1：（注：网上下的程序是有错的，我有修改了，这里是正确的）//网上的程序经修改BYTEPOLY=0x13;//生成项，13H＝10011，这样CRC是4比特unsignedshortdata=0x035B;//待测数据是35BH，12比特，注意，数据不是16比特unsignedshortregi=0x0000;//loadtheregisterwithzerobits//augmentthedatabyappendingW(4)zerobitstotheendofit.//按CRC计算的定义，待测数据后加入4个比特0，以容纳4比特的CRC；//这样共有16比特待测数据，从第5比特开始做除法，就要做16－5＋1＝12次XORdata=4;//wedoitbitafterbitfor(intcur_bit=15;cur_bit=0;--cur_bit)//处理16次，前4次实际上只是加载数据{//testthehighestbitwhichwillbepopedlater.///infact,the5thbitfromrightisthehightestbithereif(((regi4)&0x0001)==0x1)regi=regi^POLY;regi=1;//shifttheregister//readingthenextbitoftheaugmenteddataunsignedshorttmp=(datacur_bit)&0x0001;//加载待测数据1比特到tmp中，tmp只有1比特regi|=tmp;//这1比特加载到寄存器中}if(((regi4)&0x0001)==0x1)regi=regi^POLY;//做最后一次XOR//这时，regi中的值就是CRC程序2：我做的通用CRC计算程序：_int64POLY=0x104C11DB7;//生成项，需要含有最高位的1，这样CRC是32比特intcrcbitnumber=32;//crc是32比特_int64data=0x31323334;//待测数据，为字串1234intdatabitnumber=32;//数据是32比特_int64regi=0x0;//loadtheregist