Loaderové intermezzo

Trošku nečekaně se mi v mém plánu na články o loaderech objevil jeden hezký kousek, o který bych se s vámi rád podělil. Není moc efektní, jeho kouzlo je schované uvnitř, ale kdoví, třeba se bude někomu hodit.

Zatímco se jinde často jde od teorie k praxi, zde to zkusím obráceně a začnu rovnou praxí. Tady máte jeden .tzx soubor, zkuste si ho v emulátoru spustit…

(nezbytná pauza na stažení, spuštění emulátoru, spuštění nahrávání… čekáme… aha… aha… hmm… a co to jako je, to je všechno?)

Nojo, to je všechno. Prostě se jen nahrávají obrazovky z pásku. Já vám to říkal, že to není moc na efekt. Ale zkuste se na ten TAP podívat. Jasně, BASIC, jasně, loader, jednotlivé obrazovky, nojo, 2682 bajtů, 2189, 3340, 4522 bajtů, aha, jsou komprimované… aha, ale nahrávají se přímo… ten loader je musí dekomprimovat za běhu!

No vidíte, že to šlo!

V minulém článku jsem frajersky tvrdil, že Digisynth při nahrávání data rozbaloval. Tyjo, opravdu? Nezdálo se mi to? Paměť mám děravou… Tak jsem stáhnul Digisynth, chvíli brejlil do kódu a pak jsem zahlédl povědomou pasáž: Ne, nezdálo! Dobrý, chtěl jsem to pustit z hlavy, ale znáte to… V metru mi to začalo vrtat: Vždyť nemůže být složité ten loader rekonstruovat a udělat k němu i packer… Huffmanova komprese je jednoduchá…

Hufmannova komprese

je opravdu jednoduchá. Tedy ve chvíli, kdy už trošku kompresních metod znáte. Pokud ne, dovolte mi rychlý kurz:

Nejjednodušší kompresní metody jsou takové, které eliminují dlouhé sekvence bajtů o stejné hodnotě (RLE). Jsou rychlé a nenáročné, takže je lze použít i v loaderu a nasadit třeba do kopíráku (takže se do paměti vejde víc než by se tam vejít mělo, jelikož kopírák při nahrávání data kompresuje tímhle jednoduchým způsobem: „Následuje blok šedesáti nul!“

Lepší kompresní metody využívají toho, že se některé sekvence často opakují. Vytváří si proto slovník opakujících se sekvencí, a ty nahrazují kratším kódem. Proto se jim říká „slovníkové metody“. Vycházejí z pramáti slovníkových algoritmů, totiž LZ (Lempel-Ziv).

Jiný přístup zvolil pan Huffman a navrhl kompresi, založenou nikoli na sekvencích, ale na četnosti výskytu určitých hodnot. Zkrátka vezme všechny hodnoty v souboru (třeba bajty, takže 0 až 255) a spočítá, kolikrát se jaká hodnota ve vstupním souboru vyskytne. Pomocí téhle informace vytvoří pro každou hodnotu kód (sekvenci bitů), který má tu vlastnost, že čím je hodnota častější, tím je sekvence kratší. Například u těch obrazovek se velmi často vyskytuje nula. Pokud je tam opravdu velmi často, je zakódována klidně jako dva bity. V extrémním případě i jako jeden. Ano, na druhou stranu ty málo používané hodnoty jsou delší, zaberou klidně dvanáct, patnáct bitů. Ale tuhle ztrátu bohatě vynahradí úspora u těch častých.

Pokud jsou ve vstupním souboru různé hodnoty, a všechny přibližně stejněkrát, tak se Huffmanova komprese stane neefektivní, ale pro běžné soubory má výsledky dobré. Často se také používá pro komprimaci hodnot ze slovníkové komprese LZ (LZHUF). Je použita i v algoritmu JPEG…

Do implementačních detailů nebudu zabíhat, stačí vědět, že si algoritmus vytvoří binární strom, který nakonec má přesně tu vlastnost, co jsem výše popisoval.

Nevýhoda je, že pro rozkódování potřebujeme předat nejdřív tenhle strom. Tuto nevýhodu obchází adaptivní Huffmanovo kódování, ale to je zase výpočetně náročnější při dekompresi. Na Spectru v loaderu nic moc…

Dekompresní strom tak, jak je implementovaný, je v zásadě velmi jednoduchá struktura. Každá položka má dvě hodnoty, jednu pro nulový bit, druhou pro jedničkový. Hodnota je buď odkaz na jinou položku (pokud kód pokračuje), nebo výsledné číslo.

Názorně

Dejme tomu, že máme řetězec ABRAKADABRA. Strom je vidět zde, a výsledný kód je:

A: 0
B: 100
R: 11
K: 1011
D: 1010

Dekompresní strom tedy bude vypadat takto:

Nebojte, hned vysvětlím. Dekomprese začíná vždy u první položky. Pokud je první bit nulový, bere se levá část (*, A), pokud jedničkový, pravá (., 1). Hvězdička znamená „Už vím, co to je za znak, je to tenhle!“, tečka znamená „pokračuj daným záznamem“.

Dejme tomu, že budou chodit bity 0, 1, 0, 0, 1, 1, 0, … Co se bude dít?

  • Záznam číslo 0.
  • Bit=0: levá část oznamuje, že jsme našli znak A. Máme první bajt, začínáme znovu záznamem 0
  • Bit=1: pravá část říká, že máme pokračovat záznamem 1
  • Bit=0: levá část (.,2) říká, že máme pokračovat záznamem číslo 2
  • Bit=0: levá část záznamu 2 říká, že jsme našli znak B. Máme druhý, začínáme znovu záznamem 0
  • Bit=1: pravá část říká, že máme pokračovat záznamem 1
  • Bit=1: pravá část říká, že jsme našli znak R. Znovu od záznamu 0
  • Bit=0: levá část oznamuje, že jsme našli znak A.
  • … a tak dále.

Implementace

Kompresní algoritmus jsem si napsal v JavaScriptu. Můžete ho použít i vy, je to normální HTML stránka, kam pomocí drag a drop přenesete soubor, který chcete zkomprimovat, a stáhne se vám .tap soubor s výsledkem, vhodným k načtení loaderem. Upozornění: Na vašem Pentiu MMX s prohlížečem IE3 to pravděpodobně fungovat nebude. Ani s novým IE to nefunguje. Použijte Chrome nebo Firefox, díky.

Výsledný soubor má následující formát:

  1. Příznakový bajt. Ignoruju ho
  2. Kontrolní součet. XOR všech hodnot vstupního souboru
  3. Délka dekompresní tabulky (počet záznamů)
  4. Data pro dekompresní tabulku. Každý záznam je uložen jako 2×9 bitů. První bit je příznak, následujících 8 hodnota. Příznak určuje, jestli jde o cílovou hodnotu (1), nebo o odkaz (0). Prvních 9 bitů je pro nulový bit, zbývajících 9 pro jedničkový.
  5. Délka souboru v bajtech. 2 byty.
  6. Zkompresovaný soubor jako bitový tok
  7. Zarovnání počtu bitů na celou osmici, aby nebyly problémy při kopírování souboru

Vlastní loader na začátku kopíruje standardní ROMkový loader, jak byl popsán minule. Pro načtení celého bajtu používám lehce upravenou rutinu LD_8_BITS, která neskládá výsledek do registru L, ale do registru E. LD_EDGE nejsou součástí rutiny, volám ty z ROMky (protože nedělám žádný speciální efekt, navíc s tím takto líp pracují emulátory a dovolí i různé zrychlené nahrávání).

Pro dekompresní tabulku je potřeba najít 1kB místa od adresy, která je zarovnaná na hodnotu $400. Já zvolil $FC00, ale můžete zvolit i jinou. Při ukládání je příznak hodnota/odkaz uložen do paměti jako celý byte (00/FF), testování je pak jednodušší (prostou rotací se zkopíruje do CY jednička nebo nula).

Rutina nekontroluje flag byte ani nebere délku dat, jediné, co potřebuje, je adresa pro uložení dat v registru IX.

V rutině nejsou žádné speciální triky, všechno je tak přímočaré, jak jsem výše popsal.

Jo a ještě: Pokud chcete, můžete ji použít pro svoje výtvory, je pod licencí CC-0 (Public Domain). Poděkování kdyžtak směřujte na autora původní rutiny z DigiSynthu…

Samozřejmě by šlo vylepšit kompresi, odstranit opakované sekvence, předkomprimovat, čímž by se výsledný kompresní poměr ještě zlepšil. Mým cílem nebylo představit nadupaný kompresor, ale ukázat, jak se dá do loaderu zakomponovat zajímavá funkcionalita.

PS: Manic Miner v Huffmanově podání

 

Příspěvek byl publikován v rubrice Software, Stroják se štítky , , , . Můžete si uložit jeho odkaz mezi své oblíbené záložky.
  • Softhouse

    Skvelý článok. Kompresii som sa venoval, len povrchne, preto som sa zasa niečo nové naučil 🙂

  • Díky, to mě těší.

  • Bystroushaak

    Velmi dobré.