ファミコンエミュ(未完成)公開

http://sakurai.s59.xrea.com/as3/Main.swf

とりあえず、公開しときます。
マリオブラザーズです。
音はなりません。
フラッシュの画面をクリックして、着合いいれて、エンターキーを押すと
ゲームが始まります。zでジャンプするとバグります。
カーソルキーで移動ですかねぇ。
10フレームに1回だけ描画してます。
ものすごく重いです。

四則演算、スタックマシンのベンチマーク

                 O    i  Oi  r   rO  ri  riO
元         : 570 460 381 361 360 350 311 310
読込       : 571 531 370 360 361 371 320 340
最適化     : 371 310 380 321 290 260 291 260
関数化     : 461 381 370 320 311 300 290 261
動的       : 120 err 110 err 350 err 350 err
動的ASM    :  30 err  20 err  30 err  30 err
動的読込   : 110 err 120 err 360 err  60 err
トランス   : 101  80  90  70  70  60  70  60
トランスASM:  30  20  41  30  30  30  30  30

とってみました。
トランスレータ速いですねぇ。
さらに、CPUのスタックを使ってやると速いってことがわかりました。
動的というか、実行時コンパイルは、最適化かけるとエラーでます。


で、なんだっけ、、、
ActionScript3.0にコンパイルするには、トランスレータ書けば十分じゃないのかという
ざっとした、結論が得られました。


てことは、6502のアセンブラ作るって話になるのか。。。
というか、NESの開発環境を作ることになるのか。
できるのかよ!

;
; スタックマシン用プログラム
;

PUSHI	1
PUSHI	2
ADD
PUSHI	10
MUL
PUSHI	1
SUB
PRINTI
RET

これを読み込んで、Dのソースを出力する。トランスレータ

import std.string;
import std.file;
int main(char argv) {
	// ファイル読み込み
	char str = cast(char)read(argv[1]);
	// トランスレート
	printf("enum { MAX_STACK = 200 };\n");
	printf("int stack[MAX_STACK];\n");
	printf("int sp = MAX_STACK - 1;\n");
	printf("int main() {\n");
	foreach (char line; str.split("\n")) {
		char[] c = line.split();
		if (c.length == 0) continue;
		switch (c[0]) {
		case "POP": printf("\t++sp;\n"); break;
		case "PUSHI": printf("\tstack[sp--] = %.*s;\n", c[1]); break;
		case "ADD": printf("\tstack[sp+2] = stack[sp+2] + stack[sp+1]; ++sp;\n"); break;
		case "SUB": printf("\tstack[sp+2] = stack[sp+2] - stack[sp+1]; ++sp;\n"); break;
		case "MUL": printf("\tstack[sp+2] = stack[sp+2] * stack[sp+1]; ++sp;\n"); break;
		case "PRINTI": printf("\tstack[sp+1] = printf(\"%%d\\n\", stack[sp+1]);\n"); break;
		case "RET": break;
		default: break;
		}
	}
	printf("\treturn 0;\n");
	printf("}\n");
	return 0;
}

で、出力結果。

enum { MAX_STACK = 200 };
int stack[MAX_STACK];
int sp = MAX_STACK - 1;
int main() {
	stack[sp--] = 1;
	stack[sp--] = 2;
	stack[sp+2] = stack[sp+2] + stack[sp+1]; ++sp;
	stack[sp--] = 10;
	stack[sp+2] = stack[sp+2] * stack[sp+1]; ++sp;
	stack[sp--] = 1;
	stack[sp+2] = stack[sp+2] - stack[sp+1]; ++sp;
	stack[sp+1] = printf("%d\n", stack[sp+1]);
	return 0;
}

分岐とか考えると、もうちょっと複雑になりますが、まぁ、こんくらいで。

スタックマシンの動的コンパイル

気力がなくなったので、ちゃんとした文章になってませんが、、、。

NYOットやろうぜ
http://members.at.infoseek.co.jp/DrHell/ps1/index.html

yaneVM2i386.cpp 等を参考にして作ってみました。

/*
 * スタックマシン動的コンパイル&実行 for d言語
 */
enum { MAX_STACK = 1024, MAGIC = 0x12345678 };

int sp;
int stack[MAX_STACK];
ubyte program[0x1000];
ubyte *pcc = program;

void compile(void *start, void *end, int num) {
	int size = end - start;
	ubyte* rc = cast(ubyte*)start;

	// retを探して、消す
	for (int i = 1;;i++) {
		if(rc[size - i] == 0xc3) {
			size -= i;
			break;
		}
	}

	// コピー
	for(int i = 0; i < size;i++) pcc[i] = rc[i];

	for(int i = 0; i < size; i++) {
		// マジックナンバーの修正
		if (*(cast(int*)&pcc[i]) == MAGIC) {
			*(cast(int*)&pcc[i])=num; i += 4;
		}
		// 相対コールの値を修正
		if (pcc[i] == 0xe8) {
			int *ip = (cast(int*)&pcc[i+1]);
			*ip = *ip - (pcc - start);
		}
	}
	pcc += size;
}

// 実行コード                                               コンパイル関数
void _pop() {++sp;}                                         void pop()       { compile(&_pop, &pop,0);}
void _pushi() {stack[sp--] = MAGIC;}                        void pushi(int i){ compile(&_pushi, &pushi, i);}
void _add() {stack[sp+2] = stack[sp+2] + stack[sp+1]; ++sp;}void add()       { compile(&_add, &add, 0);}
void _sub() {stack[sp+2] = stack[sp+2] - stack[sp+1]; ++sp;}void sub()       { compile(&_sub, &sub, 0);}
void _mul() {stack[sp+2] = stack[sp+2] * stack[sp+1]; ++sp;}void mul()       { compile(&_mul, &mul, 0);}
void _div() {stack[sp+2] = stack[sp+2] / stack[sp+1]; ++sp;}void div()       { compile(&_div, &div, 0);}
void _printi() {printf("%d\n", stack[sp+1]);}               void printi()    { compile(&_printi, &printi, 0);}
void ret() {pcc[0] = 0xc3; pcc[1] = pcc[2] = pcc[3] = 0xcc; pcc += 4;}// ret int3 int3 int3 4byteアラインしておく。

int main() {
	sp = MAX_STACK - 1;

	printf("(1 + 2)*10-1=");
	// 動的コンパイル
	pushi(1);
	pushi(2);
	add();
	pushi(10);
	mul();
	pushi(1);
	sub();
	printi();
	ret();

	// 実行
	void function() exec = cast(void function())program;
	exec();
	return 0;
}

エミュレータや、VM(Virtual Machine)では、動的コンパイルにより高速化されていることをよく聞きます。
JIT (Just In Time compile)等と呼ばれているものです。
しかしながら、簡単なサンプルソースとなるとなかなか見つかりません。
そこで、D言語を使った簡単な動的コンパイルサンプルソースを作りました。
対象とするのは、四則演算と画面出力だけの単純なスタックマシンです。
簡単にするため、元となるスタックマシンの中間コードはなくて、
直接実行時にコンパイルして、実行するだけのものです。


まずは、main関数を見てください。
コンパイルは、pop(),pushi(),add(),sub(),mul(),printi(),ret()関数を呼び行います。
コンパイルされた結果は、programという配列内に保存されます。
実行するには、program配列のアドレスを関数ポインタに代入して、関数を実行します。


さて、コンパイルはどのようにされているのでしょうか?
_pop,pop関数を見てみましょう。
void _pop() {++sp;} void pop() { compile(&_pop, &pop,0);}
_popはスタックポインタを1増やす関数です。
pop関数はcompile関数を呼び出してコンパイルする関数です。
コンパイルするには、関数の中身をコピーするので、関数の範囲を調べる必要があります。
関数の範囲は、関数のポインタから、次の定義されたもの(この場合は関数)までになります。
そのため、compile関数には、_popと、_pop関数の次に定義されているpop関数のアドレスを渡しています。


では、compile関数内を見てみましょう。
まず、関数のサイズを求めます。
次に、関数の最後は必ず、マシン語のret(0xc3)があるのですが、これがあると、次々に実行することが出来ないので
消します。そのために、retの前までをコピーするサイズにします。
次に、範囲をコピーします。
popのような関数ならば、これでOKです。
しかし、他の関数を実行するには問題があります。
それが、マジックナンバーの修正と、相対コールの修正です。


マジックナンバーの修正


pushi等で指定された値を入れるために行います。
例えば、pushiを行うには、毎回違う値が入る必要があります。
しかし、コンパイルされたプログラムは固定である必要があります。
その元の値を探して、正しい値に置き換えます。


マジックナンバーの検索


この例ではマジックナンバーには0x12345678と言った特殊な値を入れておき、
その0x12345678を検索するだけです。


この例の検索は不完全です。
マジックナンバー以外の個所に0x12345678があっても置き換えてしまいます。
これを汎用的にするには、マシン語のコードをきちんとスキャンしていく必要があります。


相対コールの修正


相対アドレスで関数呼び出しを行うcall命令のアドレスのズレを修正します。
どれだけずれているかというと、コピー元とコピー先のアドレス分です。
つまり、startからpccを引いたものを、現在の値から引いてあげればよいのです。


call命令の検索


call命令は0xe8から始まります。
ここでは単純にするため、0xe8を見つけたらcall命令であると断定しています。
これを汎用的にするには、マシン語のコードの長さを求めながら、スキャンする必要があります。


関数から戻る


さて、プログラムのコンパイルの仕方はわかりました。
あとは、実行後、コンパイルコードから正しく戻ってくるようにします。
そのためのコードをコンパイルするのがret()関数です。これは、マシン語のret(0xc3)を入れることで行います。
その後に、0xccが3つ入っているのは、4バイトアラインするためですので、なくても動作します。


さぁ、retを入れたことで1つの関数が完成しました。
あとは、先ほど説明したように、program配列のアドレスを関数ポインタに代入して、関数を実行すればOKです。