探究CRC32算法實(shí)現(xiàn)原理-why table-driven implemention
Author : Kevin Lynx
email : zmhn320@163.com
Preface
基于不重造輪子的原則，本文盡量不涉及網(wǎng)絡(luò)上遍地都是的資料。
What's CRC ?
簡(jiǎn)而言之，CRC是一個(gè)數(shù)值。該數(shù)值被用于校驗(yàn)數(shù)據(jù)的正確性。CRC數(shù)值簡(jiǎn)單地說(shuō)就是通過(guò)讓你需要做
處理的數(shù)據(jù)除以一個(gè)常數(shù)而得到的余數(shù)。當(dāng)你得到這個(gè)數(shù)值后你可以將這個(gè)數(shù)值附加到你的數(shù)據(jù)后，
當(dāng)數(shù)據(jù)被傳送到其他地方后，取出原始數(shù)據(jù)(可能在傳送過(guò)程中被破壞)與附加的CRC數(shù)值，然后將這里
的原始數(shù)據(jù)除以之前那個(gè)常數(shù)(約定好的)然后得到新的CRC值。比較兩個(gè)CRC值是否相等即可確認(rèn)你的
數(shù)據(jù)是否在傳送過(guò)程中出現(xiàn)錯(cuò)誤。
那么，如何讓你的數(shù)據(jù)除以一個(gè)常數(shù)？方法是對(duì)你的數(shù)據(jù)進(jìn)行必要的編碼處理，逐字節(jié)處理成數(shù)字。
那么這個(gè)常數(shù)是什么？你不必關(guān)注它是什么，也不需要關(guān)注它是如何獲得的。當(dāng)你真的要?jiǎng)邮謱?xiě)一個(gè)
CRC的實(shí)現(xiàn)算法時(shí)，我可以告訴你，CRC的理論學(xué)家會(huì)告訴你。不同長(zhǎng)度的常數(shù)對(duì)應(yīng)著不同的CRC實(shí)現(xiàn)算法。
當(dāng)這個(gè)常數(shù)為32位時(shí)，也就是這里所說(shuō)的CRC32。
以上內(nèi)容你不必全部理解，因?yàn)槟阈枰殚喥渌Y料來(lái)獲取CRC完整的理論介紹。
The mathematics behind CRC ?
很多教科書(shū)會(huì)把CRC與多項(xiàng)式關(guān)聯(lián)起來(lái)。這里的多項(xiàng)式指的是系數(shù)為0或1的式子，例如：
a0 + a1*x + a2*x^2 + ... + an*x^n。其中a0, a1, ..., an要么為0要么為1。我們并不關(guān)注x取什么值。
(如果你要關(guān)注，你可以簡(jiǎn)單地認(rèn)為x為2) 這里把a(bǔ)0, a1, ..., an的值取出來(lái)排列起來(lái)，就可以表示比特
流。例如 1 + x + x^3所表示的比特流就為：1101。部分資料會(huì)將這個(gè)順序顛倒，這個(gè)很正常。
什么是生成多項(xiàng)式？
所謂的生成多項(xiàng)式，就是上面我所說(shuō)的常數(shù)。注意，在這里，一個(gè)多項(xiàng)式就表示了一個(gè)比特流，也就是一堆
1、0，組合起來(lái)最終就是一個(gè)數(shù)值。例如CRC32算法中，這個(gè)生成多項(xiàng)式為：
c(x) = 1 + x + x^2 + x^4 + x^5 + x^7 + x^8 + x^10 + x^11 + x^12 + x^16 + x^22 + x^23 + x^26 + x^32。
其對(duì)應(yīng)的數(shù)字就為：11101101101110001000001100100000(x^32在實(shí)際計(jì)算時(shí)隱含給出，因此這里沒(méi)有包含它
的系數(shù))，也就是0xEDB88320(多項(xiàng)式對(duì)應(yīng)的數(shù)字可能顛倒，顛倒后得到的是0x04C11DB7，其實(shí)也是正確的)。
由此可以看出，CRC值也可以看成我們的數(shù)據(jù)除以一個(gè)生成多項(xiàng)式而得到的余數(shù)。
如何做這個(gè)除法？
套用大部分教科書(shū)給出的計(jì)算方法，因?yàn)槿魏螖?shù)據(jù)都可以被處理成純數(shù)字，因此，在某種程度上說(shuō)，我們可以
直接開(kāi)始這個(gè)除法。盡管事實(shí)上這并不是標(biāo)準(zhǔn)的除法。例如，我們的數(shù)據(jù)為1101011011(方便起見(jiàn)我直接給二進(jìn)制
表示了，從這里也可以看出，CRC是按bit進(jìn)行計(jì)算的)，給定的生成多項(xiàng)式(對(duì)應(yīng)的值)為10011。通常的教科書(shū)
會(huì)告訴我們?cè)谶M(jìn)行這個(gè)除法前，會(huì)把我們的數(shù)據(jù)左移幾位(生成多項(xiàng)式位數(shù)-1位)，從而可以容納將來(lái)計(jì)算得到
的CRC值(我上面所說(shuō)的將CRC值附加到原始數(shù)據(jù)后)。但是為什么要這樣做？我也不知道。(不知道的東西不能含糊
而過(guò))那么，除法就為：
1100001010
_______________
10011 ) 11010110110000 附加了幾個(gè)零的新數(shù)據(jù)
10011......... 這里的減法(希望你不至于忘掉小學(xué)算術(shù))是一個(gè)異或操作
-----.........
10011........
10011........
-----........
00001....... 逐bit計(jì)算
00000.......
-----.......
00010......
00000......
-----......
00101.....
00000.....
-----.....
01011....
00000....
-----....
10110...
10011...
-----...
01010..
00000..
-----..
10100.
10011.
-----.
01110
00000
-----
1110 = 這個(gè)余數(shù)也就是所謂的CRC值，通常又被稱為校驗(yàn)值。
希望進(jìn)行到這里，你可以獲取更多關(guān)于CRC的感性認(rèn)識(shí)。而我們所要做的，也就是實(shí)現(xiàn)一個(gè)CRC的計(jì)算算法。
說(shuō)白了，就是提供一個(gè)程序，給定一段數(shù)據(jù)，以及一個(gè)生成多項(xiàng)式(對(duì)于CRC32算法而言該值固定)，然后
計(jì)算得出上面的1110余數(shù)。
The simplest algorithm.
最簡(jiǎn)單的實(shí)現(xiàn)算法，是一種模擬算法。我們模擬上面的除法過(guò)程，遵從網(wǎng)上一份比較全面的資料，我們?cè)O(shè)定
一個(gè)變量register。我們逐bit地將我們的數(shù)據(jù)放到register中。然后判斷register最高位是否為1，如果是
則與生成多項(xiàng)式異或操作，否則繼續(xù)處理。這個(gè)過(guò)程簡(jiǎn)單地模擬了上述除法過(guò)程：
/**////
/// 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 )
{
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;
}
better algorithm ?
很多時(shí)候這種讓人容易理解的算法都不會(huì)被實(shí)際用到。這種逐bit操作的算法實(shí)在很慢。你可能知道
一般的CRC32算法都是一種基于表(table-driven)的算法。但是你可能不知道這個(gè)表是如何來(lái)的。
一種改善這種bit after bit的方法就是將這個(gè)bit擴(kuò)大，例如典型的做法就是換成byte。這里我要詳細(xì)地?cái)⑹鱿?br>上面那種算法的過(guò)程：
我們每次會(huì)先檢查register的最高位是否為1，如果為1，則將生成多項(xiàng)式(所謂的Poly)與register進(jìn)行異或操作。
然后，將register左移一位，也就舍棄了最高位。然后將我們的數(shù)據(jù)拿一bit出來(lái)放到register的最低位。
也就是說(shuō)，register中的某一位的值會(huì)決定后面幾位的值。如果將register最高字節(jié)每一bit編碼為：
t7 t6 t5 t4 t3 t2 t1 t0。那么，t7會(huì)決定t6-t0的值(如果為1)，t6會(huì)決定t5-t0的值，依次類推。但是，無(wú)論誰(shuí)
決定誰(shuí)的值，當(dāng)上面那個(gè)算法迭代一個(gè)字節(jié)后(8bits)，t7-t0都會(huì)被丟棄(whatever you do)。唯一留下來(lái)的東西，
就是對(duì)這個(gè)字節(jié)以后字節(jié)的影響。
那么，如果我們可以直接獲取這個(gè)影響，我們就可以byte after byte地處理，而不是bit after bit。如何獲取這個(gè)
影響呢？這個(gè)影響又是什么呢？這個(gè)影響就對(duì)應(yīng)著我們的table-driven CRC算法中的表元素！
但是，為什么我們逐bit進(jìn)行計(jì)算的過(guò)程為什么可以簡(jiǎn)化為一步操作？事實(shí)上，我們沒(méi)有簡(jiǎn)化這個(gè)操作。一種用于教學(xué)
的算法，是實(shí)時(shí)地計(jì)算這個(gè)影響值：
/**////
/// The table-driven CRC implement algorithm part 1.
////**//*
While (augmented message is not exhausted)
Begin
Examine the top byte of the register
Calculate the control byte from the top byte of the register
Sum all the Polys at various offsets that are to be XORed into
the register in accordance with the control byte
Shift the register left by one byte, reading a new message byte
into the rightmost byte of the register
XOR the summed polys to the register
End
*/
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define POLY 0x04C11DB7L
int main()
{
/**//// the data
unsigned long data = 0x1011035b;
/**//// load the register with the data
unsigned long regi = 0;
/**//// allocate memory to contain the AUGMENTED data (added some zeros)
unsigned char p[8];
/**//// copy data
memset( p, 0, 8 );
memcpy( p, &data, 4 );
/**//// because data contains 4 bytes
for( int i = 0; i < 8; ++ i )
{
/**//// get the top byte of the register
unsigned char top_byte = (unsigned char)( ( regi >> 24 ) & 0xff );
/**//// sum all the polys at various offsets
unsigned long sum_poly = top_byte << 24;
for( int j = 0; j < 8; ++ j )
{
/**//// check the top bit
if( ( sum_poly >> 31 ) != 0 )
{
/**//// TODO : understand why '<<' first
sum_poly = ( sum_poly << 1 ) ^ POLY;
}
else
{
sum_poly <<= 1;
}
}
/**//// shift the register left by on byte, reading a new
regi = ( ( regi << 8 ) | p[i] );
/**//// xor the summed polys to the register
regi ^= sum_poly;
}
/**//// and now, register contains the remainder which is also called CRC value.
return 0;
}
其中：
/**//// sum all the polys at various offsets unsigned long sum_poly = top_byte << 24;
for( int j = 0; j < 8; ++ j )
{
/**//// check the top bit
if( ( sum_poly >> 31 ) != 0 )
{
/**//// TODO : understand why '<<' first
sum_poly = ( sum_poly << 1 ) ^ POLY;
}
else
{
sum_poly <<= 1;
}
}
就是用于計(jì)算這個(gè)影響值的。事實(shí)上，table-driven CRC算法中的那個(gè)表就是通過(guò)這段代碼生成的(排除其他一些細(xì)節(jié))。
你可能并不是很理解，這里我建議你忽略各種細(xì)節(jié)(更多的細(xì)節(jié)見(jiàn)參考資料)。你所需要知道的是，我們將8次逐bit的操
作合并到了一次byte操作中。而這個(gè)byte操作，就是8次bit操作的合操作(上面提到的影響值)。這個(gè)byte操作其實(shí)就是
一個(gè)數(shù)值，也就是table-driven CRC算法中那個(gè)表的一個(gè)元素。不同序列的bit操作其實(shí)對(duì)應(yīng)著不同的unsigned char
值，因此那個(gè)table有256個(gè)元素。
show me where the table is :
如上所說(shuō)，上面的算法很容易地就可以引進(jìn)一個(gè)表：
進(jìn)一步簡(jiǎn)化：
上述算法一個(gè)典型特征是會(huì)在我們的數(shù)據(jù)后面添加若干0。這樣做其他做了很多沒(méi)用的計(jì)算。一種簡(jiǎn)化做法就是將這些
沒(méi)用的計(jì)算合并到其他計(jì)算中。其實(shí)這都是一些位操作的技巧：
/**////
/// The table-driven CRC implement algorithm part 2.
////**//*
While (augmented message is not exhausted)
Begin
Examine the top byte of the register
Calculate the control byte from the top byte of the register
Sum all the Polys at various offsets that are to be XORed into
the register in accordance with the control byte
Shift the register left by one byte, reading a new message byte
into the rightmost byte of the register
XOR the summed polys to the register
End
*/
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define POLY 0x04C11DB7L
unsigned long get_sum_poly( unsigned char top_byte )
{
/**//// sum all the polys at various offsets
unsigned long sum_poly = top_byte << 24;
for( int j = 0; j < 8; ++ j )
{
/**//// check the top bit
if( ( sum_poly >> 31 ) != 0 )
{
/**//// TODO : understand why '<<' first
sum_poly = ( sum_poly << 1 ) ^ POLY;
}
else
{
sum_poly <<= 1;
}
}
return sum_poly;
}
void create_table( unsigned long *table )
{
for( int i = 0; i < 256; ++ i )
{
table[i] = get_sum_poly( (unsigned char) i );
}
}
int main()
{
/**//// the data
unsigned long data = 0x1011035b;
/**//// load the register with the data
unsigned long regi = 0;
/**//// allocate memory to contain the AUGMENTED data (added some zeros)
unsigned char p[8];
/**//// copy data
memset( p, 0, 8 );
memcpy( p, &data, 4 );
/**//// the table
unsigned long table[256];
/**//// create the table
create_table( table );
/**//// because data contains 4 bytes
for( int i = 0; i < 8; ++ i )
{
/**//// get the top byte of the register
unsigned char top_byte = (unsigned char)( ( regi >> 24 ) & 0xff );
/**//// shift the register left by on byte, reading a new
regi = ( ( regi << 8 ) | p[i] );
/**//// xor the summed polys to the register
regi ^= table[top_byte];
}
/**//// and now, register contains the remainder which is also called CRC value.
return 0;
}
討厭的附加0
以上算法有個(gè)很大的特征就是要為我們的數(shù)據(jù)附加很多0。附加0后其實(shí)也附加了很多無(wú)用的操作。我們要將這些
討厭的0去掉：
int main()
{
/**//// the data
unsigned long data = 0x1011035b;
/**//// load the register with the data
unsigned long regi = 0;
/**//// allocate memory to contain the data
unsigned char p[4];
/**//// copy data
memcpy( p, &data, 4 );
/**//// the table
unsigned long table[256];
/**//// create the table
create_table( table );
/**//// because data contains 4 bytes
for( int i = 0; i < 4; ++ i )
{
regi = ( regi << 8 ) ^ table[ ( regi >> 24 ) ^ p[i] ];
}
/**//// and now, register contains the remainder which is also called CRC value.
return 0;
}
關(guān)鍵的一句regi = ( regi << 8 ) ^ table[ ( regi >> 24 ) ^ p[i] ]; 簡(jiǎn)化了很多沒(méi)用的操作。
In practice :
似乎一切被我說(shuō)的很簡(jiǎn)單。我想只是因?yàn)槲覜](méi)說(shuō)清楚。我盡量讓你注意到事情的重點(diǎn)。我們進(jìn)行到這里，似乎
我們立馬就可以寫(xiě)出自己的CRC32算法并用于實(shí)踐。但是你很快就會(huì)發(fā)現(xiàn)，事情并不如你想像的那么簡(jiǎn)單。
在實(shí)際處理時(shí)，很多數(shù)據(jù)的bit會(huì)進(jìn)行一種顛倒操作，例如1010會(huì)被顛倒為0101。出現(xiàn)這樣的情況是因?yàn)槟承┯布?br>在實(shí)現(xiàn)CRC算法時(shí)，采用了這種(丑陋的)習(xí)慣。有些軟件實(shí)現(xiàn)CRC算法時(shí)，也延用了這個(gè)習(xí)慣。
另外，關(guān)于register的初始值問(wèn)題，有些CRC算法會(huì)初始化為0xffffffff。以下給出一個(gè)會(huì)進(jìn)行bit顛倒的算法，
該算法可以直接輸出table-driven中的表：
/**////
/// The table-driven CRC implement algorithm part 4.
///
/// Donot need augment W/8 zero bytes.
///#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define POLY 0x04C11DB7L
#define BITMASK(X) (1L << (X))
unsigned long refelect( unsigned long v, int b )
{
int i;
unsigned long t = v;
for( i = 0; i < b; ++ i )
{
if( t & 1L )
v |= BITMASK( (b-1)-i );
else
v &= ~BITMASK( (b-1)-i );
t >>= 1;
}
return v;
}
/**//// i'll try to write a correct algorithmunsigned long get_sum_poly( unsigned char byte )
{
byte = (unsigned long) refelect( byte, 8 );
unsigned long sum_poly = byte << 24;
for( int i = 0; i < 8; ++ i )
{
/**//// check the top bit
if( ( sum_poly >> 31 ) != 0 )
{
/**//// TODO : understand why '<<' first
sum_poly = ( sum_poly << 1 ) ^ POLY;
}
else
{
sum_poly <<= 1;
}
}
sum_poly = refelect( sum_poly, 32 );
return sum_poly;
}
void create_table( unsigned long *table )
{
for( int i = 0; i <= 255; ++ i )
{
table[i] = get_sum_poly( (unsigned char) i );
}
}
void output_table( const unsigned long *table )
{
FILE *fp = fopen( "table.txt", "w" );
for( int y = 0; y < 64; ++ y )
{
fprintf( fp, "0x%08lXL,\t0x%08lXL,\t0x%08lXL,\t0x%08lXL, \n",
table[ y * 4 + 0],
table[ y * 4 + 1],
table[ y * 4 + 2],
table[ y * 4 + 3] );
}
fclose( fp );
}
int main()
{
/**//// the table
unsigned long table[256];
/**//// the data
unsigned long data = 0x1011035b;
/**//// load the register with the data
unsigned long regi = 0;
/**//// allocate memory to contain the data
unsigned char p[4];
/**//// copy data
memcpy( p, &data, 4 );
/**//// create the table
create_table( table );
/**//// output the table
output_table( table );
/**//// because data contains 4 bytes
for( int i = 0; i < 4; ++ i )
{
regi = ( regi << 8 ) ^ table[ ( regi >> 24 ) ^ p[i] ];
}
/**//// and now, register contains the remainder which is also called CRC value.
return 0;
}
Please FORGIVE me
我想我并沒(méi)有將整個(gè)過(guò)程徹底地講清楚。但是我希望你能明白大致的原理。關(guān)于table-driven中那個(gè)神奇的表的來(lái)歷，
關(guān)于CRC32算法的推導(dǎo)過(guò)程等等之類。
本文代碼下載： http://www.shnenglu.com/Files/kevinlynx/CRC%20Implement.rar
參考資料：
http://www34.brinkster.com/dizzyk/math-crc.asp
http://www.greenend.org.uk/rjk/2004/crc.html
http://www.ross.net/crc/crcpaper.html