オープンソースのツールを使い、Welcome to AtCoder を解くプログラムをFPGAで動かす

先日、Verilog で [Welcome to AtCoder](https://atcoder.jp/contests/abs/tasks/practice_1) を解くプログラムを作成した。

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

今回は、これを以下のツールを用いて実際の FPGA 上で動かしてみた。

* [GitHub - YosysHQ/yosys: Yosys Open SYnthesis Suite](https://github.com/YosysHQ/yosys)
* [GitHub - YosysHQ/nextpnr: nextpnr portable FPGA place and route tool](https://github.com/YosysHQ/nextpnr)
* [GitHub - YosysHQ/prjtrellis: Documenting the Lattice ECP5 bit-stream format.](https://github.com/YosysHQ/prjtrellis)

# 今回用いる FPGA

今回は、以前 AliExpress で購入した「iCESugar-pro」という FPGA ボードを用いた。
これには、Lattice LFE5U-25F-6BG256C という FPGA が搭載されている。

![iCESugar-pro](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/d0fcd6cb-59d6-813b-bfd3-02cae70e0470.jpeg)

購入履歴上のページはこれだが、今は別の製品が売られているようである。

[iCESugar FPGA Board Open Source RISC-V ICE40UP5k Icebreaker Fomu - AliExpress 7](https://www.aliexpress.com/item/1005003035175513.html)

現在のページでは、たとえばこれが近そうである。

[iCESugar-Pro FPGA Development-Board Lattice ECP5 FPGA RISC-V Linux SODIMM Module - AliExpress 7](https://www.aliexpress.com/item/1005002270742248.html)

入出力などの情報は以下のページにある。

[GitHub - wuxx/icesugar-pro: iCESugar series FPGA dev board](https://github.com/wuxx/icesugar-pro)

特に、以下のポートが重要である。

|ポート|接続先|
|:-:|---|
|P6|クロック入力 (25MHz)|
|A9|USB-UART TX (FPGAへの入力)|
|B9|USB-UART RX (FPGAからの出力)|
|B11|LED出力 赤|
|A11|LED出力 緑|
|A12|LED出力 青|
|J12|メモリーカード CLK|
|H12|メモリーカード CMD|
|K12|メモリーカード D0|
|L12|メモリーカード D1|
|F5|メモリーカード D2|
|G5|メモリーカード D3|

# 環境構築

Amazon EC2 上の Ubuntu 24.04 (AMI ID: `ami-05d38da78ce859165`) 上で環境構築を行った。
インスタンスタイプは t2.xlarge を用い、ストレージのサイズは 16 GiB とした。

:::note warn
デフォルトの 8 GiB のストレージを用いると、nextpnr のインストール中にストレージが足りなくなってしまった。
また、インスタンスタイプ t2.micro を用いると、Yosys のインストール中にフリーズしてしまった。
:::

とりあえず環境のアップデートを行う。

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

要求されるパッケージをインストールする。
(Yosys のページで紹介されているコマンドに、その他のツールで要求されたパッケージを追加した)

```bash
sudo apt-get install -y build-essential clang lld bison flex \
    libreadline-dev gawk tcl-dev libffi-dev git \
    graphviz xdot pkg-config python3 libboost-system-dev \
    libboost-python-dev libboost-filesystem-dev zlib1g-dev \
    cmake libboost-all-dev libeigen3-dev
```

Yosys をインストールする。

```bash
git clone --recurse-submodules https://github.com/YosysHQ/yosys.git
cd yosys
make -j 4
sudo make install
```

:::note info
この手順は、約20分かかった。
:::

Project Trellis をインストールする。

```bash
cd ~
git clone --recursive https://github.com/YosysHQ/prjtrellis
cd prjtrellis/libtrellis
cmake -DCMAKE_INSTALL_PREFIX=/usr/local .
make -j 4
sudo make install
```

:::note info
この手順は、約5分かかった。
:::

nextpnr をインストールする。

```bash
cd ~
git clone https://github.com/YosysHQ/nextpnr.git
cd nextpnr
cmake . -DARCH=ecp5 -DTRELLIS_INSTALL_PREFIX=/usr/local
make -j 4
sudo make install
```

:::note info
この手順は、約10分かかった。
:::

# 実装

今回の実装は、以下の3個の `.v` ファイルと、1個の `.lpf` ファイルからなる。

## welcome.v

[先日の記事](https://qiita.com/mikecat_mixc/items/b8aadfc3053c49feaf18) ほぼそのままだが、リセットを同期式に変更している。

```verilog:welcome.v
// 問題を解くモジュール
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 @(posedge clock) begin
		if (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 else 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
```

## uart.v

UART の送受信を行う。
ブレークの受信に対応している。
通信速度 (0.5ビットが何クロックに対応するか) をパラメータで指定する。

```verilog:uart.v
module uart #(
	parameter clock_per_half_bit = 32'd1
) (
	clock, reset, rx, tx,
	rxchar, rxchar_valid, rxchar_read,
	txchar, txchar_valid, txchar_read,
	break_received
);
	input clock;
	input reset;
	input rx;
	output reg tx;
	output reg [7:0] rxchar;
	output reg rxchar_valid;
	input rxchar_read;
	input [7:0] txchar;
	input txchar_valid;
	output txchar_read;
	output reg break_received;

	reg receiving;
	reg [31:0] receive_timer;
	reg receive_next_sample;
	reg [3:0] receive_bit_count;
	reg [7:0] received_bits;

	reg sending;
	reg [31:0] send_timer;
	reg send_next_sample;
	reg [3:0] send_bit_count;
	reg [7:0] send_bits;

	assign txchar_read = txchar_valid & ~sending;

	always @(posedge clock) begin
		if (reset) begin
			tx <= 1'b1;
			rxchar <= 8'd0;
			rxchar_valid <= 1'b0;
			break_received <= 1'b0;

			receiving <= 1'b0;
			receive_timer <= 32'd0;
			receive_next_sample <= 1'b0;
			receive_bit_count <= 4'd0;
			received_bits <= 8'd0;

			sending <= 1'b0;
			send_timer <= 32'd0;
			send_next_sample <= 1'b0;
			send_bit_count <= 4'd0;
			send_bits <= 8'd0;
		end else begin
			// 受信処理
			if (receiving) begin
				if (receive_timer == 32'd0) begin
					receive_timer <= clock_per_half_bit - 32'd1;
					receive_next_sample <= ~receive_next_sample;
					if (receive_next_sample) begin
						if (receive_bit_count == 4'd0) begin
							// スタートビット？
							if (rx) begin
								// キャンセル
								receiving <= 1'b0;
							end else begin
								receive_bit_count <= receive_bit_count + 4'd1;
							end
						end else if (receive_bit_count == 4'd9) begin
							// ストップビット？
							if (rx) begin
								// ストップビット → バイト確定、出力
								receiving <= 1'b0;
								rxchar <= received_bits;
								rxchar_valid <= 1'b1;
							end else begin
								// ストップビットなし → 受信状態継続
								receive_bit_count <= receive_bit_count + 4'd1;
							end
						end else if (receive_bit_count == 4'd15) begin
							// ブレーク？
							if (rx) begin
								receiving <= 1'b0;
								break_received <= 1'b0;
							end else begin
								// これまでのビットが全て0 → ブレーク
								if (received_bits == 8'd0) begin
									break_received <= 1'b1;
								end
							end
						end else if (receive_bit_count > 4'd9) begin
							// ストップビット？後
							if (rx) begin
								receiving <= 1'b0;
							end else begin
								receive_bit_count <= receive_bit_count + 4'd1;
							end
						end else begin
							// データビット → MSBに挿入
							receive_bit_count <= receive_bit_count + 4'd1;
							received_bits <= {rx, received_bits[7:1]};
						end
					end
				end else begin
					receive_timer <= receive_timer - 32'd1;
				end
			end else begin
				if (!rx) begin
					receive_timer <= clock_per_half_bit - 32'd1;
					receiving <= 1'b1;
					receive_next_sample <= 1'b1;
					receive_bit_count <= 4'd0;
				end
			end
			if (rxchar_read) begin
				rxchar_valid <= 1'b0;
			end

			// 送信処理
			if (sending) begin
				if (send_timer == 32'd0) begin
					send_timer <= clock_per_half_bit - 32'd1;
					send_next_sample <= ~send_next_sample;
					if (send_next_sample) begin
						if (send_bit_count == 4'd9) begin
							sending <= 1'b0;
						end else begin
							tx <= send_bits[0];
							send_bits <= {1'b1, send_bits[7:1]};
							send_bit_count <= send_bit_count + 4'd1;
						end
					end
				end else begin
					send_timer <= send_timer - 32'd1;
				end
			end else begin
				if (txchar_valid) begin
					sending <= 1'b1;
					send_timer <= clock_per_half_bit - 32'd1;
					send_next_sample <= 1'b0;
					send_bit_count <= 4'd0;
					send_bits <= txchar;
					tx <= 1'b0;
				end
			end
		end
	end

endmodule
```

## welcome_top.v

問題を解くモジュールと UART の送受信を行うモジュールを接続する。
また、起動時のリセットを行う。

```verilog:welcome_top.v
module welcome_top(clk, rx, tx, done);
	input clk;
	input rx;
	output tx;
	output done;

	reg [15:0] boot_timer;
	wire boot_reset = boot_timer != 16'hffff;

	initial begin
		boot_timer <= 16'd0;
	end

	always @(posedge clk) begin
		if (boot_reset) begin
			boot_timer <= boot_timer + 16'd1;
		end
	end

	wire [7:0] rxchar;
	wire rxchar_valid, rxchar_read;
	wire [7:0] txchar;
	wire txchar_valid, txchar_read;
	wire break_received;

	welcome welcome(
		.clock(clk), .reset(boot_reset | break_received),
		.input_char(rxchar), .input_valid(rxchar_valid), .input_read(rxchar_read),
		.output_char(txchar), .output_valid(txchar_valid), .output_read(txchar_read),
		.done(done)
	);

	uart #(
		.clock_per_half_bit(32'd1302) // 25MHz / 9600bps / 2
	) uart (
		.clock(clk), .reset(boot_reset), .rx(rx), .tx(tx),
		.rxchar(rxchar), .rxchar_valid(rxchar_valid), .rxchar_read(rxchar_read),
		.txchar(txchar), .txchar_valid(txchar_valid), .txchar_read(txchar_read),
		.break_received(break_received)
	);

endmodule
```

## welcome.lpf

トップレベルのモジュールのポートと、FPGA の物理ポートの対応を記述するファイルである。
~~昔 (2022年5月) の自分が残していたファイルを雰囲気で書き換えた。おそらく昔の自分もサンプルに含まれていたファイルを雰囲気で書き換えていたのだろう。~~

* `LOCATE` の行でポートの対応を記述する
* `IOBUF` の行でポートの種類を記述する
* `FREQUENCY` の行でポートに入力されるクロック周波数を記述する

ようである。

```text:welcome.lpf
LOCATE COMP "clk" SITE "P6";
IOBUF PORT "clk" IO_TYPE=LVCMOS33;
FREQUENCY PORT "clk" 25 MHZ;

LOCATE COMP "rx" SITE "A9";
LOCATE COMP "tx" SITE "B9";
LOCATE COMP "done" SITE "B11";

IOBUF PORT "rx" IO_TYPE=LVCMOS33;
IOBUF PORT "tx" IO_TYPE=LVCMOS33;
IOBUF PORT "done" IO_TYPE=LVCMOS33;
```

# ビルド

~~昔 (2022年5月) の自分が出典もなく残していたコマンドを使ったらできた。意味はよくわからない。~~

以下の流れでファイルを作成していくようである。

1. `yosys` コマンドで、`*.v` ファイルから `*.json` ファイルを作る
2. `nextpnr-ecp5` コマンドで、`*.json` ファイルと `*.lpf` ファイルから `*.out_config` ファイルを作る
3. `ecppack` コマンドで、`*.out_config` ファイルから `*.svf` ファイルと `*.bit` ファイルを作る

![ファイル作成の流れ](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/4b620f1b-dc8d-8a0e-066a-081693da706f.png)

具体的には、「実装」の章で用意した4個のファイルを格納したディレクトリで、以下のコマンドを順に実行する。

```bash
yosys -p "synth_ecp5 -top welcome_top -json welcome.json" *.v
```

`-top` に続いて、トップとなるモジュールの名前を指定する。

```bash
nextpnr-ecp5 --25k --package CABGA256 --speed 6 --freq 65 --top welcome_top \
    --textcfg welcome.out_config --json welcome.json --lpf welcome.lpf
```

`--25k --package CABGA256 --speed 6` の部分で、用いる FPGA の種類を指定している。

`--freq 65` は、「set target frequency for design in MHz」とのことである。(`--help` の出力より)
クロックは 25MHz のはずだが、高めに設定しておいたほうがつよそう、かな？

`--top` に続いて、トップとなるモジュールの名前を指定する。
yosys ではハイフンが1個の `-top` だったが、こちらではハイフンが2個である。

```bash
ecppack --svf welcome.svf welcome.out_config welcome.bit
```

入出力のファイル名を設定しているのみのようである。

# 実行

FPGA ボードをパソコンに USB ケーブルで接続すると、USB 大容量記憶装置 (USBメモリ) として認識される。
そのドライブに作成した `welcome.bit` をコピーすると、FPGA にプログラムが書き込まれ、動作する。

:::note info
拡張基板 (緑色の基板) にある USB コネクタではなく、本体 (黒色の基板) にある USB コネクタで接続する。
また、`.svf` ファイルではなく `.bit` ファイルをコピーする。
:::

USB 接続によってシリアルポートも認識されるため、[Tera Term](https://teratermproject.github.io/) で接続した。
そして、入力データを送信すると、出力データが表示され、処理完了を表す赤色LEDが点灯することを確認できた。

:::note info
Tera Term のデフォルトの改行コードは CR のようなので、送受信ともに LF に変更してから送受信を行う。
通信速度はデフォルトの 9600bps を用いる。
:::

以下は、プログラムの FPGA への書き込み時に出力されたメッセージに続いて Welcome to AtCoder の入力例2を送信 (ローカルエコー有り) し、出力が返ってきている様子である。

![Tera Term での実行の様子](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/1f3bbde4-cd10-fedb-71ed-c616d5af5568.png)

今回、UART のブレーク信号によりリセットできるようにしたが、残念ながらこの FPGA ボードに搭載されている USB-シリアル変換器はブレーク信号の送信に対応していないようで、Tera Term の「ブレーク送信」を押しても反応しなかった。
そこで、一旦通信速度を 4800bps に変更し、Ctrl+Space を押す (値 0x00 のバイトを送信する) ことで、ブレークのかわりとなる信号を送信し、リセットを行うことができた。
この操作を行った後は、次の送受信を行う前に通信速度を 9600bps に戻すのを忘れないようにする。

# まとめ

先日作成した Welcome to AtCoder を解くモジュールに加え、UART の送受信を行うモジュールを用意した。
さらに、これらのモジュールを接続するモジュールも用意した。

オープンソースのツールを Amazon EC2 上の Ubuntu 24.04 にインストールし、それを用いてこれらのモジュールから FPGA ボードに書き込めるデータを作成できた。

作成したデータを実際に FPGA ボードに書き込み、Welcome to AtCoder を解くプログラムが動作することを確認できた。