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

DEATHTOUCH 发表于 2022-2-7 22:31

本帖最后由 DEATHTOUCH 于 2023-10-10 15:33 编辑

上次在论坛看到有人求助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通常使用查表法，不同的多项式会产生不同的表，提前调用函数建表或使用固定表，一般的方法如下：

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;
}

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

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

基本上展开4次就够了，没必要展开太多。
下面我们来看看如何使用crc32指令，在此之前，我们要看看cpu是不是支持SSE4.2指令集，这里我们使用cpuid指令。
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指令的具体使用函数：
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, // 一次4字节crc
add edx, 4
sub ecx, 4
jmp @@1 // 循环
@@2:
cmp ecx, 0 // 此时ecx在0~3
je    @@end
@@3:
crc32 eax, byte // 一个一个字节处理，最多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, // 一次8字节
add rdx, 8
sub r8, 8
jmp @@1
@@2:
cmp r8, 0
je    @@end
@@3:
crc32 rax, byte // 和之前一样
inc rdx
dec r8
jnz @@3
@@end:
xor eax, $FFFFFFFF
{$endif}
end;
用伪代码描述一下，只描述32位的，64位同理：

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位的优化版本：

function hwcrc32c4k(crc:UInt32; buf:Pointer):UInt32;assembler;
const
K:Array 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,    // crc_a
crc32 ebx, // crc_b
crc32 ecx, // crc_c
add edi, 4
cmp edi, edx
jb    @@1
@@2:
movdqaxmm0, 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
psrldqxmm1, 4
movd edx, xmm1// edx is high part
crc32 ecx,
crc32 ecx,
xor eax,
xor edx,
crc32 ecx, eax
crc32 ecx, edx
mov eax, ecx
@@end:
pop ebx
pop edi
end;

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

DEATHTOUCH 发表于 2023-10-9 00:06

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

纯软件实现的话可以加大表的数量，性能可以提升很多（参见 slicing by 4 或 slicing ...
我根据你给的https://www.corsix.org/content/fast-crc32c-4k用汇编写了那个crc32_4k_three_way，对于32位来说基本上翻倍。

代码：
function crc32_4k_three_way(crc:UInt32; buf:Pointer):UInt32;assembler;
const
K:Array 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,
crc32 eax,
crc32 ebx,
crc32 ebx,
crc32 ecx,
crc32 ecx,
add edx, 8
cmp edx, edi
jb    @@1
@@2:
movdqaxmm0, K
movd xmm1, eax
movd xmm2, ebx
pclmulqdq xmm1, xmm0, $00
pclmulqdq xmm2, xmm0, $10
pxor xmm1, xmm2
movq ab, xmm1
crc32 ecx,
crc32 ecx,
mov eax,
xor ab, eax
mov eax,
xor ab, eax
crc32 ecx, ab
crc32 ecx, ab
mov eax, ecx
@@end:
pop ebx
pop edi
end;

应该还可以再优化一下。

对比下面这段就是翻倍的速度：
function crc32c(crc:UInt32; const buf; len:PtrUInt):UInt32;assembler;
asm
xor eax, $FFFFFFFF
@@1:
cmp ecx, 4
jb    @@2
crc32 eax,
add edx, 4
sub ecx, 4
jmp @@1
@@2:
cmp ecx, 0
je    @@end
@@3:
crc32 eax, byte
inc edx
dec ecx
jnz @@3
@@end:
xor eax, $FFFFFFFF
end;

爱飞的猫 发表于 2023-10-8 23:58

这个还不是最快的。

纯软件实现的话可以加大表的数量，性能可以提升很多（参见 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 发表于 2022-2-7 22:35

膜拜大牛！{:1_921:}

JuncoJet 发表于 2022-2-8 00:33

速度可以和time33比么

gxsky 发表于 2022-2-8 01:50

现实中的应用场景是什么

ytahdou 发表于 2022-2-8 08:15

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

DEATHTOUCH 发表于 2022-2-8 13:16

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

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

DEATHTOUCH 发表于 2022-2-8 13:18

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

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

天山雪 发表于 2022-3-14 01:21

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

冥界3大法王 发表于 2023-3-8 23:54

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

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

DEATHTOUCH 发表于 2023-3-9 00:29

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

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

页: [1] 2

吾爱破解 - 52pojie.cn's Archiver

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