CS61C Spring 2007
Project 02
sprintf for MIPS
The Two TAs in charge:
Updates
- March 1 at 2:45am -- The definitions of "unbiased" and "biased" exponents may be unclear. The are defined as follows:
- BIASED EXPONENT - The exponent that is stored in the bits of an IEEE 754 floating point number
- UNBIASED EXPONENT - The number x in the expression 2^x. That is the actual "mathematical" exponent in scientific notation.
- In other words, the unbiased exponent is less than the biased exponent.
- One more item: Remember for part 2, that we are dealing with doubles - 64 bit floating point numbers.
- Feb 26 at 2:10pm -- The stack pointer wasn't being restored
correctly when returning from test.sprintf.s. Please update your copy
of
test.sprintf.s
.
- Feb 26 at 1:15am -- There were some errors in the C code within the background. They are now fixed.
- Feb 23 at 10:30am -- There was a small error in test.ackerman.s. Please update your copy of test.ackerman.s
Purpose
Gain experience with:
- MIPS calling convention,
- recursive functions in MIPS,
- floating point representation
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.
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).
- The first argument is the address of a character array into
which
your procedure will put its results.
- The second argument is the address of 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.
Return:
- sprintf returns the number of characters it wrote to its
output string not including the null at the end.
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):
- %b: Number passed in should be interpretted as an unsigned
number and printed in binary. Do not print any leading zeros.
Number passed in |
Printed out as |
0 |
0 |
2 |
10 |
6,483 |
1100101010011 |
3,698,384,374 |
11011100011100001101110111110110 |
- %t: Number passed in should be interpreted
as an signed
(two's-complement) number and printed in binary. Do not print
any
leading zeros. If the number is negative, print a "-" sign
followed by the absolute value of the number (in binary). If it is
positive, behavior is the same as %b.
Number Passed In |
Printed Out as |
0 |
0 |
5 |
101 |
-2 |
-10 |
-8375 |
-10000010110111 |
- %c: Interpret the argument as a character. Print
it out as
one. For instance, if a 'f' is passed in as the argument, an
f
should be outputted. (This is the same as ANSI C behavior). NOTE:
All arguments (even individual characters) to sprintf always occupy 4
bytes.
- %s: Interpret the argument as a string (a pointer to the
start of
a null-terminated string). Copy this string to the output.
(This is the same as ANSI C behavior). You may
assume that the argument is non-null.
- %%: "%%" should output "%", "%%%%"
should output "%%" and so on.
- Invalid Specifiers: If you receive an
escape sequence not specified above, simply output the character.
Ex: "%Q" should output "Q".
What you don't need to do:
- Variable width or precision modifiers
(e.g., %5.2f ).
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:
- If the unbiased exponent is less than -3 or greater than 5,
print it as format: [-]1.ddd...dE(+/-)xxx...x where 1.ddd...d is the
mantissa represented in binary (note the leading 1), E
stands for Exponent (where the right side is the power of 2 to multiply
the mantissa by - recall scientific notation), and xx is the
(unbiased) exponent in binary. If
the mantissa is 1.0, print out 1.0Exxxx...x Do not have any
leading 0's on the exponent or trailing 0's on the mantissa.
- Otherwise, print the number as: [-]mmmmmm.ddd...d, where
mmmmmm is the whole number part of the float and ddd...d is the
fractional part. Both are in binary. Do not have trailing or
leading zeroes. In other words, if the fractional part is 0, do not
print the decimal point or anything after it. If the absolute
value of the number is less than 1, you should start with '0.' (no
quotes - see examples below)
- In both cases, the '-' is printed if the number is
negative. Leading zeros are not printed, except as indicted previously.
- Handle zero, denorm, infinity, and NaN as shown below in
the table.
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
- 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
procedure must work with the main function supplied in test.sprintf.s
Also, bear in mind that our autograder assumes that
sprintf obeys register conventions (and might just test for
it!).
- You must comment your MIPS code. The
graders 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.
- Minimum-Effort Digit Formatting: For all
the number formatting cases, you must minimize the number of digits
your sprintf prints. For example, if the user
tries to format the number 19 (decimal), your sprintf must format it as
"10011" in binary, and not as, say, "00010011".
- Use breakpoints to debug your MIPS code. SPIM is not
only a MIPS R2000 interpreter, it is also a debugger as well. Thus,
it is to your advantage to use SPIM's debugging functions, especially
its breakpoint functionality. Recall that you can set breakpoints using
addresses or global labels.
- Build incrementally. You should build up your MIPS code
gradually by implementing one element of your sprintf code one at a time
instead of all at once. This will save you time debugging and perhaps you sanity.
Thus, a good checkpoint is being able to return the format string. After that, you
can then try to handle each format specifier one by one.