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

  1. # Lire un tableau d’entiers, le trier, l’afficher
  2.  
  3. .globl _start  # adresse de démarrage du programme pour l’éditeur de liens
  4.  
  5. _start:
  6.  
  7. # Demander taille du tableau (< 17)
  8.     la   a1, message1 # charger l’adresse
  9.     jal  ra, print_str # affichage de la chaîne
  10. # Lecture de la taille (< 17)
  11.     jal  ra, read_int # a1 <-- l’entier lu
  12.     la   x30, nb_items
  13.     sw   a1, 0(x30) # sauve a1 dans nb_items
  14. # Remplissage du tableau
  15.     la   a0, tableau
  16.     jal  ra, remplir
  17. # Affichage du tableau
  18.     la   a0, tableau
  19.     lw   a1, nb_items
  20.     jal  ra, afficher
  21.  
  22. # Tri du tableau
  23.     la   a0, tableau
  24.     lw   a1, nb_items
  25.     jal  ra, bubble_sort
  26.  
  27. # Affichage du tableau trié
  28.     la   a0, tableau
  29.     lw   a1, nb_items
  30.     jal  ra, afficher
  31.  
  32. exit:
  33. # Fin du programme
  34.     addi a0, x0, 0  # code de retour 0
  35.     addi a7, x0, 93 # le code de commande 93
  36.     ecall           # Appel Linux pour finir
  37.  
  38. #####
  39. # remplissage du tableau
  40. # a0 : pointeur sur première case du tableau
  41. # a1 : nombre de cases à remplir
  42. remplir:
  43.     addi sp, sp, -4
  44.     sw   ra, 0(sp)    # sauvegarde ra sur la pile
  45.  
  46.     mv   x29, a0     # x29 -> tableau
  47.     mv   x28, a1     # i <-- nb cases à remplir
  48.  
  49. loop2:
  50. # Lecture d’un entier
  51.     ble  x28, x0, exit2 # rempli
  52.     la   a1, message2 # charger l’adresse
  53.     jal  ra, print_str
  54.     jal  ra, read_int  # a1 <-- l’entier lu
  55.     sw   a1, 0(x29)   # tableau[i] <-- l’entier lu
  56.     addi x28, x28, -1 # décrément de i
  57.     addi x29, x29, 4  # case suivante
  58.     j    loop2
  59.  
  60. # Retour
  61. exit2:
  62. # Retour chariot pour y voir clair
  63.     la   a1, saut
  64.     jal  ra, print_str # on y voit plus clair
  65.     lw   ra, 0(sp)    # restauration de ra depuis la pile
  66.     addi sp, sp,4    #  pour l’adresse de retour
  67.     ret
  68.  
  69. #####
  70.  # affichage du tableau
  71.  # a0 : pointeur sur première case du tableau
  72.  # a1 : nombre de cases à afficher
  73. afficher:
  74.     addi sp, sp, -4
  75.     sw   ra, 0(sp)    # sauvegarde ra sur la pile
  76.  
  77.     addi x29, a0, 0 # x29 -> tableau
  78.     addi x30, a1, 0 # x30 nb items à afficher
  79.     addi x28, x0, 0 # i <-- 0
  80.  
  81. loop3:
  82. # Affichage d’un entier
  83.     lw   a0, 0(x29)    # a0 <-- l’entier à afficher
  84.     jal  ra, print_int
  85. # Retour chariot
  86.     la   a1, saut
  87.     jal  ra, print_str
  88.    
  89.     addi x28, x28, 1 # incrément indice boucle
  90.     bge  x28, x30, exit3 # affiché
  91.     addi x29, x29, 4 # case suivante
  92.     j    loop3
  93.  
  94. # Retour
  95. exit3:
  96. # Retour chariot pour y voir clair
  97.     la   a1, saut
  98.     jal  ra, print_str # on y voit plus clair
  99.     lw   ra, 0(sp)  # restauration de ra depuis la pile
  100.     addi sp, sp,4   #  pour l’adresse de retour
  101.     ret
  102. #####
  103. .include "read-print.s"
  104. .include "strings.s"
  105. .include "bubble-sort.s"
  106. ######
  107.  
  108. .data
  109. .align    2
  110. tableau:  .word    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
  111. nb_items: .word    0
  112. saut:     .string "\n"
  113. message1: .string "Entrez le nombre de cases du tableau : \n"
  114. message2: .string "Entrez un nombre entier : \n"
  115. message3: .string "Oui, on est passé là !\n"

Télécharger

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

  1. ######
  2.  # Tri à bulles, d’après Patterson et Hennessy
  3.  
  4. bubble_sort:
  5.     addi sp, sp, -20 # accroît la pile pour 5 registres
  6.     sw   x1, 16(sp)  # sauve l’adresse de retour sur la pile
  7.     sw   x22, 12(sp) # x22 sur la pile
  8.     sw   x21, 8(sp)  # x21 sur la pile
  9.     sw   x20, 4(sp)  # x20 sur la pile
  10.     sw   x19, 0(sp)  # x19 sur la pile
  11.  
  12.     addi x21, x10, 0 # x21 <-- x10 v, vecteur à trier
  13.     addi x22, x11, 0 # x22 <-- x11 n, nb de cases à trier
  14.     addi x19, x0, 0  # i <-- 0
  15. for1tst:
  16.     bge  x19, x22, exit11 # si >= n exit11
  17.     addi x20, x19, -1 # j <-- i - 1
  18. for2tst:
  19.     blt  x20, x0, exit12 # si j < 0 exit12
  20.     slli x5, x20, 2  # x5 <-- j * 4
  21.     add  x5, x21, x5 # x5 <-- v + j * 4
  22.     lw   x6, 0(x5)   # x6 <-- v[j]
  23.     lw   x7, 4(x5)   # x7 <-- v[j + 1]
  24.     ble  x6, x7, exit12 # si x6 < x7 exit12
  25.     addi x10, x21, 0 # paramètre v -> swap
  26.     addi x11, x20, 0 # paramètre j -> swap
  27.     jal  x1, swap    # appel swap
  28.     addi x20, x20, -1 # j for2tst
  29.     jal  x0, for2tst # -> for2tst
  30. exit12:
  31.     addi x19, x19, 1 # i <-- i+1
  32.     jal  x0, for1tst # -> for1tst
  33. exit11:
  34.     add  x10, x0, x21# x10 -> tableau
  35.     lw   x19, 0(sp)  # restaure x19
  36.     lw   x20, 4(sp)  # restaure x20
  37.     lw   x21, 8(sp)  # restaure x21
  38.     lw   x22, 12(sp) # restaure x22
  39.     lw   x1, 16(sp)  # restaure adresse de retour
  40.     addi sp, sp, 20  # restaure pointeur de pile
  41.  
  42.     jalr x0, 0(x1)   # retour à l’appelant
  43.  
  44. ######
  45.  
  46. swap:
  47.     slli x6, x11, 2  # x6 <-- k * 4
  48.     add  x6, x10, x6 # x6 <-- v + (k * 4)
  49.     lw   x5, 0(x6)   # x5 <-- v[k]
  50.     lw   x7, 4(x6)   # x7 <-- v[k + 1]
  51.     sw   x7, 0(x6)   # v[k] <-- x7
  52.     sw   x5, 4(x6)   # x[k + 1] <-- x5
  53.     jalr x0, 0(x1)   # retour à l’appelant
  54.  
  55. ######

Télécharger