大学の講義で扱った MIPS のアセンブリ言語で競技プログラミングの問題を解いてみた。
環境構築
今回は、AWS EC2 の Ubuntu 24.04 (AMI ID: ami-05d38da78ce859165) で実行環境を構築してみた。
とりあえず環境をアップデートする。
sudo apt-get update
sudo apt-get -y upgrade
アセンブラ (Binutils) と実行ツール (QEMU) をインストールする。
sudo apt-get install -y binutils-mips-linux-gnu qemu-user
以下のようにして、アセンブリ言語のプログラム program.s を実行可能ファイル program に変換できる。
mips-linux-gnu-as -o program.o program.s
mips-linux-gnu-ld -o program program.o
以下のようにして、変換した実行可能ファイル program を実行できる。
qemu-mips program
今回の環境におけるアセンブリ言語
システムコール
今回の環境では、よく言われる「1 で整数を出力、10 で終了」などのシステムコールは使えないようである。
かわりに、https://syscalls.w3challs.com/?arch=mips_o32 で挙げられているシステムコールが使えるようである。
たとえば、以下のシステムコールが使える。
| 操作 | $v0 | $a0 | $a1 | $a2 |
|---|---|---|---|---|
| 終了 (exit) | 0xfa1 | 終了コード | - | - |
| 入力 (read) | 0xfa3 | ファイル ディスクリプタ |
ストア先ポインタ | 最大入力バイト数 |
| 出力 (write) | 0xfa4 | ファイル ディスクリプタ |
ロード元ポインタ | 出力バイト数 |
ファイルディスクリプタは、標準入力が 0、標準出力が 1、などである。
システムコールを実行すると、結果を表す値が $v0 に格納される。
また、callee-save レジスタの値は保持されるが、caller-save レジスタの値は破壊される可能性がある。
ただし、$a0・$a1・$a2 レジスタの値も保持される。
エントリポイント
プログラムの実行を開始する場所として、__start ラベルを定義することが求められる。
さらに、ただ定義するだけではなく、.global を使用して公開することも求められる。
.global __start
__start:
# 正常終了する
addi $v0, $zero, 0xfa1
addi $a0, $zero, 0
syscall
遅延分岐スロットを手動で扱う
MIPS といえば、分岐命令により飛ぶ場合でも分岐命令の1個次の命令を実行してから飛び先の実行に移る「遅延分岐スロット」の存在が特徴的である。
しかし、そのことを確認しようとして以下のプログラムを実行しても、命令 addi $a0, $zero, 1 は実行されず、終了コードは 0 となってしまう。
.global __start
__start:
addi $v0, $zero, 0xfa1
addi $a0, $zero, 0
j dest
addi $a0, $zero, 1 # 実行されない
dest:
syscall
これは、アセンブラが命令列を以下のように自動で変更し、遅延分岐スロットが存在しないかのように実行させるためである。
(これは、mips-linux-gnu-objdump -d program で逆アセンブルすることにより確認できる)
Disassembly of section .text:
004000d0 <__start>:
4000d0: 20020fa1 addi v0,zero,4001
4000d4: 08100038 j 4000e0 <dest>
4000d8: 20040000 addi a0,zero,0
4000dc: 20040001 addi a0,zero,1
004000e0 <dest>:
4000e0: 0000000c syscall
...
この自動変更を停止し、遅延分岐スロットを手動で考慮したプログラムをそのまま実行させるには、プログラムの先頭に .set noreorder を加えるとよい。
.set noreorder
.global __start
__start:
addi $v0, $zero, 0xfa1
addi $a0, $zero, 0
j dest
addi $a0, $zero, 1 # 実行される
dest:
syscall
実装
PracticeA - Welcome to AtCoder
を解くプログラムを実装してみた。
これは、3個の整数と1行の文字列が与えられるので、これらの整数の和と与えられた文字列を空白区切りで出力する問題である。
.set noreorder
.text
.global __start
__start:
addi $s0, $zero, 0 # 整数の和
addi $s1, $zero, 3 # 読み込む整数の数
# 文字を読み込む準備
addi $a0, $zero, 0
la $a1, data_buffer
addi $a2, $zero, 1
read_ints:
addi $s3, $zero, 0 # 今回読み込んだ整数
read_one_int:
# 文字を読み込む
addi $v0, $zero, 0xfa3
syscall
lb $t0, ($a1)
# 今回読み込んだ整数に10を掛ける (ロード直後の値を用いるのは避ける)
sll $t1, $s3, 1
sll $t2, $s3, 3
add $t1, $t1, $t2
# 読み込んだ値が '0' 未満 (改行や空白) なら、読み込みを終了する
slti $t2, $t0, 0x30
bne $t2, $zero, read_one_int_end
addi $t0, $t0, -0x30
# 今回読み込んだ整数を更新する
j read_one_int
add $s3, $t1, $t0 # 遅延分岐スロット
read_one_int_end:
addi $s1, $s1, -1
bne $s1, $zero, read_ints
add $s0, $s0, $s3 # 読み込んだ整数を足す (遅延分岐スロット)
# 求めた整数の和を文字列に変換し、出力する (空白も足しておく)
addi $s2, $zero, 10 # 除算用 (十進数)
addi $s3, $a1, 15 # 変換結果の最後の要素の次の要素へのポインタ
addi $s4, $s3, -1 # 次に変換結果を格納する要素へのポインタ
addi $t0, $zero, 0x20
sb $t0, ($s4)
write_int:
# 整数の和を10で割り、余りに '0' を足して文字列として格納する
div $s0, $s2
mfhi $t0
mflo $s0
addi $t0, $t0, 0x30
sb $t0, -1($s4)
# 商が 0 でないなら、次の桁の変換に進む
bne $s0, $zero, write_int
addi $s4, $s4, -1 # 格納先を更新する (遅延分岐スロット)
# 変換結果の文字列を出力する
addi $v0, $zero, 0xfa4
addi $a0, $zero, 1
addi $a1, $s4, 0
sub $a2, $s3, $s4
syscall
# 1行読み、そのまま出力する
addi $s1, $zero, 0x0a # 改行コードを読み込んだら終了する用
addi $a0, $zero, 0
la $a1, data_buffer
addi $a2, $zero, 1
print_line:
addi $v0, $zero, 0xfa3
syscall
lb $s0, ($a1)
addi $a0, $zero, 1
addi $v0, $zero, 0xfa4
syscall
bne $s0, $s1, print_line
# プログラムを終了する
addi $a0, $zero, 0 # 終了コードの 0 と読み込み元の標準入力を兼ねる
addi $v0, $zero, 0xfa1
syscall
.data
data_buffer:
.space 16
結論
Ubuntu 24.04 上で MIPS のアセンブラと実行用プログラムを用意し、競技プログラミングの問題を解くコードを動かすことができた。