KAIST
EE 209: 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 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

• Printing operator: p
• Arithmetic operators: +, -, *, /, %, ^
• % 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.
• The result of an arithmetic operation is in the range of a 32-bit signed integer.
• You do not need to handle an overflow/underflow. That is, it is OK not to handle it correctly even if the result of an operation exceeds the range of a 32-bit signed integer.
• You can assume that each input line has only 1 operand/operator.
• You do not need to handle input errors (but your program should not crash with invalid input). See below for more detail on error handling.

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

Part 2: 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 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

#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

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:

• 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 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:

• Your mydc.s file.
• A readme 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.

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:

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

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.

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:

• Enumerated constants, for example: .equ TRUE, 1.
• Parameter stack offsets, for example: .equ OADDEND1, 8.
• Local variable stack offsets, for example: .equ UICARRY, -4.
• Stack offsets at which callee-save registers are stored, for example: .equ EBXOFFSET, -4.