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

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

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) { b++; } } 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:

• 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

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

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

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

Lets try another MIPS->C question. In this problem,
`\$a0`
is an integer argument while
`\$a1`
is a pointer to (ie: the address of) a large array. The value in
`\$a0`
can be any integer and the size of the array that
`\$a1`
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 j loop done sb \$zero 1(\$t2) jr \$ra