【低レイヤ入門】C言語で作る自作VMを少しOSらしくする: 文字列比較を共通サブルーチンにする | UNIX Cafe

前回は、VM上で動く word-command-subroutine.bin の入力処理を、CALLI と RET で呼び出す read_line に分けました。入力が終わると呼び出し元へ戻り、保存した文字列を help / quit と比較する形です。

ただし、文字列の比較はまだ、文字ごとの命令列を並べていました。help なら h、e、l、p、最後の0を順に比較し、quit にも同じ形の処理を書いています。

今回は、この比較部分を string_equal という1つのサブルーチンにまとめます。比較する文字列の先頭アドレスをレジスタで渡し、一致したかどうかを別のレジスタで受け取ります。

Day 34: tools/write-word-command-compare-bin.c
        programs/word-command-compare.bin

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

今回の記事で扱う範囲

今回は、「入力バッファと固定文字列を同じサブルーチンで比較し、戻り値を使ってhelp / quit / unknownへ分岐するところ」までを扱います。

入力部分は前回の read_line を使います。新しいVM命令やsyscallの追加はなく、notes/vm.c も変更しません。比較に使う LDB、CMP、JZ、JNZ、INC、CALLI、RET は、すでにVMへ実装した命令です。

main
  プロンプトを表示
  CALLI read_line
  入力バッファとhelpを比較 → 一致ならhelp表示 → HALT
  入力バッファとquitを比較 → 一致なら終了表示 → HALT
  どちらでもなければunknown表示 → HALT

string_equal
  2つの文字列を1 byteずつ比較
  一致ならR0 = 1、不一致ならR0 = 0
  RET

画面の表示は前回と同じです。今回は、比較する相手を変えて同じ処理を呼び出せることと、結果を呼び出し元へ返す方法を見ていきます。

まずmonitorから手で動かす

リポジトリのルートで make を実行すると、VM本体とサンプルのバイナリを用意できます。その後、引数なしでVMを起動します。

make
./handmade-vm

host側monitorの > に programs/word-command-compare.bin を入力します。VM上のプログラムが表示する Command> には、help と入力します。

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

Command> help の help はVM上の入力ルーチンが読みます。最後の >quit はhost側monitorを終了するための入力です。VM上のプログラムは、結果を1回表示すると HALT し、monitorへ戻ります。

直接起動する場合は make run-word-command-compare でも試せます。まだ複数のコマンドを続けて受け付けるループにはしていません。

比較する文字を命令からメモリへ移す

前回は、入力バッファの1 byteを読み、その文字と比較する値を MOVI で用意していました。例えば先頭の文字なら、次の形です。

MOVI R1, 0x500
LDB R0, [R1]
MOVI R2, 104      ; hの文字コード
CMP R0, R2

この後にも e、l、p、0との比較が続きます。比較する文字列が命令列の中に埋め込まれているため、別の単語には別の命令列が必要でした。

今回は比較相手も0終端文字列としてメモリへ置きます。help は 0x420、quit は 0x430 から始まります。入力バッファは前回と同じ 0x500 です。

比較する単語:
0x420: 68 65 6C 70 00   help + 終端0
0x430: 71 75 69 74 00   quit + 終端0

helpと入力した場合:
0x500: 68 65 6C 70 00   入力バッファ

ルーチンへ渡すのは、文字列そのものではなく先頭アドレスです。R1が入力側、R2が比較相手の側を指し、両方から LDB で1 byteずつ読み出します。

仕様カードと呼び出しの約束

名前: string_equal
分類: VM上のサブルーチン
目的: 2つの0終端文字列が完全一致するか調べる
入力: R1 = 入力文字列の先頭
      R2 = 比較相手の文字列の先頭
出力: R0 = 一致なら1、不一致なら0
変更するレジスタ: R0, R1, R2, R3, R4
読むメモリ: R1とR2から始まる0終端文字列
文字列への書き込み: なし
PCの変化: CALLIで入り、RETで呼び出しの次へ戻る
SPの変化: CALLIで4減り、RETで4戻る
条件フラグ: CMPで変わる。呼び出し側はR0を改めて比較する

前回の read_line は、入力結果を memory[0x500] からの文字列として残しました。今回の string_equal は、比較結果を R0 に残します。戻った後にどこを見れば結果が分かるかを、先に決めておきます。

R1とR2は比較中に進みます。R3は比較相手から読んだ1 byte、R4は終端判定用の0に使います。R0からR4まで、呼び出し前の値を保存する約束にはしていません。

ここでは、一致したら1を返します。C言語の strcmp が一致時に0を返す規則とは異なるため、名前も string_equal としています。

help比較の呼び出しを命令で追う

今回のバイナリでは、read_line は 0x064、string_equal は 0x0A8 に配置されます。前回から命令列の長さが変わったので、入力ルーチンの開始位置も変わっています。

0x008: CALLI 0x064       read_lineを呼ぶ
0x00C: MOVI R1, 0x500    入力バッファの先頭
0x010: MOVI R2, 0x420    helpの先頭
0x014: CALLI 0x0A8       string_equalを呼ぶ
0x018: MOVI R3, 1
0x01C: CMP R0, R3
0x020: JZ 0x040          一致ならhelp表示へ

入力ルーチンから戻ったら、R1に 0x500、R2に 0x420 を入れます。その状態で CALLI 0x0A8 を実行すると、比較ルーチンはこの2つのアドレスから文字を読み始めます。

CALLI 0x0A8 の命令コードも手で確認しておきます。typeは6、opは9、下位20 bitの即値は 0x0A8 です。

命令:       CALLI 0x0A8
32bit値:    0x690000A8
メモリ上:   69 00 00 A8

CALLIの場所: 0x014
fetch後のPC: 0x018  ← スタックに保存する戻り先
移動先:      0x0A8  ← string_equal

ルーチンから RET で戻ると 0x018 から実行を再開します。そこでR0と1を比較し、一致していればhelp表示へ分岐します。ルーチン内で最後に残ったzero flagへ直接頼らず、戻り値から分岐条件を作り直しています。

1 byteずつ比較するループ

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

string_equal:
    MOVI R4, 0
compare_loop:
    LDB R0, [R1]
    LDB R3, [R2]
    CMP R0, R3
    JNZ not_equal
    CMP R0, R4
    JZ equal
    INC R1
    INC R2
    JUMP compare_loop
equal:
    MOVI R0, 1
    RET
not_equal:
    MOVI R0, 0
    RET

最初の MOVI R4, 0 は終端判定に使う0を用意します。ループへ入ると、R1が指すbyteをR0へ、R2が指すbyteをR3へ読みます。

まず CMP R0, R3 で2つのbyteを比較します。違っていれば JNZ not_equal へ進み、R0を0にして戻ります。同じだった場合だけ、続く CMP R0, R4 で、そのbyteが0かどうかを調べます。

両方が同じ0なら、文字列の末尾まで一致したことになります。equal へ進み、R0を1にして戻ります。同じ文字でも0ではなければ、R1とR2をそれぞれ1増やし、次のbyteを比較します。

helpの最後にある0まで確認する

help と入力した場合、2つのアドレスは次の順で進みます。

R1      R2      入力側   比較相手
0x500   0x420   'h'      'h'
0x501   0x421   'e'      'e'
0x502   0x422   'l'      'l'
0x503   0x423   'p'      'p'
0x504   0x424   0x00     0x00  → 完全一致

p が一致した時点では、まだ成功にしません。次のbyteも読み、両方が0で終わっていることを確かめます。

例えば helpful なら、先頭の4文字は一致しますが、次は入力側が f、比較相手が0です。この2つは異なるため、R0は0になります。

helpfulの場合:
  memory[0x504] = 'f'
  memory[0x424] = 0x00
  → 不一致

helの場合:
  memory[0x503] = 0x00
  memory[0x423] = 'p'
  → 不一致

短い hel も不一致です。入力側に0が来たという理由だけで成功にすると、途中までしか合っていない文字列も受け入れてしまいます。そのため、先に2つのbyteを比較し、その後で0かどうかを調べます。

quit比較ではアドレスを設定し直す

helpに一致しなかった場合は、次にquitと比較します。ここでR2だけをquitへ変えると、R1はhelpとの比較が止まった位置のままです。入力の途中から比較を始めないよう、R1も先頭へ戻します。

0x024: MOVI R1, 0x500
0x028: MOVI R2, 0x430
0x02C: CALLI 0x0A8
0x030: MOVI R3, 1
0x034: CMP R0, R3
0x038: JZ 0x04C          一致なら終了表示へ
0x03C: JUMP 0x058        不一致ならunknown表示へ

呼び出し先はhelp比較と同じ 0x0A8 です。一方、今回スタックへ保存する戻り先は 0x030 になります。同じルーチンでも、CALLI がそれぞれの戻り先を保存するので、RET で正しい場所へ戻れます。

このプログラムでは、入力ルーチンから戻ってから比較ルーチンを呼びます。比較ルーチンが別のサブルーチンを呼ぶ構成でもないため、各呼び出しが終わるたびにSPは元の位置へ戻ります。

writerで同じ行き先を2か所へ入れる

tools/write-word-command-compare-bin.c はhost側で実行し、VM用の命令列と文字列データをファイルへ書くCプログラムです。writer自体がhost上で入力コマンドを比較するわけではありません。

比較用の文字列は、次の定数で置き場所を決めています。表示用の長いhelpメッセージとは別のデータです。

#define HELP_WORD 0x420
#define QUIT_WORD 0x430

writerのファイル出力部分では、write_string_at が各文字列と終端0を書き込みます。エラー処理を省いて呼び出し部分だけ見ると、次の形です。

write_string_at(file, HELP_WORD, "help");
write_string_at(file, QUIT_WORD, "quit");

命令列を作るときは、2か所のCALLIの位置を call_compare_help と call_compare_quit に記録しておきます。表示処理と入力ルーチンを書いた後で、比較ルーチンの開始位置を求めます。

uint32_t string_equal = address_of(count);

1命令が4 byteなので、address_of(count) は命令数を4倍したアドレスです。今回ここまでに42命令を置いているため、42 × 4 = 168、16進数では 0x0A8 になります。

最後に、2か所のCALLIへ同じ開始アドレスを埋めます。

patch_jump(program, call_compare_help, 0x69000000, string_equal);
patch_jump(program, call_compare_quit, 0x69000000, string_equal);

これで、比較相手のアドレスだけを変えて同じVM命令列を呼べるようになります。今回の命令列は224 byteで、前回の324 byteより短くなりました。これは命令部分の長さです。固定位置へ置く文字列や、その間の空き領域も含む .bin 全体のファイルサイズとは分けて考えます。

3つの分岐と境界を確認する

まず、help / quit / helloを順に入力するMakefileのターゲットで確認します。

make test-word-command-compare

makeが表示する実行コマンドを省くと、出力は次のようになります。pipeで渡した入力文字は端末側でechoされないため、プロンプトと結果が続いて表示されます。

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

このターゲットは3つの入力を実行して表示するもので、期待する出力との差を自動判定するテストではありません。完全一致の境界は、別に入力して確認します。

printf 'hel\n' | ./handmade-vm programs/word-command-compare.bin
printf 'helpful\n' | ./handmade-vm programs/word-command-compare.bin
printf 'quits\n' | ./handmade-vm programs/word-command-compare.bin
printf '\n' | ./handmade-vm programs/word-command-compare.bin

これらはすべて、次の出力になります。

Command> Unknown command
CPU halted.

今回の実装確認では、通常の3入力に加えて、空行、短い単語、長い単語、大文字、CR、CRLF、62・63・64 byte、EOFを含む15ケースで、Day 33と標準出力・標準エラー・終了コードが一致することも確認しました。

入力の上限は前回と同じ63 byteです。上限に達すると終端0を書いて戻るため、残りの文字やEnterは読み切りません。また、CRLFではCRで入力を終えるので、後ろのLFが残ります。今回、比較の結果が同じであることを確認しましたが、残り入力の扱いを変更したわけではありません。

上限や改行に達する前にhost標準入力がEOFになった場合は、既存の SYSCALL 2 が input EOF を表示してVMを停止します。その場合は比較ルーチンへ進みません。

今回分かったこと

今回は、固定文字列との比較を、VM上の string_equal として1つにまとめました。R1とR2で先頭アドレスを渡し、R0で一致・不一致を受け取る形です。

• 比較相手の help / quit を0終端文字列としてメモリへ置きました
• 2つの文字列から1 byteずつ読み、同じループで末尾まで比較しました
• 両方の終端0まで一致した場合だけ1を返すため、hel や helpful はunknownになります
• 比較で進んだR1とR2は、次の呼び出し前に設定し直します
• 同じサブルーチンを呼んでも、CALLIが保存する戻り先は呼び出す場所ごとに異なります

入力と比較が、それぞれ呼び出せる処理になりました。次回はこの2つを使い、helpやunknownの後にプロンプトへ戻り、quitで終了する複数文字コマンドのループを考えます。繰り返し入力へ進む前に、入力上限を超えた残りの文字とCRLFをどう扱うかも決めていきます。