KomprimAce

autor: Kamil Ševeček

Když jsem si nedávno půjčil kazetu plnou nových (alespoň pro mne) her, jako majitel pouze jediného kompresního programu jsem narazil na velký problém. Diskový Mr. Pack (můj jedináček) totiž nedokáže zakomprimovat data překrývající systémové proměnné (23552 až 23755). Co jsem měl tedy dělat s objemnějšími hrami, co překryjí i tuto oblast? Po úvahách na způsob "Tam to zapakuji, připojím k tomu to a to všechno zakompresuji ještě jednou", jsem došel k výsledku - nezbývá mi nic jiného než napsat vlastní pakovací rutinu.
Moje delší hledání mělo asi tento výsledek - každá rutina si vyhradí jeden identifikační bajt jako návěští za sebou jdoucích stejných bajtů (např. 255). Jestliže pak přijde k opakujícím se hodnotám, zapíše toto návěští, onu opakující se hodnotu a kolikrát se opakuje.
Tento způsob mi v zásadě vyhovuje, má jen jedinou chybičku. Vyskytne-li se v pakovaných datech bajt rezervovaný pro návěští (u nás 255), rutina je nucena jej uložit jako sled bajtů tří a nikoli pouze jednoho. To by mohlo mít za následek i rapidní prodloužení komprimovaných dat (3 krát).
Já jsem tedy tento způsob upravil tak, že se místo jednoho bajtu ve funkci návěští použijí bajty dva. Bude-li se komprimovat blok menší než 64kB, nemůže nastat situace, kdy by se v něm vyskytovaly všechny možné dvojbajty (wordy), těch je totiž 65536, zatímco blok bude dlouhý max. 65535 bajtů. Pro bloky delší než 64 kilobajtů a kratší než 16 megabajtů by se pak mohly vzít tři indikační bajty, od 16 megabajtů do 4 gigabajtů čtyři atd.)
Pro pakování je ale potřeba najít dvojbajt, který se v komprimovaném bloku nevyskytuje. Celkem univerzální je 237,70, který je kódem instrukce IM 0. Tu asi nikdo v programu využívat nebude. Kdyby však přece, je potřeba toto nahradit jinou hodnotou (např. 237,187 nebo 237,179 - instr. OUTDR a OUTIR).
Komprimovaná data by pak vypadala asi takto:
...
Libovolná data
...
1.bajt navěští (řekněme 237)
2.bajt návěští (třeba 70)
bajt počtu opakovaní o jedničku snížený (tj. hod.10=11x)
opakovaný bajt
...
Libovolná data
...
Výsledkem mé práce byly tedy tyto rutiny (zabýval jsem se pouze kompresí paměti od 23296 do 65535, budete-li chtít používat komprimátor i pro jiné bloky paměti, jednoduše si jej upravte):
Nejprve ta pro kompresi:

PACK	ld	hl,????	;poslední bajt výsledného komprimátu - dáme sem 65535
	ld	ix,????	;poslední bajt původních dat - sem taky 65535
	ld	a,(23296)	;pro zastavení komprese na správné
	dec	a	;adrese (viz dále)
	ld	(23295),a
KOMPRES	ld	a,(ix+0)	;Načti první bajt
	cp	(ix-1)	;Srovnej ho s druhým
	jr	nz,NEPAKUJ	;pokud nejsou stejné, odskoč na neopakující se
	cp	(ix-2)	;Srovnej ho se třetím
	jr	nz,NEPAKUJ	;pokud nejsou stejné, odskoč
	cp	(ix-3)	;I čtvrtý bajt stejný
	jr	nz,NEPAKUJ	;pokud ne, odskoč
	cp	(ix-4)	;I pátý bajt stejný
	jr	nz,NEPAKUJ	;pokud není, odskoč
	ld	b,3	;Nastav počítadlo opakovaných bajtů (nejméně 4 se již určitě opakují)
	dec	ix	;Posuň tedy i ukazatel paměti o 4 bajty dál
	dec	ix
	dec	ix
JESTE	dec	ix
	cp	(ix+0)	;Srovnej další bajt jestli se opakuje
	jr	nz,VEN	;Když ne, běž VEN
	inc	b	;Zvětši počítadlo opakujících se bajtů
	jr	nz,JESTE	;Opakujících se bajtů smí být max.
	dec	b	;255, jinak počítadlo přeteče
VEN	ld	(hl),a	;Zapiš do komprimovaných dat toto opakování:
	dec	hl	;Co se opakuje
	inc	ix
	ld	(hl),b	;Kolikrát se to opakuje
	dec	hl
	ld	(hl),70	;První bajt návěští indikující opakování
	dec	hl
	ld	a,237	;Druhý bajt návěští indikující opakování
NEPAKUJ	ld	(hl),a	;Zapiš jeden neopakující se bajt
	dec	hl	;nebo druhý bajt indikace návěští
	dec	ix	;a sniž ukazatele paměti
	ld	a,hx	;Testuj, jestli už nejsi na konci (INT (23295/256)=90)
	cp	90
	jr	nz,KOMPRES	;Ne - komprimuj dál
	ret

Nejprve vstupní hodnoty - do registru HL se vloží adresa, od které dolů bude ležet komprimovaný kód (tj. 65535). Do registru IX se potom vloží adresa, od které dolů leží původní data (také 65535). Hodnota v registru IX musí být vždy menší nebo rovna hodnotě v HL, jinak by došlo ke kolizi. Komprimační rutina pracuje podobně jako instrukce LDDR odshora v paměti a postupuje k nižším adresám. To má tu výhodu, že zkomprimovaný blok o délce 38536 bajtů nebude ležet od adresy 23296 do adresy 61832 ale od 27000 do 65535. Při nahrávání se tedy nebude muset nahrávat třeba na adresu 26000, LDIRovat na adresu 23296 a následně dekomprimovat, ale nahraje se na adresu 27000 a dekomprimuje se z této adresy.
Z kompresní rutiny vychází velmi důležitá hodnota v registru HL (pozor, je o jedničku snížená) určující, kam až sahá komprimovaný kód. Jestliže tedy bude kód mezi 27000 až 65535, bude v registru HL hodnota 26999. Uložíte tedy kód od adresy HL+1 (tedy 27000) do 65535.
Kompresní rutina má ještě jedno úskalí. Testuje totiž překročení hranice adresy 23296 pouze při komprimaci jednoho bajtu, mohlo by se tedy stát, že bude-li na adrese 23295 stejná hodnota jako na adrese 23296, mohla by se přikomprimovat tato ke kódu a program by spadl. Je tedy nutné dát na adresu 23295 hodnotu o jedna nižší než hodnota z adresy 23296. Napište tedy před kompresní rutinu
ld a,(23296)
dec a
ld (23295),a
Hodnotu HL+1 (nyní 27000) potom dosadíte do této dekompresní rutiny:
UNPACK ld hl,První bajt komprimovaného kódu (hodnota HL+1 vyšlá z komprese) ld de,První bajt dekomprimovaného kódu (tady 23296) DALSI ld a,(hl) ;Přečti bajt komprimovaného kódu cp 237 ;Není to náhodou návěští opakujících se bajtů? jr nz,POSUN ;ne - odskoč inc hl ;Testuj i druhý bajt návěští ld a,(hl) dec hl cp 70 jr nz,POSUN inc hl inc hl ld c,(hl) ;Do registru BC ld b,0 ;počet opakování bajtu inc hl ZNOVU ldi ;Kopíruj bajt BC-krát dec hl jp pe,ZNOVU POSUN ldi ;Přesuň normální bajt nebo poslední opakovaný bajt ld a,h ;Opakuj do konce (nebudete-li or l ;mít komprimovaný kód až do 65535, jr nz,DALSI ;musíte test změnit) ret
Dekompresní rutina dekomprimuje paměť již od spodu nahoru (tj. od adresy HL+1 do 65535) - tedy způsobem LDIR (oproti kompresi způsobu LDDR).
Rutina je snad nejkratší, co se dala napsat a zabírá něco okolo 30 bajtů. Optimalizoval jsem ji dlouho (a krvavě...).
Až budete spouštět takto komprimovanou hru, dekompresní rutinu vložte do Video-RAM a nezapomeňte tam nastavit i zásobník a zakázat přerušení.
A nyní ještě něco o tom, jak dostat k dispozici celý blok od 23296 do 65535, kompresní rutinu ve VRAM a po komprimaci se ještě vrátit bezproblémově do Basicu, abychom si mohli zkomprimovaný kód uložit normálním příkazem SAVE.
Velmi se mi osvědčilo vložit v Basicu CLEAR 24200, nahrát DEVAST ACI II, poznamenat si adresu zásobníku (bude to nejspíše adresa 24177) a v DEVASTu II uložit část paměti od 23552 do adresy 24201 (pokud nemáte možnost použít DEVAST II, pak nějak přesuňte blok 23552-24201 třeba na adresu 50000 a tento pak uložte Basicovským SAVE). Potom do VRAM naprogramujete jednoduchý prográmek, který nahraje z pásku blok 23296,42240, zapakuje ho a provede LDIR uložené části Basicu z VRAM na adresu 23552. Celé to vypadá asi takto:

A16384	di
	ld	sp,20480
	ld	ix,23296
	ld	de,42240
	ld	a,255
	scf
	call	1366
	call	KOMPRES
	inc	hl
	ld	(20000),hl
	ld	hl,KONEC
	ld	de,23552
	ld	bc,650
	ldir
	ld	sp,24177
	ei
	ret
KOMPRES	ld	a,(23296)
	dec	a
	ld	(23295),a
	ld	hl,65535
	ld	ix,65535
	...
	jr	nz,KOMPRES
	ret
KONEC	defs	650	;zde přijde ona uložená paměť od adresy 23552 do adresy 24201

Až se vám vrátí program do Basicu, jednoduše napíšete PRINT PEEK 20000 + PEEK (20001) * 256 a od adresy, která se vám vypíše na obrazovku uložíte kód (pozor, ta hodnota, co se vypisuje na obrazovku, je už zvýšená o jedničku).
Na závěr bych snad už jen konstatoval, že rutina ušetří přibližně 2-3 kB ve 40 kB dlouhém bloku.