【低レイヤ入門】C言語で作る自作VMを少しOSらしくする: help / quitを繰り返し入力する | UNIX Cafe

自作VM開発記 15

前回は、入力バッファと help / quit の比較を、string_equal という共通サブルーチンにまとめました。R1とR2に文字列の先頭アドレスを渡し、一致ならR0に1、不一致なら0を受け取る形です。

これで、1行を読む read_line と、文字列を比較する string_equal が揃いました。ただし、前回のプログラムは結果を1回表示すると HALT していました。helpを見た後に別のコマンドを入力するには、プログラムを起動し直す必要がありました。

今回は、helpやunknownの表示後にプロンプトへ戻り、続けて入力できるようにします。終了するコマンドはquitです。繰り返しにするために、入力上限を超えた文字と、CRLFの扱いも見直します。

Day 35: tools/write-word-command-loop-bin.c
        programs/word-command-loop.bin

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

今回の記事で扱う範囲

今回は、「入力と比較を繰り返し、前の行の残りを次のコマンドへ持ち越さないところ」までを扱います。

helpとunknownの表示後に先頭へ戻る部分は、既存の JUMP で作れます。入力と比較は引き続き CALLI / RET で呼び出します。新しいVM命令やsyscallの追加はなく、notes/vm.c も変更しません。

main
  Command> を表示
  CALLI read_line
  string_equalでhelp / quitと比較
  help    → help表示 → 先頭へJUMP
  quit    → 終了表示 → HALT
  unknown → unknown表示 → 先頭へJUMP

もう1つの変更は、read_line です。前回は63 byteを保存した時点で戻っていました。今回は、保存できる量と、1行として読み切る範囲を分けます。保存上限に達しても、LFを読むまでは入力を受け取り続けます。

まずhelp、hello、quitを続けて入力する

リポジトリのルートで make を実行し、引数なしでVMを起動します。

make
./handmade-vm

host側monitorの > に programs/word-command-loop.bin を入力します。VM上の Command> では、help、hello、quitを順に入力します。

Welcome to Handmade VM
>programs/word-command-loop.bin
Command> help
Commands:
help: show help
quit: quit
Command> hello
Unknown command
Command> quit
Goodbye from Handmade VM
CPU halted.
>quit
Goodbye from Handmade VM

helpの後には、次の Command> が出ます。helloはunknownになりますが、ここでも終了せず再入力できます。VM上のquitを入力したところで初めて CPU halted. が表示され、host側monitorへ戻ります。最後の >quit はmonitorを終了するための入力です。

直接起動する場合は、次のコマンドでも試せます。

make run-word-command-loop

画面に見えているhelpなどの入力文字は、端末側がechoしているものです。今回、VM上のプログラムへBackspaceや行編集を実装したわけではありません。

仕様カードで1行の区切りを決める

繰り返し入力では、どこまでを1回のコマンドとして読むかが大切です。今回はLFで入力を確定し、CRは読み捨てる約束にします。

名前: word-command-loop.bin
分類: sample program
目的: help / unknownの後は再入力し、quitで終了する
入力: LFで終わるテキスト行。CRは読み捨てる
保存先: memory[0x500] から最大63 byte、最後に終端0
上限後: 保存せず、LFまで読み続ける
空行: unknown
read_line: R0〜R2とzero flagを変更し、バッファに結果を残す
string_equal: R1/R2を受け取り、一致ならR0=1、不一致ならR0=0
string_equalの変更: R0〜R4とzero flag
PCの変化: help / unknown後は先頭へJUMP、quitはHALT
SPの変化: 各CALLIで4減り、RETで4戻る
EOF: SYSCALL 2がinput EOFを表示して停止する

入力の上限は63文字ではなく63 byteです。今回のコマンドはASCIIのhelp / quitなので、どちらも4 byteで表せます。

上限を超えた行は、保存した先頭63 byteだけを比較します。長さ超過を専用のエラーとして表示する処理はありません。また、CR単独では行を確定しません。この改行の約束は、後でCRLFの例を使って確認します。

helpとunknownのHALTをJUMPに変える

まず、結果表示の後に進む場所を変えます。前回はhelp、quit、unknownのどの表示も HALT で終わっていました。今回はhelpとunknownの末尾を JUMP 0x000 にします。

0x000: MOVI R0, 0x300    Command> の先頭
0x004: SYSCALL 1
0x008: CALLI 0x064       read_line
       help / quitの比較

0x040: MOVI R0, 0x340    help表示
0x044: SYSCALL 1
0x048: JUMP 0x000        次のプロンプトへ

0x04C: MOVI R0, 0x3A0    goodbye表示
0x050: SYSCALL 1
0x054: HALT

0x058: MOVI R0, 0x3E0    unknown表示
0x05C: SYSCALL 1
0x060: JUMP 0x000        次のプロンプトへ

0x000 へ戻ると、プロンプト表示からもう一度実行します。VMを新しく作り直す処理ではなく、同じVMのPCを先頭へ戻す処理です。レジスタやメモリの内容も、それだけで初期化されるわけではありません。

JUMP 0x000 の命令コードも確認します。typeは6、opは8、下位20 bitの即値は0です。

命令:       JUMP 0x000
32bit値:    0x68000000
メモリ上:   68 00 00 00

例えば 0x048 の命令をfetchすると、その時点のPCは次の 0x04C になります。その後、JUMPがPCを 0x000 に書き換えます。したがって、helpを表示した後に、その下に並ぶgoodbye表示へ流れることはありません。

unknown側も同じです。0x060 で先頭へ戻るため、その直後に置いた read_line へ順番に流れ込むこともありません。入力ルーチンには、先頭付近の CALLI から入ります。

CALLI / RETを繰り返してもSPは元へ戻る

入力と比較は、前回までと同じサブルーチン呼び出しです。入力ルーチンから戻ってからhelpと比較し、一致しなければquitとも比較します。

CALLI read_line     → RET → SPは元へ
CALLI string_equal → RET → SPは元へ
必要ならquitとも比較 → RET → SPは元へ
結果を表示
JUMP 0x000         → 次の入力へ

このVMの初期SPは 0x100000 です。CALLIで4 byteの戻り先を積むと 0x0FFFFC になり、RETで取り出すと 0x100000 に戻ります。今回は入力と比較を順番に呼び、サブルーチンの中から別のサブルーチンを呼ぶ構成にはしていません。

次のコマンドへ進む時点では、入力と比較の呼び出しはすでに終わっています。先頭へ戻るJUMPはスタックを使わないため、反復のたびに戻り先が積み残されることはありません。

比較の呼び出し前には、R1を入力バッファの先頭へ、R2をhelpまたはquitの先頭へ設定し直します。比較ルーチンが進めたアドレスを、そのまま次の比較に使わない約束も前回と同じです。

63 byte保存しても、まだ1行は終わっていない

ここまでのJUMPだけで、短いLF区切りのコマンドは繰り返せます。ただし、前回の入力ルーチンをそのまま使うと、長い行では問題が起きます。

前回は63 byteを保存すると、すぐに終端0を書いて戻っていました。host標準入力に残っている文字や改行までは読みません。次の例で考えてみます。

入力:
xを63個 + help + LF + quit + LF

上限に達したところですぐ戻る入力ルーチンを繰り返すと、1回目はxを63個読み、2回目はその後ろに残ったhelpを読みます。入力した側では1行だったものが、2回のコマンドに分かれてしまいます。

上限ですぐ戻ると:
  1回目: xを63個
  2回目: 同じ行の残りのhelp
  3回目: quit

今回の方式:
  1回目: xを63個保存し、残りのhelpとLFも読む
  2回目: quit

63 byteちょうどの行にも注意が必要です。文字をすべて保存できたとしても、後ろのLFを残すと、次の入力ではそのLFだけを読んで空行になります。今回のプログラムなら、余分なunknown表示が出る原因になります。

そのため、「もう保存できない」と「この行を読み終えた」を別に扱います。 バッファへの保存は止めても、LFまでは読み取りを続けます。

read_lineで保存上限と行末を分ける

今回の入力ルーチンは次の形です。これはラベル付きの説明用表記で、現在のsmall-asmがそのまま組み立てるコードではありません。実際のバイナリは専用writerで生成します。

read_line:
    MOVI R1, 0x500
read_loop:
    SYSCALL 2
    MOVI R2, 10
    CMP R0, R2
    JZ finish_input
    MOVI R2, 13
    CMP R0, R2
    JZ read_loop
    MOVI R2, 0x53F
    CMP R1, R2
    JZ read_loop
    STB [R1], R0
    INC R1
    JUMP read_loop
finish_input:
    MOVI R0, 0
    STB [R1], R0
    RET

入口では、毎回R1を 0x500 に戻します。SYSCALL 2 で1 byteを読んだら、まずLFかどうかを調べます。LFなら終端処理へ進み、CRなら保存せず次のbyteを読みます。

それ以外のbyteについて、保存先のR1が 0x53F に達していないかを確認します。まだ達していなければ STB で保存し、INC R1 で次の場所へ進みます。

0x500..0x53E: 入力を保存する63 byte
0x53F:       最大長の場合の終端0

0x53F - 0x500 = 63

63 byteを保存すると、R1は 0x53F になります。その後に普通の文字を読んでも、上限の比較で JZ read_loop が成立します。STBとINCを飛ばすため、余分な文字を保存せず、R1も進めません。

LFの判定は、保存上限の判定より前にあります。したがって、上限に達した後でも、LFが来れば finish_input へ進めます。そこでR1が指す位置へ0を書き、RETで呼び出し元へ戻ります。

63 byteを保存した直後:
  R1 = 0x53F

次の普通の文字:
  保存せず読み捨てる
  R1 = 0x53Fのまま

LF:
  memory[0x53F] = 0
  RET

最大長の場合は、予約しておいた最後の1 byteに終端0が入ります。短い行なら、途中まで進んだR1の位置に0が入ります。どちらの場合も、戻った時点ではLFまで消費しています。

CRLFを1行として読む

前回はLFでもCRでも入力を終えていました。そのため、CRとLFが続くCRLFでは、CRを読んだ時点で戻り、LFが残っていました。これを繰り返すと、そのLFが次の空行になってしまいます。

今回はCRを読み捨て、LFで確定します。

help + LF:
  h e l pを保存 → LFで終端0 → RET

help + CR + LF:
  h e l pを保存 → CRを無視 → LFで終端0 → RET

この約束なら、LFとCRLFはどちらも1回の入力になります。quitをCRLFで渡した場合も、LFまで読んでから判定するので、VMがHALTした後のhost側monitorへ、そのLFを残さずに済みます。

ただし、CR単独は行末として扱いません。今回の処理は「CRの次がLFか調べる」ものではなく、CRを見たら常に読み捨てるものです。行中にCRがある he\rlp\n も、保存される文字列はhelpになります。

先読みや、読んだ文字を次の入力へ持ち越す処理は追加せず、LF / CRLFのテキスト行を扱う約束にしています。

EOFの扱いは既存の SYSCALL 2 のままです。LFが来る前にEOFになると、input EOF を表示してVMを停止し、その未完の行は比較しません。

printf 'help' | ./handmade-vm programs/word-command-loop.bin

Command> input EOF

helpの後ろにLFを付けた場合は、helpを実行してから次の入力へ進みます。そこでEOFになれば、次のようになります。

printf 'help\n' | ./handmade-vm programs/word-command-loop.bin

Command> Commands:
help: show help
quit: quit
Command> input EOF

この停止はHALT命令によるものではないため、CPU halted. は表示されません。入力上限に達していても、LFまで読み切る前にEOFになれば同じように停止します。

前回より短い入力と終端0

コマンドを繰り返すと、同じ入力バッファを何度も使います。先にhelpfulを入力し、次にhelpを入力した場合を考えます。

helpfulを入力した後:
0x500: h e l p f u l 00

続けてhelpを入力した後:
0x500: h e l p 00 u l 00

2回目の入力では、先頭からh、e、l、pを書き、LFを読んだところで 0x504 に0を書きます。前回のuとlはメモリに残りますが、比較ルーチンは新しく書いた終端0までを見ます。そのため、helpと完全一致します。

バッファ全体を毎回0で埋める必要はありません。毎回先頭へ戻して保存し、今回の末尾へ必ず0を書くことが大切です。空行の場合は、1文字も保存せず 0x500 に0を書きます。helpにもquitにも一致しないのでunknownになります。

なお、今回はテキスト入力を想定しており、入力に含まれるNUL byteを拒否する処理はありません。NULも保存され、文字列比較は最初のNULまでになります。任意のbyte列を、その行の最後まで比較するプログラムにはしていません。

writerの配置と自動テストを確認する

tools/write-word-command-loop-bin.c はhost側で実行し、VM用の命令列と文字列データを書き出します。入力や比較を実行するのは、生成された word-command-loop.bin を読み込んだVMです。

writerでは、プロンプトを置く前に先頭アドレスを記録します。

uint32_t command_loop = address_of(count);

この時点では命令数のcountが0なので、command_loop も0です。helpとunknownの表示後には、それぞれ次の命令を生成します。

emit(program, &count, 0x68000000 | command_loop);

これが JUMP 0x000 になります。入力ルーチンの分岐も、CRなら read_loop へ、保存上限でも read_loop へ戻るように変更しています。

今回の命令数は前回と同じ56命令、224 byteです。HALTをJUMPへ置き換え、入力ルーチンでは上限判定の位置と分岐先を変更したため、命令数は増えていません。read_lineは 0x064、string_equalは 0x0A8 のままです。224 byteは命令部分の長さであり、文字列や空き領域を含むファイル全体のサイズではありません。

手で動かした後は、自動テストで確認します。今回のテストにはPython 3が必要です。

make test-word-command-loop

成功すると、最後に次の行が表示されます。

word-command-loop: 26 cases passed

tools/test-word-command-loop.py は実際のVMを起動し、標準出力全体、標準エラー、終了コードを期待値と照合します。前回のMakefileターゲットは3つの入力を実行して表示する形でしたが、今回は結果の一致まで自動判定します。各起動には5秒の待ち時間上限も設けています。

確認しているのは、通常のhelp / unknown / quitに加え、空行、完全一致の境界、CRLF、CR単独、行中CR、前回より短い入力、62・63・64・4096 byteの行、上限後のコマンド風文字列、EOFです。helpを1,000回繰り返すケースと、HALT後にmonitorへ戻って終了するケースも含めています。

CRLFは次のように個別にも試せます。

printf 'help\r\nhello\r\nquit\r\n' | ./handmade-vm programs/word-command-loop.bin

Command> Commands:
help: show help
quit: quit
Command> Unknown command
Command> Goodbye from Handmade VM
CPU halted.

pipeで渡した入力文字は端末側でechoされないので、Command> Commands: のようにプロンプトと結果が続いて見えます。CRLFのLFによる余分なunknown表示がないことを確認します。

前回より短い入力も試します。

printf 'helpful\nhelp\nquit\n' | ./handmade-vm programs/word-command-loop.bin

Command> Unknown command
Command> Commands:
help: show help
quit: quit
Command> Goodbye from Handmade VM
CPU halted.

最初のhelpfulはunknownですが、次のhelpは正しく一致します。入力を繰り返すときは、1回ごとの結果だけでなく、前の入力が次の入力へ影響しないことも確認します。

今回分かったこと

今回は、入力と比較のサブルーチンを使い、複数文字コマンドを繰り返し受け付けるようにしました。

• help / unknownの表示後にJUMPで先頭へ戻り、quitでHALTします。
• 各CALLIはRETで戻るため、次の反復へ進む時点でSPも元に戻ります。
• 63 byteを保存した後も、LFまでは入力を消費します。
• CRを読み捨て、LFで確定することで、CRLFのLFを次の入力へ残さずに済みます。
• 入力の末尾へ0を書けば、前回の長い文字列が比較へ混ざりません。

先頭へ戻る命令自体は1つですが、繰り返すためには、1回分の入力をどこまで読むかも決める必要がありました。今回は、バッファへ保存できる量と、行末まで読み切る範囲を分けて扱いました。

次に進むこと

今回は、helpやunknownの後にコマンド入力へ戻り、quitで終了するループを作りました。続く第16回では、このループにechoコマンドを追加します。echoと入力してEnterを押した後、次の行に表示したい本文を入力する形です。同じ入力処理をコマンドと本文で使い分ける仕組みや、本文にquitと書いても終了しない理由は、echoコマンドで次の1行を表示するで確認できます。