Project 3 Assembly Solution

Description

1 Introduction

1.1 All about Assembly

This project will introduce you to everything regarding assembly from simple loops and conditionals to IO and recursive subroutines! Please read through the entire PDF for helpful debugging information and start early!

1.2 Files Provided

Inside the student directory, you will find two subdirectories – part1 and part2. Both will be due on 10/30 but we highly recommend you to finish part1 by 10/23. If you do not turn in part1 by the checkpoint date, you will not lose any points. We have simply provided this halfway point so you have plenty of time to complete the much more complicated second half by the final due date. Make sure both parts are turned in by the final due date.

2 Implementation

2.1 Part 1

2.1.1 length.asm

For this part, you should write a program to calculate the length of the string located at the memory address represented by the label STRING. Store your answer at the memory address represented by the label ANSWER.

Note: The length does not include the null terminator.

2.1.2 numbertriangle.asm

For this subroutine, you will be building a reverse triangle starting with the value ‘n’ stored at the address represented by label TRIANGLE. To create this triangle, your first line will be ‘n’ printed ‘n’ times followed by a newline character. The second line will be a space, followed by ‘n-2’ printed ‘n-2’ times, followed by a newline character. This algorithm will continue while n is greater than 0.

For example, if TRIANGLE = 5, our terminal output would be:

55555

333

1

Note: This is equivalent to 55555\n_333\n__1\n, where each ‘_’ represents a space

Note: We will only give you an initial TRIANGLE value of numbers 1 – 9.

2.1.3 comparestring.asm

For this program, you will be writing a string comparison tool similar to the compareTo() method in Java. This function should take in the addresses of two strings (i.e. the address of the first character in the string), which are stored at STR1 and STR2, respectively. (Again note that this means ‘STR1’ holds the address of the first character of string 1, not the character itself). You should take these two strings and return either -1, 0, or 1 based on the ordering of the strings alphabetically (in ASCII order) and store the result in ANSWER. That is, you should set ANSWER to:

• -1: If STR1 would come before STR2 when sorted alphabetically (e.g. STR1 = “Apple”, STR2 = “Banana”).

• 0: If STR1 == STR2 (e.g. STR1 = “twins”, STR2 = “twins”).

• 1: If STR1 would come after STR2 when sorted alphabetically (e.g. STR1 = “Southern”, STR2 = “Conte”)

Note: Casing does matter! Meaning “apple” comes after “Zebra” when ordered alphabetically.

2.1.4 linkedlist.asm

For this problem, your goal is to return the number of nodes in the linked list whose age is larger than the value at memory address NUMBER and whose first letter of their name is before LETTER in alphabetical order. You will be storing the answer in the memory address represented by the label ANSWER In order to do so, take a look at this node structure: Every node in our linked list is an object with three attributes – next node, age, and name. These three attributes are stored in memory like so:

			Address of	Age of	Name
Node
			next node	node	of node

The head (first node) of the linked list is located at the memory address represented by the label HEAD.

So, for more than one node, our data structure would look like this:

Head
Memory		Memory	Memory
x4000		x4001	x4002
x4008		5	Henry
Address of		Age of	Name of
next node		head node	head node
Memory		Memory	Memory
x4008		x4009	x400A
x0000		10	Jake
Address		Value of	Name of
of next		next node	next node
node(null)

For example, if Node A contained the data (25, “Manley”), Node B contained the data (36, “Pulkit”), Node C contained the data (5, “Jarrett”), NUMBER is 7, and LETTER is “N”; our function would return 1 (because only node A has an age larger than NUMBER and a name before LETTER in alphabetical order).

2.1.5 fibonacci.asm

For this problem, your goal is to write a subroutine that returns the nth fibonacci number.

For this subroutine and all other subroutines that follow, we will be using the calling convention taught in class and in the book (Chapter 8). You will be given one argument passed through R0, n, that will determine

which fibonacci number to return. You should return the nth fibonacci number through R1. Make sure to manage your stack properly for recursive calls!

Reminder:

• fibonacci(0) = 1

• fibonacci(1) = 1

• fibonacci(2) = 2

• fibonacci(3) = 3

• …

• fibonacci(n) = fibonacci(n – 2) + fibonacci(n – 1)

2.2 Part 2 – operationlinkedlist.asm

For Part 2, we will be using the same node structure as the linked list in Part 1. Here it is again for your convenience: Every node in our linked list is an object with three attributes – next node, age, and name. These three attributes are stored in memory like so:

			Address of	Age of	Name
Node
			next node	node	of node

The head (first node) of the linked list is located at the memory address represented by the label HEAD.

So, for more than one node, our data structure would look like this:

Head
Memory		Memory	Memory
x4000		x4001	x4002
x4008		5	Henry
Address of		Age of	Name of
next node		head node	head node
Memory		Memory	Memory
x4008		x4009	x400A
x0000		10	Jake
Address		Value of	Name of
of next		next node	next node
node(null)

2.2.1 operationlinkedlist

The main subroutine here is called operationLinkedList. This subroutine takes in two parameters, the head of a linked list and an address of a function. This subroutine is a wrapper function that will call the other functions (reverse, replaceAge) with the head of the linked list. How: As taught in class, these two

arguments will be passed through using registers. The head of the linked list will be passed to this function via R0 and the address of the function to call will be passed to this function via R1. operationLinkedList will then call the function whose address is located in R1 with the argument located in textbfR0. Below is the following pseudocode:

function operationlinkedlist (head, anotherFunction) { anotherFunction(head)

}

function anotherFunction(head) {

…

}

There are two possible other functions that we can call – reverse and replaceAge

2.2.2 reverse

This subroutine will reverse the linked list recursively. For example, a linked list looking like

Henry -> Maddie -> Jarrett

Will end up looking like this:

Jarrett -> Maddie -> Henry

The pseudocode for this algorithm is:

function reverse_ll(Node head)

{

if (head == null || head.next == null)

{

return head;

}

new_head = reverse_ll(head.next);

head.next.next = head;

head.next = null;

return new_head;

}

Note: During your recursive call, remember to pass any parameters to your function through R0 and have R1 contain the return value!

2.2.3 replaceAge

This subroutine will iterate through the linked list, square each node’s age, and replace the current age with the squared one. This means a list looking like

1->5->3

Will turn into:

1->25->9

This subroutine will iterate through each node and call another subroutine square to square the age. The pseudocode for this algorithm is:

function replaceAge(head) {

curr = head;

while (curr != null) {

newAge = square(curr.age)

curr.age = newAge

}

}

Note: During your implementation of replaceAge, remember that the parameter head will be passed through R0 and there is no return value, so R1 should not be modified.

With the pseudocode for the recursive square algorithm being:

function square(age) {

if (age == 0) {

return 0

} else {

return (square(age – 1) + (2 * age) – 1)

}

}

Note: During your implementation of square and recursive call, remember that the parameter should be passed through R0 and R1 should contain the return value!

We have also included a print_ll subroutine that will help you debug your code! To use the subroutine, load the head of the linked list into R0 load the address of the print_ll subroutine – x7000 into a register, and jump to that subroutine.

3 Debugging

When you turn in your files on Gradescope for the first time, you might 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 tool known as tester strings.

1. First off, we can get these tester strings in two places: the local grader or off of Gradescope. To run the local grader:

1. • Mac/Linux Users:

1. • 1. Navigate to the directory your project is in. In your terminal, not in your browser

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

1. • 3. Now run ./grade.sh

1. • Windows Users:

1. • 1. On docker quickstart, navigate to the directory your project is in

1. • 2. Run ./grade.sh

When you run the script, you should see an output like this:

Copy the string, starting with the leading ‘B’ and ending with the final backslace. Do not include the quotations.

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 backslace 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.

5. 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. Just be careful: if you misclick and select Show Non Zero, it may make the window freeze (it’s a known Complx bug).

You can also test a function manually

1. If the function is not a subroutine, simply hit ’RUN’ in complx

2. If the function is a subroutine:

1. 1. In Complx, go to Debug -> Simulate Subroutine Call and pick which subroutine you would like to manually test

   2. Change the value of R0 inside Complx and hit enter

1. 3. Run your code via the ’RUN’ button and check that it ran successfully by looking at your regis-ters/memory values

4 Deliverables

Turn in the files length.asm, printstring.asm, comparestring.asm, linkedlist.asm, fibonacci.asm, and opera-tionlinkedlist.asm to Gradescope by the due date.

Note: Please do not wait until the last minute to run/test your project, history has proved that last minute turn-ins will result in long queue times for grading on Gradescope. You have been warned.

5 LC-3 Assembly Programming Requirements

5.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.

4. Following from 3. You can randomize the memory and load your program by doing File – Randomize and Load.

4. 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.

4. 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.

4. Do NOT execute any data as if it were an instruction (meaning you should put .fills after HALT or RET).

4. Do not add any comments beginning with @plugin or change any comments of this kind.

4. Test your assembly. Don’t just assume it works and turn it in.

6 Rules and Regulations

6.1 General Rules

1. 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.

2. Please read the assignment in its entirety before asking questions.

3. Please start assignments early, and ask for help early. Do not email us the night the assignment is due with questions.

3. 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.

6.2 Submission Conventions

1. When preparing your submission you must submit the files individually to Gradescope.

2. 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.

6.3 Submission Guidelines

1. You are responsible for turning in assignments on time. This includes allowing for unforeseen cir-cumstances. 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. Projects turned in late receive zero credit. You alone are responsible for submitting your project before the assignment is due; neither Canvas/Gradescope, nor 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 after the assignment is due is non-negotiable.

6.4 Syllabus Excerpt on Academic Misconduct

Academic misconduct is taken very seriously in this class.

1. Students are expected to have read and agreed to the Georgia Tech Honor Code, see http://osi.gatech.edu/content/honor-code.

2. Suspected plagiarism will be reported to the Division of Student Life office. It will be prosecuted to the full extent of Institute policies.

3. A student must submit an assignment or project as his/her own work (this is what is expected of the students).

4. Using code from GitHub, via Googling, from Stack Overflow, etc., is plagiarism and is not permitted. Do not publish your assignments on public repositories (i.e., accessible to other students). This is also a punishable offense.

5. Although discussion among the students through piazza and other means are encouraged, the sharing of work is plagiarism. If you are not sure about it, please ask a TA or stop by the instructor’s office during the office hours.

6. TAs and Instructor determine whether the project is plagiarized. Trust us, it is really easy to determine this….

6.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 should not 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. Consider instead using a screen-sharing collaboration app, such as http://webex.gatech.edu, to help someone with debugging if you’re not in the same room.

12