Homework 7 Recursive Assembly

CS 2110 Homework 7
Recursive Assembly

Contents
1 Overview 2
2 Instructions 2
2.1 Part 1: String Operations (20 points) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.1.1 String Length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.1.2 Count Character . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Part 2: Handshaking (30 points) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Part 3: Build Heap (50 points) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3.1 Heapify (35 points) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3.2 Build Heap (15 points) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Deliverables 4
4 LC-3 Assembly Programming Requirements 5
4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.2 LC-3 Calling Convention Guide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
5 Rules and Regulations 10
5.1 General Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.2 Submission Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.3 Submission Guidelines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1 Overview
In this assignment, you will be implementing several subroutines in assembly, taking advantage of the calling
convention that has been outlined in class/lecitation. For each subroutine, you will be required to
implement the entire calling convention. This includes the buildup and teardown on the stack.
2 Instructions
You have been provided three assembly files, string ops.asm, handshake.asm, and buildheap.asm.
These files contain a label for each of the subroutines that you will be asked to implement. DO NOT
RENAME THE LABELS! You can add more to suit your needs, but don’t change the existing ones.
Implement the following subroutines, use complx to debug them, and submit your files on Gradescope.
It is in your best interest to do the problems in order. The last one builds on the first two.
2.1 Part 1: String Operations (20 points)
The first part of this assignment is to implement a method to count the occurrences of a character in a
string. This will utilize the strlen subroutine, which has been implemented for you.
2.1.1 String Length
To help you get started on the homework, we have provided you with the implementation of strlen. It
includes the buildup of the stack, body of the function, and teardown of the stack. The pseudocode is
provided here for your reference, but you do not have to implement this yourself. You will, however,
have to call it from the next subroutine, so make sure you are familiar with how it works.
Pseudocode
int strlen(String s) {
int count = 0;
while (s.charAt(count) != "\0") {
count++;
}
}
2.1.2 Count Character
Complete the count occurrence function in the string ops.asm file. This function should count how
many times a given character appears in a string. This method should call the strlen method that you
implemented in the previous part.
Pseudocode
int count_occurrence(String s, char c) {
int count = 0;
for (int i = 0; i < strlen(s); i++) {
if (s.charAt(i) == c) {
count++;
}
2
}
return count;
}
2.2 Part 2: Handshaking (30 points)
The second part of this assignment is solving the handshake problem.
Background
With n people at a party, find the maximum number of handshakes possible given that any two people can
only shake each other’s hand once. This problem can be easily solved using recursion and the pseudocode
for this problem is in the next section!
Pseudocode
int handshake(int n) {
if (n == 0)
return 0;
else
return (n - 1) + handshake(n - 1);
}
2.3 Part 3: Build Heap (50 points)
Background
If you have taken CS 1332 (don’t worry if you haven’t), then you might be familiar with the data structure
known as the binary heap. A binary heap (specifically a max heap) is essentially a binary tree with the
property that for every node, its children are less than or equal to it. This means that the root node of the
heap is the largest element. The cool thing about binary heaps is that they can be represented as arrays,
where a node at index n has its left child at index 2n + 1 and its right child at index 2n + 2. The goal of the
next two problems will be to implement a function that will order an array of elements so that they form a
valid heap. While it may help you to know more about binary heaps in order to understand what is going on
(you can ready about them at https://www.geeksforgeeks.org/binary-heap/), you don’t actually have
to know anything about them since we give you the pseudocode.
2.3.1 Heapify (35 points)
The first subroutine that we will have you implement is heapify. Heapify takes in an array, its length, and a
given node i and then ensures that the heap property of a node being larger than its children is maintained
for that node. If you have to swap two elements, then heapify recursively re-checks the heap property for
child nodes. Once we have implemented, we will be able to call it for every node to actually convert a given
array into a heap.
Your job is to implement heapify in the buildheap.asm file, starting at the heapify label.
Heapify Pseudocode
void heapify(int[] arr, int n, int i) {
// The following are all indices, not values
3
int largest = i; // Initialize largest as root
int leftChild = 2*i + 1; // left = 2*i + 1
int rightChild = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (leftChild < n && arr[leftChild] arr[largest])
largest = leftChild;
// If right child is larger than largest so far
if (rightChild < n && arr[rightChild] arr[largest])
largest = rightChild;
// If largest is not root
if (largest != i)
{
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
2.3.2 Build Heap (15 points)
Once you’ve implemented heapify, buildheap is easy. All you have to do is start at the end of the array and
iterate backwards over each element, calling heapify on each one.
In buildheap.asm, implement the following pseudocode, starting at the buildheap label.
Build Heap Pseudocode
void buildheap(int arr[], int n) {
for (int i = n; i = 0; i--)
heapify(arr, n, i);
}
3 Deliverables
Please upload the following files onto the assignment on Gradescope:
1. string ops.asm
2. handshake.asm
3. buildheap.asm
Be sure to check your score to see if you submitted the right files, as well as your email
frequently until the due date of the assignment for any potential updates.
4
4 LC-3 Assembly Programming Requirements
4.1 Overview
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.
4.2 LC-3 Calling Convention Guide
A handy assembly guide written by Kyle Murray (RIP) follows on the next page:
5




5 Rules and Regulations
5.1 General Rules
1. Starting with the assembly homeworks, any code you write must be meaningfully commented. You
should comment your code in terms of the algorithm you are implementing; we all know what each
line of code does.
2. Although you may ask TAs for clarification, you are ultimately responsible for what you submit. 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.
3. Please read the assignment in its entirety before asking questions.
4. Please start assignments early, and ask for help early. Do not email us the night the assignment is due
with questions.
5. 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.
5.2 Submission Conventions
1. All files you submit for assignments in this course should have your name at the top of the file as
a comment for any source code file, and somewhere in the file, near the top, for other files unless
otherwise noted.
2. When preparing your submission you may either submit the files individually to Canvas/Gradescope
or you may submit an archive (zip or tar.gz only please) of the files. You can create an archive by right
clicking on files and selecting the appropriate compress option on your system. Both ways (uploading
raw files or an archive) are exactly equivalent, so choose whichever is most convenient for you.
3. Do not submit compiled files, that is .class files for Java code and .o files for C code. Only submit the
files we ask for in the assignment.
4. 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.
5.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.
3. There is a 6-hour grace period added to all assignments. You may submit your assignment without
penalty up until 11:55PM, or with 25% penalty up until 5:55AM. So what you should take from this is
not to start assignments on the last day and plan to submit right at 11:54AM. You alone are responsible
for submitting your homework before the grace period begins or ends; neither Canvas/Gradescope, nor
10
your flaky internet are to blame if you are unable to submit because you banked on your computer
working up until 11:54PM. The penalty for submitting during the grace period (25%) or after (no
credit) is non-negotiable.