Due July 15th at 11:59PM.
"TA" in charge: Scott
Submit your solution by creating a directory named hw4 that contains files named hw4q1.s, hw4q2.s, hw4q3.s, hw4q4.s, hw4q5.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 hw4. This is not a partnership assignment; hand in your own work.
Copy the contents of ~cs61c/hw/04 to a suitable location in your home directory.
$ cp -r ~cs61c/hw/04/ ~/hw4 |
All the files referred in this homework will be in the folder you copied.
P&H Exercise 2.14. Reproduced here for ease of reference:
The MIPS translation of the C segment:
while (save[i] == k) i = i + 1; |
on page 74 uses both a conditional branch and an unconditional jump each time through the loop. Only poor compilers would produce code with this loop over-head. Rewrite the assembly code so that it uses at most one branch or jump each time through the loop. How many instructions are executed before and after the optimization if the number of iterations of the loop is 10.
Save your answer to a file named hw4q1.s.
P&H Exercise 2.15. (Page 149)
Save your answer to a file named hw4q2.s.
Problem reproduced here for ease of reference.
Implement the following C code in MIPS, assuming that set_array is the first function called:
int i; void set_array(int num){ int array[10]; for (i=0; i<10; i++){ array[i] = compare(num, i); } } int compare(int a, int b){ if (sub(a, b) >= 0) return 1; else return 0; } int sub (int a, int b) { return a-b; } |
Be sure to handle the stack pointer appropriately. The Array declared in set_array is allocated on the stack, and i corresponds to $s0. Draw the status of the stack before calling set_array and during each function call. Indicate the names of registers and variables stored on the stack and mark the location of $sp.
NOTE: I removed all references to $fp that are seen in the book for this problem. Since we did not cover the $fp register in lecture, using $fp is optional for this problem
P&H Exercise 2.16. Reproduced here for ease of reference:
Write a MIPS procedure to compute the nth Fibonacci number F(n) where:
F(n) = 0, if n = 0; 1, if n = 1; F(n-1) + F(n-2), otherwise; |
Base your algorithm on the recursive algorithm below (do not compile to an iterative solution):
int fib(int n){ if (n == 0) return 0; else if (n == 1) return 1; else return fib(n-1) + fib(n-2); } |
Save your answer to a file named hw4q3.s.
Write the following VectorSum function as a MIPS procedure call:
struct vector { int x; int y; }; void VectorSum(struct vector* vp, struct vector** vectors, int len) { ... } |
The function VectorSum takes an array of pointers to struct vector and calculates the sum of all vectors. The sum of two vectors (x1,y1) and (x2,y2) is simply (x1+x2, y1+y2). The resulting vector should be stored in the struct vector pointed to by vp.
You can assume the integer x is stored at lower memory address than y. Therefore, if the address of a struct vector is at 0x50000, than the member x is located at 0x50000, and the member y is located at 0x50004.
Save your answer to a file named hw4q5.s.