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

CS61C, Spring 2008

Put away the Wii, it's HW 3!

[TA] Ben Sussman - And other, more ancient ones

Due Wednesday, Feb 20, 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. There are first some plain C questions to keep you on your toes (C is hard!) and teach you in a simpler setting the joys and hardships that are logical bit manipulation.

Submitting your Solutions

Submit your solution by creating a directory named hw3 that contains files named hw3.txt, bitcount.c, htoi.c and hash.c. (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

Problem 1

Complete Exercise 2-3 on page 46 of K&R which is as follows:

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.

Problem 2

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) {
	return b;

Problem 3

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

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

Problem 5

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
. Assume that each array consists of 2500 words indexed 0 through 2499, that the base addresses of the arrays are stored in
respectively, and their sizes (2500) are stored in
, respectively. Add comments to the code and describe in one sentence what this code does. Specifically, what will be returned in

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

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

Assume that
corresponds to register
corresponds to register
Assume that
corresponds to register
and the array
has a base address of 6,400,000ten.

Problem 7

Lets try another MIPS->C question. In this problem,
is an integer argument while
is a pointer to (ie: the address of) a large array. The value in
can be any integer and the size of the array that
points to is big enough (as long as you don't dereference memory before $a1, you won't be accessing memory that isn't yours) for the code to work correctly.

The instructions are the same as before: add comments to the code and then briefly explain what it does. Specifically, what is in the array as the function returns?

Translate the following code into C:

addi$t1 $zero 31
addi$t0 $zero 31
loop:srlv$t3 $a0 $t1
andi$t3 $t3 1
addi$t3 $t3 48
sub$t4 $t0 $t1
add$t2 $a1 $t4
sb$t3 0($t2)
beq$t1 $zero done
subi$t1 $t1 1
donesb$zero 1($t2)