From:?http://blog.csdn.net/sparkliang/article/details/5671977

CRC算法詳解（2）

初見?Table-Driven

?

變換到上面的方法后，我們離?table-driven?的方法只有一步之遙了，我們知道一個字節能表示的正整數范圍是?0~255，步驟?1?中的計算就是針對?reg?的高?Byte?位進行的，于是可以被提取出來，預先計算并存儲到一個有?256?項的表中，于是下面的算法就出爐了，這個和上面的算法本質上并沒有什么區別。

[cpp]?view plaincopy

#define?POLY?0x04C11DB7L?//?CRC32生成多項式??

static?unsigned?int?crc_table[256];??

unsigned?int?get_sum_poly(unsigned?char?data)??

{??

????unsigned?int?sum_poly?=?data;??

????sum_poly?<<=?24;??

????for(int?j?=?0;?j?<?8;?j++)??

????{??

????????int?hi?=?sum_poly&0x80000000;?//?取得reg的最高位??

????????sum_poly?<<=?1;??

????????if(hi)?sum_poly?=?sum_poly^POLY;??

????}??

????return?sum_poly;??

}??

void?create_crc_table()??

{??

????for(int?i?=?0;?i?<?256;?i++)??

????{??

????????crc_table[i]?=?get_sum_poly(i&0xFF);??

????}??

}??

//?以byte數據為例??

unsigned?int?CRC32_3(unsigned?int?data)??

{??

????unsigned?char?p[8];??

????memset(p,?0,?sizeof(p));??

????memcpy(p,?&data,?4);??

????unsigned?int?reg?=?0,?sum_poly?=?0;??

????for(int?i?=?0;?i?<?8;?i++)??

????{??

????????//?計算步驟1??

????????sum_poly?=?crc_table[(reg>>24)&0xFF];??

????????//?計算步驟2??

????????reg?=?(reg<<8)|p[i];??

????????reg?=?reg?^?sum_poly;??

????}??

????return?reg;??

}??

更進一步

?

上面的這個算法已經是一個Table-Driven的CRC-32算法了，但是實際上我們看到的CRC校驗代碼都是如下的形式：<div><div><div style="color:silver;"><strong>[cpp]</strong> <a target=_blank href="http://blog.csdn.net/sparkliang/article/details/5671977#" title="view plain" style="color:rgb(160, 160, 160);">view plain</a><a target=_blank href="http://blog.csdn.net/sparkliang/article/details/5671977#" title="copy" style="color:rgb(160, 160, 160);">copy</a></div></div><ol start="1" style="color:rgb(92, 92, 92);"><li style="color:inherit;"><span style="color:black;">r=0;??</span></li><li><span style="color:black;"><span style="color:rgb(0, 102, 153);">while</span>(len--)??</span></li><li style="color:inherit;"><span style="color:black;">?????r?=?(r<<8)?^?t[(r?>>?24)?^?*p++];??</span></li></ol></div>

下面我們將看看是做了什么轉化而做到這一點的。

?

?

首先上述?CRC?算法中，我們需要為原始數據追加?r/8Byte?個?0?，?CRC-32?就是?4Byte?。或者我們可以再計算原始數據之后，把?0?放在后面單獨計算，像這樣：

[cpp]?view plaincopy

//?先計算原始數據??

for(int?i?=?0;?i?<?len;?i++)??

{??

????????sum_poly?=?crc_table[(reg>>24)&0xFF];??

????????reg?=?(reg<<8)|p[i];??

????????reg?=?reg?^?sum_poly;??

}??

//?再計算追加的4Byte?0??

for(int?i?=?0;?i?<?4;?i++)??

{??

????????reg?=?(reg<<8)?^?crc_table[(reg>>24)&0xFF];??

}??

這看起來已經足夠好了，而事實上我們可以繼續向下進行以免去為了附加的?0?而進行計算。在上面算法中，最后的?4?次循環是為了將輸入數據的最后?r/8?位都移出?reg?，因為?0?對?reg?的值并沒有絲毫影響。

對于?CRC-32?，對于任何輸入數據?Dn...D8…D5D4…D1?，第一個?for?循環將?Dn…D8…D5?都依次移入，執行XOR?運算再移出?reg?；并將?D4…D1?都移入了?reg?，但是并未移出；因此最后的?4?次循環是為了將?D4…D1?都移出?reg?。

Di?與?Ri?執行?XOR?運算后值將會更新，設更新后的值表示為?Di’?，不論執行了多少次?XOR?運算。

如果?reg?初始值是?0?，那么第一個?for?循環中開始的?4?次循環干的事情就是，把?Dn…Dn-3?移入到?reg?中（與0?做?XOR?結果不變），執行?4?次后?reg?的值就是?Dn.Dn-1.Dn-2.Dn-3?；

第?5?次循環的結果就是：?reg = crc_table[Dn] ^ Dn-1.Dn-2.Dn-3.Dn-4?；

第?6?次循環的結果就是：?reg = crc_table[Dn-1’] ^ Dn-2’.Dn-3’.Dn-4?；?Dn?移出?reg?。

因此上面的計算可以分為?3?個階段：

1?）前?4?次循環，將?Dn.Dn-1.Dn-2.Dn-3?裝入?reg?；

2?）中間的?n-4?次循環，依次將?Di?移入?reg?，在隨后的?4?次循環中，依次計算?Di+4?，?Di+3?，?Di+2?和?Di+1對?Di?的影響；最后移出?reg?；??

3?）最后的?4?次循環，實際上是為了計算?D4?，?D3?，?D2?和?D1?都能執行第?2?步的過程；

具體考察?Di?：

1?）?Di?移入到?reg?中，?R1=Di?，接著與?crc_table[R4]?執行?XOR?運算；

2?）循環?4?次后，?Di?成為?reg?的最高位?R4?，并且因為受到了?Dn…Di+1?的影響而更新為?Di’?；

上面的運算步驟如下面所示，其中?F?是對應得?crc_table[R]?的值。

可以清晰的看到，最后?reg?的高?Byte?是?Di?和?F?之間一次次?XOR?運算的結果。依然根據?XOR?運算的結合律，我們可以分兩步走：

1）??先執行?F?之間的?XOR?運算，設結果為?FF?，它就是?reg?的首字節；

2）??然后再直接將?Di?和?FF?進行?XOR?運算，并根據結果查?CRC?表；

3）??計算出?XOR?運算后，?Di…Di-3?已經移入?reg?；因此再將查表結果和?(reg<<8)?執行?XOR?運算即可；

這就是方法?2?，于是我們的?table-driven?的?CRC-32?校驗算法就可以寫成如下的方式了：

[cpp]?view plaincopy

reg?=?0;??

for(int?i?=?0;?i?<?len;?i++)??

{??

????reg?=?(reg<<8)?^?crc_table[(reg>>24)&0xFF?^?p[i]];??

}??

總結

以上是生活随笔為你收集整理的CRC32算法详细推导（2）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。