KAIST
EE209: Programming Structures for EE

Purpose

The purpose of this assignment is to help you learn about computer architecture, assembly language programming, and testing strategies. It will also give you the opportunity to learn more about the GNU/Unix programming tools, especially bash, gcc, and gdb for assembly language programs.

A Desk Calculator Program in Assembly Language

Part a: Implement basic functions of dc

In this work, you are required to write the dc (desk calculator) program in assembly language. We provide you the skeleton code for dc written in assembly language, a startup file (details are in the below). You will start from reviewing this code and modifying and adding the code with respect to the requirement specified below. Good luck!

dc (desk calculator) is a tool on Unix-like operating systems. In its simplest form, dc reads a list of numbers from the standard input (stdin) and uses a set of command keys to display the results of the user-specified operations on the standard output (stdout).

In dc, the operands (numbers) and operators are added in reverse-polish (also known as postfix) notation. In this scheme, the operator follows the operands. The following example execution run explains how dc is used.

567
343223
+
p
q

The result will be printed (by p command) to the standard output stream as:

343790

dc uses a stack to store numbers in LIFO order (last-in, first-out). Whenever it encounters an arithmetic operator, it first pops out the last 2 operands from the stack, runs the operation on those numbers and then pushes the result back into the stack. In the example above, 567 and 343223 are pushed in the stack one after the other. Once the operator '+' is entered, dc first pops 343223 and then 567 from the stack. It then adds the two integers and finally pushes the result (343790) back in the stack. The command p is used to print the value that sits on the top of the stack. Please note that p only retrieves the value without popping (this is also known as a peek operation). The user can either quit the program by entering q or EOF character to the program. In other words, if the annotated text mentioned above is stored in a file named values.txt then dc can also be executed in the following manner:

$ dc < values.txt

which will print the result to the standard output stream as:

  343790

• Printing operator: p
• Arithmetic operators: +, -, *, /, %, ^
• +, -, * computes addition, subtraction, and multiplication, respectively.
• / computes the quotient (in integer) in integer division. For example, 3/2 = 1.
• % performs remainder operation.
• ^ performs exponentiation (e.g., 2^4 = 16). You don't need to implement negative exponent.
• Terminating operator: q

To make the assignment tractable in assembly programming, we make some simplifying assumptions:

• You can assume all operands are 32-bit signed integers.

You might want to use rsp and rbp registers or temporary registers (r12, r13, and r14) to implement your stack for computation in your code. For simplicity, you can assume that the maximum number of element in the stack is 64 (i.e., your program should be able to handle at least 64 elements.)

We provide skeleton code and several utilities (e.g., Makefile and tests) in assignment4.tar.gz. As usual, please check README.md. Please go through the pseudo-code before you begin writing the program. It is acceptable to use global (i.e. bss section or data section) variables in mydc.s. Please make sure that you create your own function to implement the power (^) arithmetic operator. In dc, negative numbers can be added by pre-appending '_' symbol to the number. For example

_4
3
-
p
q

-7

Part b: Advanced functions

Please note that 'f' does not pop out any numbers out of the stack. The following example run of dc shows how a combination of different dc operators can be used:

53
48
35
+
+
343223
43
56
76
35
98
1
f
q

which will print the result to the standard output stream as:

1
98
35
76
56
43
343223
136

dc keeps on pushing the integers on the stack (53, 48, 35) till it encounters the first '+' operator. It pops out 35 and 48, computes the addition and inserts 83 back in the top of the stack. When the second '+' is inserted, it repeats the same process with the integers 83 and 53 and inserts back 136 in the empty stack. Later when 'f' is entered, dc prints out all the contents of the stack in LIFO order.

Error Handling

• Your program should ignore trailing characters from the input value. In other words, you can just check the first letter, and regard the input as an operand if it is a number or starting with _. For example, regard 123abc as 123, pabc as p, and abc123 as a (not an operator, do nothing). Additionally, the words pre-appending '_' symbol to the characters, such as _abc, can be treated as 0.
• You should check whether the stack has at least two operands for +, -, *, /, %, ^ operations. If there are not enough operands, dc should print out 'dc: stack empty' to standard error and should not be terminated (i.e., keep continuing).
• For p operators, dc should again print 'dc: stack empty' to standard error if the stack does not contain at least one operand.
• For other operators (i.e., f, c operators), dc should do nothing if the stack is empty.
• If dc has to divide by 0, it should print 'dc: divide by zero' to standard error and should be terminated.
• If dc has to compute remainder by 0, it should print 'dc: remainder by zero' to standard error and should be terminated.
• If the result of an arithmetic operation is not in the range of a 32-bit (i.e., overflow or underflow), dc should print 'dc: overflow happens' to standard error and should be terminated.

Detailed Semantics

Refer to the table below for semantics of each operator.

if len(stack) < 2:
  fprintf(stderr, "dc: stack empty\n")
  continue
op2 = stack.pop()
op1 = stack.pop()
stack.push(op1+op2)
if overflow:
  fprintf(stderr, "dc: overflow happens\n")
  exit(1)

if len(stack) < 2:
  fprintf(stderr, "dc: stack empty\n")
  continue
op2 = stack.pop()
op1 = stack.pop()
stack.push(op1-op2)
if overflow:
  fprintf(stderr, "dc: overflow happens\n")
  exit(1)

if len(stack) < 2:
  fprintf(stderr, "dc: stack empty\n")
  continue
op2 = stack.pop()
op1 = stack.pop()
stack.push(op1*op2)
if overflow:
  fprintf(stderr, "dc: overflow happens\n")
  exit(1)

if len(stack) < 2:
  fprintf(stderr, "dc: stack empty")
  continue
op2 = stack.pop()
op1 = stack.pop()
if op2 == 0:
  fprintf(stderr, "dc: divide by zero\n")
  exit(1)
stack.push(op1/op2)
if overflow:
  fprintf(stderr, "dc: overflow happens\n")
  exit(1)

if len(stack) < 2:
  fprintf(stderr, "dc: stack empty\n")
  continue
op2 = stack.pop()
op1 = stack.pop()
if op2 == 0:
  fprintf(stderr, "dc: remainder by zero\n")
  exit(1)
stack.push(op1%op2)

if len(stack) < 2:
  fprintf(stderr, "dc: stack empty\n")
  continue
op2 = stack.pop()
op1 = stack.pop()
stack.push(power(op1,op2))
if overflow:
  fprintf(stderr, "dc: overflow happens\n")
  exit(1)

exit(0)

if len(stack) == 0:
  fprintf(stderr, "dc: stack empty\n")
  continue
printf("%d\n", stack[len(stack)-1])

for (i = len(stack)-1; i >= 0; i--):
  printf("%d\n", stack[i])

stack.clear()   #len(stack) should be 0 after this line

Logistics

Develop on lab machines. Use your favorite editor to create source code. Use gdb to debug. Your code must be written in x86-64 assembly (64-bit), not IA-32 (32-bit). Please do not use flags such as -m32. You will get zero point if your code does not compile in x86-64.

If you want to figure out whether your binary is 32-bit or 64-bit, use file command.

$ file mydc
mydc: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=c0c395501f6462219f4b8054e352e478d12d4c27, for GNU/Linux 3.2.0, with debug_info, not stripped
$ file mydc_x86
mydc_x86: ELF 32-bit LSB shared object, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, BuildID[sha1]=7a1e89b5efa55eb22c0c32aec30047a1e1398513, for GNU/Linux 3.2.0, with debug_info, not stripped

Do not use a C compiler to produce any of your assembly language code. Doing so would be considered an instance of academic dishonesty. Instead, you should write your assembly language code manually.

We encourage you to develop "flattened" pseudo-code (as described in EE209 and EE485) to bridge the gap between the given pseudo-code and your assembly language code. Using flattened pseudo-code as a bridge can eliminate logic errors from your assembly language code, leaving only the possibility of translation errors.

We also encourage you to use your flattened pseudo-code as comments in your assembly language code. Such comments can clarify your assembly language code substantially.

Your README.md file should contain:

• Your name and student ID.
• A description of whatever help (if any) you received from others while doing the assignment, and the names of any individuals with whom you collaborated, as prescribed by the course "Policy" Web page.
• (Optionally) An indication of how much time you spent doing the assignment.
• (Optionally) Your assessment of the assignment.
• (Optionally) Any information that will help us to grade your work in the most favorable light. In particular you should describe all known bugs.

Submission

Use KLMS submission link to submit your assignments. Your submission should be one gzipped tar file whose name is

YourStudentID_assign4.tar.gz

Your submission need to include the following files:

• Your mydc.s file.
• A README.md file.
• Observance of Ethics. Sign on the document, save it into a PDF file, and submit it.
• (Optionally) Any data file you tested your mydc program with.

Your submission file should look like this: