本章是循环控制语句的具体应用。通常,strlen()函数由循环语句while()语句实现。参照MSVC标准库对strlen()函数的定义方法,我们讨论下述的程序:
int my_strlen (const char * str)
{
const char *eos = str;
while( *eos++ ) ;
return( eos - str - 1 );
}
int main()
{
// test
return my_strlen("hello!");
};
Non-optimizing MSVC
使用MSVC 2010编译上述程序可得到:
_eos$ = -4 ; size = 4
_str$ = 8 ; size = 4
_strlen PROC
push ebp
mov ebp, esp
push ecx
mov eax, DWORD PTR _str$[ebp] ; 将指针指向字符串
mov DWORD PTR _eos$[ebp], eax ; 指向局部变量eos
$LN2@strlen_:
mov ecx, DWORD PTR _eos$[ebp] ; ECX=eos
; take 8-bit byte from address in ECX and place it as 32-bit value to EDX with sign extension
movsx edx, BYTE PTR [ecx]
mov eax, DWORD PTR _eos$[ebp] ; EAX=eos
add eax, 1 ; EAX++
mov DWORD PTR _eos$[ebp], eax ; EAX还原为EOS
test edx, edx ; EDX = 0 ?
je SHORT $LN1@strlen_ ; yes, then finish loop
jmp SHORT $LN2@strlen_ ; continue loop
$LN1@strlen_:
; here we calculate the difference between two pointers
mov eax, DWORD PTR _eos$[ebp]
sub eax, DWORD PTR _str$[ebp]
sub eax, 1 ; subtract 1 and return result
mov esp, ebp
pop ebp
ret 0
_strlen_ ENDP
这里出现了两个新指令:MOVSX和TEST。
此处,MOVSX指令从内存中读取8位(单字节)数据,并把它存储到32位寄存器里。MOVSX是MOV with Sign-Extend的缩写。在把小空间数据转换为大空间数据时,存在填充高位数据的问题;本例中,MOVSX将用原始数据的8位数据填充EDX寄存器的低8位;如果原始数据是负数,该指令将使用1填充第8到第31位(高24位),否则使用0填充高24位。
这是为了保证有符号型数据在类型转换后的数值保持不变。
根据C/C++标准,char类型数据是signed(有符号型)数据。现在设想一下把char型数据转换为int型数据(都是有符号型数据)的情况:假如char型数据的原始值是−2(0xFE),直接把整个字节复制到int型数据的最低8位上时,int型数据的值就变成0x000000FE,以有符号型数据的角度看它被转换为254了,而没有保持原始值−2。−2对应的int型数据是0xFFFFFFFE。所以,在把原始数据复制到目标变量之后,还要使用符号标志位填充剩余的数据,而这就是MOVSX的功能。
本书第30章会更为详细地介绍有符号型数据的表示方法。
虽然不太确定寄存器是否有必要分配EDX寄存器专门保存char型数据,看上去它只使用了寄存器的低8位空间(相当于DL)。显然,编译器根据自身的寄存器分配规则进行了相应分配。
您将在后面看到“TEST EDX,EDX”指令。本书会在第19章详细介绍TEST指令。在本例中,它的功能是检查EDX的值是否是零,并设置相应的标志位。
Non-optimizing GCC
使用GCC 4.4.1(未启用优化选项)编译上述程序,可得到:
public strlen
strlen proc near
eos = dword ptr -4
arg_0 = dword ptr 8
push ebp
mov ebp, esp
sub esp, 10h
mov eax, [ebp+arg_0]
mov [ebp+eos], eax
loc_80483F0:
mov eax, [ebp+eos]
movzx eax, byte ptr [eax]
test al, al
setnz al
add [ebp+eos], 1
test al, al
jnz short loc_80483F0
mov edx, [ebp+eos]
mov eax, [ebp+arg_0]
mov ecx, edx
sub ecx, eax
mov eax, ecx
sub eax, 1
leave
retn
strlen endp
GCC编译的结果和MSVC差不多。这里它没有使用MOVSX指令,而是用了MOVZX指令。MOVZX是MOV with Zero-Extent的缩写。在将8位或16位数据转换为32位数据的时候,它直接复制原始数据到目标寄存器的相应低位,并且使用0填充剩余的高位。拆文解字的角度来看,这条指令相当于一步完成了“xor eax, eax”和“mov al,[源8/16位数据]”2条指令。
另一方面,编译器可以生成“mov al, byte ptr [eax] / test al, al”这样的代码,但是这样一来EAX寄存器的高位将会存在随机的噪声。不如说,这就是编译器的短板所在——在它生成汇编代码的时候,它不会照顾汇编代码的(人类)可读性。严格说来,编译器编译出来的代码本来就是给机器运行的,而不是给人阅读的。
本例还出现了未介绍过的SETNZ指令。从前面一条指令开始解释:如果AL的值不是0,则“test al, al”指令会设置标志寄存器ZF=0;而SETNZ(Not Zero)指令会在ZF=0的时候,设置AL=1。用白话解说,就是:如果AL不等于0,则跳到loc_80483F0处。编译器转译出来的代码中,有些代码确实没有实际意义,这是因为我们没有开启优化选项。
Optimizing MSVC
使用MSVC(启用优化选项/Ox /Ob0)编译上述程序,可得到如下所示的指令。
指令清单15.1 Optimizing MSVC 2012 /Ob0
_str$ = 8 ; size = 4
_strlen PROC
mov edx, DWORD PTR _str$[esp-4] ;用EDX作字符串指针
mov eax, edx ; 复制到 EAX
$LL2@strlen:
mov cl, BYTE PTR [eax] ; CL = *EAX
inc eax ; EAX++
test cl, cl ; CL==0?
jne SHORT $LL2@strlen ; no, continue loop
sub eax, edx ; 计算指针的变化量
dec eax ; decrement EAX
ret 0
_strlen ENDP
优化编译生成的程序短了很多。不必多说,只有在函数较短且局部变量较少的情况下,编译器才会做出这种程度的优化。
inc/dec指令就是递增、递减指令,换句话说它们相当于运算符“++”“−−”。
Optimizing MSVC + OllyDbg
我们使用OllyDbg打开MSVC优化编译后的可执行文件。程序在进行第一次迭代时的情况如图15.1所示。
图15.1 OllyDbg:第一次迭代
OllyDbg识别出了循环结构,并且用方括号把整组循环体指令标示了出来。如需OllyDbg在内存窗口里显示对应的数据,可用右键单击EAX寄存器,然后选择“Follow in Dump”,OllyDbg将自动滚动到对应的地址。在内存数据的显示窗口里,我们可以看到字符串“hello!”。字符串会用数值为零的字节做结尾,在零之后的数据就是随机的噪音数据。如果OllyDbg发现某个寄存器的值是指向这片内存地址(某处)的指针,它就会把对应的字符串提示出来。
然后不停地按F8键,等待循环体进入下一次循环。
如图15.2所示,EAX寄存器的值是个指针,它指向字符串的第二个字符的地址。
图15.2 OllyDbg:第二次迭代
继续按F8键,等待循环语句执行完毕。
如图15.3所示,EAX寄存器里的指针最终指向了数值为零的字符串终止字符。在循环过程中,EDX寄存器的值始终没有发生变化,它一直是字符串首地址的指针。在循环语句结束后,程序即将计算两个指针的差值。
图15.3 OllyDbg:即将计算指针(地址)之间的差值
把这两个寄存器的值(指针)相减,再减去1,就可得到字符串的长度,如图15.4所示。
图15.4 OllyDbg:EAX递减
经计算,指针之间的差值为7。实际上我们的字符串“hello!”只有6个字节,算上结束标志字节才是7个字节。很明显字符串以外的那个数值为零的字节不应当纳入字符串的长度,所以函数最后做了递减运算,把这个字节去掉。
Optimizing GCC
使用GCC 4.4.1编译(启用优化选项“-O3”)上述程序,可得到:
public strlen
strlen proc near
arg_0 = dword ptr 8
push ebp
mov ebp, esp
mov ecx, [ebp+arg_0]
mov eax, ecx
loc_8048418:
movzx edx, byte ptr [eax]
add eax, 1
test dl, dl
jnz short loc_8048418
not ecx
add eax, ecx
pop ebp
retn
strlen endp
GCC编译的结果和MSVC差不多,主要区别体现在MOVZX指令上。
即使把这条MOVZX指令替换为“mov dl, byte ptr [eax]”也没问题。
GCC编译器的代码生成器这样做,或许是为了便于“记住”整个寄存器已经分配给了char型变量,以保证寄存器的高地址位(bits)不会含有噪音数据。
接下来将要介绍的是NOT指令。NOT指令对操作数的所有位(bit)都进行非运算。可以说,这条指令和XOR ECX, 0xffffffffh指令等价。“not ecx”的结果与某数相加,相当于某数减去ECX和1。在程序开始的时候,ECX保存了字符串首个字符的地址(指针),EAX寄存器存储的是终止符的地址。对ECX求非、再与eax相加,就是在计算eax−ecx−1的值。这种运算可以得到正确的字符串长度。
其中的数学问题,请参见第30章。
换句话说,在执行完循环语句之后,函数进行了如下操作:
ecx=str;
eax=eos;
ecx=(-ecx)-1;
eax=eax+ecx
return eax
它得到的结果与下述运算完全相同:
ecx=str;
eax=eos;
eax=eax-ecx;
eax=eax-1;
return eax
GCC编译器这么编译代码的具体原因不明。我们能够确定的是,即使GCC和MSVC分别选择不同的算法,计算的结果肯定相同。
32bit ARM
Non-optimizing Xcode 4.6.3 (LLVM) (ARM mode)
指令清单15.2 Non-optimizing Xcode 4.6.3 (LLVM) (ARM mode)
_strlen
eos =-8
str =-4
SUB SP, SP, #8 ; allocate 8 bytes for local variables
STR R0, [SP,#8+str]
LDR R0, [SP,#8+str]
STR R0, [SP,#8+eos]
loc_2CB8 ; CODE XREF: _strlen+28
LDR R0, [SP,#8+eos]
ADD R1, R0, #1
STR R1, [SP,#8+eos]
LDRSB R0, [R0]
CMP R0, #0
BEQ loc_2CD4
B loc_2CB8
loc_2CD4 ; CODE XREF: _strlen+24
LDR R0, [SP,#8+eos]
LDR R1, [SP,#8+str]
SUB R0, R0, R1 ; R0=eos-str
SUB R0, R0, #1 ; R0=R0-1
ADD SP, SP, #8 ; deallocate 8 bytes
BX LR
如果不指定优化选项,LLVM编译器所生成的代码会很啰唆。但是这种冗长的代码有助于我们理解它处理局部变量所用的栈结构。本例只用到了2个局部变量,即eos和str。
在IDA的反编译结果中,我把变量var_8重命名为原始变量名eos,把var_4重命名为str。
程序的前几条指令把输入值传递给变量str和eos。
循环体的起始地址是loc_2CB8。
循环体内的前3条指令(LDR,ADD,STR)把eos的值保存在R0寄存器里,然后将这个值递增(+1),再把修改后的值直接赋值给栈内的局部变量eos。
接着“LDRSB RO,[R0]” (Load Register Signed Byte)指令从R0所指向的地址处读取1个字节,并将之转换为32位有符号数据(Keil也把Char型数据视为有符号数据)。这条指令类似于x86的MOVSX指令(参见15.1.1节)。既然在C标准里char类型数据是Signed类型数据,编译器就把这个值当作Signed型数据处理。
应当注意的是,虽然x86系统可以把一个32位寄存器拆分为8位寄存器或16位寄存器单独调用,但是ARM系统没有把寄存器拆解出来、分别使用的助记符。确切地说,x86的这种特性是兼容性的要求:为了运行16位8086指令甚至是8位8080指令,它的指令集必须向下兼容。而ARM系统的处理器最初就是32位RISC处理器。所以,在使用ARM系统的寄存器时,只能把它当作完整的32位寄存器使用。
此后,LDRSB指令把字符串中的字符逐字节地传递到R0寄存器。其后的CMP和BEQ指令,会检查这个字节是不是零字节。如果这个字节不是0,则再次进行循环;如果这个字节是0,则结束循环语句。
函数在结束以前计算eos和str的差值,再把这个差值减去1,然后作为函数的返回值、保存在R0寄存器里。
整个函数没有把寄存器推送入栈的操作。按照ARM调用函数的约定,R0~R3寄存器的作用是传递参数的暂存寄存器;函数在退出以后它们已经完成使命了,也不必恢复它们的初始值。在被调用方函数结束之后,再怎么操作它们都行。另外,这个程序没有用到其他的寄存器,也没必要使用栈。所以在函数结束时,唯一需要做的工作就是使用跳转指令(BX)把控制权交给LR寄存器保存的返回地址。
Optimizing Xcode 4.6.3 (LLVM) (Thumb mode)
指令清单15.3 Optimizing Xcode 4.6.3 (LLVM) (Thumb mode)
_strlen
MOV R1, R0
loc_2DF6
LDRB.W R2, [R1],#1
CMP R2, #0
BNE loc_2DF6
MVNS R0, R0
ADD R0, R1
BX LR
在进行优化编译的时候,编译器认为寄存器已经足够用了,不必使用栈来保管变量eos和str。在开始循环之前,编译器使用R0寄存器存储变量str、用R1寄存器存储变量eos。
“LDRB.W R2, [R1],#1”从R1所指向的地址里读取1个字节,将其转换为32位有符号数据(signed)之后存储在R2寄存器里。指令末端的立即数#1将在上述操作之后,把R1寄存器的值加1(递增)。这种指令属于延迟索引寻址(Post-indexed address,又称后变址寻址)指令,便于操作数组。
本书的28.2节会详细介绍延迟索引寻址。
循环体的CMP和BNE指令负责判断循环结束的条件。它们在读取到数值为零的字节之前会保证循环语句处于的迭代状态。
MVNS(MoVe Not)指令相当于x86指令集中的NOT指令,与后面的ADD指令配合完成“eos-str-1”的运算。在15.1.1节里,我们详细介绍过其中的各种细节,这里不再复述。
LLVM编译器与GCC都认为这种代码的效率更高。
Optimizing Keil 6/2013 (ARM mode)
使用Keil(启用优化选项)编译上述程序,可得到如下所示的指令。
指令清单15.4 Optimizing Keil 6/2013 (ARM mode)
_strlen
MOV R1, R0
loc_2C8
LDRB R2, [R1],#1
CMP R2, #0
SUBEQ R0, R1, R0
SUBEQ R0, R0, #1
BNE loc_2C8
BX LR
这段代码与前面的LLVM优化编译生成的Thumb代码相似。区别在于前面的例子在循环结束后才运算str−eos−1,而本例则是在循环体内进行表达式演算。前文介绍过,条件执行指令中的-EQ后缀表示其运行条件为“当前面的CMP比较的两个值相等/EQ时,才会执行该指令”。所以,如果R0寄存器的值是0,则会触发CMP指令之后的两条SUBEQ指令。其运算结果会被保留在R0寄存器,迭代结束之后就自然成为函数的返回值。
ARM64
Optimizing GCC (Linaro) 4.9
my_strlen:
mov x1, x0
; X1 is now temporary pointer (eos), acting like cursor
.L58:
; load byte from X1 to W2, increment X1 (post-index)
ldrb w2, [x1],1
; Compare and Branch if NonZero: compare W2 with 0, jump to .L58 if it is not
cbnz w2, .L58
; calculate difference between initial pointer in X0 and current address in X1
sub x0, x1, x0
; decrement lowest 32-bit of result
sub w0, w0, #1
ret
本例的算法与指令清单15.11的算法相同。它计算首字符和终止符地址的差值,然后再从差里减去1。指令清单中的注释详细介绍了具体的演算方法。不过,我的源程序有问题:my_strlen()的返回值是32位int型数据,但是它应当返回size_t或者另外一种64位数据。理论上讲,在64位平台上,strlen()函数的参数地址可能是4GB以上的内存地址,所以它在64位平台上的返回值应当是64位数据。由于源程序存在这个缺陷,所以最后一条SUB指令只对寄存器的低32位进行操作,但是倒数第二条SUB指令依然是对完整的64位寄存器进行减法运算。虽说程序存在缺陷,但是出于演示的目的,我还是把这个样本保留了下来。
Non-optimizing GCC (Linaro) 4.9
my_strlen:
; function prologue
sub sp, sp, #32
; first argument (str) will be stored in [sp,8]
str x0, [sp,8]
ldr x0, [sp,8]
; copy "str" to "eos" variable
str x0, [sp,24]
nop
.L62:
; eos++
ldr x0, [sp,24] ; load "eos" to X0
add x1, x0, 1 ; increment X0
str x1, [sp,24] ; save X0 to "eos"
; load byte from memory at address in X0 to W0
ldrb w0, [x0]
; is it zero? (WZR is the 32-bit register always contain zero)
cmp w0, wzr
; jump if not zero (Branch Not Equal)
bne .L62
; zero byte found. now calculate difference.
; load "eos" to X1
ldr x1, [sp,24]
; load "str" to X0
ldr x0, [sp,8]
; calculate difference
sub x0, x1, x0
; decrement result
sub w0, w0, #1
; function epilogue
add sp, sp, 32
ret
关闭优化功能之后,编译器生成的代码就长了许多。在操作变量时,程序频繁地访问内存中的栈。此外,由于源程序的设计缺陷,最后一条SUB指令只对寄存器的低32位数据进行了减法运算。
指令清单15.5 Optimizing GCC 4.4.5 (IDA)
my_strlen:
; "eos" variable will always reside in $v1:
move $v1, $a0
loc_4:
; load byte at address in "eos" into $a1:
lb $a1, 0($v1)
or $at, $zero ; load delay slot, NOP
; if loaded byte is not zero, jump to loc_4:
bnez $a1, loc_4
; increment "eos" anyway:
addiu $v1, 1 ; branch delay slot
; loop finished. invert "str" variable:
nor $v0, $zero, $a0
; $v0=-str-1
jr $ra
; return value = $v1 + $v0 = eos + ( -str-1 ) = eos - str - 1
addu $v0, $v1, $v0 ; branch delay slot
MIPS的指令集里没有求非(NOT)运算指令,但是它有非或NOR(即OR+NOT)指令。在数字电路领域,非或运算电路十分普遍;但是在计算机编程领域,它还比较冷门。借助非或运算指令,求非的NOT运算指令可由“NOR DST,$ZERO,SRC”指令变相实现。
前文介绍过,求非运算相当于“求负、再减1”的运算。与后面的ADDU指令配合,可完成“eos−str−1”的运算,求得正确的字符串长度。
请描述下列代码的功能。
指令清单15.6 Optimizing MSVC 2010
_s$ = 8
_f PROC
mov edx, DWORD PTR _s$[esp-4]
mov cl, BYTE PTR [edx]
xor eax, eax
test cl, cl
je SHORT $LN2@f
npad 4 ; align next label
$LL4@f:
cmp cl, 32
jne SHORT $LN3@f
inc eax
$LN3@f:
mov cl, BYTE PTR [edx+1]
inc edx
test cl, cl
jne SHORT $LL4@f
$LN2@f:
ret 0
_f ENDP
指令清单15.7 GCC 4.8.1 -O3
f:
.LFB24:
push ebx
mov ecx, DWORD PTR [esp+8]
xor eax, eax
movzx edx, BYTE PTR [ecx]
test dl, dl
je .L2
.L3:
cmp dl, 32
lea ebx, [eax+1]
cmove eax, ebx
add ecx, 1
movzx edx, BYTE PTR [ecx]
test dl, dl
jne .L3
.L2:
pop ebx
ret
指令清单15.8 Optimizing Keil 6/2013 (ARM mode)
f PROC
MOV r1,#0
|L0.4|
LDRB r2,[r0,#0]
CMP r2,#0
MOVEQ r0,r1
BXEQ lr
CMP r2,#0x20
ADDEQ r1,r1,#1
ADD r0,r0,#1
B |L0.4|
ENDP
指令清单15.9 Optimizing Keil 6/2013 (Thumb mode)
f PROC
MOVS r1,#0
B |L0.12|
|L0.4|
CMP r2,#0x20
BNE |L0.10|
ADDS r1,r1,#1
|L0.10|
ADDS r0,r0,#1
|L0.12|
LDRB r2,[r0,#0]
CMP r2,#0
BNE |L0.4|
MOVS r0,r1
BX lr
ENDP
指令清单15.10 Optimizing GCC 4.9 (ARM64)
f:
ldrb w1, [x0]
cbz w1, .L4
mov w2, 0
.L3:
cmp w1, 32
ldrb w1, [x0,1]!
csinc w2, w2, w2, ne
cbnz w1, .L3
.L2:
mov w0, w2
ret
.L4:
mov w2, w1
b .L2
指令清单15.11 Optimizing GCC 4.4.5 (MIPS) (IDA)
f:
lb $v1, 0($a0)
or $at, $zero
beqz $v1, locret_48
li $a1,0x20#''
b loc_28
move $v0, $zero
loc_18: # CODE XREF: f:loc_28
lb $v1, 0($a0)
or $at, $zero
beqz $v1, locret_40
or $at, $zero
loc_28: # CODE XREF: f+10
# f+38
bne $v1, $a1, loc_18
addiu $a0, 1
lb $v1, 0($a0)
or $at, $zero
bnez $v1, loc_28
addiu $v0, 1
locret_40: # CODE XREF: f+20
jr $ra
or $at, $zero
locret_48: # CODE XREF: f+8
jr $ra
move $v0, $zero