繰り返しと条件分岐 (i386)

繰り返し（ループ）はプログラミングにおける最重要機能と言ってよいだろう。ループを使わなければできないことはたくさんあるし，むしろほとんどのプログラムはループ処理を含んでいる。

第0部において，条件付きジャンプ命令を使ってループや条件分岐を実現した。 i386でも同じである。比較命令 cmp と条件付きジャンプ命令を組み合わせ，手前の命令に戻ればループ，先の命令を飛び越せば条件分岐になる。

第0部ではアセンブラを使えなかったので，ジャンプ先の番地は自分で調べる必要があったが，アセンブラを使う場合は，ラベルを使うことで，番地の計算を機械にやらせることができる。

ループを持つ極小プログラム

例として，1以上10以下の整数の総和を計算するプログラムを考えよう。 C言語なら以下のように記述できる。（printf等を使っていないので #include 文は不要。）

int main()
{
  int sum, i;
  sum = 0;
  for (i = 1; i <= 10; i++) {
    sum += i;
  }
  return sum;   /* 終了コードとして出力 */
}

構成要素を単純にするために，forの代わりにwhileを使って書き換えれば，以下のようになる。

int main()
{
  int sum, i;
  sum = 0;
  i = 1;
  while (i <= 10) {
    sum += i;
    i++;
  }
  return sum;
}

以降，このプログラムのアセンブリ言語版を考える。

ジャンプ命令によるループ

無条件ジャンプ命令 jmp を使ったプログラム例を以下に示す。 jmpはミクロンのb命令に当たる。（なお，jmpの前のincは「1増やす」演算命令。） jmpのオペランドはジャンプ先番地だが，アセンブリ言語では普通，ラベルでジャンプ先を表す。プログラムの先頭を表すラベル _start と同じように，プログラム中の好きな位置にラベルを付け，それをジャンプ命令のオペランドに指定できる。（なお，_start の先頭の _ は「特別な目的のあるラベル」の印なので，通常のラベルには使わない。）

        ; 1以上10以下の整数の和 (未完成)
        section .text
        global  _start
_start:
        mov     ebx, 0          ; sumの代わりにebxを使う
        mov     ecx, 1          ; iの代わりにecxを使う
loop:
        add     ebx, ecx        ; sum += i
        inc     ecx             ; i++
        jmp     loop            ; loopに戻る

        mov     eax, 1          ; exitのシステムコール番号
        int     0x80            ; システムコール

（このプログラムは，jmp loop を実行すると必ずloopに戻るので，停止しない。）

参考：ジャンプ命令の機械語コード

ジャンプ命令は機械語ではどのようになるか，見てみよう。上記プログラムを sum10.s という名前で保存し，アセンブルして，逆アセンブルする。

$ nasm sum10.s
$ ld sum10.o
$ objdump -M intel -d a.out
-- 中略
セクション .text の逆アセンブル

08049060 <_start>:
 8049000:       bb 00 00 00 00          mov    ebx,0x0
 8049005:       b9 01 00 00 00          mov    ecx,0x1

0804900a <loop>:
 804900a:       01 cb                   add    ebx,ecx
 804900c:       41                      inc    ecx
 804900d:       e9 f8 ff ff ff          jmp    804900a <loop>
 8049012:       b8 01 00 00 00          mov    eax,0x1
 8049017:       cd 80                   int    0x80

jmp命令のオペランドは，アセンブリ表記中ではジャンプ先の番地だが，機械語コードでは番地そのものではなく相対位置になっている。 jmp loopは機械語では e9 f8 ff ff ff になっているが，e9 がオペコードであり，残り4バイトがオペランドだ。このオペランドは 0xfffffff8 という32ビットの数を表している。これは実は −8 を意味する（2の補数による負数表現）（負数の表し方は後の章で扱う）。このjmp命令を実行しているとき，命令ポインタ EIP はすでに次の命令の番地 0x8049012 を指しており，jmp命令がEIPに −8 を加えるので，次に実行するのは 0x804900a 番地 (= loop) の命令になる。

条件付きジャンプ

条件付きジャンプ命令を使って，ループを10回繰り返したら終了するように上記のプログラム例を書き直そう。第0部と同様に，cmp命令と条件付きジャンプ命令を使えばよい。

        ; 1以上10以下の整数の和
        section .text
        global  _start
_start:
        mov     ebx, 0          ; sumの代わりにebxを使う
        mov     ecx, 1          ; iの代わりにecxを使う
loop:
        add     ebx, ecx        ; sum += i
        inc     ecx             ; i++
        cmp     ecx, 10         ; ecxと10を比較
        jle     loop            ; lessまたはequalならloopに戻る

        mov     eax, 1          ; exitのシステムコール番号
        int     0x80            ; システムコール

比較命令 cmp (compare) と条件付きジャンプ命令 jle (jump if less or equal) を組にして使っている。第0部とは命令のニーモニックが ble から jle に変わるだけだ。ミクロンと違い，cmpの第2引数は即値でもよい。

補足：フラグレジスタ

フラグレジスタについておさらいしておこう。

フラグレジスタは，演算結果に関する特定の情報を格納する特殊レジスタだ。 …と言うとわかりにくいが，例えば以下のような情報を格納する。

演算結果が0だった（Zeroフラグ; ZF）
演算によって桁上がり・桁借りが発生した（Carryフラグ; CF）
演算結果が負数だった（Signフラグ; SF）
符号付き数同士の演算として見たとき，演算によって桁あふれが発生した（Overflowフラグ; OF）
- i386（や他の実用的なCPU）は符号付き数を扱う機能を持っている。SF・OFは符号付き数用の機能で使われる。

基本的に，演算命令を実行するとフラグレジスタの値が変化する。どのフラグビットが影響を受けるかは命令ごとに決まっている（下表）。

各命令のフラグレジスタへの影響
（『Intel 80386 Programmer's Reference Manual 1986』付録C: Status Flag Summary を基に作成）

（この表にない命令は，（一部の例外を除き）フラグを変化させない。）
参考: 上の表中の T は「そのフラグの値を使用する」ことを表す。例えば，ADD命令はフラグレジスタの値を使わないが，もう一つの加算命令であるADC命令 (add with carry) は，2つの被演算数に加えてCFの値（0または1）も加える。これは，桁数の大きい数同士の加算を16ビットや32ビットごとに分けて行うとき，下位桁で桁上がりが起こったことを上位桁の加算に反映させるために使う。

条件付きジャンプ命令は，フラグレジスタの値を参照し，ジャンプするかしないか決める。例えばje命令 (jump if equal) は，Zeroフラグが1（真）ならば指定された番地にジャンプし，そうでなければ何もせず次の命令に進む。

条件付きジャンプ命令の一覧

以下は，cmp命令と組にして使うための条件付きジャンプ命令だ。「意味」欄は，cmp命令の第1オペランドが第2オペランドより大きいか小さいか等しいかを表している。

		意味（下記ならばジャンプ）
JE	(jump if equal)	等しい (==)
JG	(jump if greater)	大きい (>)
JGE	(jump if greater or equal)	大きいまたは等しい (>=)
JL	(jump if less)	小さい (<)
JLE	(jump if less or equal)	小さいまたは等しい (<=)
JA	(jump if above)	上 (>)
JAE	(jump if above or equal)	上または等しい (>=)
JB	(jump if below)	下 (<)
JBE	(jump if below or equal)	下または等しい (<=)
JN__	(jump if not __)	（上記の各命令のJをJNに換えたもの）上記の意味の逆

（「大きい・小さい」と「上・下」の意味の違いは後述。）

JNE (jump if not equal)，JNG (jump if not greater) のように，上記の各ジャンプ命令の J を JN (jump if not) に変えた命令が存在する。意味は逆になる（JNEは「等しくない」，JNGは「大きくない」）。

参考：JNG（大きくない）とJLE（小さいまたは等しい）は同じ意味で，実際 JNG は JLE の別名だ（機械語コードは同じ）。同様に JNGE = JL, JNL = JGE, JNLE = JG, ... だ。

参考:「大きい・小さい」と「上・下」

ミクロンの bgt，bge に当たる i386 の命令は，実は jg，jge ではなく，ja，jae である。

i386では，「大きい (greater)・小さい (less)」は「符号付き（負数も扱う場合）」の大小，「上 (above)・下 (below)」は「符号無し（0以上の数しか扱わない場合）」の大小を表す。 C言語やJavaでのint型の値の大小は「大きい・小さい」に当たる。C言語でのunsigned型の値やポインタの大小は「上・下」に当たる。符号付き数については後の章で扱う。

0以上0x7fffffff (= 2,147,483,647) 以下の数しか扱わない場合は，「大きい・小さい」と「上・下」は同じである。

参考: while と do-while

第0部でも述べたが，上記のプログラムのループは while 文ではなく do-while 文に当たる。

loop:
        ...
        cmp     ecx, 10         ; ecxと10を比較
        jle     loop            ; lessまたはequalならloopに戻る

  do {
    ...
  } while (i <= 10);

while 文と同じ動作にするには，ループの先頭で条件分岐し，かつ，ループ末尾からループ先頭に無条件ジャンプすればよい。

  while (i <= 10) {
    ...
  }

loop:
        cmp     ecx, 10         ; ecxと10を比較
        jnle    endloop         ; lessまたはequalでなければループを抜ける
        ...
        jmp     loop            ; loopに戻る
endloop:

参考: 0になるまで繰り返すループ

これも第0部で述べたが，「レジスタの値を減らしていって，0になったらループを抜ける」というループ構造もよく用いられる。

        ; 1以上10以下の整数の和 (10,9,8,...の順)
        section .text
        global  _start
_start:
        mov     ebx, 0          ; sumの代わりにebxを使う
        mov     ecx, 10         ; 10から始めて段々減らす
loop:
        add     ebx, ecx        ; sum += i
        dec     ecx             ; i--
        jnz     loop            ; 0でなければloopに戻る

        mov     eax, 1          ; システムコール番号
        int     0x80            ; exitシステムコール

inc命令 (increment) とdec命令 (decrement) はそれぞれ「1増やす」「1減らす」命令だ。 CやJavaにも i++, i-- という記法があるように，「1増やす」「1減らす」演算はよく使うので，i386では専用の命令が用意されている。

このプログラム例では，ECXの値を1ずつ減らしていき，0より大きい間はループし，0と等しくなったらループを抜ける。 JNZ (jump if not zero) は，直前の演算結果が0でなければジャンプする命令だ。（JNZ は JNE の別名であり，両者の機械語コードは同じである。このプログラム例では jne ではなく jnz と書いた方が，「演算結果が 0 でなければ」という意図が明確になる。）

前述の「CMP命令と組にして使うジャンプ命令」以外のジャンプ命令として下記がある。それぞれ，対応するフラグビットが1ならばジャンプする。

		意味（下記ならばジャンプ）
JZ	(jump if zero)	演算結果が0
JC	(jump if carry)	桁上がり・桁借りが発生した
JO	(jump if overflow)	桁あふれが発生した
JS	(jump if sign)	演算結果が負
JN__	(jump if not __)	（上記の各命令のJをJNに換えたもの）上記の意味の逆

参考：「残り回数が0になるまで繰り返すループ」はよく使うので，i386の場合，dec ecx と jnz を1命令で行う loop という命令も用意されている（ただし，残り回数を数えるレジスタが ECX と決められている）。

条件分岐 (if-then-else)

条件分岐も第0部と同じである。

以下は，「x の値が100以上なら100減じ，100未満なら100加えて出力するプログラム」を，C言語とアセンブリ言語で記述したものである。

int main()
{
  int x;
  ...
  if (x >= 100) {
    x -= 100;
  } else {
    x += 100;
  }
  return x;
}

        ...
        cmp     ebx, 100        ; ebx >= 100?
        jnge    else            ; 100以上でなければelseへ

        sub     ebx, 100        ; then節 (x -= 100)
        jmp     endif           ; else節を飛び越える
else:
        add     ebx, 100        ; else節 (x += 100)
endif:
        mov     eax, 1          ; exitのシステムコール番号
        int     0x80            ; システムコール

else節を飛び越える jmp endif を忘れると，then節を実行した後 else節も実行してしまうので注意。

参考：スパゲッティプログラム

while や if-then-else が，比較命令とジャンプ命令で実現できることを見てきた。ジャンプ命令は，前でも後ろでも好きな位置にジャンプできるので，while や if よりある意味自由だ。しかし使いすぎると，流れを追いにくい非常にわかりづらいプログラムになる（実際，過去の授業の提出物にも多くある）。そういうプログラムをスパゲッティプログラムと言う。

上手なプログラムを書くことはこの授業の目的ではないが，ややこしいプログラムはバグが入り込みやすく，デバッグも大変だ。「簡潔ですっきりしたプログラム」を書けるようにしておかないと，課題の難易度が上がるにつれて手に負えなくなってしまう。「高級言語で自由なジャンプができないのはむしろぐちゃぐちゃになるのを防ぐため」と考えて，なるべく while や if-then-else と同じ流れになるように記述した方が安全だ。先に高級言語風のアルゴリズムを書いてから，アセンブリ言語で書き直すのが良いと思われる。

例えば，下記のようなループはその下のアセンブリコードに書き換えればよい。

do {
  -- A --
} while (i <= 10);

loop:
        -- A --
        cmp     ecx, 10
        jle     loop

下記のようなif文はその下のアセンブリコードに書き換えればよい。

if (x == 0) {
  -- A --
} else {
  -- B --
}

        cmp     edx, 0
        jne     else
        -- A --
        jmp     endif
else:
        -- B --
endif:

これらが組み合わさっても，一つ一つパタン通りに書き換えればよい。例えば，ループの中にif文がある下記のコードを考える。

do {
  if (x == 0) {
    -- A --
  }
  n--;
} while (n != 0);

悪い例． 必要以上にジャンプ命令が多くて流れを追うのに手間がかかるし，同じことを2回書いている箇所（つまりコードクローン）も目につく。（実際，このような提出物はしばしば見かける。）

loop:
        cmp     edx, 0
        je      then
        dec     ecx
        jnz     loop
        jmp     end
then:
        -- A --
        dec     ecx
        jnz     loop
end:

良い例． 高級言語からアセンブリ言語への書き換えを正しく行えば，ifのためのジャンプとループのためのジャンプそれぞれ1個で済む。ジャンプが少なければ流れを追うのが容易だし，簡潔な方が理解しやすくバグも入り込みにくい。

loop:
        cmp     edx, 0
        jne     endif
        -- A --
endif:
        dec     ecx
        jnz     loop

練習問題

演習1.2-6　以下の各プログラムを作成し，作成したソースコードを自分のGitHubリポジトリに提出（commit & push）しなさい。リポジトリ中のサブディレクトリ chap2 の中に各ソースファイルを置くこと。ソースファイル名は各小問で指定する。異なる名前のファイルや異なるディレクトリに置かれているファイルは無視する（逆に言えば，提出物ではないファイルをリポジトリに置いても構わない）。期限は別途指示する。小問5〜6はオプション課題である。

受講生が使用できる検査プログラムは提供しない。提出後に自動検査システムが提出物を検査する。検査に合格しない提出物は未提出と同じ扱いとする。自動検査システムの検査結果一覧のありかは別途周知する。

（演習1.2-5の再掲） 123 + 45 − 67 + 8 − 9 を計算して出力するアセンブリ言語プログラムを作成しなさい。（提出ファイル名: 123.s）
5 以上 21 以下の整数の総和を計算して出力するアセンブリ言語プログラムを作成しなさい。（提出ファイル名: sum521.s）
フィボナッチ数 f_n を，式 f₀ = 0，f₁ = 1，f_n = f_n−1 + f_n−2 (n ≥ 2) で定義する。f₁₃ の値を計算して出力するアセンブリ言語プログラムを作りなさい。（提出ファイル名: fib13.s）
数列 (a_n) を，式 a₀ = 1 と $a_{n + 1} = {\begin{cases} 2 a_{n} + 1 & a_{n} < 101 のとき \\ a_{n} - 101 & それ以外 \end{cases}$ (n ≥ 0) で定義する。a₅₀ の値を計算して出力するアセンブリ言語プログラムを作成しなさい。なお，2a_n = a_n + a_n である。（提出ファイル名: a50.s）
（オプション課題）フィボナッチ数 f_n に関して，f_n ≥ 123456789 を満たす最小の n を求めて出力するアセンブリ言語プログラムを作成しなさい。ただし，123456789という定数を記述する箇所（コメントを除く）は1箇所とし，それを別の数（例えば54321）に書き換えれば，f_n がその数以上になる最小の n を答えるように作成すること（3未満の数や10億より大きい数に書き換えられることはないと仮定してよい）。フィボナッチ数の定義は小問3を参照。（提出ファイル名: fge123m.s）
（オプション課題）フィボナッチ数 f_n（n ≥ 1）に対し，f_n−1 以上 f_n 以下の整数の総和を s_n とする。s_n ≥ 123456789 となる最小の n を求めて出力するアセンブリ言語プログラムを作成しなさい。ただし，123456789という定数を記述する箇所（コメントを除く）は1箇所とし，それを別の数（例えば54321）に書き換えれば，s_n がその数以上になる最小の n を答えるように作成すること（3未満の数や10億より大きい数に書き換えられることはないと仮定してよい）。フィボナッチ数の定義は小問3を参照。（提出ファイル名: sge123m.s）

（ヒント）

（容易なので省略）
「1以上10以下の整数の総和」とほぼ同じ。
3つのレジスタを使って，n, f_n, f_n−1 を表せばよい。ループの中ですることは，(1) もう一つレジスタを使って f_n + f_n−1 を計算する，(2) nを1増やし，f_n−1, f_n を更新する，(3) nが13未満なら(1)に戻る。
小問3と同様に，漸化式の通り a₁ から順に計算していけばよい。a_n から a_n+1 を計算するときに条件分岐が必要。
小問3と同様。繰り返しの終了条件と出力すべき値がちがうだけ。出力するのは f_n ではなく n であることに注意。
想定している解法: 小問3・5と同様に計算を行うが，(2) で n, f_n−1, f_n を更新するたびに，f_n−1 以上 f_n 以下の整数の総和を（内側のループで）計算する。

2-b. 繰り返しと条件分岐 (i386)