pondělí 22. července 1996

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.

1 komentář:

  1. In Roulette, the objective is to predict where precisely the ball will land on the wheel. There are three primary Roulettes variants obtainable; French, European, and American Roulette. However, there are many of|there are numerous} different variations yow will discover at a web-based on line casino. The bonuses at Las Atlantis online on line casino are pretty profitable, with new players getting a 280% deposit bonus for 5 deposits. This casino’s underwater theme is probably the best considered one of 카지노사이트 all online roulette casinos on this article, and it really works} amazingly on each desktop computer systems and cellular gadgets.

    OdpovědětVymazat