TITLE "MP4 by Douglas Jones" ; Plot the largest H-tree that will fit on the screen, ; but with a 1/3 probability of printing any particular subtree ; Based on the reference solution dated Oct. 17, 2011 ; with code added to generate random numbers and prune the tree USE "hawk.h" USE "monitor.h" ;RETAD = 0 H = 4 W = 8 ARSIZE = 12 INT MAIN S MAIN MAIN: ; executable code begins here ; expects R3 = w, the screen width ; expects R4 = h, the screen height STORES R1,R2 STORE R3,R2,W STORE R4,R2,H ADDI R2,R2,ARSIZE JSR R1,FINDMAX ; order = findmax(w,h) ADDI R2,R2,-ARSIZE LOAD R4,R2,W SRU R4,1 LOAD R5,R2,H ADDSI R5,-1 SRU R5,1 ADDI R2,R2,ARSIZE JSR R1,PLOTH ; ploth(order,w/2,(h-1)/2) ADDI R2,R2,-ARSIZE LOADS R1,R2 JUMPS R1 ; return to the monitor to stop! SUBTITLE "findmax - find max h-tree that fits on screen" FINDMAX: ; expects R3 = w, the screen width ; expects R4 = h, the screen height ; returns R3 = order CMP R3,R4 BGEU FMXEI1 ; if (w < h) { -- find minimum dimension MOVE R4,R3 ; h = w FMXEI1: ; } -- h is now controlling dimension ; -- setup for loop LIS R3,0 ; order = 0 -- order of H-tree LIS R5,0 ; r = 0 -- right diagonal dimension LIS R6,0 ; l = 0 -- left diagonal dimension FMXLP: ; do { ADDSI R3,1 ; order = order + 1 BITTST R3,0 BBS FMXODD ; if (order is even) { ADD R5,R5,R5 ADDSI R5,2 ; l = 2l + 2 BR FMXEI2 FMXODD: ; } else { -- order is odd ADD R6,R6,R6 ADDSI R6,2 ; r = 2r + 2 FMXEI2: ; } ADD R7,R6,R5 CMP R7,R4 BLEU FMXLP ; } while ((r + l) < h) ADDSI R3,-1 ; order = order - 1 JUMPS R1 ; return order SUBTITLE "ploth - plot h-tree" ; activation record ;RETAD = 0 ARSIZE = 4 PLOTH: ; expects R3 = order of the tree to plot ; expects (R4,R5) = (x,y) coordinates of the center point STORES R1,R2 TESTR R1 BZS PLHEI1 ; if (order > 0) { ADDI R7,R3,-1 SRU R7,1 ; o = (order-1)/2; LIS R6,1 ; d = 1 TESTR R7 BZS PLHEI2 ; if (o != 0) { PLHLP: ; do { ADD R6,R6,R6 ; d = 2d ADDSI R7,-1 ; o = o - 1 BZR PLHLP ; } while (o != 0) PLHEI2: ; } ; -- now d = 2**((order-1)/2) BITTST R3,0 BBS PLHODD ; if (order is even) { MOVE R3,R6 ADDI R2,R2,ARSIZE JSR R1,PLOTHE ; plothe(d,x,y) ADDI R2,R2,-ARSIZE BR PLHEI3 PLHODD: ; } else { -- else order is odd MOVE R3,R6 ADDI R2,R2,ARSIZE JSR R1,PLOTHO ; plotho(d,x,y) ADDI R2,R2,-ARSIZE PLHEI3: ; } PLHEI1: ; } LOADS R1,R2 JUMPS R1 ; return SUBTITLE "plothe - plot even h-tree" ; activation record ;RETAD = 0 SAVER8 = 4 ; save locations for R8-R11 SAVER9 = 8 SAVER10 = 12 ARSIZE = 16 PLOTHE: ; expects R3 = d, halflength of diagonal of tree to plot ; expects (R4,R5) = (x,y) coordinates of the center point STORES R1,R2 STORE R8,R2,SAVER8 STORE R9,R2,SAVER9 STORE R10,R2,SAVER10 ; -- save registers MOVE R8,R3 ; d = d MOVE R9,R4 ; x = x MOVE R10,R5 ; y = y -- moved to new locations TESTR R3 BZS PLEEI ; if (d != 0) ADDI R2,R2,ARSIZE JSR R1,RANDOM JSR R1,MOD3 ADDI R2,R2,-ARSIZE TESTR R3 BZS PLEEI ; and (random() mod 3 != 0) { MOVE R3,R8 MOVE R4,R9 MOVE R5,R10 ; -- recover d,x,y ADD R4,R4,R3 ; -- plot my upper right child SUB R5,R5,R3 ADDI R2,R2,ARSIZE JSR R1,PLOTHO ; plotho(d,x+d,y-d) ADDI R2,R2,-ARSIZE MOVE R3,R8 MOVE R4,R9 MOVE R5,R10 ; -- recover d,x,y SUB R4,R4,R3 ; -- plot my lower left child ADD R5,R5,R3 ADDI R2,R2,ARSIZE JSR R1,PLOTHO ; plotho(d,x-d,y+d) ADDI R2,R2,-ARSIZE PLELP: ; do { -- plot diagonal twixt children ADD R3,R9,R8 ADDSI R3,-1 SUB R4,R10,R8 ADDSI R4,1 LIS R5,"/" ADDI R2,R2,ARSIZE JSR R1,ATPLOT ; atplot(x+d-1,y-d+1,'/') ADDI R2,R2,-ARSIZE SUB R3,R9,R8 ADD R4,R10,R8 LIS R5,"/" ADDI R2,R2,ARSIZE JSR R1,ATPLOT ; atplot(x-d,y+d,'/') ADDI R2,R2,-ARSIZE ADDSI R8,-1 ; d = d - 1; BZR PLELP ; } while (d != 0 PLEEI: ; } LOAD R8,R2,SAVER8 LOAD R9,R2,SAVER9 LOAD R10,R2,SAVER10 ; -- restore registers LOADS R1,R2 JUMPS R1 ; return SUBTITLE "plotho - plot odd h-tree" ; activation record ;RETAD = 0 SAVER8 = 4 ; save locations for R8-R10 SAVER9 = 8 SAVER10 = 12 ARSIZE = 16 PLOTHO: ; expects R3 = d, halflength of diagonal ; expects (R4,R5) = (x,y) coordinates of the center point STORES R1,R2 STORE R8,R2,SAVER8 STORE R9,R2,SAVER9 STORE R10,R2,SAVER10 ; -- save registers MOVE R8,R3 ; d = d MOVE R9,R4 ; x = x MOVE R10,R5 ; y = y -- moved to new locations ADDI R2,R2,ARSIZE JSR R1,RANDOM JSR R1,MOD3 ADDI R2,R2,-ARSIZE TESTR R3 BZS PLOEI ; if (random() mod 3 != 0) { MOVE R3,R8 MOVE R4,R9 MOVE R5,R10 ; -- recover order,x,y,d SUB R4,R4,R3 ; -- plot my upper left child SUB R5,R5,R3 SR R3,1 ADDI R2,R2,ARSIZE JSR R1,PLOTHE ; plothe(d/2,x-d,y-d) ADDI R2,R2,-ARSIZE MOVE R3,R8 MOVE R4,R9 MOVE R5,R10 ; -- recover order,x,y,d ADD R4,R4,R3 ; -- plot my lower left child ADD R5,R5,R3 SR R3,1 ADDI R2,R2,ARSIZE JSR R1,PLOTHE ; plothe(d/2,x+d,y+d) ADDI R2,R2,-ARSIZE PLOLP: ; do { -- plot diagonal twixt children SUB R3,R9,R8 SUB R4,R10,R8 ADDSI R4,1 LIS R5,"\" ADDI R2,R2,ARSIZE JSR R1,ATPLOT ; atplot(x-d,y-d+1,'\') ADDI R2,R2,-ARSIZE ADD R3,R9,R8 ADDSI R3,-1 ADD R4,R10,R8 LIS R5,"\" ADDI R2,R2,ARSIZE JSR R1,ATPLOT ; atplot(x+d-1,y+d,'\') ADDI R2,R2,-ARSIZE ADDSI R8,-1 ; d = d - 1; BZR PLOLP ; } while (d != 0) PLOEI: ; } LOAD R8,R2,SAVER8 LOAD R9,R2,SAVER9 LOAD R10,R2,SAVER10 ; restore registers LOADS R1,R2 JUMPS R1 ; return SUBTITLE "atplot - at a location plot a character" ; activation record ;RETAD = 0 CH = 4 ; character to plot ARSIZE = 8 ATPLOT: ; expects R3,R4 = x,y location ; expects R5 = ch, the character STORES R1,R2 STORE R5,R2,CH ADDI R2,R2,ARSIZE LIL R1,PUTAT JSRS R1,R1 ; putat(x,y) ADDI R2,R2,-ARSIZE LOAD R3,R2,CH ADDI R2,R2,ARSIZE LIL R1,PUTCHAR JSRS R1,R1 ; putchar(ch) ADDI R2,R2,-ARSIZE LOADS R1,R2 JUMPS R1 ; return SUBTITLE "random -- pseudorandom number generator" ; algorithm: seed = (seed * 16807) mod (2**31-1) ; note: 16807 = #41A7 = 100 0001 1010 0111 ; note: 2**31-1 = #7FFFFFFF ; seed always remains in the range 1 to #7FFFFFFE COMMON SEED,4 T = . ; we will initialize SEED below . = SEED ; to any value in the legal range W 87654321 . = T RANDOM: ; returns R3 = a pesudorandom (and quite likely very large) integer ; uses [R3,R4] = seed, 64-bit registers (least sig half first) ; uses [R5,R6] = acc, same format ; uses R7 as a pointer to seed LIL R7,SEED LOADS R3,R7 LIS R4,0 ; -- seed loaded and widened to 64 bits ; the following does acc = seed * 16807 by brute force (64-bit product) MOVE R5,R3 MOVE R6,R4 ; [R5,R6]: acc = 1 * seed SL R3,1 ADDC R4,R4 ; seed = seed * 2 ADD R5,R5,R3 ADDC R6,R4 ; acc = 11 * seed SL R3,1 ADDC R4,R4 ; seed = seed * 2 ADD R5,R5,R3 ADDC R6,R4 ; acc = 111 * seed SL R3,1 ADDC R4,R4 ; seed = seed * 2 SL R3,1 ADDC R4,R4 ; seed = seed * 2 SL R3,1 ADDC R4,R4 ; seed = seed * 2 ADD R5,R5,R3 ADDC R6,R4 ; acc = 100111 * seed SL R3,1 ADDC R4,R4 ; seed = seed * 2 SL R3,1 ADDC R4,R4 ; seed = seed * 2 ADD R5,R5,R3 ADDC R6,R4 ; acc = 10100111 * seed SL R3,1 ADDC R4,R4 ; seed = seed * 2 ADD R5,R5,R3 ADDC R6,R4 ; acc = 110100111 * seed SL R3,1 ADDC R4,R4 ; seed = seed * 2 SL R3,1 ADDC R4,R4 ; seed = seed * 2 SL R3,1 ADDC R4,R4 ; seed = seed * 2 SL R3,1 ADDC R4,R4 ; seed = seed * 2 SL R3,1 ADDC R4,R4 ; seed = seed * 2 SL R3,1 ADDC R4,R4 ; seed = seed * 2 ADD R5,R5,R3 ADDC R6,R4 ; acc = 100000110100111 * seed ; the following does seed = acc mod 2**31-1 ; NOTE: using base 2**31, this is computed as ; seed = sum of base 2**31 digits in acc (there are only 2 digits) MOVE R3,R5 SL R3,1 SRU R3,1 ; seed = low 31 bits of acc SL R5,1 ADDC R6,R6 ADD R3,R3,R6; seed = seed + next higher 31 bits of acc ; -- note: the sum fits in 32 bits LIW R4,#7FFFFFFF CMP R3,R4 BLTU RANDOK ; if (seed >= 2**32-1) { SUB R3,R3,R4; seed = seed - 2**32-1 RANDOK: ; } STORES R3,R7 ; -- put seed back JUMPS R1 ; return seed SUBTITLE "mod3 -- compute the remainder after divide by 3" ; algorithm lifted from solution to homework 9 MOD3: ; given x in R3, returns x mod 3 in R3 ; uses R4, R5 as tempories y and z LIW R5,#33333333 MOVE R4,R3 SRU R4,2 AND R4,R5 ; y = (x >> 2) & #33333333 AND R3,R5 ; x = x & #33333333 ADD R3,R3,R4 ; x = x + y; ; -- each 4-bit chunk sums 2 base-4 digits ; -- the maximum value of each chunk is 6 LIW R5,#07070707 MOVE R4,R3 SRU R4,4 AND R4,R5 ; y = (x >> 4) & #07070707 AND R3,R5 ; x = x & #07070707 ADD R3,R3,R4 ; x = x + y; ; -- each 8-bit chunk sums 4 base-4 digits ; -- the maximum value of each chunk is 12 LIW R5,#000F000F MOVE R4,R3 SRU R4,8 AND R4,R5 ; y = (x >> 4) & #000F000F AND R3,R5 ; x = x & #000F000F ADD R3,R3,R4 ; x = x + y; ; -- each 16-bit chunk sums 8 base-4 digits ; -- the maximum value of each chunk is 24 MOVE R4,R3 SRU R4,16 ; y = (x >> 16) TRUNC R3,5 ; x = x & #0000001F ADD R3,R3,R4 ; x = x + y; ; -- x sums 16 base-4 digits ; -- the maximum value is 48 (16 digits times 3) ; -- this has no more than 3 base-4 digits MOVE R4,R3 SRU R4,2 TRUNC R4,2 ; y = (x >> 2) & #00000003 MOVE R5,R3 SRU R5,4 TRUNC R5,2 ; z = (x >> 4) & #00000003 TRUNC R3,2 ; x = x & #00000003 ADD R3,R3,R4 ADD R3,R3,R5 ; x = x + y + z ; -- x sums the 3 base-4 digits of the previous sum ; -- the maximum value is now 8 (< 3 digits times 3) ; -- this has no more than 2 base-4 digits MOVE R4,R3 SRU R4,2 TRUNC R4,2 ; y = (x >> 2) & #00000003 TRUNC R3,2 ; x = x & #00000003 ADD R3,R3,R5 ; x = x + y ; -- x sums the 2 base-4 digits of the previous sum ; -- the maximum value is now 4 (< 2 digits times 3) CMPI R3,3 BLT MOD3QT ; if (x >= 3) { ADDSI R3,-3 ; x = x - 3; MOD3QT: ; } JUMPS R1 ; return x -- the original value mod 3! END