CRC-16/CRC-32 程序代碼
2019-11-17 05:21:57
供稿：網友
不久前寫一程序時要用到 CRC-16 ，但找來找去只在 UDDF 里找到一個 Delphi 的 CRC-32 程序代碼，而且是用查表法，雖然說查表法速度快，但 256 項 32 位數據我懷疑可能會有輸入錯誤， 讓人不是那么放心，而我又不知道這個表是怎么算出來的。后來我又在一本兩年前的筆記本里找到一段關于 CRC 的內容， 也不知是從哪里抄來的，還好里面有一段程序代碼，是 CRC-16 的，這段程序正是產生 CRC 表的， 可是這區區幾行的程序（基本上與下面的 BuilderTable16 函數相同）看得我一頭霧水，直到這兩天才弄明白， 并據此推出 CRC-32 的算法，現將全部程序列在下面，并作一些說明以助于理解，不但要知其然，還要知其所以然嘛：
// 注重：因最高位一定為“1”，故略去
const unsigned short cnCRC_16 = 0x8005;
// CRC-16 = X16 + X15 + X2 + X0
const unsigned short cnCRC_CCITT = 0x1021;
// CRC-CCITT = X16 + X12 + X5 + X0，據說這個 16 位 CRC 多項式比上一個要好
const unsigned long cnCRC_32 = 0x04C10DB7;
// CRC-32 = X32 + X26 + X23 + X22 + X16 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + X0
unsigned long Table_CRC[256]; // CRC 表
// 構造 16 位 CRC 表
void BuildTable16( unsigned short aPoly )
{
unsigned short i, j;
unsigned short nData;
unsigned short nAccum;
for ( i = 0; i < 256; i++ )
{
nData = ( unsigned short )( i << 8 );
nAccum = 0;
for ( j = 0; j < 8; j++ )
{
if ( ( nData ^ nAccum ) & 0x8000 )
nAccum = ( nAccum << 1 ) ^ aPoly;
else
nAccum <<= 1;
nData <<= 1;
}
Table_CRC[i] = ( unsigned long )nAccum;
}
}
// 計算 16 位 CRC 值，CRC-16 或 CRC-CCITT
unsigned short CRC_16( unsigned char * aData, unsigned long aSize )
{
unsigned long i;
unsigned short nAccum = 0;
BuildTable16( cnCRC_16 ); // or cnCRC_CCITT
for ( i = 0; i < aSize; i++ )
nAccum = ( nAccum << 8 ) ^ ( unsigned short )Table_CRC[( nAccum >> 8 ) ^ *aData++];
return nAccum;
}
// 構造 32 位 CRC 表
void BuildTable32( unsigned long aPoly )
{
unsigned long i, j;
unsigned long nData;
unsigned long nAccum;
for ( i = 0; i < 256; i++ )
{
nData = ( unsigned long )( i << 24 );
nAccum = 0;
for ( j = 0; j < 8; j++ )
{
if ( ( nData ^ nAccum ) & 0x80000000 )
nAccum = ( nAccum << 1 ) ^ aPoly;
else
nAccum <<= 1;
nData <<= 1;
}
Table_CRC[i] = nAccum;
}
}
// 計算 32 位 CRC-32 值
unsigned long CRC_32( unsigned char * aData, unsigned long aSize )
{
unsigned long i;
unsigned long nAccum = 0;
BuildTable32( cnCRC_32 );
for ( i = 0; i < aSize; i++ )
nAccum = ( nAccum << 8 ) ^ Table_CRC[( nAccum >> 24 ) ^ *aData++];
return nAccum;
}
說明： CRC 的計算原理如下（一個字節的簡單例子）
11011000 00000000 00000000 <- 一個字節數據, 左移 16b
^10001000 00010000 1 <- CRC-CCITT 多項式, 17b
--------------------------
1010000 00010000 10 <- 中間余數
^1000100 00001000 01
-------------------------
10100 00011000 1100
^10001 00000010 0001
-----------------------
101 00011010 110100
^100 01000000 100001
---------------------
1 01011010 01010100
^1 00010000 00100001
-------------------
01001010 01110101 <- 16b CRC
仿此，可推出兩個字節數據計算如下：d 為數據，p 為項式，a 為余數
dddddddd dddddddd 00000000 00000000 <- 數據 D ( D1, D0, 0, 0 )
^pppppppp pppppppp p <- 多項式 P
-----------------------------------
...
aaaaaaaa aaaaaaaa 0 <- 第一次的余數 A'' ( A''1, A''0 )
^pppppppp pppppppp p
--------------------------
...
aaaaaaaa aaaaaaaa <- 結果 A ( A1, A0 )
由此與一字節的情況比較，將兩個字節分開計算如下：
先算高字節：
dddddddd 00000000 00000000 00000000 <- D1, 0, 0, 0
^pppppppp pppppppp p <- P
-----------------------------------
...
aaaaaaaa aaaaaaaa <- 高字節部分余數 PHA1, PHA0
此處的部分余數與前面兩字節算法中的第一次余數有如下關系，即 A''1 = PHA1 ^ D0, A''0 = PHA0：
aaaaaaaa aaaaaaaa <- PHA1, PHA0
^dddddddd <- D0
-----------------
aaaaaaaa aaaaaaaa <- A''1, A''0
低字節的計算：
aaaaaaaa 00000000 00000000 <- A''1, 0, 0
^pppppppp pppppppp p <- P
--------------------------
...
aaaaaaaa aaaaaaaa <- 低字節部分余數 PLA1, PLA0
^aaaaaaaa <- A''0 ， 即 PHA0
-----------------
aaaaaaaa aaaaaaaa <- 最后的 CRC ( A1, A0 )
總結以上內容可得規律如下：
設部分余數函數
PA = f( d )
其中 d 為一個字節的數據（注重，除非 n = 0 ，否則就不是原始數據，見下文）
第 n 次的部分余數
PA( n ) = ( PA( n - 1 ) << 8 ) ^ f( d )
其中的
d = ( PA( n - 1 ) >> 8 ) ^ D( n )
其中的 D( n ) 才是一個字節的原始數據。
公式如下：
PA( n ) = ( PA( n - 1 ) << 8 ) ^ f( ( PA( n - 1 ) >> 8 ) ^ D( n ) )
可以注重到函數 f( d ) 的參數 d 為一個字節，對一個確定的多項式 P， f( d ) 的返回值
是與 d 一一對應的，總數為 256 項，將這些數據預先算出保存在表里，f( d )就轉換為一
個查表的過程，速度也就可以大幅提高，這也就是查表法計算 CRC 的原理，在 CRC_16 和
CRC_32 兩個函數的循環中的語句便是上面那個公式。
再來看 CRC 表是如何計算出來的，即函數 f( d ) 的實現方法。分析前面一個字節數據的
計算過程可發現，d 對結果的影響只表現為對 P 的移位異或，看計算過程中的三個 8 位
的列中只有低兩個字節的最后結果是余數，而數據所在的高 8 位列最后都被消去了，因其
中的運算均為異或，不產生進位或借位，故每一位數據只影響本列的結果，即 d 并不直接
影響結果。再將前例變化一下重列如下：
11011000
--------------------------
10001000 00010000 1 // P
^ 1000100 00001000 01 // P
^ 000000 00000000 000 // 0
^ 10001 00000010 0001 // P
^ 0000 00000000 00000 // 0
^ 100 01000000 100001 // P
^ 00 00000000 0000000 // 0
^ 1 00010000 00100001 // P
-------------------
01001010 01110101
現在的問題就是如何根據 d 來對 P 移位異或了，從上面的例子看，也可以理解為每步
移位，但根據 d 決定中間余數是否與 P 異或。從前面原來的例子可以看出，決定的條
件是中間余數的最高位為0，因為 P 的最高位一定為1，即當中間余數與 d 相應位異或
的最高位為1時，中間余數移位就要和 P 異或，否則只需移位即可。具體做法見程序中
的 BuildTable16 和 BuildTable32 兩個函數，其方法如下例（上例的變形，注重其中
空格的移動表現了 d 的影響如何被排除在結果之外）：
d --------a--------
1 00000000 00000000 <- HSB = 1
0000000 000000000 <- a <<= 1
0001000 000100001 <- P, CRC-CCITT 不含最高位的 1
-----------------
1 0001000 000100001
001000 0001000010
000100 0000100001
-----------------
0 001100 0001100011 <- HSB = 0
01100 00011000110
-----------------
1 01100 00011000110 <- HSB = 1
1100 000110001100
0001 000000100001
-----------------
1 1101 000110101101 <- HSB = 0
101 0001101011010
-----------------
0 101 0001101011010 <- HSB = 1
01 00011010110100
00 01000000100001
-----------------
0 01 01011010010101 <- HSB = 0
1 010110100101010
-----------------
0 1 010110100101010 <- HSB = 1
0101101001010100
0001000000100001
-----------------
0100101001110101 <- CRC
結合這些，前面的程序就好理解了。至于 32 位 CRC 的計算與 16 相似，就不多加說明，請參考源程序。
