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上で実行させるのを目標にしたいと思います。
