6809の奇妙な命令でゲームを60%高速化した話

MS-DOS時代に遡るんだが、友人のWard ChristensenはIBMのテクニカルセールスサポートで働いていた。彼らは販売中の全製品をリストアップしたファイルを非公式に管理していて、それはPCで読める形式だった。彼はテキストエディタでそれを検索するのがとても上手だったが、同僚たちが簡単に検索できるようにMS-DOSベースのスタンドアロンプログラムが欲しかった。こうしてPCxREFが生まれた。それは僕が書いたTurbo Pascalベースのプログラムで、検索機能を含んでいた。

最初の実装は、組み込みの文字列マッチングを使った素朴な検索だった。ファイルのサイズとPCの速度のせいで、検索に30秒以上かかることもあった。Wardはもっと速く、はるかに速くしてほしいと言った。

やがて僕は、検索したいテキストを特殊なビットマスクのテーブルに変換するアルゴリズムを思いついた。それは256バイト長のテーブルで、ゼロで初期化されていた。検索文字列の最初の文字がDなら、大文字小文字を区別するために$44と$64のマスクの最初のビットをセットする。ワイルドカード*は1文字分の長さだが、その文字の全ビットをセットする。次に8088のXLAT命令とごく小さなループを使って、検索対象のテキストから1文字を取り込み、それをマスクテーブルのインデックスとして使い、別のレジスタにある既存のフラグとANDし、それをシフトしてキャリー（一致！）をチェックし、ゼロでなければループする。

ファイル全体がRAMにロードされていれば、検索時間は3秒未満に短縮された。細い……