繰り返しと条件分岐

ループとジャンプ命令

演習0.2-1　 0x00〜0x0c番地に 01 01 00 01 02 01 03 01 01 02 06 06 00 を書き込みなさい。どのような動作をするプログラムか，実際に実行して確かめなさい。

演習0.2-1のプログラムのアセンブリ表記は以下の通り。

  mov a, 0      // a = 0
  mov b, 1      // b = 1
  add a, a, b   // a = a + b
  b   0x06      // jump to 'add'
  hlt

06 xx（ニーモニックは b (branch)）は，「実行位置を xx 番地にせよ（xx 番地に行け）」という機械語命令である。このような実行位置を変更する命令を総称してジャンプ命令と呼ぶ。上記のプログラムでは，b 0x06 を実行すると実行位置が 0x06 番地（すなわち add a, a, b）に戻る。以降，0x06〜0x0b 番地を繰り返す（無限ループ。Stopボタンを押すと止まる）。

このように，ジャンプ命令で手前の命令の位置に戻ることでループを実現できる。（音楽プレイヤーのループ再生に似ている。）

ジャンプ命令が行っているのは，単に命令ポインタ (IP) の値を変更することだけである。 CPUは，1命令実行するたびに命令ポインタが指す番地から次の命令を読み出して実行するよう作られている。命令ポインタの値を変更することで，プログラム中の別の位置に「ジャンプ」することができる。

（なお，上記のプログラムの末尾の hlt 命令は，そこに決して到達しないので冗長である。ただし，いつも末尾に hlt 命令を置くよう習慣づけておいた方が安全。）

条件付きジャンプ命令

演習0.2-2　演習0.2-1のプログラムを改造し，以下のアセンブリ表記と等しくなるようにしなさい（最初の3命令は演習0.2-1と同じ）。実行して結果を確認しなさい。

  mov a, 0      // a = 0
  mov b, 1      // b = 1
  add a, a, b   // a = a + b
  mov c, 0x0a   // c = 10
  cmp a, c      // compare a and c
  bne 0x06      // jump to 'add' if a != c
  hlt

cmp命令のオペコードは 05，bne命令のオペコードは 0a である。

（このプログラムでは末尾の hlt 命令は必須。条件付きジャンプ命令 bne においてジャンプしない場合は次の命令に進むから。）

b命令による無条件ジャンプだけでは無限ループしか作ることができない。「条件が真であればジャンプせよ」という命令（条件付きジャンプ命令）を使うことで，高級言語の while と同じように，条件が真である間だけ繰り返すことができる。

0a xx（ニーモニックは bne (branch if not equal)）は「等しくなければ xx 番地にジャンプせよ（等しいならこの命令を無視して次に進め）」という命令である。条件付きジャンプ命令として他に，beq (branch if equal)（等しいならジャンプせよ），bgt (branch if grater than)（大きいならジャンプせよ），などがある。「等しくない」「等しい」「大きい」とはどういう意味だろうか?

これらの条件付きジャンプ命令は通常，cmp命令 (compare) と組にして使う。条件付きジャンプ命令の直前にcmp命令を実行し，例えば bne は「cmp命令の2引数が等しくなければジャンプせよ」，bgt は「cmp命令の第1引数が第2引数より大きいならジャンプせよ」という意味になる。以下，もう少し詳しくこの仕組みを説明する。

フラグと条件付きジャンプ

演算命令（ミクロンの場合は add, sub, cmp の3つ）を実行すると，特殊レジスタである Z フラグ及び C フラグの値が自動的に変化する。

Z (zero) フラグは，演算結果が0であったとき T（真），そうでなかったとき F（偽）になる。
C (carry) フラグは，演算によって下から9ビット目への桁上がり（減算の場合は桁借り）が発生したとき T（真），そうでなかったとき F（偽）になる。

cmp命令は実は「結果を保存しない減算」である。つまり，sub と同じように減算を行うが，減算結果自体は捨ててしまう。ただしフラグは sub と同じように変化させる。従って，レジスタx, y に対してcmp x, yを実行したとき，Zフラグ・Cフラグの値は以下のようになる。

xの値とyの値が等しいとき，（x − y を計算すると 0 になるので）Z フラグが T になる。等しくなければ Z フラグが F になる。
xの値がyの値より小さいとき，（x − y を計算すると桁借りが発生するので）C フラグが T になる。xの値がyの値以上のとき，C フラグが F になる。

条件付きジャンプ命令は，Zフラグ・Cフラグの値に応じて，ジャンプするかしないかを決める。具体的には以下の通り。

beq ... Z = T ならジャンプ
bne ... Z = F ならジャンプ
bgt ... Z = F かつ C = F ならジャンプ
bge ... C = F ならジャンプ
ble ... Z = T または C = T ならジャンプ
blt ... C = T ならジャンプ

補足：カウントダウン形のループ

演習0.2-3　演習0.2-2のプログラムを改造し，以下のアセンブリ表記と等しくなるようにしなさい。実行して結果を確認しなさい。

  mov a, 0x0a   // a = 10
  mov b, 1      // b = 1
  sub a, a, b   // a = a - b
  bne 0x06      // jump to 0x06 if a != 0
  hlt           // halt

上述のように，cmpだけでなくaddやsubでもフラグは変化する。そして条件付きジャンプ命令はフラグの値に応じてジャンプするかどうか決めるだけなので，必ずしもcmpと一緒に使わなくてもよい。演習0.2-3のプログラムのように「ある値から1ずつ減らしていき，0になるまで繰り返す」ような場合，1減らした結果 0 になったかどうかがZフラグに格納されるので，1減らすsub命令とbne命令の組でループを実現できる。（少ない命令でループを実現できるので，この形のループは機械語プログラムではしばしば用いられる。）

参考：whileとdo-while

演習0.2-2のプログラム中のループは，C言語やJavaのwhile文ではなくdo-while文に当たる。すなわち，ループ本体を少なくとも1回実行した後で，繰り返しを続けるか否か判定を行う。

演習0.2-2のプログラムのアセンブリ表記:

  mov a, 0      // a = 0
  mov b, 1      // b = 1
  add a, a, b   // a = a + b
  mov c, 0x0a   // c = 10
  cmp a, c      // compare a and c
  bne 0x06      // jump to 'add' if a != c
  hlt

上記プログラムをC言語風に書いたもの:

  a = 0;
  b = 1;
  do {
    a = a + b;
  } while (a != 10);

以下のように，ループ本体を実行する前に繰り返し条件を調べるようにすれば，while文と同じ動作をさせることができる。 5命令目の条件付きジャンプは「繰り返しをやめる」ジャンプなので，演習0.2-2のプログラムの条件付きジャンプ命令とは条件の真偽が逆になっている。また，ループの末尾にループの先頭に戻る無条件ジャンプ命令が必要である。

  mov a, 0      // a = 0
  mov b, 1      // b = 1
  mov c, 0x0a   // c = 10
  cmp a, c      // compare a and c
  beq 0x14      // jump to 'hlt' if a == c
  add a, a, b   // a = a + b
  b   0x06      // go back to 'mov c, 0x0a'
  hlt

上記プログラムをC言語風に書いたもの:

  a = 0;
  b = 1;
  while (a != 10) {
    a = a + b;
  }

条件分岐

条件付きジャンプ命令は，高級言語の if のような条件分岐にも使うことができる。

演習0.2-4　以下のアセンブリ表記と等しい機械語プログラムを書きなさい。このプログラムは何を行うプログラムか考えなさい。 0xf0 番地に好きなデータ値を書き込んで実行し，結果を確かめなさい。

  mov c, 0xf0
  ldr a, c      // a = mem[0xf0]
  mov b, 0x64   // b = 100
  cmp a, b
  blt 0x12      // jump to 'str' if a < b
  sub a, a, b   // a = a - b
  str a, c      // mem[0xf0] = a
  hlt

演習0.2-4のプログラムは，C言語風に書けば以下のようになる。

  c = 0xf0;
  a = mem[c];
  if (a >= 100) {
    a = a - 100;
  }
  mem[c] = a;

つまり，0xf0 番地の値が 100 以上ならその値を 100 減らす，という処理を行う。

高級言語の if は「条件が真ならばthen節であるブロックを実行」する機構だが，これは「条件が偽ならばthen節を実行せずに飛び越える（スキップする）」機構と言い換えることができる。従って条件付きジャンプ命令で実現できる。演習0.2-4のプログラムでは，レジスタAの値が100より小さいときにblt命令でジャンプすることにより，「A が 100 以上ならば sub を実行する（そうでなければ実行しない）」ことを実現している。

if-then-else

演習0.2-4のプログラムを，C言語風に書くと以下のようになるように改造しよう。

  c = 0xf0;
  a = mem[c];
  if (a >= 100) {
    a = a - 100;
  } else {          // 追加
    a = a + 100;    // 追加
  }
  mem[c] = a;

演習0.2-5　演習0.2-4のプログラムを，以下のアセンブリ表記と等しくなるように改造しなさい。 0xf0 番地に好きなデータ値を書き込んで実行し，結果を確かめなさい。

  mov c, 0xf0
  ldr a, c      // a = mem[c]
  mov b, 0x64   // b = 100
  cmp a, b
  blt 0x14      // jump to 'add' if a < b
  sub a, a, b   // a = a - b
  b   0x18      // jump to 'str'
  add a, a, b   // a = a + b
  str a, c      // mem[c] = a
  hlt

if-then-else 文も if-then 文と同じ考え方でプログラムできるが，then節を実行したときにはelse節を実行しないようにする必要がある。演習0.2-5のプログラムでは，then節の末尾に無条件ジャンプ命令 b を置いて，then節を実行したときはelse節をスキップするようにしている。

16ビット同士の加減算

ミクロンの加減算命令add, sub（と cmp）は8ビットの値同士の加減算を行う命令である。ミクロンにはこれら以外に演算命令はない。では，8ビットを超える桁数（例えば16ビット）の加算や減算は，ミクロンでは不可能なのだろうか?

……そんなことはなく，加算や減算を何回かに分けて行えば，基本的に何桁同士でも加算や減算が可能である。その際，C (carry) フラグが重要な役割を果たす。

例として，0xf0〜0xf1番地に格納されている16ビットの値 x に 15000 (= 0x3a98) を加えるプログラムを作ってみよう。なお，x の下位8ビットが0xf0番地，上位8ビットが0xf1番地に格納されているとする。（このような格納方式をリトルエンディアン (little endian) という。参考: エンディアン）

演習0.2-6　

以下のアセンブリ表記と等しい機械語プログラムを書きなさい。さらに，0xf0番地と0xf1番地にそれぞれ 0xa8 と 0x61 を書き込みなさい。プログラムを実行し，結果を確認しなさい。
0xf0番地と0xf1番地にそれぞれ 0x44 と 0x61 を書き込みなさい。同じプログラムを実行し，結果を確認しなさい。

  mov b, 0xf0
  ldr a, b     // a = mem[0xf0]
  mov c, 0x98
  add a, a, c  // a = mem[0xf0] + 0x98
  str a, b     // mem[0xf0] = a
  mov b, 0xf1
  ldr a, b     // a = mem[0xf1]
  bge 0x1f     // jump to 'mov c,0x3a' if not carry
  mov c, 1
  add a, a, c  // a = a + 1 (carry)
  mov c, 0x3a
  add a, a, c  // a = mem[0xf1] + 0x3a + carry
  str a, b     // mem[0xf1] = a
  hlt

演習0.2-6のプログラムは，0xf0〜0xf1番地の16ビットの値に 0x3a98 (= 15000) を加算する。演習0.2-6の1では，0xf0〜0xf1番地に 0x61a8 (= 25000) を格納した上で実行し，2では 0x6144 (= 24900) を格納した上で実行する。前者の結果は 40000 (= 0x9c40)，後者の結果は 39900 (= 0x9bdc) になるはずである。

16ビット同士の加算は，基本的には，下位8ビット同士の和と上位8ビット同士の和をそれぞれ計算すればよい。ただし，下位8ビット同士の加算で桁上がりが発生したときは，その桁上がり分を上位8ビットの和に加える必要がある。

          1
   01100001 10101000  (= 0x61a8 = 25000)
+) 00111010 10011000  (= 0x3a98 = 15000)
-----------------------
   10011100 01000000  (= 0x9c40 = 40000)

   01100001 01000100  (= 0x61a8 = 24900)
+) 00111010 10011000  (= 0x3a98 = 15000)
-----------------------
   10011011 11011100  (= 0x9bdc = 39900)

0x09〜0x0c 番地のadd a, a, cで，下位8ビット同士の和を計算している。このとき，上位バイトへの桁上がりが発生していればCフラグが T になる。 bgeはCフラグが F ならばジャンプするので，下位バイトの和で桁上がりが発生したときのみ mov c, 1 と add a, a, c が実行され，レジスタAに 1 加算される。（なお，演算命令以外ではフラグが変化しないので，add a, a, c と bge の間の str, mov, ldr ではフラグは変化しない。）

最後に，レジスタAに 0x3a を加えて0xf1番地に書き込むことで，0xf1番地には上位8ビット同士，及び，下位8ビットからの桁上がりを加算した和が格納される。

練習問題

演習0.2-7　以下の各プログラムを作成し，プログラムを格納したメモリの中身をファイルに保存して提出しなさい。提出ファイル名は各小問で指定する。異なる名前のファイルは提出できないので注意。提出方法は後述。期限は別途指示する。小問4〜5はオプション課題である。

各小問とも，実行開始時の 0xf0〜0xff 番地の値を変更しても正しく動作するようにすること（提出するhexファイルの 0xf0〜0xff 番地の値は何であっても良い）。

提出前に後述の検査プログラムを使って検査すること。検査に合格しない提出物は提出できない。

1以上10 (= 0x0a) 以下の整数の総和を計算し，0xf0 番地に格納して停止するプログラムを作りなさい。（提出ファイル名: sum10.hex）
1以上30 (= 0x1e) 以下の奇数の総和を計算し，0xf0 番地に格納して停止するプログラムを作りなさい。（提出ファイル名: sumodd30.hex）
0xf0〜0xff 番地に順に 0xff, 0xfe, 0xfd, …, 0xf1, 0xf0 を書き込んで停止するプログラムを作りなさい。（提出ファイル名: fftof0.hex）
（オプション課題）0xf0〜0xff 番地の各値（それぞれ0以上255以下）の最大値を求め，0xe0 番地に格納して停止するプログラムを作りなさい。（提出ファイル名: max.hex）
（オプション課題）1以上200 (= 0xc8) 以下の整数の総和を16ビットの値として計算し，下位8ビットを 0xf0 番地，上位8ビットを 0xf1 番地に格納して停止するプログラムを作りなさい。（下の注1を参照。）（提出ファイル名: sum200.hex）

注1）8ビットを超える2進数をメモリに保存するときに，下位桁を小さい番地に，上位桁を大きい番地に格納することを，リトルエンディアン (little endian) と言う。第I部以降で扱う i386 や ARM もリトルエンディアンを採用している（ただし ARM は設定で変更可能）。上位桁を小さい番地に格納するビッグエンディアンを採用しているCPUも存在する。

（ヒント）

まずはC言語やJavaで書いてみるとよい。「1, 2, 3, …, 10 を順にとる変数」と「現時点の合計を保持する変数」を使うと思うが，単に2つのレジスタをそれらの目的に使えばよいだけである。残り1個のレジスタを各種作業用（1増やすときに1を格納したり，10と等しいか調べるときに10を格納したり）に使えばよい。
小問1の「1, 2, 3, …, 10 を順にとる」が「1, 3, 5, …, 29 を順にとる」に変わるだけ。
2個のレジスタを「0xf0, 0xf1, …, 0xff を順にとるレジスタ」と「0xff, 0xfe, …, 0xf0 を順にとるレジスタ」にそれぞれ使えばさほど難しくない。繰り返し条件の設計によっては，0xff に1加えると 0 になることに注意が必要（「等しいか等しくないか」なら問題ない。「大きいか小さいか」だと注意が必要）。
C言語やJavaで書いてみてから機械語に翻訳すればよい。ただ，レジスタ3個だけでやりくりするのが少し面倒。「0xf0, 0xf1, …, 0xff を順にとるレジスタ」に1個使い，残りの2個は作業用にするのが一つの案である。「現時点の最大値」を常に 0xe0 番地に置くことにすれば，ループで行う処理は「0xe0 番地の値と A が指す番地の値をそれぞれ B, C に読み出し，C の方が大きければそれを 0xe0 番地に書き込む」となる。この処理は B, C だけでできる。
小問1や2とアルゴリズムはほとんど同じで，桁上がりが起きたときに上位バイトに1を加算すればよいだけだが，これもレジスタのやりくりが面倒。小問4と同じく，「1, 2, …, 200 を順にとるレジスタ」に1個使い，残り2個を作業用とするのが一案。ループで行う処理は「0xf0 番地の値を A の値だけ増やす。上位バイトへの桁上がりが起こっていたら，0xf1 番地の値を1だけ増やす」となる。movやstrを実行してもフラグは変わらないことを利用するとよい。なお，開発中は 200 ではなく 30 や 50 等の小さい値を使い，計算結果が正しいことを確かめてから大きい数に変えるとよい。

検査プログラム & 提出方法

コマンド名が ~y-takata/Public/pl2test027 及び ~y-takata/Public/pl2submit027（演習0.2-7の検査・提出という意味）に変わるだけで，使い方は演習0.1-8のときと同じである．

$ ~y-takata/Public/pl2test027 sum10.hex
$ ~y-takata/Public/pl2test027 sumodd30.hex
$ ~y-takata/Public/pl2test027 fftof0.hex
$ ~y-takata/Public/pl2test027 max.hex
$ ~y-takata/Public/pl2test027 sum200.hex

$ ~y-takata/Public/pl2submit027 sum10.hex sumodd30.hex
$ ~y-takata/Public/pl2submit027 fftof0.hex max.hex sum200.hex

2. 繰り返しと条件分岐