基本的字符串转数字算法是:
total = total*10 + digit
,从最高位开始计算 (例如对于一个由数字组成的ASCII字符串,
digit = *p++ - '0'
)。因此,最左侧/最高位/第一个数字(在内存中和读取顺序中)乘以10的N次方,其中N是其后的总数字数。
这种方法通常比每个数字乘以正确的10的幂之后再相加更有效率。后者需要2次乘法;一次增长为10的幂,另一次将其应用于数字。(或者使用递增的10的幂查找表)。
当然,
为了效率,您可以使用SSSE3 pmaddubsw
和SSE2 pmaddwd
并行地将数字与它们的位值相乘:请参见
有没有快速将8个ASCII十进制数字的字符串转换为二进制数字的方法?以及任意长度的
如何使用SIMD实现atoi?。但是当数字通常较短时,后者可能不会获胜。当大多数数字仅有几个数字时,一个标量循环是有效的。
在 @Michael 的回答基础上,可能有用的是将 int->string 函数停止于第一个非数字字符,而不是固定长度。这将捕捉到像用户按下回车键时字符串包含换行符之类的问题,以及避免将 12xy34
转换为一个非常大的数字。(将其视为 12
,就像 C 中的 atoi
函数)。停止字符也可以是 C 隐式长度字符串中的终止符 0
。
我还进行了一些改进:
我更改了寄存器,使其遵循x86-64 System V ABI(第一个参数在RDI中,返回值在EAX中)。
迁移至32位:这与64位无关;只需使用32位寄存器即可将其迁移到32位。 (例如,用
edi
替换
rdi
,用
ecx
替换
rax
,用
eax
替换
rax
)。请注意,在32位和64位之间存在C调用约定的差异,例如,EDI是调用保留的,并且参数通常在堆栈上传递。但是,如果您的调用者是汇编语言,则可以在EDI中传递参数。
global base10string_to_int
base10string_to_int:
movzx eax, byte [rdi]
sub eax, '0'
cmp al, 9
jbe .loop_entry
xor eax,eax
ret
.next_digit:
lea eax, [rax*4 + rax]
lea eax, [rax*2 + rcx]
.loop_entry:
inc rdi
movzx ecx, byte [rdi]
sub ecx, '0'
cmp ecx, 9
jbe .next_digit
ret
这会在第一个非数字字符处停止转换。通常,这将是终止隐式长度字符串的0字节。如果您想检测尾随垃圾,则可以在循环后通过检查
ecx == -'0'
来检查它是否为字符串末尾,而不是其他非数字字符(其仍然保持超出范围的
str [i] - '0'
整数“数字”值)。
如果您的输入是显式长度的字符串,则需要使用循环计数器而不是检查终止符(如@Michael的答案),因为内存中的下一个字节可能是另一个数字,或者可能在未映射的页中。
将第一次迭代特殊处理并在进入循环的主要部分之前处理它被称为
循环剥离。剥离第一次迭代允许我们特别优化它,因为我们知道total = 0,所以没有必要将任何东西乘以10。这就像从
sum = array [0];i = 1
开始,而不是
sum = 0,i = 0;
。
为了获得
良好的循环结构(带有底部条件分支),我使用了跳转到循环中间进行第一次迭代的技巧。这甚至不需要额外的
jmp
,因为我已经在剥离的第一次迭代中进行了分支。重新排列循环,使中间的
if()break
成为底部的循环分支,称为循环旋转,并且可能涉及剥离第一次迭代的前半部分和最后一次迭代的第二部分。
解决非数字退出循环的简单方法是在循环体中加入一个
jcc
,就像在
total = total*10 + digit
之前的C语言
if() break;
语句一样。但是这样我需要一个
jmp
,并且在循环中有2个总分支指令,意味着更多的开销。
如果我不需要
sub ecx, '0'
的结果作为循环条件,我也可以使用
lea eax, [rax*2 + rcx - '0']
在 LEA 中完成。但这会使 Sandybridge 系列 CPU 上的 LEA 延迟增加到 3 个时钟周期,而不是 1 个(3 组成部分的 LEA 而不是 2 或更少)。两个 LEA 在
eax
(
total
)上形成了一个循环传递的依赖链,因此在 Intel 上(特别是对于大数),这样做并不值得。在
base + scaled-index
和
base + scaled-index + disp8
速度相同的 CPU 上(
Bulldozer-family / Ryzen),如果您有一个明确的长度作为循环条件,并且根本不想检查数字,那么当然可以这样做。
我一开始使用了movzx进行零扩展加载,而不是在将数字从ASCII转换为整数后再进行。 (必须在某个时候执行此操作以添加到32位EAX中)。经常操作ASCII数字的代码使用字节操作数大小,例如
mov cl,[rdi]
。但这会在大多数CPU上创建对RCX旧值的错误依赖。
sub al,'0'
比
sub eax,'0'
节省1个字节,但在Nehalem / Core2甚至PIII上会导致部分寄存器停顿。在其他所有CPU系列上都很好,即使是Sandybridge:它是AL的RMW,因此它不会单独重命名部分寄存器和EAX。但是,
cmp al,9
没有问题,因为读取字节寄存器总是fine。它可以节省一个字节(特殊编码,没有ModRM字节),所以我在函数顶部使用了它。
如果想了解更多优化方面的内容,请查看http://agner.org/optimize,以及x86 标签维基中的其他链接。
标签维基还有初学者链接,包括一个FAQ部分,其中包含指向整数转换为字符串函数和其他常见初学者问题的链接。
相关: