CPSC 213: Assignment 3

Goal

Similar to the second assignment, this assignment encourages you to think about how HLL features are implemented at the level of machine instructions; the difference is, now your understanding is extended to include not only expression statements, but also conditional and looping statements. Furthermore, you will also practice deriving HLL statements from a sequence of machine instructions --- a process known as decompilation.

Provided Code

Download the example code snippets for this assignment and carefully inspect them, comparing the HLL (.c) versions with the SM213 Assembly (.s) version. They contain examples of the types of statements you will be expected to be able to translate to and from SM213 assembly language: everything from the previous assignment, plus if(), for(), while(), and do ... while(). Using the reference simulator, step through and convince yourself of the correspondence between the high-level expression and the instructions the machine executes. Note that the examples all perform some possibly useful computation, as described in the section below. You are not expected to understand the algorithms, but are encouraged to experiment with modifying their inputs and running in the simulator to observe their result.

Your Task

Download the code snippets to work on and carefully inspect them. Your task for this assignment is to produce commented SM213 Assembly versions for the first three code snippets, and produce a C version of the fourth (supplied as a .s file.) With the exception of the fourth, they are ordered in increasing complexity so you are strongly encouraged to start with the first and progress in order. When writing your solutions, refer to the provided examples and keep in mind the following points:

• Do not assume any initial value for the registers.
• You may optimise across the statements within the snippet; as with the previous assignment, you are encouraged to make use of the constants and invariants within a single statement. The only constraint is that the state of memory after its execution conform to the same effect it would have in C. For example, a loop counter that is global may be kept in a register throughout the body and only written to its final resting place in memory once at the end.
• The snippets are designed so that you will have sufficient registers and/or memory locations to implement them. Local variables (those which are defined and exist only within block expressions such as the two clauses of a conditional or a loop body) are to be kept in a register.
• Add comments to denote the correspondence between expressions and/or parts thereof in the HLL snippet, and the machine instructions you generated.
• Use the reference simulator for syntax checking and testing. The code you produce must load without syntax errors in order to receive credit for it.
• Although there is no equivalent in C or Java, end your code with a halt instruction to prevent the simulator from "running off the end".
• These are snippets, not complete programs; thus they will not compile and run. In particular, notice that there are no functions nor classes yet (and in assembly, neither is obligatory). You will learn about those later.
• Assume any pointer variables have been already initialised to hold the address of an array of unspecified but adequate size. For testing purposes you may do this initialisation statically in the respective .long, as illustrated in the examples. Several of the snippets also use a separate variable to hold the size of the dynamic array. (You will learn how this happens at runtime later.)
• All of these HLL snippets are in C syntax. Later assignments will include a mix of C and Java.
• For the fourth snippet, produce a .c file which contains a possible series of statements corresponding to the machine instructions. Note that there are many possibilities which are correct; to receive full credit, it is sufficient that you provide one possibility that matches the algorithm the given code implements. For example, for() and while() are equivalent (but not do...while() --- beware!), conditional expressions can be expressed using if(), etc. It is important that the algorithm be explicitly present in the code, so for example if the Asm version was an exponentiation function, you will receive no credit for submitting only a call to pow().

Hints

• Understand the overall structure of the code, and "linearise" the nested block structure into ifs and goto before writing any Asm.
• Notice that although SM213 has only two types of branches, thinking about how to order the basic blocks (e.g. "top-check" vs. "bottom-check" for loops, the order of the two clauses for an if) and the order of subtraction in the test may eliminate any need to branch around a branch. This is shown in the examples.
• Analyse where variables are used and their values need to be preserved ("live" in compiler terminology) and plan their allocation in registers to help reduce unnecessary reads from memory and/or optimise register usage. The example snippets contain comments explaining some of this.
• For decompiling the 4th snippet, understand the overall structure and try to "delinearise" it into the HLL block structure, noting where branches go and how execution flows through it. An assumed register allocation is provided for you; make use of it in commenting it to help you derive the individual HLL statements that each may correpond to multiple machine instructions.

Provided Materials

• Example code snippets containing:
  1. a3_ex1.c and a3_ex1.s
  2. a3_ex2.c and a3_ex2.s
  3. a3_ex3.c and a3_ex3.s
  4. a3_ex4.c and a3_ex4.s
• Code snippets to work on containing:
  1. a3_1.c
  2. a3_2.c
  3. a3_3.c
  4. a3_4.s

Handing In

Use the handin program. The assignment directory is a3. Please hand in exactly and only the following files with the specified names.

1. README.txt that contains
   • The first three lines should be your name, student number, and 4-character CS account name, with each on a separate line, like:
     John Doe
     12345678
     a0b1
   • The statement "I have read and understood the plagiarism policies at http://www.ugrad.cs.ubc.ca/~cs213/winter12t1/cheat.html" Of course, make sure that's true!
   • Any additional assumptions or comments you would like to make. Following the academic conduct guidelines, if you discussed the assignment in detail with anybody besides the instructor or TAs, say so explicitly and list their names here.
2. a3_1.s containing your solution for a3_1.c
3. a3_2.s containing your solution for a3_2.c
4. a3_3.s containing your solution for a3_3.c
5. a3_4.c containing your solution for a3_4.s (do not hand in the provided a3_4.s!)

File Format Requirements

Refer to the section of the same name in the second assignment. Your a3_4.c should conform to the same requirements.

Snippet Descriptions

The 4 examples and snippets that you are to work on implement possibly useful and/or interesting algorithms. This section provides a brief description of each. Alternatively, try to figure out what they do by experimenting, before reading this section.

a3_ex1: In binary, multiplication of a single bit is equivalent to a logical AND operation. As SM213 does not have a multiply instruction, this snippet shows how it can be done in at most 32 shift-and-add steps. Works with positive and negative numbers. See here for more information.

a3_ex2: The extremely simple but inefficient Bubble sort sorting algorithm.

a3_ex3: Similar to the first example, this shows how to compute an integer square root using a shift-and-subtract algorithm.

a3_ex4: The Euclidean algorithm, applied to finding the greatest common divisor of all the elements in an array.

The following are the algorithms that you will implement; it may be beneficial to become familiar with them so you can test your implementation.

a3_1: A common job-interview question is to implement this algorithm (although not in Asm), to reverse the elements of an array.

a3_2: Simple iterative method to compute the n^th Fibonacci number.

a3_3: Calculate the sine and cosine of an angle (specified in radians) using the CORDIC algorithm. Note that it uses only shifting and adding, with a (provided) lookup table, and is the same algorithm common handheld scientific calculators use. The inputs and outputs are scaled by a factor of 2³⁰ = 1073741824 to allow fractions so that e.g. 1 -> 1073741824 (0x40000000), 0.75 -> 805306368 (0x30000000), π/4 (45°) ≈ 0.7854 -> 0x3243f6a8, etc. When implemented on SM213, it is accurate to at least 7 significant digits of precision.

a3_4: Description omitted deliberately, for you to think about as you attempt to derive the corresponding HLL code for it.