CS 2506 Computer Organization II ASM01: MIPS Programming
Replicating a Function in C Implementing sprint() 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.
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:
* Returns: $v0 contains the length of the string written into dest, not including null * terminator
*/
$a0 contains the address of the formatted dest, including null terminator
Version 1.00 This is a purely individual assignment! 1
CS 2506 Computer Organization II ASM01: MIPS Programming
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.)
Version 1.00 This is a purely individual assignment! 2
CS 2506 Computer Organization II ASM01: MIPS Programming
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. Otherwise, if your current Procedure A calls a second Procedure B, there will be no way to return back to the correct location from Procedure A.
• Always back up registers $s0-s7 when starting a procedure if you write to them within the procedure. There is no need to add $s4 to the stack if your procedure doesn’t write to $s4. But if your procedure does write to $s4, then it is the responsibility of your 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 absolutely 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 withintheprocedure). Note,however,that$v0and$v1areintendedforusewhenreturningavaluefroma 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. The procedure itself has no responsibility to restore the values in these registers after it finishes executing.
BelowisanexampleofaprocedureMAINwhichcallsaprocedureCOMPUTATION. TheCOMPUTATIONprocedurewrites into$s0,$s3,and$a0asitprocessesdata. Theprogrammerwishestomaintainthevaluesof$t0-$t4inMAINwhen calling COMPUTATION, keeping that data available to use after returning from the procedure. In this case, the MIPS code should be structured as follows:
# MAIN code here:
# …
subi $sp, $sp, 20
sw $t0, 0($sp)
sw $t1, 4($sp)
sw $t2, 8($sp)
sw $t3, 12($sp)
sw $t4, 16($sp)
jal COMPUTATION
lw $t0, 0($sp)
lw $t1, 4($sp)
lw $t2, 8($sp)
lw $t3, 12($sp)
lw $t4, 16($sp)
addi $sp, $sp, 20
# …
# COMPUTATION code here:
subi $sp, $sp, 16
sw $ra, 0($sp)
sw $s0, 4($sp)
sw $s3, 8($sp)
sw $a0, 12($sp)
# … COMPUTATION BODY
lw $ra, 0($sp)
lw $s0, 4($sp)
lw $s3, 8($sp)
lw $a0, 12($sp)
addi $sp, $sp, 16
jr $ra
In this assignment, we will require you to follow these rules for stack manipulation. 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.
Version 1.00 This is a purely individual assignment! 3
CS 2506 Computer Organization II ASM01: MIPS Programming
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 my own solution, I even went beyond that, leaving myself 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 my PROC_SPRINTF solution I jump over the section that handles inserting a string variable into the final string, with my branch targeting the integer variable section. Even though there’s no need for a label on the string variable section, I 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.
Version 1.00 This is a purely individual assignment! 4
CS 2506 Computer Organization II ASM01: MIPS Programming
Division Details
Division in MIPS is a somewhat unique operation, which makes use of the hi and lo registers that are not directly accessible. Saythatyouruntheunsigneddivisioninstructiondivu$t6,$t1. Thisactioncomputes$t6/$t1as expected,buttheresultisstoredasanintegerintheloregister. Simultaneously,theremainder$t6%$t1iscomputedand storedinthehiregister. Inordertoaccesstheseresults,youmustusethemfloandmfhiinstructionstoretrievethe 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.tarfrom the course website and unpack it. You should receive the following files:
main.asm
tests.asm
sprint.asm
driver code for testing your procedures (don’t edit this file)
the collection of tests that are executed on your code (don’t edit this file)
code file that contains helper procedures and scaffolding for you to implement your solutions
One important note is that this is a 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 PROC_CONVERT_INT_TO_STRING PROC_SPRINTF
Manual grading of appropriate stack manipulation
100pts 100pts 200pts 100pts
This assignment is worth 6% of your final grade in the course.
What to Submit
You will submit your solution as a single .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.
Version 1.00 This is a purely individual assignment! 5
CS 2506 Computer Organization II ASM01: MIPS Programming
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.
We reserve the option of assigning a score of zero to any submission that is undocumented or does not contain this statement.
Version 1.00 This is a purely individual assignment! 6
CS 2506 Computer Organization II ASM01: MIPS Programming
Change Log Relative to Version 1.00
Version Posted 1.00 Feb 20
Pg Change
Base document.
Version 1.00
This is a purely individual assignment! 7