 |
|
| Start | Super Packer | Atari Graphics Studio | Graph2Font | Mads | MadPascal | YouTube | http://madteam.atari8.info |
|
Fox/Taquart
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: 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: 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ę:
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 |
|
madteam.atari8.info © MadTeam, hosted: www.atari8.info |