Brainf*ck(何となく伏せ字)という言語があるそうな。たった8つの命令しかないのに、(理論上)あらゆるプログラムが書ける(というかチューリング完全な)言語です。詳しくは Wikipediaの記事などを。
8つしか命令がない、引数もないので、コンパイラやインタプリタを作るのがとても簡単。というわけで作ってみました。
しかしただ作るだけでは面白くないので、なるべく小さくすることに挑戦してみます。
小さくと言っても、
とかがあるらしいですが、後者のバイナリを小さする方に挑戦してみました。
言語・環境としてはC (gcc)、Linux i386で挑戦。とりあえずgccで出来る範囲で頑張る、ということにします。
参考
Binary Hacks ―ハッカー秘伝のテクニック100選
- 作者: 高林哲,鵜飼文敏,佐藤祐介,浜地慎一郎,首藤一幸
- 出版社/メーカー: オライリー・ジャパン
- 発売日: 2006/11/14
- メディア: 単行本(ソフトカバー)
- 購入: 23人 クリック: 383回
- この商品を含むブログ (221件) を見る
- GCCが出力した小さなバイナリからsection headerを除去したりする話
仕様
仕様としては[ ]のネストには対応。でも[ ]の対応がおかしいようなプログラムを入れたときにはSEGVってもいいや。
工夫
とりあえず取り入れた工夫は以下の通り。ていうか上記サイトの説明そのまんま orz
またコンパイルの際には、
- セクションヘッダなど、実行に不要な情報は削る
- exitシステムコールを呼んだらそれ以降は決して実行されないので、それ以降の命令も削る
書いてみたコード。
]での巻き戻しのときに[]の対応を探さなくても良いよう、[の出現時にstackに戻り位置を記録。
ちなみにCFLAGS=-DDEBUGをつけてmakeするとデバッグ出力もできます(printfできないから一生懸命write…)。
#include <asm/unistd.h> #define _syscall1(type,name,type1) static inline type name(type1 arg1) { ? long _res; ? __asm__ volatile ("int $0x80" ? : "=a" (_res) ? : "a" (__NR_##name),"b" ((long)(arg1)) ? : "memory"); ? } #define _syscall3(type,name,type1,type2,type3) static inline type name(type1 arg1, type2 arg2, type3 arg3) { ? long _res; ? __asm__ volatile ("int $0x80" ? : "=a" (_res) ? : "0" (__NR_##name),"b" ((long)(arg1)), "c" ((long)(arg2)), "d" ((long)(arg3)) ? : "memory"); ? return (type)(_res); ? } static inline void exit(int arg1) __attribute((noreturn)); _syscall1(void, exit, int); _syscall3(int, open, char*, int, int); _syscall3(int, write, int, void*, int); _syscall3(int, read, int, void*, int); #ifdef DEBUG void print_num(int i) { char x; int y = 10000, k = 1, f = 0; do { x = i/y%10 + '0'; if (f || y == 1 || x != '0') { write(3,&x,1); f = 1; } } while (y /= 10); } #endif #define SIZE 32767 void _start(char *exec, char *file) __attribute__((noreturn,cdecl)); void _start(char *exec, char *file) { int argc = *(int*)((long)&exec-4); unsigned char *stack[SIZE]; unsigned char heap[SIZE]; unsigned char code[SIZE]; unsigned char **sp = stack; unsigned char *hp = heap+SIZE/2; unsigned char *ip = code; unsigned char *last; int i; for (i = 0; i <= SIZE; i++) { heap[i] = 0; code[i] = 0; } int fd = open(file,0,0); last = code + read(fd,code,SIZE); while (last > ip) { #ifdef DEBUG write(3,"ip: ",4); print_num(ip-code); write(3,"?tcmd: ",6); write(3,ip,1); #endif switch (*ip++) { case '>': hp++; break; case '<': hp--; break; case '+': (*hp)++; break; case '-': (*hp)--; break; case '.': write(1,hp,1); break; case ',': if(1 != read(0,hp,1)) *hp = 0; break; case '[': if (!*hp) { i = 1; do { if (*ip == '[') i++; if (*ip == ']' && !--i) break; ip++; } while (1); // while(last > ip++) ip++; } else *sp++ = ip-1; break; case ']': ip = *(--sp); break; } #ifdef DEBUG write(3,"?thp: ",5); print_num(hp-heap-SIZE/2); write(3," = ",3); print_num(*(hp-2)); write(3," ",1); print_num(*(hp-1)); write(3," [",2); print_num(*hp); write(3,"] ",2); print_num(*(hp+1)); write(3," ",1); print_num(*(hp+2)); write(3,"?n",1); #endif } exit(0); }
Makefileはこんな感じでしょか。ddでセクションヘッダを削った後、さらにperlスクリプトで余計なコードを削ります。perlの中に出てくる "cd 80" というのは、int80命令、システムコール呼び出しです。このスクリプトで最後のシステムコール呼び出し、つまり exit 以降を削ってます。ほんとはコード領域を単純に削ってるのでELFヘッダのサイズと合ってないはずなんですが、Linuxはそんなのヘッチャラのようなので、放置。
all: gcc -Os -fno-builtin -fno-ident -fomit-frame-pointer ${CFLAGS} -g -c a.c strip -gR .note.GNU-stack a.o ld --entry=_start -x a.o cp a.out tmp strip -s tmp strip -R=data tmp dd if=tmp of=mini bs=`readelf -S tmp | head -1 | perl -npe 's/^.*?([^ ]*):/hex($$1)/e'` count=1 rm tmp perl -e 'open(M,"+<mini"); join("",<M>) =~ /^(.*?xcd?x80)/; truncate(M,length($$&));' chmod +x mini ls -l mini
a.cはソースコード、a.outというのが普通(?)のバイナリ、miniというのがいろいろ削ったバイナリです。適当過ぎ。
書いてみて思ったこと。
gccって-Os つけても最短バイナリを吐く努力をしてくれる訳じゃないんですよね。なので最適化の都合か、不思議なことが色々起こります。例えば、最初のところでheapとcodeを0で初期化してますが、code[i] = 0を外すと、逆にサイズが10バイトくらい増えたりします。しかもダンプしてみると、初期化とは何の関係もないところで命令が冗長になっている。他にもswitchじゃなくてifで書くとでかくなったり、いろいろ試せば試すほど深みに。「どんだけ〜」って叫びたくなります。謎を解明するためにはgccを深追いしなくては…。
しっかし、ぶっちゃけ「もういいや、全部アセンブラで書くべきだった…」とか思い始めました。^^; まあ疲れたのでしばらくこれ以上やりません。多分w
どうせなら、自分を入力ファイルとして渡すと××するBrainf*uckインタプリタ、とかにすれば良かった。。。
# shinh度102%だ…。