コグノスケ

volatileをnon-volatileで参照してはいけない

目次: GCC

過去の日記（2021年3月13日の日記参照）にプログラムがバグっていて未定義動作だ（つまりGCCのせいじゃない）とコメントいただいたので、C11規格を眺めていました。

C11 committee draft(N1570) 6.7.3 Type qualifiersの6に、volatileとnon-volatileを併用したときの未定義動作の記述がありました。

6.7.3 Type qualifiers

...

6
If an attempt is made to modify an object defined with a const-qualified type through use of 
an lvalue with non-const-qualified type, the behavior is undefined. If an attempt is made to 
refer to an object defined with a volatile-qualified type through use of an lvalue with 
non-volatile-qualified type, the behavior is undefined. 133)

133) This applies to those objects that behave as if they were defined with qualified types, 
even if they are never actually defined as objects in the program (such as an object at a 
memory-mapped input/output address).

（ざっくり訳）
const-qualified型で定義したオブジェクトをnon-const-qualified型の左辺値（lvalue）を使用して変更した場合、
動作は未定義です。volatile-qualified型で定義したオブジェクトを、non-volatile-qualified型の左辺値で参照した場合、
動作は未定義です。

133)
たとえプログラム内でオブジェクトとして定義されていなくても、これ（注: 上記の6のこと）は修飾された型で定義されたように
振る舞うオブジェクト（メモリマップされたI/Oアドレスにあるオブジェクトなど）に適用されます。

未定義動作ならmemmoveやmemcopyに何が起きても不思議ではないですね。C言語難しいわ……。

解像度の設定を保存する

目次: Linux

Raspberry Pi 3 Model B (以降RasPi 3B)のHDMI出力の解像度はFull HDがデフォルト設定です。今日日のディスプレイで困ることはほぼありませんが、古いアスペクト比4:3のディスプレイなど、Full HD以外の解像度で出力してほしいときが稀にあります。

RasPi 3Bに限りませんけど、X Window Systemはxrandrコマンドで解像度を手軽に変更できます。しかし解像度の設定は保存されず、セッションを終了したり再起動すると元のFull HD出力に戻ります。まあ、これはこれで誤った設定のまま固定されないというありがたい面もあるものの、普通は再起動後も解像度を維持してほしいです。

調べるとX Window Systemの設定ファイルを変更するか、autorandrコマンドで解像度を維持できるみたいです（autorandrのソースコード）。例として1024x768 60Hzの解像度で維持するやり方を挙げます。

$ apt-get install autorandr

$ xrandr -s 1024x768 --rate 60
$ autorandr --save (profile名)

設定は~/.config/autorandr/(profile名)/というディレクトリに保存されます。

autorandrとXDG autostart機能

起動時に解像度を変更している方法が気になったので調べると、XDG autostart（Desktop Application Autostart Specification）を使って実現していました。

Linuxのデスクトップ環境は実装ごとに自動起動の方法が違いますが、XDG autostartは多数のデスクトップ環境が対応している自動起動の仕組みのようです。私が使っている64bit版Raspberry Pi OSはデスクトップ環境としてLXDE (Lightweight X11 Desktop Environment)を採用していて、LXDEもXDG autostartに対応しています。

XDG autostartはデスクトップ表示の際に/etc/xdg/autostart/ディレクトリの下の設定を全部実行します。autorandrの設定は/etc/xdg/autostart/autorandr.desktopにありました。

[Desktop Entry]
Name=Autorandr
Comment=Automatically select a display configuration based on connected devices
Type=Application
Exec=/usr/bin/autorandr -c --default default
X-GNOME-Autostart-Phase=Initialization

実行されるコマンドラインのうちオプション-cはchangeの意味で、最初に見つけたprofileの解像度に変更します。オプション--defaultはdefaultという名のprofileを使うように変更する指令らしいのですが、効き目が良くわかりません。

もし複数のprofileが存在していた場合にどれが選ばれるのか気になるので、デバッグオプションを付けて実行してみましょう。

$ autorandr -c --default default --debug

fullhd (detected) (1st match) (current)
xga (detected) (2nd match)
| Differences between the two profiles:
| [Output HDMI-1] Option --mode (= `1920x1080') is `1024x768' in the new configuration
\-
Config already loaded

$ autorandr -l xga

$ autorandr -c --default default --debug

xga (detected) (1st match) (current)
fullhd (detected) (2nd match)
| Differences between the two profiles:
| [Output HDMI-1] Option --mode (= `1024x768') is `1920x1080' in the new configuration
\-
Config already loaded

こんな動作をしました。最後に利用もしくは保存したprofileが使われるみたいですね。

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から見たときで命令列の意味が大きく変わります。図示するとこんな感じです。

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

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

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

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

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の方が柔軟に配置できる理由です。

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

100万回のHello, World! - バイナリサイズを削って遊ぼう

目次: ベンチマーク

前回（2024年2月25日の日記参照）はループ、再帰なし、1000バイト以下で100万回のHello, World!を実施する問題に対し、アセンブラというかほぼバイナリ直書きのC言語で挑戦しました。その後、バイナリサイズを削って遊んでみたところgccのみで840バイト、stripありで520バイトとなり、バイナリでも1000バイト以下を達成しました。

今回はどこまでバイナリのサイズを切り詰められるか試してみたいと思います。ツール頼みだとこれ以上削れないと思うのでバイナリエディタで削っていきます。

バイナリの見直し

前回の私のバイナリ実装はかなり適当だったので猛者に叩きなおしてもらいました。変化点としては、

• レジスタに0x1を代入するとき、movではなくpushとpopを使う
• exitを呼ぶときwriteを呼ぶ処理を流用してmovを減らす
• アドレスが固定であることを期待して、幅を取ってたlea命令をmovに置き変える

といったところです。

const char _start[] __attribute__((section(".text"))) = {
        0xbb, 0x40, 0x42, 0x0f, 0x00, //ebx 1000000
        0x6a, 0x01, //push 0x1
        0x58, //pop rax
        0x89, 0xc7, //mov eax,edi
        0x6a, 0x0e, //push 0xe
        0x5a, //pop rdx
        0xbe, 0x1c, 0x01, 0x40, 0x00, //mov 0x4011c, esi
        0x0f, 0x05, //syscall
        0xff, 0xcb, //dec ebx
        0x75, 0xed, //jne -> push 0x1
        0x6a, 0x3c, //push 0x3c
        0xeb, 0xeb, //jmp -> pop rax
        'H', 'e', 'l', 'l', 'o', ',', ' ',
        'W', 'o', 'r', 'l', 'd', '!', '\n',
};

この改良の時点で520→512バイト（8バイト減）に改善します。素晴らしい〜。

$ gcc -static -nostdlib -Wl,-Ttext=0x400100 -Wl,--build-id=none -fno-ident a.c
/tmp/cczsMtLk.s: Assembler messages:
/tmp/cczsMtLk.s:4: Warning: ignoring changed section attributes for .text

$ ls -la a.out
-rwxr-xr-x 1 katsuhiro suzuki 832  2月 25 13:47 a.out

$ strip -s a.out
$ ls -la a.out
-rwxr-xr-x 1 katsuhiro suzuki 512  2月 25 13:47 a.out  ★8バイト改善

$ objdump -DrS a.out
(略)
0000000000400100 <.text>:
  400100:       bb 40 42 0f 00          mov    $0xf4240,%ebx
  400105:       6a 01                   push   $0x1
  400107:       58                      pop    %rax
  400108:       89 c7                   mov    %eax,%edi
  40010a:       6a 0e                   push   $0xe
  40010c:       5a                      pop    %rdx
  40010d:       be 1c 01 40 00          mov    $0x40011c,%esi
  400112:       0f 05                   syscall
  400114:       ff cb                   dec    %ebx
  400116:       75 ed                   jne    0x400105
  400118:       6a 3c                   push   $0x3c
  40011a:       eb eb                   jmp    0x400107

★ここから下はHello, World!の文字列なので命令列としては無意味

  40011c:       48                      rex.W
  40011d:       65 6c                   gs insb (%dx),%es:(%rdi)
  40011f:       6c                      insb   (%dx),%es:(%rdi)
  400120:       6f                      outsl  %ds:(%rsi),(%dx)
  400121:       2c 20                   sub    $0x20,%al
  400123:       57                      push   %rdi
  400124:       6f                      outsl  %ds:(%rsi),(%dx)
  400125:       72 6c                   jb     0x400193
  400127:       64 21 0a                and    %ecx,%fs:(%rdx)


$ ./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

動作確認もできました。バイナリはこんな感じです。

$ hexdump -C remove_prg_section_org.out
00000000  7f 45 4c 46 02 01 01 00  00 00 00 00 00 00 00 00  |.ELF............|
00000010  02 00 3e 00 01 00 00 00  00 01 40 00 00 00 00 00  |..>.......@.....|
00000020  40 00 00 00 00 00 00 00  40 01 00 00 00 00 00 00  |@.......@.......|
00000030  00 00 00 00 40 00 38 00  03 00 40 00 03 00 02 00  |....@.8...@.....|
00000040  01 00 00 00 04 00 00 00  00 00 00 00 00 00 00 00  |................|
00000050  00 00 40 00 00 00 00 00  00 f0 3f 00 00 00 00 00  |..@.......?.....|
00000060  e8 00 00 00 00 00 00 00  e8 00 00 00 00 00 00 00  |................|
00000070  00 10 00 00 00 00 00 00  01 00 00 00 05 00 00 00  |................|
00000080  00 01 00 00 00 00 00 00  00 01 40 00 00 00 00 00  |..........@.....|
00000090  00 01 40 00 00 00 00 00  2a 00 00 00 00 00 00 00  |..@.....*.......|
000000a0  2a 00 00 00 00 00 00 00  00 10 00 00 00 00 00 00  |*...............|
000000b0  51 e5 74 64 06 00 00 00  00 00 00 00 00 00 00 00  |Q.td............|
000000c0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
000000e0  10 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
000000f0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000100  bb 40 42 0f 00 6a 01 58  89 c7 6a 0e 5a be 1c 01  |.@B..j.X..j.Z...|
00000110  40 00 0f 05 ff cb 75 ed  6a 3c eb eb 48 65 6c 6c  |@.....u.j<..Hell|
00000120  6f 2c 20 57 6f 72 6c 64  21 0a 00 2e 73 68 73 74  |o, World!...shst|
00000130  72 74 61 62 00 2e 74 65  78 74 00 00 00 00 00 00  |rtab..text......|
00000140  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
00000180  0b 00 00 00 01 00 00 00  06 00 00 00 00 00 00 00  |................|
00000190  00 01 40 00 00 00 00 00  00 01 00 00 00 00 00 00  |..@.............|
000001a0  2a 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |*...............|
000001b0  20 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  | ...............|
000001c0  01 00 00 00 03 00 00 00  00 00 00 00 00 00 00 00  |................|
000001d0  00 00 00 00 00 00 00 00  2a 01 00 00 00 00 00 00  |........*.......|
000001e0  11 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
000001f0  01 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000200

サイズは小さいですが0データの羅列が目立ちます。削れそうな気がしてきませんか？

削れそうなもの - プログラムヘッダ、セクション（512→162バイト）

大物から削りましょう。プログラムヘッダがなぜか3つありますが2つ不要、セクションヘッダは実行には不要、セクションヘッダ削除に伴って.shstrtabも不要です。

プログラムヘッダ:
  タイプ        オフセット          仮想Addr           物理Addr
            ファイルサイズ        メモリサイズ         フラグ 整列
  LOAD           0x0000000000000000 0x0000000000400000 0x00000000003ff000  ★いらない
                 0x00000000000000e8 0x00000000000000e8  R      0x1000
  LOAD           0x0000000000000100 0x0000000000400100 0x0000000000400100
                 0x000000000000002a 0x000000000000002a  R E    0x1000
  GNU_STACK      0x0000000000000000 0x0000000000000000 0x0000000000000000  ★いらない
                 0x0000000000000000 0x0000000000000000  RW     0x10

削除データの位置は下記の図の通りです。

削除するデータ（プログラムヘッダ、セクションヘッダなど）の位置

単純に削除すると.textセクションの位置とヘッダに記載されているアドレスがズレて動かなくなりますから、

• ELFヘッダ: e_entry, e_phoff, e_phnum
• プログラムヘッダ: p_offset, p_vaddr, p_paddr, p_filesz, p_memsz

上記の値を調整します。調整後のバイナリが下記です。

$ ls -la remove_prg_section.out
-rwxr-xr-x 1 katsuhiro suzuki 162  2月 25 14:05 remove_prg_section.out

$ hexdump -C remove_prg_section.out
00000000  7f 45 4c 46 02 01 01 00  00 00 00 00 00 00 00 00  |.ELF............| ★ELFヘッダ
00000010  02 00 3e 00 01 00 00 00  78 00 40 00 00 00 00 00  |..>.....x.@.....|
00000020  40 00 00 00 00 00 00 00  40 01 00 00 00 00 00 00  |@.......@.......|
00000030  00 00 00 00 40 00 38 00  01 00 40 00 03 00 02 00  |....@.8...@.....|
00000040  01 00 00 00 05 00 00 00  60 00 00 00 00 00 00 00  |........`.......| ★プログラムヘッダ
00000050  60 00 40 00 00 00 00 00  60 00 40 00 00 00 00 00  |`.@.....`.@.....|
00000060  40 00 00 00 00 00 00 00  40 00 00 00 00 00 00 00  |@.......@.......|
00000070  00 10 00 00 00 00 00 00  bb 40 42 0f 00 6a 01 58  |.........@B..j.X| ★0x78〜: 実行する命令列
00000080  89 c7 6a 0e 5a be 94 00  40 00 0f 05 ff cb 75 ed  |..j.Z...@.....u.|
00000090  6a 3c eb eb 48 65 6c 6c  6f 2c 20 57 6f 72 6c 64  |j<..Hello, World|
000000a0  21 0a                                             |!.|
000000a2

0データの羅列が減ってだいぶスリム化しました。サイズは162バイトです。

削れそうなもの - ELFヘッダ（162→120バイト）

ELFヘッダには色々な値が並んでいますが、実行ファイルを実行（execveシステムコール）するときに全ての値をチェックしているわけではありません。これを逆手にとってELFヘッダに実行命令列やデータを詰め込むことができます。図で示した黄色い部分以外は好き勝手に変えて大丈夫です。

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

最初の空き地はe_identの後半（アドレス: 0x04〜0x0f、12バイト）とe_version（アドレス: 0x14〜0x17、4バイト）です。実行バイナリの先頭4命令、10バイト分、そのあとの2バイト分を入れます。各領域の終端2バイトはジャンプ命令に使います。そうしないと命令列ではないところまで実行してクラッシュするからからです。

★e_identに入れる分
  400100:       bb 40 42 0f 00          mov    $0xf4240,%ebx
  400105:       6a 01                   push   $0x1
  400107:       58                      pop    %rax
  400108:       89 c7                   mov    %eax,%edi

★e_versionに入れる分
  40010a:       6a 0e                   push   $0xe

次の空き地はe_shoff, e_flags, e_ehsize（アドレス: 0x28〜0x35、14バイト）です。ちょうど"Hello, World!\n"と同じ長さなので文字列を置きます。

最後の空き地はELFヘッダの終端、e_shentsize, e_shnum, e_shstrndx（アドレス: 0x3a〜0x3f、6バイト）です。ここは命令列を置くよりe_phnumの値とプログラムヘッダの先頭p_typeも値が0x01であることを利用して、プログラムヘッダを8バイト手前にずらした方が良いでしょう。命令列を置くとジャンプ命令分を除いて、4バイトしか改善できないからです。

ELFヘッダの終端とプログラムヘッダの先頭8バイトを重ねる

プログラムヘッダの方は空き地はほぼなく、ヘッダ終端のp_align（8バイト）だけ変更OKでした。ここにも命令列を置きましょう。

最後にアドレスを調整するとこんなバイナリです。120バイトになりました。当然、実行できて100万回のHello, World!を出力します。

$ hexdump -C overwrap_elfh.out
00000000  7f 45 4c 46 bb 40 42 0f  00 6a 01 58 89 c7 eb 04  |.ELF.@B..j.X....|
00000010  02 00 3e 00 6a 0e eb 50  04 00 40 00 00 00 00 00  |..>.j..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  60 00 00 00 00 00 00 00  60 00 40 00 00 00 00 00  |`.......`.@.....|
00000050  60 00 40 00 00 00 00 00  30 00 00 00 00 00 00 00  |`.@.....0.......|
00000060  30 00 00 00 00 00 00 00  5a be 28 00 40 00 0f 05  |0.......Z.(.@...|
00000070  ff cb 75 95 6a 3c eb 93                           |..u.j<..|
00000078


$ ./overwrap_elfh.out | head
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!

$ ./overwrap_elfh.out | wc
1000000 2000000 14000000

あくまでもこのバイナリは私が使っているLinux kernel 6.1系のチェックを掻い潜って実行できるだけ、です。gdbは実行ファイルとして認識してくれませんし、readelfも大量のエラーを出します。将来のLinuxカーネルでも実行できなくなる可能性があります。

$ gdb ./remove_elf.out
GNU gdb (Debian 13.1-3) 13.1
(略)
"(略)/./remove_elf.out": not in executable format: file format not recognized

(gdb)

$ readelf -a remove_elf.out
ELF ヘッダ:
  マジック:  7f 45 4c 46 bb 40 42 0f 00 6a 01 58 89 c7 eb 04
  クラス:                            <不明: bb>
  データ:                            <不明: 40>
  Version:                           66 <unknown>
  OS/ABI:                            AROS
  ABI バージョン:                    0
  型:                                EXEC (実行可能ファイル)
  マシン:                            Advanced Micro Devices X86-64
  バージョン:                        0x50eb0e6a
  エントリポイントアドレス:          0x400004
  プログラムヘッダ始点:            0 (バイト)
  セクションヘッダ始点:              56 (バイト)
  フラグ:                            0x0
  Size of this header:               25928 (bytes)
  Size of program headers:           27756 (bytes)
  Number of program headers:         11375
  Size of section headers:           22304 (bytes)
  Number of section headers:         29295
  Section header string table index: 25708
readelf: 警告: The e_shentsize field in the ELF header is larger than the size of an ELF section header
readelf: エラー: Reading 653395680 bytes extends past end of file for セクションヘッダ
readelf: エラー: セクションヘッダが利用できません!
readelf: エラー: Too many program headers - 0x2c6f - the file is not that big

このファイルには動的セクションがありません。
readelf: エラー: Too many program headers - 0x2c6f - the file is not that big

さらにLinuxの裏をかいて削減できるような気もしますけど……、キリがないのでこれくらいにしておきます。

余談

GDBはセクションヘッダを削除した時点でELFファイルとして認識しなくなります。ジャンプ先を間違ったとき、アドレスが間違っていてSEGVするときのデバッグができずしんどいです。

ELFヘッダを書き換えるとreadelfすら訳の分からない表示になるので、デバッグがさらに辛いですね……。

100万回のHello, World!

目次: ベンチマーク

Twitterで100万回のHello, World!問題を見かけ、面白そうだったのでやってみました。消えてしまった時のためにレギュレーションを書き写しておくと、

• 設問: ループや再帰なしで100万回Hello, World!するには？
• 条件: for, while, goto, 再帰, 1000バイト越え, 外部ファイルは使用禁止

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バイト以下」のレギュレーションを極めましょう。

• 設問: ループや再帰なしで100万回Hello, World!するには？
• 条件: for, while, goto, 再帰, 1000バイト越え（ソースコード、バイナリともに）, 外部ファイルは使用禁止

レギュレーションを上記のように強化しました。

1000バイト以下に収めよう（バイナリも） - まずはstrip

まずは先ほど動作確認したバイナリのサイズを確認します。

$ 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バイトほどしか減りません。

おっと……これは？もしかして意外と難しいのか？

1000バイト以下に収めよう（バイナリも） - 変な空白を消そう

バイナリのセクションヘッダを眺めていると、なぜか.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セクションと重なっているとのこと。

1000バイト以下に収めよう（バイナリも） - さようなら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を見たときはどうなるかと思いましたが、意外と何とかなるものです。

1000バイト以下に収めよう（バイナリも） - ダメ押しのstrip

既に目標は達成しましたが、さらに.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アセンブラが得意じゃないので、何か書いてやろうという気は起きませんけど……。

国立科学博物館の乗り物体験ツアー

昨年8月ころに国立科学博物館が資金難に陥りクラウドファンディングをしていました（地球の宝を守れ - 国立科学博物館500万点のコレクションを次世代へ（国立科学博物館2023/08/07公開） - クラウドファンディング READYFOR）。科博にはこれからも頑張ってほしいなと思い、微力ながら「【体験】【寄付控除あり】乗り物体験＜昔の電気自動車など＞」コースに寄付しました。

んで、今日は寄付の返礼品のツアーに行ってきました。

残念ながら建物外観も含め写真を撮ってはダメで、写真がありません。車に乗っているところは写真を撮って良かったのですが、公開してはいけませんとのことで、日記に使える写真はありません。

ツアーの内容 - 車

科博の筑波地域の簡単な歴史や説明、注意事項、ツアーの時間を説明したオリエンテーリングのあと、実験植物園の裏口から理工資料棟に向かいました。こんな入り口あったんだ……。資料棟に入る前には靴底を洗い、靴にカバーを付けてから入場します（資料保護のためです）。

車は6台ありました。

• Milburn 電気自動車
• マツダ RX-8
• マツダ コスモスポーツ
• マツダ R360クーペ
• スバル 360
• 謎の三輪自動車

Milburn電気自動車（理工電子資料館:Milburn 電気自動車 - 国立科学博物館）は、名前だけ聞くと電気自動車？EVの仲間？と思いますが、なんと100年前（1920年くらい）のアメリカの車です。

リンク先の写真を見てもらうとわかりますが、形がほぼ「馬車」です。御者台のない馬車というのかな。当時はガソリンエンジンが圧倒的シェアを取る前で、蒸気、電気、ガソリンなど様々な動力で走る車がいたそうです。面白い時代です。

マツダの各車、スバル 360は名前は知ってましたが乗ったのは初めてです。スバル 360は屋根が低すぎます。マツダ R360クーペは車内の狭さが尋常じゃないです。後部座席なんかほぼ壁です。4人乗りと名乗るには無茶が過ぎないか……？？

ツアーの内容 - おまけ

車に乗ったり撮ったりするのが一巡したところでおまけツアーが始まりました。今日のツアー担当の方は3人いらっしゃって、車、天文、物理が専門の方々でした。たぶん2回目のツアーは担当の方が違うはずで、ツアーの内容も変わると思いますので参考程度。

最初は望遠鏡のツアーでした。

ちょうど車と同じフロアに天体望遠鏡が置いてあったため、望遠鏡の説明をしていただきました。今はデジタル撮像素子を使いますが、昔は写真乾板を使って撮影していたため数十分レベルの長時間露光が必要でした。単に数十分露光すると星が動いてしまって正しく撮影できないので、望遠鏡には望遠鏡の撮影部分を星の動きに追尾させる機構があります。

当時はモーターなどが精度良いものはなかったそうで、錘と調速機構（＝遠心ガバナー）を使って一定速度で望遠鏡を回すという仕組みだそうです。望遠鏡は何台か所蔵されており上野の日本館の屋上で稼働していたニコンの60cm（だったかな？）反射式望遠鏡も置いてありました。反射式望遠鏡はどれもでかいですねえ……。

望遠鏡の次はコンピュータ系のツアーでした。

地球シミュレータが置いてありました。コンピュータはカッコいい系のデザインにされることが多いですが、地球シミュレータのデザインはかわいいですね。愛嬌があって良いと思います。京コンピュータもあったみたいですが、カバーが掛かったままで良く見えませんでした。

あと日立 HITAC5020もありました。前面パネルを開けて配線を見せてもらいましたが、辿ることすら困難なグチャグチャ配線でゾッとしました。良く配線したものだ、メンテも地獄だったのではなかろうか……。気合と根性の日本って感じがします。