再探CRC
之前寫了CRC16的程序，雖說能用，卻不知其所心然，現(xiàn)在要用CRC32，重溫一遍，一下就通了。筆記如下
CRC我沒記錯的話是Cyclic Redundancy Code，Cyclic和Redundancy非常傳神，所謂冗余就是附加的信息，這就是計算下面的原始數(shù)據(jù)時為什么原始數(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ù)即生成多項式的位數(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;
}
以上程序就是上面照片里算法的模擬實現(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生成多項式如上，如果CRC32校驗也要按BIT來計算的話，將是一個多么大的工程。所以一般會以BYTE為單位進行計算，因為計算機的寄存器位數(shù)都是8的位數(shù)。
我們先來看異或的一個特性，這是我們展開下面描述的基礎(chǔ)：
還是照片里的計算例子，這里把首位為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ù)就是寄存器里的當前值，這里寄存器已經(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!!!!
我們試另一種算法，把數(shù)據(jù)1101011011以5位一段分開：11010,11011
先對11010做對poly的CRC校驗，即110100000模2除poly結(jié)果是1000，把1000 0000與110110000異或，得到10110000再模2除poly，結(jié)果還是1110與之前的計算結(jié)果一樣。
看到這里，你可能想到了，把數(shù)據(jù)按8位一段劃分，先對最高位的byte進行CRC校驗，校驗值與下一byte異或進行校驗。。。。。。。，最后我們也得到了CRC校驗值。