DEFLATE and Gzip Formats

DEFLATE is the bitstream format defined by RFC 1951. It combines an LZ77 sliding window with Huffman codes. “zlib” and “gzip” often refer to files that contain DEFLATE, but each is a different wrapper around the raw bitstream.

Block Boundaries and BTYPE #

A DEFLATE stream is a sequence of blocks. Each block begins at the current bit position with BFINAL (one bit) and BTYPE (two bits):

BFINAL is one only for the last block. A compressed block ends when its literal/length stream emits end-of-block (EOB), symbol 256. The next block header follows immediately at the next bit; a compressed block is not padded to a byte boundary. Stored blocks are the exception: after their header, the decoder discards remaining bits in the current byte, reads little-endian LEN and NLEN (the one’s complement of LEN), and copies exactly LEN bytes. LEN is 16 bits, so one stored block holds at most 65,535 bytes.

LZ77 Symbols and Huffman Codes #

The compressed data alphabet has literal bytes 0–255, EOB 256, and length symbols 257–285. A length symbol selects a base length and a number of extra bits. A following distance symbol selects a base distance and extra bits. The resulting pair copies bytes from the already produced output, up to 32 KiB backward and up to 258 bytes long; overlap is valid.

Fixed blocks use code lengths prescribed by RFC 1951. Dynamic blocks carry HLIT (5 bits), HDIST (5 bits), and HCLEN (4 bits), then transmit a code-length alphabet in a specified permutation. That alphabet describes the literal/length and distance code lengths, including repeat codes for runs of zeros or repeated lengths. Canonical reconstruction turns those lengths into the actual codes.

DEFLATE packs data elements from the least-significant bit upward within each byte. Numeric extra-bit fields use least-significant-bit-first order. Huffman codes are assigned as canonical values but emitted with the format’s bit-reversal convention. A parser must keep a bit cursor rather than reading every field as a byte-aligned integer.

zlib and gzip Wrappers #

Raw DEFLATE has no header or trailer. The zlib wrapper (RFC 1950) starts with CMF and FLG, whose FCHECK makes the 16-bit header divisible by 31. If FDICT is set, a four-byte Adler-32 dictionary identifier follows. The stream ends with a big-endian Adler-32 of the uncompressed data.

The gzip wrapper (RFC 1952) is a sequence of members. Each member has the magic bytes 1f 8b, compression method 8, flags, modification time, extra flags, and operating-system fields. Flags can add an extra field, an original filename, a comment, and a header CRC. The trailer stores a little-endian CRC-32 of the uncompressed member and ISIZE, its size modulo 2³². Metadata is not a substitute for validating the trailer.

Protocol documentation must name the representation. HTTP Content-Encoding: gzip carries the gzip format, while a ZIP entry using method 8 normally carries a raw DEFLATE stream. A zlib decoder cannot safely be selected merely because a payload is described as “compressed.”

References #

• RFC 1951: DEFLATE
• RFC 1950: zlib Format
• RFC 1952: gzip Format