CS 61C (Fall 2007) |
Project 2Submit as "proj2". Due 2:45pm before lecture 10/3/2007. |
This is an individual assignment; you must work alone. Submit your solution, a file named snprintf.s, as proj2.
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/files/proj/2/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.
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 the file ~cs61c/bin/mars/mars-cs61c.jar
, 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 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.