第42章 字符串转换成数字,函数atoi()

我们来重新实现一下标准的C函数atoi()。这是一个将字符串转换成整数的函数。

42.1 例1

本例可按照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.1 64位下的MSVC 2013优化

指令清单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编译器经常会做这种指令替换。

42.1.2 64位下的GCC 4.9.1优化

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.1.3 ARM模式下Keil 6/2013优化

指令清单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.1.4 Thumb模式下Keil 6/2013优化

指令清单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’”、求得中间差,然后计算输入字符与中间差的和。虽然这种算法的计算结果必定和源代码的计算结果相同,但是请不要忽视编译器的算式重排功能。

42.1.5 ARM64下的GCC 4.9.1优化

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

42.2 例2

现在,我们把例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.2.1 64位下的GCC 4.9.1优化

指令清单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.2.2 ARM模式下的Keil6/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(取反)指令。

42.3 练习

这里顺便提一下,安全研究人员经常研究各种异常情况。他们重点关注不合乎预期的输入值,通过这种数据诱使程序进行某种与设计思路相左的行为。因此,他们也会关注模糊测试方法。作为练习,我们可以试图输入非数字字符,看看会发生什么。自己可以尝试着解释一下背后的成因是什么。