はじめに
Assembly x64 で「AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～」を解きました。
構文の説明
まず、nasmのプログラムは基本的に3つのセクション(.bss、.data、.text)に分けられます(が、私が解いた10問では、.bssセクションを1度も使いませんでした。)。
.dataセクションは、プログラムに必要な初期化済みデータの記述場所です。
.textセクションは、実行可能なコードの置き場所です。
さて、.textセクションには、主に4種類のものがあります。
一つ目は、global。これは、指定したシンボルを他のファイルからアクセスできるようにするためのものです。
二つ目は、extern。これは、他のファイルのシンボルへアクセスできるようにするためのものです。
三つ目は、ラベルです。その位置のアドレスを、分かりやすい名前で定義し、参照できるようにするためのものです。ラベルの後ろには、:を付けるのがよいとされています。
四つ目は、命令です。push,mov,subなど、いろいろな種類があります。
第0問 PracticeA - Welcome to AtCoder
section .data
fmti db "%d%d%d%s", 10, 0;
fmto db "%d %s", 10, 0;
section .text
global main
extern printf, scanf
main:
push rbp
mov rbp, rsp
sub rsp, 128
lea rdi, [rel fmti]
lea rsi, [rsp]
lea rdx, [rsp + 4]
lea rcx, [rsp + 8]
lea r8, [rsp + 12]
call scanf wrt ..plt
mov rax, [rsp]
mov rbx, [rsp + 4]
mov rcx, [rsp + 8]
lea rdx, [rsp + 12]
add rax, rbx
add rax, rcx
lea rdi, [rel fmto]
mov rsi, rax
call printf wrt ..plt
xor eax, eax
mov rsp, rbp
pop rbp
ret
入出力はcallを使用してc言語の機能を呼び出しました。...ええ、命令が何種類もありますね。今から説明します。ついてこい。
callは、関数やサブルーチンを呼び出す命令です。これで呼ぶ関数の引数は、第1,2,3,4,5引数がそれぞれrdi,rsi,rdx,rcx,r8です。
addは、add destination, sourceとした時、destinationにdestination + sourceを入れます。(ちなみに、他の命令も計算結果を入れるレジスタはdestination、つまり左側のことが多いです。)
leaは、メモリの指定した位置のアドレスを計算し、結果をレジスタに格納します。それに対し、movは、レジスタからレジスタに、あるいはメモリからレジスタに、データをコピーします。
なお、main内の上3行と下4行はfunction prologue/epilogue というもので、おまじないだと思っておけばいいと思います。(必要なメモリ量に応じて128の部分は変わるので注意)
第1問 ABC 086 A - Product
section .data
fmt db "%d%d",0;
odd db "Odd", 10, 0;
even db "Even", 10, 0;
section .text
global main
extern puts, scanf
main:
push rbp
mov rbp, rsp
sub rsp, 128
lea rdi, [rel fmt]
lea rsi, [rsp]
lea rdx, [rsp + 4]
call scanf WRT ..plt
mov rax,[rsp]
mov rbx,[rsp + 4]
mul rbx
test rax, 1
jz res1
lea rdi, [rel odd]
jmp ep
res1 :
lea rdi, [rel even]
ep :
call puts WRT ..plt
mov eax, 0
mov rsp,rbp
pop rbp
ret
偶奇判定は1とBit単位andを(testコマンドで)行って0と比較すると楽です。
まず、mul、test命令についても説明します。
mul命令は、mul operandとして使用し、rax × operandの値を計算し、下位64bitをrax、上位64bitをrdxに入れます。桁あふれを防ぐため、このような仕様になっています。
test命令はtest operand1, operand2として使用し、operand1とoperand2のBit単位andを計算し、その結果を捨てます(「直前の計算結果」が変わり、条件分岐に影響が出ます)。
さらに、条件分岐に必要な、jz,jmpについて説明します。
jmpは、プログラムの実行を指定した位置にジャンプさせます。
jzは、直前の計算結果(このスクリプトでは、test rax, 1の結果)が0なら、ジャンプします。
第2問 ABC081A - Placing Marbles
section .data
fmt db "%d",10, 0;
section .text
global main
extern printf, scanf
main:
push rbp
lea rdi, [rel fmt]
lea rsi, [rsp]
call scanf WRT ..plt
lea rdi, [rel fmt]
mov rax, [rsp]
mov rbx, 9
div rbx
mov rsi, rdx
call printf WRT ..plt
mov eax, 0
pop rbp
ret
文字列処理はしんどいので整数として受けとって9で割った余りを返します。
divという新しい命令が出ていますが、mulの除算版(rax/rdxの商をraxに、余りをrdxに入れる)と思えばいいでしょう。
第3問 ABC081B - Shift only
section .data
fmt db "%d", 10, 0;
section .text
global main
extern printf, scanf
main:
push rbp
lea rdi, [rel fmt]
lea rsi, [rsp]
call scanf wrt ..plt
xor rbx, rbx,
mov r13, [rsp]
loop:
lea rdi, [rel fmt]
lea rsi, [rsp]
call scanf wrt ..plt
mov rax, [rsp]
or rbx, rax
dec r13
jnz loop
lea rdi, [rel fmt]
tzcnt rsi, rbx
call printf wrt ..plt
xor eax, eax
pop rbp
ret
とうとうループ処理が出てきました。が、jnzで飛ぶ先がその命令より前になってるだけです。
dec(対象レジスタを1減らす)命令、or(Bit単位orを計算する)命令、tzcnt(下位Bitから数えて何Bit0が連続するか計算する。)命令などを用いています。
tzcnt命令のこの問題以外での活用法って何ですかね？
なお、callでの処理は一部のレジスタを変更することがあるので、保存しときたいデータはrbxやr13などに突っ込みましょう。
第4問 ABC087B - Coins
section .data
fmt4 db "%d%d%d%d", 10, 0;
a dd 500;
b dd 100;
c dd 50;
fmt1 db "%d", 10, 0;
section .text
global main
extern printf, scanf
main:
push rbp
mov rbp, rsp
sub rsp, 128
lea rdi, [rel fmt4]
lea rsi, [rsp]
lea rdx, [rsp + 8]
lea rcx, [rsp + 16]
lea r8 , [rsp + 24]
call scanf wrt ..plt
mov rax, [rsp]
mov rbx, [rsp + 8]
mov rcx, [rsp + 16]
mov r12, [rsp + 24]
mov edx, [rel a] ; maisuu -> kingaku
mul edx
mov r8, rax
mov rax, rbx
mov edx, [rel b]
mul edx
mov rbx, rax
mov rax, rcx
mov edx, [rel c]
mul edx
mov rcx, rax
lea rdi, [rel fmt1]
xor rsi, rsi ; Final answer
.L1:
mov r9, rbx
.L2:
mov r10, rcx
.L3:
mov r11, r8 ; sum of money
add r11, r9
add r11, r10
cmp r11, r12
jne .SK
inc rsi
.SK:
sub r10, 50
jnc .L3
sub r9, 100
jnc .L2
sub r8, 500
jnc .L1
lea rdi, [rel fmt1]
call printf WRT ..plt
xor eax, eax
mov rsp, rbp
pop rbp
ret
多重ループになりましたが、本質はあまり変わっていません。
レジスタのbit数を間違えると事故るので注意しましょう(n敗)
新しいjump命令が出てきました。jncは最後の演算で符号なし整数の桁溢れが発生したとき、jneでは2つの値が等しくないときにjumpします。
cmp命令は、第一オペランドと第二オペランドの値を比較し、それに応じて「直前の計算結果」が変化します。
第5問 ABC083B - Some Sums
section .data
fmt3 db "%d%d%d", 10, 0;
fmt1 db "%d", 10, 0;
section .text
global main
extern printf, scanf
main:
push rbp
mov rbp, rsp
sub rsp, 32
lea rdi, [rel fmt3]
lea rsi, [rsp]
lea rdx, [rsp + 8]
lea rcx, [rsp + 16]
call scanf wrt ..plt
mov r8, [rsp]
mov rbx, [rsp + 8]
mov rcx, [rsp + 16]
loop:
mov rax, r8
xor r9, r9 ; r9 = digit sum
mov r11, 10
dig:
xor rdx, rdx
div r11
add r9, rdx
cmp rax, 0
jne dig
cmp rbx, r9 ; check A <= r9 <= B
jg skip
cmp r9, rcx
jg skip
add r12, r8
skip:
dec r8
jnz loop
lea rdi, [rel fmt1]
mov rsi, r12
call printf WRT ..plt
xor eax, eax
mov rsp, rbp
pop rbp
ret
jgは直前の比較結果が左側 > 右側ならjumpです。なおdig:の直後にあるxor rdx, rdxがないとバグります。(何故?)
第6問 ABC088B - Card Game for Two
section .data
fmt db "%lld", 10, 0;
section .text
global main
extern printf, scanf
main:
push rbp
mov rbp, rsp
sub rsp, 128
lea rdi, [rel fmt]
lea rsi, [rsp + 104]
call scanf wrt ..plt
mov r13, [rsp + 104]
.input:
lea rdi, [rel fmt]
lea rsi, [rsp + 104]
call scanf wrt ..plt
mov rax, [rsp + 104]
lea rdi, [rsp]
add rdi, rax
xor byte[rdi], 1
dec r13
jnz .input
xor rax, rax
mov rbx, 100
.check:
lea rdi, [rsp]
add rdi, rbx
cmp byte[rdi], 0
jz .next
xor r13, 1
jz .b
add rax, rbx
jmp .next
.b:
sub rax, rbx
.next:
dec rbx
jnz .check
lea rdi, [rel fmt]
mov rsi, rax
call printf wrt ..plt
xor eax, eax
mov rsp, rbp
pop rbp
ret
とうとうメモリ管理の必要性が出てきました。さすがにソートはしたくないので、「A点のカードが何枚あるか」を管理します。偶数枚あるカードは無視しても問題ないので無視すると楽です。
第7問 ABC085B - Kagami Mochi
section .data
fmt db "%lld", 10, 0;
section .text
global main
extern printf, scanf
main:
push rbp
mov rbp, rsp
sub rsp, 128
lea rdi, [rel fmt]
lea rsi, [rsp + 104]
call scanf wrt ..plt
mov r13, [rsp + 104]
.input:
lea rdi, [rel fmt]
lea rsi, [rsp + 104]
call scanf wrt ..plt
mov rax, [rsp + 104]
lea rdi, [rsp]
add rdi, rax
or byte[rdi], 1
dec r13
jnz .input
mov rbx, 100
.check:
lea rdi, [rsp]
add rdi, rbx
cmp byte[rdi], 1
jne .next
inc r13
.next:
dec rbx
jnz .check
lea rdi, [rel fmt]
mov rsi, r13
call printf wrt ..plt
xor eax, eax
mov rsp, rbp
pop rbp
ret
6問目が解ける人なら難なく解けると思います。
第8問 ABC085C - Otoshidama
section .data
fmti db "%lld%lld", 10, 0;
fmto db "%lld %lld %lld", 10, 0;
a dq 10000;
b dq 5000;
c dq 1000;
section .text
global main
extern printf, scanf
main:
push rbp
mov rbp, rsp
sub rsp, 128
lea rdi, [rel fmti]
lea rsi, [rsp]
lea rdx, [rsp + 8]
call scanf wrt ..plt
mov r12, [rsp] ; N
mov r13, [rsp + 8] ; Y
lea rdi, [rel fmto]
mov r8, r12 ; x
.loop1:
mov rax, [rel a]
mul r8
mov rbx, rax
mov r9, r12 ; y
sub r9, r8
.loop2:
mov rax, [rel b]
mul r9
mov rcx, rax
mov r10, r12 ; z
sub r10, r8
sub r10, r9
mov rax, [rel c]
mul r10
add rax, rbx
add rax, rcx
cmp rax, r13
jne .next
mov rsi, r8
mov rdx, r9
mov rcx, r10
call printf WRT ..plt
xor eax, eax
mov rsp, rbp
pop rbp
ret
.next:
dec r9
jns .loop2
dec r8
jns .loop1
mov rsi, -1
mov rdx, -1
mov rcx, -1
call printf WRT ..plt
xor eax, eax
mov rsp, rbp
pop rbp
ret
愚直に解くと$O(N^3)$となり、間に合いません。$z=N-x-y$として全探索を行えば、$O(N^2)$となり、充分高速です。なお、ループによる全探索の際、$y≦N-x$であることを用いると実装が楽です。
第9問 ABC049C - 白昼夢
section .data
fmt db "%s", 10, 0;
YES db "YES", 0;
NO db "NO", 0;
s1 db "dream", 0;
s2 db "dreamer", 0;
s3 db "erase", 0;
s4 db "eraser", 0;
section .text
global main
extern puts, scanf, strcmp
strcmp:
.loop:
movsx eax, BYTE[rdi]
movsx ecx, BYTE[rsi]
inc rdi
inc rsi
sub eax, ecx
jne .end
test BYTE[rsi], 255
jnz .loop
.end:
ret
main:
push rbp
mov rbp, rsp
sub rsp, 131072
lea rdi, [rel fmt]
lea rsi, [rsp]
call scanf wrt ..plt
lea r13, [rsp] ; Str.end()
lea rbx, [rsp] ; Str.begin()
.strlen:
inc r13
test BYTE[r13], 255
jnz .strlen
.check:
mov r12, r13
cmp rbx, r13
jl .match
lea rdi, [rel YES]
call puts wrt ..plt
xor eax, eax
mov rsp, rbp
pop rbp
ret
.match:
lea rdi, BYTE[r12 - 5]
lea r13, [rdi]
cmp rbx, rdi
jg .no
lea rsi, [rel s1]
call strcmp
test eax, eax
jz .check
lea rdi, BYTE[r12 - 5]
lea rsi, [rel s3]
call strcmp
test eax, eax
jz .check
lea rdi, BYTE[r12 - 6]
lea r13, [rdi]
cmp rbx, rdi
jg .no
lea rsi, [rel s4]
call strcmp
test eax, eax
jz .check
lea rdi, BYTE[r12 - 7]
lea r13, [rdi]
cmp rbx, rdi
jg .no
lea rsi, [rel s2]
call strcmp
test eax, eax
jz .check
.no:
lea rdi, [rel NO]
call puts wrt ..plt
xor eax, eax
mov rsp, rbp
pop rbp
ret
strcmpという文字列を比較するサブルーチン(注：これはC言語での仕様と若干異なる)を作っておきます。後は後ろから貪欲に。
第10問 ABC086C - Traveling
section .data
fmt1 db "%lld",0;
fmt3 db "%lld%lld%lld",0;
Yes db "Yes", 0;
No db "No", 0;
section .text
global main
extern puts, scanf
main:
push rbp
mov rbp, rsp
sub rsp, 32
lea rdi, [rel fmt1]
lea rsi, [rsp]
call scanf WRT ..plt
mov rbx, [rsp] ;N
xor r12, r12 ;t
xor r13, r13 ;x
xor r14, r14 ;y
.loop:
lea rdi, [rel fmt3]
lea rsi, [rsp]
lea rdx, [rsp + 8]
lea rcx, [rsp +16]
call scanf WRT ..plt
mov r8, [rsp]
mov r9, [rsp + 8]
mov r10,[rsp +16]
mov rax, r9
sub rax, r13
mov r13, r9
mov rdx, rax
sar rdx, 63
xor rax, rdx
sub rax, rdx
mov rcx, r10
sub rcx, r14
mov r14, r10
mov rdx, rcx
sar rdx, 63
xor rcx, rdx
sub rcx, rdx
add rax, rcx
mov rdx, r8
sub rdx, r12
mov r12, r8
; rax = (x+y)diff, rdx = tdiff
cmp rax, rdx
jg .out
xor rax, rdx
test rax, 1
jz .safe
.out:
lea rdi, [rel No]
call puts WRT ..plt
xor eax, eax
mov rsp,rbp
pop rbp
ret
.safe:
dec rbx
jnz .loop
lea rdi, [rel Yes]
call puts WRT ..plt
xor eax, eax
mov rsp,rbp
pop rbp
ret
メモリがO(1)で済むってうれしいですね
感想
こういう低水準言語は新鮮で、楽しかったです(printfやscanfをCから持ってこれなかったら、結構難しかったかも)