Homework 2

Due Monday, Oct. 22

Note: In this and future assignments, do not use any language construct (e.g. machine instruction types) not covered in our course by the due date.

Here you will do further work with the compression technique (run-length encoding) in Homework 1.

This time we will assume that the uncompressed array is one-dimensional, but still consists of 1s and 0s. We will again assume that the array has at least one nonzero element.

You may have heard the terms getters and setters, which are class methods to read and write to array elements. Say you have an array x as a member variable of some object o. Then instead of simply reading element 5 directly as the expression o.x[5], you would read it via a method call o.xgetter(5). The motivation is that this serves the encapsulation aspect of object-oriented programming philosophy.

Personally (note that these things are a matter of taste, and sometimes of hot debate), I consider the getter/setter concept to be a silly redundancy that overly complicates one's code. However in our case here of compressed arrays, it does make sense. So, in this assignment, you'll be writing Intel Linux assembly code for getter and setter subroutines for our RLE application.

• The compressed array (CA) is in run-length encoded form; e.g. 2 1 5 3 11 2 means one 1 starting at x[2] (0-based indexing), three 1s starting at x[5], and two 1s starting at x[11].
• The lengths of the uncompressed array (UA) and the CA are stored in the two words immediately preceding the CA.

readsa():

• The "getter."
• Assumes the caller has placed in EAX the address of an array, whose components (one per word) are:
  • the address of the length of UA, and
  • the index of the element of the UA to be read.

• Places the requested array element in EBP before returning.

writea():

• The "setter."
• Arguments are the same as for readsa(), except that the array pointed to by EAX has three elements, the last of which is the value to be written.
• There is no return value.
• Note that the write may change a lot of the CA.

Notes:

• Both readsa() and writesa() are functions/subroutines, so your test code must use the CALL instruction (and the TA's test code will do so).
• Make sure you truly master Chapter 3 through Section 3.10 before beginning to code. Then walk through a couple of numerical examples to make sure you understand what the code is supposed to do.
• Do not uncompress the array.
• Make a reasonable effort to avoid memory accesses, especially in loops.
• Good debugging skills--including deft use of a debugging TOOL--will be crucial.