Thaw, a PNG decoder written from nothing

Copies and codes

The pixels of a PNG are com­pressed with DEFLATE, the same method as in a ZIP file and in much of the web’s traf­fic. DEFLATE stacks two ideas. The first is : when a run of bytes ap­peared ear­lier, write “go back so far and copy so many” in­stead of the bytes. The second is Huffman coding: give the sym­bols that are used often short codes and the rare ones long codes, so the whole takes fewer bits.

Type below. Your browser com­presses the text with its own DEFLATE, and Thaw de­codes it again and shows what it read. Plain let­ters were sent as they are. The marked ones came from a copy: point at one to see where it was copied from.

The code is sent at the start of each block, as a list of lengths alone: given the lengths, the codes them­selves follow by a fixed rule. The list is com­pressed in turn with a third, smaller code, and its own lengths are sent in an order chosen so the unused ones fall at the end and can be left off.

Each row against the row above

A pho­to­graph rarely re­peats a run of bytes ex­actly, so before com­press­ing, PNG fil­ters each row. A byte is stored as its dif­fer­ence from a guess: the pixel to its left (Sub), the one above (Up), the av­er­age of the two (Average), or whichever of left, above and above-left is clos­est to left plus above minus above-left (Paeth, after Alan Paeth). A smooth pic­ture be­comes a stream of small num­bers, which com­presses well. The en­coder picks a filter per row, and the strip beside the image above shows which.

Undoing them is a few lines each, but the order mat­ters: a row can only be undone after the row above it, and each byte after the one to its left. An in­ter­laced PNG adds , after Adam Costello: the image is sent in seven passes, first every eighth pixel in both di­rec­tions and last every other row, so a browser can draw a coarse pic­ture early. Each pass is fil­tered as an image of its own.

Held against zlib and Chromium

The DEFLATE de­coder is held against zlib, the li­brary nearly every pro­gram uses. Random data of four kinds, from noise to a re­peated phrase, is com­pressed by zlib with every level, strat­egy and window size, and Thaw must give back every byte. Then the streams are dam­aged at random, by a flipped bit, a cut end or over­writ­ten bytes, and read with­out a check­sum to catch it. Thaw must reject ex­actly the streams zlib re­jects, and read the same bytes from the rest.

$ node web/notes/thaw/zlib.mjs
20,000 streams from zlib 1.3.1-470d3a2, 199.7 MB, every one given back byte for byte
20,000 damaged streams: zlib and Thaw both refused 11,251 and read the same bytes from the other 8,749
in 11.6 s

The PNG de­coder is held against Chromium’s, pixel for pixel, on all of PngSuite and on random files writ­ten by a sep­a­rate en­coder in the com­mand: random sizes, color types, bit depths, palettes, trans­parency, in­ter­lac­ing and a random filter on every row, cut into random chunks.

$ node web/notes/thaw/suite.mjs
PngSuite against Chromium 141.0.7390.37: 175 files, 174 the same, 13 of them refused by both
  xcsn0g01.png: Chromium shows it, Thaw refuses it
2,000 random PNGs: 2,000 the same, pixel for pixel
in 23.3 s

Where Chromium and the specification part

The first runs dis­agreed on every image with six­teen bits per sample. A screen shows eight, so a de­coder has to drop half, and there are sev­eral ways to do it. Chromium, read back through WebGL, keeps the high byte of a gray sample, but turns a color sample into a half-pre­ci­sion float first and rounds from that, which lands one step lower on some values. Thaw now does the same, and agrees on every sample of every such file in PngSuite. Firefox and Safari may do it dif­fer­ently, and the check above will show it.

One file still dif­fers, on pur­pose. xcsn0g01.png has a wrong check­sum on its image data. Under the spec­i­fi­ca­tion’s rules for errors, a bad check­sum on a crit­i­cal chunk is not one to read past, and Thaw re­fuses the file. Chromium shows it.

What it does not have

Thaw reads the num­bers in the file and stops there. It ig­nores gamma, color pro­files and chro­matic­i­ties, which a browser ap­plies when it shows an image, and that is why the com­par­i­son above turns them off on the browser’s side too. It does not play an­i­mated PNGs, draws noth­ing until the whole file has been read, and has no limit on how large a file may unpack to. It is writ­ten to be read and to be right.

The source is in the port­fo­lio’s repos­i­tory under web/notes/thaw/: thaw.js for DEFLATE, zlib and PNG, browser.js for read­ing the browser’s pixels, zlib.mjs and suite.mjs for the com­mands, thaw.test.mjs for the tests. PngSuite is Willem van Schaik’s, free to use for any pur­pose.