1.概要
論理回路シミュレータのlogisimを使って，Brainfuckのコードをそのまま(?)実行可能なCPUをマイクロプログラム方式で作ってみました．この記事ではその成果，作り方，仕様を簡単に説明しますが，僕はCPUの勉強を始めたところなので，細かい内容については保証できません．
作ったlogisimのファイルとか，命令セットとかを書いた秘伝のエクセルシートとかはここに投げておきます．
2.とりあえず成果
興味本位で見に来たという方がほとんどだと思うので，説明はともかくとりあえず動作している様子はこんな感じです．
デコーダ上ではBrainfuckの命令とマイクロコードを読み取っていい感じにBrainfuckのプログラムを実行しています．
今回はlogisimに搭載されているキーボードやディスプレイを使えるようにしているので，入出力がちゃんとできるようになっています．上のGIFではどっかから引っ張ってきたHello Worldのコードを実行していますが右下のディスプレイにちゃんと「Hello World!」が表示されています．
3.実装方法(マイクロコード編)
このCPUのキモはBrainfuckのコードが～という下りよりも，CPUの命令の制御にマイクロプログラムを用いているという点です．この制御方式はマイクロプログラム方式とよばれていて，1つの命令をより単純な命令群に置き換えるというものです．マイクロプログラム方式の詳しい話はWikipediaをみるか，CPU関係で有名な本である『コンピュータの構成と設計 第二版 上』を読むといいと思います(最新版では省略されているかもしれないです)．
先に少し触れましたが，マイクロプログラム方式ではCPUの命令をより単純な命令群で置き換えるというものです．
まもな高級言語がなくアセンブラ言語でガリガリ書いていた時代では，より高度な命令をCPUに組み込ませるという考え方(CISC)が流行っていたようで，その考えのもとで作られたCPUではマイクロプログラム方式がよく用いられてきたようです．
今ではあまり使われていない方式のようですが，この方式を用いれば複雑な命令を実行できるので，Brainfuckを実行するCPUを作るのはお茶の子さいさいというわけです．
このCPUではBrainfuckの命令(+-,.><[])それぞれを次のようなマイクロプログラムで動かしています．エクセルシートもあげてありますので気になる方はそっちを見てください．
このマイクロプログラムからデコーダが適切な信号を出力します．
4.デコーダ
デコーダは割りと雑な感じになっていますがこんな感じです．雑に説明を入れておきました（あとで僕が見る用なので）
先程見せたマイクロプログラムの命令（マイクロ命令）から，適切な信号を出力するような回路となっているはずです．
マイクロ命令から出力される信号はこんな感じです．
5.コンパイラ
コンパイラと言っても対応する数字を出力するだけのプログラムです．余分なincludeとかありますが無視してください．出力されたファイルはlogisimでROMデータに書き込むことができます．
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <queue> | |
| #include <vector> | |
| #include <algorithm> | |
| #include <map> | |
| #include <string> | |
| #include <cstdio> | |
| #include <cstdlib> | |
| #include <ctime> | |
| #ifndef _USEFUL_MACROS_ | |
| #define _USEFUL_MACROS_ | |
| #define INF 99999999 | |
| #define FOR(i,a,b) for (int i=(a);i<(b);i++) | |
| #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) | |
| #define REP(i,n) for (int i=0;i<(n);i++) | |
| #define RREP(i,n) for (int i=(n)-1;i>=0;i--) | |
| #endif | |
| using namespace std; | |
| int main(int argv,char *argc[]){ | |
| FILE *src; | |
| FILE *output; | |
| char c; | |
| if( argv <= 2 ){ | |
| cout << "Error: no input file." << endl; | |
| cout << "usage: ./bfc code.txt out.txt" << endl; | |
| return 0; | |
| } | |
| src = fopen(argc[1],"r"); | |
| if( src == NULL ){ | |
| cout << "File \"" << argc[1] << "\" not foud." << endl; | |
| return 0; | |
| } | |
| output = fopen(argc[2],"w"); | |
| if( output == NULL ){ | |
| cout << "File \"" << argc[2] << "\" not foud." << endl; | |
| return 0; | |
| } | |
| fprintf(output,"v2.0 raw\n"); | |
| while( (c=fgetc(src)) != EOF ){ | |
| int n = -1; | |
| char codes[9] = "><+-.,[]"; | |
| REP(i,8) | |
| if( codes[i] == c ) | |
| n = i; | |
| if( n != -1 ){ | |
| fprintf(output,"%d ",n); | |
| } | |
| } | |
| fclose(src); | |
| fclose(output); | |
| return 0; | |
| } |
6.感想とか
この間『コンピュータの構成と設計 第二版 上』を読了しまして，その時にないがしろになっていた桁上げ先見加算器とマイクロプログラム方式について一応手を動かして作ってみた感じです．もともと大学のレポートで自由課題として提出する用に作っていたのですが，Brainfuckの方は間に合わなかったのでブログに書いて供養させた感じです．
なるべく早く下巻を読み終えてパイプライン処理のmipsを実装したらFPGAに手を出していきたい所存です……
