Hello and welcome to Project 3. In this project, youll write some simple programs in assembly, and then build your very own Reverse Polish Notation calculator in assembly!

1.2 General Instructions

• You can create your own labels and fill them with data as you see fit.
• You can modify the values stored in some of the helper labels we provide you if you think itll make it easier for you to program with
• You are free to create your own helper subroutines (although you are not required to for this project).
• Take a look at Section 6 for details on the LC-3 Assembly Programming requirements that you must adhere to

1.3 Running the autograder

Take a look at section 4 for information on how to run the autograder, and how to debug your code.

2 Simple ASM Programs

2.1 Compare

To start off, you will implement the compare function. Comparing two values is something you will do frequently in assembly, so its important you know how to do this. The two operands are stored in memory with the labels A and B. You will load them from memory, and store a value in the label RESULT. The value that you store to RESULT depends on whether A is greater than B.

• If A<B, you should store 1.
• If A = B, you should store 0.
• If A>B, you should store 1.

You may assume that the memory addresses labeled as A, B, RESULT are reachable via a PC-offset instruction with 9-bit offset. Write your code in comp.asm.

2.2 Modulus

In this part of the project, you will be implementing the modulus operator that you will find in a lot of programming languages. Since there are different interpretations of modulus for negative numbers, you should take the absolute values of both your operands and then perform the operation. The two operands are stored in memory with the labels A and B. You will load them from memory, perform the modulus operation, and then store the result in the label RESULT.

Suggested Pseudocode:

a = mem[A]; b = mem[B];

a = abs(a); b = abs(b);

while (a >= b) { a = a b;

} mem[RESULT] = a;

You may assume that the memory addresses labeled as A, B, RESULT are reachable via a PC-offset instruction with 9-bit offset. You do not need to worry about overflow for negation or subtraction. Write your code in mod.asm.

2.3 To Uppercase

Next, you will write a program that prints out an all uppercase version of an input string. You do not need to change the string store in memory, but instead just print the uppercase string to console.

• Strings are essentially a contiguous array of ASCII values. In this case, the first character is stored at the address indicated by the value at the address labeled as STRING.
• The string continues until the first instance of a null terminator, which has the value of 0.

Here is an example layout:

Address	Label	Value
x3021	STRING	x4000
x3022	RESULT
x4000		h
x4001		A
x4002		h
x4003		A

The string that you receive can contain any characters, and you should change all letters to uppercase, and leave non-letters as is. You may assume that the memory address labeled as STRING will be reachable via a PC-offset instruction with 9-bit offset. However, the actual contents of the string might be stored at addressed that cant be reached via a 9-bit offset. We have given you some labels in the assembly file that you might find helpful. As a hint, take a look at the trap vectors to see how you might print characters to the console. Write your code in toupper.asm.

2.4 Alternating array sum

For this section, you will iterate through an array and either add or subtract from a sum depending on the index of the array. For every element with an even index, you should add its value to the sum. For every element with an odd index, you should subtract its value from the sum. The sum should start from 0, and we are using 0-indexing here. The array length will be stored at the label LENGTH and the address of the first element will be stored at the label ARRAY. Note that ARRAY stores the address of the first element instead of the first element itself. An example memory layout might look something like this:

Address	Label	Value
x3020	LENGTH	4
x3021	ARRAY	x7000
x3022	RESULT
x7000		1
x7001		2
x7002		3
x7003		4

After you compute the sum, you should store the value in RESULT. You can assume that the labels LENGTH, ARRAY, RESULT will be reachable via a PC-offset instruction with a 9-bit offset, but you cannot make the same assumption about the starting address of the array stored in ARRAY. You might notice that the memory layout is very similar to the previous question, so maybe consider resuing your code. Write your code in sum.asm.

3 Building an RPN Calculator

For this part of the project, you will be implementing a Reverse Polish Notation calculator (RPN) from scratch in LC3 assembly.

Your calculator must support the following operators:

1. Addition (+)
2. Subtraction ()
3. Multiplication ()
4. Division (/)

The operands will be integers in 2s complement. You dont have to support floating point numbers.

The part of the project is further subdivided into two sub-parts. For the first sub-part, you will be implementing all of the supported operands (+, -, *, /) as subroutines. For the second sub-part, you will use these subroutines to build the calculator.

Before we lay out the specification for each part, we will discuss some background material.

3.1 Background

We are used to calculating expressions like (3 + 4)/10 and 5 8 20/10 using PEMDAS, which helps us discern the order of precedence, i.e., the order in which we should carry out calculations.

Expressions of this form, in which the operator is in between the operands, are called infix expressions. This notation is commonly used in our day-to-day life because its easy to read and parse by humans.

However, for computers, computing infix expressions poses some challenges. For simple expressions like 5 + 1 10, the task is relatively straightforward: accumulate the results from left to right.

Things get more interesting when we start bringing parentheses and operators with different precedence into the picture. Lets take 5 8 20/10. If we were to compute it from left to right, accumulating results as we go, well get 2 as the final answer, which is incorrect. This is because and / have a higher precedence that (as per PEMDAS), and therefore stick to its operands more strongly. As a result, we must first perform 5 8, then 20/10, and only then subtract the results. Doing this gives us 38, which is the correct answer.

This is a simple example. It gets even more complicated when we have deep levels of nesting. A standard way to compute infix expressions is by writing a Pratt parser. Making you write such a parser, and then evaluate the resulting tree, in LC3 assembly, would be very mean, and I would like to think that I have a heart <3.

So, how do we solve this problem?

3.1.1 Leveraging the Stack

Lucky for us, there exists another notation for arithmetic and logical expressions. Its the postfix notation.

In this notation, the operators come after their operands. For example, 3 + 4 in infix notation would be 3 4 + in postfix notation. A very nice property of postfix notation is that we can compute the resulting expression using a stack. Allow me to blow your mind :).

Lets say we want to compute 3+4. Its corresponding postfix form is 3 4 +. To begin calculating the result, we will parse tokens (numbers or operators) starting from the left. If we encounter a number, we push it onto the stack. If we encounter an operator, well pop values off the stack, calculate the result of applying the operator on the values we just popped, and the push the result back onto the stack. The final result will be the value thats on top of the stack.

For 3 4 +, the first token is 3, which is a number. Since its a number, we push it onto the stack (Figure 1a). Next, we find 4, which is also a number. So, we push 4 onto the the stack (Figure 1b). Then, we find +, which is an operator. + is a binary operator, and takes in two operands. Therefore, we pop two values off the stack, carry out the addition on these two values, and then push the result back onto the stack. The two values in our case are 3 and 4. Performing the addition gives us 7 (Figure 1c). Pushing 7 results in Figure 1d. Since we dont have any more tokens to parse, we can stop. The final result 7 is on top of the stack.

Alright, so this is super cool and all, but does it solve the problem that we earlier had with infix expressions? You sure betcha! The postfix form of 5 8 20/10 is 5 8 20 10 / (Do not worry about how we got this postfix expression. Interestingly enough, you can build such an expression from the infix form using a stack). Try computing this postfix expression using the method described above. You will get 38 as your final answer, which is indeed the correct answer!

The postfix notation is also known as Reverse Polish Notation (RPN). An RPN calculator, therefore, is a stack based calculator that can compute postfix expressions.

Computerphile has a really neat video on RPN. Feel free to take a look if you need help understanding postfix notation a little more.

With background information out of the way, lets begin writing our RPN calculator!

(a) Push A onto stack (b) Push B onto stack (c) Execute operation

(d) Push A + B onto stack

Figure 1: Computing (3 4 +) on the stack

3.2 Specification

3.2.1 Implementing the Operators

For this part, we will be implementing four operators:

1. Addition (+)
2. Subtraction ()
3. Multiplication ()
4. Division (/)

You will write your code in rpn.asm.

For each subroutine in rpn.asm, you will find comments that document the expected API contract that you need to uphold.

For multiplication and division, we highly recommend that you use the following pseudocode as a guide when writing your assembly. Recursive implementations of these operations exist, and you can definitely solve it that way for an added challenge, but we dont test for recursion, and so you are not required to do it.

Suggested Pseudocode:

Multiply:

result = 0; counter = B; negate = 0; if (counter < 0) { counter = -1 * counter; negate = 1;

} while (counter > 0) { result = result + A; counter = counter -1;

}

if (negate > 0) { result = -1 * result;

}

Divide:

result = 0; tempA = A; negate = 0; if (tempA < 0) { negate = negate 1; tempA = -1 * tempA;

} tempB = B; if (tempB < 0) { negate = negate + 1; tempB = -1 * tempB;

} while (tempA >= tempB) { result = result + 1; tempA = tempA tempB

}

if (negate != 0) { result = -1 * result; }

3.2.2 Bringing it all together

Now that we have all of our operators implemented, it is time to build the RPN calculator.

You will write your code for this part in rpn.asm as a subroutine under the label rpn. The comments above the subroutine document the expected API contract that you need to uphold.

4 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:
   • Mac/Linux Users:
     • Navigate to the directory your project is in. In your terminal, not in your browser
     • Run the command sudo chmod +x grade.sh
     • Now run ./grade.sh
   • Windows Users:
     • On docker quickstart, navigate to the directory your project is in (b) 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, dont 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. Just be careful: if you misclick and select Show Non Zero, it may make the window freeze (its a known Complx bug).

5 Deliverables

Turn in the files comp.asm, mod.asm, toupper.asm, sum.asm, and rpn.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.

6 LC-3 Assembly Programming Requirements

6.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 its much harder to interpret what is happening later, and youll 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 doesnt help in understanding what the code is doing.

Good Comment

ADD R3, R3, -1	; counter
BRp LOOPBad Comment	; if counter == 0 dont 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 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. Dont just assume it works and turn it in.

7 Demos

This project will be demoed. Demos are designed to make sure that you understand the content of the project and related topics. They may include technical and/or conceptual questions.

• Sign up for a demo time slot via Canvas before the beginning of the first demo slot. This is the only way you can ensure you will have a slot.
• If you cannot attend any of the predetermined demo time slots, e-mail the Head TA before the beginning of the first demo slot.
• If you know you are going to miss your demo, you can cancel your slot on Canvas with no penalty. However, you are not guaranteed another time slot. You cannot cancel your demo within 24 hours or else it will be counted as a missed demo.
• Your overall project score will be ((autograder_score * 0.5) + (demo_score * 0.5)), meaning if you received a 90% on your autograder, but a 30% on the demo you would receive an overall score of 60%. If you miss your demo you will not receive any of these points and the maximum you can receive on the project is 50%.
• You will be able to makeup one of your demos at the end of the semester for half credit.