CS61C Spring 2007

Project 02
sprintf for MIPS

The Two TAs in charge:

Updates

Purpose

Gain experience with:

and generally become an all-around totally awesome assembly programmer.

Instead of one big, long, crazy project, you will do two smaller, shorter, sane sub-projects and one additional exercise.

Getting Started

Copy them from ~cs61c/proj/02 by typing the following:

cp -r ~cs61c/proj/02 ~/proj

This copies three files you will turn in (sprintf.s, ackerman.s, fp.c) as well as a Makefile and corresponding test harnesses for each of the files you will turn in.

Submission

To submit your project, create a directory named proj2 that contains: sprintf.s, ackerman.s and fp.c. From within that directory, type "submit proj2".

The project deadline is 11:59:59pm on Friday, March 09, 2007.

DEADLINE WARNING We strongly encourage you to finish the project by Friday, 2nd March.  The midterm (on Monday, 5th March) will have sizable MIPS and float content and it will be best for you to have done this MIPS/float intenstive project.  You should especially be sure to have completed parts 2 (floats) and 3 (recursive MIPS).

Part 1: sprintf

In this project you will be writing a C function sprintf:
int sprintf (char *outbuf, char *format, ...)

sprintf is similar to printf, except that it writes to the string outbuf instead of to standard output. outbuf already points to pre-allocated space - large enough to hold the string. The second argument is the format string (much like printf) - more specifically a memory address that starts a null-terminated string. 

Arguments:

Your function must accept any number of arguments, passed according to a MIPS standard conventions: If there are more than four arguments, the additional ones will be spilled to the stack, with the first "spilled" argument in the lowest stack position (meaning, the address closer to zero. Looking at the figures in the tutorial below, this means closer the to top).

Return:

More Details about arguments:

Since there can be an arbitrary number of arguments to the sprintf function, all arguments after the fourth (if they exist) will be passed on the stack. Before your function is called, the caller will save any extra arguments to the stack in the same way $s0-$s7 registers are saved. (By doing sw $s0, offset($sp)). In order to access these variables, you will need to figure out the correct offset in relation to the callee stack pointer.

For example, if the caller stores an argument in 0($sp), the callee might access the argument at 8($sp), depending on how the stack pointer is moved in the callee function. (NOTE: It is not always an offset of 8, it depends on how the stack is moved)

If this is at all confusing to you, please read this Tutorial on MIPS stack management with more detailed information and nifty diagrams.

What you need to do:
Within sprintf.s, you will be implementing format specifiers that significantly differ from those in the ANSI sprintf.  Here are the ones you are to implement (Remember, they are case-sensitive):

What you don't need to do:

Testing sprintf

To run this portion of the project, you can type "gmake sprintf". This creates temporal.sprintf.s by combining test.sprintf.s (a test harness) and your sprintf.s. Then, it runs that combined file through SPIM. If your sprintf procedure does not behave as expected, you can load temporal.sprintf.s manually into SPIM and debug from there.

Part 2: Floating Point

Fill in the C function:

void sprint_double(char* outbuf, uint64_t f)
The function should write into outbuf a string corresponding to interpreting f as an IEEE 754 64-bit floating point number (a.k.a. double-precision float) using the guidelines below. As is the case with sprintf, you may assume that outbuf already has enough space allocated to hold your float.  Put your code in the framework in fp.c. Test code is provided in test.fp.c.  You can compile and execute your code under the test bench by typing "gmake fp".

Recall that uint64_t is the C99 64-bit int type.

Print it out according the format specified below:


The following table lists all the floating point possibilities:

Double Precision Object Represented What you must write into the buffer
Exponent Mantissa
0 0 zero [-]0
0 nonzero ± denormalized number [-]denorm
1-2046 anything ± normalized number [-]mantissa_in_binaryE[-]exponent_in_binary
or
[-]whole_part_in_binary.fractional_part_in_binary
according to rules above
2047 0 ± infinity [-]infinity
2047 nonzero NaN (Not a Number) [-]NaN

Sample cases:

Value in argument (f) What gets printed to buffer
Hex (spaces added for readability, not implementation)
0x ffff 0000 0000 0000 -NaN
0x 7ff0 0000 0000 0000 infinity
0x 0001 0000 0000 0000 denorm
0x 8000 0000 0000 0000 -0
0x 3455 4342 0000 0000 1.0101010000110100001E-10111010
Floating point arguments
35 100011
64 1.0E110
-96 -1.1E110
-0.375 -0.011
2.75 10.11
.0625 1.0E-100

Part 3: Ackerman Function - A quick exercise

Implement ackerman(m,n), a recursive algorithm to compute the Ackerman Function, one of the fastest growing functions ever created, in MIPS. NOTE: You must use this recursive algorithm. Iterative solutions will receive zero (zip, nothing, nada) points.

Given m and n (in $a0 and $a1), return the ackerman(m,n) entry in $v0. You can treat m and n as unsigned ints.

Do not worry about error checking the inputs (m and n should be non-negative) or overflow.

Code in scheme:

(define (ackerman m n)
(if (= m 0)
(+ 1 n)
(if (= n 0)
(ackerman (- m 1) 1)
(ackerman (- m 1) (ackerman m (- n 1))))))

Put your code in the framework given in ackerman.s. You can test your ackerman procedure by typing "gmake ackerman". This combines ackerman.s and test.ackerman.s into temporal.ackerman.s and feeds the combined file through SPIM. Like sprintf, if your ackerman procedure is not behaving as expected, you can debug temporal.ackerman.s file.

Things to keep in mind