彭茜珍

(湖北科技學(xué)院 學(xué)報(bào)編輯部,湖北 咸寧 437100)

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

一、引言

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

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

幾個(gè)基本概念：[1]

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

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

表1 常用的CRC32碼的生成多項(xiàng)式

CRC檢驗(yàn)碼的計(jì)算：

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

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

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

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

二、CRC32校驗(yàn)碼算法研究

CRC32碼一位計(jì)算公式的推導(dǎo)：

對(duì)于一個(gè)二進(jìn)制序列數(shù)可以表示為式(1)：

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

(1)

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

(2)

可以設(shè)：

(3)

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

(4)

再設(shè)：

(5)

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

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

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

推論：對(duì)于較長(zhǎng)的二進(jìn)制序列，可以通過(guò)每次左移4位、8位、16位、32位及64位來(lái)計(jì)算其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可以理解為將目標(biāo)左移8位(即上一次計(jì)算出的CRC-32碼)再與源左移32位后相加即(異或運(yùn)算)后模2除以G(X)所得的余數(shù)。

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

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

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

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

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

以CRC32 r64,r/m64指令為例用偽碼給出其可能描述，其中，一個(gè)N位寬的操作數(shù)BIT_REFLECT是從最高有效位到最低有效位的逐位反射操作，MOD2是多項(xiàng)式做模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)用指導(dǎo)

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

例1 簡(jiǎn)單串行方法使用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碼的計(jì)算程序。其中ESI的內(nèi)容為某一字節(jié)串的起始地址，EDX的內(nèi)容為這個(gè)字節(jié)串位的長(zhǎng)度。

mov esi,eax

mov eax,0FFFFFFFFH ; 表示計(jì)算成功

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

jz _Exit

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

jz _Exit

mov ecx,edx

shr ecx, 2

test ecx,ecx ; 測(cè)試字節(jié)串的長(zhǎng)度是否超過(guò)3，沒(méi)有結(jié)束

jz _Exit

xor edx,edx

_Acrc:

crc32 eax,[edx*4+esi] ;計(jì)算CRC碼

inc edx

cmp edx,ecx

jb _Acrc

_Exit:

not eax ;計(jì)算不成功00000000H

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

；對(duì)N+1(N < 15)個(gè)通道并行方法，使用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

在此過(guò)程結(jié)束時(shí), 我們有N+1個(gè)單獨(dú)的CRC值。然后將它們合并為單個(gè)值。合并采用無(wú)符號(hào)乘法進(jìn)行。

五、結(jié)語(yǔ)

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