本章讨论的是将小写字符转换成大写字符的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码表格就能看得更清楚了。
图48.1 EMACS中的7位ASCII码表
非优化的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
优化的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寄存器。可见它能在条件不成立的情况下舍弃错误的值。也就是说,编译器为了避免使用条件转移指令而预先进行了减法运算。
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.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
本章演示的优化技术已经属于十分常见的编译器优化技术。逆向工程分析人员会频繁遇到这种类型的汇编指令。
[1] 然而,如果小心翼翼的话,还是有些编译器即使不用优化的办法,也能输出正确的结果。