Professor Shai Simonson - CSC-304 - Computer Architecture

Assignment 3

Assembly Language Using MIPS
Basic Data Structures
Stacks, Arrays, Procedures and Functions


Due  Friday, March 2.  (Total:  25 points)

    Problems (8 points)

0.  In the book - Chapter 2:  2.23, 2.38, 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

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?


1.  (6 points)  Write a SPIM program that places 24 distinct 4-byte integers into the data section..  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-2) and a column C (0-7) 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. (11 points)  Using an array to implement a stack, write a SPIM function that takes a string in postfix notation and returns its value when executed.  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.  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. Note, you should need only one jal instruction and one function.  If you try to use nested procedures then you will need to set up stack frames in order to save return addresses.