University of California at Berkeley
College of Engineering
Department of Electrical Engineering and Computer Science

EECS 61C, Spring 2007

HW 3

Due Wednesday, Feb 14, 2007 @ 11:59:59pm

Updates

Goals

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.

Background reading

Submitting Your Solution

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.

Problem 0

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.

Problem 1 (htoi.c)

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

Problem 2 (bitcount.c)

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;
}

Problem 3 (hash.c)

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

Problem 4 (cod.txt)

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
$a0
and
$a1
are used for input and both initially contain the integers a and b, respectively. Assume that
$v0
is 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
jloop
finish:addi$t0, $t0, 100
add$v0, $t0, $zero

Problem 5 (cod.txt)

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
$a0
and
$a1
respectively, and their sizes (2500) are stored in
$a2
and
$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

Problem 6 (cod.txt)

P&H 2.32, 2.33 (2.9):

Show the single MIPS instruction or minimal sequence of instructions for the following C statements:

Assume that
a
corresponds to register
$t0
and
b
corresponds to register
$t1
.
Assume that
a
corresponds to register
$t3
and the array
x
has a base address of 6,400,000ten.

Problem 7 (p7.s)

P&H 2.34 (2.3, 2.6, 2.9):

The following program tries to copy words from the address in register
$a0
to 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...