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 | a | 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 | a | 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.