CS61C Spring 2008 -- HW 3

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.

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) {
			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:

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

, 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

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

corresponds to register

$t0

and

corresponds to register

$t1

.
Assume that

corresponds to register

$t3

and the array

has a base address of 6,400,000_ten.

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