Bad Apple!! — One Bit Deep

A port has to satisfy three separate budgets, and they fail in different ways. Storage is how much room the whole animation occupies — exceed it and the port does not exist. Bandwidth is how fast pixels can be pushed to the display — exceed it and the port runs, slowly. Decode is how much work the processor must do per frame to turn stored data into pixels — exceed it and the port stutters, or the decompression eats the time the display needed.

Almost every interesting decision in a Bad Apple port is a trade between these three, and the animation’s one-bit depth is what makes the trade winnable.

2.1 Where the orders of magnitude go

Start from the top. The source animation is commonly worked from at 512 by 384 pixels. As eight-bit greyscale that is 196,608 bytes per frame — about 192 KiB, per frame, before anything else. At even fifteen frames per second no eight-bit micro will ever see the end of it.

Throwing away the greyscale costs nothing, because there was never any greyscale to throw away. Packing eight pixels into each byte brings one frame to 24,576 bytes. That is a factor of eight for free, obtained purely by matching the storage format to the material.

Dropping the resolution is the next lever, and it is nearly free too, for the same reason. The silhouettes are large, simple shapes; they survive brutal downsampling in a way that a photograph or a textured game scene would not. At 64 by 48 — a common small OLED size — a packed one-bit frame is 384 bytes.

384 bytes per frame is still too much. At thirty frames per second across roughly six and a half thousand frames it comes to about 2.5 megabytes, against the 62 kilobytes of flash on a very cheap microcontroller. The last factor of forty has to come from compression, and this is where the ports get inventive.

2.2 Why the image compresses so well

The animation’s structure is almost designed for it, even though it was not.

Runs are long. Scan across a frame and most rows consist of one long white run, one long black run, and one more white run. Run-length encoding — storing each stretch of identical pixels as a value and a count — is the first tool everyone reaches for, and it works far better here than on any natural image.

Frames barely change. Successive frames differ over a small fraction of their area. Storing the difference between one frame and the next rather than the frame itself throws away most of the remaining data.

The vocabulary is small. Divide a frame into eight-by-eight tiles and most tiles are entirely black or entirely white. The remainder are edges, and the set of distinct edge tiles that appear across the whole animation is far smaller than the 2^64 that eight-by-eight one-bit tiles could in principle take. That observation produces the technique that appears in the most aggressive ports independently: build a codebook of tiles, usually by k-means clustering over every tile in the animation, then store each frame as a sequence of indices into it. A frame stops being three thousand pixels and becomes forty-eight tile numbers.

Layered on top of tile coding come the general-purpose methods — Huffman coding for the tile indices, LZSS or LZ77 back-references for repeated sequences, and in the most extreme case arithmetic range coding.

The 512-by-384 Minecraft implementation is the counter-example that proves the rule: it renders in grayscale with six levels rather than pure black and white, and pays for it with a rendering bottleneck rather than a storage one, because in that environment the constraint is world updates rather than bytes.

2.3 Two worked examples

The Commodore 64 demo Bad Apple 64, released by Onslaught on 29 June 2014, fits more than two thousand frames onto a single floppy disk in roughly 170 kilobytes and plays them at twelve frames per second, streaming continuously from the drive. That works out to about seventy bytes per frame, on a machine running at one megahertz. The significant constraint there was not storage but the disk: the data has to arrive faster than it is consumed, from a drive famous for being slow.

At the other extreme, the badderapple project targets a CH32V006 — a RISC-V microcontroller with 62 kilobytes of flash and 8 kilobytes of RAM — driving a 64-by-48 OLED. It fits all 6,570 frames, plus the audio, plus the playback code, into 64.5 kilobytes total, at thirty frames per second. The published figure for the video stream alone is 75.626 bits per frame, or about nine and a half bytes. Getting there required stacking nearly every technique named above: an eight-by-eight glyph codebook generated by k-means, range coding, LZSS matching, and a de-blocking filter to soften the tile boundaries the codebook introduces. The audio is separately compressed as a Huffman-coded MIDI interpretation with reverse-LZSS back-references and Exponential-Golomb coding for distances and lengths.

The author’s summary of the exercise is the most quotable line in the whole subject, and it generalises well beyond this animation: finding a way to express the data more concisely obliterates any compression algorithm that could be thrown at the problem.

2.4 Decode is the budget people forget

Compression is not free. A frame stored in nine bytes has to be expanded into three thousand pixels in less than a thirtieth of a second, on a processor with no floating point, no cache, and eight kilobytes of working memory. Every technique that improves storage makes decode harder, and the best-compressed ports are the ones that found schemes cheap to decompress rather than merely small.

This is why run-length and tile codebooks dominate over general-purpose compressors. Both decode in a straight line with almost no state: read an index, copy a tile, repeat. A general algorithm might store the same data more tightly and be unable to unpack it fast enough to matter.

It is also why the Apple II implementation uses the rotation speed of the floppy drive as its clock — the machine has no timer — and interleaves sector reads with drawing, because reading a sector blocks the processor. Storage, bandwidth and decode there are not three separate budgets but one tangled one.

2.5 The extreme case: no decode at all

The logical endpoint is to remove the processor. One documented project drives a composite video signal from a breadboard of standard CMOS logic — binary counters, shift registers and an EPROM — with no CPU, no RAM, and no framebuffer anywhere in the system. The video stream is encoded in software beforehand and decompressed by dedicated logic during playback, with pixels generated on the fly at exactly the rate the television consumes them. There is no frame in memory at any instant, because there is nowhere to put one.

That is the clearest statement of what the one-bit format buys. A frame does not have to exist as an object. It only has to be produced, left to right, top to bottom, in time.