我们来重新实现一下标准的C函数atoi()。这是一个将字符串转换成整数的函数。
本例可按照ASCII表把数字字符转换为数字。代码没有做容错处理,因此当输入值为非数字型字符时,返回值也就不会正确。
#include <stdio.h>
int my_atoi (char *s)
{
int rt=0;
while (*s)
{
rt=rt*10 + (*s-'0');
s++;
};
return rt;
};
int main()
{
printf ("%d\n", my_atoi ("1234"));
printf ("%d\n", my_atoi ("1234567890"));
};
这个算法实现的是从左到右读取数字,并将每个读取的字符减去数字0的ASCII值。我们知道,在ASCII表中,数字0~9是按照递增顺序连续存放的。因此无论字符“0”对应的数值是多少,“0”的值减去“0”的值为0,“9”的值减去“0”的值为9。按照这种模式,函数就可把单字节字符转换为相应数值。因此,如果函数读取的字符不是数字型字符的话,计算结果就不会正确。在处理多字符字符串时还要考虑数权问题,本例会把前一步的结果(即变量rt)乘以10,再累加本次转换出来的数字。换句话说,在转换单个字符的每次迭代过程中,转换函数都应当给上一次迭代的转换结果分配一次合理的数权。最后一个被转换的字符不会被提高数权。
指令清单42.1 64位下的MSVC2013优化
s$ = 8
my_atoi PROC
; load first character
movzx r8d, BYTE PTR [rcx]
; EAX is allocated for "rt" variable
; its 0 at start'
xor eax, eax
; first character is zero-byte, i.e., string terminator?
; exit then.
test r8b, r8b
je SHORT $LN9@my_atoi
$LL2@my_atoi:
lea edx, DWORD PTR [rax+rax*4]
; EDX=RAX+RAX*4=rt+rt*4=rt*5
movsx eax, r8b
; EAX=input character
; load next character to R8D
movzx r8d, BYTE PTR [rcx+1]
; shift pointer in RCX to the next character:
lea rcx, QWORD PTR [rcx+1]
lea eax, DWORD PTR [rax+rdx*2]
; EAX=RAX+RDX*2=input character + rt*5*2=input character + rt*10
; correct digit by subtracting 48 (0x30 or '0')
add eax, -48 ; ffffffffffffffd0H
; was last character zero?
Test r8b, r8b
; jump to loop begin, if not
jne SHORT $LL2@my_atoi
$LN9@my_atoi:
ret 0
my_atoi ENDP
字符串的第一个字符可能就是终止符。在这种情况下,函数不应当进入字符转换的迭代过程。此外,编译器没有分配“乘以10”的乘法指令,而是使用了第一条、第三条LEA指令分步实现了“上次迭代的rt值乘以5”、“输入字符+5倍原始rt值×2”的运算。某些情况下,MSVC编译器会刻意避开减法运算的SUB指令、转而分配“ADD某个负数”的指令来实现减法运算。本例就发生了这种情况。虽然笔者也不明白ADD指令的优越性到底在哪,但是MSVC编译器经常会做这种指令替换。
GCC 4.9.1优化更精确,但是它会在代码的最后添加一个多余的返回指令RET。其实一个RET就足够了。
指令清单42.2 64位下的GCC 4.9.1优化
my_atoi:
; load input character into EDX
movsx edx, BYTE PTR [rdi]
; EAX is allocated for "rt" variable
xor eax, eax
; exit, if loaded character is null byte
test dl, dl
je .L4
.L3:
lea eax, [rax+rax*4]
; EAX=RAX*5=rt*5
; shift pointer to the next character:
add rdi, 1
lea eax, [rdx-48+rax*2]
; EAX=input character - 48 + RAX*2 = input character - '0' + rt*10
; load next character:
movsx edx, BYTE PTR [rdi]
; goto loop begin, if loaded character is not null byte
test dl, dl
jne .L3
rep ret
.L4:
rep ret
指令清单42.3 ARM模式下Keil 6/2013 优化
my_atoi PROC
; R1 will contain pointer to character
MOV r1,r0
; R0 will contain "rt" variable
MOV r0,#0
B |L0.28|
|L0.12|
ADD r0,r0,r0,LSL #2
; R0=R0+R0<<2=rt*5
ADD r0,r2,r0,LSL #1
; R0=input character + rt*5<<1 = input character + rt*10
; correct whole thing by subtracting '0' from rt:
SUB r0,r0,#0x30
; shift pointer to the next character:
ADD r1,r1,#1
|L0.28|
; load input character to R2
LDRB r2,[r1,#0]
; is it null byte? if no, jump to loop body.
CMP r2,#0
BNE |L0.12|
; exit if null byte.
; "rt" variable is still in R0 register, ready to be used in caller function
BX lr
ENDP
指令清单42.4 Thumb模式下Keil 6/2013优化
my_atoi PROC
; R1 will be pointer to the input character
MOVS r1,r0
; R0 is allocated to "rt" variable
MOVS r0,#0
B |L0.16|
|L0.6|
MOVS r3,#0xa
; R3=10
MULS r0,r3,r0
; R0=R3*R0=rt*10
; shift pointer to the next character:
ADDS r1,r1,#1
; correct whole thing by subtracting 0' character from it':
SUBS r0,r0,#0x30
ADDS r0,r2,r0
; rt=R2+R0=input character + (rt*10 - '0')
|L0.16|
; load input character to R2
LDRB r2,[r1,#0]
; is it zero?
CMP r2,#0
; jump to loop body if it is not
BNE |L0.6|
; rt variable in R0 now, ready to be used in caller function
BX lr
ENDP
很有趣的是,我们以前上学时学习到的规则是:加法和减法的运算顺序无所谓先后,完全可以重排。本例就活用了这一原则:编译器首先计算乘/减法的混合运算表达式“rt*10−‘0’”、求得中间差,然后计算输入字符与中间差的和。虽然这种算法的计算结果必定和源代码的计算结果相同,但是请不要忽视编译器的算式重排功能。
ARM64的编译器可以使用预增量指令后缀。
指令清单42.5 ARM64的GCC 4.9.1指令优化
my_atoi:
; load input character into W1
ldrb w1, [x0]
mov x2, x0
; X2=address of input string
; is loaded character zero?
; jump to exit if its so'
; W1 will contain 0 in this case.
; it will be reloaded into W0 at L4.
cbz w1, .L4
; W0 will contain "rt" variable
; initialize it at zero:
mov w0, 0
.L3:
; subtract 48 or '0' from input variable and put result into W3:
sub w3, w1, #48
; load next character at address X2+1 into W1 with pre-increment:
ldrb w1, [x2,1]!
add w0, w0, w0, lsl 2
; W0=W0+W0<<2=W0+W0*4=rt*5
add w0, w3, w0, lsl 1
; W0=input digit + W0<<1 = input digit + rt*5*2 = input digit + rt*10
; if the character we just loaded is not null byte, jump to the loop begin
cbnz w1, .L3
; variable to be returned (rt) is in W0, ready to be used in caller function
ret
.L4:
mov w0, w1
ret
现在,我们把例1的源代码改得更高级一些:令其检测第一个字符是否为负数符号“−”,并且检测输入值里有没有非数字型字符;当输入字符串含有非数字字符的时候,要令程序提示错误信息。
#include <stdio.h>
int my_atoi (char *s)
{
int negative=0;
int rt=0;
if (*s=='-')
{
negative=1;
s++;
};
while (*s)
{
if (*s<'0' || *s>'9')
{
printf ("Error! Unexpected char: '%c'\n", *s);
exit(0);
};
rt=rt*10 + (*s-'0');
s++;
};
if (negative)
return -rt;
return rt;
};
int main()
{
printf ("%d\n", my_atoi ("1234"));
printf ("%d\n", my_atoi ("1234567890"));
printf ("%d\n", my_atoi ("-1234"));
printf ("%d\n", my_atoi ("-1234567890"));
printf ("%d\n", my_atoi ("-a1234567890")); // error
};
指令清单42.6 64位下的GCC 4.9.1优化
.LC0:
.string "Error! Unexpected char: '%c'\n"
my_atoi:
sub rsp, 8
movsx edx, BYTE PTR [rdi]
; check for minus sign
cmp dl, 45 ; '-'
je .L22
xor esi, esi
test dl, dl
je .L20
.L10:
; ESI=0 here if there was no minus sign and 1 if it was
lea eax, [rdx-48]
; any character other than digit will result unsigned number greater than 9 after subtraction
; so if it is not digit, jump to L4, where error will be reported:
cmp al, 9
ja .L4
xor eax, eax
jmp .L6
.L7:
lea ecx, [rdx-48]
cmp cl, 9
ja .L4
.L6:
lea eax, [rax+rax*4]
add rdi, 1
lea eax, [rdx-48+rax*2]
movsx edx, BYTE PTR [rdi]
test dl, dl
jne .L7
; if there was no minus sign, skip NEG instruction
; if it was, execute it.
test esi, esi
je .L18
neg eax
.L18:
add rsp, 8
ret
.L22:
movsx edx, BYTE PTR [rdi+1]
lea rax, [rdi+1]
test dl, dl
je .L20
mov rdi, rax
mov esi, 1
jmp .L10
.L20:
xor eax, eax
jmp .L18
.L4:
; report error. character is in EDX
mov edi, 1
mov esi, OFFSET FLAT:.LC0 ; "Error! Unexpected char: '%c'\n"
xor eax, eax
call __printf_chk
xor edi, edi
call exit
如果字符串的第一个字符是负号,那么就要在转换的最后阶段执行NEG指令,把结果转换为负数。
另外值得一提的是“检测字符是否是数字字符”的判断表达式。我们在程序中可以看到代码为:
if (*s<'0' || *s>'9')
...
这是两个比较操作。比较有意思的是,我们完全可以只用一个比较指令就完成这两步比较运算:将输入字符的值减去“0”字符的值,将结果视为无符号数(这是关键)与9进行比较。若最后的无符号数比9还大,那么输入字符就不是数字字符。
比如说,如果我们在输入的字符串中含有小数点(“.”),这个符号在ASCII表中排在字符零“0”的前2位。因此判断语句的减法运算表达式是:46−48=−2。有符号数的减法运算当然会求得有符号数。被减数比减数小,计算的结果肯定是负数。但是,如果我们把这个结果当作无符号数来处理的话,它将是0xfffffffe(对应的十进制数是42949672294),显然它比9大。举这个例子是想说明按照无符号数处理的重要性。
编译器经常会这样做,因此我们应该重新认识这种技巧。
我们可以本书的其他地方看到这个例子:比如48.1.2节。
在编译64位应用程序时,MSVC 2013还好使用这种优化技巧。
指令清单42.7 ARM模式下的Keil6/2013优化
1 my_atoi PROC
2 PUSH {r4-r6,lr}
3 MOV r4,r0
4 LDRB r0,[r0,#0]
5 MOV r6,#0
6 MOV r5,r6
7 CMP r0,#0x2d '-'
8 ; R6 will contain 1 if minus was encountered, 0 if otherwise
9 MOVEQ r6,#1
10 ADDEQ r4,r4,#1
11 B |L0.80|
12 |L0.36|
13 SUB r0,r1,#0x30
14 CMP r0,#0xa
15 BCC |L0.64|
16 ADR r0,|L0.220|
17 BL __2printf
18 MOV r0,#0
19 BL exit
20 |L0.64|
21 LDRB r0,[r4],#1
22 ADD r1,r5,r5,LSL #2
23 ADD r0,r0,r1,LSL #1
24 SUB r5,r0,#0x30
25 |L0.80|
26 LDRB r1,[r4,#0]
27 CMP r1,#0
28 BNE |L0.36|
29 CMP r6,#0
30 ; negate result
31 RSBNE r0,r5,#0
32 MOVEQ r0,r5
33 POP {r4-r6,pc}
34 ENDP
35
36 |L0.220|
37 DCB "Error! Unexpected char: '%c'\n",0
32位ARM的指令集里没有NEG(取负)指令,因此编译器分配了第31行的“反向减法”指令。当第29行指令——即CMP的比较结果为“不相等”时,才会执行第31行的条件执行指令(我们可以看到NE后缀,也就是“(运行条件为)Not Equal”的意思)。而后,RSBNE指令用0减去上一步的计算结果。这条指令确实就是减法运算指令,只是被减数和减数的操作符排列位置对调了一下。用0来减去任何数,实际的效果就是对该数取负。实现的结果可以用这个来表示:0−x=−x。
Thumb程序的运算模式几乎完全相同。
在编译ARM64平台的应用程序时,GCC 4.9能够分配NEG(取反)指令。
这里顺便提一下,安全研究人员经常研究各种异常情况。他们重点关注不合乎预期的输入值,通过这种数据诱使程序进行某种与设计思路相左的行为。因此,他们也会关注模糊测试方法。作为练习,我们可以试图输入非数字字符,看看会发生什么。自己可以尝试着解释一下背后的成因是什么。