Brainf**kの命令を直接実行できるCPUを作ってみる

きっかけ

ある日、YouTubeショートを眺めていたら、面白そうなプログラミング言語を見つけました。
その言語はBrainfuckといいその名の通りbrainがFUCK!!!するほどの難解言語の一つで、
使えるのはたったの8文字だけだそうです。

そしてこの言語の命令を見ているうちに((これCPUでもできそうだな))と思いやってみることにしました。
今回はLigisim evolutionというソフトで開発します。

Brainfuckの命令一覧

記号	意味
>	メモリの番地を右に1つ移動する(ポインタ++)
<	メモリの番地を左に1つ移動する(ポインタ--)
+	ポインタが指すメモリの値を+1する
-	ポインタが指すメモリの値を-1する
,	入力から1バイト読み込んで指しているポインタに代入する
.	ポインタが指す値(メモリの値)を文字として出力する
[	ポインタが指すが0なら対応する ] までジャンプする(JEQ)
]	ポインタが指す値が0でないなら対応する [ までジャンプする(JNE)

(ほらね以外とできそうでしょ?)

構想

• 命令は3bitで可能
• メモリのセルサイズは65536(16bit)
• 必要そうなのはRAM,ROM,PC,CPUコントローラー,IO(ASCIIテーブル),ポインタカウンタ
• • rom 4bit
• • ram　8bit
• • PC 16bit
• • pointer 16bit
• • AR(アドレスレジスタ) 16bit

RAMは文字出力の時都合がいいから8bitに、
PC,pointer,ARは実行できる命令を増やすために16bitにした
4bitだと15文字しか打てないからね...

課題:どうやってジャンプ命令を実装するか

案1 sp([のアドレスを示すレジスタ),ep(]のアドレスを示すレジスタ)を追加する
⇢ネストした時のためにPOP/PUSH作んなきゃいけなくてだるくなる

案2 自動で],[の位置を特定させる
⇢時間がかかる、だるい、非効率

案3 ROMに直接アドレスを入れる
⇢少し効率は落ちるが思いついた中では一番マシ。色々ごっちゃになるけど許して...

　
ということで[を細かく分解して

1. ARにアドレス(下8bit)を読み込ませる
2. ARにアドレス(上8bit)を読み込ませる
3. PC=AR(JMP])

という感じで実装する。(初期段階、V1)
Brainf**k にはもともとPC(プログラムカウンタ)という存在がなかったから問題なし!!

アセンブリ構想

0ooo

oオペコード

o	OP	意味
000	INC P	>と同義
001	DEC P	<と同義
010	INC M[p]	+と同義
011	DEC M[P]	-と同義
100	IN	,と同義
101	OUT	.と同義
110	JEQ AR	ゼロなら]にジャンプ([と同義)
111	JNE AR	ゼロじゃないなら[にジャンプ(]と同義)

1bit目が1なら対応する命令がないのでnopってことになります。

早速作っていく

V1

いつも通りHACKのようにユニットを分けて作りました。

ユニットの役割は以下の通り

programUNIT

PC(プログラムカウンタ)と命令ROMを統合したものです

controlUNIT

命令を分析して各ユニットに信号を送ります。

ポート名	意味
usePOINTER	ポインタを更新するかどうか
inc_P	ポインターをインクリメントするか
useMEMORY	メモリを書き換えるか
memoryinc	メモリをインクリマンとするか
useIO	IOを使うか
IOtype	IOのタイプ　1ならOUT
IO_ALdata	OUT出力データ＆ARデータ
ALHL	ARの上位8bit/下位8bitどっちを書き換えるか決める　1なら下位8bit
AL	ARを更新するか

※ALとARスペルミスってます　正しくはARです。

memoryUNIT

ポインタとメモリを統合しています。

IOUNIT

IOはROMとRAMを使って再現します
Input時はROMで値だけを出力しOutputはRAMを使って書き換えられるようにしました。

---

結果

無理!!

ジャンプ、IO命令にで不具合が発生。リアルで一日費やしても治んなかったので作り直すことにしました...

アドレスレジスタに0xCを格納する命令を実行した結果↓

V2

8bitだとみにくいし回路が肥大化するので4bitにしました。
アドレス格納方式もAR上位/下位書き換えから4bitレジスタ4個で格納する分散方式にしました。
UNIT構成、役割は変わってないので割愛。

---

結果

まあまあ...

ジャンプ命令は動作するようになったがIO命令が動作しない
これまた一日費やしたが直せる見込みがないのでV3を作ることにした
(このままだと期限に間に合わない...)

V3

V1,V2...と色々試行錯誤した結果、全てのユニットを一つにまとめて操作した方が簡単に作れるしデバックも簡単になることがわかったので今回は一つの回路にまとめて作ります。

---

結果

成功!!
IO命令だって動くしジャンプも正常に動作する　やったー

---

Central Control Unit

せっかくなので詳しく解説します。
V1,V2のユニットをIO以外全てこれに統合しました。

今は色々バグ修正したり改良したせいで画像と少し回路が違うけど原理は全く同じだから安心して!!

---

1 命令デコーダー

I(命令)を4bit->3bitにしてデマルチプレクサで信号を送るか制御します。
5の"ジャンプ制御"でジャンプアドレスをレジスタに格納している間は出力信号を0にして命令を無視します。
(アドレスと命令の混同を防ぐため)

2ジャンプ判定

8の入力を持つORゲートを使用します。
ORゲートは入力のどれかのビットが1なら1を出力する回路です。
なので入力が0x0なら1を出力します。

3ジャンプ結果保存

2で判定した結果をD-FFという名前の回路(1bitレジスタ)に保存します。
後にPCを書き換えるかの信号として使います

4ジャンプアドレス保存

4bitレジスタ4つで16bitのアドレスを保存します。

0110 :JEQ_AR	
0001 :a<-0x1
0000 :b<-0x0
0000 :c<-0x0
0000 :d<-0x0

という感じで格納され、この場合アドレスはdcbaの順　すなわち0x1になります。

5ジャンプ制御

カウンタとデマルチプレクサを使用してa,b,c,dにアドレスを格納&ジャンプを制御します。

ステップ0 命令が0110,0111でない限りカウンタをリセットし続ける
ステップ1 aにアドレスを格納
ステップ2 b
ステップ3 c
ステップ4 d
ステップ5 D-FF=1ならJMP

ステップ5にて　これもPCがインクリされるのでアドレスは'ジャンプする場所-1'にしないとちゃんと動作しない

(画像の回路はミスってます　ごめんなさい 修正したものが以下の画像です)

この画像は　ステップ5 D-FF=1ならJMP　の状態です。

6ポインタ制御

構造は簡単です。
I=0001/0000ならポインタにクロック信号を伝えます。
I=0001の時だけデクリメントフラグを1にします。(要はデクリメントモードにする)
ちなみにポインタはカウンターコンポーネントを使いました。

7メモリ制御

メモリ制御も構造は"ポインタ制御"とあまり変わりません
しかし、RAMにはインクリメントデクリメント機能がないのでそれを作る必要があります。

7の少し右上に値をインクリ/デクリする回路があります。
仕組みは簡単で先に両方計算しといてその結果をマルチプレクサで選択するって感じです。

OUT命令でもメモリを使用するのでそこもマルチプレクサを使って制御します。

IO

IOはCCU外に作りました。
参照する度に自動でアドレスをインクリメントしてくれます

テスト

今回は,[,.](入力されたものをひたすら出力するというコード)をこのCPUで実行していきたいと思います。

テストコード(バイナリ)

0100  :,
0110  :[
1001  :0x09
0000  :0x00
0000  :0x00
0000  :0x00
1000  :NOP
0100  :,
0101  :.
0111  :]
0001  :0x01
0000  :0x00
0000  :0x00
0000  :0x00
1000  :NOP
1000  :NOP
1000  :NOP
1000  :NOP
...

Ligisim evolutionではバイナリは打てないので16進数に変換して打つ必要がある

テストコード

4 6 9 0 0 0 8 4 5 7 1 0 0 0 8 8 8 8 8 8 8 8 8 ...

ちゃんとROMの内容がRAMに反映されている!!
成功だ!!

最後に

ということで今回はBrainFuckを直接実行できるCPUを作ってみました。
(このCPUは配布する予定)
じゃ。

参考にしたサイト

https://hirlab.net/nblog/category/programming/art_1604/
https://hatuna-827.github.io/blog/brainfuck/about/
https://ja.wikibooks.org/wiki/Brainfuck