【GMC-4】LEDが3個点灯するナイトライダー

この記事を発見した。
[大人の科学 vol24: Yoshiのブログ](https://yoshi-s.cocolog-nifty.com/cpu/2012/09/vol24-460a.html)
この中に、ナイトライダーについて以下の記述があった。

> 　LEDが1個流れるのは簡単で、3個が流れるのはちょっと面倒、
> 最小はプログラム38ワード、データ2ワードだ。　どうよ ＞T君

そこで、LED3個を流すプログラムの作成に挑戦することにした。

# 仕様

記事に掲載されていた動画から、以下の仕様が読み取れた。

* 2進LEDの点灯位置が左右に往復する
* LEDは3個のかたまりで点灯させる
* 端においても、止まっている時間は中間地点と同じで、2倍にはならない
* 点灯する位置は約0.1秒間隔で切り替える (0.25倍速での再生で、4段階移動するのに約1.6秒かかった)

# 実装

アセンブリ言語のプログラムは[MikeAssembler](https://mikecat.github.io/mike_assembler/)でアセンブルできる。

## とりあえず動かす

最初にLEDを3個点灯させ、左方向への動きと右方向への動きを別のループで表現した。
正の数を加算し、実行フラグが0になった状態だと `CAL` 系の命令を実行できないので、
加算を2回に分割して実行フラグが1になるようにした。

```
target gmc4

	TIA 0
	TIY 2
	CAL SETR
	TIY 1
	CAL SETR
	TIY 0
	CAL SETR
loop1:
	CAL TIMR
	CAL RSTR
	AIY 4
	AIY -1
	CAL SETR
	AIY -2
	CIY 4
	JUMP loop1
loop2:
	CAL TIMR
	AIY 3
	AIY -1
	CAL RSTR
	AIY -3
	CAL SETR
	CIY 0
	JUMP loop2
	JUMP loop1
```

以下は、このプログラムの機械語表現である。

```
  | 0 1 2 3  4 5 6 7  8 9 A B  C D E F
--+-----------------------------------
0 | 8 0 A 2  E 1 A 1  E 1 A 0  E 1 E C
1 | E 2 B 4  B F E 1  B E D 4  F 0 E E
2 | C B 3 B  F E 2 B  D E 1 D  0 F 1 F
3 | F 0 E
```

プログラム51ワード、データ0ワードである。

データだけなら、既に記事が主張する「最小」より少ない。
しかし、プログラムを実行前に手動で入力されることが要求されるGMC-4において、やはりプログラムの長さの方が使い勝手に繋がる重要なパラメータであろう。

## 1個のループで表現する

「とりあえず動かす」のプログラムには、似た形のループが2個あり、それぞれに `JUMP` が使われている。
さらに、`CAL SETR` や `CAL RSTR` がそれぞれのループに加え、ループに入る前の初期化でも使われている。
そこで、これらを共通化することでプログラムを短縮したい。
特に、`JUMP` は3ワードも食うので、なるべく使わないようにしたい。
そこで、左右2方向のLEDの移動を、1個のループのみで表現する方法を考えた。

今回の「7個の枠の中をLEDが3個並んで往復する」という設定では、以下の8個の状態がある。
(LEDの消灯を `0`、点灯を `1` で表現する)

|状態|LED|次の移動|
|:-:|:-:|:-:|
|1|`0000111`|左|
|2|`0001110`|左|
|3|`0011100`|左|
|4|`0111000`|左|
|5|`1110000`|右|
|6|`0111000`|右|
|7|`0011100`|右|
|8|`0001110`|右|

状態が8個なので、3ビットのカウンタを単純に回すことで表現できる可能性がある。

4ビットのレジスタに2ずつ加算し、上位3ビットをカウンタとして用いる。
このカウンタの値に8 (2進数で `1000` を足すと、キャリーの有無 (実行フラグ) で最上位ビットが0か1かを判別できる。
そして、`CAL` 系の命令は実行フラグが1のときのみ実行される性質を利用し、
カウンタの最上位ビットが1であったときのみ `CAL CMPL` 命令でビットNOTをとってみた。
さらに1を引いて調整し、`CAL SIFT` 命令で1ビット右シフトすると、以下のように都合よく往復する数が得られた。

```
     +8   CMPL -1   SIFT
0000 1000 1000 0111 0011 (3)
0010 1010 1010 1001 0100 (4)
0100 1100 1100 1011 0101 (5)
0110 1110 1110 1101 0110 (6)
1000 0000 1111 1111 0111 (7)
1010 0010 1101 1100 0110 (6)
1100 0100 1011 1010 0101 (5)
1110 0110 1001 1000 0100 (4)
```

得られた値から1を引くと、2進LEDを点灯させる一番左の場所の番号が得られる。
そこから1ずつ引き、残りのLEDも点灯させる。
ウェイトを入れた後、次のステップでも必ず点灯させる真ん中のLEDは点灯させたままにし、次のステップでは点灯させない可能性がある左右のLEDを消灯させる。
カウンタから点灯位置への変換処理によってカウンタの値は破壊されるため、データメモリに保存しておく。

以下が、以上を実装したプログラムである。
ループの前に、カウンタとそれを保存するアドレス(兼ウェイト時間)を初期化している。

```
target gmc4

	TIA 0
	TIY 0
	AM
loop:
	AIA 8
	CAL CMPL
	AIA -1
	CAL SIFT
	AIA -1
	CY
	CAL SETR
	AIY -1
	CAL SETR
	AIY -1
	CAL SETR
	CAL TIMR
	CAL RSTR
	AIY 3
	AIY -1
	CAL RSTR
	CY
	MA
	AIA 2
	AM
	JUMP loop
```

以下は、このプログラムの機械語表現である。

```
  | 0 1 2 3  4 5 6 7  8 9 A B  C D E F
--+-----------------------------------
0 | 8 0 A 0  4 9 8 E  4 9 F E  6 9 F 3
1 | E 1 B F  E 1 B F  E 1 E C  E 2 B 3
2 | B F E 2  3 5 9 2  4 F 0 5
```

プログラム44ワード、データ1ワードである。

## 計算をまとめる

「1個のループで表現する」のプログラムでは、`CAL SIFT`の前に1を引き、後でも1を引いている。
しかし、少し考えると、この2回の減算は1回にまとめられることがわかる。
そこで、これをまとめることで、プログラムのサイズを減らす。

以下が、これを適用したプログラムである。
ついでに、点灯位置の切り替えを遅くしての動作確認をしやすいよう、冒頭の初期化における `TIY 0` (これによりウェイト時間が決まる) を `TIA 0` の前に移動した。

```
target gmc4

	TIY 0
	TIA 0
	AM
loop:
	AIA 8
	CAL CMPL
	AIA -3
	CAL SIFT
	CY
	CAL SETR
	AIY -1
	CAL SETR
	AIY -1
	CAL SETR
	CAL TIMR
	CAL RSTR
	AIY 3
	AIY -1
	CAL RSTR
	CY
	MA
	AIA 2
	AM
	JUMP loop
```

以下は、このプログラムの機械語表現である。

```
  | 0 1 2 3  4 5 6 7  8 9 A B  C D E F
--+-----------------------------------
0 | A 0 8 0  4 9 8 E  4 9 D E  6 3 E 1
1 | B F E 1  B F E 1  E C E 2  B 3 B F
2 | E 2 3 5  9 2 4 F  0 5
```

プログラム42ワード、データ1ワードである。

## 初期化を省略する

記事に掲載されている動画には、プログラムの実行を開始するところは映っておらず、LEDの点灯位置が往復している場面のみが映っている。
したがって、実行開始直後は多少動作が安定しなくても、その後安定してLEDの点灯位置を往復させればよいと解釈できる。

「1個のループで表現する」ではカウンタとして用いるレジスタの最下位ビットが0のときを考えたが、最下位ビットが1のときのレジスタの値と変換後の値の関係を確認しよう。

```
     +8   CMPL -1   SIFT
0001 1001 1001 1001 0100 (4)
0011 1011 1011 1010 0101 (5)
0101 1101 1101 1100 0110 (6)
0111 1111 1111 1110 0111 (7)
1001 0001 1110 1101 0110 (6)
1011 0011 1100 1011 0101 (5)
1101 0101 1010 1001 0100 (4)
1110 0111 1000 0111 0011 (3)
```

位相は少しずれたものの、都合よく最下位ビットが0のときと同じ範囲を往復する値が得られた。
よって、プログラムの実行開始時のカウンタの値が0～0xFのどの値であっても、LEDの往復動作ができる。
そこで、プログラムの実行開始時にカウンタを初期化する処理を省略することにした。

以下は、これを適用したプログラムである。

```
target gmc4

	TIY 0
loop:
	AIA 8
	CAL CMPL
	AIA -3
	CAL SIFT
	CY
	CAL SETR
	AIY -1
	CAL SETR
	AIY -1
	CAL SETR
	CAL TIMR
	CAL RSTR
	AIY 3
	AIY -1
	CAL RSTR
	CY
	MA
	AIA 2
	AM
	JUMP loop
```

以下は、このプログラムの機械語表現である。

```
  | 0 1 2 3  4 5 6 7  8 9 A B  C D E F
--+-----------------------------------
0 | A 0 9 8  E 4 9 D  E 6 3 E  1 B F E
1 | 1 B F E  1 E C E  2 B 3 B  F E 2 3
2 | 5 9 2 4  F 0 2
```

プログラム39ワード、データ1ワードである。

# 2段階加算を解消する

「初期化を省略する」のプログラムでは、操作する2進LEDの位置に2を足した後に実行フラグを1にして `CAL RSTR` を実行するため、
「2を足す」処理を「3を足す」と「1を引く」に分けて実行している。

ここで、`TIY` 命令および `TIA` 命令は実行フラグを常に1にすることに注目した。
一番最初に実行している `TIY 0` を、この2段階目の加算の代わりに入れることで、実行フラグを1にして `CAL RSTR` を実行できる。
なお、この位置では `CY` 命令によりレジスタを入れ替えているので、`TIA 0` 命令を置く。

この最初の初期化 `TIY 0` を移動することの影響を確認する。
プログラムの実行開始からこの2段階加算の位置までで、初期化対象のレジスタ (`CY` 命令まではYレジスタ、`CY` 命令からはAレジスタ) を参照する命令は `CY` 命令と `CAL TIMR` 命令しかない。
したがって、`CAL TIMR` 命令による最初の待機時間が変わりうるが、これは最大でも1.6秒である。
また、2周目以降の待機時間は、2段階加算のかわりに置いた `TIA 0` 命令により0.1秒に設定される。
さらに、データメモリへのアクセスはこの2段階加算の場所の後にしかないため、未初期化のアドレスを用いることはない。
よって、この初期化を移動することの害は十分小さいと考えられる。

これを適用したプログラムが以下である。

```
target gmc4

loop:
	AIA 8
	CAL CMPL
	AIA -3
	CAL SIFT
	CY
	CAL SETR
	AIY -1
	CAL SETR
	AIY -1
	CAL SETR
	CAL TIMR
	CAL RSTR
	AIY 2
	TIA 0
	CAL RSTR
	CY
	MA
	AIA 2
	AM
	JUMP loop
```

以下は、このプログラムの機械語表現である。

```
  | 0 1 2 3  4 5 6 7  8 9 A B  C D E F
--+-----------------------------------
0 | 9 8 E 4  9 D E 6  3 E 1 B  F E 1 B
1 | F E 1 E  C E 2 B  2 8 0 E  2 3 5 9
2 | 2 4 F 0  0
```

プログラム37ワード、データ1ワードである。
記事で最小と主張していた「プログラム38ワード、データ2ワード」より、**プログラム、データともに少ないワード数**で処理を実現できた。

# 実行結果

以下が、「2段階加算を解消する」のプログラムを実行した結果である。
最初に動き出すまでは少し時間がかかるものの、動き出してからはきれいにLEDの点灯位置が往復している。

<iframe width="560" height="315" src="https://www.youtube.com/embed/GVK3KnkkdkM" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

# 結論

記事で最小と主張している「プログラム38ワード、データ2ワード」より少ない、プログラム37ワード、データ1ワードで、GMC-4の7個の2進LEDのうち連続した3個を点灯させ、その点灯位置を左右に往復させる処理を実現できた。