Skip to content

Computer Architecture Programming Assignment

Assignment 2: RPN Calculator

Assignment Description

You are to write a simple calculator for unlimited-precision unsigned integers.

Reverse Polish notation (RPN) is a mathematical notation in which every operator follows all of its operands, for example 3 + 4 would be presented as "3 4 +".For simplicity, each operator will appear on a separate line of input.Input and output operands are to be in hexadecimal representation.

Each number or operator is entered in a separate line. For example, to enter a number 0x7A the user should type:

7A

Operations are performed as is standard for an RPN calculator: any input number is pushed onto an operand stack, represented as an array (not the 80X86 machine stack), and each operation is performed on operands which are taken (and removed) from the stack. The result, if any, is pushed onto the stack. Output will contain no leading zeroes (the input could have some leading zeroes).

The operand stack size should be 5, specified such that in order to change it to a different number only one line of code should be modified (hint: use EQU). You should print out "Error: Stack Overflow" if the calculation attempts to push too many operands onto the stack, and "Error: Not Enough Arguments on Stack" if an operation attempts to pop an empty stack. Your program should also count the number of operations performed. Number type size is not bounded. The following section suggests a recommended implementation.

Implementation of Unlimited Precision

In order to support unlimited precision, each operand in the operand stack stores a linked list (of bytes) for each operand. A linked list (of bytes, in this case) is implemented as follows. You should, conceptually, have a "type" consisting of a pointer to next, and a byte of data. Since there are no types in assembly language, any memory block of the requisite size (5 in this case: 4 for the pointer, one for the byte of data) can be seen as an element of this type. To make sure the memory blocks are free before use, you should allocate them from free memory, using malloc(), just as you would do in C.

If an operation results in a carry from the most significant byte, additional bytes must be allocated to store the results. The operand stack is best implemented as an array of pointers - each pointing to the first element of the list representing the number, or null (a null pointer has value 0). The operand stack size should still be 5.

Example:
0x7D12AF could be represented by the following linked list:

The required operations

The operations to be performed are:
  • Addition (unsigned) (+)
  • Pop-and-print (p)
  • Duplicate (d)
  • Log2 (l)*
  • Number of '1' bits(n)
  • Quit (q)

* Floor of log in base 2. That is, the exponent of the closest power of 2 (i.e. 0,1,2,4,8,16,32 etc.) that is at not greater than the given number. For example: log2(31) = 4, log2(32) = 5, log2(33) = 5, log2(63) = 5, log2(64) = 6.

The (+) operator gets 2 operands, and provides one result. The (l) and (n) operators get one operand and provide one result. The "duplicate" operator takes one operand and provides two results - duplicates of its input operand. Note that all operands are implicit, i.e. they are popped from the stack, and not specified in the command line. The result(s) is pushed onto the stack. Pop-and-print takes one operand, and provides no result. It just prints the value of the operand to the standard output in either hexadecimal or decimal, depending on the current representation setting.

Run example

An example of user input and program output appears below. Comments (which will not appear in input or output) are preceded by ";". The calculator prompt to the user is "calc: "

calc: 09     ; user inputs a number
calc: 1      ; user inputs another number
calc: d      ; user enters "duplicate" operator
calc: p      ; user enters pop-and-print-operator
1
calc: +      ; user enters "addition" operator, 0x0A is in top of (and is the sole element in) stack right after
calc: d
calc: p
A
calc: 10      ; user enters another number 10
calc: +
calc: d
calc: p
1A ; the sum
calc: +
Error: Insufficient argument count in stack
calc: AB      ; user inputs a number
calc: FE12     ; user inputs a number
calc: n      ; user enters "number of '1' bits" operator
calc: p
9      ; the result of FE12 number of '1' bits"
calc: l      ; user enters "log2" operator
calc: p
3
calc: q      ; Quit calculator

Additional Requirements

Modularity is a requirement in this assignment. Thus, calculator functions, as well as input and output functions, must be programmed as procedures (subroutines). Additionally, printout of results should use the C library function printf(), and getting a line by using gets(). Your code will be written entirely in assembly. The "main" program (that you also need to write in assembly) calls my_calc that is your primal procedure, and prints out the number of operations performed by my_calc. (Note that my_calc should count and return that number). If the user enters "q" at any time during the run of the program, your program should exit gracefully, by having my_calc returning the total number of operations performed, and using RET to return to the "main" code (which should print out that number before exiting).

Desired Output:

  • A successful calculation should present no additional output.
  • Pop-and-print should print out the top member of the stack.
  • If an action results in a stack overflow, you program must print (without the quotes): "Error: Stack Overflow"
  • If an action requires more arguments than currently available in the stack, your program should print: "Error: Not Enough Arguments on Stack"
  • In any case, if an error occurs, your program must return the stack to its previous state (such as in a case when an action that requires 2 arguments fails because there is only one argument in the stack, etc).

Prototypes for C functions you can use

  • char* gets(char *s)
  • int printf(char *format, arg list …)
  • void* malloc(size_t size) // size_t is unsigned int for our purpose
  • If you use those functions the beginning of your text section will be as follows (no _start label):

section .text
     align 16
     global main
     extern printf
     extern malloc
     extern gets
main:
      … ; your code

  • Declare a label "main:" and "global main" in your assembly program.
  • Declare "extern printf, extern malloc" and "extern gets" so you will be able to use those functions in the program 
  • Compile and link your assembly file calc.s as follows:

    nasm -f elf calc.s -o calc.o
    gcc -m32 -Wall -g calc.o -o calc.bin

    Note: there is no need in c file! Gcc will “connect” external c functions to your assembly program.

    Assumptions and Minor requirements

    • Illegal characters should be ignored.
    • You may assume that the number entry format is correct.
    • Each input line is no more than 80 characters in length, with the operator and/or number beginning as the first character of the line.
    • Other errors can be either ignored or flagged, but your program should never crash.

Frontal Checking Hours

Inf3 Computer Architecture - 2017-18


Announcements:

  • Mar 8: Assignment 2 released

  • Feb 5: First assignment released

  • First lecture is Monday, 15th January 2018 at 10:00 in David Hume Tower, LG.11.


Lectures: Mondays and Thursdays, David Hume Tower, LG.11, 10:00 - 10:50am.

Course staff:

Textbook: Hennessy and Patterson Computer Architecture: A Quantitative Approach (5th edition). 4th edition is also acceptable.
You are strongly advised to obtain a copy of the textbook as there are no printed lecture notes for this module.

Course materials:

Assignments: There will be two programming assignments, which (in total) will contribute 25% of the overall mark for this course.

  • Assignment 1: In this assignment, which will contribute 12.5% of your overall mark, you will simulate various branch predictors using the Pin tool. Out 5-2-2018; Due 19-2-2018

  • Assignment 2: In this assignment, which will contribute 12.5% of your overall mark, you will implement and compare data prefetchers using the Pin tool. Out 8-3-2018; Due 22-3-2018

Late coursework submissions: See the Informatics' late coursework policy.

There is zero tolerance for any form of academic misconduct. See the Informatics' Academic Misconduct Policy.

Additional information and useful resources:

  • Formative Feedback: Formative feedback for the CAR course will be provided through oral feedback provided during tutorials.

  • Course Descriptor:Here you can find assessment information, a link to a timetable covering tutorials and lectures, and other useful info.

  • Past exam papers: You can find past papers in the ITO past papers repository.


Vijay Nagarajan, IF room 2.04A, ext. 513440
Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK
Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail: school-office@inf.ed.ac.uk
Please contact our webadmin with any comments or corrections. Logging and Cookies
Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh