# 第13章 strlen() 現在，讓我們再看一眼循環結構。通常，strlen（）函數是由while（）來實現的。這就是MSVC標準庫中strlen的做法： ``` #!cpp int my_strlen (const char * str) { const char *eos = str; while( *eos++ ) ; return( eos - str - 1 ); } int main() { // test return my_strlen("hello!"); }; ``` ## 13.1 x86 ### 13.1.1 無優化的 MSVC 讓我們編譯一下： ``` #!bash _eos$ = -4 ; size = 4 _str$ = 8 ; size = 4 _strlen PROC push ebp mov ebp, esp push ecx mov eax, DWORD PTR _str$[ebp] ; place pointer to string from str mov DWORD PTR _eos$[ebp], eax ; place it to local varuable eos $LN2@strlen_: mov ecx, DWORD PTR _eos$[ebp] ; ECX=eos ; take 8-bit byte from address in ECX and place it as 32-bit value to EDX with sign extension movsx edx, BYTE PTR [ecx] mov eax, DWORD PTR _eos$[ebp] ; EAX=eos add eax, 1 ; increment EAX mov DWORD PTR _eos$[ebp], eax ; place EAX back to eos test edx, edx ; EDX is zero? je SHORT $LN1@strlen_ ; yes, then finish loop jmp SHORT $LN2@strlen_ ; continue loop $LN1@strlen_: ; here we calculate the difference between two pointers mov eax, DWORD PTR _eos$[ebp] sub eax, DWORD PTR _str$[ebp] sub eax, 1 ; subtract 1 and return result mov esp, ebp pop ebp ret 0 _strlen_ ENDP ``` 我們看到了兩個新的指令：MOVSX（見13.1.1節）和TEST。 關于第一個：MOVSX用來從內存中取出字節然后把它放到一個32位寄存器中。MOVSX意味著MOV with Sign-Extent（帶符號擴展的MOV操作）。MOVSX操作下，如果復制源是負數，從第8到第31的位將被設為1，否則將被設為0。 現在解釋一下為什么要這么做。 C/C++標準將char（譯注：1字節）類型定義為有符號的。如果我們有2個值，一個是char，另一個是int（int也是有符號的），而且它的初值是-2（被編碼為0xFE），我們將這個值拷貝到int（譯注：一般是4字節）中時，int的值將是0x000000FE，這時，int的值將是254而不是-2。因為在有符號數中，-2被編碼為0xFFFFFFFE。 所以，如果我們需要將0xFE從char類型轉換為int類型，那么，我們就需要識別它的符號并擴展它。這就是MOVSX所做的事情。 請參見章節“有符號數表示方法”。（35章） 我不太確定編譯器是否需要將char變量存儲在EDX中，它可以使用其中8位（我的意思是DL部分）。顯然，編譯器的寄存器分配器就是這么工作的。 然后我們可以看到TEST EDX, EDX。關于TEST指令，你可以閱讀一下位這一節（17章）。但是現在我想說的是，這個TEST指令只是檢查EDX的值是否等于0。 ### 13.1.2 無優化的 GCC 讓我們在GCC 4.4.1下測試： ``` #!bash public strlen strlen proc near eos = dword ptr -4 arg_0 = dword ptr 8 push ebp mov ebp, esp sub esp, 10h mov eax, [ebp+arg_0] mov [ebp+eos], eax loc_80483F0: mov eax, [ebp+eos] movzx eax, byte ptr [eax] test al, al setnz al add [ebp+eos], 1 test al, al jnz short loc_80483F0 mov edx, [ebp+eos] mov eax, [ebp+arg_0] mov ecx, edx sub ecx, eax mov eax, ecx sub eax, 1 leave retn strlen endp ``` 可以看到它的結果和MSVC幾乎相同，但是這兒我們可以看到它用MOVZX代替了MOVSX。 MOVZX代表著MOV with Zero-Extend（0位擴展MOV）。這個指令將8位或者16位的值拷貝到32位寄存器，然后將剩余位設置為0。事實上，這個指令比較方便的原因是它將兩條指令組合到了一起：xor eax,eax / mov al, [...]。 另一方面來說，顯然這里編譯器可以產生如下代碼： mov al, byte ptr [eax] / test al, al，這幾乎是一樣的，但是，EAX高位將還是會有隨機的數值存在。 但是我們想一想就知道了，這正是編譯器的劣勢所在——它不能產生更多能讓人容易理解的代碼。嚴格的說， 事實上編譯器也并沒有義務為人類產生易于理解的代碼。 還有一個新指令，SETNZ。這里，如果AL包含非0， test al, al將設置ZF標記位為0。 但是SETNZ中，如果ZF == 0（NZ的意思是非零，Not Zero），AL將設置為1。用自然語言描述一下，如果AL非0，我們就跳轉到loc_80483F0。編譯器生成了少量的冗余代碼，不過不要忘了我們已經把優化給關了。 ### 13.1.3 優化后的 MSVC 讓我們在MSVC 2012下編譯，打開優化選項/Ox： 清單13.1: MSVC 2010 /Ox /Ob0 ``` #!bash _str$ = 8 ; size = 4 _strlen PROC mov edx, DWORD PTR _str$[esp-4] ; EDX -> 指向字符的指針 mov eax, edx ; 移動到 EAX $LL2@strlen: mov cl, BYTE PTR [eax] ; CL = *EAX inc eax ; EAX++ test cl, cl ; CL==0? jne SHORT $LL2@strlen ; 否，繼續循環 sub eax, edx ; 計算指針差異 dec eax ; 遞減 EAX ret 0 _strlen ENDP ``` 現在看起來就更簡單點了。但是沒有必要去說編譯器能在這么小的函數里面，如此有效率的使用如此少的本地變量，特殊情況而已。 INC / DEC是遞增 / 遞減指令，或者換句話說，給變量加一或者減一。 ### 13.1.4 優化后的 MSVC + OllyDbg 我們可以在OllyDbg中試試這個（優化過的）例子。這兒有一個簡單的最初的初始化：圖13.1。 我們可以看到OllyDbg 找到了一個循環，然后為了方便觀看，OllyDbg把它們環繞在一個方格區域中了。在EAX上右鍵點擊，我們可以選擇“Follow in Dump”，然后內存窗口的位置將會跳轉到對應位置。我們可以在內存中看到這里有一個“hello！”的字符串。 在它之后至少有一個0字節，然后就是隨機的數據。 如果OllyDbg發現了一個寄存器是一個指向字符串的指針，那么它會顯示這個字符串。 讓我們按下F8（步過）多次，我們可以看到當前地址的游標將在循環體中回到開始的地方：圖13.2。我們可以看到EAX現在包含有字符串的第二個字符。 我們繼續按F8，然后執行完整個循環：圖13.3。我們可以看到EAX現在包含空字符（）的地址，也就是字符串的末尾。同時，EDX并沒有改變，所以它還是指向字符串的最開始的地方。現在它就可以計算這兩個寄存器的差值了。 然后SUB指令會被執行：圖13.4。 差值保存在EAX中，為7。 但是，字符串“hello!”的長度是6，這兒7是因為包含了末尾的。但是strlen（）函數必須返回非0部分字符串的長度，所以在最后還是要給EAX減去1，然后將它作為返回值返回，退出函數。  圖13.1： 第一次循環迭代起始位置  圖13.2：第二次循環迭代開始位置  圖13.3： 現在要計算二者的差了  圖13.4： EAX需要減一 ### 13.1.5 優化過的GCC 讓我們打開GCC 4.4.1的編譯優化選項（-O3）： ``` #!bash public strlen strlen proc near arg_0 = dword ptr 8 push ebp mov ebp, esp mov ecx, [ebp+arg_0] mov eax, ecx loc_8048418: movzx edx, byte ptr [eax] add eax, 1 test dl, dl jnz short loc_8048418 not ecx add eax, ecx pop ebp retn strlen endp ``` 這兒GCC和MSVC的表現方式幾乎一樣，除了MOVZX的表達方式。 但是，這里的MOVZX可能被替換為`mov dl, byte ptr [eax]`。 可能是因為對GCC編譯器來說，生成此種代碼會讓它更容易記住整個寄存器已經分配給char變量了，然后因此它就可以確認高位在任何時候都不會有任何干擾數據的存在了。 之后，我們可以看到新的操作符NOT。這個操作符把操作數的所有位全部取反。可以說，它和XOR ECX, 0fffffffh效果是一樣的。NOT和接下來的ADD指令計算差值然后將結果減一。在最開始的ECX出存儲了str的指針，翻轉之后會將它的值減一。 請參考“有符號數的表達方式”。（第35章） 換句話說，在函數最后，也就是循環體后面其實是做了這樣一個操作： ``` ecx=str; eax=eos; ecx=(-ecx)-1; eax=eax+ecx return eax ``` 這樣做其實幾乎相等于： ``` ecx=str; eax=eos; eax=eax-ecx; eax=eax-1; return eax ``` 為什么GCC會認為它更棒呢？我不能確定，但是我確定上下兩種方式都應該有相同的效率。 ## 13.2 ARM ### 13.2.1 無優化 Xcode (LLVM) + ARM模式 清單13.2: 無優化的Xcode（LLVM）+ ARM模式 ``` #!bash _strlen eos = -8 str = -4 SUB SP, SP, #8 ; allocate 8 bytes for local variables STR R0, [SP,#8+str] LDR R0, [SP,#8+str] STR R0, [SP,#8+eos] loc_2CB8 ; CODE XREF: _strlen+28 LDR R0, [SP,#8+eos] ADD R1, R0, #1 STR R1, [SP,#8+eos] LDRSB R0, [R0] CMP R0, #0 BEQ loc_2CD4 B loc_2CB8 ; ---------------------------------------------------------------- loc_2CD4 ; CODE XREF: _strlen+24 LDR R0, [SP,#8+eos] LDR R1, [SP,#8+str] SUB R0, R0, R1 ; R0=eos-str SUB R0, R0, #1 ; R0=R0-1 ADD SP, SP, #8 ; deallocate 8 bytes for local variables BX LR ``` 無優化的LLVM生成了太多的代碼，但是，這里我們可以看到函數是如何在棧上處理本地變量的。我們的函數里只有兩個本地變量，eos和str。 在這個IDA生成的列表里，我把var_8和var_4命名為了eos和str。 所以，第一個指令只是把輸入的值放到str和eos里。 循環體從loc_2CB8標簽處開始。 循環體的前三個指令（LDR、ADD、STR）將eos的值載入R0，然后值會加一，然后存回棧上本地變量eos。 下一條指令“LDRSB R0, [R0]”（Load Register Signed Byte，讀取寄存器有符號字）將從R0地址處讀取一個字節，然后把它符號擴展到32位。這有點像是x86里的MOVSX函數（見13.1.1節）。因為char在C標準里面是有符號的，所以編譯器也把這個字節當作有符號數。我已經在13.1.1節寫了這個，雖然那里是相對x86來說的。 需要注意的是，在ARM里會單獨分割使用8位或者16位或者32位的寄存器，就像x86一樣。顯然，這是因為x86有一個漫長的歷史上的兼容性問題，它需要和他的前身：16位8086處理器甚至8位的8080處理器相兼容。但是ARM確是從32位的精簡指令集處理器中發展而成的。因此，為了處理單獨的字節，程序必須使用32位的寄存器。 所以LDRSB一個接一個的將符號從字符串內載入R0，下一個CMP和BEQ指令將檢查是否讀入的符號是0，如果不是0，控制流將重新回到循環體，如果是0，那么循環結束。 在函數最后，程序會計算eos和str的差，然后減一，返回值通過R0返回。 注意：這個函數并沒有保存寄存器。這是因為由ARM調用時的轉換，R0-R3寄存器是“臨時寄存器”（scratch register），它們只是為了傳遞參數用的，它們的值并不會在函數退出后保存，因為這時候函數也不會再使用它們。因此，它們可以被我們用來做任何事情，而這里其他寄存器都沒有使用到，這也就是為什么我們的棧上事實上什么都沒有的原因。因此，控制流可以通過簡單跳轉（BX）來返回調用的函數，地址存在LR寄存器中。 ### 13.2.2 優化后的 Xcode (LLVM) + thumb 模式 清單13.3: 優化后的 Xcode（LLVM） + thumb模式 ``` #!bash _strlen MOV R1, R0 loc_2DF6 ; CODE XREF: _strlen+8 LDRB.W R2, [R1],#1 CMP R2, #0 BNE loc_2DF6 MVNS R0, R0 ADD R0, R1 BX LR ``` 在優化后的LLVM中，為eos和str準備的棧上空間可能并不會分配，因為這些變量可以永遠正確的存儲在寄存器中。在循環體開始之前，str將一直存儲在R0中，eos在R1中。 “LDRB.W R2, [R1],#1”指令從R1內存中讀取字節到R2里，按符號擴展成32位的值，但是不僅僅這樣。 在指令最后的#1被稱為“后變址”（Post-indexed address），這代表著在字節讀取之后，R1將會加一。這個在讀取數組時特別方便。 在x86中這里并沒有這樣的地址存取方式，但是在其他處理器中卻是有的，甚至在PDP-11里也有。這是PDP-11中一個前增、后增、前減、后減的例子。這個很像是C語言（它是在PDP-11上開發的）中“罪惡的”語句形式_ptr++、_++ptr、_ptr--、_--ptr。順帶一提，C的這個語法真的很難讓人記住。下為具體敘述：  C語言作者之一的Dennis Ritchie提到了這個可能是由于另一個作者Ken Thompson開發的功能，因此這個處理器特性在PDP-7中最早出現了（參考資料[28][29]）。因此，C語言編譯器將在處理器支持這種指令時使用它。 然后可以指出的是循環體的CMP和BNE，這兩個指令將一直處理到字符串中的0出現為止。 MVNS（翻轉所有位，也即x86的NOT）指令和ADD指令計算cos-str-1.事實上，這兩個指令計算出R0=str+cos。這和源碼里的指令效果一樣，為什么他要這么做的原因我在13.1.5節已經說過了。 顯然，LLVM，就像是GCC一樣，會把代碼變得更短或者更快。 ### 13.2.3 優化后的 Keil + ARM 模式 清單13.4: 優化后的 Keil + ARM模式 ``` #!bash _strlen MOV R1, R0 loc_2C8 ; CODE XREF: _strlen+14 LDRB R2, [R1],#1 CMP R2, #0 SUBEQ R0, R1, R0 SUBEQ R0, R0, #1 BNE loc_2C8 BX LR ``` 這個和我們之前看到的幾乎一樣，除了str-cos-1這個表達式并不在函數末尾計算，而是被調到了循環體中間。 可以回憶一下-EQ后綴，這個代表指令僅僅會在CMP執行之前的語句互相相等時才會執行。因此，如果R0的值是0，兩個SUBEQ指令都會執行，然后結果會保存在R0寄存器中。