基于Intel SSE4.2指令集crc32指令进行快速crc32c校验(使用Delphi/Fpc内联汇编实现)

DEATHTOUCH

上次在论坛看到有人求助crc32是什么指令，在我了解了该指令之后，将我目前所得的成果分享给大家。CRC32通常用于数据的校验，但是使用纯软件实现的CRC32速度较慢，于是Intel在扩展指令集SSE4.2中加入了crc32指令，用于快速的crc32计算，经过多年(大概10多年)，现在支持SSE4.2的cpu基本已经普及。
但是该指令与我们平常见到的crc32校验有所不同，具体是crc32指令使用的是多项式0x1EDC6F41(反转后为0x82F63B78)，我们称之为CRC32C；而一般用的crc32使用的多项式为0x04C11DB7(反转后为0xEDB88320)，符合IEEE 802.3规范，也可以称为CRC32B。
软件实现的CRC32通常使用查表法，不同的多项式会产生不同的表，提前调用函数建表或使用固定表，一般的方法如下：

[C] 纯文本查看 复制代码

?

1 2 3 4 5 6 7 8

unsigned long crc32(unsigned long crc, char* buf, int len) {     crc = crc ^ 0xFFFFFFFF;     for (int i=0;i<len;i++) {         crc = CRC32Table[(crc ^ *(buf++)) & 0xFF] ^ (crc >> 8); // CRC32Table是一个256长度的无符号整型数组，也就是我们说的表     }     return crc ^ 0xFFFFFFFF; }

对于上面的代码，显然效率不是很高，我们可以使用循环展开的方法进行手动优化，伪代码如下：

[C] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12

while (len>=4){     crc = CRC32Table[(crc ^ buf[0]) & 0xFF] ^ (crc >> 8);     crc = CRC32Table[(crc ^ buf[1]) & 0xFF] ^ (crc >> 8);     crc = CRC32Table[(crc ^ buf[2]) & 0xFF] ^ (crc >> 8);     crc = CRC32Table[(crc ^ buf[3]) & 0xFF] ^ (crc >> 8);     len-=4;     buf+=4; } while (len>0){     crc = CRC32Table[(crc ^ *(buf++)) & 0xFF] ^ (crc >> 8);     len--; }

基本上展开4次就够了，没必要展开太多。
下面我们来看看如何使用crc32指令，在此之前，我们要看看cpu是不是支持SSE4.2指令集，这里我们使用cpuid指令。

[Delphi] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15

function SSE42Support:Boolean;assembler; asm @start:   push ebx // 注意64位汇编要使用 push rbx   mov eax, 1 // eax为1，返回cpu功能信息   cpuid   test ecx, $100000 // ecx第20位(从0开始)为1，则说明支持SSE4.2   je @not   mov eax, 1 // 返回值设置为1   jmp @out @not:   xor eax, eax @out:   pop ebx // 注意64位汇编要使用 pop rbx end;

如果该函数返回True，那么我们可以放心使用crc32指令了，下面是crc32指令的具体使用函数：

[Delphi] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

function FastCrc32c(crc:LongWord;const buf;len:Integer):LongWord;assembler; asm {$ifdef CPUX86} { crc = eax, buf = edx, len = ecx } // 这是参数所代表的寄存器，Delphi使用的是 eax、edx、ecx、栈 的顺序，不同语言要看具体情况     xor     eax, $FFFFFFFF @@1:     cmp     ecx, 4 // 与4比较     jb      @@2 // 小于则跳走     crc32   eax, [edx] // 一次4字节crc     add     edx, 4     sub     ecx, 4     jmp     @@1 // 循环 @@2:     cmp     ecx, 0 // 此时ecx在0~3     je      @@end @@3:     crc32   eax, byte [edx] // 一个一个字节处理，最多3次     inc     edx     dec     ecx     jnz     @@3 @@end:     xor     eax, $FFFFFFFF {$else} { crc = rcx, buf = rdx, len = r8 } // Windows平台下64位汇编参数统一为 rcx、rdx、r8、r9、栈     mov     rax, rcx     xor     eax, $FFFFFFFF @@1:     cmp     r8, 8     jb      @@2     crc32   rax, [rdx] // 一次8字节     add     rdx, 8     sub     r8, 8     jmp     @@1 @@2:     cmp     r8, 0     je      @@end @@3:     crc32   rax, byte [rdx] // 和之前一样     inc     rdx     dec     r8     jnz     @@3 @@end:     xor     eax, $FFFFFFFF {$endif} end;

用伪代码描述一下，只描述32位的，64位同理：

[C] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11

eax = crc; while (len>=4){     ebx = *(long *)(buf++);     crc32 eax, ebx     len-=4; } while (len>0){     bl= *(buf++);     crc32 eax, bl     len--; }

你会发现这些代码和前面循环展开后的代码是如此的相似！

使用1GB的缓冲区，每个字节都填充1，来测试计算这个缓冲区的crc32c的耗时。

在我的电脑上，32位查表法需要大约2200毫秒，用crc32指令要大约200毫秒；64位查表法需要大约2250毫秒，而用crc32指令只要大约110毫秒。

不过根据Faster CRC32-C on x86 (corsix.org)，有一种更好的利用crc32指令提高吞吐量的方法，就是同时用crc32指令计算3段缓冲区并将结果合并，实测发现32位有大约50%多的提升，但是对于64位几乎没有提升，目前并不清楚具体原因，可能一次分段是4K太小了，导致其它指令的开销过大，可能使用纯汇编会有更好的效果。

这里给出4KB缓冲区32位的优化版本：

[Delphi] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

function hwcrc32c4k(crc:UInt32; buf:Pointer):UInt32;assembler; const   K:Array[0..3] of UInt32 = ($8A074012, 0, $93E106A4, 0); asm     push    edi     push    ebx     xor     ebx, ebx     xor     ecx, ecx     mov     edi, edx  // edi is data pointer     add     edx, 1360 @@1:     crc32   eax, [edi]        // crc_a     crc32   ebx, [edi+1360]   // crc_b     crc32   ecx, [edi+1360*2] // crc_c     add     edi, 4     cmp     edi, edx     jb      @@1 @@2:     movdqa  xmm0, K     movd    xmm1, eax     movd    xmm2, ebx     pclmulqdq xmm1, xmm0, $00     pclmulqdq xmm2, xmm0, $10     pxor    xmm1, xmm2     movd    eax, xmm1  // eax is low part     psrldq  xmm1, 4     movd    edx, xmm1  // edx is high part     crc32   ecx, [edi+1360*2]     crc32   ecx, [edi+1360*2+4]     xor     eax, [edi+1360*2+8]     xor     edx, [edi+1360*2+12]     crc32   ecx, eax     crc32   ecx, edx     mov     eax, ecx @@end:     pop     ebx     pop     edi end;

以上就是本人关于crc32指令研究出的具体内容了，有问题欢迎提出，共同讨论。

DEATHTOUCH

爱飞的猫 发表于 2023-10-8 23:58
这个还不是最快的。

纯软件实现的话可以加大表的数量，性能可以提升很多（参见 slicing by 4 或 slicing ...

我根据你给的https://www.corsix.org/content/fast-crc32c-4k用汇编写了那个crc32_4k_three_way，对于32位来说基本上翻倍。

代码：

[Asm] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

function crc32_4k_three_way(crc:UInt32; buf:Pointer):UInt32;assembler; const   K:Array[0..3] of UInt32 = ($8A074012, 0, $93E106A4, 0); var   ab:UInt64; asm     push    edi     push    ebx     xor     ebx, ebx     xor     ecx, ecx     mov     edi, edx     add     edi, 1360 @@1:     crc32   eax, [edx]     crc32   eax, [edx+4]     crc32   ebx, [edx+1360]     crc32   ebx, [edx+1360+4]     crc32   ecx, [edx+1360*2]     crc32   ecx, [edx+1360*2+4]     add     edx, 8     cmp     edx, edi     jb      @@1 @@2:     movdqa  xmm0, K     movd    xmm1, eax     movd    xmm2, ebx     pclmulqdq xmm1, xmm0, $00     pclmulqdq xmm2, xmm0, $10     pxor    xmm1, xmm2     movq    ab, xmm1     crc32   ecx, [edx+1360*2]     crc32   ecx, [edx+1360*2+4]     mov     eax, [edx+1360*2+8]     xor     ab[0], eax     mov     eax, [edx+1360*2+12]     xor     ab[4], eax     crc32   ecx, ab[0]     crc32   ecx, ab[4]     mov     eax, ecx @@end:     pop     ebx     pop     edi end;

应该还可以再优化一下。

对比下面这段就是翻倍的速度：

[Asm] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21

function crc32c(crc:UInt32; const buf; len:PtrUInt):UInt32;assembler; asm     xor     eax, $FFFFFFFF @@1:     cmp     ecx, 4     jb      @@2     crc32   eax, [edx]     add     edx, 4     sub     ecx, 4     jmp     @@1 @@2:     cmp     ecx, 0     je      @@end @@3:     crc32   eax, byte [edx]     inc     edx     dec     ecx     jnz     @@3 @@end:     xor     eax, $FFFFFFFF end;

爱飞的猫

这个还不是最快的。

纯软件实现的话可以加大表的数量，性能可以提升很多（参见 slicing by 4 或 slicing by 8 技巧）
→ 代码参考 https://create.stephan-brumme.com/crc32/ ，有代码案例和性能评测。

SSE 加速还有个更快的 clmul 指令可以用，参考：
https://www.corsix.org/content/fast-crc32c-4k
主打一个每轮处理 64 字节，crc32 指令一次处理 8 字节也赶不上这个效率

slicing 技巧和 clmul SSE 指令都是英特尔研究的，还出了论文（当然，我还看不太懂，只会拿来用）：

- M. E. Kounavis and F. L. Berry, "Novel Table Lookup-Based Algorithms for High-Performance CRC Generation," in IEEE Transactions on Computers, vol. 57, no. 11, pp. 1550-1560, Nov. 2008, doi: 10.1109/TC.2008.85.
- V. Gopal, E. Ozturk, et al., Fast CRC Computation for Generic Polynomials Using PCLMULQDQ Instruction, 2009

chuiyan121

膜拜大牛！

JuncoJet

速度可以和time33比么

gxsky

现实中的应用场景是什么

ytahdou

大神，Delphi现在能够研究的这么NewBee的不多了。

DEATHTOUCH

JuncoJet 发表于 2022-2-8 00:33
速度可以和time33比么

time33一般是拿来给字符串哈希的，这个crc32是拿来文件校验的，用处不一样

DEATHTOUCH

gxsky 发表于 2022-2-8 01:50
现实中的应用场景是什么

crc32是干什么的，这个就是干什么的，只不过用cpu指令能加速crc32的运算，节省时间

天山雪

现在学习Delphi的人不多了吧。

冥界3大法王

天山雪 发表于 2022-3-14 01:21
现在学习Delphi的人不多了吧。

不对，我还活着呢，天天用得爱不释手啊。

DEATHTOUCH

冥界3大法王 发表于 2023-3-8 23:54
不对，我还活着呢，天天用得爱不释手啊。

是啊，很多时候用起来确实是很方便的，开发效率很高，而且植入汇编也很是友好，除了编译器优化确实不咋地，想要高性能还得用C/C++等。