コグノスケ

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

JavaとM5Stamp C3とBluetooth LE - ビルド準備編

目次: Arduino

M5Stamp C3をBluetooth LEデバイスにして、Linux PCもしくはRaspberry PiなどのLinux SBCとお話する取り組みの続編です。

今回はbluez-dbusを使ったJavaアプリのビルド準備をします。目的は依存するライブラリが全て含まれた（つまり単独で実行可能な）JARファイルを生成することです。ビルドシステムは昔はAntでしたが今はMavenがメジャーでしょうか？Mavenは依存関係の解消が楽で良いですね。

アプリ開発そのものはテキストエディタでもIntelliJ IDEAやEclipseなどのIDEでも、お好きなツールを使っていただければ良いかと思います。

基本的な設定

ビルドを試すだけならJavaのソースコードは不要で、プロジェクトのディレクトリにpom.xmlを作成するだけで試せます。今回作成するアプリはbluez-dbusに依存するので依存設定を記述するdependenciesタグはこんな感じにします。

    <dependencyManagement>
        <dependencies>
            <dependency>
                <groupId>com.github.hypfvieh</groupId>
                <artifactId>bluez-dbus</artifactId>
                <version>0.1.4</version>
            </dependency>
        </dependencies>
    </dependencyManagement>

    <dependencies>
        <dependency>
            <groupId>com.github.hypfvieh</groupId>
            <artifactId>bluez-dbus</artifactId>
        </dependency>
    </dependencies>

Mavenでは記述を2つに分けるのが推奨のようです、例えば依存関係の記述ならdependenciesタグとdependencyManagementタグに分けます。特に大きなプロジェクトだと複数のpom.xmlに渡ってビルドの設定を記述することが増え、各pom.xmlのdependenciesタグの中でバージョンなどを何度も書くと間違うし更新漏れが発生します。トップレベルにあるpom.xmlのdependencyManagementタグの中でバージョンなどを定義し、子レベルにあるpom.xmlではdependenciesタグから参照する使い方が良いのだとか。

今回はpom.xmlが1ファイルしかないので分けなくても問題ありません。分けない方の例も挙げましょう。プラグイン設定も同様にpluginsタグとpluginMnagementタグの2つに分けますが、ここではあえて1つのpluginsタグに全て書きます。

        <plugins>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-assembly-plugin</artifactId>
                <executions>
                    <execution>
                        <goals>
                            <goal>single</goal>
                        </goals>
                        <phase>package</phase>
                        <configuration>
                            <descriptorRefs>
                                <descriptorRef>jar-with-dependencies</descriptorRef>
                            </descriptorRefs>
                            <archive>
                                <manifest>
                                    <mainClass>main.java.Main</mainClass>
                                </manifest>
                            </archive>
                        </configuration>
                    </execution>
                </executions>
            </plugin>
        </plugins>

上記に出てくるmaven-assembly-pluginは依存ライブラリを全て含んだJARファイルを生成できるプラグインです。jar-with-dependenciesという定義済みのdescriptorRefを指定すると良いそうです。階層構造といい変な名前といい何かの呪文のようです、とても覚えられません。

テストの設定などを除けば、基本的には依存ライブラリ設定とプラグイン設定で最低限の役目は果たすはずです。ですがビルドしてみたらめっちゃハマりました。Mavenつらい……。

ハマりポイントその1 - maven-assembly-pluginのバージョン

バージョンを特に指定しない場合、現状maven-assembly-pluginは2.2-beta-5というバージョンになります。が、このバージョンは動作がおかしいようでmvn packageがビルドエラーになります。

[INFO] ------------------------------------------------------------------------
[INFO] BUILD FAILURE
[INFO] ------------------------------------------------------------------------
[INFO] Total time:  1.211 s
[INFO] Finished at: 2024-02-19T19:40:23+09:00
[INFO] ------------------------------------------------------------------------
[ERROR] Failed to execute goal org.apache.maven.plugins:maven-assembly-plugin:2.2-beta-5:single (default) on project bluetooth-test: Failed to create assembly: Error creating assembly archive jar-with-dependencies: A zip file cannot include itself -> [Help 1]
[ERROR]
[ERROR] To see the full stack trace of the errors, re-run Maven with the -e switch.
[ERROR] Re-run Maven using the -X switch to enable full debug logging.
[ERROR]
[ERROR] For more information about the errors and possible solutions, please read the following articles:
[ERROR] [Help 1] http://cwiki.apache.org/confluence/display/MAVEN/MojoExecutionException

エラーの原因が全くわかりません。Mavenのエラーメッセージは全般的に何が言いたいのかわからず、pom.xmlのデバッグは困難を極めます。色々調べたり試した限りでは、プラグインのバージョンを2.1に固定するとこの現象は発生しなくなることがわかりました。何だそりゃ？どういうことだ……？？

            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-assembly-plugin</artifactId>
                <version>2.1</version>    ★★バージョン2.1に固定した★★
                <executions>
                    <execution>
                        <goals>
                            <goal>single</goal>
                        </goals>
                        <phase>package</phase>
                        <configuration>
                            <descriptorRefs>
                                <descriptorRef>jar-with-dependencies</descriptorRef>
                            </descriptorRefs>
                            <archive>
                                <manifest>
                                    <mainClass>main.java.Main</mainClass>
                                </manifest>
                            </archive>
                        </configuration>
                    </execution>
                </executions>
            </plugin>

本当に意味がわからないです。Mavenつらすぎる。

ハマりポイントその2 - 2回目のビルドとmaven-clean-plugin

次のハマりポイントはmvn packageを2回連続で実行すると下記のエラーが出て失敗することです。mvn-assembly-pluginどうなってんだお前……。

[INFO] --- maven-jar-plugin:2.4:jar (default-jar) @ bluetooth-test ---
[INFO] Building jar: /home/katsuhiro/ble-test/target/bluetooth-test-0.1.jar
[INFO] ------------------------------------------------------------------------
[INFO] BUILD FAILURE
[INFO] ------------------------------------------------------------------------
[INFO] Total time:  1.332 s
[INFO] Finished at: 2024-02-20T02:41:20+09:00
[INFO] ------------------------------------------------------------------------
[ERROR] Failed to execute goal org.apache.maven.plugins:maven-jar-plugin:2.4:jar (default-jar) on project bluetooth-test: Error assembling JAR: A zip file cannot include itself -> [Help 1]
[ERROR]
[ERROR] To see the full stack trace of the errors, re-run Maven with the -e switch.
[ERROR] Re-run Maven using the -X switch to enable full debug logging.
[ERROR]
[ERROR] For more information about the errors and possible solutions, please read the following articles:
[ERROR] [Help 1] http://cwiki.apache.org/confluence/display/MAVEN/MojoExecutionException

なぜかmaven-jar-pluginがエラーを起こします。メッセージの意味がさっぱりわかりません。なぜかmaven-clean-pluginを追加して最初にcleanを実行すると現象が発生しなくなります。ビルド時のゴミが残っているのか？ビルドが毎回全てやり直しになるので遅いですけど、ビルドエラーよりはマシでしょう……。

            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-clean-plugin</artifactId>
                <executions>
                    <execution>
                        <id>auto-clean</id>
                        <phase>initialize</phase>
                        <goals>
                            <goal>clean</goal>
                        </goals>
                    </execution>
                </executions>
            </plugin>

やっとmvn packageが動作するようになりました。思い出していただきたいのは、Mavenの設定ファイルpom.xmlたった1つしか作っておらず、Java言語を1文字足りとも書いていないのにこの有様だということです。Mavenは著名ツールの割にエラーメッセージが意味不明すぎてつらいです。Maven使っている人はpom.xmlをどうやってデバッグしているんでしょうね？

ソースコード

ソースコードという程でもないですが、こちらからどうぞ。

•  上記の説明で使ったpom.xml（Mavenに渡すときはpom.xmlにリネームして使ってください）

JavaとM5Stamp C3とBluetooth LE - 導入編

目次: Arduino

以前の日記（2024年2月12日の日記参照）でM5Stamp C3をBluetooth LEデバイスにして、スマホのアプリとお話ができるようになりました。とくれば、次はM5Stamp C3とLinux PCもしくはRaspberry PiなどのLinux SBCとお話したくなります。

LinuxでBluetoothを扱う場合は、BlueZという実装を使います。BlueZはDBusというマシン内のイベントを配信するシステムに依存しており、軽く調べた感じではC言語からDBusを制御するのは結構大変そうです。Pythonだと簡単らしいですがGUIも実装したいんですよね。ちょっと悩みましたが久しぶりにJavaで書くことにしました。

素晴らしいことにJavaからBlueZを制御する場合、bluez-dbusという（bluez-dbusのリポジトリ）求めていた用途そのもののライブラリがあります。DBus制御は同作者さんのdbus-java（dbus-javaのリポジトリ）を使うようです。Unixソケットを使うライブラリにも依存しているようですね。

ちなみにbluez-dbusはJavaで実装されているものの、Javaの外の世界にOSやシステム依存（DBus、Unixソケットの存在に依存）があるため、Linuxでしか動作しないことに注意が必要です。用途次第ではWindowsやMacOSで動作しないと困るのでしょうけど、私が今回想定している用途ではLinux専用で問題ありません。ありがたくbluez-dbusを使わせていただきます。

bluez-dbusのドキュメント

ドキュメント（bluez-dbusのJavaDoc）を自分でビルドするのは大変なので、javadoc.ioを参照（Overview (bluez-dbus 0.1.4 API)）すると楽です。

ちなみにjavadoc.ioって何？と思ったらMavenに収容されているリポジトリのJavaDocを生成して公開してくれているサイトなのだそうです。ありがとうMavenプロジェクト、とても便利です。

LinuxでBluetooth LEデバイスをスキャンする

目次: Arduino

毎回BlueZというかhcitoolの使い方を忘れてググっているのでメモしておきます。

Bluetooth LEデバイスのスキャンはhcitool lescanです。Bluetoothアダプタが2つ以上あるなら-iオプション（-i hci0など）でアダプタを指定できます。lescanは別の機器Crtl+Cなどで止めるまで発見したBluetooth LEデバイスのMACアドレスが延々と流れ続けます。

デバイス情報を見る場合はhcitool leinfoです。

# hcitool leinfo (xx:xx:xx:xx:xx:xx)

Requesting information ...
        Handle: 55 (0x0037)
        LMP Version: 5.0 (0x9) LMP Subversion: 0x16
        Manufacturer: Espressif Incorporated ( ?鑫信息科技(上海)有限公司 ) (741)
        Features: 0x01 0xf9 0x01 0x00 0x00 0x00 0x00 0x00

M5Stamp C3のMACアドレスを指定して実行するとこんな情報が表示されました。SoCのESP32シリーズの製造元はEspressifなので合ってそうですね。