home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS - Coast to Coast / simteldosarchivecoasttocoast2.iso / ddjmag / ddj8611.zip / MORTON.NOV < prev    next >
Text File  |  1986-12-01  |  26KB  |  766 lines
  1. ;
  2. ;  procedure DissBits (srcB, destB: bitMap; srcR, dstR: rect); external;
  3. ;
  4. ; mike morton
  5. ; release: 30 june 1986, version 5.3
  6. ; this version is formatted for the Lisa Workshop assembler
  7. ;
  8. ; differences from version 5.2:
  9. ;    extraneous code removed from bitwidth routine
  10. ;    introductory comments are much shorter
  11. ;
  12. ; **********************************************************************
  13. ; *     copyright 1984, 1985, 1986 by michael s. morton           *
  14. ; **********************************************************************
  15. ;
  16. ; DissBits is freeware.  you're welcome to copy it, use it in programs, and
  17. ; to modify it, as long as you leave my name in it.  i'd be interested in
  18. ; seeing your changes, especially if you find ways to make the central
  19. ; loops faster, or port it to other machines/languages.
  20. ;
  21. ; if, for some reason, you only have a hard copy of this and would like a
  22. ; source on a diskette, please contact:
  23. ;       robert hafer
  24. ;       the boston computer society
  25. ;       one center plaza
  26. ;       boston, mass.  02108
  27.  
  28. ;
  29. ; include files:
  30. ;       tlasm/graftypes -- definitions of "bitMap" and "rect"
  31. ;       tlasm/quickmacs -- macros for quickdraw calls (e.g., _hidecursor)
  32. ;
  33.  
  34. .nolist
  35. .include tlasm/graftypes
  36. .include tlasm/quickmacs
  37. .list
  38.  
  39. ;
  40. ; definitions of the "ours" record: this structure, of which there are
  41. ; two copies in our stack frame, is a sort of bitmap:
  42. ;
  43.  
  44. oRows   .equ    0        ; (word) number of last row (first is 0)
  45. oCols   .equ    oRows+2        ; (word) number of last column (first is 0)
  46. oLbits  .equ    oCols+2        ; (word) size of left margin within 1st byte
  47. oStride .equ    oLbits+2    ; (word) stride in memory from row to row
  48. oBase   .equ    oStride+2    ; (long) base address of bitmap
  49.  
  50. osize   .equ    oBase+4        ; size, in bytes, of "ours" record
  51.  
  52. ;
  53. ; stack frame elements:
  54. ;
  55.  
  56. srcOurs .equ    -osize        ; (osize) our view of source bits
  57. dstOurs .equ    srcOurs-osize    ; (osize) our view of target bits
  58.  
  59. sflast  .equ    dstOurs        ; relative address of last s.f. member
  60. sfsize  .equ    -sflast        ; size of s.f. for LINK (must be EVEN!)
  61. ;
  62. ;       parameter offsets from the stack frame pointer, A6:
  63. ;       last parameter is above return address and old s.f.
  64. ;
  65.  
  66. dRptr   .equ    4+4        ; ^destination rectangle
  67. sRptr   .equ    dRptr+4        ; ^source rectangle
  68. dBptr   .equ    sRptr+4        ; ^destination bitMap
  69. sBptr   .equ    dBptr+4        ; ^source bitMap
  70.  
  71. plast   .equ    sBptr+4        ; address just past last parameter
  72.  
  73. psize   .equ    plast-dRptr    ; size of parameters, in bytes
  74.  
  75. ;
  76. ; entrance: set up a stack frame, save some registers, hide the cursor.
  77. ;
  78.  
  79. .proc   dissBits        ; main entry point
  80.  
  81.     link    A6,#-sfsize    ; set up a stack frame
  82.     movem.l    D3-D7/A2-A5,-(SP)       ; save registers compiler may need
  83.     _hidecurs        ; don't let the cursor show for now
  84.  
  85. ;
  86. ; convert source and destination bitmaps and rectangles to a format we prefer.
  87. ; we won't look at these parameters after this.
  88. ;
  89.  
  90.     move.l    sBptr(A6),A0    ; point to source bitMap
  91.     move.l    sRptr(A6),A1    ; and source rectangle
  92.     lea    srcOurs(A6),A2    ; and our source structure
  93.     bsr    CONVERT        ; convert to our format
  94.  
  95.     move.l    dBptr(A6),A0    ; point to destination bitMap
  96.     move.l    dRptr(A6),A1    ; and rectangle
  97.     lea    dstOurs(A6),A2    ; and our structure
  98.     bsr    CONVERT        ; convert to our format
  99.  
  100. ;
  101. ; check that the rectangles match in size.
  102. ;
  103.     move.w    srcOurs+oRows(A6),D0     ; pick up the number of rows
  104.     cmp.w    dstOurs+oRows(A6),D0      ; same number of rows?
  105.     bne    ERROR        ; nope -- bag it
  106.  
  107.     move.w    srcOurs+oCols(A6),D0     ; check the number of columns
  108.     cmp.w    dstOurs+oCols(A6),D0      ; same number of columns, too?
  109.     bne    ERROR        ; that's a bozo no-no
  110.  
  111. ;
  112. ; figure the bit-width needed to span the columns, and the rows.
  113. ;
  114.  
  115.     move.w    srcOurs+oCols(A6),D0     ; get count of columns
  116.     ext.l    D0        ; make it a longword
  117.     bsr    LOG2        ; figure bit-width
  118.     move.w    D0,D1        ; set aside that result
  119.     beq    SMALL        ; too small?  wimp out and use copyBits
  120.  
  121.     move.w    srcOurs+oRows(A6),D0     ; get count of rows
  122.     ext.l    D0        ; make it a longword
  123.     bsr    LOG2        ; again, find the bit-width
  124.     tst.w    D0        ; is the result zero?
  125.     beq    SMALL        ; if so, our algorithm will screw up
  126.  
  127. ;
  128. ; set up various constants we'll need in the in the innermost loop
  129. ;
  130.  
  131.     move.l    #1,D5        ; set up...
  132.     lsl.l    D1,D5        ; ...the bit mask which is...
  133.     sub.l    #1,D5        ; ...bit-width (cols) 1's
  134.  
  135.     add.w    D1,D0        ; find total bit-width (rows plus columns)
  136.     lea    TABLE,A0    ; point to the table of XOR masks
  137.     moveq    #0,D3        ; clear out D3 before we fill the low byte
  138.     move.b    0(A0,D0),D3    ; grab the correct XOR mask in D3
  139.  
  140. ;
  141. ; table is saved compactly, since no mask is wider than a byte.
  142. ;  we have to unpack it so high-order bit of the D0-bit-wide field is on:
  143. ;
  144.  
  145. UNPACK  add.l    D3,D3        ; shift left by one
  146.     bpl.s    UNPACK        ; keep moving until top bit that's on is
  147.                 ; aligned at the top end
  148.  
  149.     rol.l    D0,D3        ; now swing the top D0 bits around to be
  150.                 ; bottom D0 bits, the mask
  151.     move.l    D3,D0        ; 1st sequence element is the mask itself
  152.  
  153. ;
  154. ; do all kinds of preparation:
  155. ;
  156.  
  157.     move.l    srcOurs+oBase(A6),D2     ; set up base ptr for source bits
  158.     lsl.l    #3,D2        ; make it into a bit address
  159.     move.l    D2,A0        ; put it where the fast loop will use it
  160.     move.w    srcOurs+oLbits(A6),D2    ; now pick up source left margin
  161.     ext.l    D2        ; make it a longword
  162.     add.l    D2,A0        ; make A0 useful for odd routine below
  163.  
  164.     move.l    dstOurs+oBase(A6),D2     ; set up base pointer for target
  165.     lsl.l    #3,D2        ; again, bit addressing works out faster
  166.     move.l    D2,A1        ; stuff it where we want it for the loop
  167.     move.w    dstOurs+oLbits(A6),D2    ; now pick up destination left margin
  168.     ext.l    D2        ; make it a longword
  169.     add.l    D2,A1        ; and make A1 useful, too
  170.  
  171.     move.w    srcOurs+oCols(A6),A2    ; pick up the often-used count
  172.                     ; of columns
  173.     move.w    srcOurs+oRows(A6),D2    ; and of rows
  174.     add.w    #1,D2        ; make row count one-too-high for compares
  175.     ext.l    D2        ; and make it a longword
  176.     lsl.l    D1,D2        ; slide it to line up w/rows part of D0
  177.     move.l    D2,A4        ; and save that somewhere useful
  178.  
  179.     move.w    D1,D2        ; put log2(columns) in a safe place (sigh)
  180.  
  181. ;
  182. ; try to reduce the amount we shift down D2.  this involves:
  183. ;    halving the strides as long as each is even, decrementing D2 as we go
  184. ;    masking the bottom bits off D4 when we extract the row count in the loop
  185. ;
  186. ; alas, can't always shift as little as we want.  for instance, if we don't
  187. ; shift down far enough, row count will be so high as to exceed a halfword,
  188. ; and the dread mulu instruction won't work (eats only word operands).  so,
  189. ; we have to have an extra check to take us out of the loop early.
  190. ;
  191.  
  192.     move.w    srcOurs+oStride(A6),D4   ; pick up source stride
  193.     move.w    dstOurs+oStride(A6),D7   ; and target stride
  194.     move.w    srcOurs+oRows(A6),D1     ; get row count for klugey check
  195.  
  196.     tst.w    D2            ; how's the bitcount?
  197.     beq.s    HALFDONE        ; skip out if already down to zero
  198.  
  199. HALFLOOP
  200.     btst    #0,D4        ; is this stride even?
  201.     bne.s    HALFDONE    ; nope -- our work here is done
  202.     btst    #0,D7        ; how about this one?
  203.     bne.s    HALFDONE    ; have to have both even
  204.  
  205.     lsl.w    #1,D1        ; can we keep max row number in a halfword?
  206.     bcs.s    HALFDONE    ; nope -- D2 mustn't get any smaller!
  207.  
  208.     lsr.w    #1,D4        ; halve each stride...
  209.     lsr.w    #1,D7        ; ...like this
  210.     sub.w    #1,D2        ; and remember not to shift down as far
  211.     bne.s    HALFLOOP    ; loop unless we're down to no shift at all
  212.  
  213. HALFDONE            ; no tacky platitudes, please
  214.     move.w    D4,srcOurs+oStride(A6)   ; put back source stride
  215.     move.w    D7,dstOurs+oStride(A6)   ; and target stride
  216.  
  217. ;
  218. ; make some stuff faster to access -- use the fact that (An) is faster
  219. ; to access than d(An).  this means we'll misuse our frame pointer, but
  220. ; don't worry -- we'll restore it before we use it again.
  221. ;
  222.  
  223.     move.w    srcOurs+oStride(A6),A5  ; make source stride faster
  224.                     ; to access, too
  225.     move.l    A6,-(SP)        ; save framitz pointer
  226.     move.w    dstOurs+oStride(A6),A6  ; pick up destination stride
  227.     move.l    #0,D6        ; we do only AND.w x,D6 -- but ADD.l D6,x
  228.  
  229.     clr.w    -(SP)        ; reserve room for function result
  230.     bsr    MULCHK        ; go see if strides are powers of two
  231.     tst.w    (SP)+        ; can we eliminate the horrible MULUs?
  232.     bne     NOMUL        ; yes!  hurray!
  233.  
  234. ;
  235. ; main loop: map the sequence element into rows and columns, check if it's
  236. ; in bounds and skip on if it's not, flip the appropriate bit, generate
  237. ; the next element in the sequence, and loop if the sequence isn't done.
  238. ;
  239.  
  240. ;
  241. ; check row bounds. note that we can check row before extracting it from
  242. ; D0, ignoring bits at bottom of D0 for the columns. to get these bits
  243. ; to be ignored, had to make A4 1-too-high before shifting up to align it.
  244. ;
  245.  
  246. LOOP                ; here for another time around
  247.     cmp.l    A4,D0        ; is row in bounds?
  248.     bge.s    NEXT        ; no: clip this
  249.  
  250. ;
  251. ; map it into the column; check bounds.     note that we save this check
  252. ; for second; it's a little slower because of the move and mask.
  253. ;
  254. ; chuck sagely points out that when the "bhi" at the end of the loop takes, we
  255. ; know we can ignore the above comparison.  thanks, chuck.  you're a
  256. ; great guy.
  257. ;
  258.  
  259. LOOPROW                ; here when we know the row number is OK
  260.     move.w    D0,D6        ; copy the sequence element
  261.     and.w    D5,D6        ; find just the column number
  262.  
  263.     cmp.w    A2,D6        ; too far to the right? (past oCols?)
  264.     bgt.s    NEXT        ; yes: skip out
  265.  
  266.     move.l    D0,D4        ; we know element will be used; copy it
  267.     sub.w    D6,D4        ; remove column's bits
  268.     lsr.l    D2,D4        ; shift down to row, NOT right-justified
  269.  
  270. ;
  271. ; get source byte, and bit offset.  D4 has the bit offset in rows, and
  272. ; D6 is columns.
  273. ;
  274.  
  275.     move.w    A5,D1    ; get the stride per row (in bits)
  276.     mulu    D4,D1    ; stride * row; find source row's offset in bits
  277.     add.l    D6,D1    ; add in column offset (bits)
  278.     add.l    A0,D1    ; plus base of bitmap (bits [sic])
  279.     move.b    D1,D7    ; save the bottom three bits for the BTST
  280.     lsr.l    #3,D1    ; while we shift down to a word address
  281.     move.l    D1,A3    ; and save that for the test, too
  282.     not.b    D7    ; get right bit number (compute #7-D7)
  283.  
  284. ;
  285. ; find the destination bit address and bit offset
  286. ;
  287.  
  288.     move.w    A6,D1    ; extract cunningly hidden destination stride
  289.     mulu    D1,D4    ; stride*row number = dest row's offset in bits
  290.     add.l    D6,D4    ; add in column bit offset
  291.     add.l    A1,D4    ; and base address, also in bits
  292.     move.b    D4,D6    ; set aside the bit displacement
  293.     lsr.l    #3,D4    ; make a byte displacement
  294.     not.b    D6    ; get right bit number (compute #7-D6)
  295.  
  296.     btst    D7,(A3)    ; test the D7th bit of source byte
  297.     move.l    D4,A3    ; point to target byte (don't lose CC from btst)
  298.     bne.s    SETON    ; if on, go set destination on
  299.     bclr    D6,(A3)    ; else clear destination bit
  300.  
  301. ;
  302. ; find the next sequence element.  see knuth, vol ii., page 29
  303. ; for sketchy details.
  304. ;
  305.  
  306. NEXT            ; jump here if D0 not in bounds
  307.     lsr.l    #1,D0    ; slide one bit to the right
  308.     bhi.s    LOOPROW    ; if no carry out, but not zero, loop
  309.  
  310.     eor.l    D3,D0    ; flip magic bits for bitwidth we want...
  311.     cmp.l    D3,D0    ; ...but has this brought us to square 1?
  312.     bne.s    LOOP    ; if not, loop back; else...
  313.  
  314.     bra.s    DONE    ; ...we're finished
  315.  
  316. SETON
  317.     bset    D6,(A3)    ; source bit was on: set destination on
  318.  
  319.     ; copy of above code, stolen for inline speed -- sorry.
  320.     lsr.l    #1,D0    ; slide one bit to the right
  321.     bhi.s    LOOPROW    ; if no carry out, but not zero, loop
  322.     eor.l    D3,D0    ; flip magic bits...
  323.     cmp.l    D3,D0    ; ...but has this brought us to square 1?
  324.     bne.s    LOOP    ; if not, loop back; else fall through
  325.  
  326.  
  327. ;
  328. ; here when done; the (0,0) point has not been done yet.  this is
  329. ; really the (0,left margin) point. also jump here from another copy loop.
  330. ;
  331.  
  332. DONE
  333.     move.l    (SP)+,A6    ; restore stack frame pointer
  334.  
  335.     move.w    srcOurs+oLbits(A6),D0    ; pick up bit offset of left margin
  336.     move.w    dstOurs+oLbits(A6),D1    ; and ditto for target
  337.     not.b    D0        ; flip to number the bits for 68000
  338.     not.b    D1        ; ditto
  339.  
  340. ; alternate, late entrance, when SCREEN routine has already set up D0 and
  341. ; D1 (it doesn't want the bit offset negated).
  342.  
  343. DONEA                ; land here with D0, D1 set
  344.     move.l    srcOurs+oBase(A6),A0     ; set up base ptr for source bits
  345.     move.l    dstOurs+oBase(A6),A1     ; and pointer for target
  346.  
  347.     bset    D1,(A1)        ; assume source bit was on; set target
  348.     btst    D0,(A0)        ; was first bit of source on?
  349.     bne.s    DONE2        ; yes: skip out
  350.     bclr    D1,(A1)        ; no: oops!  set it right, and fall through
  351.  
  352. ;
  353. ; return
  354. ;
  355.  
  356. DONE2                ; here when we're really done
  357. ERROR                ; we return silently on errors
  358.     _showcurs        ; let's see this again
  359.  
  360.     movem.l    (SP)+,D3-D7/A2-A5    ; restore lots of registers
  361.     unlk    A6        ; restore caller's stack frame pointer
  362.     move.l    (SP)+,A0    ; pop return address
  363.     add.l    #psize,SP    ; unstack parameters
  364.     jmp (A0)        ; home to mother
  365.  
  366. ;
  367. ; --------------------------------------------------------------
  368. ;
  369. ; sleazo code for when we're asked to dissolve very small regions.  if
  370. ; either dimension of the rectangle is too small, we bag it and just
  371. ; delegate the problem to copyBits.  a possible problem with this is
  372. ; if someone decides to substitute us for the standard copyBits routine
  373. ; -- this case will become recursive...
  374. ;
  375.  
  376. SMALL                ; here when it's too small
  377.     move.l    sBptr(A6),-(SP)    ; push args: source bitmap
  378.     move.l    dBptr(A6),-(SP)    ;    destination bitmap
  379.     move.l    sRptr(A6),-(SP)    ;    source rectangle
  380.     move.l    dRptr(A6),-(SP)    ;    destination rectangle
  381.     move.w    #srcCopy,-(SP)    ;    transfer mode -- source copy
  382.     clr.l    -(SP)        ;    mask region -- NIL
  383.     _copyBits        ; do the copy in quickdraw-land
  384.     bra.s    DONE2        ; head for home
  385.  
  386. ;
  387. ; -----------------------------------------------------------------------
  388. ;
  389. ; code identical to the usual loop, but A5 and A6 have been changed to
  390. ; shift counts. other than that, it's the same.  really it is!  well, no,
  391. ; wait a minute... because we don't have to worry about the word-size
  392. ; mulu operands, we can collapse the shifts and countershifts further
  393. ; as shown below:
  394.  
  395. NOMUL            ; here for alternate version of loop
  396.     tst.w    D2    ; is right shift zero?
  397.     beq.s    NOMUL2    ; yes: can't do much more...
  398.     cmp.w    #0,A5    ; how about one left shift (for source stride)?
  399.     beq.s    NOMUL2    ; yes: ditto
  400.     cmp.w    #0,A6    ; and the other left shift (destination stride)?
  401.     beq.s    NOMUL2    ; yes: can't do much more...
  402.  
  403.     sub.w    #1,D2    ; all three...
  404.     sub.w    #1,A5    ; ...are...
  405.     sub.w    #1,A6    ; ...collapsible
  406.     bra.s    NOMUL    ; go see if we can go further
  407.  
  408. ;
  409. ; see if we can do the super-special-case loop, which basically is
  410. ; equivalent to any rectangle where the source and destination are
  411. ; both exactly the width of the Mac screen.
  412. ;
  413.  
  414. NOMUL2            ; here when D2, A5, and A6 are all collapsed
  415.     tst.w    D2    ; did this shift get down to zero?
  416.     bne.s    NLOOP    ; no: skip to first kludged loop
  417.     cmp.w    #0,A5    ; is this zero?
  418.     bne.s    NLOOP    ; no: again, can't make further optimization
  419.     cmp.w    #0,A6    ; how about this?
  420.     bne.s    NLOOP    ; no: the best-laid plans of mice and men...
  421.     cmp.w    A2,D5    ; is there no check on the column?
  422.     bne.s    NLOOP    ; not a power-of-two columns; rats!
  423.  
  424.     move.w    A0,D6    ; grab the base address of the source
  425.     and.b    #7,D6    ; select the low three bits
  426.     bne.s    NLOOP    ; doesn't sit on a byte boundary; phooey
  427.  
  428.     move.w    A1,D6    ; now try the base of the destination
  429.     and.b    #7,D6    ; and select its bit offset
  430.     beq.s    SCREEN    ; yes!  do extra-special loop!
  431.  
  432. ;
  433. ; fast, but not super-fast loop, used when both source and destination
  434. ; bitmaps have strides which are powers of two.
  435. ;
  436.  
  437. NLOOP            ; here for another time around
  438.     cmp.l    A4,D0    ; is row in bounds?
  439.     bge.s    NNEXT    ; no: clip this
  440.  
  441. NLOOPROW        ; here when we know the row number is OK
  442.     move.w    D0,D6    ; copy the sequence element
  443.     and.w    D5,D6    ; find just the column number
  444.  
  445.     cmp.w    A2,D6    ; too far to the right? (past oCols?)
  446.     bgt.s    NNEXT    ; yes: skip out
  447.  
  448.     move.l    D0,D4    ; we know element will be used; copy it
  449.     sub.w    D6,D4    ; remove column's bits
  450.     lsr.l    D2,D4    ; shift down to row, NOT right-justified
  451.  
  452.     move.w    A5,D7    ; get log2 of stride per row (in bits)
  453.     move.l    D4,D1    ; make a working copy of the row number
  454.     lsl.l    D7,D1    ; * stride/row is source row's offset in bits
  455.     add.l    D6,D1    ; add in column offset (bits)
  456.     add.l    A0,D1    ; plus base of bitmap (bits [sic])
  457.     move.b    D1,D7    ; save the bottom three bits for the BTST
  458.     lsr.l    #3,D1    ; while we shift down to a byte address
  459.     move.l    D1,A3    ; and save that for the test, too
  460.     not.b    D7    ; get right bit number (compute #7-D7)
  461.  
  462.     move.w    A6,D1    ; extract log2 of destination stride
  463.     lsl.l    D1,D4    ; stride*row number = dest row's offset in bits
  464.     add.l    D6,D4    ; add in column bit offset
  465.     add.l    A1,D4    ; and base address, also in bits
  466.     move.b    D4,D6    ; set aside the bit displacement
  467.     lsr.l    #3,D4    ; make a byte displacement
  468.     not.b    D6    ; get right bit number (compute #7-D6)
  469.  
  470.     btst    D7,(A3)    ; test the D7th bit of source byte
  471.     move.l    D4,A3    ; point to target byte (don't ruin CC from btst)
  472.     bne.s    NSETON    ; if on, go set destination on
  473.     bclr    D6,(A3)    ; else clear destination bit
  474.  
  475. NNEXT            ; jump here if D0 not in bounds
  476.     lsr.l    #1,D0    ; slide one bit to the right
  477.     bhi.s    NLOOPROW    ; if no carry out, but not zero, loop
  478.     eor.l    D3,D0    ; flip magic bits...
  479.     cmp.l    D3,D0    ; ...but has this brought us to square 1?
  480.     bne.s    NLOOP    ; if not, loop back; else...
  481.     bra.s    DONE    ; ...we're finished
  482.  
  483. NSETON
  484.     bset    D6,(A3)    ; source bit was on: set destination on
  485.     lsr.l    #1,D0    ; slide one bit to the right
  486.     bhi.s    NLOOPROW    ; if no carry out, but not zero, loop
  487.     eor.l    D3,D0    ; flip magic bits...
  488.     cmp.l    D3,D0    ; ...but has this brought us to square 1?
  489.     bne.s    NLOOP    ; if not, loop back; else fall through
  490.     bra.s    DONE    ; and finish
  491.  
  492. ;
  493. ; -------------------------------------------------------------------------
  494. ;
  495. ; super-special case, which happens to hold for the whole mac screen --
  496. ; or subsets of it which are as wide as the screen. here, we've found that
  497. ; the shift counts in D2, A5, and A6 can all be collapsed to zero.
  498. ; and D5 equals A2, so there's no need to check whether D6 is in limits --
  499. ; or even take it out of D0!  so, this loop is the NLOOP code without
  500. ; the shifts or the check on the column number.  should run like a bat;
  501. ; have you ever seen a bat run?
  502. ;
  503. ; one further restriction -- the addresses in A0 and A1 must point to
  504. ; integral byte addresses with no bit offset.  (this still holds
  505. ; for full-screen copies.)  because both the source and destination are
  506. ; byte-aligned, we can skip the ritual Negation Of The Bit Offset which
  507. ; the 68000 usually demands.
  508.  
  509. SCREEN    ; here to set up to do the whole screen, or at least its width
  510.     move.l    A0,D6    ; take the base source address...
  511.     lsr.l    #3,D6    ; ... and make it a byte address
  512.     move.l    D6,A0    ; replace pointer
  513.  
  514.     move.l    A1,D6    ; now do the same...
  515.     lsr.l    #3,D6    ; ...for...
  516.     move.l    D6,A1    ; ...the destination address
  517.  
  518.     bra.s    N2LOOP    ; jump into loop
  519.  
  520. N2HEAD            ; here when we shifted and a bit carried out
  521.     eor.l    D3,D0    ; flip magic bits to make the sequence work
  522.  
  523. N2LOOP            ; here for another time around
  524.     cmp.l    A4,D0    ; is row in bounds?
  525.     bge.s    N2NEXT    ; no: clip this
  526.  
  527. N2LOOPROW        ; here when we know the row number is OK
  528.     move.l    D0,D1    ; copy row number, shifted up, plus column offset
  529.     lsr.l    #3,D1    ; while we shift down to a word offset
  530.  
  531.     btst    D0,0(A0,D1)    ; test bit of source byte
  532.     bne.s    N2SETON        ; if on, go set destination on
  533.     bclr    D0,0(A1,D1)    ; else clear destination bit
  534.  
  535. N2NEXT                ; jump here if D0 not in bounds
  536.     lsr.l    #1,D0        ; slide one bit to the right
  537.     bhi.s    N2LOOPROW    ; if no carry out, but not zero, loop
  538.     bne.s    N2HEAD        ; if carry out, but not zero, loop earlier
  539.     bra.s    N2DONE    ; 0 means next sequence element would have been D3
  540.  
  541. N2SETON
  542.     bset    D0,0(A1,D1)    ; source bit was on: set destination on
  543.     lsr.l    #1,D0        ; slide one bit to the right
  544.     bhi.s    N2LOOPROW    ; if no carry out, but not zero, loop
  545.     bne.s    N2HEAD        ; if carry out, but not zero, loop earlier
  546.                                ; zero means the loop has closed on itself
  547.  
  548. ;
  549. ; because our bit-numbering isn't like that of the other two loops, we set
  550. ; up D0 and D1 ourselves before joining a bit late with the common code to
  551. ; get the last bit.
  552. ;
  553.  
  554. N2DONE
  555.     move.l    (SP)+,A6    ; restore the stack frame pointer
  556.  
  557.     move.w    srcOurs+oLbits(A6),D0    ; get bit offset of left margin
  558.     move.w    dstOurs+oLbits(A6),D1    ; and ditto for target
  559.     bra    DONEA    ; go do first bit, which sequence doesn't cover
  560.  
  561. ;
  562. ; --------------------------------------------------------------------
  563. ;
  564.  
  565. ; mulchk -- see if we can do without multiply instructions.
  566. ;
  567. ; calling sequence:
  568. ;       A5 holds the source stride
  569. ;       A6 holds the destination stride
  570. ;       clr.w    -(SP)        ; reserve room for boolean function return
  571. ;       bsr    MULCHK        ; go check things out
  572. ;       tst.w    (SP)+        ; test result
  573. ;       bne.s    SHIFT        ; if non-zero, we can shift and not multiply
  574. ;
  575. ;       (if we can shift, A5 and A6 have been turned into shift counts)
  576. ;
  577. ; registers used: none  (A5, A6)
  578.  
  579. MULCHK
  580.  
  581.     movem.l    D0-D3,-(SP)    ; stack caller's registers
  582.     move.l    A5,D0        ; take the source stride
  583.     bsr    BITWIDTH    ; take log base 2
  584.     move.l    #1,D1        ; pick up a one...
  585.     lsl.l    D0,D1        ; ...and try to recreate the stride
  586.     cmp.l    A5,D1        ; does it come out the same?
  587.     bne.s    NOMULCHK    ; nope -- bag it
  588.     move.w    D0,D3        ; save magic logarithm of source stride
  589.  
  590.     move.l    A6,D0        ; yes -- now how about destination stride?
  591.     bsr    BITWIDTH    ; convert that one, also
  592.     move.l    #1,D1        ; again, try a single bit...
  593.     lsl.l    D0,D1        ; ...and see if original # was 1 bit
  594.     cmp.l    A6,D1        ; how'd it come out?
  595.     bne.s    NOMULCHK    ; doesn't match -- bag this
  596.  
  597. ;
  598. ; we can shift instead of multiplying.  change address registers & tell
  599. ; our caller.
  600. ;
  601.     move.w    D3,A5        ; set up shift for source stride
  602.     move.w    D0,A6        ; and for destination stride
  603.     st    4+16(SP)    ; tell our caller what's what
  604.     bra.s    MULRET        ; and return
  605.  
  606. NOMULCHK
  607.  
  608.     sf 4+16(SP)        ; tell caller we can't optimize
  609. MULRET                ; here to return; result set
  610.     movem.l    (SP)+,D0-D3    ; pop some registers
  611.     rts            ; all set
  612.  
  613. ;
  614. ; ------------------------------------------------------------------------
  615. ;
  616. ; table of (longword) masks to XOR in strange Knuthian algorithm.
  617. ; the first table entry is for a bit-width of two, so the table actually
  618. ; starts two bytes before that.     hardware jocks among you may recognize
  619. ; this scheme as the software analog of a "maximum-length sequence
  620. ; generator".
  621. ;
  622. ; to save a bit of room, masks are packed in bytes, but should be aligned
  623. ; as described in the code before being used.
  624. ;
  625.  
  626. table   .equ    *-2        ; first element is #2
  627.     .byte    3o        ; 2
  628.     .byte    3o        ; 3
  629.     .byte    3o        ; 4
  630.     .byte    5o        ; 5
  631.     .byte    3o        ; 6
  632.     .byte    3o        ; 7
  633.     .byte    27o        ; 8
  634.     .byte    21o        ; 9
  635.     .byte    11o        ; 10
  636.     .byte    5o        ; 11
  637.     .byte    145o        ; 12
  638.     .byte    33o        ; 13
  639.     .byte    65o        ; 14
  640.     .byte    3o        ; 15
  641.     .byte    55o        ; 16
  642.     .byte    11o        ; 17
  643.     .byte    201o        ; 18
  644.     .byte    71o        ; 19
  645.     .byte    11o        ; 20
  646.     .byte    5o        ; 21
  647.     .byte    3o        ; 22
  648.     .byte    41o        ; 23
  649.     .byte    33o        ; 24
  650.     .byte    11o        ; 25
  651.     .byte    161o        ; 26
  652.     .byte    71o        ; 27
  653.     .byte    11o        ; 28
  654.     .byte    5o        ; 29
  655.     .byte    145o        ; 30
  656.     .byte    11o        ; 31
  657.     .byte    243o        ; 32
  658. .align 2
  659. ;
  660. ; ----------------------------------------------------------------------
  661. ;
  662. ; convert -- convert a parameter bitMap and rectangle to our internal form.
  663. ;
  664. ; calling sequence:
  665. ;       lea    bitMap,A0    ; point to the bitmap
  666. ;       lea    rect,A1        ; and the rectangle inside it
  667. ;       lea    ours,A2        ; and our data structure
  668. ;       bsr    CONVERT        ; call us
  669. ;
  670. ; when done, all fields of the "ours" structure are filled in:
  671. ;    oBase is address of first byte in which any bits are to be changed
  672. ;    oLbits is number of bits into that first byte which are ignored
  673. ;    oStride is the stride from one row to the next, in bits
  674. ;    oCols is the number of columns in the rectangle
  675. ;    oRows is the number of rows
  676. ;
  677. ; registers used: D0, D1, D2
  678. ;
  679.  
  680. CONVERT
  681.  
  682. ;
  683. ; save the starting word and bit address of the stuff:
  684. ;
  685.        move.w    top(A1),D0    ; pick up top of inner rectangle
  686.        sub.w    bounds+top(A0),D0    ; figure rows to skip within bitmap
  687.        mulu    rowbytes(A0),D0    ; compute bytes to skip (relative offset)
  688.  
  689.        add.l    baseaddr(A0),D0    ; find absolute address of first row to use
  690.  
  691.        move.w    left(A1),D1    ; pick up left coordinate of inner rect
  692.        sub.w    bounds+left(A0),D1    ; find columns to skip
  693.        move.w    D1,D2        ; copy that
  694.        and.w    #7,D2        ; compute bits to skip in first byte
  695.        move.w    D2,oLbits(A2)    ; save that in the structure
  696.  
  697.        lsr.w    #3,D1        ; convert column count from bits to bytes
  698.        ext.l    D1        ; convert to a long value, so we can...
  699.        add.l    D1,D0        ; add to row start in bitmap to find 1st byte
  700.        move.l    D0,oBase(A2)    ; save that in the structure
  701.  
  702. ;
  703. ; save stride of bitmap; this is same as for the original, but in bits.
  704. ;
  705.        move.w    rowbytes(A0),D0    ; pick up the stride
  706.        lsl.w    #3,D0        ; multiply by eight to get a bit stride
  707.        move.w    D0,oStride(A2)    ; stick it in the target structure
  708.  
  709. ;
  710. ; save the number of rows and columns.
  711. ;
  712.     move.w    bottom(A1),D0    ; get the bottom of the rectangle
  713.     sub.w    top(A1),D0    ; less the top coordinate
  714.     sub.w    #1,D0        ; get number of highest row (1st is zero)
  715.     bmi.s    CERROR        ; nothing to do?  (note: 0 IS ok)
  716.     move.w    D0,oRows(A2);    ; save that in the structure
  717.  
  718.     move.w    right(A1),D0    ; get the right edge of the rectangle
  719.     sub.w    left(A1),D0    ; less the left coordinate
  720.     sub.w    #1,D0        ; make it zero-based
  721.     bmi    CERROR        ; nothing to do here?
  722.     move.w    D0,oCols(A2)    ; save that in the structure
  723.  
  724. ;
  725. ; all done.  return.
  726. ;
  727.     rts
  728.  
  729. ;
  730. ; error found in CONVERT.  pop return and jump to the error routine, such as it is.
  731. ;
  732. CERROR
  733.     addq.l    #4,SP        ; pop four bytes of return address.
  734.     bra.s    ERROR        ; return silently
  735.  
  736. ;
  737. ; -------------------------------------------------------------------------
  738. ;
  739. ; log2 -- find the ceiling of the log, base 2, of a number.
  740. ; bitwidth -- find how many bits wide a number is
  741. ;
  742. ; calling sequence:
  743. ;       move.l    N,D0        ; store the number in D0
  744. ;       bsr    LOG2        ; call us
  745. ;       move.w    D0,...        ; D0 contains the word result
  746. ;
  747. ; registers used: D2, (D0)
  748. ;
  749.  
  750. BITWIDTH
  751.     sub.l    #1,D0        ; so 2**n works right (sigh)
  752. LOG2
  753.     tst.l    D0        ; did they pass us a zero?
  754.     beq.s    LOGDONE        ; if D0 was one, answer is zero
  755.     move.w    #32,D2        ; initialize count
  756. LOG2LP
  757.     lsl.l    #1,D0        ; slide bits to the left by one
  758.     dbcs    D2,LOG2LP    ; decrement and loop until a bit falls off
  759.  
  760.     move.w    D2,D0        ; else save our value where we promised it
  761. LOGDONE                ; here with final value in D0
  762.     rts            ; and return
  763.  
  764. .end    ; procedure dissBits
  765. 
  766.