第48章 toupper()函数

本章讨论的是将小写字符转换成大写字符的toupper()函数。这是一个比较常见的函数。

char toupper (char c)
{
         if(c>='a' && c<='z')
                  return c-'a'+'A';
         else
                  return c;
}

这里的程序代码中,我们可以看到’a’+’A’这个表达式。这种写法旨在增强程序的可读性。在程序的实际编译过程中,它会被优化为相应的计算指令。[1]

我们知道,小写的英文首字母a的ASCII码十六进制是61,也就是十进制的97;而大写的A的ASCII码的十六进制则是41,相当于十进制的65。很显然,在ASCII码表中,两者的差值是32(0x20)。

实际上,我们从图48.1所示的这个7位标准ASCII码表格就能看得更清楚了。

4801{}

图48.1 EMACS中的7位ASCII码表

48.1 x64

48.1.1 两个比较操作

非优化的MSVC非常直接:为了执行转换到大写字母的目的,程序首先检查输入的符号的十进制数值是否在97~122这个范围,也就是小写字母a~z的范围内。如果输入值满足这个条件,那么就将它的数值减去十进制的32,从而得到相应的大写字母所对应的值了。非优化编译时,编译器同样会对代码进行小幅度的优化处理。

指令清单48.1 x64下的MSVC 2013非优化程序

 1  c$ = 8
 2  toupper PROC
 3          mov     BYTE PTR [rsp+8], cl
 4          movsx   eax, BYTE PTR c$[rsp]
 5          cmp     eax, 97
 6          jl      SHORT $LN2@toupper
 7          movsx   eax, BYTE PTR c$[rsp]
 8          cmp     eax, 122
 9          jg      SHORT $LN2@toupper
10          movsx   eax, BYTE PTR c$[rsp]
11          sub     eax, 32
12          jmp     SHORT $LN3@toupper
13          jmp     SHORT $LN1@toupper ; compiler artefact
14  $LN2@toupper:
15          movzx   eax, BYTE PTR c$[rsp] ; unnecessary casting
16  $LN1@toupper:
17  $LN3@toupper: ; compiler artefact
18          ret     0
19  toupper ENDP

需要注意的是:程序第3行把输入的字节装载到64位栈的那条指令。输入值显然是占据了64位的低8位,而其高位(从第8位到第63位)则保持不变。我们可以在调试器debugger里看到这高56位是随机的噪音数据(也就是随机数)。因为所有指令都是以字节为操作对象,因此这种存储方案不会引发问题。第15行的最后一个MOVZX指令从本地栈里取出一个字节,把它无符号扩展为32位数据中,因此这高56位的噪音数据都会被填充为零。

而非优化的GCC生成的代码几乎相同。

指令清单48.2 x64下的GCC 4.9非优化代码

toupper:
         push    rbp
         mov     rbp, rsp
         mov     eax, edi
         mov     BYTE PTR [rbp-4], al
         cmp     BYTE PTR [rbp-4], 96
         jle     .L2
         cmp     BYTE PTR [rbp-4], 122
         jg      .L2
         movzx   eax, BYTE PTR [rbp-4]
         sub     eax, 32
         jmp     .L3
.L2:
         movzx   eax, BYTE PTR [rbp-4]
.L3:
         pop     rbp
         ret
48.1.2 一个比较操作

优化的MSVC表现得更好,它只分配一个比较操作指令。

指令清单48.3 x64下的MSVC 2013优化程序

toupper PROC
        lea     eax, DWORD PTR [rcx-97]
        cmp     al, 25
        ja      SHORT $LN2@toupper
        movsx   eax, cl
        sub     eax, 32
        ret     0
$LN2@toupper:
        movzx   eax, cl
        ret     0
toupper ENDP

前面已经解释过了,如何用一个比较操作来代替两个(参见本书42.2.1节)。

如果用C/C++重写,相应的源代码如下:

int tmp=c-97;

if (tmp>25)
         return c;
else
         return c-32;

这里的变量tmp应当是一个有符号数。这里的转换过程采用了两个减法指令以及一个比较指令。而原来的算法是通过两个比较指令加一个减法指令来实现的。

优化的GCC算法更好,它不用跳转指令JUMP,转而采用CMOVcc指令(参见33.1节)。

指令清单48.4 x64下的GCC 4.9优化程序

1  toupper:
2          lea      edx, [rdi-97] ; 0x61
3          lea      eax, [rdi-32] ; 0x20
4          cmp      dl, 25
5          cmova    eax, edi
6          ret

第三行的指令代码首先准备了要减去的数值0x20(十六进制的20,十进制的32),这会给人一种印象,好像减法总会发生似的。而第五行的指令,在不应进行转换(也就是不执行减法)的时候,把原始的输入数据复制给EAX寄存器。可见它能在条件不成立的情况下舍弃错误的值。也就是说,编译器为了避免使用条件转移指令而预先进行了减法运算。

48.2 ARM

ARM模式下的Keil优化也只有一个比较指令。

指令清单48.5 ARM模式下的Keil 6/2013优化程序

toupper PROC
        SUB     r1,r0,#0x61
        CMP     r1,#0x19
        SUBLS   r0,r0,#0x20
        ANDLS   r0,r0,#0xff
        BX      lr
        ENDP

从这里的程序我们可以看到,如果R1的值小于或等于0x19(十六进制的19),那么就会执行SUBLS指令和ANDLS指令。这两条指令实际执行的是转换大写字符的操作。

而Thumb模式下的Keil优化也可以通过单条比较指令进行大写转换。

指令清单48.6 Thumb模式下的Keil 6/2013的优化指令

toupper PROC
        MOVS    r1,r0
        SUBS    r1,r1,#0x61
        CMP     r1,#0x19
        BHI     |L0.14|
        SUBS    r0,r0,#0x20
        LSLS    r0,r0,#24
        LSRS    r0,r0,#24
|L0.14|
        BX      lr
        ENDP

最后的两条指令(LSLS和LSRS)的整体作用其实就是“AND reg,0xFF”。用C/C++表达式书写的话,它就可以表示为“(i<<24)>>24”,也就是先左移动24位,然后右移24位。显然,Thumbe模式下的Keil认为,它们这里的2个双字节的指令比“AND reg,0xFF”的运行效率更高(后者要首先将0xFF载入寄存器,然后做And与操作)。

48.2.1 ARM64下的GCC

指令清单48.7 ARM64下的非优化GCC 4.9

toupper:
        sub     sp, sp, #16
        strb    w0, [sp,15]
        ldrb    w0, [sp,15]
        cmp     w0, 96
        bls     .L2
        ldrb    w0, [sp,15]
        cmp     w0, 122
        bhi     .L2
        ldrb    w0, [sp,15]
        sub     w0, w0, #32
        uxtb    w0, w0
        b       .L3
.L2:
        ldrb    w0, [sp,15]
.L3:
        add     sp, sp, 16
        ret

指令清单48.8 ARM64下的优化GCC 4.9

toupper:
        uxtb    w0, w0
        sub     w1, w0, #97
        uxtb    w1, w1
        cmp     w1, 25
        bhi     .L2
        sub     w0, w0, #32
        uxtb    w0, w0
.L2:
        ret

48.3 总结

本章演示的优化技术已经属于十分常见的编译器优化技术。逆向工程分析人员会频繁遇到这种类型的汇编指令。


[1] 然而,如果小心翼翼的话,还是有些编译器即使不用优化的办法,也能输出正确的结果。