EECS 61C, Spring 2007
Due Wednesday, Feb 14, 2007 @ 11:59:59pm
This assignment will give you practice of C and MIPS. By the end of the homework assignment, you should be able to translate C to MIPS code and back with ease and feel comfortable if not already with C structures and memory management.
Submit your solution by creating a directory named hw3 that contains files named cod.txt, bitcount.c, htoi.c, hash.c, p7.s. (Note that capitalization matters in file names; the submission program will not accept your submission if your file names differ at all from those specified.) From within that directory, type "submit hw3". This is not a partnership assignment; hand in your own work.
Copy the contents of ~cs61c/hw/03 to a suitable location in your home directory.
$ cp -r ~cs61c/hw/03/ ~/hw3 |
All the files referred in this homework will be in the folder you copied.
Complete Exercise 2-3 on page 46 of K&R. Write a function htoi(s), which converts a string of hexadecimal digits (including an optional 0x or 0X) into its equivalent base 10 unsigned integer value. The allowable digits are 0 through 9, a through f, and A through F.
You may assume that all input is correct (i.e. either 0x or 0X is present or not, followed by 8 hex digits) and may wish to familiarize yourself with bit operations/bit masking for this problem to help you in future MIPS assignments. You may NOT use library functions that do this for you; strtol and strtoul come to mind.
The relevant readings are available here if you don't have the book: Chapter 2.7 and Chapter 2.9
Rewrite the bitcount function on page 50 of K&R such that it doesn't use any conditional statements (meaning no if, switch, ?: expression statements).
/* bitcount: count 1 bits in x */ int bitcount(unsigned x) { int b; for (b = 0; x != 0; x >>= 1) { if (x & 01) { b++; } } return b; } |
Complete Exercise 6-5 on page 145 of K&R. All the code from section 6.6 is provided in hash.c already, with some quick test code around it. Just fill in the blank for the undef function definition -- remember to free the appropriate malloc'd space used and to correctly deal with deleting a node from a linked list (i.e. the next pointers). The return values are there for you to use (return values of 0 and 1 are straightforward and -1 if you feel like you need it).
The relevant reading is available here if you don't have the book: Chapter 6.6
Some test input you may try with hash.c:
Compile the program and run using the following command:
$ gcc -g hash.c && ./a.out |
P&H 2.29 (2.3, 2.6, 2.9) and write the C equivalent:
Add comments to the code and describe in one sentence what this code does. Assume that$a0and
$a1are used for input and both initially contain the integers a and b, respectively. Assume that
$v0is used for the output.
Also, convert this MIPS code to C (you may find it easier to understand if you do this first!).
add | $t0, $zero, $zero | |
loop: | beq | $a1, $zero, finish |
add | $t0, $t0, $a0 | |
sub | $a1, $a1, 1 | |
j | loop | |
finish: | addi | $t0, $t0, 100 |
add | $v0, $t0, $zero |
P&H 2.30 (2.3, 2.6, 2.9) and write the C equivalent:
The following code fragment processes two arrays and produces an important value in register$v0. Assume that each array consists of 2500 words indexed 0 through 2499, that the base addresses of the arrays are stored in
$a0and
$a1respectively, and their sizes (2500) are stored in
$a2and
$a3, respectively. Add comments to the code and describe in one sentence what this code does. Specifically, what will be returned in
$v0?
Also, convert this MIPS code to C (you may find it easier to understand if you do this first!).
sll | $a2, $a2, 2 | |
sll | $a3, $a3, 2 | |
add | $v0, $zero, $zero | |
add | $t0, $zero, $zero | |
outer: | add | $t4, $a0, $t0 |
lw | $t4, 0($t4) | |
add | $t1, $zero, $zero | |
inner: | add | $t3, $a1, $t1 |
lw | $t3, 0($t3) | |
bne | $t3, $t4, skip | |
addi | $v0, $v0, 1 | |
skip: | addi | $t1, $t1, 4 |
bne | $t1, $a3, inner | |
addi | $t0, $t0, 4 | |
bne | $t0, $a2, outer |
P&H 2.32, 2.33 (2.9):
Show the single MIPS instruction or minimal sequence of instructions for the following C statements:
b = 25 | a;
x[4] = x[5] + a;
acorresponds to register
$t0and
bcorresponds to register
$t1.
acorresponds to register
$t3and the array
xhas a base address of 6,400,000ten.
P&H 2.34 (2.3, 2.6, 2.9):
The following program tries to copy words from the address in register$a0to the address in register
$a1, counting the number of words copied in register
$v0. The program stops copying when it finds a word equal to 0. You do not have to preserve the contents of registers
$v1, $a0, $a1. This terminating word should be copied, not counted.
addi | $v0, $zero, 0 | # Initialize count | |
loop: | lw | $v1, 0($a0) | # Read next word from source |
sw | $v1, 0($a1) | # Write to destination | |
addi | $a0, $a0, 4 | # Advance pointer to next source | |
addi | $a1, $a1, 4 | # Advance pointer to next destination | |
beq | $v1, $zero, loop | # Loop if word copied != zero |
There are multiple bugs in this MIPS program; fix them and turn in a bug-free version.
Hint: You may find SPIM to be useful...