借り初めのひみつきち

仮ブログです。

WASM 自作 PC エミュレータ日記/202001

自作PCエミュレーターの進捗です。

GitHub - neri/vpc: A PC Emulator implemented by WebAssembly

はりぼてOS

f:id:neriring16:20200125112734p:plain

前回投稿時点では 起動画面が出るところまでの動作でそれ以降の動作は不安定になってましたが、その後の改良で現在ではほとんどのアプリが動くようになりました。
マウスも「Pointer Lock API」というものを使ってかなり理想に近い動作をするようになりました。タッチパネルの動作をどうするかが現在の課題です。
また、どうもmmlplayer のタイマーがうまく動いていないらしく途中で再生が止まってしまう不具合を確認しています。

最も近い隣人

画像を拡大縮小するアルゴリズムはいくつかあって多くのアルゴリズムは近くのピクセルの値と演算して補完しますが、「Nearest Neighbor」というのは直訳すると「最も近い隣人」になり、最も近い場所にあるピクセルをそのまま描画するというかっこいい名前とは裏腹に最も単純なアルゴリズムです。

f:id:neriring16:20200125110437p:plain

f:id:neriring16:20200125110458p:plain

ピクセルアートを整数倍表示するときはこの「Nearest Neighbor」を使うとボケのない綺麗な描画できます。
しかし整数倍にできなかったり風景写真やアウトラインフォントなどの描画は「Nearest Neighbor」を使うとガクガクしてしまうので、設定画面で切り替えできるようにしました。
iOS端末では「Nearest Neighbor」は常時オフにした方が全体的に良好な描画結果になるようです。

デバッグ機能、Step Over、Break on MBR

もともとCPUはステップ実行できるようになっていて、実行中にレジスタの値を読み書きできるように設計されていましたが、デバッガといえるほどの機能が充実していませんでした。
そこで、インターフェースを改良していろんなコマンドを実行できるようにしました。
現在、MS-DOS 付属の debug コマンドのコマンドに近いインターフェースを実装しています。
アセンブル機能はありませんが、メモリのダンプ、逆アセンブルレジスタの参照と編集、ステップ実行などのデバッグ機能が利用できます。
実行中に「DevTool」にある「Step」ボタンを押すか、「ICEBP」という隠し命令 (オペコード 0xF1) を実行するとデバッグモードになります。

f:id:neriring16:20200125113022p:plain

また、新たに Step Over (ptrace) 機能も実装しました。
これは次に実行する命令が CALL 命令や INT 命令だった場合に「次の次の命令」にブレークポイントを設定し、それ以外の命令の場合は通常のステップ実行する機能で、デバッグ時に関数の中身まで関心がない場合にステップを省略することができます。
この機能はハードウェアブレークポイントで実装しています。ハードウェアブレークポイントが設定されると CPU 実行時に CS:EIP の値を監視するので実行速度が1〜2割程度低下しますが、有効になるのはデバッグの一時的な実行時だけでソフトウェアブレークポイントよりメリットが多いので採用しました。

f:id:neriring16:20200125110638p:plain

さらに「Break on MBR」という機能も実装しました。
この機能を有効にすると起動時に MBR にジャンプした瞬間にデバッグモードになって OS の起動をデバッグできるようになります。

自作フォントエディタの話

今年作ったソフトの紹介をします。

このソフトウェアはビットマップフォントを編集することができます。
ビットマップフォントというのは名前の通りフォントデータをピクセル単位のビットマップで扱うフォント形式で、昔のOS・自作OS・組み込み環境などで主に使われており、現在の WindowsMac などで通常使われているアウトラインフォントとは異なる形式です。

もともと自作 OS で使っていた FONTX2 形式のフォントを編集しようとしたところ、昔使っていた編集ソフトが現在の環境に合わなかったり色々と細かい仕様が気になってきたので自作することになりました。

当初は Electron 向けに開発していましたが、ブラウザからアクセスできた方が便利ということで現在はオンライン版がメインとなっています。 PC やスマフォなど多くの環境でフォントを編集できます。

フォントの編集

f:id:neriring16:20191124055931p:plain

起動すると色々画面が出てきます。

新しくフォントを作成するときは「General Info」にフォント情報を入力します。
よく使われるフォントサイズは 8x16 で、このソフトで編集可能な最大サイズは 32x32 です。
既存のフォントを編集するときはこの部分は触る必要がありません。

フォントを編集するには左上の「Glyph Selector」に文字や文字コードを入力して文字を選択します。
すると真ん中のキャンバスに選択した文字が拡大表示されるので適当にクリックすると描画されます。

右側にあるToolsの「Apply」をクリックすると編集した内容が適用されて下のプレビューに反映されます。
内容に満足したら「Glyph Selector」で次の文字を選択して編集します。

セーブ・ロード・エクスポート

このソフトは「Apply」した時などに localStorage に保存されるので、次回同じブラウザで開いた時に続きから編集できます。
クラウドセーブはそのうち対応したいけど今のところ非対応です。

f:id:neriring16:20191124060028p:plain

上部メニューの「Save/Load」をクリックすると「Save/Load」画面が表示されます。
この時テキストボックスに表示される内容が現在編集中のフォントデータになります。この内容を自分自身で管理する事もできます。
自分自身で管理している別のデータをロードしたいときはテキストボックスの内容を置き換えた後に「Load」ボタンを押してください。

「Open」ボタンを押すとローカルのファイル選択ダイアログでファイルを開くことができます。
ドラッグ&ドロップに対応しているブラウザの場合はドラッグ&ドロップでもファイルを開くことができます。
はりぼてOSの「hankaku.txt」も読み取りのみ対応しています。

「Web」ボタンを押した画面でURLを入力するとインターネット上のフォントデータをロードすることができます。
Ajaxを利用するので対象のサーバーがクロスオリジンに対応している必要があります。
なお、本アプリのURLのハッシュの後にフォントデータのURLを入力すると起動時にそのデータをロードします。*1

「Export」ボタンを押すと指定した形式でデータをエクスポートできます。
形式を選択した後の画面で「Export」ボタンを押すとローカルファイルに保存できます。
一部のブラウザは「Export」ボタンを押してもうまくファイルが保存できない場合があります。その場合はテキストボックスの内容をコピペして保存してください。ただしこの方法でバイナリファイルは扱えません。

現状全ての機能に対応している形式は「FONTX2」形式となります。

f:id:neriring16:20191124182733p:plain

自作OSなどに組み込む場合は「C Header」形式でエクスポートすると簡単に扱える気がします。

f:id:neriring16:20191124182656p:plain

PNGイメージをエクスポート・インポートすることもできますがオマケ機能です。フォント情報が欠落して正しくインポートできなくなる事があります。

Fork や Patch

GitHub 上に GPL で公開されているので何かあったらご自由にどうぞ。

github.com

x86 の汎用レジスタのルーツ

x86 の汎用レジスタは AX CX DX BX です。AX BX CX DX ではありません!
この由来について 8086 のルーツから探ってみたいと思います。

Intel 4004

Intel が初めて作った CPU は電卓を作るために開発された 4004 でした。
このことから 8086 は電卓の子孫と言われることがあります。本当なのでしょうか?

8086 の祖先は 8080 であり、 8080 の祖先は 8008 でした。
では 8008 の先祖が 4004 かというと、同時期に同じ会社が作ったものだからパッケージ技術等の多少の共通点はあるにしてもそれ以上の類似性は認められません。両者を調べれば調べるほど 8008 が 4004 の後継とは考えにくいです。
8008 の後継の 8080 が出るのと同時期に 4004 の後継の 4040 がリリースされていることなどからも両者は別のシリーズだと考えられます。

ちなみに 4004 の汎用レジスタは Accumulator とは独立した16個の4ビットレジスタがあり、偶数番号のレジスタと奇数番号のレジスタをペアにして8組の8ビットレジスタとして使える命令もあったようです。
汎用レジスタの個数も合計容量も 8008 より多いです。

Intel 8008

f:id:neriring16:20191113075713p:plain

8008 は Intel が初めて作った8ビット CPU で 8080 や 8008 の先祖になります。

8008 の機械語の基本構造は8進数です。 8bit の機械語が 2bit + 3bit + 3bit の構造になっていて、 3bit で同じグループに属する8種類の命令を指定したり、8種類(以下)のレジスタを指定したり使われました。例えば ADD, ADC, SUB, SBB, AND, XOR, OR, CMP の8種類の ALU 命令は同じグループに属した同じ構造の機械語になっています。 CPU によってニーモニックや順番は多少変わるもののこれらは 8080 を経て 8086 に現在も受け継がれている特徴のひとつです。

8008 には A B C D E H L の7つの8ビットレジスタがありました。8番目のレジスタに相当する M という仮想レジスタは後述の HL ペアレジスタで指定するメモリアクセスを指しています。

A レジスタは別名 Accumulator という ALU に直結された演算のためのレジスタで、ほとんどの演算命令は A レジスタが暗黙のソースオペランドになります。
なお、古い CPU では ALU に直結された同様のレジスタはよく使われました。

H レジスタと L レジスタは High/Low のペアになっていて、仮想レジスタ M にアクセスする命令は HL レジスタペアでメモリアドレスを間接参照するメモリアクセスに使われました。
ただし 8008 にはペアレジスタの概念がなく H レジスタと L レジスタはあくまで独立したふたつの8ビットレジスタだったので、 256 バイト境界を超えるブロック転送はかなりめんどくさかったようです。

B C D E レジスタは特に決まった用途のない一時的なデータを格納するレジスタだったようです。

8008 のスタックは CPU 内部に7レベルの固定スタックが存在していました。7つと中途半端なのはおそらく PC レジスタと合わせて8つのレジスタからマルチプレクサで切り替えるような構造になってたんじゃないかと思います。

フラグは Sign, Zero, Parity, Carry の4つあって演算の動作や分岐方法は 8080 や 8086 と大きくは変わらなかったようですが、大きな違いとしてフラグレジスタのようなまとまったレジスタが存在しないので値を直接取得したり設定したりすることはできなかったようです。

Intel 8080

f:id:neriring16:20191109030510p:plain

8080 は 8008 の後継の CPU で、汎用レジスタは 8008 と同様に A B C D E H L の7つの物理レジスタと仮想レジスタ M がありました。
バイナリは非互換ですがアセンブリソースレベルでは 8008 の上位互換があったようです。

8080 で進化した点のひとつに、ふたつのレジスタをペアにして BC DE HL という3組の仮想的な16ビットレジスタにすることで一部の命令で16ビット処理ができるようになり256バイト境界を超えるメモリ転送などの処理が楽になりました。

スタックは CPU 外のメモリに追い出されて SP レジスタで指定する現代的な方式に変わりました。ただし SP レジスタにアクセス可能な命令はかなり限定されていて汎用レジスタとはだいぶ扱いが違いました。

また、フラグがフラグレジスタ (F) という8ビットのレジスタとしてまとまり、PUSH / POP 命令のみ A レジスタとフラグ(F)レジスタを組み合わせたレジスタペア (PSW/AF) も使うことができました。*1
フラグレジスタのビット配置は現在の x86 の rFLAGS の下位8ビットとほぼ同じ内容で、謎の予約ビットはこの時代から謎の予約ビットとして存在しました。

8080 の代表的な OS として CP/M が存在しました。
CP/Mシステムコールは基本的に C レジスタに機能番号、 DE レジスタにパラメータを入れて CALL 5 で呼び出しました。

Intel 8085 / Z80

f:id:neriring16:20191109025458p:plain

8085 は 8080 の公式の上位互換 CPU で一部命令が拡張されましたが、あまり使われませんでした。

Z80 は 8080 の設計者が Intel から独立して作った CPU で 8080 とバイナリレベルでほぼ上位互換があり、たくさんの8ビットコンピュータに採用されました。

Z80 で拡張された汎用レジスタに IX, IY というメモリブロック転送のための16ビットレジスタがありました。
IX, IY レジスタデコーダ回路のトランジスタを節約するために HL レジスタのデコードを流用していたので、非公式の隠し命令を使うことで IXH, IXL, IYH, IYL のような8ビットレジスタとして使うこともできました。

Intel 8086

f:id:neriring16:20191109025510p:plain

ご存知 8086 は 8080 の後継として作られた16ビット CPU です。
8086 は 8080 と 8008 の間ほどではないですが 8080 系 CPU のソフトウェアが移植しやすいように設計されていました。

8086 の汎用レジスタは8個の16ビットレジスタがありました。そのうち半分は4組の8ビットレジスタペアとして使うこともできました。

4組の16ビットレジスタペアはそれぞれ役割 (Accumulator, Counter, Data, Base) に応じて A C D B で始まる名前が付けられ、 16bit ペアの時は X、8bit の時は上位(High) の H と下位(Low) の L の接尾辞が付きました。

そして、これらのレジスタは 8080 の汎用レジスタとほぼ同等の機能と使い方をしました。

A レジスタは Accumulator として使われ、 AL レジスタになりました。
B/BC レジスタZ80 で Counter として使われました。 8086 では CL/CX レジスタが引き継ぎました。
DE レジスタは他の汎用レジスタに比べると特化した目的が少ない Data として使われたため DX レジスタになりました。
HL レジスタはメモリ関節アドレスに使われました。 8086 ではアドレッシングモードが増えたものの Base Address として依然として重要なため BX レジスタになりました。
F レジスタは拡張して rFLAGS レジスタになりましたが、8080 の AF ペアで使われた名残で 8086 では LAHF/SAHF 命令で AH レジスタと関係があります。
IX/IY レジスタは Index として使われ、Source/Destination を明示してより用途が明確な SI/DI レジスタになりました。一方 SI/DI の8ビットバージョンである SIL/DIL は AMD64 の登場まで待たねばなりませんでした。

8086 の代表的な OS である MS-DOS の初期のバージョンは CP/M のクローンと言われるほどよく似ていて MS-DOS ファンクションコールの最初の30個くらいは CP/M とほぼ同じだったため、アセンブラレベルで変換することで 8080 の CP/M のプログラムが 8086 の MS-DOS である程度動いたと言われています。

このように 8080 と同等の機能を持つレジスタの名前が後付けで変更されたために AX CX DX BX という不規則な順番になったと当初仮定していました。
しかし、実は 8080 の時点で汎用レジスタ機械語上の順番は A B C D E H L ではありませんでした。

汎用レジスタのルーツはなんとなくわかったものの順番の理由は不明でした。 Intel の偉い人に聞いてください。

*1:このレジスタペアは 8080 では PSW というわかりにくい呼称でしたが、 Z80 では AF という構造がわかりやすい呼称に変わりました。

任意コード実行可能なホームページ作った。

今年作った自作アプリの紹介します。

TL; DR

このアプリは Web ブラウザ上で PC をエミュレーションします。
技術的には WebAssembly、 Canvas、 WebWorker、 WebAudio、 WebMIDI などを利用しています。

かんたんな紹介

もともと osz という自作 OS をサイトで紹介するためにブラウザで実行可能な PC エミュレーターを探していました。
JavaScript で動作するものはいくつか見つけたのですが、パフォーマンスなどに満足できるものがなかったので自作することになりました。
「Playground」という名前はブラウザ上で手軽に自作 OS を試してもらおうという願いでつけられた名前です。

現在は FreeDOS や osz がそれなりに動くようになり、ゲームなどもある程度動きます。

f:id:neriring16:20191214214819p:plain
f:id:neriring16:20191214215425p:plain
f:id:neriring16:20191214215224p:plain
f:id:neriring16:20191214214844p:plain

はりぼて OS は起動画面が出るものの、今一歩動作不良状態です。

f:id:neriring16:20191214214954p:plain

技術的なお話

実は数年前に今とは別のアプローチで実装した同名のエミュレータがありました。
エミュレータ本体は 7shi 氏の 8086run*1 をサーバーで実行し、ブラウザ上のターミナルエミュレータと WebSocket で接続して利用していました。
それなりに動いていましたが、サーバーで実行する必要がある等の制約のため、公開前に開発終了になりました。

それから数年、 WebAssembly が登場してこなれて来たようなので新たに自作することにしました。

このエミュレータは CPU コアと周辺デバイスが完全に独立しており、フロントエンドは現在ベタ書きの JavaScript です。
バックエンドは CPU コアが WebAssembly (clang) 、周辺デバイスは TypeScript で一緒に WebWorker で動作しています。
現在は UI が貧弱なためデバッグ支援機能などがあまり多くないですが、一応 CPU コアは外部からレジスタ操作をしたり1命令ずつ実行する機能があり、ユニットテストではこれらの機能を node.js から呼び出しています。

CPU 世代はリセット時にいつでも変更できますが、世代の判別によく使われる命令を除いてほとんどの命令の動作には影響ありません。本来実行できない世代の命令でも実行できます。

画面モードはテキストモードとグラフィックスモードがあり、テキストモードではブラウザのフォントを使って描画するので近代的なデバイスの上では非常に綺麗なレンダリングになります。グラフィックスモードは現在 320 x 200 モードしかサポートしていません。

WebMIDI に対応していて MPU-401 互換デバイスとして振る舞うので iPad で SOUND Canvas から音を鳴らすような使い方もできます。

f:id:neriring16:20191214220746p:plain

UEFI ゴルフの果てに

前回の記事の UEFI ゴルフの続報です。

Hello world はどの環境でも文字列出力関数(API, メソッド, etc...)を呼び出すだけなのでコードはほぼ定型となりコード部分の最適化の余地はほとんどありませんでした。
ゴルフのお題のひとつに CHARS というものがあり、これは印字可能 ASCII 文字の一覧を出力するものです。
CHARS は固定の文字列データが存在しないのでロジックの最適化で Hello world より小さくできる可能性が高いです。

ということで、試行錯誤の末にヘッダの圧縮とセットで 268 バイトまで削減することができました。

EfiMain:
    push rbx
    push rdi
    enter 0x20, 0

    mov rdi, rdx
    mov ebx, 0x20
.loop:
    mov rcx, [rdi + 0x40] ; EFI_SYSTEM_TABLE->ConOut
    lea rdx, [rbp + 0x20]
    mov [rdx], ebx
    call [rcx + 0x08] ; EFI_SIMPLE_OUTPUT_PROTOCOL->OutputString
    inc ebx
    cmp bl, 0x7F
    jb .loop

    xor eax, eax
    leave
    pop rdi
    pop rbx
    ret

なお、最後に改行を入れてないのでシェルのプロンプトによって表示が一部破壊されてしまいます。これがレギュレーション的に OK だったかどうかよく覚えてません...

f:id:neriring16:20191128231935p:plain

実際には push/pop を使わないバージョンも一応動きはするのですが、なぜか起動しません。

f:id:neriring16:20191128232634p:plain

そこですぐに ret する何もしないアプリケーションを作って nop の量を調整して調査した所、どういうわけかテキストセクションのサイズが 0x28 (40) バイトに満たないバイナリは問答無用でエラーになるようです。

つまり、これ以上ロジックを最適化しても意味がないということで、ゴルフ終了・・・?

ねり先生の次回作にご期待ください。

成果物を GitHub に公開しておきます。

github.com

最小の UEFI Hello World

UEFI は実行ファイルに PE/COFF という形式を採用しています。

PE/COFF 形式はご存知の方も多いかと思いますが Windows で現在主流の実行ファイル形式で、名前の通り昔 UN*X で使われていた COFF 形式の派生です。
COFF から PE/COFF になる際にオリジナルの COFF の機能のいくつかは廃れ、逆に Windows に必要な情報がいくつか追加されました。その際、元の COFF にあった廃れたフィールドはそのまま残し、新たに追加されたフィールドは Optional Header に追記する形で拡張されました。
またその後 Windows の進化に合わせて PE/COFF にも新しい機能が追加されたり廃れたりしました。
このような経緯のため PE/COFF のヘッダーにはほとんど使われていないフィールドが多数存在します。*1

また、 PE/COFF は DOS や古い Windows との互換性のために DOS Stub というダミーの DOS プログラムが含まれています。*2


UEFI では仕様を決める際に実行形式として PE/COFF を利用することが決まりました。
Windows のために色々な機能がてんこ盛りされた PE/COFF ですが UEFI ではほとんどの機能が不要なので使われていません。
つまり、適当なツールで適当に生成された UEFI の PE/COFF には無駄がたくさん詰まってるということになります。


というわけで、最小の UEFI Hello World に挑戦してみたのが以下になります。345 バイトになりました。

A Experimental of Minimal EFI Hello World · GitHub

これ以上小さくするには使われていないヘッダフィールドに別のヘッダーを埋め込むようなテクニックが必要になりますが、 BaseOfCode を 0x1000 より小さくするのが難しそうだったのでヘッダーに埋め込むのは無理かもしれません。


ところで、 PE/COFF には無駄がたくさん詰まっているということは偉い人も気づいていたようで、 EFI の初期化環境である PEI 仕様では TE (Terse Executable) という形式がサポートされています。
TE 形式は PE/COFF から DOS Stub を廃止して COFF Header と Optional Header から最小限の重要な情報だけを抜粋した独自のヘッダーに差し替えたものです。

f:id:neriring16:20191104194532p:plain:w300

UEFI BIOS ROM イメージをダンプしてみると TE 形式のファイルが埋め込まれているのが確認できます。

f:id:neriring16:20191104195304p:plain:w300


PE 形式から TE 形式にコンバートするだけで COFF Header と Optional Header の無駄なフィールドがほとんど消えて数百バイト節約でき、理論上 Hello world が 120 バイト前後まで小さくできます。
しかし、試しに手元でバイナリーをいじってみたところうまく実行できませんでした。
ヘッダーの書き方が悪かったのか、それとも通常の EFI Application 実行環境ではサポートされていないのかいまのところ不明です。

*1:ただし明確に使用しないと明言されているフィールドは少なく、使われているのかどうか不明なフィールドも多数存在します。

*2:多くの場合 DOS Stub はメッセージを出すだけの小さなプログラムですが、 EXE 形式で実現可能なプログラムは何でも入れることができるのでまれに DOS Stub の部分だけでひとつのアプリケーションになっている場合もありました。

DirectInput と XInput

USB ゲームパッドは大きく分けると DirectInput 形式と XInput 形式の2種類存在しています。
いったい何が違うのでしょうか?

DirectInput

DirectInput 形式の名前の由来は Windows APIDirectInput からきていて、規格としては USB HID (03 00 00) をベースにしています。
XInput 形式よりはるか昔からあるので、古いゲームパッドは基本的に DirectInput 形式に対応しています。

HID 規格というのはユーザーの操作をスイッチやセンサーを通じてコンピューターにデータ入力するあらゆるデバイスを統括しようとしたとても壮大な規格で、 USB キーボードやマウスも USB HID 規格の一部です。

HID 規格のゲームパッドはどのボタンをどこにどう配置するのか決まっていないのでハードウェアを設計する人が自由に決めることができます。
逆に、どのボタンがどこに配置されているのかという情報はソフトウェア側からわかりません。
そのため DirectInput 形式のゲームパッドに対応するゲームではボタンの割り当てをユーザーが設定できるものが多いです。

XInput

XInput 形式は比較的最近登場した新しい形式で、規格としてはベンダー定義の独自プロトコル (FF 5D 01〜04) となっています。

XBox で使われているゲームパッドがベースになっているのでボタンの個数や配置などがある程度決まっています。
Windows で扱う場合はあらかじめ要件が決まっているので扱いやすいのだと思います。

仕様が一般に公開されておらず、第三者によるプロトコル解析によるとバリエーションが数種類あるようです。
バリエーションの判別方法や今後別のバリエーションが増える可能性を考えると Windows 以外では正常に動作する保証がありません。