Practice2 Explanation - GawinGowin/libasm GitHub Wiki

Practice2: 階乗計算プログラムの詳細解説

課題文

目標: x86-64アセンブリ言語を使って階乗計算を行う再帰関数を実装する

要件:

  1. NASMアセンブラを使用してx86-64アセンブリで実装
  2. 再帰を使用して階乗計算を行う関数 factorial を作成
  3. System V AMD64 ABI に準拠した関数呼び出し規約を使用
  4. 引数: rdi（計算する数値n）、戻り値: rax（n!の結果）
  5. ベースケース: n ≤ 1 の場合は 1 を返す

ファイル名: practice2.s

関数仕様:

  • 関数名: factorial
  • 引数: rdi (uint64_t n)
  • 戻り値: rax (uint64_t n!)
  • 計算式: n! = n × (n-1) × (n-2) × ... × 1

テスト例:

factorial(0) = 1
factorial(1) = 1
factorial(3) = 6
factorial(5) = 120

コンパイル・実行手順:

nasm -f elf64 practice2.s -o practice2.o
gcc -no-pie practice2.o practice2.c -o test_factorial
./test_factorial

注意: リンカー警告を回避するため、アセンブリファイルの最後に以下を追加してください：

; セキュリティ対策: 実行可能スタックを無効化
section .note.GNU-stack noalloc noexec nowrite progbits

テスト用Cファイル (test_factorial.c):

#include <stdio.h>
#include <stdint.h>

// アセンブリ関数の宣言
extern uint64_t factorial(uint64_t n);

int main() {
    // テストケース
    uint64_t test_cases[] = {0, 1, 3, 5, 10};
    int num_tests = sizeof(test_cases) / sizeof(test_cases[0]);
    
    printf("階乗計算テスト:\n");
    printf("================\n");
    
    for (int i = 0; i < num_tests; i++) {
        uint64_t n = test_cases[i];
        uint64_t result = factorial(n);
        printf("factorial(%lu) = %lu\n", n, result);
    }
    
    return 0;
}

なぜこの練習を行うのか

学習目的

  1. 再帰関数の実装理解

    • スタックの動作メカニズム
    • 関数の呼び出しと戻り
    • ベースケースと再帰ケースの概念

  2. 基本算術命令の習得

    • 乗算命令（MUL）の使用方法
    • 比較命令（CMP）の理解
    • 条件分岐命令（JLE）の実践

  3. レジスタ管理の基礎

    • 値の保存と復元（PUSH/POP）
    • レジスタの役割分担
    • データの受け渡し方法

コード詳細解析

; practice2.s - 階乗計算
section .text
    global factorial

factorial:
    ; 引数: rdi (n)
    ; 戻り値: rax
    cmp rdi, 1
    jle .base_case
    
    push rdi
    dec rdi
    call factorial
    pop rdi
    
    mul rdi
    ret

.base_case:
    mov rax, 1
    ret

; セキュリティ対策: 実行可能スタックを無効化
section .note.GNU-stack noalloc noexec nowrite progbits

関数構造の解説

関数シグネチャ

factorial:
    ; 引数: rdi (n)
    ; 戻り値: rax

System V AMD64 ABI準拠:

  • 第1引数: rdi レジスタ
  • 戻り値: rax レジスタ

ベースケース判定

cmp rdi, 1          ; rdi と 1 を比較
jle .base_case      ; rdi <= 1 なら .base_case へジャンプ

条件フラグの動作:

  • CMP: 減算を行い、結果でフラグを設定（値は変更しない）
  • JLE: Less or Equal （≤）でジャンプ
  • 階乗の数学的定義: 0! = 1, 1! = 1

CMP命令によるフラグレジスタの更新

cmp rdi, 1 の実行により、以下のフラグレジスタが更新されます：

主要なフラグレジスタ

ZF (Zero Flag) - ゼロフラグ:

  • rdi == 1 の場合: ZF = 1
  • rdi != 1 の場合: ZF = 0
  • 用途: 等価性判定（je, jne命令で使用）

SF (Sign Flag) - 符号フラグ:

  • rdi < 1 の場合: SF = 1 (結果が負)
  • rdi >= 1 の場合: SF = 0 (結果が正またはゼロ)
  • 用途: 符号付き比較の基礎

CF (Carry Flag) - キャリーフラグ:

  • rdi < 1 (符号なし比較) の場合: CF = 1
  • rdi >= 1 (符号なし比較) の場合: CF = 0
  • 用途: 符号なし比較の基礎

実際の例

; 例1: rdi = 1 の場合
cmp rdi, 1
; → ZF=1, SF=0, CF=0 (1-1=0, 等しい)

; 例2: rdi = 5 の場合  
cmp rdi, 1
; → ZF=0, SF=0, CF=0 (5-1=4, 大きい)

; 例3: rdi = 0 の場合
cmp rdi, 1
; → ZF=0, SF=1, CF=1 (0-1=-1, 小さい)

JLE命令の判定条件

jle .base_case は以下の条件でジャンプします：

  • 条件: (SF ≠ OF) || (ZF = 1)
  • 意味: rdi <= 1 (符号付き比較)

具体的な判定:

  • rdi = 0: SF=1, OF=0, ZF=0 → SF≠OF なのでジャンプ
  • rdi = 1: SF=0, OF=0, ZF=1 → ZF=1 なのでジャンプ
  • rdi = 2: SF=0, OF=0, ZF=0 → 条件不成立でジャンプしない

再帰処理の詳細

スタック管理

push rdi            ; 現在の n をスタックに保存
dec rdi             ; n を 1 減らす (n-1)
call factorial      ; factorial(n-1) を再帰呼び出し
pop rdi             ; 元の n をスタックから復元

重要なポイント:

  • PUSH/POP: スタックでの値保存・復元
  • DEC: レジスタの値を1減少
  • CALL: 関数呼び出し（戻りアドレスを自動的にスタックに保存）

乗算処理

mul rdi             ; rax = rax * rdi (factorial(n-1) * n)
ret                 ; 呼び出し元に戻る

MUL命令の特徴:

  • MUL reg64: rax = rax * reg64
  • 結果は常に rax に格納
  • オーバーフロー時は rdx:rax に128bit結果

実行フローの追跡

factorial(3) の実行例

1. factorial(3) 呼び出し
   - rdi = 3
   - 3 > 1 なので再帰へ

2. push 3, call factorial(2)
   - スタック: [3]
   - rdi = 2

3. factorial(2) 内で push 2, call factorial(1)
   - スタック: [3, 2]
   - rdi = 1

4. factorial(1) 実行
   - 1 <= 1 なので base_case
   - rax = 1, return

5. factorial(2) 復帰
   - pop 2 → rdi = 2
   - mul 2 → rax = 1 * 2 = 2
   - return

6. factorial(3) 復帰
   - pop 3 → rdi = 3
   - mul 3 → rax = 2 * 3 = 6
   - return

結果: 6

学習効果

この練習で身につくスキル

  1. 再帰アルゴリズムの実装

    • 数学的定義をコードに変換
    • 終了条件の適切な設定
    • スタックオーバーフローの理解

  2. スタック操作の理解

    • LIFO（Last In, First Out）の概念
    • レジスタ値の一時保存
    • 関数呼び出し時のスタック変化

  3. 算術命令の活用

    • 乗算命令の正しい使用
    • レジスタ間でのデータ操作
    • 効率的な計算処理

デバッグのポイント

スタックバランス

; 必須: PUSH と POP の対応
push rdi    ; 保存
; ... 処理 ...
pop rdi     ; 復元（必須！）

無限再帰の回避

; ベースケースの適切な条件設定
cmp rdi, 1      ; 0 や 1 で停止
jle .base_case  ; <= 条件で安全に停止

応用課題

この理解を基に以下を実装できるようになります：

  1. 他の数学関数

    • フィボナッチ数列
    • べき乗計算
    • 最大公約数（GCD）

  2. 最適化技法

    • 末尾再帰最適化
    • メモ化による高速化
    • 反復実装への変換

よくある間違い

1. スタック不均衡

; 間違い: POPし忘れ
push rdi
call factorial
; pop rdi が抜けている
mul rdi  ; 間違った値を使用

2. ベースケース抜け

; 間違い: 終了条件なし
factorial:
    dec rdi
    call factorial  ; 無限再帰！

3. レジスタ破壊

; 間違い: 引数レジスタを直接変更
dec rdi         ; rdi を直接変更
call factorial
mul rdi         ; 変更後の値を使用（間違い）

この練習により、再帰処理とスタック管理の基礎が身につき、より複雑なアルゴリズム実装への準備が整います。

⚠️ **GitHub.com Fallback** ⚠️