How a 1981 IBM PC was made to play full-motion video
8088 Domination Post-Mortem
Trixter explains how he pulled off 8088 Domination, full-motion video on a 1981 IBM PC, after years of calling it impossible. The trick: only update screen memory where pixels actually change, use stable ordered dithering so local edits stay local, and precompute every delta, run, and slice during encoding because the 8088 can't make those calls in real time.
It sure felt impossible, so that’s why I said it. Then I thought about the problem for 7 years.
- Agingcoder
Having used these machines, this is mind boggling.
- exikyut
([2014])
- akoboldfrying
Always cool to see this come up. I really like the idea of "encoding" the video as... x86 machine instructions!
The hairsplitting nerd in me can't help but point out that the claim in the Part 2 article that the problem of combining deltas is NP hard isn't true. In fact you can solve this optimally in O(n^3) time with DP: Let g(i, j) be the minimum number of bytes needed to encode input deltas i..j as a single (i.e., combined) output delta. Given g(i, j), computing g(i, j+1) takes constant time, so we can compute all of this function's values in O(n^2) total time. Now let f(i, j) be the minimum number of bytes needed to encode input deltas i..j using any sequence of output deltas (combined or not). Note that any such sequence must consist of some number (possibly zero) of optimally encoded output deltas followed by an optimally encoded output delta that itself ends with input delta j. IOW, it must be that f(i, j) is equal to f(i, k) + g(k+1, j) for some k, and there are at most n values of k that we need to try, so we can compute each value of f() in O(n); there are O(n^2) values to compute, so O(n^3) time overall. f(1, n) is then the minimum number of bytes needed to encode the entire list of input deltas, and standard backtracing through the DP matrix can be used to recover the actual sequence of output deltas.