我學(xué)習(xí)CRC32、CRC16、CRC原理和算法的總結(jié)（與WINRAR結(jié)果一致）
wxleasyland(wxlwww@gmail.com)
2010年9月2日
比較愚鈍，學(xué)了CRC校驗(yàn)好幾天，很痛苦的過程，現(xiàn)終于有眉目了，總結(jié)一下。
國外版的“輕松無痛苦學(xué)習(xí)CRC指南”，在
http://www.repairfaq.org/filipg/LINK/F_crc_v31.html
（為什么好的資料都是老外寫的？）我的英文有限，這種專業(yè)性太強(qiáng)的文章，很多都看不太明白，所以沒辦法翻譯，靠參考國內(nèi)的翻譯和自己瞎琢磨的。
國內(nèi)的翻譯比較不全，而且有點(diǎn)誤導(dǎo)，能看英文的還是看英文吧，國內(nèi)版資料比較零散，可參考：
http://www.q.cc/2001/12/08/10190.html
http://www.360doc.com/content/10/0703/12/1317564_36621098.shtml
http://www.yuanma.org/data/2006/1010/article_1637.htm
我結(jié)合國內(nèi)資料和英文原版進(jìn)行總結(jié)，達(dá)到和WINRAR一樣的CRC32計(jì)算結(jié)果。
一、 CRC原理
可參考http://www.luocong.com/articles/show_article.asp?Article_ID=15
計(jì)算CRC的過程，就是用一個特殊的“除法”，來得到余數(shù)，這個余數(shù)就是CRC。
它不是真正的算術(shù)上的除法！過程和算術(shù)除法過程一樣，只是加減運(yùn)算變成了XOR（異或）運(yùn)算！
算術(shù)上的除法：
120÷9＝13 余 3，120是被除數(shù)，9是除數(shù)，13是商，3是余數(shù)。念作120除以9，或者9除120，或者9去除120！（除法的過程就不寫了）
這個除法計(jì)算機(jī)當(dāng)然會做，但是做起來很麻煩，因?yàn)闇p法有借位，很耗時間和指令!
所以，計(jì)算CRC也是除法，但是用XOR來代替減法，這就簡單多了！
CRC的除法：
120÷9＝14 余 6，商、余數(shù)和算術(shù)除法不一定相同??！因?yàn)槌ㄓ玫氖荴OR，而不是真正的減法。
以二進(jìn)制模擬這個計(jì)算過程：
1110 商為1110，即14，商有4位，表示進(jìn)行了4次XOR
________
1001/1111000 被除數(shù)120是1111000，除數(shù)9是1001
1001 ^
----
1100 第一次XOR后得到011，加入下一位0。最高位的0可以消掉了，這樣最高位是1,所以下個商是1
1001 ^
----
1010 第二次XOR后得到0101，加入下一位0。最高位的0可以消掉了，這樣最高位是1,所以下個商是1
1001 ^
----
0110 第三次XOR后得到0011，加入下一位0。最高位的0可以消掉了，這樣最高位是0,所以下個商是0
0000 ^
----
110 -> 最后一次XOR后得到0110，最高位的0可以消掉了，得到余數(shù)為110，即6
注意，余數(shù)不是0110，而是110，因?yàn)樽钋懊婺莻€0已經(jīng)被XOR后消掉了！
可見，除法（XOR）的目的是逐步消掉最高位的1或0！
由于過程是XOR的，所以商是沒有意義的，我們不要。我們要的是余數(shù)。
余數(shù)110是1111000的CRC嗎？不是！
余數(shù)110是1111（即十進(jìn)制15）的CRC?。?！
為什么？因?yàn)镃RC是和數(shù)據(jù)一起傳送的，所以數(shù)據(jù)后面要加上CRC。
數(shù)據(jù)1111加上CRC110后，變成1111110，再傳送。接收機(jī)收到1111110后，除以除數(shù)1001，余數(shù)為000，正確；如果余數(shù)不為0，則說明傳送的數(shù)據(jù)有誤！這樣完成CRC校驗(yàn)。
即發(fā)送端要發(fā)送1111，先在1111后加000，變成1111000，再除以1001得到余數(shù)110，這個110就是CRC，將110加到數(shù)據(jù)后面，變成1111110，發(fā)送出去。
接收端收到1111110，用它除以1001，計(jì)算得余數(shù)為000，就說明收到的數(shù)據(jù)正確。
所以原始數(shù)據(jù)后面要先擴(kuò)展出3位0，以容納CRC值！
會發(fā)現(xiàn)，在上面的除法過程中，這3位0，能保證所有的4個數(shù)據(jù)位在除法時都能夠被處理到！不然做一次除法就到結(jié)果了，那是不對的。這個概念后面要用到。
所以，實(shí)際上，數(shù)據(jù)是1111，CRC是110。
對于除數(shù)1001，我們叫它生成多項(xiàng)式，即生成項(xiàng)，或POLY，即g(x)。
數(shù)據(jù)1111根據(jù)POLY1001，計(jì)算得到CRC110。
如果POLY不是1001，而是1011，那得到的CRC也是不同的！
所以生成項(xiàng)不同，得到的CRC也不同。要預(yù)先定義好POLY，發(fā)送端和接收端要用一樣的POLY！
二、 生成項(xiàng)
上面例子中，生成項(xiàng)是1001，共4位比特，最高位的1，實(shí)際上在除法的每次XOR時，都要消掉，所以這個1可不做參考，后3位001才是最重要的！001有3位，所以得到的余數(shù)也是3位，因?yàn)樽詈笠淮纬╔OR時，最高位消掉了。所以CRC就是3位比特的。
CRC是3比特，表示它的寬度W＝3。也就是說，原始數(shù)據(jù)后面要加上W=3比特的0進(jìn)行擴(kuò)展！
生成項(xiàng)的最低位也必須是1，這是規(guī)定的。
生成項(xiàng)1001，就等效于g(x)=x2+1
生成項(xiàng)也可以倒過來寫，即顛倒過來，寫成1001，這里倒過來的值是一樣的。
再如CRC32的生成項(xiàng)是：
1 0000 0100 1100 0001 0001 1101 1011 0111 （33個比特）
即g(x)= x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1
顛倒過來，就可以寫成1110 1101 1011 1000 1000 0011 0010 0000 1
一般生成項(xiàng)簡寫時不寫最高位的1，故生成項(xiàng)是0x04C11DB7，顛倒后的生成項(xiàng)是0xEDB88320
CRC32的生成項(xiàng)是33比特，最高位是消掉的，即CRC值是32比特（4個字節(jié)），即寬度W=32，就是說，在計(jì)算前，原始數(shù)據(jù)后面要先擴(kuò)展W=32個比特0，即4個0x00字節(jié)。
注意：我看到網(wǎng)上CRC32的POLY有0x04C10DB7這個值的，它和正規(guī)的POLY值不同，需要注意！
顛倒過來，即是鏡像，為什么要顛倒，后述。
三、 直接計(jì)算法 Straightforward CRC Implementation
“直接計(jì)算法”就是直接模擬上面的除法的過程，來得到余數(shù)即CRC！
上面的例子中，除數(shù)是4位，但最高位是要一直消掉的，所以我們只需要一個3位的寄存器就好了。
計(jì)算過程：
待測數(shù)據(jù)后擴(kuò)展W=3個比特0，變成1111000；
寄存器初始化置0；
先在寄存器中移入數(shù)據(jù)111；
寄存器左移一位，并且右邊移入下一位數(shù)據(jù)1。這樣最高位1移出，由于最高位是1，故本次的商是1，要用除數(shù)1001來進(jìn)行XOR，最高位肯定XOR得0，故不管它，只要用低3位001來進(jìn)行XOR就可以，即001對寄存器進(jìn)行XOR，寄存器中得到110，即第一次XOR后的結(jié)果（相當(dāng)于是數(shù)據(jù)1111與生成項(xiàng)1001進(jìn)行了一次XOR，并把最高位0消掉了）。 如果移出的最高位是0，則用0000來進(jìn)行XOR（0 XOR 后，得到的還是原值）。
一直重復(fù)這個過程，就能得到最后余數(shù)了。
總共處理次數(shù)＝商的位數(shù)＝待測數(shù)據(jù)的位數(shù)－生成項(xiàng)位數(shù)＋1＋寬度W＝待測數(shù)據(jù)的位數(shù)＝4次。
我們假設(shè)待測數(shù)據(jù)是1101 0110 11，生成項(xiàng)是10011，假設(shè)有一個4 bits的寄存器，通過反復(fù)的移位和進(jìn)行CRC的除法，最終該寄存器中的值就是我們所要求的余數(shù)。
3 2 1 0 Bits
+---+---+---+---+
Pop <-- | | | | | <----- Augmented message（已加0擴(kuò)張的原始數(shù)據(jù)）
+---+---+---+---+
1 0 0 1 1 = The Poly 生成項(xiàng)
依據(jù)這個模型，我們得到了一個最最簡單的算法：
把register中的值置0.
把原始的數(shù)據(jù)后添加w個0.
While (還有剩余沒有處理的數(shù)據(jù))
Begin
把register中的值左移一位，讀入一個新的數(shù)據(jù)并置于register最低位的位置。
If (如果上一步的左移操作中的移出的一位是1)
register = register XOR Poly.
End
實(shí)際上就是模擬XOR除法的過程，即被測數(shù)據(jù)一位一位放到寄存器中來做除法。
比如生成項(xiàng)是10011，則生成的余數(shù)是4位XXXX，所以寄存器是4位。
待測數(shù)據(jù)是1101 0110 11，后面加上0000，即擴(kuò)張4位，以容納余數(shù)。
只要與生成項(xiàng)的0011做XOR就好了，最高位經(jīng)過XOR肯定出0，可不用最高位。
過程如下：
待測數(shù)據(jù)先移4位即1101到寄存器中，準(zhǔn)備開始除法。
第1次除法：寄存器中是1101，先從寄存器移出最高位1，移進(jìn)下一位待測數(shù)據(jù)位0，則寄存器中是1010，由于移出的位是1，則需要與生成項(xiàng)的0011做XOR，得到1001，即做了第1次除法后，寄存器中是1001，這個就是余數(shù)。
第2次除法：寄存器中是1001，從寄存器移出最高位1，移進(jìn)下一位待測數(shù)據(jù)位1，則寄存器中是0011，由于移出的位是1，則需要與生成項(xiàng)的0011做XOR，得到0000，即做了第2次除法后，寄存器中是0000，這個就是余數(shù)。
第3次除法：寄存器中是0000，從寄存器移出最高位0，移進(jìn)下一位待測數(shù)據(jù)位1，則寄存器中是0001，由于移出的位是0，則需要不做XOR，直接下一步移位。也可以等同于：本次的商是0,0*生成項(xiàng)＝0，即是0000與寄存器做XOR，得到寄存器的數(shù)不變，還是0001，即做了第3次除法后，寄存器中是0001，這個就是余數(shù)。
第4次除法：寄存器中是0001，從寄存器移出最高位0，移進(jìn)下一位待測數(shù)據(jù)位0，則寄存器中是0010，由于移出的位是0，則需要不做XOR，直接下一步移位。
第5次除法：移位，不用做XOR，得到寄存器中是0101
第6次除法：移位，不用做XOR，得到寄存器中是1011
第7次除法：移位，移出的位是1，又要與生成項(xiàng)做XOR了
一直做下去。。。。。。直到最后，寄存器中的就是整個計(jì)算后的余數(shù)了。即CRC值。
注意：
這個算法，計(jì)算出的CRC32值,與WINRAR計(jì)算出來的不一樣，為什么？算法是正確的，不用懷疑！只是CRC32正式算法還涉及到數(shù)據(jù)顛倒和初始化預(yù)置值等，后述。
程序?qū)崿F(xiàn)：
程序1：
（注：網(wǎng)上下的程序是有錯的，我有修改了，這里是正確的）
//網(wǎng)上的程序經(jīng)修改
BYTE POLY=0x13; //生成項(xiàng)，13H＝10011，這樣CRC是4比特
unsigned short data = 0x035B; //待測數(shù)據(jù)是35BH，12比特，注意，數(shù)據(jù)不是16比特
unsigned short regi = 0x0000; // load the register with zero bits
// augment the data by appending W(4) zero bits to the end of it.
//按CRC計(jì)算的定義，待測數(shù)據(jù)后加入4個比特0，以容納4比特的CRC；
//這樣共有16比特待測數(shù)據(jù)，從第5比特開始做除法，就要做16－5＋1＝12次XOR
data <<= 4;
// we do it bit after bit
for ( int cur_bit = 15; cur_bit >= 0; -- cur_bit ) //處理16次，前4次實(shí)際上只是加載數(shù)據(jù)
{
// 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 ) regi = regi ^ POLY;
regi <<= 1; // shift the register
// reading the next bit of the augmented data
unsigned short tmp = ( data >> cur_bit ) & 0x0001; //加載待測數(shù)據(jù)1比特到tmp中，tmp只有1比特
regi |= tmp; //這1比特加載到寄存器中
}
if ( ( ( regi >> 4 ) & 0x0001 ) == 0x1 ) regi = regi ^ POLY; //做最后一次XOR
//這時， regi中的值就是CRC
程序2：我做的通用CRC計(jì)算程序：
_int64 POLY = 0x104C11DB7; //生成項(xiàng)，需要含有最高位的"1"，這樣CRC是32比特
int crcbitnumber=32; //crc是32比特
_int64 data = 0x31323334; //待測數(shù)據(jù)，為字串"1234"
int databitnumber=32; //數(shù)據(jù)是32比特
_int64 regi = 0x0; // load the register with zero bits
// augment the data by appending W zero bits to the end of it.
//按CRC計(jì)算的定義，加入32個比特0，以容納32比特的CRC；
//這樣共有64比特待測數(shù)據(jù)，從第33比特開始做除法，就要做64－33＋1＝32次XOR
data <<= crcbitnumber;
// we do it bit after bit
for ( int cur_bit = databitnumber+crcbitnumber-1; cur_bit >= 0; -- cur_bit ) //處理64次（32比特待測數(shù)據(jù)＋32比特?cái)U(kuò)展0），前32次是加載數(shù)據(jù)
{
// test the highest bit which will be poped later.
/// in fact, the 5th bit from right is the hightest bit here
if ( ( ( regi >> crcbitnumber ) & 0x0001 ) == 0x1 ) regi = regi ^ POLY;
regi <<= 1; // shift the register
// reading the next bit of the augmented data
unsigned short tmp = ( data >> cur_bit ) & 0x0001; //加載待測數(shù)據(jù)1比特到tmp中，tmp只有1比特
regi |= tmp; //這1比特加載到寄存器中
}
if ( ( ( regi >> crcbitnumber ) & 0x0001 ) == 0x1 ) regi = regi ^ POLY; //做最后一次XOR
//這時， regi中的值就是CRC
四、 驅(qū)動表法 Table-Driven Implementation
上面的“直接計(jì)算法”很直觀，卻非常的低效。為了加快它的速度，我們使它一次能處理大于4 bit的數(shù)據(jù)。一次能處理一個字節(jié)的數(shù)據(jù)的話，那就方便多了。
我們想要實(shí)現(xiàn)的32 bit的CRC校驗(yàn)。我們還是假設(shè)有和原來一樣的一個4 "bit"的register，但它的每一位是一個8 bit的字節(jié)。
3 2 1 0 Bytes
+----+----+----+----+
Pop! <-- | | | | | <----- Augmented message（擴(kuò)展0后的數(shù)據(jù)）
+----+----+----+----+
1 <------32 bits------> （生成項(xiàng)，暗含了一個最高位的“1”）
根據(jù)同樣的原理我們可以得到如下的算法：
While (還有剩余沒有處理的數(shù)據(jù))
Begin
檢查register頭字節(jié)，并取得它的值
求不同偏移處多項(xiàng)式的XOR
register左移一個字節(jié)，最右處存入新讀入的一個字節(jié)
把register的值 和 多項(xiàng)式的XOR結(jié)果 進(jìn)行XOR運(yùn)算
End
可是為什么要這樣作呢？ 同樣我們還是以一個簡單的例子說明問題：
為了簡單起見，我們假設(shè)一次只移出4個比特！而不是8個比特。
生成多項(xiàng)式為： 1 0101 1100，即寬度W=8，即CRC8，這樣寄存器為8位
待測數(shù)據(jù)是1011 0100 1101
按正常的算法做：
將1011 0100放入寄存器中，然后開始計(jì)算CRC。
先將高4位移出寄存器：
當(dāng)前register中的值： 0100 1101
4 bit應(yīng)該被移出的值： 1011
生成多項(xiàng)式為： 1010 1110 0
第一步：
Top Register （top指移出的數(shù)據(jù)）
---- --------
1011 0100 1101 待測數(shù)
1010 1110 0 + (CRC XOR) POLY
-------------
0001 1010 1101 第一次XOR后的值
第二步：
這時，首4 bits 不為0說明沒有除盡，要繼續(xù)除:
0001 1010 1101
1 0101 1100 + (CRC XOR) 將POLY右移3位后，再做XOR
-------------
0000 1111 0001 第二次XOR后的值
^^^^
這時，首4 bits 全0說明不用繼續(xù)除了，結(jié)果滿足要求了。
也就是說：待測數(shù)據(jù)與POLY相XOR，得到的結(jié)果再與POLY相XOR，POLY要適當(dāng)移位，以消掉1。重復(fù)進(jìn)行，直到結(jié)果滿足要求。
下面，我們換一種算法，來達(dá)到相同的目的：
POLY與POLY自已先進(jìn)行XOR，當(dāng)然POLY要進(jìn)行適當(dāng)移位。使得得到的結(jié)果值的高4位與待測數(shù)據(jù)相同。
第一步：
1010 1110 0 POLY
1 0101 1100 + 右移3位后的POLY
-------------
1011 1011 1100 POLY與POLY自已進(jìn)行XOR后得到的值
第二步：
1011 1011 1100 POLY相XOR后得到的值
1011 0100 1101+ 待測數(shù)據(jù)
-------------
0000 11110001 得到的結(jié)果值和上面是一樣的（說明可以先把POLY預(yù)先XOR好，再與待測數(shù)據(jù)XOR，就能得到結(jié)果）
結(jié)論：
現(xiàn)在我們看到，這二種算法計(jì)算的結(jié)果是一致的！這是基于XOR的交換律，即(a XOR b) XOR c = a XOR (b XOR c)。而后一種算法可以通過查表來快速完成，叫做“驅(qū)動表法”算法。
也就是說，根據(jù)4 bit被移出的值1011，我們就可以知道要用POLY自身XOR后得到的 1011 1011 1100 來對待測數(shù)據(jù)1011 0100 1101進(jìn)行XOR，這樣一次就能消掉4BIT待測數(shù)據(jù)。（注意藍(lán)色的最高4位要一樣，這樣XOR后才能得0000，就能消掉了）
即1011對應(yīng)1011 1011 1100，實(shí)際只需要用到后8位，即1011對應(yīng)1011 1100
用查表法來得到，即1011作為索引值，查表，得到表值1011 1100。
表格可以預(yù)先生成。
這里是每次移出4位，則POLY與POLY進(jìn)行XOR的組合有2^4＝16種，即從0000到1111。
注意，POLY自身與自身相XOR時，要先對齊到和寄存器一樣的長度，再XOR。相當(dāng)于有12位進(jìn)行XOR。
組合后的結(jié)果有16種：（黑色的0表示對齊到和寄存器一樣的長度）
1. 0000 0000 0000 即表示待測數(shù)據(jù)移出的4位都是0，不需要與POLY相XOR，即相當(dāng)于待測數(shù)據(jù)移出的4位后，與0000 0000 0000相XOR
2. 0001 0101 1100 即表示待測數(shù)據(jù)移出的4位是0001，需要與右移過3位的POLY相XOR
3. 0010 1011 1000
4. 0010 1011 1000 與 0001 0101 1100 相XOR，XOR后前4位為0011 即表示待測數(shù)據(jù)移出的4位后，需要與POLY進(jìn)行二次相XOR，結(jié)果才能滿足要求。
5. 0101 0111 0000 與 0001 0101 1100相XOR， XOR后前4位為0100
6. 0101 0111 0000 ， 前4位為 0101
7. 0101 0111 0000 與 0010 1011 1000、0001 0101 1100 相XOR， XOR后前4位為0110
8. 0101 0111 0000 與 0010 1011 1000， XOR后前4位為0111
9. 1010 1110 0000 與 0010 1011 1000相XOR， XOR后前4位為1000
10.1010 1110 0000 與 0010 1011 1000、0001 0101 1100相XOR， XOR后前4位為1001
11.1010 1110 0000， 前4位為 1010
12.1010 1110 0000 與 0001 0101 1100相XOR， XOR后前4位為1011
13.1010 1110 0000 與 0101 0111 0000、0010 1011 1000、0001 0101 1100相XOR， XOR后前4位為1100
14.1010 1110 0000 與 0101 0111 0000、0010 1011 1000相XOR， XOR后前4位為1101
15.1010 1110 0000 與 0101 0111 0000、0001 0101 1100相XOR， XOR后前4位為1110
16.1010 1110 0000 與 0101 0111 0000相XOR， XOR后前4位為1111
以XOR后得到的結(jié)果的前4位做為索引值，以XOR后得到的結(jié)果的后8位做為表值，生成一張表，即：
TABLE[0]=0000 0000B;
TABLE[1]=0101 1100B;
TABLE[2]=1011 1000B;
TABLE[3]=[(0010 1011 1000B ^ 0001 0101 1100B) >> 4 ] & 0xff
....
這張表我叫它為“直接查詢表”。
就是說，一次移出的待測數(shù)據(jù)的4位bit，有2^4個值，即0000,0001,0010,....,1111，根據(jù)這個值來查表，找到相應(yīng)的表值，再用表值來XOR寄存器中的待測數(shù)據(jù)。
所以，如果一次移出待測數(shù)據(jù)的8位bit，即一次進(jìn)行一個字節(jié)的計(jì)算，則表格有2^8＝256個表值。
CRC16和CRC32都是一次處理一個字節(jié)的，所以它們的查詢表有256個表值。
“驅(qū)動表法”算法為：
3 2 1 0 Bytes
+----+----+----+----+
+-----<| | | | | <----- Augmented message（擴(kuò)展0后的數(shù)據(jù)）
| +----+----+----+----+
| MSB ^ LSB
| |
| XOR
| |
| 0+----+----+----+----+
查表v +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
+----->+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
255+----+----+----+----+
描述：
1：register左移一個字節(jié),從原始數(shù)據(jù)中讀入一個新的字節(jié).
2：利用剛從register移出的字節(jié)作為下標(biāo)定位 table 中的一個32位的值
3：把這個值XOR到register中。
4：如果還有未處理的數(shù)據(jù)則回到第一步繼續(xù)執(zhí)行。
用C可以寫成這樣：
r=0; //r是寄存器，先初始化為0
while (len--) //len是已擴(kuò)展0之后的待測數(shù)據(jù)的長度
{
byte t = (r >> 24) & 0xFF;
r = (r << 8) | *p++; //p是指向待測數(shù)據(jù)的指針（待測數(shù)據(jù)需已經(jīng)擴(kuò)展過0）
r^=table[t]; //table是查詢表
}
這個代碼可以優(yōu)化為：
r=0; //r是寄存器，先初始化為0
while (len--) //len是已擴(kuò)展0之后的待測數(shù)據(jù)的字節(jié)長度
r = ((r << 8) | *p++) ^ t[(r >> 24) & 0xFF]; //p是指向待測數(shù)據(jù)的指針（待測數(shù)據(jù)需已經(jīng)擴(kuò)展過0）,t是查詢表
注意：
這個“驅(qū)動表法”算法和“直接計(jì)算法”是完全一樣的，不僅結(jié)果完全一樣，處理方式也是完全一樣的，所以“驅(qū)動表法”可以完全替代“直接計(jì)算法”！
原始數(shù)據(jù)都需要先用0擴(kuò)展W位；最開始的幾次循環(huán)的實(shí)質(zhì)都只是先將待測數(shù)據(jù)移動到寄存器中去而已；
會發(fā)現(xiàn)，這個算法用到的“直接查詢表”的表值，和網(wǎng)上公開的查詢表（我叫它“正規(guī)查詢表”）的表值不一樣！為什么？因?yàn)榫W(wǎng)上公開的正規(guī)查詢表是用于“顛倒”算法的！后述。
會發(fā)現(xiàn)，這個算法，計(jì)算出的CRC32值，同樣與WINRAR計(jì)算出來的不一樣。
生成的“直接查詢表”的內(nèi)容是：
CRC16直接查詢表
00H 0000 8005 800F 000A
04H 801B 001E 0014 8011
08H 8033 0036 003C 8039
0CH 0028 802D 8027 0022
10H 8063 0066 006C 8069
14H 0078 807D 8077 0072
18H 0050 8055 805F 005A
1CH 804B 004E 0044 8041
20H 80C3 00C6 00CC 80C9
24H 00D8 80DD 80D7 00D2
28H 00F0 80F5 80FF 00FA
2CH 80EB 00EE 00E4 80E1
30H 00A0 80A5 80AF 00AA
34H 80BB 00BE 00B4 80B1
38H 8093 0096 009C 8099
3CH 0088 808D 8087 0082
40H 8183 0186 018C 8189
44H 0198 819D 8197 0192
48H 01B0 81B5 81BF 01BA
4CH 81AB 01AE 01A4 81A1
50H 01E0 81E5 81EF 01EA
54H 81FB 01FE 01F4 81F1
58H 81D3 01D6 01DC 81D9
5CH 01C8 81CD 81C7 01C2
60H 0140 8145 814F 014A
64H 815B 015E 0154 8151
68H 8173 0176 017C 8179
6CH 0168 816D 8167 0162
70H 8123 0126 012C 8129
74H 0138 813D 8137 0132
78H 0110 8115 811F 011A
7CH 810B 010E 0104 8101
80H 8303 0306 030C 8309
84H 0318 831D 8317 0312
88H 0330 8335 833F 033A
8CH 832B 032E 0324 8321
90H 0360 8365 836F 036A
94H 837B 037E 0374 8371
98H 8353 0356 035C 8359
9CH 0348 834D 8347 0342
A0H 03C0 83C5 83CF 03CA
A4H 83DB 03DE 03D4 83D1
A8H 83F3 03F6 03FC 83F9
ACH 03E8 83ED 83E7 03E2
B0H 83A3 03A6 03AC 83A9
B4H 03B8 83BD 83B7 03B2
B8H 0390 8395 839F 039A
BCH 838B 038E 0384 8381
C0H 0280 8285 828F 028A
C4H 829B 029E 0294 8291
C8H 82B3 02B6 02BC 82B9
CCH 02A8 82AD 82A7 02A2
D0H 82E3 02E6 02EC 82E9
D4H 02F8 82FD 82F7 02F2
D8H 02D0 82D5 82DF 02DA
DCH 82CB 02CE 02C4 82C1
E0H 8243 0246 024C 8249
E4H 0258 825D 8257 0252
E8H 0270 8275 827F 027A
ECH 826B 026E 0264 8261
F0H 0220 8225 822F 022A
F4H 823B 023E 0234 8231
F8H 8213 0216 021C 8219
FCH 0208 820D 8207 0202
CRC32直接查詢表
00H 00000000 04C11DB7 09823B6E 0D4326D9
04H 130476DC 17C56B6B 1A864DB2 1E475005
08H 2608EDB8 22C9F00F 2F8AD6D6 2B4BCB61
0CH 350C9B64 31CD86D3 3C8EA00A 384FBDBD
10H 4C11DB70 48D0C6C7 4593E01E 4152FDA9
14H 5F15ADAC 5BD4B01B 569796C2 52568B75
18H 6A1936C8 6ED82B7F 639B0DA6 675A1011
1CH 791D4014 7DDC5DA3 709F7B7A 745E66CD
20H 9823B6E0 9CE2AB57 91A18D8E 95609039
24H 8B27C03C 8FE6DD8B 82A5FB52 8664E6E5
28H BE2B5B58 BAEA46EF B7A96036 B3687D81
2CH AD2F2D84 A9EE3033 A4AD16EA A06C0B5D
30H D4326D90 D0F37027 DDB056FE D9714B49
34H C7361B4C C3F706FB CEB42022 CA753D95
38H F23A8028 F6FB9D9F FBB8BB46 FF79A6F1
3CH E13EF6F4 E5FFEB43 E8BCCD9A EC7DD02D
40H 34867077 30476DC0 3D044B19 39C556AE
44H 278206AB 23431B1C 2E003DC5 2AC12072
48H 128E9DCF 164F8078 1B0CA6A1 1FCDBB16
4CH 018AEB13 054BF6A4 0808D07D 0CC9CDCA
50H 7897AB07 7C56B6B0 71159069 75D48DDE
54H 6B93DDDB 6F52C06C 6211E6B5 66D0FB02
58H 5E9F46BF 5A5E5B08 571D7DD1 53DC6066
5CH 4D9B3063 495A2DD4 44190B0D 40D816BA
60H ACA5C697 A864DB20 A527FDF9 A1E6E04E
64H BFA1B04B BB60ADFC B6238B25 B2E29692
68H 8AAD2B2F 8E6C3698 832F1041 87EE0DF6
6CH 99A95DF3 9D684044 902B669D 94EA7B2A
70H E0B41DE7 E4750050 E9362689 EDF73B3E
74H F3B06B3B F771768C FA325055 FEF34DE2
78H C6BCF05F C27DEDE8 CF3ECB31 CBFFD686
7CH D5B88683 D1799B34 DC3ABDED D8FBA05A
80H 690CE0EE 6DCDFD59 608EDB80 644FC637
84H 7A089632 7EC98B85 738AAD5C 774BB0EB
88H 4F040D56 4BC510E1 46863638 42472B8F
8CH 5C007B8A 58C1663D 558240E4 51435D53
90H 251D3B9E 21DC2629 2C9F00F0 285E1D47
94H 36194D42 32D850F5 3F9B762C 3B5A6B9B
98H 0315D626 07D4CB91 0A97ED48 0E56F0FF
9CH 1011A0FA 14D0BD4D 19939B94 1D528623
A0H F12F560E F5EE4BB9 F8AD6D60 FC6C70D7
A4H E22B20D2 E6EA3D65 EBA91BBC EF68060B
A8H D727BBB6 D3E6A601 DEA580D8 DA649D6F
ACH C423CD6A C0E2D0DD CDA1F604 C960EBB3
B0H BD3E8D7E B9FF90C9 B4BCB610 B07DABA7
B4H AE3AFBA2 AAFBE615 A7B8C0CC A379DD7B
B8H 9B3660C6 9FF77D71 92B45BA8 9675461F
BCH 8832161A 8CF30BAD 81B02D74 857130C3
C0H 5D8A9099 594B8D2E 5408ABF7 50C9B640
C4H 4E8EE645 4A4FFBF2 470CDD2B 43CDC09C
C8H 7B827D21 7F436096 7200464F 76C15BF8
CCH 68860BFD 6C47164A 61043093 65C52D24
D0H 119B4BE9 155A565E 18197087 1CD86D30
D4H 029F3D35 065E2082 0B1D065B 0FDC1BEC
D8H 3793A651 3352BBE6 3E119D3F 3AD08088
DCH 2497D08D 2056CD3A 2D15EBE3 29D4F654
E0H C5A92679 C1683BCE CC2B1D17 C8EA00A0
E4H D6AD50A5 D26C4D12 DF2F6BCB DBEE767C
E8H E3A1CBC1 E760D676 EA23F0AF EEE2ED18
ECH F0A5BD1D F464A0AA F9278673 FDE69BC4
F0H 89B8FD09 8D79E0BE 803AC667 84FBDBD0
F4H 9ABC8BD5 9E7D9662 933EB0BB 97FFAD0C
F8H AFB010B1 AB710D06 A6322BDF A2F33668
FCH BCB4666D B8757BDA B5365D03 B1F740B4
“驅(qū)動表法”的程序：
// 注意：因生成項(xiàng)POLY最高位一定為“1”，故略去最高位的"1"，
unsigned short cnCRC_16 = 0x8005; // CRC-16 = X16 + X15 + X2 + X0
unsigned short cnCRC_CCITT = 0x1021; // CRC-CCITT = X16 + X12 + X5 + X0，據(jù)說這個 16 位 CRC 多項(xiàng)式比上一個要好
unsigned long cnCRC_32 = 0x04C11DB7; //采用正規(guī)的CRC32的POLY
unsigned long Table_CRC16[256]; // CRC16 表
unsigned long Table_CRC32[256]; // CRC32 表
// 構(gòu)造 16 位 CRC 表 "直接查詢表"
unsigned short i16, j16;
unsigned short nData16;
unsigned short nAccum16;
for ( i16 = 0; i16 < 256; i16++ )
{
nData16 = ( unsigned short )( i16 << 8 );
nAccum16 = 0;
for ( j16 = 0; j16 < 8; j16++ )
{
if ( ( nData16 ^ nAccum16 ) & 0x8000 )
nAccum16 = ( nAccum16 << 1 ) ^ cnCRC_16; //也可以用cnCRC_CCITT
else
nAccum16 <<= 1;
nData16 <<= 1;
}
Table_CRC16[i16] = ( unsigned long )nAccum16;
}
// 構(gòu)造 32 位 CRC 表 "直接查詢表"
unsigned long i32, j32;
unsigned long nData32;
unsigned long nAccum32;
for ( i32 = 0; i32 < 256; i32++ )
{
nData32 = ( unsigned long )( i32 << 24 );
nAccum32 = 0;
for ( j32 = 0; j32 < 8; j32++ )
{
if ( ( nData32 ^ nAccum32 ) & 0x80000000 )
nAccum32 = ( nAccum32 << 1 ) ^ cnCRC_32;
else
nAccum32 <<= 1;
nData32 <<= 1;
}
Table_CRC32[i32] = nAccum32;
}
unsigned char aData[512]={0x31,0x32,0x33,0x34}; //待測數(shù)據(jù)，為字串"1234"
unsigned long aSize;
unsigned long i;
unsigned char *point;
// 計(jì)算 16 位 CRC 值，CRC-16 或 CRC-CCITT
//Table-Driven驅(qū)動表法，需要用到“直接查詢表”（不能用“正規(guī)查詢表”）；待測數(shù)據(jù)需擴(kuò)展0
unsigned short CRC16_1;
aSize=4; //數(shù)據(jù)長度字節(jié)（不包含擴(kuò)展0）
CRC16_1 = 0; //寄存器歸0
point=aData;
while (aSize--)
CRC16_1 = ((CRC16_1 << 8) | *point++) ^ Table_CRC16[(CRC16_1 >> 8) & 0xFF];
for ( i = 0; i < 2; i++ )
CRC16_1 = ((CRC16_1 << 8) ) ^ Table_CRC16[(CRC16_1 >> 8) & 0xFF]; //加入2字節(jié)的擴(kuò)展0
//這時， CRC16_1中的值就是CRC
// 計(jì)算 32 位 CRC-32 值
//Table-Driven驅(qū)動表法，需要用到“直接查詢表”（不能用“正規(guī)查詢表”）；待測數(shù)據(jù)需擴(kuò)展0
unsigned long CRC32_1;
aSize=4; //數(shù)據(jù)長度字節(jié)（不包含擴(kuò)展0）
CRC32_1=0x0; //寄存器歸0
point=aData;
while (aSize--)
CRC32_1 = ((CRC32_1 << 8) | *point++) ^ Table_CRC32[(CRC32_1 >> 24) & 0xFF];
for ( i = 0; i < 4; i++ ) CRC32_1 = ((CRC32_1 << 8) ) ^ Table_CRC32[(CRC32_1 >> 24) & 0xFF];//加入4字節(jié)的擴(kuò)展0
//這時， CRC32_1中的值就是CRC
打印查詢表的語句：（在TC中實(shí)現(xiàn)）
for ( i16 = 0; i16 < 256; i16++ )
{
printf("%02xh %04x %04x %04x %04x\n",i16,( unsigned short)Table_CRC16[i16],( unsigned short)Table_CRC16[i16+1],( unsigned short)Table_CRC16[i16+2],( unsigned short)Table_CRC16[i16+3]);
i16++;
i16++;
i16++;
}
for ( i16 = 0; i16 < 256; i16++ )
{
printf("%02xh %08lx %08lx %08lx %08lx\n",i16,Table_CRC32[i16],Table_CRC32[i16+1],Table_CRC32[i16+2],Table_CRC32[i16+3]);
i16++;
i16++;
i16++;
}
五、 直驅(qū)表法 DIRECT TABLE ALGORITHM
對于上面的算法：
1．對于尾部的w/8個擴(kuò)展0字節(jié)，事實(shí)上它們的作用只是確保所有的原始數(shù)據(jù)都已被送入register，并且被算法處理。
2．如果register中的初始值是0，那么開始的4次循環(huán)，作用只是把原始數(shù)據(jù)的頭4個字節(jié)送入寄存器，而沒有進(jìn)行真正的除法操作。就算初始值不是0（我注：這里并沒有說是“寄存器的初始值”，而是指算法開始時的“初始化值”），開始的4次循環(huán)也只是把原始數(shù)據(jù)的頭4個字節(jié)移入到register中，然后再把它們和一個特定常數(shù)相XOR（我注：即這時進(jìn)行初始化操作，后述）。
3．因?yàn)橛薪粨Q律：(A xor B) xor C = A xor (B xor C)
這些信息意味著，上面提到的算法可以被優(yōu)化，待測數(shù)據(jù)不需要先循環(huán)幾次進(jìn)入到寄存器中后再進(jìn)行處理，而是數(shù)據(jù)直接就可以處理到寄存器中。
可以這樣：數(shù)據(jù)可以先與剛從寄存器移出的字節(jié)相XOR，用得到的結(jié)果值進(jìn)行查表，再用表值XOR寄存器。這引出了以下“直驅(qū)表法”算法：
+-----<Message (non augmented) 待測數(shù)據(jù)（不用擴(kuò)展0）
|
v 3 2 1 0 Bytes
| +----+----+----+----+
XOR----<| | | | |
| +----+----+----+----+
| MSB ^ LSB
| |
| XOR
| |
| 0+----+----+----+----+
查表v +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
+----->+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
255+----+----+----+----+
“直驅(qū)表法”算法：
1. Shift the register left by one byte, reading in a new message byte.（我注：老外的這句話有問題，應(yīng)只是Shift the register left by one byte，而不將新的信息字節(jié)讀入register中。所以翻譯為：寄存器左移一個字節(jié)）
2. XOR the top byte just rotated out of the register with the next message byte to yield an index into the table ([0,255]). 將剛從register移出的字節(jié)與新的信息字節(jié)相XOR，結(jié)果值作為定位索引，從查詢表中取得相應(yīng)的表值。
3. XOR the table value into the register. 把表值XOR到register中
4. Goto 1 iff more augmented message bytes. 如果還有未處理的數(shù)據(jù)則回到第一步繼續(xù)執(zhí)行。
用C可以寫成這樣：
r=0; //r是寄存器，先初始化為0
while (len--) //len是待測數(shù)據(jù)（不用擴(kuò)展0）的字節(jié)長度
r = (r<<8) ^ t[(r >> 24) ^ *p++]; //p是指向待測數(shù)據(jù)的指針,t是查詢表
算法相當(dāng)于：
寄存器左移出1字節(jié)，右邊補(bǔ)0；
移出的字節(jié)與待測信息字節(jié)進(jìn)行XOR，根據(jù)結(jié)果值查表，得表值
表值與寄存器進(jìn)行XOR
注意：
這個“直驅(qū)表法”算法的數(shù)學(xué)原理我也不明白，但它肯定是從“驅(qū)動表法”算法推導(dǎo)出來的，得到的CRC結(jié)果值是完全一樣的！只是它們的處理方式是不一樣的。
這個算法很方便，原始數(shù)據(jù)不需要先用0擴(kuò)展W位；
這個算法很方便，第一次循環(huán)就能夠處理待測數(shù)據(jù)并在寄存器中生成結(jié)果，而不單純只是將數(shù)據(jù)移動到寄存器中去而已；
這個算法，用的是和“驅(qū)動表法”同樣的“直接查詢表”，而不是“正規(guī)查詢表”。
正是由于處理方式不一樣，所以如果寄存器初始化預(yù)置值不為0，那么本算法可不受影響，而“驅(qū)動表法”則需要將預(yù)置值再另外XOR到寄存器中。后述。
“直驅(qū)表法”的程序：
// 注意：因生成項(xiàng)POLY最高位一定為“1”，故略去最高位的"1"，
unsigned short cnCRC_16 = 0x8005; // CRC-16 = X16 + X15 + X2 + X0
unsigned short cnCRC_CCITT = 0x1021; // CRC-CCITT = X16 + X12 + X5 + X0，據(jù)說這個 16 位 CRC 多項(xiàng)式比上一個要好
unsigned long cnCRC_32 = 0x04C11DB7; //采用正規(guī)的CRC32的POLY
unsigned long Table_CRC16[256]; // CRC16 表
unsigned long Table_CRC32[256]; // CRC32 表
// 構(gòu)造 16 位 CRC 表 "直接查詢表"
unsigned short i16, j16;
unsigned short nData16;
unsigned short nAccum16;
for ( i16 = 0; i16 < 256; i16++ )
{
nData16 = ( unsigned short )( i16 << 8 );
nAccum16 = 0;
for ( j16 = 0; j16 < 8; j16++ )
{
if ( ( nData16 ^ nAccum16 ) & 0x8000 )
nAccum16 = ( nAccum16 << 1 ) ^ cnCRC_16; //也可以用cnCRC_CCITT
else
nAccum16 <<= 1;
nData16 <<= 1;
}
Table_CRC16[i16] = ( unsigned long )nAccum16;
}
// 構(gòu)造 32 位 CRC 表 "直接查詢表"
unsigned long i32, j32;
unsigned long nData32;
unsigned long nAccum32;
for ( i32 = 0; i32 < 256; i32++ )
{
nData32 = ( unsigned long )( i32 << 24 );
nAccum32 = 0;
for ( j32 = 0; j32 < 8; j32++ )
{
if ( ( nData32 ^ nAccum32 ) & 0x80000000 )
nAccum32 = ( nAccum32 << 1 ) ^ cnCRC_32;
else
nAccum32 <<= 1;
nData32 <<= 1;
}
Table_CRC32[i32] = nAccum32;
}
unsigned char aData[512]={0x31,0x32,0x33,0x34}; //待測數(shù)據(jù)，為字串"1234"
unsigned long aSize;
unsigned long i;
unsigned char *point;
// 計(jì)算 16 位 CRC 值，CRC-16 或 CRC-CCITT
//DIRECT TABLE直驅(qū)表法，需要用到“直接查詢表”（不能用“正規(guī)查詢表”）；待測數(shù)據(jù)不需要擴(kuò)展0
unsigned short CRC16_2;
aSize=4; //數(shù)據(jù)長度字節(jié)（數(shù)據(jù)不用擴(kuò)展0了）
CRC16_2 = 0; //寄存器中預(yù)置初始值
point=aData;
for ( i = 0; i < aSize; i++ )
CRC16_2 = ( CRC16_2 << 8 ) ^ ( unsigned short ) Table_CRC16[( CRC16_2 >> 8 ) ^ *point++];
//這時， CRC16_2中的值就是CRC
// 計(jì)算 32 位 CRC-32 值
//DIRECT TABLE直驅(qū)表法，需要用到“直接查詢表”（不能用“正規(guī)查詢表”）；待測數(shù)據(jù)不需要擴(kuò)展0
unsigned long CRC32_2;
aSize=4; //數(shù)據(jù)長度字節(jié)（數(shù)據(jù)不用擴(kuò)展0了）
CRC32_2 = 0x0; //寄存器中預(yù)置初始值
point=aData;
for ( i = 0; i < aSize; i++ )
CRC32_2 = ( CRC32_2 << 8 ) ^ Table_CRC32[( CRC32_2 >> 24 ) ^ *point++];
//這時， CRC32_2中的值就是CRC
六、 CRC的參數(shù)模型
實(shí)際上，這時已經(jīng)可以計(jì)算出與WINRAR相同的CRC32值了。但是會發(fā)現(xiàn)，算出的結(jié)果和WINRAR是不一樣的，為什么？因?yàn)椴粌H僅是生成項(xiàng)POLY會影響到CRC值，還有很多參數(shù)會影響到最終的CRC值！
CRC計(jì)算，需要有CRC參數(shù)模型，比如CRC32的參數(shù)模型是：
Name : "CRC-32"
Width : 32
Poly : 04C11DB7
Init : FFFFFFFF
RefIn : True
RefOut : True
XorOut : FFFFFFFF
Check : CBF43926
解釋：
NAME
名稱
WIDTH
寬度，即CRC比特?cái)?shù)
POLY
生成項(xiàng)的簡寫。以16進(jìn)制表示，即是0x04C11DB7。忽略了最高位的"1"，即完整的生成項(xiàng)是0x104C11DB7。
重要的一點(diǎn)是，這是“未顛倒”的生成項(xiàng)！前面說過，“顛倒的”生成項(xiàng)是0xEDB88320。
INIT
這是算法開始時寄存器的初始化預(yù)置值，十六進(jìn)制表示。
這個值可以直接賦值給“直驅(qū)表法”算法中的寄存器，作為寄存器的初始值！
而對于“驅(qū)動表法”算法及“直接計(jì)算法”，寄存器的初始值必須是0！前面幾次循環(huán)先將待測數(shù)據(jù)移入到寄存器中，當(dāng)寄存器裝滿后，再用這個初始化預(yù)置值去XOR寄存器，這樣寄存器就被這個值初始化了！
這點(diǎn)很重要??！如果在“驅(qū)動表法”算法開始時，寄存器的初始值不為0，那么寄存器中的值就會相當(dāng)于是待測數(shù)據(jù)了，這樣算出的CRC結(jié)果就不對了！我們的目的是用預(yù)置值去初始化寄存器，而不是將預(yù)置值作為待測數(shù)據(jù)去處理！
REFIN
這個值是真TRUE或假FALSE。
如果這個值是FALSE，表示待測數(shù)據(jù)的每個字節(jié)都不用“顛倒”，即BIT7仍是作為最高位，BIT0作為最低位。
如果這個值是TRUE，表示待測數(shù)據(jù)的每個字節(jié)都要先“顛倒”，即BIT7作為最低位，BIT0作為最高位。
REFOUT
這個值是真TRUE或假FALSE。
如果這個值是FALSE，表示計(jì)算結(jié)束后，寄存器中的值直接進(jìn)入XOROUT處理即可。
如果這個值是TRUE，表示計(jì)算結(jié)束后，寄存器中的值要先“顛倒”，再進(jìn)入XOROUT處理。注意，這是將整個寄存器的值顛倒，因?yàn)榧拇嫫鞯母鱾€字節(jié)合起來表達(dá)了一個值，如果只是對各個字節(jié)各自顛倒，那結(jié)果值就錯誤了。
XOROUT
這是W位長的16進(jìn)制數(shù)值。
這個值與經(jīng)REFOUT后的寄存器的值相XOR，得到的值就是最終正式的CRC值！
CHECK
這不是定義值的一部分，這只是字串"123456789"用這個CRC參數(shù)模型計(jì)算后得到的CRC值，作為參考。
我們發(fā)現(xiàn)，CRC32模型的Init=0xFFFFFFFF，就是說寄存器要用0xFFFFFFFF進(jìn)行初始化，而不是0。
為什么？因?yàn)榇郎y數(shù)據(jù)的內(nèi)容和長度是隨機(jī)的，如果寄存器初始值為0，那么，待測字節(jié)是1字節(jié)的0x00，與待測字節(jié)是N字節(jié)的0x00，計(jì)算出來的CRC32值都是0，那CRC值就沒有意義了！所以寄存器用0xFFFFFFFF進(jìn)行初始化，就可以避免這個問題了！
RefIn=True，表示輸入數(shù)據(jù)的每個字節(jié)需要“顛倒”！為什么要“顛倒”，因?yàn)楹芏嘤布诎l(fā)送時是先發(fā)送最低位LSB的！比如UART等。
字節(jié)順序不用顛倒，只是每個字節(jié)內(nèi)部的比特進(jìn)行顛倒。例如待測的字串是"1234"，這時也是一樣先處理"1"，再處理"2"，一直到處理"4"。處理字符"1"時，它是0x31，即0011 0001，需要先將它顛倒，變成低位在前，即1000 1100，即0x8C，再進(jìn)行處理。
也就是說，待處理的數(shù)據(jù)是0x31 32 33 34，顛倒后就變成0x8C 4C CC 2C，再進(jìn)行CRC計(jì)算。
RefOut=True，表示計(jì)算完成后，要將寄存器中的值再顛倒。注意，這是將整個寄存器的值顛倒，即如果寄存器中的值是0x31 32 33 34，顛倒后就變成0x2C CC 4C 8C！
XorOut=FFFFFFFF，表示還需要將結(jié)果值與0xffffffff進(jìn)行XOR，這樣就得到最終的CRC32值了！
我們直接用“直驅(qū)表法”，計(jì)算字串"1234"的CRC32值。
程序如下：
要先做一個顛倒比特的子程序：
unsigned long int Reflect(unsigned long int ref, char ch)
{
unsigned long int value=0;
// 交換bit0和bit7，bit1和bit6，類推
for(int i = 1; i < (ch + 1); i++)
{
if(ref & 1)
value |= 1 << (ch - i);
ref >>= 1;
}
return value;
}
在主程序中的程序：
// 注意：因生成項(xiàng)POLY最高位一定為“1”，故略去最高位的"1"，
unsigned long cnCRC_32 = 0x04C11DB7; //采用正規(guī)的CRC32的POLY
unsigned long Table_CRC32[256]; // CRC32 表
// 構(gòu)造 32 位 CRC 表 "直接查詢表"
unsigned long i32, j32;
unsigned long nData32;
unsigned long nAccum32;
for ( i32 = 0; i32 < 256; i32++ )
{
nData32 = ( unsigned long )( i32 << 24 );
nAccum32 = 0;
for ( j32 = 0; j32 < 8; j32++ )
{
if ( ( nData32 ^ nAccum32 ) & 0x80000000 )
nAccum32 = ( nAccum32 << 1 ) ^ cnCRC_32;
else
nAccum32 <<= 1;
nData32 <<= 1;
}
Table_CRC32[i32] = nAccum32;
}
unsigned char aData[512]={0x31,0x32,0x33,0x34}; //待測數(shù)據(jù)，為字串"1234"
unsigned long aSize;
unsigned long i;
unsigned char *point;
unsigned char chtemp;
// 計(jì)算 32 位 CRC-32 值
//Table-Driven驅(qū)動表法，需要用到“直接查詢表”（不能用“正規(guī)查詢表”）；待測數(shù)據(jù)需擴(kuò)展0
unsigned long ii;
unsigned long CRC32_1;
aSize=4; //數(shù)據(jù)長度字節(jié)（不包含擴(kuò)展0）
CRC32_1=0x0; //寄存器歸0
point=aData;
ii=0;
while (aSize--)
{
chtemp=*point++;
chtemp=(unsigned char)Reflect(chtemp, 8); //將數(shù)據(jù)字節(jié)內(nèi)部的比特進(jìn)行顛倒
CRC32_1 = ((CRC32_1 << 8) | chtemp) ^ Table_CRC32[(CRC32_1 >> 24) & 0xFF];
ii++;
if (ii==4) CRC32_1=CRC32_1^0xffffffff;//當(dāng)寄存器裝滿4個字節(jié)后，用預(yù)置值0xffffffff去XOR寄存器，這樣寄存器就被這個值初始化了！
}
for ( i = 0; i < 4; i++ )
{
CRC32_1 = ((CRC32_1 << 8) ) ^ Table_CRC32[(CRC32_1 >> 24) & 0xFF]; //加入4字節(jié)的擴(kuò)展0
ii++;
if (ii==4) CRC32_1=CRC32_1^0xffffffff;//如果待測數(shù)據(jù)小于4字節(jié)，則只有在這里寄存器才會裝滿4個字節(jié)，才進(jìn)行初始化
}
CRC32_1=Reflect(CRC32_1, 32); //顛倒寄存器的值
CRC32_1=CRC32_1^0xffffffff; //寄存器的值與0xffffffff異或
//這時， CRC32_1中的值就是CRC
//DIRECT TABLE直驅(qū)表法，需要用到“直接查詢表”（不能用“正規(guī)查詢表”）；待測數(shù)據(jù)不需要擴(kuò)展0
unsigned long CRC32_2;
aSize=4; //數(shù)據(jù)長度字節(jié)（數(shù)據(jù)不用擴(kuò)展0了）
CRC32_2 = 0xffffffff; //寄存器中直接預(yù)置初始值0xffffffff即可
point=aData;
for ( i = 0; i < aSize; i++ )
{
chtemp=*point++;
chtemp=(unsigned char)Reflect(chtemp, 8); //將數(shù)據(jù)字節(jié)內(nèi)部的比特進(jìn)行顛倒
CRC32_2 = ( CRC32_2 << 8 ) ^ Table_CRC32[( CRC32_2 >> 24 ) ^ chtemp];
}
CRC32_2=Reflect(CRC32_2, 32); //顛倒寄存器的值
CRC32_2=CRC32_2^0xffffffff; //寄存器的值與0xffffffff異或
//這時， CRC32_2中的值就是CRC
得到的結(jié)果與WINRAR的計(jì)算結(jié)果是完全一樣的！成功了！
其它的CRC參數(shù)模型：
Name : "CRC-16"
Width : 16
Poly : 8005
Init : 0000
RefIn : True
RefOut : True
XorOut : 0000
Check : BB3D
Name : "CRC-16/CITT"
Width : 16
Poly : 1021
Init : FFFF
RefIn : False
RefOut : False
XorOut : 0000
Check : ?
Name : "XMODEM"
Width : 16
Poly : 8408
Init : 0000
RefIn : True
RefOut : True
XorOut : 0000
Check : ?
Name : "ARC"
Width : 16
Poly : 8005
Init : 0000
RefIn : True
RefOut : True
XorOut : 0000
Check : ?
七、 最后的戰(zhàn)斗－“顛倒的直驅(qū)表法”算法 "Reflected" Table-Driven Implementations
顛倒，也就是鏡像！
CRC32要求輸入的字節(jié)要顛倒，那么在程序中，在對每個字節(jié)處理前，還要先把這個字節(jié)先顛倒一下，再處理，那不是超級麻煩！
所以就把“直驅(qū)表法”算法顛倒一下（查詢表顛倒），那么算法就可以直接處理不顛倒的字節(jié)了，就方便多了。
我們把算法照鏡子：
“直驅(qū)表法” 鏡子 “顛倒的直驅(qū)表法”
+-----<Message (non augmented) 待測數(shù)據(jù)（要顛倒） | v 3 2 1 0 Bytes | +----+----+----+----+ XOR----<| | | | | | +----+----+----+----+ | MSB ^ LSB | | | XOR | | | 00H +----+----+----+----+ 查表v 01H +----+----+----+----+ 04C11DB7H | 02H +----+----+----+----+ | 03H +----+----+----+----+ | +----+----+----+----+ | +----+----+----+----+ | +----+----+----+----+ +-----> +----+----+----+----+ +----+----+----+----+ 80H +----+----+----+----+ 690CE0EEH +----+----+----+----+ +----+----+----+----+ FFH +----+----+----+----+ 索引值和表值都不顛倒
待測數(shù)據(jù)（不顛倒）Message (non augmented) >-----+ | Bytes 3 2 1 0 v +----+----+----+----+ | | | | | |>----XOR +----+----+----+----+ | MSB ^ LSB | | | XOR | | | +----+----+----+----+ 00H | EDB88320H +----+----+----+----+ 80H v查表 +----+----+----+----+ C0H | +----+----+----+----+ 20H | +----+----+----+----+ A0H | +----+----+----+----+ | +----+----+----+----+ | +----+----+----+----+<-----+ +----+----+----+----+ 77073096H +----+----+----+----+ 01H +----+----+----+----+ +----+----+----+----+ +----+----+----+----+255 索引值和表值都顛倒 |
“顛倒的直驅(qū)表法”用的查詢表，是網(wǎng)上可以找到的查詢表，我叫它“正規(guī)查詢表”，實(shí)際就是“顛倒的直接查詢表”。對應(yīng)關(guān)系是：
“直接查詢表” “正規(guī)查詢表”（顛倒的查詢表）
0000 0000（00H） 0000 0000（00H）
0000 0001（01H）表值04C11DB7H 1000 0000（80H）表值EDB88320H
0000 0010（02H） 0100 0000（C0H）
0000 0011（03H） 1100 0000（20H）
0000 0100（04H） 0010 0000（A0H）
...
1000 0000（80H）表值690CE0EEH 0000 0001（01H）表值77073096H
...
1111 1111（FFH） FFFF FFFF（FFH）
也就是說，將“直接查詢表”的索引值和表值直接鏡像就是“正規(guī)查詢表”。
比如，直接查詢表的[01H]= 04C11DB7H，因?yàn)?1H鏡像后是80H，04C11DB7H鏡像后是EDB88320H，就得到正規(guī)查詢表的[80H]= EDB88320H。
舉例來說，假設(shè)待測的原始數(shù)據(jù)是10H，簡單起見，不考慮寄存器移出的字節(jié)的影響（即假設(shè)它是00H）：
“直驅(qū)表法”，原始數(shù)據(jù)先顛倒為01H，根據(jù)01H查表得04C11DB7H，寄存器移出的字節(jié)是向左移。
“顛倒的直驅(qū)表法”， 直接根據(jù)原始數(shù)據(jù)10H查表得EDB88320H，寄存器移出的字節(jié)是向右移。
可見，這時這二個方法本質(zhì)上是一樣的。
對于“直驅(qū)表法”，顛倒的數(shù)據(jù)用不顛倒的表索引值、得到不顛倒的表值寄存器進(jìn)入寄存器，得到的寄存器結(jié)果值是不顛倒的，還要再顛倒，變成“顛倒的CRC”。
對于“顛倒的直驅(qū)表法”，不顛倒的數(shù)據(jù)用顛倒的表索引值、得到顛倒的表值寄存器進(jìn)入寄存器，得到的寄存器結(jié)果值就已經(jīng)是“顛倒的CRC”，不用再顛倒了。
可見，對于REFIN=TRUE并且REFOUT=TRUE的CRC模型來說（注意這個先決條件），就可以直接用“顛倒的直驅(qū)表法”來代替“直驅(qū)表法”，這樣原始數(shù)據(jù)的比特不用鏡像，處理起來就很簡單。
那是不是說：不顛倒的數(shù)據(jù)用不顛倒的表索引值和表值，把得到的寄存器結(jié)果值顛倒一下，就能得到和顛倒的數(shù)據(jù)一樣的計(jì)算結(jié)果？不可能的。顛倒的數(shù)據(jù)和不顛倒的數(shù)據(jù)是完全不一樣的數(shù)據(jù)，得到的結(jié)果完全兩碼事。
注意：
先決條件是REFIN=TRUE并且REFOUT=TRUE的CRC參數(shù)模型。
“顛倒的直驅(qū)表法”用的是“正規(guī)查詢表”。
寄存器的初始化預(yù)置值也要顛倒。
待測數(shù)據(jù)每個字節(jié)的比特不用顛倒，因?yàn)樗惴ǖ钠渌糠侄甲鲞^顛倒處理了。
待測數(shù)據(jù)串肯定不用顛倒，即待測的字串是"1234"，這時也是一樣先處理"1"，再處理"2"，一直到處理"4"。
算法如下:
1. 將寄存器向右移動一個字節(jié)。
2. 將剛移出的那個字節(jié)與待測數(shù)據(jù)中的新字節(jié)做XOR運(yùn)算，得到一個指向查詢表的索引值。
3. 將索引所指的表值與寄存器做XOR運(yùn)算。
4. 如數(shù)據(jù)沒有全部處理完，則跳到步驟1。
用C可以寫成這樣：
r=0; //r是寄存器，先初始化為0
for(i=0; i <len; i++) //len是待測數(shù)據(jù)（不用擴(kuò)展0）的字節(jié)長度
{
r = t[( r^(*(p+i)) ) & 0xff] ^ (r >> 8); //p是指向待測數(shù)據(jù)的指針,t是查詢表
}
“正規(guī)查詢表”的內(nèi)容是：
CRC16正規(guī)查詢表
00h 0000 C0C1 C181 0140 C301 03C0 0280 C241
08h C601 06C0 0780 C741 0500 C5C1 C481 0440
10h CC01 0CC0 0D80 CD41 0F00 CFC1 CE81 0E40
18h 0A00 CAC1 CB81 0B40 C901 09C0 0880 C841
20h D801 18C0 1980 D941 1B00 DBC1 DA81 1A40
28h 1E00 DEC1 DF81 1F40 DD01 1DC0 1C80 DC41
30h 1400 D4C1 D581 1540 D701 17C0 1680 D641
38h D201 12C0 1380 D341 1100 D1C1 D081 1040
40h F001 30C0 3180 F141 3300 F3C1 F281 3240
48h 3600 F6C1 F781 3740 F501 35C0 3480 F441
50h 3C00 FCC1 FD81 3D40 FF01 3FC0 3E80 FE41
58h FA01 3AC0 3B80 FB41 3900 F9C1 F881 3840
60h 2800 E8C1 E981 2940 EB01 2BC0 2A80 EA41
68h EE01 2EC0 2F80 EF41 2D00 EDC1 EC81 2C40
70h E401 24C0 2580 E541 2700 E7C1 E681 2640
78h 2200 E2C1 E381 2340 E101 21C0 2080 E041
80h A001 60C0 6180 A141 6300 A3C1 A281 6240
88h 6600 A6C1 A781 6740 A501 65C0 6480 A441
90h 6C00 ACC1 AD81 6D40 AF01 6FC0 6E80 AE41
98h AA01 6AC0 6B80 AB41 6900 A9C1 A881 6840
A0h 7800 B8C1 B981 7940 BB01 7BC0 7A80 BA41
A8h BE01 7EC0 7F80 BF41 7D00 BDC1 BC81 7C40
B0h B401 74C0 7580 B541 7700 B7C1 B681 7640
B8h 7200 B2C1 B381 7340 B101 71C0 7080 B041
C0h 5000 90C1 9181 5140 9301 53C0 5280 9241
C8h 9601 56C0 5780 9741 5500 95C1 9481 5440
D0h 9C01 5CC0 5D80 9D41 5F00 9FC1 9E81 5E40
D8h 5A00 9AC1 9B81 5B40 9901 59C0 5880 9841
E0h 8801 48C0 4980 8941 4B00 8BC1 8A81 4A40
E8h 4E00 8EC1 8F81 4F40 8D01 4DC0 4C80 8C41
F0h 4400 84C1 8581 4540 8701 47C0 4680 8641
F8h 8201 42C0 4380 8341 4100 81C1 8081 4040
CRC32正規(guī)查詢表
00h 00000000 77073096 EE0E612C 990951BA
04h 076DC419 706AF48F E963A535 9E6495A3
08h 0EDB8832 79DCB8A4 E0D5E91E 97D2D988
0Ch 09B64C2B 7EB17CBD E7B82D07 90BF1D91
10h 1DB71064 6AB020F2 F3B97148 84BE41DE
14h 1ADAD47D 6DDDE4EB F4D4B551 83D385C7
18h 136C9856 646BA8C0 FD62F97A 8A65C9EC
1Ch 14015C4F 63066CD9 FA0F3D63 8D080DF5
20h 3B6E20C8 4C69105E D56041E4 A2677172
24h 3C03E4D1 4B04D447 D20D85FD A50AB56B
28h 35B5A8FA 42B2986C DBBBC9D6 ACBCF940
2Ch 32D86CE3 45DF5C75 DCD60DCF ABD13D59
30h 26D930AC 51DE003A C8D75180 BFD06116
34h 21B4F4B5 56B3C423 CFBA9599 B8BDA50F
38h 2802B89E 5F058808 C60CD9B2 B10BE924
3Ch 2F6F7C87 58684C11 C1611DAB B6662D3D
40h 76DC4190 01DB7106 98D220BC EFD5102A
44h 71B18589 06B6B51F 9FBFE4A5 E8B8D433
48h 7807C9A2 0F00F934 9609A88E E10E9818
4Ch 7F6A0DBB 086D3D2D 91646C97 E6635C01
50h 6B6B51F4 1C6C6162 856530D8 F262004E
54h 6C0695ED 1B01A57B 8208F4C1 F50FC457
58h 65B0D9C6 12B7E950 8BBEB8EA FCB9887C
5Ch 62DD1DDF 15DA2D49 8CD37CF3 FBD44C65
60h 4DB26158 3AB551CE A3BC0074 D4BB30E2
64h 4ADFA541 3DD895D7 A4D1C46D D3D6F4FB
68h 4369E96A 346ED9FC AD678846 DA60B8D0
6Ch 44042D73 33031DE5 AA0A4C5F DD0D7CC9
70h 5005713C 270241AA BE0B1010 C90C2086
74h 5768B525 206F85B3 B966D409 CE61E49F
78h 5EDEF90E 29D9C998 B0D09822 C7D7A8B4
7Ch 59B33D17 2EB40D81 B7BD5C3B C0BA6CAD
80h EDB88320 9ABFB3B6 03B6E20C 74B1D29A
84h EAD54739 9DD277AF 04DB2615 73DC1683
88h E3630B12 94643B84 0D6D6A3E 7A6A5AA8
8Ch E40ECF0B 9309FF9D 0A00AE27 7D079EB1
90h F00F9344 8708A3D2 1E01F268 6906C2FE
94h F762575D 806567CB 196C3671 6E6B06E7
98h FED41B76 89D32BE0 10DA7A5A 67DD4ACC
9Ch F9B9DF6F 8EBEEFF9 17B7BE43 60B08ED5
A0h D6D6A3E8 A1D1937E 38D8C2C4 4FDFF252
A4h D1BB67F1 A6BC5767 3FB506DD 48B2364B
A8h D80D2BDA AF0A1B4C 36034AF6 41047A60
ACh DF60EFC3 A867DF55 316E8EEF 4669BE79
B0h CB61B38C BC66831A 256FD2A0 5268E236
B4h CC0C7795 BB0B4703 220216B9 5505262F
B8h C5BA3BBE B2BD0B28 2BB45A92 5CB36A04
BCh C2D7FFA7 B5D0CF31 2CD99E8B 5BDEAE1D
C0h 9B64C2B0 EC63F226 756AA39C 026D930A
C4h 9C0906A9 EB0E363F 72076785 05005713
C8h 95BF4A82 E2B87A14 7BB12BAE 0CB61B38
CCh 92D28E9B E5D5BE0D 7CDCEFB7 0BDBDF21
D0h 86D3D2D4 F1D4E242 68DDB3F8 1FDA836E
D4h 81BE16CD F6B9265B 6FB077E1 18B74777
D8h 88085AE6 FF0F6A70 66063BCA 11010B5C
DCh 8F659EFF F862AE69 616BFFD3 166CCF45
E0h A00AE278 D70DD2EE 4E048354 3903B3C2
E4h A7672661 D06016F7 4969474D 3E6E77DB
E8h AED16A4A D9D65ADC 40DF0B66 37D83BF0
ECh A9BCAE53 DEBB9EC5 47B2CF7F 30B5FFE9
F0h BDBDF21C CABAC28A 53B39330 24B4A3A6
F4h BAD03605 CDD70693 54DE5729 23D967BF
F8h B3667A2E C4614AB8 5D681B02 2A6F2B94
FCh B40BBE37 C30C8EA1 5A05DF1B 2D02EF8D
“顛倒的直驅(qū)表法”的程序：
同樣要先做一個顛倒比特的子程序：
unsigned long int Reflect(unsigned long int ref, char ch)
{
unsigned long int value=0;
// 交換bit0和bit7，bit1和bit6，類推
for(int i = 1; i < (ch + 1); i++)
{
if(ref & 1)
value |= 1 << (ch - i);
ref >>= 1;
}
return value;
}
在主程序中的程序：
unsigned long int crc32_table[256];
unsigned long int ulPolynomial = 0x04c11db7;
unsigned long int crc,temp;
for(int i = 0; i <= 0xFF; i++) // 生成CRC32“正規(guī)查詢表”
{
temp=Reflect(i, 8);
crc32_table[i]= temp<< 24;
for (int j = 0; j < 8; j++)
{
unsigned long int t1,t2;
unsigned long int flag=crc32_table[i]&0x80000000;
t1=(crc32_table[i] << 1);
if(flag==0)
t2=0;
else
t2=ulPolynomial;
crc32_table[i] =t1^t2 ;
}
crc=crc32_table[i];
crc32_table[i] = Reflect(crc32_table[i], 32);
}
//計(jì)算CRC32值
unsigned long CRC32;
BYTE DataBuf[512]={0x31,0x32,0x33,0x34}; //待測數(shù)據(jù)，為字串"1234"
unsigned long len;
unsigned long ii;
unsigned long m_CRC = 0xFFFFFFFF; //寄存器中預(yù)置初始值
BYTE *p;
len=4; //待測數(shù)據(jù)的字節(jié)長度
p = DataBuf;
for(ii=0; ii <len; ii++)
{
m_CRC = crc32_table[( m_CRC^(*(p+ii)) ) & 0xff] ^ (m_CRC >> 8); //計(jì)算
}
CRC32= ~m_CRC; //取反。經(jīng)WINRAR對比，CRC32值正確?。?/p>
//這時， CRC32中的值就是CRC
八、 結(jié)束
以上程序均在VC6中測試成功，很多程序是直接抄網(wǎng)上的再修改。
CRC計(jì)算其實(shí)很簡單，也就才4個算法，移來移去、優(yōu)化來優(yōu)化去而已。
但是就是這么簡單的東西，國內(nèi)網(wǎng)上好像沒有文章能說得完全明白。搞得我這種笨人花了整整5天才整理出來。
書上的都是理論一大堆，這個式子那個式子的，一頭霧水，我這個非專業(yè)人士更看不懂。
應(yīng)該說，用程序?qū)崿F(xiàn)和優(yōu)化算法是容易的，創(chuàng)造出CRC方法的人才是真正的強(qiáng)人。
