| Start | Super Packer | Atari Graphics Studio / AGS | Graph2Font / G2F | Mads | MadPascal |   http://madteam.atari8.info  
SKŁAD GRUPY
PRODUKCJE
scena
gry
użytki
vbxe
SPRZĘT
Sio2SD / Pajero
Sio2SD / Rocky
Stereo / Pajero
GTIA / Psychol
ANTIC + VBXE test
ARTYKUŁY
DEMO EFFECTS
LINKI
   

Fox/Taquart
Dekompresja formatu DEFLATE
Syzygy #8

W numerach 10 i 11 Serious-a kol. Glonisz/Quasimodos bardzo ładnie opisał różne metody kompresji. Przed przystąpieniem do lektury poniższego artykułu polecam zapoznanie się z oboma tekstami Glonisza.

Kilka miesięcy temu zmierzyłem się z podobnym problemem, jak Glonisz, czyli kompresją dema. Również przyjąłem rozwiązanie spakowania całości i rozpakowywania poszczególnych efektów przed uruchomieniem. Jako człowiek, jestem z natury leniwy, więc postanowiłem skorzystać z istniejących kompresorów. Po przeanalizowaniu wszystkich algorytmów kompresji, w liczbie jeden, zwyciężył format DEFLATE.

Cóż to jest DEFLATE? Otóż jest to od wielu lat bez wątpienia najpopularniejszy format kompresji na świecie. Wystarczy wspomnieć, że jest on używany w archiwach ZIP i GZ, obrazach PNG oraz bibliotece ZLIB. Pełny opis tego formatu znajduje się w dokumencie RFC 1951 pod adresem http://www.ietf.org/rfc/rfc1951.txt

Poniżej opiszę skrótowo główne założenia formatu, co powinno pomóc w analizie mojej procedury dekompresji. Wg numeracji Glonisza zastosowano w nim połączenie metod 2 i 3. Wejście jest traktowane jako strumień bitów, co rzeczywiście sprawia, że dekompresja jest wolna (daje się to odczuć w demie), chociaż nie tak ślimacząca się jak w wiekowych kompresorach na Atari, jak np. Super Packer.

Spakowane dane składają się z bloków, chociaż z tego, co zauważyłem, dla niezbyt długich danych zazwyczaj jest tylko jeden blok. Występują trzy typy bloków: nieskompresowany, skompresowany z domyślnymi drzewami Huffmana, skompresowany z podanymi drzewami Huffmana. Typ bloku jest zapisywany na dwóch bitach (kombinacja 11 oznacza błąd). Jeden bit mówi nam, czy jest to ostatni blok.

Budowa bloku nieskompresowanego jest prosta. Dalsze dane są wyrównane do granicy bajtu, a są to kolejno: dwubajtowa długość, dwubajtowa długość z zanegowanymi bitami (z punktu widzenia kompresji zbędna, ale umożliwiająca wykrycie błędu), nieskompresowane dane.

Typy bloków nieskompresowanych różnią się tym, że drzewa Huffmana mogą być podane, lub nie. W drugim przypadku używamy domyślnych drzew Huffmana, które są wbudowane w dekompresor, dlatego nie muszą się znajdować w skompresowanych danych. Drzewa domyślne w wielu przypadkach dobrze się sprawdzają, szczególnie w przypadku plików tekstowych.

Cóż to są drzewa Huffmana? Są to właśnie drzewa tak ładnie rysowane przez Glonisza. Opisują one, jakie kody są reprezentowane przez poszczególne ciągi bitów.

Ponieważ w DEFLATE mamy połączenie dwóch metod kompresji (słownikowej i probabilistycznej), wygodnie jest myśleć o kompresji jako procesie dwuprzebiegowym. W pierwszym przebiegu dokonujemy kompresji słownikowej przez wyszukanie powtarzających się sekwencji, a w drugim stosujemy kompresję probabilistyczną.

Weźmy sztandarowy przykład danych do kompresji: "hello, hello". Po kompresji słownikowej otrzymujemy "hello, [5;7]"."[5;7]" oznacza, że powinniśmy wstawić 5 bajtów, które wystąpiły 7 bajtów wcześniej.

Co mamy na wejściu kompresji probabilistycznej? Musimy zakodować pojedyncze bajty, sekwencje "słownikowe" oraz koniec bloku. Właśnie, w danych skompresowanych nie jest podana ich długość, lecz jest specjalny kod oznaczający koniec. Wszystkie dane, które mamy zapamiętać, dzielimy na dwa zbiory: w jednym są odległości (w przykładzie 7), w drugim wszystko inne. Dokładnie alfabety kodów wyglądają następująco:

1. Zbiór podstawowy

  0-255: bajty 0-255
    256: koniec bloku
    257: sekwencja 3-bajtowa
    258: sekwencja 4-bajtowa
259-285: coraz dłuższe sekwencje, do 258 bajtów włącznie

2. Zbiór odległości

   0: odległość 1 bajtu
   1: odległość 2 bajtów
2-29: coraz dłuższe odległości, do 32768 bajtów włącznie

Mając dwa zbiory, dla każdego tworzymy drzewo Huffmana... i już! Dekompresja jest bajecznie prosta:

  • 1. Pobierz z wejścia kod, posługując się podstawowym drzewem Huffmana.

  • 2. Jeśli 0-255, zapisz na wyjście i idź do 1.

  • 3. Jeśli 256, zakończ.

  • 4. W przeciwnym przypadku pobierz z wejścia kod, posługując się drzewem odległości, przepisz sekwencję i idź do 1.

    Muszę wyjaśnić, co się kryje pod określeniami "coraz dłuższe sekwencje/odległości". Początkowo są to wartości zwiększające się o 1, ale później jest inaczej, np.

    4: odległość 5 lub 6 bajtów
    5: odległość 7 lub 8 bajtów
    6: odległość od 9 do 12 bajtów
    

    Jak widać, sam kod może nie określać jednoznacznie długości/odległości. Jak ją określić dokładnie? Należy pobrać dodatkowe bity z wejścia.

    W przypadku kodów odległości 4 i 5 wystarczy pobrać po 1 bicie, a dla kodu 6 bierzemy 2 bity i dodajemy do wartości bazowej. Analogicznie postępujemy dla długości. Dokładne wartości dla standardu DEFLATE można znaleźć w RFC oraz w tablicach w kodzie źródłowym, mających w nazwie człon "BaseValue" lub "ExtraBits".

    Pozostało pytanie, skąd wziąć drzewa Huffmana?

    Drzewa te są jednoznacznie określone przez długości bitów poszczególnych kodów. Dla przykładu rozważmy 3-bajtowe dane nieskompresowane "AAB". Podstawowe drzewo Huffmana będzie zawierać następującą informację:

         A - 0
         B - 10
    koniec - 11
    

    Drzewo odległości będzie puste, bo nie mamy tu powtarzających się sekwencji. Skompresowany ciąg będzie miał postać "001011".

    Drzewo Huffmana budujemy dysponując następującymi informacjami:

            A - 1 bit
            B - 2 bity
       koniec - 2 bity
    inne kody - 0 bitów (nie są używane)
    

    W przypadku domyślnych drzew Huffmana ilości bitów dla poszczególnych kodów są znane dekompresorowi.

    W drugim rodzaju bloku skompresowanego muszą one zostać odczytane. Długości kodów są nie większe, niż 15, dlatego mogłyby być zapisane na 4 bitach. Dla 286+30 kodów oznaczałoby to 158 bajtów informacji o drzewach Huffmana.

    Jednak zapis długości kodów jest skompresowany! Stosuje się tutaj połączenie kompresji RLE (nr 1 u Glonisza) i probabilistycznej (nr 3). Mamy jeszcze inny alfabet kodów:

    0-15: długość 0-15
      16: powtórz poprzednią wartość 3-6 razy
      17: wpisz 3-10 zer
      18: wpisz 11-138 zer
    

    Dla kodów 16-18 pobieramy dodatkowe 2, 3 lub 7 bitów, które nam precyzują wartość. Dla tego alfabetu znów potrzebujemy drzewo Huffmana...

    Czy jeszcze się nie pogubiliście? :-) Tym razem długości kodów (od 0 do 7) mogą być zapisane na 3 bitach, co by dawało 3*19 bitów. Okazuje się, że szkoda nawet tylu bitów, bo sporo wartości może być nie używanych. Odczytujemy więc od 4 do 19 długości 3-bitowych. Liczba od 4 do 19 jest zapisana na 4 bitach. Odczytujemy nie po kolei długości kodów 0, 1, 2, 3..., lecz kodów 16, 17, 18, 0, 8, 7, ... (patrz tablica tempCodeLengthOrder).

    A więc to był skrótowy opis założeń formatu. ;-) Szczegóły można sobie wyczytać w RFC i źródle procedury dekompresji. Jeśli szczęśliwie dobrnąłeś do tego momentu, to znaczy że pewnie chcesz skorzystać z tego formatu kompresji.

    Niestety, nie słyszałem o kompresorze DEFLATE na 8-bitowym Atari i zapewne nigdy go nie będzie (biorąc chociażby pod uwagę szybkość). Kompresję musimy wykonać na większej maszynie. Możliwe podejścia to:

  • Użycie dowolnego kompresora ZIP. Niestety mamy tu problem, jakim jest wycięcie nagłówków.

  • Skorzystanie z biblioteki ZLIB (w języku C) lub klasy java.util.zip.Deflater (w języku Java). Jako zagorzały zwolennik Javy, podaję sposób kompresji do formatu DEFLATE bez dodatkowych nagłówków:

    import java.util.zip.Deflater;
    Deflater d = new Deflater(Deflater.BEST_COMPRESSION, true);
    d.setInput(nieskompresowane);
    d.finish();
    długość = d.deflate(skompresowane);
    

    Jeśli będzie zapotrzebowanie, mogę przygotować prosty kompresor w języku C - na PC/Amigę/TT...

    Moja procedura dekompresji znajduje się:

  • W kompilatorze CC65, gdzie można ją wywołać z poziomu języka C

  • W pliku inflate.asx w formacie xasm-a. Opis użycia pierwszej wersji znajduje się w zlib.h, a drugiej jest następujący:

    • etykietę zpage ustawiamy na 11 bajtów na stronie zerowej przeznaczonych dla tej procedury

    • etykietę inflate ustawiamy na adres, gdzie procedura ma być skompilowana - zajmuje ona ok. 3 strony pamięci na kod i tablice stałych, a następne 3 strony zajmują tablice zmiennych - w sumie niecałe 1,5 kilobajta.

    • kompilujemy inflate.asx i łączymy z naszym programem

    • wywołujemy:

        mwa #skompresowane inputPointer
        mwa #rozkompresowane outputPointer
        jsr inflate
      

    Na koniec porównanie jakości kompresji formatu DEFLATE z metodami opisanymi przez Glonisza.

    Plik QA.COM:
    niespakowany: 12329
    Huffman: 11634
    LZ: 11209
    LZ i Huffman: 10876
    Super Packer: 12329
    DEFLATE: 9812
    

    Plik DEMO.ASM:
    niespakowany: 6362
    Huffman: 3151
    LZ: 2379
    LZ i Huffman: 2540
    Super Packer: 2228
    DEFLATE:  1581
    

    Jeszcze jako ciekawostka:

    Demo NUMEN:
    niespakowane: 380441
    DEFLATE: 171436
    

    Jeśli ktoś chciałby przeprowadzić więcej testów, najprościej jest to zrobić dowolnym kompresorem ZIP (oczywiście włączając maksymalną kompresję) - należy wziąć pod uwagę wyświetlaną długość po kompresji, gdyż plik zawiera pokaźne nagłówki ZIPa. Można skompresować na raz wiele plików, gdyż w ZIPie każdy plik jest pakowany osobno.

    Fox/Taquart

    PS. Wprawdzie nie zgłoszono mi jeszcze zapotrzebowania, ale i tak postanowiłem napisać kompresor w języku C. Jego źródło znajduje się w archiwum deflater.zip. Jest tam też skompilowany dla peceta plik wykonywalny. Kompilowałem przy użyciu GCC 3.0.4/ DJGPP poleceniem

    gcc -s -O2 -o deflater.exe deflater.c -lz
    



  • Zebrane produkcje z ostatnich lat dla Atari 8bit XE/XL (11 MB)
     

    madteam.atari8.info © MadTeam, hosted: www.atari8.info