Algorytm LZW w GIF

GIF używa algorytmu LZW z kilkoma dodatkami: dwoma kodami specjalnymi, kodami o zmiennej długości i ograniczeniem słownika do 4096 wpisów. To one sprawiają, że własny dekoder GIF najczęściej "prawie działa".

Słownik początkowy i kody specjalne

W bloku obrazu przed danymi stoi minimalna długość kodu m. Z niej wynika cały układ słownika:

kody 0 .. 2^m - 1 pojedyncze kolory (indeksy palety) 2^m CLEAR: wyczyść słownik i zacznij od nowa 2^m + 1 END: koniec danych obrazu od 2^m + 2 kolejne wpisy słownika przykład, m = 2: 0 1 2 3 kolory, 4 = CLEAR, 5 = END, pierwszy wolny kod: 6

Strumień zwykle zaczyna się od CLEAR, a zawsze powinien kończyć się kodem END.

Kody o zmiennej długości

Kody zaczynają się od m + 1 bitów, bo muszą pomieścić także CLEAR i END. Gdy słownik dorośnie do granicy potęgi dwójki, kody wydłużają się o 1 bit, aż do 12:

m = 2: kody 3-bitowe dla wartości 0..7 po dopisaniu wpisu 7 → kody 4-bitowe (0..15) po dopisaniu wpisu 15 → kody 5-bitowe ... najwyżej 12 bitów, czyli kody 0..4095

Najtrudniejsze w implementacji jest ustalenie, kiedy dokładnie zmienia się długość. Kompresor dopisuje wpis w chwili wysłania kodu, a dekompresor krok później, więc oba muszą liczyć tę samą granicę z przesunięciem o jeden:

dekompresor: po dopisaniu wpisu, gdy następny wolny kod = 2^szerokość → szerokość + 1 kompresor: po dopisaniu wpisu, gdy następny wolny kod > 2^szerokość → szerokość + 1

Zastosowanie w obu programach tego samego warunku (np. "=") daje kompresor, który zmienia długość o jeden kod za wcześnie. Taki plik psuje się zwykle po kilku pierwszych pikselach.

Pełny słownik

Gdy słownik ma 4096 wpisów, nie można dopisać następnego. Kompresor ma dwie możliwości:

wysłać CLEAR (12-bitowy) i zacząć od pustego słownika, z kodami znowu m + 1 bitów. Najprostsze i najczęstsze.
nie dopisywać nowych wpisów i dalej kodować starym słownikiem, aż sam zdecyduje o wyczyszczeniu (tzw. deferred clear). Bywa lepsze dla obrazów, w których wzorce się nie zmieniają.

Dekoder musi obsłużyć oba przypadki: gdy słownik jest pełny, przestaje dopisywać wpisy i czeka na CLEAR.

Pakowanie bitów

Kody układa się w bajty od najmłodszego bitu (LSB first). Pierwszy kod zajmuje najmłodsze bity pierwszego bajtu, następny kolejne bity, a kod, który się nie mieści, przechodzi do następnego bajtu. Na koniec bajty dzieli się na podbloki po 255.

kody: 4 (3 bity), 0 (3 bity), 0 (3 bity), ... bajt 0: b7 b6 b5 b4 b3 b2 b1 b0 └┬┘ └─┬──┘ └──┬───┘ │ │ └─ kod 4 = 100 │ └────────── kod 0 = 000 └──────────────── dwa najmłodsze bity kodu 0 = 00 (trzeci bit trafia do bajtu 1)

Pełny przebieg dla przykładowego pliku jest na stronach kompresja LZW w GIF i dekompresja LZW w GIF.