Komprimacia "dva bajty - cislo"

   V niekolkych predoslych lekciach sme si ukazali ako sa daju robit rozne komprimacne a dekomprimacne rutinky. Vsetky tieto rutinky mali jednu spolocnu vlastnost - ako informaciu identifikujucu pocet skomprimovanych bajtov pouzivali jeden specialne urceny bajt, odborne nazvany "znackovy bajt".

   Komprimacia pouzivajuca znackovy bajt ma dve urcite nevyhody. Prva spociva v tom ze do skomprimovaneho bloku treba namiesto kazdeho samostatneho znackoveho bajtu v zdrojovom bloku ulozit informaciu identifikujucu pocet, potom ten pocet (v nasom pripade to bude 1) a na koniec samotny bajt. Ak sa taketo znackove bajty vyskytuju v zdrojovom bloku prilis casto, potom sa dlzka skomprimovaneho bloku znacne natahuje. Da sa tomu odpomoct tak, ze este pred zacatim komprimacie spocitame jednotlive vyskyty bajtov - kolkokrat sa ktory bajt nachadza v zdrojovom bloku a ako znackovy bajt vyberieme ten, ktory sa vyskytuje najmenej casto.

   A prave v tom spociva druha nevyhoda - potrebujeme pred komprimaciou poznat tento bajt. Pokial mame cely zdrojovy blok naraz v pameti, nie je problem bajty spocitat. Lenze nie vzdy mozme mat cely neskomprimovany blok v pameti k dispozicii. Typickym prikladom su magnetofonove kopirovacie programy s komprimaciou na ZX Spektre alebo inych pocitacoch. Na zaciatku loadovania bloku do pameti este nevieme aky bude dlhy a ci sa nam cely zmesti do pameti, preto musime blok komprimovat priebezne ako nam prichadzaju bajty z pasky. Lenze na zaciatku tiez nevieme, ktory bajt sa bude v bloku vyskytovat najmenej aby by sme ho mohli pouzit ako znackovy.

   Jednym z moznych rieseni tohto problemu je ako informaciu identifikujucu pocet pouzit namiesto konkretnej hodnoty dakeho bajtu dva za sebou iduce rovnake bajty. Komprimacna rutinka bude potom pracovat tak, ze bude postupne ukladat zo zdrojoveho neskomprimovaneho bloku bajty do skomprimovaneho cieloveho bloku. Akonahle ulozi dva za sebou iduce rovnake bajty, bude predpokladat ze za tymito dvomi bajtami sa este nachadza viac bajtov s takouto hodnotou a preto ich uz nebude ukladat ale ich spocita a az ich pocet ulozi do skomprimovaneho bloku. Dekomprimacna rutinka bude pracovat podobne - bude bajty presuvat zo skomprimovaneho bloku do neskomprimovaneho, ale ak ulozi dva za sebou iduce rovnake bajty, bude predpokladat ze dalsi bajt vyjadruje pocet kolko este bude tychto bajtov.

   V komprimacnej rutinke treba osetrit dva krajne pripady. V prvom pripade moze nastat taka situacia ze v zdrojovom bloku sa nadchadzaju za sebou rovnake bajty iba dva. Pocet nasledujucich bajtov rovnakych ako tie dva je tym padom nulovy. Preto musi komprimacna rutinka vediet osetrit tento pripad. Druhy pripad ktory treba osetrit nastane vtedy, ak pocet bajtov rovnakych ako tie dva presahuje cislo zobrazitelne v jednom bajte (255). Vtedy bude rozumne, ak do skomprimovaneho bloku zapiseme ako pocet cislo 255 a na bajte, ktory sme uz nezaratali do tohto poctu spustime cely komprimacny algoritmus od zaciatku.

   Maly priklad na ozrejmenie: Ak sa v povodnom bloku bude nachadzat nieco taketo:

77 22 22 55 88 88 88 ...(400 bajtov 88)... 88 88 88 66

   potom sa vo vysledom skomprimovanom bloku budu nadchadzat taketo bajty:

77 22 22 0 55 88 88 255 88 88 141 66

   Hodnota 0 tu teraz teda neznamena 256 ako v minulej rutinke, ale skutocnu nulu. S tym musime pocitat pri tvorbe dekomprimacnej rutinky.

   Komprimacna rutinka 
 ld hl,#4000 zaciatocna adresa bloku 
 ld de,#8000 kam ukladat skomprimovany blok 
 ld bc,#1b00 dlzka bloku 
rec ld a,(hl) vezmeme prvy bajt (na porovnanie) 
 ldi  prenesieme ho do skomprimovaneho bloku 
 ret po ak sme uz preniesli vsetko, navrat 
nekom cp (hl) porovname ci bajt je taky isty ako predosly 
 ld a,(hl) vezmeme bajt (kvoli porovnavaniu s dalsim) 
 ldi  prenesieme ho do skomprimovaneho bloku 
 ret po ak sme uz preniesli vsetko, navrat 
 jr nz,nekom ak boli bajty nerovnake, ostavame v slucke 
 ld xh,#00 inicializacia pocitadla rovnakych bajtov 
komzac cpi  nasleduje este taky isty bajt ? 
 jr nz,komend ak nie tak koniec ratania rovnakych bajtov 
 jp po,komstp ak sme uz vycerpali cely blok, koniec 
 inc xh zvecsenie pocitadla rovnakych bajtov 
 jr nz,komzac ak este nepretieklo, pocitame dalej v slucke 
 dec xh korekcie hodnot v pripade pretecenia 
 dec hl  
 inc bc  
komend call komstp ulozenie stavu pocitadla do skompr. bloku 
 jr rec a pokracujeme znovu od zaciatku 
komstp ld a,xh podprogram na ulozenie stavu 
 ld (de),a pocitadla do vysledneho 
 inc de skomprimovaneho bloku 
 ret   
    
   Dekomprimacna rutinka 
 ld hl,#8000 kde je ulozeny skomprimovany blok 
 ld de,#4000 zaciatocna adresa bloku 
 ld bc,#1b00 dlzka neskomprimovaneho bloku 
play ld a,(hl) vezmeme prvy bajt (na porovnanie) 
 ldi  prenesieme ho do dekomprimovaneho bloku 
 ret po ak sme uz preniesli vsetko, navrat 
nedek cp (hl) porovname ci bajt je taky isty ako predosly 
 ld a,(hl) vezmeme bajt (kvoli porovnavaniu s dalsim 
 ldi  prenesieme ho do dekomprimovaneho bloku 
 ret po ak sme uz preniesli vsetko, navrat 
 jr nz,nedek ak boli bajty nerovnake, ostavame v slucke 
 ld a,(hl) vezmeme hodnotu pocitadla rovnakych bajtov 
dekom inc hl ukazovatel na dalsi bajt 
 or je pocitadlo nulove ? 
 jr z,play ak ano tak koniec ukladania rovnakych bajtov 
 dec hl ukazovatel presunieme na ten bajt 
 dec hl ktory sa v bloku nachadzal viackrat 
 ldi  presunieme tento bajt do dekompr. bloku 
 ret po ak sme uz preniesli vsetky tak navrat 
 dec zmensenie pocitadla 
 jr dekom a pokracujeme v ukladani bajtu 

   Na domacu ulohu skuste prist na jeden malicky nedostatok komprimacnej metody, ktoru pouzivaju tieto nase rutinky. Tento nedostatok sme si uz v tejto lekcii tak nenapadne a nepriamo spomenuli, takze by to nemal byt pre vas prilis velky problem.

Vas Busy.

Nazad / back , predchadzajuca a dalsia lekcia