No string output in MIPS assembly code. I tried looking this up for sometime now and I can't seem to find a proper answer. The code below implements bubble sort on a string, it only works on lowercase letters as it compares ascii code numbers.(sorry if I am not using proper terminology)
.data
InputPrompt: .asciiz "Please input a string(no more than 255 Characters: "
Buffer: .space 256
.text
li $v0, 4
la $a0, InputPrompt
syscall
li $v0, 8
la $a0, Buffer
li $a1, 255
syscall #taking input
jal BubbleSort
move $a0, $v0
li $v0, 4
syscall
li $v0, 10
syscall
BubbleSort:
addi $sp, $sp, -32
sw $ra, 0($sp)
sw $t0, 4($sp) #temporary storage for the string
sw $t1, 8($sp) #Used to go back to beginning of string
sw $t2, 12($sp) #register to keep track of iterator
sw $t3, 16($sp) #flag to check if a switch happened or not
sw $t4, 20($sp) #for str[i] < str[i+1] condition
sw $t5, 24($sp) #current byte
sw $t6, 28($sp) #next byte
la $t0, ($a0) #loading string
li $t3, 0
OutterLoop: #while(!sorted)
move $t2, $zero #reset iterator
beq $t3, 1, Done # (!sorted) condition
li $t3, 1
li $t1, 0
InnerLoop:
lb $t5, 0($t0) #load current byte
lb $t6, 1($t0) #load next byte
beqz $t6, EndString #'\0' has value of 0
slt $t4, $t5, $t6 #str[i] < str[i+1]
beq $t4, 1, ELSE
sb $t6, 0($t0)
sb $t5, 1($t0)
li $t3, 0
ELSE:
addi $t0, $t0, 1
addi $t1, $t1, 1
j InnerLoop
EndString:
sub $t0, $t0, $t1 #go back to beginning of string
j OutterLoop
Done:
move $v0, $t0 #return string
lw $ra, 0($sp)
lw $t0, 4($sp)
lw $t2, 8($sp)
lw $t3, 12($sp)
lw $t4, 16($sp)
lw $t5, 20($sp)
lw $t6, 24($sp)
addi $sp, $sp, 32
jr $ra
The comments above pretty much explain what each part does sufficiently.
I tried looking up through online resources on what the problem might be, but didn't get to any proper answers. Example input: hello Expected output: ehllo Output from code: (nothing)
The exit condition for the outer loop is that you have not swapped anything, therefore it is considered sorted. To put it another way, the continuation condition for the outer loop is that something has been swapped, therefore it is considered non-sorted.
However, you "swap" not just when less than, but less that or equal, and hello has two l's. Thus, the outer loop never stops, when the input string has two letters the same. Try helo for input and it will work.
This swap on equal is unnecessary but harmless — until the string is fully sorted, when it becomes the only swap and thus prevents the loop from terminating — classic infinite loop.
You should be able to debug this yourself. Use single step and observe the outer loop and inner loop swapping continues ad nauseam even after the string is fully sorted.
Let's look at your swap condition test:
slt $t4, $t5, $t6 #str[i] < str[i+1]
beq $t4, 1, ELSE
That's doing $t5 < $t6, and then testing for the true condition for skipping the then-part. So, the then-part execution condition is the opposite: $t5 >= $t6, which leads to swapping when 'l' == 'l' in 'hello'`. In essence, you're doing:
if ( p[0] >= p[1] ) {
// swap when earlier letter is > following letter, but also when equal
$t3 = 0;
}
where you really want:
if ( p[0] > p[1] ) {
// swap only when really necessary
$t3 = 0;
}
To solve the problem, you need to test for $t5 <= $t6 (as the if-then condition for skipping the then-part) instead, such that the condition to execute the then-part is now $t5 > $t6.
You can use sle instead of slt.
Though FYI, this is a pseudo instruction that expands to 3 real machine code instructions, since the MIPS hardware doesn't actually have this operation, only the assembler knows this one.
So, what can be done if we don't want that help from the assembler?
We can swap the operands of slt, as in $t6 < $t5, and then also swap the exit test to branch to the ELSE if this condition doesn't hold — this would appear to be double negation but it isn't exactly: taken together it moves the equality test to the other condition (the other branch of the if-then), making it $t6 >= $t5 aka $t5 <= $t6 instead of just $t5 < $t6.
That means skipping ahead to the ELSE part when ! (p[1] < p[0]), which is the same as p[1] >= p[0]:
slt $t4, $t6, $t5 # str[i+1] < str[i]
beq $t4, $0, ELSE # goto ELSE when ! (str[i+1] < str[i])
# aka goto ELSE when str[i+1] >= str[i]
# aka goto ELSE when str[i] <= str[i+1]
which is equivalent to:
if ( p[1] >= p[0] ) goto ELSE; // aka if ( p[0] <= p[1] ) goto ELSE;
// swap only when really necessary
$t3 = 0;
ELSE:
which is equivalent to:
if ( p[1] < p[0] ) { // and also same as: if ( p[0] > p[1] ) {
// swap only when necessary
$t3 = 0;
}
This is super confusing stuff, easy to make a mistake or typo. There are two different though related concepts here, one is negation, and the other is operand swapping.
= comes or goes e.g.
! (a <= b) becomes a > b, and! (a < b) becomes a >= b), whereas= stays as is (whether present or absent), e.g.
a < b becomes b > a, anda <= b becomes b >= a.We combine both negation and operand swapping as here to use the slt instruction that MIPS hardware has.
You are storing $t registers on the stack, and restoring them later. Don't do this — it is pointless and benefits no one as these registers are scratch / call-clobbered. Only $s registers need be saved on the stack, and only if they are used by the function.
You are saving $ra on the stack, but since it is never modified by your function, this is also unnecessary. If your sort function were to call another function (a swap, for example), that would necessarily repurpose $ra for that nested invocation, and you would indeed need to save your function's original $ra value so the sort function can get back to its caller when its done (here main but doesn't always have to be), after the swap function uses $ra to get back to the sort function.
syscall #8 accepts input from the user and puts it into the buffer, including the carriage return the user enters, yet you don't strip that from the input prior to sorting. Since the user's carriage return character is also in the buffer, and, the carriage return character has a very low ascii value, the bubble sort will bring that character to the beginning of the string. So you'll have \nhelo, which sort of works, but is probably unexpected, and explains the extra newline that comes out first, when printing to the sorted string.
As a side note let's mention that beq with a constant is a psuedo instruction that expands into multiple instructions by the assembler. Since slt yields a boolean 1 or 0, it would be simpler to do bne $t4, $0, ELSE, which is not a pseudo instruction, and also having the same effect of testing for 1 in order to exit a loop or skip a then-part. This a better way to do the same as you have (this does not address the >= vs. > problem, of course).
We can think of beq ... $0 ... as a metaphor for branch on false, and bne ... $0 ... as a metaphor for branch on true, when booleans such as those delivered by slt are being tested.
This also applies to your other boolean $t3 regarding your exit test for the outer loop.
beq $t3, 1, Done # (!sorted) condition
is simpler and more iconic as:
bne $t3, $0, Done # (!sorted) condition
If you do choose to strip the newline character before doing the sort operation, be aware that your sort function expects at least 1 character in the user's input (it only tests for null on the 2nd character) and will fail in some way (that may or may not be observable) if the input is empty. A sort function should work properly when there are no elements to sort. You can test for this condition once outside of and before the outer sorting loop, and simply skip the whole sort (jumping to the function exit prologue) if str[0] is null.
When using syscall #8, you'll get a newline followed by null terminator. If you overwrite the newline with a null, that means any string in the buffer will have two nulls, even the empty string, and so your algorithm will be ok.
However, if you used another method to put strings in the buffer, the scenario is that then a long string "hello world" later overwritten by a shorter string "x" might look like this "x\0llo world\0" in the buffer. You're not supposed to look past the first null found, and your algorithm won't with that one but if the later shorter string was simply the empty string, you'll have an initial null followed by some characters from the previous string "\0ello world\0" — in that case your algorithm will stop at the second null, which is in the previous string instead of at the proper first null.
You have
la $t0, (a0)
but this again is a pseudo instruction, unnecessary here, this is better done as:
move $t0, $a0
or, if you want to avoid even the simple pseudo instructions then:
add $t0, $a0, $0
Your code to reset the main pointer, $t0 could be simpler. It would be more normal to simply reset the pointer rather than using pointer subtraction. You have:
$t0 = $a0; // #1
outer loop
$t1 = 0 // #2
inner loop
$t1++ // #3
end inner loop
$t0 = $t0 - $t1 // #4
end outer loop
move $v0, $t0 // #5
This can be simplified as follows:
outer loop
$t0 = $a0; // #1 simply initialize, now inside outer loop at top
inner loop
...
end inner loop
end outer loop
move $v0, $a0 // #5 to return original string use value from $a0
By re-initializing from the original, unmodified $a0, there's no need for the counter variable, $t1 at all, and so #2,#3,#4 can be eliminated.
Though of no real consequence in your original code, the return value would probably normally be obtained from the unmodified parameter $a0, rather than the mutating pointer, $t0. In my update here it is important to use $a0, since $t0 isn't reinitialized at the bottom of the loop, and would reasonably be done after the exit test at the top of the loop, leaving $t0 in a bad place to use as return value.