Question

A.10 [10] <§§A.6, A.9> Using SPIM, write and test a recursive program for solving the classic mathematical recreation, the Towers of Hanoi puzzle. (This will require the use of stack frames to support recursion.) The puzzle consists of three pegs (1, 2, and 3) and n disks (the number n can vary; typical values might be in the range from 1 to 8). Disk 1 is smaller than disk 2, which is in turn smaller than disk 3, and so forth, with disk n being the largest. Initially, all the disks are on peg 1,

Starting with disk n on the bottom, disk n − 1 on top of that, and so forth, up to disk 1 on the top. The goal is to move all the disks to peg 2. You may only move one disk at a time, that is, the top disk from any of the three pegs onto the top of either of the other two pegs. Moreover, there is a constraint: You must not place a larger disk on top of a smaller disk.

The C program below can be used to help write your assembly language program.

/* move n smallest disks from start to finish using

extra */

void hanoi(int n, int start, int finish, int extra){

if(n != 0){

hanoi(n-1, start, extra, finish);

print_string(“Move disk”);

print_int(n);

print_string(“from peg”);

print_int(start);

print_string(“to peg”);

print_int(finish);

print_string(“.\n”);

hanoi(n-1, extra, finish, start);

}

}

main(){

int n;

print_string(“Enter number of disks>“);

n = read_int();

hanoi(n, 1, 2, 3);

return 0;

}

Short answer

The corresponding MIPS assembly language program:

Call Hanoi(4, 1, 3):

mov r0, #3

push {r0}

mov r0, #1

push {r0}

mov r0, #4

push {r0}

Call Hanoi(4, 1, 3)

bl Hanoi

add sp, sp, #12

Hanoi:

push {lr}

push {fp}

mov fp, sp

sub sp, sp, #4

ldr r0, [fp, #8]

cmp r0, #1

bne else

movw r0, #:lower16:Str

movt r0, #:upper16:Str

ldr r1, [fp, #12]

ldr r2, [fp, #16]

bl printf

b ifEnd

else:

ldr r0, [fp, #12]

rsb r0, r0, #6

ldr r1, [fp, #16]

sub r0, r0, r1

str r0, [fp, #-4]

ldr r0, [fp, #-4]

push {r0}

ldr r0, [fp, #12]

push {r0}

ldr r0, [fp, #8]

sub r0, r0, #1

push {r0}

Call Hanoi(ndisk-1, fromPeg, helpPeg)

bl Hanoi

add sp, sp, #12

movw r0, #:lower16:Str

movt r0, #:upper16:Str

ldr r1, [fp, #12]

ldr r2, [fp, #16]

bl printf

ldr r0, [fp, #16]

push {r0}

ldr r0, [fp, #-4]

push {r0}

ldr r0, [fp, #8]

sub r0, r0, #1

push {r0}

Call Hanoi(ndisk-1, fromPeg, helpPeg)

bl Hanoi

add sp, sp, #12

ifEnd:

mov sp, fp

pop {fp}

pop {pc}

.data

Step-by-step solution

Define the concept of MIPS instructions.

• One of the MIPS instructions is “add $t3 $t4 $t5” for add where $t3 = $t4 + $t5.
• One of the MIPS instructions is “sub $t3 $t4 $t5” for subtracting where $t3 = $t4 - $t5.
• The “branch-not-equal (bne)” is a decision-making instruction in MIPS assembly language. The purpose of using this MIPS assembly instruction “bne reg1, reg2 Label” is going to the statement “Label” if the value of “reg1” is not equal to the “reg2”.
• The MIPS instruction “ldr” is used for loading from the memory to a register.
• One of the MIPS instruction “bl” is used for branching and linking.

Determine the program with the comment.

The corresponding MIPS assembly language program:

Call Hanoi(4, 1, 3): move 4 disk from peg 1 to peg 3

mov r0, #3

push {r0} // Pass the “peg2” = 3

mov r0, #1

push {r0} // Pass the “peg1” = 1

mov r0, #4

push {r0} // Pass the “ndisks” = 4

Call Hanoi(4, 1, 3)

bl Hanoi

add sp, sp, #12 // Pop parameters

Hanoi:

// Prelude

push {lr} // For saving the return address

push {fp} // For saving the frame pointer

mov fp, sp // For making the base pointer

sub sp, sp, #4 // The Local var helpPeg

// if (ndisk == 1 )

ldr r0, [fp, #8] // r0 = ndisks

cmp r0, #1 // Check (ndisks == 1)

bne else

movw r0, #:lower16:Str

movt r0, #:upper16:Str

ldr r1, [fp, #12] // r1 = fromPeg

ldr r2, [fp, #16] // r2 = toPeg

bl printf

b ifEnd

else:

ldr r0, [fp, #12] // r0 = fromPeg

rsb r0, r0, #6 // r0 = 6 - fromPeg

ldr r1, [fp, #16] // r1 = toPeg

sub r0, r0, r1 // r0 = 6 - fromPeg - toPeg

str r0, [fp, #-4]

// Hanoi(ndisk-1, fromPeg, helpPeg)

ldr r0, [fp, #-4]

push {r0} // Pass the helpPeg

ldr r0, [fp, #12]

push {r0} // Pass the fromPeg

ldr r0, [fp, #8]

sub r0, r0, #1

push {r0} // Pass the ndisk-1

Call Hanoi(ndisk-1, fromPeg, helpPeg)

bl Hanoi

add sp, sp, #12 // Pop parameters

movw r0, #:lower16:Str

movt r0, #:upper16:Str

ldr r1, [fp, #12] // r1 = fromPeg

ldr r2, [fp, #16] // r2 = toPeg

bl printf

// Hanoi(ndisk-1, helpPeg, toPeg)

ldr r0, [fp, #16]

push {r0} // Pass the toPeg

ldr r0, [fp, #-4]

push {r0} // Pass the helpPeg

ldr r0, [fp, #8]

sub r0, r0, #1

push {r0} // Pass the the ndisk-1

Call Hanoi(ndisk-1, fromPeg, helpPeg)

bl Hanoi

add sp, sp, #12 // Pop parameters

ifEnd:

// Return

mov sp, fp

pop {fp}

pop {pc}

.data