University of California at Berkeley
College of Engineering
Department of Electrical Engineering and Computer Science
CS61C, Summer 2008
[TA] Bill Kramer
Due Wednesday, July 16, 2008 @ 11:59:59pm
July 15, 2008 @ 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.
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.
Copy the contents of ~cs61c/hw/03 to a suitable location in your home
directory.
$ cp -r ~cs61c/hw/03/ ~/hw3 |
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.
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; } |
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 |
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 |
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
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.
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 |