LZW compression in GIF
This page shows how the example file's eight pixels become the five bytes 04 12 30 13 05. The rules are on the LZW compression and LZW in GIF pages.
Input
The run
| Step | w | c | Code output | Bits | New entry | Width after step |
|---|---|---|---|---|---|---|
| start | 4 (CLEAR) | 3 | 3 | |||
| 1 | 0 | 0 | 0 | 3 | 6 = 0 0 | 3 |
| 2 | 0 | 1 | 0 | 3 | 7 = 0 1 | 3 |
| 3 | 1 | 1 | 1 | 3 | 8 = 1 1 | 4 (next free 9 > 8) |
| 4 | 1 | 0 | 1 | 4 | 9 = 1 0 | 4 |
| 5 | 0 | 3 | 0 | 4 | 10 = 0 3 | 4 |
| 6 | 3 | 3 | 3 | 4 | 11 = 3 3 | 4 |
| 7 | 3 | 1 | 3 | 4 | 12 = 3 1 | 4 |
| end | 1 | 1 | 4 | |||
| 5 (END) | 4 |
None of the added entries was used, because the image is too short for sequences to repeat. So 8 pixels of 2 bits (16 bits) became 36 bits: compression made the data bigger. In real images the dictionary quickly fills with long sequences and one code covers many pixels.
Bit packing
In each byte the earlier code takes the lower bits, so reading a byte from the left shows the codes in reverse. Byte 1, for instance, is: the 4 bits of the second code 1 (0001), the 3 bits of the first code 1 (001) and the top bit of the code 0 that started in byte 0 (0).
The encoder
// data: pixel indices, result: LZW bytes (before splitting into sub-blocks)
function gifLzwEncode(data, minCodeSize) {
const clear = 1 << minCodeSize, eoi = clear + 1;
let width, next, dict;
const reset = () => { width = minCodeSize + 1; next = eoi + 1; dict = new Map(); };
const bytes = [];
let acc = 0, bits = 0;
const emit = (code) => {
acc |= code << bits; bits += width;
while (bits >= 8) { bytes.push(acc & 255); acc >>= 8; bits -= 8; }
};
reset();
emit(clear);
let w = data[0];
for (let i = 1; i < data.length; i++) {
const c = data[i];
const key = w * 256 + c;
if (dict.has(key)) { w = dict.get(key); continue; }
emit(w);
dict.set(key, next++);
if (next > 1 << width && width < 12) width++;
if (next === 4096) { emit(clear); reset(); } // dictionary full: start over
w = c;
}
emit(w);
emit(eoi);
if (bits > 0) bytes.push(acc & 255);
return bytes;
}
gifLzwEncode([0, 0, 1, 1, 0, 3, 3, 1], 2); // [0x04, 0x12, 0x30, 0x13, 0x05]The encoder was tested on random images up to 256 × 256 pixels and 256 colors, including repeated dictionary resets. An independent system decoder reads the resulting files without errors.