自作CPU Advent Calendar 2022 4日目

CalicoCPU で Xorshift による乱数生成を行った。

3-Digit 7seg Board

基板設計データ | ソフトウェア

8ビットの入力値を7セグメントLEDで表示する。以下のモードがある。

• 16進数 (左の2桁を使用)
• 10進数 (3桁を使用)
• 直接制御 (左の1桁を使用)
• シリアル通信による直接制御 (3桁を使用)

方針

8bit用xorshift乱数発生アルゴリズム - Sim's blog
を参考にする。
今回の環境では周期65535 (= 2^16 - 1) がちょうどよさそうだが、この周期はこのサイトには載っていない。
そこで、「周期が16777215 (= 2^24 - 1)」をベースに、自分で適切な A, B, C の値を探索することにした。
以下のアルゴリズムを用いる。

uint8_t x, y, t;
t = x ^ x << a;
x = y;
y ^= y >> c ^ t ^ t >> b;
return z;

以下のC言語のプログラムで探索を行う。

#include <stdio.h>
#include <string.h>

char visited[1 << 16];

int main(void) {
	int a, b, c;
	for (a = 0; a < 8; a++) {
		for (b = 0; b < 8; b++) {
			for (c = 0; c < 8; c++) {
				unsigned char x = 0, y = 1, t;
				int count = 0;
				memset(visited, 0, sizeof(visited));
				while (!visited[x + y * 256]) {
					count++;
					visited[x + y * 256] = 1;
					t = x ^ (x << a);
					x = y;
					y ^= (y >> c) ^ t ^ (t >> b);
				}
				if (count == (1 << 16) - 1) {
					printf("%d %d %d\n", a, b, c);
				}
			}
		}
	}
	return 0;
}

以下の7通りの A, B, C の組が得られた。

3 2 5
3 2 7
5 1 2
5 1 3
5 4 3
7 1 2
7 6 1

今回は、この中から (A, B, C) = (5, 4, 3) を採用した。
以下のC言語のプログラムにより、出力するべき値が得られる。

#include <stdio.h>

int main(void) {
	unsigned char x = 255, y = 0, t;
	int i;
	for (i = 0; i < 100; i++) {
		t = x ^ (x << 5);
		x = y;
		y ^= (y >> 3) ^ t ^ (t >> 4);
		printf("%03d\n", y);
	}
	return 0;
}

このプログラムの出力の冒頭は、以下のようになった。

030
029
205
098
005
037
142
018
090
006

実装

以下が MikeAssembler 用のプログラムである。

target calico

	movi a, -1
	drive 0, a
	; A: x, B: y
loop_start:
	; t = x ^ (x << 5)
	mov c, a
	shl c, 5
	xor c, a, d
	; // y ^= (y >> 3) ^ t ^ (t >> 4)
	; t ^= t >> 4
	mov a, c
	shr a, 4
	xor c, a, d
	; t ^= y >> 3
	mov a, b
	shr a, 3
	xor c, a, d
	; x = y
	mov a, b
	; y ^= t
	xor b, c, d
	; return y
	out 0, b
	; proceed to next iteration
	movi d, loop_start
	jnz d, d

以下が、機械語をHEX形式で表したものである。

:10000000203F16808789C8C28EC28E080F0FC8C2D3
:100010008EC28E040F0BC8C28EC28E04C4CA4ECAD2
:040020004E52E3DF7A
:00000001FF

実行結果

3-Digit 7seg Board を用いて、生成した乱数を10進数で表示する。

乱数の値が計算できている。