彭茜珍

(湖北科技學院 學報編輯部,湖北 咸寧 437100)

在網(wǎng)絡(luò)和通信程序設(shè)計中，經(jīng)常會涉及數(shù)據(jù)校驗碼的計算，CRC32校驗碼是常見的使用較多一種數(shù)據(jù)校驗碼，由于計算CRC碼會占用較多的CPU時間，導致程序運行出現(xiàn)性能瓶頸，其主要的原因是校驗碼的計算量較大導致的。本文提出了一種基于Intel CRC指令的校驗碼計算思路，借助于該思路可以加快計算速度，提高生成校驗碼的效率。

一、引言

CRC全稱為Cyclic Redundancy Check，又叫循環(huán)冗余校驗。CRC是目前使用廣泛一種校驗算法，它是由W. Wesley Peterson在1961年發(fā)表的論文中提出。CRC檢驗原理實際上就是在一個N位二進制數(shù)據(jù)序列之后附加一個R位二進制檢驗碼(序列)，從而構(gòu)成一個總長為K=N+R位的二進制序列；附加在數(shù)據(jù)序列之后的這個檢驗碼與數(shù)據(jù)序列的內(nèi)容之間存在著某種特定的關(guān)系。如果因干擾等原因使數(shù)據(jù)序列中的某一位或某些位發(fā)生錯誤，這種特定關(guān)系就會被破壞。因此，通過檢查這一關(guān)系，就可以實現(xiàn)對數(shù)據(jù)正確性的檢驗。

任意一個由二進制位串組成的代碼都可以和一個系數(shù)僅為0和1取值的多項式一一對應(yīng)。例如：代碼1010111對應(yīng)的多項式為x6+x4+x2+x+1，而多項式為x5+x3+x2+x+1對應(yīng)的代碼101111。

幾個基本概念：[1]

(1)多項式模2運行：實際上是按位異或(Exclusive OR)運算，即相同為0，相異為1，也就是不考慮進位、借位的二進制加減運算。

(2)生成多項式(generator polynomial)：當進行CRC檢驗時，發(fā)送方與接收方需要事先約定一個除數(shù)，即生成多項式，一般記作G(x)。生成多項式的最高位與最低位必須是1。表1常用的CRC32碼的生成多項式：

表1 常用的CRC32碼的生成多項式

CRC檢驗碼的計算：

設(shè)信息字段為N位，校驗字段為R位，則碼字長度為K(K=N+R)。假設(shè)雙方事先約定了一個R次多項式G(x)，將XRB(x) 模2除以G(x)，得到商為Q(x)的多項式,余數(shù)為r(x)的多項式，即CRC碼：

XRB(x) =Q(x)G(x) +r(x)

其中: B(x)為N-1次信息多項式，r(x)為R-1次校驗多項式。這里r(x)對應(yīng)的代碼即為冗余碼，加在原信息字段后即形成CRC碼。

r(x)的計算方法為：在N位信息字段的后面添加R個0，再除以G(x)對應(yīng)的代碼序列，得到的余數(shù)即為r(x)對應(yīng)的代碼(應(yīng)為R位；若不足，而在高位補0)。

二、CRC32校驗碼算法研究

CRC32碼一位計算公式的推導：

對于一個二進制序列數(shù)可以表示為式(1)：

B(X)=Bn·Xn+Bn-1·Xn-1+…+B1·X+B0

(1)

求此二進制序列的CRC-32碼時，先乘以X32后(即左移32位)，再除以其生成多項式G(X)，所得余數(shù)即是所要求的CRC-32碼。如式(2)所示：

(2)

可以設(shè)：

(3)

其中Qn(X)為整式，Rn(X)為32位二進制余式。將式(3)代入式(2)得：

(4)

再設(shè)：

(5)

其中Qn-1(X)為整式，Rn-1(X)為32位二進制余式。

根據(jù)CRC-32的定義，由式(5)可以得到結(jié)論：

定理：計算某一位的CRC-32碼等于上一位CRC-32碼乘以2(即左移一位)后除以多項式G(X)，所得的余數(shù)再加上本位左移32位后除以多項式G(X)所得的余數(shù)。

推論：對于較長的二進制序列，可以通過每次左移4位、8位、16位、32位及64位來計算其CRC-32碼。

本推論是理解CRC32指令的關(guān)鍵之所在。

三、CRC32指令的研究

Intel CRC指令是在SSE4.2指令集中加入的[2，3]。共包括5種匯編格式：

CRC32 r32, r/m8

CRC32 r32, r/m16

CRC32 r32, r/m32

CRC32 r64, r/m8

CRC32 r64, r/m64

根據(jù)前述推論，CRC32 r32, r/m8可以理解為將目標左移8位(即上一次計算出的CRC-32碼)再與源左移32位后相加即(異或運算)后模2除以G(X)所得的余數(shù)。

CRC32 r32, r/m16可以理解為將目標左移16位(即上一次計算出的CRC-32碼)再與源左移32位后相加即(異或運算)后模2除以G(X)所得的余數(shù)。

CRC32 r32, r/m32可以理解為將目標左移32位(即上一次計算得出的CRC-32碼)再與源左移32位后相加即(異或運算)后模2除以G(X)所得的余數(shù)。

CRC32 r64, r/m64可以理解為將目標左移64位(即上一次計算得出的CRC-32碼)再與源左移32位后相加即(異或運算)后模2除以G(X)所得的余數(shù)。

這些指令表明以目標操作數(shù)中的初始值開始，對源操作數(shù)累加一個CRC32，采用的多項式是0x11EDC6F41值(該值由RFC3309 - Stream Control Transmission Protocol (SCTP)定義)，并將結(jié)果存儲在目標操作數(shù)中。源操作數(shù)可以是一個寄存器或存儲單元；目的操作數(shù)必須是r32或r64寄存器。如果目標是一個r64寄存器，那么32位的結(jié)果存儲在這個r64寄存器的最低有效雙字中，00000000H存儲在這個r64寄存器的最高有效的雙字中。

目標操作數(shù)提供的初始值是一個雙字整數(shù)，它存儲在r32寄存器中，或存儲在r64寄存器的最低雙字中。為了遞增累加CRC32值，軟件應(yīng)在目標操作數(shù)中保留前一個CRC32操作的結(jié)果，然后，以源操作數(shù)中新輸入的數(shù)據(jù)再次執(zhí)行這個CRC32指令。在源操作數(shù)中包含的數(shù)據(jù)以所反射的位次序處理。這意味著，源操作數(shù)中的最高有效位被視為商的最低有效位，對源操作數(shù)的所有位都應(yīng)這樣看待。同樣，CRC操作的結(jié)果是以所反射的位次序存儲在目標操作數(shù)中，這意味著，所產(chǎn)生的CRC(位31)的最高有效位是存儲在目標操作數(shù)(位0)的最低有效位，對所有的CRC位也應(yīng)這樣看待。

以CRC32 r64,r/m64指令為例用偽碼給出其可能描述，其中，一個N位寬的操作數(shù)BIT_REFLECT是從最高有效位到最低有效位的逐位反射操作，MOD2是多項式做模2除法的余數(shù)。

TEMP1[63-0] = BIT_REFLECT64 (SRC[63-0])；

TEMP2[31-0] = BIT_REFLECT32 (DEST[31-0])；

TEMP3[95-0] = TEMP1[63-0] << 32；

TEMP4[95-0] = TEMP2[31-0] << 64；

TEMP5[95-0] = TEMP3[95-0] XOR TEMP4[95-0]；

TEMP6[31-0] = TEMP5[95-0] MOD2 11EDC6F41H；

DEST[31-0] = BIT_REFLECT (TEMP6[31-0])；

DEST[63-32] = 00000000H；

四、INTEL CRC指令應(yīng)用指導

Intel CRC指令將基于處理器的CRC，以實現(xiàn)快速高效的數(shù)據(jù)完整性檢驗，其成本低于上層數(shù)據(jù)傳輸協(xié)議(如Internet、小型計算機系統(tǒng)接口(SCSI)和遠程直接內(nèi)存存取(RDMA))中的單獨專用芯片[4]。下面給出Intel CRC指令應(yīng)用舉例及指導。

例1 簡單串行方法使用CRC32指令的偽代碼：

mov rax, crc_init ; rax = crc_init;

mov rbx, len

crc32_loop:

crc32 rax, [buff]

add buff, 8

sub rbx, 8

jne crc32_loop

例2 這里給出較完整的CRC32碼的計算程序。其中ESI的內(nèi)容為某一字節(jié)串的起始地址，EDX的內(nèi)容為這個字節(jié)串位的長度。

mov esi,eax

mov eax,0FFFFFFFFH ; 表示計算成功

test edx,edx ; 測試位串的字節(jié)長度，為0結(jié)束

jz _Exit

test esi,esi ; 測試字節(jié)串是否為空串，是結(jié)束

jz _Exit

mov ecx,edx

shr ecx, 2

test ecx,ecx ; 測試字節(jié)串的長度是否超過3，沒有結(jié)束

jz _Exit

xor edx,edx

_Acrc:

crc32 eax,[edx*4+esi] ;計算CRC碼

inc edx

cmp edx,ecx

jb _Acrc

_Exit:

not eax ;計算不成功00000000H

例3 計算CRC32的并行化方法。如果我們將緩沖區(qū)劃分為N個非重疊部分，然后并行執(zhí)行N個CRC32計算。由于每個計算相互獨立，因此每部分CRC32指令不再相關(guān)，這可以以吞吐率執(zhí)行。偽代碼給出了N+1個通道并行方法的主體處理循環(huán)。并行方法對于較大的緩沖區(qū)變得更有效。

；對N+1(N < 15)個通道并行方法，使用CRC32指令的偽代碼

mov r12, BLOCKSIZE/8

_main_loop:

crc32 rdx, [r9 + 0*BLOCKSIZE] ; crc0

crc32 rbx, [r9 + 1*BLOCKSIZE] ; crc1

crc32 rax, [r9 + 2*BLOCKSIZE] ; crc2

…

crc32 rxx, [r9 + N*BLOCKSIZE] ; crcN

add r9, N*8

dec r12

jne _main_loop

在此過程結(jié)束時, 我們有N+1個單獨的CRC值。然后將它們合并為單個值。合并采用無符號乘法進行。

五、結(jié)語

在信息通信、網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)倪^程中，普遍使用CRC32校驗碼，但軟件計算數(shù)據(jù)的CRC32校驗碼比較耗時，也是通信、網(wǎng)絡(luò)軟件性能的瓶頸之一。借助于Intel CRC32指令，利用本文給出的CRC碼計算方法，對相關(guān)軟件中校驗碼計算進行優(yōu)化，能夠顯著提高數(shù)據(jù)處理的速度，降低CPU的占用率。這為很多網(wǎng)絡(luò)應(yīng)用做軟件開發(fā)的人員帶來了一種設(shè)計思路。