借り初めのひみつきち

仮ブログです。

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

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

このソフトウェアはビットマップフォントを編集することができます。
ビットマップフォントというのは名前の通りフォントデータをピクセル単位のビットマップで扱うフォント形式で、昔の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 バイトになりました。

github.com

これ以上小さくするには使われていないヘッダフィールドに別のヘッダーを埋め込むようなテクニックが必要になりますが、 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 の部分だけでひとつのアプリケーションになっている場合もありました。

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 などのメモリ上の特定のビット操作をアトミックに扱う事ができます。

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