本帖最后由 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通常使用查表法，不同的多项式会产生不同的表，提前调用函数建表或使用固定表，一般的方法如下：
[C] 纯文本查看 复制代码
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] 纯文本查看 复制代码
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] 纯文本查看 复制代码 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] 纯文本查看 复制代码 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] 纯文本查看 复制代码
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] 纯文本查看 复制代码 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指令研究出的具体内容了，有问题欢迎提出，共同讨论。
| 
[复制链接]
发表于 2022-2-7 22:31
|
发表于 2023-10-9 00:06
发表于 2023-10-8 23:58
