Verilogでbrainfuckのインタプリタを作ってシミュレーションしてみる

verilogの勉強のためにプログラミング言語のbrainfuckのインタプリタ実装に挑戦してみました。verilog上でbrainfuckの”Hello World!”を出力するプログラムを実行できたらゴールとします。

環境

  • mac os
  • コンパイラ iVerilog

環境構築方法はこちらを参考下さい

Mac上でverilog HDLをシミュレーションして波形表示させる環境を構築する最新の方法をメモします。 手順 icarus veri...

Brainfuckとは?

  • 難読プログラミング言語の一種
  • わずか8つの命令だけで記述できる言語
  • Brainfuckでは前提として値0で初期化されたとても長い配列が与えられる
アドレス 0 1 2 3 4 5 6 7
データ 0 0 0 0 0 0 0 0
  • Brainfuckの8つの命令
コマンド 意味
+ アドレスが指す値をインクリメント
アドレスが指す値をデクリメント
> アドレスをインクリメント
< アドレスをデクリメント
. アドレスが指す値を出力
, 1byte標準入力から読み込みアドレスが指す値にセット(今回は実装しない)
[ アドレスが指す値が0なら、対応する ] の直後にジャンプする
] アドレスが指す値が0でないなら、対応する [ の直後にジャンプする。
  • Hello World
    brainfuckでのHello World!は以下のように書けます。

    これをhello.bfとして保存して下さい。
    これがHello World!を出力する仕組みはこちらの記事で別に解説しています。
Brainf*ck(Brainfuck)という言語をご存知でしょうか? わずか8つの記号しか使えない変態言語なのですが、チューリング完...

Brainfuckコードを16進数に変換

まずbrainfuckコードをverilogに読みませる方法を考えます。Verilogの$readmemh()というタスクを使えばできそうです。しかし$readmemh()は16進数の値しか読み取れません。そこで、まずbashでbrainfuckのプログラムを16進数に変換するスクリプトを作成しました。

gsedを使っています。brewでインストールできます。

このスクリプトは単純にアスキーコードを16進数に変換しているだけです。これをbftohex.shとして保存しました。そして変換したファイルをhelloworld.stxとして保存します。

helloworld.stxは一行ごとにアスキーコードの16進数が書き込まれています。

インタプリタ実装

dataとdataAdressはbrainfuckのデータ構造を表しています。

dataAdress 0 1 2 3 4 5 6 1023
data 0 0 0 0 0 0 0 0

commandStrageにはhelloworld.stxが格納されます。

インタプリタの実装部分ではまずcommandStrageからデータを読み込んでいきます。すなわちhelloworld.stxを一行ずつ読み込みcommandに格納しています。

そしてcommandが+-<>.[]のどれであるかを評価し、dataとdataAdressで表されるbrainfuckのデータ構造を更新して行きます。
そして、.が呼ばれた場合は現在のアドレスが指す値をresultに格納しています。

テストベンチ

シミュレーションのためのテストベンチコードです。
helloworld.stxの読み込みや値の初期化を記述しています。

commandとresultの値をモニターするように設定します。resultにはbrainfuckを実行した結果が格納されるので、%cを指定し、文字列として表示するようにします。

シミュレーション

665~785クロックにかけてHello World!のアスキーコードが出力されていることが確認できました。
また、bfInterpreter.vcdというファイルが出力されるのでgtkwaveなどで波形を確認しても同様のことが確かめられます。

まとめ

brainfuckのインタプリタは言語仕様がとてもシンプルなので難易度は低いと思います。
いつか実機でも動かしてみたい所です。