Moiz's journal

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

Brainf**kを直接実行するCPUを作ってみる

Brainf**kについて

先日こちらのブログを拝見しました。

itchyny.hatenablog.com

見に行ったときはLLVMについて興味があったのですが、記事中で使われているBrainf**kという言語に興味津々。恥ずかしながらこれまで存在を知りませんでした。Wikipediaによると、この言語で使われる要素は><+-.,[]だけだそうです

Brainfuck - 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

シミュレーション実行
f:id:uzusayuu:20170306152358p:plain
わかりにくいですが、動作しました。実行結果をモニターする部分を拡大するとこんな感じです。
f:id:uzusayuu:20170306152527p:plain
ちゃんと"Hello, World!"と表示されています。

終わりに

一通りコーディングした後で検索したところ当然ながらBrainf**k CPUの先行事例は山ほどでてきましたが、自分の楽しみのためにやっているので問題ありません。次は少し時間がかかるかもしれませんが、論理合成して周辺回路と合わせてFPGA上で実行させるのを目標にしたいと思います。