はじめに
前回のエントリーに書いたとおり、Brainf**k言語を直接実行するCPUがFPGA(Terasic DE0)で動作したのでまとめてみます。
VerilogのコードとQuartusのプロジェクトファイルはこちらに公開してあります。
以下この稿では、このCPUをBF CPUと呼びます。
Brainf**kについて
Brainf**kは本来**の位置にはucが入るのですが、英語圏で非常に下品な単語なためこのように記述されることが多々あります。言語仕様としては'+-><.,[]'だけの非常にシンプルなものですが、チューリング完全であることが示されているということです。詳しくはWikipediaのページなどをご覧ください。
スペック、必要な環境など
BF CPUのスペック
- クロック速度: 50 MHz (ボードの制約による)
- ROM (プログラム用): 4K byte
- RAM (データ用): 4K byte
- 入力: 8bit (switchからの入力)
- 出力:8bit (LCDへの表示)
環境
- ターゲットデバイス: Terasic DE0 (LCD必須)
- 開発環境: Quartus II 13.1 (DE0用にセットアップされていること)
- 使用言語: Verilog HDL (テストベンチにはSystem Verilogも使用)
BF CPUのブロック図
全体のブロック図はこんな感じです。
コア部分のブロック図はこう
目を疑うほどシンプルですが、一部制御などを省いて書いている以外は、だいたいこのとおりのHDLになっています。
ステートマシーンはこう
バカにしてるのかと思うほど単純ですが、先々パイプライン化もしたいなと考えて、あえて単純な形に残しています。この他にステートと内部信号から制御信号を作る制御回路があります。
処理の流れとしては、コマンド毎にこうなります
- '+' or '-': PC++, data_out=data_in+1 (or data_in-1)
- '>' or '<': PC++, dp_adr ++ (or --)
- ',' or '.' : PC++, data_out=data_in。','の場合data_inはメモリーからで、data_outは出力へ。'.'の場合、data_inは入力からで、data_outはメモリーへ
- '[': PC++, data_in=0なら探索モード(正方向)に移行
- ']': dp_adr変更なし、data_in>0なら、探索モード(負方向)に移行。それ以外はPC++。
- 探索モード(正方向): PC++、コマンドが'['なら、ループネストカウンターを+1。']'なら-1。カウンターが0になったら探索モード終了
- 探索モード(負方向): PC--、コマンドが']'なら、ループネストカウンターを+1。'['なら-1。カウンターが0になったら探索モード終了
探索モードは'['と']'によるループのために作られたものです。'['又は']'が来ると条件次第でこのモードに入り、対応する'['や']'を探します。負方向に関してはスタックを作れば高速化できるのはわかっていたのですが、まずは小さいサイズで始めるためにこのようにしました。
実行してみる
まずBrainf**kのコードを用意します。普通の人間にかけるものではないので(書ける人もいるようですが...)、変換器などを使うのが良いと思います。文字を表示するだけならこちらをどうぞ。
こちらのサイトは文字を入力すると、その文字を出力するBFコードを作ってくれます。
たとえば、'BF rocks!'ならこう。
このコードを適当なテキストファイルにコピーし、Quartusのコンパイラーが読めるように、tools内にあるtxt2hex.cを使ってrom_data.hexという名前のHEXテキスト形式ファイルに変換します。*1このファイルはプロジェクトファイル(bf.qpf)と同じ階層においておきます。 Quartus IIはこのファイルを読んで、ROM化します。ファイルの中身はこんな感じです。
:100000002b2b2b2b5b2b2b2b2b3e2d2d2d3c5d3ea1
:100010002d2e2b2b2b2b2e5b2d2d3e2b3c5d3e2d89
:100020002d2d2e3e2d5b2d2d2d3e2b3c5d3e2d2d61
:100030002d2e2d2d5b2d2d2d3e2b3c5d3e2d2e2d61
:100040002d2d2d2d2d2d2d2d2d2d2d2e2b2b2b2be7
:100050002b2b2b2b2e2b2b2b2b2b2b2b2b2e2b5bba
:100060002d2d3e2b2b2b2b2b3c5d3e2d2e5b5d0a2d
:00000001FF
これで準備ができました。
次にQuartus II 13.1を起動し、プロジェクト(bf.qpf)を開き、Processing->Start compilationでコンパイル、Tools->Programmerでプログラマーを開き、DE0に転送します。転送が終了したら、Button-2を押すとソフトリセットがかかり、こんなふうに実行されます。
まとめ
単純な回路なのでCPUのロジック自体は半日程度でできたのですが、実際のROM/RAMをとりつけて、LCDに表示できるようになるまで随分かかってしまいました。この後改行をつけたり、入力を改善したりしようかなと思っています。
*1:フォーマットについてはWikipediaなどでIntel HEXを参照ください。