コグノスケ

100万回のHello, World! - バイナリサイズを削って遊ぼう、究極編その1

目次: ベンチマーク

前回（2024年2月26日の日記参照）はループ、再帰なし、1000バイト以下で100万回のHello, World!を実施する問題に対して、バイナリサイズをどこまで削れるかに挑戦しました。結果120バイトのバイナリとなりました。

今回は削減の限界値と思われる値まで達成したので、その内容を紹介したいと思います。空き地の開拓は私ですが、アセンブラの短縮に関しては私ではなくhdkさん（hdkのページ）がほぼやってくれました。結構難しいので、わかるように説明できているか怪しいです……。

バイナリの最小サイズ（削減の限界）は112バイト

正常に動作するELF形式の実行ファイルには、ELFヘッダ（64バイト）とプログラムヘッダ（56バイト）が必要です。120バイト必要に見えますが、2つのヘッダは破綻しない範囲で重ねて良いです。今のところ112バイトが最小サイズだと思われます。

ELFヘッダのなかで正しい値を維持しなければならない部分

前回紹介した通り、ELFヘッダには適当な値を入れるとエラーになって動かなくなる部分があります。プログラムヘッダも同様に制約があり、先頭のp_typeとp_flags（01 00 00 00 05 00 00 00）は変更できません。そのあとに続くp_offsetも上位バイトは変更できず、p_vaddr = p_paddr、p_filesz = p_memszでなければなりません。結構厳しいです。

これらの条件を満たせるのはe_phnum, e_shentsize, e_shnum, e_shstrndx（計8バイト）とp_type, p_flags（計8バイト）を重ねることだけだと思われます。単純な合計サイズから8バイト減った64 + 56 - 8 = 112バイトが最小サイズのはず。もし間違っていたら教えてください。私が喜びます。

削減のアイデア - プログラムヘッダの空き地p_fileszとp_memsz

前回は見落としましたが、プログラムヘッダ中に命令列を置ける空き地が1つ残っていました。p_fileszとp_memsz（どちらも8バイト）です。あまりに大きな値にするとエラーで動かなくなりますが、6バイトくらいなら何を書いても大丈夫そうです。

注意点としてはp_fileszとp_memszを同じ値にしないとエラーになることです。両方書き換えますが実行に使うのはどちらか片方だけとなるでしょう。

削減のアイデア - 命令の途中にジャンプ

RISC系のCPUを使う人からすると信じがたい動きですが、x86 CPUは命令のアラインメントがなく「命令の途中」にジャンプしても良いです。例を示しましょう。

0000: be 28 01 b0 3c: mov $0x3cb00128, %esi

この命令の4バイト目（アドレス3）にジャンプすると

0003: b0 3c: mov $0x3c, %al

という命令に見えるので、継続して実行可能。

もし命令の一部が有効な命令として解釈可能ならそのまま実行を続けられます。x86 CPUの無茶苦茶な仕様には驚きですが、今回はこの動きが役立ちます。

削減のアイデア - 4バイトジャンプの代わりにtest命令

ELFヘッダのe_identの後半（アドレス: 0x04〜0x0f、12バイト）とe_version（アドレス: 0x14〜0x17、4バイト）の間には、e_type, e_machineという書き換えてはいけない4バイトの情報があります。単純に実装するとe_identの最後に4バイトジャンプ（eb 04）を置いて飛ばせば良いです。

test命令を4バイトスキップの代わりにする例

しかし上記のようにアドレス0x000fをtest命令（a9）に置き換えますと、後続の4バイトと合わせて1命令（a9 02 00 3e 00: test $0x3e0002, %eax）とみなせます。test命令はフラグレジスタ以外には影響を及ぼさないので、a9 02 00 3e 00は実行されるものの何も効力を発揮しません。

ジャンプ命令2バイトからtest命令の先頭1バイトのみで済みますので、空き地が1バイト増加します。test命令に変更する代償はフラグレジスタの内容が破壊されることです。例えば条件分岐命令の直前などでtest命令を使うと、分岐の結果が変わる可能性があります。

削減のアイデア - デクリメント＋条件分岐の代わりにpush, pop, loop命令

100万回のループを行うときは、ebxレジスタなどcallee-saveレジスタ（関数呼び出しで値が壊れないレジスタ）に1,000,000を入れ、デクリメントし（ff cb: dec %ebx）、条件不一致ならループの先頭にジャンプ（75 xx: jne +-7bit幅ショートジャンプ）する、2命令、合計4バイトで実現するのが普通だと思います。

実はx86_64にはloop命令といってdec %ecxとjne xxを実行する命令があります。サイズは2バイト（e2 xx: loop +-7bit幅ショートループ）です。ただしecxレジスタはcallee-savedではないため、関数呼び出しやsyscallで内容が壊れます。必ずecxレジスタの保存（51: push %rcx）と復帰（59: pop %ecx）を伴うため合計サイズは4バイトで変わりません。

それなら置き換える意味がないのでは？と思うかもしれませんが、同じ4バイトでも2バイト命令2つ（dec, jne）と1バイト命令2つ＋2バイト命令1つ(push, pop, loop）を比べると、後者の方が部品が多くてより柔軟に配置できるのです。

もう1つ良い点はdec命令とjne命令は近くに配置しないといけない制約（フラグを壊す算術命令やtest命令を間に入れると動かなくなるから）がありますが、push/pop命令はloop命令から多少離れても問題ありません。これもloopの方が柔軟に配置できる理由です。

続きはまた明日書きます。