Intel CRC指令研究及其應用

彭茜珍

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

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

一、引言

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

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

幾個基本概念：[1]

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

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

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

CRC檢驗碼的計算：

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

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

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

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

二、CRC32校驗碼算法研究

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

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

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

(1)

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

(2)

可以設：

(3)

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

(4)

再設：

(5)

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

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

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

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

本推論是理解CRC32指令的關鍵之所在。

三、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

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

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

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

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

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

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

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

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指令應用指導

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

例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的內容為某一字節串的起始地址，EDX的內容為這個字節串位的長度。

mov esi,eax

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

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

jz _Exit

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

jz _Exit

mov ecx,edx

shr ecx, 2

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

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的并行化方法。如果我們將緩沖區劃分為N個非重疊部分，然后并行執行N個CRC32計算。由于每個計算相互獨立，因此每部分CRC32指令不再相關，這可以以吞吐率執行。偽代碼給出了N+1個通道并行方法的主體處理循環。并行方法對于較大的緩沖區變得更有效。

；對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

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

五、結語

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