先日は、Verilog で競技プログラミングの問題を解いてみた。
Verilog で競技プログラミングの問題を解いてみる #AtCoder - Qiita
今回は、Veryl で競技プログラミングの問題を解いてみた。
環境構築
ツールのインストール
インストール - The Veryl Hardware Description Language
今回は、AWS EC2 上の Ubuntu 24.04 (AMI ID: ami-05d38da78ce859165) 上で環境構築を行った。
とりあえずアップデートする。
sudo apt-get update
sudo apt-get upgrade -y
Veryl をインストールするためのツールをインストールするためのツールをインストールする。
sudo apt-get install -y cargo
Veryl をインストールするためのツールをインストールする。
これには10分くらいかかった。
cargo install verylup
最後に
warning: be sure to add `/home/ubuntu/.cargo/bin` to your PATH to be able to run the installed binaries
と出たので、これを行う。
echo "export PATH=\$PATH:/home/ubuntu/.cargo/bin" >> .bashrc
source .bashrc
Veryl をインストールする。
verylup setup
また、コードを実行するためのツールと、その実行のために使うツールもインストールしておく。
sudo apt-get install -y verilator make g++
hello, world
Hello, World! - The Veryl Hardware Description Language
Example Create-Binary Execution — Verilator Devel 5.031 documentation
適当な場所 (たとえばホームディレクトリ) に hello ディレクトリを作成し、その中に以下のファイルを置く。
[project]
name = "hello"
version = "0.1.0"
module hello {
initial {
$display("hello, world");
}
}
Veryl のドキュメントでは src ディレクトリ内に hello.veryl を置いているが、このディレクトリは不要である。
この hello ディレクトリを作業ディレクトリにした状態で、以下のコマンドを実行することで、ビルドを行う。
veryl build
verilator --binary -f hello.f
Verilator のドキュメントにある -Wall オプションは、つけてはいけない。
このオプションをつけると、以下のエラーが出て失敗した。
%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 オプションをつけろと主張しているが、このオプションをつけても実行可能ファイルは得られないようだった。
ビルド後、以下のコマンドを実行することで、ビルドしたプログラムを実行する。
./obj_dir/Vhello
すると、以下の出力が得られる。
hello, world
終了する処理を書いていないため、このプログラムは自動では終了しない。
自動で終了する hello, world
前章のプログラムは、終了する処理を書いていないため自動では終了しない。
そこで、終了する処理を追加する。
失敗した方法
まずは Verilog と同じ $finish(0); を試してみた。
module hello {
initial {
$display("hello, world");
$finish(0);
}
}
すると、終了はしたものの、標準出力に余計な出力がされてしまった。
これは競技プログラミングにおいては致命的になるだろう。
hello, world
- /home/ubuntu/hello/hello.sv:4: Verilog $finish
引数を 0 のかわりに -1、1、2 にしても、出力は変わらなかった。
引数をなくして $finish; にすると、エラーになった。
[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:
エラーメッセージを Tera Term からコピペすると罫線がアルファベットに化けてしまったため、半角罫線からコピペして手動で修正した。
$finish(0); のかわりに $stop(0); を使うと、余計な出力が増え、さらに終了コードも 0 ではなく 134 になってしまった。
hello, world
%Error: /home/ubuntu/hello/hello.sv:4: Verilog $stop
Aborting...
Verilator のオプションを調べたものの、この出力を回避する方法は発見できなかった。
Verilator の拡張として、C++ のコードを埋め込める $c というものがある。
Language Extensions — Verilator Devel 5.031 documentation
そこで、これを用いて exit(0) を呼び出すことを考えた。
$c をそのまま書くと、エラーになった。
module hello {
initial {
$display("hello, world");
$c("exit(0);");
}
}
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:: をつけても、エラーになった。
module hello {
initial {
$display("hello, world");
$sv::$c("exit(0);");
}
}
[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# をつけてみても、エラーになった。
module hello {
initial {
$display("hello, world");
$sv::r#$c("exit(0);");
}
}
[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 による埋め込みを試みたが、これもインラインではエラーになった。
module hello {
initial {
$display("hello, world");
embed (inline) sv{{{
$c("exit(0);");
}}}
}
}
[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 内で代入することはできないと怒られてしまった。
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
}}}
[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 をつけても、ダメだった。
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
}}}
[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:
SystemVerilog の戻り値の無い関数 (task) として $c("exit(0);"); を呼び出す関数を定義し、それを用いることで、余計な出力をせずに終了コード 0 でプログラムの実行を終了することができた。
$c は、C++ のコードを埋め込んで実行する Verilator の拡張 である。
module hello {
initial {
$display("hello, world");
$sv::exit();
}
}
embed (inline) sv{{{
task exit;
$c("exit(0);");
endtask
}}}
hello, world
問題を解いてみる
今回は、AtCoder Beginners Selection に含まれる問題
を解いてみることにした。
この問題は、空白区切りで2個の正の整数が与えられ、その積が偶数か奇数かを判定する問題である。
与えられる整数の1の位だけを見て、それらが全て奇数なら奇数、1個でも偶数があれば偶数と判定すればよい。
これは、たとえば以下のように実装できる。
[project]
name = "abs_abc086_a"
version = "0.1.0"
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
配列 - The Veryl Hardware Description Language
クロックとリセット - The Veryl Hardware Description Language
今回は、以下の型を用いた。
-
logic：1本の線を表す。0・1・Z・Xの4種類の値をとれる -
logic<n>：n本の線のセット (整数) を表す -
型[n]：「型」を要素とするn要素の配列を表す -
clock_posedge：正極性のクロックを表す -
reset_async_high：正極性の非同期リセットを表す
極性と同期かを指定しないリセット型 reset は、SystemVerilog で書かれたモジュールとの接続には使えない (使うとエラーになる) ようである。
コメント
字句構造 - The Veryl Hardware Description Language
行のうち、// 以降の部分はコメントになる。
モジュールの定義
モジュール - The Veryl Hardware Description Language
特徴 - The Veryl Hardware Description Language
以下の書式で、モジュールを定義できる。
module モジュール名 {
// 中身
}
ポートを定義するには、以下のようにする。
module モジュール名 (
ポート名1: 方向1 型1,
ポート名2: 方向2 型2,
// ...
) {
// 中身
}
「方向」は、モジュールの外部から内部にデータを渡す入力 input や、モジュールの内部から外部にデータを渡す出力 output などが使用可能である。
ポートリストの最後の要素の後にも、コンマをつけてよい。(末尾コンマ)
SystemVerilog で記述したモジュールなどの使用
他言語組み込み - The Veryl Hardware Description Language
SystemVerilogとの相互運用 - The Veryl Hardware Description Language
以下のように記述すると、SystemVerilog でモジュールや関数などを定義できる。
embed (inline) sv{{{
// SystemVerilog のコード
}}}
ここで定義したモジュールなどは、Veryl のコードから $sv::モジュールなどの名前 として参照できる。
モジュールのインスタンス化
インスタンス - The Veryl Hardware Description Language
モジュールをインスタンス化して他のモジュール内で用いるには、以下のようにする。
inst インスタンス名: モジュール名 (
// ポートに接続する変数のリスト
);
ポートに接続する変数は、変数名とポート名が同じ場合はそのまま変数名を書き、異なる場合は ポート名: 変数名 のように書く。
変数
変数 - The Veryl Hardware Description Language
配列リテラル - The Veryl Hardware Description Language
変数を定義するには、以下のようにする。
var 変数名: 型;
値を指定する変数を定義するには、以下のようにする。
let 変数名: 型 = 値;
値を指定する配列は、以下のように定義できる。
let 変数名: 要素の型[要素数] = '{値リスト};
整数
数値 - The Veryl Hardware Description Language
整数は、以下の書式で表せる。
| 種類 | 書式 |
|---|---|
| 2進数 | ビット数'b値 |
| 10進数 | ビット数'd値 |
| 16進数 | ビット数'h値 |
演算子
演算子 - The Veryl Hardware Description Language
代入 - The Veryl Hardware Description Language
ビット選択 - The Veryl Hardware Description Language
配列 - The Veryl Hardware Description Language
今回は、以下の演算子を用いた。
| 演算子 | 意味 |
|---|---|
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) を返す |
Verilog と違って、代入に <= は用いない。
レジスタの定義
レジスタ - The Veryl Hardware Description Language
以下のようにして、レジスタを用いた代入を定義できる。
クロックやリセットは、モジュールのポートで指定したものが用いられる。
always_ff {
if_reset {
// リセット時に行う操作を記述する
} else {
// 通常時 (クロック入力時) に行う操作を記述する
}
}
組み合わせ回路の定義
組み合わせ回路 - The Veryl Hardware Description Language
以下のようにして、組み合わせ回路 (すなわち、レジスタを含まないゲートの組み合わせで、入力を変えるとすぐに (ゲートの遅延のみで) 出力が変わる回路) による代入を定義できる。
always_comb {
// 代入を記述する
}
条件分岐
if - The Veryl Hardware Description Language
以下のようにすることで、条件式の真偽によって処理を行うか否かを変えることができる。
if 条件式 {
// 条件式が真のときのみ行う処理
}
if 条件式 {
// 条件式が真のときのみ行う処理
} else {
// 条件式が偽のときのみ行う処理
}
if 条件式1 {
// 条件式1が真のときのみ行う処理
} else if 条件式2 {
// 条件式1が偽、かつ条件式2が真のときのみ行う処理
} else {
// 条件式1も条件式2も偽のときのみ行う処理
}
条件式のまわりにカッコ () は不要である。
カッコをつけても、それは式全体を囲む無意味なカッコがあるだけなので、問題はない。
結論
Veryl と Verilator を用いて、競技プログラミングの問題を解くプログラムをビルドすることができた。