CS2110-Project 3 Assembly Solved

Hello and welcome to Project 3. In this project, you’ll 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 it’ll 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 it’s 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 AB, 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 can’t 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 2’s complement. You don’t 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 it’s 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. Let’s take 5 ∗ 8 − 20/10. If we were to compute it from left to right, accumulating results as we go, we’ll 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. It’s 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 :).

Let’s say we want to compute 3+4. It’s 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, we’ll 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 that’s on top of the stack.

For 3 4 +, the first token is 3, which is a number. Since it’s 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 don’t 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, let’s 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 don’t 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.