le tri de tableau en mips (assemblée)

Codage direct de l'assemblée est une douleur. Ce que je faire à la place est de commencer avec un algorithme (psuedocode ou code) de traduire systématiquement, comme si je suis un compilateur. Je vais ignorer l'entrée et la sortie des trucs et de se concentrer sur une fonction qui trie.

Vous ferait appel à un haut niveau lanaguage comme C:

insertionsort(data, N);

où data est un tableau d'entiers et N le nombre d'éléments (il n'y a pas les attributs de taille au niveau des machines).

Car les appels de fonction rien, il a besoin d'aucun cadre de pile. Observer la norme MIPS conventions de l'aide $t registres, de sorte que vous ne sont pas bousiller quelque chose de quelqu'un d'autre se passe dans les paramètres dans $a0 et $a1 dans cet ordre.

Étape 1: obtenir un algorithme. Voici une de [Wikipedia][1] pour le tri par insertion:

i ← 1
while i < length(A)
    x ← A[i]
    j ← i - 1
    while j >= 0 and A[j] > x
        A[j+1] ← A[j]
        j ← j - 1
    end while
    A[j+1] ← x
    i ← i + 1
end while

Etape 2: coller dans un fichier texte, mettez toutes les lignes dans les commentaires et convertir systématiquement à l'assemblée. J'ai utiliser des modèles pour des choses comme les boucles qui prennent la conjecture hors de codage (voir mon livre gratuit pour des exemples). Je vais juste donner le produit fini ici; appeler, vous avez besoin de mettre l'adresse de début du tableau en $a0 et sa taille en $a1, puis jal insertionsort:

# algorithm for insertion sort
# from https://en.wikipedia.org/wiki/Insertion_sort
# usage: insertionsort (a,N)
# pass array start in $a0, size in elements, N in $a1
# Philip Machanick
# 30 April 2018

            .globl insertionsort

            .text

# leaf function, no stack frame needed
# Registers:
#   $a0: base address; $a1: N
#   $t0: i
#   $t1: j
#   $t2: value of A[i] or A[j]
#   $t3: value of x (current A[i])
#   $t4: current offset of A[i] or A[j] as needed
insertionsort:
# i ← 1
       li $t0, 1
# while i < N
       j Wnext001        # test before 1st iteration
Wbody001:                # body of loop here
      sll $t4, $t0, 2    # scale index i to offset
      add $t4, $a0, $t4  # address of a[i]
#     x ← A[i]
      lw $t3, 0($t4)
#     j ← i - 1
      addi $t1, $t0, -1
#     while j >= 0 and A[j] > x
       j Wnext002        # test before 1st iteration
Wbody002:                # body of loop here
#         A[j+1] ← A[j]
          sll  $t4, $t1, 2        # scale index j to offset
          add $t4, $a0, $t4       # address of a[j]
          lw $t2, 0($t4)          # get value of A[j]
          addi $t4, $t4, 4        # offset of A[j+1]
          sw $t2, 0($t4)          # assign to A[j+1]
#         j ← j - 1
          addi $t1, $t1, -1
#     end while
Wnext002: # construct condition, j >= 0 and A[j] > x
          blt $t1, $zero Wdone002 # convert to: if j < 0 break from loop #####
          sll  $t4, $t1, 2        # scale index j to offset
          add $t4, $a0, $t4       # address of a[j]
          lw $t2, 0($t4)          # A[j]
          bgt $t2, $t3, Wbody002  # no need to test j >= 0, broke from loop already if false
Wdone002:                         # branch here to short-circuit and
#     A[j+1] ← x
          add  $t4, $t1, 1        # scale index j+1 to offset
          sll  $t4, $t4, 2        # scale index j to offset
          add $t4, $a0, $t4       # address of a[j+1]
          sw $t3, 0($t4)          # A[j+1] becomes x
#     i ← i + 1
          addi $t0, $t0, 1
# end while
Wnext001: blt $t0,$a1, Wbody001  # i < N easy this time
          jr $ra                 # return to caller

Plus longtemps que les autres exemples – mais si vous commencez à partir d'un algorithme et de le traduire, vous êtes moins susceptible de se tromper. Cela peut aller dans un fichier séparé si votre assembleur respecte la .globl la directive, ce qui rend le nom visible dans d'autres fichiers.

[1]: https://en.wikipedia.org/wiki/Insertion_sort – en fait, à partir de Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Article 2.1: le tri par Insertion". Introduction aux Algorithmes (2e ed.). MIT Press et McGraw-Hill. pp. 15-21