CRC16和CRC32探討

之前寫了CRC16的程序，雖說能用，卻不知其所心然，現在要用CRC32，重溫一遍，一下就通了。筆記如下
CRC我沒記錯的話是Cyclic Redundancy Code，Cyclic和Redundancy非常傳神，所謂冗余就是附加的信息，這就是計算下面的原始數據時為什么原始數據要左移四位的原因，

///
/// The simplest CRC implement algorithm.
///
/*
Load the register with zero bits.
Augment the message by appending Wzerobits to the end of it.
While (more message bits)
Begin
Shift the register left by one bit, reading thenextbit 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

#define POLY 0x13

int main()
{
/// the data
unsigned short data = 0x035b;
/// load the register with zero bits
unsigned short regi = 0x0000;
/// augment thedataby appending W(4)zerobits 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位數（與被除數即生成多項式的位數一樣），模2除
{
regi = regi ^ POLY;
}
/// shift the register regi <<= 1;
/// reading thenextbit 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;
}
以上程序就是上面照片里算法的模擬實現，步驟完全一致。
Some popular polys are:
16 bits: (16,12,5,0) [X25standard]
(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生成多項式如上，如果CRC32校驗也要按BIT來計算的話，將是一個多么大的工程。所以一般會以BYTE為單位進行計算，因為計算機的寄存器位數都是8的位數。
我們先來看異或的一個特性，這是我們展開下面描述的基礎：
還是照片里的計算例子，這里把首位為0
Original message : 1101011011
Poly : 10011
Message after appending Wzeros : 11010110110000
Now we simply divide the augmented message by thepolyusing 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,.,,.... //每一次的余數就是寄存器里的當前值，這里寄存器已經左移了一位，//讀入一位新數據
10011,.,,....
-----,.,,....
00001.,,....//首位為0，寄存器內值比除數小，則繼續讀入下一位
00000.,,....
-----.,,....
00010,,....
00000,,....
-----,,....
00101,....
00000,....
-----,....
01011....
00000....
-----....
10110...
10011...
-----...
01010..
00000..
-----..
10100.
10011.
-----.
01110
00000
-----
1110 = Remainder = THE CHECKSUM!!!!

我們試另一種算法，把數據1101011011以5位一段分開：11010,11011
先對11010做對poly的CRC校驗，即110100000模2除poly結果是1000，把1000 0000與110110000異或，得到10110000再模2除poly，結果還是1110與之前的計算結果一樣。

看到這里，你可能想到了，把數據按8位一段劃分，先對最高位的byte進行CRC校驗，校驗值與下一byte異或進行校驗。。。。。。。，最后我們也得到了CRC校驗值。