如何使用SIMD指令高效实现atoi？-C++-PHP中文网

如何使用SIMD指令高效实现atoi？

Susan Sarandon

发布： 2024-11-26 20:16:14

原创

588 人浏览过

How to efficiently implement atoi using SIMD instructions?

如何使用SIMD实现atoi？

问题：
我想尝试编写一个atoi使用 SIMD 指令实现，包含在 RapidJSON 中。我想出的算法如下：

按以下方式初始化长度为 N 的向量：
[10^N..10^1]
转换将缓冲区中的每个字符转换为整数并将它们放入另一个向量中。
将有效数字向量中的每个数字乘以匹配的数字向量中的数字并对结果求和。

我的算法正确吗？有更好的办法吗？有使用任何 SIMD 指令集的 atoi 参考实现吗？

答案：
算法正确且完整。它适用于 int 和 uint，从 MIN_INT=-2147483648 到 MAX_INT=2147483647 以及从 MIN_UINT=0 到 MAX_UINT=4294967295。

提供了参考实现，使用 intel 语法用 GNU 汇编器编写。

这段代码的属性如下：

前导 '-' 字符表示负数（合理），前导 ' ' 字符被忽略
前导零（带或不带符号字符）被忽略
溢出被忽略 - 更大的数字只是环绕
零长度字符串导致值 0 = -0
识别无效字符，并且转换在第一个无效字符处结束
最后一个前导零之后的至少 16 个字节必须可访问，并且在 EOS 后读取可能存在安全隐患留给调用者
只需要SSE4.2

的方法算法如下：

ESI 中需要指向数字字符串
检查第一个字符是否为“-”，然后指示 EDX 中是否为负数 (A)
检查前导零和 EOS (B)
检查字符串获取有效数字并获取有效字符的 strlen() (C)
反转字符串，以便
10^0 的幂始终为 BYTE 15
10^1始终位于字节 14
10^2 始终位于字节 13
10^3 始终在 BYTE 12
10^4 始终在 BYTE 11
...
并屏蔽掉所有以下字符 (D)
从中减去饱和的“0” 16 个可能的字符中的每一个(1)
获取 16 个连续的字节值，并将它们拆分为两个 XMM 寄存器中的单词
(2)
P O N M L K J I | H G F E D C B A ->
H G F E | DC B A (XMM0)
P O N M | L K J I (XMM1)
将每个 WORD 乘以其位值模 10000 (1,10,100,1000)
（小于 MAX_WORD 的因子，每个 QWORD/halfXMM 4 个因子）
( 2) 所以我们可以在另一个之前水平组合两次
PMADDWD 指令可以执行此操作以及下一步：
将相邻的 WORD 水平添加到 DWORD (3)
H1000 G100 F10 E1 | D1000 C100 B10 A1 (XMM0)
P1000 O100 N10 M1 | L1000 K100 J10 I1 (XMM1)
将 XMM0 和 XMM1 中的相邻 DWORD 水平添加到 XMM0 (4)
xmmDst[31-0] = xmm0[63-32] xmm0[31-0]
xmmDst[63-32] = xmm0[127-96] xmm0[95-64]
xmmDst[95-64] = xmm1[63-32] xmm1[31-0]
xmmDst[127-96] = xmm1[127-96] xmm1[95-64]
XMM0 中的值乘以因子 (5)
P1000 O100 N10 M1（DWORD 因子1000000000000 = 对于 DWORD 来说太大，但对于 QWORD 数字字符串可能有用）
L1000 K100 J10 I1（DWORD 因子 100000000）
H 1000 G100 F10 E1（DWORD 因子 10000）
D1000 C100 B10 A1（DWORD 因子 1）
最后一步是将这四个 DWORD 添加在一起2PHADDD 由 2(PSHUFD PADDD)
- xmm0[31-0] = xmm0[63-32] xmm0[31-0] (6)xmm0[63-32] = xmm0[127-96] xmm0[95-64]
  （上面的 QWORD 包含相同内容，被忽略）
- 7)
8)