CS 61C, Summer 2008
Due Friday, July 18, 2008 @ 11:59pm
Last Updated July 9, 2008 @ 11pm
CS 61C (Summer 2008) |
This is an individual assignment; you must work alone. Submit your solution as proj2 with the files fp.c and snprintf.s.
This part of the project taken from Fall 2007
This project should give you more practice with representation of data types, in particular, working with how they are passed as arguments on a MIPS processor. It will also give you more experience with MIPS assembly language programming.
Make a directory named proj2 in your home directory. Then copy the file ~cs61c/public_html/su08/assignments/proj/proj2/snprintf.s to the directory; this is a main program that includes several calls to snprintf, and into which you should put your code.
For this project we will be running our code in MARS, a MIPS simulator which provides a rich debugging GUI, rather than trying to run on a bare processor. In general, assembly programmers prefer this mode of development when possible as it is far easier to debug and work with the code.
You can run MARS in the lab, by
running ssh -X cory
, entering your password and then running mars-cs61c
on cory
. If you
forget to run ssh -X cory
to log into cory.cs.berkeley.edu
before running MARS,
the GUI will not display properly. This seems to be a problem with the java installation on nova
.
To run MARS from home, you can download it from ~cs61c/bin/mars/mars-cs61c.jar
or here, which is an executable
JAR file. To run it, simply open a command line, navigate to the directory containing mars-cs61c.jar
and
run java -jar mars-cs61c.jar
. Of course this will only work if you have java installed properly and
on your path.
When you go to open your file snprinf.s
in MARS, the "home" icon in the open file dialog will get you back
to your normal home directory.
You are to provide a MIPS assembly language implementation of the C function snprintf:
int snprintf (char *outbuf, size_t outbufsize, char *format, ...)
snprintf is similar to printf, except that it writes to the
first argument, the string outbuf, instead of to standard output (the screen).
A terminating null character ('\0'
) is written to outbuf prior to
return from snprintf. The second argument specifies the size of the
output buffer referred to by outbuf, in bytes (we will be using ASCII for this
project so 1 byte = 1 character). The third argument is the
format string, much like printf's.
Some special cases:
outbufsize
bytes total and we need space for a null terminator) instead of being written to the array
and a null byte is written at the end of the array.Your function must accept any number of arguments, passed according to 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. (This means the address closer to zero.)
The first argument is the address of a character array into which your procedure will put its results.
The second argument is the number of characters that the array can hold. This count includes space for the terminating null byte.
The third argument is the address of the start 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.
snprintf returns the number of characters it wrote to its output string, not including the null at the end. The return value will not exceed outbufsize-1.
Since there can be an arbitrary number of arguments to the snprintf 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 your code moves the stack).
If this is at all confusing to you, please read this tutorial on MIPS stack management from Spring 2007 with more detailed information and nifty diagrams.
Within snprintf.s, you will be implementing format specifiers that differ from those in the ANSI snprintf. The ones you are to implement are listed below. All are case-sensitive.
%d: Interpret the argument word as a signed decimal value, and write the signed decimal representation with no leading zeroes to the output string.
%u: Interpret the argument word as an unsigned value, and write its decimal representation (again with no leading zeroes) to the output string.
%x: Interpret the argument word as an unsigned value,
and write its hexadecimal representation (again with no leading zeroes)
to the output string (use lowercase
a-f
).
%c: Interpret the low-order byte of the argument word as a character, and write it to the output string. (This means that all arguments to snprintf, even single characters, occupy 4 bytes = 1 word).
%s: Interpret the argument as a pointer to the start of a null-terminated string. Copy this string to the output. Don't change the output if the character pointer is 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".
%
as last character of format string: Simply output
a %
.
Ex: "%" should output "%".
Variable width or precision modifiers (e.g., %5.2f).
String length limits (e.g., %5f
).
The ANSI standard notes that for various error cases, snprintf's behavior is undefined. Listed below are some error cases, along with how you should handle them for this project.
Error case | How to handle it |
The output buffer is null. | Return 0. |
The format string is null. | Return 0 without changing the output buffer. |
The number of characters to print is greater than the output buffer size minus 1. | Discard extra characters. |
The format string contains occurrences of '%' followed by a character that's not one of 'd', 'u', 'x', 'c', 's', or '%'. | Copy the unrecognized character to the output buffer ("%z" becomes "z"). |
The string argument corresponding to a "%s" in the format string is null. | Copy nothing to the output buffer for that format specifier. |
You may assume that there at least as many things to print as there are format specifiers. It would be nice to be able to test this, but it isn't possible (hint: try to figure out how to test for this, it can't be done and you'll soon see why.)
Obey all register conventions in this project. return the number of characters in $v0 and do not use $s? registers without saving them first. In particular, remember that the $a? registers are temporary registers, so they will be clobbered by any function call. Points will be deducted for violations of these conventions. Your snprintf procedure must work with the main function supplied in snprintf.s Also, bear in mind that our autograder assumes that snprintf obeys register conventions (and will probably 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. Your code, like ours, should be at leasat 50% comments, if not more. Professionally written assembly is often 75% or more comments.
Don't print leading zeroes. For all the number formatting cases, you must minimize the number of digits your snprintf prints. For example, if the user tries to format the number 19 (decimal), your snprintf must format it as "13" in hexadecimal, and not as, say, "00000013".
Use breakpoints to debug your MIPS code. MARS provides fantastic debugging functionality. Use it, or you'll regret it.
Build incrementally. You should build up your MIPS code gradually by implementing one element of your snprintf 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.
You should consider writing a complete set of test cases as part of your solution. Building these test cases as you add functionality will allow to quickly verify that any new functionality has not broken your old functionality. Consider automating these tests as much as possible to save yourself time in the long run. We will post the highlites of our autograder tests once they are finished.
First copy over the files fp.c, fp.h, student.h, test.fp.c, and Makefile from ~cs61c/public_html/su08/assignments/proj/proj2/. Note that all of your changes must be in fp.c and student.h. The other files should not be changed, and you should not add additional files. You can compile and execute your code under the sample test bench by using the Makefile by typing "gmake fp".
Fill in the following C functions in fp.c:
fixed_point_t float_half_conversion(uint16_t f, enum format_t format);
void printf_converted_float(fixed_point_t value);
The data type format_t is an enumerated data type with two possible values (BINARY_POINT and EXPONENT_NOTATION). The two possible values will indicate which output format to use when handling denorms or regular normalized floats.
The function float_half_conversion should create a structure of type fixed_point_t (whose format is discussed below) that has a value equivalent to treating the argument uint16_t f as an IEEE 754r 16-bit floating point number (a.k.a. half-precision float) using the guidelines below. Recall that uint16_t is the C99 16-bit unsigned integer type. We use this to guarantee a type that is exactly 16 bits, as well as to make bit manipulation easier, even though we will not be treating the number as an integer.
The function printf_converted_float should take a copy of your created fixed_point_t structure, and print the value of the float that was used to create it according to the guidelines below.
The fixed_point_t structure has five fields. The float_half_conversion function should fill in these fields, and then the printf_converted_float function should use that data to print the desired output. Note that all of the printing *must* occur in printf_converted_float. Because of this, float_half_conversion must perform a conversion into the fixed_point_t format. This format will allow the printing function to do nothing more than print pre-calculated numbers in binary.
To create the fixed_point_t representation of a floating-point number, first determine what type of number it is (normalized, denormalized, infinity, zero, or NaN) and store a number that indicates which type it is in the type field. In the case of numbers that are not normalized or denormalized numbers, this is enough. For normalized and denormalized numbers though, we need to store a representation of the float that works for both the BINARY_POINT and EXPONENT_NOTATION formats. This representation consists of the bits in integer_portion being on the left-hand side of an imaginary binary point, and the bits in fractional_portion being on the right-hand side of the imaginary binary point. Note that the bits in integer_portion are right-aligned (meaning that all of the significant bits are in the right-most bits of integer_portion, with leading zeros), and that the bits in fractional_portion are left-aligned (with trailing zeros). The current_exponent field allows us to shift bits around and change the exponent appropriately to maintain the same value. This allows us to simply shift bits to achieve a current_exponent of zero to get the BINARY_POINT format, and to shift bits around to get a single "one bit" in the right-most bit of integer_portion to get the EXPONENT_NOTATION format.
Format of IEEE 754r half-precision float:
Fields: |
Sign |
Biased Exponent (Bias of 15) |
Significand Expression |
Width in bits: |
1 |
5 |
10 |
Print it out according the format specified below:
A bit of clarification on biased vs. unbiased:
The following table lists all the floating point possibilities:
Half Precision |
Object Represented |
What you must print |
|
Exponent |
Mantissa |
||
0 |
0 |
zero |
[-]0 |
0 |
nonzero |
± denormalized number |
[-]mantissa_in_binaryE[-]exponent_in_binary |
1-30 |
anything |
± normalized number |
[-]mantissa_in_binaryE[-]exponent_in_binary |
31 |
0 |
± infinity |
[-]infinity |
31 |
nonzero |
NaN (Not a Number) |
[-]NaN |
Sample cases:
Value of f in Hexadecimal |
Value of f in Decimal |
What gets printed (format == BINARY_POINT) |
What gets printed (format == EXPONENT_NOTATION) |
0x fc1a |
N/A |
-NaN |
-NaN |
0x 7c00 |
Infinity |
infinity |
infinity |
0x 0001 |
2^-24 |
0b0.000000000000000000000001 |
0b1.0E-11000 |
0x 8000 |
0 |
-0 |
-0 |
0x 3455 |
0b0.010001010101 |
0b1.0001010101E-10 |
|
0x c900 |
10 |
-0b1010.0 |
-0b1.01E11 |
0x 8400 |
-2^-14 |
-0b0.00000000000001 |
-0b1.0E-1110 |