Replicating a Function in C: Implementing sprintf()
For this assignment, you will use MIPS to implement a (limited) sprintf() function, with behavior similar to what is supplied by the C standard library. The library version of sprintf() is used to send formatted output to a string:
int sprint(char *str, const char *format, ...)
The first parameter of the function str contains a pointer to an array of char elements where the resulting C string is stored (in other words, an address). The second parameter format contains the text to be written to str, and can optionally contain embedded format tags that are replaced by the values specified in subsequent additional arguments and formatted as requested. For the purpose of this assignment, you can assume that these format tags will be limited to unsigned decimal integers (%u) and other strings (%s). If successful, the total number of characters written to str is returned, excluding the null-character appended at the end of the string. If a failure occurs, a negative number is returned.
You will be using the MARS simulator for this assignment. A link to the simulator is available here and also in the Course Resources page on Canvas under the Course Tools heading. In order to make use of the testing harness that is provided for this assignment, you may need to select the “Assemble all files in directory” setting in MARS, as shown here:
Additionally, you should always have main.asm open in the editor tab when you assemble the code. If the edit tab is on any other file, the build process will create a standalone application for that file. The code may assemble successfully, but will terminate with errors when you attempt to run the resulting executable.
Your goal for this assignment is to complete the procedures contained in the sprintf.asm file, supporting the specification that is included in both the file as well as here:
/** Given the address of a string and a string which may or may not include format
*specifiers, write a formatted version of the string into the output register $v0
*
*Pre: $a0 contains the address of string dest, where the final string will be
*written into
*$a1 contains the address of a format string, which may or may not include
*format specifiers, and which details the required final state of the
*output string
*$a2 contains an unsigned integer or the address of a string, or is empty
*$a3 contains an unsigned integer or the address of a string, or is empty
*
*Post: $a0 contains the address of the formatted dest, including null terminator
*Returns: $v0 contains the length of the string written into dest, not including null
*terminator
*/
For the assignment, you may make the following assumptions:
$a0 will point to a memory location with sufficient space for you to write the final formatted string.
$a1 will contain no more than two format specifiers, and $a2 and $a3 will properly match the order and format requirements of these specifiers (i.e., a format string “abc %u def %s\n” that is provided in $a1 will be accompanied by an unsigned integer in $a2 and a string in $a3).
No “%” characters will be used in the format string, except to denote format specifiers (i.e., there is no need to consider % escape characters).
No modifiers will be applied to the format specifiers; they will only appear as %u and %s.
For example, consider the following case:
$a0 contains the address 0x400100, which points to empty memory space
$a1 contains the address 0x400200, which points to the string “This is example test case number %u!\n”
$a2 contains the number 42
$a3 contains 0x00000000, which could be interpreted no value or as the number 0
After running the procedure, $a0 should still contain the address 0x400100, which now stores the string “This is example test case number 42!\n”, and $v0 should contain the number 37.
Here is a suggested approach that you can consider when implementing your solution:
Because there is no way to know if $a3 contains a 0 or is not used, you can first identify the number of “%” characters in the $a1 string. This will tell you if you need to use both $a2 and $a3, only $a2, or neither of the two parameters.
Finding only one format specifier in “This is example test case number %u!\n”, you can disregard $a3 and only worry about including $a2 into the appropriate position in $a1.
Since the only format specifier is “%u”, you know that $a2 contains an unsigned decimal integer. This integer needs to be converted into a string in order to include it in the formatted string.
After 42 has been converted into “42”, it should replace the “%u” in the formatted string in $a1, with the output written into $a0. You can approach this by copying $a1 into $a0 character-by-character until reaching the format specifier, then copying the converted integer character-by-character into $a0, and then finally copying the rest of the $a1 format string into $a0.
The address of the final version of the string should still be stored in $a0.
The length of the final version of the string should also be stored in $v0.
You can see the opportunity to include several helper procedures in this approach. You may also create some helper procedures of your own, but you must also implement the following:
PROC_COUNT_FORMAT_SPECIFIERS: Given the address of a string, count the number of format specifiers that appear in that string. (Hint: Count the number of ‘%’ characters.)
PROC_CONVERT_INT_TO_STRING: Given an integer, convert it into a string. (Hint: A ‘digits’ allocation of memory is provided for you to write the string into and use in PROC_SPRINTF later.)
Some additional helper procedures are provided for you. Think about how you might use these in your solution before you start writing any instructions into MARS:
PROC_FIND_LENGTH_STRING: This procedure will find the length of a provided string by counting characters until the null terminator is reached.
PROC_FIND_NUM_DIGITS: This procedure will determine the number of digits in the provided integer input via iterative division by 10.
PROC_REVERSE_STRING: This procedure will reverse the characters in a string in-place when given the address of the first and last characters in the string.
PROC_CLEAR_DIGITS: This procedure will clear the contents of the ‘digits’ memory allocation that is defined in the data block of the sprintf.asm file. (Hint: If you properly null-terminate the strings that you create, you should never need to use this procedure.)
Some Notes on the Use of Registers
One of the clear challenges of writing code in any assembly language, including MIPS, is the small set of registers that are available to store data. Luckily, we have two techniques that work hand-in-hand to address this limitation: the use of procedures, and saving register values to the stack. Our convention for backing up these register values in MIPS depends on both the type of register and whether you are beginning a procedure or are calling a procedure. These rules are detailed for you at the end of the L03 MIPS Assembly Overview slides, but a short summary is:
Always back up the $ra register when starting a procedure if the procedure that you start calls another nested procedure. Otherwise, if Procedure A calls a second Procedure B which calls a third Procedure C, there will be no way to return back to the correct location of Procedure A from Procedure B.
Always back up registers $s0-s7 when starting a procedure if you write to them within the procedure, the procedure has been called by an outer procedure which has also written the same registers, and the outer calling procedure reads the same registers after the called procedure returns. There is no need to add $s4 to the stack if your called procedure doesn’t write to $s4 of if the outer calling procedure doesn’t write to $s4. But if your procedure does write to $s4 and if the calling procedure also writes to $s4 and then tries to read $s4 after the called procedure returns (expecting the register to hold the value set before the procedure call), then it is the responsibility of your called procedure to save whatever value may have been previously in the register, as well as to return it to its previous state when you conclude the procedure.
It is often recommended but not necessary to follow the $s0-s7 rules above when your procedure writes into registers $v0-v1 and $a0-$a3 (you will often write into these registers when performing a syscall within the procedure). Note, however, that $v0 and $v1 are intended for use when returning a value from a procedure. If you overwrite this return value when exiting the procedure, that return value will never get to the calling procedure.
It is the responsibility of the calling procedure to back up registers $t0-$t9 if you want to retain those values for use after returning from the procedure, if the calling and called procedure both write to these registers and if the calling procedure needs to read these registers after the called procedure returns. The called procedure itself has no responsibility to restore the values in these registers after it finishes executing.
Below is an example of a procedure MAIN which calls a procedure COMPUTATION. The COMPUTATION procedure writes into $s0, $s3, and $a0 as it processes data and the main procedure intends to read the same registers after COMPUTATION returns. The programmer also wishes to maintain the values of $t0-$t4 in MAIN when calling COMPUTATION, keeping that data available to use after returning from the procedure for similar reasons. In this case, the MIPS code should be structured as follows:
# MAIN code here: # COMPUTATION code here:
# ... subi $sp, $sp, 16
subi $sp, $sp, 20 sw $ra, 0($sp)
sw $t0, 0($sp) sw $s0, 4($sp)
sw $t1, 4($sp) sw $s3, 8($sp)
sw $t2, 8($sp) sw $a0, 12($sp) sw $t3, 12($sp)
sw $t4, 16($sp) # ... COMPUTATION BODY
jal COMPUTATION lw $ra, 0($sp) lw $s0, 4($sp)
lw $t0, 0($sp) lw $s3, 8($sp)
lw $t1, 4($sp) lw $a0, 12($sp)
lw $t2, 8($sp) addi $sp, $sp, 16 lw $t3, 12($sp)
lw $t4, 16($sp) jr $ra
addi $sp, $sp, 20 # ...
In this assignment, we will require you to follow these rules for stack manipulation, if and only if these are necessary because of the choice of registers that you make while writing your procedures. This includes both (1) appropriate management of the stack and stack pointer ($sp) to backup important registers, and (2) only backing up the minimum necessary for your code to properly function (i.e., don’t just copy and paste code at the beginning and ending of every procedure that backs up every required register). The TAs will perform a manual grading pass to verify compliance with this requirement. Though it is possible for you to complete this assignment without storing anything onto the stack, normal MIPS programming will require you to follow these rules. For example, creating or using a library will require you to follow these caller/callee register saving conventions, so that your library and code can properly interface.
Advice
Writing assembly code can feel very different from writing code in a high-level language, thanks to the limitations presented by the number of available registers, the fact that register names don’t reflect data contents the way that variable names do, and the low-level approach necessary to implement any functionality. As such, we recommend that you consider the following advice when working on your solutions:
Comment, comment, comment, comment, comment. It is incredibly easy to lose track of what data is stored in your registers, what step of the functionality you are currently addressing, and what you have already written and forgotten about. This may be one of those times when you need to add comments to every single instruction in your code, and that is totally OK to do! In our own solution, we even went beyond that, leaving ourselves additional explanations about the state of the computation. Here are just a few examples:
o# at this point, $t2 is pointed at \0
o# if we’re in this chunk of code, then we just hit a ‘%’ character
o# first, we need to determine if we’re loading the address from $a2 or # $a3 by checking the value in $s4
o# this section of code handles passing the integer into the #PROC_CONVERT_INT_TO_STRING procedure and initializing a pointer #to the first character in the subsequent string
In addition to your comments, labels are also your friend. Labels provide the functional purpose of serving as branch and jump targets, but there is nothing stopping you from adding additional labels to the code that serve as section heading reminders for you. For example, in our PROC_SPRINTF solution we jump over the section that handles inserting a string variable into the final string, with our branch targeting the integer variable section. Even though there’s no need for a label on the string variable section, we added one anyway as a reminder:
# jump to the integer segment if we found a u beq $t3, $t4, INTEGER_SEGMENT
STRING_SEGMENT:
# ... code to handle strings here
INTEGER_SEGMENT:
# ... code to handle integers here
Read the provided code. There are several procedures that are provided for you as helpers that you can use in your solution. They can also be used as templates for you to begin scaffolding your own procedures (is there much difference between looping over a string to count the total number of characters vs. looping over a string to count the number of ‘%’ characters?), as well as giving you some examples of good MIPS coding practices and reminders about how you can model certain computational patterns like loops and branches.
Add your own simple tests. The grading harness that is provided will score your performance on the output of an entire procedure, but there is nothing stopping you from creating your own testing file that lets you write a single test to check the correctness of the first quarter of the procedure that you have implemented. For example, when you are writing your PROC_SPRINTF procedure, you may want to start with handling the case where the formatting string contains zero format specifiers. After you code that segment, writing your own small tests to confirm that all text is accurately copied from the $a1 address to the $a0 address will be beneficial.
Print things. The grading harness won’t penalize you for including additional output, and sometimes the easiest way to ensure that MIPS is behaving as you intend is to print out the current state of a string at each iteration in the loop. Remember from 2505 that this is a perfectly valid method of debugging called instrumenting your code.
Don’t wait until a procedure is finished to test. Not to harp on the same point again and again, but these procedures can get complicated, and it is easy to lose track of the current state of the registers. If you test early, then you can have confidence that the first quarter of your procedure is bug-free, and that the second quarter is likely the location of the issue that you have just discovered.
Watch the MIPS lectures. They aren’t just posted on Canvas because we recorded them for fun. They’re helpful in getting you thinking in an assembly mindset, approaching a problem one small, incremental step at a time.
Division Details
Division in MIPS is a somewhat unique operation, which makes use of the hi and lo registers that are not directly accessible. Say that you run the unsigned division instruction divu $t6, $t1. This action computes $t6/$t1 as expected, but the result is stored as an integer in the lo register. Simultaneously, the remainder $t6%$t1 is computed and stored in the hi register. In order to access these results, you must use the mflo and mfhi instructions to retrieve the values and store them into a general-purpose register. For example:
mflo $t6: take the quotient stored in lo and copy it to $t6
mfhi $s7: take the remainder stored in hi and copy it to $s7
Testing/Grading Harness
Download the posted tar file, sprintf_harness.tar from Canvas and unpack it. You should receive the following files:
main.asm driver code for testing your procedures (don’t edit this file)
tests.asm the collection of tests that are executed on your code (don’t edit this file)
sprint.asm code file that contains helper procedures and scaffolding for you to implement your solutions
One important note is that this is a relatively new assignment, and so the grading harness is not as robustly designed and thoroughly debugged as 2506 assignments that have been in use for years. Despite our best efforts, there may be issues, and we ask that you report them as you discover them. If your code happens to misuse the stack, then the final grade report may be incorrect.
There are four components involved in computing your score, weighted as follows: PROC_COUNT_FORMAT_SPECIFIERS 100pts
PROC_CONVERT_INT_TO_STRING 100pts
PROC_SPRINTF 200pts
Manual grading of appropriate stack manipulation 100pts This assignment is worth 8% of your final grade in the course.
What to Submit
Please note that you may work with a partner on this assignment and we advise you to do so and to use collaborative (pair) programming. You may register with a group under ‘MIPS Assembly Programming Groups’ (accessible via ‘People’) on Canvas.
You must submit your solution as a single sprintf.asm file to Canvas.
You will submit your completed versions of sprintf.asm. Your submission will be assembled with the test driver using the command shown above. Again, we have supplied the testing/grading harness so that you can be sure your solution is complete and correct before you submit it, and we expect you to make use of that harness. We will make no allowances for special treatment if you fail to do this.
Pledge
Each of your program submissions must be pledged to conform to the Honor Code requirements for this course. Specifically, you must include the following pledge statement in the submitted file:
## On my honor:
##
## - I have not discussed the C language code in my program with ## anyone other than my instructor or the teaching assistants ## assigned to this course.
##
## - I have not used C language code obtained from another student, ## the Internet, or any other unauthorized source, either modified ## or unmodified.
##
## - If any C language code or documentation used in my program
## was obtained from an authorized source, such as a text book or ## course notes, that has been clearly noted with a proper citation ## in the comments of my program.
##
## - I have not designed this program in such a way as to defeat or ## interfere with the normal operation of the grading code.
##
##
##