Homework 6 Subroutines and Calling Conventions

CS 2110 Homework 6
Subroutines and Calling Conventions

Contents
1 Overview 3
1.1 Purpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Task . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Detailed Instructions 4
2.1 Part 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.1 Collatz Conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.2 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Part 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.1 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.2 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Part 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3.1 Linked List Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3.2 Linked List Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3.3 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Autograder 7
4 Deliverables 7
5 Appendix 8
5.1 Appendix A: LC-3 Instruction Set Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6 Debugging LC-3 Assembly 9
6.1 Appendix C: LC-3 Assembly Programming Requirements and Tips . . . . . . . . . . . . . . . 12
7 Appendix D: Rules and Regulations 13
7.1 General Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1
7.2 Submission Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.3 Submission Guidelines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.4 Syllabus Excerpt on Academic Misconduct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.5 Is collaboration allowed? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2
1 Overview
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. collatz.asm
2. sort.asm
3. llsum.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!
3
2 Detailed Instructions
2.1 Part 1
2.1.1 Collatz Conjecture
The Collatz conjecture states that the hailstone sequence, defined below, for any positive integer n will
eventually reach 1.
f(n) = (
n
2
n ≡ 0 (mod 2)
3n + 1 n ≡ 1 (mod 2)
For example, n = 5 results in the sequence 5 → 16 → 8 → 4 → 2 → 1, taking a total of 5 steps. Another
example, n = 3, takes 7 steps with the sequence 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1.
For this part of the assignment, you will be recursively computing the number of steps a number in the
hailstone sequence takes to reach 1. The collatz subroutine takes in a single parameter that is the starting
number of the hailstone sequence and returns the total number of steps it takes for the sequence to reach 1.
A divide by 2 subroutine is also provided to help calculate n/2 when n is even.
If you would like additional reading on the hailstone sequence and Collatz conjecture, see https://plus.
maths.org/content/mathematical-mysteries-hailstone-sequences.
2.1.2 Pseudocode
The pseudocode is as follows:
collatz(int n, function div2) {
if (n == 1) {
return 0;
}
if (n % 2 == 0) {
return collatz(n/2) + 1;
} else {
return collatz(3 * n + 1) + 1;
}
}
4
2.2 Part 2
2.2.1 Selection Sort
For this part of this assignment, you will be implementing selection sort on an array of integers. The
parameters for the sort subroutine are the memory address of the first element in the array, an integer value
representing the number of elements in the array, and the memory address of the subroutine used to compare
elements. Following execution of this subroutine, the specified array will be sorted according to the provided
comparison function.
To compare two elements a and b with the comparison function, pass a and b as arguments to the subroutine.
compare(a, b) returns a positive number if the value of a is considered to be greater than the value of b.
That is, a should appear after b in the sorted array.
If you are unfamiliar with selection sort and would like more information about it, see https://www.
geeksforgeeks.org/selection-sort/.
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) {
i = 0;
while (i < len - 1) {
j = i;
k = i + 1;
while (k < len) {
// update j if ARRAY[j] > ARRAY[k]
if (compare(ARRAY[j], ARRAY[k]) > 0) {
j = k;
}
k++;
}
temp = ARRAY[i];
ARRAY[i] = ARRAY[j];
ARRAY[j] = temp;
i++;
}
}
5
2.3 Part 3
2.3.1 Linked List Sum
For this part of the assignment, you will write a recursive subroutine to calculate the sum of all the nodes
in a linked list. The parameter of the function is a node representing the head node of the linked list and
the return value is the sum of all the data in the list.
2.3.2 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.
x4000
Head Node
Address of
next node
x4008
Memory
x4000
Address of
next node
5
Memory
x4001
Data
x0000
Memory
x4008
Address
of next
node (null)
8
Memory
x4009
Data
See https://www.geeksforgeeks.org/data-structures/linked-list/#singlyLinkedList for more information regarding linked lists.
2.3.3 Pseudocode
Here is the pseudocode for this subroutine:
llsum(Node head) {
// note that a NULL address is the same thing as the value 0
if (head == NULL) {
return 0;
}
Node next = head.next;
sum = head.data + llsum(next);
return sum;
}
6
3 Autograder
To run the autograder locally, follow the steps below depending upon your operating system:
• 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.
4 Deliverables
Turn in the following files to Gradescope:
1. collatz.asm
2. sort.asm
3. llsum.asm
Note: Please do not wait until the last minute to run/test your homework. Last minute
turn-ins will result in long queue times for grading on Gradescope. You have been warned.
7
5 Appendix
5.1 Appendix A: LC-3 Instruction Set Architecture
8
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.
9
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
10
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.
11
6.1 Appendix C: LC-3 Assembly Programming Requirements and Tips
1. Your code must assemble with NO WARNINGS OR ERRORS. To assemble your program, open
the file with Complx. It will complain if there are any issues. If your code does not assemble you
WILL get a zero for that file.
2. Comment your code! This is especially important in assembly, because it’s much harder to interpret
what is happening later, and you’ll be glad you left yourself notes on what certain instructions are
contributing to the code. Comment things like what registers are being used for and what less intuitive
lines of code are actually doing. To comment code in LC-3 assembly just type a semicolon (;), and the
rest of that line will be a comment.
3. Avoid stating the obvious in your comments, it doesn’t help in understanding what the code is doing.
Good Comment
ADD R3, R3, -1 ; counter--
BRp LOOP ; if counter == 0 don’t loop again
Bad Comment
ADD R3, R3, -1 ; Decrement R3
BRp LOOP ; Branch to LOOP if positive
4. DO NOT assume that ANYTHING in the LC-3 is already zero. Treat the machine as if your
program was loaded into a machine with random values stored in the memory and register file.
5. Following from 3. You can randomize the memory and load your program by doing File - Randomize
and Load.
6. Use the LC-3 calling convention. This means that all local variables, frame pointer, etc. . . must be
pushed onto the stack. Our autograder will be checking for correct stack setup.
7. Start the stack at xF000. The stack pointer always points to the last used stack location.
This means you will allocate space first, then store onto the stack pointer.
8. Do NOT execute any data as if it were an instruction (meaning you should put .fills after HALT or
RET).
9. Do not add any comments beginning with @plugin or change any comments of this kind.
10. Test your assembly. Don’t just assume it works and turn it in.
12
7 Appendix D: Rules and Regulations
7.1 General Rules
1. Although you may ask TAs for clarification, you are ultimately responsible for what you submit. As
such, please start assignments early, and ask for help early. This means that (in the case of demos)
you should come prepared to explain to the TA how any piece of code you submitted works, even if
you copied it from the book or read about it on the internet.
2. If you find any problems with the assignment it would be greatly appreciated if you reported them to
the author (which can be found at the top of the assignment). Announcements will be posted if the
assignment changes.
7.2 Submission Conventions
1. Do not submit links to files. The autograder does not understand it, and we will not manually grade
assignments submitted this way as it is easy to change the files after the submission period ends. You
must submit all files listed in the Deliverables section individually to Gradescope as separate files.
7.3 Submission Guidelines
1. You are responsible for turning in assignments on time. This includes allowing for unforeseen circumstances. If you have an emergency let us know IN ADVANCE of the due time supplying documentation (i.e. note from the dean, doctor’s note, etc). Extensions will only be granted to those who contact
us in advance of the deadline and no extensions will be made after the due date.
2. You are also responsible for ensuring that what you turned in is what you meant to turn in. After
submitting you should be sure to download your submission into a brand new folder and test if it
works. No excuses if you submit the wrong files, what you turn in is what we grade. In addition, your
assignment must be turned in via Canvas/Gradescope. Under no circumstances whatsoever we will
accept any email submission of an assignment. Note: if you were granted an extension you will still
turn in the assignment over Canvas/Gradescope.

7.5 Is collaboration allowed?
Collaboration is allowed on a high level, meaning that you may discuss design points and concepts relevant
to the homework with your peers, share algorithms and pseudo-code, as well as help each other debug code.
What you shouldn’t be doing, however, is pair programming where you collaborate with each other on a
single instance of the code. Furthermore, sending an electronic copy of your homework to another student
for them to look at and figure out what is wrong with their code is not an acceptable way to help them,
because it is frequently the case that the recipient will simply modify the code and submit it as their own.
14