この記事はCompetitive Programming （その2） Advent Calendar 2016の20日目の記事です。
標準CライブラリやOSの機能を用いず競技プログラミングの問題を解く話です。無駄に長いですが、読んでも競技プログラミングの腕は上がりませんので、ご注意ください。
はじめに
簡単な問題を"コンパクト"に解いてみよう。題材は記念すべきAtCoder Beginner Contest 第1回のA問題とする。
A - 積雪深差
この問題は2000以下の正整数を２つ入力として受け取り、その差を出力するものである。
"ショートコード"の観点ではAtCoderでは現在Perlで書かれた下記13byteのコードが最短である。
print<>-<>,$/
だが、"コンパクト"の意味をメモリ消費量や実行バイナリのサイズととるとそうはいかない。たとえばUbuntu 64bit 16.04ではPerlのバイナリは2MB近い。
$ ls -l /usr/bin/perl -rwxr-xr-x 2 root root 1907192 Mar 13 2016 /usr/bin/perl
確かに上記コードは短いが、2MBのバイナリで実行するコードをコンパクトと言ってよいものだろうか。
以下、"コンパクト"とは"実行用のバイナリが小さいこと"と定義し、コンパクトな解法を考えてみよう。
C言語で挑む
実行バイナリのサイズという点では、高級言語のインタプリタは不利である。そこでまずはシンプルにC言語で書いてみよう。以下入力がvalidであることを前提とし、エラー処理は含まない。
#include <stdio.h> int main(int argc, char** argv) { int H1, H2; scanf("%d%d", &H1, &H2); printf("%d\n", H1 - H2); return 0; }
Ubuntu 64bit 16.04上で、サイズを減らす-Osオプションをつけてコンパイルし、stripで余計な情報をそぎ落とすと6.3KBになる。
$ gcc -Os abc001_a.c $ strip a.out $ wc -c a.out 6328 a.out
gccに-m32オプションをつけ、32bitコンパイルすると5.6KB弱まで落ちる。*1
$ gcc -Os -m32 abc001_a.c $ strip a.out $ wc -c a.out 5596 a.out $ file a.out a.out: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=df384dc800722e80104bccf1cc61a7f0f3a3b589, stripped
これでゴールでいいのだろうか？
5.5KBはまだかなり大きい気がするが、もう一つ問題がある。
このプログラムは標準Cライブラリを利用しているため、実行時に共有ライブラリlibc.soをリンクする。
実行バイナリの外にある共有ライブラリを利用しておいて、「小さなバイナリが出来た」などと言うのは邪道ではないだろうか。
$ ldd a.out
linux-gate.so.1 => (0xf773e000)
libc.so.6 => /lib/i386-linux-gnu/libc.so.6 (0xf757b000)
/lib/ld-linux.so.2 (0x56652000)
標準Cライブラリを使わず挑む
外部の共有ライブラリを使っているではないか、などと言われないよう、標準Cライブラリを使わず書くことにする。その際は以下の２つの点に気を付ける。
- 標準Cライブラリがないのでprintf関数やscanf関数は使えない。read関数やwrite関数も利用できない。
- プログラムはmainではなく_startから始まる*2。_start関数からreturnしてはいけない(スタックが空になるためSEGVでプログラムが終了する)
前者はread/writeシステムコールを直接呼ぶことで対応する。
Linux x86(32bit)環境では、システムコール実行は外部のライブラリなど不要で、アセンブラを使いCPUのsysenter命令かint 80h命令を実行すれば良い。今回は後者を利用した。
scanf/printfが行ってくれていた文字列と数値の変換はしょうがないので自力で実装しよう。
main関数がない点の対応は、関数名を_startとするとともに、関数からreturnせずexitシステムコールを直接呼び終了することで回避できる。
以上を踏まえてコードを書いてみる*3。まずはサイズは気にせずストレートに書いてみる。標準Cライブラリを使わないので、stdio.hすらincludeする必要はない。
/* 標準入力から1文字readする */ char mygetchar() { char buf; char* pbuf = &buf; int ret; /* ret = read(0, pbuf, 1) */ asm volatile("int $0x80" : "=a" (ret) : "0"(3), "b" (0), "c" (pbuf), "d" (1) : "cc", "memory"); return buf; } /* 標準出力に1文字writeする */ void __attribute__((__noinline__)) myputchar(char c) { char* pbuf = &c; int ret; /* ret = write(1, pbuf, 1) */ asm volatile ("int $0x80" : "=a" (ret) : "0"(4), "b" (1), "c" (pbuf), "d" (1) : "cc", "memory"); } /* 標準入力から1行読み取り、整数として返す */ int getval() { int val = 0; while(1) { char c = mygetchar(); if (c=='\n') break; val = val * 10 + (c-'0'); } return val; } /* 整数を標準出力に出力 */ void putval(int val) { if (val == 0) { /* 0は特別扱い */ myputchar('0'); } else { char buf[10]; int len = 0; if (val < 0) { /* 負の数の処理 */ myputchar('-'); val = -val; } /* 下の桁から一時バッファに書き出し、逆順で標準出力に書く */ while (val > 0) { buf[len++] = '0' + (val%10); val /= 10; } while (len>0) myputchar(buf[--len]); } myputchar('\n'); } void _start() { int H1, H2; H1 = getval(); H2 = getval(); putval(H1 - H2); /* exit(0) */ asm volatile("int $0x80" : : "a" (1), "b" (0)); }
nostdlibオプションでlibcを外してコンパイルすることで、生成されるバイナリは1160バイトまで縮小した。
static linkされており外部のライブラリにも依存しない。
$ gcc -nostdlib -Os -m32 abc001_nostdlib.c $ strip a.out $ file a.out a.out: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), statically linked, ※ static linkされている BuildID[sha1]=bcad91a1d24db5ba2a22508fb86a19aea1a64673, stripped $ wc -c a.out 1160 a.out
もう少し削ることを考えよう。
下記の通り、a.outの内部構造を見てみると実行に関係ないセクションが多数あるので、.text以外を削除してしまおう。こうすると624byteまで行ける。
$ readelf -l a.out Elf file type is EXEC (Executable file) Entry point 0x80481bd There are 4 program headers, starting at offset 52 Program Headers: Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align LOAD 0x000000 0x08048000 0x08048000 0x002f4 0x002f4 R E 0x1000 NOTE 0x0000b4 0x080480b4 0x080480b4 0x00024 0x00024 R 0x4 GNU_EH_FRAME 0x0001e4 0x080481e4 0x080481e4 0x00034 0x00034 R 0x4 GNU_STACK 0x000000 0x00000000 0x00000000 0x00000 0x00000 RW 0x10 Section to Segment mapping: Segment Sections... 00 .note.gnu.build-id .text .eh_frame_hdr .eh_frame 01 .note.gnu.build-id 02 .eh_frame_hdr 03 $ objcopy -R .note.gnu.build-id -R .eh_frame_hdr -R .eh_frame -R .comment -S a.out b.out ※要らないセクションを削除 $ wc -c b.out 624 b.out
さらに反則的な手段でもう少し削減できる。
こうして作成したb.outは624byteではあるが、Program Headerを見ると先頭0x1e4 Byteしかメモリにロードされない。そこで先頭0x1e4=484Byteだけ残し後ろを捨てても動作する。(Section Headersを消してしまうのでobjdumpコマンドなどには文句を言われる)
$ readelf -l b.out Elf file type is EXEC (Executable file) Entry point 0x80481bd There are 4 program headers, starting at offset 52 Program Headers: Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align LOAD 0x000000 0x08048000 0x08048000 0x001e4 0x001e4 R E 0x1000 NOTE 0x000000 0x00000000 0x00000000 0x00000 0x00000 R 0x4 GNU_EH_FRAME 0x000000 0x00000000 0x00000000 0x00000 0x00000 R 0x4 GNU_STACK 0x000000 0x00000000 0x00000000 0x00000 0x00000 RW 0x4 $ head -c 484 b.out > c.out $ ./c.out ※ちゃんと動く 1234 987 247
ひとまずこれで500Byteは切れることを確認できた。コードを細かく切り詰めればもっと小さくなるだろうが、ひとまずはこの辺にしておく。
こうして作られた実行ファイルは共有ライブラリも使っていないので、外部に実行コードを持つわけでもない。
そしてOSレス解法へ
ここまではLinux上でコードを実行した。
…考えてみると、標準入出力はLinuxカーネルが提供する機能である。
Ubuntu 16.04のカーネルは、圧縮しても7MBものサイズがある。そんな巨大なカーネルにぶら下がっておいて、コンパクトな実行バイナリができたと喜んでいいのだろうか？
$ sudo wc -c /boot/vmlinuz-4.4.0-53-generic 7065648 /boot/vmlinuz-4.4.0-53-generic
カーネルの余計な機能を絞ることもできるが、昨今のカーネルを頑張って縮めても数百KB後半のオーダーのバイナリになってしまう*4。
そもそも、２つ整数を読んで１つ出力するのにキロだメガだなどという規模のバイナリを要するのは過剰ではないだろうか。
方針は決まった。OSなどなくとも動くようにしよう。以下、Legacy BIOS起動を前提とする。
MBR作成の環境構築
BIOSは、ブートデバイスの先頭セクタ(Master Boot Record)をメモリに読み込み、そこのコードを実行してくれる。このMBRに格納するコードを作ろう。まずは開発環境を整える。と言ってもそれほど特殊なツールは必要ない。
Ubuntuの場合、上記手順で32bitコンパイル可能な状態であればよい。
cygwinの場合、elf形式を扱いたいのでbinutilsとgccを別途ソースからビルドしてインストールしよう。cygwin標準のツール群はexe形式向けでコンパイルされており、elf形式を処理できない。
binutilsとgccとnewlibのソースを展開し、以下のようにconfigureしたのちmakeすればcygwinでもgcc-elfやas-elfというコマンド名でelf形式を扱える。
今回利用したcygwinおよびUbuntu環境では、最終的に同一のバイナリが生成されたことを確認している。
../binutils-2.27/configure --target=i386-elf --prefix=/usr/local/i386-elf/ --program-suffix=-elf ../gcc-6.2.0/configure --enable-languages=c,c++ --target=i386-elf --prefix=/usr/local/i386-elf/ --program-prefix= --program-suffix=-elf --with-gnu-as --with-gnu-ld --with-newlib --with-headers=../newlib-2.4.0/newlib/libc/include
MBRのコードを書いてみる
MBR中のコードは以下の前提で実行される。
- BIOSは起動すると起動デバイスの先頭セクタ512Byteをメモリアドレス0x7C00に読み込み、そこから読み込んだプログラムに制御を渡す。
- 末尾2byteはSignature "0x55 0xAA"で埋めなければならない(そうしないとBIOSがブートしてくれない)ため、使えるのは510Byte。
- 当然ながら16bitモード前提でプログラムを組む。割り込みをかけてBIOSの機能を利用できる。
通常MBRの仕事は次の段階のブートローダを実行することであり、FDD/HDD関連の処理を行う。そのためブートセクタのプログラムはIPL(Initial Program Loader)と呼ばれることも多い。
だが今回はそれらは必要なく、整数の入出力さえできればよい。入出力にはそれぞれ以下のBIOSの機能を用いることにした。
- Int 16/AH=0Eh KEYBOARD - GET KEYSTROKE : 1文字入力
- 実行するとキーボードに入力がくるまで待機し、AHレジスタにキーボードのスキャンコード、ALレジスタにアスキーコードが入る。スキャンコードはInt 09の項を参考にしよう。
- キーを押すだけでなく離す場合も処理が返る。その場合AHのMSBがセットされる。今回のプログラムではキーを離す場合は無視するようにしよう。
- 何気に結構賢くてキーリピートとかも対応している。
- Int 10/AH=0Eh VIDEO - TELETYPE OUTPUT : 1文字出力
- ALにアスキーコードを入れるとそれを出力する。BXレジスタはモノラルなテキストモードでは設定不要である。
- こちらも結構賢くて、改行どころかスクロールも対応してくれる。
ここまでわかればもうプログラムが書けるはず。さらっと書いてみよう。以下gas向けに書いたipl.Sファイルの内容である。
以下は(本来削除すべきではないが短縮のため)セグメントレジスタやスタックの初期化をコメントアウトしている。
#16bit用のコード .code16gcc .text .global start #------------------------------------ #以下プログラム開始(0000:7C00より) start: /* 以下はなくてもVMでは動くので外す #割り込み禁止 cli #セグメントレジスタ初期化 xor %ax, %ax mov %ax, %ds mov %ax, %es mov %ax, %ss #スタック及びフレームポインタ設定 mov $0x7BFC,%sp mov %sp,%bp #割り込み許可 sti */ main_loop: # 2値を取得 callw getint mov %dx,%si # 返り値H1を%siに保存 callw getint sub %dx,%si # si = H1 - H2 # スタックポインタの現在値を覚えておく mov %sp,%cx # 改行記号を入れておく、あとで0x30足すので引いた値を入れる pushw $0xFFDD # 0x0D pushw $0xFFDA # 0x0A # %siが0なら'0'表記 jne check_negative # 上のsi-dxで判定 pushw $0x0 jmp output # %siが負ならマイナス表記 check_negative: jns output_positive mov $0x2d, %al # AH=0x0e, AL='-' getintの延長でah=0x0eのまま int $0x10 # 符号反転 imul $-1,%si output_positive: # 下の桁から順にメモリに書いて逆順で出力 # 除算がax,dxしか使えないのでそちらを利用 mov %si, %ax while_positive: # while(%si>0) xor %dx, %dx or %ax, %ax # cmpより1byte小さい je output mov $10, %si idiv %si push %dx # 余りをスタックに追加 jmp while_positive output: cmp %sp, %cx # while(cx>0) je main_loop # 出力を終え次の入力へ mov $0x0e30,%ax # '0'の分加算 pop %dx add %dx,%ax int $0x10 jmp output getint: # %dxで返す xor %dx, %dx # 一時変数 getint_while: # キー入力取得 xor %ax, %ax int $0x16 cmp $0x1c, %ah # 改行キーなら抜ける je getint_break cmp $0x02, %ah # '1'～'0'のキーを押す以外の場合再ループ。 jb getint_while cmp $0x0B, %ah ja getint_while # 10倍して最下位桁を挿入 imul $10, %dx # asciiコードなので'0'を引く、スキャンコード(ah)よりasciiコード(al)の方がよい xor %ah, %ah add %ax, %dx # axは下のローカルエコーで使うので書き換えない sub $0x30,%dx # なくてもいいけどローカルエコー mov $0x0e, %ah int $0x10 jmp getint_while getint_break: # 改行文字(0D 0A)を書く mov $0x0e, %ah # alはもともと0x0d int $0x10 mov $0x0a, %al int $0x10 retw
コンパイルしてみる
上記プログラムをコンパイルするわけだが、当然BIOSはLinuxなどで用いられるelf形式の実行ファイルを認識しない。
そこでいったんelf形式でコンパイルし、コード部分だけ取り出そう。
今回メモリ上の配置などを明示的に指定するため、リンカスクリプトを書く。
今回は以下のリンカスクリプトipl.lsを作成した。実行に必要なセクション(.text, .data, .bss)のみ連続して0x7C00に配置し、残りは捨てるようにしている。
OUTPUT_FORMAT(elf32-i386)
ENTRY(start)
MEMORY{
ipl_body : org = 0x7C00, len = 0x1FE
}
SECTIONS{
.text : { *(.text) } > ipl_body
.data : { *(.data .rdata .rodata*) } > ipl_body
.bss : { *(.bss) } > ipl_body
/* いらないセクションはすべて削る */
/DISCARD/ : { *(*)}
}こうして作成したipl.Sとipl.lsからバイナリを作成する。
まずは普通にipl.Sをコンパイルし、ipl.lsを指定してリンクしよう。
こうして作成したelf形式の実行ファイルipl.elfはまだ大きい。ここから、stripコマンドでフォーマットをbinary指定にして余計な情報を外す。
今回は107byteのバイナリipl.binが出来上がった。16bit指定で逆アセンブルするとそれらしいコードも出てくる。
$ gcc -c -o ipl.o ipl.S $ ld -T ipl.ls -o ipl.elf ipl.o $ wc -c ipl.elf 32140 ipl.elf $ strip -O binary -o ipl.bin ipl.elf $ wc -c ipl.bin 107 ipl.bin $ objdump -D -b binary -mi386 -Maddr16,data16 ipl.bin | head -15 ipl.bin: file format binary Disassembly of section .data: 00000000 <.data>: 0: e8 3a 00 call 0x3d 3: 89 d6 mov %dx,%si 5: e8 35 00 call 0x3d 8: 29 d6 sub %dx,%si a: 89 e1 mov %sp,%cx c: 6a dd push $0xffdd e: 6a da push $0xffda 10: 75 04 jne 0x16
(アセンブラレベルでさらに短縮することは可能として)こうして107byteというかなり小さなバイナリが出来上がった。
ここで少々残念であるが、上記の通りBIOSブートには511,512Byte目にSignatureが必要である。そのため厳密にはどうしても512byteのデータが最小となってしまう。
Signatureの埋め込みは下記の通り、510Byteのゼロ埋めファイルを作成後、echoで0x55, 0xaaを追記し、また先頭にipl.binを埋め込めば完了する。こうしてMBRに入れる512byteのipl.secが出来上がった。
$ dd if=/dev/zero of=ipl.sec bs=510 count=1 1+0 records in 1+0 records out 510 bytes copied, 0.000193767 s, 2.6 MB/s $ echo -en "\x55\xaa" >> ipl.sec $ dd if=ipl.bin of=ipl.sec conv=notrunc 0+1 records in 0+1 records out 107 bytes copied, 0.000212634 s, 503 kB/s
動かしてみる
作ったプログラムを動かしてみよう。UEFI環境では動作しないため、Legacy BIOS起動環境で実施する。
実機の場合、作ったipl.secをFD/HDD/USBメモリなどの先頭セクタにddコマンドで書き込めばよい。
VMの場合、仮想FD/ディスクイメージの先頭512byteにipl.secを埋めればよい。
以下VirtualBoxの実行例である。起動後画面が暗くなった後、キーボード入力が可能である。
２行整数を入力すると、１行その差が出力される。差が負やゼロの場合もうまくいっている。
ここで少々お詫びがある。
上記プログラムはVM環境ではbochs、VirtualBox、Hyper-Vと複数環境で動作を確認した。
ただ、実機環境では一部出力が乱れるケースがあった(一部文字が表示されない、なぜか入力値が２値同じなのに差がマイナス判定されるなど)。
減算後のEFLAGSがどうもおかしく見えたりするなど、原因が究明できなかったので今回は実機動作確認は未完である。*5
ともあれ、これにてようやくABC#001のA問題を解くことができた。今回作ったプログラムはFDに詰めれば20年前のPCでも動くだろう。
Signatureを除けば107byteとかなり小さいバイナリである。今回見栄えのためのキー入力数字の出力をしているが、それをなくせば100byteも切れる*6。
自分はアセンブラのショートコーディング経験はないためここで止めるが、うまくlea命令やstring系命令を使えばもっと縮まるかもしれない。
補足:Windows編
Windowsで小さなバイナリを作る場合、メガデモなどの分野を筆頭に圧縮機能を備えたリンカを用いた極小exeファイル作成手法があるようだ。
今回は時間切れのため自分では試さなかったが、以下が参考になる。
- デモシーンへようこそ 〜 4KBで映像作品を作る技術 〜(PowerPoint Online) (100MB超でかなり重いので注意) *7
上記サイトを見るに、さすがに今回のプログラムは512byteは超えそうなので、まぁIPL版の方が小さいと考えていいだろう。
…ところで、普段Windowsの実行ファイルといえば拡張子.exeが一般的だが、昔使われた.comファイルは32bit版であれば今のWindowsでも実行できる。
.comファイルはヘッダなどなく非常にコンパクトな実行形式で、そのままメモリ上に配置される。また、.comファイルが動作する仮想x86モードではBIOSの機能も利用できる。
…ここまで読んで予感がしたかもしれないが、その通り。今回作ったipl.binは、実は拡張子を.comにするとそのままWindowsのコマンドプロンプトでも動く。
*8
下記の通り、107byteの.comファイルで実機でも想定通り動いた。USBメモリを何十回も抜きさししてブートを繰り返して実機で実験など必要なかったのだ。
参考文献
ほかにもいろいろあるが、今回特に参照した文献のみ示す。
まとめ
日頃競プロや高級言語だけ扱っていると、書いたコードがどう実行されるというのはあまり気にならないと思いますが、たまにはmain関数が実行されるまで何が起こっているかを気にしてみると面白いと思います。
昔ブートセクタプログラムを書いたときは資料が少なく苦労しましたが、最近(特に書籍「30日でできる！ OS自作入門」が登場してから？)ネット上でも日本語で書かれた資料が増えてきました。この本はOS自作界での蟻本に相当するかもしれません。
明日はevimaさんの「新Google翻訳って結局どうなのさ？」とtogatogaさんの「自作のCDCL SATソルバでプロコンの問題を殴る」です。どちらもどんな内容か気になりますね。
*1:Ubuntuに32bitコンパイルの環境を導入する手順は Ubuntu 14.04 64bit で 32bit アプリを動作させる方法 - 明日にはでっかい太陽が昇るかもしれません。 など参照
*2:通常はlibc内に_startがあり、様々な初期化をしたうえでmain関数を呼んでいる。興味がある人はglibcのsysdeps/i386/start.Sから追ってみよう
*3:最適化オプション次第で最適化の過程でインラインアセンブラの部分がうまく動かず、結構てこずった
*4:小さいLinux環境の作り方 - Speaker DeckやSFO15-BFO2: Reducing the arm linux kernel size without losing your mi…参照
*5:コンパイルしてddでUSBメモリに抜き差しして実験機をリブートして…を数十回やってたらさすがに疲れた。レジスタとか覗けないのでデバッグもまともにできないし…
*6:BIOSの機能使うのずるくない？との指摘はもっともだが、キーボードコントローラを初期化して…とかやると510Byteには収まらず結局int 13hで別セクタを読む必要があるのでそこは勘弁してほしい
*7:i-saint氏のゲームといえば、eXecptionのCD版を買い逃したことをいまだに悔んでいる。DLSiteにはあるんだけどね。ちなみに4kb introでは私もelevatedが好きです。
*8:注意：.comファイルはメモリ上0x100byte目以降に展開されるため、0x7C00byte目に展開されるMBRとはアドレスが異なる。幸い今回のコードは絶対アドレスが登場しないため問題ない。
