CSE 410 Computer Systems - Homework 2 - Spring 2010

CSE Home

About Us

Search

Contact Info

Due: Thursday, April 15, at 11 pm. (An hour before income taxes are due!)

This assignment will give you some practice with MIPS programming.

Part I. Written Warmup Questions

1. Write a sequence of MIPS instructions corresponding to each of the following C/Java statements. You should assume that the variables are stored in registers as follows: x is in $t3, y is in $s2, the base address of the array d is in $a1, and i is in $a0. You may use any other registers you wish in your code for calculated values. All variables and array elements are 4-byte integers.
   1. x = x+y;
   2. d[3] = d[i]-y;
   
   
2. Here is a snippet of MIPS assembly code:

     start: beq   $s1, $s2, exit
            add   $t0, $s2, $s2
            add   $t0, $t0, $t0
            add   $t0, $t0, $s0
            lw    $t1, 0($t0)
            add   $t1, $t1, $t1
            sw    $t1, 0($t0)
            addi  $s2, $s2, 1
            j     start
     exit:
     

   We'd like to trace this code to discover what it does. Here is a table showing initial values of some of the registers right before starting execution, with room for updated values as the code runs. (Initial values for $t0 and $t1 are not shown because they are only used as temporary variables and their initial values do not matter.)
   
   

   Register	Initial contents	First time at "j start"	Second time at "j start"	etc. ...
   $s0	400
   $s1	5
   $s2	0
   $t0	N/A
   $t1	N/A

   
   
   Here is a second table showing the contents of part of memory right before execution begins.
   
   

   Address	Initial contents	First time at "j start"	Second time at "j start"	etc. ...
   400	11
   404	23
   408	63
   412	128
   416	911

   
   Trace through the MIPS code above. Each time you reach the "j start" line, write down the contents of addresses 400-416 and registers $s0, $s1, $s2, $t0 and $t1 by filling in the tables above (you might need to add more columns to the tables). In one sentence describe what this program does.
   
   

Part II. String Processing in MIPS

In this part of the assignment, write and test two assembly language functions to perform two common string operations: compare two strings, and convert a string of digit characters into the corresponding 32-bit binary integer value. Similar functions are found in the standard library for almost every programming language; the particular specifications here are taken from the C library functions strcmp and atoi. (But don't worry if you have never seen C before - it makes no difference.)

String Representation

The most common representation of a character string in MIPS programs, as in C, is a sequence of ASCII characters stored in successive bytes in memory. The end of the string is indicated by a byte containing all 0 bits (0x00). The length of a string is not stored explicitly; if we need to know the length we can count the number of bytes preceding the 0x00 byte that marks its end. (Hint: you probably don't need to compute string lengths for these particular problems.)

For example, The string "Hello!" would be stored in memory in 7 consecutive bytes. In hexadecimal, it would be written as 0x48656c6c6f00. This is the representation used when a string constant is included in the data part of a SPIM program using the .asciiz assembler directive.

To get started, download the file template.s. This MIPS program contains a main function that prints some messages, calls a skeleton atoi function (that doesn't work yet), and prints its result. Don't feel that you have to use anything that's in here literally, but we suggest you run this program in SPIM and see how it works before you work on your own code. You should create two separate assembly files atoi.s and strcmp.s for your solutions to these programming problems. You can start by making copies of the template.s file.

Hint: There is a discussion of string functions and an example of a string copy function in sec. 2.9 of the textbook. You may find that to be a useful source of ideas, but don't feel that you have to use the code you find there or write your code the same way if it doesn't fit your solution.

For this assignment, you must follow the normal MIPS function calling and register usage conventions described in class and in the book. However it may not be necessary for your functions to allocate stack frames and save registers since they don't call other functions and there may be enough registers available for your code to use without having to save and restore anything.

You should include appropriate tests in your main programs to check that your functions work as specified. Be thorough, but don't include lots of redundant tests that basically check the same thing. Part of your grade will be based on the quality and comprehensiveness of your test cases.

Include reasonable comments in your code, and keep things simple. A correct, understandable program is preferable to a complex, tricky one. A program that works correctly is far more worthwhile than one that's broken.

strcmp

The function strcmp(s,t) compares two strings s and t to see which is "less" than the other. Function strcmp returns an integer result that is negative if s < t, zero if s == t, and positive if s > t. If the strings are not equal the particular integer value returned is not specified. It may be anything that is convenient for the implementation as long as it is positive or negative as appropriate.

Strings are compared character-by-character using their ASCII codes to decide their ordering. The ordering is roughly alphabetical. For example,

"a" < "b"
"abc" < "abcd"
"A" < "a"

Hint: Recall that if a MIPS function has two arguments, they are supplied in registers $a0 and $a1. In the case of strings, the argument registers would contain the addresses of the strings in main memory.

atoi

The function atoi(s) processes its string argument s and returns the corresponding 32-bit two's complement binary integer as its result. For this problem, you may assume that the string s consists only of decimal digit characters in the range '0' to '9'. The digit characters may be preceded by an optional '+' or '-' character giving the sign of the decimal integer constant. You may also assume that the resulting value can be stored as a 32-bit two's complement integer without overflowing. Your code does not need to check for overflow or illegal characters in the input.

Turn-In Instructions

Use the turn-in drop box link on the main course web page to submit your assignment. This should include a text file with the answers to the written questions, and the two separate files atoi.s and strcmp.s containing your solutions to the programming problems. Please be sure to include your name at the top of each of the files you turn in.

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to Hal Perkins]