Cruncher 5.0
From Atariki
| Wersja z dnia 19:53, 11 lip 2006 KMK (Dyskusja | wkład) (→Mała rewolucja) ← Previous diff |
Wersja z dnia 20:21, 20 gru 2006 Miker (Dyskusja | wkład) Next diff → |
||
| Linia 2: | Linia 2: | ||
| == Historia == | == Historia == | ||
| - | [[Cruncher 5.0]] to następca [[Cruncher 4.64|Crunchera 4.64]] napisany przez [[Magnus]]a. Ujrzał światło dzienne w rok po swoim poprzedniku, a był to rok 1991. Ta wersja w stosunku do poprzedniej oferowała kompresję w dwóch przebiegach. Pierwszy etap to tzw. kompresja znacznikowa (z angielskiego [[char-pack]]), drugi etap to w/g dokumentacji dołaczonej do programu przez Magnusa to "pointer-sequence-bit-packer". Algorytm tego typu był przez niektórych nazywany [[imploding]]iem, a próbując określić to dokładniej możemy się domyślać, iż była to jakaś odmiana algorytmu [http://pl.wikipedia.org/wiki/LZ77 LZ77]/[http://en.wikipedia.org/wiki/LZSS LZSS]. Należy dodać, iż w tamtych czasach był to pierwszy [[cruncher]] który używał tego typu algorytmu na ATARI. [[Cruncher 5.0]] był najbardziej efektywnym cruncherem do czasu pojawiania się jego następców, np. [[Code3 Cruncher]]a. Wyznaczył on pewien standard cruncherów na 8-bitowym ATARI i tak naprawdę zapoczątkował "modę" na skracanie programów i gier. Kilka rewelacyjnych pomysłów Magnusa pokazało, iż da się obejść parę problemów, przez które nikt wcześniej za bardzo nie chciał się zabierać za pisanie crunchera z prawdziwego zdarzenia. | + | [[Cruncher 5.0]] to następca [[Cruncher 4.64|Crunchera 4.64]] napisany przez [[Magnus]]a. Ujrzał światło dzienne w rok po swoim poprzedniku, a był to rok 1991. Ta wersja w stosunku do poprzedniej oferowała kompresję w dwóch przebiegach. Pierwszy etap to tzw. kompresja znacznikowa (z angielskiego ''Run-Length Encoding'' lub [http://pl.wikipedia.org/wiki/RLE RLE]), drugi etap to w/g dokumentacji dołaczonej do programu przez Magnusa to "pointer-sequence-bit-packer". Algorytm tego typu był przez niektórych nazywany [[imploding]]iem, a próbując określić to dokładniej możemy się domyślać, iż była to jakaś odmiana algorytmu [http://pl.wikipedia.org/wiki/LZ77 LZ77]/[http://en.wikipedia.org/wiki/LZSS LZSS]. Należy dodać, iż w tamtych czasach był to pierwszy [[cruncher]] który używał tego typu algorytmu na ATARI. [[Cruncher 5.0]] był najbardziej efektywnym cruncherem do czasu pojawiania się jego następców, np. [[Code3 Cruncher]]a. Wyznaczył on pewien standard cruncherów na 8-bitowym ATARI i tak naprawdę zapoczątkował "modę" na skracanie programów i gier. Kilka rewelacyjnych pomysłów Magnusa pokazało, iż da się obejść parę problemów, przez które nikt wcześniej za bardzo nie chciał się zabierać za pisanie crunchera z prawdziwego zdarzenia. |
| == Mała rewolucja == | == Mała rewolucja == | ||
Wersja z dnia 20:21, 20 gru 2006
Spis treści |
Historia
Cruncher 5.0 to następca Crunchera 4.64 napisany przez Magnusa. Ujrzał światło dzienne w rok po swoim poprzedniku, a był to rok 1991. Ta wersja w stosunku do poprzedniej oferowała kompresję w dwóch przebiegach. Pierwszy etap to tzw. kompresja znacznikowa (z angielskiego Run-Length Encoding lub RLE), drugi etap to w/g dokumentacji dołaczonej do programu przez Magnusa to "pointer-sequence-bit-packer". Algorytm tego typu był przez niektórych nazywany implodingiem, a próbując określić to dokładniej możemy się domyślać, iż była to jakaś odmiana algorytmu LZ77/LZSS. Należy dodać, iż w tamtych czasach był to pierwszy cruncher który używał tego typu algorytmu na ATARI. Cruncher 5.0 był najbardziej efektywnym cruncherem do czasu pojawiania się jego następców, np. Code3 Crunchera. Wyznaczył on pewien standard cruncherów na 8-bitowym ATARI i tak naprawdę zapoczątkował "modę" na skracanie programów i gier. Kilka rewelacyjnych pomysłów Magnusa pokazało, iż da się obejść parę problemów, przez które nikt wcześniej za bardzo nie chciał się zabierać za pisanie crunchera z prawdziwego zdarzenia.
Mała rewolucja
To właśnie Magnus wprowadził podział kompresji pliku na dwa etapy. W pierwszym etapie plik zostaje wczytany do pamięci, po czym do akcji wkracza właściwa procedura pakująca. Po zakończeniu tej operacji, możemy dokonać połączenia spakowanych danych z procedurami dekompresji przy pomocy tzw. linkera. Cruncher 5.0 był pierwszym programem kompresującym pliki, który mógł być użyty przez ludzi nie mających pojęcia o asemblerze i procedurach kompresji danych. Był bardzo prosty w użyciu i pozwalał każdemu na spróbowanie swoich sił w skracaniu programów. Do tego nie zadawał zbędnych trudnych pytań.
Smutne realia
Warto tutaj wspomnieć iż Cruncher 5.0 Magnusa był programem typu shareware. Jeżeli ktoś używał tego programu powinien był zapłacić jego autorowi. Był taki okres, iż prawie wszyscy używali crunchera Magnusa jednak nikt nie zadał sobie trudu aby wysłać jakiekolwiek pieniądze autorowi. Magnus myśląc, iż zainteresowanie programem jest nikłe, zaprzestał prac nad kolejnymi wersjami (zobacz także fragment wywiadu z Magnusem odnośnie tej kwestii). Podobna sytuacja przydarzyła się SoTe który stworzył Code3 Crunchera. Ten program również posiadał status shareware, jednak nigdy żadnej złotówki SoTe nie zobaczył, co również szybko zniechęciło go do dalszych prac nad następnymi wersjami. Na taką sytuację mogła mieć wpływ trudna wówczas (pierwsza połowa lat 90. XX w.) sytuacja gospodarcza w Polsce, początki demokracji zazwyczaj bywają niełatwe. Być może ludzie po prostu nie byli jeszcze na to gotowi.
Kompresja dla ATARI, dlaczego tak późno?
Niektórzy mogą się zastanawiać dlaczego na 8-bitowym ATARI nikt wcześniej nie skłaniał się do napisania podobnego programu, w ówczesnym czasie na konkurencyjnej platformie Commodore 64 była dostępna niezliczona ilość cruncherów. C64 miało jednak pewne ograniczenia narzucone przez system, które sprawiły iż ludzie zajmujący się tamtą platformą sprzętową musieli sobie jakoś poradzić. C64 do dyspozycji miało pełne 64KB pamięci, jednak system komputera narzucał ograniczenie na rozmiar i miejsce wczytywania pliku. Maksymalny rozmiar wczytywanego pliku to 38911 bajtów. Do tego wszystkiego program musiał się wczytywać za jednym razem, bez możliwości wykonania jakichkolwiek operacji podczas wczytywania, musiał się ładować od adresu $801 i jedyną możliwością załadowania programu do pamięci była komenda "LOAD" z poziomu interpretera BASICa.
W przypadku ATARI, człowiek który wymyślił format plików binarnych (prawdopodobnie autor pierwszego DOSa), był na tyle przewidujący iż format który opracował był zarazem genialny w swojej prostocie i do tego bardzo, ale to bardzo funkcjonalny. Program mógł się wczytywać w prawie w dowolne obszary pamięci, mogł być podzielony na niezależne bloki, podczas wczytywania po każdym wczytanym bloku można było wywołać własne procedury, taki program mógł uruchamiać się od dowolnego podanego w pliku adresu.
Można się domyślać iz własnie zastosowanie takiego formatu pliku w przypadku ATARI, pozwalało twórcom oprogramowania zachować dowolność co do rozmieszczenia danych w pamięci. Takie rozwiązanie miało swoje niezaprzeczalne zalety. Jednak jeżeli chcielibyśmy stworzyć program kompresujący takie pliki, pojawiają się także pewne problemy. Przed cruncherem Magnusa powstało kilka programów próbujących skracać pliki binarne, jednak były to tylko namiastki prawdziwych cruncherów. Dobrym przykładem takiej próby był program Zagęszczacz, Dariusza Rogozińskiego z Iron Softu.
Dlaczego tak?
Wracając jednak do Crunchera 5.0... Magnus pisał go z myślą o kompresowaniu plików które nie potrzebują dla swojej pracy DOS-a, np. gry i dema są świetnym przykładem tego typu programów. Drugim założeniem było to iż program który chcemy poddać kompresji po uruchomieniu nie będzie próbował powrócić do systemu nadrzędnego, a jedyną możliwością przerwania pracy programu będzie klawisz RESET.
Przyglądając się strukturze plików binarnych, oraz mając na uwadze to co mogą one wyprawiać podczas ładowania Magnus musial dojść do wniosku iż struktura i zachowanie takiego pliku podczas ładowania nie jest po prostu możliwa do przewidzenia. Najlepszym wyjściem z tej sytuacji było napisanie własnego loadera, który ładował by te pliki do pamięci i pozwalał im na wykonywanie dowolnych operacji podczas wczytywania. Bloki typu INIT ($2E2-$2E3) wskazujące adres uruchomienia kodu w trakcie ładowania, zostały dopuszczone, natomiast nie wolno było pozwolić na uruchomienie się programu poprzez tzw. blok RUN ($2E0-$2E1). Zamiast uruchomienia wczytanego przez loader pliku, następował skok do procedury kompresującej.
Jak wiadomo Cruncher 5.0 Magnusa dokonuje kompresji w dwóch przebiegach. Pierwszy przebieg to prosty algorytm znacznikowy, drugi o wiele bardziej efektywny LZ77/LZSS. O ile Cruncher 4.64 posiadał tylko ten pierwszy algorytm, o tyle zdziwienie może budzić zastosowanie go również Cruncherze 5.0. Na początku wydawać by się mogło iż drugi przebieg może działać nieco efektywniej na danych spakowanych wcześniej prostym algorytmem znacznikowym. Praktyczne sprawdzenie tej teorii daje nam nieco więcej do myślenia, okazuje się, że dane nie poddane wcześniej kompresji tym prostym algorytmem pakują się nieco lepiej... więc po co stosować wstępną komresję algorytmem znacznikowym? A to dlatego iż pojawia się pewiem drobny problem związany z przestrzenią adresową w ATARI, ale o tym za chwilę.
ATARI i jego pamięć RAM czyli Strefa 51
Jak wiadomo 8-bitowe ATARI teoretycznie ma 64kB pamięci RAM. Przestrzeń adresowa procesora 6502 ma zakres od $0000-$FFFF, jednak w przypadku ATARI nie cały obszar możemy wykorzystać. Po odłączeniu systemowego ROM mamy teoretycznie do dyspozycji następujące obszary pamięci; od $0000 do $CFFF, oraz od $D800 do $FFFF. Obszar od $D000 do $D7FF jest niestety obszarem niemożliwym do wykorzystania, ponieważ w tej przestrzeni mają między innymi swoje rejestry takie układy jak GTIA,POKEY,PIA,ANTIC. Podczas kompresji obszar ten należało pominąć. Oczywiście napisanie prostego algorytmu kompresji który omija ten "zakazany" obszar pamięci nie jest jakimś strasznym problemem. Może to jedynie spowolnić procedurę kompresji bo należy cały czas sprawdzać czy pobierany/zapisywany aktualnie bajt nie znajduje się przypadkiem w niedozwolonej przestrzeni adresowej. Tutaj trzeba przyznać iż C64 miało ten problem rozwiązany
Magnus w Strefie 51, co robić?
Zastosowany w drugim przebiegu kompresji algorytm dokonuje milionów porównań w poszukiwaniu powtarzających się sekwencji bajtów. Kompresja zajmuje bardzo dużo czasu właśnie ze względu na ilość potrzebnych porównań, gdyby Magnus napisal algorytm kompresji w sposób taki aby jeszcze do tego wszystkiego uwględniał omijanie "zakazanych" obszarów... kompresja trwałaby po prostu całe wieki :) Prawdopodobnie dlatego Magnus wpadł na pewien pomysł, który pozwolił na uniknięcie problemu z omijaniem "zakazanego" obszaru pamięci.
Zadaniem pierwszego przebiegu jest skrócenie danych w ten sposób aby nie przekroczyły adresu $CFFF. I w ten oto sposób drugi z zastosowanych algorytmów kompresji nie musi w ogóle sprawdzać czy dane znajdują sie w niedozwolonej przestrzeni adresowej. A ponieważ prawdopodobnie Magnus doszedł do wniosku iż im lepiej spakował dane pierwszy algorytm tym gorzej pakuje drugi, więc postanowił wprowadzić tzw. "step" przy pierwszym przebiegu kompresji. Im większy "step" tym więcej danych pierwsza procedura kompresująca pozostawia nieskompresowanych, chodzi tylko o to aby udało się zmieścić te dane przed adresem $D000. Z tak przygotowanymi danymi doskonale już sobie poradzi drugi przebieg...
Algorytm LZSS i "offset", coż to takiego?
Przed rozpoczęciem drugiego przebiegu zostaniemy zapytani o tzw. "offset", wartość ta to nic innego jak wielkość określająca ile bajtów wcześniej procedura kompresująca ma poszukiwać identycznych sekwencji bajtów. Cyfrom od 1 do 7 przypisano odpowiednie wartości offsetów w przedziale od $100 do $4000. Tak wiec widać iż przy offsecie "7", procedura przeszukuje poprzednie 16kB czy nie występuje w nim szukana sekwencja bajtów. Jak się można domyślić im większy offset tym wolniej, jednak mamy szansę iż znajdzie się sekwencja której poszukujemy. Jednak nie jest tak różowo... im większy offset tym więcej bitów trzeba wysłać aby określić położenie znalezionej sekwencji... więc należy pamiętać iz wybranie większego offsetu nie zawsze oznacza lepszę kompresję.
Podsumowanie
Cruncher 5.0 Magnusa pokazał iż da się zrobić porządny cruncher na ATARI. Zastosowanie własnego loadera i podział kompresji na dwa etapy (pakowanie i linkowanie), unaoczniło jak można zapanować nad nieprzewidywalnymi programi w formacie binarnym. Zastosowanie pierwszego znacznikowego etapu kompresji do upchnięcia danych przed obszarem $D000, to pomysły które pozwoliły Magnusowi na stworzenie pierwszego naprawdę znaczącego crunchera dla komputerów ATARI. Dzięki swojemu programowi rozpoczął on pewną małą rewolucję na scenie ATARI. Prawdopodobnie był inspiracją dla innych, a na pewno dla SoTe który postanowił napisać własnego crunchera (Code3 Cruncher). Jedną podstawową wadą tego programu było to iż nie można było nim kompresować programów wymagających dla swojego działania obecności DOSa, w ograniczonym stopniu umożliwiał to Cruncher 4.64 jednak jego efektywność pozostawiała wiele do życzenia.
Alternatywa
Przez długi czas brakowało na scenie programu który umożliwialby porzadną kompresję programów przeznaczonych dla DOS-a, nie było także programu który pozwalałby na zachowanie orginalnej struktury pliku, po kompresji... trochę czasu musiało minąć zanim pojawiły się takie programy jak np. DJ Packer Sparrow Hawka, FlashPack Foxa czy Super Packer Jiriego Bernaska. Pokazały one w 100% inne podejście do problemu... niestety te programy wymagały już nieco większej wiedzy od użytkownika jednak możliwości ich były bardziej rozbudowane. Nie można powiedzieć iż w 100% zastępowały one typowe crunchery, bardzo dobrze jednak uzupełniały lukę która długo nie była niczym wypełniona. Ich odmienne działanie polegało na tym, iż przetwarzały każdy blok binarnego pliku oddzielnie, crunchery z założenia kompresowały całą pamięć, mogły wczytac o wiele większe pliki. Każdy z tych programów nich miał swoje zastosowanie i należą się wielkie podziękowania ich autorom za to że powstały.
