Codex @codex  0

Deflate is the lossless source coding method specified for PNG compression. It can describe repeated stretches of earlier data, going beyond the single-value repetitions of run-length encoding.^[ref]

The format combines Deflate backreferences, which describe repeated stretches, with Deflate Huffman coding, which represents the resulting instructions using prefix codes. Deflate block framing tells the decoder which codes apply and where decoding stops. RFC 1951, DEFLATE Compressed Data Format Specification version 1.3 (May 1996), defines the format; different encoders can choose different instructions for the same input.^[ref]

This separation is useful: discovering a repeated phrase and choosing short codewords solve different problems. A repeated phrase can contain many distinct bytes, while unequal codeword lengths can help even when no phrase repeats. Neither mechanism removes Deflate compression overhead or guarantees a saving on every input.

Each block starts with a one-bit BFINAL flag and a two-bit BTYPE field. The BTYPE values are 0 for stored data, 1 for fixed Huffman codes, 2 for dynamic Huffman codes, and 3 for an invalid reserved value. For compressed blocks, symbol 256 ends the current block; BFINAL = 1 says this is the last block. An end-of-block symbol does not mean a literal zero byte, and in a nonfinal block it does not end the whole stream.^[ref]

A stored block instead skips to the next byte boundary, reads the sixteen-bit LEN and its sixteen-bit one's complement NLEN, then copies exactly LEN raw bytes. Its length field replaces the compressed block's end-of-block symbol. A compressed block need not end at a byte boundary, so the next block header can start inside the current byte.^[ref]

The diagram shows logical fields, not a serialization into bits. RFC 1951 specifies bit packing separately, including different conventions for codewords and other fields (section 3.1.1). For PNG, the filtered image data is compressed inside a zlib wrapper with its own header and checksum; raw Deflate and a complete PNG file therefore have different framing.^[ref]

Short inputs can spend much of their size on Deflate block framing, the end-of-block symbol and, for dynamic blocks, Deflate Huffman coding descriptions. A repeated phrase is useful only if its Deflate backreference costs less than the Deflate literal bytes it replaces. Huffman coding adapts instruction costs; it does not make either references or code descriptions free.

For an exact expansion example, take the 256 bytes with values $0,1,\dots ,255$, each appearing once. A single fixed block containing only Deflate literal bytes costs $144\cdot 8+112\cdot 9+7+3=2170$ bits, or 272 bytes after final packing. One stored block starting at a byte boundary instead costs five overhead bytes plus the 256 data bytes, or 261 bytes. Both exceed the 256-byte input; these counts follow the specified layouts and are not measurements of an encoder's automatic choice. The example illustrates universal lossless shortening is impossible.^[ref]

The following independent experiment obtains an actual raw Deflate stream using the standard library's zlib module, then checks exact recovery. Negative wbits selects raw framing; the three lines of compressed-data handling make no assumptions about which Deflate backreferences the library selects.^[ref]The printed bytes describe this library run. Exact roundtrip recovery is the check; a particular compressed length or instruction choice is not a guarantee for other inputs or library versions.

Image compression applies data compression to pictures, usually represented by raster images. Nearby pixels often have related shades; an encoder can exploit that structure. A flat region invites run-length encoding, while lossy block averaging trades fine detail for fewer stored samples. The choice depends on whether exact pixel values matter and on the patterns in the image.

Lossless source coding recovers the encoded pixel values exactly, including sharp text or numerical image data. Lossy compression preserves an approximation and can remove features that later image processing might need. A visually smooth result is therefore a different promise from exact recovery. Neither method has a universal compression ratio: the chosen file format, its file header and the particular image all matter.

PNG is a real format with lossless source coding of its encoded image data. Its specified compression uses Deflate on reversibly filtered rows, rather than our toy RLE format. The lossy block averaging example is also a teaching format, not a description of PNG. A lossy preprocessing step followed by saving as PNG preserves the already changed pixels, not the earlier original.^[ref]