Zlib algorithms and interfaces

Start with eight bytes. Build the compression and decoding process before discussing proofs.

Literals and back-references

Take a look at this string: ABABABAB.

We could send all eight bytes. Another option is to send A and B, then add an instruction: go back two bytes and copy one byte at a time, until six more bytes have been produced.

There are two numbers here. The distance, 2, tells the receiver where to read. The length, 6, tells it how many bytes to produce. Together, they describe a match. A single byte sent directly is called a literal.

It is too early to count the savings. We have only replaced the bytes with a sequence of symbols. Those symbols still need an encoding, and the stream may need a wrapper. For an input this short, the final compressed representation could easily be larger than the original.

But we have made the main problem smaller. If the receiver can execute these three symbols, it can reconstruct the string. Try copying just one byte at a time.

The first copy reads the original A. The second reads B. The third reads an A that this very match has just written.

The instruction does not take a six-byte snapshot of the original two-byte history. Each step goes back two positions, reads a byte, and adds it to the output. As the history grows, the read position moves forward. That is why the match length can exceed its distance.

Change the distance to 1 to see another familiar pattern: one A keeps producing more copies of itself.

This is the LZ77 idea used by DEFLATE. Previously seen content can be reproduced by referring back to history. The example explains the meaning of a valid symbol sequence; it does not claim that real zlib will choose exactly these symbols for this short input.

Related interfaces and formats：inflate

Library and formats

We can now put the names back into the picture.

zlib is a C library. It provides compression, decompression, checksums, and interfaces for buffers and streams. Its core streaming compression interface is called deflate; the decompression interface is inflate.

DEFLATE is a data format. It describes how literals, matches, and blocks become bits, and how to recover those symbols from the bits. It does not prescribe how a compressor must find its matches. Two compressors can choose different representations of the same input and still produce valid streams.

zlib and gzip are also wrapper formats. They put different headers and trailers around a DEFLATE payload. Raw DEFLATE has no such wrapper.

Producing the last data byte does not necessarily finish the stream. The decoder may still need to read an end-of-block symbol, check a checksum, or validate the gzip size field. We will return to this distinction when we split decompression across calls.

The original format definitions are DEFLATE / RFC 1951, zlib / RFC 1950, and gzip / RFC 1952.

Keep recent bytes, then find repetition

We used a length-6, distance-2 match to represent the repeated ABABAB. The compressor must now solve another problem: when new input arrives, how can it find an earlier copy of the same passage?

Imagine keeping the entire file in memory and searching all earlier bytes at every new position. The amount of retained data keeps growing. If input is still arriving, we may not even know how much memory the whole file will need.

Zlib keeps a bounded recent history and searches within it. Once older bytes leave that range, later matches no longer refer to them. The file can keep growing while the memory needed for retained history has a limit.

A sliding window first solves a storage problem: what history to keep and how to reuse its memory. It is not a separate encoding. The compressed stream still carries literals and length/distance pairs.

A retained range that follows the input

Use a small illustration that keeps only the most recent eight bytes. The processed prefix is 0123ABCD; the next bytes are ABCDwxyz. The compressor finds ABCD in retained history, so it can describe the next four bytes as “go back 4 bytes and copy 4 bytes.”

After accepting that match, the processed prefix is 0123ABCDABCD. Its last eight bytes are ABCDABCD, so the old 0123 can leave the retained range. After processing wxyz, the retained suffix becomes ABCDwxyz.

These positions name bytes in the whole input stream. The implementation must also place those bytes in a finite array. deflate fills a contiguous byte area, then moves the still-needed portion toward the beginning as it approaches the end. Keeping a recent logical suffix does not require moving the array on every input step.

The move in actual C

Before reading the move, name the positions it must preserve. The compressor state pointer is s; s->window selects its byte array. The fields strstart, match_start, and block_start record the array positions of the current input, a saved match, and the current block’s beginning. The local wsize is the number of bytes by which this slide shifts positions; more counts free bytes at the end. The comment’s MAX_DIST is the implementation’s maximum allowed backward search distance, explained in the window chapter. All these positions and distances are measured in bytes.

These four statements come from the project's pinned fill_window, inside its sliding branch:

zmemcpy(s->window, s->window + wsize, (unsigned)wsize - more);
s->match_start -= wsize;
s->strstart    -= wsize; /* we now have strstart >= MAX_DIST */
s->block_start -= (long) wsize;

The first line uses zmemcpy to copy the retained bytes to lower indices. The next three subtract the same displacement from the saved match, current processing position, and block start.

For example, a current position of 800 becomes 288 and a candidate at 700 becomes 188. Both decrease by 512, so their distance stays 100. Array indices change; the referenced bytes do not.

The eight-byte window is only an illustration, not a supported zlib window configuration. The window chapter opens the actual array layout, sliding condition, search-distance bound, and position-table updates.

Search less of the retained history

Keeping the bytes still leaves a search problem. Trying every retained position repeatedly compares many impossible candidates. Hash chains solve this second problem: how to check fewer positions.

Zlib hashes the first three bytes to group possible matches into a bucket. head names its newest position; prev links it to earlier positions. These tables hold search clues, while the actual bytes stay in the window. A matching hash only means “worth checking.” Byte comparisons determine the real match length.

Here, the most recent candidate is at position 4, starting with ABCR. An earlier candidate is at position 0, starting with ABCQ. The input we are about to process is ABCQABCX.

position  0    4    8
          ABCQ ABCR ABCQABCX
          ↑    ↑    ↑
        earlier latest current

Checking only the latest candidate finds ABC, a match of length 3. Following the chain once more finds ABCQABC, a match of length 7. Both candidates begin with the same three bytes; the later bytes determine how far the match can extend.

Searching farther costs more comparisons. zlib's settings include a candidate budget and a match length that is good enough to stop early. Higher compression levels can spend more time searching, but this is still a bounded search. It does not promise a globally optimal compressed representation.

The window retains recent bytes, hash chains find candidates, byte comparisons establish their lengths, and a search budget limits the work. Together they produce matches for the encoder. Next, we will see why finding a match does not always mean taking it immediately.

Related interfaces and formats：deflate · deflateTune

Lazy matching

Suppose we have already found a match of length 3. Taking it immediately seems reasonable. But what if a much longer match starts at the next position?

Let the history contain XABZ and ABCDEFGH. The current input is XABCDEFGQ.

history: !XABZ!ABCDEFGH!
input:    XABCDEFGQ
          ↑ current position

At the current position, XAB matches the history. The comparison then stops because the historical Z differs from the current C. The match length is 3.

Move forward one position. The remaining input is now ABCDEFGQ. It matches ABCDEFG in the history, stopping where H differs from Q. This match has length 7.

We can therefore emit a literal X and use the longer match from the next position. That is the idea behind lazy matching: delay the current decision long enough to see whether the next position offers a better match.

zlib's slow strategy keeps the match found at the previous position. If the new position does not offer a longer match, it uses the saved one. If the new match is longer, it emits the previous position's first byte as a literal and keeps considering the new match. Search conditions also limit when this extra work is worthwhile.

The example compares available matches. It does not claim that the second path always has a smaller final bit cost. Literals, lengths, and distances have different encoding costs. A local match decision and the minimum cost of an entire block are different questions.

Related interfaces and formats：deflate.c

Huffman trees

We have avoided sending some repeated bytes, but the remaining symbols still need an encoding. If every symbol takes the same number of bits, common symbols receive no advantage.

Start with four abstract symbols. Suppose a block contains A eight times, B four times, and C and D twice each. Encoding every symbol in two bits takes 32 bits.

We would like to give the common A a shorter code. But the receiver must still decode a continuous stream without separators. A prefix code makes this possible: no complete symbol's code is the beginning of another symbol's code.

Huffman construction repeatedly merges the two lowest-weight nodes. Here, it first combines C:2 and D:2 into a node of weight 4. That node combines with B:4 to make 8. Finally, the result combines with A:8 to form the root.

2 + 2 → 4
4 + 4 → 8
8 + 8 → 16

Each tree level adds one bit to a leaf's code. A ends up at depth 1, B at depth 2, and C and D at depth 3. The data now costs:

8 × 1 + 4 × 2 + 2 × 3 + 2 × 3 = 28 bits

The fixed two-bit comparison only explains this four-symbol example. It is not DEFLATE's fixed Huffman table, which has a larger alphabet and specific code-length rules.

Canonical Huffman codes

We could flip the left and right branches of the tree and get different bit patterns with the same lengths. If the compressor and decoder choose their trees independently, how can they agree on the codes?

DEFLATE uses canonical Huffman codes. Both sides follow the same rule: order symbols by code length, then by symbol value, and assign consecutive codes. The compressor does not need to send a complete tree. It only needs to let the decoder recover each symbol's length.

For A:1, B:2, C:3, D:3, that rule gives:

A →   0
B →  10
C → 110
D → 111

To move from 0 to 10, first advance past the code already used at the shorter length, then shift left to make room for another bit. Symbols at the same length simply receive consecutive numbers.

A leaf of length 1 occupies half of the tree's coding space. A leaf of length 2 occupies one quarter. Adding 2⁻length over the used symbols gives the Kraft sum. A sum of 1 fills the space exactly; a sum greater than 1 means that some codes must conflict.

This gives a decoder an early check. If a length description is impossible, it does not have to wait until data decoding to discover the contradiction. Real zlib also distinguishes complete tables, empty tables, and certain single-symbol cases. The decoding chapters will return to those details.

Related interfaces and formats：DEFLATE

Block types and costs

Our four-symbol example reduced the data cost from 32 bits to 28. If explaining the new code to the receiver costs more than four bits, the complete representation has saved nothing.

A dynamic table is not free. It works best when enough data can share its description cost. A small block may do better with a code that both sides already know, or with the original bytes stored directly.

DEFLATE therefore provides three block forms:

When flushing a block, zlib computes the fixed and dynamic coding costs, then considers whether it can use the stored form. The original bytes must still be available for that branch to copy. Strategy settings also influence the choice.

There are therefore two different decisions between the input and the compressed stream. First, choose the literals and matches that represent the input. Then choose how to encode that block of symbols. The next chapter follows the reverse direction: how does a receiver turn those bits back into the original bytes?

Bit order and buffers

Now move to the decoder’s side. It receives bytes, extracts their bits, and turns those bits back into symbols.

Positions within each byte are used from low to high. Ordinary numeric fields put their least significant bit first; a Huffman code puts its most significant code bit first. As a result, the same bits look reversed when shown in arrival order and in the usual notation for an integer.

Take C’s code, 110. The first 1 goes into buffer bit 0, the second 1 into bit 1, and the final 0 into bit 2. Written with the highest bit on the left, the buffer value is 011.

With that distinction, the bit buffer becomes less mysterious. zlib stores its value in hold and counts its valid bits in bits. Refills append bytes above the existing valid bits; interpreting a field or code removes the required number of bits from the low end.

Decode tables

Reading one bit at a time and following the coding tree will decode a symbol. An implementation can combine several of those decisions into one array access: inspect a few low bits and look up the result.

Keep A=0, B=10, C=110, and D=111, and let the root table inspect two bits. There are only four slots:

Why does A occupy two slots? Its code is only one bit long. Once the lowest bit is 0, the next bit can be either 0 or 1 without changing A’s meaning. The root table inspects two bits but consumes only one.

Try decoding AD. Concatenating the codewords gives 0 | 111; written as a buffer integer, that is 1110. The root index is 10, yet the result is still A. Removing one bit leaves 111: root index 11 follows the link, then subtable index 1 gives D.

This separates three things: how many bits we inspect, how many we consume, and which symbol we emit. Dropping two bits after finding A would swallow D’s first bit and misalign everything that follows.

C and D need a subtable because two root bits cannot distinguish them. A wider root can reduce subtable lookups, but uses more space. The real inflate_table builds its root and subtables around the length distribution rather than expanding an entire fifteen-level tree.

Related interfaces and formats：inflate

Decode in batches with a small buffer

Decoding explains how compressed bytes recover the original data. An application has another practical concern: the result may be large, and we want to use a small output buffer, saving or forwarding each batch as it becomes available.

That is what streaming means here: one decoding task can span several calls. Each call uses the input and output space currently supplied. When output space runs out, the function returns; the application takes the result and provides writable space to continue. It need not allocate one buffer for the entire decoded file.

Keep the direction clear: inflate takes compressed bytes as input and produces recovered original bytes as output. An output buffer is a piece of memory supplied by the application. It is neither a compressed block nor the whole decoded result.

One five-byte buffer, two batches

The first call writes ABABA, filling all five positions. The application takes those bytes, then can reuse the same memory for the next call's BAB. Saving the two batches in order gives ABABABAB.

The illustration starts after parsing the compressed bits. It executes the instructions we already know: emit A, emit B, then go back two bytes and copy six times. The literals take the first two output positions, leaving room for only three copy iterations. The other three must wait for the next call.

The C call an application actually makes

The program initializes one z_stream once. It repeats the following code inside a loop, with a five-byte output array:

stream.next_out = output;             /* writable destination */
stream.avail_out = sizeof output;     /* five bytes of room */

int result = inflate(&stream, Z_NO_FLUSH);
unsigned produced = sizeof output - stream.avail_out;

Start with the buffer fields. next_out points to writable memory; avail_out is the remaining space. The function advances the pointer and reduces that count. Subtracting the space left from the capacity supplied gives the number of bytes produced. Z_NO_FLUSH is the argument used for this ordinary decoding call; it does not require the entire result to be recovered before returning.

After taking the produced bytes beginning at output, if any, the application resets next_out and avail_out to the array's start and capacity. Keep the same stream; do not initialize it again. Its unread input pointer and count also remain in place. Do not resend the input from its beginning.

The complete compilable program includes initialization, errors, the loop, and cleanup. It uses the five compressed bytes above. Compiling and running it against the project's pinned zlib source produces:

call 1: input=4, output=5, bytes=ABABA, result=Z_OK
call 2: input=1, output=3, bytes=BAB, result=Z_STREAM_END

input and output count bytes consumed and produced during that call. One compressed byte remains after the first call; the next call continues from it. Z_OK means progress without completion. Z_STREAM_END reports completion. A full output buffer, or even the last recovered data byte, cannot replace that completion signal.

Two things the decoder must retain

First, unfinished work: for example, “three copies remain, at distance 2.” The implementation calls this stage MATCH. The next call resumes that work instead of interpreting the same instruction again.

Second, bytes that a later copy still needs. After the application takes the first batch, its output array can be overwritten. The next match still needs the earlier B and A, so the decoder saves the necessary suffix in its own history window. It reads B and A from saved history, then reads the newly written first B from the current output, producing BAB.

This history window has a different job from the compressor's window: compression history helps find repetition; decoding history helps execute a received back-reference. Both retain recent bytes, but they are not the same allocation.

A real call can also pause because input ends halfway through a field. Supply input when it is missing, and output space when that is exhausted. Repeating a blocked call without changing either resource cannot create progress. The suspension and resumed-calls chapter explains the full input, output, error, and completion protocol.

Related interfaces and formats：inflate · Stream rules