Assignment 9, due April 3Solutions
Part of
the homework for CS:2630, Spring 2015
|
- 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: R3–R4 — 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
LOADS R1,R2
JUMPS R1
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
LOADS R3,R1
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 PUTCHARTo 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
- 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 ADDI R2,R2,ARSIZE LOADS R1,R3 ; -- get pointer to object's descriptor LOAD R1,R1,WIDTH ; -- get pointer to the width() method JSRS R1,R1 ; -- rootwindow.width() ADDI R2,R2,-ARSIZE SR R3,1 ADDSI R3,-5 MOVE R8,R3 ; x = rootwindow.width()/2 - 5 LIL R3,ROOTWINDOW ; -- object ADDI R2,R2,ARSIZE LOADS R1,R3 LOAD R1,R1,HEIGHT JSRS R1,R1 ; -- rootwindow.height() ADDI R2,R2,-ARSIZE 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 ADDI R2,R2,ARSIZE LOADS R1,R3 LOAD R1,R1,NEWWIN JSRS R1,R1 ; -- rootwindow.newwin( x, y, 11, 1 ) ADDI R2,R2,-ARSIZE MOVE R8,R3 ; w = rootwindow.newwin( x, y, 11, 1 ) MOVE R3,R8 ; -- object w LIS R4,0 ; -- param LIS R5,0 ; -- param ADDI R2,R2,ARSIZE LOADS R1,R3 LOAD R1,R1,SETAT JSRS R1,R1 ; w.setat( 0, 0 ) ADDI R2,R2,-ARSIZE MOVE R3,R8 ; -- object w LEA R4,HELLO ; -- param ADDI R2,R2,ARSIZE LOADS R1,R3 LOAD R1,R1,PUTS JSRS R1,R1 ; w.puts( "Hello World" ) ADDI R2,R2,-ARSIZE ... HELLO: ASCII "Hello World",0Here 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 ADDSI R3,-5 MOVE R8,R3 ; x = rootwindow.width()/2 - 5 LIL R3,ROOTWINDOW ; -- object LOADS R1,R3 LOAD R1,R1,HEIGHT 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 LOADS R1,R3 LOAD R1,R1,NEWWIN 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 LOADS R1,R3 LOAD R1,R1,SETAT JSRS R1,R1 ; w.setat( 0, 0 ) MOVE R3,R8 ; -- object w LEA R4,HELLO ; -- param LOADS R1,R3 LOAD R1,R1,PUTS JSRS R1,R1 ; w.puts( "Hello World" ) ADDI R2,R2,-ARSIZE ; -- do this just once ... HELLO: ASCII "Hello World",0