CRC算法原理及C語言實現(xiàn)

1、（一）crc算法原理及c語言實現(xiàn) 1.crc原理介紹 crc的英文全稱為cyclic redundancy check（code），中文名稱為循環(huán)冗余校驗（碼）。它是一類重要的線性分組碼，編碼和解碼方法簡單，檢錯和糾錯能力強，在通信領域廣泛地用于實現(xiàn)差錯控制。 crc計算與普通的除法計算有所不同。普通的除法計算是借位相減的，而crc計算則是異或運算。任何一個除法運算都需要選取一個除數(shù)，在crc運算中我們稱之為poly，而寬度w就是poly最高位的位置。比如poly 1001的w是3，而不是4。注意最高位總是1，當你選定一個寬度，那么你只需要選擇低w各位的值。假如我們想計算一個位串的crc碼，并

2、要保證每一位都要被處理，因此我們需要在目標位串后面加上w個0。下面舉例說明crc算法的過程。 在此例中，我們假設位串為110101101。poly(除數(shù)) = 10011（寬度w = 4）bitstring + w個0 = 110101101 0000 10011/ 1101011010000/110000101 （我們不關心此運算的商） 10011| -| 10011| 10011| -| 00001| 00000| -| 00010| 00000| -| 00101| 00000| -| 01010| 00000| -| 10100| 10011| -| 01110| 00000| -|

3、11100 10011 - 1111 - 余數(shù) - crc！計算過程總結如下：1. 只有當位串的最高位為1，我們才將它與poly做xor運算，否則我們只是將位串左移一位。2. 異或運算的結果實質上是被操作位串與poly的低w位進行運算的結果，因為最高位總為0。2.crc原理及其逆向破解方法：2.1介紹：這篇短文包含crc原理介紹和其逆向分析方法,很多程序員和破解者不是很清楚crc的工作原理,而且?guī)缀鯖]人知道如何逆向分析它的方法，事實上它是非常有用的。首先，這篇教程教你一般如何計算crc，你可以將它用在數(shù)據(jù)代碼保護中。第二，主要是介紹如何逆向分析crc-32，你可以以此來分析程序中的crc保護（

4、象反病毒編碼）。當然有很多有效的工具用來對付crc，但我懷疑它是否會說明原理。我要告訴你，這篇短文里中應用了很多數(shù)學知識，這不會影響一些人，而且會被一般的程序員與逆向分析者很好理解，為什么？那么如果你不知道數(shù)學是如何被應用在crc中，我建議你可以停止繼續(xù)學習了。所以我假定你們（讀者）都是具備二進制算術知識的。2.2第一部分：crc 介紹,crc是什么和計算crc的方法2.2.1循環(huán)冗余碼 crc我們都知道crc，甚至你沒有印象，但當你想到那些來自諸如rar，zip等壓縮軟件發(fā)給你由于錯誤連接和其他一些意外原因導致的文件錯誤的惱人的消息時，你就會知道。crc是塊數(shù)據(jù)的計算值，比如對每一個文件進行

5、壓縮，在一個解壓縮過程中，程序會從新計算解壓文件的crc值，并且將之與從文件中讀取的crc值進行比對，如果值相同，那么正確。在crc-32中，會有1/232的可能性發(fā)生對確認數(shù)據(jù)更改的校驗錯誤。 很多人認為crc就是循環(huán)冗余校驗。假如crc真的就是循環(huán)冗余校驗，那么很多人都錯用了這個術語。你不能說這個程序的crc是12345678。人們也常說某一個程序有crc校驗，而不說是 循環(huán)冗余校驗 校驗。結論：crc 代表循環(huán)冗余碼，而不是循環(huán)冗余校驗。計算是如何完成的呢？好，主要的想法就是將一個文件看成一個被一些數(shù)字分割的很長的位字串，這里會有一個余數(shù)crc！你總會有一個余數(shù)(可以是0)，它至多比除數(shù)

6、小1。(9/3=3 余數(shù)=0 ；(9+2)/3=3 余數(shù)=2)(或者它本身就包含一個除數(shù)在其中)。在這里crc計算方法與除法有一點點區(qū)別，除法就是將被減數(shù)重復的減去除數(shù)x次，然后留下余數(shù)。如果你希望得到原值，那么你就要把除數(shù)乘上x次，然后加上余數(shù)。crc計算使用特殊的減法與加法完成的，也就是一種新的算法。計算中每一位計算的進位值被忽略了。 看如下兩個例子，（1）是普通減法，（2）和（3）是特殊的。 （1） （2） （3）1101101010100+0=00-0=01010 1111 +1111 0+1=1 *0-1=11+0=11-0=1001101010101*1+1=01-1=0在（1）中

7、，右數(shù)第二列可以看成是0 -1= -1，因此要從高位借1，就變成(10+0)-1=1， (這就象普通的by-paper十進制減法)。特例（2,3）中，1+1會有正常的結果10，“1”是計算后的進位，這個值被忽略了。特殊情況0-1應該有正常結果“-1”就要退到下一位。這個值也被忽略了，假如你對編程有一定了解，這就象xor 操作或者更好。 現(xiàn)在來看一個除法的例子:在普通算法中:1001/11110001101 13 9/12013 1001 - 09 -| - -| 1100 30 | 1001 - 27 - - - 0110 3 - 余數(shù) 0000 - - 1100 1001 - - 011 -

8、 3, 余數(shù)在crc算法中:1001/11110001110 9/12014 余數(shù)為 6 1001 - - 1100 1001 - - 1010 1001 - - 0110 0000 - - 110 - 余數(shù)(例 3)這個除法的商并不重要，也沒必要去記住，因為他們僅僅是一組無關緊要的位串。真正重要的是余數(shù)！它就是這個值，可以說比原文件還重要的值，他就是基本的crc。過度到真正的crc碼計算。 進行一個crc計算我們需要選則一個除數(shù)，從現(xiàn)在起我們稱之為poly。寬度w就是最高位的位置，所以這個poly 1001的w 是3，而不是4。注意最高位總是1，當你選定一個寬度，那么你只需要選擇低w各位的值

9、。 假如我們想計算一個位串的crc碼，我們想確定每一個位都被處理過，因此，我們要在目標位串后面加上w個0位。在此例中，我們假設位串為110101101。請仔細分析下面一個例子：poly = 10011，寬度 w=4位串 bitstring bitstring + w zeros = 110101101 + 000010011/1101011010000110000101 (我們不關心此運算的商) 10011| - -| 10011| 10011| - -| 00001| 00000| - -| 00010| 00000| - -| 00101| 00000| - -| 01010| 00000

10、| - -| 10100| 10011| - -| 01110| 00000| - -| 11100 10011 - - 1111 - 余數(shù) - the crc!(例 4)重要兩點聲明如下:1、只有當bitstring的最高位為1，我們才將它與poly做xor運算，否則我們只是將bitstring左移一位。2、xor運算的結果就是被操作位串bitstring與低w位進行xor運算，因為最高位總為0。算法設計: 你們都應知道基于位運算的算法是非常慢的而且效率低下，但如果將計算放在每一字節(jié)上進行，那么效率將大大提高。不過我們只能接受poly的寬度w是8的倍數(shù)(一個字節(jié)；)?？梢孕蜗蟮目闯蛇@樣一個寬

11、度w為32的poly(w=32)： 3 2 1 0 byte +-+-+-+-+pop! -| | | | |- bitstring with w zero bits added, in this case 32 +-+-+-+-+ 1 this is the poly, 4*8 bits(figure 1) 這是一個你用來存放暫時crc結果的寄存器，現(xiàn)在我稱它為crc寄存器或者寄存器。你從右至左移動位串，當從左邊移出的位是1，則整個寄存器被與poly的低w位進行xor運算。(此例中為32)。事實上，我們精確的完成了上面除法所做的事情。移動前寄存器值為:10110100，當從右邊移入4位時，左

12、邊的高4位將被移出，此例中1011將被移出，而1101被移入。情況如下:當前8位crc寄存器 : 01001101剛剛被移出的高4位 : 1011我們用此poly : 1 0101 1100，0x5c 寬度 w=8現(xiàn)在我們用如前介紹的方法來計算寄存器的新值。頂部 寄存器- -101101001101 高四位和當前寄存器值101011100 + (*1) poly 放在頂部最高位進行xor運算 (因為那里是1)-000110101101 運算結果現(xiàn)在我們仍有一位1在高4位:0001 10101101 上一步結果 1 01011100+ (*2) poly 放在頂部的最低位進行xor運算 (因為那

13、里是1)-0000 11110001 第二步運算結果現(xiàn)在頂部所有位均為0，所以我們不需要在與poly進行xor運算你可以得到相同的結果如果你先將(*1)與(*2)做xor然后將結果與記存器值做xor.這就是標準xor運算的特性:(a xor b) xor c = a xor (b xor c) 由此,推出如下的運算順序也是正確的.101011100 poly (*1) 放在頂部最高位101011100+ polys (*2) 放在頂部最低位-101110111100 (*3) xor運算結果the result (*3) 將(*3)與寄存器的值做xor運算1011 101111001011 0

14、1001101+ 如右:-0000 11110001你看到了嗎？得到一樣的結果！現(xiàn)在(*3)變的重要了，因為頂部為1010則(3)的值總是等于10111100(當然是在一定的條件之下),這意味著你可以預先計算出任意頂部位結合的xor值。注意，頂部結果總是0，這就是組合xor操作導致的結果。(翻譯不準確,保留原文) 現(xiàn)在我們回到figure 1，對每一個頂部字節(jié)的值都做移出操作，我們可以預先計算出一個值。此例中，它將是一個包含256個double word(32 bit)雙字的表。(附錄中crc-32的表).(翻譯不準確,保留原文) 用偽語言表示我們的算法如下: while (byte stri

15、ng is not exhausted) begin top = top_byte of register ; / (register value8)register = register shifted 8 bits left orred with a new byte from string ;/ (register value8) register = register xorred by value from precomputedtable at position top ; end / register crc_tabletopnew byte from string;direct

16、 table算法: 上面提到的算法可以被優(yōu)化，字節(jié)串中的字節(jié)在被用到之前沒有必要經(jīng)過整個寄存器。用這個新的算法，我們可以直接用一個字節(jié)去xor一個字節(jié)串通過將此字節(jié)移出記存器。結果指向預先計算的表中的一個值，這個值是用來被記存器的值做xor運算的。 我不十分確切的知道為什么這會得到同樣的結果(這需要了解xor運算的特性)，但是這又極為便利，因為你無須在你的字節(jié)串后填充0字節(jié)/位。(如果你知道原理，請告訴我。) 讓我們來實現(xiàn)這個算法: +- byte string (or file) 字節(jié)串,(或是文件) | v 3 2 1 0 byte 字節(jié) | +-+-+-+-+xor-: : : : :

17、+-+-+-+-+ | | | | | +-+-+-+-+(figure 2)reflected direct table 算法: 由于這里有這樣一個與之相對應的“反射”算法，事情顯得復雜了。一個反射的值/寄存器就是將它的每一位以此串的中心位為標準對調形成的。例如:0111011001就是1001101110的反射串。 他們提出“反射”是因為uart(一種操作io的芯片)發(fā)送每一個字節(jié)時是先發(fā)最沒用的0位,最后再發(fā)最有意義的第7位，這與正常的位置是相逆的。 除了信息串不做反射以外，在進行下一步操作前，要將其余的數(shù)據(jù)都做反射處理。所以在計算值表時，位向右移，且poly也是作過反射處理的。當然,在

18、計算crc時，寄存器也要向右移，而且值表也必須是反射過的. byte string (or file) -+ | 1. 表中每一個入口都是反射的. byte 3 2 1 0 v 2. 初始化記存器也是反射的. +-+-+-+-+ | 3. 但是byte string中的數(shù)據(jù)不是反射的, | | | | |-xor 因為其他的都做過反射處理了. +-+-+-+-+ | | | xor v | +-+-|-+-+ | | | | | | | 值表 +-+-+-+-+ | : : : : : -+ +-+-+-+-+ | | | | | +-+-+-+-+(figure 3)我們的算法如下:1. 將

19、記存器向右移動一個字節(jié)。2. 將剛移出的那個字節(jié)與byte string中的新字節(jié)做xor運算,得出一個指向值表table0.255的索引。3. 將索引所指的表值與記存器做xor運算.4. 如數(shù)據(jù)沒有全部處理完,則跳到步驟1.下面是這個算法的簡單的可執(zhí)行匯編源碼:完整的crc-32標準所包含的內容:name : crc-32width : 32poly : 04c11db7initial value : ffffffffreflected : truexor out with : ffffffff作為對你好奇心的獎勵, 這里是crc-16標準: :)name : crc-16width : 1

20、6poly : 8005initial value : 0000reflected : truexor out with : 0000xor out with 是為了最終得到crc而用來與寄存器最后結果做xor運算的值。假如你想了解一些關于reversed逆向crc poly的話,請看我的參考文章. 我是在16位dos模式下用的32位編碼，因此你會在這個程序中看到很多32位與16位混合的編碼.當然這是很容易轉換成純32位編碼的。注意這個程序是經(jīng)過完整測試并且能夠正常運行的.下面的java 和 c 代碼都是由這個匯編代碼而來的. 底下的這段程序就是用來計算crc-32 table的: xor e

21、bx, ebx ;ebx=0, 將被用做一個指針.inittableloop: xor eax, eax ;eax=0 為計算新的entry. mov al, bl ;al-bl ;生成入口. xor cx, cxentryloop: test eax, 1 jz no_topbit shr eax, 1 xor eax, poly jmp entrygoonno_topbit: shr eax, 1entrygoon: inc cx test cx, 8 jz entryloop mov dword ptrebx*4 + crctable, eax inc bx test bx, 256 j

22、z inittableloop注釋: - crctable 是一個包含256個dword的數(shù)組. - 由于使用反射算法，eax被向右移。 - 因此最低的8位被處理了.用java和c寫的代碼如下(int is 32 bit):for (int bx=0; bx256; bx+) int eax=0; eax=eax&0xffffff00+bx&0xff; / 就是 mov al,bl 指令 for (int cx=0; cx=1; eax=poly; else eax=1; crctablebx=eax;下面的匯編代碼是用來計算crc-32的:computeloop: xor ebx, ebx

23、xor al, si mov bl, al shr eax, 8 xor eax, dword ptr4*ebx+crctable inc si loop computeloop xor eax, 0ffffffffh注釋: - ds:si 指向將要被處理的byte string信息流. - cx 信息流的長度. - eax 是當前的crc. - crctable是用來計算crc的值表. - 此例中記存器的初始值為: ffffffff. - 要將中間值與ffffffffh做xor才能得到crc下面是java和c寫的代碼:for (int cx=0; cx=8; eax=crctableebx;

24、eax=0xffffffff; 現(xiàn)在我們已經(jīng)完成了本文的第一部分:crc原理部分，所以如果你希望能夠對crc做更深的研究，那么我建議你去讀在本文最后給出連接上的資料，我讀了，好了，終于到了本文最有意思的部分：crc的逆向分析!-2.3第二部分：crc的逆向分析 我遇到了很多障礙，當我思考如何破解crc時，我試圖使用一些特殊順序的字節(jié)使crc無效。但我沒有做到.后來我意識到這種方法是行不通的，因為crc內建了一些處理過程，無論你改變任何位它都不會出問題。真正的crc就是在不斷變化的，總是在變化的找一些crc程序，你可以自己嘗試一下。 現(xiàn)在我知道我只能“糾正”在crc后面的那些我想改變的字節(jié)。所以

25、我要構造一個字節(jié)序列，它可以將crc轉化成任何我想要的樣子! 具體實現(xiàn)這個想法一個字節(jié)串? 01234567890123456789012345678901234567890123456789012you want to change from this byte to this one.就是位置9-26。同時我們需要額外的4個字節(jié)用來在最后恢復原始字節(jié)串。 當你計算crc-32時，從0-8都沒有問題，直到第9位，修補過的字節(jié)串會使crc發(fā)生根本的改變。即使當走過了第26位，以后的字節(jié)都沒有改變，你也不可能在得到原始的crc了，不可能了!你讀過后面的段落時就會明白為什么。簡而言之，當你修改一個

26、字節(jié)串時，要保證crc不變。1. 計算并保存從19位的crc.2. 繼續(xù)計算直到第27位還有額外的4字節(jié)并保存結果.3. 用1的值來計算新的字節(jié)串和額外4字節(jié)的crc(對應patch后的新的crc值),并將之保存.4. 現(xiàn)在我們得到了一個新的crc,但是我們希望將它還原成原先的crc,所以我們用逆向算法 來計算那額外的4字節(jié).13就是實際的情況,下面你將學到最關鍵的部分4.反轉crc-16 我想,先來介紹計算逆crc-16對于你來說會簡單些.好的,我們現(xiàn)在處在一個恰當?shù)奈恢?在以修改代碼后面,就是你想將crc還原的地方.我們知道原始的crc(是在patch代碼之前計算出來的)還有這個當前的記存

27、器值.現(xiàn)在我們的目的就是計算可以改變當前記存器值到原始記存器值的兩個字節(jié). 首先,我們用正常的方法計算這兩個未知字節(jié)的crc.我們設他們?yōu)閤,y.設記存器為a1,a0,只有0不能用來作為變量(00).:)在來看一下我們的crc算法,figure3,更好的理解下面我要做的.好,我們開始:用這兩字節(jié)串x y 字節(jié)是從左邊開始被處理的.記存器現(xiàn)在是a1 a0.用+來表示xor運算(和第一部分中用的一樣)處理第一個字節(jié), x:a0+x 這是頂部字節(jié)的計算結果 (1)b1 b0 這是(1)在表中索引對象.00 a1 向右移動記存器.00+b1 a1+b0 上面兩行對應位做xor運算.現(xiàn)在記存器為: (b

28、1) (a1+b0)處理第二個字, y:(a1+b0)+y 此輪頂部字節(jié)的計算結果(2)c1 c0 這是(2)在表中的索引對象.00 b1 向右移動記存器.00+c1 b1+c0 上面兩行對應位做xor運算.最后記存器就是: (c1) (b1+c0)我用一點不同的方法來表示:a0 + x =(1) 在表中指向b1 b0.a1 + b0 + y =(2) 在表中指向c1 c0. b1 + c0=d0 記存器中新的低位字節(jié). c1=d1 記存器中新的高位字節(jié). (1) (2)wow! 請大家暫時記住上面的信息:)別著急, 下面給出一個有具體值的例子. 如果你想要的記存器的值是d1 d0(是原始的c

29、rc),而且你知道在變換之前的記存器的值(a1 a0).那么你將要送如什么樣的2個字節(jié)進記存器來做crc計算呢? 好了,現(xiàn)在我們的工作應該從幕后走到臺前來了.d0一定是bi+c0,并且d1一定是c1.但是這到底是怎么回事,我聽到你這樣問了,你能知道b1和c0的值嗎?你還記得哪個值表嗎?你只需要在表中查找c0 c1這個字的值就可以了因為你知道c1.所以你需要編寫一個查找程序.假如你找到了這個值,一定要記住這個值的索引,因為這就是找出未知的兩個頂部字節(jié),舉例來說:(1)和(2)! 所以,現(xiàn)在你找到了c1 c0,那么如何來得到b1 b0呢?如果b1+c0=d0那么b1=d0+c0!如前所述,現(xiàn)在你用

30、哪個查找程序在表中查b1 b0的值.現(xiàn)在我們得到了所有計算x和y所需要的值.cool huh? a1+b0+y=(2) so y=a1+b0+(2)a0+x=(1) so x=a0+(1)實例.讓我們來看看這個具體值的例子:-register before: (a1=)de (a0=)ad-wanted register: (d1=)12 (d0=)34在附錄的crc-16的表中查找以12開頭值的入口.這里入口38h的值為12c0.試這找一找是否還有以12開頭的值的入口.你不可能在找到的,因為我們計算每一中頂部字節(jié)組合而得的值的入口,一共是256個值,記住!現(xiàn)在我們知道(2)=38,c1=12

31、,c0=c0,所以b1=c0+34=f4,現(xiàn)在查找以f4開頭的b1的入口.這里入口4fh的值是f441.我們還知道 (1)=4f,b1=f4,b0=41,現(xiàn)在所有我們需要的都已經(jīng)清楚了,接下來我們計算x,y.y=a1+b0+(2)=de+41+38=a7x=a0+(1) =ad+4f =e2結論:將crc 記存器的值從 dead 變?yōu)?1234 我們需要這兩個字節(jié) e2 a7 (以此順序). 你看,破解crc校驗你需要反向計算,還有要記住的就是計算過程中的值.當你在用匯編編寫查找表程序時,要注意intel在小模式中是反向存儲值的.現(xiàn)在你可能已經(jīng)明白如何去破解這個crc-16了.下面介紹如何在c

32、rc-32中實現(xiàn).破解 crc-32現(xiàn)在我們來看crc-32,和crc-16是一樣容易的(可能一樣的不容易你認為).這里你操作的對象是4個字節(jié)的而不是2字節(jié)的.繼續(xù)向下看,將它與上面crc-16版本做對比.設4字節(jié)串 x y z w , 從左邊開始處理.設記存器為 a3 a2 a1 a0注意a3是msb,而a0是lsb處理第一個字節(jié), x:a0+x 這是頂部字節(jié)的計算結果(1).b3 b2 b1 b0 這是(1)在表中索引對象序列.00 a3 a2 a1 右移記存器.00+b3 a3+b2 a2+b1 a1+b0 上面兩行對應位做xor運算.現(xiàn)在記存器是: (b3) (a3+b2) (a2+b

33、1) (a1+b0)processing second byte, y:(a1+b0)+y 這是頂部字節(jié)的計算結果(2).c3 c2 c1 c0 這是(2)在表中索引對象序列.00 b3 a3+b2 a2+b1 右移記存器.00+c3 b3+c2 a3+b2+c1 a2+b1+c0 上面兩行對應位做xor運算.現(xiàn)在記存器是: (c3) (b3+c2) (a3+b2+c1) (a2+b1+c0)processing third byte, z:(a2+b1+c0)+z 這是頂部字節(jié)的計算結果(3).d3 d2 d1 d0 這是(3)在表中索引對象序列.00 c3 b3+c2 a3+b2+c1 右

34、移記存器.00+d3 c3+d2 b3+c2+d1 a3+b2+c1+d0 上面兩行對應位做xor運算.現(xiàn)在記存器是: (d3) (c3+d2) (b3+c2+d1) (a3+b2+c1+d0)processing fourth byte, w:(a3+b2+c1+d0)+w 這是頂部字節(jié)的計算結果(4).e3 e2 e1 e0 這是(4)在表中索引對象序列.00 d3 c3+d2 b3+c2+d1 右移記存器.00+e3 d3+e2 c3+d2+e1 b3+c2+d1+e0 上面兩行對應位做xor運算.最后,記存器為: (e3) (d3+e2) (c3+d2+e1) (b3+c2+d1+e0

35、)我用一個不同一點的方法來表示:a0 + x =(1) 在表中指向 b3 b2 b1 b0 a1 + b0 + y =(2) 在表中指向 c3 c2 c1 c0 a2 + b1 + c0 + z =(3) 在表中指向 d3 d2 d1 d0 a3 + b2 + c1 + d0 + w =(4) 在表中指向 e4 e3 e2 e1 b3 + c2 + d1 + e0 =f0 c3 + d2 + e1 =f1 d3 + e2 =f2 e3 =f3 (1) (2) (3) (4)(figure 4)這里是用的與crc-16同樣的方法來實現(xiàn)的,我會給出一個具體值的例子.查找用附錄中crc-32的值表.

36、take for crc register before, a3 a2 a1 a0 - ab cd ef 66take for crc register after, f3 f2 f1 f0 - 56 33 14 78 (wanted value)我們開始:first byte of entries entry valuee3=f3 =56 - 35h=(4) 56b3c423 for e3 e2 e1 e0d3=f2+e2 =33+b3 =e6 - 4fh=(3) e6635c01 for d3 d2 d1 d0c3=f1+e1+d2 =14+c4+63 =b3 - f8h=(2) b366

37、7a2e for c3 c2 c1 c0b3=f0+e0+d1+c2=78+23+5c+66=61 - deh=(1) 616bffd3 for b3 b2 b1 b0now we have all needed values, thenx=(1)+ a0= de+66=b8y=(2)+ b0+a1= f8+d3+ef=c4z=(3)+ c0+b1+a2= 4f+2e+ff+cd=53w=(4)+d0+c1+b2+a3=35+01+7a+6b+ab=8e(final computation)結論:要將 crc-32 的記存器的值從 abcdef66 改變到 56331478 我們需要這樣一個字

38、節(jié)序列: b8 c4 53 8ecrc-32的破解算法 假如你考慮手動計算這個可以還原crc記存器的字節(jié)序列,那么這將很難變成一個簡潔的算法. 看看下面這個最后計算的附加版本: positionx =(1) + a0 0y =(2) + b0 + a1 1z =(3) + c0 + b1 + a2 2w =(4) + d0 + c1 + b2 + a3 3f0= e0 + d1 + c2 + b3 4f1= e1 + d2 + c3 5f2= e2 + d3 6f3= e3 7(figure 5) 它就等同于figure 4,只不過是一些值/字節(jié)被交換了.這種方法可以幫助我們構造一個簡潔的算法

39、.這里我們用一個8字節(jié)的緩沖區(qū),0-3位我們放置a0到a3,4-7位我們放置f0到f3.象以前一樣,我們用這個已知值e3(由figure 5中得知)在表中查出(e3 e2 e1 e0),并且象圖5(figure 5)中所示,將它們放到第4位(position 4),我們馬上得到了d3的值.因為f2=e2+d3,所以f2+e2=d3.又因為(4)已知(入口值),我們照樣把它也放到位置3.然后在用d3查表得到(d3 d2 d1 d0),同上也將他們放到圖中所述位置.同樣,由于有f1+e1+d2=c3在位置5上. 我們繼續(xù)做直到將b3 b2 b1 b0放到位置1,對了，就是它! et voila!此

40、時,緩沖區(qū)的第3-第0字節(jié)中已經(jīng)包含全部元素,用來計算xw! 算法總結如下:1.對于這個8字節(jié)的緩沖區(qū),03字節(jié)放入a0.a3(crc記存器起始值),47字節(jié)放入f0.f3 (目標記存器的值).2.取出位置7的已知值,查表得到相應值.3.將查出值放如圖5相應位置,其實就是做xor運算.(為了直觀,可以擬定此圖)4.將入口字節(jié)放入圖中.也是做xor運算.5.繼續(xù)做2,3兩步3次,同時每次降低1個位置 position 5 to 4, 4 to 3 and so on.算法的實現(xiàn): 現(xiàn)在是時候給出代碼了.下面就是用匯編寫成的可執(zhí)行的crc-32算法(用其他語言也一樣簡單,對于其他的crc-32標準

41、也一樣).注意在匯編中(計算機里)雙字在讀寫操作中順序都是反著的.就是逆向順序.crcbefore dd (?)wantedcrc dd (?)buffer db 8 dup (?) mov eax, dword ptrcrcbefore ;/* mov dword ptrbuffer, eax mov eax, dword ptrwantedcrc ; step 1 mov dword ptrbuffer+4, eax ;*/ mov di, 4computereverseloop: mov al, byte ptrbuffer+di+3 ;/* call gettableentry ; s

42、tep 2 */ xor dword ptrbuffer+di, eax ; step 3 xor byte ptrbuffer+di-1, bl ; step 4 dec di ;/* jnz computereverseloop ; step 5 */notes:-registers eax, di bx are usedimplementation of gettableentrycrctable dd 256 dup (?) ;should be defined globally somewhere & initialized of course mov bx, offset crctable-1gettableentryloop: add bx, 4 ;points to (crctable-1)+k*4 (k:1.256) cmp bx, al ;must always find the valu