Jednoducha komprimacia

   V minulych lekciach sme sa pomerne dlhy cas zaoberali roznymi matematickymi operaciami a prepoctami. Naucili sme sa nasobit, delit, odmocnovat, ukazali sme si ako treba spracuvat desiatkove a sestnastkove cisla.

   Avsak tentoraz celkom zmenime temu. V dnesnej lekcii (a v niekolkych nasledujucich) sa budeme zaoberat rutinkami, ktore su velmi uzitocne a preto v praxi velmi pouzivane. Rutinky tohto typu su uz standartnou vybavou vsetkych serioznych finalnych programov. Su to komprimacne a dekomprimacne rutinky.

   Predstavme si, ze mate v pameti pocitaca nejaky program. Tento program sa sklada z niekolkych samostatnych casti. Medzi tymito castami je prazdny priestor - presnejsie povedane - su tam bajty v ktorych sa nachadzaju same nuly. Alebo sa v tomto programe nachadzaju nejake rozsiahle bloky dat, pricom tieto data su "riedke" - to znamena ze sa v nich nachadza velmi vela takychto prazdnych oblasti.

   Teraz si tento program ulozime na nejake zaznamove mediu (kazeta, disketa, harddisk, streamer...). Tym sme dosiahli to, ze cast zaznamoveho media si pameta iba tie nuly. Teraz si predstavme, ze na medium namiesto useku nulovych bajtov ulozime iba pocet kolko ma byt tych nul a nejaku informaciu, ktorou zabezpecime aby sme neskor vedeli tento pocet identifikovat (odlisit od samotnych dat programu). Tym padom dosiahneme to, ze na priestore pametoveho media, kde sa nam predtym zmestili iba dva programy, sa nam teraz zmestia napr. tri take programy. No nie je to perfektne ? Tato cinnost sa odborne nazyva komprimacia (alebo tiez pakovanie).

   Kedze komprimovat priamo pri ukladani programu na pametove medium je znacne narocne a procesor by to uz nemusel stihnut, zvykne sa to v praxi robit tak, ze sa tento program skomprimuje najprv v pameti a takto vopred skomprimovany program sa ulozi na pametove medium. Skusme teda vymysliet rutinku, ktora vezme nejaky usek pameti, skomprimuje ho a takto skomprimovany ho ulozi zase na ine miesto v pameti.

   Ked sa nad tym trosku zamyslime, tak prideme na to, ze ono je to vlasne cinnost podobna ako robi instrukcia LDIR, samozrejme len s tym rozdielom, ze LDIR nekomprimuje. Zaujimave je na tom prave to, ze nasa rutinka potrebuje na vstupe presne tie iste informacie ako uz spominany LDIR - t.j. adresu a dlzku daneho useku v pameti a adresu, kam ma ulozit tento usek skoprimovany.

   Ak nasa rutina potrebuje na vstupe tie iste informacie ako LDIR tak si pre jednoduchost zvolme, ze jej tie informacie budeme davat v tych istych registroch ako pre LDIR - t.j. HL bude adresa daneho useku, v BC jeho dlzka a v DE bude adresa miesta, kam sa ma ulozit skomprimovany usek pameti. Tymto padom si vytvorime akysi inteligentny LDIR, ktory sa navonok od normalneho bude lisit iba tym, ze bude komprimovat.

   No a teraz podme k samotnej komprimacii. Ako informaciu pomocou ktorej sa identifikuje pocet je v nasom pripade najvhodnejsie pouzit priamo ten bajt, ktoreho sa tyka tento pocet. Cize bude to nula. Pri komprimacii teda budeme nenulove bajty kopirovat ako klasicky LDIR, ale ako nahle nadabime na nejake nuly, do vysledneho skomprimovaneho useku ulozime iba jednu nulu (to je ta informacia identifikujuca pocet) a potom pocet kolko nul sa to vlastne nachadzalo v povodnom useku. Pocet si pre jednoduchost zvolme jednobajtovy. To nam dava moznost vyjadrit hodnoty z intervalu 0-255. Kedze vsak hodnotu 0 nebudeme potrebovat (predsa nebudeme do vysledneho useku ukladat informaciu ze v povodnom bolo nula nul!) tak si povedzme ze hodnota 0 bude znamenat pocet 256 nul.

   Ale co ak sa nahodnou v useku pameti vyskytne za sebou viac ako 256 nul a jednobajtove pocitadlo nam nebude stacit ? Aj tento pripad musime osetrit. Zvykne sa to robit tak, ze po 256. nule sa napise do skomprimovaneho bloku zaznam o tom, ze nul bolo 256 a nuly v povodnom useku sa zacnu zase pocitat odznovu. Teda ak bolo v povodnom useku napr. 258 nul, do skoprimovaneho useku sa zapisu tieto styri bajty: 0,256,0,2.

   No a po tychto teoretickych zakladoch mozeme priamo prikrocit k samotnej rutinke. Na zaciatku rutinky su ako ukazkovy priklad do registrov HL,DE,BC vlozene hodnoty ktore predstavuju pixlovu cast videoramky (prave tu sa zvykne vyskytovat velmi vela nul) na pocitaci ZX Spektrum. Teda s tymito ukazkovymi hodnotami tato rutinka skomprimuje obsah videopamete a ulozi ho na adresu #8000.

pack ld hl,#4000 priklad adresy povodneho useku 
 ld de,#8000 priklad adresy volneho miesta 
 ld bc,#1800 priklad dlzky povodneho useku 
komlop ld a,(hl) vezme bajt z povodneho useku 
 ldi  skopiruje ho do noveho useku 
 or je to nula ? 
 jr z,kompck ak ano tak odchod na spocitanie nul 
komend ld a,b inak - spracovali sme uz cely usek ? 
 or (kontrola nuly v BC) 
 jr nz,komlop ak nie tak spracovanie dalsieho bajtu 
 ret  ak ano tak navrat z rutinky 
kompck ld xh,a inicializacia pocitadla nul 
komnul inc xh zvecsenie pocitadla po jednej nule 
 jr z,komset ak nam pocitadlo pretieklo tak koniec 
 ld a,b ak sme nahodou 
 or narazili na koniec povodneho useku 
 jr z,komset tak tiez koniec 
 ld a,(hl) je tu este jedna nula ? 
 inc hl korekcia ukazovatelov 
 dec bc na povodny usek 
 or ak tu este je jedna nula 
 jr z,komnul tak skok v slucke pocitania nul 
 dec hl inak vratenie ukazovatelov 
 inc bc (lebo sme uz dosli na nenulovy bajt) 
komset ld a,xh koniec pocitania nul 
 ld (de),a zapis poctu nul 
 inc de a nasledne zvysenie ukazovatela 
 jr komend skok na test ci sme uz spracovali cely povodny usek 

   Na domacu ulohu skuste porozmyslat, ako by sa dal z takto skomprimovaneho useku ziskat znovu ten nas povodny usek pameti.

Vas Busy.

Nazad / back , predchadzajuca a dalsia lekcia