Brainf**kについて
先日こちらのブログを拝見しました。
見に行ったときはLLVMについて興味があったのですが、記事中で使われているBrainf**kという言語に興味津々。恥ずかしながらこれまで存在を知りませんでした。Wikipediaによると、この言語で使われる要素は><+-.,[]だけだそうです
Wikipediaにのっていた例によるとHello, World!を表示するコードはこうなります。(実行部分のみ)
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
Wikipediaによると意味は以下の通り
- +でポインタ値を+1
- ーでポインタ値を-1
- >でポインタを+1(一つ進む)
- <でポインタを-1(一つ戻る)
- [で、ポインタ値が0なら対応する]に進む
- ]で、ポインタ値が非0なら対応する[に戻る
- .でポインタ値を出力
- ,で入力値をポインタ先に代入
ちょうど、久しぶりにハードウェア関係で何か遊びたいなとか、VerilogHDLでデザイン書いてみたいな(自分はVHDL派でした)、などと思っていたところなので、Brainf**kをネイティブ実行するCPUを書いてみました。
Brainf**k CPU
たぶんググったら先行事例が沢山出てくると思うので、検索とかせずに、ひたすらコーディング。しばし格闘の後、できました。
module brainfuck( clk, rst_n, pc, pc_r, op, op_en, dp, d_o, w_en, w_sel, d_i, r_en, r_sel, d_en); input clk, rst_n; output [11:0] pc; input [7:0] op; output pc_r; input op_en; output [11:0] dp; output [7:0] d_o; output w_en; output w_sel; // 0: mem, 1: key input [7:0] d_i; output r_en; output r_sel; // 0: mem, 1: key input d_en; reg [11:0] pc; reg [11:0] pc_i, pc_n; reg [11:0] dp; reg [7:0] d_o; wire r_en; reg pc_r, w_en, w_sel, r_en_reg, r_sel; reg mov, mov_dir; // mov: 0, regular, 1: [ or ] reg [11:0] p_cnt; // number of parenthesis skipped reg [4:0] cur, nxt; // state machine reg [7:0] cur_op; parameter IDLE = 5'b00000, FETCH = 5'b00001, DEC = 5'b00010, MEMR = 5'b00100, MEMW = 5'b01000; reg pc_inc, pc_dec; wire mread, mwrite; // state machine always @(posedge clk or negedge rst_n) begin if (rst_n==0) cur <= IDLE; else cur <= nxt; end // state machine next state always @(cur or op_en or mread or d_en) begin case (cur) IDLE: nxt <= FETCH; FETCH: if (op_en == 1) // Next ope code came in nxt <= MEMR; MEMR: if (mread==0 | d_en == 1'b1) nxt <= MEMW; MEMW: nxt <= FETCH; default: nxt <= FETCH; // IDLE endcase end // pc change always @(posedge clk or negedge rst_n) begin if (rst_n==0) pc_i <= 0; else pc_i <= pc_n; end always @(pc_inc or pc_dec or pc_i) begin if (pc_inc==1 & pc_dec==0) pc_n <= pc_i + 1; else if (pc_inc==0 & pc_dec==1) pc_n <= pc_i - 1; else pc_n <= pc_i; end // pc_read always @(pc_inc or pc_dec or pc_n or pc_i) begin pc_r <= pc_inc | pc_dec; if (pc_inc | pc_dec) pc <= pc_n; else pc <= pc_i; end // Decoder for [ & ] always @(posedge clk or negedge rst_n) begin if (rst_n==0) begin mov <= 0; mov_dir<= 0; p_cnt <= 0; end else if (cur==MEMR) if (mov == 1) begin if ((mov_dir==0 & cur_op==8'h91) | (mov_dir==1 & cur_op==8'h93)) p_cnt <= p_cnt+1; else if (((mov_dir==0 & cur_op==8'h93) | (mov_dir==1 & cur_op==8'h91)) & (p_cnt==0)) mov <= 0; else if ((mov_dir==0 & cur_op==8'h93) | (mov_dir==1 & cur_op==8'h91)) p_cnt = p_cnt-1; end else if (d_en == 1'b1 & cur_op==8'h91 & d_i==0) begin mov <= 1; mov_dir <= 0; p_cnt <= 0; end else if (d_en == 1'b1 & cur_op==8'h93 & d_i!=0) begin mov <=1; mov_dir <= 1; p_cnt <= 0; end end // decoder for PC change always @(cur) begin case (cur) IDLE: begin pc_inc <= 1; pc_dec <= 1; end MEMW: begin pc_inc <= (mov==0 | mov_dir==0) ? 1 : 0; pc_dec <= (mov==0 | mov_dir==0) ? 0 : 1; end default: begin pc_inc <= 0; pc_dec <= 0; end endcase end always @(posedge clk or negedge rst_n) begin if (rst_n == 1'b0) cur_op <= 8'h0; else if (cur==FETCH & op_en==1) cur_op <= op; end // dp always @(posedge clk or negedge rst_n) begin if (rst_n == 1'b0) dp <= 0; else if (cur==MEMR & mov==0 & cur_op==8'h60) dp <= dp - 12'h1; else if (cur==MEMR & mov==0 & cur_op==8'h62) dp <= dp + 12'h1; end // r_en always @(posedge clk or negedge rst_n) begin if (rst_n == 1'b0) r_en_reg <= 0; else if (cur==FETCH & nxt==MEMR & mread) r_en_reg <= 1; else if (cur==MEMR & nxt==MEMR) r_en_reg <= 1; else r_en_reg <= 0; end assign r_en = (cur==FETCH & nxt==MEMR & mread) | r_en_reg; assign mread = (mov==0 & (op==8'h43 | op==8'h45 | op==8'h44 | op==8'h91 | op==8'h93)) ? 1 : 0; // data read always @(posedge clk or negedge rst_n) begin if (rst_n == 1'b0) d_o <= 0; else if (mov==1) d_o <= d_o; // no operation. Just for readability else if (cur==MEMR & d_en==1 & cur_op==8'h43) // + d_o <= d_i + 1; else if (cur==MEMR & d_en==1 & cur_op==8'h45) // - d_o <= d_i - 1; else if (cur==MEMR & d_en==1) d_o <= d_i; end // r_sel always @(posedge clk or negedge rst_n) begin if (rst_n == 1'b0) r_sel <= 0; else if (cur==FETCH & op_en==1 & op==8'h46) r_sel <= 1; else if (cur==FETCH & op_en==1) r_sel <= 0; end // write the data always @(posedge clk or negedge rst_n) begin if (rst_n == 1'b0) w_en<=0; else if (nxt == MEMW) w_en <= mwrite; else w_en <= 0; end assign mwrite = (mov==0 & (cur_op==8'h43 | cur_op==8'h45 | cur_op==8'h44)) ? 1 : 0; // w_sel always @(posedge clk or negedge rst_n) begin if (rst_n == 1'b0) w_sel <= 0; else if (cur==FETCH & op_en==1 & op==8'h44) w_sel <= 1; else if (cur==FETCH & op_en==1) w_sel <= 0; end endmodule
シミュレーションによる動作確認
とりあえずシミュレーションで動作確認してみます。
先ほどのHello, World!をVerilogのテストベンチが読めるように、ASCIIコードでファイルに書きます。わかりやすいように改行が入っていますが、上と同じ物です。
@00 91 91 91 93 93 93 00 43 43 43 43 43 43 43 43 91 62 43 43 43 43 91 62 43 43 62 43 43 43 62 43 43 43 62 43 60 60 60 60 45 93 62 43 62 43 62 45 62 62 43 91 60 93 60 45 93 00 62 62 44 62 45 45 45 44 43 43 43 43 43 43 43 44 44 43 43 43 44 62 62 44 60 45 44 60 44 43 43 43 44 45 45 45 45 45 45 44 45 45 45 45 45 45 45 45 44 62 62 43 44 62 43 43 44
シミュレーション実行
わかりにくいですが、動作しました。実行結果をモニターする部分を拡大するとこんな感じです。
ちゃんと"Hello, World!"と表示されています。
終わりに
一通りコーディングした後で検索したところ当然ながらBrainf**k CPUの先行事例は山ほどでてきましたが、自分の楽しみのためにやっているので問題ありません。次は少し時間がかかるかもしれませんが、論理合成して周辺回路と合わせてFPGA上で実行させるのを目標にしたいと思います。