簡単なアルゴリズムからアセンブリ言語の予備的研究

コンパイルを無視しないでください

C、C++、Javaなど、日常生活で慣れ親しんでいる高級言語と比較すると、アセンブリ言語は機械語に近いです。その一般的な操作は、値（即値、レジスタ番号、またはメモリデータ）をレジスタにロードするのと同じくらい簡単です。したがって、アセンブリにプログラムタスクを完了させるプロセスは比較的わかりにくく、高級言語は多くの機械の詳細（手順（関数）スタックフレームの初期化、手順終了時のスタックフレームの復元など）を隠しており、コードは明確で理解しやすいです。

私は 1960 年代や 1970 年代の偉大な人たちがいかにしてそれを乗り越えたかを本当に尊敬しています。彼らを崇拝しています。 100 以内の整数の合計を記述することは、十分なアセンブリドキュメントがあっても、しばらくの間は私を悩ませます。うんざりです。しかし、アセンブリの動作とその重要な詳細のいくつかを理解することは、コンピューターのソフトウェアとハードウェアがどのように機能するかを理解するのに役立ちます。簡単なアルゴリズムでアセンブリを紹介します。

プロセスアセンブリプレリュード

プロセスは C の関数として理解できます。呼び出し元が呼び出し先を呼び出すと、システムは呼び出し先のためにスタック内にスペースを割り当てます。このスペースはスタックフレームと呼ばれます。スタックの構造はおおよそ次のようになります。

プログラムスタックは、データ構造のスタック構造と同様に、後入れ先出しの特性を持ち、下位アドレスに向かって大きくなるスタックです。レジスタ %esp (スタックポインタ) にはスタックトップポインタのアドレスが格納され、レジスタ %ebp (** ポインタ) にはフレームポインタのアドレスが格納されます。プログラムを実行すると、スタックポインターを移動してプログラムスタックのスペースを増減できますが、プログラムスタックに格納されるデータのほとんどはフレームポインター (フレームポインター + オフセット) を基準とするため、フレームポインターは固定されます。

呼び出し元が別のプロシージャを呼び出す場合:

まず、呼び出されたプロシージャにパラメータがある場合、これらのパラメータは呼び出しスタックフレーム内に構築され、呼び出し元のスタックフレームに格納されます (このため、上の図ではパラメータ n...パラメータ 1 が表示されています)。

戻りアドレスをスタックにプッシュします。戻りアドレスは、呼び出されたプロシージャが完了した後に呼び出し元が引き続き実行する必要がある命令のアドレスです。これは呼び出し元のスタックフレームの一部であり、呼び出し元のスタックフレームの末尾を形成します。

このステップでは、呼び出し先のスタックフレーム、いわゆる現在のスタックフレームに入ります。呼び出し元のプログラムスタックを後で取得できるように、呼び出し元のフレームポインターを保存します。

最後に、プログラムが実行されます。通常、サブ 0xNh %esp は、現在のプログラムスタックのサイズを割り当てるために使用され、一時変数にアクセスしたり、レジスタ値を一時的に保存したりするために使用されます。

呼び出し先が別のプロシージャを呼び出す場合は、最初のステップに戻るだけです。

プロセスが終了すると、スタックポインターとフレームポインターが復元され、逆アセンブリで次のような内容が表示されることがよくあります。

移動 %esp,%ebp

ポップ%ebp

同時に、返信先アドレスが PC に復元されます。

この時点で、呼び出し元が実行を継続するはずだった場所に戻ります。

上記のテキストは、さらに要約することができます。プロセス (関数) を逆アセンブルすると、確立 (初期化)、本体 (実行)、終了 (戻り) が行われます。以前はスタックとヒープ (データ構造ではない) を混同しやすかったので、皆さんと共有したい良い記事を見つけました: スタックとヒープの違い。何度も転送されているとのことで、よく書かれていることが分かります。プロシージャの呼び出しと戻りは、それぞれ call と ret (戻り) を使用してアセンブリ言語で実装されます。 call メソッドと ret メソッドはあまり透過的ではありません。

呼び出しは戻りアドレスをスタックにプッシュし、PC を呼び出されたプロシージャの開始アドレスにジャンプします。

ret は call の反対で、スタックから戻りアドレスをポップし、PC をジャンプします。

詳細は画像をご覧ください:

アセンブリコード形式について

最も一般的なアセンブリコード形式は、ATT と Intel アセンブリコードです。ATT は古いものですが、GCC と OBJDUMP のデフォルトの形式です。複数のオペランドを持つ命令の場合は、オペランドの並び順が逆になるため、考えが混乱しやすいので注意が必要です。例えば、%esp→%eaxを実装する場合、以下のような違いがあります。

  #インテル
  ムーヴァックス、特に
  #アトム
  移動 %esp,%eax

書籍の影響で、レジスタの前に「%」を追加することに慣れており、ATT 形式のアセンブリコードを好みます。

分解特有の分析

(次のプログラムスタック図では、パラメータをスタックにプッシュしてから、「パラメータ i = ?」とマークしています。これは少しわかりにくいかもしれません。「パラメータ x = ?」の方が良いでしょう :))

簡単なプログラムがあります。どのような機能を実装しているかに関係なく、これを読めば必ず何かが得られます。与えられた C コードは次のとおりです。

  #include <iostream>
　　使用して 名前空間std
  intfun(符号なしintx)
  {
　　(x == 0)の場合
　　0を返す
  符号なし intnx = x>>1
  intrv = fun(nx)
　　戻り値(x &0x01)+rv
  }
  intmain()
  {
  符号なし整数 = 100
  楽しい(i)
　　0を返す
  }

Visual Studio 2008 でアセンブリコードをデバッグして表示すると、次の逆アセンブリコードが取得されます。わかりにくいため、次のようにコピーしました。

  004110E6 ジャンプファン (4113A0h)
  intfun(符号なしintx)
 {
  004113A0 プッシュEBP
  004113A1 移動 ebp、esp
  004113A3 サブエスピー、0D8h
  004113A9 プッシュebx
  004113AA プッシュESI
  004113AB プッシュ編集
  004113AC リーエディ、[ebp-0D8h]
  004113B2 移動ecx、36h
  004113B7 移動 eax,0CCCCCCCCCh
  004113BC は DWORD ポインタを返します:[edi]
　　(x == 0)の場合
  004113BE cmp dword ポインター [x],0
  004113C2 楽しい+28h (4113C8h)
　　0を返す
  004113C4 xor eax、eax
  004113C6 ジャンプファン+48h (4113E8h)
  符号なし intnx = x>>1
  004113C8 移動 eax,dword ポインター [x]
  004113CB shr eax、1
  004113CD mov dword ptr [nx],eax
  intrv = fun(nx)
  004113D0 移動 eax,dword ポインタ [nx]
  004113D3 EAXを押す
  004113D4 コールファン（4110E6h）
  004113D9 esp を追加、4
  004113DC 移動 dword ptr [rv],eax
　　戻り値(x &0x01)+rv
  004113DF 移動 eax,dword ポインタ [x]
  004113E2 および eax,1
  004113E5 eax、dword ptr [rv] を追加
  }
  004113E8 ポップエディ
  004113E9 ポップエシ
  004113EA ポップ ebx
  004113EB esp を追加、0D8h
  004113F1 CMP EBP、ESP
  004113F3 @ILT+315(__RTC_CheckEsp) を呼び出す (411140h)
  004113F8 移動esp、ebp
  004113FA ポップEBP
  004113FB 戻り
  intmain()
  {
  00411420 プッシュEBP
  00411421 移動 ebp、esp
  00411423 サブエスピー、0CCh
  00411429 プッシュebx
  0041142A プッシュESI
  0041142B プッシュ編集
  0041142C レアエディ、[ebp-0CCh]
  00411432 移動ecx、33h
  00411437 移動 eax,0CCCCCCCCCh
  0041143C は DWORD ポインタを返します:[edi]
  符号なし整数 = 12
  0041143E mov ダブルワードポインター [i],0Ch
  楽しい(i)
  00411445 移動 eax,dword ptr [i]
  00411448 EAXを押す
  00411449 電話して楽しんでください（4110E6h）
  0041144E esp を追加、4
　　0を返す
  00411451 xor eax、eax
  }
  00411453 ポップエディ
  00411454 ポップエシ
  00411455 ポップ ebx
  00411456 esp、0CCh を追加
  0041145C CMPebp、ESP
  0041145E @ILT+315(__RTC_CheckEsp) を呼び出す (411140h)
  00411463 移動esp、ebp
  00411465 ポップEBP
 00411466 レット

上記のコードでは、最初の文で fun のアドレスが間接的に記述されています。 fun を呼び出す前に準備があることがわかります。

  楽しい(i)
  00411445 移動 eax,dword ptr [i]
  00411448 EAXを押す
  00411449 電話する 楽しい (4110E6h)
  0041144E esp を追加、4

00411445h の命令は、fun のパラメータ (この時点では i=6、上の図を思い出してください、パラメータ n - パラメータ 1) と戻りアドレスをスタックにプッシュし、その後 PC は 004110E6h にジャンプします。このとき、main のスタックフレームは次のようになります。

jmp を使用して 004113A0h にジャンプし、正式に fun 関数に入ります。まず、フレームポインタ、呼び出し先の保存されたレジスタ、およびその他の関連データが fun に保存されます。関数は、パラメーター x==0 の場合にのみ終了します。したがって、fun の再帰呼び出し (呼び出しではなく再帰呼び出しであることに注意してください) の前 (つまり、fun を呼び出す前) には、次のものがあります。

写真

したがって、再帰を続けると次のようになります。

x==0 になるまで、if 分岐実行ステップに入ります。

　　(x == 0)の場合
  004113BE cmp dword ポインター [x],0
  004113C2 楽しい+28h (4113C8h)
　　0を返す
  004113C4 排他的論理和 eax、eax
  004113C6 ジャンプファン+48h (4113E8h)

アセンブリでは、XOR ロジック演算を使用してレジスタをクリアします (アドレス 004113C4h の命令)。x==0 なので、PC は 004113E8h にジャンプし、実行が戻ります。

  004113E8 ポップエディ
  004113E9 ポップエシ
  004113EA ポップ ebx
  004113EB esp を追加、0D8h
  004113F1 CMP EBP、ESP
  004113F3 @ILT+315(__RTC_CheckEsp) を呼び出す (411140h)
  004113F8 移動esp、ebp
  004113FA ポップEBP
  004113FB 戻り

ここでは、保存されたレジスタ値がすべてポップアウトされ、スタックが復元され、%esp と %ebp に対する操作に注意が払われ、ret 操作が実行されて戻ります。

プログラムは実行を続けます:

  # intrv = fun(nx)
  #004113D0 移動 eax,dword ポインター [nx]
  #004113D3 プッシュeax
  #004113D4 楽しいコール（4110E6h）
  004113D9 esp を追加、4
  004113DC 移動 dword ptr [rv],eax
  rv = 0;

ご覧のとおり、プロセッサはスタック上のメモリ (%esp+4、スタックは下位アドレスに向かって大きくなることに注意してください) を解放します。これは、呼び出し前、つまりアドレス 00411448h で、呼び出し元、つまりメイン関数が %eax パラメータをスタックにプッシュし、その後 fun が終了した後にパラメータメモリが当然解放されるためです。考えてみてください。パラメータが多数ある場合、呼び出し前に複数のプッシュが行われ、それに応じて、呼び出し後にそれらを解放するための「add %esp n」操作が行われます。そして、%eax の値 (レジスタの使用習慣では、%eax は戻り値レジスタとしてよく使用されます) が rv に渡され、rv は自然に fun の戻り値を取得します。次：

　　戻り値(x &0x01)+rv
  004113DF 移動 eax,dword ポインタ [x]
  004113E2 および eax,1
  004113E5 eax、dword ptr [rv] を追加
  %eax←(x&0x01)+rv = 0x01&0x01 + 0 = 1; (ヒント: ここから楽しい機能を体験してみましょう)

単に x&0x01+rv を入力して、%eax に送信します (%eax は戻り値レジスタとしてよく使用されることに注意してください)。この時点で、x がどこから来るのか疑問に思うかもしれません。答えは、x は関数のパラメータであるため、呼び出し先のスタックフレームではなく、呼び出し元のスタックフレームに存在するということです。dword ptr [x] は、呼び出し元のスタックフレームにある x パラメータを読み取る必要があります。スタックを復元する時が来ました:

  004113E8 ポップエディ
  004113E9 ポップエシ
  004113EA ポップ ebx
  004113EB esp を追加、0D8h
  004113F1 CMP EBP、ESP
  004113F3 @ILT+315(__RTC_CheckEsp) を呼び出す (411140h)
  004113F8 移動esp、ebp
  004113FA ポップEBP
  004113FB 戻り

図に示すように、スタックフレームを復元し、ret を実行します。

Fun は再び正常に復帰し、プログラムは続行されます。

  # intrv = fun(nx)
  #004113D0 移動 eax,dword ポインター [nx]
  #004113D3 プッシュeax
  #004113D4 楽しいコール（4110E6h）
  004113D9 esp を追加、4
  004113DC 移動 dword ptr [rv],eax
  rv = %eax = 1;

先ほどの状態に戻りましたが、データは異なります。次に、プログラムは return を実行して終了します。

　　戻り値(x &0x01)+rv
  004113DF 移動 eax,dword ポインタ [x]
  004113E2 および eax,1
  004113E5 eax、dword ptr [rv] を追加
  %eax←(x&0x01)+rv = 0x3&0x01 + 1 = 2; もう一度 ret してスタックを復元します。
  004113E8 ポップエディ
  004113E9 ポップエシ
  004113EA ポップ ebx
  004113EB esp を追加、0D8h
  004113F1 CMP EBP、ESP
  004113F3 @ILT+315(__RTC_CheckEsp) を呼び出す (411140h)
  004113F8 移動esp、ebp
  004113FA ポップEBP
  004113FB 戻り

スタックフレームの構造は次のとおりです。

あと 1 回残っているので、プログラムは戻った後も実行を続けます。

  # intrv = fun(nx)
  #004113D0 移動 eax,dword ポインター [nx]
  #004113D3 プッシュeax
  #004113D4 楽しいコール（4110E6h）
  004113D9 esp を追加、4
  004113DC 移動 dword ptr [rv],eax
  rv = %eax = 2;

次に、プログラムは終了に戻ります (面倒なことはもうありません)。

　　戻り値(x &0x01)+rv
  004113DF 移動 eax,dword ポインタ [x]
  004113E2 および eax,1
  004113E5 eax、dword ptr [rv] を追加
  004113E8 ポップエディ
  004113E9 ポップエシ
  004113EA ポップ ebx
  004113EB esp を追加、0D8h
  004113F1 CMP EBP、ESP
  004113F3 @ILT+315(__RTC_CheckEsp) を呼び出す (411140h)
  004113F8 移動esp、ebp
  004113FA ポップEBP
  004113FB 戻り

この時点で、プログラムは fun の再帰プロセスを完全に終了し、メイン関数 main に戻ります。main も関数であるため、main には独自のスタックフレームもあります。下に：

  # 楽しい(i)
  #00411445 mov eax,dword ptr [i]
  #00411448 プッシュeax
  #00411449 電話して楽しんでください (4110E6h)
  0041144E esp を追加、4
　　0を返す
  00411451 xor eax、eax

0x0041144E では、%esp,4 を追加します。これは、最初にスタックにプッシュされた fun のパラメータを解放することが目的で、main 関数は 0 を返し (return 0)、排他的論理和演算 xor も使用して %eax をクリアします。

この時点で、再帰呼び出しプロセス中にプログラムスタックがどのように変化するか、および上記の関数がパラメーター i のビットの合計を計算する方法について理解が深まったと思います。

利益

私はこのような小さな再帰プログラムを見つけ、その逆アセンブルを分析することで自然に戻ったような感覚を得ることができ、「再帰呼び出し」をより明確に理解することができました。上記の分析を見ると、再帰呼び出しはアルゴリズムで問題を解決するための一般的な方法ですが、再帰回数が多いプログラムでは大量のメモリを消費します（分析のため、上記で選択した再帰回数は比較的少ないです）。したがって、プログラムを作成するときは、時間とスペースの消費を慎重に決定する必要があります。アセンブリコードと逆アセンブリコードの分析を学習することで、マシンの動作をより深く理解し、より効率的なコードを記述できるようになります。

記事は少し長いですが、議論を歓迎します。

オリジナルリンク: http://www.cnblogs.com/daoluanxiaozi/archive/2012/02/08/2340530.html

【編集者のおすすめ】