Munis de la lecture et de l’écriture de nombres (à la console), ainsi que de chaînes de caractères (de longueur fixe), éventuellement dans des fichiers, nous pouvons créer des tableaux de nombres afin de nous amuser à les trier. Commençons par le tri à bulles, obligeamment procuré par Messieurs Patterson et Hennessy (au passage je salue Alfred Aho et Jeffrey Ullman, qui viennent de recevoir le prix Turing qui avait en 2017 été décerné à Hennessy et Patterson). Voici le programme principal, qui demande la saisie du tableau de nombres au clavier, appelle le programme de tri, puis affiche le résultat trié.
# Lire un tableau d’entiers, le trier, l’afficher
.globl _start # adresse de démarrage du programme pour l’éditeur de liens
_start:
# Demander taille du tableau (< 17)
la a1, message1 # charger l’adresse
jal ra, print_str # affichage de la chaîne
# Lecture de la taille (< 17)
jal ra, read_int # a1 <-- l’entier lu
la x30, nb_items
sw a1, 0(x30) # sauve a1 dans nb_items
# Remplissage du tableau
la a0, tableau
jal ra, remplir
# Affichage du tableau
la a0, tableau
lw a1, nb_items
jal ra, afficher
# Tri du tableau
la a0, tableau
lw a1, nb_items
jal ra, bubble_sort
# Affichage du tableau trié
la a0, tableau
lw a1, nb_items
jal ra, afficher
exit:
# Fin du programme
addi a0, x0, 0 # code de retour 0
addi a7, x0, 93 # le code de commande 93
ecall # Appel Linux pour finir
#####
# remplissage du tableau
# a0 : pointeur sur première case du tableau
# a1 : nombre de cases à remplir
remplir:
addi sp, sp, -4
sw ra, 0(sp) # sauvegarde ra sur la pile
mv x29, a0 # x29 -> tableau
mv x28, a1 # i <-- nb cases à remplir
loop2:
# Lecture d’un entier
ble x28, x0, exit2 # rempli
la a1, message2 # charger l’adresse
jal ra, print_str
jal ra, read_int # a1 <-- l’entier lu
sw a1, 0(x29) # tableau[i] <-- l’entier lu
addi x28, x28, -1 # décrément de i
addi x29, x29, 4 # case suivante
j loop2
# Retour
exit2:
# Retour chariot pour y voir clair
la a1, saut
jal ra, print_str # on y voit plus clair
lw ra, 0(sp) # restauration de ra depuis la pile
addi sp, sp,4 # pour l’adresse de retour
ret
#####
# affichage du tableau
# a0 : pointeur sur première case du tableau
# a1 : nombre de cases à afficher
afficher:
addi sp, sp, -4
sw ra, 0(sp) # sauvegarde ra sur la pile
addi x29, a0, 0 # x29 -> tableau
addi x30, a1, 0 # x30 nb items à afficher
addi x28, x0, 0 # i <-- 0
loop3:
# Affichage d’un entier
lw a0, 0(x29) # a0 <-- l’entier à afficher
jal ra, print_int
# Retour chariot
la a1, saut
jal ra, print_str
addi x28, x28, 1 # incrément indice boucle
bge x28, x30, exit3 # affiché
addi x29, x29, 4 # case suivante
j loop3
# Retour
exit3:
# Retour chariot pour y voir clair
la a1, saut
jal ra, print_str # on y voit plus clair
lw ra, 0(sp) # restauration de ra depuis la pile
addi sp, sp,4 # pour l’adresse de retour
ret
#####
.include "read-print.s"
.include "strings.s"
.include "bubble-sort.s"
######
.data
.align 2
tableau: .word 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
nb_items: .word 0
saut: .string "\n"
message1: .string "Entrez le nombre de cases du tableau : \n"
message2: .string "Entrez un nombre entier : \n"
message3: .string "Oui, on est passé là !\n"Et voici la procédure de tri à bulles (les autres procédures ont été publiées dans l’article précédent, cf. le lien ci-dessus).
######
# Tri à bulles, d’après Patterson et Hennessy
bubble_sort:
addi sp, sp, -20 # accroît la pile pour 5 registres
sw x1, 16(sp) # sauve l’adresse de retour sur la pile
sw x22, 12(sp) # x22 sur la pile
sw x21, 8(sp) # x21 sur la pile
sw x20, 4(sp) # x20 sur la pile
sw x19, 0(sp) # x19 sur la pile
addi x21, x10, 0 # x21 <-- x10 v, vecteur à trier
addi x22, x11, 0 # x22 <-- x11 n, nb de cases à trier
addi x19, x0, 0 # i <-- 0
for1tst:
bge x19, x22, exit11 # si >= n exit11
addi x20, x19, -1 # j <-- i - 1
for2tst:
blt x20, x0, exit12 # si j < 0 exit12
slli x5, x20, 2 # x5 <-- j * 4
add x5, x21, x5 # x5 <-- v + j * 4
lw x6, 0(x5) # x6 <-- v[j]
lw x7, 4(x5) # x7 <-- v[j + 1]
ble x6, x7, exit12 # si x6 < x7 exit12
addi x10, x21, 0 # paramètre v -> swap
addi x11, x20, 0 # paramètre j -> swap
jal x1, swap # appel swap
addi x20, x20, -1 # j for2tst
jal x0, for2tst # -> for2tst
exit12:
addi x19, x19, 1 # i <-- i+1
jal x0, for1tst # -> for1tst
exit11:
add x10, x0, x21# x10 -> tableau
lw x19, 0(sp) # restaure x19
lw x20, 4(sp) # restaure x20
lw x21, 8(sp) # restaure x21
lw x22, 12(sp) # restaure x22
lw x1, 16(sp) # restaure adresse de retour
addi sp, sp, 20 # restaure pointeur de pile
jalr x0, 0(x1) # retour à l’appelant
######
swap:
slli x6, x11, 2 # x6 <-- k * 4
add x6, x10, x6 # x6 <-- v + (k * 4)
lw x5, 0(x6) # x5 <-- v[k]
lw x7, 4(x6) # x7 <-- v[k + 1]
sw x7, 0(x6) # v[k] <-- x7
sw x5, 4(x6) # x[k + 1] <-- x5
jalr x0, 0(x1) # retour à l’appelant
######