IFT209 – Programmation système Examen final Hiver 2023

IFT209 – Programmation système

Université de Sherbrooke

Examen final
Enseignant: Michael Blondin
Date: jeudi 27 avril 2023
Durée: 3 heures

Directives:
— Répondez aux questions dans le cahier de réponses, pas sur ce questionnaire;
— Une feuille (recto verso) de notes au format 81/2” × 11” est permise, et les fiches en annexe;
— Aucun matériel additionnel (notes de cours, examens antérieurs, etc.) n’est permis;
— Aucun appareil électronique (calculatrice, téléphone, tablette, ordinateur, etc.) n’est permis;
— Donez une seule réponse par sous-question;
— L’examen comporte 5 questions sur 10 pages valant un total de 50 points;
— La correction se base sur la clarté, l’exactitude et la concision de vos réponses, ainsi que sur
la justification pour les questions qui en requièrent une;
— À moins d’avis contraire, le langage d’assemblage utilisé est celui de l’architecture ARMv8 tel
qu’utilisé en classe; un sommaire est présenté à l’annexe B;
— La question 5 utilise le langage d’assemblage du NES tel qu’utilisé en classe; un sommaire est
présenté à l’annexe C.

Question 1: valeurs booléennes et chaînes de bits

(a) Considérons une chaîne de cinq bits b4 b3 b2 b1 b0 . Chacun des trois schémas ci-dessous représente une opé- 3 pts
ration de masquage. Vous devez trouver des opérateurs et des masques qui mènent à chacun des résultats.
Vous devez donc remplacer chaque occurrence de ? par un opérateur logique parmi ∧, ∨ ou ⊕, et chaque
occurrence de ? par 0 ou 1. Dans chaque cas, l’opérateur est appliqué bit à bit.

opération A opération B opération C

b4 b3 b2 b1 b0 b4 b3 b2 b1 b0 b4 b3 b2 b1 b0
? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
0 b3 0 b1 b0 1 1 1 1 1 b4 ¬b3 ¬b2 b1 b0

opération A opération B opération C

b4 b3 b2 b1 b0 b4 b3 b2 b1 b0 b4 b3 b2 b1 b0
∧ ∨ ⊕
0 1 0 1 1 1 1 1 1 1 0 1 1 0 0
0 b3 0 b1 b0 1 1 1 1 1 b4 ¬b3 ¬b2 b1 b0

(b) Considérons la représentation de pixel, en niveaux de gris, stocké sur n bits, où 0 représente noir et 2n − 1 5 pts
représente blanc. Par exemple, avec n = 2, les niveaux possibles sont noir 00 , gris foncé 01 , gris pâle 10
et blanc 11 . Avec n = 8, ces 256 niveaux de gris peuvent être représentés:

page 1 sur 10
IFT209 – Programmation système Examen final Hiver 2023

01010101 (85) 11111111 (255)

00000000 (0) 10101010 (170)

Supposons que w19 contienne un pixel au format 2 bits. Nous cherchons à convertir sa représentation au
format 8 bits dans w20 comme suit:

w19 w20

0 ··· 0 00000000 0 ··· 0 00000000

0 ··· 0 00000001 0 ··· 0 01010101
0 ··· 0 00000010 0 ··· 0 10101010
0 ··· 0 00000011 0 ··· 0 11111111

Complétez les portions trouées de ces deux programmes afin qu’ils accomplissent chacun cette tâche:

programme A programme B

lsl w20, ???, 2 ror w20, w19, 1

orr w20, w20, w19 asr w20, w20, 31
lsl w19, w20, ??? and w20, w20, 0x55
orr w20, ???, w20 ror w19, w19, 2
asr w19, w19, 31
and w19, w19, ???
orr w20, w19, w20

programme A programme B

lsl w20, w19, 2 ror w20, w19, 1

orr w20, w20, w19 asr w20, w20, 31
lsl w19, w20, 4 and w20, w20, 0x55
orr w20, w19, w20 ror w19, w19, 2
asr w19, w19, 31
and w19, w19, 0xAA
orr w20, w19, w20

Question 2: chaînes de caractères

Rappelons le format du codage UTF-8 tel que présenté dans les notes de cours:

plage de codes format binaire des octets

# bits
début fin octet 1 octet 2 octet 3 octet 4
7 00000016 00007F16 0******* — — —
11 00008016 0007FF16 110***** 10****** — —
16 00080016 00FFFF16 1110**** 10****** 10****** —
21 01000016 10FFFF16 11110*** 10****** 10****** 10******

page 2 sur 10
IFT209 – Programmation système Examen final Hiver 2023

(a) Le pictogramme « ❤ » et l’émoji « 🙊 » sont des caractères représentés, respectivement, par les codages 2 pts
UTF-8 « 11100010 10011101 10100100 » et « 11110000 10011111 10011001 10001010 ». Donnez le code
numérique Unicode associé à chacun de ces deux caractères (en hexadécimal).

276416 (obtenu de 11100010 10011101 10100100) et 1F64A16 (obtenu de 11110000 10011111 10011001 10001010)

(b) Le code numérique Unicode de la lettre accentuée « ê » est 0xEA. Donnez son codage UTF-8. 2 pts

11000011 10101010 (obtenu de 0x000080 ≤ 0xEA ≤ 0x0007FF)

(c) Rappelons que le codage ISO 8859-1 (Latin-1) permet de représenter les caractères dont le code numérique 2 pts
Unicode appartient à la plage 0x00 à 0xFF. Combien de caractères de cette chaîne de caractères UTF-8 sont
représentables en Latin-1? Justifiez.
11010111 10000110 11000011 10101010 01111010 11100011 10000011 10000001 00000000
3 car il y a deux caractères d’un octet, et un caractère de deux octets dont le code numérique est
inférieur ou égal à 0xFF:
11010111 10000110 11000011 10101010 01111010 11100011 10000011 10000001 00000000

(d) Rappelons que les lettres accentuées ont un code numérique dans la plage 0xC0 à 0xFF, et que le sixième 6 pts
bit de poids faible du code numérique vaut 1 si et seulement si la lettre est en minuscule. Par exemple, le
code numérique de « ê » est 111010102 (0xEA) et celui de « Ê » est 110010102 (0xCA).
Écrivez un sous-programme qui accomplit cette tâche:
Entrée: adresse d’une chaîne de caractères s sous codage UTF-8,
dont chaque caractère est d’au plus deux octets (premier et seul paramètre)
Retour: quantité de lettres accentuées en minuscule dans s

En particulier, votre sous-programme devrait retourner 2 sur la chaîne de caractères « Été à Sherbrooke ».
Vous avez accès aux macros SAVE et RESTORE.
Remarque: pour simplifier la question, vous avez la promesse qu’il n’y aura aucun caractère de trois ou quatre octets.

compter: // unsigned long compter(char* s)

SAVE // {
mov x19, x0 //
mov x0, 0 // unsigned long n = 0;
boucle: // do {
ldrb w20, [x19], 1 // oct1 = *s; s++;
cbz w20, fin // if (oct1 == 0) { break; }
//
tbz w20, 7, boucle // if (oct1 & 0b10000000 != 0) {
ldrb w21, [x19], 1 // oct2 = *s; s++;
//
cmp w20, 0xC3 // if (oct1 == 0x11000011) { // lettre accentuée?
[Link] boucle //
lsr x21, x21, 5 //
and x21, x21, 0x01 //
add x0, x0, x21 // n += (oct2 >> 5) & 0b00000001; // += minuscule
b boucle // }
// }
RESTORE // }
ret // return n;
// }

page 3 sur 10
IFT209 – Programmation système Examen final Hiver 2023

Question 3: sous-programmes et mémoire

Considérons cet algorithme qui détermine récursivement si un tableau trié t contient un certain élément x:

Entrée : tableau t d’entiers signés de 64 bits, triés en ordre croissant,

entier signé de 64 bits n qui représente le nombre d’éléments du tableau,
entier signé de 64 bits x
Retour : un indice m tel que t[m] = x s’il en existe un, −1 sinon
fouille(t, n, x):
retourner fouille_aux(t, x, 0, n − 1) // lancer une fouille dichotomique

fouille_aux(t, x, i, j ):
si i > j alors
retourner −1 // élément pas dans le tableau
sinon
m ← (i + j) ÷ 2
si x < t[m] alors
retourner fouille_aux(t, x, i, m − 1) // l'élément est à gauche?
sinon si t[m] < x alors
retourner fouille_aux(t, x, m + 1, j ) // l'élément est à droite?
sinon
retourner m // t[m] = x, élément trouvé

(a) Implémentez l’algorithme en complétant les sous-programmes « fouille: » et « fouille_aux: ». 5 pts

fouille:
/* à compléter au besoin */
SAVE
/* à compléter */
RESTORE
/* à compléter au besoin */

fouille_aux:
/* à compléter au besoin */
SAVE
/* à compléter */
RESTORE
/* à compléter au besoin */

Remarque: ne modifiez pas l’algorithme pour le rendre itératif, il doit demeurer récursif.

page 4 sur 10
IFT209 – Programmation système Examen final Hiver 2023

fouille: // long fouille(long[] t, long n, long x)

sub x3, x1, 1 //
mov x1, x2 //
mov x2, 0 //
bl fouille_aux //
A: ret // return fouille_aux(t, x, 0, n - 1);
// }
//
fouille_aux: // fouille_aux(long[] t, long x, long i, long j)
SAVE // {
cmp x2, x3 //
[Link] fouille_aux_corps // if (i > j) {
mov x0, -1 // return -1;
b fouille_aux_ret // }
// else {
fouille_aux_corps: //
add x19, x2, x3 //
lsr x19, x19, 1 // long m = (i + j) / 2;
ldr x20, [x0, x19, lsl 3] //
cmp x1, x20 //
fouille_aux_si: //
[Link] fouille_aux_sinonsi // if (x < t[m]) {
sub x3, x19, 1 //
bl fouille_aux // return fouille_aux(t, x, i, m - 1);
b fouille_aux_ret // }
fouille_aux_sinonsi: // else if (x > t[m]) {
[Link] fouille_aux_sinon //
add x2, x19, 1 //
bl fouille_aux // return fouille_aux(t, x, m + 1, j);
B: b fouille_aux_ret // }
fouille_aux_sinon: // else {
mov x0, x19 // return m;
// }
fouille_aux_ret: // }
RESTORE //
ret // }

(b) Expliquez ce qui se produit si on retire SAVE et RESTORE de votre code et qu’on l’appelle avec l’entrée t = [10], 2,5 pts
n = 1 et x = 15.
L’appel fouille_aux(t, 15, 0, 0) assigne « x30 ← A ». Comme 15 > t[0], l’appel fouille_aux(t,
15, 1, 0) assigne « x30 ← B ». Par la suite, chaque « ret » banche à B, ce qui crée une boucle infinie.

(c) Remplacez SAVE et RESTORE par votre propre code afin de sauvegarder uniquement le contenu des registres 2,5 pts
nécessaires, par ex. si vous n’utilisez pas x28 , alors il ne devrait pas être sauvegardé.

page 5 sur 10
IFT209 – Programmation système Examen final Hiver 2023

fouille:
stp x29, x30, [sp, -16]!
mov x29, sp
// ...
ldp x29, x30, [sp], 16
ret
fouille_aux:
stp x29, x30, [sp, -32]!
mov x29, sp
stp x19, x20, [sp, 16]
// ...
ldp x19, x20, [sp, 16]
ldp x29, x30, [sp], 32
ret

Question 4: nombres en virgule flottante

(a) Considérons le système de nombres en virgule flottante où la base est β = 2, la mantisse possède n = 4 5 pts
bits, et l’exposant varie entre emin = −5 et emax = 5. Effectuez la multiplication suivante:

(1,110 × 2−2 ) · (1,100 × 22 ).

Votre résultat doit être normalisé et approximé par arrondi avec bris d’égalité vers chiffre pair (l’arrondi vu en
classe). Laissez une trace de votre démarche.

Réponse: 1,010 × 21
Démarche:
1,110
×
1,100
0,1110
+ 1,110
10,1010
On obtient 10,1010 × 2−2+2 = 10,1010 × 20 = 1,01010 × 21 . Il y a égalité entre les approximations
1,010 et 1,011. On choisit la première car elle termine par 0.

(b) Rappelons que la norme IEEE 754 représente un nombre en virgule flottante ainsi en binaire:

format signe exposant mantisse

simple 1 bit 8 bits (biais de 127) 23 bits (+1 bit caché)
double 1 bit 11 bits (biais de 1023) 52 bits (+1 bit caché)

Par exemple, le nombre 1,5 est codé sous précision simple par « 0 01111111 10000000000000000000000 ».
(i) Donnez le codage du nombre 13,625 au format simple précision. 2,5 pts

Comme 13,625 = +1101,101 × 20 = +1,101101 × 23 et 3 + 127 = 128 + 2, on obtient:

0 10000010 10110100000000000000000

page 6 sur 10
IFT209 – Programmation système Examen final Hiver 2023

(ii) Vrai ou faux: afin de convertir un nombre en virgule flottante du format simple vers le format double, 2,5 pts
on doit ajouter 32 zéros à sa gauche. Justifiez.

Faux, par ex. si le nombre est négatif, alors l’ajout de ces zéros engendrera un nombre positif.

Question 5: entrées/sorties
Rappelons les trois types d’interruptions du NES, du plus au moins prioritaire:

0. RESET: lancée au démarrage de la console (bouton « POWER » enfoncé) ou

lorsque la console est redémarrée (bouton « RESET » appuyé)
1. NMI: lancée lors de l’intervalle de rafraîchissement vertical (VBLANK)
2. IRQ: ne possède pas d’usage particulier, mais peut, par exemple, être
lancée par une puce électronique

(a) Le NES Mouse209 est un périphérique fictif du NES. Il s’agit d’une souris munie de deux boutons: 7 pts

Le NES Mouse209 se connecte dans le second port et fonctionne comme suit:

— Pour demander l’état, on envoie 1, puis 0, à l’adresse 401716 liée au port de communication;
— Ensuite, chaque octet b7 · · · b0 lu à l’adresse 401716 donne de l’information comme suit:

b7 b6 b5 b4 b3 b2 b1 b0

Première lecture: — — — — — — — —
Deuxième lecture: bouton droit appuyé? bouton gauche appuyé? — — — — — —
Troisième lecture: haut = 1, bas = 0 déplacement vertical (entier non signé de 7 bits)
Quatrième lecture: gauche = 1, droite = 0 déplacement horizontal (entier non signé de 7 bits)

Complétez le code ci-dessous afin que le curseur se déplace horizontalement selon l’information fournie par
la souris. Vous n’avez pas à gérer les débordements hors de l’écran; le curseur peut réapparaître de l’autre
côté. Vous n’avez pas à gérer le déplacement vertical.
Le curseur doit également changer d’apparence. Il est représenté graphiquement par la tuile 129  lorsque
le bouton gauche est appuyé, et par la tuile 128  sinon.

posX: .rs 1 ; Position horizontale du curseur

posY: .rs 1 ; Position verticale du curseur
btnGauche: .rs 1 ; Bouton gauche appuyé?
btnDroite: .rs 1 ; Bouton droite appuyé?
;

page 7 sur 10
IFT209 – Programmation système Examen final Hiver 2023

point_entree: ; point_entree() {
lda #%00000000 ; Désactiver temporairement les interruptions NMI
sta $2000 ;
;
ldx #$FF ;
txs ; Initialiser la pile d'exécution
;
jsr init ; Initialiser les variables
;
lda #%10011000 ; Réactiver les interruptions NMI et
sta $2000 ; choisir les tables de tuiles
lda #%00010000 ;
sta $2001 ; Activer les tuiles
;
boucle: ; while (true) { }
jmp boucle ; }
;
gestion: ; gestion()
; {
SAVE ; /* empiler a, x et y */
jsr deplacer ; deplacer()
jsr afficher ; afficher()
RESTORE ; /* dépiler a, x et y */
rti ; }
;
init: ; init()
lda #100 ; {
sta posX ; posX = 100
sta posY ; posY = 100
lda #0 ;
sta btnGauche ; btnGauche = 0
sta btnDroite ; btnDroite = 0
rts ; }
;
;; Déplacer curseur selon ;
;; l'état du NES Mouse209 ;
deplacer: ; deplacer()
; {
;; À COMPLÉTER ;
; }
;
;; Afficher le curseur ;
afficher: ; afficher()
; {
;; À COMPLÉTER ; ; Ordre: pos. verticale, identifiant, attributs,
; pos. horizontale
lda #$05 ; Envoi par accès direct à la mémoire (DMA)
sta $4014 ; de la plage $0500 à $05FF
;
;; À COMPLÉTER ;
; }
;

page 8 sur 10
IFT209 – Programmation système Examen final Hiver 2023

;; Segment des interruptions ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

.word À COMPLÉTER ; NMI
.word À COMPLÉTER ; RESET
.word À COMPLÉTER ; IRQ

deplacer:
;; Demander état souris
lda #1
sta $4017
lda #0
sta $4017

;; Bouton gauche?
lda $4017
lda $4017
and #%01000000
sta btnGauche

ldx #0
deplacer_decalage:
lsr btnGauche
inx
cpx #6
bne deplacer_decalage

;; Curseur
lda $4017
lda $4017
tax
and #%1000000
cmp #%1000000
txa
and #%0111111
bne deplacer_suite
deplacer_gauche:
eor #%1111111
clc
adc #1 ; a = -a // complément à deux
deplacer_suite:
clc
adc posX
sta posX
rts

afficher:
lda posY
sta $0500

lda #128
ora btnGauche
sta $0501

lda #%00000000
sta $0502

lda posX
sta $0503

lda #$05
sta $4014

rts

;; Segment des interruptions ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

.word gestion ; NMI
.word point_entree ; RESET
.word 0 ; IRQ

page 9 sur 10
IFT209 – Programmation système Examen final Hiver 2023

(b) Rappelons que l’intervalle de rafraîchissement vertical (VBLANK) se produit à intervalle régulier. On peut en 3 pts
être averti par une interruption (NMI) ou en inspectant le bit de poids fort à l’adresse 200216 . Considérons
cette légère modification du code précédent:

;; COMME AVANT ICI ; ...

;
boucle: ; while (true) {
jsr deplacer ; deplacer() // l'appel a été déplacé ici <---
jmp boucle ; } |
; } |
; |
gestion: ; gestion() |
; { |
SAVE ; /* empiler a, x et y */ ----------------------
jsr afficher ; afficher()
RESTORE ; /* dépiler a, x et y */
rti ; }
;
;; COMME AVANT ICI ; ...

Le déplacement du curseur se fait maintenant trop rapidement par rapport à l’affichage. Expliquez comment
ralentir la lecture de l’état de la souris afin qu’elle se fasse à la même cadence que l’affichage.

On peut utiliser l’attente active afin d’attendre le VBLANK:

boucle:
lda $2002 ; Attendre VBLANK
and #%10000000 ;
cmp #%10000000 ;
bne boucle ;
jsr deplacer
jmp boucle

page 10 sur 10
 Annexe A:

Fiches récapitulatives
8. Programmation structurée
Séquence Itération
▶ Composition séquentielle d’instructions ▶ Exécution répétée d’instructions (while, do while, for, ...)
▶ Une instruction de haut niveau peut nécessiter plusieurs ins- ▶ Implémentation: branchements arrière, et parfois avant:
tructions de bas niveau; par ex. « x19 *= 7 » devient:
while (cond(xd, xn)) { boucle:
mov x20, 7 // code cmp xd, xn
mul x19, x19, x20 } b.¬cond fin
// code
Sélection b boucle
fin:
▶ Exécution conditionnelle d’instructions (if, switch, ...)
▶ Implémentation: branchements avant: Sous-programmes
if (cond(xd, xn)) { si: ▶ Permettent de modulariser le code en sous-routines
// code si
}
cmp xd, xn
▶ Registres partagés par programme et sous-programmes
b.¬cond sinon
else { // code si ▶ Arguments: passés par valeur ou adresse dans x0 –x7 (en ordre)
// code sinon b fin
} sinon: ▶ Appel: « bl sprog » assigne x30 ← pc+4 et branche à sprog:
// code sinon
fin: ▶ Retour: « ret » branche vers l’adresse de retour x30
▶ Conditions multiples: obtenues avec plusieurs sélections ▶ Sauvegarde: l’appelé doit rétablir les registres x19 à x30

9. Valeurs booléennes et chaînes de bits

Valeurs booléennes ▶ Bit de signe copié lors d’un décalage arithmétique à droite:
▶ Correspond à un bit: 1 = vrai, 0 = faux 3 bits vers la droite
11000101 −−−−−−−−−−−→ 11111000 asr xd, xn, 3
▶ Représentation: sur un octet, puisque bits non adressables
▶ Multiplication/division: par 2k correspond à un décalage de
Opérateurs logiques k bits vers la gauche/droite
▶ Opérations: ¬, ∧, ∨, ⊕ « bit à bit » étendues aux chaînes: Décalages circulaires
mvn x19, x20 and x19, x20, x21 orr x19, x20, x21 eor x19, x20, x21 ▶ Comme un décalage logique, mais les bits « perdus » sont ré-
¬ ··· ¬ ¬ ¬ 0 ··· 1 0 1 0 ··· 1 0 1 0 ··· 1 0 1 insérés de l’autre côté:
0 ··· 1 0 1 ∧ ··· ∧ ∧ ∧ ∨ ··· ∨ ∨ ∨ ⊕ ··· ⊕ ⊕ ⊕
3 bits vers la gauche
1 ··· 0 1 0 1 ··· 1 0 0 1 ··· 1 0 0 1 ··· 1 0 0 11000101 −−−−−−−−−−−→ 00101110 n’existe pas sur ARMv8
0 ··· 1 0 0 1 ··· 1 0 1 1 ··· 0 0 1 3 bits vers la droite
11000101 −−−−−−−−−−−→ 10111000 ror xd, xn, 3
▶ Échange de valeurs: se fait sans registre temporaire avec eor Masquage
▶ Permet d’isoler certains bits à manipuler:
Décalages logiques et arithmétiques
sélection r∧m met à 0 les bits de r non spécifiés par m
▶ Décale les bits de j positions vers la gauche/droite:
activation r∨m met à 1 les bits de r spécifiés par m
3 bits vers la gauche
11000101 −−−−−−−−−−−→ 00101000 lsl xd, xn, 3 désactivation r ∧ ¬m met à 0 les bits de r spécifiés par m
3 bits vers la droite
11000101 −−−−−−−−−−−→ 00011000 lsr xd, xn, 3 basculement r⊕m inverse les bits de r spécifiés par m

10. Chaînes de caractères

UTF-8
Généralités ▶ Représente > 1 000 000 caractères sur 1 à 4 octets
▶ Caractère: symbole représenté par une chaîne de bits ▶ Caractères 0 à 127: ASCII
▶ Chaîne de caractères: suite finie de caractères, normalement ▶ Caractères 128 à 255: ISO 8859-1, mais codés différemment
terminée par un caractère nul
▶ Format général:
ASCII # bits
plage de codes 1 format binaire des octets
début fin octet 1 octet 2 octet 3 octet 4
▶ Représente 128 caractères codés sur 7 bits
7 00000016 00007F16 0******* — — —
▶ Lettre minuscule mise en majuscule en assignant le 6ème bit 11 00008016 0007FF16 110***** 10****** — —
16 00080016 00FFFF16 1110**** 10****** 10****** —
de poids faible à 0, par ex. a = 11000012 et A = 10000012 21 01000016 10FFFF16 11110*** 10****** 10****** 10******

ISO 8859-1 (Latin-1) ▶ Exemples:

▶ Représente 256 caractères codés sur 8 bits
car. code codage
▶ Caractères 0 à 127: ASCII a 11000012 011000012
▶ Caractères 128 à 255: lettres accentuées et autres caractères é 000 111010012 11000011 101010012
� 00110000 101100012 11100011 10000010 101100012
𒐍 00001 00100100 000011012 11110000 10010010 10010000 100011012
11. Sous-programmes et mémoire
Disposition de la mémoire. Tas.
00000 · · · 000016

Instructions (text)
▶ Contient les données allouées dynamiquement: structures de
Données statiques données, objets, etc.
Initialisées, en lecture seule (rodata)
Pile d’exécution.
Initialisées (data)
▶ Stocke les données temporaires lors d’appel de sous-prog.
Non initialisées (bss) ▶ Données empilées à l’appel et dépilées au retour
▶ Pointeur de pile: sp contient l’adresse du sommet de la pile
Données dynamiques

Tas
▶ Empiler: décrémenter sp + stocker avec stp xd, xn, a
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ▶ Dépiler: incrémenter sp + charger avec ldp xd, xn, a

Récursion.
sp (pointeur de pile)
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
▶ Implémentée par: appels de sous-prog. + usage de la pile
Pile ▶ Récursion trop profonde: erreur car la pile est bornée
FFFF · · · FFFF16 ▶ Solution (partielle): empiler le moins de données possibles

12. Nombres en virgule flottante

Représentation. Précision.
▶ Nombre en virgule flottante: ▶ Approximations de nombres réels:
signe exposant (a) arrondir (égalité: dernier chiffre pair): 1,9565 −
→ 1,956
z}|{ z}|{
± d0 ,d1 d2 · · · dn−1 × β e (b) troncation: 1,5416 −
→ 1,541
| {z } |{z}
mantisse en base β base ▶ Erreur relative: err(x) := x−x
x où x est l’approximation

▶ Normalisé: si d0 ̸= 0 ▶ Borne pour mode (a): |err(x)| ≤ (β/2) · β −n

| {z }
Norme IEEE 754. ε machine
▶ Représente différents ordres de grandeur:
⁄2
7
▶ format signe exposant mantisse
−3 ⁄2
5
−2 −3⁄2
−1 −3⁄4 −1⁄2 ⁄8 5
⁄4 ⁄4
7
5
⁄8 7

simple 1 bit 8 bits 23 bits (+1 bit caché)

−5⁄4 −7⁄8 −5⁄8 1
⁄2 ⁄4 1
3
−5⁄2
−7⁄4 ⁄2
3
2
−7⁄2 3 double 1 bit 11 bits 52 bits (+1 bit caché)
Arithmétique. ▶ Repr. avec biais: 1000011011100 · · · 0 = −1,11 × 213−127
▶ Addition: (1) mettre exposants en commun; (2) additionner ▶ ±0 (s0 · · · 00 · · · 0); ±∞ (s1 · · · 10 · · · 00); NaN (s1 · · · 1 e 0 · · · 01)
mantisses; (3) normaliser; (4) arrondir
ARMv8.
▶ Multiplication: (1) additionner exposants; (2) multiplier ▶ Registres: dn (64 bits) et sn (32 bits)
mantisses; (3) normaliser; (4) arrondir
▶ Instructions: ldr, str, fmov, fcmp, fadd, fmul, fsqrt, etc.

13. Introduction aux entrées/sorties : NES

Architecture. Tuiles.
▶ Pas RISC: possible de manipuler la mémoire directement ▶ Images: constituées de tuiles de 8 × 8 pixels
▶ Processeurs: proc. principal + proc. d’images (PPU) ▶ Tuiles: stockées dans la cartouche, transférées vers le PPU
▶ Mémoire principale: primaire + registres d’E/S + programme ▶ Tuile: spécifiée par 4 octets (y, i, a, x): position verticale y,
▶ Mémoire vidéo: stocke les tuiles et palettes de couleurs numéro de tuile i, attributs a, position horizontale x
▶ Attributs: 8 bits pour réflexions, profondeur et couleurs
Jeu d’instructions.
▶ Registres: a (accumulateur), x (index), y (index), s (pile) Sorties (graphiques).
▶ Valeurs imm.: # (numérique), $ (hexadécimal), % (binaire) ▶ L’affichage se fait lors du rafraîchissement vertical
▶ Accès mémoire: lda, ldx, ldy (chargement d’octet); sta, stx, ▶ Sortie: stocker tuiles de 0X0016 à 0XFF16 en mém. principale
sty (stockage d’octet); txa, tax, tya, etc. (copie) ▶ Affichage: transférer au PPU en écrivant #$0X à $4014
▶ Arithmétique: adc (addition avec report); sbc (soustraction avec
Entrées (manettes).
emprunt); inc, inx, iny, dec (inc/décrémentation)
▶ Entrée: protocole de communication via port de manettes
▶ Logique: asl (<< 1), lsr (>> 1), and (∧), ora (∨), eor (⊕)
▶ Demande de lecture: envoyer #1, puis #0, via $4016
▶ Contrôle: cmp, cpx, cpy (comparaison); beq, bne (branch. condi-
tionnel), jmp (branch. incond.), jsr/rts (sous-prog.) ▶ Lecture: lire bit de poids faible à $4016 pour chaque bouton
14. Entrées/sorties
Mécanismes d’entrée/sortie. Accès direct à la mémoire (DMA).
▶ Attente active: interrogation continue d’un registre d’état jus- ▶ DMA: permet au processeur d’initier un accès mémoire et de
qu’à un événement (ex. VBLANK) laisser un contrôleur effectuer le transfert de données
▶ Interruption: signal lancé vers le processeur lors d’un événe- ▶ Sur le NES: envoi des tuiles mem[0x0200, 0x02FF] vers la
ment (ex. NMI, RESET, IRQ) mémoire de sprites via DMA:
lda #$02
Interruptions. sta $4014
Appels système.
▶ Gestionnaire: sous-routine qui traite une interruption ▶ Accès E/S: empêché par le système d’exploitation (sécurité)
▶ Table d’interruptions: contient l’adresse des gestionnaires ▶ Appel système: service offert par le noyau du système d’ex-
▶ Traitement: sauvegarder l’état du processeur; appeler le ges- ploitation; appelé via une interruption logicielle
tionnaire; restaurer l’état ▶ Exemples UNIX + ARMv8: // Afficher chaine
▶ Priorité: valeur numérique assignée à une interruption mov x8, 64
code appel système
▶ Gestion des priorités: interruption ignorée si une interruption mov x0, 1
64 write(flux, chaine, #octets) adr x1, chaine
de priorité > est en cours; gestionnaire en exécution mis en
63 mov x2, 10
attente si une interruption de priorité ≥ est lancée read(flux, tampon, #octets)
svc 0
▶ Non masquable: top priorité, ne peut pas ignorer (ex. RESET) Flux d’entrée standard = 0
Flux de sortie standard = 1
 Annexe B:

Sommaire de l’architecture ARMv8

Registres.
▶ Chaque registre xn possède 64 bits: b63 b62 · · · b1 b0
▶ Notation: xn ⟨i⟩ := bi , xn ⟨i, j⟩ := bi bi−1 · · · bj , rn réfère au registre xn ou wn
▶ Chaque sous-registre wn possède 32 bits et correspond à xn ⟨31, 0⟩
▶ Le compteur d’instruction pc n’est pas accessible
▶ Conventions:

Registres Nom Utilisation

x0 – x7 — registres d’arguments et de retour de sous-programmes
x8 xr registre pour retourner l’adresse d’une structure
x9 – x15 — registres temporaires sauvegardés par l’appelant
x16 – x17 ip0 – ip1 registres temporaires intra-procéduraux
x18 pr registre temporaire pouvant être réservé par le système
x19 – x28 — registres temporaires sauvegardés par l’appelé
x29 fp pointeur vers l’ancien sommet de pile (frame pointer)
x30 lr registre d’adresse de retour (link register)
xzr sp registre contenant la valeur 0, ou pointeur de pile (stack pointer)

Arithmétique (entiers).
▶ Les codes de condition sont modifiés par cmp, adds, adcs, subs, sbcs et negs
▶ À cette différence près, adds, adcs, subs, sbcs et negs se comportent respectivement comme add, adc, sub, sbc et neg
▶ Instructions, où i est une valeur immédiate de 12 bits et j est une valeur immédiate de 6 bits:

Code d’op. Syntaxe Effet Exemple

cmp rd, rm compare rd et rm cmp x19, x21
cmp cmp rd, i compare rd et i cmp x19, 42
cmp rd, rm, decal j compare rd et rm decal j cmp x19, x21, lsl 1
add rd, rn, rm rd ← rn + rm add x19, x20, x21
add add rd, rn, i rd ← rn + i add x19, x20, 42
add rd, rn, rm, decal j rd ← rn + (rm decal j) add x19, x20, x21, lsl 1
adc adc rd, rn, rm rd ← rn + rm + C adc x19, x20, x21
sub rd, rn, rm rd ← rn − rm sub x19, x20, x21
sub sub rd, rn, i rd ← rn − i sub x19, x20, 42
sub rd, rn, rm, decal j rd ← rn − (rm decal j) sub x19, x20, x21, lsl 1
sbc sbc rd, rn, rm rd ← rn − rm − 1 + C sbc x19, x20, x21
neg rd, rm rd ← −rm neg x19, x21
neg
neg rd, rm, decal j rd ← −(rm decal j) neg x19, x21, lsl 1
mul mul rd, rn, rm rd ← rn · rm mul x19, x20, x21
udiv udiv rd, rn, rm rd ← rn ÷ rm (non signé) udiv x19, x20, x21
sdiv sdiv rd, rn, rm rd ← rn ÷ rm (signé) sdiv x19, x20, x21
madd madd rd, rn, rm, ra rd ← ra + (rn · rm ) madd x19, x20, x21, x22
msub msub rd, rn, rm, ra rd ← ra − (rn · rm ) msub x19, x20, x21, x22
Accès mémoire.
▶ ldrsw, ldrsh et ldrsb se comportent respectivement comme ldr (4 octets), ldrh et ldrb à l’exception du fait qu’ils effectuent
un chargement dans xd où les bits excédentaires sont le bit de signe de la donnée chargée, plutôt que des zéros
▶ Instructions, où a est une adresse et memb [a] réfère aux b octets à l’adresse a de la mémoire principale:

Code d’op. Syntaxe Effet Exemple

mov rd, rm rd ← rm mov x19, x21
mov
mov rd, i rd ← i mov x19, 42
ldr xd, a charge 8 octets: xd ⟨63, 0⟩ ← mem8 [a] ldr x19, [x20]
ldr
ldr wd, a charge 4 octets: xd ⟨31, 0⟩ ← mem4 [a]; xd ⟨63, 32⟩ ← 0 ldr w19, [x20]
ldrh ldrh wd, a charge 2 octets: xd ⟨15, 0⟩ ← mem2 [a]; xd ⟨63, 16⟩ ← 0 ldrh w19, [x20]
ldrb ldrb wd, a charge 1 octet: xd ⟨ 7, 0⟩ ← mem1 [a]; xd ⟨63, 8⟩ ← 0 ldrb w19, [x20]
str xd, a stocke 8 octets: mem8 [a] ← xd ⟨63, 0⟩ str x19, [x20]
str
str wd, a stocke 4 octets: mem4 [a] ← xd ⟨31, 0⟩ str w19, [x20]
strh strh wd, a stocke 2 octets: mem2 [a] ← xd ⟨15, 0⟩ str w19, [x20]
strb strb wd, a stocke 1 octet: mem1 [a] ← xd ⟨ 7, 0⟩ strb w19, [x20]
ldp ldp xd, xn, a charge 16 octets: xd ⟨63, 0⟩ ← mem8 [a], xn ⟨63, 0⟩ ← mem8 [a + 8] ldp x19, x20, [sp]
stp stp xd, xn, a stocke 16 octets: mem8 [a] ← xd ⟨63, 0⟩, mem8 [a + 8] ← xn ⟨63, 0⟩ stp x19, x20, [sp]

Conditions de branchement.
▶ Codes de condition: N (négatif), Z (zéro), C (report), V (débordement)
▶ C indique aussi l’absence d’emprunt lors d’une soustraction
▶ Conditions de branchement:

Entiers non signés Entiers signés

Code Signification Codes de condition Code Signification Codes de condition
eq = Z eq = Z
ne ̸= ¬Z ne ̸= ¬Z
hs ≥ C ge ≥ N=V
hi > C ∧ ¬Z gt > ¬ Z ∧ ( N = V)
ls ≤ ¬C ∨ Z le ≤ Z ∨ (N ̸= V)
lo < ¬C lt < N ̸= V
vs débordement V
vc pas de débordement ¬V
mi négatif N
pl non négatif ¬N

Branchement.
▶ Instructions de branchement, où j est une valeur immédiate de 6 bits:

Code d’op. Syntaxe Effet Exemple

b. [Link] etiq branche à etiq: si cond [Link] main100
b b etiq branche à etiq: b main100
cbz cbz rd, etiq branche à etiq: si rd = 0 cbz x19 main100
cbnz cbnz rd, etiq branche à etiq: si rd ̸= 0 cbnz x19 main100
tbz tbz rd, j, etiq branche à etiq: si rd ⟨j⟩ = 0 tbz x19, 1, main100
tbnz tbnz rd, j, etiq branche à etiq: si rd ⟨j⟩ ̸= 0 tbnz x19, 1, main100
bl bl etiq branche à etiq: et x30 ← pc + 4 bl printf
blr blr xd branche à xd et x30 ← pc + 4 blr x20
br br xd branche à xd br x20
ret ret branche à x30 (retour de sous-prog.) ret
Adressage.
▶ Modes d’adressages, où k est une valeur immédiate de 7 bits:

Nom Syntaxe Adresse Effet Exemple

adresse d’une étiquette adr xd, etiq — xd ← adresse de etiq: adr x19, main100
indirect par registre [xd] xd — [x20]
[xd, xn] xd + xn — [x20, x21]
indirect par registre indexé [xd, k] xd +k — [x20, 1]
[xd, xn, decal k] xd + (xn decal k) — [x20, x21, lsl 1]
ind. par reg. indexé pré-inc. [xd, k]! xd +k xd ← xd + k avant calcul [x20, 1]!
ind. par reg. indexé post-inc. [xd], k xd xd ← xd + k après calcul [x20], 1
relatif etiq adresse de etiq — main100

Autres instructions.
Code d’op. Syntaxe Effet Exemple
csel csel rd, rn, rm, cond si cond: rd ← rn , sinon: rd ← rm csel x19, x20, x21, eq

Logique et manipulation de bits.

▶ Les instructions lsl, lsr, asr et ror possèdent également une variante de 32 bits utilisant les registres wd , wn et wm (dans ce
cas, les 32 bits de poids fort sont mis à 0)
▶ Instructions, où i est une valeur immédiate de 12 bits et j est une valeur immédiate de 6 bits:

Code d’op. Syntaxe Effet Exemple

mvn mvn rd, rn rd ← ¬rn mvn x19, x20
and rd, rn, rm rd ← rn ∧ rm and x19, x20, x21
and and rd, rn, i rd ← rn ∧ i and x19, x20, 4
and rd, rn, rm, decal j rd ← rn ∧ (rm decal j) and x19, x20, x21, lsl 1
orr rd, rn, rm rd ← rn ∨ rm orr x19, x20, x21
orr orr rd, rn, i rd ← rn ∨ i orr x19, x20, 4
orr rd, rn, rm, decal j rd ← rn ∨ (rm decal j) orr x19, x20, x21, lsl 1
eor rd, rn, rm rd ← rn ⊕ rm eor x19, x20, x21
eor eor rd, rn, i rd ← rn ⊕ i eor x19, x20, 4
eor rd, rn, rm, decal j rd ← rn ⊕ (rm decal j) eor x19, x20, x21, lsl 1
bic rd, rn, rm rd ← rn ∧ ¬rm bic x19, x20, x21
bic bic rd, rn, i rd ← rn ∧ ¬i bic x19, x20, 4
bic rd, rn, rm, decal j rd ← rn ∧ ¬(rm decal j) bic x19, x20, x21, lsl 1
décalage de j bits vers la gauche:
lsl lsl xd, xn, j lsl x19, x20, 1
xd ⟨63, j⟩ ← xn ⟨63 − j, 0⟩; xd ⟨j − 1, 0⟩ ← 0
décalage de j bits vers la droite:
lsr lsr xd, xn, j lsr x19, x20, 1
xd ⟨63 − j, 0⟩ ← xn ⟨63, j⟩; xd ⟨63, 64 − j⟩ ← 0
décalage arithmétique de j bits vers la droite:
asr asr xd, xn, j asr x19, x20, 1
xd ⟨63 − j, 0⟩ ← xn ⟨63, j⟩; xd ⟨63, 64 − j⟩ ← xn ⟨63⟩
décalage circulaire de j bits vers la droite:
ror ror xd, xn, j ror x19, xn, 1
xd ← xn ⟨j − 1, 0⟩ xn ⟨63, j⟩
Registres (nombres en virgule flottante).
▶ Possède 32 registres double précision (64 bits) de la forme dn
▶ Chaque registre dn possède un sous-registre simple précision (32 bits) sn
▶ vn réfère au registre dn ou sn
▶ Conventions:

Registres Utilisation
d0 – d7 registres d’arguments et de retour de sous-programmes
d8 – d15 registres sauvegardés par l’appelé
d16 – d31 registres sauvegardés par l’appelant

Manipulation et arithmétique (nombres en virgule flottante).

▶ Les conditions de branchement sont les mêmes que pour les entiers et sont déterminées à partir de codes de condition mis
à jour par fcmp

Code d’op. Syntaxe Effet Exemple

ldr dn, a charge un nombre en virgule flottante double ldr d8, [x19]
ldr
précision de l’adresse a vers dn (8 octets)
ldr sn, a charge un nombre en virgule flottante simple ldr s8, [x19]
précision de l’adresse a vers sn (4 octets)
str dn, a stocke un nombre en virgule flottante double str d8, [x19]
str
précision de dn vers l’adresse a (8 octets)
str sn, a stocke un nombre en virgule flottante simple str s8, [x19]
précision de sn vers l’adresse a (4 octets)
fmov vd, vm vd ← vm fmov d8, d9
fmov
fmov vd, i vd ← i fmov d8, 1.5
fcmp vd, vm compare vd et vm fcmp d8, d9
fcmp
fcmp vd, i compare vd et i fcmp d8, 0.0
fadd fadd vd, vn, vm vd ← vn + vm fadd d8, d9, d10
fsub fsub vd, vn, vm vd ← vn − vm fsub d8, d9, d10
fmul fmul vd, vn, vm vd ← vn · vm fmul d8, d9, d10
fdiv fdiv vd, vn, vm vd ← vn /vm fdiv d8, d9, d10
√
fsqrt fsqrt vd, vn vd ← vn fsqrt d8, d9
fabs fabs vd, vn vd ← |vn | fabs d8, d9
convertit l’entier non signé dans rn vers un ucvtf d8, x19
nombre en virgule flottante dans vd (selon le ucvtf d8, w19
ucvtf ucvtf vd, rn
mode d’approximation configuré dans le registre de contrôle ucvtf s8, x19
FPCR) ucvtf s8, w19
convertit l’entier signé dans rn vers un scvtf d8, x19
nombre en virgule flottante dans vd (selon le scvtf d8, w19
scvtf scvtf vd, rn
mode d’approximation configuré dans le registre de contrôle scvtf s8, x19
FPCR) scvtf s8, w19
convertit le nombre en virgule flottante dans
fcvt fcvt vd, vn vn vers un nombre en virgule flottante d’une fcvt d8, s9
autre précision dans vd
Appels système.
▶ x8 : code numérique du service
▶ x0 à x5 : arguments
▶ svc 0: appel du service

Données statiques.

Segments de données Données

Pseudo-instruction Contenu .align k donnée suivante stockée à une adresse divisible par k
.section ".text" instructions .skip k réserve k octets
.section ".rodata" données en lecture seule .ascii s chaîne de caractères initialisée à s
.section ".data" données initialisées .asciz s chaîne de caractères initialisée à s suivi du carac. nul
.section ".bss" données non-initialisées .byte v octet initialisé à v
.hword v demi-mot initialisé à v
.word v mot initialisé à v
.xword v double mot initialisé à v
.single f nombre en virg. flottante simple précision initialisé à f
.double f nombre en virg. flottante double précision initialisé à f

Entrées/sorties (haut niveau).

▶ Affichage: printf(&format, val1 , val2 , . . .)
▶ Lecture: scanf(&format, &var1 , &var2 , . . .)
▶ Spécificateurs de format:

Famille Format Type

%ld entier décimal signé
%lu entier décimal non signé
Nombres sur 64 bits
%lX entier hexadécimal non signé
%lf nombre en virgule flottante
%d entier décimal signé
%u entier décimal non signé
Nombres sur 32 bits
%X entier hexadécimal non signé
%f nombre en virgule flottante
%hd entier décimal signé
Nombres sur 16 bits %hu entier décimal non signé
%hX entier hexadécimal non signé
%c caractère (1 octet)
Caractères
%s chaîne de caractères
 Annexe C:

Sommaire de l’architecture du NES

Registres.
▶ Possède 4 registres d’un octet
▶ Registre interne: p (registre d’état), contient des états et codes de conditions dont report/emprunt (1 octet)
▶ Registre interne: pc (compteur d’instruction), contient l’adresse de la prochaine instruction (2 octets)

Nom Utilisation principale

a accumulateur, utilisé comme opérande et valeur de retour des opé-
rations arithmétiques et logiques
x utilisé comme compteur ou comme index pour l’adressage indexé
y utilisé comme compteur ou comme index pour l’adressage indexé
s pointeur de pile (pointe vers 010016 + s)

Valeurs immédiates.
▶ #: valeur numérique, sans #: adresse
▶ $: valeur hexadécimale
expression valeur
▶ %: valeur binaire
#5 510
▶ Exemples: #$FF FF16
#%00010011 000100112
$FF adresse FF16

Modes d’adressage.
Nom. Syntaxe Adresse Exemple
absolu i i lda $D010
i, x i+x lda $D010, x
indexé par x
etiq, x etiq + x lda tab, x
i, y i+y lda $D010, y
indexé par y
etiq, y etiq + y lda tab, y

Accès mémoire.
▶ Instructions, où mem1 [a] dénote l’octet situé à l’adresse a de la mémoire principale:

Code d’op. Syntaxe Effet Exemple

lda #i a←i lda #42
lda
lda adr a ← mem1 [adr] lda var
ldx #i x←i ldx #42
ldx
ldx adr x ← mem1 [adr] ldx var
ldy #i y←i ldy #42
ldy
ldy adr y ← mem1 [adr] ldy var
sta sta adr mem1 [adr] ← a sta var
stx stx adr mem1 [adr] ← x stx var
sty sty adr mem1 [adr] ← y sty var
txa txa a←x txa
tax tax x←a tax
tya tya a←y tya
tay tay y←a tay
txs txs s←x txs
tsx tsx x←s tsx
pha pha empile a sur la pile pha
pla pla dépile le premier octet de la pile vers a pla
Arithmétique.
Code d’op. Syntaxe Effet Exemple
adc #i a ← a + i + report lda #1
adc
adc adr a ← a + mem1 [adr] + report adc var
sbc #i a ← a − i − emprunt sbc #1
sbc
sbc adr a ← a − mem1 [adr] − emprunt sbc var
clc clc report ← 0 (utile avant adc) clc
sec sec emprunt ← 0 (utile avant sbc) sec
inx inx x←x+1 inx
iny iny y←y+1 iny
inc inc adr mem1 [adr] ← mem1 [adr] + 1 inc var
dec dec adr mem1 [adr] ← mem1 [adr] − 1 dec var

Logique.
Code d’op. Syntaxe Effet Exemple
asl asl adr décalage logique de mem1 [adr] d’un asl var
bit à gauche (directement en mémoire)
lsr lsr adr décalage logique de mem1 [adr] d’un lsr var
bit à droite (directement en mémoire)
and #i a←a∧i and #%00100011
and
and adr a ← a ∧ mem1 [adr] and var
ora #i a←a∨i ora #%00100011
ora
ora adr a ← a ∨ mem1 [adr] ora var
eor #i a←a⊕i eor #%00100011
eor
eor adr a ← a ⊕ mem1 [adr] eor var

Comparaisons et branchements.
Code d’op. Syntaxe Effet Exemple
cmp #i compare a et i cmp #0
cmp
cmp adr compare a et mem1 [adr] cmp var
cpx #i compare x et i cpx #0
cpx
cpx adr compare x et mem1 [adr] cpx var
cpy #i compare y et i cpy #0
cpy
cpy adr compare y et mem1 [adr] cpy var
beq beq etiq branche à etiq: si = beq boucle
bne bne etiq branche à etiq: si ̸= bne boucle
jmp jmp etiq branche à etiq: jmp boucle
jsr jsr etiq branche au sous-programme etiq: jsr func
et empile l’adresse de retour
rts rts branche à l’adresse de retour d’un rts
sous-programme
rti rti branche à l’adresse de retour d’une rti
interruption