CS270 Programming Assignment 7: The Stack

Warning

This assignment has changed from the Fall 2016 version.

Goals

1. To practice the LC-3 stack protocol.
2. To apply the stack protocol to implement a recursive function.
3. To practice algorithms.

The Assignment

In this assignment, you will be implementing binary search on an integer array recursively. Please refer to the following link for an overview of this algorithm: click here. Notice that the array in this assignment is sorted in descending order.

Here is the C implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <stdio.h>

// Parameter and result
int Needle = 4;
int *Result;

// Array definition
int Count = 7;
int Haystack[] = {14, 12, 10, 8, 6, 4, 2};

// Forward declaration
int *BinarySearch(int x, int *loAddress, int *hiAddress);

// Entry point
int main() {
  Result = BinarySearch(Needle, Haystack, Haystack + (Count - 1));
  
  // Print the result (you don't need to do this in assembly)
  if (Result)
    printf("Found at address %p (contains %d)\n", Result, *Result);
  else
    printf("Element not found!\n");
}

// Binary search recursive function
// Adapted from: http://www.cs.utsa.edu/~wagner/CS3343/recursion/binsearch.html
int *BinarySearch(int x, int *loAddress, int *hiAddress) {
  int midOffset = 0;
  int *midAddress = 0;
  
  // Base case (the element was not found)
  if (loAddress > hiAddress) return 0;
  
  // Calculate the address of the element in the middle
  midOffset = (hiAddress - loAddress) / 2;
  midAddress = loAddress + midOffset;
  
  // Have we found the element?
  if (x == *midAddress) {
    // We have found it!
    return midAddress;
  } else if (x > *midAddress) {
    // We haven't found it: continue on the lower half
    return BinarySearch(x, loAddress, midAddress - 1);
  } else {
    // We haven't found it: continue on the upper half
    return BinarySearch(x, midAddress + 1, hiAddress);
  }
}

Note that the array that we perform the search on is called the Haystack, and the element we are searching for is called the Needle. The BinarySearch function is supposed to return the memory address where the element is located (or 0 if it is not in the array). Also, notice that the Count variable must contain the number of elements in the Haystack array.

Specifications

1. Make sure you understand the C implementation fully. You should become thoroughly familiar with the algorithm and the C implementation we provided before you attack the problem. Download the file from here: bsearch.c. Run the code with different parameters and arrays. Experiment with corner cases. Trace the recursion. When you feel that you have owned the code, move on. You can compile and run this program in the CS machines using the following commands:

   c11 -o bsearch bsearch.c

   ./bsearch

2. Seriously, get familiar with the C implementation first.
3. Now download the skeleton file: bsearch.asm. You will be implementing the BinarySearch function only. The Main function is given to you. Do not change it. Notice that the return value of your function is not printed (like in the C implementation). It is stored in the Result label. Your program must eventually get to the HALT instruction in the Main subroutine. At that point, your return value should be in the Result label and R5 and R6 should be restored to x4000.
4. Pay attention to the comments in the skeleton file. If the comments say not to change something, do not change it. For example, do not change the number of lines in the array definition section. Also, do not add any variables before the array definition section. If you do, the auto-grader will not be able to find the array. If you need labels for constants (I didn't), create them right above the BinarySearch label.
5. Assume that the Haystack array is already sorted in descending order. Also, assume that it will not be larger than 20 elements. Do not assume that the elements in the array are unique.
6. You should understand the Main function in the skeleton file so that you find out what is being given to you and how your return value is being used.
7. You must follow the C implementation. Do not try to improve it. For example, do not try to perform the division before your check for the base case. Use the same local variables and populate them appropriately (and at the right time) even if you think they are useless. If you deviate from the C implementation, you will probably get no credit for the assignment.
8. Your function must be implemented recursively. You must follow the stack protocol described later in this document. It is not enough to get the right answer. We will check the stack in the auto-grader (refer to the grading criteria).
9. Do not implement helper functions or subroutines. You might be tempted to define a subroutine to perform division by 2. Do not do this. My division section was only 5 lines long. You can choose between implementing it as repeated subtraction or as a right shift.
10. You have some control over how hard this assignment is. If you want it to take many days and sleepless nights, you can start coding immediately without a plan of action and without drawing anything on paper. If you want the assignment to be reasonable, use pencil and paper, design a plan of action, draw the stack, and check your thought process. If you do not remember what an instruction does, do not just put it in your program hoping that it will work. Try in a separate program until you are comfortable with it.

Stack Protocol

You must follow the following stack protocol in this assignment:

• Both R5 and R6 are initially set to x4000 (the Main subroutine does this for you).
• Step 1: the caller pushes the parameters for the callee in reverse order (from right to left).
• Step 2: the caller calls the callee using JSR.
• Step 3: the callee allocates space in the stack for the return value.
• Step 4: the callee pushes the return address (the current value of R7). This is similar to making a backup of R7 in a label, except that we are storing it in the stack instead of a label.
• Step 5: the callee pushes the previous frame pointer. Each activation record has a frame pointer that points to a fixed location within the record. This allows a function to access all the different parts of its activation record by using the frame pointer as a base address. The frame pointer is stored in R5 (by LC-3 conventions). Hence, in this step, we push the value of R5 into the stack.
• Step 6: the callee sets up its own frame pointer. It involves updating R5. The convention is to make the frame pointer point to where the first local variable is (or would be).
• Step 7: the callee allocates space for local variables. The order of the local variables in the stack is related to the order in which they are declared in the C function: in our case, the midOffset variable must have a higher address than the midAddress variable (midOffset is pushed before midAddress).
• Step 8: at this point, the activation record for the callee has been fully built. The callee can now execute its body. In this step, the function will need to update the return value at some point.
• Step 9: it is now time to start popping the activation record out of the stack. In this step the callee pops the local variables.
• Step 10: the next thing in the stack is the previous frame pointer. The callee pops it into R5 (to restore the previous frame pointer).
• Step 11: the next thing in the stack is the return address. The callee pops it into R7 (to restore the return address).
• Step 12: the callee can now return to the caller using RET.
• Step 13: the next thing in the stack is the return value. The caller can pop it into a register for its own use.
• Step 14: the only things left in the activation record are the parameters. The caller pops them out.

Do not modify R5, R6, and R7 in your function outside of what the stack protocol demands.

Testing

To help you overcome any addiction you may have to preliminary testing, we have decided to provide only one preliminary testing case: to check if your program assembles.

That said, we also decided to provide you with screenshots of what the stack should look like for some test cases (you can be sure we will not test those specific cases).

Note: the stack you get should match, except possibly for the return address of the activation records above the first one. The return address for the first activation record must match. If it does not, you did something wrong.

Test Case 1:

This is what the needle and the haystack look like:

When my program reaches the HALT instruction in the Main subroutine, my Result label and stack look like this:

And R5 = x4000, R6 = x4000, R7 = x3011.

Test Case 2:

This is what the needle and the haystack look like:

When my program reaches the HALT instruction in the Main subroutine, my Result label and stack look like this:

And R5 = x4000, R6 = x4000, R7 = x3011.

Grading Criteria

Preliminary Testing (1 point):

We will check that your program assembles.

Final Testing (99 points):

To test your program, we will take advantage of the fact that when something is popped off the stack, the value remains in memory. Hence, we will run your program up to the HALT instruction. Then, we will dump the stack and the values of the R5, R6, and R7 registers. We will check that your stack matches our solution (except possibly for the return address - the only return address that must match is the one in the first activation record). We will test your program with different values for the Needle, the Count, and the contents of the Haystack array.

There is very little room for partial credit (if any). We will not change the auto-grader to accommodate your own stack protocol or your own implementation. For example, if the order of the parameters in your stack is different from ours, you might not get any points (even if you got the right answer).

The grading criteria are deliberately vague: you will have to design your own test cases. We reserve the right to test corner cases.

If you feel that there are ambiguities in the instructions that the provided test screenshots do not resolve, let us know early.