Jim's Depository

I have been writing a little dashboard renderer for embedded systems, and it wants to answer HTTP requests with a picture of the screen. That sentence hides a problem: the picture is bigger than the memory.

A 320×240 display at four bytes per pixel is 307,200 bytes of framebuffer. The machines I care about have tens of kilobytes of RAM. The renderer already deals with this by drawing in bands — lay the scene out once, then render it 28 rows at a time into a buffer of 30KB or so, ship those rows somewhere, rewind, render the next band. The display driver is happy to eat bands.

But an HTTP client wants an image file, and image files want to be compressed, and compressors famously want memory. zlib's deflate, at its default settings, wants about a quarter megabyte of workspace — roughly ten times the RAM budget, for the compressor alone.

Here is the trick this post is about: you can write a PNG encoder in about two hundred lines that compresses runs of identical pixels, holds about five kilobytes of state, streams its output as it goes, and produces files that every browser and image decoder written since 1996 opens without complaint. No custom format, no decoder to ship, no JavaScript to unpack anything. The secret is that DEFLATE — the only compression PNG speaks — contains a tiny, pre-agreed-upon subset that amounts to run-length encoding, and you can emit just that subset and ignore the rest.

What is actually in a PNG file

Strip away the mystique and a PNG is a small, orderly thing:

• An 8-byte signature: 137 80 78 71 13 10 26 10.
• A series of chunks, each being a 4-byte big-endian length, a 4-byte type, the payload, and a CRC-32 of the type and payload.
• Three chunk types are mandatory. IHDR holds width, height, bit depth, and color type in 13 bytes. One or more IDAT chunks carry the pixel data. IEND says goodbye.

The pixel data inside the IDAT chunks is a single zlib stream, compressing every scanline concatenated top to bottom, with one twist: each scanline is preceded by a filter byte saying how that row was predicted from its neighbors before compression. Filter 0 means "no prediction, raw bytes," and that is the only filter we will use. (The other filters — Sub, Up, Paeth — are how serious encoders squeeze gradients. They cost memory: you need the previous row around. We decline.)

A zlib stream is itself pleasantly small: a 2-byte header, a DEFLATE stream, and an Adler-32 checksum of the uncompressed data. Yes, that means a PNG carries two different checksums from two different design lineages. Standards are like that.

So the encoder's whole output plan is: signature, IHDR, some IDAT chunks carrying a deflate stream, IEND. The only interesting part is the deflate stream.

The pre-agreed Huffman tables

DEFLATE (RFC 1951) compresses with two mechanisms layered together: LZ77 — "the next N bytes are a copy of the bytes D positions back" — and Huffman coding of the symbols that express both literals and those copy instructions.

A deflate stream is a series of blocks, and each block declares its type in a 3-bit header. Type 2 blocks carry custom Huffman tables tuned to the data — that is where real compressors live, and where the memory goes. But type 1 blocks use fixed Huffman tables that are printed in the RFC itself. Both sides already know them. Nothing is transmitted, nothing is computed, nothing is stored:

symbols        meaning                 code length
-------------  ----------------------  -----------
0–143          literal bytes 0–143     8 bits
144–255        literal bytes 144–255   9 bits
256            end of block            7 bits
257–279        copy lengths 3–114      7 bits
280–287        copy lengths 115–258    8 bits
distance 0–29  copy distances 1–32768  5 bits

Emitting a literal byte is a table lookup and a bit-shove. Emitting a copy is a length symbol (plus a few extra bits for lengths the symbols don't name exactly), then a 5-bit distance code (plus extra bits, which we will never need). The entire "Huffman coder" is a page of arithmetic. There is no tree, no frequency counting, no table in RAM beyond what the code itself expresses.

The part that is secretly RLE

Now the observation that makes the whole thing work. LZ77's copy instruction is allowed to reach back a distance shorter than the length being copied. A copy at distance 4 says: go back four bytes — to the previous pixel — and copy from there. As copied bytes enter the output, the copy can keep feeding itself for the whole run. For four-byte pixels, distance 4 is exactly "repeat the previous pixel."

That is run-length encoding, wearing deflate as a costume.

So the encoder scans each rendered row and does only two things:

• A pixel different from its left neighbor: emit its 4 bytes as literals. Costs 32–36 bits.
• A run of identical pixels: emit copy instructions at distance 4. A run of 64 pixels — 256 bytes — costs one 8-bit length symbol, 5 extra bits, and a 5-bit distance code. Eighteen bits.

Distance 4 happens to be distance code 3, no extra bits, so the distance side of every copy is the same five bits, 00011, forever. Of DEFLATE's thirty distance codes we use one; of its two smarter block types we use zero. Every decoder ever shipped handles it anyway, because a correct inflate routine cannot tell minimalism from art.

What the encoder actually holds in memory, in its entirety: a 64-bit accumulator for packing bits, the running Adler-32 (two integers), a 256-entry CRC-32 table (1KB, computed at startup), and a 4KB staging buffer — because a chunk's length is written before its data, so you buffer that much, then flush it as one IDAT and start the next. Call it 5KB, plus a few registers of bookkeeping. The bands flow in, the chunks flow out, and at no point does the whole image exist.

The receipts

The test dashboard for my renderer is a 320×240 screen of the usual dashboard vocabulary — flat panels, rounded corners, gauge bars, anti-aliased text. The image at the top of this post is the 320×240 benchmark, as literally produced by the encoder described above. The comparison:

encoding                                         bytes    of raw
-----------------------------------------------  -------  ------
raw BGRA framebuffer                             307,200  100%
PNG, stored blocks (deflate's "no compression")  307,533  100.1%
PNG, RLE-via-fixed-Huffman (this post)           29,719   9.7%
PNG, zlib level 9                                11,603   3.8%

Two honest observations. First, the trick earns a 10× reduction over shipping raw pixels, from a compressor whose state fits in a CPU's pocket change. Second, a real encoder is still 2.6× smaller than we are — full LZ77 finds the repeated text of "REACTOR", matches patterns across rows, and Huffman-codes the anti-aliased edges we pay literals for. (Amusingly, my copy of macOS re-encodes the same image through ImageIO at 18,102 bytes — the adaptive-filter heuristics that help photographs can actively hurt flat dashboard art. We beat nobody, but the professionals don't always beat each other either.)

That 2.6× is the price of the quarter-megabyte workspace we don't have. On a machine where the choice is "29KB served from 5KB of state" versus "no image at all," it is not a hard negotiation.

Limits, so you can decide if it's for you

• Runs are horizontal only. Vertical structure — which dashboards have in abundance — goes uncompressed. PNG's Up filter plus this same trick would catch it (a row identical to the one above becomes a row of zeros, which is one giant run) at the cost of buffering one prior row. I may not resist that forever.
• Gradients, photographs, and dithering are worst cases: nearly every pixel becomes four literals, and the "compressed" file approaches 108% of raw. Know your pixels.
• This is an encoder trick only. Decoding still requires real inflate — the asymmetry is the point. Your 20KB microcontroller encodes; the browser with gigabytes decodes.

The implementation lives in PNG.swift in my swift-pane dashboard renderer (documentation), where it pairs with the banded renderer so a full-frame PNG streams out of a band-sized buffer. But there is nothing Swift-shaped about the idea: a bit-packer, two checksums, one distance code, and the nerve to send a 1996 file format exactly as much cleverness as you can afford. The decoders will never know how little you did.