Description

Irene Feijoo, Avaneesh Naren, Izabela Hadula
Contents
1 Timed Lab Rules – Please Read 2
2 Overview 2
2.1 Purpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Task . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3 Detailed Instructions 3
3.1 tolowercase (THIS FUNCTION IS GIVEN TO YOU) . . . . . . . . . . . . . . . . . . . . 3
3.2 areletters equal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.3 ispalindrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4 Checkpoints 5
4.1 Checkpoints (72 points) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.2 Other Requirements (28 points) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
5 Deliverables 6
6 Local Autograder 7
7 LC-3 Assembly Programming Requirements 8
7.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
8 Appendix 9
8.1 Appendix A: LC-3 Instruction Set Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Please take the time to read the entire document before starting the assignment. It is your responsibility to follow the instructions and rules.
1 Timed Lab Rules – Please Read
2 Overview
2.1 Purpose
The purpose of this timed lab is to test your understanding of implementing subroutines in the LC-3 assembly language using the calling convention, from both the callee and caller side.
2.2 Task
You will implement the subroutines listed below in LC-3 assembly language. Please see the detailed instructions for the subroutines on the following pages. We have provided pseudocode for the subroutines—you should follow these algorithms when writing your assembly code. Your subroutines must adhere to the LC-3 calling conventions.
2.3 Criteria
Your assignment will be graded based on your ability to correctly translate the given pseudocode for a subroutine (function) 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 what you must submit to Gradescope.
You must produce the correct return 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 conventions correctly, all of these things will happen automatically. Additionally, we will check that you made the correct subroutine calls, so you should not try to implement a recursively subroutine iteratively.
Your code must assemble with no warnings or errors (Complx and the autograder 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.
3 Detailed Instructions
For this Timed Lab, you are given a doubly-linked list and you need to check if its data is a palindrome ignoring case.
Each node in the doubly-linked list is represented by three consecutive words in memory. The first word is the data held by the node. Each node holds a character encoded in ASCII, so the entire list can be viewed as a string. The second and third words are the addresses of the previous and next nodes in the list respectively. If there is no previous or next node — that is, if the node is the first or last node in the list respectively — then both those addresses will be set to x0000.

The primary function you will implement is ispalindrome. It takes as parameters the addresses of the first and last nodes in the linked list. The function will return 1 if the string represented by the list is a palindrome ignoring case and 0 otherwise. Note that case should be ignored, so the method should return 1 even if the string is “abA”. Also note that it should return 1 for an empty list.
For convenience, the pseudocode uses a few helper methods. The tolowercase function takes in as its only parameter a character encoded in ASCII. It makes the character lowercase if it’s an uppercase letter, leaving it untouched otherwise. The tolowercase function will be given to you. The arelettersequal function takes as its parameters two nodes in the doubly-linked list and returns whether their data are equal ignoring case. You will implement arelettersequal.
3.1 tolowercase (THIS FUNCTION IS GIVEN TO YOU)
Parameter c: Character encoded in ASCII
Returns: Lowercase version of c if it’s in the range ‘A’ to ‘Z’; otherwise just c unchanged Examples:
• tolowercase(‘a’) == ‘a’
• tolowercase(‘A’) == ‘a’
• tolowercase(‘5’) == ‘5’
3.2 arelettersequal
This function takes in two addresses of nodes from the doubly-linked list as input. It outputs whether they contain equal data ignoring case. Note that case is ignored. All the characters should be taken to lowercase before comparing them.
Parameter node1: The address of a node in the doubly-linked list Parameter node2: The address of a node in the doubly-linked list Returns: 1 if both nodes have the same data ignoring case, 0 otherwise Examples:
• are lettersequal on node1 containing ‘A’ and node2 containing ‘A’ returns 1
• arelettersequal on node1 containing ‘A’ and node2 containing ‘a’ returns 1
• are lettersequal on node1 containing ‘5’ and node2 containing ‘6’ returns 0 Pseudocode:
are_letters_equal(Node node1 (address), Node node2 (address)) { char letter1 = mem[node1]; char letter2 = mem[node2];
letter1 = to_lowercase(letter1); letter2 = to_lowercase(letter2);
if (letter1 == letter2) { return 1;
} else { return 0;
}
}
3.3 ispalindrome
Takes in both the head and tail addresses for a doubly-linked list, and returns whether the data contained inside is a palindrome ignoring case. Note that case is ignored. All the characters should be taken to lowercase before comparing them.
Parameter head: The address of the first node in the doubly-linked list
Parameter tail: The address of the last node in the doubly-linked list Returns: 1 if the list’s data represents a palindrome ignoring case; 0 otherwise Examples:
• ispalindrome on “aba” returns 1
• ispalindrome on “abA” returns 1
• ispalindrome on “abba” returns 1
• ispalindrome on “ab!” returns 0
• ispalindrome on “Happy Birthday!” returns 0
Pseudocode:
is_palindrome(Node head (address), Node tail (address)) { if (head == 0 || tail == 0) { return 1;
}
if (are_letters_equal(head, tail) == 0) { return 0;
}
Node new_head = mem[head + 2]; Node new_tail = mem[tail + 1]; return is_palindrome(new_head, new_tail); }
4 Checkpoints
4.1 Checkpoints (72 points)
In order to get all of the points for this timed lab, your code must meet these checkpoints:
• Checkpoint 1 (30 points): Implement subroutine arelettersequal to return if the letters at each node passed in are equal, ignoring case.
• Checkpoint 2 (22 points): Implement the base case of ispalindrome to successfully compute and return 1 in the case that either the the head or tail is NULL, or return 0 if the current head and tail data values are not equal.
• Checkpoint 3 (20 points): Implement the recursive case of ispalindrome to successfully compute and return the value of the recursive call.
4.2 Other Requirements (28 points)
Your subroutine must follow the LC-3 calling convention. Specifically, it must fulfill the following conditions:
• Your arelettersequal subroutine must call the tolowercase subroutine according to the pseudocode’s description.
• Your ispalindrome subroutine must be recursive and call itself and arelettersequal according to the pseudocode’s description.
• When your subroutine returns, every register must have its original value preserved (except R6).
• When your subroutine returns, the stack pointer (R6) must be decreased by 1 from its original value so that it now points to the return value.
5 Deliverables
1. tl03.asm
6 Local 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
7 LC-3 Assembly Programming Requirements
7.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
Bad Comment ; if counter == 0 don’t loop again
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 4., you can randomize the memory and load your program by going to File ¿ Advanced Load and selecting RANDOMIZE for registers and memory.
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. The stack will start 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 HALT or RET instructions before any .fills).
9. Do not add any comments beginning with @plugin or change any comments of this kind.
10. You should not use a compiler that outputs LC3 to do this assignment.
11. Test your assembly. Don’t just assume it works and turn it in.
8 Appendix
8.1 Appendix A: LC-3 Instruction Set Architecture