This is an individual assignment; you must work alone. Submit your solution as proj2 with the files fp.c and snprintf.s.

Part 1 - MIPS implementation of snprintf

This part of the project taken from Fall 2007

Goals

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.

Getting started

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.

Note carefully the line below which all your changes must be made, do not make any changes above that line or in other files.

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.

snprintf

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:

• if outbufsize is 0, nothing is written and outbuf can be a null pointer
• if the number of characters to be output exceeds the size of the buffer, output characters beyond the outbufsize-1st are discarded (remember we have 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.

Arguments

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.

• The remaining arguments are values that are to be converted to printable character form according to the format instructions.

Return

• 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.

More details about arguments

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.

What you need to do

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 "%".

What you don't need to do

• Variable width or precision modifiers (e.g., %5.2f).

• String length limits (e.g., %5f).

Handling error cases

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.

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.)

Things to keep in mind

• 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.

Testing

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.

Part 2 - Conversion and Printing of Floats in C

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:

Print it out according the format specified below:

• If the format argument is equal to EXPONENT_NOTATION, print the normalized or denormalized number in format: [-]0b1.ddddddddddE[-]xxxx where “1.dddddddddd” 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 “xxxx” is the (unbiased) exponent in binary. If the mantissa is 1.0, print out 0b1.0E[-]xxxx. You should not have any leading 0's on the exponent or trailing 0's on the mantissa, except for the case where the mantissa is 1.0. Note that if the unbiased exponent is equal to 0 (zero), then the exponent portion should appear as “E0”, which is a capital letter E, and the digit zero.

• A bit of clarification on biased vs. unbiased:

• BIASED EXPONENT - The exponent that is stored in the bits of an IEEE 754r 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
• Unbiased exponent = biased exponent – exponent bias
• One more item: Remember for this portion of the assignment, that we are dealing with half-precision floating points - 16 bit floating point numbers.
• If the format argument is equal to BINARY_POINT, print the number as: [-]0bmmmmmm.dd...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 any trailing or leading zeroes, except for those used to indicate a whole or fractional part that is equal to zero. If the whole part is equal to zero (meaning that the entire number is fractional), the format should be [-]0b0.ddddddd...d. If the fractional part is 0, the format should be [-]0bmmm...m.0
• In both cases, the '-' is printed if the number is negative. Leading zeros are not printed, except as indicated previously.
• Handle zero, infinity, and NaN as shown below in the table, where [-] means that you should print a minus sign at that position if the number has the sign bit set, and you should not print a minus sign if the sign bit is not set. The brackets are merely to indicate that the sign bit is conditional. No brackets should ever appear in your results.
• Note that the revised specification requires you to produce output for denorms that is in the same format as normalized numbers.

The following table lists all the floating point possibilities:

Sample cases:

Note that your printf_converted_float function should never print a newline character!