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

CS61C, Summer 2008

Home Work 3

[TA] Bill Kramer

Due Wednesday, July 16, 2008 @ 11:59:59pm
July 15, 2008 @ 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, and htoi.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 (htoi.c)

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 signed 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 (e.g strtol or stroul) that do this for you.

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) (Optional)

This problem is optional and will not be graded for credit. It is valuable practice though and if you have enough time to work on proj2 after, we recommend trying this.

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

Some test input you may want to try with hash.c:

Compile the program and run using the following command:

$ gcc -g hash.c && ./a.out

Problem 4

P&H Problem 2.29 (relevant readings 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 Problem 2.30 (relevant readings 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

Assume that the MIPS code is run on a machine with a 2 GHz clock that requires the following number of cycles for each instruction:

·          add, addi, sll: 1 Cycle

·          lw, bne: 2 Cycles

In the worst case, how many seconds will it take to execute this code?

Problem 6

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

1.               b = 25 | a;
2.               x[4] = x[5] + a;

 

For 1, assume that a corresponds to register $t0 and b corresponds to register $t1.

For 2 assume that a corresponds to register $t3 and the array x has a base address of 6,400,000ten.

Problem 7 (Optional)

This problem is optional and will not be graded for credit. It is valuable practice though and if you have enough time to work on proj2 after, we recommend trying this.

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