条件分岐と繰り返し

繰り返し（ループ）が使えるようになると，プログラムでできることが大きく増える。以下は，ループを使ってできるプログラムの例だ。

第 n フィボナッチ数を計算するプログラム
n が素数かどうか判定するプログラム
n 以下の素数の個数を計算するプログラム

ほかにもいろいろ考えられる。むしろ，ほとんどのプログラムはループ処理を含んでいる。例えば数値を10進数（数字の列）で出力することも，（printf等を使わず自力でプログラムするなら）ループを使わなければ困難だ。

機械語ではループをどう実現するのだろうか?　以下，それを見ていこう。

ループとは?

例として，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;
}

さて，この「while」が行っていることは本質的には何だろうか?

音楽プレイヤーにも「ループ再生」という機能があるが，「ループ」の本質はループ再生もwhileループも同じ。「末尾まで来たら先頭に戻る」ことだ。ただし，ループ再生は普通，いつまでもループし続ける「無限ループ」だと思うけど，whileの場合は「無限ループ」にならないよう「繰り返し条件」が付いている。

ジャンプ命令

CやJavaにしろ，機械語プログラムにしろ，通常はプログラムの先頭から下に向かって実行が進んでいくが，「実行位置を上に戻す」動作ができればループを実現できる。機械語プログラムの場合，それはジャンプ (jump) という機能で実現される。CPUの中には命令ポインタという特殊レジスタ（i386の場合はEIP）があって，「命令ポインタが指す位置から次の機械語命令を読み出す」「命令ポインタをその次の命令を指すよう更新する」という動作を1命令実行するたびに行っている。ジャンプ命令は，命令ポインタが指す位置を変更する命令だ。

ジャンプ命令を使ったプログラム例を以下に示す。ジャンプ命令 JMP が使われている。オペランドは「ジャンプ先であるプログラム中の位置」だが，アセンブリ言語ではプログラム中の位置をラベルで表す。プログラムの先頭を表すラベル _start と同じように，プログラム中の好きな位置にラベルを付け，それをジャンプ命令のオペランドに指定すればよい（なお，_start の先頭の _ は「特別な目的のあるラベル」の印なので，通常のラベルには使わない）。

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

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

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

ジャンプ命令は機械語ではどのようになるか，見てみよう。上記プログラムを sum10.s という名前で保存し，アセンブルして，逆アセンブルする。ELFファイル（.oファイルやa.out）の逆アセンブルは objdump コマンドを使うとできる。

$ nasm sum10.s
$ ld sum10.o
$ objdump -M intel -d a.out
-- 中略
Disassembly of section .text:

08048060 <_start>:
 8048060:       bb 00 00 00 00          mov    ebx,0x0
 8048065:       b9 01 00 00 00          mov    ecx,0x1

0804806a <loop0>:
 804806a:       01 cb                   add    ebx,ecx
 804806c:       41                      inc    ecx
 804806d:       e9 f8 ff ff ff          jmp    804806a <loop0>
 8048072:       b8 01 00 00 00          mov    eax,0x1
 8048077:       cd 80                   int    0x80

左端の16進数は，主記憶装置内での番地 (address) を表す。この機械語プログラムを起動すると，OSがa.outの中から25バイトの機械語プログラムを読み出し，主記憶装置の0x8048060番地から0x8048078番地に配置する。その後，0x8048060番地 (= _start) から実行を開始する。ラベルは「番地に付けた名前」のことだ。

jmp loop0は機械語では e9 f8 ff ff ff になっている。e9 が命令を表し，残り4バイトがオペランドだ。このオペランドは 0xfffffff8 という32ビットの数を表しているが，これは実は −8 を意味する（2の補数による負数表現）（負数の表し方は後の章で扱う）。このJMP命令の実行を行っているとき，命令ポインタ EIP はすでに次の命令の番地 0x8048072 を指しており，JMP命令がEIPに −8 を加えるので，次に実行するのは 0x804806a 番地 (= loop0) の命令になる。

条件付きジャンプ

ジャンプ命令で実行位置を戻せばループを作ることができるが，常にジャンプするのでは無限ループになってしまう。上記のプログラム例の場合，「ECXの値が10以下のときだけloop0に戻る」ようにしたいのだが，どうすればよいだろうか?

機械語プログラムでは，条件付きジャンプ命令というものを使って，このような動作を実現する。条件付きジャンプ命令を使って上記のプログラム例を書き直すと以下のようになる。

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

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

比較命令 CMP (compare) と条件付きジャンプ命令 JLE (jump if less or equal) を組にして使っている。 cmp ecx, 10 でECXの値と10を大小比較し，JLE命令で，ECXの方が小さいか等しいならloop0にジャンプする。そうでなければ次の命令（mov eax, 1）に進む。

比較命令 CMP は演算命令の一種だが，この命令を理解するためにはフラグレジスタのことを理解しなければならない。

フラグレジスタ

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

演算結果が0だった（Zeroフラグ; ZF）
演算結果が負数だった（Signフラグ; SF）
演算によって桁上がりが発生した（Carryフラグ; CF）
- 例えばEAXの値が0x60007000のときに add eax, 0xc000c000 を実行すると，本来の加算結果は33ビットの数 0x120013000 になるが，EAXには下位32ビットの 0x20013000 が代入される。このとき「桁上がり (carry) が発生した」と言う。

フラグレジスタの値は演算命令を実行するたびに更新される。

参考：i386のフラグレジスタ EFLAGS の内部構成

（上位16ビットは省略。空欄は未使用ビットまたはシステムフラグ。）
参考：i386の場合，ZF, SF, CFのほかに OF (overflow), AF (adjust), PF (parity) がある。DF (direction), IF (interrupt enable), TF (trap) は「制御フラグ」（CPUによっては，フラグレジスタの中に「CPUの動作設定のためのビット」が含まれ，これを「制御フラグ」と言う。その内，一般アプリケーションからは操作できないものを特に「システムフラグ」と言う）。
参考：「フラグレジスタ」の別名として，Program Status Register (PSR)，Condition Code Register (CCR) などがある（CPU製造者によって呼び名がちがう）。

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

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

（この表にない命令は，（一部の例外を除き）フラグを変化させない。）

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

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

比較命令CMP

ところでCMP命令だが，これは「減算命令 (SUB) と同じだが減算結果をどこにも代入しない」命令だ。つまり，減算を行うのだがオペランドの値は変化しない。ただし，フラグは変化する。例えば cmp ecx, 10 を実行したとき，ECXの値が10ならば減算結果は0になり，ZFが1になる。10より小さければ減算結果は負になり，SF, CF, OFが変化する。CMP命令の次に条件付きジャンプ命令を置くことで，これらのフラグ情報を使って，ジャンプするかしないか決めることができる。一方，いずれの場合もECXの値は変化しない（減算結果はECXに代入されない）。

以下は，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に換えたもの）上記の意味の逆

参考：「大きい」「小さい」は「符号付き（負数も扱う場合）」の大小，「上」「下」は「符号無し（0以上の数しか扱わない場合）」の大小を表す。符号については後の章で扱うが，比較する2数が0以上0x7fffffff (= 2,147,483,647) 以下なら結果は同じだ。

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, ... だ。

参考: while と do-while

上記のプログラムのループ構造を抜き出すと下記のようになる。

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

これは，C言語やJavaだと，下記のような do-while 文に相当する。

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

下記の while 文との違いは「do-while はループ本体を最低1回実行する」ことだ。 while 文は，初めから条件が偽なら，ループ本体を一度も実行しない。

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

上のwhile文と等価なループをアセンブリ言語で記述したければ，例えば以下のようにすればよい。

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

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

上記の1以上10以下の整数の総和を計算するプログラムは，以下のように記述することもできる。1, 2, 3, ... の順に加える代わりに 10, 9, 8, ... の順に加える。

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

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

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

このプログラム例では，ECXの値を1ずつ減らしていき，0より大きい間はループし，0と等しくなったらループを抜ける。 JNZ (jump if not zero) は，直前の演算結果が0でなければジャンプする命令だ。

「決まった回数繰り返す」ループの場合，いずれかのレジスタに繰り返し回数を代入し，「1ずつ減らし，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 の場合しか使えない）。
参考：loop命令が存在するので，loopという名前のラベルは使えない。

条件分岐 (if-then-else)

ジャンプ命令の飛び先はプログラム中のどこでも構わないので，前に戻ってループを作る以外に，次に続く命令を飛び越すためにも使うことができる。

再度，C言語で考えよう。「12359が17で割り切れれば0，そうでなければ1」を出力するプログラムは以下のように記述できる。

int main()
{
  int x;
  if (12359 % 17 == 0) {
    x = 0;
  } else {
    x = 1;
  }
  return x;
}

if-then-else構造は，「条件が偽ならthen節を飛び越える。条件が真ならthen節に進み，その後else節を飛び越える」構造と考えることができる。つまり，これもジャンプ命令を使って実現できるわけだ。

上記のプログラム例をアセンブリ言語で書き直すと，以下のように記述できる。

        ; 12359が17で割り切れれば0, そうでなければ1を出力
        section .text
        global  _start
_start:
        mov     eax, 12359      ; 被除数
        mov     edx, 0          ; 被除数の上位32ビット
        mov     ecx, 17         ; 除数
        div     ecx             ; edx = 12359 % 17

        cmp     edx, 0          ; 剰余が0?
        jne     else            ; 等しくなければelseへ
        mov     ebx, 0          ; then節 (x = 0)
        jmp     endif           ; else節を飛び越える
else:   mov     ebx, 1          ; else節 (x = 1)
endif:
        mov     eax, 1          ; システムコール番号
        int     0x80            ; exitシステムコール

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

スパゲッティプログラム

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

スパゲッティプログラムにしないために，以下に気をつけるとよい。

下から上に戻るジャンプは，ループを作るとき以外には使わない（プログラムが上から下に進むように作る）。
まず while と if を使ってプログラムの構造を決めてから，ここまで説明してきた「ジャンプ命令の使用パターン」に置き換えていく。
一度動くプログラムが出来たら，それは試作品と考えて，新しく書き直す。実際，「最初に作った版」には無意味なジャンプや必要ない命令が多々含まれがちだ。

練習問題

以下の問題で述べるプログラムを作りなさい。期待される出力値がいくらであるか自分たちで調べ，作ったプログラムの出力が正しいことを確認すること（期待される出力値は，フィボナッチ数の表や素数の表を探すなどして調べなさい）。

リポジトリのルートディレクトリにサブディレクトリ chap3 を作成し，その中にソースファイルを置きなさい。

参考：新しいディレクトリの中のファイルは，git add するまでは，git status を実行しても表示されない。
参考：ディレクトリをgit addすると「中のすべてのファイルをgit addする」という意味になる。ディレクトリが空の場合は何も起きない（ディレクトリそのものはコミットできない）。

演習1.3-1　フィボナッチ数 f_n を，漸化式 f₀ = 0，f₁ = 1，f_n = f_n−1 + f_n−2 (n ≧ 2) で定義する。 f₁₃ の値を計算して出力するアセンブリ言語プログラムを作りなさい。作成したプログラムを共有リポジトリにpushしなさい。ただし，リポジトリ中にサブディレクトリ chap3 を作成し，その中にソースファイルを fib13.s という名前で作成すること。

（ヒント）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)に戻る。

演習1.3-2　12379が素数かどうか判定し，素数ならば0，素数でなければ1を出力するプログラムを作りなさい。ただし，12379という定数を記述する箇所（コメントを除く）は1箇所とし，それを別の数（例えば12389）に書き換えればその数の素数判定ができるように記述すること（3未満の数に書き換えられることはないと仮定してよい）。ソースファイルを，サブディレクトリ chap3 に isprime.s という名前で作成すること。作成したプログラムを共有リポジトリにpushしなさい。ただし，演習1.3-1のプログラムをコミットしたメンバーとは別のメンバーがコミットすること（共有リポジトリ上のisprime.sの最終変更者が，fib13.sの最終変更者と異なるようにすること）。

素数とは，1とその数以外の約数を持たない2以上の整数である。

（ヒント）素数判定対象数 n が，2以上n未満の各整数 d で割り切れないことを調べればよい。 2つのレジスタを使って，nとdを表せばよい。ただし，DIV命令を使うとEAX, EDXの値が変更されてしまうので，それ以外のレジスタを使う。ESI, EDIも使ってよい。ループの中ですることは，(1) nをEAXにコピーし，EDXを0にして，dで割る，(2) 剰余が0なら n は素数でないのでループを抜ける，(3) dを1増やす，(4) dがnより小さいなら(1)に戻る。

演習1.3-3　255以下の素数の個数を計算して出力するアセンブリ言語プログラムを作りなさい。ただし，255という定数を記述する箇所（コメントを除く）は1箇所とし，それを別の数（例えば1500）に書き換えればその数以下の素数の個数が出力されるように記述すること（3未満の数に書き換えられることはないと仮定してよい）。ソースファイルを，サブディレクトリ chap3 に nprime255.s という名前で作成すること。作成したプログラムを共有リポジトリにpushしなさい。ただし，3人グループの場合，演習1.3-1及び演習1.3-2のプログラムをコミットしたメンバーとは別のメンバーがコミットすること（共有リポジトリ上のnprime255.sの最終変更者が，fib13.sの最終変更者ともisprime.sの最終変更者とも異なるようにすること）。2人グループの場合はどちらがコミットしても構わない。

（ヒント）演習1.3-2の素数判定プログラムを二重ループ化し，素数判定対象数 n を2以上255以下の範囲で変化させればよい（2は調べるまでもなく素数として，3以上255以下の範囲を調べてもよい）。素数の個数を表すためにレジスタを1個使い，n が素数とわかったら個数を1増やす。

演習1.3-4　255以下の素数のうち大きい方から10番目の数を計算して出力するアセンブリ言語プログラムを作りなさい。ただし，255という定数を記述する箇所（コメントを除く）は1箇所とし，それを別の数（例えば200）に書き換えればその数以下の大きい方から10番目の素数が出力されるように記述すること（31未満の数に書き換えられることはないと仮定してよい）。ソースファイルを，サブディレクトリ chap3 に 10thprime.s という名前で作成すること。作成したプログラムを共有リポジトリにpushしなさい。どのメンバーがコミットしても構わない。

（ヒント）演習1.3-3のプログラムにおいて，n を大きい数から順に調べるようにし，見つけた素数の個数が10になったらループを抜けるようにすればよい。

3. 条件分岐と繰り返し