Bad Apple in 65 Kilobytes

Hackaday Supercon 2026 (Nov 6-8)

Charles Lohr + Evan Fletcher / rev -

Storyboard by Μμ
Animation by Anira
Original Music by ZUN
Newer revision by nomico
MIDI by cherry_berry17
What is Bad Apple?
  • Started as a storyboard
  • Was animated
  • Blew up
  • Like Doom
  •  
  • People ran it on everything.
13¢
Badder Apple
  • Started 10 years ago
  • Originally for the ESP8266
  • Tried lots of compression schemes
  • Iterated but never found an interesting take
  • Until...
My Rules
  • Must all fit and run on the 006
  • Run on an OLED (64x48 px) and be recognizable
  • Full Length (3:39) and 30FPS (~95:1 ratio)
  • Have audio - bleep-bloops are OK.
  • Be human-authored. 
  • Memory region         Used Size  Region Size  %age Used
           FLASH:       62976 B        62 KB     99.19%
      BOOTLOADER:        3324 B       3328 B     99.88%
             RAM:        8064 B         8 KB     98.44%
Structural Encoding
  • Perfect symbol compression only gets so far.
  • Things have structure or repeated patterns.
  • What if we look for runs? 
        aaaaaabaaaacaaaaa
        a(5x)b(0x)a(3x)c(0x)a(4x)
Output / Input References
Output-ref
  • Common (gzip, zstd)
  • Typically better
  • Buffer output
  • RAM hungry
Input-ref
  • Unusual
  • Typically worse
  • Random input access
  • Tiny RAM
😵‍💫
Tile Compression
  • Onslaught got it to 170kB @ 12FPS
  • I needed it at 64kB @ 30FPS
  • Let's use tiles, and look at gzip, zstd...
Getting off the ground
  • Raster-based RLE
  • Zone updates
  • Originally targeting the ESP8286
  • But then...
How hard could it be?
  • Let's use state-of-the-art HEVC compression.
170kB
Oof
Structual Encoding
  • But we can do better!
  • Look for patterns not just runs.
  • Lempel-Ziv-Storer-Szymanski (Back-references)
What else has structure?
80kB 🫤
Needs improvement
  • Need greyscale (can't do?)
  • Too big (80kB)
  • You can see blocks
  • Low visual quality
Let's Solve Audio First
  • Uncompressed: 42MB
  • Compressed (opus): 219kB
  • Could do MIDI: 17kB
Huffman Trees
  • Some notes are more common than others.
  • Some note lengths are more common than others.
  • Huffman trees are great for this.
  • Theoretically optimal (bit-boundaries). 
ddddbddddcddcdddddcdddddaddddccc
SymbolCount
a1
b1
c6
d24
 
a (1)
 
b (1)
 
c (6)
 
d (24)
SymbolCount
a | b2
c6
d24
 
  a|b(2)
 /     \ 
a(1)  b(1)
 
c (6)
 
d (24)
SymbolCount
a | b | c8
d24
 
    a|b|c(8)
     /     \
  a|b(2)   c(6)  
 /     \ 
a(1)  b(1)
 
d (24)
SymbolCount
a | b | c | d32
 
         a|b|c|d(32)
          /      \
     a|b|c(8)   d(24)
     /     \
  a|b(2)   c(6)  
 /     \ 
a(1)  b(1)
SymbolEncoding
a000
b001
c01
d1
 
         a|b|c|d(32)
          /0     \1
     a|b|c(8)   d(24)
     /0    \1
  a|b(2)   c(6)  
 /0    \1
a(1)  b(1)
SymbolEncoding
a000
b001
c01
d1
 
         a|b|c|d(32)
          /0     \1
     a|b|c(8)   d(24)
     /0    \1
  a|b(2)   c(6)  
 /0    \1
a(1)  b(1)
 
111100111110111011111101111110001111010101
Only 43 bits for 32 symbols!
Exponential-Golomb Encoding
decbin+1bin digs-1uegolomb
0101
1101010
2111011
3100200100
4101200101
5110200110
6111200111
7100030001000
8100130001001
numunsbin+1segolomb
0011
1110010
−1211011
2310000100
−2410100101
3511000110
−3611100111
4710000001000
−4810010001001
Exponential-Golomb Encoding
  • Use fewer bits for smaller numbers.
  • Use more bits for bigger numbers.
  • Easy to encode/decode.
  • No need to store a table!
  • Extensively used in H.264 and H.265
K-means
  • Brother and Sister in Law
  • Scales to 64-dimensions well
  • Easily tuneable, for more or less clusters
  • Very fast

CompressionSize
Raw .dat3820 (100%)
Huffman (1 table)1644 (43%)
Huffman (3 table)1516 (40%)
VPX (no LZSS)1680 (44%)
VPX (forward LZSS)665 (17.4%)
VPX (reverse LZSS)673 (17.6%)
Huffman (2-table+LZSS)704 (18.4%)
Huffman (2 table+reverse LZSS)856 (22.4%)
gzip -9 (for reference)682
zstd -9 (for reference)724
 
int SpeedtropyEmbeddedRead( uint8_t prob )
{
	while( range <= (0x10000) )
	{
		uint8_t data = *(bitstream++);
		range <<= 8;
		value = (value << 8) | data;
	}

	uint32_t split = (range>>8) * prob;
	int bit = value >= split;

	if( !bit )
		range = split;
	else
	{
		value -= split;
		range -= split;
	}
	// 8 asm instructions in fast-path, 18 in slow-path.
	return bit;
}

CompressionSize
Raw .dat3820 (100%)
Huffman (1 table)1644 (43%)
Huffman (3 table)1516 (40%)
VPX (no LZSS)1680 (44%)
VPX (forward LZSS)665 (17.4%)
VPX (reverse LZSS)673 (17.6%)
Huffman (2-table+LZSS)704 (18.4%)
Huffman (2 table+reverse LZSS)†856 (22.4%)
gzip -9 (for reference)682
zstd -9 (for reference)724
VPX or "Binary Range Coding"
  • Can be arbitrary.
  • Probabilities can change per-read.
  • VPX is a "special" case of range coding.
    • VPX from google's VP8, VP9 video codecs.
Better than Huffman?

  • Huffman is optimal
    • (but only by-bit)
  • Fractions of a bit!
  • Arithmatic Coding, Asymmetric numeral systems, Range Coding?
  • Under the umbrella term "entropy coding"
  • Lots of tightly related concepts.
Reorder Data
  • Tiles are stored as 32-bit
  • Raster order or depth order?
  • [x][y][t] vs [t][x][y].
  • Changes the locality of the data.
Needs improvement
  • Need greyscale (can't do?)Need greyscale (can't do?)
  • Too big (80kB)
  • You can see blocks
  • Low visual quality
Entropy Trees
  • VPX + Speedtropy is great for individual bits.
  • How would we specify a tile?

SymBinChance
A0065%
B0120%
C1010%
D115%
 
         (A|B|C|D)
       /85%       \15%
    (A|B)        (C|D)
   /76% \24%    /67% \33%
  A      B     C      D

Credit: Wikipedia Binary Tree
85%76%67%
Bit order
doesn't matter.
Tree only overhead
Needs improvement
  • Need greyscale (can't do?)
  • Too big (80kB)Too big (80kB)
  • You can see blocks
  • Low visual quality
Deblocking Filter
  • Idea stolen from h.264
  • Feather edges of blocks
  • Only need one pixel
  • Must be performed
    horizontally and
    vertically.


Needs improvement
  • Need greyscale (can't do?)
  • Too big (80kB)
  • You can see blocksYou can see blocks
  • Low visual quality
Framing as a Machine Learning Problem
  • Use a semantic loss function
    • Cares less about per-pixel brightness
    • Cares more about “semantic content”
  • Write the video rendering as a PyTorch problem
    • Optimize outputs as nn.parameters: tiles, sequence
    • Use torch autodiff → Everything needs to be differentiable
  • Optimize outputs (tiles, sequence) as nn.parameter-s
    • Requires some alternate representations
  • Add in an optical flow target for motion
Hero Cell

Optimization: Tile Edges
Optimization
How hard could it be?
Hero Cell Editor
It works!
Monochrome

Raw K-Means
Final

De-Blocking Filter
Video Rendering: Optical Flow

Lucas-Kanade Optical Flow
Needs improvement
  • Need greyscale (can't do?)
  • Too big (80kB)
  • You can see blocks
  • Low visual qualityLow visual quality
  • It actually needs to work
Outta time
Complete the Owl
  • Compress Video
  • Decompress Video
  • Write the player in the bootloader
  • 3328 bytes, let's goooo
Neighbor Tile Blending
Simulate firmware’s bitwise blending filter on block edges
Convert truth table to trilinear lut for fp32 eval:
f( left, center, right ) → new_center
Quantization

  • Pass 1: Optimize in fp32
    • Produces better-than-display output
  • Pass 2: Quantized fine-tune
    • Recovers detail lost at 3 gray levels

Choosing Tiles from Categorical Distributions
“Sequence”
P(tile) @ (x, y, t)
⮕
@ frame N

Categorical distribution
P(tile) for this spot & time
Assembling Frames from Tiles
+
Per-Frame Tile Idx
@ Each Location
⮕
tiles = np.fromfile("blocks.dat", dtype=np.float32).reshape(-1, 8, 8)
stream = np.fromfile("stream.dat", dtype=np.int32).reshape(-1, 48//8, 64//8)
assembled_tiles = tiles[stream]
assembled_tiles = assembled_tiles.transpose(0, 1, 3, 2, 4)
assembled_images = assembled_tiles.reshape(stream.shape[ 0 ],
                                            stream.shape[ 1 ] * 8,
                                            stream.shape[ 2 ] * 8)
block_weights = F.one_hot( self.sequence[frame_idxs , ...].argmax( dim = -1),
                           num_classes = self.sequence.size( -1 )
                         ).float()
uf_reconstructed = torch.matmul( block_weights,
                                 block_rep.view( self.n_blocks, block_len)
                               ).permute( 0, 2, 1)
reconstructed = self.fold(uf_reconstructed)
Framing as a Machine Learning Problem
  • Very discrete space - Hard to take derivatives
    • 3 gray levels
    • Discrete choice of which tile goes in which square
  • Interconnected problem space
    • Tile blending → Replacing one tile changes 8 neighbors
    • Moving video + few tiles → Replacing a tile generates motion
  • Still needs to compress nicely
Framing as a Machine Learning Problem
  • Tiles represented natively
    • Just an array of 256 8x8 images
  • Categorical logits for sequences
    • 256 bins, one per tile...
    • For each tile spot in video (x 48)...
    • For every frame (x 6572)
  • Total 80.77M params (~323 MB)
    • ~80M sequence params
    • + 16,384 tiles
Horizontal De-Blocking Filter
  • Gamma-correct:
    0→0, 1→1, 2→3
  • T + ( N + P + 1 ) / 2 - 1
  • Need to unpack pixels
  • 5 Operations Per Pixel (after unpack)
  • Too Slow (~72 op/8px)
  • But what if?
We make the 13¢ μC do SIMD
  • Make a full truth table for all in-and-outs
  • Use a web converter to decompose the math into gates.
  • We only need 2-bit math
  • Turn it into C code.
Operations are 32-bits
void EmitEdge( uint16_t tgprev, uint16_t tg, uint16_t tgnext )
{
    // pixel data is to compute 8-pixels-at-a-time. The MSB for each pixel
    // is the top byte, and the LSB for each pixel is the bottom byte.

    uint16_t A = tgprev >> 8;
    uint16_t B = tgprev;      // implied & 0xff
    uint16_t C = tgnext >> 8;
    uint16_t D = tgnext;      // implied & 0xff
    uint16_t E = tg >> 8;
    uint16_t F = tg;          // implied & 0xff

    int tghi = (D&E)|(B&E)|(B&C&F)|(A&D&F); // 8 bits worth of MSBs
    int tglo = E|C|A|(D&F)|(B&F)|(B&D);     // 8 bits worth of LSBs

    PMEmit( (tghi << 8) | tglo ); // Write to intermediate framebuffer.
}
Not outta time
Not outta time
Build
Build
Rawdraw
Web Viewer

Web Demo