COMP1521 2022T2 Q8 · 10 marks · MIPS Topic: MIPS functions & recursion · Source: https://cgi.cse.unsw.edu.au/~cs1521/26T1/resources/practice_exams.html

Summary: Towers of Hanoi: move_disks / find_lowest_target

You have been given 22t2final_q8.s :

COMP1521 22T2 ... final exam, question 8

.data

char default_char = ' ';

default_char: .byte ' '

.text

void move_disks(char size, char *target, char *peg1, char *peg2) {

move_disks:

TODO: Complete this function

jr $ra

.text

char *find_lowest_target(char *target) {

find_lowest_target:

TODO: Complete this function

jr $ra

Add code to 22t2final_q8.s to make it equivalent to this C program which you have been given as 22t2final_q8.c :

// // // // // // // // DO NOT CHANGE THIS FILE! // // // // // // // // // COMP1521 22T2 ... final exam, question 8

#include <stdlib.h>

#include "22t2final_q8.h"

char default_char = ' ' ;

void move_disks ( char size , char * target , char * peg1 , char * peg2 ) { char * peg_max = & default_char ; char * source = NULL ; char * other = NULL ;

for ( int i = 0 ; peg1 [ i ] != '\0' ; i ++ ) { if ( peg1 [ i ] > * peg_max && peg1 [ i ] <= size ) { peg_max = peg1 + i ; source = peg1 ; other = peg2 ; } if ( peg2 [ i ] > * peg_max && peg2 [ i ] <= size ) { peg_max = peg2 + i ; source = peg2 ; other = peg1 ; } }

if ( * peg_max == ' ' ) return ;

move_disks ( size - 1 , other , source , target ); char * lowest_target = find_lowest_target ( target ); swap ( peg_max , lowest_target );

while ( * peg_max != * ( peg_max + 1 )) { swap ( peg_max , peg_max + 1 ); peg_max ++ ; }

print_towers (); move_disks ( size - 1 , target , source , other ); }

char * find_lowest_target ( char * target ) { if ( * target == ' ' ) return target ; return find_lowest_target ( target + 1 ); }

22t2final_q8.c is part of a larger program that helps solve the "Towers of Hanoi" problem - a famous mathematical game played with three towers of disks.

You must translate both functions to MIPS assembler and following the standard calling conventions used in lectures.

Note that you have been provided a 22t2final_q8_main.s file which includes a main function to help test your code, along with a complete implementation of the swap function which is used in the C code provided above.

For example:

1521 mipsy 22t2final_q8_main.s 22t2final_q8.s

|g f e d c b a | | | | |

================ |g f e d c b | |a | | |

[lots of output]

|a | |g f e d c b | | |

================ | | |g f e d c b a | | |

You should check your MIPS code against the C reference code: make 22t2final_q8 ./22t2final_q8 >c.output 1521 mipsy 22t2final_q8_main.s 22t2final_q8.s >mips.output diff c.output mips.output

(no output from diff is good!)

Your solution must be in MIPS only.

Your solution must not be in C , C++ , Python , or any other language.

No error checking is necessary or required.

🤖 Write MIPS (mipsy). Read n. Print the Tower-of-Hanoi moves that transfer n disks from peg 1 to peg 3 using peg 2, one move per line as <from> <to>.

Verified on the sandbox AND cross-checked against an independent oracle.