コグノスケ


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

link もっと前
2024年3月12日 >>> 2024年2月28日
link もっと後

2024年2月28日

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

  • and: axレジスタ相当の部分(eaxレジスタの下位16ビット)を0クリア
  • cwtl: axレジスタをeaxレジスタに符号拡張

もしwriteシステムコールがエラーを返してeaxレジスタが負の値になっていたとしても、and命令がaxレジスタ相当の下位16ビットを0クリアし、cwtlで符号拡張するので必ずeaxレジスタは0x3cになる仕組みです。

この手のコードゴルフではエラー処理まで考えないことが多いですが、きれいに解決されています。ちなみに私はcwtl命令を初めて知りました。こんな命令あるんだ……。

編集者:すずき(2024/02/27 09:09)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link もっと前
2024年3月12日 >>> 2024年2月28日
link もっと後

管理用メニュー

link 記事を新規作成

<2024>
<<<03>>>
-----12
3456789
10111213141516
17181920212223
24252627282930
31------

最近のコメント5件

  • link 24年1月24日
    すずきさん (02/19 18:37)
    「簡単にできる方法はPowerShellの...」
  • link 24年1月24日
    KKKさん (02/19 02:30)
    「追伸です。\nネットで調べたらマイクロソ...」
  • link 24年1月24日
    KKKさん (02/19 02:25)
    「私もエラーで困ってます\n手動での回復パ...」
  • link 24年1月24日
    すずきさん (02/13 11:48)
    「ありがとうございます。\n私のPCはもう...」
  • link 24年1月24日
    えはらさん (02/12 15:00)
    「Powershellのスクリプトは以下の...」

最近の記事3件

  • link 24年2月28日
    すずき (02/27 09:09)
    「[100万回のHello, World! - バイナリサイズを削って遊ぼう、究極編その2] 目次: ベンチマーク前回(2024...」
  • link 23年4月10日
    すずき (02/27 02:26)
    「[Linux - まとめリンク] 目次: Linuxカーネル、ドライバ関連。Linuxのstruct pageって何?Linu...」
  • link 20年6月22日
    すずき (02/27 02:26)
    「[LinuxデバイスツリーのYAMLドキュメントチェッカー] 目次: Linux最近、というほどでもないのですが、Linux ...」
link もっとみる

こんてんつ

open/close wiki
open/close Linux JM
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 2019年
open/close 2020年
open/close 2021年
open/close 2022年
open/close 2023年
open/close 2024年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDFファイル RSS 1.0

最終更新: 02/27 09:09