吾爱破解 - 52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

查看: 4149|回复: 14
收起左侧

[其他原创] 基于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通常使用查表法,不同的多项式会产生不同的表,提前调用函数建表或使用固定表,一般的方法如下:
[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指令研究出的具体内容了,有问题欢迎提出,共同讨论。

免费评分

参与人数 5吾爱币 +5 热心值 +4 收起 理由
天山雪 + 1 + 1 谢谢@Thanks!
kaixianxian + 1 + 1 用心讨论,共获提升!
tzg2008 + 1 谢谢@Thanks!
chuiyan121 + 1 + 1 用心讨论,共获提升!
Microooooogle + 1 + 1 用心讨论,共获提升!

查看全部评分

发帖前要善用论坛搜索功能,那里可能会有你要找的答案或者已经有人发布过相同内容了,请勿重复发帖。

 楼主| 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位来说基本上翻倍。

代码:
[Asm] 纯文本查看 复制代码
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] 纯文本查看 复制代码
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;

免费评分

参与人数 1热心值 +1 收起 理由
爱飞的猫 + 1 强强

查看全部评分

爱飞的猫 发表于 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
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++等。
您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则

返回列表

RSS订阅|小黑屋|处罚记录|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2024-11-24 19:33

Powered by Discuz!

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表