# 第12章 循環結構 ## 12.1 x86 在x86指令集中，有一些獨特的LOOP指令，它們會檢查ECX中的值，如果它不是0的話，它會逐漸遞減ECX的值（減一），然后把控制流傳遞給LOOP操作符提供的標簽處。也許，這個指令并不是多方便，所以，我沒有看到任何現代編譯器自動使用它。如果你看到哪里的代碼用了這個結構，那它很有可能是程序員手寫的匯編代碼。 順帶一提，作為家庭作業，你可以試著解釋以下為什么這個指令如此不方便。 C/C++循環操作是由for()、while()、do/while()命令發起的。 讓我們從for()開始吧。 這個命令定義了循環初始值（為循環計數器設置初值），循環條件（比如，計數器是否大于一個閾值？），以及在每次迭代（增/減）時和循環體中做什么。 ``` for (初始化； 條件； 每次迭代時執行的語句) ｛ 循環體； ｝ ``` 所以，它生成的代碼也將被考慮為4個部分。 讓我們從一個簡單的例子開始吧： ``` #!cpp #include <stdio.h> void f(int i) { printf ("f(%d) ", i); }; int main() { int i; for (i=2; i<10; i++) f(i); return 0; }; ``` 反匯編結果如下（MSVC 2010）： 清單12.1: MSVC 2010 ``` #!bash _i$ = -4 _main PROC push ebp mov ebp, esp push ecx mov DWORD PTR _i$[ebp], 2 ; loop initialization jmp SHORT $LN3@main $LN2@main: mov eax, DWORD PTR _i$[ebp] ; here is what we do after each iteration: add eax, 1 ; add 1 to i value mov DWORD PTR _i$[ebp], eax $LN3@main: cmp DWORD PTR _i$[ebp], 10 ; this condition is checked *before* each iteration jge SHORT $LN1@main ; if i is biggest or equals to 10, let’s finish loop mov ecx, DWORD PTR _i$[ebp] ; loop body: call f(i) push ecx call _f add esp, 4 jmp SHORT $LN2@main ; jump to loop begin $LN1@main: ; loop end xor eax, eax mov esp, ebp pop ebp ret 0 _main ENDP ``` 看起來沒什么特別的。 GCC 4.4.1生成的代碼也基本相同，只有一些微妙的區別。 清單12.1: GCC 4.4.1 ``` #!bash main proc near ; DATA XREF: _start+17 var_20 = dword ptr -20h var_4 = dword ptr -4 push ebp mov ebp, esp and esp, 0FFFFFFF0h sub esp, 20h mov [esp+20h+var_4], 2 ; i initializing jmp short loc_8048476 loc_8048465: mov eax, [esp+20h+var_4] mov [esp+20h+var_20], eax call f add [esp+20h+var_4], 1 ; i increment loc_8048476: cmp [esp+20h+var_4], 9 jle short loc_8048465 ; if i<=9, continue loop mov eax, 0 leave retn main endp ``` 現在，讓我們看看如果我們打開了優化開關會得到什么結果（/Ox）： 清單12.3: 優化后的 MSVC ``` #!bash _main PROC push esi mov esi, 2 $LL3@main: push esi call _f inc esi add esp, 4 cmp esi, 10 ; 0000000aH jl SHORT $LL3@main xor eax, eax pop esi ret 0 _main ENDP ``` 要說它做了什么，那就是：本應在棧上分配空間的變量i被移動到了寄存器ESI里面。因為我們這樣一個小函數并沒有這么多的本地變量，所以它才可以這么做。 這么做的話，一個重要的條件是函數f（）不能改變ESI的值。我們的編譯器在這里倒是非常確定。假設編譯器決定在f（）中使用ESI寄存器的話，ESI的值將在函數的初始化階段被壓入棧保存，并且在函數的收尾階段將其彈出（注：即還原現場，保證程序片段執行前后某個寄存器值不變）。這個操作有點像函數開頭和結束時的PUSH ESI/ POP ESI操作對。 讓我們試一試開啟了最高優化的GCC 4.4.1（-03優化）。 清單12.4: 優化后的GCC 4.4.1 ``` #!bash main proc near var_10 = dword ptr -10h push ebp mov ebp, esp and esp, 0FFFFFFF0h sub esp, 10h mov [esp+10h+var_10], 2 call f mov [esp+10h+var_10], 3 call f mov [esp+10h+var_10], 4 call f mov [esp+10h+var_10], 5 call f mov [esp+10h+var_10], 6 call f mov [esp+10h+var_10], 7 call f mov [esp+10h+var_10], 8 call f mov [esp+10h+var_10], 9 call f xor eax, eax leave retn main endp ``` GCC直接把我們的循環給分解成順序結構了。 循環分解（Loop unwinding）對這些沒有太多迭代次數的循環結構來說是比較有利的，移除所有循環結構之后程序的效率會得到提升。但是，這樣生成的代碼明顯會變得很大。 好的，現在我們把循環的最大值改為100。GCC現在生成如下： 清單12.5: GCC ``` #!bash public main main proc near var_20 = dword ptr -20h push ebp mov ebp, esp and esp, 0FFFFFFF0h push ebx mov ebx, 2 ; i=2 sub esp, 1Ch nop ; aligning label loc_80484D0 (loop body begin) by 16-byte border loc_80484D0: mov [esp+20h+var_20], ebx ; pass i as first argument to f() add ebx, 1 ; i++ call f cmp ebx, 64h ; i==100? jnz short loc_80484D0 ; if not, continue add esp, 1Ch xor eax, eax ; return 0 pop ebx mov esp, ebp pop ebp retn main endp ``` 這時，代碼看起來非常像MSVC 2010開啟/Ox優化后生成的代碼。除了這兒它用了EBX來存儲變量i。 GCC也確信f（）函數中不會修改EBX的值，假如它要用到EBX的話，它也一樣會在函數初始化和收尾時保存EBX和還原EBX，就像這里main（）函數做的事情一樣。 ### 12.1.1 OllyDbg 讓我們通過/Ox和/Ob0編譯程序，然后放到OllyDbg里面查看以下結果。 看起來OllyDbg能夠識別簡單的循環，然后把它們放在一塊，為了演示方便，大家可以看圖12.1。 通過跟蹤代碼（F8， 步過）我們可以看到ESI是如何遞增的。這里的例子是ESI = i = 6： 圖12.2。 9是i的最后一個循環制，這也就是為什么JL在遞增的最后不會觸發，之后函數結束，如圖12.3。  圖12.1： OllyDbg main（）開始  圖12.2： OllyDbg： 循環體剛剛遞增了i，現在i=6  圖12.3： OllyDbg中ESI=10，循環終止 ### 12.1.2 跟蹤 像我們所見的一樣，手動在調試器里面跟蹤代碼并不是一件方便的事情。這也就是我給自己寫了一個跟蹤程序的原因。 我在IDA中打開了編譯后的例子，然后找到了PUSH ESI指令（作用：給f（）傳遞唯一的參數）的地址，對我的機器來說是0x401026，然后我運行了跟蹤器： ``` #!bash tracer.exe -l:loops_2.exe bpx=loops_2.exe!0x00401026 ``` BPX的作用只是在對應地址上設置斷點然后輸出寄存器狀態。 在tracer.log中我看到執行后的結果： ``` #!bash PID=12884|New process loops_2.exe (0) loops_2.exe!0x401026 EAX=0x00a328c8 EBX=0x00000000 ECX=0x6f0f4714 EDX=0x00000000 ESI=0x00000002 EDI=0x00333378 EBP=0x0024fbfc ESP=0x0024fbb8 EIP=0x00331026 FLAGS=PF ZF IF (0) loops_2.exe!0x401026 EAX=0x00000005 EBX=0x00000000 ECX=0x6f0a5617 EDX=0x000ee188 ESI=0x00000003 EDI=0x00333378 EBP=0x0024fbfc ESP=0x0024fbb8 EIP=0x00331026 FLAGS=CF PF AF SF IF (0) loops_2.exe!0x401026 EAX=0x00000005 EBX=0x00000000 ECX=0x6f0a5617 EDX=0x000ee188 ESI=0x00000004 EDI=0x00333378 EBP=0x0024fbfc ESP=0x0024fbb8 EIP=0x00331026 FLAGS=CF PF AF SF IF (0) loops_2.exe!0x401026 EAX=0x00000005 EBX=0x00000000 ECX=0x6f0a5617 EDX=0x000ee188 ESI=0x00000005 EDI=0x00333378 EBP=0x0024fbfc ESP=0x0024fbb8 EIP=0x00331026 FLAGS=CF AF SF IF (0) loops_2.exe!0x401026 EAX=0x00000005 EBX=0x00000000 ECX=0x6f0a5617 EDX=0x000ee188 ESI=0x00000006 EDI=0x00333378 EBP=0x0024fbfc ESP=0x0024fbb8 EIP=0x00331026 FLAGS=CF PF AF SF IF (0) loops_2.exe!0x401026 EAX=0x00000005 EBX=0x00000000 ECX=0x6f0a5617 EDX=0x000ee188 ESI=0x00000007 EDI=0x00333378 EBP=0x0024fbfc ESP=0x0024fbb8 EIP=0x00331026 FLAGS=CF AF SF IF (0) loops_2.exe!0x401026 EAX=0x00000005 EBX=0x00000000 ECX=0x6f0a5617 EDX=0x000ee188 ESI=0x00000008 EDI=0x00333378 EBP=0x0024fbfc ESP=0x0024fbb8 EIP=0x00331026 FLAGS=CF AF SF IF (0) loops_2.exe!0x401026 EAX=0x00000005 EBX=0x00000000 ECX=0x6f0a5617 EDX=0x000ee188 ESI=0x00000009 EDI=0x00333378 EBP=0x0024fbfc ESP=0x0024fbb8 EIP=0x00331026 FLAGS=CF PF AF SF IF PID=12884|Process loops_2.exe exited. ExitCode=0 (0x0) ``` 我們可以看到ESI寄存器是如何從2變為9的。 甚至于跟蹤器可以收集某個函數調用內所有寄存器的值，所以它被叫做跟蹤器（a trace）。每個指令都會被它跟蹤上，所有感興趣的寄存器值都會被它提示出來，然后收集下來。 然后可以生成IDA能用的.idc-script。所以，在IDA中我知道了main()函數地址是0x00401020，然后我執行了： ``` #!bash tracer.exe -l:loops_2.exe bpf=loops_2.exe!0x00401020,trace:cc ``` bpf的意思是在函數上設置斷點。 結果是我得到了loops_2.exe.idc和loops_2.exe_clear.idc兩個腳本。我加載loops_2.idc到IDA中，然后可以看到圖12.4所示的內容。 我們可以看到ESI在循環體開始時從2變化為9，但是在遞增完之后，它的值從9（譯注：作者原文是3，但是揣測是筆誤，應為9。）變為了0xA（10）。我們也可以看到main（）函數結束時EAX被設置為了0。 編譯器也生成了loops_2.exe.txt，包含有每個指令執行了多少次和寄存器值的一些信息： 清單12.6: loops_2.exe.txt ``` #!bash 0x401020 (.text+0x20), e= 1 [PUSH ESI] ESI=1 0x401021 (.text+0x21), e= 1 [MOV ESI, 2] 0x401026 (.text+0x26), e= 8 [PUSH ESI] ESI=2..9 0x401027 (.text+0x27), e= 8 [CALL 8D1000h] tracing nested maximum level (1) reached, skipping this CALL 8D1000h=0x8d1000 0x40102c (.text+0x2c), e= 8 [INC ESI] ESI=2..9 0x40102d (.text+0x2d), e= 8 [ADD ESP, 4] ESP=0x38fcbc 0x401030 (.text+0x30), e= 8 [CMP ESI, 0Ah] ESI=3..0xa 0x401033 (.text+0x33), e= 8 [JL 8D1026h] SF=false,true OF=false 0x401035 (.text+0x35), e= 1 [XOR EAX, EAX] 0x401037 (.text+0x37), e= 1 [POP ESI] 0x401038 (.text+0x38), e= 1 [RETN] EAX=0 ``` 生成的代碼可以在此使用：  圖12.4： IDA加載了.idc-script之后的內容 ## 12.2 ARM ### 12.2.1 無優化 Keil + ARM模式 ``` #!bash main STMFD SP!, {R4,LR} MOV R4, #2 B loc_368 ; --------------------------------------------------------------------------- loc_35C ; CODE XREF: main+1C MOV R0, R4 BL f ADD R4, R4, #1 loc_368 ; CODE XREF: main+8 CMP R4, #0xA BLT loc_35C MOV R0, #0 LDMFD SP!, {R4,PC} ``` 迭代計數器i存儲到了R4寄存器中。 ``` “MOV R4,#2”初始化i。 “MOV R0, R4”和”BL f”指令組成循環體，第一個指令為f（）準備參數，第二個用來調用它。 “ADD R4, R4, #1”指令在每次迭代中為i加一。 “CMP R4，#0xA”將i和0xA（10）比較，下一個指令BLT（Branch Less Than，分支小于）將在i<10時跳轉。 否則， R0將會被寫入0（因為我們的函數返回0），然后函數執行終止。 ``` ### 12.2.2 優化后的 Keil + ARM模式 ``` #!bash _main PUSH {R4,LR} MOVS R4, #2 loc_132 ; CODE XREF: _main+E MOVS R0, R4 BL example7_f ADDS R4, R4, #1 CMP R4, #0xA BLT loc_132 MOVS R0, #0 POP {R4,PC} ``` 事實上，是一樣的。 ### 12.2.3 優化后的 Xcode（LLVM） + thumb-2 模式 ``` #!bash _main PUSH {R4,R7,LR} MOVW R4, #0x1124 ; "%d " MOVS R1, #2 MOVT.W R4, #0 ADD R7, SP, #4 ADD R4, PC MOV R0, R4 BLX _printf MOV R0, R4 MOVS R1, #3 BLX _printf MOV R0, R4 MOVS R1, #4 BLX _printf MOV R0, R4 MOVS R1, #5 BLX _printf MOV R0, R4 MOVS R1, #6 BLX _printf MOV R0, R4 MOVS R1, #7 BLX _printf MOV R0, R4 MOVS R1, #8 BLX _printf MOV R0, R4 MOVS R1, #9 BLX _printf MOVS R0, #0 POP {R4,R7,PC} ``` 事實上，printf是在我的f（）函數里調用的： ``` #!cpp void f(int i) { // do something here printf ("%d ", i); }; ``` 所以，LLVM不僅僅是拆解了（unroll）循環，而且還把我的短函數f（）給作為內聯函數看待了，這樣，它把它的函數體內插了8遍，而不是用一個循環來解決。對于我們這種簡短的函數來說，編譯器這樣做是有可能的。 ## 12.3 更多的一些事情 在編譯器生成的代碼里面，我們可以發現在i初始化之后，循環體并不會被執行，轉而是先檢查i的條件，在這之后才開始執行循環體。這么做是正確的，因為，如果循環條件在一開始就不滿足，那么循環體是不應當被執行的。比如，在下面的例子中，就可能出現這個情況： ``` #!cpp for (i=0; i<total_entries_to_process; i++) loop_body; ``` 如果 total_entries_to_process 等于0，那么循環體就不應該被執行。這就是為什么應當在循環體被執行之前檢查循環條件。 但是，開啟編譯器優化之后，如果編譯器確定不會出現上面這種情況的話，那么條件檢查和循環體的語句可能會互換（比如我們上面提到的簡單的例子以及Keil、Xcode（LLVM）、MSVC的優化模式）。