Chapter 16 數組


數組是在內存中連續排列的一組變量,這些變量具有相同類型1。

16.1 小例子

#!cpp
#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
", i, a[i]);
    return 0;
};

16.1.1 x86

編譯后:

Listing 16.1: MSVC

#!bash
_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 [email protected]
[email protected]:
    mov     eax, DWORD PTR _i$[ebp]
    add     eax, 1
    mov     DWORD PTR _i$[ebp], eax
[email protected]:
    cmp     DWORD PTR _i$[ebp], 20 ; 00000014H
    jge     SHORT [email protected]
    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 [email protected]
[email protected]:
    mov     DWORD PTR _i$[ebp], 0
    jmp     SHORT [email protected]
[email protected]:
    mov     eax, DWORD PTR _i$[ebp]
    add     eax, 1
    mov     DWORD PTR _i$[ebp], eax
[email protected]:
    cmp     DWORD PTR _i$[ebp], 20 ; 00000014H
    jge     SHORT [email protected]
    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 [email protected]
[email protected]:
    xor eax, eax
    mov esp, ebp
    pop ebp
    ret 0
_main ENDP

這段代碼主要有兩個循環:第一個循環填充數組,第二個循環打印數組元素。shl ecx,1指令使ecx的值乘以2,更多關于左移請參考17.3.1。 在堆棧上為數組分配了80個字節的空間,包含20個元素,每個元素4字節大小。

GCC 4.4.1編譯后為:

Listing 16.2: GCC 4.4.1

#!bash
            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
"
            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

順便提一下,一個int*類型(指向int的指針)的變量—你可以使該變量指向數組并將該數組傳遞給另一個函數,更準確的說,傳遞的指針指向數組的第一個元素(該數組其它元素的地址需要顯示計算)。比如a[idx],idx加上指向該數組的指針并返回該元素。 一個有趣的例子:類似”string”字符數組的類型是const char*,索引可以應用與該指針。比如可能寫作”string”[i]—正確的C/C++表達式。

16.1.2 ARM + Non-optimizing Keil + ARM mode

#!bash
        EXPORT _main
_main
        STMFD   SP!, {R4,LR}
        SUB     SP, SP, #0x50           ; allocate place for 20 int variables
; 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, run loop body again
; second loop
        MOV     R4, #0                  ; i
        B       loc_4C4
loc_4B0
        LDR     R2, [SP,R4,LSL#2]       ; (second printf argument) R2=*(SP+R4<<4) (same as *(SP+R4*4))
        MOV     R1, R4                  ; (first printf argument) R1=i
        ADR     R0, aADD                ; "a[%d]=%d
"
        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           ; deallocate place, allocated for 20 int variables
        LDMFD   SP!, {R4,PC}

int類型長度為32bits即4字節,20個int變量需要80(0x50)字節,因此“sub sp,sp,#0x50”指令為在棧上分配存儲空間。 兩個循環迭代器i被存儲在R4寄存器中。 值i*2被寫入數組,通過將i值左移1位實現乘以2的效果,整個過程通過”MOV R0,R4,LSL#1指令來實現。 “STR R0, [SP,R4,LSL#2]”把R0內容寫入數組。過程為:SP指向數組開始,R4是i,i左移2位相當于乘以4,即*(SP+R4*4)=R0。 第二個loop的“LDR R2, [SP,R4,LSL#2]”從數組讀取數值到寄存器,R2=*(SP+R4*4)

16.1.3 ARM + Keil + thumb 模式優化后

#!bash
_main
        PUSH    {R4,R5,LR}
; allocate place for 20 int variables + one more variable
        SUB     SP, SP, #0x54
; first loop
        MOVS    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
; second loop
        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
"
        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 place, allocated for 20 int variables + one more variable
        ADD     SP, SP, #0x54
        POP     {R4,R5,PC}

Thumb代碼也是非常類似的。Thumb模式計算數組偏移的移位操作使用特定的指令LSLS。 編譯器在堆棧中申請的數組空間更大,但是最后4個字節的空間未使用。

16.2 緩沖區溢出

Array[index]中index指代數組索引,仔細觀察下面的代碼,你可能注意到代碼沒有index是否小于20。如果index大于20?這是C/C++經常被批評的特征。 以下代碼可以成功編譯可以工作:

#!cpp
#include <stdio.h>
int main()
{
    int a[20];
    int i;
    for (i=0; i<20; i++)
        a[i]=i*2;
    printf ("a[100]=%d
", a[100]);
    return 0;
};

編譯后 (MSVC 2010):

#!bash
_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 [email protected]
[email protected]:
    mov     eax, DWORD PTR _i$[ebp]
    add     eax, 1
    mov     DWORD PTR _i$[ebp], eax
[email protected]:
    cmp     DWORD PTR _i$[ebp], 20  ; 00000014H
    jge     SHORT [email protected]
    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 [email protected]
[email protected]:
    mov     eax, DWORD PTR _a$[ebp+400]
    push    eax
    push    OFFSET $SG2460
    call    _printf
    add     esp, 8
    xor     eax, eax
    mov     esp, ebp
    pop     ebp
    ret     0
_main       ENDP

運行,我們得到: a[100]=760826203

打印的數字僅僅是距離數組第一個元素400個字節處的堆棧上的數值。 編譯器可能會自動添加一些判斷數組邊界的檢測代碼(更高級語言3),但是這可能影響運行速度。 我們可以從棧上非法讀取數值,是否可以寫入數值呢? 下面我們將寫入數值:

#!cpp
#include <stdio.h>
int main()
{
    int a[20];
    int i;

    for (i=0; i<30; i++)
        a[i]=i;

    return 0;
};

我們得到:

#!bash
_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 [email protected]
[email protected]:
    mov     eax, DWORD PTR _i$[ebp]
    add     eax, 1
    mov     DWORD PTR _i$[ebp], eax
[email protected]:
    cmp     DWORD PTR _i$[ebp], 30 ; 0000001eH
    jge     SHORT [email protected]
    mov     ecx, DWORD PTR _i$[ebp]
    mov     edx, DWORD PTR _i$[ebp] ; that instruction is obviously redundant
    mov     DWORD PTR _a$[ebp+ecx*4], edx ; ECX could be used as second operand here instead
    jmp     SHORT [email protected]
[email protected]:
    xor     eax, eax
    mov     esp, ebp
    pop     ebp
    ret     0
_main       ENDP

編譯后運行,程序崩潰。我們找出導致崩潰的地方。 沒有使用調試器,而是使用我自己寫的小工具tracer足以完成任務。 我們用它看被調試進程崩潰的地方:

#!bash
generic tracer 0.4 (WIN32), http://conus.info/gt

New process: C:PRJ...1.exe, PID=7988
EXCEPTION_ACCESS_VIOLATION: 0x15 (<symbol (0x15) is in unknown module>), ExceptionInformation
[0]=8
EAX=0x00000000 EBX=0x7EFDE000 ECX=0x0000001D EDX=0x0000001D
ESI=0x00000000 EDI=0x00000000 EBP=0x00000014 ESP=0x0018FF48
EIP=0x00000015
FLAGS=PF ZF IF RF
PID=7988|Process exit, return code -1073740791

我們來看各個寄存器的狀態,異常發生在地址0x15。這是個非法地址—至少對win32代碼來說是!這種情況并不是我們期望的,我們還可以看到EBP值為0x14,ECX和EDX都為0x1D。 讓我們來研究堆棧布局。 代碼進入main()后,EBP寄存器的值被保存在棧上。為數組和變量i一共分配84字節的棧空間,即(20+1)*sizeof(int)。此時ESP指向_i變量,之后執行push something,something將緊挨著_i。 此時main()函數內棧布局為:

#!bash
ESP 
ESP+4 
ESP+84 
ESP+88 
4 bytes for i
80 bytes for a[20] array
saved EBP value
returning address

指令a[19]=something寫入最后的int到數組邊界(這里是數組邊界!)。 指令a[20]=something,something將覆蓋棧上保存的EBP值。 請注意崩潰時寄存器的狀態。在此例中,數字20被寫入第20個元素,即原來存放EBP值得地方被寫入了20(20的16進制表示是0x14)。然后RET指令被執行,相當于執行POP EIP指令。 RET指令從堆棧中取出返回地址(該地址為CRT內部調用main()的地址),返回地址處被存儲了21(0x15)。CPU執行地址0x15的代碼,異常被拋出。 Welcome!這被稱為緩沖區溢出4。 使用字符數組代替int數組,創建一個較長的字符串,把字符串傳遞給程序,函數沒有檢測字符串長度,把字符復制到較短的緩沖區,你能夠找到找到程序必須跳轉的地址。事實上,找出它們并不是很簡單。 我們來看GCC 4.4.1編譯后的同類代碼:

#!bash
            public main
main        proc near

a           = dword ptr -54h
i           = dword ptr -4

            push    ebp
            mov     ebp, esp
            sub     esp, 60h
            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下運行將產生:段錯誤。 使用GDB調試:

#!bash
(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)

寄存器的值與win32例子略微不同,因為堆棧布局也不太一樣。

16.3 防止緩沖區溢出的方法

下面一些方法防止緩沖區溢出。MSVC使用以下編譯選項:

#!bash
/RTCs Stack Frame runtime checking
/GZ Enable stack checks (/RTCs)

一種方法是在函數局部變量和序言之間寫入隨機值。在函數退出之前檢查該值。如果該值不一致則掛起而不執行RET。進程將被掛起。 該隨機值有時被稱為“探測值”。 如果使用MSVC編譯簡單的例子(16.1),使用RTC1和RTCs選項,將能看到函數調用@_RTC_[email protected]

我們來看GCC如何處理這些。我們使用alloca()(4.2.4)例子:

#!cpp
#include <malloc.h>
#include <stdio.h>
void f()
{
    char *buf=(char*)alloca (600);
    _snprintf (buf, 600, "hi! %d, %d, %d
", 1, 2, 3);

    puts (buf);
};

我們不使用任何附加編譯選項,只使用默認選項,GCC 4.7.3將插入“探測“檢測代碼: Listing 16.3: GCC 4.7.3

#!bash
.LC0:
    .string "hi! %d, %d, %d
"
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
"
    mov     DWORD PTR [esp+4], 600
    mov     DWORD PTR [esp], ebx
    mov     eax, DWORD PTR gs:20                    ; canary
    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                    ; canary
    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)將輸出以下信息:

#!bash
*** 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時代。現在的作用和以前不同。簡要的說,gs寄存器在linux下一直指向TLS(48)–存儲線程的各種信息(win32環境下,fs寄存器同樣的作用,指向TIB8 9)。 更多信息請參考linux源碼arch/x86/include/asm/stackprotector.h(至少3.11版本)。

16.3.1 Optimizing Xcode (LLVM) + thumb-2 mode

我們回頭看簡單的數組例子(16.1)。我們來看LLVM如何檢查“探測值“。

#!bash
_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
"
            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              ; canary still correct?
            MOVEQ   R0, #0
            ADDEQ   SP, SP, #0x54
            LDREQ.W R8, [SP+0x64+var_64],#4
            POPEQ   {R4-R7,PC}
            BLX     ___stack_chk_fail

首先可以看到,LLVM循環展開寫入數組,LLVM認為先計算出數組元素的值速度更快。 在函數的結尾我們能看到“探測值“的檢測—局部存儲的值與R8指向的標準值對比。如果相等4指令塊將通過”ITTTT EQ“觸發,R0寫入0,函數退出。如果不相等,指令塊將不會被觸發,跳向___stack_chk_fail函數,結束進程。

16.4 One more word about arrays

現在我們來理解下面的C/C++代碼為什么不能正常使用10:

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

這是因為在編譯階段編譯器不知道數組的具體大小無論是在堆棧或者數據段,無法分配具體空間。 如果你需要任意大小的數組,應該通過malloc()分配空間,然后訪問內存塊來訪問你需要的類型數組。或者使用C99標準[15,6.7.5/2],但它內部看起來更像alloca()(4.2.4)。

16.5 Multidimensional arrays

多維數組和線性數組在本質上是一樣的。 因為計算機內存是線性的,它是一維數組。但是一維數組可以很容易用來表現多維的。 比如數組a[3][4]元素可以放置在一維數組的12個單元中:

#!bash
[0][0]
[0][1]
[0][2]
[0][3]
[1][0]
[1][4]
[1][5]
[1][6]
[2][0]
[2][7]
[2][8]
[2][9]

該二維數組在內存中用一維數組索引表示為:

1 2 3
4 5 6 7
8 9 10 11

為了計算我們需要的元素地址,首先,第一個索引乘以4(矩陣寬度),然后加上第二個索引。這種被稱為行優先,C/C++和Python常用這種方法。行優先的意思是:先寫入第一行,接著是第二行,…,最后是最后一行。 另一種方法就是列優先,主要用在FORTRAN,MATLAB,R等。列優先的意思是:先寫入第一列,然后是第二列,…,最后是最后一列。 多維數組與此類似。 我們看個例子: Listing 16.4: simple example

#!cpp
#include <stdio.h>

int a[10][20][30];

void insert(int x, int y, int z, int value)
{
    a[x][y][z]=value;
};

16.5.1 x86

MSVC 2010:

Listing 16.5: MSVC 2010

#!bash
_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

多維數組計算索引公式:address=600*4*x+30*4*y+4z。因為int類型為32-bits(4字節),所以要乘以4。

Listing 16.6: GCC 4.4.1

#!bash
        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使用的不同的計算方法。為計算第一個操作值30y,GCC沒有使用乘法指令。GCC的做法是:(???? + ????) ? 4 ? (???? + ????) = (2????) ? 4 ? 2???? = 2 ? 16 ? ???? ? 2???? = 32???? ? 2???? = 30????。因此30y的計算僅使用加法和移位操作,這樣速度更快。

16.5.2 ARM + Non-optimizing Xcode (LLVM) + thumb mode

Listing 16.7: Non-optimizing Xcode (LLVM) + thumb mode

#!bash
_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]
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代碼在棧中保存了所有變量,這是冗余的。元素地址的計算我們通過公式已經找到了。

16.5.3 ARM + Optimizing Xcode (LLVM) + thumb mode

Listing 16.8: Optimizing Xcode (LLVM) + thumb mode

#!bash
_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 ; R9 = pointer to a array
LDR.W       R9, [R9]
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 =
                                ; ptr to a + y*30*4 + x*600*4 + z*4
BX          LR

這里的小技巧沒有使用乘法,使用移位、加減法等。 這里有個新指令RSB(逆向減法),該指令的意義是讓第一個操作數像SUB第二個操作數一樣可以應用LSL#4附加操作。 “LDR.W R9, [R9]”類似于x86下的LEA指令(B.6.2),這里什么都沒有做,是冗余的。顯然,編譯器沒有優化它。

Chapter 17 位域


很多函數參數的輸入標志使用了位域。當然,可以使用bool類型來替代,只是有點浪費。

17.1 Specific bit checking

17.1.1 x86

Win32 API 例子:

#!cpp
    HANDLE fh;

    fh=CreateFile ("file", GENERIC_WRITE | GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_ALWAYS,
FILE_ATTRIBUTE_NORMAL, NULL);

MSVC 2010: Listing 17.1: MSVC 2010

#!bash
push    0
push    128            ; 00000080H
push    4
push    0
push    1
push    -1073741824    ; c0000000H
push    OFFSET $SG78813
call    DWORD PTR [email protected]
mov     DWORD PTR _fh$[ebp], eax

我們再查看WinNT.h:

Listing 17.2: WinNT.h

#!cpp
#define GENERIC_READ (0x80000000L)
#define GENERIC_WRITE (0x40000000L)
#define GENERIC_EXECUTE (0x20000000L)
#define GENERIC_ALL (0x10000000L)

容易看出GENERIC_READ | GENERIC_WRITE = 0x80000000 | 0x40000000 = 0xC0000000,該值作為CreateFile()1函數的第二個參數。 CreateFile()如何檢查該標志呢? 以Windows XP SP3 x86為例,在kernel32.dll中查看CreateFileW檢查該標志的代碼片段: Listing 17.3: KERNEL32.DLL (Windows XP SP3 x86)

#!bash
.text:7C83D429 test byte ptr [ebp+dwDesiredAccess+3], 40h
.text:7C83D42D mov [ebp+var_8], 1
.text:7C83D434 jz short loc_7C83D417
.text:7C83D436 jmp loc_7C810817

我們來看TEST指令,該指令并未檢測整個第二個參數,僅檢測關鍵的一個字節(ebp+dwDesiredAccess+3),檢測0x40標志(這里代表GENERIC_WRITE標志)。 Test對兩個參數(目標,源)執行AND邏輯操作,并根據結果設置標志寄存器,結果本身不會保存(CMP和SUB與此類似(6.6.1))。 該代碼片段邏輯如下:

#!cpp
if ((dwDesiredAccess&0x40000000) == 0) goto loc_7C83D417

如果AND指令沒有設置ZF位,JZ將不觸發跳轉。如果dwDesiredAccess不等于0x40000000,AND結果將是0,ZF位將會被設置,條件跳轉將被觸發。

我們在linux GCC 4.4.1下查看:

#!bash
#include <stdio.h>
#include <fcntl.h>
void main()
{
    int handle;

    handle=open ("file", O_RDWR | O_CREAT);
};

我們得到: Listing 17.4: GCC 4.4.1

#!bash
    public main
main proc near


var_20 = dword ptr -20h
var_1C = dword ptr -1Ch
var_4 = dword ptr -4


    push ebp
    mov ebp, esp
    and esp, 0FFFFFFF0h
    sub esp, 20h
    mov [esp+20h+var_1C], 42h
    mov [esp+20h+var_20], offset aFile ; "file"
    call _open
    mov [esp+20h+var_4], eax
    leave
    retn
main endp

我們在libc.so.6庫中查看open()函數,看到syscall: Listing 17.5: open() (libc.so.6)

#!bash
.text:000BE69B mov edx, [esp+4+mode] ; mode
.text:000BE69F mov ecx, [esp+4+flags] ; flags
.text:000BE6A3 mov ebx, [esp+4+filename] ; filename
.text:000BE6A7 mov eax, 5
.text:000BE6AC int 80h ; LINUX - sys_open

因此open()對于標志位的檢測在內核中。 對于linux2.6,當sys_open被調用時,最終傳遞到do_sys_open內核函數,然后進入do_filp_open()函數(該函數位于源碼fs/namei.c中)。 除了通過堆棧傳遞參數,還可以通過寄存器傳遞方式,這種調用方式成為fastcall(47.3)。這種調用方式CPU不需要訪問堆棧就可以直接讀取參數的值,所以速度更快。GCC有編譯選項regram2,可以設置通過寄存器傳遞的參數的個數。 Linux2.6內核編譯附加選項為-mregram=33 4。 這意味著前3個參數通過EAX、EDX、ECX寄存器傳遞,剩余的參數通過堆棧傳遞。如果參數小于3,僅部分寄存器被使用。 我們下載linux內核2.6.31源碼,在Ubuntu中編譯:make vmlinux,在IDA中打開,找到do_filp_open()函數。在開始部分我們可以看到(注釋個人添加): Listing 17.6:do_filp_open() (linux kernel 2.6.31)

#!bash
do_filp_open proc near
...
    push ebp
    mov ebp, esp
    push edi
    push esi
    push ebx
    mov ebx, ecx
    add ebx, 1
    sub esp, 98h
    mov esi, [ebp+arg_4] ; acc_mode (5th arg)
    test bl, 3
    mov [ebp+var_80], eax ; dfd (1th arg)
    mov [ebp+var_7C], edx ; pathname (2th arg)
    mov [ebp+var_78], ecx ; open_flag (3th arg)
    jnz short loc_C01EF684
    mov ebx, ecx ; ebx <- open_flag

GCC保存3個參數的值到堆棧。否則,可能會造成寄存器浪費。 我們來看代碼片段: Listing 17.7: do_filp_open() (linux kernel 2.6.31)

#!bash
loc_C01EF6B4:            ; CODE XREF: do_filp_open+4F
    test bl, 40h         ; O_CREAT
    jnz loc_C01EF810
    mov edi, ebx
    shr edi, 11h
    xor edi, 1
    and edi, 1
    test ebx, 10000h
    jz short loc_C01EF6D3
    or edi, 2

O_CREAT宏等于0x40,如果open_flag為0x40,標志位被置1,接下來的JNZ指令將被觸發。

17.1.2 ARM

Linux kernel3.8.0檢測O_CREAT過程有點不同。 Listing 17.8: linux kernel 3.8.0

#!bash
struct file *do_filp_open(int dfd, struct filename *pathname,

const struct open_flags *op)
{

… filp = path_openat(dfd, pathname, &nd, op, flags | LOOKUP_RCU); … }

static struct file *path_openat(int dfd, struct filename *pathname,
    struct nameidata *nd, const struct open_flags *op, int flags)

{

… error = do_last(nd, &path, file, op, &opened, pathname); … } static int do_last(struct nameidata *nd, struct path *path, struct file *file, const struct open_flags *op, int *opened, struct filename *name) { … if (!(open_flag & O_CREAT)) { … error = lookup_fast(nd, path, &inode); … } else { … error = complete_walk(nd); } … }

在IDA中查看ARM模式內核: Listing 17.9: do_last() (vmlinux)

#!bash
...
.text:C0169EA8 MOV           R9, R3 ; R3 - (4th argument) open_flag
...
.text:C0169ED4 LDR           R6, [R9] ; R6 - open_flag
...
.text:C0169F68 TST           R6, #0x40 ; jumptable C0169F00 default case
.text:C0169F6C BNE           loc_C016A128
.text:C0169F70 LDR           R2, [R4,#0x10]
.text:C0169F74 ADD           R12, R4, #8
.text:C0169F78 LDR           R3, [R4,#0xC]
.text:C0169F7C MOV           R0, R4
.text:C0169F80 STR           R12, [R11,#var_50]
.text:C0169F84 LDRB          R3, [R2,R3]
.text:C0169F88 MOV           R2, R8
.text:C0169F8C CMP           R3, #0
.text:C0169F90 ORRNE         R1, R1, #3
.text:C0169F94 STRNE         R1, [R4,#0x24]
.text:C0169F98 ANDS          R3, R6, #0x200000
.text:C0169F9C MOV           R1, R12
.text:C0169FA0 LDRNE         R3, [R4,#0x24]
.text:C0169FA4 ANDNE         R3, R3, #1
.text:C0169FA8 EORNE         R3, R3, #1
.text:C0169FAC STR           R3, [R11,#var_54]
.text:C0169FB0 SUB           R3, R11, #-var_38
.text:C0169FB4 BL            lookup_fast
...
.text:C016A128 loc_C016A128          ; CODE XREF: do_last.isra.14+DC
.text:C016A128 MOV           R0, R4
.text:C016A12C BL            complete_walk
...

TST指令類似于x86下的TEST指令。 這段代碼來自do_last()函數源碼,有兩個分支lookup_fast()和complete_walk()。這里O_CREAT宏也等于0x40。

17.2 Specific bit setting/clearing

例如:

#!cpp
#define IS_SET(flag, bit) ((flag) & (bit))
#define SET_BIT(var, bit) ((var) |= (bit))
#define REMOVE_BIT(var, bit) ((var) &= ~(bit))
int f(int a)
{
    int rt=a;
    SET_BIT (rt, 0x4000);
    REMOVE_BIT (rt, 0x200);

    return rt;
};

17.2.1 x86

MSVC 2010: Listing 17.10: MSVC 2010

#!bash
_rt$ = -4 ; size = 4
_a$ = 8 ; size = 4
_f PROC
push ebp
mov ebp, esp
push ecx
mov eax, DWORD PTR _a$[ebp]
mov DWORD PTR _rt$[ebp], eax
mov ecx, DWORD PTR _rt$[ebp]
or ecx, 16384            ; 00004000H
mov DWORD PTR _rt$[ebp], ecx
mov edx, DWORD PTR _rt$[ebp]
and edx, -513            ; fffffdffH
mov DWORD PTR _rt$[ebp], edx
mov eax, DWORD PTR _rt$[ebp]
mov esp, ebp
pop ebp
ret 0
_f ENDP

OR指令添加一個或多個bit位而忽略了其余位。 AND用來重置一個bit位。 如果我們使用msvc編譯,并且打開優化選項(/Ox),代碼將會更短: Listing 17.11: Optimizing MSVC

#!bash
_a$ = 8          ; size = 4
_f PROC
    mov eax, DWORD PTR _a$[esp-4]
    and eax, -513    ; fffffdffH
    or eax, 16384    ; 00004000H
    ret 0
_f ENDP

我們來看GCC 4.4.1無優化的代碼:

#!bash
            public f
f           proc near
var_4       = dword ptr -4
arg_0       = dword ptr 8
        push ebp
        mov ebp, esp
        sub esp, 10h
        mov eax, [ebp+arg_0]
        mov [ebp+var_4], eax
        or [ebp+var_4], 4000h
        and [ebp+var_4], 0FFFFFDFFh
        mov eax, [ebp+var_4]
        leave
        retn
f           endp

MSVC未優化的代碼有些冗余。 現在我們來看GCC打開優化選項-O3:

Listing 17.13: Optimizing GCC

#!bash
    public f
f       proc near
arg_0 = dword ptr 8
    push ebp
    mov ebp, esp
    mov eax, [ebp+arg_0]
    pop ebp
    or ah, 40h
    and ah, 0FDh
    retn
f       endp

代碼更短。值得注意的是編譯器使用了AH寄存器-EAX寄存器8bit-15bit部分。

enter image description here

8086 16位CPU累加器被稱為AX,包含兩個8位部分-AL(低字節)和AH(高字節)。在80386下所有寄存器被擴展為32位,累加器被命名為EAX,為了保持兼容性,它的老的部分仍可以作為AX/AH/AL寄存器來訪問。 因為所有的x86 CPU都兼容于16位CPU,所以老的16位操作碼比32位操作碼更短。”or ah,40h”指令僅復制3個字節比“or eax,04000h”需要復制5個字節甚至6個字節(如果第一個操作碼不是EAX)更合理。 編譯時候開啟-O3并且設置regram=3生成的代碼會更短。

Listing 17.14: Optimizing GCC

#!bash
        public f
f       proc near
    push ebp
    or ah, 40h
    mov ebp, esp
    and ah, 0FDh
    pop ebp
    retn
f       endp

事實上,第一個參數已經被加載到EAX了,所以可以直接使用了。值得注意的是,函數序言(push ebp/mov ebp,esp)和結語(pop ebp)很容易被忽略。GCC并沒有優化掉這些代碼。更短的代碼可以使用內聯函數(27)。

17.2.2 ARM + Optimizing Keil + ARM mode

Listing 17.15: Optimizing Keil + ARM mode

#!bash
02 0C C0 E3     BIC     R0, R0, #0x200
01 09 80 E3     ORR     R0, R0, #0x4000
1E FF 2F E1     BX  LR

BIC是“邏輯and“類似于x86下的AND。ORR是”邏輯or“類似于x86下的OR。

17.2.3 ARM + Optimizing Keil + thumb mode

Listing 17.16: Optimizing Keil + thumb mode

#!bash
01 21 89 03     MOVS     R1, 0x4000
08 43       ORRS     R0, R1
49 11       ASRS     R1, R1, #5 ; generate 0x200 and place to R1
88 43       BICS     R0, R1
70 47       BX   LR5

從0x4000右移生成0x200,采用移位使代碼更簡潔。

17.2.4 ARM + Optimizing Xcode (LLVM) + ARM mode

Listing 17.17: Optimizing Xcode (LLVM) + ARM mode

#!bash
42 0C C0 E3     BIC     R0, R0, #0x4200
01 09 80 E3     ORR     R0, R0, #0x4000
1E FF 2F E1     BX  LR

該代碼由LLVM生成,從源碼形式上看,看起來更像是:

#!bash
REMOVE_BIT (rt, 0x4200);
SET_BIT (rt, 0x4000);

為什么是0x4200?可能是編譯器構造的5,可能是編譯器編譯錯誤,但生成的代碼是可用的。 更多編譯器異常請參考相關資料(67)。 對于thumb模式,優化Xcode(LLVM)生成的代碼相似。

17.3 Shifts

C/C++的移位操作通過<<和>>實現。 這里有一個例子函數,計算輸入變量有多少個位被置為1.

#!cpp
#define IS_SET(flag, bit) ((flag) & (bit))
int f(unsigned int a)
{
    int i;
    int rt=0;
    for (i=0; i<32; i++)
        if (IS_SET (a, 1<<i))
        rt++;

    return rt;
    };

在循環中,迭代計數從0到31,1<<i語句將計數從1到0x80000000。1<<i即1左移n位,將包含32位數字所有可能的bit位。每次移位僅有1位被置1,其它位均為0,IS_SET宏將判斷a對應的位是否置1。

enter image description here

IS_SET宏就是邏輯與(AND)操作,如果對應的位不為1,則返回0。if條件表達式如果不為0,if()將被觸發。

17.3.1 x86

MSVC 2010:

Listing 17.18: MSVC 2010

#!bash
_rt$ = -8       ; size = 4
_i$ = -4        ; size = 4
_a$ = 8         ; size = 4
_f PROC
    push ebp
    mov ebp, esp
    sub esp, 8
    mov DWORD PTR _rt$[ebp], 0
    mov DWORD PTR _i$[ebp], 0
    jmp SHORT [email protected]
[email protected]:
    mov eax, DWORD PTR _i$[ebp]     ; increment of 1
    add eax, 1
    mov DWORD PTR _i$[ebp], eax
[email protected]:
    cmp DWORD PTR _i$[ebp], 32      ; 00000020H
    jge SHORT [email protected]            ; loop finished?
    mov edx, 1
    mov ecx, DWORD PTR _i$[ebp]
    shl edx, cl             ; EDX=EDX<<CL
    and edx, DWORD PTR _a$[ebp]
    je SHORT [email protected]             ; result of AND instruction was 0?
    ; then skip next instructions
    mov eax, DWORD PTR _rt$[ebp]    ; no, not zero
    add eax, 1 ; increment rt
    mov DWORD PTR _rt$[ebp], eax
[email protected]:
    jmp SHORT [email protected]
[email protected]:
    mov eax, DWORD PTR _rt$[ebp]
    mov esp, ebp
    pop ebp
    ret 0
_f ENDP

下面是GCC 4.4.1編譯的代碼: Listing 17.19: GCC 4.4.1

#!bash
        public f
f           proc near
rt      = dword ptr -0Ch
i       = dword ptr -8
arg_0   = dword ptr 8

        push ebp
        mov ebp, esp
        push ebx
        sub esp, 10h
        mov [ebp+rt], 0
        mov [ebp+i], 0
        jmp short loc_80483EF
loc_80483D0:
        mov eax, [ebp+i]
        mov edx, 1
        mov ebx, edx
        mov ecx, eax
        shl ebx, cl
        mov eax, ebx
        and eax, [ebp+arg_0]
        test eax, eax
        jz short loc_80483EB
        add [ebp+rt], 1
loc_80483EB:
        add [ebp+i], 1
loc_80483EF:
        cmp [ebp+i], 1Fh
            jle short loc_80483D0
            mov eax, [ebp+rt]
        add esp, 10h
        pop ebx
        pop ebp
        retn
f           endp

在乘以或者除以2的指數值(1,2,4,8等)時經常使用移位操作。 例如:

#!cpp
unsigned int f(unsigned int a)
{
    return a/4;
};

MSVC 2010: Listing 17.20: MSVC 2010

#!bash
_a$ = 8                     ; size = 4
_f      PROC
        mov eax, DWORD PTR _a$[esp-4]
        shr eax, 2
        ret 0
_f ENDP

例子中的SHR(邏輯右移)指令將a值右移2位,最高兩位被置0,最低2位被丟棄。實施上丟棄的兩位是除法的余數。 SHR作用類似SHL只是移位方向不同。

enter image description here

使用十進制23很好來理解。23除以10,丟棄最后的數字(3是余數),商為2。 與此類似的是乘法。比如乘以4,僅需將數字左移2位,最低兩位被置0。就像3乘以100—僅僅在最后補兩個0就行了。

17.3.2 ARM + Optimizing Xcode (LLVM) + ARM mode

Listing 17.21: Optimizing Xcode (LLVM) + ARM mode

#!bash
        MOV R1, R0
        MOV R0, #0
        MOV R2, #1
        MOV R3, R0
loc_2E54
        TST R1, R2,LSL R3       ; set flags according to R1 & (R2<<R3)
        ADD R3, R3, #1      ; R3++
        ADDNE R0, R0, #1        ; if ZF flag is cleared by TST, R0++
        CMP R3, #32
        BNE loc_2E54
        BX LR

TST類似于x86下的TEST指令。 正如我前面提到的(14.2.1),ARM模式下沒有單獨的移位指令。對于用作修飾的LSL(邏輯左移)、LSR(邏輯右移)、ASR(算術右移)、ROR(循環右移)和RRX(帶擴展的循環右移指令),需要與MOV,TST,CMP,ADD,SUB,RSB結合來使用6。 這些修飾指令被定義,第二個操作數指定移動的位數。 因此“TST R1, R2,LSL R3”指令所做的工作為????1 ∧ (????2 ? ????3).

17.3.3 ARM + Optimizing Xcode (LLVM) + thumb-2 mode

幾乎一樣,只是這里使用LSL.W/TST指令而不是只有TST。因為Thumb模式下TST沒有定義修飾符LSL。

#!bash
    MOV     R1, R0
    MOVS    R0, #0
    MOV.W   R9, #1
    MOVS    R3, #0
loc_2F7A
    LSL.W   R2, R9, R3
    TST     R2, R1
    ADD.W   R3, R3, #1
    IT NE
    ADDNE   R0, #1
    CMP     R3, #32
    BNE     loc_2F7A
    BX      LR

17.4 CRC32 calculation example

這是非常流行的CRC32哈希散列計算7。

#!cpp
/* By Bob Jenkins, (c) 2006, Public Domain */
#include <stdio.h>
#include <stddef.h>
#include <string.h>
typedef unsigned long ub4;
typedef unsigned char ub1;
static const ub4 crctab[256] = {
    0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
    0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
    0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
    0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
    0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
    0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
    0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
    0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
    0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
    0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
    0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
    0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
    0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
    0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
    0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
    0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
    0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
    0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
    0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
    0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
    0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
    0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
    0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
    0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
    0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
    0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
    0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
    0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
    0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
    0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
    0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
    0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
    0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
    0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
    0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
    0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
    0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
    0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
    0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
    0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
    0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
    0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
    0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d,
};
/* how to derive the values in crctab[] from polynomial 0xedb88320 */
void build_table()
{
ub4 i, j;
for (i=0; i<256; ++i) {
    j = i;
    j = (j>>1) ^ ((j&1) ? 0xedb88320 : 0);
    j = (j>>1) ^ ((j&1) ? 0xedb88320 : 0);
    j = (j>>1) ^ ((j&1) ? 0xedb88320 : 0);
    j = (j>>1) ^ ((j&1) ? 0xedb88320 : 0);
    j = (j>>1) ^ ((j&1) ? 0xedb88320 : 0);
    j = (j>>1) ^ ((j&1) ? 0xedb88320 : 0);
    j = (j>>1) ^ ((j&1) ? 0xedb88320 : 0);
    j = (j>>1) ^ ((j&1) ? 0xedb88320 : 0);
    printf("0x%.8lx, ", j);
    if (i%6 == 5) printf("
");
 }
}
/* the hash function */
ub4 crc(const void *key, ub4 len, ub4 hash)
{
    ub4 i;
    const ub1 *k = key;
    for (hash=len, i=0; i<len; ++i)
        hash = (hash >> 8) ^ crctab[(hash & 0xff) ^ k[i]];
    return hash;
}

/* To use, try "gcc -O crc.c -o crc; crc < crc.c" */
int main()
{
    char s[1000];
    while (gets(s)) printf("%.8lx
", crc(s, strlen(s), 0));
    return 0;
}

我們只關心crc()函數。注意for()語句兩個循環初始化:hash=len,i=0。標準C/C++允許這樣做。循環體內通常需要使用兩個初始化部分。 讓我們用MSVC優化(/Ox)。為了簡潔,僅列出crc()函數的代碼,包括我做的注釋。

#!bash
 key$ = 8               ; size = 4
_len$ = 12              ; size = 4
_hash$ = 16             ; size = 4
_crc PROC
    mov     edx, DWORD PTR _len$[esp-4]
    xor     ecx, ecx    ; i will be stored in ECX
    mov     eax, edx
    test    edx, edx
    jbe     SHORT [email protected]
    push    ebx
    push    esi
    mov     esi, DWORD PTR _key$[esp+4] ; ESI = key
    push    edi
[email protected]:

; work with bytes using only 32-bit registers. byte from address key+i we store into EDI

    movzx   edi, BYTE PTR [ecx+esi]
    mov     ebx, eax ; EBX = (hash = len)
    and     ebx, 255 ; EBX = hash & 0xff
; XOR EDI, EBX (EDI=EDI^EBX) - this operation uses all 32 bits of each register
; but other bits (8-31) are cleared all time, so it’s OK
; these are cleared because, as for EDI, it was done by MOVZX instruction above
; high bits of EBX was cleared by AND EBX, 255 instruction above (255 = 0xff)

    xor     edi, ebx

; EAX=EAX>>8; bits 24-31 taken "from nowhere" will be cleared

        shr     eax, 8

; EAX=EAX^crctab[EDI*4] - choose EDI-th element from crctab[] table
    xor     eax, DWORD PTR _crctab[edi*4]
    inc     ecx         ; i++
    cmp     ecx, edx ; i<len ?
    jb      SHORT [email protected] ; yes
    pop     edi
    pop     esi
    pop     ebx
[email protected]:
    ret 0
_crc ENDP    

我們來看GCC 4.4.1優化后的代碼:

#!bash
    public crc
crc     proc near
key     = dword ptr 8
hash    = dword ptr 0Ch
push    ebp
xor     edx, edx
mov     ebp, esp
push    esi
mov     esi, [ebp+key]
push    ebx
mov     ebx, [ebp+hash]
test    ebx, ebx
mov     eax, ebx
jz      short loc_80484D3
nop                 ; padding
lea     esi, [esi+0]        ; padding; ESI doesn’t changing here
loc_80484B8:
mov     ecx, eax        ; save previous state of hash to ECX
xor     al, [esi+edx]       ; AL=*(key+i)
add     edx, 1          ; i++
shr     ecx, 8          ; ECX=hash>>8
movzx   eax, al         ; EAX=*(key+i)
mov     eax, dword ptr ds:crctab[eax*4]     ; EAX=crctab[EAX]
xor     eax, ecx        ; hash=EAX^ECX
cmp     ebx, edx
ja      short loc_80484B8
loc_80484D3:
    pop ebx
    pop esi
    pop ebp
    retn
crc endp

GCC在循環開始的時候通過填入NOP和lea esi,esi+0來按8字節對齊。更多信息請閱讀npad小結(64)。

您的支持將鼓勵我們繼續創作!

[微信] 掃描二維碼打賞

[支付寶] 掃描二維碼打賞