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

• 02/14/07 @ 2AM: Added some clarifications from newsgroup.
• 02/13/07 @ ~6PM: Moved the static hashtab in hash.c to before undef() and made p7.s debuggable in SPIM.

## 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.

• K&R: Chapters 1-6.
• P&H: Chapters 2.1-2.3, 2.6, 2.9 (pg 95, 96)

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:

• the sky is blue
• I hate apples!
• I procrastinated on CS61C proj1

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:

`\$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 j loop 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`
`\$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:

• `b = 25 | a;`
• `x[4] = x[5] + a;`
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`
`\$a1`
`\$v0`
`\$v1, \$a0, \$a1`