4ビット仮想CPUを考える
学研の GMC-4 や Intel 4004 に思いをはせながら、4 ビット命令を搭載した仮想 CPU を考えました。チューリング完全にするだけなら Brainfuck のようにで 3 ビット命令だけでも通用するけど、命令のビット長が中途半端になるので扱いやすい 4 ビットにしました。ポインタ以外のレジスタなし、サブルーチンコールなし、命令コードの格納場所とユーザランドメモリは連続している、という設定です。命令バイナリのバイト配列はビッグエディアンです。
1. CPU 命令一覧
サポートするニーモニックは以下のとおり。4ビット命令なので、1バイト(8ビット)の半分。 つまり16個の命令から成ります。
0 zero 値を0に初期化する
1 inc 値をインクリメント
2 dec 値をデクリメント
3 add 値に前の値を足して代入する
4 sub 値に前の値を引いて代入する
5 swap 値と前の値を入れ替える
6 copy 値に前の値をコピーする
7 not 値をNOT演算して代入する
8 pzero ポインタ位置を0に初期化する
9 pinc ポインタ位置をインクリメント
A pdec ポインタ位置をデクリメント
B jump 値が0なら次のラベルへジャンプ
C back 値が0なら前のラベルへジャンプ
D get 値に入力値を代入してpinc
E put 値を出力してpinc
F label ラベル
コーディングしながら思ったけど、0x0 をラベルにすれば良かったかな。
2. サンプルコード
上の表を見ながら、簡単な計算プログラムを考えてみます。
2.1. 足し算電卓
二つの値を入力し、結果を印字するプログラムです。
get # 一つ目を入力
get # 二つ目を入力
pdec # ポインタを一つ前に戻して
add # 加算して
put # 印字
バイナリで言うと「DD A3 E」。後述のアセンブラでアセンブルするとバイト単位アクセスの都合上、末尾にラベルの「0xF」が付きます。
解説
ありゃ、これは簡単すぎましたね。5命令で実現できてしまいました。
| || ||
| || 0 | 1 | 2 ||
-------------------------
D | get || 3 |[ ]| || <=== 3 入力
D | get || 3 | 2 |[ ]|| <=== 2 入力
A | pdec || 3 |[2]| ||
3 | add || 3 |[5]| ||
E | put || 3 |[5]| || ===> 5 出力
2.2. かけ算電卓
足し算は簡単すぎたので、今度はかけ算に挑戦しようと思います。バイナリで言うと「DD 09 FA 3A A2 B9 99 0C F9 9E」。条件分岐と繰りかえし処理があるし、評価用サンプルにはちょうど良いかもしれません。
#かけ算を行うプログラム
get # 一つ目の値
get # 二つ目の値
zero
pinc
label
pdec
add
pdec
pdec
dec
jump # 一つ目の値が 0 なら、ループを抜けて結果の印字処理へ
pinc
pinc
pinc
zero
back # 一つ目の値が 0 になるまで、上のラベルへ戻る
#結果の印字処理
label
pinc
pinc
put # 印字
解説
「3」「2」と入力した場合、下記のように処理を行い、最終的に 3 × 2 の答え「6」を印字します。 命令実行直後のメモリの値を併記しました。[ ] は、ポインタを示しています。
| || 1 回目 || 2 回目 || 3 回目 || ラスト ||
| || 0 | 1 | 2 | 3 || 0 | 1 | 2 | 3 || 0 | 1 | 2 | 3 || 0 | 1 | 2 | 3 ||
--------------------------------------------------------------------------------
D | get || 3 |[ ]| | || | | | || | | | || | | | || <=== 3 入力
D | get || 3 | 2 |[ ]| || | | | || | | | || | | | || <=== 2 入力
0 | zero || 3 | 2 |[0]| || | | | || | | | || | | | ||
9 | pinc || 3 | 2 | 0 |[ ]|| | | | || | | | || | | | ||
F | label || 3 | 2 | 0 |[ ]|| 2 | 2 | 2 |[0]|| 1 | 2 | 4 |[0]|| | | | ||
A | pdec || 3 | 2 |[0]| || 2 | 2 |[2]| 0 || 1 | 2 |[4]| 0 || | | | ||
3 | add || 3 | 2 |[2]| || 2 | 2 |[4]| 0 || 1 | 2 |[6]| 0 || | | | ||
A | pdec || 3 |[2]| 2 | || 2 |[2]| 4 | 0 || 1 |[2]| 6 | 0 || | | | ||
A | pdec ||[3]| 2 | 2 | ||[2]| 2 | 4 | 0 ||[1]| 2 | 6 | 0 || | | | ||
2 | dec ||[2]| 2 | 2 | ||[1]| 2 | 4 | 0 ||[0]| 2 | 6 | 0 || | | | ||
B | jamp ||[2]| 2 | 2 | ||[1]| 2 | 4 | 0 ||[0]| 2 | 6 | 0 || | | | ||
9 | pinc || 2 |[2]| 2 | || 1 |[2]| 4 | 0 || | | | || | | | ||
9 | pinc || 2 | 2 |[2]| || 1 | 2 |[4]| 0 || | | | || | | | ||
9 | pinc || 2 | 2 | 2 |[ ]|| 1 | 2 | 4 |[0]|| | | | || | | | ||
0 | zero || 2 | 2 | 2 |[0]|| 1 | 2 | 4 |[0]|| | | | || | | | ||
C | back || 2 | 2 | 2 |[0]|| 1 | 2 | 4 |[0]|| | | | || | | | ||
F | label || | | | || | | | || | | | ||[0]| 3 | 6 | 0 ||
9 | pinc || | | | || | | | || | | | || 0 |[3]| 6 | 0 ||
9 | pinc || | | | || | | | || | | | || 0 | 3 |[6]| 0 ||
E | put || | | | || | | | || | | | || 0 | 3 |[6]| 0 || ===> 6 出力
- メモリの0番地と1番地にそれぞれ計算したい値を入力する。
- 2番地を0で初期化する。
- 2番地に1番地の値を加算する。
- 0番地の値をデクリメント(マイナス1)する。
- 0番地の値が0になるまで、3から4を繰りかえす。上記例の場合は3回繰りかえす。
- 結果が2番地に貯まるので、それを印字して終了。
3. プリプロセッサ
コメントと余分な空白文字を削除してやれば良いいので、下記のようになります。空行は次項のアセンブラによって読み飛ばされるので、この時点で処理する必要はありません。
perl -e 'for(){s/#.*$|[ \t]//g;print;}' < kakezan.code > kakezan.s
4. アセンブラ
キーワードをバイナリ値に置換しているだけです。 このアセンブラでアセンブルすれば、仮想 CPU 用のバイナリ・ファイルが生成されます。
#include
#include
#include
int main(int argc, char** argv)
{
char s[256];
char n, nn=0;
FILE *f;
int c=0;
if (argc!=2)
puts("Usage: ./asm output < source.s");
else {
if ((f = fopen(argv[1], "wb"))==NULL)
return 1;
while(fgets(s, sizeof(s), stdin) != NULL){
if (!strcmp(s, "zero\n")) {n = 0x0;}
else if (!strcmp(s, "inc\n")) {n = 0x1;}
else if (!strcmp(s, "dec\n")) {n = 0x2;}
else if (!strcmp(s, "add\n")) {n = 0x3;}
else if (!strcmp(s, "sub\n")) {n = 0x4;}
else if (!strcmp(s, "swap\n")) {n = 0x5;}
else if (!strcmp(s, "copy\n")) {n = 0x6;}
else if (!strcmp(s, "not\n")) {n = 0x7;}
else if (!strcmp(s, "pzero\n")) {n = 0x8;}
else if (!strcmp(s, "pinc\n")) {n = 0x9;}
else if (!strcmp(s, "pdec\n")) {n = 0xA;}
else if (!strcmp(s, "jump\n")) {n = 0xB;}
else if (!strcmp(s, "back\n")) {n = 0xC;}
else if (!strcmp(s, "get\n")) {n = 0xD;}
else if (!strcmp(s, "put\n")) {n = 0xE;}
else if (!strcmp(s, "label\n")) {n = 0xF;}
else {n = -1;}
if (n>=0x0&&n<=0xF) {
c++;
if (c%2)
nn = n<<4;
else {
nn += n;
fwrite(&nn, sizeof(char), 1, f);
}
}
}
if (c%2) {
nn += 0xF;
fwrite(&nn, sizeof(char), 1, f);
}
fclose(f);
}
return 0;
}
4.1. 使い方
#ビルド
gcc -o asm asm.c
#アセンブルの実行。kakezan.exe が生成されます。
./asm kakezan.exe < kakezan.s
バイナリファイルの中身を確認するには xxd コマンドを使用します。
#ちゃんと出来ているかな
$ xxd kakezan.exe
0000000: dd09 fa3a a2b9 990c f99e ...:......
5. エミュレータ
バイナリファイルをコマンドライン引数に渡せば、CPU の動作をエミュレートして実行します。
#include
int main(int argc, char** argv)
{
const int RAMSIZE = 256;
int p; / RAM Pointer /
int *pp; / Program Pointer /
int ps; / Program Size /
int r[RAMSIZE]; / RAM /
FILE *f;
int c, t;
if ((f = fopen(argv[1], "r")) == NULL) return 1;
// Load binary to RAM
p = r;
while ((c = fgetc(f)) != EOF) {
c &= 0xFF;
*p++ = c >> 4;
*p++ = c & 0xF;
}
fclose(f);
ps = p - r;
// Execute
for (pp=r; pp-r<ps; pp++) {
// printf("%1x[%d]: %d %d %d %d\n",
// *pp, p-r-ps, r[ps], r[ps+1], r[ps+2], r[ps+3]);
switch (pp) {
case 0x0: p = 0; break;
case 0x1: (p)++; break;
case 0x2: (p)--; break;
case 0x3: *p += *(p-1); break;
case 0x4: *p -= *(p-1); break;
case 0x5: t = *p; *p = *(p-1); *(p-1) = t; break;
case 0x6: *p = *(p-1); break;
case 0x7: *p = !(p); break;
case 0x8: p = r; break;
case 0x9: p++; break;
case 0xA: p--; break;
case 0xB: if (p==0) while(pp!=0xF) pp++; break;
case 0xC: if (p==0) while(pp!=0xF) pp--; break;
case 0xD: scanf("%d", p++); break;
case 0xE: printf("%d\n", *p++); break;
default: break;
}
}
return 0;
}
r が int なので、char な2命令1セットが実メモリに展開される場合、sizeof(int) バイトに拡張されてしまいます。
リトルエディアンの処理系だとビッグエディアンなバイナリとメモリにロードされたイメージとでは差が出てしまいます。実害はないけど、ちょっと変な仕様だなと思いました。
5.1. 使い方
変なバイナリを食わせると危険ですので、自己責任で実行してください。
#ビルド
$ gcc -o emu emu.c
#実行
$ ./emu kakezan.exe
123
321
39483
#bc を使って、答え合わせ
$ echo 123 * 321 | bc
39483
#よし。