8088 Domination Post-Mortem

8088 Domination Post-Mortem, Part 1

これらの投稿では、私が8088 Dominationを作成した技術的な詳細を解説します。これは、1981年製のIBM PCでかなりまともなフルモーションビデオを表示するプログラムです。さらに読み進める前に、もしこのプロダクションを見たことがなければ、まずそれに慣れておくのが良いでしょう。コンポジット出力ジャックを介してテレビに接続された1981年製IBM PC 5150で実行されている様子を示すビデオはこちらです。

…そして、上記のビデオの信憑性を疑うのであれば、プロダクションをダウンロードして、ご自身のビンテージハードウェアで実行して証明することもできます。

この書き込み全体を通して、過去形（例：設計段階での私の思考プロセス）と現在形（特定の目標を達成する方法を説明する場合）が混在することについて、あらかじめお詫び申し上げます。

背景

私は何十年もデスクトップデジタルビデオに魅了されてきました。1990年代初頭の最初のVideo For Windowsツールから始まり、初期のキャプチャハードウェア（Media Vision Pro Movie Spectrumなど、MSV1/CRAMフォーマットに直接キャプチャするもの）を使用して、デスクトップビデオとその可能性をいじってきました。

もちろん、私は1990年代初頭からデモシーンにも魅了されており、これほど好きなものが2つあれば、それらを融合させる方法を見つけるものです。私のデモシーンプロダクションの多くは、何らかの形でビデオを一部または全部に含んでいます。Grind（1993年）は、音楽に合わせて完璧に踊るSpring Breakの女の子を表示するmodplayerでした。 Explicit（1996年）の終盤には、音楽に合わせて踊るクラブダンサーがキューブに埋め込まれており、もちろん8088 Corruption（2004年）は、1981年製IBM PCでFMVを表示し、私の15分の多くを費やしました。

8088 Corruptionは、その素晴らしいビデオ品質で認められたわけではありませんが、そのような限られたプラットフォームでFMVを表示するという問題に対する斬新な解決策で認められました。その解決策は、40×25テキストモードを使用することでした。なぜなら、それはビデオメモリの量において唯一のモードであり、システムを過負荷にしたり、目障りなアーティファクトを引き起こしたりすることなく、フレームごとに完全に変更できる量だったからです。

2007年に講演で8088 Corruptionについて詳しく説明しましたが、その講演で、CGAをグラフィックスモードで使用してFMVを表示することは不可能だと説明しました。これは、CGAグラフィックスモードが8088 Corruptionが処理していた量の8倍のビデオメモリを使用するためです。たとえ24fpsのビデオを仮定した単純な計算でも、1秒あたりに更新する必要があるデータの量（24fps * 16KB = 384KB/s）は、IBM PCの能力を超えていることがわかります。CGA RAMは240KB/sのレートでしか変更できず、当時のほとんどのハードドライブは約90KB/sで動作していました。それは不可能に感じられたので、そう言いました。

それから7年間、この問題について考え続けました。

期待値の調整

過去数年間、この「不可能」な問題について考えているうちに、いくつかのことに気づきました。最も基本的な気づきは、説得力のあるFMVを表示するために、常に画面上のすべてのピクセルを変更する必要はないということです。伝統的なアニメーションや「トークヘッド」のニュース放送のように、フレームの一部しか動いていない場合、すべてのピクセルが変化しているわけではありません。しかし、フレーム内のすべてのピクセルが変化している場合でも、わずかに変化しているだけかもしれません…そして、わずかに変化しているだけなら、変更しないというごまかしをしても、視聴者は気づかないかもしれません。したがって、フレームごとに画面全体を変更しなければならないという考えを捨てる必要があります。適切な画像コンテンツがあれば、画面メモリの一部だけを変更しても、画面全体を変更しているように見せかけることができます。

［画像: delta_anim］

左：白黒＝差分、グレー＝未変更。右：変更のみを適用した後のユーザーが見るもの

もう一つの気づきは、システムで利用可能な帯域幅の種類を再評価したときに得られました。以前は、「40×25テキストモード2KのRAM」という定義を、画面上で変更できるものの限界として使用していました。しかし、「変更される2Kのデータ」が真の限界ではありません。むしろ、「2Kを変更するのにかかる時間を超えないこと」です。言い換えれば、真の限界は画面メモリを更新するフレームあたりの特定の時間量子を超えないことであり、どれだけの画面メモリを変更しても関係ありません。

これはディスクI/Oについても同様の考えにつながりました。Corruptionでは、ディスク帯域幅を、必要なフレームレートの周波数での固定長読み取りのシリーズとして扱いました。その結果、Corruptionは固定長のビデオ+オーディオパケットを使用するため、（フレームレート * パケットサイズ）が利用可能なディスク帯域幅を下回ることが保証されていました。しかし、それに従う理由はありません。真の限界はディスクI/O自体であり、ハードウェアが提供できる量を超えない限り、任意の量のディスクを特定の期間内に読み取ることができました。これにより、ビデオ+オーディオパケットは可変長にできるという認識につながりました。

これらのアイデアやその他のアイデアの組み合わせにより、元の「グラフィックスモードでのFMV」という要件を満たすことができるシステムが設計されました。つまり、次のシステムが必要です。

• フレーム間の差分を見つけ、その差分のみで画面メモリを更新する
• 画面メモリの変更にかかる時間と、それを超えないように追跡する
• 使用されるディスクスペースの量を追跡し、ディスクサブシステムの転送レートを超えないようにする
• 最も重要なのは、ソース画像の表示が完了する前にCPU時間またはディスク帯域幅が不足した場合に、優雅に劣化すること

IBM PCはこれらの決定をリアルタイムで行うには（帯域幅も不足しているため）十分に速くないため、これらの制約のほとんど（すべてではないにしても）はエンコードフェーズで処理する必要がありました。そこでは、ほぼ無制限の時間があります。それはまた、これらの制約のほとんどが実際にはデータ管理の問題であることを意味します。それについては後で説明します。しかし、コードを1行書く前に、少し戻って、24ビットカラー画像をCGAカードでひどいものに見えないものに変換する方法を見てみましょう。

CGA FMVグラフィックス変換

CGAの簡単な説明：CGAはIBM PCの最初のカラーグラフィックス標準であり、画面の内容を保持するための16KBのメモリが含まれています。そのメモリは、見た目は異なるが、実際にはすべて同じであるいくつかの異なるグラフィックスモードとして表示できます。幅80バイト列×高さ200ライン。それらの80バイト列は、いくつかの異なる方法でスライスできます。

• 640×200、2色（1ピクセルあたり1ビット）
• 320×200、4色（1ピクセルあたり2ビット）
• 160×200、16色（1ピクセルあたり4ビット）

実際にそれらがどのように見えるか見てみましょう。ここに pretty hummingbird があります。

［画像: hum_original］

…そして、ここに、特別な処理なしで、これらの3つの基本的な選択肢に変換されたhummingbirdがあります。

［画像: hum_160_nodither］

160×200、16色

［画像: hum_320_nodither］

320×200、4色、パレット1

［画像: 640x200, 2 colors］

640×200、2色

すでに、聴衆の中のグラフィックスプログラマーはDITHER THAT SHITと叫んでいるでしょう、そして彼らは通常正しいでしょう。しかし、人々が一般的に知っているディザリングのほとんどはエラー拡散ディザリングであり、エラー差分が画像全体に伝播することを意味します。これは、フレーム間の変更を記録するシステムにとっては良い考えではありません。なぜなら、ソースマテリアルで単一のピクセルが変更された場合、変更後のディザアルゴリズムの行走査順序のすべてのピクセルが変更されるからです。私たちが求めているのは、いわゆる安定したまたは局所的なディザリングであり、各出力ピクセルの値はその隣接ピクセルに依存しないものです。そうすれば、ソースマテリアルの局所的な領域のみが変更された場合、宛先ディザのその領域のみが変更されます。

エラー伝播を空間的に最小限に抑えるいくつかの変更された代替ディザリング（例：Riemersma dither、Hilbert curveに沿ってディザリングするもの）はありますが、真に局所的なディザリングアルゴリズムとして私が知っている唯一のものは、オーダーディザリング、またはBayerディザリングと呼ばれるものです。カラーオーダーディザリングに関する最高の公開研究の一部はBisqwit（「Yliluoma’s arbitrary-palette positional dithering algorithm」）によるものですので、ここでは概念を説明しようとはしません。代わりにそれを参照してください。

私たちのソースに基本的なオーダーディザリングを適用すると、3つのグラフィックスモードに変換されたhummingbirdは次のようになります。

［画像: 160x200, 16 colors, ordered dither］

160×200、16色、オーダーディザ

［画像: 320x200, 4 colors, palette 1, ordered dither］

320×200、4色、パレット1、オーダーディザ

［画像: 640x200, 2 colors, ordered dither］

640×200、2色、オーダーディザ

はるかに見栄えが良く、ソースで1ピクセルしか変更されない場合に、ディザがフレーム間に大規模な違いを生み出す心配をする必要がありません。

これらの3つのモードはそれぞれ独自の点で実行可能に見えますが、Dominationでは、中央のモード（320×200、4色）を破棄するという決定を下さなければなりませんでした。これは、16色モードと2色モードがCGAカードのコンポジット出力ジャックを介して正しく表示され、コンポでネイティブハードウェアをプロジェクターに接続して提示する必要があったためです。したがって、私の選択肢は160x200x16と640x200x2に限定されました。

変更の管理

8088で画面メモリを変更する最も速い方法は、REP MOVSBを使用して線形バイトシーケンスをコピーするか、REP STOSBを使用して線形バイトシーケンス全体を同じ値に設定することです。これを念頭に置いて、変更されたバイトの開始オフセットと終了オフセットとして各変更を追跡することを選択しました。これは、「再生」する変更を正確な方法に最も近いものでした。混乱を減らすために、用語を採用しました。変更されたバイトの領域を指すために「デルタ」という用語を造り、デルタをさらに「スライス」（すべてのバイトが同じではないデルタ）と「ラン」（すべてのバイトが同じであるデルタ）に分類しました。「ラン」はREP STOSBを使用して画面メモリを非常に迅速に埋めることができるため、それらを追跡する価値がありました。これが私が使用した実際のデータ構造です。

  TDelta=object(TObject)
    startOfs:word;         {starting offset of delta in buffer (first changed byte)}
    endOfs:word;           {ending offset of delta in buffer (last changed byte)}
                           {rest are calculated during insert or other operations:}
    dtype:deltaType;       {slice or run}
    fillvalue:byte;        {for informational purposes only, not used for anything}
    blength:word;          {length of delta in bytes}
    numPixelsChanged:word; {# of pixels changed in the entire delta}
    REPcycleCost:real;     {different whether slice or run}
    frozen:boolean;        {flag used to control various optimization phases}

    Constructor Init(starto,endo:word);
    Destructor Done; virtual;
  end;

これらのすべてのデルタは、それらを収集および管理するための良い構造を必要としたため、Turbo Pascal 7のデータ構造であるTSortedCollection（ソート済み連結リストに類似）を使用することにしました。デルタはこのリストに追加され、次の基準のさまざまな組み合わせでソート順序が維持されました。

1. より大きい/より長いデルタを、より小さい/より短いデルタの前に配置する
2. 同じ長さの場合、「ラン」を「スライス」の前に配置する
3. すべてのランをそのフィル値でソートする
4. 同じ長さの場合、すべてのデルタをインターレースされた開始オフセットでソートする

ソート順序は、ここで言及するには奇妙なことのように思えるかもしれません。プロジェクトの成功に貢献したため、言及しました。それは後で多くのデータ処理問題を解決しました。それは非常に役立ったので、詳細に検討する価値があると思います。

1. より大きい/より短いデルタを、より小さい/より短いデルタの前に配置する：リストの上から下へデルタを処理すると、帯域幅がなくなるまで、画面の最大の領域が最初に変更されます。帯域幅の枯渇によりリスト全体を完全に破棄することを決定した場合、リストの下部にある最小の変更（視覚的にはあまり重要ではなく、数ピクセルしか変更しないもの）のみが破棄されます。
2. 同じ長さの場合、「ラン」を「スライス」の前に配置する：これによりランが優先されました。なぜなら、REP STOSBを使用して画面メモリの領域を設定することは、同じ領域をREP MOVSBでコピーしようとするよりも高速で小さいためです。
3. すべてのランをそのフィル値でソートする：これはエンコードフェーズで役立ちました。そこで、フィル値を一度設定し、該当する場合は後続のランに対してその値をキャッシュすることができました。同様のフィル値がすぐ近くにない場合、それはできなかったでしょう。
4. 同じ長さの場合、すべてのデルタをインターレースされた開始オフセットでソートする：これは美的選択でした。もし私がすべてのデルタがまったく同じ長さの領域（画面の長方形領域など）を変更しなければならない場合、これは変更がやや線形の上から下への順序で「ペイント」されることを可能にしました。これは、CGAのフレームバッファは線形に組織化されているのではなく、インターレースされているため必要です。

好奇心旺盛な方のために、ソート演算子は次のようになります。

Function TDeltas.Compare;
{
We want to maximize motion fidelity, so we are going to make our lives
easier and sort deltas by size.
Note that the comparisons are reversed -- that's because we want the largest
deltas at the beginning of the list.  (-1 means beginning of collection.)
- We add a second comparison so that deltas of the same length are sorted
by cycle execution time; this keeps runs prioritized over slices in terms
of what to prioritize if our bandwidth gets starved.
- We add a third comparison so that runs of the same run value
are kept together, so that we can cache the run value.
- We can optionally add a fourth comparison so that, all things being equal,
deltas are sorted by start offset compensated for CGA interlaced memory layout
(this is what I'm colloquially calling "Dave Murry interlace handling"
based on how Dave handled it in the PC booter Sierra Championship Boxing).
}

var
  k1so,k2so:word;

begin
  k1so:=PDelta(Key1)^.startofs;
  k2so:=PDelta(Key2)^.startofs;
  if MurryHandling then begin
    {if k1so > screenRAMsize div 2 then k1so:=k1so-(screenRAMsize div 2);}
    {if k2so > screenRAMsize div 2 then k2so:=k2so-(screenRAMsize div 2);}
    k1so:=k1so AND $1fff;
    k2so:=k2so AND $1fff;
  end;
  {sort by delta length}
  if PDelta(Key1)^.blength > PDelta(Key2)^.blength
    then Compare := -1
    else if PDelta(Key1)^.blength  PDelta(Key2)^.fillvalue
            then Compare := -1
            else if PDelta(Key1)^.fillvalue < PDelta(Key2)^.fillvalue
              then Compare := 1
              {sort deltas by start offset}
              else if k1so  k2so
                  then Compare := 1
                  else Compare := 0;
end;

データ構造が確定したら、1つのビデオフレーム分の変更のエンコードは、次のことを行う単純な問題になります。

1. 既存のフレームと新しいソース画像をスキャンして差分を見つけ、見つかった各差分をデルタリストデータ構造に挿入する
2. 変更をペイントするために利用可能なCPU時間とディスク帯域幅の量（「バイトプール」と「サイクルプール」）を決定する
3. リスト内の各デルタについて、最初から始めて最後に反復する。
   1. このデルタをペイントするためのサイクルとバイトのコストを推定する
   2. サイクルまたはバイトプールがこれらのコストによって枯渇しない場合、デルタをディスクにエンコードしてからリストから削除し、プールを更新する
   3. プールが1つでも枯渇する場合、このデルタをスキップして次のデルタに進む。これはおそらくより小さく、またはより高速（またはその両方）であり、プールを枯渇させる可能性がより高い。
4. リストを空にすると、フレームの処理は完了です。
5. リストの終わりに達した場合、フレームの「時間」がなくなったため、次のいずれかを行う必要があります。
   1. 既存のソース画像が完全に表示される機会を与えるために、リストを再度通過して完了するために次のフレームを費やす、または：
   2. 残りを破棄して、新しいソース画像の作業を開始する

それがほぼすべてです。数週間後にソースをリリースするとき、コードが上記のロジックに非常に近いことを確認できます。しかし、再生パフォーマンスにとって重要な、まだ説明していない非常に重要な詳細が1つあります。それは、「デルタをディスクにエンコードする」とは具体的に何を意味するのか、そしてエンコードされたデルタを画面メモリにできるだけ速く再生するにはどうすればよいかということです。その問題に対する独自の解決策をどのように思いついたかについては、私たちのスリリングな物語の結論に進んでください。