Laboratoire 8 - Routines

Sommaire

ASCII vers entier

Écrire la routine atoi (dans un programme atoi.s) qui prend un paramètre une chaîne de caractère représentant un entier décimal et retourne l’entier correspondant. Note: la conversion s’arrête quand un non chiffre est rencontré. Si aucun chiffre n’est rencontré, 0 est retourné.

Entrée: a0 adresse de la chaîne
Sortie: a0 nombre entier signé

Exemples:

.data
test1:	.string "123" # atoi doit donner 123
test2:	.string "toto" # atoi doit donner 0
test3:	.string "42toto"  # atoi doit donner 42

Somme des arguments

Écrire un programme soma.s qui fait la somme de tous les arguments de la ligne de commande en utilisant atoi pour les convertir en entier.

3 Tours de Hanoi

Implémentez la solution récursive du célèbre programme des Tours de Hanoï.

Pseudocode:

void main() {
    int n = readInt();
    Hanoï(n, 1, 3, 2);
}

void Hanoï(int n, int d, int a, int i) {
    if (n > 0) {
        Hanoï(n-1, d, i, a);
        System.out.printf("Deplacer le disque de %d vers %d.\n", d, a);
        Hanoï(n-1, i, a, d);
    }
}

Contrainte: utilisez printf de libs.s pour l’affichage.

Si vous n’avez pas de tours de Hanoï sous la main, testez votre solution sur http://championmath.free.fr/tourhanoi.htm par exemple.

Exemple

Pour 5, cela devait donner

Deplacer le disque de 1 vers 3.
Deplacer le disque de 1 vers 2.
Deplacer le disque de 3 vers 2.
Deplacer le disque de 1 vers 3.
Deplacer le disque de 2 vers 1.
Deplacer le disque de 2 vers 3.
Deplacer le disque de 1 vers 3.
Deplacer le disque de 1 vers 2.
Deplacer le disque de 3 vers 2.
Deplacer le disque de 3 vers 1.
Deplacer le disque de 2 vers 1.
Deplacer le disque de 3 vers 2.
Deplacer le disque de 1 vers 3.
Deplacer le disque de 1 vers 2.
Deplacer le disque de 3 vers 2.
Deplacer le disque de 1 vers 3.
Deplacer le disque de 2 vers 1.
Deplacer le disque de 2 vers 3.
Deplacer le disque de 1 vers 3.
Deplacer le disque de 2 vers 1.
Deplacer le disque de 3 vers 2.
Deplacer le disque de 3 vers 1.
Deplacer le disque de 2 vers 1.
Deplacer le disque de 2 vers 3.
Deplacer le disque de 1 vers 3.
Deplacer le disque de 1 vers 2.
Deplacer le disque de 3 vers 2.
Deplacer le disque de 1 vers 3.
Deplacer le disque de 2 vers 1.
Deplacer le disque de 2 vers 3.
Deplacer le disque de 1 vers 3.

Extra: appel terminal

Il est possible de remplacer le second jal hanoi, qui est terminal (tail call) par un simple j. Ceci nécessite d’ajouter une étiquette vers laquelle brancher (et éventuellement préparer les arguments)

Semaine 2

Majusculisation

Écrire un programme upper.s qui:

Lit deux chaînes str1 et str2 de 80 caractères maximum (81 octets en contant le ‘\0’ final).
Les convertit en majuscules.
Affiche la seconde chaîne puis la première.

Contraintes:

Implémentez un routine uppercase qui prend l’adresse d’une chaîne et la modifie pour la convertir en majuscule.
Les deux chaînes sont allouées dans les données statiques (.data).
Utilisez readString et printString de libs.s pour lire et écrire les chaînes (et non les appels système de RARS).

Majusculisation dans la pile

Adaptez upper.s pour allouer les deux chaînes dans la pile.
Utilisez des symboles (et .eqv) pour identifier les deux chaînes.
- Nommez le décalage dans la pile qui permet de retrouver les chaines.

Fold

Implémentez un programme fold.s qui fournit la routine fold (appelée aussi reduce dans d’autres langages).

fold ressemble à l’itérateur each vu en cours mais possède un paramètre supplémentaire. fold applique successivement la routine passée en paramètre à chacun des éléments et retourne un résultat accumulé.

a0: t l’adresse du tableau
a1: n le nombre d’éléments du tableau
a2: s la taille d’un élément (en octets)
a3: r l’adresse de la routine à appeler
a4: v une valeur initiale
retour: a0 la valeur accumulée

La routine pointée par r est appelée avec deux arguments:

a0: le résultats précédent.
Au premier appel, on utilise v, la valeur initiale
a1: l’adresse de l’élément courant.
retour: a0 qui sera utilisé comme premier paramètre de l’appel suivant.
Au dernier appel, a0 sera retourné par fold

Pseudocode:

fold(t, n, s, r, v) {
	while (n>0) {
		v = r(v, t)
		t += s;
		n--;
	}
	return v;
}

Somme

.data
	.eqv tlen, 10 # nombre d'éléments du tableau t
	.eqv esize, 4 # taille d'un élément de t
t:	.word 8, 1, 2, 10, 5, 5, -2, 2, 5, 4

.text

# somme: additionne a0 et le mot à l'adresse a1
somme:
	lw a1, (a1)
	add a0, a0, a1
	ret

Utilisez fold pour calculer la somme des éléments du tableau.

a3 doit être somme
a4 doit être 0.

Minimum

Utilisez fold pour déterminer l’élément minimum de t.

Développez la routine min à utiliser pour a3.
Note: a4 doit être la première case du tableau.

Adressage

Soit le code RISC-V 64 bits suivant:

	# Appelant (programme principal)
	#
	# call: 0x0000000000400008
	# foo:  0x0000000000400014
	# sp:   0x000000007FFFEFFC
	
	li a0, 42
	li a1, -2
call:
	jal foo
	li a7, 10
	ecall

	# Appelé (routine)
foo:
	# Prologue
	addi sp, sp, -16
	sd ra, 0(sp)
	sw a0, 8(sp)
	sw a1, 12(sp)
	
	lb a2, 13(sp)
	
	ebreak	# <-- ICI
	
	# [...]

Les adresses des étiquettes call et foo sont données, ainsi que la valeur initiale du registre sp.

Déterminez lors du ebreak (ICI):

les valeurs des registres ra et sp (16 chiffres hexadécimaux)
les 16 octets du contenu de la pile (en commençant à l’adresse sp)
la valeur du registre a2 (16 chiffres hexadécimaux)

Validez ensuite votre réponse avec le simulateur RARS