# /*
#  * C Tower of Hanoi (recursive_tower_of_hanoi_mips.c)
#  */
# #include <stdio.h>
# 
# // move disks from source to dest using temp as a temporary
# void hanoi(int disk, char source, char dest, char temp){ 
#   if(disk == 0) { // the smallest disk
#     printf("move disk %d from %c to %c\n", disk, source, dest);
#   } else {
#     hanoi(disk - 1, source, temp, dest); // move disk - 1 from source to temp
#     printf("---- ---- %d ---- %c -- %c\n", disk, source, dest);
#     hanoi(disk - 1, temp, dest, source); // move disk - 1 from temp to dest
#   }
# }
# 
# void main(){
#   int n;
#   printf("\nEnter the number of disks: ");
#   scanf("%d", &n);
#   hanoi(n - 1, 's', 'd', 't'); // move n disks from s to d using t as a temporary
# }

# 
# MIPS Tower of Hanoi (recursive_tower_of_hanoi.s)
# 
.data
$LC0: .ascii "move disk %d from %c to %c\n"
$LC1: .ascii "---- ---- %d ---- %c -- %c\n"
.text
hanoi:                           # hanoi(int disk, char source, char dest, char temp)
    addiu  $sp,  $sp,  -40       # reserve stack space
    sw     $31,  36($sp)         # save return address
    sw     $20,  32($sp)         # save $20
    sw     $19,  28($sp)         # save $19
    sw     $18,  24($sp)         # save $18
    sw     $17,  20($sp)         # save $17
    sw     $16,  16($sp)         # save $16
    move   $18,  $4              # $18: disk
    move   $16,  $5              # $16: source
    move   $17,  $6              # $17: dest
    move   $19,  $7              # $19: temp
    bne    $4,   $0,   $L2       # if (disk == 0)
    lui    $4,         %hi($LC0) # { // disk == 0
    addiu  $4,   $4,   %lo($LC0) #   printf(): $4: address of string to be printed
    move   $5,   $0              #   printf(): $5: disk
    move   $6,   $16             #   printf(): $6: source
    move   $7,   $17             #   printf(): $7: dest
    jal    printf                #   printf("move disk %d from %c to %c\n");
    j      $L1                   # }
$L2:                             # else
    addiu  $20,  $4,  -1         # { // disk != 0
    move   $4,   $20             #   hanoi(): $4: disk - 1
    move   $5,   $16             #   hanoi(): $5: source
    move   $6,   $19             #   hanoi(): $6: temp
    move   $7,   $17             #   hanoi(): $7: dest
    jal    hanoi                 #   hanoi(disk - 1, source, temp, dest);
    lui    $4,         %hi($LC1) #   
    addiu  $4,   $4,   %lo($LC1) #   printf(): $4: address of string to be printed
    move   $5,   $18             #   printf(): $5: disk
    move   $6,   $16             #   printf(): $6: source
    move   $7,   $17             #   printf(): $7: dest
    jal    printf                #   printf("---- ---- %d ---- %c -- %c\n");
    move   $4,   $20             #   hanoi(): $4: disk - 1
    move   $5,   $19             #   hanoi(): $5: temp
    move   $6,   $17             #   hanoi(): $6: dest
    move   $7,   $16             #   hanoi(): $7: source
    jal    hanoi                 #   hanoi(disk - 1, temp, dest, source);
$L1:                             # }
    lw     $31,  36($sp)         # restore return address
    lw     $20,  32($sp)         # restore $20
    lw     $19,  28($sp)         # restore $19
    lw     $18,  24($sp)         # restore $18
    lw     $17,  20($sp)         # restore $17
    lw     $16,  16($sp)         # restore $16
    addiu  $sp,  $sp,   40       # release stack space
    jr     $31                   # return from hanoi
.data
$LC2: .ascii "\nEnter the number of disks: "
$LC3: .ascii "%d"
.text
main:                            # main()
    addiu  $sp,  $sp,  -32       # reserve stack space
    sw     $31,  28($sp)         # save return address
    lui    $4,         %hi($LC2) # 
    addiu  $4,   $4,   %lo($LC2) # printf(): $4: address of string to be printed
    jal    printf                # printf("\nEnter the number of disks: ");
    lui    $4,         %hi($LC3) # 
    addiu  $4,   $4,   %lo($LC3) # scanf(): $4: address of a string which is "%d"
    addiu  $5,   $sp,  16        # scanf(): $5: location where the inputted n is stored
    jal    scanf                 # scanf("%d", &n);
    lw     $4,   16($sp)         # n: number of disks
    addiu  $4,   $4,  -1         # hanoi(): $4: n - 1 (disk)
    addiu  $5,   $0,   0x73      # hanoi(): $5: 's'   (source)
    addiu  $6,   $0,   0x64      # hanoi(): $6: 'd'   (dest)
    addiu  $7,   $0,   0x74      # hanoi(): $7: 't'   (temp)
    jal    hanoi                 # hanoi(n - 1, 's', 'd', 't');
    lw     $31,  28($sp)         # restore return address
    addiu  $sp,  $sp,  32        # release stack space
    jr     $31                   # return to OS
.end