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

$ uname -m
armv7l

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

$ sudo pip 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.

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.

$ 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 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

$ gcc -g -o part2 part2.s

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

1. Hvem er det som har ansvar for registrene, og hvilke registre, når det kalles en funksjon under ARM funksjonskallkonvensjon?
2. Hva skjer med input argumentet til fib funksjonen etter at fib returnerer?
3. 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

$ gcc -g -o part3 part3.c

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.

$ 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 enklere å tolke Assembler kode.

1. 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 det GCC produserer?
2. Endre -Os til -O2, hvordan påvirker dette den produserte koden? Prøv å endre til -O3, ser du noen forandring nå?
3. 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.

Et 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.

1. Oversett 2.0 til IEEE 754 32-biter flyttall.
2. Oversett 3.0 til IEEE 754 32-biter flyttall.
3. Oversett 0.50390625 til IEEE 754 32-biter flyttall.
4. Legg sammen tallene 2.0 og 0.50390625 med samme fremgangsmåte som Figur 5.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.

1. Maskere ut og flytte ned eksponenten i begge tall.
2. Masker ut desimalen og legg til et ledende 1 tall.
3. Trekk fra den minste eksponenten fra den største og set eksponenten til det nye tallet lik den største av de to eksponentene.
4. Høyre skift desimalen til det minste tallet med forskjellen fra steget over.
5. Summer desimalene.
6. Normaliser resultatet hvis nødvendig, høyre skift desimalen og øk eksponenten med 1.
7. 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. 1.0 + 1.0 = 2.0 (0x3F800000 + 0x3F800000 = 0x40000000)
2. 2.0 + 1.0
3. 3.0 + 3.5
4. 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
• Summen av addisjonene 2-4 fra Algoritmer