Assignment 9, Solutions

Part of the homework for 22C:60 (CS:2630), Spring 2012
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Background: Here is a recursive expression of the "Russian Peasant" multiplication algorithm:

   int times( int a, int b ) {
      if (a != 0) { /* nontrivial case */
         if (a & 1) { /* a is odd */
            a = times( a >> 1, b << 1 ) + b;
         } else { /* a is even */
            a = times( a >> 1, b << 1 );
         }
      }
      return a;
   }

A Problem: Translate this to a SMAL Hawk subroutine, preserving as much of the control structure of the original as possible, and documenting it with comments that clearly reflect the original code wherever that is possible. You will be graded on how easy your code is to read as well as on its correctness. (0.6 points)

          SUBTITLE "times, recursive version"
; activation record format
;RETAD  =       0
B       =       4
ARSIZE  =       8

TIMES:  ; expects R3 = a -- the multiplier
        ;         R4 = b -- the multiplicand
        STORES  R1,R2
        TESTR   R3
        BZS     TIMEX           ; if (a != 0) {
        BITTST  R3,0
        BBR     TIMELS          ;   if (a & 1) { -- a is odd
        STORE   R4,R2,B         ;     -- save b
        SR      R3,1            ;     -- parameter a >> 1
        SR      R4,1            ;     -- parameter b << 1
        ADDI    R2,R2,ARSIZE
        JSR     R1,TIMES        ;     a = times( a >> 1, b << 1 )
        ADDI    R2,R2,-ARSIZE
        LOAD    R4,R2,B
        ADD     R3,R3,R4        ;     a = a + b
        BR      TIMEND
TIMELS:                         ;   } else {
        SR      R3,1            ;     -- parameter a >> 1
        SR      R4,1            ;     -- parameter b << 1
        ADDI    R2,R2,ARSIZE
        JSR     R1,TIMES        ;     a = times( a >> 1, b << 1 )
        ADDI    R2,R2,-ARSIZE
TIMEND:                         ;   }
TIMEX:                          ; }
        LOADS   R1,R2
        JUMPS   R1              ; return a

Background: Objects of class point have three fields, x — the x coordinate of the point y — the y coordinate of the point ch — the character to use to plot that point.
If p is the handle for a point object (that is, a pointer to the object), the method call p.setpoint(1,2,'o') sets the attributes p.x to 1, p.y to 2, p.ch to 'o'.
the method call p.plotpoint() causes p.ch to be plotted on the screen at coordinates p.x, p.y.
Assume that the point class is not polymorphic, so there is only one implementation of each method, and therefore, setpoint() and pointplot() are implemented, in assembly code, as simple subroutines.
a) (0.6 points) Given that R3 is the address of the point object p, you want to be able to write, for example, LOAD R4,R3,X in order to load R4 with the contents of the p.x. Give appropriate SMAL definitions of X, Y, CH, and POINTSIZE, suitable for inclusion in the header file point.h that defines the SMAL interface to the point class.
```
; fields of a point object
X       =       0
Y       =       4
CH      =       8
POINTSIZE=      12
```
An aside: If you want to hide the internal structure of point objects from their users, the only definition you would put in point.h would be POINTSIZE while the others would only be defined in point.a. Of course, point.h also needs to include EXT SETPOINT and EXT PLOTPOINT, but those lines were not required by the assignment for this part.
b) Suppose you needed a temporary object of class point as a local variable in a subroutine. Prior to discovering you needed this, your activaiton record declarations looked like this:
```
;RETAD  =       0
COUNTER =       4
ARSIZE  =       8
```
Modify this code so that the activation record includes a field named MYPOINT of size POINTSIZE (as defined in part a). Note that the storage for the object should be directly included in the activation redord, without any use of handles, pointers or other complexity. (0.6 points)
```
;RETAD  =       0
COUNTER =       4
ARSIZE  =       8

MYPOINT =       ARSIZE
ARSIZE  =       ARSIZE+POINTSIZE
```
c) Assume all of the definitions from parts a, b and c, and write code for inclusion in your subroutine that is the SMAL Hawk equivalent of mypoint.setpoint(1,2,'o'). (0.6 points)
```
        LEA     R3,R2,MYPOINT   ; -- parameter, handle for mypoint
        LIS     R4,1            ; -- parameter 1
        LIS     R5,2            ; -- parameter 2
        LIS     R6,'o'          ; -- parameter 'o'
        ADDI    R2,R2,ARSIZE
        LIL     R1,SETPOINT
        JSRS    R1,R1           ; mypoint.setpoint(1,2,'o')
        ADDI    R2,R2,-ARSIZE
```
d) Write code that belongs inside point.a for the SMAL Hawk subroutine that implements the setpoint method. You may assume that the appropriate definitions from point.h are available. (0.6 points)
```
INT     SETPOINT
SETPOINT:       ; given R3 = object handle
                ;       R4 = x coordinate
                ;       R5 = y coordinate
                ;       R6 = ch, a character
        STORE   R4,R3,X         ; object.x = x
        STORE   R5,R3,Y         ; object.y = y
        STORE   R6,R3,CH        ; object.ch = ch
        JUMPS   R1      ; return
```
An aside: It is interesting to note that the body of SETPOINT is smaller than the code in part c that calls it. This is an example where the smart optimization would be to substitute the code of the method body in place of the call -- but as usual, do this last, after you're sure that nobody will ever need to change the definition or behavior of the point class.