I am having trouble with translating this C code of Insertion sort into mips. He
ID: 3564098 • Letter: I
Question
I am having trouble with translating this C code of Insertion sort into mips.
Here is the C code
And here is my assembly code so far that does not work
# Data/declarations
.data
# For main function
initStr: .asciiz "The initial array is: "
endStr: .asciiz "Insertion sort is finished! "
# For print_array
arrPrintStart: .asciiz "["
arrPrintEnd: .asciiz " ] "
spc: .asciiz " "
size: .word 16
# For str_lt
nullChar: .asciiz ""
charX: .asciiz ""
charY: .asciiz ""
xCounter: .word 0
yCounter: .word 0
# For insertSort
value: .asciiz ""
space: .align 5
# General
iCounter: .word 0
jCounter: .word 0
arr: .align 5
.asciiz "Joe"
.align 5
.asciiz "Jenny"
.align 5
.asciiz "Jill"
.align 5
.asciiz "John"
.align 5
.asciiz "Jeff"
.align 5
.asciiz "Joyce"
.align 5
.asciiz "Jerry"
.align 5
.asciiz "Janice"
.align 5
.asciiz "Jake"
.align 5
.asciiz "Jonna"
.align 5
.asciiz "Jack"
.align 5
.asciiz "Jocelyn"
.align 5
.asciiz "Jessie"
.align 5
.asciiz "Jess"
.align 5
.asciiz "Janet"
.align 5
.asciiz "Jane"
.align 5
.text
.globl main
# Main method
main:
la $a0, initStr #
li $v0, 4 # Load and print the initial string
syscall #
jal print_array # Call print_array
jal insertSort # Call insertSort
la $a0, endStr #
li $v0, 4 # Load and print the initial string
syscall #
jal print_array # Call print_array
li $v0, 10 # Exit (system call code for exit is 10)
syscall # Make the syscall
print_array:
addi $sp, $sp, -8 # Adjust the stack for 2 more items
sw $ra, 4($sp) # Save the return address
sw $a0, 0($sp) # Save the user input (size)
la $s0, arr # Store array address in s0
la $a0, arrPrintStart #
li $v0, 4 # Print arrPrintStart (in $v0)
syscall #
startLoop:
lw $a0, size # Load the array size to a0
blt $a1, $a0, loopNotDone # If a1<a0, goto loopNotDone
# Here the loop is done, so we want to print arrPrintEnd and exit
la $a0, arrPrintEnd #
li $v0, 4 # Print arrPrintEnd (in $v0)
syscall #
lw $ra, 4($sp) # Load the return address
addi $sp, $sp, 8 # Remove 2 items off the stack
jr $ra # Return to the caller
loopNotDone:
addi $a1, $a1, 1 # Add 1 to i
la $a0, spc #
li $v0, 4 # Print a space
syscall #
la $a0, 0($s0) #
li $v0, 4 # Print the current array item
syscall #
addi $s0, $s0, 32 # Add 32 to s0
jal startLoop # Call startLoop (recursive)
lw $ra, 4($sp) # Load the return address
addi $sp, $sp, 8 # Remove 2 items off the stack
jr $ra # Return to caller
str_lt:
# $a1 will point to xChar
# $a2 will point to yChar
addi $sp, $sp, -4 # Adjust the stack for 1 more item
sw $ra, 0($sp) # Save the return address
startCharLoop:
bgtz $a1, exit # If xChar is '', exit
bgtz $a2, exit # If yChar is '', exit
blt $a1, $a2, return1 # If xChar<yChar, return 1
blt $a2, $a1, return0 # If yChar<xChar, return 0
add $a1, $a1, 1 # Increment pointer to xChar
add $a2, $a2, 1 # Increment pointer to yChar
j startLoop # Start the loop again
return0:
add $v0, $zero, $zero # Set our result to 0
lw $ra, 0($sp) # Load the return address
addi $sp, $sp, 4 # Remove 1 item off the stack
jr $ra # Return to the caller
return1:
add $v0, $zero, 1 # Set our result to 1
lw $ra, 0($sp) # Load the return address
addi $sp, $sp, 4 # Remove 1 item off the stack
jr $ra # Return to the caller
exit:
beqz $a2, return0 # If yChar='', return 0
j return1 # Else return 1
insertSort:
# Adjust the stack for 1 more item
addi $sp, $sp, -4
# Save the return address
sw $ra, 0($sp)
lw $t6, size # Set $t6 to the array size
lw $t0, iCounter # Load iCounter to t0 - for individual chars
lw $t1, jCounter # Load jCounter to t1 - for individual chars
la $s1, arr # Load array to s1 - will act as iCounter for full strings
la $s2, arr # Load array to s2 - will act as jCounter for full strings
la $t2, arr # Load the array as a pointer to t2
addi $t0, $zero, 1 # Set $t0 to 1 (the first loop counter)
startFirstForLoop:
beq $t0, $t6, end # If i=size of array, exit
j startSecondForLoop # Else goto startSecondForLoop
startSecondForLoop:
add $t3, $s1, $t0 # Set *value to the correct item
sub $t1, $t0, 1 # Set $t1 to t0-1 (jCounter = iCounter - 1)
la $t7, 32 #
mult $t7, $t0 # Set s1 pointer to t0*32
add $s1, $t2, $t7 #
la $t7, 32 #
mult $t7, $t1 # Set s2 pointer to t1*32
add $s2, $t2, $t7 #
la $a0, 0($t3) #
li $v0, 4 # Print the current array item
syscall #
bge $t1, $zero, firstCondMet # Branch to firstCondMet if t1 >= 0
j startFirstForLoop # Else goto startFirstForLoop
firstCondMet:
### Making sure our registers used in str_lt are assigned correctly ###
add $s1, $s1, $t0 # Point to the i char of this word
add $s2, $s2, $t1 # Point to the i char of this word
lb $a0, ($s1) # Load the pointer to arr[t0] to a0 (our first str_lt parameter)
lb $a1, ($s2) # Load the pointer to arr[t1] to a1 (our first str_lt parameter)
jal str_lt # Goto str_lt (result will be saved to $v0)
sub $s1, $s1, $t0 # Reset $s1 to a multiple of 32
sub $s2, $s2, $t1 # Reset $s2 to a multiple of 32
beq $v0, $zero, startFirstForLoop # Branch to startFirstForLoop if v0=0
j secondCondMet # Else goto secondCondMet
secondCondMet:
addi $t4, $t1, 1 # Set t1+1 to t4
la $t4, ($t1) # Set t4 (t1+1) to t1 (a[j+1] = a[j])
subi $t1, $t1, 1 # t1 = t1-1
jal startSecondForLoop # Recurse back to the start of the second for loop
addi $t4, $t1, 1 # Set t1+1 to t4
la $t4, ($t3) # Set t4 (t1+1) to t3 (a[j+1] = value)
addi $t0, $t0, 1 # Increment the iCounter
jal startFirstForLoop # Recurse back to the start of the first for loop
end:
lw $ra, 0($sp) # Load the return address
addi $sp, $sp, 4 # Remove 1 item off the stack
jr $ra # Return to caller
Explanation / Answer
Correct code:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.