Project 2
Towers of Hanoi and sprintf

0. Changes

• July 26, 2006 @ 13:08: Provided a Java version of the Tower of Hanoi code here.

1. Goals

The purpose of this project is to familiarize you with the details of the MIPS calling convention and enhance your assembly programming skills.

2. Administrative Requirements

To submit your project, create a directory named proj2 that contains your sprintf.s and hanoi.s file. From within that directory, type "submit proj2".

The deadline to submit your project is 11:59pm on Friday, July 28th.

This is an individual project, not to be done in partnership. Submit in your own work. Remember, you are allowed to discuss approaches, but NOT solutions.

3. Disclaimer

This document mentions certain test cases. However, this input/output behavior is not a comprehensive specification of all possible behavior. Therefore, even if your project submission passes all of the test cases mentioned here, it may not be entirely correct. We strongly urge you to create test cases in addition to the ones provided here.

4. Background

4.1 Tower of Hanoi

The Tower of Hanoi (commonly also known as the "Towers of Hanoi"), is a puzzle invented by E. Lucas in 1883. The puzzle is simply this: given a stack of n disks arranged from largest on the bottom to smallest on top placed on a peg, together with two empty pegs, what are the minimum number of moves required to move the stack from one rod to another, where moves are allowed only if they place smaller disks on top of larger disks.

4.2 MIPS Stack Management

By now, you should know how to manage the stack when writing functions in MIPS. Let's assume you have a function light_blue, which calls a function dark_blue. The very first thing that light_blue does is to allocate space in the stack for its variables (prolog). In Figure 1 (middle) we can see that it allocates space for 4 words. light_blue eventually calls dark_blue, which allocates space for its own variables. Figure 1 (right) shows that dark_blue has allocated space for 2 words.

Figure 1 -- Typical Stack

4.3 MIPS Argument Passing

The MIPS function calling convention uses registers $a0-$a3 for passing arguments down to functions. If there are more than four, the remaining arguments are passed on the stack. How is this mixed with the normal stack managing? Each argument gets one word of stack space (Why one word?). Suppose we are trying to write in MIPS assembler a program like this:

    int dark_blue (int lvl, int hp, int mp, int str, int agl, int spd, int intel, int vit, int ftg) {

         int a;
         ...
         a = spd;
         ...
    }

    int light_blue () {
         int c, d, e;
         ...
         dark_blue (c, d, e, 62, 25, 99, 47, 29, 1);
         ...
    }

Procedure dark_blue has nine integer arguments. The first four arguments are placed on $a0-$a3 as expected. The remaining arguments are "spilled" onto the stack as part of the caller's (light_blue) stack frame. In other words, light_blue, not dark_blue, must allocate the space needed for the remaining arguments.

Figure 2 shows this stack management method. light_blue now allocates space in the stack for its variables and the arguments that it will use to call dark_blue. We can see in Figure 2 (middle) that it allocates space for 9 words: 4 for its own consumption, and 5 more for the spilled arguments in calling dark_blue

light_blue eventually calls dark_blue that then allocates space for its own variables. Figure 2 (right) shows that dark_blue has allocated space for 2 words. Note that dark_blue can access to the 5 arguments by accessing to the beginning of the stack reserved by its caller process (light_blue).

Figure 2 - Stack with Spilled Arguments

The 5 spilled arguments (patterned light-blue stack) are located at the lower addresses of light_blue's stack frame.

That is, light_blue will use 0($sp) to store the argument agl, 4($sp) to store the argument spdy, and so on. Therefore, dark_blue will use 8($sp) to access to the argument agl, 12($sp) to access to the argument spd, and so on.

Note that the first spilled argument is always at the caller's stack frame lowest address, and the last spilled argument at the highest address. You have to be consistent about this so that dark_blue knows which argument is which.

light_blue:
	# prolog
        addi $sp, $sp, -16  # allocate stack space for 4 words:
                            # $ra, c, d, and e
        sw   $ra, 12($sp)   # save $ra
                            # use 0($sp) to save c ($t0) when needed
                            # use 4($sp) to save d ($t1) when needed
                            # use 8($sp) to save e ($t2) when needed

	# body

        ...

        addi $t0, $0, 3     # assume this holds the value of c
        addi $t1, $0, 4     # assume this holds the value of d
        addi $t2, $0, 5     # assume this holds the value of e

        ...

	# this is the call to dark_blue
        addi $sp, $sp, -20  # allocate stack space for 5 "spilled" words (patterned
                            #   light-blue): the args agl, spd, intel, vit, fatigue
        sw   $t0, 20($sp)   # save c before calling dark_blue
        sw   $t1, 24($sp)   # save d before calling dark_blue
        sw   $t2, 28($sp)   # save e before calling dark_blue

        add  $a0, $0, $t0   # arg lvl = c
        add  $a1, $0, $t1   # arg hp = d
        addi $a2, $0, $t2   # arg mp = e
        addi $a3, $0, 62    # arg str = 62
        addi $t0, $0, 25    # arg agl = 25, but no more registers
        sw   $t0, 0($sp)    #   so pass on the stack
        addi $t0, $0, 99    # arg spd = 99, but no more registers
        sw   $t0, 4($sp)    #   so pass on the stack
        addi $t0, $0, 47    # arg intel = 47, but no more registers
        sw   $t0, 8($sp)    #   so pass on the stack
        addi $t0, $0, 29    # arg vit = 29, but no more registers
        sw   $t0, 12($sp)   #   so pass on the stack
        addi $t0, $0, 1     # arg ftg = 1, but no more registers
        sw   $t0, 16($sp)   #   so pass on the stack
        jal  dark_blue
        addi $sp, $sp, 20   # restore stack space used for calling dark_blue

        ...

	# epilog
        lw   $ra, 12($sp)   # reload return address
        addi $sp, $sp, 16   # restore stack space
        jr   $ra            # return to caller


	...


dark_blue:
	# prolog
        addi $sp, $sp, -8   # allocate stack space for 2 words:
                            # $ra, a
        sw   $ra, 4($sp)    # save $ra
                            # use 0($sp) to save a when needed

	# body

        ...

        add  $t0, $0, $a1   # get argument hp
        lw   $t1, 20($sp)   # *** (see below)
                            # 8 (dark_blue's frame) + 12 = 20 up on stack
                            # fetched argument vit
        ...

	# epilog
        lw   $ra, 4($sp)    # reload return address
        addi $sp, $sp, 8    # restore stack space
        jr   $ra            # return to caller

The instruction indicated by "***" is the key to understanding the stack method of argument passing. Function dark_blue is referring to a word of stack memory that is from the caller's stack frame. Its own frame includes only the two words 0($sp) and 4($sp).

5. Project Description

5.1 Setup

Copy the contents of ~cs61c/public_html/su06/hw/proj2 to a suitable location in your home directory.

  % cd ~
  % cp -r ~cs61c/public_html/su06/hw/proj2 ~/proj2

5.2 sprintf

The first part of your project will be partially implementing the C sprintf function (see 'man sprintf') in MIPS. You will then use this function to record moves in solving the Tower of Hanoi problem. This is the function prototype for sprintf:

  int sprintf (char *outbuf, char *format, ...)

sprintf works like printf, except that it writes to the string outbuf instead of to standard output. outbuf is assumed already to point to allocated memory sufficient to hold the generated characters. Your function must accept any number of arguments passed according to the MIPS standard convention.

The first argument is the address of a character array into which your procedure will put its results. The second argument is a format string in which each occurrence of a percent sign (%) indicates where one of the subsequent arguments is to be substituted and how it is to be formatted. The remaining arguments are values that are to be converted to printable character form according to the format instructions. sprintf returns the number of characters in its output string not including the null at the end.

You do not have to do any error checking (e.g. comparing the number of arguments to the number of % specifications). You also do not have to implement all of the formatting options of the real sprintf. Here are the ones you are to implement:

• %d: signed integer argument to signed decimal (treat the next argument as a signed integer and output in decimal)
• %o: unsigned integer argument to unsigned octal (treat the next argument as a unsigned integer and output in octal)
• %c: character argument copied to output (treat the low byte of the argument word as a character and copy it to the output)
• %s: include a string of characters in output (treat the argument as a pointer to a null-terminated string to be copied to the output)
• %f: floating-point number (treat the argument as a 32-bit word containing a IEEE 754, single-precision floating point number, and copy its value to the output following the guidelines mentioned below)

Don't implement width or precision modifiers (e.g., %6d ).

5.2.1 Floating-Point Formatting

Formatting floating-point numbers is a hard problem. Therefore, we will use a different format than what the real sprintf produces.

Remember that the IEEE 754 standard defines 5 different encodings for single-precision FP numbers: zero, normalized numbers, denormalized numbers, NaN, and infinity. We want your sprintf implementation to support all of them. The good thing is that, for 4 out of the 5 encodings, you'll just copy to the output buffer the sign and a string stating what encoding uses the number (0, denorm, Inf, or NaN). You must only develop the real value for normalized numbers, and in that case, you will format the mantissa in binary, and the exponent in decimal.

Single Precision		Object Represented	What you must write into the buffer
Exponent	Mantissa
0	0	zero	[-]0
0	nonzero	± denormalized number	[-]denorm
1-254	anything	± normalized number*	[-]mantissa_in_binary_2 x 2^([-]exponent_in_decimal)
255	0	± infinity	[-]inf
255	nonzero	NaN (Not a Number)	[-]NaN
* Note that there is a "_2 x " after the mantissa when it is printed out

Consider the following piece of code:

	.data
__buffer:
	.space  200
__format:
	.asciiz "%f"
__float:
	# here goes the code in the table's left column
	***

	.text

	addi $sp, $sp, -20          # space for the stack of parameters
	la   $t0, __buffer
	sw   $t0, 0($sp)            #  0($sp): __buffer
	la   $t0, __format
	sw   $t0, 4($sp)            #  4($sp): __format
	la   $t0, __float
	lw   $t0, 0($t0)
	sw   $t0, 8($sp)            #  8($sp): __float   (%f)
	jal  sprintf

The following table shows some examples of how your sprintf code must deal with different floating point values. The left column of the table shows what goes in the line indicated by "***", and the right column what sprintf must write into the output buffer.

Code in "***"	Output Buffer
.word 0xffff0000	-NaN
.word 0x7f800000	inf
.word 0x00100000	denorm
.word 0x80000000	-0
.float 1.2e25	1.00111101101000110010101_2 x 2^(83)
.float 1048576.5	1.000000000000000000001_2 x 2^(20)
.float 1048576.125	1.00000000000000000000001_2 x 2^(20)
.float 1048576.0625	1.0_2 x 2^(20)
.float 0.5078125	1.000001_2 x 2^(-1)
.float -0.03125	-1.0_2 x 2^(-5)
.float +1.125	1.001_2 x 2^(0)
.float -1.25	-1.01_2 x 2^(0)
.float -1.5	-1.1_2 x 2^(0)
.float -1.0	-1.0_2 x 2^(0)

5.3 Tower of Hanoi

The next part of your project is to write a MIPS assembly language implementation of a function that will fill a character array with the list the moves needed to solve a Tower of Hanoi puzzle of size n, where n is a positive integer (i.e. n > 0). If we asked to write this in Scheme, your code may look like this:

  (define (hanoi peg1 peg2 peg3 discs)
    (if (= discs 1)
        (list (cons peg1 peg3))
        (append (hanoi peg1 peg3 peg2 (- discs 1))
                (append (list (cons peg1 peg3))
                        (hanoi peg2 peg1 peg3 (- discs 1))))))

The C prototype for the function you are implementing is as follows:

  void hanoi(char* result, char peg1, char peg2, char peg3, int discs);

result will be a buffer you will write your result into using the sprintf function you wrote in the previous part. peg1, peg2, and peg3 will be names of the pegs. discs is the number of discs to move. You can assume result will have more than enough space to output your result and discs will only be passed integers greater than 0. If you have not noticed, there are 5 variables to hanoi. Based on what you have been discussed in this project, it should be clear which variables will appear where.

When your Tower of Hanoi function returns, the output buffer should be similar to the line below:

    (a . c)(a . b)(c . b)(a . c)(b . a)(b . c)(a . c)\0

In other words, there are no leading whitespaces, no spaces between the pairs, and no trailing whitespace after the list of pairs. Like any C string, it is null terminated. Do NOT terminate the buffer with a newline character. It will be added by the call to SPIM's printf function.

5.4 Testing

To test your sprintf, you need to load two files in the correct order: run xspim (or spim), load test.sprintf.s, then load sprintf.s. Finally, run your program. Testing your Tower of Hanoi MIPS implementation is similar to testing sprintf--loading test.hanoi.s, then sprintf.s, and finally hanoi.s. The following Makefile may make your life easier. make sprintf will test your sprintf implementation and make hanoi will test your Tower of Hanoi implementation. Note: certain errors will not be reported by spim/xspim to you if you use the Makefile

5.5 Submission Details

From within the directory containing your code, run submit proj2. You must include the following files: sprintf.s, hanoi.s, and README. Additionally, make sure no labels in your solutions begin with '__'. The testing framework will use labels that begin with __.

6. Miscellaneous Requirements

• Obey all register conventions in this project: return the number of characters in $v0 and do not use $sx registers without saving them first. In particular, remember that the $ax registers are temporary registers, so they will be clobbered by any function call. Points will be deducted for violations of these conventions. Your sprintf function must work with the main function supplied in test.sprintf.s (as well as work with hanoi.s).

• Addenum to the register conventions -- $sp points to the lowest occupied space of the stack. This means you will need to move the stack pointer (i.e. addi $sp, $sp, 4) befor using the 0th offset of the stack pointer (i.e. sw $ra, 0($sp)).

• You MUST comment your MIPS code. The readers will read it, and they need to be able to quickly understand what every section does. A common style for commenting assembly is to include a long introductory comment before every block of assembly statements, with a short comment after every line telling what it does. The introductory comment must describe the algorithm that the following block implements. The line-by-line comments must just be an easy-to-read version of the assembly code, using real variable names and perhaps more C-like constructs. If your code ends up being at least as much comment as code, this is probably a sign that you are doing a good job of commenting.

• Put your login name, section, and TA information at the top of hanoi.s and sprintf.s.