7

アセンブリで再帰的なフィボナッチプログラムを実装しようとしています。ただし、未処理の例外を除いてプログラムがクラッシュし、問題を特定できないようです。スタックの不適切な使用が関係していることは間違いありませんが、どこにあるのか指摘できないようです...

.386
.model Flat
public Fibonacci
include iosmacros.inc ;includes macros for outputting to the screen

.code
Fibonacci proc

MOV EAX, [EBP+8]
CMP EAX, 1
    JA Recurse
    MOV ECX, 1
    JMP exit

Recurse:
    DEC EAX
    MOV EDX, EAX
    PUSH EAX
    CALL Fibonacci
    ADD ESP, 4
    MOV EBX, ECX
    DEC EDX
    PUSH EDX
    CALL Fibonacci
    ADD ECX, EBX
exit:
ret
Fibonacci endp


.data


end

また、外部プロシージャでフィボナッチ値を取得するために使用している数値をスタックにプッシュしました。問題が存在する可能性のあるアイデアはありますか？

4

3 に答える 3

7

を実行するcallと、次の操作のアドレスが戻り値としてスタックにプッシュされます。関数を作成するときは、「スタックフレーム」を作成するのが通例です。このフレームは、呼び出しスタック、およびローカル変数と引数のオフセットを出力するために使用できます。フレームは、関数の開始時に2つの操作によって作成されます。

push ebp
mov ebp, esp

関数の最後で、呼び出しスタックはleave、を使用して削除されます。これは、これら2つの操作の逆に相当します。スタックフレームを使用する場合、の値espはに格納されebp、フレームのベースと呼ばれるスタック上の場所を指します。このアドレスの上には、の古い値ebpとリターンアドレスがあるため、通常はを使用して最初の引数を取得します[ebp+8]。ただし、スタックフレームは設定していません。これは、の古い値がebpスタックにプッシュされておらず、現在の値をebp使用して引数を取得できないことを意味します。これは、の場所がわからないためです。したがって、を使用して引数を取得する必要があります[esp+4]。

また、戻り値は呼び出し元に配置され、保持されるのeaxが通例です。ebxコードはこれらの規則のいずれにも従いません。また、技術的には関数を保存する必要はありません。したがって、保存したいecx場合edxは、通常、別の関数を呼び出す前に関数をスタックにプッシュする必要があります。このコードではedx、ebx2より大きい値で呼び出されると上書きされ、無効な結果が発生します。

これが私が言及したすべての修正を含む完全なリストです。スタックフレームは必要ないので作成しませんでしたし、コードも作成しませんでした。

.386
.model Flat
public Fibonacci
include iosmacros.inc ;includes macros for outputting to the screen

.code
Fibonacci proc

    MOV EAX, [ESP+4]
    CMP EAX, 1
    JA Recurse
    MOV EAX, 1 ; return value in eax
    JMP exit

Recurse:
    PUSH EBX ; preserve value of ebx
    DEC EAX
    PUSH EAX
    CALL Fibonacci
    MOV EBX, EAX ; ebx is preserved by callee, so it is safe to use
    DEC [ESP] ; decrement the value already on the stack
    CALL Fibonacci
    ADD EAX, EBX ; return value in eax
    ADD ESP, 4 ; remove value from stack
    POP EBX ; restore old value of ebx
exit:
ret
Fibonacci endp
于 2011-04-11T04:43:45.080 に答える
6

いくつかの問題：

  • スタックにパラメータを渡す場合は、正しい（標準の）関数エントリがないため、EBPは間違った場所を指します
  • 引数の値をedxに正しく保存していません

スタックにパラメーターを渡すと仮定すると、これが私が望んでいたことです（各命令にコメントを追加して、それが何をしていると思うかを明確にするのが最善です）：

Fibonacci proc
  PUSH EBP          ; save previous frame pointer
  MOV  EBP, ESP     ; set current frame pointer

  MOV  EAX, [EBP+8] ; get argument N
  CMP  EAX, 1       ; N<=1?
  JA   Recurse      ; no, compute it recursively
  MOV  ECX, 1       ; yes, Fib(1)--> 1
  JMP  exit

Recurse:
  DEC  EAX          ; = N-1
  MOV  EDX, EAX     ; = N-1
  PUSH EDX          ; save N-1
  PUSH EAX          ; set argument = N-1
  CALL Fibonacci    ; compute Fib(N-1) to ECX
  POP  EAX          ; pop N-1
  DEC  EAX          ; = N-2
  PUSH ECX          ; save Fib(N-1)
  PUSH EAX          ; set argument = N-2
  CALL Fibonacci    ; compute Fib(N-2) to ECX
  POP  EAX          ; = Fib(N-1)
  ADD  ECX, EAX     ; = Fib(N-1)+FIB(N-2)
exit:
  MOV  ESP,EBP      ; reset stack to value at function entry 
  POP  EBP          ; restore caller's frame pointer
  RET               ; and return

ただし、スタック上のパラメーターを渡す必要はありません。レジスタを使用する方が効率的です。

Fibonacci proc ; computes Fib(EAX) --> EAX; do not call with EAX==0
  CMP  EAX, 1      ; N<=1?
  JBE  exit        ; yes, we have the answer
  DEC  EAX         ; = N-1
  PUSH EAX         ; save N-1
  CALL Fibonacci   ; computing FIB(n-1)to EAX
  XCHG EAX,0[ESP]  ; swap FIB(n-1) for saved N-1 (You'll love this instruction, look it up in the Intel manual)
  DEC  EAX         ; = N-2
  CALL Fibonacci   ; computing FIB(N-2) to EAX
  POP  ECX         ; = FIB(N-1)
  ADD  EAX,ECX     ; = FIB(N-1)+FIB(N-2)
exit:
  RET
于 2011-04-11T04:32:28.957 に答える
1

まず、EBPからのスタックオフセット8を使用しているのはなぜですか？ESPじゃないの？また、通常の呼び出しでは32ビットセルが1つしか使用されないため、引数はオフセット4にある必要があります。他の問題が存在することは間違いありませんが、それから始めることができます。

あなたはおそらく、あなたと私たちがあなたが達成しようとしていることを見ることができるように、いくつかの擬似コードを書くべきです。
不正行為をしたい場合は、「nasm recursivefibonacci」をグーグルで検索すると、実用的なプログラムに移動します。しかし、自分で解決すれば、より優れたプログラマーになるでしょう。

于 2011-04-11T04:21:12.423 に答える