CRC32CRC16CRC原理及算法.docx
- 文档编号:17940830
- 上传时间:2023-08-05
- 格式:DOCX
- 页数:46
- 大小:36.45KB
CRC32CRC16CRC原理及算法.docx
《CRC32CRC16CRC原理及算法.docx》由会员分享,可在线阅读,更多相关《CRC32CRC16CRC原理及算法.docx(46页珍藏版)》请在冰点文库上搜索。
CRC32CRC16CRC原理及算法
我学习CR
C32、"CR
C16、"CRC原理和算法的总结(与WINRAR结果一致)
比较愚钝,学了CRC校验好几天,很痛苦的过程,现终于有眉目了,总结一下。
国外版的“轻松无痛苦学习CRC指南”,在
http:
31."html
(为什么好的资料都是老外写的?
)我的英文有限,这种专业性太强的文章,很多都看不太明白,所以没办法翻译,靠参考国内的翻译和自己瞎琢磨的。
国内的翻译比较不全,而且有点误导,能看英文的还是看英文吧,国内版资料比较零散,可参考:
http:
10190."html
http:
."shtml
http:
1637."htm
我结合国内资料和英文原版进行总结,达到和WINRAR一样的CRC32计算结果。
一、"CRC原理
可参考http:
计算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/11000被除数120是11000,除数9是1001
1001^
----
1100第一次XOR后得到011,加入下一位
0。
"最高位的0可以消掉了,这样最高位是1,所以下个商是1
1001^
----
10第二次XOR后得到01,加入下一位
0。
"最高位的0可以消掉了,这样最高位是1,所以下个商是1
1001^
----
0110第三次XOR后得到0011,加入下一位
0。
"最高位的0可以消掉了,这样最高位是0,所以下个商是0
00^
----
110->最后一次XOR后得到0110,最高位的0可以消掉了,得到余数为110,即6注意,余数不是0110,而是110,因为最前面那个0已经被XOR后消掉了!
可见,除法(XOR)的目的是逐步消掉最高位的1或0!
由于过程是XOR的,所以商是没有意义的,我们不要。
我们要的是余数。
余数110是11000的CRC吗?
不是!
余数110是11(即十进制15)的CRC!
!
!
为什么?
因为CRC是和数据一起传送的,所以数据后面要加上CRC。
数据11加上CRC110后,变成1110,再传送。
接收机收到1110后,除以除数1001,余数为000,正确;如果余数不为0,则说明传送的数据有误!
这样完成CRC校验。
即发送端要发送11,先在11后加000,变成11000,再除以1001得到余数110,这个110就是CRC,将110加到数据后面,变成1110,发送出去。
接收端收到1110,用它除以1001,计算得余数为000,就说明收到的数据正确。
所以原始数据后面要先扩展出3位0,以容纳CRC值!
会发现,在上面的除法过程中,这3位0,能保证所有的4个数据位在除法时都能够被处理到!
不然做一次除法就到结果了,那是不对的。
这个概念后面要用到。
所以,实际上,数据是11,CRC是
110。
"
对于除数1001,我们叫它生成多项式,即生成项,或POLY,即g(x)。
数据11根据POLY1001,计算得到CRC
110。
"
如果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的生成项是:
1000100110000010001110110110111(33个比特)
即g(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1颠倒过来,就可以写成1110110110111000100000110010001
一般生成项简写时不写最高位的1,故生成项是0x04C11DB7,颠倒后的生成项是0xEDB88320
CRC32的生成项是33比特,最高位是消掉的,即CRC值是32比特(4个字节),即宽度W=32,就是说,在计算前,原始数据后面要先扩展W=32个比特0,即4个0x00字节。
注意:
我看到网上CRC32的POLY有0x04C10DB7这个值的,它和正规的POLY值不同,需要注意!
颠倒过来,即是镜像,为什么要颠倒,后述。
三、直接计算法StraightforwardCRCImplementation
“直接计算法”就是直接模拟上面的除法的过程,来得到余数即CRC!
上面的例子中,除数是4位,但最高位是要一直消掉的,所以我们只需要一个3位的寄存器就好了。
计算过程:
待测数据后扩展W=3个比特0,变成11000;
寄存器初始化置0;
先在寄存器中移入数据111;
寄存器左移一位,并且右边移入下一位数据
1。
"这样最高位1移出,由于最高位是1,故本次的商是1,要用除数1001来进行XOR,最高位肯定XOR得0,故不管它,只要用低3位001来进行XOR就可以,即001对寄存器进行XOR,寄存器中得到110,即第一次XOR后的结果(相当于是数据11与生成项1001进行了一次XOR,并把最高位0消掉了)。
如果移出的最高位是0,则用00来进行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位XX,所以寄存器是4位。
待测数据是1101011011,后面加上00,即扩张4位,以容纳余数。
只要与生成项的0011做XOR就好了,最高位经过XOR肯定出0,可不用最高位。
过程如下:
待测数据先移4位即1101到寄存器中,准备开始除法。
第1次除法:
寄存器中是1101,先从寄存器移出最高位1,移进下一位待测数据位0,则寄存器中是10,由于移出的位是1,则需要与生成项的0011做XOR,得到1001,即做了第1次除法后,寄存器中是1001,这个就是余数。
第2次除法:
寄存器中是1001,从寄存器移出最高位1,移进下一位待测数据位1,则寄存器中是0011,由于移出的位是1,则需要与生成项的0011做XOR,得到00,即做了第2次除法后,寄存器中是00,这个就是余数。
第3次除法:
寄存器中是00,从寄存器移出最高位0,移进下一位待测数据位1,则寄存器中是0001,由于移出的位是0,则需要不做XOR,直接下一步移位。
也可以等同于:
本次的商是0,0*生成项=0,即是00与寄存器做XOR,得到寄存器的数不变,还是0001,即做了第3次除法后,寄存器中是0001,这个就是余数。
第4次除法:
寄存器中是0001,从寄存器移出最高位0,移进下一位待测数据位0,则寄存器中是0010,由于移出的位是0,则需要不做XOR,直接下一步移位。
第5次除法:
移位,不用做XOR,得到寄存器中是01
第6次除法:
移位,不用做XOR,得到寄存器中是1011
第7次除法:
移位,移出的位是1,又要与生成项做XOR了
一直做下去。
。
。
。
。
。
直到最后,寄存器中的就是整个计算后的余数了。
即CRC值。
注意:
这个算法,计算出的CRC32值,与WINRAR计算出来的不一样,为什么?
算法是正确的,不用怀疑!
只是CRC32正式算法还涉及到数据颠倒和初始化预置值等,后述。
程序实现:
程序1:
(注:
网上下的程序是有错的,我有修改了,这里是正确的)
//网上的程序经修改
BYTEPOLY=0x13;//生成项,13H=10011,这样CRC是4比特
unsignedshortdata=0x035B;//待测数据是35BH,12比特,注意,数据不是16比特
unsignedshortregi=0x00;//loadtheregisterwithzerobits
//augmentthedatabyappendingW
(4)zerobitstotheendofit.
//按CRC计算的定义,待测数据后加入4个比特0,以容纳4比特的CRC;//这样共有16比特待测数据,从第5比特开始做除法,就要做16-5+1=12次XORdata<<=4;
//wedoitbitafterbit
for(intcur_bit=15;cur_bit>=0;--cur_bit)//处理16次,前4次实际上只是加载数据{//testthehighestbitwhichwillbepopedlater.
///infact,the5thbitfromrightisthehightestbithere
if(((regi>>4)&0x0001)==0x1)regi=regi^POLY;
regi<<=1;//shifttheregister
//readingthenextbitoftheaugmenteddata
unsignedshorttmp=(data>>cur_bit)&0x0001;//加载待测数据1比特到tmp中,tmp只有1比特
regi|=tmp;//这1比特加载到寄存器中}if(((regi>>4)&0x0001)==0x1)regi=regi^POLY;//做最后一次XOR
//这时,regi中的值就是CRC
程序2:
我做的通用CRC计算程序:
_int64POLY=0x104C11DB7;//生成项,需要含有最高位的"1",这样CRC是32比特intcrcbitnumber=32;//crc是32比特
_int64data=0x;//待测数据,为字串"1234"
intdatabitnumber=32;//数据是32比特
_int64regi=0x0;//loadtheregisterwithzerobits
//augmentthedatabyappendingWzerobitstotheendofit.
//按CRC计算的定义,加入32个比特0,以容纳32比特的CRC;
//这样共有64比特待测数据,从第33比特开始做除法,就要做64-33+1=32次XOR
data<<=crcbitnumber;
//wedoitbitafterbit
for(intcur_bit=databitnumber+crcbitnumber-1;cur_bit>=0;--cur_bit)//处理64次(32比特待测数据+32比特扩展0),前32次是加载数据{//testthehighestbitwhichwillbepopedlater.
///infact,the5thbitfromrightisthehightestbithere
if(((regi>>crcbitnumber)&0x0001)==0x1)regi=regi^POLY;
regi<<=1;//shifttheregister
//readingthenextbitoftheaugmenteddata
unsignedshorttmp=(data>>cur_bit)&0x0001;//加载待测数据1比特到tmp中,tmp只有1比特
regi|=tmp;//这1比特加载到寄存器中}if(((regi>>crcbitnumber)&0x0001)==0x1)regi=regi^POLY;//做最后一次XOR
//这时,regi中的值就是CRC
四、驱动表法Table-DrivenImplementation
上面的“直接计算法”很直观,却非常的低效。
为了加快它的速度,我们使它一次能处理大于4bit的数据。
一次能处理一个字节的数据的话,那就方便多了。
我们想要实现的32bit的CRC校验。
我们还是假设有和原来一样的一个4"bit"的register,但它的每一位是一个8bit的字节。
3210Bytes
+----+----+----+----+
Pop!
<--|||||<-----Augmentedmessage(扩展0后的数据)
+----+----+----+----+
1<------32bits------>(生成项,暗含了一个最高位的“1”)
根据同样的原理我们可以得到如下的算法:
While(还有剩余没有处理的数据)
Begin
检查register头字节,并取得它的值
求不同偏移处多项式的XOR
register左移一个字节,最右处存入新读入的一个字节
把register的值和多项式的XOR结果进行XOR运算
End
可是为什么要这样作呢?
同样我们还是以一个简单的例子说明问题:
为了简单起见,我们假设一次只移出4个比特!
而不是8个比特。
生成多项式为:
1011100,即宽度W=8,即CRC8,这样寄存器为8位待测数据是101101001101
按正常的算法做:
将10110100放入寄存器中,然后开始计算CRC。
先将高4位移出寄存器:
当前register中的值:
01001101
4bit应该被移出的值:
1011
生成多项式为:
1011100
第一步:
TopRegister(top指移出的数据)
------------
101101001101待测数
1011100+(CRCXOR)POLY
-------------
0001101101第一次XOR后的值
第二步:
这时,首4bits不为0说明没有除尽,要继续除:
0001101101
1011100+(CRCXOR)将POLY右移3位后,再做XOR
-------------
00110001第二次XOR后的值
^^^^
这时,首4bits全0说明不用继续除了,结果满足要求了。
也就是说:
待测数据与POLY相XOR,得到的结果再与POLY相XOR,POLY要适当移位,以消掉
1。
"重复进行,直到结果满足要求。
下面,我们换一种算法,来达到相同的目的:
POLY与POLY自已先进行XOR,当然POLY要进行适当移位。
使得得到的结果值的高4位与待测数据相同。
第一步:
1011100POLY
1011100+右移3位后的POLY
-------------
101110111100POLY与POLY自已进行XOR后得到的值
第二步:
101110111100POLY相XOR后得到的值
101101001101+待测数据
-------------
00110001得到的结果值和上面是一样的(说明可以先把POLY预先XOR好,再与待测数据XOR,就能得到结果)
结论:
现在我们看到,这二种算法计算的结果是一致的!
这是基于XOR的交换律,即(aXORb)XORc=aXOR(bXORc)。
而后一种算法可以通过查表来快速完成,叫做“驱动表法”算法。
也就是说,根据4bit被移出的值1011,我们就可以知道要用POLY自身XOR后得到的101110111100来对待测数据101101001101进行XOR,这样一次就能消掉4BIT待测数据。
(注意蓝色的最高4位要一样,这样XOR后才能得00,就能消掉了)
即1011对应101110111100,实际只需要用到后8位,即1011对应10111100用查表法来得到,即1011作为索引值,查表,得到表值1011
1100。
"
表格可以预先生成。
这里是每次移出4位,则POLY与POLY进行XOR的组合有2^4=16种,即从00到
11。
"
注意,POLY自身与自身相XOR时,要先对齐到和寄存器一样的长度,再XOR。
相当于有12位进行XOR。
组合后的结果有16种:
(黑色的0表示对齐到和寄存器一样的长度)
1.000000即表示待测数据移出的4位都是0,不需要与POLY相XOR,即相当于待测数据移出的4位后,与000000相XOR
2.0001011100即表示待测数据移出的4位是0001,需要与右移过3位的POLY相XOR
3.001010111000
4.001010111000与0001011100相XOR,XOR后前4位为0011即表示待测数据移出的4位后,需要与POLY进行二次相XOR,结果才能满足要求。
5.01011100与0001011100相XOR,XOR后前4位为0100
6.01011100,前4位为01
7.01011100与00101011
1000、"0001011100相XOR,XOR后前4位为0110
8.01011100与001010111000,XOR后前4位为0111
9.10111000与001010111000相XOR,XOR后前4位为1000
1
0."10111000与00101011
1000、"0001011100相XOR,XOR后前4位为1001
1
1."10111000,前4位为10
1
2."10111000与0001011100相XOR,XOR后前4位为1011
1
3."10111000与010111
00、"00101011
1000、"0001011100相XOR,XOR后前4位为1100
1
4."10111000与010111
00、"001010111000相XOR,XOR后前4位为1101
1
5."10111000与010111
00、"0001011100相XOR,XOR后前4位为
111016."10111000与01011100相XOR,XOR后前4位为11
以XOR后得到的结果的前4位做为索引值,以XOR后得到的结果的后8位做为表值,生成一张表,即:
TABLE[0]=0000B;
TABLE[1]=011100B;
TABLE[2]=10111000B;
TABLE[3]=[(001010111000B^0001011100B)>>4]&0xff
....
这张表我叫它为“直接查询表”。
就是说,一次移出的待测数据的4位bit,有2^4个值,即00,0001,0010,....,11,根据这个值来查表,找到相应的表值,再用表值来XOR寄存器中的待测数据。
所以,如果一次移出待测数据的8位bit,即一次进行一个字节的计算,则表格有2^8=256个表值。
CRC16和CRC32都是一次处理一个字节的,所以它们的查询表有256个表值。
“驱动表法”算法为:
3210Bytes
+----+----+----+----+
+-----<|||||<-----Augmentedmessage(扩展0后的数据)
|+----+----+----+----+
|MSB^LSB
||
|XOR
||
|0+----+----+----+----+
查表v+----+----+----+----+
|+----+----+----+----+
|+----+----+----+----+
|+----+----+----+----+
|+----+----+----+----+
|+----+----+----+----+
+----->+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
255+----+----+----+----+
描述:
1:
register左移一个字节,从原始数据中读入一个新的字节.
2:
利用刚从register移出的字节作为下标定位table中的一个32位的值
3:
把这个值XOR到register中。
4:
如果还有未处理的数据则回到第一步继续执行。
用C可以写成这样:
r=0;//r是寄存器,先初始化为0
while(len--)//len是已扩展0之后的待测数据的长度{bytet=(r>>24)&0xFF;
r=(r<<8)|*p++;//p是指向待测数据的指针(待测数据需已经扩展过0)r^=table[t];//table是查询表}这个代码可以优化为:
r=0;//r是寄存器,先初始化为0
while(len--)//len是已扩展0之后的待测数据的字节长度
r=((r<<8)|*p++)^t[(r>>24)&0xFF];//p是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- CRC32CRC16CRC 原理 算法