GIF LZW Decompression: Dynamic String Table Rebuild

During GIF decoding, image data is expanded using the Lempel-Ziv-Welch (LZW) algorithm without storing an explicit dictionary inside the file. Instead, the decoder dynamically reconstructs the string table step-by-step from the incoming stream of variable-length codes. By tracking the previous code emitted, retrieving the current sequence, and pairing them together, the decoder perfectly mirrors the state of the original encoder at every step of decompression.

1. Dictionary Initialization

The decompression process begins by reading the "LZW Minimum Code Size" byte stored in the GIF image descriptor. If this value is denoted as \(N\):

  • Color Palette Roots: The table assigns the first \(2^N\) indices (from \(0\) to \(2^N - 1\)) to represent single-pixel color indices directly matching the image palette.
  • Clear Code: Index \(2^N\) is reserved as the Clear Code. It signals the decoder to reset the dictionary to its initial state and restore the starting bit-depth.
  • End of Information (EOI) Code: Index \(2^N + 1\) marks the end of the compressed data stream.
  • Next Available Entry: Dynamic allocation starts at index \(2^N + 2\).

The initial reading bit-width is set to \(N + 1\) bits, and the decoder prepares an empty buffer to track the OldCode.

2. The Main Decoding Loop

Once initialized, the decoder reads incoming bit sequences of the current code size:

  1. Read Code: Read the first code into NewCode. If it is a Clear Code, reset the table and continue.
  2. First Symbol Processing: For the first non-control code, output its corresponding single-pixel value directly to the pixel array, assign OldCode = NewCode, and proceed to the next code.
  3. Subsequent Codes: For every incoming NewCode:
    • Look up NewCode in the dictionary to retrieve its corresponding byte sequence.
    • Write this sequence to the output pixel stream.
    • Dynamically add a new entry to the string table: take the string represented by OldCode and append the first character of the string represented by NewCode.
    • Update OldCode = NewCode.

3. Resolving the Code-Not-Yet-In-Table Edge Case

A unique scenario occurs when the encoder creates a code and immediately references it in the very next step (often occurring with repetitive pixel sequences like A B A B A). In this scenario, the decoder receives a NewCode that matches the next available table index—meaning it has not been inserted into the table yet.

The decoder handles this deterministically:

  • The unknown sequence is known to be the string from OldCode followed by the first character of that same OldCode string.
  • The decoder constructs this sequence, outputs it, and inserts it into the table at the expected index.
  • OldCode is then set to NewCode as normal.

4. Dynamic Bit-Length Increases and Resets

As the string table grows, the number of bits required to represent table indices increases:

  • Bit Width Increments: Whenever the next table index exceeds the capacity of the current bit-length (e.g., reaching index 512 while reading 9-bit codes), the reading width is incremented by 1 bit, up to a maximum limit of 12 bits (4096 entries).
  • Clear Code Handling: If the string table reaches 4096 entries, the encoder typically emits a Clear Code. Upon receiving this, the decoder flushes all dynamically added entries, restores the table to its initial \(2^N + 2\) state, and sets the reading width back to \(N + 1\) bits before resuming data processing.