【低レイヤ入門】C言語で作る自作VMに入力バッファを追加する: Enterまでの文字をメモリに保存する | UNIX Cafe

前回は、小さな自作VM上で動く外部プログラムに、起動メッセージとhelp表示を追加しました。

boot-message.bin では、命令列の後ろに0終端文字列を置き、SYSCALL 1 でまとめて表示しました。起動時には Welcome to Handmade VM を表示し、h を入力するとhelp用文字列を表示し、q を入力すると終了メッセージを表示して HALT します。

Welcome to Handmade VM
>h
Commands:
h: help
q: quit
>>q
Goodbye from Handmade VM
CPU halted.

ここまで来ると、VM上のプログラムはかなり「小さなOSの入口」らしくなってきます。起動メッセージがあり、プロンプトがあり、help表示があり、終了コマンドもあります。

けれど、まだ入力は1文字ずつしか扱えません。h ならhelp、q ならquit、という形です。人間が普段使うコマンドのように help や quit という単語を入力しているわけではありません。

単語コマンドへ進むには、まず「Enterまでの入力をメモリに貯める」必要があります。1文字読んですぐ分岐するのではなく、h、e、l、p のように順番に読み、VM内の memory に並べて保存します。

今回は、その入口として programs/line-buffer.bin を追加します。

Day 30: tools/write-line-buffer-bin.c / programs/line-buffer.bin

今回の練習ノートとコードは、GitHubの handmade-vm-os に置いています。

今回の記事で扱う範囲

今回の記事で実装するのは、「Enterまでの入力をVM内メモリに保存し、0終端文字列として表示するところ」までです。

画面上では、次のような流れになります。最初に入力を促すメッセージを表示し、help と入力して Enter を押すと、VMが保存した文字列をそのまま表示します。

Type a word, then Enter
>help
You typed: help
CPU halted.

自動確認では、標準入力から help\n を渡すため、入力した文字そのものは端末にechoされません。その場合は次のように見えます。

Type a word, then Enter
>You typed: help
CPU halted.

ここで大事なのは、You typed: help の help が、命令列に直接書かれている文字列ではないことです。help は、実行中に SYSCALL 2 で読み、STB で memory に保存した文字列です。

ただし、今回はまだ help と quit の文字列比較はしません。まずは、入力された行をVM内メモリに置き、あとから文字列として読める形にするところまでを確認します。

今回のゴール

まず完成形を実行します。今回追加したターゲットは make test-line-buffer です。

make test-line-buffer

このターゲットでは、VMに programs/line-buffer.bin を読み込ませ、標準入力から help\n を渡します。

printf 'help\n' | ./handmade-vm programs/line-buffer.bin
Type a word, then Enter
>You typed: help
CPU halted.

今回のプログラムは、次の順番で動きます。

• Type a word, then Enter と > を表示する
• 入力バッファの先頭アドレス 0x180 を R1 に入れる
• SYSCALL 2 で1 byte読む
• Enterでなければ STB [R1], R0 で保存する
• INC R1 で次の保存先へ進む
• Enterが来たら 0x00 を書き、0終端文字列にする
• SYSCALL 1 で入力バッファを文字列として表示する

今回の中心は STB [R1], R0 です。R0 に入っている入力文字を、R1 が指すメモリへ1 byte書き込みます。

仕様カード

今回の line-buffer.bin は、新しいVM命令ではなく、既存命令を組み合わせたサンプルプログラムです。それでも、何を読み、何を書き、どこで止まるのかを仕様カードとして整理しておくと、あとでコードを追いやすくなります。

名前: line-buffer.bin
分類: sample program
目的: Enterまでの入力をVM内メモリへ1 byteずつ保存し、0終端文字列として表示する
命令長: 4 byte固定
使う命令:
  MOVI
  SYSCALL 1
  SYSCALL 2
  SYSCALL 3
  CMP
  STB
  INC
  JUMP
  JZ
  HALT
読むレジスタ: R0, R1, R2
書くレジスタ: R0, R1, R2
読むメモリ: memory[R0] から 0 byte まで
書くメモリ: memory[0x180] から最大63 byteと終端0 byte
PCの変化: fetch時に +4、JUMP/JZで即値アドレスへ変更
条件フラグの変化: CMPでzero flagを更新する
成功条件: 入力した単語をVM内メモリに保存し、Enter後に同じ文字列として表示する

今回のポイントは、memory を読むだけでなく書くところです。前回の boot-message.bin では、writerがあらかじめ配置した文字列を SYSCALL 1 で読みました。今回は、VMの実行中に入力文字を memory へ書き込みます。

つまり、前回は「バイナリ内に最初からある文字列を表示する」練習でした。今回は「実行中にできた文字列をメモリに用意する」練習です。

なぜ入力バッファが必要なのか

1文字コマンドだけなら、入力を読んだ直後に分岐できます。

1文字読む
↓
h かどうか比べる
↓
q かどうか比べる
↓
その他なら ? を表示する

しかし、help という単語を扱う場合は、最初の h だけでは判断できません。h のあとに e が続くのか、hello のような別の単語が来るのか、まだ分からないためです。

そこで、まず入力をまとめて保存します。

h を読む → memory[0x180] に保存
e を読む → memory[0x181] に保存
l を読む → memory[0x182] に保存
p を読む → memory[0x183] に保存
Enterを読む → memory[0x184] に 0x00 を保存

この形になっていれば、あとから memory[0x180] 以降を見て、help なのか quit なのかを比べられます。

今回はまだ比較までは進めません。まずは、Enterまでの入力を memory に並べ、最後に 0x00 を置いて、0終端文字列として扱えるようにします。

入力バッファの場所を決める

今回の入力バッファは、0x180 から始めます。

0x00000100: "Type a word, then Enter\n>\0"
0x00000140: "You typed: \0"
0x00000180: 入力バッファ

0x100 には最初に表示するメッセージを置きます。0x140 には結果表示用の You typed: を置きます。そして 0x180 から先を、実行中に入力を書き込む場所として使います。

このように命令列、固定文字列、入力バッファの位置を分けておくと、VMが何を読んでいて、どこへ書いているのかを追いやすくなります。

今回のプログラムでは、R1 を「次に書く場所」として使います。最初に R1 = 0x180 にしておき、1文字保存するたびに INC R1 で次のアドレスへ進めます。

R0: 読んだ文字
R1: 次の保存先
R2: 比較用の値

ここで混乱しやすいのは、R1 そのものがメモリではないことです。R1 はレジスタです。その中に、入力バッファのアドレスを入れます。

R1              レジスタ
regs[1]         R1の中身
regs[1] = 0x180 入力バッファの先頭アドレス
memory[regs[1]] 実際に書き込むmemoryの場所

STB [R1], R0 を読むときは、この段階を分けて考えると追いやすくなります。

プログラム全体の配置を見る

line-buffer.bin の命令列は、次のような配置にしています。

0x00000000: MOVI R0, 0x100
0x00000004: SYSCALL 1
0x00000008: MOVI R1, 0x180
0x0000000C: SYSCALL 2
0x00000010: MOVI R2, 10
0x00000014: CMP R0, R2
0x00000018: JZ 0x40
0x0000001C: MOVI R2, 13
0x00000020: CMP R0, R2
0x00000024: JZ 0x40
0x00000028: STB [R1], R0
0x0000002C: INC R1
0x00000030: MOVI R2, 0x1BF
0x00000034: CMP R1, R2
0x00000038: JZ 0x40
0x0000003C: JUMP 0x0C
0x00000040: MOVI R0, 0
0x00000044: STB [R1], R0
0x00000048: MOVI R0, 0x140
0x0000004C: SYSCALL 1
0x00000050: MOVI R0, 0x180
0x00000054: SYSCALL 1
0x00000058: MOVI R0, 10
0x0000005C: SYSCALL 3
0x00000060: HALT

0x00000100: "Type a word, then Enter\n>\0"
0x00000140: "You typed: \0"
0x00000180: 入力バッファ

先頭では、まず 0x100 の文字列を表示します。

MOVI R0, 0x100
SYSCALL 1

これは前回と同じ形です。R0 に文字列の先頭アドレスを入れ、SYSCALL 1 で0終端文字列を表示します。

次に、入力バッファの先頭アドレスを R1 に入れます。

MOVI R1, 0x180

ここから先、R1 は「次に入力文字を書き込む場所」を表します。最初は memory[0x180] に書き込み、次は memory[0x181]、その次は memory[0x182] へ進みます。

1 byte読む

入力を読む命令は、以前追加した SYSCALL 2 です。

SYSCALL 2

SYSCALL 2 は、host標準入力から1 byte読み、R0 へ入れます。VM本体では、次のような処理になっています。

} else if (inst.imm == 2) {
    int ch = getchar();

    if (ch == EOF) {
        printf("input EOF\n");
        vm->running = false;
    } else {
        vm->regs[0] = (uint8_t)ch;
    }
}

例えば help\n が入力される場合、最初の SYSCALL 2 では h が読まれます。ASCIIでは h は 104、16進数では 0x68 です。

入力: help\n
最初に読むbyte: h
R0 = 0x68

ここでは、まだ保存はしていません。まず R0 に「読んだ文字」が入った状態になります。

Enterかどうかを調べる

入力バッファでは、Enterを見つけたところで読み取りを終えます。今回は、LFの 10 と、CRの 13 の両方を見ています。

MOVI R2, 10
CMP R0, R2
JZ 0x40
MOVI R2, 13
CMP R0, R2
JZ 0x40

R2 は比較用の一時レジスタとして使っています。まず 10 を入れて R0 と比べます。次に 13 を入れて、もう一度 R0 と比べます。

CMP R0, R2 は、R0 と R2 が同じなら zero_flag を立てます。そして JZ 0x40 は、zero_flag が立っているときだけ PC を 0x40 へ変更します。

0x40 は、入力を終える処理の先頭です。つまり、読んだ文字が Enter なら、保存ループを抜けて終端処理へ進みます。

一方、読んだ文字が h の場合は 10 でも 13 でもありません。そのため JZ 0x40 では飛ばず、次の保存処理へ進みます。

STBで入力文字を保存する

Enterではない文字は、入力バッファへ保存します。

STB [R1], R0

この命令は、R0 の下位8bitを、R1 が指すメモリへ書き込みます。C実装では、STB は次の処理に対応します。

vm->memory[vm->regs[inst.rd]] = vm->regs[inst.rs] & 0xFF;

STB [R1], R0 の場合は、rd = 1、rs = 0 です。これをCコードへ置き換えると、次のようになります。

rd = 1
rs = 0

vm->memory[vm->regs[1]] = vm->regs[0] & 0xFF;

ここで、regs[1] には 0x180 が入っています。regs[0] には、さきほど読んだ h、つまり 0x68 が入っています。

vm->regs[1] = 0x180
vm->regs[0] = 0x68

vm->memory[0x180] = 0x68;

これで、入力文字 h が memory[0x180] に保存されました。

ここで間違いやすいのは、memory[R1] と考えてしまうことです。Cコードの中に R1 という配列添字があるわけではありません。実際には、R1 に対応する regs[1] の中身を取り出し、その値をアドレスとして使います。

R1              レジスタ名
1               レジスタ番号
regs[1]         R1の中身
memory[regs[1]] R1の中身をアドレスとして見たmemory

この「番号」「中身」「アドレス」を分けると、LDB や STB のようなメモリアクセス命令を追いやすくなります。

INCで次の保存先へ進む

1文字保存したら、次の文字を書き込むために R1 を1増やします。

INC R1

最初は R1 = 0x180 でした。h を保存したあとに INC R1 を実行すると、R1 = 0x181 になります。

保存前:
  R1 = 0x180

STB [R1], R0:
  memory[0x180] = 'h'

INC R1:
  R1 = 0x181

次のループで e を読むと、今度は memory[0x181] に保存されます。そのあとまた INC R1 で 0x182 へ進みます。

memory[0x180] = 'h'
memory[0x181] = 'e'
memory[0x182] = 'l'
memory[0x183] = 'p'

このように、R1 を「現在の書き込み位置」として動かすことで、入力された文字を連続したメモリ領域に保存できます。

バッファの上限を見る

今回のサンプルでは、入力バッファに最大63 byteまで保存します。保存に使う範囲は、0x180 から 0x1BE までです。

MOVI R2, 0x1BF
CMP R1, R2
JZ 0x40

0x1BF は、終端用の 0x00 を書く場所として使います。R1 == 0x1BF になった場合は、Enterを読んでいなくても終端処理へ進みます。

この上限処理を入れておく理由は、入力が長すぎたときに、そのままどこまでも memory へ書き続けないようにするためです。今回は本格的なエラー表示や再入力処理までは入れませんが、「バッファには終わりがある」という形だけは残しておきます。

入力がまだ上限に達していない場合は、JUMP 0x0C で読み取りループへ戻ります。

JUMP 0x0C

0x0C は SYSCALL 2 の位置です。つまり、次の1 byteを読むところへ戻ります。

最後に0 byteを書く

Enterを読んだら、Enterそのものは入力バッファへ保存しません。代わりに、現在の R1 が指す場所へ 0x00 を書き込みます。

MOVI R0, 0
STB [R1], R0

例えば help を入力した場合、p を保存したあと、R1 は 0x184 になっています。

memory[0x180] = 'h'
memory[0x181] = 'e'
memory[0x182] = 'l'
memory[0x183] = 'p'
R1 = 0x184

そこで MOVI R0, 0 により R0 へ 0 を入れ、STB [R1], R0 で memory[0x184] に 0x00 を書きます。

memory[0x180] = 'h'
memory[0x181] = 'e'
memory[0x182] = 'l'
memory[0x183] = 'p'
memory[0x184] = 0x00

これで、入力バッファは0終端文字列になりました。

前回の記事では、writerが write_string_at の最後で 0x00 を書いていました。今回は、VM上のプログラム自身が STB を使って 0x00 を書いています。

ここが今回の面白いところです。0終端文字列は、最初からバイナリに置くこともできますし、実行中に入力から生成することもできます。

保存した文字列を表示する

入力バッファに 0x00 を書いたら、あとは前回と同じように SYSCALL 1 で表示できます。

MOVI R0, 0x140
SYSCALL 1
MOVI R0, 0x180
SYSCALL 1
MOVI R0, 10
SYSCALL 3
HALT

まず 0x140 の You typed: を表示します。次に 0x180 の入力バッファを表示します。最後に SYSCALL 3 で改行文字を表示し、HALT します。

SYSCALL 1 は、R0 を文字そのものではなく、文字列の先頭アドレスとして扱います。そのため、R0 = 0x180 にしてから SYSCALL 1 を呼ぶと、memory[0x180] から 0x00 までが表示されます。

R0 = 0x180
SYSCALL 1

memory[0x180] = 'h'
memory[0x181] = 'e'
memory[0x182] = 'l'
memory[0x183] = 'p'
memory[0x184] = 0x00

表示される文字列:
help

前回と同じ SYSCALL 1 ですが、今回は表示する文字列の置き方が違います。前回はwriterがあらかじめ用意した固定データでした。今回は、VMを実行中に標準入力から入力し、STB で生成したデータです。

writerでline-buffer.binを生成する

今回も、小アセンブラにはまだ .string やラベルを追加しません。前回と同じく、専用のwriterで line-buffer.bin を生成します。

命令列を書いている部分は、次のようになっています。

write_u32_be(file, 0x40000100);  // MOVI R0, 0x100
write_u32_be(file, 0x60000001);  // SYSCALL 1
write_u32_be(file, 0x40100180);  // MOVI R1, 0x180
write_u32_be(file, 0x60000002);  // SYSCALL 2
write_u32_be(file, 0x4020000A);  // MOVI R2, 10
write_u32_be(file, 0x24020000);  // CMP R0, R2
write_u32_be(file, 0x6A000040);  // JZ 0x40
write_u32_be(file, 0x4020000D);  // MOVI R2, 13
write_u32_be(file, 0x24020000);  // CMP R0, R2
write_u32_be(file, 0x6A000040);  // JZ 0x40
write_u32_be(file, 0x31100000);  // STB [R1], R0
write_u32_be(file, 0x20100000);  // INC R1
write_u32_be(file, 0x402001BF);  // MOVI R2, 0x1BF
write_u32_be(file, 0x24120000);  // CMP R1, R2
write_u32_be(file, 0x6A000040);  // JZ 0x40
write_u32_be(file, 0x6800000C);  // JUMP 0x0C
write_u32_be(file, 0x40000000);  // MOVI R0, 0
write_u32_be(file, 0x31100000);  // STB [R1], R0
write_u32_be(file, 0x40000140);  // MOVI R0, 0x140
write_u32_be(file, 0x60000001);  // SYSCALL 1
write_u32_be(file, 0x40000180);  // MOVI R0, 0x180
write_u32_be(file, 0x60000001);  // SYSCALL 1
write_u32_be(file, 0x4000000A);  // MOVI R0, 10
write_u32_be(file, 0x60000003);  // SYSCALL 3
write_u32_be(file, 0x01000000);  // HALT

固定文字列は、前回と同じ write_string_at で配置します。

write_string_at(file, 0x100, "Type a word, then Enter\n>");
write_string_at(file, 0x140, "You typed: ");

0x180 には、writerでは文字列を書きません。そこは、VM上のプログラムが実行中に入力を書き込む場所だからです。

この違いも大切です。

0x100: writerが固定文字列を書く
0x140: writerが固定文字列を書く
0x180: VM上のプログラムが入力を書き込む

同じ memory の中でも、あらかじめバイナリに入っているデータと、実行中に作られるデータがあります。入力バッファは後者です。

バイナリの中身を見る

xxd で programs/line-buffer.bin の先頭を見ると、命令列と文字列データの位置が確認できます。

xxd -g 1 -l 416 programs/line-buffer.bin

00000000: 40 00 01 00 60 00 00 01 40 10 01 80 60 00 00 02
00000010: 40 20 00 0a 24 02 00 00 6a 00 00 40 40 20 00 0d
00000020: 24 02 00 00 6a 00 00 40 31 10 00 00 20 10 00 00
00000030: 40 20 01 bf 24 12 00 00 6a 00 00 40 68 00 00 0c
00000040: 40 00 00 00 31 10 00 00 40 00 01 40 60 00 00 01
00000050: 40 00 01 80 60 00 00 01 40 00 00 0a 60 00 00 03
00000060: 01 00 00 00 ...
00000100: 54 79 70 65 20 61 20 77 6f 72 64 2c 20 74 68 65
00000110: 6e 20 45 6e 74 65 72 0a 3e 00 ...
00000140: 59 6f 75 20 74 79 70 65 64 3a 20 00

0x00000000 から 0x00000060 あたりまでは命令列です。0x00000100 には Type a word, then Enter\n> が置かれています。0x00000140 には You typed: が置かれています。

0x00000180 は、この時点ではまだ空き領域です。ここには、実行中に入力文字が保存されます。

helpの中身を追ってみる

最後に、help を入力したときの memory の変化を手で追ってみます。

初期状態:
  R1 = 0x180

1文字目:
  SYSCALL 2 で 'h' を読む
  R0 = 'h'
  STB [R1], R0
  memory[0x180] = 'h'
  INC R1
  R1 = 0x181

2文字目:
  SYSCALL 2 で 'e' を読む
  memory[0x181] = 'e'
  R1 = 0x182

3文字目:
  SYSCALL 2 で 'l' を読む
  memory[0x182] = 'l'
  R1 = 0x183

4文字目:
  SYSCALL 2 で 'p' を読む
  memory[0x183] = 'p'
  R1 = 0x184

Enter:
  SYSCALL 2 で '\n' を読む
  JZ 0x40 で終端処理へ進む
  memory[0x184] = 0x00

最終的に、入力バッファは次の形になります。

0x180: h
0x181: e
0x182: l
0x183: p
0x184: 0x00

この形になっていれば、SYSCALL 1 は 0x180 から順番に読み、0x00 に到達したところで表示を止められます。

今回まだやらないこと

今回できたのは、入力を「行」としてメモリに置くところまでです。まだ、入力された文字列が help なのか quit なのかを判定していません。

また、Backspaceにも対応していません。入力途中で文字を消す処理や、画面表示を戻す処理は、もう少し後で扱います。

今回の目的は、行編集を完成させることではありません。単語コマンドへ進む前に、まず「入力された文字がVM内メモリに並ぶ」という状態を作ることです。

ここを分けておくと、次に文字列比較を追加するときにも、問題を切り分けやすくなります。

今回:
  入力をmemoryに保存する
  0終端文字列として表示する

次回以降:
  memory上の文字列を help / quit と比較する
  コマンドごとに分岐する

今回分かったこと

今回は、Enterまでの入力をVM内メモリに保存し、0終端文字列として表示するところまで進みました。

今回確認した内容は次の通りです。

• SYSCALL 2 は、host標準入力から1 byte読み、R0 へ入れる
• R1 は、入力バッファ内の次の書き込み先として使える
• STB [R1], R0 は、regs[1] が指す memory へ regs[0] の下位8bitを書き込む
• INC R1 で、次の保存先へ進める
• Enterを読んだら、Enterそのものではなく 0x00 を書く
• 最後に SYSCALL 1 を使えば、入力バッファを0終端文字列として表示できる

今回分かったことを整理すると、入力バッファは「読んだ文字を一時的に置いておく場所」ではなく、あとから文字列として扱うためのメモリ領域だと言えます。R1 に保存先アドレスを入れ、STB で1 byteずつ書き、最後に 0x00 を置くことで、VM上のプログラム自身が文字列を作れるようになりました。

まとめ

前回は、writerが配置した固定文字列を表示しました。今回は、VM上のプログラムが実行中に文字列を用意しました。

この差は小さく見えますが、自作OSや自作シェルへ進むうえでは大きな一歩です。コマンド入力は、最初からバイナリに入っている文字列ではありません。実行中にユーザーが入力し、それをOS側がメモリに保存して、あとから解釈します。

これで、h や q のような1文字コマンドから、help や quit のような単語コマンドへ進むための土台ができました。

次に進むこと

第10回では、Enterまでの入力を memory に保存し、0終端文字列として表示する入力バッファを作りました。

次回は、少し寄り道して、VM本体の起動方法を見直します。引数なしで ./handmade-vm を起動したときに Welcome表示と > を表示し、こから外部バイナリを選んで実行できるhost側monitorを追加します。