Deflate is the compression method inside gzip, zlib, ZIP and PNG, defined in RFC 1951. It combines two things. Repeated data is replaced by a copy of what came earlier (LZ77), and the symbols that result are then coded with Huffman codes, so that common symbols take few bits. The explorer shows every part below for a file dropped on this site: pick the compressed data, then Show.
Blocks
A Deflate stream is a sequence of blocks. Bits are packed starting from the lowest bit of each byte. Numbers are read the same way, lowest bit first; Huffman codes are the one exception, and go from their most significant bit first, so that a decoder can read them one bit at a time.
Each block starts with three bits:
| Bits | Name | Meaning |
|---|---|---|
| 1 | BFINAL | 1 for the last block of the stream |
| 2 | BTYPE | 0 stored, 1 fixed Huffman codes, 2 dynamic Huffman codes, 3 reserved (an error) |
A stored block skips to the next byte boundary, then holds LEN, a 16-bit count, NLEN, its one's complement, and LEN bytes as they are. It is how Deflate avoids making incompressible data larger; at most 65,535 bytes fit in one.
Literals, lengths and distances
A compressed block is a run of tokens. The alphabet of literal and length symbols has 288 values: 0 to 255 are literal bytes, 256 ends the block, and 257 to 285 start a copy. A copy repeats earlier output, from a distance back of up to 32,768 bytes, for a length of 3 to 258 bytes. The copy may overlap its own output, so a run of one byte is a copy from distance 1.
Length symbols and distance symbols give a range. Extra bits, sent straight after the symbol, pick the exact value within that range.
| Length symbol | Lengths | Extra bits |
|---|---|---|
| 257 to 264 | 3 to 10 | 0 |
| 265 to 268 | 11 to 18 | 1 |
| 269 to 272 | 19 to 34 | 2 |
| 273 to 276 | 35 to 66 | 3 |
| 277 to 280 | 67 to 130 | 4 |
| 281 to 284 | 131 to 257 | 5 |
| 285 | 258 | 0 |
After a length symbol comes a distance symbol, 0 to 29, with up to 13 extra bits: symbols 0 to 3 are the distances 1 to 4 with no extra bits, and from there each pair of symbols doubles the range and adds one extra bit, up to 24,577 to 32,768 for symbol 29.
Fixed Huffman codes
A fixed block uses codes every decoder knows, so it needs no table:
| Symbols | Code length | Codes |
|---|---|---|
| 0 to 143 | 8 bits | 00110000 to 10111111 |
| 144 to 255 | 9 bits | 110010000 to 111111111 |
| 256 to 279 | 7 bits | 0000000 to 0010111 |
| 280 to 287 | 8 bits | 11000000 to 11000111 |
Distance symbols are all 5 bits in fixed blocks.
Dynamic Huffman codes
A dynamic block sends its own code lengths first. The codes themselves are canonical: given only the length of every symbol's code, the decoder assigns the codes in order, shorter codes first and, within a length, in symbol order. Only the lengths are sent, and even those are compressed, with a third, small Huffman code. The header is:
| Bits | Name | Meaning |
|---|---|---|
| 5 | HLIT | literal and length codes sent, less 257 |
| 5 | HDIST | distance codes sent, less 1 |
| 4 | HCLEN | code length codes sent, less 4 |
| HCLEN + 4 fields of 3 bits | lengths of the code length code, in this order: 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 | |
| variable | HLIT + 257 literal/length code lengths, then HDIST + 1 distance code lengths, in the code length code |
A code length symbol from 0 to 15 is that code length. Symbol 16 repeats the previous length 3 to 6 times (2 extra bits), 17 repeats zero 3 to 10 times (3 extra bits), and 18 repeats zero 11 to 138 times (7 extra bits).
The zlib wrapper
A zlib stream (RFC 1950) is Deflate data with a two-byte header and a checksum. PNG and PDF use it; gzip and ZIP have their own headers and use raw Deflate.
| Byte | Name | Meaning |
|---|---|---|
| 0 | CMF | the low 4 bits are the method (8 is Deflate); the high 4 bits give the window size, as a power of two less 8 |
| 1 | FLG | bits 0 to 4 make CMF × 256 + FLG a multiple of 31; bit 5 says a preset dictionary is used; bits 6 and 7 give the compression level |
| after the Deflate data | Adler-32 | a checksum of the uncompressed data, big-endian |
Looking at it in the explorer
Open a gzip, ZIP, PNG or PDF file. The compressed data has a Show button, which opens the stream’s summary, its blocks, every token with its bit position, and a picture of what each output byte cost. Blocks open to show their code lengths and codes. Long streams are limited to the first 2 million tokens and 200,000 blocks, and the screen says so.