Cruncher 5.0
From Atariki
| Wersja z dnia 16:24, 5 paź 2005 Miker (Dyskusja | wkład) ← Previous diff |
Aktualna wersja Krótki (Dyskusja | wkład) (Unikam wikilinka do strony przekierowującej; a także ortografia.) |
||
| Linia 2: | Linia 2: | ||
| == Historia == | == Historia == | ||
| - | [[Cruncher 5.0]] to następca [[Cruncher 4.64|Crunchera 4.64]] napisany przez [[Magnus|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 [[char-pack]]), drugi etap to w/g dokumentacji dołaczonej do programu przez [[Magnus|Magnusa]] to "pointer-sequence-bit-packer". Algorytm tego typu był przez niektórych nazywany [[imploding|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żwyał tego typu algorytmu na ATARI. [[Cruncher 5.0]] był najbardziej efektywnym [[cruncher|cruncherem]] do czasu pojewiania się jego następców, np. [[Code3 Cruncher|Code3 Crunchera]]. Wyznaczył on pewien standard [[cruncher|cruncherów]] na 8-bitowym ATARI i tak naprawdę zapoczątkował "modę" na skracanie programów i gier. Kilka rewelacyjnych pomysłów [[Magnus|Magnusa]] pokazało iż da się obejść parę problemów, przez które wcześniej nikt nie za bardzo chciał się zabierać na pisanie [[cruncher|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łączonej 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 [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 [[Atari 8-bit|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 == | ||
| - | 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łaczenia spakowanych danych z procedurami dekompresji przy pomocy tzw. [[linker|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 [[assembler|assemblerze]] 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ń. | + | 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. [[linker]]a. Cruncher 5.0 był pierwszym programem kompresującym pliki, który mógł być użyty przez ludzi nie mających pojęcia o [[asembler]]ze 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 == | == Smutne realia == | ||
| - | Warto tutaj wspomnieć iż [[Cruncher 5.0]] [[Magnus|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 [[cruncher|crunchera]] [[Magnus|Magnusa]] jednak nikt, nie zadał sobie trudu aby wysłać jakiekolwiek pieniądze autorowi. [[Magnus]] myśląc iż zainteresowanie programem jest niłke zaprzestał prac nad kolejnymi wersjami. Podobna sytuacja przydarzyła się [[SoTe]] który stworzył [[Code3 Cruncher|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ą sytację mogła mieć wpływ trunda wówczas sytuacja w Polsce, początki demokracji zazwyczaj bywają trudne. Może po prostu ludzie nie byli jeszcze na to gotowi. | + | Warto tutaj wspomnieć iż Cruncher 5.0 Magnusa był programem typu [http://pl.wikipedia.org/wiki/Shareware 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 [http://www.atari.org.pl/wywiad/zenek-mikolajczyk-%28magnus-wfmh%29/1 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? == | == 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 [[C64]] była dostępna niezliczona ilość [[cruncher|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 [[BASCI|BASICa]]. | + | 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 [http://en.wikipedia.org/wiki/Commodore_64 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 [[BASIC]]a. |
| - | W przypadku ATARI, człowiek który wymyślił format plików binarnych (prawdopodobnie autor pierwszego [[DOS|DOSa]]), był na tyle przwidują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. | + | W przypadku ATARI, człowiek który wymyślił format plików binarnych (prawdopodobnie autor pierwszego [[DOS]]a), 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, mógł 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 [[cruncher|cruncherem]] [[Magnus|Magnusa]] powstało kilka programów próbujących skracać pliki binarne, jednak były to tylko namiastki prawdziwych [[cruncher|cruncherów]]. Dobrym przykładem takiej próby był program [[Zagęszczacz]], [[Dariusz Rogoźiński|Dariusza Rogoźińskiego]] z [[Iron Soft|Iron Softu]]. | + | Można się domyślać iż właśnie 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]], [[Dariusz Rogoziński|Dariusza Rogozińskiego]] z [[Iron Soft]]u. |
| == Dlaczego tak? == | == Dlaczego tak? == | ||
| - | Wracając jednak do [[Cruncher 5.0|Crunchera 5.0]]... [[Magnus]] pisał go z myślą o kompresowaniu plików które nie potrzebują dla swojej pracy [[DOS|DOSa]], np. gry i [[demo|dema]] są świetnym przykładem tego typu programów :) Drugim założeniem było to iż program który chcemy poddac 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. | + | 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 [[demo|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 [[loader|loadera]], który ładwoał 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. | + | Przyglądając się strukturze plików binarnych, oraz mając na uwadze to co mogą one wyprawiać podczas ładowania Magnus musiał 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]] [[Magnus|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ż [[Cruncher 5.0|cruncherze 5.0]]. Na początku wydawać by się mogło iz drugi przebieg może dzialać nieco efektywniej na danych spakowanych wcześniej prostym algorytmem znacznikowym. Praktyczne sprawdzenie tej teroii daje nam nieco więcej do myślenia, okazuje się 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ę :) | + | 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ą kompresję algorytmem znacznikowym? A to dlatego iż pojawia się pewien drobny problem związany z przestrzenią adresową w ATARI, ale o tym za chwilę. |
| == ATARI i jego pamięć RAM czyli Strefa 51 == | == 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 nalezy 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 | + | 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]] oraz [[ANTIC (układ)|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ć? == | == 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. | + | 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 napisał algorytm kompresji w sposób taki aby jeszcze do tego wszystkiego uwzglę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... | + | 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? == | + | == Algorytm LZSS i "offset", cóż 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ę. | + | 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ć iż wybranie większego offsetu nie zawsze oznacza lepszą kompresję. |
| == Podsumowanie == | == 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), pokazał 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 [[Magnus|Magnusowi]] na stworzenie pierwszego naprawdę znaczącego [[cruncher|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 [[DOS|dosa]], w ograniczonym stopniu umożliwiał to [[Cruncher 4.64]] jednak jego efektywność pozostawiała wiele do życzenia. | + | 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 programami 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 DOS-a, w ograniczonym stopniu umożliwiał to Cruncher 4.64 jednak jego efektywność pozostawiała wiele do życzenia. |
| == Alternatywa == | == Alternatywa == | ||
| - | Przez długi czas brakowało na scenie programu który umożliwialby porzadną kompresję programów przeznaczonych dla [[DOS|dosa]], 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. [[DJP|DJ Packer]] [[Sparrow Hawk|Sparrow Hawka]], [[FlashPack]] [[Fox|Foxa]] czy [[Super Packer]] [[Jiri Bernasek|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 [[cruncher|crunchery]], bardzo dobrze jednak uzupełniały lukę która długo nie była niczym wypełniona. Ich odmienne działanie polegało to tym iz przetwarzały każdy blok binarnego pliku oddzielnie, [[cruncher|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 :) | + | Przez długi czas brakowało na scenie programu który umożliwiałby porządną kompresję programów przeznaczonych dla DOS-a, nie było także programu który pozwalałby na zachowanie oryginalnej struktury pliku, po kompresji... trochę czasu musiało minąć zanim pojawiły się takie programy jak np. [[DJP|DJ Packer]] [[Sparrow Hawk]]a, [[FlashPack]] [[Fox]]a czy [[Super Packer]] [[Jiří Bernášek|Jiříego Bernáška]]. 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 wczytać 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. |
| [[Kategoria:Oprogramowanie Atari 8-bit]] | [[Kategoria:Oprogramowanie Atari 8-bit]] | ||
| + | [[Kategoria:Polskie programy]] | ||
| [[Kategoria:Programy użytkowe]] | [[Kategoria:Programy użytkowe]] | ||
Aktualna wersja
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łączonej 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, mógł 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ć iż właśnie 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 musiał 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ą kompresję algorytmem znacznikowym? A to dlatego iż pojawia się pewien 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 oraz 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 napisał algorytm kompresji w sposób taki aby jeszcze do tego wszystkiego uwzglę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", cóż 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ć iż 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 programami 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 DOS-a, 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żliwiałby porządną kompresję programów przeznaczonych dla DOS-a, nie było także programu który pozwalałby na zachowanie oryginalnej 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 Jiříego Bernáška. 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 wczytać 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.
