A GIF87a image is one stream of variable-width LZW codes, joined together from its raster data blocks. The method is Welch’s LZW, with variable code widths from a small starting size up to 12 bits.
Codes and the code size
The byte before the raster data is the code size m. Black-and-white images use a code size of 2, since 1 leaves no room for the two codes below.
| Code | Value | Meaning |
|---|---|---|
| colour codes | 0 to 2m − 1 | A single pixel value. |
| clear code | 2m | Reset the dictionary and the code width. |
| end code | 2m + 1 | End of the raster data. |
| dictionary codes | 2m + 2 up to 4095 | Strings added while decoding. |
Codes start at m + 1 bits. The stream starts with a clear code, and the width grows by one bit each time the dictionary would otherwise run out of codes, up to 12 bits.
How codes are packed
Codes are packed into bytes low bit first: the first code takes the low bits of the first byte, the next code continues from the bit after, and the last byte is padded with spare bits. A code can cross from one data block into the next.
The dictionary
Decoding begins with entries for the colour codes only. The first code after a clear code is a colour code. After each later code a new entry is added: the string of the previous code, followed by the first value of the string the current code stands for. If the current code is the next free number it stands for the previous string followed by that string’s first value, and that is the new entry too.
When the dictionary reaches 4,096 entries, the code that follows is usually a clear code. A decoder should also allow an encoder to keep using the full dictionary, as later GIF89a files may do.
End of the data
The end code, 2m + 1, ends the codes. Unused bits of the last byte are padding. The data block with a count of 0 follows.