Dekompresja LZW w GIF
Dekoder dostaje bajty 04 12 30 13 05 i minimalną długość kodu 2. Ta strona odtwarza z nich osiem pikseli przykładowego pliku, a potem pokazuje drugi przykład, w którym występuje przypadek KwKwK. Zasady ogólne są na stronie dekompresja LZW.
Odczyt kodów
Bity czyta się od najmłodszego bitu pierwszego bajtu. Długość kodu zaczyna się od 3 bitów i rośnie, gdy słownik dojdzie do granicy (zob. LZW w GIF).
| Kod | Bity | Znany? | Wypisane | Nowy wpis | Długość dalej |
|---|---|---|---|---|---|
| 4 | 3 | CLEAR | słownik od nowa | 3 | |
| 0 | 3 | tak | 0 | (pierwszy kod, brak wpisu) | 3 |
| 0 | 3 | tak | 0 | 6 = 0 + 0 | 3 |
| 1 | 3 | tak | 1 | 7 = 0 + 1 | 4 (następny wolny = 8) |
| 1 | 4 | tak | 1 | 8 = 1 + 1 | 4 |
| 0 | 4 | tak | 0 | 9 = 1 + 0 | 4 |
| 3 | 4 | tak | 3 | 10 = 0 + 3 | 4 |
| 3 | 4 | tak | 3 | 11 = 3 + 3 | 4 |
| 1 | 4 | tak | 1 | 12 = 3 + 1 | 4 |
| 5 | 4 | END |
Słownik dekodera jest zawsze o jeden wpis za słownikiem kodera. Dlatego dekoder wydłuża kody już po dopisaniu wpisu 7, a koder dopiero po wpisie 8: oba zmieniają długość przed tym samym, piątym kodem.
Przykład z KwKwK
Sześć pikseli tego samego koloru: 0 0 0 0 0 0. Koder daje dwa bajty 84 5F, czyli kody 4, 0, 6, 7, 5 po 3 bity.
| Kod | Znany? | Wpis | Wypisane | Nowy wpis |
|---|---|---|---|---|
| 4 | CLEAR | |||
| 0 | tak | 0 | 0 | |
| 6 | nie (następny wolny = 6) | 0 + 0 = 0 0 | 0 0 | 6 = 0 0 |
| 7 | nie (następny wolny = 7) | 0 0 + 0 = 0 0 0 | 0 0 0 | 7 = 0 0 0 |
| 5 | END |
Dwa razy z rzędu przychodzi kod, którego dekoder jeszcze nie ma. Za każdym razem wpis to poprzedni ciąg plus jego pierwszy symbol. Jednolite obszary obrazu (tło, duże plamy koloru) dają ten przypadek bardzo często, więc dekoder bez obsługi KwKwK psuje się właśnie na nich.
Dekoder
// bytes: dane LZW po złączeniu podbloków, minCodeSize: bajt przed nimi
function gifLzwDecode(bytes, minCodeSize) {
const clear = 1 << minCodeSize, eoi = clear + 1;
let width, next, prefix, suffix, prev;
const reset = () => {
width = minCodeSize + 1; next = eoi + 1; prev = -1;
prefix = new Int16Array(4096); suffix = new Uint8Array(4096);
for (let i = 0; i < clear; i++) suffix[i] = i;
};
const first = (code) => { while (code >= clear) code = prefix[code]; return code; };
const emit = (code, out) => {
const stack = [];
while (code >= clear) { stack.push(suffix[code]); code = prefix[code]; }
stack.push(code);
for (let i = stack.length - 1; i >= 0; i--) out.push(stack[i]);
};
reset();
const out = [];
let acc = 0, bits = 0, pos = 0;
while (true) {
while (bits < width && pos < bytes.length) { acc |= bytes[pos++] << bits; bits += 8; }
if (bits < width) break;
const code = acc & ((1 << width) - 1);
acc >>= width; bits -= width;
if (code === clear) { reset(); continue; }
if (code === eoi) break;
if (prev === -1) { emit(code, out); prev = code; continue; }
const known = code < next;
if (next < 4096) {
prefix[next] = prev;
suffix[next] = first(known ? code : prev); // KwKwK: pierwszy symbol poprzedniego
next++;
if (next === 1 << width && width < 12) width++;
}
emit(code, out);
prev = code;
}
return out;
}
gifLzwDecode([0x04, 0x12, 0x30, 0x13, 0x05], 2); // [0, 0, 1, 1, 0, 3, 3, 1]
gifLzwDecode([0x84, 0x5F], 2); // [0, 0, 0, 0, 0, 0]Słownik zamiast całych ciągów trzyma dla każdego wpisu kod prefiksu i ostatni symbol, a ciąg odtwarza od końca na stosie. Zajmuje to stałe 12 KB niezależnie od obrazu. Dekoder sprawdzono z koderem z poprzedniej strony na losowych obrazach, także z wielokrotnym zapełnieniem słownika.
Dla obrazu z przeplotem wynik dekompresji to wiersze w kolejności przebiegów, a nie od góry do dołu. Trzeba je jeszcze ułożyć zgodnie z artykułem o przeplocie.