RLE-pakkaus (10p)¶
Huom! Sivua päivitetään vielä tarpeen mukaan, joten tarkistakaa ohjeistus aika ajoin..
Kurssin tietokonetekniikan osuuden harjoitustyö on Run Length Encoding-pakkausalgoritmin (video) toteutus y86-64 assembly-kielellä. Harjoitustyö tehdään harjoitustehtävissä kuvatulla y86 assembly-kääntäjällä ja tarpeen mukaan simulaattoreilla.
Pakkausmenetelmä toimii lyhykäisyydessään seuraavasti:
- Käsitellään dataa (merkkijono, numeromuotoinen data) taulukosta.
- Käydään taulukon alkiot läpi yksi kerrallaan.
- Joka iteraatiolla verrataan alkiota (symbolia) edelliseen, ja lasketaan montako peräkkäistä symbolia on.
- Jos symboli vaihtuu, tallennetaan peräkkäisten symbolien määrä ja symboli (tässä järjestyksessä) muistiin.
- Palataan kohtaan 2, kunnes koko data on käsitelty.
- Lopetetaan ohjelma.
Esimerkkejä.
9 merkkiä merkkijonossa: AAAABBBCC Nyt datassa on 4 A:ta, 3 B:tä ja 2 C:tä, joka RLE-pakattuna: 4A3B2C Datassa 12 numeroa: 11166660333, joka RLE-pakattuna: 31461033 5 merkkiä merkkijonossa: JOULU Nyt datassa on 1 J, 1 O, 1 U, 1 L ja 1 U, joka RLE-pakattuna: 1J1O1U1L1U Nyt "pakkaus" pidensi merkkijonon pituutta :(
RLE-pakkausta on aikoinaan käytetty erityisesti bittikarttagrafiikan pakkaamiseen, joissa oli paljon samaa peräkkäistä pikseli-informaatiota, esimerkiksi taustaväri kuvan reunoilla. Bittikarttakuvissa värien määrä oli/on vähäinen, formaatista riippuen rajoitettu vaikkapa 16:sta. Joten symboleita ei kovin isoa määrää ole ja on odotettavissa, että kuvasta löytyy laajoja alueita samaa väriä. RLE-algoritmi ei myöskään ole laskennallisesti raskas.
Esimerkki. Arvatenkin smiley pakkautuu paremmin kuin kohinainen kuva..
Vaatimukset¶
Työssä tulee toteuttaa ylläkuvattu RLE-pakkaus algoritmi, jossa on seuraavat ominaisuudet:
- Ohjelmaa alkaa
main:
-kohkosta eikä sitä ennen ole mitään alustuksia - Parametrit ohjelmalle annetaan seuraavasti
- Data-arvot ovat 64-bittisiä
- Data luetaan muistista alkaen osoitteesta
0x1200
, data on tallennettu muistiin etukäteen.quad
-käskyn avulla. - Datan pituus annetaan rekisterissä
%r10
, maksimipituus on 256 arvoa. - RLE-pakattu data talletetaan pinoon ao. järjestyksessä niin, että jokainen pakattu symboli vie kaksi peräkkäistä muistipaikkaa. Pino alkaa osoitteesta
0x1000
. - muistipaikka: symbolien määrä
- muistipaikka: symboli
- Ohjelman lopuksi palautetaan
%rax
-rekisterissä prosenttilukuna tilan säästö (engl. data compression space saving):1-(pakattu koko / alkuperäinen koko)
- Esimerkki: datan koko 10 tavua ja pakattu koko 4 tavua, säästö: 1- (4 / 10) = 0.6 eli 60%
- Säästö voi olla myös negatiivinen, jos pakattu data on pidempi kuin alkuperäinen..
- Ohjelman suorituksen tulisi olla alle 10000 konekielen käskyä
Ohjelman alustus testausta varten voi olla esimerkiksi seuraavanlainen:
.pos 0x0 irmovq $10,%r10 main: # ... # ohjelmakoodi # ... .pos 0x1000 Pino: .pos 0x1200 .quad 0x01 .quad 0x01 .quad 0x02 .quad 0x02 .quad 0x03 .quad 0x03 .quad 0x04 .quad 0x05 .quad 0x05 .quad 0x05
Annetulla datalla pinon pitäisi ohjelman loputtua näyttää seuraavalta (komentorivisimulaattorin outputista):
Osoite: Data 0x0fb0: 0x0000000000000005 0x0fb8: 0x0000000000000003 0x0fc0: 0x0000000000000004 0x0fc8: 0x0000000000000001 0x0fd0: 0x0000000000000003 0x0fd8: 0x0000000000000002 0x0fe0: 0x0000000000000002 0x0fe8: 0x0000000000000002 0x0ff0: 0x0000000000000001 0x0ff8: 0x0000000000000002
Yleisiä ohjeita¶
- Harjoitustyö tehdään yksin
- Työstä saa toki keskustella muiden kanssa, mutta oma koodi on kirjoitettava itse
- Plagiointia koskevat samat säännöt kuin Johdatus-kurssin harjoitustyötä
- Koodin kommenteissa listatkaa muut, joiden kanssa olette keskustelleet tehtävästä, ettei tule plagiointiepäilyksiä samankaltaisten ratkaisujen johdosta
- Toisen opiskelijan koodia ei saa palauttaa omanaan
Ohjeita työhön¶
Assembly-kielellä koodaaminen on astetta vaativampaa kuin korkean tason kielillä, joten muutama yleisohje on paikallaan:
- Suunnittele ohjelma aluksi, ihan kuten tekisit ohjelmaa korkean tason kielellä
- try and error-tapa koodata assembly-kielellä ei enää yksinkertaisesti toimi..
- Rakenteellisen ohjelmoinnin-materiaalista on tässäkin hyötyä. Jaa ohjelma toiminnallisuuden mukaan osiksi, jotka voit toteuttaa erikseen aliohjelmina ja lopuksi yhdistää ne toimivaksi ohjelmaksi.
- Mitä aliohjelmia tarvitaan? Miten ne sijoitetaan muistissa hyppykäskyjen / ehtolauseiden minimoiseksi? Miten niiden parametrit välitetään?
- Onko tässä harjoitustehtävien koodista apua?
- Rekistereille kannattaa valita johdonmukaisesti käyttötarkoitus etukäteen (eikä siitä pidä poiketa)
- Tietyt rekisterit ovat vain globaaleille muuttujille
- Tietyt rekisterit ovat vain apumuuttujille
- Tietyt rekisterit ovat vain aliohjelmakutsujen parametreille (tarvitseeko käyttää pinoa?)
- Pinon käytöstä
- Pino kasvaa muistissa alaspäin, joten varmista ettei pino mene koodin päälle..
- Pinossa saa olla ylimääräistä tavaraa ohjelman loputtua, kunhan pinon pohjalla/alimpana/muistissa ylimpänä on aina pakkauksen lopputulos.
- Koodin tulee olla erittäin hyvin kommentoitua
- Tätä voi itse testata unohtamalla koodin muutamaksi päiväksi ja palaamalla siihen sitten..
- Omaa algoritmiä voi laskea paperilla tai toteuttaa C-kielellä, ja selvittää siitä mitä välituloksia assembly-koodin pitäisi saada
- Omaa koodia kannattaa (lue: pitää) testata simulaattorissa
- Aliohjelmien testaus erillisinä pieninä ohjelmina
- Ehtolauseet samoin ohjelmina. Testaa kaikilla erityyppisillä tuloksen arvoilla
<0, ==0, >0
- Hyppykäskyissä riittää usein pelkästään
ZF
-tilabitin tarkastelu, siis onko operaation tulos nolla tai erisuuri kuin nolla - Harjoituksista / mattermostista voi aina kysyä apua..
Työn palautus¶
Harjoitustyölle ja harjoitustehtäville takaraja on 31. Joulukuuta 2019. Huom! Ohjatut harjoitukset loppuvat jo torstaina 12.12.
Myöhässä palautetusta työstä/tehtävistä sakotetaan tämän kurssiosion arvosanassa -1, ellei ole henkilökunnan kanssa etukäteen sovittu myöhäisestä palautuksesta perustellusta syystä.
Palautettavan ohjelman tulee olla hyvin kommentoitu ja koodin tulee toimia, mutta siinä saa olla bugeja. Voi palauttaa koodia, joka ei mene 100% tarkistimesta läpi. Koodia, joka on alkutekijöissään ei kannata palauttaa suorituksena. Palautetusta koodista tulisi näkyä, että ratkaisua on oikeasti yritetty!
Lisäksi henkilökunta käy vielä palautetut koodit käsin läpi.
Arvostelu¶
Maksimi 10 pistettä koostuu seuraavasti:
- Vaatimusten mukainen toimiva y86-assemblyohjelma, jossa on noudatettu ohjeita: 8p
- Tarkastuksessa löydetyt bugit / puuttuva vaatimus/ominaisuus: vähennetään 1-2p per bugi/vaatimus/ominaisuus
- Koodin kommentointi: 0-2p
Kurssiarvosana¶
Seuraava koskee tätä 3op:n osuutta.
- Harjoitustehtävistä saa max 20p
- Harjoitustyöstä saa max 10p
- Hyväksyttyyn kurssisuoritukseen pisteitä vaaditaan 50% harjoitustehtävien ja harjoitustyön yhteenlasketusta maksimista eli 15 / 30p
- Suorituksia tulee olla molemmista: sekä harjoitustehtäviä että lopputyö.
Koko kurssin Tietokonejärjestelmät (8op) arvosana tulee etusivulla kerrotun mukaisesti.
Kurssipalaute¶
Pyydämme palautetta tästä kurssiosuudesta joko allaolevaan boksiin tai yliopiston virallisille palautesivuille palaute.oulu.fi.
Anna palautetta
Kommentteja tehtävästä?