Veryl + Verilator で競技プログラミングの問題を解いてみた

先日は、Verilog で競技プログラミングの問題を解いてみた。

[Verilog で競技プログラミングの問題を解いてみる #AtCoder - Qiita](https://qiita.com/mikecat_mixc/items/b8aadfc3053c49feaf18)

今回は、[Veryl](https://github.com/veryl-lang/veryl) で競技プログラミングの問題を解いてみた。

# 環境構築

## ツールのインストール

[インストール - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/03_getting_started/01_installation.html)

今回は、AWS EC2 上の Ubuntu 24.04 (AMI ID: `ami-05d38da78ce859165`) 上で環境構築を行った。

とりあえずアップデートする。

```bash
sudo apt-get update
sudo apt-get upgrade -y
```

Veryl をインストールするためのツールをインストールするためのツールをインストールする。

```bash
sudo apt-get install -y cargo
```

Veryl をインストールするためのツールをインストールする。
これには10分くらいかかった。

```bash
cargo install verylup
```

最後に

> warning: be sure to add \`/home/ubuntu/.cargo/bin\` to your PATH to be able to run the installed binaries

と出たので、これを行う。

```bash
echo "export PATH=\$PATH:/home/ubuntu/.cargo/bin" >> .bashrc
source .bashrc
```

Veryl をインストールする。

```bash
verylup setup
```

また、[コードを実行するためのツール](https://www.veripool.org/verilator/)と、その実行のために使うツールもインストールしておく。

```bash
sudo apt-get install -y verilator make g++
```

## hello, world

[Hello, World! - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/03_getting_started/02_hello_world.html)
[Example Create-Binary Execution — Verilator Devel 5.031 documentation](https://verilator.org/guide/latest/example_binary.html#example-create-binary-execution)

適当な場所 (たとえばホームディレクトリ) に `hello` ディレクトリを作成し、その中に以下のファイルを置く。

```toml:Veryl.toml
[project]
name = "hello"
version = "0.1.0"
```

```text:hello.veryl
module hello {
	initial {
		$display("hello, world");
	}
}
```

:::note info
Veryl のドキュメントでは `src` ディレクトリ内に `hello.veryl` を置いているが、このディレクトリは不要である。
:::

この `hello` ディレクトリを作業ディレクトリにした状態で、以下のコマンドを実行することで、ビルドを行う。

```bash
veryl build
verilator --binary -f hello.f
```

:::note info
Verilator のドキュメントにある `-Wall` オプションは、**つけてはいけない。**
このオプションをつけると、以下のエラーが出て失敗した。

```text
%Warning-DECLFILENAME: /home/ubuntu/hello/hello.sv:1:8: Filename 'hello' does not match MODULE name: 'hello_hello'
    1 | module hello_hello;
      |        ^~~~~~~~~~~
                       ... For warning description see https://verilator.org/warn/DECLFILENAME?v=5.020
                       ... Use "/* verilator lint_off DECLFILENAME */" and lint_on around source to disable this message.
%Error: Exiting due to 1 warning(s)
```

このオプションは、Veryl の仕様との相性が悪いようである。

また、Veryl のドキュメントでは `--binary` オプションのかわりに `--cc` オプションをつけろと主張しているが、このオプションをつけても実行可能ファイルは得られないようだった。
:::

ビルド後、以下のコマンドを実行することで、ビルドしたプログラムを実行する。

```bash
./obj_dir/Vhello
```

すると、以下の出力が得られる。

```text:実行結果
hello, world
```

:::note warn
終了する処理を書いていないため、このプログラムは自動では終了しない。
:::

## 自動で終了する hello, world

前章のプログラムは、終了する処理を書いていないため自動では終了しない。
そこで、終了する処理を追加する。

<details><summary>失敗した方法</summary>

まずは Verilog と同じ `$finish(0);` を試してみた。

```text:hello.veryl
module hello {
	initial {
		$display("hello, world");
		$finish(0);
	}
}
```

すると、終了はしたものの、**標準出力に余計な出力がされてしまった。**
これは競技プログラミングにおいては致命的になるだろう。

```text:出力結果
hello, world
- /home/ubuntu/hello/hello.sv:4: Verilog $finish
```

引数を `0` のかわりに `-1`、`1`、`2` にしても、出力は変わらなかった。
引数をなくして `$finish;` にすると、エラーになった。

```text:エラー
[INFO ]   Processing file (/home/ubuntu/hello/hello.veryl)
Error: ParserError::SyntaxError

  × Unexpected token: ';'
   ┌─[/home/ubuntu/hello/hello.veryl:4:10]
 3 │         $display("hello, world");
 4 │         $finish;
   ·                ┬
   ·                └── Error location
 5 │     }
   └────
  help:
```

:::note info
エラーメッセージを Tera Term からコピペすると罫線がアルファベットに化けてしまったため、[半角罫線](https://var.blog.jp/archives/74885245.html)からコピペして手動で修正した。
:::

`$finish(0);` のかわりに `$stop(0);` を使うと、余計な出力が増え、さらに終了コードも `0` ではなく `134` になってしまった。

```text:$stop(0); を使った場合の出力結果
hello, world
%Error: /home/ubuntu/hello/hello.sv:4: Verilog $stop
Aborting...
```

Verilator のオプションを調べたものの、この出力を回避する方法は発見できなかった。

Verilator の拡張として、C++ のコードを埋め込める `$c` というものがある。
[Language Extensions — Verilator Devel 5.031 documentation](https://verilator.org/guide/latest/extensions.html)
そこで、これを用いて `exit(0)` を呼び出すことを考えた。

`$c` をそのまま書くと、エラーになった。

```text:エラーになったコード
module hello {
	initial {
		$display("hello, world");
		$c("exit(0);");
	}
}
```

```text:エラーメッセージ
Error:   × veryl check failed

Error: undefined_identifier (https://doc.veryl-lang.org/book/07_appendix/02_semantic_error.html#undefined_identifier)

  × $c is undefined
   ┌─[/home/ubuntu/hello/hello.veryl:4:3]
 3 │         $display("hello, world");
 4 │         $c("exit(0);");
   ·         ─┬
   ·          └── Error location
 5 │     }
   └────
  help:
```

[`$sv::`](https://doc.veryl-lang.org/book/ja/05_language_reference/10_systemverilog_interoperation.html) をつけても、エラーになった。

```text:エラーになったコード
module hello {
	initial {
		$display("hello, world");
		$sv::$c("exit(0);");
	}
}
```

```text:エラーメッセージ
[INFO ]   Processing file (/home/ubuntu/hello/hello.veryl)
Error: ParserError::SyntaxError

  × Unexpected token: '::'
   ┌─[/home/ubuntu/hello/hello.veryl:4:6]
 3 │         $display("hello, world");
 4 │         $sv::$c("exit(0);");
   ·            ─┬
   ·             └── Error location
 5 │     }
   └────
  help:
```

さらに `$c` の前に `r#` をつけてみても、エラーになった。

```text:エラーになったコード
module hello {
	initial {
		$display("hello, world");
		$sv::r#$c("exit(0);");
	}
}
```

```text:エラーメッセージ
[INFO ]   Processing file (/home/ubuntu/hello/hello.veryl)
Error: ParserError::SyntaxError

  × Unexpected token: '#'
   ┌─[/home/ubuntu/hello/hello.veryl:4:9]
 3 │         $display("hello, world");
 4 │         $sv::r#$c("exit(0);");
   ·               ┬
   ·               └── Error location
 5 │     }
   └────
  help:
```

[`embed`](https://doc.veryl-lang.org/book/ja/05_language_reference/12_foreign_language_integration.html) による埋め込みを試みたが、これもインラインではエラーになった。

```text:エラーになったコード
module hello {
	initial {
		$display("hello, world");
		embed (inline) sv{{{
			$c("exit(0);");
		}}}
	}
}
```

```text:エラーメッセージ
[INFO ]   Processing file (/home/ubuntu/hello/hello.veryl)
Error: ParserError::SyntaxError

  × Unexpected token: ')'
   ┌─[/home/ubuntu/hello/hello.veryl:3:26]
 2 │     initial {
 3 │         $display("hello, world");
   ·                                ┬
   ·                                └── Error location
 4 │         embed (inline) sv{{{
   └────
  help:
```

SystemVerilog のモジュール内に `$c` を配置し、信号で制御することを試みたが、`initial` 内で代入することはできないと怒られてしまった。

```text:エラーになったコード
module hello {
	let want_exit: logic = 0;

	inst exiter_i: $sv::exiter (want_exit);

	initial {
		$display("hello, world");
		want_exit = 1;
	}
}

embed (inline) sv{{{
	module exiter(want_exit);
		input want_exit;
		always @(want_exit) begin
			if (want_exit) begin
				$c("exit(0);");
			end
		end
	endmodule
}}}
```

```text:エラーメッセージ
[INFO ]   Processing file (/home/ubuntu/hello/hello.veryl)
Error:   × veryl check failed

Error: invalid_statement (https://doc.veryl-lang.org/book/07_appendix/02_semantic_error.html#invalid_statement)

  × assignment statement can't be placed at here
   ┌─[/home/ubuntu/hello/hello.veryl:8:13]
 7 │         $display("hello, world");
 8 │         want_exit = 1;
   ·                   ┬
   ·                   └── Error location
 9 │     }
   └────
  help: remove assignment statement
```

`assign` をつけても、ダメだった。

```text:エラーになったコード
module hello {
	let want_exit: logic = 0;

	inst exiter_i: $sv::exiter (want_exit);

	initial {
		$display("hello, world");
		assign want_exit = 1;
	}
}

embed (inline) sv{{{
	module exiter(want_exit);
		input want_exit;
		always @(want_exit) begin
			if (want_exit) begin
				$c("exit(0);");
			end
		end
	endmodule
}}}
```

```text:エラーメッセージ
[INFO ]   Processing file (/home/ubuntu/hello/hello.veryl)
Error: ParserError::SyntaxError

  × Unexpected token: 'assign'
   ┌─[/home/ubuntu/hello/hello.veryl:8:3]
 7 │         $display("hello, world");
 8 │         assign want_exit = 1;
   ·         ───┬──
   ·            └── Error location
 9 │     }
   └────
  help:
```

---

</details>

SystemVerilog の[戻り値の無い関数 (task)](http://www.cs.tsukuba.ac.jp/~kanazawa/verilog/func.html) として `$c("exit(0);");` を呼び出す関数を定義し、それを用いることで、余計な出力をせずに終了コード `0` でプログラムの実行を終了することができた。
`$c` は、C++ のコードを埋め込んで実行する [Verilator の拡張](https://verilator.org/guide/latest/extensions.html) である。

```text:hello.veryl
module hello {
	initial {
		$display("hello, world");
		$sv::exit();
	}
}

embed (inline) sv{{{
	task exit;
		$c("exit(0);");
	endtask
}}}
```

```text:出力結果
hello, world
```

# 問題を解いてみる

今回は、[AtCoder Beginners Selection](https://atcoder.jp/contests/abs) に含まれる問題

[ABC086A - Product](https://atcoder.jp/contests/abs/tasks/abc086_a)

を解いてみることにした。
この問題は、空白区切りで2個の正の整数が与えられ、その積が偶数か奇数かを判定する問題である。
与えられる整数の1の位だけを見て、それらが全て奇数なら奇数、1個でも偶数があれば偶数と判定すればよい。

これは、たとえば以下のように実装できる。

```toml:Veryl.toml
[project]
name = "abs_abc086_a"
version = "0.1.0"
```

```text:abs_abc086_a.veryl
module main {
	var clk: clock_posedge;
	var rst: reset_async_high;
	var in_char: logic<8>;
	var in_valid: logic;
	var in_read: logic;
	var out_char: logic<8>;
	var out_valid: logic;
	var out_write: logic;
	var done: logic;

	inst con: $sv::controller(
		clk, rst,
		in_char, in_valid, in_read,
		out_char, out_valid, out_write,
		done,
	);
	inst sol: solver(
		clk, rst,
		in_char, in_valid, in_read,
		out_char, out_valid, out_write,
		done,
	);
}

embed (inline) sv{{{
	module controller(
		clk, rst,
		in_char, in_valid, in_read,
		out_char, out_valid, out_write,
		done
	);
		output reg clk;
		output reg rst;
		output [7:0] in_char;
		output in_valid;
		input in_read;
		input [7:0] out_char;
		input out_valid;
		output out_write;
		input done;

		reg [8:0] in_char_raw;
		assign in_char = in_char_raw[7:0];
		assign in_valid = ~in_char_raw[8];

		assign out_write = out_valid;

		initial begin
			clk = 0;
			rst = 1;
			in_char_raw = $fgetc('h80000000);
			#11
			rst = 0;
		end

		always #10 begin
			clk <= ~clk;
		end

		always @(posedge clk) begin
			if (~rst) begin
				if (in_read) begin
					in_char_raw <= $fgetc('h80000000);
				end
				if (out_valid) begin
					$write("%c", out_char);
				end
				if (done) begin
	`ifdef VERILATOR
					$c("exit(0);");
	`else
					$finish(0);
	`endif
				end
			end
		end
	endmodule
}}}

module solver (
	clk: input clock_posedge,
	rst: input reset_async_high,
	in_char: input logic<8>,   // 入力する文字
	in_valid: input logic,     // 入力する文字が有効か
	in_read: output logic,     // このモジュールが、入力する文字を受け取ったか
	out_char: output logic<8>, // 出力する文字
	out_valid: output logic,   // 出力する文字が有効か
	out_write: input logic,    // 外部のモジュールが、出力する文字を出力したか
	done: output logic,        // 処理が完了したか
) {
	let even_str: logic<8>[8] = '{8'h45, 8'h76, 8'h65, 8'h6e, 8'h0a, 8'h00, 8'h00, 8'h00};
	let odd_str: logic<8>[8] = '{8'h4f, 8'h64, 8'h64, 8'h0a, 8'h00, 8'h00, 8'h00, 8'h00};

	var is_input_phase: logic;
	var is_odd: logic;
	var prev_char: logic<8>;
	var output_pos: logic<3>;

	var next_char_to_output: logic<8>;

	always_comb {
		// 出力位置に応じて、今の文字と次の文字を取得する
		if is_odd {
			out_char = odd_str[output_pos];
			next_char_to_output = odd_str[output_pos + 3'd1];
		} else {
			out_char = even_str[output_pos];
			next_char_to_output = even_str[output_pos + 3'd1];
		}
		// 今回は、入力モードかつ入力があればすぐに読み込む
		in_read = is_input_phase & in_valid;
	}

	always_ff {
		if_reset {
			// 初期化
			is_input_phase = 1'b1;
			is_odd = 1'b1;
			prev_char = 8'd1;
			output_pos = 3'd0;
			out_valid = 1'b0;
			done = 1'b0;
		} else {
			// 動作
			if is_input_phase {
				// 入力モード
				if in_valid {
					if in_char == 8'h20 {
						// 空白が入力されたら、前の文字に基づいて結果の偶奇を更新する
						is_odd &= prev_char[0];
					} else if in_char == 8'h0a {
						// 改行が入力されたら、前の文字に基づいて結果の偶奇を更新する
						// さらに、出力モードに移行し、最初の文字を出力する
						is_odd &= prev_char[0];
						is_input_phase = 1'b0;
						out_valid = 1'b1;
					} else {
						// その他の文字 (数字のはず) が入力されたら、保存しておく
						prev_char = in_char;
					}
				}
			} else {
				// 出力モード
				if ~out_valid {
					// 出力が完了し、次の文字が求められているとき
					if next_char_to_output != 8'd0 {
						// 出力するべき文字が残っているなら、出力を進める
						output_pos += 3'd1;
						out_valid = 1'b1;
					} else {
						// 出力するべき文字が残っていないなら、終了を伝える
						done = 1'b1;
					}
				}
			}
			if out_write {
				// 出力した文字が受け取られたら、出力を完了する
				out_valid = 1'b0;
			}
		}
	}
}
```

# 今回用いた Veryl の構文

## 変数の型

[組み込み型 - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/03_data_type/01_builtin_type.html)
[配列 - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/03_data_type/03_array.html)
[クロックとリセット - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/03_data_type/04_clock_reset.html)

今回は、以下の型を用いた。

* `logic`：1本の線を表す。`0`・`1`・`Z`・`X` の4種類の値をとれる
* `logic<n>`：`n` 本の線のセット (整数) を表す
* `型[n]`：「型」を要素とする`n` 要素の配列を表す
* `clock_posedge`：正極性のクロックを表す
* `reset_async_high`：正極性の非同期リセットを表す

:::note info
極性と同期かを指定しないリセット型 `reset` は、SystemVerilog で書かれたモジュールとの接続には使えない (使うとエラーになる) ようである。
:::

## コメント

[字句構造 - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/02_lexical_structure.html)

行のうち、`//` 以降の部分はコメントになる。

## モジュールの定義

[モジュール - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/07_module.html)
[特徴 - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/02_features.html#trailing-comma)

以下の書式で、モジュールを定義できる。

```text
module モジュール名 {
    // 中身
}
```

ポートを定義するには、以下のようにする。

```text
module モジュール名 (
    ポート名1: 方向1 型1,
    ポート名2: 方向2 型2,
    // ...
) {
    // 中身
}
```

「方向」は、モジュールの外部から内部にデータを渡す入力 `input` や、モジュールの内部から外部にデータを渡す出力 `output` などが使用可能である。

:::note info
ポートリストの最後の要素の後にも、コンマを**つけてよい**。(末尾コンマ)
:::

## SystemVerilog で記述したモジュールなどの使用

[他言語組み込み - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/12_foreign_language_integration.html)
[SystemVerilogとの相互運用 - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/10_systemverilog_interoperation.html)

以下のように記述すると、SystemVerilog でモジュールや関数などを定義できる。

```text
embed (inline) sv{{{
    // SystemVerilog のコード
}}}
```

ここで定義したモジュールなどは、Veryl のコードから `$sv::モジュールなどの名前` として参照できる。

## モジュールのインスタンス化

[インスタンス - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/06_declaration/10_instantiation.html)

モジュールをインスタンス化して他のモジュール内で用いるには、以下のようにする。

```text
inst インスタンス名: モジュール名 (
    // ポートに接続する変数のリスト
);
```

ポートに接続する変数は、変数名とポート名が同じ場合はそのまま変数名を書き、異なる場合は `ポート名: 変数名` のように書く。

## 変数

[変数 - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/06_declaration/01_variable.html)
[配列リテラル - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/02_lexical_structure/03_array_literal.html)

変数を定義するには、以下のようにする。

```text
var 変数名: 型;
```

値を指定する変数を定義するには、以下のようにする。

```text
let 変数名: 型 = 値;
```

値を指定する配列は、以下のように定義できる。

```text
let 変数名: 要素の型[要素数] = '{値リスト};
```

## 整数

[数値 - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/02_lexical_structure/02_number.html)

整数は、以下の書式で表せる。

|種類|書式|
|:-:|:-:|
|2進数|`ビット数'b値`|
|10進数|`ビット数'd値`|
|16進数|`ビット数'h値`|

## 演算子

[演算子 - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/02_lexical_structure/01_operator.html)
[代入 - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/05_statement/01_assignment.html)
[ビット選択 - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/04_expression/06_bit_select.html)
[配列 - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/03_data_type/03_array.html)

今回は、以下の演算子を用いた。

|演算子|意味|
|---|---|
|`a = b`|`a` に `b` を代入する|
|`a += b`|`a` に `a` と `b` の和を代入する|
|`a &= b`|`a` に `a` と `b` のビットANDを代入する|
|`a == b`|`a` と `b` が等しいかを返す|
|`a != b`|`a` と `b` が異なるかを返す|
|`a + b`|`a` と `b` の和を返す|
|`a & b`|`a` と `b` のビットANDを返す|
|`a[b]` (`a` は整数)|`a` の下から `b` ビット目 (0-origin) を返す|
|`a[b]` (`a` は配列)|`a` の `b` 要素目 (0-origin) を返す|

:::note info
Verilog と違って、代入に `<=` は用いない。
:::

## レジスタの定義

[レジスタ - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/06_declaration/03_register.html)

以下のようにして、レジスタを用いた代入を定義できる。
クロックやリセットは、モジュールのポートで指定したものが用いられる。

```text
always_ff {
    if_reset {
        // リセット時に行う操作を記述する
    } else {
        // 通常時 (クロック入力時) に行う操作を記述する
    }
}
```

## 組み合わせ回路の定義

[組み合わせ回路 - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/06_declaration/04_combinational.html)

以下のようにして、組み合わせ回路 (すなわち、レジスタを含まないゲートの組み合わせで、入力を変えるとすぐに (ゲートの遅延のみで) 出力が変わる回路) による代入を定義できる。

```text
always_comb {
    // 代入を記述する
}
```

## 条件分岐

[if - The Veryl Hardware Description Language](https://doc.veryl-lang.org/book/ja/05_language_reference/05_statement/03_if.html)

以下のようにすることで、条件式の真偽によって処理を行うか否かを変えることができる。

```text
if 条件式 {
    // 条件式が真のときのみ行う処理
}
```

```text
if 条件式 {
    // 条件式が真のときのみ行う処理
} else {
    // 条件式が偽のときのみ行う処理
}
```

```text
if 条件式1 {
    // 条件式1が真のときのみ行う処理
} else if 条件式2 {
    // 条件式1が偽、かつ条件式2が真のときのみ行う処理
} else {
    // 条件式1も条件式2も偽のときのみ行う処理
}
```

:::note info
条件式のまわりにカッコ `()` は不要である。
カッコをつけても、それは式全体を囲む無意味なカッコがあるだけなので、問題はない。
:::

# 結論

Veryl と Verilator を用いて、競技プログラミングの問題を解くプログラムをビルドすることができた。