Bit-Packing Order for GIF LZW Codes

This article explains the precise bit-packing scheme used to serialize variable-length LZW codes into byte streams within GIF data sub-blocks. In the GIF specification (GIF87a and GIF89a), variable-width LZW codes are written into bytes using a Least Significant Bit (LSB) first convention. This guide details how individual code bits map across byte boundaries and how the resulting bytes are organized inside sub-blocks.

LSB-First Bit Packing

LZW codes in GIF are variable in length, starting at code_size + 1 bits (where code_size is the LZW Minimum Code Size, at least 2) and expanding dynamically up to a maximum of 12 bits.

When packing these arbitrary-length codes into 8-bit bytes:

  1. Bit Placement: The least significant bit (LSB) of the LZW code is mapped to the lowest unused bit (starting at bit 0) of the current byte.
  2. Byte Saturation: Successive bits of the code fill the current byte upward toward the most significant bit (bit 7).
  3. Byte Spanning: When an LZW code contains more bits than remain in the current byte, the lower bits of the code fill the remainder of the current byte up to bit 7. The byte is then emitted, and the remaining higher-order bits of the code are placed starting at bit 0 of the next byte.

Step-by-Step Packing Example

Assume the current code width is 5 bits, and the encoder outputs two consecutive 5-bit codes:

  • Code A: 10110 (binary, value 22)
  • Code B: 01101 (binary, value 13)

Packing Code A:

  • Code A has bits: \(a_0=0, a_1=1, a_2=1, a_3=0, a_4=1\).
  • Bits 0 through 4 of Byte 0 receive Code A:
    • Byte 0 bits [4:0] = 10110

Packing Code B:

  • Code B has bits: \(b_0=1, b_1=0, b_2=1, b_3=1, b_4=0\).
  • Only 3 bits remain in Byte 0 (bits 5, 6, and 7). They are filled with \(b_0, b_1, b_2\):
    • Byte 0 bits [7:5] = 101
    • Complete Byte 0 = 10110110 (0xB6)
  • Byte 0 is completed and pushed to the stream.
  • The remaining bits of Code B (\(b_3, b_4\)) are placed into the beginning of Byte 1:
    • Byte 1 bits [1:0] = 01
    • Byte 1 bits [7:2] remain open for subsequent codes.

Sub-Block Encapsulation

The stream of packed 8-bit bytes is not written continuously across the entire image. Instead, it is partitioned into discrete data sub-blocks:

  • Block Size Byte: Each sub-block begins with an unsigned 1-byte count (specifying a payload between 1 and 255 bytes).
  • Payload: The exact number of packed data bytes specified by the count byte.
  • Block Termination: A sub-block with a length byte of 0x00 (the Block Terminator) signifies the end of the image's LZW data stream.

When the encoder outputs the final code (the End of Information code, or EOI), any partially filled final byte is padded with zero bits up to bit 7 and emitted into the current sub-block before writing the 0x00 terminator.