GIF LZW Variable-Length Code Packing Explained

The Graphics Interchange Format (GIF) uses a modified Lempel-Ziv-Welch (LZW) compression algorithm that relies on dynamic, variable-length codes packed into a continuous stream of bytes. This system optimizes data storage by using the minimum number of bits necessary to represent dictionary indices, dynamically increasing the bit width as the dictionary grows, and resetting when maximum capacity is reached. This article details how initial code sizes are established, how bit lengths increase dynamically, how codes are packed across byte boundaries, and how special control codes govern the process.

Initial Code Size and the Code Table

A GIF image defines a "LZW Minimum Code Size" based on the color table depth. If an image uses \(N\) bits per pixel (where \(N\) is at least 2), the base alphabet size is \(2^N\).

The algorithm reserves two special control codes immediately following the standard pixel values:

Clear Code (CC): Value is \(2^N\). It signals the decoder to reset the dictionary.
End of Information Code (EOI): Value is \(2^N + 1\). It signals the end of the image data stream.

Because values from \(0\) up to \(2^N + 1\) must be represented, the initial code size used for packing is always \((N + 1)\) bits. The first assignable compression code representing a pixel sequence begins at \(2^N + 2\).

Dynamic Code Size Expansion

As the compression algorithm encounters new sequences of pixels, it assigns them incremental integer values in a dictionary. Because the current bit width limits the maximum integer that can be emitted, the code size must expand as the dictionary fills:

Bit Growth Threshold: When the next code to be added exceeds the maximum value representable by the current bit width (i.e., when the code value reaches \(2^{\text{current\_code\_size}}\)), the code size increases by 1 bit.
Timing of Increase: In standard GIF LZW, the encoder increases the bit length immediately before emitting a code that requires the larger bit width.
Maximum Limit: The bit width begins at \(N + 1\) bits and grows up to a strict maximum of 12 bits (representing a maximum code value of 4095).

Bit Packing: Least Significant Bit (LSB) First

LZW codes have arbitrary bit lengths (ranging from 3 to 12 bits), but computer storage is organized in 8-bit bytes. GIF packs these variable-length codes into bytes using Least Significant Bit (LSB) first ordering:

An accumulator (or bit buffer) holds incoming bits.
When a code is written, its least significant bit is placed into the lowest available bit position of the current byte.
When 8 bits accumulate, that complete byte is appended to the data stream.
Any remaining bits of the current code overflow into the least significant positions of the next byte.

For example, packing a 5-bit code 10110 followed by a 5-bit code 01001:

The first byte receives 10110 in bits 0 through 4.
The second code splits: its lowest 3 bits (001) fill bits 5 through 7 of the first byte, completing it as 00110110 (0x36).
The remaining 2 bits of the second code (01) become bits 0 and 1 of the second byte.

Dictionary Reset via Clear Code

When the dictionary fills completely at 4096 entries (code 4095), the encoder can no longer create new strings using 12 bits. The encoder typically emits the Clear Code (\(2^N\)).

Upon encountering the Clear Code:

The dictionary is wiped clean, retaining only the basic pixel values (\(0\) to \(2^N - 1\)) and the two control codes.
The code size immediately resets to the initial value of \((N + 1)\) bits.
The next code assigned to a new sequence returns to \(2^N + 2\).

Sub-Block Encapsulation

The continuous packed byte stream is not written directly to the file as a single block. Instead, it is partitioned into data sub-blocks:

Each sub-block begins with a 1-byte size indicator ranging from 1 to 255 (0x01 to 0xFF).
The specified number of packed data bytes immediately follows the size byte.
A sub-block with a size of zero (0x00), known as the Block Terminator, marks the end of the image data stream immediately following the sub-block containing the EOI code.