A GIF image is one stream of variable-width LZW codes, joined together from the sub-blocks of its image data. Pixels are colour indexes, and an image in the explorer can show each code it is made of: its position, its width, what it adds to the dictionary and the pixels it stands for.
Codes and the minimum code size
The byte before the image data is the LZW minimum code size, m. It is normally the number of bits a pixel needs, though at least 2: a 1-bit image uses 2, since the codes below need room. Everything follows from it:
| Code | Value | Meaning |
|---|---|---|
| colour codes | 0 to 2m − 1 | A single pixel value. |
| clear code | 2m | Empty the dictionary and reset the code width. |
| end code | 2m + 1 | End of the data. |
| dictionary codes | 2m + 2 up to 4095 | Entries the decoder has built so far. |
The first code in the stream is m + 1 bits wide and the width only ever grows. No code is wider than 12 bits, so the largest code is 4095.
How codes are packed
The codes run together as a stream of bits, low bit first. The first code takes the low bits of the first byte, the next code continues from the bit after, and a code that does not fit in a byte carries on into the low bits of the next. Each byte is therefore filled from its low bit upward. The sub-block boundaries do not affect this: a code can cross from one sub-block’s last byte into the next one’s first.
The dictionary
Decoding starts with an empty dictionary and two pointers: the previous code, and the code number that comes next, which starts at 2m + 2. For each code:
- A clear code resets everything. The first code after it is always a colour code, which is copied to the output and becomes the previous code.
- A code already in the dictionary emits the string of pixels that entry stands for. A new entry is added: the string of the previous code, followed by the first pixel of the string just emitted.
- A code equal to the next free number is not in the dictionary yet. It stands for the string of the previous code followed by that string’s own first pixel. This case is known as KwKwK, and it arises from a run of one value.
Each entry is stored as a prefix, the code of a shorter string, and one new pixel, so the dictionary’s strings can be recovered by following the prefixes back.
Code widths
After an entry is added, if the next code number has reached 2width and the width is below 12, the width goes up by one. Encoder and decoder keep the same count, so they stay in step. In the example below the width is 3 bits for the first four codes and 4 bits from the fifth.
Clear codes
A clear code can come at any point. It empties the dictionary, sets the width back to m + 1 and starts a new string. The specification asks encoders to send one as the very first code. When the dictionary is full, at 4,096 entries, the next code may be a clear code, or the encoder may keep sending codes against the full dictionary without changing it until it chooses to clear, which is called a deferred clear. Decoders must allow for this: a dictionary that is full simply stops growing.
The end code
The end code, 2m + 1, is the last code of the image. Any bits left in its last byte are padding. The whole image’s pixels are width × height, and a decoder should stop when it has them, even if some writer leaves more data behind.
Worked example
The 10 × 10 example file has m = 2, so 0 to 3 are colours, 4 is clear, 5
is end, and new entries start at 6. Its image data begins 8C 2D 99 87 2A.
Reading three bits at a time from the low end:
| Code | Width | Meaning | Emits | New entry |
|---|---|---|---|---|
| 4 | 3 | Clear | ||
| 1 | 3 | Colour | 1 | |
| 6 | 3 | Not yet in the dictionary | 1 1 | #6 = 1 1 |
| 6 | 3 | Entry #6 | 1 1 | #7 = 1 1 1 |
| 2 | 4 | Colour | 2 | #8 = 1 1 2 |
So far these codes have produced the pixels 1 1 1 1 1 2, the start of the image’s first row. The width rises to 4 bits at the fifth code, because after code #6 was used the next code number reached 8.