| 導購 | 订阅 | 在线投稿
分享
 
 
 

CRC-16/CRC-32程序代碼

來源:互聯網網民  2008-06-01 01:47:49  評論

不久前寫一程序時要用到 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 相似,就不多加說明,請參考源程序。

 
特别声明:以上内容(如有图片或视频亦包括在内)为网络用户发布,本站仅提供信息存储服务。
 
  不久前寫一程序時要用到 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 相似,就不多加說明,請參考源程序。
󰈣󰈤
王朝萬家燈火計劃
期待原創作者加盟
 
 
 
>>返回首頁<<
 
 
 
 
 
 熱帖排行
 
 
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有