Qiita Engineer Festa 2024（キータ・エンジニア・フェスタ 2024） - Qiita
において、約1ヶ月で38記事という大量の記事の投稿を要求されることがわかった。
そこで、あまりコストをかけずに記事数を稼ぐ方法を考えた結果、「Welcome to AtCoder を様々な言語で解く」ことを思いついた。
単に解くだけでなく、使用する言語仕様の解説を入れれば、記事として一応成立するだろう。
Welcome to AtCoder
PracticeA - Welcome to AtCoder
Welcome to AtCoder では、以下の形式で整数 $a$, $b$, $c$ および文字列 $s$ が入力として与えられる。
a
b c
s
この入力をもとに、与えられた整数の和 $sum = a + b + c$ および文字列 $s$ を、以下の形式で出力することが求められる。
sum s
整数 $a$, $b$, $c$ は 1 以上 1,000 以下である。
今回用いる機能
AtCoder の Assembly x64 は、x86_64 向けのアセンブリ言語 (NASM) である。
レジスタ
x86_64 では、64ビットの整数を格納する以下のレジスタが使用できる。
- RAX、RBX、RCX、RDX
- RSI、RDI
- RSP
- RBP
- R8 ～ R15
このうち、RAX、RBX、RCX、RDX については、以下のように32ビット、16ビット、8ビットの部分を用いることができる。
| 64ビット | 下位32ビット | 下位16ビット | 下位8ビット | 下位16ビット中の 上位8ビット |
|---|---|---|---|---|
| RAX | EAX | AX | AL | AH |
| RBX | EBX | BX | BL | BH |
| RCX | ECX | CX | CL | CH |
| RDX | EDX | DX | DL | DH |
また、詳細は省略するが、今回挙げたこれ以外のレジスタについてもそれぞれ下位32ビット、下位16ビット、下位8ビットの部分を用いることができる。
これらのレジスタの「下位32ビット」に値を書き込むと、64ビットのうち残りの部分 (上位32ビット) はゼロクリアされる。
たとえば、EAX に値を書き込むと、RAX の上位32ビットはゼロクリアされる。
16ビットや8ビットの部分への書き込みでは、このようなゼロクリアは起こらない。
RSP レジスタは、通常スタックポインタとして用い、スタック上で最後のデータ (スタックトップ) があるアドレスを格納する。
RBP レジスタは、通常ベースポインタとして用い、スタック上のローカル変数の位置の基準となるアドレスを格納する。
対象とするCPUモードの明示
BITS を用いることで、記述するプログラムが想定するCPUモードを明示できる。
今回は、64ビットモードを想定するので、
bits 64
とする。
モードはアセンブル時の出力形式などから自動で推定されるので明示は不要であるが、明示しておいたほうがわかりやすいだろう。
スタック上のデータを実行不可にする
アセンブラを混ぜてコンパイルするとスタックが実行可になってしまう話 #Linux - Qiita
スタック上のデータは、セキュリティのため実行を許さないのがよいとされる。
.note.GNU-stack セクションを作ることで、スタック上のデータを実行させないことを示すことが出来る。
section .note.GNU-stack
と書くことで、このセクションを作ることができる。
さらに
section .text
と書くことで、この後書くコードを通常のプログラムを配置する .text セクションに配置できる。
命令の記述方法
NASM では、Intel記法で命令を記述する。
これは、基本的に
命令 デスティネーション, ソース
の形式で記述する記法である。
(命令によっては、引数の数が異なる場合もある)
たとえば、EAX レジスタに定数 72 を格納する命令は
mov eax, 72
と記述できる。
このように、レジスタや即値はそのまま記述すればよい。
メモリアクセスは、アクセスするアドレスを [] で囲って表現する。
たとえば、RSP レジスタが指す場所のデータを EAX レジスタにロードする命令は
mov eax, [rsp]
と記述できる。
[] の前に以下のキーワードを用いることで、アクセスするメモリのサイズを指定できる。
即値を書き込む場合など、他のオペランドなどからアクセスするサイズがわからない場合、このような指定が必要である。
mov byte [rax], 72 ; 1 バイト
mov word [rax], 72 ; 2 バイト
mov dword [rax], 72 ; 4 バイト
mov qword [rax], 72 ; 8 バイト
エスケープシーケンスを無視する文字列は、"" または '' で囲って表現できる。
エスケープシーケンスが有効な文字列は、`` で囲って表現できる。
(3.4.2 Character Strings)
短い (8バイト以下の) 文字列は、リトルエンディアンで解釈して数値として使用できる。
(3.4.3 Character Constants)
mov eax, '\n' ; eax に 0x6e5c を格納する
mov eax, `\n` ; eax に 0x0a を格納する
関数の作り方
System V Application Binary Interface (3.2 Function Calling Sequence)
ラベルと関数の公開
関数は、ラベルを用いてその関数が呼ばれた時に実行を開始する場所を指定することで作成する。
global ラベル を用いると、指定したラベルを標準ライブラリを含む他のファイル (プログラム) から参照できるようになる。
実行開始時に標準ライブラリから呼び出される main 関数は、この global を用いて参照できるようにしておかなければならない。
global func ; func 関数を外部から参照できるようにする
func: ; func 関数の実行開始点
; func 関数の処理内容
ret ; func関数から呼び出し元に戻る
レジスタの使い方
caller-save と callee-save
RAX、RCX、RDX、RSI、RDI、R8～R11 レジスタは、関数内で自由に使用し、呼び出された時の値を復元せずに関数から戻ってもよい。(caller-save)
逆に、関数内で関数を呼び出すと、これらのレジスタの値は変化する可能性がある。
RBX、RSP、RBP、R12～R15 レジスタは、関数内で使用しないか、使用した場合は関数から戻る際には関数が呼び出されたときと同じ値が格納された状態に復元しなければならない。(callee-save)
逆に、関数内から関数を呼び出しても、これらのレジスタの値は変化しないことになっている。
引数と戻り値
1個のレジスタに収まるサイズの整数である引数や返り値は、以下のレジスタに格納する。
| データ | レジスタ |
|---|---|
| 第1引数 | RDI |
| 第2引数 | RSI |
| 第3引数 | RDX |
| 第4引数 | RCX |
| 第5引数 | R8 |
| 第6引数 | R9 |
| 戻り値 | RAX |
1個のレジスタに収まらないサイズ (構造体など)・整数以外・第7引数以降の渡し方も定義されているが、今回は使わないのでここでは省略する。
中で関数を呼び出す関数
中で関数を呼び出す関数では、呼び出された後最初に行う処理であるプロローグでスタックフレームを作成し、呼び出し元に戻る直前に行う処理であるエピローグで作成したスタックフレームを破棄するのが基本である。
func:
; プロローグ
push rbp ; スタックに現在の RBP の値をプッシュする
mov rbp, rsp ; RBP にスタックポインタの値 (前の RBP の値を格納したアドレス) を格納する
sub rsp, 16 ; スタック上にローカル変数用の領域を確保する
; 関数の処理本体
; エピローグ
leave ; スタックポインタを RBP の値に設定し、スタックから RBP に値をポップする
ret ; 呼び出し元に戻る
関数を呼び出す際、スタックポインタの値は 16 の倍数でなければならないことになっている。
関数を呼び出すと、戻り先のアドレスがスタックにプッシュされ、スタックポインタの値が 8 減る。
この状態でさらに RBP をプッシュすると、スタックポインタの値がさらに 8 減り、再び 16 の倍数になる。
よって、その後関数を呼び出す前にスタックポインタから減算する量 (の合計) は 16 の倍数でなければならない。
上のコード例では例として 16 を減算しているが、処理内容に応じてより大きい 16 の倍数を減算したり、逆に 0 を減算したり (または、この sub 命令を省略したり) してもいい。
このプロローグの実行後、スタックは以下の状態になる。
callee-save レジスタの値も、復元用に「ローカル変数」の領域に保存することがある。
leave 命令を用いると、このプロローグの操作の逆を行い、RBP およびスタックポインタ (RSP) の値を関数が呼び出された時の値に戻すことで、関数から戻る準備を行うことができる。
エピローグでは、この命令を用いて関数から戻る準備をした後、ret 命令により呼び出し元に戻る。
プロローグに相当する操作ができる enter 命令も存在するが、効率が悪いとされ、あまり用いられない。
中で関数を呼び出さない関数
中で関数を呼び出さない関数 (leaf functions) では、スタックフレームを作らず、直接 RSP を基準にしてローカル変数などを扱ってもよい。
このとき、RSP から 128 を引いたアドレス以上 RSP 未満の部分を red zone といい、この部分は割り込みハンドラなどに破壊されることなく用いることができることになっている。
これより大きい領域をローカル変数で用いる場合など、スタックフレームを作ってもよい。
中で関数を呼び出す関数の実行中にも red zone は存在するが、関数を呼び出す際にスタックにプッシュされる戻り先アドレスや呼び出す関数のローカル変数などによりデータが破壊されることがあるため、一般にデータの保存には適さない。
システムコール
Linux System Call Table for x86 64 · Ryan A. Chapman
System V Application Binary Interface (A.2 AMD64 Linux Kernel Conventions)
システムコールを用いることで、入出力などのシステム (OS) が用意する機能を用いることができる。
x86_64 の Linux におけるシステムコールは、以下の値を各レジスタに設定し、syscall 命令を実行することで呼び出すことができる。
| レジスタ | 設定する値 |
|---|---|
| RAX | システムコール番号 |
| RDI | 第1引数 |
| RSI | 第2引数 |
| RDX | 第3引数 |
| R10 | 第4引数 |
| R8 | 第5引数 |
| R9 | 第6引数 |
レジスタに収まらないデータ・整数以外・第7引数以降は用いない。
システムコールを実行すると、RAX レジスタに結果を表す数値が格納される。
また、RCX レジスタおよび R11 レジスタの値が破壊される。
read
read(2): read from file descriptor - Linux man page
以下の内容をレジスタに格納して呼び出す。
| レジスタ | 設定する内容 |
|---|---|
| RAX | 0 |
| RDI | 読み込み元のファイルディスクリプタ |
| RSI | 読み込んだデータを格納するメモリアドレス |
| RDX | 読み込む最大のバイト数 |
指定したファイルディスクリプタに対応するファイルからデータを読み込み、メモリに格納する。
通常、標準入力に対応するファイルディスクリプタは 0 である。
成功した場合は、RAX に読み込んだバイト数が格納される。
失敗した場合は、RAX に負の値が格納される。
write
write(2): to file descriptor - Linux man page
以下の内容をレジスタに格納して呼び出す。
| レジスタ | 設定する内容 |
|---|---|
| RAX | 1 |
| RDI | 書き込み先のファイルディスクリプタ |
| RSI | 書き込むデータが格納されたメモリアドレス |
| RDX | 書き込む (最大の) バイト数 |
指定したファイルディスクリプタに対応するファイルにデータを書き込む。
通常、標準出力に対応するファイルディスクリプタは 1 である。
成功した場合は、RAX に書き込んだバイト数が格納される。
失敗した場合は、RAX に負の値が格納される。
exit
exit(2): terminate calling process - Linux man page
以下の内容をレジスタに格納して呼び出す。
| レジスタ | 設定する内容 |
|---|---|
| RAX | 60 |
| RDI | 終了ステータス |
プログラム (プロセス) の実行を終了する。
終了ステータスは、0 で正常終了を、0 以外で異常終了を表す。
今回使用した命令
add
add 加算先, 加算する値
「加算先」(レジスタ/メモリ) の値に「加算する値」(レジスタ/メモリ/即値) の値を加算し、和を「加算先」に格納する。
ただし、メモリ上の値に直接メモリ上の値を加算することはできない。
call
call 飛び先のラベル
関数を呼び出す。
すなわち、次の命令のアドレスをスタックにプッシュし、「飛び先のラベル」に制御を移す。
cdq
CWD/CDQ/CQO — Convert Word to Doubleword/Convert Doubleword to Quadword
cdq
EAX レジスタの値を、EDX:EAX に符号拡張する。
すなわち、EAX レジスタの最上位ビットを、EDX レジスタの全ビットにコピーする。
cmp
cmp 引かれる数, 引く数
「引かれる数」(レジスタ/メモリ) の値から「引く数」(レジスタ/メモリ/即値) の値を減算し、差は保存せずに捨てる。
主に条件分岐命令を実行する直前に実行し、数値を比較するために用いる。
メモリ上の値同士を直接減算することはできない。
dec
dec 対象
「対象」(レジスタ/メモリ) の値を 1 だけ小さくする。(デクリメントする)
idiv
idiv 割る数
(割る数が32ビットの場合) EDX:EAX を「割る数」で割り、商を EAX レジスタに、余りを EDX レジスタに格納する。
割られる数と割る数はともに符号付きの数として扱う。
「割る数」がゼロの場合、および商が格納先のレジスタに収まらない (オーバーフローを起こす) 場合、例外が発生する。
特に、割られる数を EAX レジスタのみに書き込み、EDX レジスタの設定を忘れてしまうと、エラーが発生する原因となる。
割られる数のサイズも割る数のサイズも32ビットの場合は、割られる数を EAX レジスタに書き込んだ後 cdq 命令を用いて符号拡張するとよいだろう。
imul
imul 格納先, 掛けられる数, 掛ける数
「掛けられる数」(レジスタ/メモリ) と「掛ける数」(即値) の積を計算し、結果を「格納先」(レジスタ) に格納する。
掛けられる数と掛ける数はともに符号付きの数として扱う。
imul 命令にはオペランドが 1 個の形式および 2 個の形式も存在するが、今回は使用していないためここでは省略する。
jg / jl / jne / jnz
Jcc — Jump if Condition Is Met
jg 飛び先のラベル
jl 飛び先のラベル
jne 飛び先のラベル
jnz 飛び先のラベル
条件分岐を行う。
sub 命令や cmp 命令で $a - b$ の減算を行った直後に実行した場合、以下の条件を満たすならば「飛び先のラベル」に制御を移し、満たさないならばそのまま次の命令の実行に移る。
| 命令 | 条件 |
|---|---|
jg |
$a > b$ |
jl |
$a < b$ |
jne / jnz
|
$a \neq b$ |
これらの命令は他の命令の実行結果により設定される「フラグ」に基づいて条件を満たすかを判定する。
たとえば、jne / jnz は計算結果がゼロであることを表すフラグが立っていないとき条件を満たすと判定し、立っているとき条件を満たさないと判定する。
フラグの詳細は、ここでは省略する。
jmp
jmp 飛び先のラベル
無条件で、「飛び先のラベル」に制御を移す。
lea
lea 格納先, [メモリアドレス]
「メモリアドレス」の値を「格納先」(レジスタ) に格納する。
(「メモリアドレス」が指すメモリの中身を格納するわけではない)
add 命令では加算する2個の値のうち1個は必ず書き込み先になるが、lea 命令では加算の結果を関係ないレジスタに書き込めるので、効率が良くなることがある。
leave
LEAVE — High Level Procedure Exit
leave
関数のスタックフレームを破棄する。
すなわち、以下の操作を行う。
- RBP レジスタの値を RSP レジスタ (スタックポインタ) に書き込む
- スタックから RBP レジスタに値をポップする
- スタックポインタが指すアドレスから RBP レジスタに値をロードする
- スタックポインタの値を 8 増やす
mov
mov 書き込み先, 書き込む値
「書き込む値」(レジスタ/メモリ/即値) を「書き込み先」(レジスタ/メモリ) に書き込む。
メモリ上の値を直接メモリに書き込むことはできない。
push
PUSH — Push Word, Doubleword, or Quadword Onto the Stack
push 値
「値」をスタックにプッシュする。
すなわち、以下の操作を行う。
- RSP レジスタ (スタックポインタ) の値を 8 減らす
- スタックポインタが指すアドレスに「値」を書き込む
ret
ret
関数から呼び出し元に戻る。
すなわち、以下の操作を行う。
- RSP レジスタ (スタックポインタ) が指す値から飛び先のアドレスをロードする
- スタックポインタの値を 8 増やす
- ロードした飛び先のアドレスに制御を移す
sub
sub 減算先, 減算する値
「減算先」(レジスタ/メモリ) の値から「減算する値」(レジスタ/メモリ/即値) の値を減算し、差を「減算先」に格納する。
ただし、メモリ上の値から直接メモリ上の値を減算することはできない。
syscall
syscall
対応した環境において、システムコールを実行する。
test
test 値1, 値2
「値1」(レジスタ/メモリ) と「値2」(レジスタ/即値) のビットAND演算を行い、結果は保存せずに捨てる。
ビットAND演算とは、入力の対応する位置のビットが両方1のとき結果のビットを1、そうでないとき結果のビットを0とする演算である。
今回は、値1と値2に同じレジスタを指定し、そのレジスタに格納されている値がゼロかどうかを判定するために用いた。
xor
xor デスティネーション, ソース
「デスティネーション」(レジスタ/メモリ) と「ソース」(レジスタ/メモリ/即値) のビットXOR演算を行い、結果を「デスティネーション」に格納する。
ただし、メモリ上の値同士を直接演算することはできない。
ビットXOR演算とは、入力の対応する位置のビットのうち1であるビットが奇数個のとき結果のビットを1、そうでないとき結果のビットを0とする演算である。
今回は、デスティネーションとソースに同じレジスタを指定し、そのレジスタにゼロを格納するために用いた。
提出コード
bits 64
section .note.GNU-stack
section .text
; int read_char(void)
; 1文字(バイト)読み込み、文字コードを返す
read_char:
xor eax, eax
xor edi, edi
lea rsi, [rsp - 8]
mov edx, 1
syscall
cmp eax, 1
jne read_char_error
mov al, [rsp - 8]
ret
read_char_error:
mov eax, -1
ret
; void print_char(int c)
; 1文字(バイト)出力する
print_char:
mov [rsp - 8], edi
mov eax, 1
mov edi, eax
lea rsi, [rsp - 8]
mov edx, eax
syscall
ret
; int read_int(void)
; 十進数の非負整数を1個読み込む
read_int:
push rbp
mov rbp, rsp
sub rsp, 16
mov [rbp - 8], ebx
xor ebx, ebx
read_int_loop:
call read_char
cmp eax, '0'
jl read_int_end
cmp eax, '9'
jg read_int_end
imul ebx, ebx, 10
sub eax, '0'
add ebx, eax
jmp read_int_loop
read_int_end:
mov eax, ebx
mov ebx, [rbp - 8]
leave
ret
; void print_int(int value)
; 非負整数を十進数で出力する
print_int:
mov eax, edi
mov rsi, rsp
mov ecx, 10
print_int_convert_loop:
cdq
idiv ecx
add dl, '0'
dec rsi
mov [rsi], dl
test eax, eax
jnz print_int_convert_loop
mov eax, 1
mov edi, eax
mov rdx, rsp
sub rdx, rsi
syscall
ret
global main
main:
push rbp
mov rbp, rsp
sub rsp, 16
; 3個の数値の和を出力する
call read_int
mov [rbp - 8], eax
call read_int
add [rbp - 8], eax
call read_int
add eax, [rbp - 8]
mov edi, eax
call print_int
; 区切りとなる空白を出力する
mov edi, ' '
call print_char
; 文字列を1行出力する
main_loop:
call read_char
mov [rbp - 16], al
mov edi, eax
call print_char
cmp byte [rbp - 16], `\n`
jne main_loop
; 終了する
mov eax, 60
xor edi, edi
syscall
提出 #54766528 - AtCoder Beginners Selection
提出コードの各関数の解説
read_char
read システムコールを用いて標準入力から1バイト読み込む。
システムコールを実行した後、結果が格納された EAX レジスタの値をチェックする。
値が 1 ならば、期待通り1バイト読み込めたということなので、読み込んだ値を EAX レジスタに格納して返す。
(EAX レジスタの値はこの時点で 1 であることがわかっているので、下位8ビットの AL に書き込むだけで EAX 全体の値が読み込んだ値になる)
そうでなければ、エラーまたはファイルの終端に達しているので、-1 を EAX レジスタに格納して返す。
print_char
write システムコールを用いて標準出力に1バイト出力する。
レジスタから直接出力することはできないので、出力する値を一旦メモリに格納し、それを出力している。
read_int
標準入力から数値を1個読み込む。
読み込む数値は十進数であることを仮定し、半角の 0～9 以外の文字が来たら読み込みを終了する。
数字が来たら、これまでに読み込んだ結果の数値に10を掛け、新しい数字が表す数値を加算する。
文字の読み込みには read_char 関数を用いるので、数値は callee-save レジスタである EBX を用いて管理する。
print_int
数値を1個標準出力に出力する。
まず、割り算を用いて、出力する数値を文字列に変換する。
このとき、下位を表す数字から順に決まるので、決まった数字を後ろ向きにメモリに格納していく。
変換が完了したら、変換結果の文字列を write システムコールを用いて出力する。
出力する文字数は、変換結果を格納する位置を表すポインタの初期値と最終値の差を計算することで求められる。
main
まず、数値を3個読み込み、和を出力する。
このとき、読み込んだ数値の扱いは、以下のようにそれぞれ変えている。
- 読み込んだ数値をメモリに格納する
- 読み込んだ数値をメモリに格納された前回読み込んだ数値に加算する
- メモリに格納された前2回で読み込んだ数値の和を、レジスタ上の読み込んだ数値に加算する
次に、出力において数値と文字列を区切る空白を出力する。
そして、3行目の文字列を出力する。
読み込んだ文字を出力した後、それが改行文字であるかをチェックし、改行文字でなければ次の文字の読み込みと出力を行う。
最後に、exit システムコールを用いてプログラムの実行を終了する。