Рекурсивное решение «Ханойские башни» с использованием MIPS

Question

Я новичок в задании вопросов о переполнении стека и еще новее в MIPS.Я попытался реализовать следующее рекурсивное решение проблемы «Ханойских башен» (взято из здесь ) с использованием MIPS.Я думаю, что моя неудача заключается в том, что я не понимаю, когда мне нужно восстанавливать / сохранять регистры, такие как $ra, $sp - поэтому я просто предполагаю, что мне нужно делать это везде - любая помощь будет принята с благодарностью:

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)
{
    if (n == 1)
    {
        printf("\n Move disk 1 from rod %c to rod %c", from_rod, to_rod);
        return;
    }
    towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
    printf("\n Move disk %d from rod %c to rod %c", n, from_rod, to_rod);
    towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
}

int main()
{
    int n = 4; // Number of disks
    towerOfHanoi(n, 'A', 'C', 'B');  // A, B and C are names of rods
    return 0;
}

И это моя попытка «перевести» это в MIPS:

.globl main
main:
    addi $sp, $sp, -4
    sw $ra, 0($sp)

    li $v0, 5 # system call code for read_int
    syscall

    move $a0, $v0 # a0 holds the number of disks
    li $a1, 'A' # a1 holds from_rod
    li $a2, 'C' # a2 holds to_rod
    li $a3, 'B' # a3 holds aux_rod

    jal hanoi

    lw $ra, 0($sp)
    addi $sp, $sp, 4
    li $v0, 10
    syscall

hanoi:
    addi $sp, $sp, -4
    sw $ra, 0($sp)

    beq $a0, 1, base_case
    addi $a0, $a0, -1 # number_of_disks -= 1
    # swap between to_rod and aux_rod :
    move $t0, $a2 # temp = to_rod
    move $a2, $a3 # to_rod = aux_rod
    move $a3, $t0 # aux_rod = temp
    jal hanoi

    jal print

    # swap between from_rod and aux_rod :
    move $t0, $a1 # temp = from_rod
    move $a1, $a3 # from_rod = aux_rod
    move $a3, $t0 # aux_rod = temp
    jal hanoi

    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra
base_case:
    addi $sp, $sp, -4
    sw $ra, 0($sp)

    jal print

    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra
print:
    addi $sp, $sp, -4
    sw $ra, 0($sp)
    move $t0, $a0

    li $v0, 11
    move $a0, $a1
    syscall # print from_rod
    li $a0, '>'
    syscall # print the char '>'
    move $a0, $a2
    syscall # print  to_rod
    li $a0, '\n'
    syscall # pirnt new line
    move $a0, $t0

    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra

Answer 1

Посмотрите на это решение:

# Towers of Hanoi
# MIPS assembly implementation (tested with MARS)

.data
prompt: .asciiz "Enter a number: "
part1: .asciiz "\nMove disk "
part2: .asciiz " from rod "
part3: .asciiz " to rod "

.text
.globl main
main:
    li $v0,  4          # print string
    la $a0,  prompt
    syscall
    li $v0,  5          # read integer
    syscall

    # parameters for the routine
    add $a0, $v0, $zero # move to $a0
    li $a1, 'A'
    li $a2, 'B'
    li $a3, 'C'

    jal hanoi           # call hanoi routine

    li $v0, 10          # exit
    syscall

hanoi:

    #save in stack
    addi $sp, $sp, -20 
    sw   $ra, 0($sp)
    sw   $s0, 4($sp)
    sw   $s1, 8($sp)
    sw   $s2, 12($sp)
    sw   $s3, 16($sp)

    add $s0, $a0, $zero
    add $s1, $a1, $zero
    add $s2, $a2, $zero
    add $s3, $a3, $zero

    addi $t1, $zero, 1
    beq $s0, $t1, output

    recur1:

        addi $a0, $s0, -1
        add $a1, $s1, $zero
        add $a2, $s3, $zero
        add $a3, $s2, $zero
        jal hanoi

        j output

    recur2:

        addi $a0, $s0, -1
        add $a1, $s3, $zero
        add $a2, $s2, $zero
        add $a3, $s1, $zero
        jal hanoi

    exithanoi:

        lw   $ra, 0($sp)        # restore registers from stack
        lw   $s0, 4($sp)
        lw   $s1, 8($sp)
        lw   $s2, 12($sp)
        lw   $s3, 16($sp)

        addi $sp, $sp, 20       # restore stack pointer

        jr $ra

    output:

        li $v0,  4              # print string
        la $a0,  part1
        syscall
        li $v0,  1              # print integer
        add $a0, $s0, $zero
        syscall
        li $v0,  4              # print string
        la $a0,  part2
        syscall
        li $v0,  11             # print character
        add $a0, $s1, $zero
        syscall
        li $v0,  4              # print string
        la $a0,  part3
        syscall
        li $v0,  11             # print character
        add $a0, $s2, $zero
        syscall

        beq $s0, $t1, exithanoi
        j recur2

Это в значительной степени прямой перевод вашего кода C, и его должно быть достаточно, чтобы понять, как сохранить рутинные аргументы через стек.