CMPUT 229 - Computer Organization and Architecture I

Lab 2: Return-Address Stack Ordering

Starter Code

You can download the starter code here.

Introduction

The goal of this assignment is to write a RISC-V program that creates a stack to simulate a Return-Address Stack.

The internal architecture of most advanced microprocessors contains a mechanism called the Return-Address Stack. Conceptually it is simple: each time that a function call is executed, the memory address of the instruction where execution must continue after the function returns is pushed into the stack. Whenever a return instruction is executed, the top of the stack is popped to discover the address where execution will continue.

A stack is a data structure that occupies a space in memory where data can be stored. To make the programming assignment simpler, the program created processes a string of characters. Open parenthesis stands for function calls and closing parenthesis stands for function return. Next to each open parenthesis, there is always be a single character that stands for the return address. Thus, the solution will use a stack to store characters. Data is added to the stack by pushing it onto the stack, and data is removed from the stack by popping it from the stack. Popping a value from the stack does not remove the value from memory, it simply changes the address of the top of the stack. The popped value is no longer part of the active stack and will be overwritten later when another value is pushed to that position of the stack.

When storing a stack in memory, a buffer must be allocated to contain the stack. This buffer is a contiguous sequence of bytes in memory. Stacks can be implemented to grow in one of two different ways. A stack can grow either by adding to or subtracting from the address of the top of the stack. In this lab, we will be asking you to grow the stack by subtracting from the provided stack address, in other words, as you push items onto the stack you will have to decrement the value provided to you in a1 for the first byte of the memory space reserved to contain the stack. For example, if the stack is to contain bytes, and starts at address 0x10001024 then the first item pushed onto the stack would be stored at address 0x10001024 and the second element pushed onto the stack will be stored at address 0x10001023.

Task

Create a program that, given a string of characters, containing opening parenthesis, closing parenthesis, and other characters, will print another string containing only alpha characters. Each time that a closing parenthesis is encountered in the input string, the character that immediately follows the open parenthesis must be printed.

Input

Your program will read characters from a provided string. Each character occupies a byte in memory. Therefore you can read a character from the string using the lb or lbu instruction (lbu is recommended for loading characters) --- you are supplied (in common.s) with code that reads the string from a file and stores it in the memory before your program executes.

common.s is in the starter code zip file linked above.

A valid input string is formed by ASCII character and must follow these constraints:

• "(": symbolizes a function call and must be immediately followed by an ID
• ")": symbolizes a function return
• "a-z" or "A-Z":
• if preceded by an "(", is the ID of that function
• otherwise, is meaningless
• Any other ASCII character: is meaningless
• Parenthesis are balanced: there must be a ")" to match every "("
• The string is null-terminated: there is a character with value zero at the end of the string.

Example input:

(a(b))

This string is representing the execution of a program. In that execution the following actions would occur in sequence:

1. A function call with return address a;
2. a function call with return address b;
3. the function call with return address b returns;
4. the function call with return address a returns.

The program should print the order in which the functions return occur in the string representation. For example, the correct output for the above example is ba.

More example input and correct output:

Input	Correct Output
(a(b(c)))(b)	cbab
a(car)(dog(egg))	ced

In the second example, the characters a, ar, og, and gg are ignored. This input is equivalent to (c)(d(e))

The following strings are invalid inputs and can never occur:
(a(b)
)a(b)(
(((a)

Specifications

Write a function called rsa (standing for "return-address stack"). Thus, the label rsa: must appear immediately after the .text directive. When rsa starts executing, the input string is already stored in memory. The memory space that is needed to store the stack is also already allocated. rsa receives these memory addresses as arguments in registers a0 and a1 respectively. Here is the specification for rsa:

• rsa:
• Arguments:
• a0: address of the string to parse.
• a1: address of the memory that is to be used as a stack.
• Effect:
• print the function IDs in the order they return, based on the string representation of some program's control flow. Do not print a newline after printing the order so that the solution works well with the automated grading scripts.
• Note:
• In RISC-V assembly every subroutine must have a return statement, this return statement is the instruction: jr ra. Thus, make sure to include this instruction at the end of rsa so that it can work well with the automated grading scripts.

When RARS starts executing it looks for a main: label where it will find the user code. This common.s file, that is provided, contains a main function that reads a string from a file, writes the string to memory, allocates memory for the stack, and then calls your rsa function. You are encouraged to read the code in the common.s file to understand how the whole program works. Do not include the provided common.s along with the solution. The grading script will use a different file to execute the solution.

Tips

The following is a possible algorithm, though others are also correct:

1. Load a byte from the input string, a0.
2. If the character is an "(", push the next character onto the stack.
3. If the character is an ")", pop a character from the stack and print it using the PrintChar system call.
4. Ignore all other characters.
5. Repeat the above process until you encounter the terminating null character, "\0"

Hint: PrintChar prints the character in a0, therefore, a character needs to be put into a0 before it can be printed. Before putting a value in a register, we need to think about what is currently in that register because that value will be overwritten. In this case, the address of the input string is stored in a0, this is important data that cannot be simply overwritten. Consider moving the address of the input string to another register to avoid overwriting it. Look into the mv instruction.

Testing

To test your program ensure that you follow the steps in Lab 1 to enable program arguments in RARS. Once you have assembled your program, enter the name the test file into the Program Arguments section in the Execute tab. Note: You must open RARS from the same directory that contains the test file. Otherwise, RARS will be unable to find the file.

Test files should be text files with valid input on the first line. Examples in the Code/tests folder.

We have provided an executable file for you to download: rsaInputChecker (linux) rsaInputChecker (mac), that finds the solution when provided valid input and reports an error for invalid input. To use the tool, use the following command: ./rsaInputChecker TESTPATH. Replace TESTPATH with the path of the file that you want to run rsaInputChecker on. Make sure you turn the file into an executable with the command: chmod +x rsaInputChecker first. ThersaInputChecker executable may not work on your machine, in that case you should try using it on the lab machine.

Resources

• Old Video for in-class presentation of the lab (YouTube)
• Slides used for in-class introduction of the lab (.pptx) (.pdf)

Marking Guide

• 70% for correct program functionality
• 30% for program style
• Here is the mark sheet used for grading

Submission

Files to submit for this assignment:

• File rsa.s should contain the assembly program you wrote.
• Do not add a main label to this file
• Do not modify the line .include "common.s"
• Submit only your rsa.s