Moiz's journal

プログラミングやFPGAなどの技術系の趣味に関するブログです

FPGAで動作するBrainf**k CPUを作ってみた

はじめに

前回のエントリーに書いたとおりBrainf**k言語を直接実行するCPUFPGA(Terasic DE0)で動作したのでまとめてみます。

f:id:uzusayuu:20170501084716p:plain

VerilogのコードとQuartusのプロジェクトファイルはこちらに公開してあります。

github.com

以下この稿では、このCPUをBF CPUと呼びます。

Brainf**kについて

Brainf**kは本来**の位置にはucが入るのですが、英語圏で非常に下品な単語なためこのように記述されることが多々あります。言語仕様としては'+-><.,[]'だけの非常にシンプルなものですが、チューリング完全であることが示されているということです。詳しくはWikipediaのページなどをご覧ください。

Brainfuck - Wikipedia

Brainfuck - Esolang 

 

スペック、必要な環境など

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のブロック図

全体のブロック図はこんな感じです。

f:id:uzusayuu:20170501064512p:plain

コア部分のブロック図はこう

f:id:uzusayuu:20170501071531p:plain

目を疑うほどシンプルですが、一部制御などを省いて書いている以外は、だいたいこのとおりのHDLになっています。

ステートマシーンはこう

f:id:uzusayuu:20170501072438p:plain

バカにしてるのかと思うほど単純ですが、先々パイプライン化もしたいなと考えて、あえて単純な形に残しています。この他にステートと内部信号から制御信号を作る制御回路があります。

処理の流れとしては、コマンド毎にこうなります

  • '+' 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のコードを用意します。普通の人間にかけるものではないので(書ける人もいるようですが...)、変換器などを使うのが良いと思います。文字を表示するだけならこちらをどうぞ。

Brainfuck text generator

こちらのサイトは文字を入力すると、その文字を出力するBFコードを作ってくれます。

たとえば、'BF rocks!'ならこう。

f:id:uzusayuu:20170501075405p:plain

このコードを適当なテキストファイルにコピーし、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を押すとソフトリセットがかかり、こんなふうに実行されます。

f:id:uzusayuu:20170430161743j:plain

まとめ

単純な回路なのでCPUのロジック自体は半日程度でできたのですが、実際のROM/RAMをとりつけて、LCDに表示できるようになるまで随分かかってしまいました。この後改行をつけたり、入力を改善したりしようかなと思っています。

*1:フォーマットについてはWikipediaなどでIntel HEXを参照ください。