Oblig 3 - Assemblerprogrammering p? Raspberry Pi
Assemblerprogrammering
Assembler er den laveste (med noen unntak) m?ten ? programmere en CPU
. Programmeringsspr?ket er en menneskeleselig versjon av instruksjonene som maskinvaren utf?rer. Settet av instruksjoner som kan utf?res er forskjellig avhengig av prosessorarkitektur, og assemblerkode er derfor spesifikt til prosessoren det kj?rer p?. Til sammenligning m? h?yere niv? spr?k, som C
eller Python
, oversettes til Assembler. Dette gj?res enten av en kompilator eller ved at koden tolkes under kj?ring.
Assemblerprogrammering er noe man sjeldent kommer borti i dagliglivet som programmerer. Allikevel finnes det gode grunner til ? kunne skrive og lese Assembler. For mange mikroprosessorer trenger man assemblerprogrammering for ? kunne utnytte alle egenskapene til prosessoren. Assembler brukes ogs? blandt annet dersom man skal skrive kompilatorer, drivere eller operativsystemer. I denne obligen skal vi implementere noen enkle algoritmer i Assembler. Dette vil gi en innf?ring i hvordan enkle byggeblokker kan kombineres for ? skape funksjonalitet.
Raspberry Pi (ARMv7
)
I dette kurset skal vi jobbe med ARM Assembler p? Raspberry Pi (RPi
fra n? av). F?r vi begynner m? vi finne hvilken utgave av assembler prosessoren v?r st?tter. Vi starter med ? se p? mikroprosessoren som RPi
bruker. RPi 4B
modellen har en BCM2711
, og RPi 3B+
har en BCM2837B0
. BCM2711
best?r av fire ARM Cortex-A72 kjerner, og BCM2837B0
best?r av fire ARM Cortex-A53 kjerner. Begge disse prosessorene st?tter ARMv8
arkitektur. 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 er den arkitekturen vi skal bruke.
Vi kan ogs? finne ut hvilken versjon vi skal bruke ved ? kalle f?lgene:
$ uname -m
armv7l
Dette forteller oss at v?r versjon av Raspbian
st?tter ARMv7
Assembler. I l?reboken omtales ARMv4
som for alle form?l i denne obligen vil v?re likt som ARMv7
. Vi er n? klare til ? skrive assemblerkode.
Denne obligen best?r av fire deler. I f?rste del av obligen skal vi implementere en algoritme som regner ut Fibonacci sekvensen i Assembler. I andre del skal vi utvide denne koden ved ? gj?re den om til en funksjon vi kan kalle. I tredje del skal vi se hvordan en kompilator oversetter fra et h?yere niv? spr?k(C
) til lav niv? Assembler. I den siste delen skal vi se hvordan moderne datamaskiner representerer flyttall og hvordan man kan legge sammen slike tall. Selv om flyttall 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 svar p? tekstoppgavene. For programmeringsoppgavene skal 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 en avluser som heter GDB
. Denne har kun terminalbasert brukergrensesnitt, s? for ? gj?re avlusingen lettere benytter vi oss i steden av et tredjeparts program, gdbgui
, for ? f? et grafisk brukergrensesnitt.
For ? installere gdbgui
kan man kj?re f?lgende kommandoer i et terminalvindu
sudo apt-get update
sudo apt-get upgrade
python3 -m pip install --user pipx
python3 -m userpath append ~/.local/bin/
python3 -m pipx ensurepath
Lukk terminalen, og ?pne en ny terminal. Kj?r s? f?lgende kommando:
pipx install gdbgui
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 rekurrensen F(N) = F(N - 1) + F(N - 2)
med grunnstegene F(0) = 0
og F(1) = 1
. Algoritmen er vist i pseudokode under
current = 0
previous = 1
n = 13
while n > 0:
temporary = current
current = previous + current
previous = temporary
n = n - 1
# `current` contains the answer!
For ? komme i gang raskere benytter vi kodeskjelettet under.
.text
.global main
@ Main function of program
main:
@ First load the desired Fibonacci number
MOV r0, #13 @ N
@ Initialize the first two numbers in the sequence
MOV r1, #0 @ current
MOV r2, #1 @ previous
@ 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 kodeskjelettet har vi gjort f?lgende for ? hjelpe deg med ? komme i gang:
- Vi plasserer verdien
13
i register0
(r0
), dette indikerer at vi ?nsker ? beregne Fibonacci tallet forN = 13
. - Vi har s? initialisert to registere(
r1
ogr2
) med de to f?rste tallene i Fibonacci rekken.
Oppgaven er ? fylle 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
(test med flere verdier for ? forsikre deg om at oppgaven er l?st riktig).
Kompilere koden
Lagre koden ovenfor i en fil med navnet part1.s
. For ? kunne kompilere og kj?re koden m? vi benytte oss av en kompilator, som kan gj?re om kildekoden til en kj?rbar fil. Den f?lgende kommandoen vil kompilere kildekoden:
gcc -g -o part1 part1.s
Kj?r programmet ved hjelp av gdbgui
med f?lgende kommando:
gdbgui -b chromium-browser part1
En rask innf?ring i gdbgui
finnes her.
Innlevering:
- Kildekode til Fibonacci algorithmen i Assembler
Del 2:
En viktig inndeling i mange programmeringsspr?k er funksjoner. Funksjoner kan brukes til ? lage mindre blokker med separert logikk. N? skal vi se hvordan dette fungerer p? det laveste niv?et.
I denne oppgaven skal vi utvide Fibonacci algoritmen fra forrige del til ? bli en funksjon vi kan kalle. N?r man skriver en funskjon i assembler er det viktig ? f?lge funksjonskallkonvensjonen
(calling convention
p? engelsk), som er beskrevet i kapittel 6.3.7
i l?reboka. Denne konvensjonen beskriver hvilke registere som benyttes til inngangsverdier og returverdier, og hvilke registere funksjoner har lov til ? endre p?. Det er viktig ? passe p? at alle registere man ikke har lov til ? endre har samme verdi n?r man returnerer fra funksjonen som det de hadde da funksjonen ble kallt. Hvis man ikke passer p? dette kan funksjonskalleren f? seg en overraskelse n?r tallene som var der har forsvunnet.
Lag en ny kildekode fil med navnet part2.s
, fyll inn skjelettet under og implementer funksjonen som heter fib
. Funksjonen skal ta inn et argument, det ?nskede Fibonacci tallet N
, og skal returnere et tall, det beregnede svaret. I main
skal fib
funksjonen kalles, deretter skal resultatet skrives ut med printf
.
printf
kan kalles p? som alle andre funksjoner i Assembler (dvs. printf
kalles p? akkurat samme m?te som fib
). For v?re form?l vil vi behandle den som en funksjon som tar inn to argumenter, v?r formateringsstreng og tallet vi ?nsker ? skrive ut.
.text
.global main
@ Function that `main` should call
fib:
@ Fill in the Fibonacci algorithm here
@ ensure that input arguments and return values
@ follows the ARM calling convetion, section `6.3.7`
@ Also note that if you need extra registers it might
@ be necessary to store previous state on the stack
BX lr
main:
@ Always return properly to caller (even from 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
.
Det finnes to m?ter ? returnere fra et funksjonskall p?. 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 kompileres programmet ditt ved ? kj?re f?lgende:
gcc -g -o part2 part2.s
Bruk gdbgui
for ? teste programmet ditt. N?r du er ferdig pr?v ? kj?re programmet uten gdbgui
ved ? kalle p? programmet ditt i en terminal (./part2
).
Tekstoppgaver
- Hvem er det som har ansvar for ? ta vare p? verdiene i 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 det er viktig ? kunne forst? Assembler koden som h?yere niv? programmeringsspr?k produserer. Dette kan v?re for ? finne feil eller for ? oppdage bedre m?ter ? utnytte CPU
ressursene p?. I denne oppgaven skal vi se p? hvordan kompilatoren GCC
oversetter C
-kode til Assembler instruksjoner.
Under har vi laget et C
program for ? regne ut det N-te Fibonacci tallet.
#include <stdio.h>
// Our now familiar Fibonacci function
int fib(unsigned int n) {
// Initialize variables
int curr = 0;
int prev = 1;
// Loop until done
while(n != 0) {
int tmp = curr;
curr = curr + prev;
prev = tmp;
n = n - 1;
}
// Return as usual
return curr;
}
// Main is required in C and "should" return an integer,
// for now we can ignore the arguments to this function
int main(int argc, char** argv) {
// Calculate the 13th Fibonacci number
const int f = fib(13);
printf("%d\n", f);
// In C main should return a "status" of the program when
// exiting, '0' means successful (program terminated as
// expected)
return 0;
}
Lagre dette i en fil med navnet part3.c
.
Tekstoppgaver
For ? unders?ke hva kompilatoren gj?r med kildekoden m? 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.
gcc -Os -S -o part3.s part3.c
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 Assembler kode som er enklere ? tolke.
- 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:
- 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 i bin?r p?, slik at man kan regne med dem p? en datamaskin. IEEE 754
er en standard som s? godt som alle prosessorarkitekturer st?tter. Standarden beskriver hvordan flyttall skal operere, og gj?r at det er forutsigbart hva som skjer n?r vi jobber med desimaltall p? forskjellige maskiner.
N?r vi lagrer desimaltall som flyttall p? en datamaskin mistes noe informasjon grunnet avrunding. I titallsystemet kan tallet 1/10
representeres n?yaktig som 0.1
. P? grunn av representasjonen vi bruker for flyttall kan ikke dette tallet representeres n?yaktig i datamaskinen, det n?rmeste vi kommer er 0.10000000000000001
. Dersom vi gj?r mange flyttallsoperasjoner kan disse sm? avrundingsfeilene etter hvert "balle p? seg", og svaret v?rt kan bli feil. 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.
Et flyttall best?r av et fortegn (sign
p? bildet), eksponent (exponent
) og en desimal (fraction
). Tallet representerer 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 f?rst tallet til bin?r, 228 = 11100100
, deretter konverterer vi til vitenskapelig notasjon 11100100 = 1.11001 x 2^7
. Tallet 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 Figur 5.30 i boka. (du trenger ikke ? ta hensyn til avrunding).
Innlevering:
- Svar p? tekstoppgaver
Del 5:
Til slutt skal vi implementere addisjon av flyttall i Assembler uten bruk av innebygde flyttallsoperasjoner. Vi anbefaler at du leser deg opp p? assembleroperasjonene AND/ORR
, LSR/LSL
og 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. 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
Flyttallsaddisjonen dere skal utf?re er beskrevet i kap. 5.3 i l?reboka. Oppsummert skal koden din gj?re f?lgende.
- Maskere ut og flytte ned eksponenten i begge tall, slik at eksponenten ligger i de minst signifikante bitsene i registeret.
- Maskere ut desimalen. Legg til et ledende
1
tall p? desimalen dersom eksponenten ikke er 0. - Trekke den minste eksponenten fra den st?rste og sette eksponenten til det nye tallet lik den st?rste av de to eksponentene.
- H?yre skifte desimalen til det minste tallet med forskjellen av eksponentene fra steget over.
- Summere desimalene.
- Normalisere resultatet hvis n?dvendig. (h?yre skift desimalen og ?k eksponenten med
1
) - Fjerne ledende
1
fra den nye desimalen og konstruere det nye flyttallet med fortegn, eksponent og desimal. - Legg resultatet i r0.
Test algoritmen din med f?lgende addisjoner for ? overbevise deg selv om at alt er riktig. Lagre resultatet av addisjonene i en tekstfil med navn addisjoner.txt
.
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
gcc -g -o part5 part5.s
Bruk gdbgui
for ? teste programmet ditt (gdbgui -b chromium-browser part5
).
Innlevering:
- Kildekode til flyttallsaddisjon i Assembler
- Teksfilen
addisjoner.txt
Lever alle filene i canvas i en zippet mappe.