Chapter 1 ： C/C++に於けるジャンプテーブルの実装に関する考察

 いきなりですが､コンピュータが動作する際に最も重要な働きをするのはCPUであると思います。
CPU(ノイマン型アーキテクチャの)はメモリからオペコードをフェッチしてそれを実行するという
まさに､コンピュータの中核をなす動作をするのですが､無論ハードを模倣するエミュレータにとっても
CPUと言うのは最も重要なパーツであって､エミュレータ製作の際にはCPUのエミュレーションコードを
書くのが最初の作業になるケースが一般的だと思われます。

 そこで､CPUのエミュレーションですが､大概はオペコードによって処理を割り振るわけです。
例えば､次のように

switch(opcode){
case xx:
	...
case xx:
	...
case xx:
	...
}

実装するわけです。

例えば､先頭１バイトがオペコードになっているケースに於いては
ここでcaseラベルが256個(ANSI C では256個が上限のようです､VCでは拡張機能としてその制限がなくなっています)
になるわけですが､ここでここで気になるのは､ちゃんとジャンプテーブルにコンパイルされるかという事です。
switchは if - elseif …のチェイン(cmp xx jz xx ...)に展開されることもしばしばで､
こんなものになってしまったらジャンプテーブルに比べて圧倒的に速度が低がするのは想像に硬くありません。
例えば､switch文の最後に

default:
	__assume(0); // (VCの拡張機能､ここに来ることは有り得ないと言う事)

等としてやるとVCに於いてはほぼ確実にジャンプテーブルに展開されるようになります(なるそうです…)。
まあ､取り敢えずはこれで効率の良いジャンプテーブルが生成できるわけですが､
もっとも､caseラベルにかけるのは定数のみで､そもそも連番でないと
if - elseif のチェインになってしまう可能性が出てきます。
要するにものすごく自由度が低いわけです。

まあ､この程度でも例えば6502などは充分これでジャンプデーブルが生成されるコードを書くことが出来るのですが､
ここで､CPUの内部ステートによりジャンプテーブルを切り替えしたい場合などが出てきた場合､
アセンブラのように

mov cur_tbl,tbl_1 ; 実際にはEAXレジスタでも経由させる
jmp dword ptr [cur_tbl+op_code*4]

のような実装は出来ず､switchをネストさせるかそのぐらいしか方法がなさそうです。
それで､またステートごとのジャンプテーブルが一部実装が被っていた場合など､かなり無駄な面倒をする羽目になります。
関数テーブルで実装と言う手もありますが､やはりcallよりもjmpの方がオーバーヘッドが少なそうです。

そこで､何とかC/C++でジャンプテーブルをダイレクトに実装できないかと考えてみようと思います。
(以下､環境はVCを仮定)

まず､アセンブラ上(MASM5.10以降を仮定)ではジャンプテーブルは

tbl dd lab_xx,lab_xx,lab_xx,...

...

lab_xx:
	...

...

jmp dword ptr tbl[opcode*4]

等と実装します。


ここで､C/C++(以下単にCと記述)でも

void *tbl[]={(void*)lab_xx,(void*)lab_xx,...}; // void * でなくとも良いでしょう

lab_xx:
	...

...

goto tbl[op_code];


等と言うように出来ればいいのでしょうけど､
どうやらCではラベルは変数に代入できないようです。
そもそもCのシンボルとして認識されていないみたいです。
それに､gotoのジャンプ先も即値(ラベル)じゃないといけないみたいです。

どうやらCではジャンプテーブルを表現出来なさそうです。
そこでちょっと妥協して､インラインアセンブラを導入してみましょう。

とりあえず単純なジャンプテーブル実装(List1)

#include <stdio.h>

int main(void)
{
	void *tbl[4];

	__asm{
		mov eax,offset lab_1
		mov tbl[0],eax
		mov eax,offset lab_2
		mov tbl[4],eax
		mov eax,offset lab_3
		mov tbl[8],eax
		mov eax,offset lab_4
		mov tbl[12],eax
	};

	// この2は0-3までなら何でも良いです
	__asm mov eax,2
	__asm jmp tbl[eax*4]

lab_1:
	printf("lab_1に来たよ\n");
	goto end_lab;
lab_2:
	printf("lab_2に来たよ\n");
	goto end_lab;
lab_3:
	printf("lab_3に来たよ\n");
	goto end_lab;
lab_4:
	printf("lab_4に来たよ\n");
	goto end_lab;

end_lab:
	return 0;
}

なんと言うか､これはCプログラムとは言いませんね…
まあ､一応ジャンプテーブルは実装できているような感じです。
しかし､ラベルが関数の外に追い出せません。
どうやら､ラベルが有効なのは関数の中のみのようです。
全体的に認識できるシンボル､といえば他には関数があります。
そこで､関数を使って実装してみましょう。

関数を使った実装(?) (List2)

int foo()
{
	printf("foo\n");

#ifdef _DEBUG
	__asm pop edi
	__asm pop esi
	__asm pop ebx
	__asm add esp,64	
	__asm mov esp,ebp
	__asm pop ebp
#else
	__asm add esp,16
#endif

	return 0;
}

int main(void)
{
	__asm jmp foo
	return 0;
}

すみません。これは無かったことで…
あまりにもあほ過ぎます。
最悪なプログラミングコンテストで優勝しそうです。
一応敢えてこれをジャンプテーブルとして実装してみます。

関数を使ったジャンプテーブル実装(?) (List3)

#include <stdio.h>

int foo0()
{
	printf("foo4\n");
	return 0;
}

int foo1()
{
	printf("foo1\n");
	return 0;
}

int foo2()
{
	printf("foo2\n");
	return 0;
}

int foo3()
{
	printf("foo3\n");
	return 0;
}

int main(void)
{
	static void *tbl[]={(void*)foo0,(void*)foo1,(void*)foo2,(void*)foo3};

#ifdef _DEBUG
	__asm pop edi
	__asm pop esi
	__asm pop ebx
	__asm add esp,64
	__asm mov esp,ebp
	__asm pop ebp
#else
	__asm add esp,16
#endif

	__asm mov eax,2
	__asm jmp tbl[eax*4]

	return 0;
}

えー､鋭い方はこれがジャンプテーブル1回しか実装できないことにお気づきでしょう。
そこで､以下のように実装してみました。

関数を使ったジャンプテーブル暫定版(List4)

#include <stdio.h>

#ifdef _DEBUG
#define stack_adjust() \
	__asm pop edi \
	__asm pop esi \
	__asm pop ebx \
	__asm add esp,64 \
	__asm mov esp,ebp \
	__asm pop ebp
#else
#define stack_adjust() _asm add esp,16
#endif

#define tbl_entry(arg) \
	void arg() \
	{ \
		stack_adjust();

#define end_entry \
	__asm jmp main_loop \
	}

#define goto(x,y) \
	__asm mov eax,y \
	__asm jmp x[eax*4]

void *main_loop;

tbl_entry(foo0)
	printf("foo0\n");
end_entry

tbl_entry(foo1)
	printf("foo1\n");
end_entry

tbl_entry(foo2)
	printf("foo2\n");
end_entry

tbl_entry(foo3)
	printf("foo3\n");
end_entry

int main(void)
{
	static void *tbl[]={(void*)foo0,(void*)foo1,(void*)foo2,(void*)foo3};
	static int dat[]={0,2,1,3,2,0,999},cur,count;

	__asm mov eax,offset loop_start
	__asm mov main_loop,eax

loop_start:
	cur=dat[count++];
	if (cur!=999){
		goto(tbl,cur);
	}

	return 0;
}

ここまできたら呆れるとかを通り越してむしろかっこいいです。
前の方をヘッダにでもまとめればCライクに書けるかも知れません。
(ほんと良く分からなくなってきた…)
まあ､JMPで飛んでる割にはスタック調整とかやってて関数テーブルと殆ど変わらないのではないかと言う
意見もあるでしょうが､それはこの際'無視'しましょう。
馬鹿馬鹿しさにこそ価値があるんです(と言うのは嘘ですが)…
当初の目的と大きく外れてきましたが､最終的にこれをオブジェクト指向に適応させるための
布石として考えてもらえればよいです。
まあ､他の開き直り案として､完全にフラットな所での実装も考えられますが､
恥ずかしいのでやめておきます。

とりあえず､最近のプログラミングにおいてはクラスで実装する場合が多いので､
クラスのメンバ関数でこれが出来るように改良してみます。
とりあえず､CPUエミュレータを実装する場合を例として､cpu::exec()関数がジャンプテーブルで
オペコードを実行する場合を考えてみます。

クラス内ジャンプテーブルの実装(List5)

#include <stdio.h>
#include <stddef.h>

class cpu
{
public:
	cpu();
	void exec();

	void main();
	void ops();
private:
	void *main_loop,*tbl[4];
};

static int offset_main,offset_ops,_this;

cpu::cpu()
{
	offset_main=offsetof(cpu,main_loop);
	offset_ops=offsetof(cpu,tbl);
	main();
	ops();

	_this=(int)this;
}

void cpu::main()
{
	static int dat[]={0,2,3,1,2,0,999};
	static int count=0,tmp;

	__asm mov eax,offset _main
	__asm mov ebx,offset_main
	__asm mov [ecx+ebx],eax
	return;

_main:
	tmp=dat[count++];
	if (tmp!=999){
		__asm mov ecx,_this
		__asm mov eax,tmp
		__asm mov ebx,offset_ops
		__asm add ebx,ecx
		__asm jmp dword ptr [ebx+eax*4]
	}
}

void cpu::ops()
{
	__asm mov ebx,offset_ops
	__asm add ebx,ecx
	__asm mov eax,offset _op1
	__asm mov [ebx],eax
	__asm mov eax,offset _op2
	__asm mov [ebx+4],eax
	__asm mov eax,offset _op3
	__asm mov [ebx+8],eax
	__asm mov eax,offset _op4
	__asm mov [ebx+12],eax
	return;

_op1:
	printf("op1を実行しました\n");
	__asm mov ebx,offset_main
	__asm add ebx,_this
	__asm jmp dword ptr [ebx]
_op2:
	printf("op2を実行しました\n");
	__asm mov ebx,offset_main
	__asm add ebx,_this
	__asm jmp dword ptr [ebx]
_op3:
	printf("op3を実行しました\n");
	__asm mov ebx,offset_main
	__asm add ebx,_this
	__asm jmp dword ptr [ebx]
_op4:
	printf("op4を実行しました\n");
	__asm mov ebx,offset_main
	__asm add ebx,_this
	__asm jmp dword ptr [ebx]
}

void cpu::exec()
{
	__asm mov ebx,offset_main
	__asm jmp dword ptr [ecx+ebx]
}

int main()
{
	cpu _cpu;
	_cpu.exec();

	return 0;
}

スタック無理やり補正とか使ってないところが何となくさっきよりは好感が持てましょうか…
最初にジャンプテーブルの初期化をやっているのがミソです。
こうすることで､殆どペナルティ無しにジャンプテーブルが実装できるはずです。
オペコードはops()の中に追加して､先頭でテーブルに登録するところに書き足せばOKです。
先ほどまでは､アセンブラで書いても殆ど変わらなかったようにも見えますが､
こちらは一応クラスが使えます。オブジェクト指向の中においても差ほど違和感無く取り込めるに違いありません。
(冗談ですよ…念のため)
メンバ関数を使った実装については､先ほどの繰り返しにもなりますし､
色々面倒なので､興味のある方は各自実装してみてください。

結局何が言いたかったのか…うーん､私にも良く分かりません。
C/C++ジャンプテーブル(もしくはまがいの事)を実装するのは難しい…と言うことぐらいでしょうか?
結論は出さない方が面白そうですし…

Copyright(C) Hii 2001