第18章 数组

在内存中,数组就是按次序排列的、相同数据类型的一组数据。

18.1 简介

#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; 
};
18.1.1 x86

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倍。

..\TU\1801.tif{}

图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++表达式的表示方法!

18.1.2 ARM

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
18.1.3 MIPS

面向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章中会提到的循环优化技术。通过这种技术,编译器可尽量避免效率较低的乘法运算。

18.2 缓冲区溢出

18.2.1 读取数组边界以外的内容

综上所述,编译器借助索引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所示。

..\TU\1802.tif

图18.2 OllyDbg:运算结果

这是地址接近栈内数组的数据的值。它的地址距离数组的起始地址有80字节。

让我们通过OllyDbg看看这个数从哪里来。如图18.3所示,使用OllyDbg加载这个程序,找到数组最后一个值之后的数据。

..\TU\1803.tif{}

图18.3 OllyDbg:读取数组中的第20个元素、并使用printf()输出

这是什么的值?根据栈结构来判断,这个值是先前保存的EBP寄存器的值。我们继续跟踪这个程序,如图18.4所示,看看它的提取过程。

..\TU\1804.tif{}

图18.4 OllyDbg:还原EBP寄存器的值

到底有没有什么办法控制数组的访问边界问题呢?如果需要控制数组边界,就要修改编译器,强制其生成的程序检查索引index是否在边界之内。某些高级编程语言,如Python和Java,就会进行边界检查。但是这种控制会严重影响程序的性能。

18.2.2 向数组边界之外的地址赋值

既然我们可以“非法地”利用栈来读取数组边界以外的数值,那么我们是否也可以向数组边界以外的地址里写入数据呢?

可通过下面的程序来进行验证。

#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所示。

..\TU\1805.tif{}

图18.5 OllyDbg:恢复EBP的值之后

然后逐步执行程序,等待函数结束,如图18.6所示。

..\TU\1806.tif{}

图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下寄存器的值也存在细微的差别。

18.3 缓冲区溢出的保护方法

无论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)。这个文件的注释详细描述了有关变量的功能。

18.3.1 Optimizing Xcode 4.6.3 (LLVM) (Thumb-2 mode)

我们使用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进行异常处理,实际上会终止个程序。

18.4 其他

现在我们应该可以理解为什么C/C++编译不了下面的程序了。[4]

void f(int size)
{
    int a[size];
...
};

在编译阶段,编译器必须确切地知道需要给数组分配多大的存储空间,它需要事先明确分配局部栈或数据段(全局变量)的格局,所以编译器无法处理上述这种长度可变的数组。

如果无法事先确定数组的长度,那么我们就应当使用malloc()函数分配出一块内存,然后直接按照常规变量数组的方式访问这块内存;或者遵循C99标准(参见ISO07,6.7.5/2)进行处理,但是遵循C99标准而设计出来的程序,内部实现的方法更接近alloca()函数(详情请参阅5.2.4节)。

18.5 字符串指针

本节以下述程序为例。

指令清单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.5.1 x64

指令清单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

上述程序的功能如下:

编译器的优化编译结果更为直接。

指令清单18.10 Optimizing GCC 4.9 x64

        movsx   rdi, edi
        mov     rax, QWORD PTR month1[0+rdi*8]
        ret
18.5.2 32位MSVC

使用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。

18.5.3 32位ARM

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.5.4 ARM64

指令清单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.5.5 MIPS

指令清单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>
18.5.6 数组溢出

本例参数的取值范围是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()了。

18.6 多维数组

多维数组和线性数组在本质上是相同的。

计算机内存是连续的线性空间,它可以与一维数组直接对应。在被拆分成多个一维数组之后,多维数组与内栈线性空间同样存在直接对应的存储关系。

举例来说,二维数组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)匹配的优先顺序最优。只要相互匹配,那么程序就可以连续访问数据,整体性能就会提高。所以,如果程序以“逐行”的方式访问数据,那么就应当以行优先的顺序组织数组;反之亦然。

18.6.1 二维数组举例

本例用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。

..\TU\1807.tif

图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。

..\TU\1808.tif

图18.8 OllyDbg:填充数据之后的数组

18.6.2 以一维数组的方式访问二维数组

以一维数组的方式访问二维数组的方法至少有两种。

#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
18.6.3 三维数组

多维数组的情况也差不多。

在下面的例子里,我们演示一个由整型数据构成的三维数组,每个整数元素占用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
18.6.4 更多案例

计算机的显示屏幕是一个2D显示空间,但是显存却是一个一维线性数组。

本书第83章将详细介绍有关内容。

18.7 二维字符串数组的封装格式

在指令清单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要乘以零,再把零加在最终结果里?虽然说它不影响最终运行结果,但是也足以说是编译器的某种怪癖了。本文刻意演示这种怪癖代码,是希望读者不要拘泥于编译器生成的指令的形式,而要从编程人员的角度理解程序的源代码。

18.7.1 32位ARM

由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.7.2 ARM64

指令清单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.7.3 MIPS

指令清单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
18.7.4 总结

字符串存储技术属于经典的数组技术。Oracle RDBMS的程序中就大量使用了这种技术。虽然当代计算机程序中可能很少应用这种数组技术了,但是字符串型数据可充分演示数组的各方面特点。

18.8 本章小结

在内存中,数组就是依次排列的一组同类型数据。数组元素可以是任意类型的数据,甚至可以是结构体型的数据。如果要访问数组中的特定元素,首先就要计算其地址。

18.9 练习题

18.9.1 题目1

请描述下述代码的功能。

指令清单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
18.9.2 题目2

请描述下述程序的功能。

通过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
18.9.3 题目3

请描述下列代码的作用。

通过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.9.4 题目4

请描述下列代码的作用。

请判断数组的维度。

指令清单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.9.5 题目5

请描述下列代码的作用。

指令清单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()函数的实现方式相近。