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的占用率。这为很多网络应用做软件开发的人员带来了一种设计思路。