再探CRC
之前寫了CRC16的程序，雖說(shuō)能用，卻不知其所心然，現(xiàn)在要用CRC32，重溫一遍，一下就通了。筆記如下
CRC我沒(méi)記錯(cuò)的話是Cyclic Redundancy Code，Cyclic和Redundancy非常傳神，所謂冗余就是附加的信息，這就是計(jì)算下面的原始數(shù)據(jù)時(shí)為什么原始數(shù)據(jù)要左移四位的原因，
///
/// The simplest CRC implement algorithm.
///
/*
Load the register with zero bits.
Augment the message by appending W zero bits to the end of it.
While (more message bits)
Begin
Shift the register left by one bit, reading the next bit of the augmented message into register bit position 0.
If (a 1 bit popped out of the register during step 3)
Register = Register XOR Poly.
End
The register now contains the remainder.
*/
#include <stdio.h>
#define POLY 0x13
int main()
{
/// the data
unsigned short data = 0x035b;
/// load the register with zero bits
unsigned short regi = 0x0000;
/// augment the data by appending W(4) zero bits to the end of it.
data <<= 4;
/// we do it bit after bit
for( int cur_bit = 15; cur_bit >= 0; -- cur_bit )
{
/// test the highest bit which will be poped later.
/// in fact, the 5th bit from right is the hightest bit here
if( ( ( regi >> 4 ) & 0x0001 ) == 0x1 )//湊夠5位數(shù)（與被除數(shù)即生成多項(xiàng)式的位數(shù)一樣），模2除
{
regi = regi ^ POLY;
}
/// shift the register regi <<= 1;
/// reading the next bit of the augmented data
unsigned short tmp = ( data >> cur_bit ) & 0x0001;
regi |= tmp;
}
/// and now, register contains the remainder which is also called CRC value.
return 0;
}
以上程序就是上面照片里算法的模擬實(shí)現(xiàn)，步驟完全一致。
Some popular polys are:
16 bits: (16,12,5,0) [X25 standard]
(16,15,2,0) ["CRC-16"]
32 bits: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) [Ethernet]
我們常用的CRC生成多項(xiàng)式如上，如果CRC32校驗(yàn)也要按BIT來(lái)計(jì)算的話，將是一個(gè)多么大的工程。所以一般會(huì)以BYTE為單位進(jìn)行計(jì)算，因?yàn)橛?jì)算機(jī)的寄存器位數(shù)都是8的位數(shù)。
我們先來(lái)看異或的一個(gè)特性，這是我們展開(kāi)下面描述的基礎(chǔ)：
還是照片里的計(jì)算例子，這里把首位為0
Original message : 1101011011
Poly : 10011
Message after appending W zeros : 11010110110000
Now we simply divide the augmented message by the poly using CRC
arithmetic. This is the same division as before:
1100001010 = Quotient (nobody cares about the quotient)
_______________
10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
=Poly 10011,,.,,....
-----,,.,,....
10011,.,,.... //每一次的余數(shù)就是寄存器里的當(dāng)前值，這里寄存器已經(jīng)左移了一位，//讀入一位新數(shù)據(jù)
10011,.,,....
-----,.,,....
00001.,,....//首位為0，寄存器內(nèi)值比除數(shù)小，則繼續(xù)讀入下一位
00000.,,....
-----.,,....
00010,,....
00000,,....
-----,,....
00101,....
00000,....
-----,....
01011....
00000....
-----....
10110...
10011...
-----...
01010..
00000..
-----..
10100.
10011.
-----.
01110
00000
-----
1110 = Remainder = THE CHECKSUM!!!!
我們?cè)嚵硪环N算法，把數(shù)據(jù)1101011011以5位一段分開(kāi)：11010,11011
先對(duì)11010做對(duì)poly的CRC校驗(yàn)，即110100000模2除poly結(jié)果是1000，把1000 0000與110110000異或，得到10110000再模2除poly，結(jié)果還是1110與之前的計(jì)算結(jié)果一樣。
看到這里，你可能想到了，把數(shù)據(jù)按8位一段劃分，先對(duì)最高位的byte進(jìn)行CRC校驗(yàn)，校驗(yàn)值與下一byte異或進(jìn)行校驗(yàn)。。。。。。。，最后我們也得到了CRC校驗(yàn)值。