CPSC 213: Assignment 4

Due Tue Oct 9 2012, 6pm

Goal

Building upon the previous assignments, this assignment extends the HLL constructs that you will be required to understand how to implement in Asm to include structures and procedures with parameters and local variables. In addition, in a similar fashion to the previous assignment, you will also practice decompiling from machine instructions HLL statements that use these new constructs.

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 structure accesses, procedure calls, procedures with parameters and local variables. 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 two code snippets, and produce a C version of the last two (supplied as a .s file.) For the first snippet, some of the functions have been provided for you; you will only need to fill in the body of the functions marked with "**** FOR YOU TO COMPLETE ****", following the suggested stack layout. When writing your solutions, refer to the provided examples and keep in mind the following points:

Hints

Provided Materials

Handing In

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

  1. README.txt that contains
  2. a4_1.s containing your solution for a4_1.c
  3. a4_2.s containing your solution for a4_2.c
  4. a4_3.c containing your solution for a4_3.s
  5. a3_4.c containing your solution for a4_4.s

File Format Requirements

Refer to the section of the same name in the second assignment. Your a4_3.c and a4_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.

a4_ex1: The Quicksort sorting algorithm.

a4_ex2: Traversing a linked list and performing a simple operation on each node of it.

a4_ex3: Traversing a binary tree in preorder, inorder, and postorder sequences. The contents of each node are added to an array.

a4_ex4: Searching a binary search tree implemented using array indices instead of pointers (instead of left and right children fields of each node being addresses, they are indices into the array, with -1 indicating there is no subtree.)

a4_1: A simple (and slow) Sudoku solver.

a4_2: Evaluating an arithmetic expression represented as a binary tree stored in "parallel array" format.

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

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-29 18:15