コグノスケ

未来から過去へ表示

過去から未来へ表示(*)

もっと前

2024年2月28日 >>> 2024年2月28日

もっと後

2024年2月28日

permalink

編集する

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

目次: ベンチマーク

前回（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）の方です。

983cb068: mov: esiレジスタに"Hello, World\n"のアドレスを入れる
983cb06d: push: rcxレジスタを保存
983cb060: syscall: writeシステムコールに相当
983cb062: pop: syscallによってrcxレジスタが壊れるのでrcxを復帰
983cb063: loop: rcxレジスタが0になるまでループ

ループ100万回が終了してrcxレジスタが0になるとloop命令の次のアドレス983cb065に進みます。eaxレジスタに0x3cを入れてsyscall（exitシステムコールに相当する）するので、プログラムが終了します。

命令重ね合わせの妙

この命令列の凄いところはand命令とmov命令の重ね合わせです。アドレス0x983cb065から見たときと、アドレス0x983cb068から見たときで命令列の意味が大きく変わります。図示するとこんな感じです。

アドレス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バイトにきっちり収まっています。

ELF実行ファイル全体、動作確認

$ 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命令です、簡単に解説します。