【ORANGE-4】Xorshift【未解決の問題あり】

[前回作成したXOR演算を行うプログラム](https://qiita.com/mikecat_mixc/items/ce3a6edc14eb1c4d4f5b)を用いて、[Xorshift](https://ja.wikipedia.org/wiki/Xorshift)による乱数生成を行うことにした。
GMC-4では容量が足りなそうだったので、プログラムメモリの容量が多く、サブルーチンも作れる[ORANGE-4](http://www.picosoft.co.jp/ORANGE-4/index.html)を使うことにした。

# 方針

[8bit用xorshift乱数発生アルゴリズム - Sim's blog](https://blog.goo.ne.jp/sim00/e/33b576696be51efbb3eab4b5c61ffb87)
を用いる。
今回は、「周期が255 (= 2^8 - 1)」のアルゴリズムで、(A, B, C) = (4, 5, 3) を採用した。

生成した乱数を、2進LEDに表示する。
GMC-4の2進LEDは7ビットだが、ORANGE-4では8ビット目(最上位ビット)を7セグメントLEDの小数点に表示できるようである。

以下のC言語のプログラムにより、出力されるべき値が得られる。

```c
#include <stdio.h>

int main(void) {
	int A = 4, B = 5, C = 3;
	const unsigned char INIT_VALUE = 0x11;
	unsigned char x = INIT_VALUE;
	int i;
#if 0
	if(scanf("%d%d%d", &A, &B, &C) != 3) return 1;
#endif
	do {
		x ^= x >> A;
		x ^= x << B;
		x ^= x >> C;
		for (i = 7; i >= 0; i--) {
			printf("%d", (x >> i) & 1);
		}
		putchar('\n');
	} while (x != INIT_VALUE);
	return 0;
}
```

このプログラムの出力の最初の20行は、以下のようになった。

```
00010010
01111101
00111101
11100001
00001110
11010111
10001001
10110101
01110001
10100000
11110111
11100111
11010000
01110010
11001111
10110111
00111011
00111111
10101011
10010001
```

`0`をLEDの消灯で、`1`をLEDの点灯で表す。

ループして1ビットずつシフトする方式だと容量を多く使ってしまうようだったので、それぞれのシフト幅に合わせたシフト計算プログラムを直接書いた。
ORANGE-4で扱う値は1個が4ビットであり、2個を組み合わせて8ビットにしている。
そのため、シフト幅が4以上であれば1個の値が0固定となり、繰り上がりも考えなくてよくなるので計算が楽になる。
しかし、残念ながらサイトに載っていた周期が255になるA, B, Cの組み合わせで、全てが4以上のものは無いようだった。

# 実装

以下のプログラムは、[MikeAssembler](https://mikecat.github.io/mike_assembler/)でアセンブルできる。
また、先頭の`target orange4`を外せばORANGE-4 IDEでもアセンブルできる。

```
target orange4

	; x : [0xF]:[0xE]
	; temp: [0xD]:[0xC]

	org 0x00

	; 初期化
	ldyi 0x8
	ldi 9
	st
	ldi 1
	ldyi 0xE
	st
	ldyi 0xF
	st

main_loop:
	; xの値を出力する
	scall 0xD

	; temp = x >> 4; x ^= temp
	ldyi 0xD
	ldi 0
	st
	ldyi 0xF
	ld
	ldyi 0xC
	st
	call xor
	; temp = x << 5; x^= temp
	ldyi 0xC
	ldi 0
	st
	ldyi 0xE
	ld
	add
	ldyi 0xD
	st
	call xor
	; temp = x >> 3; x ^= temp
	; 結果の上位ニブルは、[0xF]の最上位ビットが1なら1、0なら0
	; とりあえず1としておく
	ldyi 0xD
	ldi 1
	st
	; [0xF]を1ビット左シフト
	ldyi 0xF
	ld
	add
	jmpf shift_right_carry1
	; [0xF]の最上位ビットが0だった場合、結果の上位ニブルを0にする
	abyz
	ldyi 0xD
	ldi 0
	st
	abyz
shift_right_carry1:
	; [0xF]の下位3ビットの1ビット左シフトを結果の下位ニブルに格納する
	ldyi 0xC
	st
	; [0xE]の最上位ビットをチェックする
	ldyi 0xE
	ld
	add
	jmpf shift_right_carry2
	; キャリーが無い(最上位ビットが0な)ので、計算終了
	jmpf shift_right_end

	org 0x80

shift_right_carry2:
	; キャリーがある(最上位ビットが1な)ので、結果の下位ニブルに1を足す
	ldyi 0xC
	ld
	addi 1
	st
shift_right_end:
	call xor
	; 設定した時間待つ
	ldyi 0x8
	ld
	ink
	st
	scall 0xC
	jmpf main_loop

	; [0xF]:[0xE] ^= [0xD]:[0xC]
xor:
	ldyi 0xF
	ld
	ldyi 0
	st
	ldyi 0xD
	ld
	ldyi 1
	st
	call xor_nibble
	ldyi 0xF
	st
	ldyi 0xE
	ld
	ldyi 0
	st
	ldyi 0xC
	ld
	ldyi 1
	st
	call xor_nibble
	ldyi 0xE
	st
	ret

xor_nibble:
	; A = [0] ^ [1] ([0] and [1] will be broken)
	; [2] : delta
	; 今求めているビットを表す値を1にする
	ldi 1
	ldyi 2
	st
	; 計算結果を0にする
	ldi 0
	abyz
xor_loop:
	; 入力の値の和を求める
	ldyi 0
	ld
	ldyi 1
	add
	; 和の最下位ビットをチェックする
	ldyi 0
	; take jmpf if lsb is 0
	scall 6 ; 右シフト
	jmpf xor_skip_add
	; 和の最下位ビットが1だった場合、計算結果に今求めているビットを表す値を加える
	abyz
	add
	abyz
xor_skip_add:
	; 入力の値をそれぞれ1ビット右シフトする
	ld
	scall 6 ; 右シフト
	st
	ldyi 1
	ld
	scall 6 ; 右シフト
	st
	; 今求めているビットを表す値を1ビット左シフト(2倍)する
	ldyi 2
	ld
	add
	st
	; 今求めているビットを表す値がゼロでなかったら、次のビットの計算に行く
	cpi 0
	jmpf xor_loop
	; 計算結果をAレジスタに格納する
	abyz
	ret
```

以下が、機械語をORANGE-4のモニターに入力する用の形式に変換したものである。

```
E00:A889481AE4AF4EDA
E10:D804AF5AC4F6095A
E20:C804AE56AD4F6095
E30:AD814AF56F432AD8
E40:042AC4AE56F80F86
E80:AC5914F6095A8504
E90:ECF0DAF5A04AD5A1
EA0:4F60C0AF4AE5A04A
EB0:C5A14F60C0AE4F61
EC0:81A24802A05A16A0
ED0:E6FD82625E64A15E
EE0:64A2564C0FC82F61
```

ORANGE-4のプログラム領域を過不足無くピッタリ使い切る結果になった。

# 実行結果

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

最初のうちはうまく乱数を計算することができたが、乱数を数十個程度生成した所で暴走してしまうようで、以下の症状が見られた。

* 正常動作時と比べ2進LEDが明るくなる
* 7セグメントLEDの小数点(乱数の最上位ビット)が点灯しなくなる
* キー操作が効かなくなる

なお、今回使用したORANGE-4のファームウェアバージョンは1.09である。
(記事執筆時点で[ORANGE-4のサイト](http://www.picosoft.co.jp/ORANGE-4/index.html)には「最新ファーム(Ver 1.08)」とあるが、本当に1.09より1.08の方が新しいのかな…？)