目次: ベンチマーク
Twitterで100万回のHello, World!問題を見かけ、面白そうだったのでやってみました。消えてしまった時のためにレギュレーションを書き写しておくと、
Cだとマクロを入れ子にする、setjmp/longjmpやsignalでgotoの代わりにする、辺りが設問意図のようです。C++だとクラスAのコンストラクタでHello, World!を書いておいて、A hoge[100 * 10000]のように配列宣言する方法があるみたいです。なるほどスマート。スクリプト言語だと大抵は繰り返し処理の構文があるので、あまり難しくないみたいです。最近の言語にとっては手ごたえのない問題かもしれません。
ツイートの引用をざっと見た感じだとアセンブラでやっている人がいなかったので、Cのふりしたアセンブラ(というかほぼバイナリ直書き)でチャレンジしました。
const char _start[] __attribute__((section(".text"))) = {
0xbb, 0x40, 0x42, 0x0f, 0x00, //ebx 1000000
0x66, 0xb8, 0x01, 0x00, //ax
0x89, 0xc7, //edi
0x66, 0xba, 0x0e, 0x00, //dx
0x48, 0x8d, 0x35, 0x0c, 0x00, 0x00, 0x00, //esi
0x0f, 0x05, //syscall
0xff, 0xcb, //dec ebx
0x75, 0xe9, //jne
0x66, 0xb8, 0x3c, 0x00, //ax
0x0f, 0x05, // syscall
'H', 'e', 'l', 'l', 'o', ',', ' ',
'W', 'o', 'r', 'l', 'd', '!', '\n', '\0',
};
これだけです。ソースコードのサイズは433バイトで、コメントなどは削っていませんが余裕で1000バイト以下に収まります。何が書いてあるのかわからんと思うので逆アセンブルした結果も載せます。
0000000000401000 <_start>: 401000: bb 40 42 0f 00 mov $0xf4240,%ebx ★0xf4240 = 100万 401005: 66 b8 01 00 mov $0x1,%ax 401009: 89 c7 mov %eax,%edi 40100b: 66 ba 0e 00 mov $0xe,%dx 40100f: 48 8d 35 0c 00 00 00 lea 0xc(%rip),%rsi # 401022 <_start+0x22> 401016: 0f 05 syscall ★write(1, "Hello, World!\n", 14)に相当する 401018: ff cb dec %ebx 40101a: 75 e9 jne 401005 <_start+0x5> ★goto 2行目 40101c: 66 b8 3c 00 mov $0x3c,%ax 401020: 0f 05 syscall ★exit()に相当、libcを使っていないのでretするとSEGVする ★ここから下はHello, World!の文字列なので命令列としては無意味 401022: 48 rex.W 401023: 65 6c gs insb (%dx),%es:(%rdi) 401025: 6c insb (%dx),%es:(%rdi) 401026: 6f outsl %ds:(%rsi),(%dx) 401027: 2c 20 sub $0x20,%al 401029: 57 push %rdi 40102a: 6f outsl %ds:(%rsi),(%dx) 40102b: 72 6c jb 401099 <_start+0x99> 40102d: 64 21 0a and %ecx,%fs:(%rdx)
次に動作確認しましょう。
$ gcc -static -nostdlib a.c /tmp/ccdifyE1.s: Assembler messages: /tmp/ccdifyE1.s:4: Warning: ignoring changed section attributes for .text $ ./a.out | head Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! Hello, World! $ ./a.out | wc 1000000 2000000 14000000
Hello, World!が繰り返し出ていること、100万行出ていること、異常事態(SEGVなど)が発生しないことを見ています。これで良さそうですね。
アセンブラでやる人がいないのは、jmp命令がgotoと同等なので当たり前にクリアできて何も面白くないからだと思います。なのでもう少しこだわって「1000バイト以下」のレギュレーションを極めましょう。
レギュレーションを上記のように強化しました。
まずは先ほど動作確認したバイナリのサイズを確認します。
$ gcc -static -nostdlib a.c /tmp/ccdifyE1.s: Assembler messages: /tmp/ccdifyE1.s:4: Warning: ignoring changed section attributes for .text $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 4864 2月 25 03:23 a.out $ strip -s a.out $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 4544 2月 25 03:25 a.out $ strip -s -R .note.gnu.build-id -R .comment a.out strip: a.out: warning: empty loadable segment detected at vaddr=0x400000, is this intentional? $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 4360 2月 25 03:28 a.out
実質の命令列+文字列で50バイトくらいなのにバイナリは4KBを超えています。なんだこれは。stripしても300バイトほどしか減りません。readelfで確認すると.note.gnu.build-idと.commentというセクションがstripされずに残っていたため、排除しましたが500バイトほどしか減りません。
おっと……これは?もしかして意外と難しいのか?
バイナリのセクションヘッダを眺めていると、なぜか.textが0x1000から配置されています。
セクションヘッダ: [番] 名前 タイプ アドレス オフセット サイズ EntSize フラグ Link 情報 整列 [ 0] NULL 0000000000000000 00000000 0000000000000000 0000000000000000 0 0 0 [ 1] .text PROGBITS 0000000000401000 00001000 ★この時点でバイナリサイズ4KBが確定 0000000000000031 0000000000000000 AX 0 0 32 [ 2] .shstrtab STRTAB 0000000000000000 00001031 0000000000000011 0000000000000000 0 0 1
デフォルトリンカースクリプト(gccに-Wl,-verboseオプションを渡すと表示できます)を調べると、特に何も指定しない場合.textは0x400000+SIZEOF_HEADERSというアドレスに配置されることがわかります。
SECTIONS
{
PROVIDE (__executable_start = SEGMENT_START("text-segment", 0x400000));
. = SEGMENT_START("text-segment", 0x400000) + SIZEOF_HEADERS;
SIZEOF_HEADERSを決定する仕組みがいまいち分からないですが、恐らくSIZEOF_HEADERS = 0x1000でしょう。0x400000のような大きなアドレスの場合はプログラムヘッダのロードアドレスで調整するので、0x400000の0データがバイナリに書かれることはありません。しかし一定サイズ以下(今回のような0x1000など)の場合はバイナリに0データを埋め込んで開始位置を調整するようです。
この仕組みを逆手にとって.textの開始アドレス下位をもっと手前のアドレスにずらすことで、ELFヘッダやプログラムヘッダを避けながら開始位置調整用の無駄な0データを削除できるはずです。
$ gcc -static -nostdlib -Wl,-Ttext=0x400160 a.c $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 1120 2月 25 03:43 a.out セクションヘッダ: [番] 名前 タイプ アドレス オフセット サイズ EntSize フラグ Link 情報 整列 [ 0] NULL 0000000000000000 00000000 0000000000000000 0000000000000000 0 0 0 [ 1] .text PROGBITS 0000000000400160 00000160 ★0x1000から0x160に詰められた 0000000000000031 0000000000000000 AX 0 0 32 [ 2] .note.gnu.bu[...] NOTE 00000000004000e8 000000e8 0000000000000024 0000000000000000 A 0 0 4 [ 3] .comment PROGBITS 0000000000000000 00000191 000000000000001f 0000000000000001 MS 0 0 1 [ 4] .symtab SYMTAB 0000000000000000 000001b0 0000000000000090 0000000000000018 5 2 8 [ 5] .strtab STRTAB 0000000000000000 00000240 000000000000001d 0000000000000000 0 0 1 [ 6] .shstrtab STRTAB 0000000000000000 0000025d 000000000000003d 0000000000000000 0 0 1
開始アドレス下位を0x1000から0x160までずらすとバイナリ中の0データ領域が減り、一気に1120バイトまで減りました。劇的な効果です。変更により動作不良を起こしていないかも忘れずにチェックします(動作チェックのログは省略)。
もう一息削れば1000バイトはすぐそこですが、、、
$ gcc -static -nostdlib -Wl,-Ttext=0x400140 a.c /tmp/cc5LlyKi.s: Assembler messages: /tmp/cc5LlyKi.s:4: Warning: ignoring changed section attributes for .text /usr/bin/ld: section .text LMA [0000000000400140,0000000000400170] overlaps section .note.gnu.build-id LMA [0000000000400120,0000000000400143] collect2: error: ld returned 1 exit status
残念ながら.textの開始アドレス下位を0x140にすると「別のセクションと重なってるぞ!」と怒られてリンクエラーになります。.note.gnu.build-idセクションと重なっているとのこと。
とりあえず.note.gnu.build-idセクションは無くても実行できるので、-Wl,--build-id=noneで消し去ります。.note.gnu.build-idセクションがいなくなった分、.textセクションをさらに前の0x100まで詰められます。
$ gcc -static -nostdlib -Wl,-Ttext=0x400100 -Wl,--build-id=none a.c /tmp/cctmYikq.s: Assembler messages: /tmp/cctmYikq.s:4: Warning: ignoring changed section attributes for .text $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 936 2月 25 03:52 a.out
やりました。stripに頼らずとも1000バイトを下回ることができました。最初の4KBを見たときはどうなるかと思いましたが、意外と何とかなるものです。
既に目標は達成しましたが、さらに.commentセクションの排除と、stripするとどこまで減るか試しましょう。まずは.commentセクションの排除です。
$ gcc -static -nostdlib -Wl,-Ttext=0x400100 -Wl,--build-id=none -fno-ident a.c $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 840 2月 25 04:55 a.out
次はstripです。.symtabセクションと.strtabセクションが消えます。
$ strip -s ./a.out $ ls -la a.out -rwxr-xr-x 1 katsuhiro suzuki 520 2月 25 04:56 a.out
サイズは520バイトまで減らせました。1000バイトの約半分です。もっと複雑な処理でも詰め込めるでしょう。私はx86_64アセンブラが得意じゃないので、何か書いてやろうという気は起きませんけど……。
< | 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 | - | - |
合計:
本日: