AtCoderでは2023年の言語アップデートでAMD64向けのアセンブリ言語（の中でもNASM）による提出ができるようになりました。
これで問題解いてみたいな～とは思っていたもののなかなか手が出ていませんでしたが、ABS程度ならいけるかと思い立って解いてみました。
ちなみに、先駆者がいるか提出一覧を調べてみたところ1名はいたようです。なので、初制覇というわけではないです。
以下で解法を書きたいわけですが、まあ高級言語ならやるだけで済んじゃうので、普通にメモ書いてもつまらないです。
どうせなら解いててハマったところとか書いていこうかなと思います。
NASMの文法とかアセンブリ言語の約束事など
一応述べておいた方が良さそうなので、最低限知ってなきゃいけないことだけ書きます。私は専門家ではないので、正しさは保証しません。
NASMについて
アセンブリ言語と一口に言っても、アーキごとに命令セットが違うのは当然として、アーキが同じでもアセンブラごとに文法が異なります。
有名どころでは、GAS記法とIntel記法というのを聞いたことがあるかもしれません。
AtCoderで使えるのは色々あるアセンブラのうち、NASMというアセンブラになります。
NASMの文法が知りたい場合は、公式のマニュアルを見るのが確実です。
コードの構造について
アセンブリ言語の場合は、コードの構造がほぼそのまま実行ファイルの構造と結びつくので、実行ファイル中の命令やデータの配置を知っておく必要があります。
実行形式によって配置や構造は異なるのかもしれませんが、私はELF64しか知らないですし、AtCoderの環境も多分そうなのでその前提でいきます。
AtCoderでコードを実行するにあたっては最低でも以下の4つの領域があるということを知っておく必要があります。
- テキスト領域
- 命令が格納される領域。.textというセクション名で定義。
- データ領域
- 何らかのデータで初期化された領域。.dataというセクション名で定義。
- BSS領域
- 0初期化されたデータが格納された領域。.bssというセクション名で定義。
- スタック領域
- いわゆるローカル変数の確保やレジスタの保存を行う領域。コード中では特にセクション名を付けなくてよい。
これらはリンカスクリプトでオブジェクトファイル中のどこにどの程度のサイズで配置するかを制御できますが、GCCでC言語のコードをコンパイルをするときにいちいちリンカスクリプトを作らなくていいように、いつもはリンカがよしなにやってくれます。
例えば、ldを使っている場合はld --verboseなどとすれば、デフォルトでどういうリンカスクリプトが適用されているか確認できます。
エントリポイントについて
ネットでコードの書き方について調べると、メインのコードの始まりのラベルがmainだったり_startだったりすると思います。
これはcrt0.oやcrt1.oのようなプログラムの起動処理を実行するルーチンがリンクされているかどうかで違います。（と、私は認識してます。違ったら教えてください）
AtCoderの環境ではリンクされますから、エントリポイントはそちら側にあり、私たちはmainから始める必要があります。
ABIについて
Application Binary Interfaceです。プログラム間のバイナリレベルでのインタフェースを定義しています。
Linux環境ではおそらくSystem V ABIというのが使われていると思います。
https://www.uclibc.org/docs/psABI-x86_64.pdf
私も細かいことは詳しく知りませんが、差し当たって知っていなければいけないのはレジスタの使い方でしょう。
上記のドキュメントで言えば、「Figure 3.4: Register Usage」がそれにあたります。
AMD64のプロセッサではGPRが16本ありますが、それぞれ引数渡し用、返り値用、一時用などの用途や、ルーチン呼び出し時のレジスタ保存の役割分担などが決まっています。
割とこれハマりがちだったので、頭に入れておいたほうが良いです。
命令セットについて
当たり前ですが、AMD64向けの命令しか使えません。
Intelからマニュアルが出ていますから、これを参照しましょう。具体的には、「Intel64 and IA-32 Architectures Software Developer's Manual Volume 2 (2A, 2B, 2C, & 2D) Instruction Set Reference, A-Z」です。
各問題の解法
ようやくですが、解法です。
ちなみに、最初はシステムコールとHW命令だけで突っ張るつもりだったのですが、ちょっと無理ゲーなので、入出力だけはライブラリ使います。
libcがリンクされているからだと思うのですが、extern printfでprintfが使えます。
PracticeA - Welcome to AtCoder
提出例：Submission #49418142 - AtCoder Beginners Selection
初手なので少し細かめで。
scanfとprintfを使うつもりなので、externでそれを宣言します。また、フォーマット用の文字列が必要ですが、これはデータ領域に格納します。
fmtpのうしろの10って何？って思われるかもしれませんが、Asciiコード表を見ると、10進数の10は改行コードであることがわかります。なので、C言語で言えば"%d %s\n"とおなじです。最後に0を付けているのは、NULL終端のためです。
入力のsは文字列なので、配列が必要です。これはどの領域にとってもいいのですが、解いたときはBSS領域に格納したようです。
データ領域のときはdbが8bitサイズ、BSS領域のときはresbが8bitサイズとなります。なので、s resb 1024は、C言語で言えばstatic uint8_t s[1024];とかと同じです。
.textセクションに入って、まずはrbpをスタックに保存します。
その後、スタックポインタを引いてスタック領域にローカル変数保存用の領域を確保します。32という数字に特に意味はないです。12で十分ですが、まあ多少多めにとっても問題はないです。
次はscanfのための引数をレジスタに渡します。
ABIによれば、引数をレジスタ経由で渡す場合、1つ目から順にrdi, rsi, rdx, rcx, r8, r9を使う必要があります。なので、fmtのアドレスをrdiに渡して、それ以外は確保したスタック領域から順に4Byte区切りでアドレスをレジスタに渡していきます。
fmtのアドレスを取得するときに[rel fmt]としなくてはならないのは、このコードがPIE(位置独立実行形式)としてリンクされるからのようです。この場合、rip相対で参照する必要があり、rip相対参照は[rel fmt]とすることでできます。
callの前にやっているのは、raxのクリアです。xor eax, eaxはよくあるレジスタのクリア方法で、eaxをクリアすればraxまでクリアされます。
なんでクリアするのかですが、ABIでraxは可変長引数を渡すときにベクトルレジスタをいくつ使うかの情報を渡すのに使われることになっているからです。試してみるとなんかクリアしなくても動くのですが、scanfもprintfも可変長引数を要求する関数なので、一応クリアしておきます。
ついにscanfを呼びます。共有ライブラリのルーチンは、PLT (Procedure Linkage Table)を経由して呼び出されるため、scanfもcall scanf wrt ..pltとしなくてはなりません。これはprintfも同様です。(NASMのリファレンスの「10.2.5 Calling Procedures Outside the Library」とかを参照するとよいです)
入力ができたら、まずはa + b + cを作ります。スタックの若いほうから4Byteおきに数値を格納したので、順にesiに格納して足し込んでいきます。
a + b + cが作れたら、rdxにsのアドレスを格納します。
ここまででprintfの第2，3引数は格納できているので、あとは第1引数としてfmtpのアドレスを格納して、raxをクリアしたら、printfを呼び出します。
最後はスタックポインタとベースポインタをもとに戻して、retで戻ります。
スタックポインタに足す数字がめちゃくちゃでトラブるというのはありがちなので気をつけましょう。(だから32固定にしているというのもある)
また、ここでraxをクリアしないと、終了ステータスが0以外になってしまい、REで死にます。ちゃんとクリアしてからretしましょう。
ABC086A - Product
提出例：Submission #49519868 - AtCoder Beginners Selection
掛け算と偶奇判定と条件分岐が出来ればよいです。
掛け算にはmulが使えます。これは符号なし整数の掛け算を行う命令で、符号付き整数の場合にはimulという命令があります。
オペランドは1つだけ、レジスタかメモリをとれます。もう一方の項はどうしたって話ですが、Instruction Set Referenceを読めばわかる通り、64bitの計算ならraxが暗黙的に指定されます。
計算結果は、64bitの場合、下位ビットがrax、上位ビットがrdxに格納されます。なので、rdxが破壊されます。rdxに意味のある値が入っている場合には、事前に退避させる必要があります。
偶奇判定ですが、これは結果が入っているraxのLSBが1かどうかを確認すればよいでしょう。C言語でいえば、(rax & 1) == 1をチェックできればよいです。
これにはtestが使えます。これはレジスタ、メモリ、即値を2つ引数に取り（ただし、即値は1つまで）、ANDをとった結果に応じてフラグレジスタを変化させます。
test rax 1であれば、raxの最下位ビットが0である場合にZFが1にセットされ、そうでないとき0にセットされます。
条件分岐には、je, jne, jg, jl...（その他多数）を使うことができます。詳細はInstruction Set Reference参照ですが、今回使ったjeは、ZFが立っているときに指定したラベルへ飛びます。
なので、test rax 1のあとje evとすることで、raxと1のANDが0の場合はev("Even"を出力するほう)へ飛び、そうでないときはそのまま"Odd"を出力できます。
"Odd"を出力した後は、"Even"を出力する処理の後ろに設置したepilog:ラベルに無条件ジャンプします。
結果として偶奇判定と条件分岐を実現することができます。
ABC081A - Placing Marbles
提出例：Submission #49520205 - AtCoder Beginners Selection
3Byte入力して、すべて足し込んでから144 (Asciiコードで'0'は10進数の48)を引けばよいです。
silはrsiの最下位1Byteです。メモリから1ByteとってくるときはBYTEを指定すればよいです（小文字でもOK）。2ByteならWORD、4ByteならDWORD、8ByteならQWORDです。
ABC081B - Shift only
提出例：Submission #49520373 - AtCoder Beginners Selection
Trailing Zerosを数えて、Minをとって出力すればよいです。加えて、地味に面倒くさいループ処理です。
Trailing Zerosを数えるのには、tzcntという命令があります。2つのオペランドが必要で、1つ目はレジスタ、2つ目はレジスタかメモリです。
2つ目のオペランドのTrailing Zerosを数えて、結果は1つ目のオペランドに指定したレジスタに格納されます。
計算対象が0だと未定義動作になりますが、制約ではそのような入力はないので問題ないです。
Minを取るための命令はたぶんないと思います。なので、頑張って条件分岐で求めます。
提出例ではcmpという命令を使っています。testとの違いは、cmpは1つ目のオペランドから2つ目のオペランドを引き算した結果でフラグレジスタを設定するところです。
jgはcmpの結果、1つ目のオペランドが大きかった場合に指定されたラベルにジャンプします。(厳密には、OFとSFが等しいかつZFが立っていないときにジャンプするが、subの結果がこうなる場合は1オペランド目が大きい)
ループのパターンは決まっていて、まずカウンタ用のレジスタのクリア、その直後にラベルを付け、ループ末尾でincやaddを使ってカウンタを更新、最後に継続条件を判定して、満たす場合はループの頭のラベルにジャンプします。
今回はC言語でいうところのfor (int i = 0; i < n; i++)がしたいので、これをcmpとjgを使って実装します。
ABC087B - Coins
提出例：Submission #49520715 - AtCoder Beginners Selection
ただただループ処理が面倒くさいだけなので、頑張って実装します。
内側ループでは割り算が必要ですが、整数除算にはdivが使えます。
これもmul同様に1つだけオペランドを取りますが、面倒なことに即値は指定できないので、レジスタに50を格納してから計算します。
暗黙に指定されるオペランドはrax, rdxの2つで、rdxが上位、raxが下位です。結果は、商がrax、剰余がrdxに格納されます。
実はハマりどころですが、連続でdivするときにはrdxをクリアしないと、前の計算結果の剰余がそのまま次の計算の暗黙のオペランドの上位ビットに含まれてしまい、計算結果が大きく狂います。
今回はXが50の倍数であることによって、rdxが必ず0になるためクリアは不要ですが、この後の問題でこれによってドハマりしました。気をつけましょう。
ABC083B - Some Sums
提出例：Submission #49386518 - AtCoder Beginners Selection
桁和を求めるなら普通ループ書くと思いますが、アセンブリ言語でループ書くのは面倒ですし、高々5ケタしかないので、ループ展開しちゃいます。
divを使えば商と剰余が手に入るので、10で割りながら剰余を足し込みます。
先ほど述べたように、rdxをちゃんとクリアしないと、結果がめちゃくちゃになります。
ABC088B - Card Game for Two
提出例：Submission #49398501 - AtCoder Beginners Selection
ソートして交互に足し引きするだけの問題ですが、アセンブリ言語で書くのはあまりに苦痛な問題です。
libcが使えるならたぶんqsortが使えると思いますが、ポリシー的にびみょいので、ここは気合で実装します。
Nの制約が小さいので、バブルソートや選択ソートも余裕で通りそうです。ここでは実装が簡単そうな選択ソートをすることにしました。
実装は気合で二重ループと条件分岐を書くだけです。
ちょっとした工夫としては、選択された値をメモリに書き戻す必要はないので、レジスタに値を格納した後はそれをスワップし続けます。
スワップ用の命令としてはxchgというものがあり、レジスタとメモリの値のスワップができます。暗にlockが指定されるためパフォーマンスが悪いらしいですが、まあ今回の用途では誤差です。
もう一つ面倒なのが、配列のアクセスの際、ループカウンタのレジスタを使って、例えば[rel s + rax]のように参照する箇所を指定することができない点です（即値なら可能）。
どうすればいいかですが、これはいったんレジスタにlea rbp [rel s]などとしてアドレスをロードし、このレジスタに値のサイズを加算しながら参照すればよいです。実は何かよいやり方があるのかなあと思っていますが、今のところ見つかっていないので、これでしのぎました。
ABC085B - Kagami Mochi
提出例：Submission #49398793 - AtCoder Beginners Selection
ソートが本質みたいな問題なので、前の問題のコードをそのまま使いまわします。
あとは隣接項の大小関係で場合分けして答えを加算するだけです。
ABC085C - Otoshidama
提出例：Submission #49398990 - AtCoder Beginners Selection
気合で二重ループ書くだけの問題です。ここまで述べたハマりどころ意外には特にハマりどころがありません。
ABC049C - 白昼夢
提出例：Submission #49417731 - AtCoder Beginners Selection
実質ボス問です。
高級言語なら配列作ってDPやるだけだろ？って話ですが、文字列操作のライブラリは使いませんから、あらゆる操作が苦痛な問題です。strlenもstrcmpも使えないので、ループや何らかのハックで頑張るしかありません。
まずは文字列のサイズがわからないとどうしようもないので、頑張ってループを書いて確かめます。
NULL終端されているはずですから、文字の0判定を行い、終端に辿り着いたら抜けます。
0判定には、同じレジスタを2つのオペランドに指定してtestするという方法が使えます。
その次は本題のDPです。
カウンタを回しながら、まずそこまでをdream, dreamer, erase, eraserで構成できるのか確認したのち、そこからこの4つで文字列を伸ばせるか確認します。
伸ばせるかの確認が面倒なところですが、いずれの文字も8文字よりは小さいことを考えると、64bit整数の一致判定で何とかなります。
まずはレジスタにQWORDとしてメモリをロードし、文字列長でマスクをかけ、文字列が構成するビットパターンにマッチするか確認すればよいです。
andやcmpは即値をとれるのですが、Instruction Set Referenceを見ればわかるとおり、64bitの即値は取れません。なので、movでレジスタにいったん即値をロードし、これをオペランドにする必要があります。
ABC086C - Traveling
提出例：Submission #49521145 - AtCoder Beginners Selection
最終問題です。ここまで来てしまうと、あんまりハマりどころもないので、説明すべき点もないです。
入力を取りながら、前の座標とのマンハッタン距離を求めて時間を引き、マイナス判定と偶奇判定を行い、どちらかの判定に失敗した時点でbad:に飛べばよいです。
マイナス判定については、いずれも直前のsubでマイナスになったらSFが立ちますから、jsやjnsで目的のラベルに飛ばせます。
あとがき
デバッグがとにかく辛かったです。なんせprintfするだけでも、引数の準備が微妙に面倒くさかったり、最後にしか出力しない前提で書いているコードだと自分で保存しないといけないレジスタを何の考えもなく使っていてprintfの内部でそいつが破壊されて結果が意味不明になったりということがあります。
手元で環境用意してデバッガでステップ実行するのが手早い説はありますが、そこまでする根性がなかったです。
ただ、ABIやら実行形式やらメモリ上のデータの配置やら、高級言語ばかり書いているとわからないがちなところを抑えないと書けないだけあって、とても勉強になりました。
今後もたまにはアセンブリ言語触っていきたいですね。
