Tämän harjoituksen tavoitteet

Päätavoite:

• Tietämyksesi tietokoneen toiminnasta ja konekielestä syvenee.
• Saavutat työelämässä ja jatkokursseilla odotetun perustaitotason konekielen ymmärtämisessä. Esimerkiksi (OPS-kaudella 2017-2020) syventävän kurssin Kääntäjätekniikka alku on pehmeämpi, kun olet tehnyt hieman konekieltä käsipelillä. Samoin syventävän kurssin Ohjelmistoturvallisuus laajempi tekninen versio on sitä helpompi mitä enemmän konekielen toiminta on ehtinyt hahmottua. Sama pätee muihinkin laiteläheiseen ohjelmointiin liittyviin kursseihin ja työtehtäviin tulevaisuudessa.

Edelleen käytetään nykyaikaisia työkaluja, joita kurssilla on tähän asti käytetty. Tehdään AMD64 -prosessorin (ts. "x86-64") konekieltä GNU:n assemblersyntaksilla, jota on tähänkin asti nähty debuggerin tulosteissa. Ohjelma käännetään ja linkitetään komentoriviltä GNU:n työkaluilla Jyväskylän yliopiston suorakäyttökoneella (jalava tai halava), jossa sitä myös kokeillaan. Jotta työskentely olisi näppärää, screen-ohjelman, shellin ja tekstieditorin käyttö on hyvä olla hanskassa.

Johdanto

Valmistele hakemisto tätä demoa varten ja hae pieni koodipaketti seuraavin komennoin:

wget https://gitlab.jyu.fi/itka203-kurssimateriaali/itka203-kurssimateriaali-avoin/-/raw/master/2015/demot/mallikoodia/d06/d06_paketti.zip
unzip d06_paketti.zip

Tutki paketista avautunutta runkoa aiemmin opituilla keinoilla (mm. komennot ls, less, tekstieditori). Mukana on Makefile, joka automatisoi vaiheita. Seuraava komento kääntää ohjelman mallirungon:

make

Paketissa on mukana konekielisen aliohjelman tynkä useimmiten.s, johon sinun tulee tehdä rajapinnan ja dokumentaation mukainen toiminnallisuus. Muista kääntää ja kokeilla aina pienten muutosten jälkeen, ennen kuin koodi menee hallitsemattomaan tilaan liian monen muutoksen kautta!

Mitä tarvitsee toteuttaa

Aliohjelmallesi useimmiten() tulee ensimmäisenä parametrina tiedosto-osoitin ja toisena parametrina kokonaisluku, jonka C-kirjaston kutsu fgetc() palauttaa luettavan tiedoston loputtua. Aliohjelmasi tulee lukea C-alustakirjaston fgetc() -kutsua käyttäen kaikki syötetiedostosta tulevat tavut ja palauttaa tieto, mikä tavu syötteessä esiintyi useiten.

Huomioita:

• Hyväksytään, että rajoitutaan 8-bittisiin tavuihin syöttövirrassa. Se sattuu olemaan meidän esimerkkikäyttöjärjestelmässämme juuri näin. Esimerkiksi ääkköset menevät UTF-8 -merkistössä usean tavun yhdistelminä, mutta ei anneta sen nyt häiritä. Testaillaan esim. amerikan aakkosilla ja ASCIIssa määritellyillä erikoismerkeillä.
• Ilmeisesti täytyy yksi kerrallaan käydä läpi kaikki syötteen merkit. Aina seuraavan merkin saat kutsumalla kertaalleen standardia C-aliohjelmaa fgetc(). Katso dokumentaatio. Syöte on loppunut, jos fgetc() palauttaa EOF. Koska tämä EOF on käytännössä jokin C-kirjaston puolella määritelty kokonaisluku, niin nyt aliohjelmasi saa sen toisena parametrina, kuten voit pääohjelman koodista todeta. Voit siis nyt tunnistaa tiedoston päättymisen siitä, että fgetc() palautti saman luvun, jonka sait omaan aliohjelmaasi toisena parametrina.

Strategia ongelman ratkaisemiseksi yleisellä tasolla:

• Useiten esiintyvän tavun selvittämiseksi täytyy ilmeisesti laskea kaikkien syötteessä esiintyvien tavujen esiintymismäärät.
• Helppo tapa on käyttää taulukkoa 256 kokonaisluvusta, jotka ovat aluksi nollia. Suosittelemme, että varaat tällaiselle pikkutaulukolle tilaa aliohjelmasi pinokehyksestä. Muista nollata, koska pinossa on aluksi aiempien aliohjelma-aktivaatioiden "roskaa". Selkeintä voi olla käyttää 64-bittisiä kokonaislukuja, jollaisia esimerkiksi demossa 5 nähtiin.
• Sitten käyt läpi syötteen merkkejä, kunnes syötetiedosto loppuu. Jokaisen merkin kohdalla lisäät ykkösen vastaavaan alkioon taulukossa.
• Lopulta taulukossa on siis kaikkien tavujen 0,1,2,...,255 (heksana 0x0,0x1,..0xff) esiintymisten määrä syötteessä.
• Käyt sitten vielä läpi tulostaulukon ja etsit suurimman alkion indeksin. (Jos et sitten ylläpitänyt tietoa suurimman indeksistä jo samalla kun luit merkkejä ja summasit esiintymismääriä!)
• Asetat aliohjelmasi paluuarvoksi eniten esiintyneen tavun indeksin.

Tehtävä siis aikalailla Ohjelmointi 1 -tasoa. Nyt vaan tehdään se konekielellä.

Rajoituksia ja vapauksia:

• Tyyli on vapaa, kunhan ohjelmasi noudattaa x86-64:n SysV ABIa niin, että sitä voi kutsua C:stä ja että voit itse kutsua fgetc() -aliohjelmaa ilman ongelmia.
• Silmukkaindekseille ei ole pakko käyttää pinokehyksestä varattuja paikallisia muuttujia, vaan voit pitää indeksit sellaisissa rekistereissä, joita tarvitsemasi C-aliohjelmakutsu ei ABIn mukaan saa sotkea. Mutta sinunkin pitää olla sotkematta kyseisiä rekistereitä eli niiden arvon pitää olla samat aliohjelmasi alussa ja lopussa. Konekielikäskyt push ja pop sopivasti käytettynä auttavat tässä. Voit myös varata rekisterien alkuperäisille arvoille tilaa pinokehyksestäsi ja siirtää ne talteen movq -käskyllä.

Vinkkejä

Tehtävässä on yhdistettävä useita tiedonmurusia luentomonisteen alkupuolelta (noin sivut 1-84). Aiemmissa demoissa hankitut taidot komentorivistä, debuggerista ym. auttavat.

Perusvinkit:

• Muista kokeilla kääntää ja suorittaa ohjelmaa usein, niin syntaksivirheitä ei pääse kasautumaan.
• Kommentoi assembler-koodisi! Muuten on itsellekin tosi vaikea pysyä kärryillä, mitä koodi tekee, ja muille lukijoille se voi olla aivan mahdotonta.
• Kynä ja paperi auttaa hahmottelussa. Esimerkiksi pinokehyksen sisältö, missä osoitteessa on taulukko jne.
• Suoraan konekielellä on hyvin vaikea "ajatella" tehtävän ratkaisua. On varmasti helpompaa ensin rakennella toimiva ohjelma C:llä, Javalla, C#:lla, Pythonilla tai millä vaan muulla rakenteisella korkean tason kielellä. Vähintään on oltava suomenkielinen pseudokoodi.
• Kommentoi koodisi (joko se olisi sanottu riittävän monta kertaa?)

Joitain yksityiskohtia:

• Ohjelma lukee syötteen standardisyöttövirrasta. Komentoriviltä kokeillessa voit antaa merkit putkittamalla samoin kuin esimerkkinä annetussa Makefilessä tehdään:

  echo "aabbbba" | ./demo06
  

  Voit myös ohjata syötteeksi tiedoston seuraavasti:

  ./demo06 < joku_testitiedosto
  

  Voit myös näppäillä pienen testijonon suoraan päätteeltä. Huomaa silloin seuraavaa: Syöte alkaa mennä ohjelmalle vasta, kun painat rivinvaihtoa ja silloin mukaan tulee aina myös rivinvaihtomerkki. Syötteessä voi olla monta riviä. Saat lopetettua syötteen näppäilemällä Ctrl-d, josta ei tule enää mitään merkkiä, vaan tämän näppäilyn jälkeen fgetc() palauttaa EOF.

• Debuggeri on mittaamattoman arvokas työkalu tässäkin hommassa. Voit käynnistää shellistä näin:

  gdb demo06
  

  Gdb:ssä voit laittaa breakpointteja vaikkapa symbolisiin osoitteisiisi:

  break useimmiten
  

  tai:

  break lue_seuraava_merkki
  

  tai mitä symboleita nyt oletkaan käyttänyt ohjelmassasi!

  Huomaa edelleen, että debuggerissakin ohjelma lukee standardisyöttövirtaa (ks. edellinen vinkki). Debuggerissa voit ohjata ohjelmalle syötetiedoston käynnistämällä sen näin:

  run < tiedostonimi
  

  Voit tehdä omia "helppoja" testitiedostoja, niin voit askeltaa vaikka koko algoritmin läpi ja varmistua muistin sisällöstä kussakin vaiheessa.

  Vaihtoehtoisesti voit syöttää merkkejä näppäimistöltä tyyliin "abbacd" ja lopettaa syötteen näppäilemällä Ctrl-D. Debuggerissa tätä ei kokeilujeni perusteella ilmeisesti voi tehdä ennen kuin on näppäilty syötteeseen ensimmäinen rivinvaihto.

  Tässäkin tyyli on vapaa, mutta toiset tavat on näppärämpiä kuin toiset. Valitse itselle sopiva.

  Esim. tällainen tuloste voisi olla hyödyllinen, jos käyttäisit 64-bittisiä lukuja tavuesiintymien laskemisessa:

  x /256g $rsp
  

  Tuohan näyttäisi 256 "giant" eli 64-bittistä lukua alkaen pinon huippuosoitteesta. Havaittiin tämä hyödylliseksi ainakin mikroluokassa Open labrapäivässä 14.5.2018 (ja 21.5.2018 ja 28.5.2018)

• Merkin lukeminen tiedostosta tapahtuu kutsumalla C-aliohjelmaa fgetc(). Miten siis assemblerilla? Ihan vaan call-käskyllä seuraavasti:

  call fgetc     # Linkkeri osaa laittaa osoitteeksi C:n fgetc():n alun.
  

  Ennen kutsua on laitettava parametrit ABIn mukaisesti. Paluuarvo on ABIn määräämässä paikassa. Kaikki tämä näkyy myös demon 5 esimerkkialiohjelmassa.

• fgetc():n dokumentaatio esim. http://pubs.opengroup.org/onlinepubs/009695299/functions/fgetc.html - tiedoston loppumisen tunnistaa siitä, että palautuu EOF. Tämä on joku kokonaisluku, mutta meidän ei tartte nyt välittää sen varsinaisesta arvosta (joka sattuu olemaan GNU:n C-kirjastossa -1), koska C-kielinen pääohjelma antaa meidän aliohjelmalle toisena parametrina tämän luvun. Meidän lukusilmukka pitää siis lopettaa siinä vaiheessa, kun fgetc():n paluuarvona on sama kokonaisluku kuin meille annettu toinen parametri.

• Virallinen ABI löytyy esim. http://refspecs.linuxbase.org/elf/x86_64-SysV-psABI.pdf mutta luentomonisteessa on kiteytetty tähän tarpeeseen olennaisimmat kohdat poislukien seuraava:

  • ABI lupaa, että rekisterit RBX, R12, R13, R14 ja R15 eivät muutu aliohjelmakutsussa. Näitä voi siis käyttää paikallisina muuttujina. Muista dokumentoida, mitä aiot käyttää mihinkin tarkoitukseen.
  • Myöskään oma aliohjelmasi ei saa jättää mainittuja rekistereitä lopussa eri arvoon kuin missä ne aliohjelmaan tultaessa olivat. Kutsuja on voinut pitää niissä jotain tarpeellista dataansa. Voit siis esimerkiksi laittaa ne alussa pinoon talteen ja palauttaa lopussa. Pysy kartalla pinokehyksesi rakenteesta!

• Vertailukäskyn operandien järjestys on ainakin itselleni aina vaikea muistaa, ja pittää joka kerta kokeilla debuggerilla tai kaivaa netistä ohjeet. Tässä nyt esimerkki valmiina:

  cmp  %rax, %rbx  # Vertaa rekisterien %rax ja %rbx arvoja
  jg   osoite      # Hyppää, jos pätee %rbx > %rax
  

  Eli GNU-assemblerissa niin, että "jos jälkimmäinen on ehdon mukaisessa suhteessa ensimmäiseen, niin hyppy tapahtuu". Lisätietoa esim. https://en.wikibooks.org/wiki/X86_Assembly/Control_Flow

• Miten viitataan indeksin mukaiseen alkioon? Yksi mahdollinen peruskaava olisi:

  lea 16(%rsp), %rsi  # Taulukon alkuosoite olis vaikka RSP+16
                      # (omassa koodissasi riippuu tekemistäsi
                      # ratkaisuista tietysti)
  mov %rcx,%rdx       # Olisit vaikka päättänyt käyttä RCX:ää
                      # indeksinä (riippuu taas ratkaisuistasi)
  shl $3,%rdx         # Rakentaisit siirroksen 64-bittisten lukujen
                      # taulukkoon kertomalla indeksin 8:lla eli
                      # siirtämällä bittejä 3 pykälää vasemmalle
  addq %rdx,%rsi      # Lisäisit siirroksen alkuosoitteeseen
  cmpq $0,(%rsi)      # Tekisit, mitä tarvitsee, alkiolle joka on
                      # indeksin mukaisessa osoitteessa.
  

  Mutta tämä on vähän hankalaa.. On olemassa suorempikin tapa:

  addq $1, -2064(%rbp, %rax, 8)  # Kajoaa muistiosoitteeseen, joka löytyy
                                 # RAXin mukaisesta indeksistä 8 tavun
                                 # mittaisiin alkioihin, joista ensimmäinen
                                 # on osoitteessa RBP-2064.
                                 #
                                 # Varsin käyttökelpoinen esimerkiksi tässä
                                 # tavumäärien laskemisessa!!
  

• Huomaa, että samaa kaavaa voi käyttää muihinkin käskyihin kuin ykkösen lisäämiseen. Toinen esimerkki:

  movq $0, -2048(%rbp, %rax, 8)  # Sijoittaa 64-bittisen nollan
                                 # alkaen osoitteesta
                                 # RBP-2048+8*RAX
                                 #
                                 # Käyttökelpoinen taulukon nollaamisessa.
  

• Syntaksista lisää esim. https://en.wikibooks.org/wiki/X86_Assembly/GAS_Syntax

• Myös Google on ystävä näitä(kin) juttuja tehdessä. Kunhan pysähdyt miettimään, mitä kaikki tarkoittaa. Tarvitaan aina hallittu "copy-paste-modify". Suora copy-pastaus ilman ajatuksella tehtyä modify-vaihetta on tuhon tie!

Nyansseja

Tässä tapauksessa ohjelma toimisi (hieman "säkällä") vaikka käyttäisit kaikkeen kurssilla tähän asti nähtyjä 64-bittisiä kokonaislukuja. Jos tekee mieli olla vähemmän tuurin varassa, voit huomioida seuravaa:

• Toisena parametrina tuleva EOF on C-kielessä int -tyyppinen, ja Linuxin x86-64 -toteutuksessa se on 32-bittinen luku, ei siis 64-bittinen.
• Myös aliohjelman paluuarvo on vastaavasti 32-bittinen.
• Käytännössä siis EOFia käsittelevät koodin kohdat pitäisi tehdä 32-bittisillä käskyillä. Esimerkiksi siirtokäsky kirjoitetaan silloin movl eikä movq. Vertailu on vastaavasti cmpl. Rekistereistä tulee käyttää 32-bittistä puolikasta, esim. siis %esi ja %eax.
• Riippuen ympäröivästä koodista, voi olla tarpeen laittaa sopivaan paikkaan käsky cltq, joka laajentaa EAX-rekisterin sisällön koko RAXin laajuiseksi monistamalla etumerkkibittiä.
• Pinokehyksen tulee oikeasti olla tasattu 16:lla jaolliseen kokoon. Eli kehyksen luonnin jälkeen tai ainakin ennen minkään call -käskyn suorittamista RSP:n viimeinen heksanumero tulee olla 0. Näin on siis sovittu, vaikka tässä nimenomaisessa esimerkissä tasaamatta jättäminen ei näyttäisi aiheuttavan ongelmia.

Kuten sanottu, tässä tapauksessa ja tällä kurssilla on lupa luottaa "tuuriinkin".

Lisävinkkejä

Tämä lähestyy juonipaljastusta, mutta ei vielä ole aivan sellainen. Kerrataan pari edellä mainittua perusvinkkiä:

• Muista kokeilla kääntää ja suorittaa ohjelmaa usein, niin syntaksivirheitä ei pääse kasautumaan.
• Mieti ensin, mitä ohjelma tulee tekemään (kynä, paperi, testitoteutus korkean tason kielellä, jne..)
• Kommentoi koodi.

Huomattiin kevään 2018 aikana, että tehtävässä voi olla hankala keksiä, mistä lähdetään liikkeelle. Tässä on yksi suositeltu toimintakaava tähän tilanteeseen. Käytännössä tämä on vain yleinen ongelmanratkaisun kaanon sovellettuna tähän demoon:

1. Varmista, että pystyt kajoamaan koodiin työkaluillasi. Tee kokeeksi sellainen muutos, että aliohjelmasi palauttaa nollan sijasta vaikkapa luvun 123. Käännä ja suorita ohjelma varmistuen, että se tulostaa vastauksen olevan merkki 123, joka ASCIIn mukaisesti tulostettuna olisi avaava aaltosulku '{'.

2. Hae tilanteesta positiivinen fiilis: Olet tehnyt konekieliseen koodiin hallitun muutoksen. Kaikki on näpeissäsi. Koodi toimii, ja ymmärrät sen tämänhetkisen toiminnan täysin. Mielellään ei tule missään vaiheessa vastaan syytä poiketa tästä tilanteesta.

3. Havaitse, että ainakin pinokehyksen luominen ja vapauttaminen täytyy joka tapauksessa tapahtua. Samalla tavoin kuin demo 5:ssä nähtiin. Koodaa siis tarvittavat rivit aliohjelman alkuun ja loppuun. Käännä ja aja, kommentoi. Varmemmaksi vakuudeksi askella debuggerissa ja katso, että kehys syntyy ja tuhoutuu siten kuin demo 5:ssä nähtiin valmiiksi tehdyn esimerkin kanssa.

4. Tee ratkaisu oman pinokehyksen sisällöstä: Mihin kohtaan tulee taulukko, mihin kohtaan muu tarvittava. Suosituksena voisi olla, että varaat 8 tavua tilaa molemmille parametreille ja 256:lle kokonaisluvulle laskentaa varten. Muokkaa aliohjelman alkua vastaavasti ja dokumentoi valittu rakenne, eli missä kohtaa kehystä pidät mitäkin. Käännä ja aja. Askella debuggerissa, jos et muuten usko, että varaus on OK.

5. Laita koodi, joka tallentaa parametrit valitsemiisi paikkoihin. Käännä. Debuggaa tarvittaessa nähdäksesi, että parametrit menee varmasti talteen.

6. Havaitse, että aliohjelman alku ja loppu on kunnossa. Toiminnallisuus tulee seuraavaksi niiden väliin. Laita ennakoiva kommentti, mitä osioita luultavasti tulee.

7. Tee koodi, joka nollaa taulukon. Käännä. Varmistu debuggerilla (ks. vinkki yllä), että taulukossa on varmasti 256 kappaletta nollaa.

8. Tee koodi, joka kutsuu fgetc():tä, kunnes se palauttaa EOF. Älä vielä edes mieti muuta toiminnallisuutta. Pieni askel kerrallaan! Käännä, aja, debuggaa. Totea, että ohjelma jää odottamaan syötettä ja että silmukka pysähtyy tiedoston päättymisen kohdalla. Helposti voi tulla aluksi kaatuminen tai ikuinen silmukka. Syy on mahdollista selvittää, kun nyt työn alla on vain muutama käsky. Varmista, että fgetc():n parametrit ja paluuarvo menevät oikein. Muista, että fgetc()-kutsu saa sotkea suuren osan rekistereistä, mm. RAX, RCX, RDX, RDI, RSI... Olet jo varautunut tämän hoitamiseen edellisissä askeleissa. Jumppaa näitä muutamaa riviä, kunnes ohjelma näyttää varmuudella lukevan syötteestä kaikki merkit ja lopettavan lukemisen EOFiin.

9. Hae onnistumisen fiilis siitä, että olet homman puolivälissä ja ymmärrät koodisi täysin.

10. Lisää koodi, joka summaa merkin saapuessa ykkösen taulukkoon oikeaan kohtaan. Testaa debuggerissa helpolla syötteellä. Esim. aseta breakpoint lukusilmukkasi perään. Käynnistä. Näppäile "abbccc", rivinvaihto ja Ctrl-D. Oletettu tilanne pysähdyspisteessä on, että taulukossa on peräkkäiset luvut 1, 2 ja 3, koska merkit 'a', 'b', 'c' ovat ASCIIssa peräkkäin. Lisäksi pitäisi olla ykkönen rivinvaihtomerkin kohdalla (indeksi 10).

11. Vasta sitten, kun lukusilmukka on testattu, on toiveita saada seuraavat vaiheet maaliin. Varmistu siis vielä, että edellinen kohta on OK.

12. Lisää koodi, joka etsii taulukon suurimman alkion. Tämä on tulossa lukemisen jälkeen, joten enää ei tulla kutsumaan fgetc():tä tai muutakaan ulkopuolista aliohjelmaa, joten voit käyttää apumuuttujina rekistereitä RAX, RCX, RDX, RDI, RSI,... Esimerkiksi:

    • Tee valinta, mitä apumuuttujia tarvitset, ja dokumentoi kommenttiin.
    • Sitten silmukkarakenne eli taulukon läpikäynti toistaiseksi ilman toiminnallisuutta; varmista, ettei tullut syntaksivirheitä tai ikuista silmukkaa. Älä yritä liikaa kerralla.
    • Lopulta silmukan sisään logiikka, jolla löytyy isoimman alkion indeksi.
    • Jumppaa, kunnes toimii.

13. Varmista, että aliohjelmasi sijoittaa paluuarvon ABIn mukaisesti RAX-rekisteriin ennen paluuta kutsuvaan ohjelmaan. Viimeistään tässä vaiheessa luovut esimerkkirungossa olleesta käskystä, joka sijoitti paluuarvoksi "vain jotakin".

14. Testaa muutamalla erilaisella syötteellä.

15. Iloitse - olet nyt astunut assembler-koodaajien kerhoon! Muista myös palauttaa demo ja näyttää teoriaosaaminen tentissä, niin saat kurssista opintopisteet...

Juonipaljastuksia

Jos ei nämä vinkit vielä auttaneet, voit hätäpainikkeena klikata seuraavaa linkkiä, jossa on vielä superlisävinkkejä: http://users.jyu.fi/~nieminen/kj20/demovedokset/spoilereita_d06.html

Pakollinen palautustehtävä

Demo palautetaan samalla tavalla kuin aiemmatkin.

Tästä demosta palautetaan tasan yksi tiedosto nimeltään "useimmiten.s" jossa on yllä selitetyn tehtävänannon mukainen, toimiva assembler-aliohjelma.