1981年のIBM PCでフルモーション動画を動かした男の全記録
8088 Domination Post-Mortem
1981年製のIBM PC 5150でフルモーション動画を表示する「8088 Domination」をどう作り上げたかの技術解説。全画面を毎フレーム書き換える常識を捨て、フレーム間の差分だけを更新し、画面メモリ書き換えとディスク帯域の時間制約をエンコード段階で管理する設計にたどり着く。CGA向けには隣接ピクセルに依存しないordered ditheringを採用し、差分が連鎖しない工夫を凝らしている。
「全画面を毎フレーム変えなければならない」という考えを捨てる必要がある。適切な映像内容であれば、画面メモリの一部だけを書き換えても、まるで全画面を更新しているかのように見せかけることができるのだ。
- Agingcoder
こういうマシンを使ってきた身としては、これはもう信じられないの一言だ。
- exikyut
（2014年）
- akoboldfrying
これが話題に出てくるのはいつ見ても最高だ。動画を…x86の機械語命令として「エンコード」するというアイデアが本当に好きだ！
ただ、細かいことにこだわるナードな自分としては、Part 2の記事にある「デルタの結合問題はNP困難だ」という主張は正しくない、と指摘せずにはいられない。実はこれはDPでO(n^3)時間で最適に解ける。g(i, j)を、入力デルタi..jを単一の（つまり結合された）出力デルタとしてエンコードするのに必要な最小バイト数としよう。g(i, j)が与えられれば、g(i, j+1)の計算は定数時間で済むので、この関数のすべての値は全体でO(n^2)時間で計算できる。次にf(i, j)を、任意の出力デルタの列（結合してもしなくてもよい）を使って入力デルタi..jをエンコードするのに必要な最小バイト数としよう。このような列は、いくつか（ゼロ個でもよい）の最適にエンコードされた出力デルタの後に、それ自体が入力デルタjで終わる最適にエンコードされた出力デルタが続く形でなければならないことに注意しよう。言い換えれば、あるkに対してf(i, j) = f(i, k) + g(k+1, j)が成り立たねばならず、試す必要のあるkの値は高々n個なので、f()の各値はO(n)で計算できる。計算すべき値はO(n^2)個あるので、全体でO(n^3)時間となる。そしてf(1, n)が入力デルタのリスト全体をエンコードするのに必要な最小バイト数であり、DP行列を標準的にバックトレースすれば、実際の出力デルタの列を復元できる。