自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

從簡(jiǎn)單的算法初探匯編語言

作者：搗亂小子
開發(fā) 開發(fā)工具 算法
匯編語言是更接近機(jī)器的語言，它的常用操作簡(jiǎn)單到把一個(gè)數(shù)值（立即數(shù)，寄存器數(shù)或者存儲(chǔ)器數(shù)據(jù)）加載到寄存器。我們今天就要從簡(jiǎn)單的算法談起，看看什么是匯編語言。

　　不忽視匯編

　　較于我們?nèi)粘＝佑|的高級(jí)語言，諸如C語言，c++，java等等，匯編語言是更接近機(jī)器的語言，它的常用操作簡(jiǎn)單到把一個(gè)數(shù)值（立即數(shù)，寄存器數(shù)或者存儲(chǔ)器數(shù)據(jù)）加載到寄存器，正是這樣，所以讓匯編完成一個(gè)程序任務(wù)，過程會(huì)比較晦澀；高級(jí)語言隱藏了很多的機(jī)器細(xì)節(jié)（比如過程（函數(shù)）棧幀的初始化，以及過程結(jié)束時(shí)棧幀的恢復(fù)），代碼清晰易懂。

　　真佩服六七十年代那些大牛們，都是怎么過來的...膜拜膜拜。寫一個(gè)100以內(nèi)整數(shù)的和，即使有充分的匯編文檔，這也足夠折騰我一陣子，太惡心了。但是了解匯編的行為方式和其中的一些重要細(xì)節(jié)，有助于理解計(jì)算機(jī)軟件和硬件的工作方式。我就一個(gè)簡(jiǎn)單的算法來認(rèn)識(shí)一下匯編。

　　過程匯編前奏

　　過程可以理解為c中的函數(shù)，當(dāng)調(diào)用者（caller）調(diào)用被調(diào)用者（be caller）的時(shí)候，系統(tǒng)會(huì)為被調(diào)用者在棧內(nèi)分配空間，這個(gè)空間就稱為棧幀。棧的結(jié)構(gòu)大概如下：

　　程序棧是向低地址生長(zhǎng)的棧，與數(shù)據(jù)結(jié)構(gòu)當(dāng)中的棧結(jié)構(gòu)類似，有后進(jìn)先出的性質(zhì)，寄存器%esp（stack pointer）保存棧頂指針的地址，寄存器%ebp（** pointer）保存幀指針的地址。 程序執(zhí)行的時(shí)候，棧指針可以移動(dòng)，以便增大或者縮小程序棧的空間，而幀指針是固定的，因?yàn)榇蠖鄶?shù)程序棧中存儲(chǔ)的數(shù)據(jù)都是相對(duì)于幀指針的（幀指針+偏移量）。

　　當(dāng)調(diào)用者調(diào)用另一個(gè)過程的時(shí)候：

　　首先，如果這個(gè)被調(diào)用過程如果有參數(shù)的話，調(diào)用的棧幀中會(huì)構(gòu)造這些參數(shù)，并存入到調(diào)用者的棧幀中（所以上面的圖參數(shù)n...參數(shù)1，就是這個(gè)原因了）；

　　將返回地址入棧。返回地址是當(dāng)被調(diào)用過程執(zhí)行完畢之后，調(diào)用者應(yīng)該繼續(xù)執(zhí)行的指令地址；它屬于調(diào)用者棧幀的部分，形成了調(diào)用者棧幀的末尾

　　到這一步就進(jìn)入了被調(diào)用者的棧幀了，所謂當(dāng)前棧幀。保存調(diào)用者的幀指針，以便在之后找回調(diào)用者的程序棧；

　　最后進(jìn)入程序執(zhí)行，一般過程會(huì)sub 0xNh %esp來分配當(dāng)前程序棧的大小，用來存取臨時(shí)變量啊，暫存寄存器的值啊等等。

　　如果被調(diào)用者又要調(diào)用另一個(gè)過程，回到第一步即可；

　　當(dāng)過程結(jié)束之時(shí)，會(huì)將棧指針，幀指針恢復(fù)，經(jīng)常會(huì)在反匯編中看到如下：

　　mov %esp,%ebp

　　pop %ebp

　　同時(shí)，返回地址會(huì)被恢復(fù)到PC。

　　這時(shí)回到了打調(diào)用者應(yīng)該繼續(xù)執(zhí)行的地方。

　　上面的文字可以更概括，反匯編一個(gè)過程（函數(shù)）會(huì)有建立（初始化），主體（執(zhí)行），結(jié)束（返回）。之前很容易把棧和堆搞混（不是數(shù)據(jù)結(jié)構(gòu)里面），找到一個(gè)好文章與大家分享：棧和堆的區(qū)別。據(jù)說被轉(zhuǎn)了無數(shù)次了，說明寫的不錯(cuò)。 過程調(diào)用和返回在匯編語言中分別用call和ret（return）來實(shí)現(xiàn)。call和ret的做法不是很透明，

　　call將返回地址入棧，并將PC跳轉(zhuǎn)到被調(diào)用過程的起始地址；

　　ret與call相反，從棧中彈出返回地址，并跳轉(zhuǎn)PC。

　　具體看圖：

關(guān)于匯編代碼格式

　　匯編代碼最為常見的是ATT和intel匯編代碼格式，ATT應(yīng)該較為古老，但卻是GCC，OBJDUMP的默認(rèn)格式。需要注意的是在帶有多個(gè)操作數(shù)的指令的情況下，列出操作數(shù)順序兩者是相反的，所以在思路上很容易混淆。例如實(shí)現(xiàn)%esp→%eax，有如下區(qū)別。

  1. 　　#intel  
  2. 　　moveax,esp  
  3. 　　#ATT  
  4. 　　movl %esp,%eax 

 　　因?yàn)槭艿綍镜挠绊?，所以我?xí)慣在寄存器前加上“%”，并且我更偏好ATT格式的匯編代碼。

　　反匯編具體分析

　?。ㄏ旅娴某绦驐D，我把參數(shù)入棧我在標(biāo)明“參數(shù)i=？”，這可能會(huì)有點(diǎn)疑惑，如果“參數(shù)x=？”這樣會(huì)更好，:)）

　　有一個(gè)簡(jiǎn)單程序，先不管它實(shí)現(xiàn)了什么功能，看下去，絕對(duì)會(huì)有收獲的。給出的c代碼是：

  1. 　　#include <iostream>  
  2. 　　using namespace std  
  3. 　　intfun(unsigned intx)  
  4. 　　{  
  5. 　　if(x == 0)  
  6. 　　return 0  
  7. 　　unsigned intnx = x>>1  
  8. 　　intrv = fun(nx)  
  9. 　　return (x &0x01)+rv  
  10. 　　}  
  11. 　　intmain()  
  12. 　　{  
  13. 　　unsigned inti = 100  
  14. 　　fun(i)  
  15. 　　return 0  
  16. 　　} 

　　在Visual Studio 2008下debug查看匯編代碼有如下反匯編代碼，因?yàn)榛逎哉巳缦拢?/p> 

  1. 　　004110E6 jmp fun (4113A0h)  
  2. 　　intfun(unsigned intx)  
  3. 　{  
  4. 　　004113A0 push ebp  
  5. 　　004113A1 mov ebp,esp  
  6. 　　004113A3 sub esp,0D8h  
  7. 　　004113A9 push ebx  
  8. 　　004113AA push esi  
  9. 　　004113AB push edi  
  10. 　　004113AC lea edi,[ebp-0D8h]  
  11. 　　004113B2 mov ecx,36h  
  12. 　　004113B7 mov eax,0CCCCCCCCh  
  13. 　　004113BC repstos dword ptr es:[edi]  
  14. 　　if(x == 0)  
  15. 　　004113BE cmp dword ptr [x],0  
  16. 　　004113C2 jne fun+28h (4113C8h)  
  17. 　　return 0  
  18. 　　004113C4 xor eax,eax  
  19. 　　004113C6 jmp fun+48h (4113E8h)  
  20. 　　unsigned intnx = x>>1  
  21. 　　004113C8 mov eax,dword ptr [x]  
  22. 　　004113CB shr eax,1  
  23. 　　004113CD mov dword ptr [nx],eax  
  24. 　　intrv = fun(nx)  
  25. 　　004113D0 mov eax,dword ptr [nx]  
  26. 　　004113D3 push eax  
  27. 　　004113D4 call fun (4110E6h)  
  28. 　　004113D9 add esp,4  
  29. 　　004113DC mov dword ptr [rv],eax  
  30. 　　return (x &0x01)+rv  
  31. 　　004113DF mov eax,dword ptr [x]  
  32. 　　004113E2 and eax,1  
  33. 　　004113E5 add eax,dword ptr [rv]  
  34. 　　}  
  35. 　　004113E8 pop edi  
  36. 　　004113E9 pop esi  
  37. 　　004113EA pop ebx  
  38. 　　004113EB add esp,0D8h  
  39. 　　004113F1 cmp ebp,esp  
  40. 　　004113F3 call @ILT+315(__RTC_CheckEsp) (411140h)  
  41. 　　004113F8 mov esp,ebp  
  42. 　　004113FA pop ebp  
  43. 　　004113FB ret  
  44. 　　intmain()  
  45. 　　{  
  46. 　　00411420 push ebp  
  47. 　　00411421 mov ebp,esp  
  48. 　　00411423 sub esp,0CCh  
  49. 　　00411429 push ebx  
  50. 　　0041142A push esi  
  51. 　　0041142B push edi  
  52. 　　0041142C lea edi,[ebp-0CCh]  
  53. 　　00411432 mov ecx,33h  
  54. 　　00411437 mov eax,0CCCCCCCCh  
  55. 　　0041143C repstos dword ptr es:[edi]  
  56. 　　unsigned inti = 12  
  57. 　　0041143E mov dword ptr [i],0Ch  
  58. 　　fun(i)  
  59. 　　00411445 mov eax,dword ptr [i]  
  60. 　　00411448 push eax  
  61. 　　00411449 call fun (4110E6h)  
  62. 　　0041144E add esp,4  
  63. 　　return 0  
  64. 　　00411451 xor eax,eax  
  65. 　　}  
  66. 　　00411453 pop edi  
  67. 　　00411454 pop esi  
  68. 　　00411455 pop ebx  
  69. 　　00411456 add esp,0CCh  
  70. 　　0041145C cmp ebp,esp  
  71. 　　0041145E call @ILT+315(__RTC_CheckEsp) (411140h)  
  72. 　　00411463 mov esp,ebp  
  73. 　　00411465 pop ebp  
  74. 　00411466 ret 

　　上面的代碼，在第一句就間接道明了fun的地址?？梢钥吹皆赾all fun之前會(huì)有一段準(zhǔn)備：

  1. 　　fun(i)  
  2. 　　00411445 mov eax,dword ptr [i]  
  3. 　　00411448 push eax  
  4. 　　00411449 call fun (4110E6h)  
  5. 　　0041144E add esp,4 

 

　　00411445h的指令就將fun的參數(shù)（此時(shí)i=6，還記得上面的圖嗎，參數(shù)n-參數(shù)1）和返回地址入棧，然后PC跳至004110E6h，此時(shí)main的棧幀如下：

　　借助jmp跳至004113A0h，正式進(jìn)入fun函數(shù)。fun內(nèi)首先保存了幀指針和被調(diào)用者保存寄存器和其他相關(guān)數(shù)據(jù)，只有當(dāng)參數(shù)x==0的時(shí)候才會(huì)終止函數(shù)的運(yùn)行，故在遞歸調(diào)用（注意，是遞歸調(diào)用，而不是調(diào)用）fun之前（即call fun之前），有如下：

　　圖

所以，一直遞歸下去的話：

直到x==0，此時(shí)會(huì)進(jìn)入if的分支執(zhí)行步驟。

  1. 　　if(x == 0)  
  2. 　　004113BE cmp dword ptr [x],0  
  3. 　　004113C2 jne fun+28h (4113C8h)  
  4. 　　return 0  
  5. 　　004113C4 xor eax,eax  
  6. 　　004113C6 jmp fun+48h (4113E8h) 

 　　在匯編中，會(huì)用到異或xor邏輯運(yùn)算來對(duì)一個(gè)寄存器清零（004113C4h地址的指令），由于x==0，PC跳至004113E8h，執(zhí)行返回。

  1. 　　004113E8 pop edi  
  2. 　　004113E9 pop esi  
  3. 　　004113EA pop ebx  
  4. 　　004113EB add esp,0D8h  
  5. 　　004113F1 cmp ebp,esp  
  6. 　　004113F3 call @ILT+315(__RTC_CheckEsp) (411140h)  
  7. 　　004113F8 mov esp,ebp  
  8. 　　004113FA pop ebp  
  9. 　　004113FB ret 

 　　在這里把被保存的寄存器值都彈出來，恢復(fù)棧歸位，留意其中針對(duì)%esp和%ebp的操作；執(zhí)行ret操作，返回，

程序繼續(xù)執(zhí)行：

  1. 　　# intrv = fun(nx)  
  2. 　　#004113D0 mov eax,dword ptr [nx]  
  3. 　　#004113D3 push eax  
  4. 　　#004113D4 call fun (4110E6h)  
  5. 　　004113D9 add esp,4  
  6. 　　004113DC mov dword ptr [rv],eax  
  7. 　　rv = 0; 

 　　可以看到，處理器釋放了棧上的內(nèi)存（%esp+4，還記得嗎，棧是向低地址增長(zhǎng)的），因?yàn)樵赾all之前，也就是00411448h地址處，調(diào)用者也就是main函數(shù)將%eax參數(shù)入棧，接著fun退出之后，參數(shù)的內(nèi)存也就理所當(dāng)然的要釋放掉。聯(lián)想一下，如果參數(shù)有很多個(gè)，那么call之前就會(huì)有多個(gè)push，對(duì)應(yīng)的，call之后就會(huì)有“add %esp n”的操作將其釋放。接著將%eax（在寄存器是用習(xí)慣當(dāng)中，%eax經(jīng)常被用作返回值寄存器）的值給了rv，如此一來rv就順理成章地得到了fun的返回值。接下來：

  1. 　　return (x &0x01)+rv  
  2. 　　004113DF mov eax,dword ptr [x]  
  3. 　　004113E2 and eax,1  
  4. 　　004113E5 add eax,dword ptr [rv]  
  5. 　　%eax←(x&0x01)+rv = 0x01&0x01 + 0 = 1;（提示：從這里開始體會(huì)fun的功能） 

 　　簡(jiǎn)單的將x&0x01+rv后送入%eax（記得嗎，%eax經(jīng)常被用作返回值寄存器），此時(shí)可能會(huì)有疑問，x是從哪里來的，答案是x存在調(diào)用者的棧幀內(nèi)，而非被調(diào)用者的棧幀，因?yàn)閤是函數(shù)的一個(gè)參數(shù)，dword ptr [x]應(yīng)該就是對(duì)讀取了調(diào)用者棧幀中的x參數(shù)。該是恢復(fù)棧的時(shí)候了：

  1. 　　004113E8 pop edi  
  2. 　　004113E9 pop esi  
  3. 　　004113EA pop ebx  
  4. 　　004113EB add esp,0D8h  
  5. 　　004113F1 cmp ebp,esp  
  6. 　　004113F3 call @ILT+315(__RTC_CheckEsp) (411140h)  
  7. 　　004113F8 mov esp,ebp  
  8. 　　004113FA pop ebp  
  9. 　　004113FB ret 

 　　恢復(fù)棧幀，執(zhí)行ret，如圖：

fun又成功返回了，程序繼續(xù)：

  1. 　　# intrv = fun(nx)  
  2. 　　#004113D0 mov eax,dword ptr [nx]  
  3. 　　#004113D3 push eax  
  4. 　　#004113D4 call fun (4110E6h)  
  5. 　　004113D9 add esp,4  
  6. 　　004113DC mov dword ptr [rv],eax  
  7. 　　rv = %eax = 1; 

 　　又回到了剛才走過的地方，但是數(shù)據(jù)有異。接下來程序執(zhí)行return退出：

  1. 　　return (x &0x01)+rv  
  2. 　　004113DF mov eax,dword ptr [x]  
  3. 　　004113E2 and eax,1  
  4. 　　004113E5 add eax,dword ptr [rv]  
  5. 　　%eax←(x&0x01)+rv = 0x3&0x01 + 1 = 2;又該是ret的時(shí)候了，恢復(fù)棧：  
  6. 　　004113E8 pop edi  
  7. 　　004113E9 pop esi  
  8. 　　004113EA pop ebx  
  9. 　　004113EB add esp,0D8h  
  10. 　　004113F1 cmp ebp,esp  
  11. 　　004113F3 call @ILT+315(__RTC_CheckEsp) (411140h)  
  12. 　　004113F8 mov esp,ebp  
  13. 　　004113FA pop ebp  
  14. 　　004113FB ret 

 　　棧幀結(jié)構(gòu)如圖：

還差一次，返回之后程序繼續(xù)執(zhí)行：

  1. 　　# intrv = fun(nx)  
  2. 　　#004113D0 mov eax,dword ptr [nx]  
  3. 　　#004113D3 push eax  
  4. 　　#004113D4 call fun (4110E6h)  
  5. 　　004113D9 add esp,4  
  6. 　　004113DC mov dword ptr [rv],eax  
  7. 　　rv = %eax = 2; 

　　接下來程序return退出（不累贅了）：

  1. 　　return (x &0x01)+rv  
  2. 　　004113DF mov eax,dword ptr [x]  
  3. 　　004113E2 and eax,1  
  4. 　　004113E5 add eax,dword ptr [rv]  
  5. 　　004113E8 pop edi  
  6. 　　004113E9 pop esi  
  7. 　　004113EA pop ebx  
  8. 　　004113EB add esp,0D8h  
  9. 　　004113F1 cmp ebp,esp  
  10. 　　004113F3 call @ILT+315(__RTC_CheckEsp) (411140h)  
  11. 　　004113F8 mov esp,ebp  
  12. 　　004113FA pop ebp  
  13. 　　004113FB ret 

 　　至此，程序完全退出了fun的遞歸過程，回到了主函數(shù)main，main也有自己的棧幀，因?yàn)閙ain也是一個(gè)函數(shù)。下圖：

  1. 　　# fun(i)  
  2. 　　#00411445 mov eax,dword ptr [i]  
  3. 　　#00411448 push eax  
  4. 　　#00411449 call fun (4110E6h)  
  5. 　　0041144E add esp,4  
  6. 　　return 0  
  7. 　　00411451 xor eax,eax 

 　　0x0041144E處，add %esp,4，目的是釋放一開始入棧的fun的參數(shù)，而主函數(shù)返回0（return 0），也是用到了異或邏輯運(yùn)算xor來講%eax清零。

　　到這里，相信有點(diǎn)明白了，在遞歸調(diào)用過程中，程序棧是如何變化的，并且上面的函數(shù)計(jì)算參數(shù)i中位的和。

　　收獲

　　發(fā)現(xiàn)這樣一個(gè)小小的遞歸程序，分析起它反匯編如有一種返璞歸真的感覺，對(duì)理解“遞歸調(diào)用”會(huì)更為清晰的思路?？v觀上面的分析，遞歸調(diào)用雖然是算法中解決問題常用的方法，但是它對(duì)付起龐大遞歸次數(shù)的程序來說（上面因?yàn)榉治鏊赃x取的遞歸次數(shù)較少），非常消耗內(nèi)存。 所以在寫程序的時(shí)候，在時(shí)間和空間的消耗抉擇上，需要謹(jǐn)慎。通過學(xué)習(xí)匯編和反匯編代碼的分析，將更了解機(jī)器的行為，從而寫出更為高效的代碼。

　　文章有點(diǎn)長(zhǎng)，歡迎討論。

原文鏈接：http://www.cnblogs.com/daoluanxiaozi/archive/2012/02/08/2340530.html

【編輯推薦】

  1. 匯編語言：從機(jī)器語言到高級(jí)語言的進(jìn)化
  2. 詳解匯編語言開發(fā)環(huán)境搭建方法
  3. JavaScript是Web的匯編語言:瘋狂,亦或只是精神錯(cuò)亂？
  4. 向Brendan致敬-那段華麗的JavaScript歷史
  5. 一位反JavaScript主義者的覺醒
責(zé)任編輯：彭凡 來源： 博客園
匯編語言
相關(guān)推薦

2011-01-14 14:08:17

Linux匯編語言

2011-01-14 14:39:32

Linux匯編語言

2011-01-14 14:15:11

Linux匯編語言

2011-01-04 17:08:10

匯編語言

2011-01-14 14:22:50

Linux匯編語言

2021-06-11 10:02:39

語言編程開發(fā)

2010-11-09 09:51:52

匯編語言

2018-01-11 14:58:40

2011-01-14 13:44:45

Linux匯編語言

2023-11-23 08:25:40

開發(fā)人員SmaliAndroid

2011-07-21 09:59:26

JavaScript

2021-04-27 07:59:11

內(nèi)聯(lián)匯編 C 語言 asm 關(guān)鍵字

2017-01-12 22:36:30

2023-06-01 16:27:34

匯編語言函數(shù)

2009-02-27 08:45:27

Unix入門

2020-11-18 09:30:29

圖片懶加載前端瀏覽器

2013-05-13 11:25:02

WAFWeb應(yīng)用防火墻WAF繞過

2021-03-25 13:05:56

網(wǎng)絡(luò)安全寄存器匯編語言

2020-12-18 08:49:11

相對(duì)跳轉(zhuǎn)絕對(duì)跳轉(zhuǎn)指令

2011-05-17 14:11:06

Dijkstra
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)