I would like to implement Hanoi Towers algorithm in MIPS assembly.
Rods are indicated by A, B and C.
Input is number of number of disks and output is the sequence of moves necessary to solve the problem.
For example:
If input is 3, output should be:
A>C
A>B
C>B
A>C
B>A
B>C
A>C
I've managed to get the result with the numbers of the rods, i.e. 1>3 instead of A>C, with the following code:
.data
NewLine: .asciiz "\n"
To: .asciiz ">"
.globl main
.text
main:
li $v0, 5
syscall
add $a0, $v0, $zero
addi $a1, $zero, 1
addi $a2, $zero, 3
addi $a3, $zero, 2
jal hanoi1
li $v0, 10
syscall
hanoi1:
addi $t0, $a0, 0
addi $t1, $zero, 1
bne $a0, $t1, hanoi2
li $v0, 1
move $a0, $a1
syscall
li $v0, 4
la $a0, To
syscall
li $v0, 1
move $a0, $a2
syscall
li $v0, 4
la $a0, NewLine
syscall
addi $a0, $t0, 0
jr $ra
hanoi2:
addi $sp, $sp, -20
sw $ra, 16($sp)
sw $a3, 12($sp)
sw $a2, 8($sp)
sw $a1, 4($sp)
sw $a0, 0($sp)
addi $t3, $a3, 0
addi $a3, $a2, 0
addi $a2, $t3, 0
addi $a0, $a0, -1
jal hanoi1
lw $ra, 16($sp)
lw $a3, 12($sp)
lw $a2, 8($sp)
lw $a1, 4($sp)
lw $a0, 0($sp)
addi $t0, $a0, 0
addi $t1, $zero, 1
li $v0, 1
move $a0, $a1
syscall
li $v0, 4
la $a0, To
syscall
li $v0, 1
move $a0, $a2
syscall
li $v0, 4
la $a0, NewLine
syscall
addi $a0, $t0, 0
addi $t3, $a3, 0
addi $a3, $a1, 0
addi $a1, $t3, 0
addi $a0, $a0, -1
jal hanoi1
lw $ra, 16($sp)
addi $sp, $sp, 20
add $v0, $zero, $t5
jr $ra
I tried to add labels such as:
PrintA:
li $v0, 4
la $a0, A
syscall
jr $ra
And add beq to branch to the right label:
beq $a1, $t7, PrintA # $t7=1
beq $a1, $t8, PrintB # $t8=2
beq $a1, $t9, PrintC # $t9=3
But the program got into infinite loop, probably because I didn't handle $ra correctly.
So my problem is I can't figure out how to convert the rods numbers to letters.
Any help would be appreciated.
To use jr $ra to return somewhere, you must first set register $ra with the address to return to, that's what jal is doing before branching, putting address of next instruction into ra.
I.e. to use this:
beq $a1, $t7, PrintA # $t7=1
beq $a1, $t8, PrintB # $t8=2
beq $a1, $t9, PrintC # $t9=3
with the PrintA/B/C variants ending by jr $ra means, that if you would not want to print anything there the next instruction instead of the beq block would be jr $ra too, ending that code-flow.
You can then do it like this:
move $a0, <number of rod (from)>
# make sure you have current `ra` stored in stack to not lose it
jal print_rod # will set ra to address of next line
... continue with printing "To" string
... and then you can reuse the same subroutine to display second rod
move $a0, <number of rod (to)>
jal print_rod # will set ra to address of next line
... do remaining things (? if any), restore ra, continue
And put the rod number to letter conversion inside the print_rod subroutine. Which then may look like 3x beq with three different tails and using jr $ra to return from each of the variant back into the code above, but if you think about it from math and assembly point of view, you are converting values [1, 2, 3] to letters [A, B, C].
There is syscal, v0=11 "print character", and needs ASCII character in the a0 as argument.
If you will check ASCII encoding table, you will see that letter A is encoded as value 65, B is 66 and C is 67. And your input is value 1, 2 or 3. In all cases to transform the numeric rod value into ASCII letter you need only to add +64 to it.
I.e. your current way of displaying rod number:
li $v0, 1
move $a0, $a1
syscall
Needs just small modification:
li $v0, 11 # print character service
addi $a0, $a1, 64 # number to ASCII letter (1->A, 2->B, 3->C)
syscall
And that's it, no branching (branching is generally slower than doing simple calculation like addi).
Your current source has different parts of code being identical to others, you want again to spend some time trying to realize which part of code are being different and keep only those, and use single code for the identical path, either extracting that identical code into subroutine (using it by jal subroutine+jr $ra), or rearranging the code flow to be like:
# something to be done in every iteration
# if (next_part_should_not_execute) branch to skip_part_2
# part 2 of code - being run just under certain condition
skip_part_2:
# if (next_part_should_not_execute) branch to skip_part_3
# part 3 of code - being run just under certain other condition
skip_part_3:
# part 4 of code, being run every iteration, unconditionally
That way you need still just single copy of "part 4" instruction in the source, but the parts 2 and 3 will be run only when certain conditions are true.