The purpose of this project is to familiarize you with the details of
the MIPS calling convention and pump up your assembly programming
skills.
To submit your project, create a directory named proj2 that contains your sprintf.s file. From within that directory, type "submit proj2".
The project deadline has been extended to 11:59pm on Friday, October 15th.
This is an individual project, not to be done in
partnership. Hand in your own work, and do not collaborate with
anyone else.
This document mentions certain test cases. However, this
input/output behavior is not a comprehensive specification of all
possible behavior. Therefore, even if your project submission passes
all of the test cases mentioned here, it may not be entirely correct.
We strongly urge you to create test cases in addition to the ones
provided here.
To help you with questions you can have, please first consult the
project FAQ.
By now, you should know how to manage the stack when writing procedures in MIPS. Let's assume you have a function light_blue, which calls a function dark_blue. The very first thing that light_blue does is to allocate space in the stack for its variables (prolog). In Figure 1 (middle) we can see that it allocates space for 4 words. light_blue eventually calls dark_blue, which allocates space for its own variables. Figure 1 (right) shows that dark_blue has allocated space for 2 words.
Figure 1 |
The MIPS procedure calling convention uses registers $a0-$a3 for passing arguments down to procedures. If there are more than four, the remaining arguments are passed on the stack. How is this mixed with the normal stack managing? Each argument gets one word of stack space. Suppose we are trying to write in MIPS assembler a program like this:
int dark_blue (int x, int y, int quux, int bar, int baz) { int a; ... a = y; ... } int light_blue () { int c, d, e; ... dark_blue (3, 4, 43, 62, 1); ... }
Procedure dark_blue has five integer arguments. The space for those arguments is allocated on the stack as part of the caller's (light_blue) stack frame. In other words, light_blue, not dark_blue, must allocate the space.
Figure 2 shows this stack management method. light_blue now allocates space in the stack for its variables and the arguments that it will use to call dark_blue. We can see in Figure 2 (middle) that it allocates space for 9 words: 4 for its own consumption, and 5 for calling dark_blue.
light_blue eventually calls dark_blue, which allocates space for its own variables. Figure 2 (right) shows that dark_blue has allocated space for 2 words. Note that dark_blue can access to the 5 arguments by accessing to the beginning of the stack reserved by its caller process (light_blue).
Figure 2 |
The 5 arguments (patterned light-blue stack) are located at the lower addresses of light_blue's stack frame.
That is, light_blue will use 0($sp) to store the argument x, 4($sp) to store the argument y, and so on. Therefore, dark_blue will use 8($sp) to access to the argument x, 12($sp) to access to the argument y, and so on.
Note that the first argument is always at the caller's stack frame lowest address, and the last argument at the highest address. You have to be consistent about this so that dark_blue knows which argument is which.
light_blue: # prolog addi $sp, $sp, -16 # allocate stack space for 4 words: # $ra, c, d, and e sw $ra, 12($sp) # save $ra # use 0($sp) to save c ($t0) when needed # use 4($sp) to save d ($t1) when needed # use 8($sp) to save e ($t2) when needed # body ... addi $t0, $0, 3 # assume this holds the value of c addi $t1, $0, 4 # assume this holds the value of d addi $t2, $0, 5 # assume this holds the value of e ... # this is the call to dark_blue addi $sp, $sp, -20 # allocate stack space for 5 words (patterned # light-blue): the args x, y, quux, bar, baz sw $t0, 20($sp) # save c before calling dark_blue sw $t1, 24($sp) # save d before calling dark_blue sw $t2, 28($sp) # save e before calling dark_blue add $a0, $0, $t0 # arg x = c sw $a0, 0($sp) # (proper MIPS convention doesn't require $a0 in stack, but we do) add $a1, $0, $t1 # arg y = d sw $a1, 4($sp) # (proper MIPS convention doesn't require $a1 in stack, but we do) addi $a2, $0, 43 # arg quux = 43 sw $a2, 8($sp) # (proper MIPS convention doesn't require $a2 in stack, but we do) addi $a3, $0, 62 # bar = 62 sw $a3, 12($sp) # (proper MIPS convention doesn't require $a3 in stack, but we do) addi $t0, $0, 1 # baz = 1, but no more registers sw $t0, 16($sp) # so pass on the stack jal dark_blue addi $sp, $sp, 20 # restore stack space used for calling dark_blue ... # epilog lw $ra, 12($sp) # reload return address addi $sp, $sp, 16 # restore stack space jr $ra # return to caller ... dark_blue: # prolog addi $sp, $sp, -8 # allocate stack space for 2 words: # $ra, a sw $ra, 4($sp) # save $ra # use 0($sp) to save a when needed # body ... add $t0, $0, $a1 # get argument y (you can also get it from the stack) lw $t1, 24($sp) # *** (see below) # 8 (dark_blue's frame) + 16 = 24 up on stack # fetched argument baz ... # epilog lw $ra, 4($sp) # reload return address addi $sp, $sp, 8 # restore stack space jr $ra # return to caller
The instruction indicated by "***" is the key to understanding the
stack method of argument passing. Procedure dark_blue is referring to a
word of stack memory that is from the caller's stack frame. Its own
frame includes only the two words 0($sp) and 4($sp).
Write a MIPS assembly language implementation of the C function sprintf:
int sprintf (char *outbuf, char *format, ...)
sprintf works like printf, except that it writes to the string outbuf instead of to standard output. outbuf is assumed already to point to allocated memory sufficient to hold the generated characters. Your function must accept any number of arguments, passed according to a non-MIPS standard conventions: All the arguments will be passed through the stack, with the first argument in the lowest stack position (lowest in value, i.e., closer to zero. This is equivalent to closer to the top in both Figure 1 and 2.) See the last extra note of this document to clear up how argument passing should work.
The first argument is the address of a character array into which your procedure will put its results. The second argument is 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. sprintf returns the number of characters in its output string not including the null at the end.
You do not have to do any error checking (e.g. comparing the number of arguments to the number of % specifications). You also do not have to implement all of the formatting options of the real sprintf. Here are the ones you are to implement:
Don't implement width or precision modifiers (e.g., %6d ). Copy the two files sprintf.s and test.sprintf.s. Or you can grab the files from your accounts in the folder ~cs61c/lib/proj2/ . Only your sprintf.s will be graded. You should modify test.sprintf.s to test your code more thoroughly.
To run this project, you need to load two files in the correct order:
run xspim and load test.sprintf.s. Next load sprintf.s. Finally, run your
program. The following Makefile may make
your life easier.
Formatting floating-point numbers is a hard problem. Therefore, we will use a different format than what the real sprintf produces.
Remember that the IEEE 754 standard defines 5 different encodings for single-precision FP numbers: zero, normalized numbers, denormalized numbers, NaN, and infinity. We want your sprintf implementation to support all of them. The good thing is that, for 4 out of the 5 encodings, you'll just copy to the output buffer the sign and a string stating what encoding uses the number (0, denorm, Inf, or NaN). You must only develop the real value for normalized numbers, and in that case, you will format the mantissa in binary, and the exponent in decimal.
Single Precision | Object Represented | What you must write into the buffer | |
Exponent | Mantissa | ||
0 | 0 | zero | [-]0 |
0 | nonzero | ± denormalized number | [-]denorm |
1-254 | anything | ± normalized number | [-]mantissa_in_binaryb 2^([-]exponent_in_decimal) |
255 | 0 | ± infinity | [-]Inf |
255 | nonzero | NaN (Not a Number) | [-]NaN |
Consider the following piece of code:
.data __buffer: .space 200 __format: .asciiz "%f" __float: # here goes the code in the table's left column *** .text addi $sp, $sp, -20 # space for the stack of parameters la $t0, __buffer sw $t0, 0($sp) # 0($sp): __buffer la $t0, __format sw $t0, 4($sp) # 4($sp): __format la $t0, __float lw $t0, 0($t0) sw $t0, 8($sp) # 8($sp): __float (%f) jal sprintf
The following table shows some examples of how your sprintf code must deal with different floating point values. The left column of the table shows what goes in the line indicated by "***", and the right column what sprintf must write into the output buffer.
Code in "***" | Output Buffer |
.word 0xffff0000 | -NaN |
.word 0x7f800000 | Inf |
.word 0x00100000 | denorm |
.word 0x80000000 | -0 |
.float 1.2e25 | 1.00111101101000110010101b 2^(83) |
.float 1048576.5 | 1.000000000000000000001b 2^(20) |
.float 1048576.125 | 1.00000000000000000000001b 2^(20) |
.float 1048576.0625 | 1.0b 2^(20) |
.float 0.5078125 | 1.000001b 2^(-1) |
.float -0.03125 | -1.0b 2^(-5) |
.float +1.125 | 1.001b 2^(0) |
.float -1.25 | -1.01b 2^(0) |
.float -1.5 | -1.1b 2^(0) |
.float -1.0 | -1.0b 2^(0) |
Here is where we deviate. For this project, your sprintf function will assume that:
In conclusion, your sprintf must get all arguments, all the time, from the stack.