Brainf*ck 小さなインタプリタ〜アセンブラバージョン

書かないと言っていたのに書いてしまいました。へたれなのでNASMじゃなくgasです。i386

ソースコード

	.file	"bf.s"
	.text
.globl _start
	.type	_start, @function
_start:
	movl	8(%esp), %ebx		/* filename (argv[1]) */
	movl	$0xffff, %ecx		/* stack size */
	subl	%ecx, %esp		/* alloc stack */
	movl	%ecx, %edx
	shrl	$1, %edx		/* max code size = stack size/2 */
.INIT:	
	movb	$0, (%esp,%ecx)
	loop	.INIT

	xorl	%eax, %eax
	movb	$5, %al			/* open filename */
	int	$0x80
	movl	%eax, %ebx
	
	movb	$3, %al			/* read */
	movl	%esp, %ecx
	int	$0x80

	movl	%esp, %esi		/* esi: inst ptr */
	leal	(%esp,%eax), %edi	/* edi: last code ptr */
	addl	%edx, %ecx		/* ecx: heap ptr */
	xorl	%ebp, %ebp		/* ebp: skip level */
	
.EXEC1:
	xorl	%eax, %eax
	movw	$0x01, %dx		/* edx = always 1 */
	cmpl	%esi, %edi
	jle	.EXIT
	movb	(%esi), %al		/* load command to eax */
	incl	%esi			/* move code ptr to next */

	test	%ebp, %ebp
	jnz	.C7			/* skip mode */
.C1:	
	cmpb	$43, %al		/* '+' */
	jne	.C2
	incb	(%ecx)
.C2:
	cmpb	$45, %al		/* '-' */
	jne	.C3
	decb	(%ecx)
.C3:
	cmpb	$62, %al		/* '>' */
	jne	.C4
	inc	%ecx
.C4:
	cmpb	$60, %al		/* '<' */
	jne	.C5
	decl	%ecx
.C5:
	cmpb	$46, %al		/* '.' */
	jne	.C6
	movb	$4, %al			/* write */
	movb	$1, %bl
	int	$0x80
.C6:
	cmpb	$44, %al		/* ',' */
	jne	.C7
	movb	$0xff, (%ecx)	/* failure code */
	movb	$3, %al			/* read */
	xorl	%ebx, %ebx
	int	$0x80
.C7:
	cmpb	$91, %al		/* '[' */
	jne	.C8
	cmpb	$0, (%ecx)
	je	.SKIP
	pushl	%esi
	jmp	.EXEC1
.SKIP:
	incl	%ebp
.C8:
	cmpb	$93, %al		/* ']' */
	jne	.EXEC1
	testl	%ebp, %ebp
	jnz	.SKIP2
	popl	%esi
	decl	%esi
	jmp	.EXEC1
.SKIP2:
	decl	%ebp
	jmp	.EXEC1
.EXIT:
	incl	%eax
	xorl	%ebx,%ebx
	int	$0x80

Makefile

前のをほぼそのまま流用したので意味ないところもあるかも。readelfが落ちないようにELFヘッダの一部を00で上書きするようにしました。

all:
	gcc -Os -fno-builtin -fno-ident -fomit-frame-pointer ${CFLAGS} -c bf.s
	ld --entry=_start -x bf.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($$&)); seek(M,0x20,0); print M "\x00"x4; seek(M,0x2e,0); print M "\x00"x6'
	chmod +x mini
	ls -l mini

出来上がり

「mini」をhexdumpしたところ。223バイトなり。なるべく4バイト則値は書かないとか(256バイトを切ればどこでも8ビット則値で相対ジャンプできるし)工夫はしているものの、命令リファレンスも見ずに適当に書いているので、まだまだ小さくする余地は残っていることでしょう。

00000000  7f 45 4c 46 01 01 01 00  00 00 00 00 00 00 00 00  |.ELF............|
00000010  02 00 03 00 01 00 00 00  54 80 04 08 34 00 00 00  |........T...4...|
00000020  00 00 00 00 00 00 00 00  34 00 20 00 01 00 00 00  |........4. .....|
00000030  00 00 00 00 01 00 00 00  00 00 00 00 00 80 04 08  |................|
00000040  00 80 04 08 df 00 00 00  df 00 00 00 05 00 00 00  |................|
00000050  00 10 00 00 8b 5c 24 08  b9 ff ff 00 00 29 cc 89  |.....\$......)..|
00000060  ca d1 ea c6 04 0c 00 e2  fa 31 c0 b0 05 cd 80 89  |.........1......|
00000070  c3 b0 03 89 e1 cd 80 89  e6 8d 3c 04 01 d1 31 ed  |..........<...1.|
00000080  31 c0 66 ba 01 00 39 f7  7e 50 8a 06 46 85 ed 75  |1.f...9.~P..F..u|
00000090  2d 3c 2b 75 02 fe 01 3c  2d 75 02 fe 09 3c 3e 75  |-<+u...<-u...<>u|
000000a0  01 41 3c 3c 75 01 49 3c  2e 75 06 b0 04 b3 01 cd  |.A<<u.I<.u......|
000000b0  80 3c 2c 75 09 c6 01 ff  b0 03 31 db cd 80 3c 5b  |.<,u......1...<[|
000000c0  75 09 80 39 00 74 03 56  eb b6 45 3c 5d 75 b1 85  |u..9.t.V..E<]u..|
000000d0  ed 75 04 5e 4e eb a9 4d  eb a6 40 31 db cd 80     |.u.^N..M..@1...|

DOS用98インタプリタに勝てないのはELFヘッダや、スタックやらの初期化コード、ファイル読み込みを含んでいるから、ということにしておこう。。。

こうやって見るとELFヘッダ内の 0000 とか多いのが無駄に思えてきますが…ELF GOLFまではしない…多分。どっちかって言うとある程度小さなバイナリをgccで簡単に吐けるような枠組みを作るのが目的だったので本末転倒……でもついやりたくなってしまうんだよなあ。

テスト

kazuhoさんの素数探索プログラムを動かしてみました。

% time ./mini  prime.b
97 89 83 79 73 71 67 61 59 53 47 43 41 37 31 29 23 19 17 13 11 07 05 03 02
./mini prime.b  1.51s user 0.00s system 99% cpu 1.515 total

大丈夫そうです。

ちなみに、前のCで作ったバイナリより1.5倍ほど遅いです。Pentium Mで比較すると3〜4倍も遅くなりました。分岐予測の精度のためでしょうか。前のCのは命令ごとの分岐をswitch文で書いたら二分探索っぽいコードを吐いてくれていたのに、上のでは一個ずつ単純に比較する(しかも else if になっていないので毎回全部の比較を通る)わけなので、当然ですかね。