Oblig 2
Assemblerprogrammering p? Raspberry Pi
H?st 2018.
Assemblerprogrammering
Assembler er den laveste (med noen unntak) m?ten ? programmere en CPU
. Programmeringsspr?ket er en menneskeleselig versjon av instruksjonene som maskinvaren faktisk utf?rer. Assembler er spesifikt til prosessoren det kj?rer p? til sammenligning med h?yere niv? spr?k, som C
, Rust
eller Python
, som enten m? oversettes til Assembler eller tolkes under kj?ring. I dette faget skal vi jobbe med ARM Assembler p? Raspberry Pi (RPi
fra n? av) beskrevet i kapittel 6.3
.
Raspberry Pi (ARMv7
)
Som beskrevet over skal vi i denne obligen se p? Assemblerprogrammering p? Raspberry Pi 3 Model B+
(RPi
). For ? vite hvilken utgave, og hvilke egenskaper, av ARM Assembler vi skal bruke m? vi vite en ting. Hvilken prosessorarkitektur bruker RPi
? For ? finne ut av dette kan vi starte med ? se p? mikroprosessoren som RPi
bruker. I v?r modell finner vi en BCM2837B0
, som ikke sier oss s? mye. Ved help av internettet s? kan vi f? vite at denne prosessoren best?r av fire ARM Cortex-A53 kjerner som st?tter ARMv8
som arkitektur. Er dette nok? Nei, dessverre ikke, ARMv8
er den nyeste arkitekturen til ARM, men ikke all programvare er oppdatert for ? st?tte denne versjonen enda. Heldigvis st?tter prosessoren v?r ogs? ARMv7
som har eksistert i en stund. For ? finne ut hvilken versjon vi skal bruke m? vi sp?rre operativsystemet v?rt hvilken versjon den benytter. Dette kan gj?res ved ? kalle f?lgende
Dette forteller oss at v?r versjon av Raspbian
st?tter ARMv7
Assembler. I boken omtales ARMv4
som for alle form?l med denne obligen vil v?re likt som ARMv7
.
Oppgave
Assemblerprogrammering er noe man sjeldent kommer borti i dagliglivet som programmerer. Allikevel finnes det gode grunner for ? kunne skrive og lese Assembler. For mange mikroprosessorer trenger man Assemblerprogrammering for ? kunne utnytte seg av alle egenskaper som eksisterer, men selv om man ikke skal jobbe med sm? 8-bitters prosessorer kan det v?re kjekt ? vite hva programmet ditt gj?r n?r den kj?rer p? en b?rbar datamaskin eller en stor server.
I denne obligen skal vi implementere noen enkle algoritmer i Assembler p? nettopp RPi
. Dette vil gi en innf?ring i hvordan enkle byggeblokker kan kombineres for ? skape funksjonalitet samtidig som vi skal se kjente elementer og hvordan disse fungerer p? det laveste niv?et.
F?rste del av obligen vil veilede gjennom implantasjonen av Fibonacci sekvensen i Assembler. I andre del skal vi utvide denne koden slik at vi f?r se hvordan en h?yere niv? metode (eller funksjon) kan implementeres. F?r vi sier oss helt ferdig med Fibonacci skal vi ta et skritt tilbake og se hvordan en kompilator kan gj?re jobben enklere ved ? oversette et h?yere niv? spr?k til lav niv? Assembler.
I siste del av denne obligen skal vi se hvordan moderne datamaskiner representerer flyttall og hvordan man kan legge sammen slike tall. Selv om dette er st?ttet i prosessoren vil det v?re en fin ?velse for ? jobbe med bin?rtall og l?re mer om lav niv? programmering.
Oppgaven skal leveres som én PDF-fil med innholdet som er spesifisert i hver del under. For programmeringsoppgavene kan kildekoden legges ved som egene filer.
N?dvendig programvare
For ? enklere kunne forst? hva som skjer i koden under kj?ring vil vi i denne obligen benytte oss av en avluser
(debugger
p? engelsk). P? RPi
er det p? forh?nd installert et program som heter GDB
som kan hjelpe oss med nettopp dette. Dessverre s? er brukergrensesnittet til GDB
ikke av de enkleste s? for ? hjelpe til litt vil vi benytte oss av et tredjeparts program, gdbgui
, for ? f? et enklere brukergrensesnitt.
For ? installere gdbgui
kan man kj?re f?lgende kommando i et terminalvindu
Merk at man m? v?re koblet til internett for at dette skal fungere.
En rask innf?ring i bruk av gdbgui
finnes her.
Del 1:
Det f?rste vi skal implementere i denne obligen er en algoritme for ? beregne det N
-te Fibonacci tallet. Vi kommer til ? begrense oss til positive heltall og null for N
. Nedenfor har vi gjengitt de fem f?rste tallene i rekken.
N = 0 |
N = 1 |
N = 2 |
N = 3 |
N = 4 |
---|---|---|---|---|
0 | 1 | 1 | 2 | 3 |
Denne rekken er beskrevet av rekurensen F(N) = F(N - 1) + F(N - 2)
med grunnstegene F(0) = 0
og F(1) = 1
.
For ? komme i gang har vi under gitt et skjelett av oppgaven som du trenger ? fylle ut med utregningen din.
.text
.global main
@ Main function of program
main:
@ First load the desired Fibonacci number
MOV r0, #13
@ Initialize the first two numbers in the sequence
MOV r1, #1
MOV r2, #0
@ Loop will do the main work calculating the Fibonacci sequence
loop:
@ ! Implement your logic here !
@ Jump to start off loop
B loop
@ To be a good citizen we branch (and exchange) on the lr register
@ to return to the caller
exit:
BX lr
I programmet over har vi gjort et par ting for ? hjelpe deg med ? komme i gang. For ? starte s? plasserer vi verdien 13
i register 0
(r0
), dette indikerer at vi ?nsker ? beregne Fibonacci tallet for N = 13
. Vi har s? initialisert to registre med de f?rste tallene som du trenger for ? beregne det endelige Fibonacci tallet.
Oppgaven din blir ? fyllet ut algoritmen og se til at resultatet plasseres i register 0
(r0
). Husk at du kan endre initialiseringen av r0
for ? teste forskjellige verdier av N
(dette kan hjelpe for ? overbevise deg selv at oppgaven er l?st riktig).
Kompilere koden
Lagre koden over i en fil med navnet part1.s
. For ? kunne kompilere og kj?re koden din trenger vi ? benytte oss av en kompilator som kan transformere kildekoden til en kj?rbar fil for din RPi
. Den f?lgende kommandoen vil kompilere kildekoden slik at vi enkelt kan kj?re den.
Kj?r programmet ved hjelp av gdbgui
med f?lgende kommando
En rask innf?ring i gdbgui
finnes her.
Innlevering:
- Kildekode til Fibonacci algorithmen i Assembler
Del 2:
En viktig inndelingene i mange programmeringsspr?k er “funksjoner”, en m?te ? dele opp kode og lage mindre blokker med separert logikk. Du har helt sikkert laget flere funksjoner i andre programmeringsspr?k, men n? skal vi se hvordan dette fungerer p? det laveste niv?et.
I denne oppgaven skal vi utvidet Fibonacci algoritmen fra forrige del til ? bli en egen funksjon som vi kan benytte. For ? passe p? at funksjoner kan “snakke sammen” er det viktig at alle er enige om hvordan registrene p? CPU
-en skal brukes. Dette kalles funksjonskallkonvensjonen
(calling convention
p? engelsk) og er beskrevet i kapittel 6.3.7
.
Lag en ny kildekode fil med navnet part2.s
, fyll inn skjelettet under og implementer en funksjon som heter fib
. Funksjonen skal ta inn et argument, det ?nskede Fibonacci tallet N
, og returnerer et tall, det beregnede svaret. I main
skal fib
funksjonen kalles p? for ? deretter skrives ut med printf
.
printf
kan kalles p? som alle andre funksjoner i Assembler. For v?re form?l vil vi behandle den som en funksjon som tar inn to argumenter, v?r formateringsstreng og tallet vi ?nsker ? bruke.
.text
.global main
main:
BX lr
@ The 'data' section contains static data for our program
.data
output_string:
.asciz "%d\n"
Formateringsstrengen kan lastes inn ved hjelp av LDR
og =output_string
.
Vi vil i motsetning til boken anbefale at du bruker BX
for ? returnere fra et funksjonskall, men begge metoder godtas under innlevering.
Kompilere koden
Som i forrige deloppgave s? kompileres programmet ditt ved ? kj?re f?lgende
Bruk gdbgui
for ? teste programmet ditt. N?r du er ferdig pr?v ? kj?r programmet uten gdbgui
ved ? kalle p? programmet ditt i en terminal (./part2
).
Tekstoppgaver
- Hvem er det som har ansvar for registrene, og hvilke registre, n?r det kalles en funksjon under ARM funksjonskallkonvensjon?
- Hva skjer med input argumentet til
fib
funksjonen etter atfib
returnerer? - Hvilken endring m?tte du gj?re fra
Del 1
slik at programmet avsluttes riktig og hvorfor m?tte dette gj?res?
Innlevering:
- Kildekode med oppdatert Fibonacci algorithme i Assembler
- Svar p? tekstoppgaver
Del 3:
Det er kanskje ikke s? mange tilfeller hvor man f?r bruk for ? skrive ren Assembler kode i hverdagen, men en viktig ting er ? kunne forst? Assembler koden som h?yere niv? programmeringsspr?k produserer. Dette kan v?re seg for ? finne feil eller for ? kunne oppdage bedre m?ter ? utnytte CPU
ressursene v?re. I denne oppgaven skal vi se litt p? hvordan GCC
oversetter C
til Assembler instruksjoner og motiver bruken av kompilatorer.
Oversett Assembler koden fra Del 2
til h?yere niv? C
kode. Kildekoden din burde best? av to metoder, int fib(unsigned int);
og main
, samt en enkel importering av <stdio.h>
for ? f? tilgang til printf
. Som i forrige oppgave skal main
kalle p? fib
for ? deretter skrive ut tallet med printf
.
Kompilere koden
Som i forrige deloppgave s? kompileres programmet ditt ved ? kj?re f?lgende
Bruk gdbgui
for ? teste programmet ditt. N?r du er ferdig pr?v ? kj?r programmet uten gdbgui
ved ? kalle p? programmet ditt i en terminal (./part3
).
Tekstoppgaver
For ? unders?ke hva kompilatoren gj?r med kildekoden v?r trenger vi ? stoppe kompilatoren f?r den gj?r om kildekoden til maskinkode. Dette kan gj?res ved ? sende inn et flag, -S
. Kj?r f?lgende kommando og unders?k den produserte Assembler koden for ? svare p? sp?rsm?lene under.
Legg merke til at vi har fjernet -g
og lagt til -Os
. For denne oppgaven s? trenger vi ikke avluserinformasjon (debug information
) som kan lage mye st?y i den produserte Assembler koden. -Os
forteller kompilatoren at vi ?nsker ? optimere for st?rrelse noe som burde gi en enklere ? tolke Assembler kode.
- Unders?k den produserte Assembler koden og sammenlign med din egen kildekode fra
Del 2
, er det noen store forskjeller mellom det du lagde og detGCC
produserer? - Endre
-Os
til-O2
, hvordan p?virker dette den produserte koden? Pr?v ? endre til-O3
, ser du noen forandring n?? - Hvilke argumenter er det for og i mot ? bruke en kompilator sammenlignet med ? skrive Assembler? Tenk spesielt p? hvor mye jobb det ville v?re ? oversette programsnuttene i
Del 1, 2 og 3
til en annen prosessorarkitektur.
Innlevering:
- Kildekode til Fibonacci algorithmen i
C
- Svar p? tekstoppgaver
Flyttall (IEEE 754
)
Flyttall, mer spesifikt IEEE 754
32-biter flyttall (beskrevet i kapittel 5.3.2
), er en m?te ? representere desimaltall for datamaskinen. IEEE 754
beskriver standarden som s? godt som alle prosessorarkitekturer st?tter for hvordan flyttall skal operere, noe som gj?r at det er forutsigbart hva som skjer n?r vi jobber med desimaltall p? forskjellige maskiner. Grunnen til at vi trenger en standard er samme grunn som forskjellen mellom 1/3
og 0.333...
beskriver samme tall. 1/3
beskriver helt presist et tall, mens 0.333...
pr?ver ? beskrive samme tall, men trenger “uendelig” med desimaler for ? kunne representere det samme tallet. Det samme er det for datamaskinen, n?r den pr?ver ? representere 1/3
m? den konvertere til bin?r, noe som er fint om vi er enige om (derav standard), samtidig som operasjoner p? dette tallet m? v?re definert.
Som et eksempel kan vi tenke p? 1/10
, i titallsystemet kan dette tallet representeres n?yaktig som 0.1
, mens for flyttall kan ikke dette tallet representeres n?yaktig og vi f?r 0.10000000000000001
. Med store utregninger og mange tall kan slike “sm?feil” fort summere til store tall. Det er derfor viktig at man kjenner til styrkene og svakhetene til flyttall slik at man ikke ender opp med feil.
I bildet under kan du se hvordan IEEE 754
32-biter flyttall er representert.
![IEEE 754 flyttall](/studier/emner/matnat/ifi/IN2060/h18/obligatoriske-oppgaver/oblig2_bilder/float_example.png)
IEEE 754
flyttallEt flyttall best?r av et fortegn (sign
p? bildet), eksponent (exponent
) og en desimal (fraction
). Tallet representerer s? desimaltall ved hjelp av vitenskapelig notasjon, men isteden for ? bruke 10
som grunntall brukes 2
.
For ? representere 228
som flyttall (ikke IEEE 754
) konverterer vi tallet f?rst til bin?r, 228 = 11100100
, deretter konverterer vi til vitenskapelig notasjon 11100100 = 1.11001 x 2^7
, 111001
kan s? plasseres i desimalen, mens 7
kan plasseres i eksponenten. IEEE 754
g?r litt lengre for ? f? litt mer ut av bitene, men det er best forklart i boken (legg merke til biasert eksponent og utnyttelse av desimalen).
Del 4:
F?r vi implementerer en algoritme for ? legge sammen flyttall trenger vi litt oppvarming i flyttallsregning. Gj?r f?lgende oppgaver for h?nd og vis fremgangsm?ten din.
- Oversett
2.0
tilIEEE 754
32-biter flyttall. - Oversett
3.0
tilIEEE 754
32-biter flyttall. - Oversett
0.50390625
tilIEEE 754
32-biter flyttall. - Legg sammen tallene
2.0
og0.50390625
med samme fremgangsm?te som Figur5.30
(du trenger ikke ? ta hensyn til avrunding).
Innlevering:
- Svar p? tekstoppgaver
Del 5:
Helt tilslutt skal du implementere addisjon av flyttall i Assembler uten bruk av flyttallsoperasjoner. Dette er en god oppgave for ? bli bedre kjent med andre assembleroperasjoner. Vi anbefaler at du leser opp p? AND/ORR
, LSR/LSL
, BIC
beskrevet i kapittel 6.3.1
og 6.3.2
.
For ? gj?re oppgaven litt enklere kommer vi til ? anta at det bare er positive heltall som skal adderes og koden trenger heller ikke ? ta hensyn til avrunding. Du trenger ikke ? lage en egen funksjon for addisjonen, men kan utf?re hele beregningen i hovedfunksjonen.
For ? komme i gang kan du bruke skjelettet under og lagre det som part5.s
.
@ The two numbers we want to add
num1: .word 0x3f800000
num2: .word 0x3f800000
.text
.global main
main:
@ Load numbers
LDR r0, num1
LDR r1, num2
@ ! Perform addition here !
@ When done, return
BX lr
Algoritmen
Oppsummert skal koden din gj?re f?lgende.
- Maskere ut og flytte ned eksponenten i begge tall.
- Masker ut desimalen og legg til et ledende
1
tall. - Trekk fra den minste eksponenten fra den st?rste og set eksponenten til det nye tallet lik den st?rste av de to eksponentene.
- H?yre skift desimalen til det minste tallet med forskjellen fra steget over.
- Summer desimalene.
- Normaliser resultatet hvis n?dvendig, h?yre skift desimalen og ?k eksponenten med
1
. - Fjern ledende
1
fra den nye desimalen og konstruer det nye flyttallet med fortegn, eksponent og desimal.
Test algoritmen din med f?lgende addisjoner for ? overbevise deg selv at alt er riktig.
1.0 + 1.0 = 2.0
(0x3F800000 + 0x3F800000 = 0x40000000
)2.0 + 1.0
3.0 + 3.5
2.0 + 0.50390625
Kompilere koden
Som i tidligere deloppgaver s? kompileres programmet ditt ved ? kj?re f?lgende
Bruk gdbgui
for ? teste programmet ditt (gdbgui -b chromium-browser part5
).
Innlevering:
- Kildekode til flyttallsaddisjon i Assembler
- Summen av addisjonene
2-4
fraAlgoritmer