コグノスケ

100万回のHello, World! - 補足

目次: ベンチマーク

前回はループ、再帰なし、1000バイト以下で100万回のHello, World!を実施する問題に対し、バイナリサイズを104バイトまで削るためのアイデアと実装方法をご紹介しました。

100万回のHello, World!プログラムの方は所定の範囲に収まって動作しているので、特に変えなくて良いです。気になるとすれば、プログラムの終了ステータスがエラー（今は60）になっている程度です。原因はexitシステムコールに渡す引数が0ではないからで、syscall命令を呼ぶ前にrdiを0にすれば直ります。まあ、できたら良いな程度で動作には関係ありません。

Linuxのシステムコール呼び出し規約は下記のようになっています。

バイナリファイルのサイズをこれ以上短くしようとするなら、ELFヘッダとプログラムヘッダをさらに重ねる必要があります。ELFヘッダとプログラムヘッダを完全に重ねると64バイト（2020年7月5日の日記参照）になりますが、プログラムはSegmentation Faultになってしまって動作しませんから、動作可能な重ね方を探す必要があります。

100万回のHello, World! - バイナリサイズを削って遊ぼう、112バイトから104バイトへ

目次: ベンチマーク

前回はループ、再帰なし、1000バイト以下で100万回のHello, World!を実施する問題に対し、バイナリサイズを112バイトまで削るためのアイデアと実装方法をご紹介しました。今まで112バイトが限界だと思っていましたが、とあるサイト（Tiny ELF Files: Revisited in 2021）からいくつかヒントを得て104バイトにできました。

概要

サイズ104バイトの実行バイナリはこんな感じです。

$ hexdump -C 104byte.out
00000000  7f 45 4c 46 bb 40 42 0f  00 6a 01 58 89 c7 90 68  |.ELF.@B..j.X...h| -> ELF header
00000010  02 00 3e 00 b2 0e eb 10  04 00 3e 00 00 00 00 00  |..>.......>.....| -> ELF header
00000020  30 00 00 00 00 00 00 00  5e 83 c6 46 0f 05 eb 30  |0.......^..F...0| -> ELF header
00000030  01 00 00 00 05 00 38 00  01 00 00 00 00 00 00 00  |......8.........| -> ELF, Program header
00000040  01 00 3e 00 00 00 00 00  48 65 6c 6c 6f 2c 20 57  |..>.....Hello, W| -> Program header
00000050  6f 72 6c 64 21 0a 00 00  6f 72 6c 64 21 0a 00 00  |orld!...orld!...| -> Program header
00000060  ff cb 75 a5 6a 3c eb a3                           |..u.j<..|         -> Program header
00000068

$ ./104byte.out | head
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!

$ ./104byte.out | wc
1000000 2000000 14000000

主な更新点は2つです。

• ELFヘッダとプログラムヘッダの重ねるサイズを8→16バイトに拡大
• p_vaddr == p_paddrは不要でp_addrは何でも良い

順番に説明したいと思います。

ELFヘッダとプログラムヘッダを重ねる

前回はELFヘッダとプログラムヘッダを8バイト重ねましたが、さらに+8バイトつまり16バイト重ねることができます。

今までp_type, p_flagsとe_flags〜e_phentsizeは重ねられないと思っていましたが、p_flagsは下位が0x0005（Read, Executable）であれば上位ワードは何でも良く、うまく重ねられることを知りました。いやーこれはすごい。この工夫によってELFヘッダ + プログラムヘッダのサイズが104バイトになります。

値を変更できない部分（黄色: ELFヘッダ由来、緑色: プログラムヘッダ由来）

今回のバイナリで自由に変更してはいけない部分に色を塗るとこんな感じです。黄色がELFヘッダに由来する制約、緑色がプログラムヘッダに由来する制約です。

ちなみにp_flagsにWriteをつけるとSEGVでクラッシュして、カーネルがこんなエラーログを出します。

__vm_enough_memory: pid: 764111, comm: 104byte.out, bytes: 11138535030784 not enough memory for the allocation

Write属性をつけると書き込み用のメモリを確保しようとするのだと思われます。プログラムヘッダのp_fileszやp_memszにめちゃくちゃな値を指定しているため、そんなサイズは確保できずにエラーになります。従ってp_flagsは0x7（RWX）でなく0x5（RX）が必須です。

p_paddrは何でも良かった

プログラムヘッダのp_vaddr（オフセット0x40）とp_paddr（オフセット0x48）は同じ値でなければならないと勘違いしていましたが、実はp_paddrはどんな値でも動作することを知りました。ELFとプログラムヘッダの重ね合わせで失われた8バイトを挽回しうる空き地となるでしょう。

• e_identの先頭4バイトは0x7f, 'E', 'L', 'F
• e_type（オフセット0x10）は0x0002
• e_machine（オフセット0x12）は0x003e
• e_entry（オフセット0x18）は実行開始アドレス（エントリアドレス）を指す
• p_filesz == p_memszが必要
• p_fileszは何でもOKだが、大すぎる値はNG（上位2バイトは0じゃないとSegmentation Faultする）

ELFヘッダやプログラムヘッダの制約をリストアップするとこんなところです。

実装

前回はC言語の配列で作っていましたが、バイナリコードに変換するのが面倒くさいので最初からアセンブラで書きます。アセンブラ実装はトリッキー度合いが低い方（2024年2月26日の日記参照）を流用しました。

	.intel_syntax
	.globl _start
	.set _top, 0x3e0000

	//e_ident
	.byte 0x7f, 'E', 'L', 'F'

_start:
	mov %ebx, 1000000
_loop:
	push 0x01
_last:
	pop %rax
	mov %edi, %eax
	nop

	//push imm inst
	.byte 0x68
	//e_type
	.word 0x0002
	//e_machine
	.word 0x003e

_second:
	mov %dl, 0x0e
	jmp _third

	//e_entry
	.quad _top + 4
	//e_phoff
	.quad 0x30

_third:
	pop %rsi
	add %esi, 0x46
	syscall
	jmp _fourth

	//e_flags(any), p_type(0x01)
	.long 0x01
	//e_ehsize(any), p_flags low(0x05)
	.word 0x05
	//e_phentsize(0x38), p_flags high(any)
	.word 0x38
	//e_phnum(0x01), e_shentsize, e_shnum, e_shstrndx, p_offset(0x01)
	.quad 0x01
	//p_vaddr
	.quad _top + 1

	//p_paddr(any)
	.byte 'H', 'e', 'l', 'l', 'o', ',', ' ', 'W'

	//p_filesz
	.byte 'o', 'r', 'l', 'd', '!', 0xa
	.word 0
	//p_memsz
	.byte 'o', 'r', 'l', 'd', '!', 0xa
	.word 0

	//p_align(any)
_fourth:
	dec %ebx
	jne _loop
	push 0x3c
	jmp _last

トリッキーなことはせず素直に詰め替えましたが、それでも104バイトに収まりました。いいね〜。

$ as 104byte.asm -o 104byte.o
$ ld --oformat binary 104byte.o -o 104byte.out


$ ./104byte.out | wc
（略）

$ ./104byte.out | head
（略）

$ objdump -D 104byte.o -M intel
（Intel記法で逆アセンブルする方法です、デフォルトはAT&T記法）

ビルド方法はこんな感じです。

文字列アドレスのロードをバラバラにする

今回はHello, World!の出力にwriteシステムコールを使っていて、rsiレジスタに文字列の先頭アドレスを渡す必要があります。単純にmov命令でesiレジスタに32bit即値をセットすると、5バイト命令が必要で配置に大きな制約が生じますので、小さい命令に分割して配置を容易にする方法を考えます。

単純に分割するとpush 5バイト、pop 1バイト、add 3バイトですが、ELFヘッダ内で変更できない邪魔者であるe_typeとe_machineの前にバイト0x68を置いてpush 0x3e0002命令にしてしまえば、4バイト節約できます。pushした値は下位アドレス2なので文字列の先頭（0x3e0048）を指すため0x46をaddします。

	//push imm inst
	.byte 0x68
	//e_type
	.word 0x0002
	//e_machine
	.word 0x003e

_second:
	mov %dl, 0x0e
	jmp _third

	//e_entry
	.quad _top + 4
	//e_phoff
	.quad 0x30

_third:
	pop %rsi          //pushした0x3e0002をpop
	add %esi, 0x46    //esiの下位を0x02から0x48へ
	syscall
	jmp _forth
...

もう一つのカギはプログラムヘッダのp_vaddrを0x3e0001にして、プログラムを0x3e0001にロードすることです。下位バイトが1なのはプログラムヘッダのp_offsetが1になっているせいです。

Windowsの日本語フォントはみな長生き

GNOME48からフォントが変わるニュースを見ていて、フォントを作成するのが割と簡単な英語圏にしては、Cantarellを15年も使っていたのは珍しい？んでしょう。結構息が長かったんだなあと思います。

フォントが長く使われる傾向に関しては日本語フォントもたいがいだよなあ？と思ったのでWindowsの日本語フォント変遷をリストアップしてみました。

• MSゴシック: Windows 3.1（1993〜）
• MS Pゴシック: Windows 95（1995〜）
• MS UIゴシック: Windows 98（1998〜）
• メイリオ: Windows Vista, 7, 8（2006〜）
• 游ゴシック: Windows 10, 11（2015〜）

やはりWindowsの日本語フォントはみんな息が長いです。次世代にバトンを渡すまでの期間だけ見ても、MSゴシック13年、メイリオ9年、游ゴシックも10年経ったんですね。Windowsの次バージョンが出るか出ないか定かじゃないですけど、もし次があったとしたらフォントを変えてきそうですね。