im in a class learning assembly using mips. I am working on sorting an array of numbers and i think that I have the method working correctly, but just a bit of trouble. I do not know how to check when im sorted fully. Im using a pretty rudimentary method for sorting, but that is all that we have learned thus far. Also, i do not know how to output the numbers to check to see if it is sorted. Im used to Java and such so assembly is kinda throwing me for a spin. Here is my code thus far:
.text
.globl main
main: la $a0, Array # sets the base address of the array to $a0
loop: lw $t0, 0($a0) # sets $t0 to the current element in array
lw $t1, 4($a0) # sets $t1 to the next element in array
blt $t1, $t0, swap # if the following value is greater, swap them
addi $a0, $a0, 4 # advance the array to start at the next location from last time
j loop # jump back to loop so we can compare next two elements
swap: sw $t0, 4($a0) # store the greater numbers contents in the higher position in array (swap)
sw $t1, 0($a0) # store the lesser numbers contents in the lower position in array (swap)
li $a0, 0 # resets the value of $a0 back to zero so we can start from beginning of array
j loop # jump back to the loop so we can go through and find next swap
.data
Array: .word 14, 12, 13, 5, 9, 11, 3, 6, 7, 10, 2, 4, 8, 1
thanks for any help guys!
This link explains how to print to the screen in a MIPS simulator like QTSPIM or MARS.
As for the code, there were a few bugs. The line li $a0, 0 is overwriting the work done by the initial la $a0, Array instruction because the li is setting the base address of your array to 0. Instead, you should move the la instruction into the loop so that $a0 is properly reset to the base address of Array after iterating over the entire array, and remove the li instruction. You also will need to add in a condition for when your program has completed the sort. I would suggest the following revisions (tested with SPIM):
main:
la $t0, Array # Copy the base address of your array into $t1
add $t0, $t0, 40 # 4 bytes per int * 10 ints = 40 bytes
outterLoop: # Used to determine when we are done iterating over the Array
add $t1, $0, $0 # $t1 holds a flag to determine when the list is sorted
la $a0, Array # Set $a0 to the base address of the Array
innerLoop: # The inner loop will iterate over the Array checking if a swap is needed
lw $t2, 0($a0) # sets $t0 to the current element in array
lw $t3, 4($a0) # sets $t1 to the next element in array
slt $t5, $t2, $t3 # $t5 = 1 if $t0 < $t1
beq $t5, $0, continue # if $t5 = 1, then swap them
add $t1, $0, 1 # if we need to swap, we need to check the list again
sw $t2, 4($a0) # store the greater numbers contents in the higher position in array (swap)
sw $t3, 0($a0) # store the lesser numbers contents in the lower position in array (swap)
continue:
addi $a0, $a0, 4 # advance the array to start at the next location from last time
bne $a0, $t0, innerLoop # If $a0 != the end of Array, jump back to innerLoop
bne $t1, $0, outterLoop # $t1 = 1, another pass is needed, jump back to outterLoop
Be sure to check out this link for additional examples and explanations on what each MIPS instruction does.
Coding direct in assembly is a pain. What I do instead is start with an algorithm (psuedocode or actual code) then translate systematically, as if I am a compiler. I will ignore the input and output stuff and focus on a function that sorts.
You would call in a high-level lanaguage like C as:
insertionsort(data, N);
where data is an integer array and N the number of elements (there are no size attributes at machine level).
Since the function calls nothing, it needs no stack frame. Observe the standard MIPS conventions of using $t registers so you are not trashing anything anyone else relies on and pass in parameters in $a0 and $a1 in that order.
Step 1: get an algorithm. Here’s one from [Wikipedia][1] for insertion sort:
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
Step 2: paste into a text file, turn all lines into comments and systematically convert to assembly. I use templates for things like loops that take the guess work out of coding (see my free book for examples). I will just give the finished product here; to call it, you need to put the start address of the array into $a0 and its size in $a1, then 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
Longer than the other examples – but if you start from an algorithm and translate you are less likely to go wrong. This can go in a separate file if your assembler respects the .globl directive, which makes the name visible in other files.
[1]: https://en.wikipedia.org/wiki/Insertion_sort – actually from Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 2.1: Insertion sort". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 15–21
.data
value: .word 0x3
Array: .word 0x14, 0x12, 0x13, 0x05
.text
.globl main
main: la $a0, Array
lw $t3,value
l1: lw $t0, 0($a0)
lw $t1, 4($a0)
blt $t1, $t0, swap
addi $a0, $a0, 4
addi $t3,$t3,-1
bne $t3,$zero,l1
jr $ra
swap: sw $t0, 4($a0)
sw $t1, 0($a0)
j l1
