小さなBrainf*ckインタプリタに挑戦

Brainf*ck(何となく伏せ字)という言語があるそうな。たった8つの命令しかないのに、(理論上)あらゆるプログラムが書ける(というかチューリング完全な)言語です。詳しくは Wikipediaの記事などを。

8つしか命令がない、引数もないので、コンパイラインタプリタを作るのがとても簡単。というわけで作ってみました。
しかしただ作るだけでは面白くないので、なるべく小さくすることに挑戦してみます。
小さくと言っても、

とかがあるらしいですが、後者のバイナリを小さする方に挑戦してみました。
言語・環境としてはC (gcc)、Linux i386で挑戦。とりあえずgccで出来る範囲で頑張る、ということにします。

参考

仕様

仕様としては[ ]のネストには対応。でも[ ]の対応がおかしいようなプログラムを入れたときにはSEGVってもいいや。

工夫

とりあえず取り入れた工夫は以下の通り。ていうか上記サイトの説明そのまんま orz

  • glibcは使わないで直接システムコールを叩く(おかげでその定義がちょっとややこしい)
  • main関数はなし、_startから直接実行が始まる

またコンパイルの際には、

  • セクションヘッダなど、実行に不要な情報は削る
  • 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というのがいろいろ削ったバイナリです。適当過ぎ。

で、いざmake。

Fedora 7のgccコンパイルしたところ、a.outは712バイト、miniは337バイトのバイナリになりました。んー、中途半端…

書いてみて思ったこと。

gccって-Os つけても最短バイナリを吐く努力をしてくれる訳じゃないんですよね。なので最適化の都合か、不思議なことが色々起こります。例えば、最初のところでheapとcodeを0で初期化してますが、code[i] = 0を外すと、逆にサイズが10バイトくらい増えたりします。しかもダンプしてみると、初期化とは何の関係もないところで命令が冗長になっている。他にもswitchじゃなくてifで書くとでかくなったり、いろいろ試せば試すほど深みに。「どんだけ〜」って叫びたくなります。謎を解明するためにはgccを深追いしなくては…。

しっかし、ぶっちゃけ「もういいや、全部アセンブラで書くべきだった…」とか思い始めました。^^; まあ疲れたのでしばらくこれ以上やりません。多分w
どうせなら、自分を入力ファイルとして渡すと××するBrainf*uckインタプリタ、とかにすれば良かった。。。

# shinh度102%だ…。