在内存中,数组就是按次序排列的、相同数据类型的一组数据。
#include <stdio.h>
int main()
{
int a[20];
int i;
for (i=0; i<20; i++)
a[i]=i*2;
for (i=0; i<20; i++)
printf ("a[%d]=%d\n", i, a[i]);
return 0;
};
MSVC
使用MSVC 2008编译上述程序可得如下所示的指令。
指令清单18.1 MSVC 2008
_TEXT SEGMENT
_i$ = -84 ; size = 4
_a$ = -80 ; size = 80
_main PROC
push ebp
mov ebp, esp
sub esp, 84 ; 00000054H
mov DWORD PTR _i$[ebp], 0
jmp SHORT $LN6@main
$LN5@main:
mov eax, DWORD PTR _i$[ebp]
add eax, 1
mov DWORD PTR _i$[ebp], eax
$LN6@main:
cmp DWORD PTR _i$[ebp], 20; 00000014H
jge SHORT $LN4@main
mov ecx, DWORD PTR _i$[ebp]
shl ecx, 1
mov edx, DWORD PTR _i$[ebp]
mov DWORD PTR _a$[ebp+edx*4], ecx
jmp SHORT $LN5@main
$LN4@main:
mov DWORD PTR _i$[ebp], 0
jmp SHORT $LN3@main
$LN2@main:
mov eax, DWORD PTR _i$[ebp]
add eax, 1
mov DWORD PTR _i$[ebp], eax
$LN3@main:
cmp DWORD PTR _i$[ebp], 20 ; 00000014H
jge SHORT $LN1@main
mov ecx, DWORD PTR _i$[ebp]
mov edx, DWORD PTR _a$[ebp+ecx*4]
push edx
mov eax, DWORD PTR _i$[ebp]
push eax
push OFFSET $SG2463
call _printf
add esp, 12 ; 0000000cH
jmp SHORT $LN2@main
$LN1@main:
xor eax, eax
mov esp, ebp
pop ebp
ret 0
_main ENDP
这里除去两个循环之外没有非常特别之处。第一个循环填充数据,第二个循环打印数据。“shl ecx, 1”指令所做的运算是ecx=ecx*2,更详细的介绍请参见16.2.1节。
程序为数组申请了80字节的栈空间,以存储20个4字节元素。
现在使用OllyDbg打开这个执行程序。
如图18.1所示,数组中的每个元素都是32位的int型数据,数组每个元素的值都是其索引值的2倍。
图18.1 OllyDbg:填充数组
因为全部数组都存储于栈中,所以我们可以在内存数据窗口里看到整个数组。
GCC
若使用GCC 4.4.1编译上述程序,可得到如下所示的指令。
指令清单18.2 GCC 4.4.1
public main
main proc near ; DATA XREF: _start+17
var_70 = dword ptr -70h
var_6C = dword ptr -6Ch
var_68 = dword ptr -68h
i_2 = dword ptr -54h
i = dword ptr -4
push ebp
mov ebp, esp
and esp, 0FFFFFFF0h
sub esp, 70h
mov [esp+70h+i], 0 ; i=0
jmp short loc_804840A
loc_80483F7:
mov eax, [esp+70h+i]
mov edx, [esp+70h+i]
add edx, edx ; edx=i*2
mov [esp+eax*4+70h+i_2], edx
add [esp+70h+i], 1 ; i++
loc_804840A:
cmp [esp+70h+i], 13h
jle short loc_80483F7
mov [esp+70h+i], 0
jmp short loc_8048441
loc_804841B:
mov eax, [esp+70h+i]
mov edx, [esp+eax*4+70h+i_2]
mov eax, offset aADD ; "a[%d]=%d\n"
mov [esp+70h+var_68], edx
mov edx, [esp+70h+i]
mov [esp+70h+var_6C], edx
mov [esp+70h+var_70], eax
call _printf
add [esp+70h+i], 1
loc_8048441:
cmp [esp+70h+i], 13h
jle short loc_804841B
mov eax, 0
leave
retn
main endp
实际上变量a的数据类型是整型指针。严格地说,在把数组传递给函数的时候,传递的数据就是指向第一个元素的指针,我们再根据这个指针就可以轻松地计算出数组每个元素的地址(即指针)。如果使用a[idx]的形式表示数组元素,其中idx是数组元素在数组里的排列序号(即索引号),那么就可以通过数组第一个元素的地址、索引号和数据容量求得各个元素的地址。
举个典型的例子:字符串常量“string”是字符型数组,它的每个字符元素都是const char*型数据。使用索引号之后,我们就可以使用“string”[i]的形式描述字符串中的第i个字符——这正是C/C++表达式的表示方法!
Non-optimizing Keil 6/2013 (ARM mode)
EXPORT _main
_main
STMFD SP!, {R4,LR}
SUB SP, SP, #0x50 ;分配20个int的存储空间
; first loop
MOV R4, #0 ; i
B loc_4A0
loc_494
MOV R0, R4,LSL#1 ; R0=R4*2
STR R0, [SP,R4,LSL#2] ; store R0 to SP+R4<<2 (same as SP+R4*4)
ADD R4, R4, #1 ; i=i+1
loc_4A0
CMP R4, #20 ; i<20?
BLT loc_494 ;yes? loop again
; second loop
MOV R4, #0 ; i
B loc_4C4
loc_4B0
LDR R2, [SP,R4,LSL#2] ; (printf的第2个参数) R2=*(SP+R4<<4)(等同于*(SP+R4*4))
MOV R1, R4 ; (printf的第1个参数) R1=i
ADR R0, aADD ; "a[%d]=%d\n"
BL __2printf
ADD R4, R4, #1 ; i=i+1
loc_4C4
CMP R4, #20 ; i<20?
BLT loc_4B0 ; yes, run loop body again
MOV R0, #0 ; value to return
ADD SP, SP, #0x50 ; 释放20个int的存储空间
LDMFD SP!, {R4,PC}
单个整型数据占32位(4字节)存储空间。以此类推,要存储20个int型数据就需要80(0x50)个字节的空间。函数尾声的“SUB SP, SP, 0x50”指令释放的空间就是存储数组所用的空间。
在两个循环体内,循环控制变量i都使用R4寄存器。
在填充数组元素的时候,编译器用左移1位的运算“LSL#1”实现乘法运算“i×2”,形成了“MOV R0, R4,LSL#1”指令。
“STR R0,[SP, R4, LSL#2]”实现了把R0寄存器的值写入数组。计算数组元素的原理:因为SP可代表数组的起始地址、R4代表变量i,所以可通过i左移2位求得i×4的相对偏移地址,再计算地址“SP+R4×4”即可推导出数组元素a[i]的指针地址。
在第二个循环里,“LDR R2, [SP,R4,LSL#2]”指令读取a[i]的值。
Optimizing Keil 6/2013 (Thumb mode)
_main
PUSH {R4,R5,LR}
; allocate place for 20 int variables + one more variable
SUB SP, SP, #0x54
;第一个循环
MOV R0,#0 ;i
MOV R5, SP ; pointer to first array element
loc_1CE
LSLS R1, R0, #1 ; R1=i<<1 (same as i*2)
LSLS R2, R0, #2 ; R2=i<<2 (same as i*4)
ADDS R0, R0, #1 ; i=i+1
CMP R0, #20 ; i<20?
STR R1, [R5,R2] ; store R1 to *(R5+R2) (same R5+i*4)
BLT loc_1CE ; yes, i<20, run loop body again
;第二个循环
MOVS R4, #0 ; i=0
loc_1DC
LSLS R0, R4, #2 ; R0=i<<2 (same as i*4)
LDR R2, [R5,R0] ; load from *(R5+R0) (same as R5+i*4)
MOVS R1, R4
ADR R0, aADD ; "a[%d]=%d\n"
BL __2printf
ADDS R4, R4, #1 ; i=i+1
CMP R4, #20 ; i<20?
BLT loc_1DC ; yes, i<20, run loop body again
MOVS R0, #0 ; value to return
; deallocate Chunk, allocated for 20 int variables + one more variable
ADD SP, SP, #0x54
POP {R4,R5,PC}
Thumb模式的程序和ARM模式的程序十分相近。在Thumb模式里,位移操作有特定的对应指令(如LSLS)。上述程序借助Thumb模式的指令计算每个数组元素的地址。
另外,本例分配的栈空间比实际需求大了一些。这个栈里的最后4个字节不会被占用。
Non-optimizing GCC 4.9.1 (ARM64)
指令清单18.3 Non-optimizing GCC 4.9.1 (ARM64)
.LC0:
.string "a[%d]=%d\n"
main:
; save FP and LR in stack frame:
stp x29, x30, [sp, -112]!
; set stack frame (FP=SP)
add x29, sp, 0
; setting initial counter variable at 0 (WZR is the register always holding zero):
str wzr, [x29,108]
; jump to loop condition checking code:
b .L2
.L3:
; load value of "i" variable:
ldr w0, [x29,108]
; multiplicate it by 2:
lsl w2, w0, 1
; find a place of an array in local stack:
add x0, x29, 24
; load 32-bit integer from local stack and sign extend it to 64-bit one:
ldrsw x1, [x29,108]
; calculate address of element (X0+X1<<2=array address+i*4) ; and store W2 (i*2) there:
str w2, [x0,x1,lsl 2]
; increment counter (i):
ldr w0, [x29,108]
add w0, w0, 1
str w0, [x29,108]
.L2:
; check if we finished:
ldr w0, [x29,108]
cmp w0, 19
; jump to L3 (loop body begin) if not:
ble .L3
; second part of the function begins here.
; setting initial counter variable at 0.
; by the way, the same place in the local stack was used for counter,
; because the same local variable (i) is being used as counter.
str wzr, [x29,108]
b .L4
.L5:
; calculate array address:
add x0, x29, 24
; load "i" value:
ldrsw x1, [x29,108]
; load value from the array at the address (X0+X1<<2 = address of array + i*4)
ldr w2, [x0,x1,lsl 2]
; load address of the "a[%d]=%d\n" string:
adrp x0, .LC0
add x0, x0, :lo12:.LC0
; load "i" variable to W1 and pass it to printf() as second argument:
ldr w1, [x29,108]
; W2 still contains the value of array element which was just loaded.
; call printf():
bl printf
; increment "i" variable:
ldr w0, [x29,108]
add w0, w0, 1
str w0, [x29,108]
.L4:
; are we finished?
ldr w0, [x29,108]
cmp w0, 19
; jump to the loop body begin if not:
ble .L5
; return 0
mov w0, 0
; restore FP and LR:
ldp x29, x30, [sp], 112
ret
面向MIPS的编译器会大量使用S-字头寄存器。因为S-字头寄存器不属于临时寄存器,所以函数在序言和尾声部分对这些寄存器的值进行了备份和还原。
指令清单18.4 Optimizing GCC 4.4.5 (IDA)
main:
var_70 = -0x70
var_68 = -0x68
var_14 = -0x14
var_10 = -0x10
var_C = -0xC
var_8 =-8
var_4 =-4
; function prologue:
lui $gp, (__gnu_local_gp >> 16)
addiu $sp, -0x80
la $gp, (__gnu_local_gp & 0xFFFF)
sw $ra, 0x80+var_4($sp)
sw $s3, 0x80+var_8($sp)
sw $s2, 0x80+var_C($sp)
sw $s1, 0x80+var_10($sp)
sw $s0, 0x80+var_14($sp)
sw $gp, 0x80+var_70($sp)
addiu $s1, $sp, 0x80+var_68
move $v1, $s1
move $v0, $zero
; that value will be used as a loop terminator.
; it was precalculated by GCC compiler at compile stage:
li $a0, 0x28 # '('
loc_34: # CODE XREF: main+3C
; store value into memory:
sw $v0, 0($v1)
; increase value to be stored by 2 at each iteration:
addiu $v0, 2
; loop terminator reached?
bne $v0, $a0, loc_34
; add 4 to address anyway:
addiu $v1, 4
; array filling loop is ended
; second loop begin
la $s3, $LC0 # "a[%d]=%d\n"
; "i" variable will reside in $s0:
move $s0, $zero
li $s2, 0x14
loc_54: # CODE XREF: main+70
; call printf():
lw $t9, (printf & 0xFFFF)($gp)
lw $a2, 0($s1)
move $a1, $s0
move $a0, $s3
jalr $t9
; increment "i":
addiu $s0, 1
lw $gp, 0x80+var_70($sp)
; jump to loop body if end is not reached:
bne $s0, $s2, loc_54
; move memory pointer to the next 32-bit word:
addiu $s1, 4
; function epilogue
lw $ra, 0x80+var_4($sp)
move $v0, $zero
lw $s3, 0x80+var_8($sp)
lw $s2, 0x80+var_C($sp)
lw $s1, 0x80+var_10($sp)
lw $s0, 0x80+var_14($sp)
jr $ra
addiu $sp, 0x80
$LC0: .ascii "a[%d]=%d\n"<0> # DATA XREF: main+44
编译器对第一个循环使用了代入的技术对变量之进行了等效处理。在第一个循环的循环体中,数组元素的值($V0的值)是控制变量i的2倍,即i×2,所以在每次迭代后控制变量的增量都是2。另外,数组元素的地址增量为4,编译器单独分配了$V1寄存器给这个指针使用,也令其增量为4。
第二个循环体根据数组索引值i、通过printf()函数依次输出数组元素。编译器首先使用$S0寄存器存储索引值,$S0在每次迭代中的增量为1。与前一个循环体相似,它单独使用$S1寄存器存储内存地址,并使其在迭代间的增量为4。
这便是本书第39章中会提到的循环优化技术。通过这种技术,编译器可尽量避免效率较低的乘法运算。
综上所述,编译器借助索引index、以array[index]的形式表示数组。若仔细审查二进制程序的代码,那么您可能会发现程序并没有对数组进行边界检查、没有判断索引是否在20以内。那么,如果程序访问数组边界以外的数据,又会发生什么情况?C/C++编译器确实不会进行边界检查,这也是它备受争议之处。
编译、并运行下面的程序,会发现整个过程中不会遇到错误提示。
#include <stdio.h>
int main()
{
int a[20];
int i;
for (i=0; i<20; i++)
a[i]=i*2;
printf ("a[20]=%d\n", a[20]);
return 0;
};
使用MSVC 2008编译后可得到如下所示的指令。
指令清单18.5 Non-optimizing MSVC 2008
$SG2474 DB 'a[20]=%d', 0aH, 00H
_i$ = -84 ; size = 4
_a$ = -80 ; size = 80
_main PROC
push ebp
mov ebp, esp
sub esp, 84
mov DWORD PTR _i$[ebp], 0
jmp SHORT $LN3@main
$LN2@main:
mov eax, DWORD PTR _i$[ebp]
add eax, 1
mov DWORD PTR _i$[ebp], eax
$LN3@main:
cmp DWORD PTR _i$[ebp], 20
jge SHORT $LN1@main
mov ecx, DWORD PTR _i$[ebp]
shl ecx, 1
mov edx, DWORD PTR _i$[ebp]
mov DWORD PTR _a$[ebp+edx*4], ecx
jmp SHORT $LN2@main
$LN1@main:
mov eax, DWORD PTR _a$[ebp+80]
push eax
push OFFSET $SG2474 ; 'a[20]=%d'
call DWORD PTR __imp__printf
add esp, 8
xor eax, eax
mov esp, ebp
pop ebp
ret 0
_main ENDP
_TEXT ENDS
END
其执行结果如图18.2所示。
图18.2 OllyDbg:运算结果
这是地址接近栈内数组的数据的值。它的地址距离数组的起始地址有80字节。
让我们通过OllyDbg看看这个数从哪里来。如图18.3所示,使用OllyDbg加载这个程序,找到数组最后一个值之后的数据。
图18.3 OllyDbg:读取数组中的第20个元素、并使用printf()输出
这是什么的值?根据栈结构来判断,这个值是先前保存的EBP寄存器的值。我们继续跟踪这个程序,如图18.4所示,看看它的提取过程。
图18.4 OllyDbg:还原EBP寄存器的值
到底有没有什么办法控制数组的访问边界问题呢?如果需要控制数组边界,就要修改编译器,强制其生成的程序检查索引index是否在边界之内。某些高级编程语言,如Python和Java,就会进行边界检查。但是这种控制会严重影响程序的性能。
既然我们可以“非法地”利用栈来读取数组边界以外的数值,那么我们是否也可以向数组边界以外的地址里写入数据呢?
可通过下面的程序来进行验证。
#include <stdio.h>
int main()
{
int a[20];
int i;
for (i=0; i<30; i++)
a[i]=i;
return 0;
};
MSVC
使用MSVC编译后可得到如下所示的指令。
指令清单18.6 Non-optimizing MSVC 2008
_TEXT SEGMENT
_i$ = -84 ; size = 4
_a$ = -80 ; size = 80
_main PROC
push ebp
mov ebp, esp
sub esp, 84
mov DWORD PTR _i$[ebp], 0
jmp SHORT $LN3@main
$LN2@main:
mov eax, DWORD PTR _i$[ebp]
add eax, 1
mov DWORD PTR _i$[ebp], eax
$LN3@main:
cmp DWORD PTR _i$[ebp], 30 ; 0000001eH
jge SHORT $LN1@main
mov ecx, DWORD PTR _i$[ebp]
mov edx, DWORD PTR _i$[ebp] ; 这条指令用处不大
mov DWORD PTR _a$[ebp+ecx*4], edx; 因为也可以用ECX 取代edx
jmp SHORT $LN2@main
$LN1@main:
xor eax, eax
mov esp, ebp
pop ebp
ret 0
_main ENDP
运行这个可执行程序的时候,程序崩溃了。崩溃并没什么希奇的,但我们要研究一下它是在哪里崩溃的。
使用OllyDbg加载整个程序,等到写满30个元素,如图18.5所示。
图18.5 OllyDbg:恢复EBP的值之后
然后逐步执行程序,等待函数结束,如图18.6所示。
图18.6 OllyDbg:对EIP进行出栈操作,但是OllyDbg找不到0x15处的程序代码
现在,我们再来分析寄存器状态。
现在EIP的值(PC)是0x15。这不是合法的程序地址——至少对于win32系统来说这个值有问题!程序在此处发生异常。同样有趣的是,这时EBP的值是0x14,ECX和EDX的值是0x1D。
我们一起回顾一下栈结构。
待程序进入main()函数之时,程序使用栈来保存EBP寄存器的值。然后程序分配了84个字节,用于存储数组和变量i。计算方法是“(20+1)*sizeof(int)”。栈顶指针ESP现在指向栈内的变量_i,在执行PUSH入栈操作之后它会指向_i的下一个地址。
即,main()函数的栈结构如下:
ESP | i所占用的4字节 |
ESP+4 | a[20]占用的80字节 |
ESP+84 | 保存过的EBP |
ESP+88 | 返回地址 |
赋值给a[19]的时候,数组a[]已经被全部赋值。
赋值给a[20],实际修改的是栈里保存的EBP。
观察程序崩溃时的寄存器状态。本例将数字20(0x14)赋值给a[19]。在函数退出之前,CPU会通过栈恢复EBP的初始值。本例它会收到的值是20(0x14)最后运行RET指令,相当于执行POP EIP指令。
RET指令将程序的控制权传递给栈里的返回地址(该地址为CRT内部调用main()的地址),不过这个RA的值被改为21(0x15)。CPU会寻找0x15处的代码,以继续执行程序。但是那处地址里没有可执行代码,所以程序就崩溃了。
恭喜!您已经了解了缓冲区溢出[1]的精妙之处。
设想一下:用字符串替代int数组,刻意构造个超长字符串,把字符串传递给程序;因为函数不会检查字符串长度,会直接赋值给较短的缓冲区,您就可以强制这个程序跳转到其他程序的地址。纸上谈兵固然简单,但是无论实际情况再怎么复杂,其原理都是一样的。
GCC
使用GCC 4.4.1编译上述程序,可得到:
public main
main proc near
= dword ptr -54h
i = dword ptr -4
push ebp
mov ebp, esp
sub esp, 60h ; 96
mov [ebp+i], 0
jmp short loc_80483D1
loc_80483C3:
mov eax, [ebp+i]
mov edx, [ebp+i]
mov [ebp+eax*4+a], edx
add [ebp+i], 1
loc_80483D1:
cmp [ebp+i], 1Dh
jle short loc_80483C3
mov eax, 0
leave
retn
main endp
在Linux系统里执行这个程序会引发段错误/Segmentation fault。
我们使用GDB Debugger调试它:
(gdb) r
Starting program: /home/dennis/RE/1
Program received signal SIGSEGV, Segmentation fault.
0x00000016 in ?? ()
(gdb) info registers
eax 0x0 0
ecx 0xd2f96388 -755407992
edx 0x1d 29
ebx 0x26eff4 2551796
esp 0xbffff4b0 0xbffff4b0
ebp 0x15 0x15
esi 0x0 0
edi 0x0 0
eip 0x16 0x16
eflags 0x10202 [ IF RF ]
cs 0x73 115
ss 0x7b 123
ds 0x7b 123
es 0x7b 123
fs 0x0 0
gs 0x33 51
(gdb)
因为Linux和Windows的栈结构不完全相同,所以Linux/Win32下寄存器的值也存在细微的差别。
无论C/C++程序员是粗心大意还是严肃认真,我们都可通过编译器的技术手段防止缓冲区溢出。例如,可以启用MSVC的编译器选项[2]:
/RTCs 启用栈帧的实时检查
/GZ 启用栈检测(/RTCs)
另外,还可以在函数启动时构造一些本地变量,在里面写入随机数,在函数结束之前检查这些值是否发生变化。如果这些值发生了变化,就不应当以RET方式结束函数,而是通过其他手段终止(stop/hang)程序。强行关闭应用程序或许确实不怎么体面,但是总比让他人入侵主机要高明。
有人把这种写入的随机值叫作“百灵鸟canary”,这个绰号来自于“矿工的百灵鸟miners’ canary”。所谓“矿工的百灵鸟”,确实是指过去矿工下矿时所带的百灵鸟。矿工使用百灵鸟来快速检测矿道里的毒气。百灵鸟对井下气体十分敏感,它们在遇到不良气体的时候就会表现得烦躁不安,甚至会直接死亡。
如果启用MSVC的RTC1和RTCs选项编译本章开头的那段程序,就会在汇编指令里看到函数在退出之前调用@_RTC_CheckStackVars@8,用以检测“百灵鸟”是否会报警。
还是来看看GCC预防缓冲区溢出的方法吧。我们借用5.2.4节的例子来进行说明:
#ifdef __GNUC__
#include <alloca.h> // GCC
#else
#include <malloc.h> // MSVC
#endif
#include <stdio.h>
void f()
{
char *buf=(char*)alloca (600);
#ifdef __GNUC__
snprintf (buf, 600, "hi! %d, %d, %d\n", 1, 2, 3); // GCC
#else
_snprintf (buf, 600, "hi! %d, %d, %d\n", 1, 2, 3); // MSVC
#endif
puts (buf);
};
即使不指定任何参数,默认情况下GCC 4.7.3也会在代码里加入百灵鸟。
经GCC 4.7.3编译前面的程序可得到如下所示的指令。
指令清单18.7 GCC4.7.3
.LC0:
.string "hi! %d, %d, %d\n"
f:
push ebp
mov ebp, esp
push ebx
sub esp, 676
lea ebx, [esp+39]
and ebx, -16
mov DWORD PTR [esp+20], 3
mov DWORD PTR [esp+16], 2
mov DWORD PTR [esp+12], 1
mov DWORD PTR [esp+8], OFFSET FLAT:.LC0 ; "hi! %d, %d, %d\n"
mov DWORD PTR [esp+4], 600
mov DWORD PTR [esp], ebx
mov eax, DWORD PTR gs:20;
mov DWORD PTR [ebp-12], eax
xor eax, eax
call _snprintf
mov DWORD PTR [esp], ebx
call puts
mov eax, DWORD PTR [ebp-12]
xor eax, DWORD PTR gs:20;
jne .L5
mov ebx, DWORD PTR [ebp-4]
leave
ret
.L5:
call __stack_chk_fail
随机值位于gs:20。在函数启动的时候,程序在栈里写入这个百灵鸟,并且在函数退出之前检测它是否发生了变化、是否与gs:20一致。如果其值发生了变化,将会调用__stack_chk_fail,在Ubuntu 13.04 x86下,我们会在控制台看见下述报错信息:
*** buffer overflow detected ***: ./2_1 terminated
======= Backtrace: =========
/lib/i386-linux-gnu/libc.so.6(__fortify_fail+0x63)[0xb7699bc3]
/lib/i386-linux-gnu/libc.so.6(+0x10593a)[0xb769893a]
/lib/i386-linux-gnu/libc.so.6(+0x105008)[0xb7698008]
/lib/i386-linux-gnu/libc.so.6(_IO_default_xsputn+0x8c)[0xb7606e5c]
/lib/i386-linux-gnu/libc.so.6(_IO_vfprintf+0x165)[0xb75d7a45]
/lib/i386-linux-gnu/libc.so.6(__vsprintf_chk+0xc9)[0xb76980d9]
/lib/i386-linux-gnu/libc.so.6(__sprintf_chk+0x2f)[0xb7697fef]
./2_1[0x8048404]
/lib/i386-linux-gnu/libc.so.6(__libc_start_main+0xf5)[0xb75ac935]
======= Memory map: ========
08048000-08049000 r-xp 00000000 08:01 2097586 /home/dennis/2_1
08049000-0804a000 r--p 00000000 08:01 2097586 /home/dennis/2_1
0804a000-0804b000 rw-p 00001000 08:01 2097586 /home/dennis/2_1
094d1000-094f2000 rw-p 00000000 00:00 0 [heap]
b7560000-b757b000 r-xp 00000000 08:01 1048602 /lib/i386-linux-gnu/libgcc_s.so.1
b757b000-b757c000 r--p 0001a000 08:01 1048602 /lib/i386-linux-gnu/libgcc_s.so.1
b757c000-b757d000 rw-p 0001b000 08:01 1048602 /lib/i386-linux-gnu/libgcc_s.so.1
b7592000-b7593000 rw-p 00000000 00:00 0
b7593000-b7740000 r-xp 00000000 08:01 1050781 /lib/i386-linux-gnu/libc-2.17.so
b7740000-b7742000 r--p 001ad000 08:01 1050781 /lib/i386-linux-gnu/libc-2.17.so
b7742000-b7743000 rw-p 001af000 08:01 1050781 /lib/i386-linux-gnu/libc-2.17.so
b7743000-b7746000 rw-p 00000000 00:00 0
b775a000-b775d000 rw-p 00000000 00:00 0
b775d000-b775e000 r-xp 00000000 00:00 0 [vdso]
b775e000-b777e000 r-xp 00000000 08:01 1050794 /lib/i386-linux-gnu/ld-2.17.so
b777e000-b777f000 r--p 0001f000 08:01 1050794 /lib/i386-linux-gnu/ld-2.17.so
b777f000-b7780000 rw-p 00020000 08:01 1050794 /lib/i386-linux-gnu/ld-2.17.so
bff35000-bff56000 rw-p 00000000 00:00 0 [stack]
Aborted (core dumped)
gs开头的寄存器就是常说的段寄存器。在MS-DOS和基于DOS的系统里,段寄存器的作用很广泛。但是,今天它的作用发生了变化。简单地说,Linux下的gs 寄存器总是指向TLS(参见第65章)——存储线程的多种特定信息。(Win32环境下的fs寄存器起到Linux下gs寄存器的作用。Win32的fs寄存器指向TIB[3])
如需详细了解gs寄存器的作用,请在3.11以上版本的Linux源代码中查阅文件(arch/x86/include/ asm/stackprotector.h)。这个文件的注释详细描述了有关变量的功能。
我们使用LLVM编译本章开头的数组程序,看看它是如何使用百灵鸟的:
_main
var_64 = -0x64
var_60 = -0x60
var_5C = -0x5C
var_58 = -0x58
var_54 = -0x54
var_50 = -0x50
var_4C = -0x4C
var_48 = -0x48
var_44 = -0x44
var_40 = -0x40
var_3C = -0x3C
var_38 = -0x38
var_34 = -0x34
var_30 = -0x30
var_2C = -0x2C
var_28 = -0x28
var_24 = -0x24
var_20 = -0x20
var_1C = -0x1C
var_18 = -0x18
canary = -0x14
var_10 = -0x10
PUSH {R4-R7,LR}
ADD R7, SP, #0xC
STR.W R8, [SP,#0xC+var_10]!
SUB SP, SP, #0x54
MOVW R0, #aObjc_methtype ; "objc_methtype"
MOVS R2, #0
MOVT.W R0, #0
MOVS R5, #0
ADD R0, PC
LDR.W R8, [R0]
LDR.W R0, [R8]
STR R0, [SP,#0x64+canary]
MOVS R0, #2
STR R2, [SP,#0x64+var_64]
STR R0, [SP,#0x64+var_60]
MOVS R0, #4
STR R0, [SP,#0x64+var_5C]
MOVS R0, #6
STR R0, [SP,#0x64+var_58]
MOVS R0, #8
STR R0, [SP,#0x64+var_54]
MOVS R0, #0xA
STR R0, [SP,#0x64+var_50]
MOVS R0, #0xC
STR R0, [SP,#0x64+var_4C]
MOVS R0, #0xE
STR R0, [SP,#0x64+var_48]
MOVS R0, #0x10
STR R0, [SP,#0x64+var_44]
MOVS R0, #0x12
STR R0, [SP,#0x64+var_40]
MOVS R0, #0x14
STR R0, [SP,#0x64+var_3C]
MOVS R0, #0x16
STR R0, [SP,#0x64+var_38]
MOVS R0, #0x18
STR R0, [SP,#0x64+var_34]
MOVS R0, #0x1A
STR R0, [SP,#0x64+var_30]
MOVS R0, #0x1C
STR R0, [SP,#0x64+var_2C]
MOVS R0, #0x1E
STR R0, [SP,#0x64+var_28]
MOVS R0, #0x20
STR R0, [SP,#0x64+var_24]
MOVS R0, #0x22
STR R0, [SP,#0x64+var_20]
MOVS R0, #0x24
STR R0, [SP,#0x64+var_1C]
MOVS R0, #0x26
STR R0, [SP,#0x64+var_18]
MOV R4, 0xFDA ; "a[%d]=%d\n"
MOV R0, SP
ADDS R6, R0, #4
ADD R4, PC
B loc_2F1C
; second loop begin
loc_2F14
ADDS R0, R5, #1
LDR.W R2, [R6, R5, LSL#2]
MOV R5, R0
loc_2F1C
MOV R0, R4
MOV R1, R5
BLX _printf
CMP R5, #0x13
BNE loc_2F14
LDR.W R0, [R8]
LDR R1, [SP,#0x64+canary]
CMP R0, R1
ITTTT EQ ;
MOVEQ R0, #0
ADDEQ SP, SP, #0x54
LDREQ.W R8, [SP+0x64+var_64],#4
POPEQ {R4-R7,PC}
BLX ___stack_chk_fail
这段Thumb-2模式程序最显著的特点就是循环体被逐一展开了。LLVM编译器判定这样的效率较高。另外,ARM模式下这种指令的效率可能更高。本书就不再进行有关验证了。
函数尾声检测了“百灵鸟”的状态。如果栈内的值没被修改(和R8寄存器所指向的值相等),则会执行ITTTT EQ后面的4条指令——令R0为0、运行函数尾声并且退出函数。如果“百灵鸟”发生了变化,程序将跳过ITTTT EQ后面的4条带“-EQ”的指令,转而调用___stack_chk_fail进行异常处理,实际上会终止个程序。
现在我们应该可以理解为什么C/C++编译不了下面的程序了。[4]
void f(int size)
{
int a[size];
...
};
在编译阶段,编译器必须确切地知道需要给数组分配多大的存储空间,它需要事先明确分配局部栈或数据段(全局变量)的格局,所以编译器无法处理上述这种长度可变的数组。
如果无法事先确定数组的长度,那么我们就应当使用malloc()函数分配出一块内存,然后直接按照常规变量数组的方式访问这块内存;或者遵循C99标准(参见ISO07,6.7.5/2)进行处理,但是遵循C99标准而设计出来的程序,内部实现的方法更接近alloca()函数(详情请参阅5.2.4节)。
本节以下述程序为例。
指令清单18.8 查询月份名称
#include <stdio.h>
const char* month1[]=
{
"January",
"February",
"March",
"April",
"May",
"June",
"July",
"August",
"September",
"October",
"November",
"December"
};
// in 0..11 range
const char* get_month1 (int month)
{
return month1[month];
};
指令清单18.9 Optimizing MSVC 2013 x64
_DATA SEGMENT
month1 DQ FLAT:$SG3122
DQ FLAT:$SG3123
DQ FLAT:$SG3124
DQ FLAT:$SG3125
DQ FLAT:$SG3126
DQ FLAT:$SG3127
DQ FLAT:$SG3128
DQ FLAT:$SG3129
DQ FLAT:$SG3130
DQ FLAT:$SG3131
DQ FLAT:$SG3132
DQ FLAT:$SG3133
$SG3122 DB 'January', 00H
$SG3123 DB 'February', 00H
$SG3124 DB 'March', 00H
$SG3125 DB 'April', 00H
$SG3126 DB 'May', 00H
$SG3127 DB 'June', 00H
$SG3128 DB 'July', 00H
$SG3129 DB 'August', 00H
$SG3130 DB 'September', 00H
$SG3156 DB '%s', 0aH, 00H
$SG3131 DB 'October', 00H
$SG3132 DB 'November', 00H
$SG3133 DB 'December', 00H
_DATA ENDS
month$ = 8
get_month1 PROC
movsxd rax, ecx
lea rcx, OFFSET FLAT:month1
mov rax, QWORD PTR [rcx+rax*8]
ret 0
get_month1 ENDP
上述程序的功能如下:
第一条指令MOVSXD把ECX的32位整型数值、连同其符号扩展位(sign-extension)扩展为64位整型数据,再存储于RAX寄存器中。ECX存储的“月份”信息是32位整形数据。因为程序随后还要进行64位运算,所以需要把输入变量转换为64位值。
然后函数把指针表的地址存储于RCX寄存器。
最后,函数的输入变量(month)的值乘以8、再与指针表的地址相加。因为是64位系统的缘故,每个地址(即指针)的数据需要占用64位(即8字节)。所以指针表中的每个元素都占用8字节空间。因此,最终字符串的地址要加上month*8。MOV指令不仅完成了字符串地址的计算,而且还完成了指针表的查询。在输入值为1时,函数将返回字符串“February”的指针地址。
编译器的优化编译结果更为直接。
指令清单18.10 Optimizing GCC 4.9 x64
movsx rdi, edi
mov rax, QWORD PTR month1[0+rdi*8]
ret
使用32位MSVC编译器编译上述程序可得如下所示的指令。
指令清单18.11 Optimizing MSVC 2013 x86
_month$ = 8
_get_month1 PROC
mov eax, DWORD PTR _month$[esp-4]
mov eax, DWORD PTR _month1[eax*4]
ret 0
_get_month1 ENDP
32位程序就不用把输入值转化为64位数据了。此外,32位系统的指针属于4字节数据,所以相关的计算因子变为了4。
ARM in ARM mode
指令清单18.12 Optimizing Keil 6/2013 (ARM mode)
get_month1 PROC
LDR r1,|L0.100|
LDR r0,[r1,r0,LSL #2]
BX lr
ENDP
|L0.100|
DCD ||.data||
DCB "January",0
DCB "February",0
DCB "March",0
DCB "April",0
DCB "May",0
DCB "June",0
DCB "July",0
DCB "August",0
DCB "September",0
DCB "October",0
DCB "November",0
DCB "December",0
AREA ||.data||, DATA, ALIGN=2
month1
DCD ||.conststring||
DCD ||.conststring||+0x8
DCD ||.conststring||+0x11
DCD ||.conststring||+0x17
DCD ||.conststring||+0x1d
DCD ||.conststring||+0x21
DCD ||.conststring||+0x26
DCD ||.conststring||+0x2b
DCD ||.conststring||+0x32
DCD ||.conststring||+0x3c
DCD ||.conststring||+0x44
DCD ||.conststring||+0x4d
数据表的首地址存储于R1寄存器。其余元素的指针地址则通过LDR指令现场计算。实参month在左移2位之后与R1的值(表地址)相加,从而计算出地址表中的指针地址。此后,再用这个指针在32位地址表中进行查询,把最终的字符串地址存储在R0寄存器里。
Thumb模式的ARM程序
由于在Thumb模式里的LDR指令不能进行LSL运算,所以代码略长一些。
get_month1 PROC
LSLS r0,r0,#2
LDR r1,|L0.64|
LDR r0,[r1,r0]
BX lr
ENDP
指令清单18.13 Optimizing GCC 4.9 ARM64
get_month1:
adrp x1, .LANCHOR0
add x1, x1, :lo12:.LANCHOR0
ldr x0, [x1,w0,sxtw 3]
ret
.LANCHOR0 = . + 0
.type month1, %object
.size month1, 96
month1:
.xword .LC2
.xword .LC3
.xword .LC4
.xword .LC5
.xword .LC6
.xword .LC7
.xword .LC8
.xword .LC9
.xword .LC10
.xword .LC11
.xword .LC12
.xword .LC13
.LC2:
.string "January"
.LC3:
.string "February"
.LC4:
.string "March"
.LC5:
.string "April"
.LC6:
.string "May"
.LC7:
.string "June"
.LC8:
.string "July"
.LC9:
.string "August"
.LC10:
.string "September"
.LC11:
.string "October"
.LC12:
.string "November"
.LC13:
.string "December"
表地址由ADRP/ADD指令对传送到X1寄存器。然后,单条LDR指令完成表查询的运算。它把W0寄存器(传递实参month)的值左移3位(相当于乘以8),将其进行有符号数扩展(sxtw后缀的含义)并与X0寄存器的值相加。通过表查询获取的64位运算结果最终存储在X0寄存器里。
指令清单18.14 Optimizing GCC 4.4.5 (IDA)
get_month1:
; load address of table into $v0:
la $v0, month1
; take input value and multiply it by 4:
sll $a0, 2
; sum up address of table and multiplied value:
addu $a0, $v0
; load table element at this address into $v0:
lw $v0, 0($a0)
; return
jr $ra
or $at, $zero ; branch delay slot, NOP
.data # .data.rel.local
.globl month1
month1: .word aJanuary # "January"
.word aFebruary # "February"
.word aMarch # "March"
.word aApril # "April"
.word aMay # "May"
.word aJune # "June"
.word aJuly # "July"
.word aAugust # "August"
.word aSeptember # "September"
.word aOctober # "October"
.word aNovember # "November"
.word aDecember # "December"
.data # .rodata.str1.4
aJanuary: .ascii "January"<0>
aFebruary: .ascii "February"<0>
aMarch: .ascii "March"<0>
aApril: .ascii "April"<0>
aMay: .ascii "May"<0>
aJune: .ascii "June"<0>
aJuly: .ascii "July"<0>
aAugust: .ascii "August"<0>
aSeptember: .ascii "September"<0>
aOctober: .ascii "October"<0>
aNovember: .ascii "November"<0>
aDecember: .ascii "December"<0>
本例参数的取值范围是0~11。如果输入值为12,会发生什么情况?虽然查询表里没有对应的值,但是程序还是会计算、取值并返回结果,只是返回值不可预料。如果其他函数访问这种超越数据边界的地址,那么在读取字符串地址时可能引发程序崩溃。
本文通过MSVC编译器生成一个Win64程序,然后使用IDA打开这个可执行程序,观察编译器的linker组件在数组后面存储了哪些信息:
指令清单18.15 在IDA里观察问题程序
off_140011000 dq offset aJanuary_1 ; DATA XREF: .text:0000000140001003
; "January"
dq offset aFebruary_1 ; "February"
dq offset aMarch_1 ; "March"
dq offset aApril_1 ; "April"
dq offset aMay_1 ; "May"
dq offset aJune_1 ; "June"
dq offset aJuly_1 ; "July"
dq offset aAugust_1 ; "August"
dq offset aSeptember_1 ; "September"
dq offset aOctober_1 ; "October"
dq offset aNovember_1 ; "November"
dq offset aDecember_1 ; "December"
aJanuary_1 db 'January',0 ; DATA XREF: sub_140001020+4
; .data:off_140011000
aFebruary_1 db 'February',0 ; DATA XREF: .data:0000000140011008
align 4
aMarch_1 db 'March',0 ; DATA XREF: .data:0000000140011010
align 4
aApril_1 db 'April',0 ; DATA XREF: .data:0000000140011018
本例的程序很小,所以数据段里的信息以月份名称为主,没有什么其他信息。但是应当注意的是,linker可能在实际生成的程序中安插“任何信息”。
输入值为12时会发生什么情况?程序应当返回数组首地址之后的第13个元素。我们一起来看CPU是如何处理第“13”个元素的那个64位值:
指令清单18.16 Executable file in IDA
off_140011000 dq offset qword_140011060
; DATA XREF: .text:0000000140001003
dq offset aFebruary_1 ; "February"
dq offset aMarch_1 ; "March"
dq offset aApril_1 ; "April"
dq offset aMay_1 ; "May"
dq offset aJune_1 ; "June"
dq offset aJuly_1 ; "July"
dq offset aAugust_1 ; "August"
dq offset aSeptember_1 ; "September"
dq offset aOctober_1 ; "October"
dq offset aNovember_1 ; "November"
dq offset aDecember_1 ; "December"
qword_140011060 dq 797261756E614Ah ; DATA XREF: sub_140001020+4
; .data:off_140011000
aFebruary_1 db 'February',0 ; DATA XREF: .data:0000000140011008
align 4
aMarch_1 db 'March',0 ; DATA XREF: .data:0000000140011010
那个地址的值是0x797261756E614A。假如某个函数以字符串指针的格式访问这个地址,那么整个程序多半会立即崩溃。毕竟这个值不太会是一个有效地址。
数组溢出保护
如果指望调用函数的用户能够保证参数不超出正常的取值范围,那么这个程序员真的算得上是很傻很天真了。在编程领域里,成熟的应用程序应当具备“Fail Early, Fail Loudly”或“Fail-fast”这类的早期错误处理功能。
C/C++ assertions就是处理手段之一。我们可以修改源程序,令其验证输入参数是否在预期范围之内。
指令清单18.17 assert() added
const char* get_month1_checked (int month)
{
assert (month<12);
return month1[month];
};
只要在函数启动的时候调用一个验证参数有效性的assert()函数,那么当输入值在取值区间之外时,程序将进行异常处理。
指令清单18.18 Optimizing MSVC 2013 x64
$SG3143 DB 'm', 00H, 'o', 00H, 'n', 00H, 't', 00H, 'h', 00H, '.', 00H
DB 'c', 00H, 00H, 00H
$SG3144 DB 'm', 00H, 'o', 00H, 'n', 00H, 't', 00H, 'h', 00H, '<', 00H
DB '1', 00H, '2', 00H, 00H, 00H
month$ = 48
get_month1_checked PROC
$LN5:
push rbx
sub rsp, 32
movsxd rbx, ecx
cmp ebx, 12
jl SHORT $LN3@get_month1
lea rdx, OFFSET FLAT:$SG3143
lea rcx, OFFSET FLAT:$SG3144
mov r8d, 29
call _wassert
$LN3@get_month1:
lea rcx, OFFSET FLAT:month1
mov rax, QWORD PTR [rcx+rbx*8]
add rsp, 32
pop rbx
ret 0
get_month1_checked ENDP
严格地说,assert()只能算作宏而不能算作函数。它对条件表达式进行判断,然后把行号信息和文件名信息传递给另外一个函数,并由后者向用户进行提示。
在可执行程序里,我们可以看到以UTF-16格式封装文件名和条件表达式,以及assert()在原文件中的行号(29)。
所有编译器在编译assert宏时的处理机制基本都大同小异。本文仅演示GCC的编译结果。
指令清单18.19 Optimizing GCC 4.9 x64
.LC1:
.string "month.c"
.LC2:
.string "month<12"
get_month1_checked:
cmp edi, 11
jg .L6
movsx rdi, edi
mov rax, QWORD PTR month1[0+rdi*8]
ret
.L6:
push rax
mov ecx, OFFSET FLAT:__PRETTY_FUNCTION__.2423
mov edx, 29
mov esi, OFFSET FLAT:.LC1
mov edi, OFFSET FLAT:.LC2
call __assert_fail
__PRETTY_FUNCTION__.2423:
.string "get_month1_checked"
从中可知,GCC向异常处理函数传递了其调用方函数的函数名称。
这种边界检查其实存在很明显的开销问题。它会降低程序的运行速度——在调用间隔较短的时间敏感函数上使用assert()宏,性能影响会非常大。以MSVC为例,Debug版的MSVC还存在大量的assert(),而最终发行版的MSVC里就不再使用这个宏了。
微软Windows NT内核也有“checked”和“free”两个版本。前一个版本还存在输入值的边界检查,而后面的第二版就不再使用asssert()了。
多维数组和线性数组在本质上是相同的。
计算机内存是连续的线性空间,它可以与一维数组直接对应。在被拆分成多个一维数组之后,多维数组与内栈线性空间同样存在直接对应的存储关系。
举例来说,二维数组a[3][4]可转化为a[12]这样的一个12个元素一维数组,如表18.1所示。
表18.1 使用一维数组表示二维数组
存储地址 |
数组元素 |
---|---|
0 |
[0] [0] |
1 |
[0] [1] |
2 |
[0] [2] |
3 |
[0] [3] |
4 |
[1] [0] |
5 |
[1] [1] |
6 |
[1] [2] |
7 |
[1] [3] |
8 |
[2] [0] |
9 |
[2] [1] |
10 |
[2] [2] |
11 |
[2] [3] |
在内存之中,3×4的二维数组将依次存储为连续的12个元素,如表18.2所示。
表18.2 二维数组在内存中的存储逻辑
0 | 1 | 2 | 3 |
4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 |
在计算上述数组中某个特定元素的内存存储编号时,可以先将二维索引号的第一个索引号乘以4(矩阵宽度),而后加上第二个索引号。这种方式就是C/C++、Python所用的“行优先的顺序”(row-majororder)。所谓行优先,就是先用第一行排满第一个索引号下的所有元素,然后再依次编排其他各行。
相应地,也有“列优先的顺序”(column-major order)。Fortran、Matlab、R语言就使用了这种顺序。这种顺序优先使用列的存储空间。
这两种优先的顺序孰优孰劣?从性能及缓存的角度来看,与数据的存储方案(scheme)和组织方式(data organization)匹配的优先顺序最优。只要相互匹配,那么程序就可以连续访问数据,整体性能就会提高。所以,如果程序以“逐行”的方式访问数据,那么就应当以行优先的顺序组织数组;反之亦然。
本例用char类型数据构造一个二维数组,其中每个数组元素都占用1字节内存。
以行优先的顺序填充数据
下面这个例子将用数字“0~3”填充数组的第二行。
指令清单18.20 逐行填充数据
#include <stdio.h>
char a[3][4];
int main()
{
int x, y;
//清空数组
for (x=0; x<3; x++)
for (y=0; y<4; y++)
a[x][y]=0
//填充第二行
for (y=0; y<4; y++)
a[1][y]=y;
};
图18.7中所示的3个红圈代表3个不同的行。我们可以看到第二行的值是0、1、2、3。
图18.7 OllyDbg:填充数据后的数组
以列优先的顺序填充数据
下列程序将数组的第三列填充为0、1、2。
指令清单18.21 逐列填充数据
#include <stdio.h>
char a[3][4];
int main()
{
int x, y;
// 清空数组
for (x=0; x<3; x++)
for (y=0; y<4; y++)
a[x][y]=0;
//填充第3列
for (x=0; x<3; x++)
a[x][2]=x;
};
图18.8中所示的3个红圈代表3个不同的行。各行的第三列分别是0、1、2。
图18.8 OllyDbg:填充数据之后的数组
以一维数组的方式访问二维数组的方法至少有两种。
#include <stdio.h>
char a[3][4];
char get_by_coordinates1 (char array[3][4], int a, int b)
{
return array[a][b];
};
char get_by_coordinates2 (char *array, int a, int b)
{
// treat input array as one-dimensional
// 4 is array width here
return array[a*4+b];
};
char get_by_coordinates3 (char *array, int a, int b)
{
// treat input array as pointer,
// calculate address, get value at it
// 4 is array width here
return *(array+a*4+b);
};
int main() {
a[2][3]=123;
printf ("%d\n", get_by_coordinates1(a, 2, 3));
printf ("%d\n", get_by_coordinates2(a, 2, 3));
printf ("%d\n", get_by_coordinates3(a, 2, 3));
};
编译并运行上述程序,可观测到数组元素的相应数值。
MSVC 2013的编译方法可圈可点,三个函数的指令完全一致。
指令清单18.22 Optimizing MSVC 2013 x64
array$ = 8
a$ = 16
b$ = 24
get_by_coordinates3 PROC
; RCX=address of array
; RDX=a
; R8=b
movsxd rax, r8d
; EAX=b
movsxd r9, edx
; R9=a
add rax, rcx
; RAX=b+address of array
movzx eax, BYTE PTR [rax+r9*4]
; AL=load byte at address RAX+R9*4=b+address of array+a*4=address of array+a*4+b
ret 0
get_by_coordinates3 ENDP
array$ = 8
a$ = 16
b$ = 24
get_by_coordinates2 PROC
movsxd rax, r8d
movsxd r9, edx
add rax, rcx
movzx eax, BYTE PTR [rax+r9*4]
ret 0
get_by_coordinates2 ENDP
array$ = 8
a$ = 16
b$ = 24
get_by_coordinates1 PROC
movsxd rax, r8d
movsxd r9, edx
add rax, rcx
movzx eax, BYTE PTR [rax+r9*4]
ret 0
get_by_coordinates1 ENDP
GCC 会生成等效的指令,只是各函数的指令略有区别。
指令清单18.23 Optimizing GCC 4.9 x64
; RDI=address of array
; RSI=a
; RDX=b
get_by_coordinates1:
; sign-extend input 32-bit int values "a" and "b" to 64-bit ones
movsx rsi, esi
movsx rdx, edx
lea rax, [rdi+rsi*4]
; RAX=RDI+RSI*4=address of array+a*4
movzx eax, BYTE PTR [rax+rdx]
; AL=load byte at address RAX+RDX=address of array+a*4+b
ret
get_by_coordinates2:
lea eax, [rdx+rsi*4]
; RAX=RDX+RSI*4=b+a*4
cdqe
movzx eax, BYTE PTR [rdi+rax]
; AL=load byte at address RDI+RAX=address of array+b+a*4
ret
get_by_coordinates3:
sal esi, 2
; ESI=a<<2=a*4
; sign-extend input 32-bit int values "a*4" and "b" to 64-bit ones
movsx rdx, edx
movsx rsi, esi
add rdi, rsi
; RDI=RDI+RSI=address of array+a*4
movzx eax, BYTE PTR [rdi+rdx]
; AL=load byte at address RDI+RDX=address of array+a*4+b
ret
多维数组的情况也差不多。
在下面的例子里,我们演示一个由整型数据构成的三维数组,每个整数元素占用4字节内存。
我们来看如下所示的指令。
指令清单18.24 simple example
#include <stdio.h>
int a[10][20][30];
void insert(int x, int y, int z, int value)
{
a[x][y][z]=value;
};
x86
用MSVC 2010 编译后,这个函数对应的汇编代码如下所示。
指令清单18.25 MSVC 2010
_DATA SEGMENT
COMM _a:DWORD:01770H
_DATA ENDS
PUBLIC _insert
_TEXT SEGMENT
_x$ = 8 ; size = 4
_y$=12 ; size = 4
_z$=16 ; size = 4
_value$ = 20 ; size = 4
_insert PROC
push ebp
mov ebp, esp
mov eax, DWORD PTR _x$[ebp]
imul eax, 2400 ; eax=600*4*x
mov ecx, DWORD PTR _y$[ebp]
imul ecx, 120 ; ecx=30*4*y
lea edx, DWORD PTR _a[eax+ecx]; edx=a + 600*4*x + 30*4*y
mov eax, DWORD PTR _z$[ebp]
mov ecx, DWORD PTR _value$[ebp]
mov DWORD PTR [edx+eax*4], ecx; *(edx+z*4)=value
pop ebp
ret 0
_insert ENDP
_TEXT ENDS
中规中矩。对于三维数组(int a[x][y][z];)来说,计算各元素指针地址的公式是:数组元素地址=600×4x + 30×4y + 4z。32位系统里int类型是32位(4字节)数据,所以要每项都要乘以4。
使用GCC 4.4.1编译上述程序可得如下所示的指令。
指令清单18.26 GCC 4.4.1
public insert
insert proc near
x = dword ptr 8
y = dword ptr 0Ch
z = dword ptr 10h
value = dword ptr 14h
push ebp
mov ebp, esp
push ebx
mov ebx, [ebp+x]
mov eax, [ebp+y]
mov ecx, [ebp+z]
lea edx, [eax+eax] ; edx=y*2
mov eax, edx ; eax=y*2
shl eax, 4 ; eax=(y*2)<<4 = y*2*16 = y*32
sub eax, edx ; eax=y*32 - y*2=y*30
imul edx, ebx, 600 ; edx=x*600
add eax, edx ; eax=eax+edx=y*30 + x*600
lea edx, [eax+ecx] ; edx=y*30 + x*600 + z
mov eax, [ebp+value]
mov dword ptr ds:a[edx*4], eax ; *(a+edx*4)=value
pop ebx
pop ebp
retn
insert endp
GCC的处理方法和MSVC不同。在计算30y的时候,GCC没有使用乘法指令。它的计算公式是(y + y) << 4 − (y + y) = (2 y)<< 4 − 2 y = 2×16y − 2 y = 32 y − 2 y = 30 y。可见,GCC组合了加法、位移和减法运算,替代了MSVC采用的乘法运算。GCC算法的运算速度比直接进行乘法运算的速度还要快。
ARM + Non-optimizing Xcode 4.6.3 (LLVM) (Thumb mode)
指令清单18.27 Non-optimizing Xcode 4.6.3 (LLVM) (Thumb mode)
_insert
value = -0x10
z = -0xC
y =-8
x =-4
; allocate place in local stack for 4 values of int type
SUB SP, SP, #0x10
MOV R9, 0xFC2 ; a
ADD R9, PC
LDR.W R9, [R9] ; get pointer to array
STR R0, [SP,#0x10+x]
STR R1, [SP,#0x10+y]
STR R2, [SP,#0x10+z]
STR R3, [SP,#0x10+value]
LDR R0, [SP,#0x10+value]
LDR R1, [SP,#0x10+z]
LDR R2, [SP,#0x10+y]
LDR R3, [SP,#0x10+x]
MOV R12, 2400
MUL.W R3, R3, R12
ADD R3, R9
MOV R9, 120
MUL.W R2, R2, R9
ADD R2, R3
LSLS R1, R1, #2 ; R1=R1<<2
ADD R1, R2
STR R0, [R1] ; R1 - address of array element
; deallocate place in local stack, allocated for 4 values of int type
ADD SP, SP, #0x10
BX LR
在不启用优化选项的情况下,LLVM使用栈保存所有变量。当然这样的程序运行效率不怎么好。在数组方面,计算各元素的内存地址的方法和前文相同。
ARM + Optimizing Xcode 4.6.3 (LLVM) + Thumb mode
启用优化选项后,使用LLVM以Thumb模式编译上述程序可得到如下所示的指令。
指令清单18.28 Optimizing Xcode 4.6.3 (LLVM) (Thumb mode)
_insert
MOVW R9, #0x10FC
MOV.W R12, #2400
MOVT.W R9, #0
RSB.W R1,R1,R1,LSL#4 ;R1-y.R1=y<<4-y=y*16-y=y*15
ADD R9, PC
LDR.W R9, [R9] ; R9 = pointer to a array
MLA.W R0, R0, R12, R9 ; R0 - x, R12 - 2400, R9 - pointer to a. R0=x*2400 + ptr to a
ADD.W R0, R0, R1,LSL#3 ; R0 = R0+R1<<3 = R0+R1*8 = x*2400 + ptr to a + y*15*8 =
; ptr to a + y*30*4 + x*600*4
STR.W R3, [R0,R2,LSL#2] ; R2 - z, R3 - value. address=R0+z*4 =
BX LR ; ptr to a + y*30*4 + x*600*4 + z*4
LLVM也用到了GCC的地址计算方法,组合了加法、位移、减法三种运算。
其中的“RSB(Reverse Subtract)”指令尚未在前面介绍过。RSB 指令称为逆向减法指令,用于把操作数2(第三个参数)减去操作数1(第二个参数),并将结果存放到目的寄存器中。为什么专门从SUB指令里派生出RSB指令呢?这是因为SUB和RSB都只能对第二个操作数进行位移运算。如果要使用SUB指令,则LSL#4就要写在第1个操作数后面,会造成识别上的混乱。而RSB指令替换了减数和被减数的位置,从而避免了这个问题。
“LDR.W R9, [R9]”指令和x86的LEA指令相似。只是这里的这条指令不影响计算结果,所以是冗余代码。很明显,编译器没有进行相应优化。
MIPS
因为源程序很小的缘故,GCC以全局指针GP在64KB可寻址空间进行表查询。
指令清单18.29 Optimizing GCC 4.4.5 (IDA)
insert:
; $a0=x
; $a1=y
; $a2=z
; $a3=value
sll $v0, $a0, 5
; $v0 = $a0<<5 = x*32
sll $a0, 3
; $a0 = $a0<<3 = x*8
addu $a0, $v0
; $a0 = $a0+$v0 = x*8+x*32 = x*40
sll $v1, $a1, 5
; $v1 = $a1<<5 = y*32
sll $v0, $a0, 4
; $v0 = $a0<<4 = x*40*16 = x*640
sll $a1, 1
; $a1 = $a1<<1 = y*2
subu $a1, $v1, $a1
; $a1 = $v1-$a1 = y*32-y*2 = y*30
subu $a0, $v0, $a0
; $a0 = $v0-$a0 = x*640-x*40 = x*600
la $gp, __gnu_local_gp
addu $a0, $a1, $a0
; $a0 = $a1+$a0 = y*30+x*600
addu $a0, $a2
; $a0 = $a0+$a2 = y*30+x*600+z
; load address of table:
lw $v0, (a & 0xFFFF)($gp)
; multiply index by 4 to seek array element:
sll $a0, 2
; sum up multiplied index and table address:
addu $a0, $v0, $a0
; store value into table and return:
jr $ra
sw $a3, 0($a0)
.comm a:0x1770
计算机的显示屏幕是一个2D显示空间,但是显存却是一个一维线性数组。
本书第83章将详细介绍有关内容。
在指令清单18.8所示的程序里,如果要制备指向月份名称的指针,就必须要进行一次以上的内存操作。有没有可能略去这步内存加载的内存操作?只要把二维数组进行相应处理,即可省略有关操作。
#include <stdio.h>
#include <assert.h>
const char month2[12][10]=
{
{ 'J','a','n','u','a','r','y', 0, 0, 0 },
{ 'F','e','b','r','u','a','r','y', 0, 0 },
{ 'M','a','r','c','h', 0, 0, 0, 0, 0 },
{ 'A','p','r','i','l', 0, 0, 0, 0, 0 },
{ 'M','a','y', 0, 0, 0, 0, 0, 0, 0 },
{ 'J','u','n','e', 0, 0, 0, 0, 0, 0 },
{ 'J','u','l','y', 0, 0, 0, 0, 0, 0 },
{ 'A','u','g','u','s','t', 0, 0, 0, 0 },
{ 'S','e','p','t','e','m','b','e','r', 0 },
{ 'O','c','t','o','b','e','r', 0, 0, 0 },
{ 'N','o','v','e','m','b','e','r', 0, 0 },
{ 'D','e','c','e','m','b','e','r', 0, 0 }
};
// in 0..11 range
const char* get_month2 (int month)
{
return &month2[month][0];
};
编译上述程序可得如下所示的指令。
指令清单18.30 Optimizing MSVC 2013 x64
month2 DB 04aH
DB 061H
DB 06eH
DB 075H
DB 061H
DB 072H
DB 079H
DB 00H
DB 00H
DB 00H
...
get_month2 PROC
; sign-extend input argument and promote to 64-bit value
movsxd rax, ecx
lea rcx, QWORD PTR [rax+rax*4]
; RCX=month+month*4=month*5
lea rax, OFFSET FLAT:month2
; RAX=pointer to table
lea rax, QWORD PTR [rax+rcx*2]
; RAX=pointer to table + RCX*2=pointer to table + month*5*2=pointer to table + month*10
ret 0
get_month2 ENDP
上述程序完全不访问内存。整个函数的功能,只是计算月份名称字符串的首字母指针pointer_to_the_table+month*10。它使用单条LEA指令,替代了多条MUL和MOV指令。
上述数组的每个字符串都占用10字节空间。最长的字符串由“September”和内容为零的字节构成,其余的字符串使用零字节对齐,所以每个字符串都占用10个字节。如此一来,计算字符串首地址的方式变得简单,整个函数的效率也会有所提高。
使用GCC 4.9进行优化编译,程序的指令甚至会更少。
指令清单18.31 Optimizing GCC 4.9 x64
movsx rdi, edi
lea rax, [rdi+rdi*4]
lea rax, month2[rax+rax]
ret
它同样使用LEA指令进行“乘以10”的运算。
若由GCC进行非优化编译,那么乘法运算的实现方式将会有所不同。
指令清单18.32 Non-optimizing GCC 4.9 x64
get_month2:
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-4], edi
mov eax, DWORD PTR [rbp-4]
movsx rdx, eax
; RDX = sign-extended input value
mov rax, rdx
; RAX = month
sal rax, 2
; RAX = month<<2 = month*4
add rax, rdx
; RAX = RAX+RDX = month*4+month = month*5
add rax, rax
; RAX = RAX*2 = month*5*2 = month*10
add rax, OFFSET FLAT:month2
; RAX = month*10 + pointer to the table
pop rbp
ret
而在不开启优化选项的情况下,MSVC编译器会直接使用IMUL指令。
指令清单18.33 Non-optimizing MSVC 2013 x64
month$ = 8
get_month2 PROC
mov DWORD PTR [rsp+8], ecx
movsxd rax, DWORD PTR month$[rsp]
; RAX = sign-extended input value into 64-bit one
imul rax, rax, 10
; RAX = RAX*10
lea rcx, OFFSET FLAT:month2
; RCX = pointer to the table
add rcx, rax
; RCX = RCX+RAX = pointer to the table+month*10
mov rax, rcx
; RAX = pointer to the table+month*10
mov ecx, 1
; RCX = 1
imul rcx, rcx, 0
; RCX = 1*0 = 0
add rax, rcx
; RAX = pointer to the table+month*10 + 0 = pointer to the table+month*10
ret 0
get_month2 ENDP
不过此处有些令人费解:为什么RCX要乘以零,再把零加在最终结果里?虽然说它不影响最终运行结果,但是也足以说是编译器的某种怪癖了。本文刻意演示这种怪癖代码,是希望读者不要拘泥于编译器生成的指令的形式,而要从编程人员的角度理解程序的源代码。
由Keil优化编译而生成的Thumb模式程序,会直接使用乘法运算指令MULS。
指令清单18.34 Optimizing Keil 6/2013 (Thumb mode)
; R0 = month
MOVS r1,#0xa
; R1 = 10
MULS r0,r1,r0
; R0 = R1*R0 = 10*month
LDR r1,|L0.68|
; R1 = pointer to the table
ADDS r0,r0,r1
; R0 = R0+R1 = 10*month + pointer to the table
BX lr
而优化编译生成的ARM模式程序,会使用加法运算和位移操作指令。
指令清单18.35 Optimizing Keil 6/2013 (ARM mode)
; R0 = month
LDR r1,|L0.104|
; R1 = pointer to the table
ADD r0,r0,r0,LSL #2
; R0 = R0+R0<<2 = R0+R0*4 = month*5
ADD r0,r1,r0,LSL #1
; R0 = R1+R0<<2 = pointer to the table + month*5*2 = pointer to the table + month*10
BX lr
指令清单18.36 Optimizing GCC 4.9 ARM64
; W0 = month
sxtw x0, w0
; X0 = sign-extended input value
adrp x1, .LANCHOR1
add x1, x1, :lo12:.LANCHOR1
; X1 = pointer to the table
add x0, x0, x0, lsl 2
; X0 = X0+X0<<2 = X0+X0*4 = X0*5
add x0, x1, x0, lsl 1
; X0 = X1+X0<<1 = X1+X0*2 = pointer to the table + X0*10
ret
SXTW指令把32位有符号数据扩展为64位有符号数据,并将之存储于X0寄存器。ADRP/ADD指令对则负责数组寻址。ADD指令中的LSL后缀用于进行乘法运算。
指令清单18.37 Optimizing GCC 4.4.5 (IDA)
.globl get_month2
get_month2:
; $a0=month
sll $v0, $a0, 3
; $v0 = $a0<<3 = month*8
sll $a0, 1
; $a0 = $a0<<1 = month*2
addu $a0, $v0
; $a0 = month*2+month*8 = month*10
; load address of the table:
la $v0, month2
; sum up table address and index we calculated and return:
jr $ra
addu $v0, $a0
month2: .ascii "January"<0>
.byte 0, 0
aFebruary: .ascii "February"<0>
.byte 0
aMarch: .ascii "March"<0>
.byte 0, 0, 0, 0
aApril: .ascii "April"<0>
.byte 0, 0, 0, 0
aMay: .ascii "May"<0>
.byte 0, 0, 0, 0, 0, 0
aJune: .ascii "June"<0>
.byte 0, 0, 0, 0, 0
aJuly: .ascii "July"<0>
.byte 0, 0, 0, 0, 0
aAugust: .ascii "August"<0>
.byte 0, 0, 0
aSeptember: .ascii "September"<0>
aOctober: .ascii "October"<0>
.byte 0, 0
aNovember: .ascii "November"<0>
.byte 0
aDecember: .ascii "December"<0>
.byte 0, 0, 0, 0, 0, 0, 0, 0, 0
字符串存储技术属于经典的数组技术。Oracle RDBMS的程序中就大量使用了这种技术。虽然当代计算机程序中可能很少应用这种数组技术了,但是字符串型数据可充分演示数组的各方面特点。
在内存中,数组就是依次排列的一组同类型数据。数组元素可以是任意类型的数据,甚至可以是结构体型的数据。如果要访问数组中的特定元素,首先就要计算其地址。
请描述下述代码的功能。
指令清单18.38 MSVC 2010+/O1
_a$ = 8 ; size = 4
_b$ = 12 ; size = 4
_c$ = 16 ; size = 4
?s@@YAXPAN00@Z PROC; s, COMDAT
mov eax, DWORD PTR _b$[esp-4]
mov ecx, DWORD PTR _a$[esp-4]
mov edx, DWORD PTR _c$[esp-4]
push esi
push edi
sub ecx, eax
sub edx, eax
mov edi, 200 ; 000000c8H
$LL6@s:
push 100 ; 00000064H
pop esi
$LL3@s:
fld QWORD PTR [ecx+eax]
fadd QWORD PTR [eax]
fstp QWORD PTR [edx+eax]
add eax, 8
dec esi
jne SHORT $LL3@s
dec edi
jne SHORT $LL6@s
pop edi
pop esi
ret 0
?s@@YAXPAN00@Z ENDP ; s
/O1 代表minimize space,即生成最小长度的程序。
通过Keil 5.03 (启用优化选项-O3)编译而得的ARM模式代码如下所示。
指令清单18.39 Optimizing Keil 6/2013 (ARM mode)
PUSH {r4-r12,lr}
MOV r9,r2
MOV r10,r1
MOV r11,r0
MOV r5,#0
|L0.20|
ADD r0,r5,r5,LSL #3
ADD r0,r0,r5,LSL #4
MOV r4,#0
ADD r8,r10,r0,LSL #5
ADD r7,r11,r0,LSL #5
ADD r6,r9,r0,LSL #5
|L0.44|
ADD r0,r8,r4,LSL #3
LDM r0,{r2,r3}
ADD r1,r7,r4,LSL #3
LDM r1,{r0,r1}
BL __aeabi_dadd
ADD r2,r6,r4,LSL #3
ADD r4,r4,#1
STM r2,{r0,r1}
CMP r4,#0x64
BLT |L0.44|
ADD r5,r5,#1
CMP r5,#0xc8
BLT |L0.20|
POP {r4-r12,pc}
指令清单18.40 Optimizing Keil 6/2013 (Thumb mode)
PUSH {r0-r2,r4-r7,lr}
MOVS r4, #0
SUB sp, sp, #8
|L0.6|
MOVS r1,#0x19
MOVS r0,r4
LSLS r1,r1,#5
MULS r0,r1,r0
LDR r2,[sp,#8]
LDR r1,[sp,#0xc]
ADDS r2,r0,r2
STR r2,[sp,#0]
LDR r2,[sp,#0x10]
MOVS r5,#0
ADDS r7,r0,r2
ADDS r0,r0,r1
STR r0,[sp,#4]
|L0.32|
LSLS r6,r5,#3
ADDS r0,r0,r6
LDM r0!,{r2,r3}
LDR r0,[sp,#0]
ADDS r1,r0,r6
LDM r1,{r0,r1}
BL __aeabi_dadd
ADDS r2,r7,r6
ADDS r5,r5,#1
STM r2!,{r0,r1}
CMP r5,#0x64
BGE |L0.62|
LDR r0,[sp,#4]
B |L0.32|
|L0.62|
ADDS r4,r4,#1
CMP r4,#0xc8
BLT |L0.6|
ADD sp,sp,#0x14
POP {r4-r7,pc}
指令清单18.41 Non-optimizing GCC 4.9 (ARM64)
s:
sub sp, sp, #48
str x0, [sp,24]
str x1, [sp,16]
str x2, [sp,8]
str wzr, [sp,44]
b .L2
.L5:
str wzr, [sp,40]
b .L3
.L4:
ldr w1, [sp,44]
mov w0, 100
mul w0, w1, w0
sxtw x1, w0
ldrsw x0, [sp,40]
add x0, x1, x0
lsl x0, x0, 3
ldr x1, [sp,8]
add x0, x1, x0
ldr w2, [sp,44]
mov w1, 100
mul w1, w2, w1
sxtw x2, w1
ldrsw x1, [sp,40]
add x1, x2, x1
lsl x1, x1, 3
ldr x2, [sp,24]
add x1, x2, x1
ldr x2, [x1]
ldr w3, [sp,44]
mov w1, 100
mul w1, w3, w1
sxtw x3, w1
ldrsw x1, [sp,40]
add x1, x3, x1
lsl x1, x1, 3
ldr x3, [sp,16]
add x1, x3, x1
ldr x1, [x1]
fmov d0, x2
fmov d1, x1
fadd d0, d0, d1
fmov x1, d0
str x1, [x0]
ldr w0, [sp,40]
add w0, w0, 1
str w0, [sp,40]
.L3:
ldr w0, [sp, 40]
cmp w0, 99
ble .L4
ldr w0, [sp,44]
add w0, w0, 1
str w0, [sp,44]
.L2:
ldr w0, [sp,44]
cmp w0, 199
ble .L5
add sp, sp, 48
ret
指令清单18.42 Optimizing GCC 4.4.5 (MIPS) (IDA)
sub_0:
li $t3, 0x27100
move $t2, $zero
li $t1, 0x64 # 'd'
loc_10: # CODE XREF: sub_0+54
addu $t0, $a1, $t2
addu $a3, $a2, $t2
move $v1, $a0
move $v0, $zero
loc_20: # CODE XREF: sub_0+48
lwc1 $f2, 4($v1)
lwc1 $f0, 4($t0)
lwc1 $f3, 0($v1)
lwc1 $f1, 0($t0)
addiu $v0, 1
add.d $f0, $f2, $f0
addiu $v1, 8
swc1 $f0, 4($a3)
swc1 $f1, 0($a3)
addiu $t0, 8
bne $v0, $t1, loc_20
addiu $a3, 8
addiu $t2, 0x320
bne $t2, $t3, loc_10
addiu $a0, 0x320
jr $ra
or $at, $zero
请描述下述程序的功能。
通过MSVC 2010 (启用 /O1选项)编译而得的代码如下所示。
指令清单18.43 MSVC 2010 + /O1
tv315 = -8 ; size = 4
tv291 = -4 ; size = 4
_a$ = 8 ; size = 4
_b$ = 12 ; size = 4
_c$ = 16 ; size = 4
?m@@YAXPAN00@Z PROC; m, COMDAT
push ebp
mov ebp, esp
push ecx
push ecx
mov edx, DWORD PTR _a$[ebp]
push ebx
mov ebx, DWORD PTR _c$[ebp]
push esi
mov esi, DWORD PTR _b$[ebp]
sub edx, esi
push edi
sub esi, ebx
mov DWORD PTR tv315[ebp], 100 ; 00000064H
$LL9@m:
mov eax, ebx
mov DWORD PTR tv291[ebp], 300 ; 0000012cH
$LL6@m:
fldz
lea ecx, DWORD PTR [esi+eax]
fstp QWORD PTR [eax]
mov edi, 200 ; 000000c8H
$LL3@m:
dec edi
fld QWORD PTR [ecx+edx]
fmul QWORD PTR [ecx]
fadd QWORD PTR [eax]
fstp QWORD PTR [eax]
jne HORT $LL3@m
add eax, 8
dec DWORD PTR tv291[ebp]
jne SHORT $LL6@m
add ebx, 800 ; 00000320H
dec DWORD PTR tv315[ebp]
jne SHORT $LL9@m
pop edi
pop esi
pop ebx
leave
ret 0
?m@@YAXPAN00@Z ENDP ; m
指令清单18.44 Optimizing Keil 6/2013 (ARM mode)
PUSH {r0-r2,r4-r11,lr}
SUB sp,sp,#8
MOV r5,#0
|L0.12|
LDR r1,[sp,#0xc]
ADD r0,r5,r5,LSL #3
ADD r0,r0,r5,LSL #4
ADD r1,r1,r0,LSL #5
STR r1,[sp,#0]
LDR r1,[sp,#8]
MOV r4,#0
ADD r11,r1,r0,LSL #5
LDR r1,[sp,#0x10]
ADD r10,r1,r0,LSL #5
|L0.52|
MOV r0,#0
MOV r1,r0
ADD r7,r10,r4,LSL #3
STM r7,{r0,r1}
MOV r6,r0
LDR r0,[sp,#0]
ADD r8,r11,r4,LSL #3
ADD r9,r0,r4,LSL #3
|L0.84|
LDM r9,{r2,r3}
LDM r8,{r0,r1}
BL __aeabi_dmul
LDM r7,{r2,r3}
BL __aeabi_dadd
ADD r6,r6,#1
STM r7,{r0,r1}
CMP r6,#0xc8
BLT |L0.84|
ADD r4,r4,#1
CMP r4,#0x12c
BLT |L0.52|
ADD r5,r5,#1
CMP r5,#0x64
BLT |L0.12|
ADD sp,sp,#0x14
POP {r4-r11,pc}
指令清单18.45 Optimizing Keil 6/2013 (Thumb mode)
PUSH {r0-r2,r4-r7,lr}
MOVS r0,#0
SUB sp,sp,#0x10
STR r0,[sp,#0]
|L0.8|
MOVS r1,#0x19
LSLS r1,r1,#5
MULS r0,r1,r0
LDR r2,[sp,#0x10]
LDR r1,[sp,#0x14]
ADDS r2,r0,r2
STR r2,[sp,#4]
LDR r2,[sp,#0x18]
MOVS r5,#0
ADDS r7,r0,r2
ADDS r0,r0,r
STR r0,[sp,#8]
|L0.32|
LSLS r4,r5,#3
MOVS r0,#0
ADDS r2,r7,r4
STR r0,[r2,#0]
MOVS r6,r0
STR r0,[r2,#4]
|L0.44|
LDR r0,[sp,#8]
ADDS r0,r0,r4
LDM r0!,{r2,r3}
LDR r0,[sp,#4]
ADDS r1,r0,r4
LDM r1,{r0,r1}
BL __aeabi_dmul
ADDS r3,r7,r4
LDM r3,{r2,r3}
BL __aeabi_dadd
ADDS r2,r7,r4
ADDS r6,r6,#1
STM r2!,{r0,r1}
CMP r6,#0xc8
BLT |L0.44|
MOVS r0,#0xff
ADDS r5,r5,#1
ADDS r0,r0,#0x2d
CMP r5,r0
BLT |L0.32|
LDR r0,[sp,#0]
ADDS r0,r0,#1
CMP r0,#0x64
STR r0,[sp,#0]
BLT |L0.8|
ADD sp,sp,#0x1c
POP {r4-r7,pc}
指令清单18.46 Non-optimizing GCC 4.9 (ARM64)
m:
sub sp, sp, #48
str x0, [sp,24]
str x1, [sp,16]
str x2, [sp,8]
str wzr, [sp,44]
b .L2
.L7:
str wzr, [sp,40]
b .L3
.L6:
ldr w1, [sp,44]
mov w0, 100
mul w0, w1, w0
sxtw x1, w0
ldrsw x0, [sp,40]
add x0, x1, x0
lsl x0, x0, 3
ldr x1, [sp,8]
add x0, x1, x0
ldr x1, .LC0
str x1, [x0]
str wzr, [sp,36]
b .L4
.L5:
ldr w1, [sp,44]
mov w0, 100
mul w0, w1, w0
sxtw x1, w0
ldrsw x0, [sp,40]
add x0, x1, x0
lsl x0, x0, 3
ldr x1, [sp,8]
add x0, x1, x0
ldr w2, [sp,44]
mov w1, 100
mul w1, w2, w1
sxtw x2, w1
ldrsw x1, [sp,40]
add x1, x2, x1
lsl x1, x1, 3
ldr x2, [sp,8]
add x1, x2, x1
ldr x2, [x1]
ldr w3, [sp,44]
mov w1, 100
mul w1, w3, w1
sxtw x3, w1
ldrsw x1, [sp,40]
add x1, x3, x1
lsl x1, x1, 3
ldr x3, [sp,24]
add x1, x3, x1
ldr x3, [x1]
ldr w4, [sp,44]
mov w1, 100
mul w1, w4, w1
sxtw x4, w1
ldrsw x1, [sp,40]
add x1, x4, x1
lsl x1, x1, 3
ldr x4, [sp,16]
add x1, x4, x1
ldr x1, [x1]
fmov d0, x3
fmov d1, x1
fmul d0, d0, d1
fmov x1, d0
fmov d0, x2
fmov d1, x1
fadd d0, d0, d1
fmov x1, d0
str x1, [x0]
ldr w0, [sp,36]
add w0, w0, 1
str w0, [sp,36]
.L4:
ldr w0, [sp, 36]
cmp w0, 199
ble .L5
ldr w0, [sp,40]
add w0, w0, 1
str w0, [sp,40]
.L3:
ldr w0, [sp,40]
cmp w0, 299
ble .L6
ldr w0, [sp,44]
add w0, w0, 1
str w0, [sp,44]
.L2:
ldr w0, [sp,44]
cmp w0, 99
ble .L7
add sp, sp, 48
ret
指令清单18.47 Optimizing GCC 4.4.5 (MIPS) (IDA)
m:
li $t5, 0x13880
move $t4, $zero
li $t1, 0xC8
li $t3, 0x12C
loc_14: # CODE XREF: m+7C
addu $t0, $a0, $t4
addu $a3, $a1, $t4
move $v1, $a2
move $t2, $zero
loc_24: # CODE XREF: m+70
mtc1 $zero, $f0
move $v0, $zero
mtc1 $zero, $f1
or $at, $zero
swc1 $f0, 4($v1)
swc1 $f1, 0($v1)
loc_3C: # CODE XREF: m+5C
lwc1 $f4, 4($t0)
lwc1 $f2, 4($a3)
lwc1 $f5, 0($t0)
lwc1 $f3, 0($a3)
addiu $v0, 1
mul.d $f2, $f4, $f2
add.d $f0, $f2
swc1 $f0, 4($v1)
bne $v0, $t1, loc_3C
swc1 $f1, 0($v1)
addiu $t2, 1
addiu $v1, 8
addiu $t0, 8
bne $t2, $t3, loc_24
addiu $a3, 8
addiu $t4, 0x320
bne $t4, $t5, loc_14
addiu $a2, 0x320
jr $ra
or $at, $zero
请描述下列代码的作用。
通过MSVC 2010(启用/Ox选项)编译而得的代码如下所示。
指令清单18.48 Optimizing MSVC 2010
_array$ = 8
_x$ = 12
_y$ = 16
_f PROC
mov eax, DWORD PTR _x$[esp-4]
mov edx, DWORD PTR _y$[esp-4]
mov ecx, eax
shl ecx, 4
sub ecx, eax
lea eax, DWORD PTR [edx+ecx*8]
mov ecx, DWORD PTR _array$[esp-4]
fld QWORD PTR [ecx+eax*8]
ret 0
_f ENDP
指令清单18.49 Non-optimizing Keil 6/2013 (ARM mode)
f PROC
RSB r1,r1,r1,LSL #4
ADD r0,r0,r1,LSL #6
ADD r1,r0,r2,LSL #3
LDM r1,{r0,r1}
BX lr
ENDP
指令清单18.50 Non-optimizing Keil 6/2013 (Thumb mode)
f PROC
MOVS r3,#0xf
LSLS r3,r3,#6
MULS r1,r3,r1
ADDS r0,r1,r0
LSLS r1,r2,#3
ADDS r1,r0,r1
LDM r1,{r0,r1}
BX lr
ENDP
指令清单18.51 Optimizing GCC 4.9 (ARM64)
f:
sxtw x1, w1
add x0, x0, x2, sxtw 3
lsl x2, x1, 10
sub x1, x2, x1, lsl 6
ldr d0, [x0,x1]
ret
指令清单18.52 Optimizing GCC 4.4.5 (MIPS) (IDA)
f:
sll $v0, $a1, 10
sll $a1, 6
subu $a1, $v0, $a1
addu $a1, $a0, $a1
sll $a2, 3
addu $a1, $a2
lwc1 $f0, 4($a1)
or $at, $zero
lwc1 $f1, 0($a1)
jr $ra
or $at, $zero
请描述下列代码的作用。
请判断数组的维度。
指令清单18.53 Optimizing MSVC 2010
_array$ = 8
_x$ = 12
_y$ = 16
_z$ = 20
_f PROC
mov eax, DWORD PTR _x$[esp-4]
mov edx, DWORD PTR _y$[esp-4]
mov ecx, eax
shl ecx, 4
sub ecx, eax
lea eax, DWORD PTR [edx+ecx*4]
mov ecx, DWORD PTR _array$[esp-4]
lea eax, DWORD PTR [eax+eax*4]
shl eax, 4
add eax, DWORD PTR _z$[esp-4]
mov eax, DWORD PTR [ecx+eax*4]
ret 0
_f ENDP
指令清单18.54 Non-optimizing Keil 6/2013 (ARM mode)
f PROC
RSB r1,r1,r1,LSL #4
ADD r1,r1,r1,LSL #2
ADD r0,r0,r1,LSL #8
ADD r1,r2,r2,LSL #2
ADD r0,r0,r1,LSL #6
LDR r0,[r0,r3,LSL #2]
BX lr
ENDP
指令清单18.55 Non-optimizing Keil 6/2013 (Thumb mode)
f PROC
PUSH {r4,lr}
MOVS r4,#0x4b
LSLS r4,r4,#8
MULS r1,r4,r1
ADDS r0,r1,r0
MOVS r1,#0xff
ADDS r1,r1,#0x41
MULS r2,r1,r2
ADDS r0,r0,r2
LSLS r1,r3,#2
LDR r0,[r0,r1]
POP {r4,pc}
ENDP
指令清单18.56 Optimizing GCC 4.9 (ARM64)
f:
sxtw x2, w2
mov w4, 19200
add x2, x2, x2, lsl 2
smull x1, w1, w4
lsl x2, x2, 4
add x3, x2, x3, sxtw
add x0, x0, x3, lsl 2
ldr w0, [x0,x1]
ret
指令清单18.57 Optimizing GCC 4.4.5 (MIPS) (IDA)
f:
sll $v0, $a1, 10
sll $a1, 8
addu $a1, $v0
sll $v0, $a2, 6
sll $a2, 4
addu $a2, $v0
sll $v0, $a1, 4
subu $a1, $v0, $a1
addu $a2, $a3
addu $a1, $a0, $a1
sll $a2, 2
addu $a1, $a2
lw $v0, 0($a1)
jr $ra
or $at, $zero
请描述下列代码的作用。
指令清单18.58 Optimizing MSVC 2012 /GS-
COMM _tbl:DWORD:064H
tv759 = -4 ;size= 4
_main PROC
push ecx
push ebx
push ebp
push esi
xor edx, edx
push edi
xor esi, esi
xor edi, edi
xor ebx, ebx
xor ebp, ebp
mov DWORD PTR tv759[esp+20], edx
mov eax, OFFSET _tbl+4
npad 8 ; align next label
$LL6@main:
lea ecx, DWORD PTR [edx+edx]
mov DWORD PTR [eax+4], ecx
mov ecx, DWORD PTR tv759[esp+20]
add DWORD PTR tv759[esp+20], 3
mov DWORD PTR [eax+8], ecx
lea ecx, DWORD PTR [edx*4]
mov DWORD PTR [eax+12], ecx
lea ecx, DWORD PTR [edx*8]
mov DWORD PTR [eax], edx
mov DWORD PTR [eax+16], ebp
mov DWORD PTR [eax+20], ebx
mov DWORD PTR [eax+24], edi
mov DWORD PTR [eax+32], esi
mov DWORD PTR [eax-4], 0
mov DWORD PTR [eax+28], ecx
add eax, 40
inc edx
add ebp, 5
add ebx, 6
add edi, 7
add esi, 9
cmp eax, OFFSET _tbl+404
jl SHORT $LL6@main
pop edi
pop esi
pop ebp
xor eax, eax
pop ebx
pop ecx
ret 0
_main ENDP
指令清单18.59 Non-optimizing Keil 6/2013 (ARM mode)
main PROC
LDR r12,|L0.60|
MOV r1,#0
|L0.8|
ADD r2,r1,r1,LSL #2
MOV r0,#0
ADD r2,r12,r2,LSL #3
|L0.20|
MUL r3,r1,r0
STR r3,[r2,r0,LSL #2]
ADD r0,r0,#1
CMP r0,#0xa
BLT |L0.20|
ADD r1,r1,#1
CMP r1,#0xa
MOVGE r0,#0
BLT |L0.8|
BX lr
ENDP
|L0.60|
DCD ||.bss||
AREA ||.bss||, DATA, NOINIT, ALIGN=2
tbl
% 400
指令清单18.60 Non-optimizing Keil 6/2013 (Thumb mode)
main PROC
PUSH {r4,r5,lr}
LDR r4,|L0.40|
MOVS r1,#0
|L0.6|
MOVS r2,#0x28
MULS r2,r1,r2
MOVS r0,#0
ADDS r3,r2,r4
|L0.14|
MOVS r2,r1
MULS r2,r0,r2
LSLS r5,r0,#2
ADDS r0,r0,#1
CMP r0,#0xa
STR r2,[r3,r5]
BLT |L0.14|
ADDS r1,r1,#1
CMP r1,#0xa
BLT |L0.6|
MOVS r0,#0
POP {r4,r5,pc}
ENDP
DCW 0x0000
|L0.40|
DCD ||.bss||
AREA ||.bss||, DATA, NOINIT, ALIGN=2
tbl
% 400
指令清单18.61 Non-optimizing GCC 4.9 (ARM64)
.comm tbl,400,8
main:
sub sp, sp, #16
str wzr, [sp,12]
b .L2
.L5:
str wzr, [sp,8]
b .L3
.L4:
ldr w1, [sp,12]
ldr w0, [sp,8]
mul w3, w1, w0
adrp x0, tbl
add x2, x0, :lo12:tbl
ldrsw x4, [sp,8]
ldrsw x1, [sp,12]
mov x0, x1
lsl x0, x0, 2
add x0, x0, x1
lsl x0, x0, 1
add x0, x0, x4
str w3, [x2,x0,lsl 2]
ldr w0, [sp,8]
add w0, w0, 1
str w0, [sp,8]
.L3:
ldr w0, [sp,8]
cmp w0, 9
ble .L4
ldr w0, [sp,12]
add w0, w0, 1
str w0, [sp,12]
.L2:
ldr w0, [sp,12]
cmp w0, 9
ble .L5
mov w0, 0
add sp, sp, 16
ret
指令清单18.62 Non-optimizing GCC 4.4.5 (MIPS) (IDA)
main:
var_18 = -0x18
var_10 = -0x10
var_C = -0xC
var_4 = -4
addiu $sp, -0x18
sw $fp, 0x18+var_4($sp)
move $fp, $sp
la $gp, __gnu_local_gp
sw $gp, 0x18+var_18($sp)
sw $zero, 0x18+var_C($fp)
b loc_A0
or $at, $zero
loc_24: # CODE XREF: main+AC
sw $zero, 0x18+var_10($fp)
b loc_7C
or $at, $zero
loc_30: # CODE XREF: main+88
lw $v0, 0x18+var_C($fp)
lw $a0, 0x18+var_10($fp)
lw $a1, 0x18+var_C($fp)
lw $v1, 0x18+var_10($fp)
or $at, $zero
mult $a1, $v1
mflo $a2
lw $v1, (tbl & 0xFFFF)($gp)
sll $v0, 1
sll $a1, $v0, 2
addu $v0, $a1
addu $v0, $a0
sll $v0, 2
addu $v0, $v1, $v0
sw $a2, 0($v0)
lw $v0, 0x18+var_10($fp)
or $at, $zero
addiu $v0, 1
sw $v0, 0x18+var_10($fp)
loc_7C: # CODE XREF: main+28
lw $v0, 0x18+var_10($fp)
or $at, $zero
slti $v0, 0xA
bnez $v0, loc_30
or $at, $zero
lw $v0, 0x18+var_C($fp)
or $at, $zero
addiu $v0, 1
sw $v0, 0x18+var_C($fp)
loc_A0: # CODE XREF: main+1C
lw $v0, 0x18+var_C($fp)
or $at, $zero
slti $v0, 0xA
bnez $v0, loc_24
or $at, $zero
move $v0, $zero
move $sp, $fp
lw $fp, 0x18+var_4($sp)
addiu $sp, 0x18
jr $ra
or $at, $zero
.comm tbl:0x64 # DATA XREF: main+4C
[1] http://en.wikipedia.org/wiki/Stack_buffer_overflow。
[2] 请参见维基百科https://en.wikipedia.org/wiki/Buffer_overflow_protection。
[3] TIB是Thread Information Block。请参见https://en.wikipedia.org/wiki/Win32_Thread_ Information_Block。
[4] 但是根据C99标准[ISO07,pp 6.7.5/2]这种可变长数组是合法数据,可以被编译。GCC确实可以使用栈处理动态数组。这时候,它实现数组的方式和5.2.4节介绍过的alloca()函数的实现方式相近。