CPSC 213: Assignment 3

Due Mon Oct 1 2012, 6pm


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:


Provided Materials

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
  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 nth 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 230 = 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.

Last modified 2012-09-21 02:21