目次: ベンチマーク
前回(2024年2月27日の日記参照)はループ、再帰なし、1000バイト以下で100万回のHello, World!を実施する問題に対し、バイナリサイズを極限まで削るためのアイデアをご紹介しました。
今回はバイナリ実装の説明を紹介したいと思います。
今回使用する100万回のHello, World!を呼ぶ命令列と処理の流れを説明します。エントリアドレスは0x983cb004なので、一番上の行から実行開始します。
983cb004: b9 40 42 0f 00 mov $0xf4240,%ecx 983cb009: 6a 01 push $0x1 983cb00b: 58 pop %rax 983cb00c: 6a 0e push $0xe 983cb00e: 5a pop %rdx 983cb00f: a9 02 00 3e 00 test $0x3e0002,%eax 983cb014: 89 c7 mov %eax,%edi 983cb016: eb 50 jmp 983cb068 <_start+0x68> 983cb028: "Hello, World!\n" 983cb060: 0f 05 syscall 983cb062: 59 pop %rcx 983cb063: e2 a4 loop 983cb009 <_start+0x9> ----- (★1)loop命令の条件に一致せず、983cb065に進んだ時に見える命令列 983cb065: 25 00 00 be 28 and $0x28be0000,%eax 983cb06a: b0 3c mov $0x3c,%al 983cb06c: 98 cwtl 983cb06d: 51 push %rcx 983cb06e: eb f0 jmp 983cb060 <_start+0x60> ----- (★2)983cb068に飛んだ時に見える命令列 983cb068: be 28 b0 3c 98 mov $0x983cb028,%esi 983cb06d: 51 push %rcx 983cb06e: eb f0 jmp 983cb060 <_start+0x60>
まず0x983cb004〜0x983cb016まで実行して、ジャンプ命令で0x983cb068に飛びます。上の図でいう(★2)の方です。
ループ100万回が終了してrcxレジスタが0になるとloop命令の次のアドレス983cb065に進みます。eaxレジスタに0x3cを入れてsyscall(exitシステムコールに相当する)するので、プログラムが終了します。
この命令列の凄いところはand命令とmov命令の重ね合わせです。アドレス0x983cb065から見たときと、アドレス0x983cb068から見たときで命令列の意味が大きく変わります。図示するとこんな感じです。
and mov cwtl push jmp | | | | | <------------> <---> <> <> <---> : アドレス983cb065から見たときの解釈 25 00 00 be 28 b0 3c 98 51 eb f0 <------------> <> <---> : アドレス983cb068から見たときの解釈 | | | mov push jmp
この工夫によってmovとjmpの合計7バイトを重ね合わせることができていて、結果112バイトにきっちり収まっています。
$ hexdump -C 112byte.out 00000000 7f 45 4c 46 b9 40 42 0f 00 6a 01 58 6a 0e 5a a9 |.ELF.@B..j.Xj.Z.| 00000010 02 00 3e 00 89 c7 eb 50 04 b0 3c 98 00 00 00 00 |..>....P..<.....| 00000020 38 00 00 00 00 00 00 00 48 65 6c 6c 6f 2c 20 57 |8.......Hello, W| 00000030 6f 72 6c 64 21 0a 38 00 01 00 00 00 05 00 00 00 |orld!.8.........| 00000040 00 00 00 00 00 00 00 00 00 b0 3c 98 00 00 00 00 |..........<.....| 00000050 00 b0 3c 98 00 00 00 00 0f 05 59 e2 a4 25 00 00 |..<.......Y..%..| 00000060 0f 05 59 e2 a4 25 00 00 be 28 b0 3c 98 51 eb f0 |..Y..%...(.<.Q..| 00000070 $ ./112byte.out | head Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! $ ./112byte.out | wc 1000000 2000000 14000000 $ ./112byte.out > /dev/null
最終的なバイナリはこんな感じです。動作もOKです。
ループ終了後exitシステムコールを呼ぶとき、アドレス983cb06aのmov命令にて0x3c(exitシステムコールを表す番号)をalレジスタに入れてsyscall命令を実行します。もしこのmov命令のみだと、writeシステムコールがエラーを返してeaxレジスタが負の値になっていると問題が起きます。alレジスタを0x3cに書き換えても上位ビットが0ではないため、eaxレジスタとして見たとき値が0x3cになりません。よってexitシステムコールが呼ばれず終了しません。
今回の112バイト版は前後のand命令とcwtl命令によってこの問題を解決しています。loop命令を通過した後の命令列を再掲します。
983cb065: 25 00 00 be 28 and $0x28be0000,%eax 983cb06a: b0 3c mov $0x3c,%al 983cb06c: 98 cwtl 983cb06d: 51 push %rcx 983cb06e: eb f0 jmp 983cb060 <_start+0x60>
ポイントは先頭の2命令です、簡単に解説します。
もしwriteシステムコールがエラーを返してeaxレジスタが負の値になっていたとしても、and命令がaxレジスタ相当の下位16ビットを0クリアし、cwtlで符号拡張するので必ずeaxレジスタは0x3cになる仕組みです。
この手のコードゴルフではエラー処理まで考えないことが多いですが、きれいに解決されています。ちなみに私はcwtl命令を初めて知りました。こんな命令あるんだ……。
< | 2024 | > | ||||
<< | < | 02 | > | >> | ||
日 | 月 | 火 | 水 | 木 | 金 | 土 |
- | - | - | - | 1 | 2 | 3 |
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | - | - |
合計:
本日: