KAIST
EE 209: Programming Structures for EE

Assignment 4: Assembly Language Programming

 

Purpose

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

Part 1: Implement basic functions of dc209

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 results of 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
343790
q

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
The dc tool supports a number of operators and subsidiary commands which you can study on the man page. For this assignment, dc209 required to implement only the following operations.

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

You might want to use esp and ebp registers to simulate the stack in the main function.

We are providing a startup file which contains the pseudo-code of dc.s file. 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 dc209, negative numbers can be added by pre-appending '_' symbol to the number. For example

mydc.s Makefile

_4
3
-
p
-7
q
calculates "-4 - 3", prints the top value (p), and quit the program (q).

Part 2: Advanced functions

The dc209 tool also provides additional operations that manipulate the input. You are required to implement the following operators for this assignment.
Advanced Operations Short decription
f Prints the contents of the stack in LIFO order. This is a useful command to use if the user wants to keep track of the numbers he/she has pushed in the stack.
c Clears the contents of the stack.
d Duplicates the top-most entry of the stack and pushes it in the stack.
r Reverses the order of (swaps) the top two values on the stack.
x Generates a non-negative random number smaller than 1024 and pushes it in the stack.
y Finds the biggest one of the prime numbers that are lesser or equal to the top-most entry in the stack, and pushes it in the stack if it exists.

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 dc209 operators can be used:

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

dc209 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, dc209 prints out all the contents of the stack in LIFO order.

The following self-explanatory example shows how one can use 'd' in dc209

4
d
*
p
16
q

Finally, 'r' is used to reverse the order of (swaps) the top two values on the stack as is shown in the example below:

4
8
f
8
4
r
f
4
8
q
In order to implement x (to generate a random number), You can implement an assembly code corresponding to following C function.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define RAND_MAX 1024

int get_random() {
    int random_number = rand() % RAND_MAX; // random number up to 1024
    return random_number;
}

int main() {
     srand(time(NULL)); // call srand at the beginning of the main
     ...
     int random_number = get_random();
     ...
}
    

Error Handling

You are required to implement basic error handling and ensure that your program does not crash with any given input (except for one case: it is OK to crash if dc209 has to divide by 0). Your program should ignore those input values that have mixed alphanumeric characters. You should check whether the stack has at least two operands for +, -, *, /, %, ^ operations. In case there are not enough operands, dc209 should print out 'dc: stack empty'(not dc209: stack empty) to standard output. For p, d, r, y operators, dc should again print 'dc: stack empty' if the stack does not contain at least one operand (two for r). For all other operators, dc209 should do nothing if the stack is empty.

Logistics

Develop on lab machines. Use emacs to create source code. Use gdb to debug.

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 produce your assembly language code manually.

We encourage you to develop "flattened" pseudo-code (as described in precepts) 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 file should contain:

Submission

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

For example, if your student ID is 20191234, please name the file as 20191234_assign4.tar.gz

Create a local directory named 'YourStudentID_assign4' and place all your files in it. Then, tar your submission file. Please refer here for how to archive your assignment.

Your submission need to include the following files:

Please do not submit emacs backup files, that is, files that end with '~'.

Create a local directory named 'YourStudentID_assign4' and place all your files in it. Then, tar your submission file. Please refer here for how to archive your assignment. Do not archive your submission file without creating a directory and moving your files inside.

Your submission file should look like this:

20191234_assign4.tar.gz
mydc.s
readme
EthicsOath.pdf
test_case
(Optional, can be any name or multiple files)

You can use this checker before you submit. This checker only checks your submission is in valid format.

Do not put another source files in your submission. Your implementation must lay in mydc.s, not in other files.
The name of the files must be exact. Note that file name is case sensitive. You might not get the full credit if the names are not correct.

Late Submission

You can use the late submission (late pass; as known as a token) which can be late up to three days without penalty for the first four programming assignments. That is, you can apply your late submission days (within 3 days in total) spread over the first four programming assignments. The minimum granulaity is one day: if you are 1 hour late, that's still counted as one day late. If you're going to spend your free late days, please say so in your readme file.

You need to notify your token usage in your readme file in following format; [TOKEN=n] where n is the number of tokens that you want to use. For example, if you want to use 2 tokens, following text MUST be included in your readme.

[TOKEN=2]

You need to strictly follow this format. Otherwise, TAs will not consider your late token usage.

Grading

As always, we will grade your work on quality from the user's and programmer's points of view. To encourage good coding practices, we will deduct points if gcc209 generates warning messages.

Comments in your assembly language programs are especially important. Each assembly language function -- especially the main function -- should have a comment that describes what the function does. Local comments within your assembly language functions are equally important. Comments copied from corresponding "flattened" C code are particularly helpful.

Your assembly language code should use .equ directives to avoid "magic numbers." In particular, you should use .equ directives to give meaningful names to:

Please note that you might not get a full credit even if you pass the test with your test case. TAs might use another test cases to test functionality and robustness of your implementation.
>