Verilog で競技プログラミングの問題を解いてみる

# 対象環境

この記事のコードは、[Icarus Verilog](https://steveicarus.github.io/iverilog/) で動作確認を行った。

# 基本操作

## 標準出力

`$display` システムタスクを用いると、数値や文字を標準出力に出力し、さらに改行を出力できる。
このシステムタスクは、C言語の `printf` のように、最初の引数に書式を表す文字列、2番目以降の引数に出力するデータをとる。
書式 `%0d` を用いると、数値を十進数で出力できる。(`0` を入れない `%d` では、数値の前に余計な空白が入ってしまった)
書式 `%c` を用いると、数値を文字として出力できる。

`$write` システムタスクを用いると、`$display` と同様の出力を、改行の出力なしで行うことができる。

```verilog
$write("hello, world...");       // 指定したデータを出力する
$display("the answer: %0d", 42); // 指定したデータと改行を出力する
```

## 標準入力

`$fscanf` システム関数を用いると、ファイルからC言語の `scanf` のように書式を用いてデータを読み込める。
`$fgetc` システム関数を用いると、ファイルから1文字読み込める。
ファイルとして `'h8000_0000` を指定することで、標準入力から読み込めるようである。

```verilog
num = $fscanf('h8000_0000, "%d", a); // 変数 a に数値を読み込む
c = $fgetc('h8000_0000);             // 変数 c に1文字読み込む
```

:::note info
`$fscanf` の戻り値を変数に代入せず無視しようとすると、「システム関数をタスクとして使用しようとしている」として怒られる原因になる。

```verilog
$fscanf('h8000_0000, "%d", a); // 怒られる
```
:::

## 実行の終了

`$finish` システムタスクを用いると、プログラムの実行を終了できる。
このとき、引数として `(0)` を指定しないと、余計な出力が標準出力にされてしまい、競技プログラミングでは不正解の原因となる。

```verilog
$finish(0); // プログラムの実行を終了する
```

# プログラム例

前章で紹介した基本操作を用いて、
[PracticeA - Welcome to AtCoder](https://atcoder.jp/contests/language-test-202001/tasks/practice_1)
を解くプログラムを書いてみた。

## 簡単な書き方

普通のプログラムのようにシンプルに書く場合、たとえば以下のように書ける。

```verilog
module welcome;
	integer stdin = 'h8000_0000;

	integer a, b, c;
	integer ch;

	integer placeholder;

	initial begin
		placeholder = $fscanf(stdin, "%d", a);
		placeholder = $fscanf(stdin, "%d%d", b, c);
		placeholder = $fgetc(stdin); // 数値の後の改行を捨てる
		$write("%0d ", a + b + c);
	end

	always #1 begin
		ch = $fgetc(stdin);
		$write("%c", ch);
		if (ch == 'ha) begin
			$finish(0);
		end
	end

endmodule
```

## ハードウェアを意識した書き方

ハードウェアで実装することを想定して書く場合、たとえば以下のように書ける。

```verilog
// 入出力用モジュール
module welcome_driver;
	integer stdin = 'h8000_0000;

	reg reset, clock;

	reg [7:0] input_char;
	wire input_valid;
	wire input_read;
	wire [7:0] output_char;
	wire output_valid;
	wire output_read;
	wire done;

	assign input_valid = 1'b1;
	assign output_read = output_valid;

	initial begin
		// 動作確認用
`ifdef OUTPUT_VCD
		$dumpfile("welcome.vcd");
		$dumpvars(0, w);
`endif
		// 状態を初期化する
		reset <= 1'b1;
		clock <= 1'b0;
		input_char <= $fgetc(stdin);
		#15;
		reset <= 1'b0;
	end

	// クロックを発生させる
	always #10 begin
		clock <= ~clock;
	end

	// 問題を解くモジュールを入出力用モジュールに接続する
	welcome w(
		clock, reset,
		input_char, input_valid, input_read,
		output_char, output_valid, output_read,
		done
	);

	// 入出力と終了を行う
	always @(posedge clock) begin
		if (input_read) begin
			input_char <= $fgetc(stdin);
		end
		if (output_valid) begin
			$write("%c", output_char);
		end
		if (done) begin
			$finish(0);
		end
	end

endmodule

// 問題を解くモジュール
module welcome(
	clock, reset,
	input_char, input_valid, input_read,
	output_char, output_valid, output_read,
	done
);
	input clock;                  // クロック
	input reset;                  // リセット (HIGHでリセットをかける)
	input [7:0] input_char;       // 入力する文字
	input input_valid;            // 次のクロックの時点で、入力する文字が有効
	output input_read;            // 次のクロックで、入力する文字を受け取る
	output reg [7:0] output_char; // 出力する文字
	output reg output_valid;      // 次のクロックの時点で、出力する文字が有効
	input output_read;            // 次のクロックで、出力する文字を受け取る
	output reg done;              // 処理が完了した

	reg reading_input;              // 入力を読み取るか

	reg [1:0] num_integers_to_read; // あと何個の数値を足すか
	reg [15:0] sum;                 // 数値の和
	reg [15:0] number_read;         // 現在読み込んでいる数値

	reg [6:0] num_chars_read;       // 文字列の入力で読み込んだ文字数
	reg [7:0] chars_read[0:127];    // 文字列の入力で読み込んだ文字の配列

	reg [4:0] output_phase;         // 何を出力しているか
	reg [3:0] number_output_phase;  // 数値のどこを出力するか
	reg number_output_flag;         // 数値の出力を開始したか
	reg [6:0] char_to_output;       // 文字列の中の次に出力する文字の位置

	// next_sum = sum + number_read
	wire [3:0] sum_raw_0 = sum[3:0] + number_read[3:0];
	wire sum_carry_0 = sum_raw_0 > 9;
	wire [3:0] sum_raw_1 = sum[7:4] + number_read[7:4] + sum_carry_0;
	wire sum_carry_1 = sum_raw_1 > 9;
	wire [3:0] sum_raw_2 = sum[11:8] + number_read[11:8] + sum_carry_1;
	wire sum_carry_2 = sum_raw_2 > 9;
	wire [15:0] next_sum = {
		sum[15:12] + number_read[15:12],
		sum_raw_2 - (sum_carry_2 ? 4'd10 : 4'd0),
		sum_raw_1 - (sum_carry_1 ? 4'd10 : 4'd0),
		sum_raw_0 - (sum_carry_0 ? 4'd10 : 4'd0)
	};

	wire [3:0] char_digit_to_output =
		number_output_phase[3] ? sum[15:12] :
		number_output_phase[2] ? sum[11:8] :
		number_output_phase[1] ? sum[7:4] :
		number_output_phase[0] ? sum[3:0] : 3'd0;

	assign input_read = ~reset & reading_input & input_valid;

	always @(reset) begin
		output_char <= 8'd0;
		output_valid <= 1'b0;
		done <= 1'b0;
		reading_input <= 1'b1;
		num_integers_to_read <= 2'd3;
		sum <= 16'd0;
		number_read <= 16'd0;
		number_output_phase <= 4'b1000;
		number_output_flag <= 1'b0;
		num_chars_read <= 7'd0;
		output_phase <= 4'd1;
		char_to_output <= 7'd0;
	end

	always @(posedge clock) begin
		if (~reset) begin
			if (reading_input) begin
				// 入力読み取りフェーズ
				if (num_integers_to_read > 0) begin
					// 数値を読み取る
					if (input_valid) begin
						if (8'h30 <= input_char && input_char <= 8'h39) begin
							// 読み取った桁を下位に挿入する
							number_read <= {number_read[11:0], input_char[3:0]};
						end else if (input_char == 8'h20 || input_char == 8'h0a) begin
							// 読み取った数値を加算し、カウントする
							num_integers_to_read <= num_integers_to_read - 2'd1;
							sum <= next_sum;
							number_read <= 16'd0;
						end
					end
				end else begin
					// 文字列を読み取る
					if (input_valid) begin
						if (input_char == 8'h0a) begin
							// 改行文字があったので、読み取りを終了する
							reading_input <= 1'b0;
						end else begin
							// 読み取った文字を格納する
							chars_read[num_chars_read] <= input_char;
							num_chars_read <= num_chars_read + 7'd1;
						end
					end
				end
			end else begin
				// 出力フェーズ
				if (output_phase[0]) begin
					// 数値の出力
					if (!number_output_phase[0] && char_digit_to_output == 4'd0 && !number_output_flag) begin
						// リーディングゼロを出力しない
						number_output_phase <= {1'b0, number_output_phase[3:1]};
					end else begin
						if (!output_valid) begin
							// 出力できる状態なら、数値を出力する
							output_char <= {4'h3, char_digit_to_output};
							output_valid <= 1'b1;
							number_output_phase <= {1'b0, number_output_phase[3:1]};
							number_output_flag <= 1'b1;
							// 最後の桁を出力したら、次の状態に進む
							if (number_output_phase[0]) begin
								output_phase <= 4'b10;
							end
						end
					end
				end else if (output_phase[1]) begin
					// 数値と文字列の間の空白の出力
					if (!output_valid) begin
						output_char <= 8'h20;
						output_valid <= 1'b1;
						output_phase <= 4'b100;
					end
				end else if (output_phase[2]) begin
					// 文字列の出力
					if (!output_valid) begin
						output_char <= chars_read[char_to_output];
						output_valid <= 1'b1;
						if (char_to_output + 6'd1 < num_chars_read) begin
							// まだ出力するべき文字がある
							char_to_output <= char_to_output + 6'd1;
						end else begin
							// 文字列の最後まで出力した
							output_phase <= 4'b1000;
						end
					end
				end else if (output_phase[3]) begin
					// 文字列の後の改行の出力
					if (!output_valid) begin
						output_char <= 8'h0a;
						output_valid <= 1'b1;
						output_phase <= 4'd0;
					end
				end else begin
					// 出力を完了したので、出力が読まれるのを待つ
					if (!output_valid) begin
						done <= 1'b1;
					end
				end
			end
			// 出力した文字を読まれたら、出力中フラグを折る
			if (output_read) begin
				output_valid <= 1'b0;
			end
		end
	end

endmodule
```

# まとめ

Verilog で競技プログラミングの問題が解けるよう、標準入出力のしかたとプログラムの終了のしかたを確認した。
また、実際に簡単な問題を解くコードを書いてみた。

# 参考資料

* [::りろ:: [Verilog HDL] システムタスク、システム関数](http://rilo.moo.jp/vlog/verilog03_1.html)
* [Verilog fgets from stdin but non-blocking - Stack Overflow](https://stackoverflow.com/questions/24217184/verilog-fgets-from-stdin-but-non-blocking)
* [Perplexity AI: Verilog の $display で余計な空白を入れずに数値を出力するには？](https://www.perplexity.ai/search/verilog-no-display-teyu-ji-nak-DN3aIXrPQcy7cWRvk7MAJQ)
* [自宅でVerilogシミュレーション](http://www.arch.cs.kumamoto-u.ac.jp/~kuga/cad/exp/sys/common/verilog_at_home.html)
* [Verilog/SystemVerilogの条件コンパイル - k0b0's record.](https://k0b0.hatenablog.com/entry/2018/02/01/141140)

# 参考にしていない資料

* [FPGAで競技プログラミングの問題を解く #VerilogHDL - Qiita](https://qiita.com/kusano_k/items/29b1cc40ff55c7760afb)