MIPS assembly sorting

Question

I've been tasked with sorting and printing a hardcoded integer array using MIPS assembly and QTSpim. I've been trying to follow the other similar questions posted here but I am struggling to understand where I am now going wrong. I'm getting "Exception occurred at PC=0x00400068 Bad address in data/stack read: 0x10040000" QTSpim highlights "[80000180] 0001d821 addu $27, $0, $1 ; 90: move $k1 $at # Save $at" I'm fairly new at assembly, so any help is much appreciated!

.data
myarray: .word 4, 1, 3, 2, 16, 9, 10, 14, 8, 7
arraysize: .word 10
str1: .asciiz "Unsorted array: "
str2: .asciiz "\nSorted array: "
nline: .asciiz "\n"

.text
.globl main

main:
    li      $v0, 0
    la      $t1, myarray #Coping base address of array into $t1
loop1: #Printing unsorted array
    bge $t0, 10, sortFlag
    lw      $t2, 0($t1) # loading word from addrs, then goes to the next addrs
    addi    $t1, $t1, 4

    li      $v0, 1 # Syscall to print value 
    move    $a0, $t2
    syscall
    li      $a0, 32 # Syscall number for printing space
    li      $v0, 11  
    syscall

    addi    $t0, $t0, 1 # Incrementing counter
    j      loop1
sortFlag:
    add $t6, $0, $0 # t6 holds flag to determine whether the list is sorted
    la  $a1, myarray # Sets $a1 to base address of array
sort:
    lw  $t2, 0($a1) #Sets $t0 to current element in array
    lw  $t3, 4($a1) #Sets $t1 to next element in array
    slt $t5, $t2, $t3 # Sets $t5 if $t0 < $t1
    beq $t5, $0, swap #Swaps if $t5 = 1
    add $t6, $0, 1 #Check list again if swapped
    sw  $t2, 4($a1) #Storing greater numbers in higher position in the array
    sw  $t3, 0($a1) #Storing lesser numbers in lower position in the array
swap:
    addi $a1, $a1, 4 #Moves to next location in array
    bne  $a1, $t6, sort #If $a0 doesn't equal the end of the array, jump to sort
    bne  $t6, $0, sortFlag #If $t6 = 1, jump to sortFlag
loop2: #Repeated from above to re-print the now sorted array
    bge     $t7, 10, exit

    lw      $t4, 0($t1)
    addi    $t1, $t1, 4

    # syscall to print value
    li      $v0, 1      
    move    $a2 $t4
    syscall

    li      $a2, 32
    li      $v0, 11  
    syscall

    addi    $t7, $t7, 1
    j      loop2
 exit:
    li      $v0, 10
    syscall

Answer 1

Here's what I gather from that error message (I could be wrong since I've never used QTspim)

"[80000180] 0001d821 addu $27, $0, $1 ; 90: move $k1 $at # Save $at"

Based on the registers in use ($k1 is used by the Linux kernel, and $at is a temporary register that is used to implement pseudo-instructions), as well as this instruction not being in your source code anywhere, I'm thinking something went wrong with one of your syscalls. Now that I think about it, you forgot a comma here: move $a2 $t4. Try fixing that and see what happens.

Answer 2

It is telling you that the instruction executing at 0x00400068 is attempting to use an illegal memory location.  (Just ignore the QtSpim highlights.)

So, use the simulator to identify which instruction is at 0x00400068.

Once you know which instruction is bad, you can identify the base register that is bad.

Once you know which base register is bad, you can find out how it got that way, by using the debugger to observe execution.

---

Values you use for pointers to words need to start aligned and be incremented by multiples of 4.  However, you're doing these things, so that doesn't appear to be an issue here.

So, what it could be then is that the loop doesn't terminate properly, and the algorithm continues on and eventually runs off the end of memory.  This hunch is also supported by the evidence of the offending address 0x10040000.  This address is near or at the end of global data memory, which usually starts at 01x0010000.  So, with your small array of 10, you shouldn't be reaching that high in memory.

---

Developing & Debugging tips:

• When testing an algorithm, try it with the smallest possible input.  For example, an array of 0 elements.  With word data, usually that can be done by merely setting some count to 0, but with strings, as they are nul-terminated, you may need to test first with a smaller string.  This will make debugging loops and recursion much easier.  Once you're sure its working for 0 elements, then move on to 1 element, and so on.
  Zero (or sometimes 1 or 2) tests edge cases, so getting that working should be a priority.

• Write small parts of code at a time, and debug them as you develop the program.  Don't wait until you have a whole program put together to try running it.  When writing code always single step any new code you write to confirm it is working.

• Single step and observe each instruction and after each, verify it does what you're expecting and nothing you're not expecting.

• Get to know your data and its addresses.  In the debugger before you step the first line of code, you can inspect your data section and see your global labels and the content there.

• Don't expect your code to work the first time you run it if you haven't followed practices like these.  If any one instruction is wrong, the program won't work, and typos are easy to make especially in assembly.

• Develop algorithms in high level language, test your algorithm to make sure it works.  And only then translate to assembly.
  This approach decouples algorithm research & development from assembly research, development and programming.  (The range of topics you can research is larger since the algorithm isn't constrained to assembly and the translation to assembly isn't constrained by the algorithm.)  This approach also ensures you'll only have typos and such to deal with in assembly — instead of algorithmic problems, which are way harder to debug in assembly.

• Translate your final algorithm into assembly quite literally.  Don't optimize in the process.  If you want to tweak the algorithm, do that in C first then knowing it works, take it to assembly.

---

Also you have variables in registers that you're relying on the simulator to initialize to 0, which is generally bad practice.  This reliance basically only works in very small programs.

---

Debugging your own code should be your first go-to rather than running without debugging and then asking strangers on the internet for help.  That you didn't notice it is running hundreds of thousands of iterations (for a 10 element array) suggests you didn't single step debug this.  Had you done single step debugging, you should have noticed problems (i.e. it never stops).  If you don't have debugging skills, now is the time to acquire them.  In the abstract, debugging assembly is no different from debugging other languages — you just watch your code run one line at a time and make sure each line does the right thing!