energy.scene.pl

autor: jaskier

Czy wiecie na czym polega pacyfikacja? Bierze się packę na muchy i się je pac, pac- pacyfikuje, a wtedy już one siedzą cicho.

A czy wiecie na czym polega packowanie? Na tym samym co pacyfikacja, tyle że nie na muchach.

Ogólnie rzecz biorąc, dane pakuje się po to, aby nam nie przeszkadzały podczas pracy. Ileż to już razy próbowaliście napisać program, w którym byłoby 40KB sampli, plus 3 fullscreeny, a do tego trochę fontów i porządnego kodu i spostrzegaliście nagle, że ATARI ma tylko 62KB RAM, a wasz program sięga już 65?

W takim przypadku nie ma co się przejmować. Te dane nam przeszkadzają. Należy je więc spacyfikować. O przepraszam spackować. Żyjemy w czasach maniakalnej ochrony środowiska, trzeba więc zastosować wersję bardziej ekologiczną, bez makabrycznych doświadczeń na zwierzętach.

Pisząc nasz zin również mieliśmy podobny problem, aczkolwiek nie w stosunku do sampli i 62KB pamięci. Problemem naszym były teksty i 260KB na dyskietce medium.

Oczywiście nie przejmowaliśmy się tym zbytnio. Zaczęliśmy packować. Niniejszy artykuł traktuje o różnych próbach pacyfikacji danych, ale będzie również przydatny dla osób nie umiejących kodować.

Teksty znajdują się na dysku w postaci spackowanej. Są to pliki *.EPK. W takiej postaci mogą być używane tylko przez ten zin. Jednakże osoby posiadające pewien program zwany EED.COM, a będący edytorem używanym przez nas do pisania tych artykułów, mogą odpackować dane i czytać je za pomocą tego edytora.

Aby odpackować teksty trzeba najpierw odpackować program do ich odpackowania. Znajduje się on na pierwszej stronie dysku w pliku PACK.ARC. Kopiujemy go na jakiś inny dysk, a następnie wczytujemy program UNARC.COM i używamy opcji odarchiwizowania wobec tego pliku. Na dysku powinny pojawić się nam nowe pliki: PACK.ASM, PACK.OBJ, PACK2.ASM, PACK2.OBJ. Pliki z rozszerzeniem .ASM są źródłówkami w Quick Assemblerze, a z .OBJ- programami do uruchomienia. PACK.OBJ jest przeznaczony dla tekstów do ENERGY, a PACK2.OBJ jego wersją dla wszystkich innych plików. Różnica jest skutkiem tego, że teksty do ENERGY wykorzystują tylko kody 0-127, co daje dodatkową możliwość zaoszczędzenia 12.5% początkowej długości pliku.

Obydwa programy służą zarówno do packowania jak i do depackowania. Jeżeli będziecie używać programu PACK2.OBJ musicie pamiętać, że pakuje on dane, a nie pliki, tzn. nie mogą mieć one postaci DOS-owej. Używanie obu programów jest dość proste, więc nie będę się tutaj nad nią rozwodził. Napiszę natomiast o metodzie packowania, która zrodziła się w wyniku wielokrotnych prób i błędów.

W plikach tekstowych jest wiele elementów powtarzających się. Te same słowa, zwroty, wyrażenia itp. Pomysł był więc taki: przeszukiwać plik o ileś bajtów w tył i poszukiwać fragmentu identycznego z aktualnie sprawdzanym. Format danych po spackowaniu byłby więc następujący: 1 bit trybu pracy, oznaczający:

a) jeżeli był ustawiony, dane spackowane,
b) jeżeli był skasowany, niespackowane.

Następnie:

ad. a) n-1 bitów ustawionych zakończonych bitem skasowanym oznaczają, że w tym miejscu było n bajtów identycznych z jakimiś występującymi już wcześniej. Następne x bitów daje wartość o jaką należy się cofnąć aby znaleźć te bajty. Przy czym wartość 0 oznacza 1 bajt w tył, $ff- 256 bajtów w tył itp.

ad. b) y bitów oznaczających ile teraz nastąpi bajtów których nie dało się upakować.
Uwaga! Wartości x, y dobierało się doświadczalnie przed packowaniem.

Może teraz wyjaśnię skąd się wzięła ta metoda. Bajty powtarzające się z reguły występują w małych grupkach. Trzeba więc było znaleźć metodę najbardziej efektywną dla tych małych ilości. Zapisywanie wartości przez ilości bitów jest właśnie taką metodą. (Wówczas 1 bit, to wartość 1, 7 bitów , to 7). Natomiast zapisywanie wartości w sposób standardowy jest bardziej efektywne dla dużych wartości. (Wówczas 7 bitów: 1001010 to wartość $4a, a 8 bitów: 10111100 to $bc). W taki sposób zapisuje się o ile bajtów trzeba się cofnąć szukając bajtów powtarzających się, bądź ile teraz nastąpi bajtów niepowtarzających się. Okazało się jednak, że w przypadku tych drugich metoda ta jest nieefektywna. Po prostu w plikach tekstowych dane powtarzają się tak często, że dane niepowtarzające się są w mniejszości. Tym samym trzeba było zmienić metodę zapisu ich ilości na tą pierwszą, czyli po prostu: 0-bajt niespackowany, a po tym ten bajt i tyle. Żadnych znaczników ilości.

Wszystko byłoby pięknie, ale nagle zacząłem się zastanawiać dlaczego teksty najlepiej pakują się dla offsetu (jest to wielkość o jaką maksymalnie można się cofnąć przeglądając plik, od tego zależy ilość bitów jaką będzie zapisana wartość o jaką należy się cofnąć aby znaleźć bajty powtarzające się) równego połowie długości pliku. Zastanowiłem się i uznałem, że stały offset to przeżytek. Jeżeli np: obecnie przeglądamy bajty oddalone o $123 od początku pliku, a offset mamy ustawiony na $800, to jeżeli znajdziemy jakieś identyczne bajty i zapiszemy ich odległość, to na pewno dwa najwyższe bity będą wyzerowane. Marnotrawstwo! Podobne jeżeli przy tym offsecie będziemy poszukiwać bajtów identycznych z tymi oddalonymi o $954 od początku pliku. Nawet jeżeli będzie 200 identycznych bajtów, ale umieszczonych na samym początku pliku to niewiele nam z tego przyjdzie, bo offset nie obejmie takiego zasięgu.

Rozwiązanie jest proste. Zmienny offset równy dokładnie odległości akurat sprawdzanych bajtów od początku pliku. Jeżeli np. sprawdzamy bajt odległy o 43 bajty od początku pliku, to ewentualną odległość identycznych bajtów zapiszemy sześcioma bitami, jeżeli oddalonych o $3fff- 10 bitami, o $4000- też 10 bitami. Pliki tekstowe packowane tą metodą skracają się do ok. 55-60% swoich poprzednich rozmiarów. Zadowolony z tego wyniku poszedłem w końcu spać.

Jak widać pacyfikacja danych nie należy do rzeczy trudnych (tylko czasochłonnych) i myślę, że dostarczy wszystkim sporo zabawy.