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:
0: [*, A | ., 1] 1: [., 2 | *, R] 2: [*, B | ., 3] 3: [*, D | *, K]
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:
- Příznakový bajt. Ignoruju ho
- Kontrolní součet. XOR všech hodnot vstupního souboru
- Délka dekompresní tabulky (počet záznamů)
- 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ý.
- Délka souboru v bajtech. 2 byty.
- Zkompresovaný soubor jako bitový tok
- 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í
.ORG $f000 ;61440
.ENGINE zxs
;test loaderu
AGAIN:
LD ix,$4000
CALL LD_BYTES
JP again
;---- Víceméně kopie ROMkových rutin - ignoruju flag byte a příznaky
LD_BYTES:
DI ;Zákaz přerušení.
LD A,$0F ;Bílý BORDER.
OUT ($FE),A
LD HL,$053F ;Adresa SA/LD_RET
PUSH HL ;na zásobník.
IN A,($FE) ;Test brány $FE.
RRA ;Rotace načteného
AND $20 ;bajtu, ale zvážení jen bitu EAR.
OR $02 ;Signál BORDER červený je uložen i do
LD C,A ;registru C. ($22 pro OFF a $02 pro ON stav vstupu EAR)
CP A ;Nulový indikátor je nastaven na 1.
;Prvním úkolem při čtení dat z pásku je zjistit,
;zda existuje nějaký pulsní signál (tedy hrany
;on-off a off-on).
LD_BREAK:
RET NZ ;Návrat při BREAKu.
LD_START:
CALL LD_EDGE_1 ;Není-li přítomen signál během 1400 T
JR NC,LD_BREAK ;stavů, návrat s CY=1.
;Jinak je BORDER nastaven na cyan.
;Dále se čeká a zjišťuje, zda je signál stále přítomen.
LD HL,$0415 ;Délka čekání je téměř 1 sekunda.
LD_WAIT:
DJNZ LD_WAIT
DEC HL
LD A,H
OR L
JR NZ,LD_WAIT ;Čekací smyčka.
CALL LD_EDGE_2 ;Pokračuj při zachycení dvou po sobě
JR NC,LD_BREAK ;jdoucích hran v dané periodě.
;Nyní bude přijat jen zaváděcí signál.
LD_LEADER:
LD B,$9C ;Časovací konstanta,
CALL LD_EDGE_2 ;Pokračuj při zachycení dvou po sobě
JR NC,LD_BREAK ;jdoucích hran v dané periodě.
LD A,$C6 ;Tyto hrany musí být zachyceny během
CP B ;3000 T.
JR NC,LD_START
INC H ;Počet párů hran je ukládán do reg. H
JR NZ,LD_LEADER ;dokud jich není 256.
;Po zaváděcím signálu přicházejí části off a on pulsu sync.
LD_SYNC:
LD B,$C9 ;Časovací konstanta.
CALL LD_EDGE_1 ;Každá hrana je testována,
JR NC,LD_BREAK ;dokud nejsou nalezeny dvě hrany blízko sebe.
LD A,B ;(startovací puls sync).
CP $D4
JR NC,LD_SYNC
CALL LD_EDGE_1 ;Na konci musí být ještě konečná hrana části on
RET NC ;synchronizačního pulsu sync.
;Teď už se mohou načítat bajty hlavičky nebo
;programu (bloku dat) v operacích LOAD, VERIFY.
;První bajt určuje typ.
LD A,C ;BORDER na zelenou / magenta
XOR $06
LD C,A
;---------
; tady začíná vlastní nahrávání.
; Nejprve se vytváří dekompresní strom
; Ukládá se od adresy FC00 (musí být dělitelná $400)
; konstanta HUF_TABLE je tato adresa / $400
HUF_TABLE EQU $3F
LD hl,HUF_TABLE * $400
CALL LD_byte ;flag byte -> E
RET nc
;zahodim flag
CALL LD_byte ;checksum -> E
RET nc
;ulozim si checksum do A'
LD a,e
EX af,af'
CALL LD_byte ; počet čtveřic v kompresním stromu
RET nc
LD d,e
; D hodnot pro tabulku
HUF_DECODE:
LD B,$B2
CALL LD_EDGE_2 ;Nalezení délky pulsů jednotlivých bitů.
RET NC ;Návrat při nesprávné (větší) délce pulsu, (pak CY=0)
LD A,$CB ;Porovnání délky oproti asi 2400 T,
CP B ;kdy pro nulový bit je CY=0 a pro jedničkový bit je CY=1.
; první bit záznamu udává příznak hodnota / odkaz
SBC a,a ; CY=0 -> 00, CY=1 -> FF
LD (hl),a ; ukládám do paměti příznak jako 00 nebo FF
INC hl ; a za něj první hodnotu / odkaz
CALL ld_byte ; načtu bajt
LD (hl),e ; a uložím.
INC hl ; Teď se bude obojí opakovat pro jedničkový bit
LD B,$AF
CALL LD_EDGE_2 ;Nalezení délky pulsů jednotlivých bitů.
RET NC ;Návrat při nesprávné (větší) délce pulsu, (pak CY=0)
LD A,$CB ;Porovnání délky oproti asi 2400 T,
CP B ;kdy pro nulový bit je CY=0 a pro jedničkový bit je CY=1.
; jeden bit příznaku
SBC a,a
LD (hl),a
INC hl
CALL ld_byte
LD (hl),e
INC hl ; čtveřice hotova
DEC d ; už mám kompletní strom?
JR nz,huf_decode ; Ještě ne, tak čtu dál.
; Tabulka je hotova, tak můžeme nahrávat data
; Nejprve délku do registrů DE
CALL ld_byte
LD h,e
CALL ld_byte
LD d,e
LD e,h
LD A,C ;BORDER na modrou a žlutou.
XOR $05
LD C,A
; vlastní smyčka pro nahrávání
HUF_LOAD:
LD b,$b2
LD l,0
HUF_BIT:
CALL LD_EDGE_2
RET nc
LD a,b
CP $cc ; lehce upravená konstanta
LD h,HUF_TABLE ; H je vyšší bajt adresy / 4
; L nižší (ukazatel na záznam)
CCF
ADC hl,hl
ADD hl,hl
; HL = adresa tabulky * 4 + 2 * CY
; tedy pro CY=0 je to 4*HL, pro CY=1 je to 4*HL+2
RRC (hl) ; příznak hodnota/odkaz do CY
INC hl
LD l,(hl) ; v L je teď hodnota nebo odkaz
LD b,$b1 ; připravíme časovací konstantu
JR nc,huf_bit ; pokud šlo o odkaz, tak pokračujeme s dalším bitem
LD (ix+0],l ; když ne, máme v L hodnotu k uložení
INC ix ; adresa++
DEC de ; počítadlo--
EX af,af'
XOR l ; kontrolní součet v A'
EX af,af'
LD a,d ; Už jsou všechny bajty načteny?
OR e
JR nz,huf_load ; Ještě ne!
EX af,af'
CP 01 ; pokud je A' nenulový, bude CY=0 - tedy chyba
RET
; načtení bajtu do reg. E
LD_BYTE:
LD B,$B2 ;Časovací konstanta.
LD_MARKER:
LD E,$01 ;Uložení značkového bitu.
;Tato smyčka sestavuje načítaný bajt do registru E.
LD_8_BITS:
CALL LD_EDGE_2 ;Nalezení délky pulsů jednotlivých bitů.
RET NC ;Návrat při nesprávné (větší) délce pulsu, (pak CY=0)
LD A,$CB ;Porovnání délky oproti asi 2400 T,
CP B ;kdy pro nulový bit je CY=0 a pro jedničkový bit je CY=1.
RL E ;Uložení nového bitu do registru E.
LD B,$B0 ;Časová konstanta pro další bit.
JR NC,LD_8_BITS ;Nejednalo-li se o poslední (osmý)bit
;skok zpět do smyčky.
;
RET ;návrat s CY=1
LD_EDGE_2 EQU $05e3
LD_EDGE_1 EQU $05e7