借り初めのひみつきち

仮ブログです。

BitTest 命令

x86 には BitTest というマイナーな命令があります。

具体的には BT BTS BTR BTC の4種類あって、それぞれ特定のビットをテスト(1かどうか返す)、セット(1)する、リセット(0)する、反転する(0⇔1)命令になります。

BitTest 命令をレジスタに使った場合はちょっとだけビット操作が楽になりますが、別に AND OR XOR でもいいよね感がありました。

実は BitTest 命令はレジスタに対して実行した場合とメモリに対して実行した場合重要な違いがあります。

x86 CPU はシフト命令などでビットを指定するオペランドは 32bit (64bitオペランドの場合は64bit) に制限され、例えばシフト命令に 100 を指定しても実際には 100回もシフトしませんでした。
BitTest 命令をレジスタに対して実行した場合はシフト命令などと同様に 32bit の制限がかかっていますが、メモリに対して実行した場合は 32bit の制限がありません。
つまり、何百何万もある巨大な配列の先頭を指定して BitTest 命令を実行するとそこから何百何万番目の遥か遠くにあるビットに対してビット操作する事ができます。

また、マルチスレッドプログラミングにおいても重要な機能があり、 BitTest 命令は実行前の対象ビットの値を CF レジスタに返します。
つまり、 LOCK プレフィックスとセットで使うと Mutex などのメモリ上の特定のビット操作をアトミックに扱う事ができます。

マイナーだけど、すごい命令です。

exFAT について

exFAT というファイルシステムがあります。
FAT ファイルシステムの次世代ファイルシステムとしてリムーバブルメディアなどに採用実績がありますが、仕様が公開されておらず特許が絡むために Microsoft 製以外の OS からはあまり使い勝手がよくありませんでした。

しかし、仕様が公開され、特許の条件も緩和されようとしているようです。

docs.microsoft.com

exFAT は名前の通り FAT を改良したファイルシステムで、以下のような FAT によく似た特徴があります。

  • クラスタという単位でセクタを管理しており、最初のクラスタ番号は2である
  • FAT というテーブルによりクラスタチェインを管理している
  • 32バイト単位のディレクトリエントリでファイルを管理している

一方で以下のような相違点もあります。

  • 空き領域はビットマップで管理されており、 FAT 上で管理されていないファイルが存在する
  • 8.3 ファイル名が存在せず、通常のファイルはディレクトリエントリを複数必要とする
  • FAT には存在しなかったメタデータ拡張機能が存在する

FAT はフロッピーディスクの時代に設計されたもので小容量ではそれなりにうまく動いていましたが、メディアが GB 単位の時代になってくると色々と不都合が増えてきました。 exFAT はより大きなメディア、特にソリッドステートメモリーでうまく扱えることを前提に設計されています。

クラスタ

FAT におけるクラスタとは、生のセクタを直接扱うと量が多すぎて管理が大変になるので、複数のセクタをまとめてクラスタという名前の論理セクタとして扱うことでトータルの論理セクタ数を減らして管理を楽にするための概念です。
よく使われるクラスタサイズとして 4KiB や 32KiB などがあります。4KiBはページングのページサイズ、32KiBはよくあるフラッシュメモリーのページサイズと一致するため管理の都合が良い数値です。

クラスタ単位でディスクアクセスすることでセクタ単位でアクセスするよりも高速で効率的なディスクアクセスが可能になります。
一方で、クラスタサイズはファイルの最小単位でもあり、1バイトでも内容のあるファイルはディスク上で最低1クラスタを占有するため、クラスタサイズが大きすぎると必ずしもディスクを効率的に扱えるとは限りません。

クラスタ番号は歴史的な事情で2から開始します。*1 クラスタ番号から実際のセクタ番号に変換する場合はオフセットを考慮する必要があります。

FAT とクラスタチェーン

クラスタサイズを超えるファイルを格納するには2つ以上のクラスタが必要です。
1番目のクラスタ番号はディレクトリエントリから辿れますが、2番目以降のクラスタを探す方法が別途必要になります。
この時 FAT 系ファイルシステムは FAT というテーブルを参照する事で2番目以降のクラスタを探します。

例えばクラスタ番号123のクラスタの次のクラスタを探す場合、 FAT テーブルの123番目の要素を調べ、そこに456とあった場合は次のクラスタは456と決めることができます。

FAT では FAT の要素のサイズによって FAT12FAT16FAT32 というバリエーションがありました。*2
exFAT は稀に FAT64 という俗称で呼ばれることがありますが FAT の要素サイズは 32bit となっています。

FAT ファイルシステムでは FAT テーブルはクラスタの利用状況を管理するためにも使い、 FAT テーブル上に 0 と記述されたクラスタは空き領域、 0xF...F7 と記述されたクラスタ不良セクタや予約セクタを含んでいるのでデータとして使用禁止、という風にクラスタを管理していました。

一方、exFAT では利用状況の管理には FAT テーブルを利用せずビットマップで管理しており、クラスタが連続していることが保証されている属性のファイルは FAT 上にクラスタチェーンを形成しません。
つまり、exFAT には FAT によるクラスタチェーンで管理しているファイルと FAT を利用しないファイルの2種類のファイルがあります。

これによるメリットは2つあります。
ビットマップは FAT テーブルに比べてサイズが小さいので空き領域を割り当てる検索処理が素早くできます。空き領域をビットマップで管理するのは他のファイルシステムでも割とよく使われる方法です。
また、ファイルアクセス時に毎回 FAT 上のクラスタチェーンを辿るのはコストがかかるため、クラスタチェーンを辿らなくても連続したクラスタにアクセスできることで高速化に寄与します。

exFAT におけるファイル管理は基本的には FAT 上にクラスタチェーンを生成しないように連続した領域を割り当て、どうしても断片化してしまった時に改めてクラスタチェーンを生成するのが効率的な管理になります。 exFAT という名前でありながら基本的には FAT を利用しないのが exFAT です。

ディレクトリエントリ

FAT も exFAT も32バイト単位のディレクトリエントリという構造体でファイルの情報を管理します。

FAT のディレクトリエントリは FAT12 の時代に設計されたもので、 FAT32 の時代になるとかなり無理のある使い方をしてすでに限界に近い状態でした。
当初、ファイル名は8.3形式の短いファイル名のみサポートしていましたが、その後特殊な属性のディレクトリエントリを繋げることで長いファイル名をサポートし、互換性のために短いファイル名と長いファイル名の2つでファイルを管理していました。

exFAT でもディレクトリエントリの基本サイズは32バイトですが、ディレクトリエントリの構造を大幅に変更することで FAT よりも多くの情報を含めることができるようになり、タイムスタンプの2秒問題などが改善しています。
通常のファイルは1つのディレクトリエントリに情報が収まりきらないため3つ以上のディレクトリエントリを繋げて使用します。
8.3形式のファイル名には対応しておらず、 FAT の長いファイル名と同等の制限の緩いファイル名を使うことができます。

また、細かい違いとして従来サブディレクトリに存在した「.」「..」という存在理由のよくわからないディレクトリエントリは exFAT のボリューム上には存在しません。

メタデータ、大文字テーブル

exFAT では従来の FAT ファイルシステムにはなかったメタデータが増えています。
例えば、先述の空き領域ビットマップはメタデータとして専用のディレクトリエントリがルートディレクトリにあります。

また、 exFAT の特徴的なメタデータとして大文字テーブルというものがあります。
FAT ファイルシステムはもともとファイル名を大文字で管理し、ファイルの検索は大文字小文字を区別しません。
exFAT では大文字に変換するためのテーブルがボリューム上のメタデータとして存在します。*3
大文字テーブルで変換したファイル名からハッシュ値を計算し、ディレクトリエントリのハッシュ値と比較することで大小文字を無視したファイルの検索が高速にできるのが他のファイルシステムにはないユニークな特徴となっています。この部分が特許に絡んでいた気がしますが、ソースを見つけることができませんでした。

ソリッドステートメモリーとの親和性

exFAT は先述のようにクラスタが連続しているファイルは FAT によるクラスタチェーンを経由せず高速にアクセスできます。
また、クラスタサイズやオフセットを調整してソリッドステートメモリーのページサイズと一致させることで効率の良いアクセスが可能になっています。
そのためにソリッドステートメモリーの特性を記述できる拡張属性が定義されています。

*1:なぜ2から始まるのかはよくわかりません

*2:実は FAT32 は要素サイズは 32bit ですが 32bit 全て使っている訳ではありません

*3:しかし仕様書によると内容は固定のようです...

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

ついに某OSの起動画面が出ました。

f:id:neriring16:20190721020613p:plain

まだ動作が怪しいですが...

この辺ならキーボードも普通に動きます。(マウスは死んでます

f:id:neriring16:20190721020631p:plain

某OSも途中で止まります。
cpuid実装してるはずなのに認識されてないのが気になります。

f:id:neriring16:20190721020652p:plain

FreeDOS (32bit) はまだよくわからない動作をします。

f:id:neriring16:20190721020703p:plain

WASMで自作PCエミュレーター Part4

自作エミュレーターVGA に(一部)対応しました!

github.com

今までは UART 経由で端末エミュレーターに接続していました。
DOS やその上で動く多くのソフトウェアは標準入出力という概念があるので、今まではこの方法が簡単に実装できてうまく動いていました。
しかし、世の中には VRAM を直接操作してテキスト表示したり、グラフィックスを扱うソフトもたくさんあります。
また、使っていた端末エミュレーターにも色々と不満が出てきていたので置き換えたいと考えていました。
そんなわけで VGA の実装をはじめたのでした。

V・G・A!

VGA を実装するにあたって問題がひとつありました。このエミュレーターMMIO に対応していません。
要するに VRAM にメモリアクセスしたことを検知して画面を更新することができません。

UART は IO 命令を契機に画面更新ができましたが、それができなくなりました。
画面のレンダリングはとても重い作業なので毎フレーム再描画するわけにもいきません。
解決策としては一定間隔で VRAM 領域をスキャンして変更があった場合に再描画するようにしました。
徹夜で調整した結果、まぁまぁのパフォーマンスが出てるようです。

モード 3 とモード 13 のみ実装しています。モード 12 は VGA = 640x480 を象徴するメジャーな画面モードのひとつではありますが、 MMIO がないと実現不可能なのでおそらく未来永劫実装しません。

PS/2 と JS のキーボード処理の闇

端末エミュレーターを廃止したのでキーボード入力もきちんと実装する必要が出てきました。
JavaScript ではキーイベントで結構細かいところまでキー入力の値が取れるのですが、そこは闇だらけでした。
環境によって取れる値が異なったり、別のキーに対して同じキーコードが割り当てられていたりします。
さらに、英語配列を基準にキーコードを決めてるようで、日本語モードだと記号の対応がぐちゃぐちゃでした。
完全に PS/2 キーボードをエミュレーションしようとすると記号キーの対応が死んでしまうので、 ASCII コードが取れるところは文字が入力したいと判断して ASCII コードを優先するようにしました。

TL; DR

これらの改修でゲームなんかもそれなりに動くようになりました。

f:id:neriring16:20190715001621p:plain

f:id:neriring16:20190715000906p:plain

f:id:neriring16:20190715001010p:plain

f:id:neriring16:20190715001050p:plain

ロングモードと64ビットモードの違い

ロングモードと64ビットモードの違い、分かりますか?

おそらく多くの人が混乱していると思うのでブログにまとめます。(そしてぼくは混乱してないことを祈る

極論を言うと、現代の x86 系プロセッサにはリアルモード、プロテクトモード、ロングモードの3つのモードしかありません *1
仮想8086モード、互換モード、64ビットモードなどというモードは存在しないのです。(え?

リアルモード、プロテクトモード、ロングモードの3つのモードを切り替えるにはシステムレジスタの CR0 の特定のフラグを操作する必要があります。逆にいうとそれ以外の方法では切り替わりません。

では、仮想8086モード、互換モード、64ビットモードはどうでしょう?
これらは eflags やコードセグメントのフラグを操作することで切り替わります。
つまり、割り込みで切り替わります。

一方、リアルモード、プロテクトモード、ロングモードはそれぞれ割り込みの仕組みが違います。(IDT からディスクリプタをロードする大まかな仕組みはよく似ていますが・・・)
割り込みでこれらのモードを行き来することはできません。

ここに大きな違いがあります。

システムとしてはリアルモード、プロテクトモード、ロングモードのどれかで動作しているのに対し、仮想8086モード、互換モード、64ビットモードの3つは単なるコンテキストの違いでしかありません。

最初の x86 系プロセッサの 8086 には制御フラグが flags レジスタしかありませんでした。
このレジスタの中には演算命令の結果でばたばた変わるフラグもあれば、割り込みを禁止するとても危険なフラグまですべてひとつのレジスタで管理していました。
今考えるととてもおろそしい仕様ですが、当時はこれが普通だったようです。

8086 が成功してマルチタスクのための大幅な拡張を施した 80286 が出たとき、この常識が覆されました。
システムの基本的な制御は MSW というレジスタで管理し、 flags レジスタはコンテキストごとの状態を保持するように明確に分離されました。
のちに MSW は 80386 が出たときに CR0 という名前に変わりましたが、基本的な路線は踏襲されました。

仮想8086モードに移行するには必ずプロテクトモードから切り替える必要があり、例外や割り込みが発生するとプロテクトモードの仕組みを使って基本的にはプロテクトモードに戻ります。*2
このことから eflags で切り替わる仮想8086モードはプロテクトモードで動作するシステムの中のコンテキストのひとつということがわかります。

一方、互換モードと64ビットモードはセグメントディスクリプタの L ビットの値で切り替わります。
ロングモードに移行直後は互換モードですが、例外や割り込みが発生するとロングモードの仕組みを使って64ビットモードに切り替わります。
やはりこの2つはロングモードで動作するシステムのコンテキストのひとつです。

プロテクトモードの時代にも16ビットで動作するモードと32ビットで動作するモードがありましたが両者を区別する正式な名前はありませんでした。*3
ロングモードの時代になってわざわざ64ビットモードだけ特別扱いするのはどうなのかな?と思いました。

*1:VMM や SMM は除く

*2:あくまで基本的なので割り込みでプロテクトモードに戻らない拡張機能があるし、タスクゲートで仮想8086モードのタスクに切り替えることは可能な気がします

*3:混在していたwin9Xは悪者扱いでした

WASMでPCエミュレータ作った話 / Part 3

github.com

さいきんはずっとエミュレーター作ってるます。

FreeDOS

ついに、FreeDOS (16bit版) が起動しましたヽ(•̀ω•́ )ゝ✧

f:id:neriring16:20190706200753p:plain

MSDOSはまだどこかおかしいようです。

f:id:neriring16:20190706202805p:plain

Web MIDI

Web MIDI に対応しました。
MPU-401 UART モード互換インターフェースのつもりなので、いろんなソフトから MIDI 機器を制御できるはずです。
また、 iPad で Web MIDI に対応したブラウザと Sound Canvas for iOS などがあれば直接鳴らすこともできます。

f:id:neriring16:20190707202126j:plain

Mac と無線で繋ぐこともできますが、タイミングが厳しくて雑音になりました(´・ω・`)

また、とある MIDI プレイヤーがタイマー割り込みの関係でうまく再生できなかったのでタイマーを補正するようにしました。従来より負荷が少し上がってるかもしれません。

テストたくさん

テストも書き始めましたが、演算命令のテスト項目が山のようにあってどうやってまとめるか試行錯誤中です:;(∩´﹏`∩);:

IBM PC のタイマー事情

IBM PCBIOS は通常、約 55ms / 18.2Hz ごとにカウントしています。
この数値は一体どこから来てどんな意味があるのでしょうか?

まず、 IBM PC で使われているタイマーIC 8254 PIT の動作クロック入力が約 1193182Hz となっています。
すごく中途半端な値に見えますが、これはよく使われている周波数で部品が入手しやすいらしいです。

この 8254 PIT で設定可能な 16bit の最大値である 65536 を設定してみます。
すると約 55ms (約18.2Hz) の周期でタイマー割り込みが発生するようになります。

さらにこのタイマー割り込みで BIOS データエリアの 40:6C にある WORD 値をインクリメントすると、 16bit の限界である 65536 回カウントしたところでおよそ 3600 秒、つまり1時間になります。
40:6C の値がオーバーフローしたら 40:6E にある WORD 値をインクリメントし、そこが 24 になると 24 時間ということで 40:70 に 1 をセットします。(ここだけなぜかカウンターではなくフラグです。)

なるほどうまくできてますね。

55ms という謎の数字にはこんな意味があったのでした。