はじめに
1 から 100 までの結果を予め用意しておいて関数呼び出し一発で出力するダイナミックリンクライブラリを使わない 808バイトの FizzBuzz プログラムをもっと小さくできないか検討してみました。
とりあえずの目標として、キリの良い数字でありディスク装置の 1セクタのバイト数でもある 512バイトを目指すこととしました。
解説
Linux の現在の標準的な実行ファイルの形式である ELF フォーマットでは、実行ファイルは最低限 elf header と program header、プログラムコードがあれば構成できます。Qiita では @amama さんの『elf.hを読んで実行可能ファイルを直書きする』に解説があります。
件の記事から引用すると、x86_64 の elf header は
+-----------------------------------------------+
|e_ident[EI_NIDENT] |
+-----------------------------------------------+
|7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00|
+-----+-----+-----------+-----------------------+
|type |mach |ver |e_entry |
+-----+-----+-----------+-----------------------+
|02 00|3e 00|01 00 00 00|78 00 40 00 00 00 00 00|
+-----+-----+-----------+-----------------------+
|e_phoff |e_shoff |
+-----------------------+-----------------------+
|40 00 00 00 00 00 00 00|00 00 00 00 00 00 00 00|
+-----------+-----+-----+-----+-----+-----+-----+
|e_flags |ehsiz|phesi|phnum|shesi|shnum|shstr|
+-----------+-----+-----+-----+-----+-----+-----+
|00 00 00 00|40 00|38 00|01 00|40 00|00 00|00 00|
+-----------+-----+-----+-----+-----+-----+-----+
という 64バイトの構造となり、program header は
+-----------+-----------+-----------------------+
|p_type |p_flags |p_offset |
+-----------+-----------+-----------------------+
|01 00 00 00|07 00 00 00|00 00 00 00 00 00 00 00|
+-----------+-----------+-----------------------+
|p_vaddr |p_paddr |
+-----------------------+-----------------------+
|00 00 40 00 00 00 00 00|00 00 40 00 00 00 00 00|
+-----------------------+-----------------------+
|p_filesz |p_memsz |
+-----------------------+-----------------------+
|90 00 00 00 00 00 00 00|90 00 00 00 00 00 00 00|
+-----------------------+-----------------------+
|p_align |
+-----------------------+
|00 00 20 00 00 00 00 00|
+-----------------------+
という 56バイトの構造となります。
先のプログラムに含まれる 1 から 100 までの FizzBuzz の文字列は改行を含めると 413バイトであり、この内容は変更しない前提とします。今回の目標は 512バイト内に実行ファイルのサイズを収めることなので、
512バイト - 413バイト = 99バイト
の空間に、64バイトの elf header、56バイトの program header、前の記事では 60バイトだったプログラムコードを収めることが今回の作業の主な内容となります。99バイトの領域にこれらの内容をそのまま格納することはできないので、ELF ファイルの構成としては正しくない方法を採ります。elf header は実行ファイルの先頭に配置する必要がありますが program header は任意の場所に配置でき、互いの内容がうまいこと合えばこの二つの領域はオーバーラップして配置することができます。また、両ヘッダの各項目は全てが使用されているわけではないので、その点を上手く利用することも可能です。「linix smallest elf」等でぐぐるとそれらについて解説した記事が複数確認できます。A Whirlwind Tutorial on Creating Really Teensy ELF Executables for Linux (or, "Size Is Everything")という記事には x64 ではなく x86 ですが Linux での elf header と program header の各項目について要不要が解説されています。それを参考に先の elf header と program header の不要な項目を XX で表すと
+-----------------------------------------------+
|e_ident[EI_NIDENT] |
+-----------------------------------------------+
|7f 45 4c 46 XX XX XX XX XX XX XX XX XX XX XX XX|
+-----+-----+-----------+-----------------------+
|type |mach |ver |e_entry |
+-----+-----+-----------+-----------------------+
|02 00|3e 00|XX XX XX XX|78 00 40 00 00 00 00 00|
+-----+-----+-----------+-----------------------+
|e_phoff |e_shoff |
+-----------------------+-----------------------+
|40 00 00 00 00 00 00 00|XX XX XX XX XX XX XX XX|
+-----------+-----+-----+-----+-----+-----+-----+
|e_flags |ehsiz|phesi|phnum|shesi|shnum|shstr|
+-----------+-----+-----+-----+-----+-----+-----+
|XX XX XX XX|XX XX|38 00|01 00|XX XX|XX XX|XX XX|
+-----------+-----+-----+-----+-----+-----+-----+
+-----------+-----------+-----------------------+
|p_type |p_flags |p_offset |
+-----------+-----------+-----------------------+
|01 00 00 00|07 XX XX XX|00 00 00 00 00 00 00 00|
+-----------+-----------+-----------------------+
|p_vaddr |p_paddr |
+-----------------------+-----------------------+
|00 00 40 00 00 00 00 00|XX XX XX XX XX XX XX XX|
+-----------------------+-----------------------+
|p_filesz |p_memsz |
+-----------------------+-----------------------+
|00 02 00 00 00 00 00 00|00 02 00 00 00 00 00 00|
+-----------------------+-----------------------+
|p_align |
+-----------------------+
|XX XX XX XX XX XX XX XX|
+-----------------------+
となります。
elf header と program header の先の表をオーバーラップする方法を検討し易い様 1次元の表にすると
+-----------------------------------------------+-----+-----+-----------+-----------------------+-----------------------+-----------------------+-----------+-----+-----+-----+-----+-----+-----+
|e_ident[EI_NIDENT] |type |mach |ver |e_entry |e_phoff |e_shoff |e_flags |ehsiz|phesi|phnum|shesi|shnum|shstr|
+-----------------------------------------------+-----+-----+-----------+-----------------------+-----------------------+-----------------------+-----------+-----+-----+-----+-----+-----+-----+
|7f 45 4c 46 XX XX XX XX XX XX XX XX XX XX XX XX|02 00|3e 00|XX XX XX XX|78 00 40 00 00 00 00 00|40 00 00 00 00 00 00 00|XX XX XX XX XX XX XX XX|XX XX XX XX|XX XX|38 00|01 00|XX XX|XX XX|XX XX|
+-----------------------------------------------+-----+-----+-----------+-----------------------+-----------------------+-----------------------+-----------+-----+-----+-----+-----+-----+-----+
+-----------+-----------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+
|p_type |p_flags |p_offset |p_vaddr |p_paddr |p_filesz |p_memsz |p_align |
+-----------+-----------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+
|01 00 00 00|07 XX XX XX|00 00 00 00 00 00 00 00|00 00 40 00 00 00 00 00|XX XX XX XX XX XX XX XX|00 02 00 00 00 00 00 00|00 02 00 00 00 00 00 00|XX XX XX XX XX XX XX XX|
+-----------+-----------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+
となります。これを使用して elf header と program header をオーバーラップさせる方法を検討した結果、program header を 0x31 から配置する方法を思い付きました。
+00+01+02+03+04+05+06+07+08+09+0a+0b+0c+0d+0e+0f+10+11+12+13+14+15+16+17+18+19+1a+1b+1c+1d+1e+1f+20+21+22+23+24+25+26+27+28+29+2a+2b+2c+2d+2e+2f+30+31+32+33+34+35+36+37+38+39+3a+3b+3c+3d+3e+3f+40+41+42+43+44+45+46+47+48+49+4a+4b+4c+4d+4e+4f+50+51+52+53+54+55+56+57+58+59+5a+5b+5c+5d+5e+5f+60+61+62
+-----------------------------------------------+-----+-----+-----------+-----------------------+-----------------------+-----------------------+-----------+-----+-----+-----+-----+-----+-----+
|e_ident[EI_NIDENT] |type |mach |ver |e_entry |e_phoff |e_shoff |e_flags |ehsiz|phesi|phnum|shesi|shnum|shstr|
+-----------------------------------------------+-----+-----+-----------+-----------------------+-----------------------+-----------------------+-----------+-----+-----+-----+-----+-----+-----+
|7f 45 4c 46 XX XX XX XX XX XX XX XX XX XX XX XX|02 00|3e 00|XX XX XX XX|78 00 40 00 00 00 00 00|40 00 00 00 00 00 00 00|XX XX XX XX XX XX XX XX|XX XX XX XX|XX XX|38 00|01 00|XX XX|XX XX|XX XX|
+-----------------------------------------------+-----+-----+-----------+-----------------------+-----------------------+-----------------------+-----------+-----+-----+-----+-----+-----+-----+
+-----------+-----------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+
|p_type |p_flags |p_offset |p_vaddr |p_paddr |p_filesz |p_memsz |p_align |
+-----------+-----------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+
|01 00 00 00|07 XX XX XX|00 00 00 00 00 00 00 00|00 00 40 00 00 00 00 00|XX XX XX XX XX XX XX XX|00 02 00 00 00 00 00 00|00 02 00 00 00 00 00 00|XX XX XX XX XX XX XX XX|
+-----------+-----------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+
これをひとつのバイト列にまとめて実行ファイルの先頭 99バイトの領域に配置すると内容は以下となります。
+00+01+02+03+04+05+06+07+08+09+0a+0b+0c+0d+0e+0f+10+11+12+13+14+15+16+17+18+19+1a+1b+1c+1d+1e+1f+20+21+22+23+24+25+26+27+28+29+2a+2b+2c+2d+2e+2f+30+31+32+33+34+35+36+37+38+39+3a+3b+3c+3d+3e+3f+40+41+42+43+44+45+46+47+48+49+4a+4b+4c+4d+4e+4f+50+51+52+53+54+55+56+57+58+59+5a+5b+5c+5d+5e+5f+60+61+62
7f 45 4c 46 XX XX XX XX XX XX XX XX XX XX XX XX 02 00 3e 00 XX XX XX XX 78 00 40 00 00 00 00 00 40 00 00 00 00 00 00 00 XX XX XX XX XX XX XX XX XX 01 00 00 00 07 38 00 01 00 00 00 00 00 00 00 00 00 00 40 00 00 00 00 00 XX XX XX XX XX XX XX XX 00 02 00 00 00 00 00 00 00 02 00 00 00 00 00 00 XX XX
XX の部分は自由に使用できる領域であり、プログラムコードを配置するにも使用できます。
0004 XX XX XX XX XX XX XX XX XX XX XX XX
0014 XX XX XX XX
0028 XX XX XX XX XX XX XX XX XX
0049 XX XX XX XX XX XX XX XX
0061 XX XX
合計 35バイトが自由に使用できることとなりますが、少々細切れであり使い勝手が悪そうです。他に上手い方法はないかとぐぐったところ、『The Return 42 Collection』というページに『tiny-x64.asm source』というコードを見つけました。これは、プログラムの開始アドレスを 0x000100000000 にすることにより program header を 0x001c から配置しており、
+00+01+02+03+04+05+06+07+08+09+0a+0b+0c+0d+0e+0f+10+11+12+13+14+15+16+17+18+19+1a+1b+1c+1d+1e+1f+20+21+22+23+24+25+26+27+28+29+2a+2b+2c+2d+2e+2f+30+31+32+33+34+35+36+37+38+39+3a+3b+3c+3d+3e+3f+40+41+42+43+44+45+46+47+48+49+4a+4b+4c+4d+4e+4f+50+51+52+53+54+55+56+57+58+59+5a+5b+5c+5d+5e+5f+60+61+62
+-----------------------------------------------+-----+-----+-----------+-----------------------+-----------------------+-----------------------+-----------+-----+-----+-----+-----+-----+-----+
|e_ident[EI_NIDENT] |type |mach |ver |e_entry |e_phoff |e_shoff |e_flags |ehsiz|phesi|phnum|shesi|shnum|shstr|
+-----------------------------------------------+-----+-----+-----------+-----------------------+-----------------------+-----------------------+-----------+-----+-----+-----+-----+-----+-----+
|7f 45 4c 46 32 31 31 31 00 8d 78 2a b0 3c 0f 05|02 00|3e 00|01 00 00 00|09 00 00 00 01 00 00 00|1c 00 00 00 00 00 00 00|00 00 00 00 00 00 00 00|01 00 00 00|40 00|38 00|01 00|00 00|54 00|00 00|
+-----------------------------------------------+-----+-----+-----------+-----------------------+-----------------------+-----------------------+-----------+-----+-----+-----+-----+-----+-----+
+-----------+-----------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+
|p_type |p_flags |p_offset |p_vaddr |p_paddr |p_filesz |p_memsz |p_align |
+-----------+-----------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+
|01 00 00 00|1c 00 00 00|00 00 00 00 00 00 00 00|00 00 00 00 01 00 00 00|40 00 38 00 01 00 00 00|54 00 00 00 00 00 00 00|54 00 00 00 00 00 00 00|00 00 20 00 00 00 00 00|
+-----------+-----------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+
elf header と program header 以外に使用可能な領域を XX で置き換えると
+00+01+02+03+04+05+06+07+08+09+0a+0b+0c+0d+0e+0f+10+11+12+13+14+15+16+17+18+19+1a+1b+1c+1d+1e+1f+20+21+22+23+24+25+26+27+28+29+2a+2b+2c+2d+2e+2f+30+31+32+33+34+35+36+37+38+39+3a+3b+3c+3d+3e+3f+40+41+42+43+44+45+46+47+48+49+4a+4b+4c+4d+4e+4f+50+51+52+53+54+55+56+57+58+59+5a+5b+5c+5d+5e+5f+60+61+62
+-----------------------------------------------+-----+-----+-----------+-----------------------+-----------------------+-----------------------+-----------+-----+-----+-----+-----+-----+-----+
|e_ident[EI_NIDENT] |type |mach |ver |e_entry |e_phoff |e_shoff |e_flags |ehsiz|phesi|phnum|shesi|shnum|shstr|
+-----------------------------------------------+-----+-----+-----------+-----------------------+-----------------------+-----------------------+-----------+-----+-----+-----+-----+-----+-----+
|7f 45 4c 46 XX XX XX XX XX XX XX XX XX XX XX XX|02 00|3e 00|XX XX XX XX|09 00 00 00 01 00 00 00|1c 00 00 00 00 00 00 00|00 00 00 00 00 00 00 00|01 00 00 00|XX XX|38 00|01 00|XX XX|54 00|00 00|
+-----------------------------------------------+-----+-----+-----------+-----------------------+-----------------------+-----------------------+-----------+-----+-----+-----+-----+-----+-----+
+-----------+-----------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+
|p_type |p_flags |p_offset |p_vaddr |p_paddr |p_filesz |p_memsz |p_align |
+-----------+-----------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+
|01 00 00 00|1c 00 00 00|00 00 00 00 00 00 00 00|00 00 00 00 01 00 00 00|XX XX 38 00 01 00 XX XX|54 00 00 00 00 00 00 00|54 00 00 00 00 00 00 00|XX XX XX XX XX XX XX XX|XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX
+-----------+-----------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+-----------------------+
となっています。プログラムコードを配置するに使用できる領域は
0004 XX XX XX XX XX XX XX XX XX XX XX XX
0014 XX XX XX XX
0034 XX XX
003a XX XX
004c XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX
合計 43バイトが使用できることとなります。先の例よりも連続して使用できる領域も長く、他に良い方法も思いつかないのでこれをパク採用させていただくこととしました。
作成したプログラム
そんなわけで以上を踏まえて書いたソースが以下となります。
fizzbuzz.s
.equiv N, 100
.equiv SYS_EXIT, 60
.equiv SYS_WRITE, 1
.equiv STDOUT_FILENO, 1
.equiv EINTR, 4
.equiv EXIT_SUCCESS, 0
.equiv EXIT_FAILURE, 1
.text
ehdr: # Elf32_Ehdr
.byte 0x7F,'E','L','F' # e_ident
_start:
movw $length, %dx
leaq string(%rip), %rsi
.byte 0xbd # mov $XXXXXXXX, %ebp
.word 2 # e_type
.word 0x3e # e_machine
incl %edi
jmp 2f
.quad _start # e_entry | p_type
.equiv phdr, .-4
.quad phdr-ehdr # e_phoff | p_flags
.long 0 # p_offset
.quad ehdr # p_vaddr
0:
xchgl %eax, %edi
.byte 0xbd # mov $XXXXXXXX, %ebp
.word phdrsize # e_phentsize
.word 1 # e_phnum
syscall
.quad filesize # p_filesz
.quad filesize # p_memsz
.equiv phdrsize, .+8-phdr
1:
cmpb $-EINTR, %al
jne 3f
2:
movl %edi, %eax
syscall
sahf
js 1b
addl %eax, %esi
subl %eax, %edx
jnz 2b
xchg %eax, %edx
3:
movb $SYS_EXIT, %dil
jmp 0b
string:
.macro num n
.if (\n) >= 10
num (\n) / 10
.endif
.byte '0' + (\n % 10)
.endm
.set i, 1
.rept N
.if i % 15 == 0
.ascii "FizzBuzz"
.elseif i % 3 == 0
.ascii "Fizz"
.elseif i % 5 == 0
.ascii "Buzz"
.else
num i
.endif
.ascii "\n"
.set i, i + 1
.endr
.equiv length, . - string
.equiv filesize, . - ehdr
.end
makefile
fizzbuzz: fizzbuzz.s
as fizzbuzz.s -o fizzbuzz.o -al=fizzbuzz.lst
ld -Ttext=100000000 -e 0 fizzbuzz.o -o fizzbuzz.x -M=fizzbuzz.map
objcopy -O binary fizzbuzz.x fizzbuzz
これをビルドすることでギリ目標である 512バイトの実行ファイルを生成することができました。
$ make
as fizzbuzz.s -o fizzbuzz.o -al=fizzbuzz.lst
ld -Ttext=100000000 -e 0 fizzbuzz.o -o fizzbuzz.x -M=fizzbuzz.map
objcopy -O binary fizzbuzz.x fizzbuzz
$ ls -l fizzbuzz
-rwxr-xr-x 1 fujita fujita 512 Jul 6 23:00 fizzbuzz
$ xxd -g1 fizzbuzz
00000000: 7f 45 4c 46 66 ba 9d 01 48 8d 35 54 00 00 00 bd .ELFf...H.5T....
00000010: 02 00 3e 00 ff c7 eb 38 04 00 00 00 01 00 00 00 ..>....8........
00000020: 1c 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00000030: 01 00 00 00 97 bd 38 00 01 00 0f 05 00 02 00 00 ......8.........
00000040: 00 00 00 00 00 02 00 00 00 00 00 00 3c fc 75 0e ............<.u.
00000050: 89 f8 0f 05 9e 78 f5 01 c6 29 c2 75 f3 92 40 b7 .....x...).u..@.
00000060: 3c eb d1 31 0a 32 0a 46 69 7a 7a 0a 34 0a 42 75 <..1.2.Fizz.4.Bu
00000070: 7a 7a 0a 46 69 7a 7a 0a 37 0a 38 0a 46 69 7a 7a zz.Fizz.7.8.Fizz
00000080: 0a 42 75 7a 7a 0a 31 31 0a 46 69 7a 7a 0a 31 33 .Buzz.11.Fizz.13
00000090: 0a 31 34 0a 46 69 7a 7a 42 75 7a 7a 0a 31 36 0a .14.FizzBuzz.16.
000000a0: 31 37 0a 46 69 7a 7a 0a 31 39 0a 42 75 7a 7a 0a 17.Fizz.19.Buzz.
000000b0: 46 69 7a 7a 0a 32 32 0a 32 33 0a 46 69 7a 7a 0a Fizz.22.23.Fizz.
000000c0: 42 75 7a 7a 0a 32 36 0a 46 69 7a 7a 0a 32 38 0a Buzz.26.Fizz.28.
000000d0: 32 39 0a 46 69 7a 7a 42 75 7a 7a 0a 33 31 0a 33 29.FizzBuzz.31.3
000000e0: 32 0a 46 69 7a 7a 0a 33 34 0a 42 75 7a 7a 0a 46 2.Fizz.34.Buzz.F
000000f0: 69 7a 7a 0a 33 37 0a 33 38 0a 46 69 7a 7a 0a 42 izz.37.38.Fizz.B
00000100: 75 7a 7a 0a 34 31 0a 46 69 7a 7a 0a 34 33 0a 34 uzz.41.Fizz.43.4
00000110: 34 0a 46 69 7a 7a 42 75 7a 7a 0a 34 36 0a 34 37 4.FizzBuzz.46.47
00000120: 0a 46 69 7a 7a 0a 34 39 0a 42 75 7a 7a 0a 46 69 .Fizz.49.Buzz.Fi
00000130: 7a 7a 0a 35 32 0a 35 33 0a 46 69 7a 7a 0a 42 75 zz.52.53.Fizz.Bu
00000140: 7a 7a 0a 35 36 0a 46 69 7a 7a 0a 35 38 0a 35 39 zz.56.Fizz.58.59
00000150: 0a 46 69 7a 7a 42 75 7a 7a 0a 36 31 0a 36 32 0a .FizzBuzz.61.62.
00000160: 46 69 7a 7a 0a 36 34 0a 42 75 7a 7a 0a 46 69 7a Fizz.64.Buzz.Fiz
00000170: 7a 0a 36 37 0a 36 38 0a 46 69 7a 7a 0a 42 75 7a z.67.68.Fizz.Buz
00000180: 7a 0a 37 31 0a 46 69 7a 7a 0a 37 33 0a 37 34 0a z.71.Fizz.73.74.
00000190: 46 69 7a 7a 42 75 7a 7a 0a 37 36 0a 37 37 0a 46 FizzBuzz.76.77.F
000001a0: 69 7a 7a 0a 37 39 0a 42 75 7a 7a 0a 46 69 7a 7a izz.79.Buzz.Fizz
000001b0: 0a 38 32 0a 38 33 0a 46 69 7a 7a 0a 42 75 7a 7a .82.83.Fizz.Buzz
000001c0: 0a 38 36 0a 46 69 7a 7a 0a 38 38 0a 38 39 0a 46 .86.Fizz.88.89.F
000001d0: 69 7a 7a 42 75 7a 7a 0a 39 31 0a 39 32 0a 46 69 izzBuzz.91.92.Fi
000001e0: 7a 7a 0a 39 34 0a 42 75 7a 7a 0a 46 69 7a 7a 0a zz.94.Buzz.Fizz.
000001f0: 39 37 0a 39 38 0a 46 69 7a 7a 0a 42 75 7a 7a 0a 97.98.Fizz.Buzz.
$
実行結果
$ ./fizzbuzz
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
22
23
Fizz
Buzz
26
Fizz
28
29
FizzBuzz
31
32
Fizz
34
Buzz
Fizz
37
38
Fizz
Buzz
41
Fizz
43
44
FizzBuzz
46
47
Fizz
49
Buzz
Fizz
52
53
Fizz
Buzz
56
Fizz
58
59
FizzBuzz
61
62
Fizz
64
Buzz
Fizz
67
68
Fizz
Buzz
71
Fizz
73
74
FizzBuzz
76
77
Fizz
79
Buzz
Fizz
82
83
Fizz
Buzz
86
Fizz
88
89
FizzBuzz
91
92
Fizz
94
Buzz
Fizz
97
98
Fizz
Buzz
$
おわりに
おわりです。