The LZW algorithm in GIF

GIF uses the LZW algorithm with a few additions: two special codes, variable-width codes and a dictionary limited to 4096 entries. These are what make a home-made GIF decoder "almost work" so often.

Initial dictionary and special codes

In the image block the data is preceded by the minimum code size m. The whole dictionary layout follows from it:

codes 0 .. 2^m - 1 single colors (palette indices) 2^m CLEAR: reset the dictionary and start over 2^m + 1 END: end of image data from 2^m + 2 further dictionary entries example, m = 2: 0 1 2 3 colors, 4 = CLEAR, 5 = END, first free code: 6

The stream usually starts with CLEAR and should always end with END.

Variable-width codes

Codes start at m + 1 bits, since they must also fit CLEAR and END. When the dictionary reaches a power-of-two boundary, codes grow by 1 bit, up to 12:

m = 2: 3-bit codes for values 0..7 after entry 7 is added → 4-bit codes (0..15) after entry 15 is added → 5-bit codes ... at most 12 bits, i.e. codes 0..4095

The hardest part to implement is exactly when the width changes. The compressor adds an entry when it emits a code; the decompressor adds it one step later, so both must compute the same boundary offset by one:

decompressor: after adding an entry, if next free code = 2^width → width + 1 compressor: after adding an entry, if next free code > 2^width → width + 1

Using the same condition in both (e.g. "=") produces a compressor that widens one code too early. Such a file usually breaks after the first few pixels.

A full dictionary

When the dictionary holds 4096 entries, no more can be added. The compressor has two options:

send CLEAR (12 bits wide) and start from an empty dictionary, with codes back to m + 1 bits. The simplest and most common.
stop adding entries and keep coding with the old dictionary until it decides to clear (a deferred clear). Sometimes better for images whose patterns do not change.

The decoder must handle both: when the dictionary is full, it stops adding entries and waits for CLEAR.

Bit packing

Codes are packed into bytes least significant bit first. The first code takes the lowest bits of the first byte, the next code the following bits, and a code that does not fit continues in the next byte. Finally the bytes are split into 255-byte sub-blocks.

codes: 4 (3 bits), 0 (3 bits), 0 (3 bits), ... byte 0: b7 b6 b5 b4 b3 b2 b1 b0 └┬┘ └─┬──┘ └──┬───┘ │ │ └─ code 4 = 100 │ └────────── code 0 = 000 └──────────────── the two low bits of code 0 = 00 (its third bit goes into byte 1)

The full run for the example file is on the LZW compression in GIF and LZW decompression in GIF pages.