Assignment 3
Assembly Language Using MIPS
Basic Data Structures
Stacks, Arrays, Procedures and Functions
Due Wednesday, March 13. (Total: 25 points)
Problems (7 points)
0. In the book - Chapter 2: 2.23, 2.38, Chapter 3: 3.22, 3.23.
1. What is the address of element 36 (decimal), assuming the array starts at 1 - as in languages like Fortran and Basic, in an array of size 45 (decimal) that starts at memory location 40 (decimal) if the elements are:
a. characters b. integers c. 7-byte structs d. 10-character strings (note that is 11 bytes including the closing ascii 0).
2. A 12 by 11, 2-dimensional array, has its first row and column numbered 0,0. The base address is 1000, and each element is a word. What is the byte address of element [8,10] assuming row-major form? What is the byte address of element [8,10] assuming column-major form?
Programs
1. (6 points) Write a SPIM program that hardcodes 24 distinct 4-byte integers into the data section, starting at some label. For convenience, the numbers can be 1-24 but your program should work with any numbers. The 24 integers in a contiguous section of memory represent a 3 by 8 array. Your program accepts a row R (0 through 2 inclusive) and a column C (0 through 7 inclusive) and prints the integer in row R column C, assuming that
(a) that the array is stored in row-major form and
(b) that the array is stored in column-major form.
For example, if the integers are:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24,
and R = 1, and C = 2. Then you should print:
In row-major form, the integer is 11.
In column-major form, the integer is 8.
2. (12 points) Using an array to implement a stack of integers (each one digit long), write a SPIM function (method) that takes a string in postfix notation and returns its value when executed, or an error code if there is an error. Note the MIPS convention for returning a value is to place the value in register $v0 (i.e., $2). The string should contain only single digits, and the symbols * or +. The function should return -1 if the input contains illegal symbols, and -2 if the input has all legal symbols but is not in correct postfix form. For example: 897*6++, should return 77 (i.e. 8+ (63+6)), 7**78+ is not in correct postfix form and should return a "-2" error code, and 7a+62 contains "a" and should therefore return a "-1" error code. The stack will help you check for error condition -2. We will review the algorithm for this in class. The bad things that can happen is you to try pop an empty stack, or reach the end of the input and the stack does not hold exactly one value. To this end, it might be useful to keep track of the size of the stack at all times. Note, that if the expression contains illegal characters and it is incorrect postfix then error (-1) takes precedence. For example 7+6a, should still throw a (-1) code, not a postfix format error. To this end, it is a good idea to scan the string first to make sure that the characters are all valid, looking for a (-1) error. After you are sure the characters are valid, you can then check for a (-2) error.
Write a SPIM program that reads in a string, calls the function, and prints an appropriate message based on the output of the function. For data structures, you will need an array for the character string input, and another for the stack of integers. Note, you should need only one jal instruction and one function (method). Thus there is no need to set up any stack frames or activation records. If you decide, however, to use nested procedures then you will need to set up stack frames in order to save return addresses and frame pointers.