從簡單的算法初探匯編語言
不忽視匯編
較于我們?nèi)粘＝佑|的高級語言，諸如C語言，c++，java等等，匯編語言是更接近機器的語言，它的常用操作簡單到把一個數(shù)值（立即數(shù)，寄存器數(shù)或者存儲器數(shù)據(jù)）加載到寄存器，正是這樣，所以讓匯編完成一個程序任務(wù)，過程會比較晦澀；高級語言隱藏了很多的機器細節(jié)（比如過程（函數(shù)）棧幀的初始化，以及過程結(jié)束時棧幀的恢復(fù)），代碼清晰易懂。
真佩服六七十年代那些大牛們，都是怎么過來的...膜拜膜拜。寫一個100以內(nèi)整數(shù)的和，即使有充分的匯編文檔，這也足夠折騰我一陣子，太惡心了。但是了解匯編的行為方式和其中的一些重要細節(jié)，有助于理解計算機軟件和硬件的工作方式。我就一個簡單的算法來認識一下匯編。
過程匯編前奏
過程可以理解為c中的函數(shù)，當(dāng)調(diào)用者（caller）調(diào)用被調(diào)用者（be caller）的時候，系統(tǒng)會為被調(diào)用者在棧內(nèi)分配空間，這個空間就稱為棧幀。棧的結(jié)構(gòu)大概如下：
程序棧是向低地址生長的棧，與數(shù)據(jù)結(jié)構(gòu)當(dāng)中的棧結(jié)構(gòu)類似，有后進先出的性質(zhì)，寄存器%esp（stack pointer）保存棧頂指針的地址，寄存器%ebp（** pointer）保存幀指針的地址。 程序執(zhí)行的時候，棧指針可以移動，以便增大或者縮小程序棧的空間，而幀指針是固定的，因為大多數(shù)程序棧中存儲的數(shù)據(jù)都是相對于幀指針的（幀指針+偏移量）。
當(dāng)調(diào)用者調(diào)用另一個過程的時候：
首先，如果這個被調(diào)用過程如果有參數(shù)的話，調(diào)用的棧幀中會構(gòu)造這些參數(shù)，并存入到調(diào)用者的棧幀中（所以上面的圖參數(shù)n...參數(shù)1，就是這個原因了）；
將返回地址入棧。返回地址是當(dāng)被調(diào)用過程執(zhí)行完畢之后，調(diào)用者應(yīng)該繼續(xù)執(zhí)行的指令地址；它屬于調(diào)用者棧幀的部分，形成了調(diào)用者棧幀的末尾
到這一步就進入了被調(diào)用者的棧幀了，所謂當(dāng)前棧幀。保存調(diào)用者的幀指針，以便在之后找回調(diào)用者的程序棧；
最后進入程序執(zhí)行，一般過程會sub 0xNh %esp來分配當(dāng)前程序棧的大小，用來存取臨時變量啊，暫存寄存器的值啊等等。
如果被調(diào)用者又要調(diào)用另一個過程，回到第一步即可；
當(dāng)過程結(jié)束之時，會將棧指針，幀指針恢復(fù)，經(jīng)常會在反匯編中看到如下：
mov %esp,%ebp
pop %ebp
同時，返回地址會被恢復(fù)到PC。
這時回到了打調(diào)用者應(yīng)該繼續(xù)執(zhí)行的地方。
上面的文字可以更概括，反匯編一個過程（函數(shù)）會有建立（初始化），主體（執(zhí)行），結(jié)束（返回）。之前很容易把棧和堆搞混（不是數(shù)據(jù)結(jié)構(gòu)里面），找到一個好文章與大家分享：棧和堆的區(qū)別。據(jù)說被轉(zhuǎn)了無數(shù)次了，說明寫的不錯。 過程調(diào)用和返回在匯編語言中分別用call和ret（return）來實現(xiàn)。call和ret的做法不是很透明，
call將返回地址入棧，并將PC跳轉(zhuǎn)到被調(diào)用過程的起始地址；
ret與call相反，從棧中彈出返回地址，并跳轉(zhuǎn)PC。
具體看圖：
關(guān)于匯編代碼格式
匯編代碼最為常見的是ATT和intel匯編代碼格式，ATT應(yīng)該較為古老，但卻是GCC，OBJDUMP的默認格式。需要注意的是在帶有多個操作數(shù)的指令的情況下，列出操作數(shù)順序兩者是相反的，所以在思路上很容易混淆。例如實現(xiàn)%esp→%eax，有如下區(qū)別。
- #intel
- moveax,esp
- #ATT
- movl %esp,%eax
因為受到書本的影響，所以我習(xí)慣在寄存器前加上“%”，并且我更偏好ATT格式的匯編代碼。
反匯編具體分析
（下面的程序棧圖，我把參數(shù)入棧我在標明“參數(shù)i=？”，這可能會有點疑惑，如果“參數(shù)x=？”這樣會更好，:)）
有一個簡單程序，先不管它實現(xiàn)了什么功能，看下去，絕對會有收獲的。給出的c代碼是：
- #include <iostream>
- using namespace std
- intfun(unsigned intx)
- {
- if(x == 0)
- return 0
- unsigned intnx = x>>1
- intrv = fun(nx)
- return (x &0x01)+rv
- }
- intmain()
- {
- unsigned inti = 100
- fun(i)
- return 0
- }
在Visual Studio 2008下debug查看匯編代碼有如下反匯編代碼，因為晦澀，所以摘抄了如下：
- 004110E6 jmp fun (4113A0h)
- intfun(unsigned intx)
- {
- 004113A0 push ebp
- 004113A1 mov ebp,esp
- 004113A3 sub esp,0D8h
- 004113A9 push ebx
- 004113AA push esi
- 004113AB push edi
- 004113AC lea edi,[ebp-0D8h]
- 004113B2 mov ecx,36h
- 004113B7 mov eax,0CCCCCCCCh
- 004113BC repstos dword ptr es:[edi]
- if(x == 0)
- 004113BE cmp dword ptr [x],0
- 004113C2 jne fun+28h (4113C8h)
- return 0
- 004113C4 xor eax,eax
- 004113C6 jmp fun+48h (4113E8h)
- unsigned intnx = x>>1
- 004113C8 mov eax,dword ptr [x]
- 004113CB shr eax,1
- 004113CD mov dword ptr [nx],eax
- intrv = fun(nx)
- 004113D0 mov eax,dword ptr [nx]
- 004113D3 push eax
- 004113D4 call fun (4110E6h)
- 004113D9 add esp,4
- 004113DC mov dword ptr [rv],eax
- return (x &0x01)+rv
- 004113DF mov eax,dword ptr [x]
- 004113E2 and eax,1
- 004113E5 add eax,dword ptr [rv]
- }
- 004113E8 pop edi
- 004113E9 pop esi
- 004113EA pop ebx
- 004113EB add esp,0D8h
- 004113F1 cmp ebp,esp
- 004113F3 call @ILT+315(__RTC_CheckEsp) (411140h)
- 004113F8 mov esp,ebp
- 004113FA pop ebp
- 004113FB ret
- intmain()
- {
- 00411420 push ebp
- 00411421 mov ebp,esp
- 00411423 sub esp,0CCh
- 00411429 push ebx
- 0041142A push esi
- 0041142B push edi
- 0041142C lea edi,[ebp-0CCh]
- 00411432 mov ecx,33h
- 00411437 mov eax,0CCCCCCCCh
- 0041143C repstos dword ptr es:[edi]
- unsigned inti = 12
- 0041143E mov dword ptr [i],0Ch
- fun(i)
- 00411445 mov eax,dword ptr [i]
- 00411448 push eax
- 00411449 call fun (4110E6h)
- 0041144E add esp,4
- return 0
- 00411451 xor eax,eax
- }
- 00411453 pop edi
- 00411454 pop esi
- 00411455 pop ebx
- 00411456 add esp,0CCh
- 0041145C cmp ebp,esp
- 0041145E call @ILT+315(__RTC_CheckEsp) (411140h)
- 00411463 mov esp,ebp
- 00411465 pop ebp
- 00411466 ret
上面的代碼，在第一句就間接道明了fun的地址。可以看到在call fun之前會有一段準備：
- fun(i)
- 00411445 mov eax,dword ptr [i]
- 00411448 push eax
- 00411449 call fun (4110E6h)
- 0041144E add esp,4
00411445h的指令就將fun的參數(shù)（此時i=6，還記得上面的圖嗎，參數(shù)n-參數(shù)1）和返回地址入棧，然后PC跳至004110E6h，此時main的棧幀如下：
借助jmp跳至004113A0h，正式進入fun函數(shù)。fun內(nèi)首先保存了幀指針和被調(diào)用者保存寄存器和其他相關(guān)數(shù)據(jù)，只有當(dāng)參數(shù)x==0的時候才會終止函數(shù)的運行，故在遞歸調(diào)用（注意，是遞歸調(diào)用，而不是調(diào)用）fun之前（即call fun之前），有如下：
圖
所以，一直遞歸下去的話：
直到x==0，此時會進入if的分支執(zhí)行步驟。
- if(x == 0)
- 004113BE cmp dword ptr [x],0
- 004113C2 jne fun+28h (4113C8h)
- return 0
- 004113C4 xor eax,eax
- 004113C6 jmp fun+48h (4113E8h)
在匯編中，會用到異或xor邏輯運算來對一個寄存器清零（004113C4h地址的指令），由于x==0，PC跳至004113E8h，執(zhí)行返回。
- 004113E8 pop edi
- 004113E9 pop esi
- 004113EA pop ebx
- 004113EB add esp,0D8h
- 004113F1 cmp ebp,esp
- 004113F3 call @ILT+315(__RTC_CheckEsp) (411140h)
- 004113F8 mov esp,ebp
- 004113FA pop ebp
- 004113FB ret
在這里把被保存的寄存器值都彈出來，恢復(fù)棧歸位，留意其中針對%esp和%ebp的操作；執(zhí)行ret操作，返回，
程序繼續(xù)執(zhí)行：
- # intrv = fun(nx)
- #004113D0 mov eax,dword ptr [nx]
- #004113D3 push eax
- #004113D4 call fun (4110E6h)
- 004113D9 add esp,4
- 004113DC mov dword ptr [rv],eax
- rv = 0;
可以看到，處理器釋放了棧上的內(nèi)存（%esp+4，還記得嗎，棧是向低地址增長的），因為在call之前，也就是00411448h地址處，調(diào)用者也就是main函數(shù)將%eax參數(shù)入棧，接著fun退出之后，參數(shù)的內(nèi)存也就理所當(dāng)然的要釋放掉。聯(lián)想一下，如果參數(shù)有很多個，那么call之前就會有多個push，對應(yīng)的，call之后就會有“add %esp n”的操作將其釋放。接著將%eax（在寄存器是用習(xí)慣當(dāng)中，%eax經(jīng)常被用作返回值寄存器）的值給了rv，如此一來rv就順理成章地得到了fun的返回值。接下來：
- return (x &0x01)+rv
- 004113DF mov eax,dword ptr [x]
- 004113E2 and eax,1
- 004113E5 add eax,dword ptr [rv]
- %eax←(x&0x01)+rv = 0x01&0x01 + 0 = 1;（提示：從這里開始體會fun的功能）
簡單的將x&0x01+rv后送入%eax（記得嗎，%eax經(jīng)常被用作返回值寄存器），此時可能會有疑問，x是從哪里來的，答案是x存在調(diào)用者的棧幀內(nèi)，而非被調(diào)用者的棧幀，因為x是函數(shù)的一個參數(shù)，dword ptr [x]應(yīng)該就是對讀取了調(diào)用者棧幀中的x參數(shù)。該是恢復(fù)棧的時候了：
- 004113E8 pop edi
- 004113E9 pop esi
- 004113EA pop ebx
- 004113EB add esp,0D8h
- 004113F1 cmp ebp,esp
- 004113F3 call @ILT+315(__RTC_CheckEsp) (411140h)
- 004113F8 mov esp,ebp
- 004113FA pop ebp
- 004113FB ret
恢復(fù)棧幀，執(zhí)行ret，如圖：
fun又成功返回了，程序繼續(xù)：
- # intrv = fun(nx)
- #004113D0 mov eax,dword ptr [nx]
- #004113D3 push eax
- #004113D4 call fun (4110E6h)
- 004113D9 add esp,4
- 004113DC mov dword ptr [rv],eax
- rv = %eax = 1;
又回到了剛才走過的地方，但是數(shù)據(jù)有異。接下來程序執(zhí)行return退出：
- return (x &0x01)+rv
- 004113DF mov eax,dword ptr [x]
- 004113E2 and eax,1
- 004113E5 add eax,dword ptr [rv]
- %eax←(x&0x01)+rv = 0x3&0x01 + 1 = 2;又該是ret的時候了，恢復(fù)棧：
- 004113E8 pop edi
- 004113E9 pop esi
- 004113EA pop ebx
- 004113EB add esp,0D8h
- 004113F1 cmp ebp,esp
- 004113F3 call @ILT+315(__RTC_CheckEsp) (411140h)
- 004113F8 mov esp,ebp
- 004113FA pop ebp
- 004113FB ret
棧幀結(jié)構(gòu)如圖：
還差一次，返回之后程序繼續(xù)執(zhí)行：
- # intrv = fun(nx)
- #004113D0 mov eax,dword ptr [nx]
- #004113D3 push eax
- #004113D4 call fun (4110E6h)
- 004113D9 add esp,4
- 004113DC mov dword ptr [rv],eax
- rv = %eax = 2;
接下來程序return退出（不累贅了）：
- return (x &0x01)+rv
- 004113DF mov eax,dword ptr [x]
- 004113E2 and eax,1
- 004113E5 add eax,dword ptr [rv]
- 004113E8 pop edi
- 004113E9 pop esi
- 004113EA pop ebx
- 004113EB add esp,0D8h
- 004113F1 cmp ebp,esp
- 004113F3 call @ILT+315(__RTC_CheckEsp) (411140h)
- 004113F8 mov esp,ebp
- 004113FA pop ebp
- 004113FB ret
至此，程序完全退出了fun的遞歸過程，回到了主函數(shù)main，main也有自己的棧幀，因為main也是一個函數(shù)。下圖：
- # fun(i)
- #00411445 mov eax,dword ptr [i]
- #00411448 push eax
- #00411449 call fun (4110E6h)
- 0041144E add esp,4
- return 0
- 00411451 xor eax,eax
0x0041144E處，add %esp,4，目的是釋放一開始入棧的fun的參數(shù)，而主函數(shù)返回0（return 0），也是用到了異或邏輯運算xor來講%eax清零。
到這里，相信有點明白了，在遞歸調(diào)用過程中，程序棧是如何變化的，并且上面的函數(shù)計算參數(shù)i中位的和。
收獲
發(fā)現(xiàn)這樣一個小小的遞歸程序，分析起它反匯編如有一種返璞歸真的感覺，對理解“遞歸調(diào)用”會更為清晰的思路。縱觀上面的分析，遞歸調(diào)用雖然是算法中解決問題常用的方法，但是它對付起龐大遞歸次數(shù)的程序來說（上面因為分析所以選取的遞歸次數(shù)較少），非常消耗內(nèi)存。 所以在寫程序的時候，在時間和空間的消耗抉擇上，需要謹慎。通過學(xué)習(xí)匯編和反匯編代碼的分析，將更了解機器的行為，從而寫出更為高效的代碼。
文章有點長，歡迎討論。
原文鏈接：http://www.cnblogs.com/daoluanxiaozi/archive/2012/02/08/2340530.html
【編輯推薦】
