# Assignment 9, due April 3

## Solutions

1. Background: Suppose you have the following two routines in a math library:
URECIP — fixed point unsigned reciprocal
Parameter: R3 — an unsigned integer
Return value: R3 — an unsigned fixed point fraction
Side effects: May disturb R4 to R7
The return value has its point to the left of bit 31, so 1/2, for example, is represented as 8000000016.
LUMUL — long unsigned multiply
Parameter: R3, R4 — unsigned integers to multiply
Return value: R3R4 — the 64-bit unsigned product
Side effects: May disturb R5 to R7
R3 is the least significant word of the product, R4 is the most significant word.

One way to compute the quotient a/b is to compute a × 1/b.

A problem: Write a divide subroutine routine using the above that conforms to the following specification: (1 point)

UDIV — unsigned divide
Parameter: R3 — dividend, R4 — divisor
Return value: R3 — the quotient
Side effects: May disturb R4 to R7
This code does not compute the remainder, and the quotient will be truncated to the next lower integer.
```; activation record format for UDIV
;RA     =       0       ; the return address
IDEND   =       4       ; the dividend
ARSIZE  =       8

UDIV:   ; given R3 = dividend
;       R4 = divisor
STORES  R1,R2
ADDSI   R2,ARSIZE       ; -- activation record is small
STORE   R3,IDEND-ARSIZE ; -- save the dividend for later
MOVE    R3,R4
JSR     R1,URECIP       ; -- parameter = 1/divisor, a 32-bit fraction
LOAD    R4,IDEND-ARSIZE ; -- parameter = dividend
JSR     R1,LUMUL        ; long_result = lumul(dividend, 1/divisor)
MOVE    R3,R4           ; return long_result >> 32
ADDSI   R2,-ARSIZE      ;  activation record is small
JUMPS   R1
```

2. A problem: To call an external subroutine called SUBR on the Hawk, you write:
```        EXT     SUBR
LIL     R1,SUBR
JSRS    R1,R1
```

To get the value of a one-word global variable called GLOB on the Hawk, you might write:

```        COMMON  GLOB,4
LIL     R1,GLOB
```

If you have a Sparrowhawk (see Chapter 16 of the Hawk manual) there are no 32-bit instructions. Section 16.2 suggests that you can rewrite an LIL as an LIS followed by two ORIS instructions.

a) This does not work for external symbols such as SUBR or GLOB from the above examples. Try them, see what happens, and then explain why the advice in Section 16.2 fails in this context. (0.5 points)

Note: The Hawk manual is correct in asserting that an LIL can, in principle, be used. You may need to review Sections 4.1 and 4.3 of the SMAL manual (about external symbols) as well as Section 2.3 in order to see what the problem is.

Here's what happens when you try it:

```+00000000: D1 +00                7          LIS     R1,PUTCHAR>>16
misuse of relocation                                          ==
+00000002: C1 +00                8          ORIS    R1,PUTCHAR>>8 & #FF
misuse of relocation                                          ==  =
+00000004: C1 +00                9          ORIS    R1,PUTCHAR    & #FF
misuse of relocation                                              =
```

Why? Sections 4.1 and 4.2 of the SMAL manual say that symbols declared with EXT and COMMON serve as new relocation bases. That is, they are relocatable. The parts of Section 2.3 of the SMAL manual that discuss the shift and logical operators say things like "Both operands must be absolute values; a "misuse of relocation" error will result if relocatable values are used."

b) (0.5 points) How can you use a PC-relative LOAD instead of an LIL to load the value of SUBR or GLOB into a register. This is step one along the road to converting Hawk code to run on the Sparrowhawk. Step two is to replace the LOAD instruction, following the suggestion in Section 16.2 of the Hawk manual (this time, it will work).

Note: You may need to review Chapter 5 of the notes. Note also that the Sparrowhawk has no LOAD instruction, only LOADS, but that the suggestion in Section 16.2 of the Hawk manual works here where it failed for part a.

The following would satisfy the assignment:

```        LOAD    R1,PPUTCH       ; in place of LIL R1,PUTCHAR

ALIGN   4               ; somewhere where it won't be executed
PPUTCH: W       PUTCHAR         ; pointer to PUTCHAR
```

To complete the exercise (not implied as part of the assignment) you could rewrite the LOAD as follows:

```PPUTDSP =       PPUTCH-(.+6)    ; start of code to fake LOAD R1,PPUTCH
LIS     R1,PPUTDSP >> 8
ORIS    R1,PPUTDSP & #FF; -- compute displacement
PLUS    R1,R0           ; -- compute PC-relative address
LOADS   R1,R1           ; end of code to fake LOAD R1,PPUTCH
```

3. Background: The Hawk monitor is awful. Suppose we wanted to design a better monitor that supported output windows. There would be one global window object provided by the new monitor, call it ROOTWINDOW. Note that the common block named ROOTWINDOW holds the object, it does not hold a variable that points to the object. The following methods would apply to any window object w:
w.height() — returns the height of window w.
w.width() — returns the width of window w.
w.setat(x,y) — set the coordinates for output to w.
Each window remembers a current location for plotting data in that window.
w.putchar(c) — plot the character c in window w
Ploting a character updates the current locaiton in the window.
Plotting wraps to the next line if you reach the margin of the window.
w.puts(s) — Equivalent to w.putchar for each character in s.
w.newwin(x,y,h,w) — returns the handle for a new window.
The parameters x and y give the upper left corner of the window;
h and w specify its height and width.

Assume we are using the compact approach to polymorphic object representation, so the first field of each object is the pointer to the class descriptor for the object, and the fields of the descriptor are pointers to the corresponding methods. This class must be polymorphic because plotting on the base window references the display hardware, while plotting on a sub-window references a field of the window representating that sub-window.

Assume that the identifiers SETAT, NEWWIN etc are defined displacements into the method table.

A problem: Write SMAL Hawk code to write "Hello World" in a new window that is just large enough for that string (you can count the characters), where that window is centered in the root window. (1 point)

First, thinking in a high level language perspective, we need:

```rw = ROOTWINDOW
w = rw.newwin( rw.width()/2 - 5, rw.height()/2, 11, 1 )
w.setat( 0, 0 )
w.puts( "Hello World" )
```

Second, we follow the boilerplate rules for calling methods of polymorphic objects for the 5 distinct calls above. The following code assumes that R8 and R9 are available as temporary storage locations. Aside from that, it is entirely unoptimized. Because there is so much boilerplate here, it is long, but there are many repeated patterns, so the information content is rather low.

```        LIL     R3,ROOTWINDOW   ; -- object = ROOTWINDOW
LOADS   R1,R3           ; -- get pointer to object's descriptor
LOAD    R1,R1,WIDTH     ; -- get pointer to the width() method
JSRS    R1,R1           ; -- rootwindow.width()
SR      R3,1
MOVE    R8,R3           ; x = rootwindow.width()/2 - 5

LIL     R3,ROOTWINDOW   ; -- object
JSRS    R1,R1           ; -- rootwindow.height()
SR      R3,1
MOVE    R9,R3           ; y = rootwindow.height()/2

LIL     R3,ROOTWINDOW   ; -- object
MOVE    R4,R8           ; -- param x
MOVE    R5,R9           ; -- param y
LIS     R6,11           ; -- param width
LIS     R7,1            ; -- param height
JSRS    R1,R1           ; -- rootwindow.newwin( x, y, 11, 1 )
MOVE    R8,R3           ; w = rootwindow.newwin( x, y, 11, 1 )

MOVE    R3,R8           ; -- object w
LIS     R4,0            ; -- param
LIS     R5,0            ; -- param
JSRS    R1,R1           ; w.setat( 0, 0 )

MOVE    R3,R8           ; -- object w
LEA     R4,HELLO        ; -- param
JSRS    R1,R1           ; w.puts( "Hello World" )

...

HELLO:  ASCII   "Hello World",0
```

Here is a more optimal version of the same code, harder to read and harder to recognize boilerplate patterns in

```        ADDI    R2,R2,ARSIZE    ; -- do this just once

LIL     R3,ROOTWINDOW   ; -- object = ROOTWINDOW
LOADS   R1,R3           ; -- get pointer to object's descriptor
LOAD    R1,R1,WIDTH     ; -- get pointer to the width() method
JSRS    R1,R1           ; -- rootwindow.width()
SR      R3,1
MOVE    R8,R3           ; x = rootwindow.width()/2 - 5

LIL     R3,ROOTWINDOW   ; -- object
JSRS    R1,R1           ; -- rootwindow.height()
SR      R3,1            ; y = rootwindow.height()/2

MOVE    R4,R8           ; -- param x
MOVE    R5,R3           ; -- param y
LIL     R3,ROOTWINDOW   ; -- object
LIS     R6,11           ; -- param width
LIS     R7,1            ; -- param height
JSRS    R1,R1           ; -- rootwindow.newwin( x, y, 11, 1 )
MOVE    R8,R3           ; w = rootwindow.newwin( x, y, 11, 1 )

; -- object w (R3 already points there)
LIS     R4,0            ; -- param
LIS     R5,0            ; -- param
JSRS    R1,R1           ; w.setat( 0, 0 )

MOVE    R3,R8           ; -- object w
LEA     R4,HELLO        ; -- param