【低レイヤ入門】C言語で作る自作VMを少しOSらしくする: echoをアセンブリへ移す | UNIX Cafe

自作VM開発記 20

この連載では、C言語で小さなVM（仮想マシン）を組み立てています。ここでいうVMは、独自に決めた命令を読み取り、文字の表示や入力の保存を実行するプログラムです。今回は、すでに動いているechoコマンドを、C言語の専用プログラムで作る方式から、アセンブリで書く方式へ移します。

今回扱うechoは、入力した文章をそのまま表示するコマンドです。Command>と表示されたらechoを入力し、Text>と表示されたら文章を入力します。表示が終われば、再びCommand>に戻って次のコマンドを待ちます。今回はこの動きを変えず、プログラムの書き方だけを変えます。

これまでのechoは、専用の生成プログラム（writer）が、命令や文字列をバイト列として並べたファイル（バイナリ）を作っていました。前回までに作った変換ツールsmall-asmを使えば、文字で書いた命令や文字列から同じバイナリを生成でき、ジャンプ先や文字列の位置もラベルという名前で参照できます。

今回はこのsmall-asmでechoを書き直します。コマンドの判定、文章の入力と表示、必要な文字列を一つのソースにまとめ、生成したバイナリがwriter版と同じ入力に同じ結果を返すことを確認します。

中心になるファイルは次の三つです。.asmがアセンブリソース、.pyがPythonの確認用スクリプトです。Day 40は開発手順の番号で、連載の第20回とは別の番号です。

Day 40: programs/asm-echo-command.asm
        tools/test-asm-echo-command.py
        tools/test-echo-command.py

今回のゴールは、アセンブリから作ったechoを動かすこと

手元で動かすには、連載のプロジェクト一式が必要です。この記事のアセンブリだけを保存しても、VM本体や変換ツールがなければ実行できません。Cコンパイラとmakeを使える環境で、プロジェクトのMakefileがあるディレクトリを開いてください。

端末で次のコマンドを実行します。makeはMakefileの手順に従って、small-asmとVMをビルドし、アセンブリソースをバイナリへ変換してVMで実行します。

make run-asm-echo-command

起動後、Command>が表示されたらecho、Text>が表示されたらhelloを入力し、それぞれEnterを押してください。helloが表示され、再びCommand>に戻ったらquitを入力します。Command>やText>自体は入力しません。表示は次のようになります。

Command> echo
Text> hello
hello
Command> quit
Goodbye from Handmade VM
CPU halted.

Text>の行のhelloは自分の入力で、その次の行のhelloがプログラムによる表示です。quitはVM上のプログラムを終了するコマンドで、CPU halted.はVMが実行を停止したことを示します。

手で動きを確認したら、自動テストでも調べます。次のテストは、writer版とアセンブリ版を同じ入力と期待出力で比較するものです。自動確認にはPython 3も使います。

make test-asm-echo-command

ビルドや実行コマンドの表示を除くと、成功時は次のように表示されます。最初の行は命令数、文字列数、バイナリの大きさ、入力バッファの開始位置です。54 cases passedは54通りの入力で期待どおりに動いたという意味で、二つの版を調べるため2行出ます。

asm-echo layout: 70 instructions, 8 strings, 421 bytes; buffer at 0x500
echo-command: 54 cases passed
echo-command: 54 cases passed

まず、命令と文字列と入力場所を分けて考える

メモリのアドレスは、1バイトずつ並んだ場所の番号です。0x500は16進数で、10進数では1280です。echoはこの場所から64バイトを、入力を一時的に置く入力バッファとして使います。

ここで確認したいのは、命令や表示用の文字列がこの入力場所と重ならないかです。重なれば、入力が文字列を上書きして次の表示が壊れてしまいます。そこで、配置をまとめた仕様カードを用意しました。文字列の「終端0」は、文章の終わりを示す値0の1バイトで、画面に表示する数字の「0」とは別です。

manual/specs/040-asm-echo-command.md

0x000〜0x117  命令70個（280 byte）
0x118〜0x1A4  文字列8個（終端0を含め141 byte）
0x1A5〜0x4FF  今回のプログラムでは使わない場所
0x500〜0x53F  入力バッファ（64 byte）

1命令は4バイトなので、70命令で280バイトです。その直後に文字列を詰めて置くと、ファイル全体は421バイトになります。ファイルはアドレス0から読み込むため、使う範囲は0〜420で、1280から始まる入力バッファとは重なりません。

文字列の位置は、ラベルに任せる

以前のwriterでは、Command>を0x300、helpの説明を0x340へ置いていました。この固定位置をそのまま再現するなら、「次のデータを0x300へ置く」という絶対配置の指示が必要になります。今回は、文字列の内容を保ち、参照するアドレスを新しい位置に合わせれば、同じ表示ができます。そこで、数値で位置を固定する代わりにラベルを使います。次はソースの一部を抜き出した例です。

command_loop:
    MOVI R0, prompt_text
    SYSCALL 1
    CALLI read_line

; 実際のソースでは、残りの命令の後ろに置く
prompt_text: .string "Command> "

R0は、VM内で数値を一時的に保持するレジスタの一つです。MOVI R0, prompt_textは、prompt_textというラベルが付いた文字列の先頭アドレスをR0に入れます。位置はsmall-asmが計算するので、書き手がアドレスを手で数える必要はありません。

SYSCALLは、表示や入力などの機能をVMへ依頼する命令です。SYSCALL 1は、R0のアドレスから文字列を読み、終端0の直前まで表示します。続くCALLI read_lineで、後述する1行入力の処理を呼び出します。

prompt_text:は、その位置に名前を付ける記述です。.stringはVMが実行する命令ではなく、small-asmに文字列と終端0を配置させる指示です。ラベルと.stringの役割を分けると、「どこにあるか」と「何を置くか」を読み取れます。

文字列の位置は次のように変わります。writer列が従来版、asm列が今回のアドレスで、名前はラベルに対応します。help_word、quit_word、echo_wordはコマンド比較用、それ以外は表示用です。長さには終端0を含み、改行を表すLFも1バイトです。

名前           writer   asm     byte数
prompt_text    0x300    0x118    10
help_text      0x340    0x122    66
goodbye_text   0x3A0    0x164    26
unknown_text   0x3E0    0x17E    17
help_word      0x420    0x18F     5
quit_word      0x430    0x194     5
echo_word      0x440    0x199     5
text_prompt    0x460    0x19E     7

このようにラベルで参照すれば、small-asmに配置用の機能を追加せずに済みます。今回は命令を先に並べ、文字列をその後ろにまとめました。命令は4バイト単位で配置しますが、文字列の後ろに命令は置かないため、位置を4の倍数に揃える処理も要りません。

入力バッファは、ファイルの外にあってよい

ファイルが421バイトしかないのに、アドレス1280（0x500）へ入力を保存できるのはなぜでしょうか。VMは起動時にメモリ全体を0で初期化し、その先頭へファイルを読み込むからです。ファイルの大きさとメモリの大きさは別なので、実行中に受け取る入力は、読み込み範囲より後ろのメモリを使えます。次は、R0に入力した1バイトが入っている場合の保存処理です。

MOVI R1, 0x500
STB [R1], R0

MOVIでR1に0x500を入れ、STBでR0の下位8ビット（1バイト）をその場所へ保存します。[R1]は「R1に入っているアドレスのメモリ」を表します。たとえばR0が文字Aの値0x41なら、アドレス0x500に0x41を書き込みます。

入力バッファのために、ファイルを0x500まで0で埋める必要はありません。ただし、0x500から先を入力用に使うのはこのプログラムで決めた約束で、small-asmが自動で保護する領域ではありません。生成した命令と文字列が0x500以降に重ならないことは、専用テストで確かめます。

echoの全体を、一つのソースへ書く

次がprograms/asm-echo-command.asmの全体です。大きく分けると、コマンドを選ぶ処理、1行を入力するread_line、文字列を比較するstring_equal、末尾の文字列データで構成されています。

command_loopでは入力をhelp、quit、echoの順に比較し、helpなら使い方を表示、quitなら終了、どれにも一致しなければUnknown commandと表示します。まずはechoと一致してdo_echoへ進み、文章を表示してcommand_loopへ戻る流れを追ってください。

read_lineとstring_equalは、繰り返し呼び出せるサブルーチンです。CALLIは戻る位置を保存してその処理へ移り、RETは呼び出し元の次の命令へ戻ります。

コード内の命令は、CMPが二つの値の比較、結果が等しければJZ、異なればJNZが指定ラベルへ移動、JUMPが条件なしの移動、INCがレジスタの値を1増やす、LDBがメモリから1バイトを読む、STBがメモリへ1バイトを書く、HALTはVMの実行を停止します。行頭のセミコロン（;）から始まる行は説明用のコメントです。

; Day 40: code first, then packed strings. Buffer: 0x500..0x53F.
command_loop:
    MOVI R0, prompt_text
    SYSCALL 1
    CALLI read_line
    MOVI R1, 0x500
    MOVI R2, help_word
    CALLI string_equal
    MOVI R3, 1
    CMP R0, R3
    JZ do_help
    ; string_equal advances both pointers; reset them for each comparison.
    MOVI R1, 0x500
    MOVI R2, quit_word
    CALLI string_equal
    MOVI R3, 1
    CMP R0, R3
    JZ do_quit
    MOVI R1, 0x500
    MOVI R2, echo_word
    CALLI string_equal
    MOVI R3, 1
    CMP R0, R3
    JZ do_echo
    JUMP do_unknown
do_help:
    MOVI R0, help_text
    SYSCALL 1
    JUMP command_loop
do_quit:
    MOVI R0, goodbye_text
    SYSCALL 1
    HALT
do_unknown:
    MOVI R0, unknown_text
    SYSCALL 1
    JUMP command_loop
do_echo:
    MOVI R0, text_prompt
    SYSCALL 1
    CALLI read_line
    MOVI R0, 0x500
    SYSCALL 1
    MOVI R0, 10
    SYSCALL 3
    JUMP command_loop

; R0/R1/R2 are scratch. Save at most 63 bytes, then a zero terminator.
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/R2: strings. R0: 1 if equal, else 0. Clobbers R0..R4 and zero flag.
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

prompt_text: .string "Command> "
help_text: .string "Commands:\nhelp: show help\nquit: quit\necho: read and print a line\n"
goodbye_text: .string "Goodbye from Handmade VM\n"
unknown_text: .string "Unknown command\n"
help_word: .string "help"
quit_word: .string "quit"
echo_word: .string "echo"
text_prompt: .string "Text> "

コマンドの判定では、入力文字列の先頭アドレス0x500をR1へ、比較相手の先頭アドレスをR2へ入れてstring_equalを呼び出します。例えばecho_wordを指定した場合、入力と文字列echoを先頭から1バイトずつ比較します。

string_equalは、違うバイトが見つかればR0に0を、両方の終端0まで一致すれば1を入れて戻ります。呼び出し元は、そのR0を1と比較して対応する処理へ進みます。比較中にR1とR2は進んでしまうため、次の候補を調べる前に両方を設定し直しています。

do_echoへ進んだ時点で、バッファにあったechoという文字の役目は終わっています。そこで同じread_lineを呼び、同じ場所へ本文を入れ直します。本文中のquitやhelpはコマンドとして扱わず、そのまま表示します。表示には、バッファの先頭0x500をR0に入れてSYSCALL 1を使います。最後にR0へ改行の値10を入れ、1文字を出力するSYSCALL 3を実行してから、command_loopへ戻ります。

read_lineは、SYSCALL 2で入力を1バイトずつ読み、R0で受け取ります。通常の文字はSTBで保存し、INC R1で保存先を一つ先へ進めます。改行を表すLF（値10）を読むと、その時点の保存先へ終端0を書いて呼び出し元へ戻ります。CR（値13）は、CRとLFの組み合わせで改行を表す入力にも対応するため、保存せず読み飛ばします。CRだけでは入力は確定しません。

保存先が0x53Fに達したら、残りの文字は保存せず、LFまで読み続けます。バッファは64バイトですが、最後の1バイトが終端0に必要なため、本文として保存できるのは0x500〜0x53Eの63バイトです。長すぎる入力の残りも読み切ることで、次のコマンド入力へ混ざるのを防ぎます。

この上限は文字数ではなくバイト数です。helloは1文字1バイトですが、日本語などでは1文字に複数バイトを使うため、63文字保存できるという意味ではありません。

ファイルの最後には文字列が並びますが、実行がそこへ流れることはありません。比較処理の末尾はRETで戻り、終了処理はHALTで止まるからです。文字列を命令として実行させないことも、配置と合わせて確認しておきます。

ファイルの一致と、動きの一致を分けて確認する

writer版は1127バイト、今回の版は421バイトです。文字列の間の空きをなくし、アドレスも変えたため、ファイル比較用のcmpで全体を比べても一致しません。そこで、「予定した箇所だけが変わったか」と「同じ入力で同じ表示になるか」を分けて確認します。

tools/test-asm-echo-command.pyでは、文字列を参照する8個のMOVIについて、移動前後のアドレス、宛先レジスタ、終端0を含む文字列の内容を確かめます。そのうえで、テスト内の比較用データに限ってその8個のアドレスを従来版の値へ置き換え、70命令を比較します。実行するバイナリを書き換えるわけではありません。これで、意図して変えたアドレス以外は従来版と同じバイト列だと確認できます。

命令の順番は保ったので、分岐先やサブルーチンの入口も同じ位置です。この比較には、JUMP、JZ、JNZ、CALLIの宛先と、0x500や0x53Fといった数値も含まれます。あわせて生成物の長さを確認し、入力バッファと重ならないことも検査します。

文字列の配置を自分で見るには、ファイルを16進数で表示するxxdも使えます。-s 280は、表示の開始位置を先頭から280バイト進んだ場所にする指定です。

xxd -s 280 programs/asm-echo-command.bin

アドレス0x118から表示すると、Command>から始まる文字列の領域を見られます。最後のText>の後ろには終端0があり、ファイル末尾の次の位置は0x1A5になります。

入出力の確認には、従来のechoを実装したDay 36の54ケースを再利用します。確認用スクリプトへVMの実行ファイルとバイナリを渡し、同じ入力と期待結果で両方を検証します。次の2行は、冒頭のmake test-asm-echo-commandに含まれる入出力テストを個別に実行する方法です。

テストには、文章中の空白、空行、CRとLFを組み合わせた改行（CRLF）、63バイトの上限と超過分の読み捨てのほか、入力の途中でデータが尽きる場合（EOF）、1000回の繰り返し、monitorから起動する場合を含めています。monitorはVM本体にある起動用の操作画面で、実行したいバイナリを指定する入口です。

python3 tools/test-echo-command.py ./handmade-vm programs/echo-command.bin
python3 tools/test-echo-command.py ./handmade-vm programs/asm-echo-command.bin

改行を読む前にEOFになると、SYSCALL 2がVMを停止するため、その時点までに入力した文章は表示されません。入力に値0のバイトが含まれていた場合は、そのバイトも保存しますが、表示や比較では文字列の終わりとして扱います。ここでの値0も、キーボードで入力する数字の「0」とは別です。こうした場合も従来版と同じ結果になることを、テストで確認します。

次は、同じ行からコマンドと引数を取り出す

今回は、新しいVM命令を増やさずにechoをアセンブリへ移せました。文字列の位置はラベルに任せ、入力バッファとの境界はテストで確かめています。命令と文字列を一つのソースで読めるようになったことで、コマンド処理を変更する入口ができました。

次の候補は、echo helloのようにコマンドと文章を同じ行に書く形です。このhelloのようにコマンドへ渡す情報を引数と呼びます。現在はecho helloを未知のコマンドとして扱います。次回は、どの空白で区切るか、本文が空ならどうするかを先に決め、小さな仕様とテストから進めます。