GIF LZW Bit Packing vs Deflate Byte Alignment

This article compares the bit-level serialization of LZW compression in GIF files with the byte-alignment and bit-packing mechanisms utilized by the Deflate algorithm. While both formats compress data using variable-length codes packed into 8-bit bytes, they differ significantly in code length variability, bit ordering within byte buffers, sub-block framing, and explicit alignment to byte boundaries.

Bit Packing in GIF LZW

GIF uses the Lempel-Ziv-Welch (LZW) algorithm to compress image pixel indices. LZW outputs variable-length integer codes rather than bytes. The bit-packing mechanism handles these codes through dynamic bit widths and sequential byte filling.

• Dynamic Code Sizes: GIF LZW starts with a code size equal to the color depth plus one bit (for instance, 9-bit codes for an 8-bit palette to accommodate Clear and End-of-Information markers). As the string table fills, the code size increases by one bit whenever a new code exceeds the current maximum bit representation, up to a maximum limit of 12 bits.
• Bit Ordering: Codes are packed into bytes using a Least Significant Bit (LSB) first scheme. When a code is written, its lowest-order bits fill the remaining lower-order bits of the current byte. Any overflow spills into the LSB of the subsequent byte.
• Sub-Block Framing: The packed bitstream in GIF does not flow continuously without structural boundaries. Instead, GIF partitions the packed bytes into discrete sub-blocks. Each sub-block begins with a single byte indicating the payload length (up to 255 bytes), followed by the packed LZW data bytes, terminating with a 0x00 block terminator byte after the End-of-Information (EOI) code.

Bit Packing and Byte Alignment in Deflate

Deflate (RFC 1951) combines LZ77 dictionary matching with Huffman coding. It processes two separate layers of bit manipulation: variable-length prefix codes and explicit byte-boundary alignment.

• Huffman Bit Ordering: Deflate packs variable-length Huffman codes into bytes starting from the least significant bit (LSB) to the most significant bit (MSB), identical to GIF's byte-filling direction. However, the Huffman codes themselves are constructed such that the most significant bit of the code is transmitted first, requiring bit-reversal during bitstream emission.
• Explicit Byte Alignment: Deflate supports three block types: uncompressed (BTYPE=00), fixed Huffman (BTYPE=01), and dynamic Huffman (BTYPE=10). When an uncompressed block is encountered, Deflate mandates immediate byte alignment. Any remaining unused bits in the current byte are discarded, padding the stream to the next byte boundary before reading the 16-bit length (LEN) and one's complement (NLEN) headers.
• Stream Continuity: Unlike GIF, Deflate does not use length-prefixed sub-blocks to chunk its bitstream. It remains a continuous bit-level stream until an end-of-block marker is reached or the stream concludes, at which point the final byte is zero-padded to reach the nearest byte boundary.

Key Differences Between the Two Approaches

Alignment Mid-Stream

GIF never aligns to a byte boundary during active compression. The LZW code size increases dynamically across arbitrary bit boundaries, and codes span continuously across byte boundaries until the EOI code is encountered. Deflate, conversely, deliberately drops padding bits to realign with 8-bit boundaries whenever switching to uncompressed data chunks.

Stream Partitioning

GIF overlays an external container requirement onto its bit packing: the bitstream must be broken every 1 to 255 bytes to inject a length-indicator byte. A single LZW code can logically span across a sub-block boundary, meaning the bit-packing engine must pause, emit the next sub-block length byte, and resume packing bits into the next block payload. Deflate manages block headers at the bit level within the stream itself, avoiding intermediate byte-count wrappers.

Code Growth vs. Static Trees

In GIF LZW, the reader and writer synchronize bit sizes implicitly based on code index increments. In Deflate, code sizes vary on a per-symbol basis dictated by Huffman tree representations transmitted in the dynamic block headers, rather than predictably widening bit-by-bit as the dictionary grows.