CS2110 - Homework 6 - Subroutines and Calling Conventions - Solved

1.1     Purpose
Now that you’ve been introduced to assembly, think back to some high level languages you know such as Python or Java. When writing code in Python or Java, you typically use functions or methods. Functions and methods are called subroutines in assembly language.

In assembly language, how do we handle jumping around to different parts of memory to execute code from functions or methods? How do we remember where in memory the current function was called from (where to return to)? How do we pass arguments to the subroutine, and then pass the return value back to the caller?

The goal of this assignment is to introduce you to the Stack and the Calling Convention in LC-3 Assembly. This will be accomplished by writing your own subroutines, calling subroutines, and even creating subroutines that call themselves (recursion). By the end of this assignment, you should have a strong understanding of the LC-3 Calling Convention and the Stack Frame, and how subroutines are implemented in assembly language.

1.2     Task
You will implement each of the four subroutines (functions) listed below in LC-3 assembly language. Please see the detailed instructions for each subroutine on the following pages. We have provided pseudocode for each of the subroutines, and suggest that you follow these algorithms when writing your assembly code. Your subroutines must adhere to the LC-3 calling convention.

1.    fib.asm

2.    sort.asm

3.    reverseLL.asm

More information on the LC-3 Calling Convention can be found on Canvas in the Lab Guides and in Lecture Slides L12 and L13. More detailed information on each LC-3 instruction can be found in the Patt/Patel book Appendix A (also on Canvas under LC3 Resources). Please check the rest of this document for some advice on debugging your assembly code, as well some general tips for successfully writing assembly code.

1.3      Criteria
Your assignment will be graded based on your ability to correctly translate the given pseudocode for subroutines (functions) into LC-3 assembly code, following the LC-3 calling convention. Please use the LC-3 instruction set when writing these programs. Check the deliverables section for deadlines and other related information.

You must obtain the correct values for each function. In addition, registers R0-R5 and R7 must be restored from the perspective of the caller, so they contain the same values after the caller’s JSR subroutine call. Your subroutine must return to the correct point in the caller’s code, and the caller must find the return value on the stack where it is expected to be. If you follow the LC-3 calling convention correctly, each of these things will happen automatically.

While we will give partial credit where we can, your code must assemble with no warnings or errors. (Complx will tell you if there are any.) If your code does not assemble, we will not be able to grade that file and you will not receive any points. Each function is in a separate file, so you will not lose all points if one function does not assemble. Good luck and have fun!

2       Detailed Instructions
2.1      Part 1
2.1.1        Fibonacci Sequence
For this part of the assignment, you will be recursively computing the n-th element of the Fibonacci sequence where n is an integer passed as an argument. The Fibonacci sequence is a sequence of numbers in which each number is the sum of the two preceding ones, starting from 0 and 1. As such, the sequence goes 0, 1, 1, 2, 3, 5, and continues infinitely. If you are interested in reading more about the Fibonacci sequence and its numbers, please visit https://mathworld.wolfram.com/FibonacciNumber.html.

2.1.2       Pseudocode
Following is the pseudocode for computing the value of the n-th element of the Fibonacci sequence. The pseudocode is as follows:

fib(int n) { if (n == 0) { return 0;

} else if (n == 1) { return 1;

} else { return fib(n - 1) + fib(n - 2);

}

}


2.2      Part 2
2.2.1          Bubble Sort with Comparison
For this part of this assignment, you will be implementing bubble sort on an array of integers using a provided comparison function passed as a parameter onto the stack. The parameters for the sort subroutine are the memory address of the first element in the array, an integer value representing the value of the number of elements in the array, and a memory address of the subroutine used to compare the elements.

To compare two elements a and b with the comparison function, pass a and b as arguments to the subroutine. if compare(a, b) returns a positive number, then a swap should be made. Otherwise, the elements should not be swapped.

Note: unlike previous questions, you can’t use JSR to jump to the provided function. JSR takes in the PC-relative location of a subroutine as one of its operands, but some of the provided functions are located too far away for JSR to reach. What function similar to JSR can be used instead?

2.2.2       Pseudocode
The pseudocode for this function is as follows.

sort(array, len, function compare) { y = len - 1; while (y > 0) { x = 0; while (x < y) {

// if compare returns a positive number, swap if (compare(ARRAY[x], ARRAY[x+1]) > 0) { temp = ARRAY[x]; ARRAY[x] = ARRAY[x+1];

ARRAY[x+1] = temp;

} x++;

} y--;

}

}

2.3      Part 3
2.4      Reverse a Linked List
For his part of the assignment, you will write a recursive subroutine to reverse the nodes in a linked list. The parameter of the function is a node representing the head node of the linked list.

2.4.1          Linked List Data Structure
The below figure depicts how each node in our linked list is laid out. Each node will have two attributes: the next node, and a value for that node.

Memory Memory Memory Memory Head Node x4000 x4001 x4008 x4009

           x4000          x4008                                                                                                  x0000

Address of          Address of            Data        Address Data next node    next node              of next

node (null)

2.4.2       Pseudocode
Here is the pseudocode for this subroutine:

reverseLL(Node head) {

// note that a NULL address is the same thing as the value 0 if (head == NULL) { return NULL;

} if (head.next == NULL) { return head;

}

Node tail = head.next; Node newHead = reverseLL(tail); tail.next = head; head.next = NULL; return newHead;

}


•   Mac/Linux Users:

1.    Navigate to the directory your homework is in (in your terminal on your host machine, not in the Docker container via your browser)

2.    Run the command sudo chmod +x grade.sh

3.    Now run ./grade.sh

•   Windows Users:

1.    In Git Bash (or Docker Quickstart Terminal for legacy Docker installations), navigate to the directory your homework is in

2.    Run chmod +x grade.sh

3.    Run ./grade.sh

Note: The checker may not reflect your final grade on this assignment. We reserve the right to update the autograder as we see fit when grading.


5       Appendix
5.1          Appendix A: LC-3 Instruction Set Architecture
 

6         Debugging LC-3 Assembly
When you turn in your files on Gradescope for the first time, you may not receive a perfect score. Does this mean you change one line and spam Gradescope until you get a 100? No! You can use a handy Complx feature called “replay strings”.

1.    First off, we can get these replay strings in two places: the local grader, or off of Gradescope. When you run the autograder, you should see an output like this:

 

Copy the string, starting with the leading ’B’ and ending with the final backslash. Do not include the quotation marks.

Side Note: If you do not have Docker installed, you can still use the tester strings to debug your assembly code. In your Gradescope error output, you will see a tester string. When copying, make sure you copy from the first letter to the final backslash and again, don’t copy the quotations.

 

2.    Secondly, navigate to the clipboard in your Docker image and paste in the string.

 

3.    Next, go to the Test Tab and click Setup Replay String

 

4.    Now, paste your tester string in the box!

 

5.    Now, Complx is set up with the test that you failed! The nicest part of Complx is the ability to step through each instruction and see how they change register values. To do so, click the step button. To change the number representation of the registers, double click inside the register box.

 

6.    If you are interested in looking how your code changes different portions of memory, click the view tab and indicate ’New View’

 

7.    Now in your new view, go to the area of memory where your data is stored by CTRL+G and insert the address

 

8.    One final tip: to automatically shrink your view down to only those parts of memory that you care about (instructions and data), you can use View Tab → Hide Addresses → Show Only Code/Data.