home *** CD-ROM | disk | FTP | other *** search
/ Carousel Volume 2 #1 / carousel.iso / mactosh / code / p_dissbi.sit / DissBits / DissBits5.a < prev    next >
Encoding:
Text File  |  1985-09-21  |  41.6 KB  |  974 lines  |  [TEXT/MACA]
  1. ;
  2. ;  procedure dissBits (srcB, destB: bitMap; srcR, dstR: rect); external;
  3. ;
  4. ; mike morton
  5. ; release: 15 september 1985
  6. ;
  7. ; this is the version 5.2.  if it doesn't work right, try copyBits and see if
  8. ; it works.  if there are bugs, they're likely due to the recent fancy
  9. ; optimizations, so version three (a much simpler version) should work instead.
  10. ;
  11. ; differences from version 5 to 5.2 are:
  12. ;       bug fixed in the full-screen-width case (first bit done right)
  13. ;       magic-constant table is compacted, stored in bytes instead of longs
  14. ;       some small changes to save space, plus the table saves about 100 bytes
  15. ;       tested by a program on several million cases; this helped find...
  16. ;       yet more bugs in log2 routine fixed ("bitwidth" routine added)
  17. ; differences from version 4 are:
  18. ;       nasty bug fixed in copying small rectangles
  19. ;       new address for correspondence
  20. ;       slightly more detailed notes on calling from C
  21. ;       various miscellaneous comment changes
  22. ; differences from version 3 are:
  23. ;       bugs in the log2 routine fixed
  24. ;       general case sped up about five percent
  25. ;       certain cases (e.g., the full screen) sped up over fifty percent
  26. ;       the time to dissolve is not directly related to the size of the rect
  27. ; differences between version 2 and version 3 are:
  28. ;       documentation improved and neatened
  29. ;       log2 routine rewritten
  30. ;
  31. ; comments and suggestions are, of course, welcome.
  32. ;
  33. ; ******************************************************************************
  34. ; *                                           *
  35. ; *            copyright 1984, 1985 by michael s. morton               *
  36. ; *    please see details below on using, copying and changing this source.    *
  37. ; *                                           *
  38. ; ******************************************************************************
  39. ;
  40. ; what this routine does:
  41. ; ----------------------
  42. ;
  43. ; dissBits is like copyBits: it moves one rect to another, in their respective
  44. ; bitMaps.  it doesn't implement the modes of copyBits, nor clipping to a
  45. ; region.  what it DOES do is copy the bits in a pseudo-random order, giving
  46. ; the appearance of "dissolving" from one image to another.  the dissolve is
  47. ; rapid: the entire screen will dissolve in under four seconds.     (note: smaller
  48. ; areas may be SLOWER to dissolve -- see below.)
  49. ;
  50. ; copyBits pays attention to the current clipping.  this routine doesn't.
  51. ;
  52. ; other likely differences from copyBits:
  53. ;     o     the rectangles must have the same extents (not necessarily the same
  54. ;     lrbt).     if they are not, the routine will return -- doing nothing!
  55. ;     no stretching copy is done as copyBits would.
  56. ;     o     the cursor is hidden during the dissolve, since drawing is done without
  57. ;     quickdraw calls.  the cursor reappears when the drawing is finished.
  58. ;     for an odd effect, change it not to hide the cursor; is this how bill
  59. ;     atkinson thought of the spray can in MacPaint?
  60. ;     o     copyBits may be smart enough to deal with overlapping areas of memory.
  61. ;     this routine certainly isn't.
  62. ;     o     because this routine is desperate for speed, it steals the A5 (globals)
  63. ;     register, uses it in the central loop, then restores it before
  64. ;     returning. if you have vertical retrace tasks which run during the
  65. ;     dissolve, they'll wake up with the bogus A5.  since the ROM pulls this
  66. ;     trick too, i feel this isn't a bug in MY code, but it IS more likely
  67. ;     to expose bugs in VBL tasks.  to correct the problem, have your task
  68. ;     load A5 from the low RAM location "currentA5" immediately upon starting
  69. ;     up, then restore its caller's A5 before returning.
  70. ;
  71. ; you should know a few implementation details which may help:
  72. ;     o     copying from a dark area (lots of 1 bits) is slower than from a light
  73. ;     area.  but just barely (a few per cent).
  74. ;     o     there is no way to use this to randomly invert a rectangle.  instead,
  75. ;     copyBits it elsewhere, invert it, and dissBits it back into place.
  76. ;     o     there is also no way to slow the dissolve of a small area.  to do this,
  77. ;     copy a large area in which the only difference is the area to change.
  78. ;     o     if you fade in a solid area, you're likely to see patterns, since the
  79. ;     random numbers are so cheesy.  don't do this; fade in nifty patterns
  80. ;     which will distract your viewers.
  81. ;     o very small areas (less than 2 pixels in either dimension) are actually
  82. ;       done with a call to the real copyBits routine, since the pseudo-random
  83. ;       sequence generator falls apart under those conditions.
  84. ;
  85. ; a close relative of this routine is "dissBytes", which (as you might guess)
  86. ; copies a byte at a time, which is really fast (the whole screen in .1 or .2
  87. ; seconds).  it works only for certain rectangles, though.
  88. ;
  89. ; sample calling code:
  90. ; -------------------
  91. ;
  92. ; this is an excerpt from how a prerelease of DarTerminal called this routine.
  93. ; note the clever use of "paintbehind".     this took about 3 seconds to dissolve
  94. ; onto the screen.
  95. ;
  96. ;var   rg:      rgnhandle;                (* window to copy into *)
  97. ;      aport:   grafptr;                (* port to draw into *)
  98. ;      bits:    bitmap;                    (* new bitmap for that port *)
  99. ;      r:       rect;                    (* rectangle to draw into *)
  100. ;      pat:     pattern;
  101. ;      text:    packed array[1..37] of char;
  102. ; ...
  103. ;   aport := grafptr(newptr(sizeof(grafport))); (* get a port *)
  104. ;   openport(aport);                    (* make it current *)
  105. ;
  106. ;   r := theport^.portbits.bounds;            (* start with whole screen *)
  107. ;   insetrect(r,100,100);                (* get window-size rect *)
  108. ;   (* note that the number of bytes per row must be even! *)
  109. ;   bits.rowbytes := (((r.right-r.left)+15) div 16) * 2; (* find bytes/row *)
  110. ;   bits.baseaddr := qdptr(newptr(bits.rowbytes*(r.bottom-r.top))); (* get space *)
  111. ;   bits.bounds := r;                    (* boundary rect for bitmap *)
  112. ;
  113. ;   setportbits(bits);                    (* make new bitmap current *)
  114. ;
  115. ;   eraserect(r);
  116. ;   textfont(london); textsize(18); textface([bold]);
  117. ;   text := 'DarTerminal version -1.9  August 1984';
  118. ;   textbox(@text,37,r,tejustcenter);
  119. ;
  120. ;   dissbits(bits,screenport^.portbits,r,r);    (* dissolve it in *)
  121. ;
  122. ;   repeat until getnextevent(mdownmask+keydownmask,anevent); (* let 'em gawk *)
  123. ;
  124. ;   rg := newrgn;                    (* get a region to clip with *)
  125. ;   rectrgn(rg,r);                    (* as a rectangle *)
  126. ;   paintbehind(windowpeek(frontwindow),rg);    (* update this area of screen *)
  127. ;
  128. ;   disposergn(rg);
  129. ;   disposptr(ptr(bits.baseaddr));
  130. ;   disposptr(ptr(aport));
  131. ;
  132. ;
  133. ; calling from languages other than pascal:
  134. ; ----------------------------------------
  135. ;
  136. ; this routine uses the standard Lisa Pascal calling sequence.  to convert it to
  137. ; most C compilers, you'll probably just have to delete this instruction from
  138. ; near the end of the main routine:
  139. ;       add.l #psize,SP                ; unstack parameters
  140. ;
  141. ; i'd be very interested in hearing about successful uses of this routine from
  142. ; other languages.
  143. ;
  144. ; speed of the dissolve:
  145. ; ---------------------
  146. ;
  147. ; you need to pay attention to this section only if: (a) you want the dissolve
  148. ; to run as fast as it can OR (b) you do dissolves of various sizes and want
  149. ; them to take proportionate lengths of time.
  150. ;
  151. ; there are 3 levels of speed; the fastest possible one is chosen for you:
  152. ; (1) an ordinary dissolve will work when moving from any bitmap to any bitmap,
  153. ;     including on the Lisa under MacWorks.  this will dissolve at about 49
  154. ;     microseconds per pixel.  a rectangle one-quarter the size of the screen
  155. ;     will dissolve in just over two seconds.  the speed per pixel will vary
  156. ;     slightly, and will be less if your rect extents are close to but less
  157. ;     than powers of 2.
  158. ; (2) the dissolve will speed up if both the source and destination bitmaps have
  159. ;     rowBytes fields which are powers of two.  if you're copying to the screen
  160. ;     on a mac, the rowBytes field already satisfies this.  so, make your source
  161. ;     bitmap the right width for a cheap speedup -- about 20% faster.
  162. ; (3) the fanciest level is intended for copying the whole screen.  it'll paint
  163. ;     it in about 3.4 seconds (19 microseconds per pixel).  actually, painting
  164. ;     any rectangle which is the full width of the screen will run at this
  165. ;     speed, for what that's worth.
  166. ;
  167. ; duplication and use of this routine:
  168. ; -----------------------------------
  169. ;
  170. ; this is freeware.  you're welcome to copy it and use it in programs.  you're
  171. ; welcome to modify it, as long as you leave everything up until this section
  172. ; unchanged.  i'd be very interested in seeing your changes, especially if you
  173. ; find ways to make the central loops faster.  you're also welcome to port it
  174. ; to other machines/languages; i'd appreciate hearing about efforts to do this.
  175. ;
  176. ; this is "freeware"; please pay me if you use it.  why?
  177. ;
  178. ;       o if you have problems using it, i'll help you debug it.
  179. ;       o i'll send you improved, debugged, faster versions.
  180. ;       o i'll tell you about other products.  this is the first thing i ever
  181. ;      wrote for the Mac; wouldn't you like to see what else i've produced?
  182. ;      send me some positive feedback!
  183. ;
  184. ; how much should you pay?  my suggestion is:
  185. ;       (cost of one copy of the program) * (log10 of number of copies sold)
  186. ; if the subroutine is an integral part of your program, double this amount.
  187. ; if it's a frill (e.g., you dissolve in your "About MacWhatever"), halve it.
  188. ;
  189. ; i find it hard to believe that any damages to you or anyone else could come
  190. ; from bugs in this routine.  but, alas, whether or not you pay me, i can't be
  191. ; liable in any way for any problems in it.
  192. ;
  193. ; send comments, contributions, criticisms, or whatever to:
  194. ;       mike morton
  195. ;       INFOCOM
  196. ;       125 CambridgePark Dr.
  197. ;       Cambridge, MA  02140
  198. ;
  199. ; if, for some reason, you only have a hard copy of this and would like a
  200. ; source on a diskette, please contact:
  201. ;       robert hafer
  202. ;       the boston computer society
  203. ;       one center plaza
  204. ;       boston, mass.  02108
  205. ;
  206.  
  207. ;
  208. ; things to think about:
  209. ; ---------------------
  210. ;
  211. ; o  clean up the register usage (as if i'll ever actually get around to this)
  212. ; o  use a dynamically-built table to avoid the multiply instruction in the general case.
  213. ;    this may not be a great idea since not everyone can afford that much space.
  214. ; o  adapt the routine to do transfer modes.  especially pattern modes, with no source.
  215. ;    it'd run significantly faster doing a fill of just black or white!     and patXor
  216. ;    would be pretty cool too (see also the XOR idea below).
  217. ; o  consider a front-end which does clipping (just like copyBits) by:
  218. ;       - allocate yet another offscreen bitmap, whose bounds are the intersection of
  219. ;      the destination rect with the bounding box of the destination's clipping rgn.
  220. ;       - copy from the destination's bitmap into the temporary bitmap.
  221. ;       - do a copyBits from the source to the temp, with the requested masking region.
  222. ;       - dissolve from the temp to the destination, thus actually dissolving that whole
  223. ;      rect, but changing only the clipped stuff.
  224. ; o  a nifty way to speed up things would be to XOR the destination into the source [sic!].
  225. ;    then the main loop doesn't have to copy a bit; it just tests if the bit is ON in the
  226. ;    altered source bitmap and, if so, TOGGLES it in the destination.  (i.e., it does a
  227. ;    srcXor operation).     to repair the source bitmap, a third XOR from the destination to
  228. ;    the source should do it [any old-timer will recognize this triple XOR as the best
  229. ;    way to swap two registers.]  the trick is making the invisible XOR run so fast that
  230. ;    the time to do it is less than the savings in the visible part.  or perhaps the batch
  231. ;    XORs could be done in spare-time...
  232. ; o  implement a partial dissolve.  this would let alex animate star trek-style teleporting.
  233. ;    there are a lot of ways to do this.  the easiest might be to include a counter in the
  234. ;    loop ("a register!     my kingdom for a register!").  alternately, we could assume that
  235. ;    the list of starting and ending points could be limited, allowing a table-based system.
  236. ;    this is something worth looking into, but could be real difficult.
  237. ; o  look at rearranging instructions so CPU-intensive ones aren't grouped, allowing us to
  238. ;    sneak in between video cycles more often.
  239. ; o  add some real error-handling.  how should we do this?  return a status?  fault?  we
  240. ;    could also return info to our caller on which of the three loops got used, so they know
  241. ;    they're getting the speed they want.
  242. ; o  don't use the BITWIDTH routine to test for exact powers of two in MULCHK.  a number X]
  243. ;    is an exact power of two if (x & -x) equals x.
  244. ;
  245.  
  246. ;
  247. ;       -- end of introduction; real stuff starts here --
  248. ;
  249.  
  250. ;
  251. ; include files:
  252. ;       tlasm/graftypes -- definitions of "bitMap" and "rect"
  253. ;       tlasm/quickmacs -- macros for quickdraw calls (e.g., _hidecursor)
  254. ;
  255.  
  256. .nolist
  257. .include tlasm/graftypes
  258. .include tlasm/quickmacs
  259. .list
  260.  
  261. ;
  262. ; definitions of the "ours" record: this structure, of which there are two copies in
  263. ; our stack frame, is a sort of bitmap:
  264. ;
  265.  
  266. oRows   .equ 0                    ; (word) number of last row (first is 0)
  267. oCols   .equ oRows+2                ; (word) number of last column (first is 0)
  268. oLbits  .equ oCols+2                ; (word) size of left margin within 1st byte
  269. oStride .equ oLbits+2                ; (word) stride in memory from row to row
  270. oBase   .equ oStride+2                ; (long) base address of bitmap
  271.  
  272. osize   .equ oBase+4                ; size, in bytes, of "ours" record
  273.  
  274. ;
  275. ; stack frame elements:
  276. ;
  277.  
  278. srcOurs .equ -osize                ; (osize) our view of source bits
  279. dstOurs .equ srcOurs-osize            ; (osize) our view of target bits
  280.  
  281. sflast  .equ dstOurs                ; relative address of last s.f. member
  282. sfsize  .equ -sflast                ; size of s.f. for LINK (must be EVEN!)
  283. ;
  284. ;       parameter offsets from the stack frame pointer, A6:
  285. ;       last parameter is above return address and old s.f.
  286. ;
  287.  
  288. dRptr   .equ 4+4                ; ^destination rectangle
  289. sRptr   .equ dRptr+4                ; ^source rectangle
  290. dBptr   .equ sRptr+4                ; ^destination bitMap
  291. sBptr   .equ dBptr+4                ; ^source bitMap
  292.  
  293. plast   .equ sBptr+4                ; address just past last parameter
  294.  
  295. psize   .equ plast-dRptr            ; size of parameters, in bytes
  296.  
  297. ;
  298. ; entrance: set up a stack frame, save some registers, hide the cursor.
  299. ;
  300.  
  301. .proc   dissBits                ; main entry point
  302.  
  303.         link A6,#-sfsize            ; set up a stack frame
  304.         movem.l D3-D7/A2-A5,-(SP)       ; save registers compiler may need
  305.         _hidecurs                ; don't let the cursor show for now
  306.  
  307. ;
  308. ; convert the source and destination bitmaps and rectangles to a format we prefer.
  309. ; we won't look at these parameters after this.
  310. ;
  311.  
  312.         move.l sBptr(A6),A0            ; point to source bitMap
  313.         move.l sRptr(A6),A1            ; and source rectangle
  314.         lea srcOurs(A6),A2            ; and our source structure
  315.         bsr CONVERT                ; convert to our format
  316.  
  317.         move.l dBptr(A6),A0            ; point to destination bitMap
  318.         move.l dRptr(A6),A1            ; and rectangle
  319.         lea dstOurs(A6),A2            ; and our structure
  320.         bsr CONVERT                ; convert to our format
  321.  
  322. ;
  323. ; check that the rectangles match in size.
  324. ;
  325.         move.w srcOurs+oRows(A6),D0     ; pick up the number of rows
  326.         cmp.w dstOurs+oRows(A6),D0      ; same number of rows?
  327.         bne ERROR                ; nope -- bag it
  328.  
  329.         move.w srcOurs+oCols(A6),D0     ; check the number of columns
  330.         cmp.w dstOurs+oCols(A6),D0      ; same number of columns, too?
  331.         bne ERROR                ; that's a bozo no-no
  332.  
  333. ;
  334. ; figure the bit-width needed to span the columns, and the rows.
  335. ;
  336.  
  337.         move.w srcOurs+oCols(A6),D0     ; get count of columns
  338.         ext.l D0                ; make it a longword
  339.         bsr LOG2                ; figure bit-width
  340.         move.w D0,D1                ; set aside that result
  341.         beq SMALL                ; too small?  wimp out and do it with copyBits
  342.  
  343.         move.w srcOurs+oRows(A6),D0     ; get count of rows
  344.         ext.l D0                ; make it a longword
  345.         bsr LOG2                ; again, find the bit-width
  346.         tst.w D0                ; is the result zero?
  347.         beq SMALL                ; if so, our algorithm will screw up
  348.  
  349. ;
  350. ; set up various constants we'll need in the in the innermost loop
  351. ;
  352.  
  353.         move.l #1,D5                ; set up...
  354.         lsl.l D1,D5                ; ...the bit mask which is...
  355.         sub.l #1,D5                ; ...bit-width (cols) 1's
  356.  
  357.         add.w D1,D0                ; find total bit-width (rows plus columns)
  358.         lea TABLE,A0                ; point to the table of XOR masks
  359.         moveq #0,D3                ; clear out D3 before we fill the low byte
  360.         move.b 0(A0,D0),D3            ; grab the correct XOR mask in D3
  361.  
  362. ;
  363. ; the table is saved compactly, since none of the masks are wider than a byte.  we have to unpack it so
  364. ; the high-order bit of the D0-bit-wide field is on:
  365. ;
  366.  
  367. UNPACK  add.l D3,D3                ; shift left by one
  368.         bpl.s UNPACK                ; keep moving until the top bit that's on is aligned at the top end
  369.  
  370.         rol.l D0,D3                ; now swing the top D0 bits around to be the bottom D0 bits, the mask
  371.         move.l D3,D0                ; 1st sequence element is the mask itself
  372.  
  373. ;
  374. ; do all kinds of preparation:
  375. ;
  376.  
  377.         move.l srcOurs+oBase(A6),D2     ; set up base pointer for our source bits
  378.         lsl.l #3,D2                ; make it into a bit address
  379.         move.l D2,A0                ; put it where the fast loop will use it
  380.         move.w srcOurs+oLbits(A6),D2    ; now pick up source left margin
  381.         ext.l D2                ; make it a longword
  382.         add.l D2,A0                ; and make A0 useful for odd routine below
  383.  
  384.         move.l dstOurs+oBase(A6),D2     ; set up base pointer for target
  385.         lsl.l #3,D2                ; again, bit addressing works out faster
  386.         move.l D2,A1                ; stuff it where we want it for the loop
  387.         move.w dstOurs+oLbits(A6),D2    ; now pick up destination left margin
  388.         ext.l D2                ; make it a longword
  389.         add.l D2,A1                ; and make A1 useful, too
  390.  
  391.         move.w srcOurs+oCols(A6),A2     ; pick up the often-used count of columns
  392.         move.w srcOurs+oRows(A6),D2     ; and of rows
  393.         add.w #1,D2                ; make row count one-too-high for compares
  394.         ext.l D2                ; and make it a longword
  395.         lsl.l D1,D2                ; slide it to line up w/rows part of D0
  396.         move.l D2,A4                ; and save that somewhere useful
  397.  
  398.         move.w D1,D2                ; put log2(columns) in a safe place (sigh)
  399.  
  400. ;
  401. ; try to reduce the amount we shift down D2.  this involves:
  402. ;    halving the strides as long as each is even, decrementing D2 as we go
  403. ;    masking the bottom bits off D4 when we extract the row count in the loop
  404. ;
  405. ; alas, we can't always shift as little as we want.  for instance, if we don't
  406. ; shift down far enough, the row count will be so high as to exceed a halfword,
  407. ; and the dread mulu instruction won't work (it eats only word operands).  so,
  408. ; we have to have an extra check to take us out of the loop early.
  409. ;
  410.  
  411.         move.w srcOurs+oStride(A6),D4   ; pick up source stride
  412.         move.w dstOurs+oStride(A6),D7   ; and target stride
  413.         move.w srcOurs+oRows(A6),D1     ; pick up row count for kludgey check
  414.  
  415.         tst.w D2                ; how's the bitcount?
  416.         beq.s HALFDONE                ; skip out if already down to zero
  417.  
  418. HALFLOOP
  419.         btst #0,D4                ; is this stride even?
  420.         bne.s HALFDONE                ; nope -- our work here is done
  421.         btst #0,D7                ; how about this one?
  422.         bne.s HALFDONE                ; have to have both even
  423.  
  424.         lsl.w #1,D1                ; can we keep max row number in a halfword?
  425.         bcs.s HALFDONE                ; nope -- D2 mustn't get any smaller!
  426.  
  427.         lsr.w #1,D4                ; halve each stride...
  428.         lsr.w #1,D7                ; ...like this
  429.         sub.w #1,D2                ; and remember not to shift down as far
  430.         bne.s HALFLOOP                ; loop unless we're down to no shift at all
  431.  
  432. HALFDONE                    ; no tacky platitudes, please
  433.         move.w D4,srcOurs+oStride(A6)   ; put back source stride
  434.         move.w D7,dstOurs+oStride(A6)   ; and target stride
  435.  
  436. ;
  437. ; make some stuff faster to access -- use the fact that (An) is faster to access
  438. ; than d(An).  this means we'll misuse our frame pointer, but don't worry -- we'll
  439. ; restore it before we use it again.
  440. ;
  441.  
  442.         move.w srcOurs+oStride(A6),A5   ; make source stride faster to access, too
  443.         move.l A6,-(SP)                ; save framitz pointer
  444.         move.w dstOurs+oStride(A6),A6   ; pick up destination stride
  445.         move.l #0,D6                ; we do only AND.W x,D6 -- but ADD.L D6,x
  446.  
  447.         clr.w -(SP)                ; reserve room for function result
  448.         bsr MULCHK                ; go see if strides are powers of two
  449.         tst.w (SP)+                ; can we eliminate the horrible MULUs?
  450.         bne  NOMUL                ; yes!  hurray!
  451.  
  452. ;
  453. ; main loop: map the sequence element into rows and columns, check if it's in bounds
  454. ; and skip on if it's not, flip the appropriate bit, generate the next element in the
  455. ; sequence, and loop if the sequence isn't done.
  456. ;
  457.  
  458. ;
  459. ; check the row bounds.     note that we can check the row before extracting it from
  460. ; D0, ignoring the bits at the bottom of D0 for the columns.  to get these bits
  461. ; to be ignored, we had to make A4 one-too-high before shifting it up to align it.
  462. ;
  463.  
  464. LOOP                        ; here for another time around
  465.         cmp.l A4,D0                ; is row in bounds?
  466.         bge.s NEXT                ; no: clip this
  467.  
  468. ;
  469. ; map it into the column; check bounds.     note that we save this check for second;
  470. ; it's a little slower because of the move and mask.
  471. ;
  472. ; chuck sagely points out that when the "bhi" at the end of the loop takes, we
  473. ; know we can ignore the above comparison.  thanks, chuck.  you're a great guy.
  474. ;
  475.  
  476. LOOPROW                        ; here when we know the row number is OK
  477.         move.w D0,D6                ; copy the sequence element
  478.         and.w D5,D6                ; find just the column number
  479.  
  480.         cmp.w A2,D6                ; too far to the right? (past oCols?)
  481.         bgt.s NEXT                ; yes: skip out
  482.  
  483.         move.l D0,D4                ; we know element will be used; copy it
  484.         sub.w D6,D4                ; remove column's bits
  485.         lsr.l D2,D4                ; shift down to row, NOT right-justified
  486.  
  487. ;
  488. ; get the source byte, and bit offset.  D4 has the bit offset in rows, and
  489. ; D6 is columns.
  490. ;
  491.  
  492.         move.w A5,D1                ; get the stride per row (in bits)
  493.         mulu D4,D1                ; stride * row; find source row's offset in bits
  494.         add.l D6,D1                ; add in column offset (bits)
  495.         add.l A0,D1                ; plus base of bitmap (bits [sic])
  496.         move.b D1,D7                ; save the bottom three bits for the BTST
  497.         lsr.l #3,D1                ; while we shift down to a word address
  498.         move.l D1,A3                ; and save that for the test, too
  499.         not.b D7                ; get right bit number (compute #7-D7)
  500.  
  501. ;
  502. ; find the destination bit address and bit offset
  503. ;
  504.  
  505.         move.w A6,D1                ; extract cunningly hidden destination stride
  506.         mulu D1,D4                ; stride*row number = dest row's offset in bits
  507.         add.l D6,D4                ; add in column bit offset
  508.         add.l A1,D4                ; and base address, also in bits
  509.         move.b D4,D6                ; set aside the bit displacement
  510.         lsr.l #3,D4                ; make a byte displacement
  511.         not.b D6                ; get right bit number (compute #7-D6)
  512.  
  513.         btst D7,(A3)                ; test the D7th bit of source byte
  514.         move.l D4,A3                ; point to target byte (don't lose CC from btst)
  515.         bne.s SETON                ; if on, go set destination on
  516.         bclr D6,(A3)                ; else clear destination bit
  517.  
  518. ;
  519. ; find the next sequence element.  see knuth, vol ii., page 29 for sketchy details.
  520. ;
  521.  
  522. NEXT                        ; jump here if D0 not in bounds
  523.         lsr.l #1,D0                ; slide one bit to the right
  524.         bhi.s LOOPROW                ; if no carry out, but not zero, loop
  525.  
  526.         eor.l D3,D0                ; flip magic bits appropriate to the bitwidth we want...
  527.         cmp.l D3,D0                ; ...but has this brought us to square 1?
  528.         bne.s LOOP                ; if not, loop back; else...
  529.  
  530.         bra.s DONE                ; ...we're finished
  531.  
  532. SETON
  533.         bset D6,(A3)                ; source bit was on: set destination on
  534.  
  535.         ; copy of above code, stolen for inline speed -- sorry.
  536.         lsr.l #1,D0                ; slide one bit to the right
  537.         bhi.s LOOPROW                ; if no carry out, but not zero, loop
  538.         eor.l D3,D0                ; flip magic bits...
  539.         cmp.l D3,D0                ; ...but has this brought us to square 1?
  540.         bne.s LOOP                ; if not, loop back; else fall through
  541.  
  542.  
  543. ;
  544. ; here when we're done; the (0,0) point has not been done yet.  this is
  545. ; really the (0,left margin) point.  we also jump here from another copy loop.
  546. ;
  547.  
  548. DONE
  549.         move.l (SP)+,A6                ; restore stack frame pointer
  550.  
  551.         move.w srcOurs+oLbits(A6),D0    ; pick up bit offset of left margin
  552.         move.w dstOurs+oLbits(A6),D1    ; and ditto for target
  553.         not.b D0                ; flip to number the bits for 68000
  554.         not.b D1                ; ditto
  555.  
  556. ; alternate, late entrance, when SCREEN routine has already set up D0 and D1 (it doesn't want the bit
  557. ; offset negated).
  558.  
  559. DONEA                        ; land here with D0, D1 set
  560.         move.l srcOurs+oBase(A6),A0     ; set up base pointer for our source bits
  561.         move.l dstOurs+oBase(A6),A1     ; and pointer for target
  562.  
  563.         bset D1,(A1)                ; assume source bit was on; set target
  564.         btst D0,(A0)                ; was first bit of source on?
  565.         bne.s DONE2                ; yes: skip out
  566.         bclr D1,(A1)                ; no: oops!  set it right, and fall through
  567.  
  568. ;
  569. ; return
  570. ;
  571.  
  572. DONE2                        ; here when we're really done
  573. ERROR                        ; we return silently on errors
  574.         _showcurs                ; let's see this again
  575.  
  576.         movem.l (SP)+,D3-D7/A2-A5       ; restore lots of registers
  577.         unlk A6                    ; restore caller's stack frame pointer
  578.         move.l (SP)+,A0                ; pop return address
  579.         add.l #psize,SP                ; unstack parameters
  580.         jmp (A0)                ; home to mother
  581.  
  582. ;
  583. ; -----------------------------------------------------------------------------------
  584. ;
  585. ; sleazo code for when we're asked to dissolve very small regions.  if either dimension of the rectangle
  586. ; is too small, we bag it and just delegate the problem to copyBits.  a possible problem with this is if
  587. ; someone decides to substitute us for the standard copyBits routine -- this case will become recursive...
  588. ;
  589.  
  590. SMALL                        ; here when it's too small to copy ourselves
  591.         move.l sBptr(A6),-(SP)            ; push args: source bitmap
  592.         move.l dBptr(A6),-(SP)            ;         destination bitmap
  593.         move.l sRptr(A6),-(SP)            ;         source rectangle
  594.         move.l dRptr(A6),-(SP)            ;         destination rectangle
  595.         move.w #srcCopy,-(SP)            ;         transfer mode -- source copy
  596.         clr.l -(SP)                ;         mask region -- NIL
  597.         _copyBits                ; do the copy in quickdraw-land
  598.         bra.s DONE2                ; head for home
  599.  
  600. ;
  601. ; -----------------------------------------------------------------------------------
  602. ;
  603. ; code identical to the usual loop, but A5 and A6 have been changed to shift counts.
  604. ; other than that, it's the same.  really it is!  well, no, wait a minute...
  605. ; because we don't have to worry about the word-size mulu operands, we can collapse
  606. ; the shifts and countershifts further as shown below:
  607.  
  608. NOMUL                        ; here for alternate version of loop
  609.         tst.w D2                ; is right shift zero?
  610.         beq.s NOMUL2                ; yes: can't do much more...
  611.         cmp.w #0,A5                ; how about one left shift (for source stride)?
  612.         beq.s NOMUL2                ; yes: ditto
  613.         cmp.w #0,A6                ; and the other left shift (destination stride)?
  614.         beq.s NOMUL2                ; yes: can't do much more...
  615.  
  616.         sub.w #1,D2                ; all three...
  617.         sub.w #1,A5                ; ...are...
  618.         sub.w #1,A6                ; ...collapsible
  619.         bra.s NOMUL                ; go see if we can go further
  620.  
  621. ;
  622. ; see if we can do the super-special-case loop, which basically is equivalent to any rectangle
  623. ; where the source and destination are both exactly the width of the Mac screen.
  624. ;
  625.  
  626. NOMUL2                        ; here when D2, A5, and A6 are all collapsed
  627.         tst.w D2                ; did this shift get down to zero?
  628.         bne.s NLOOP                ; no: skip to first kludged loop
  629.         cmp.w #0,A5                ; is this zero?
  630.         bne.s NLOOP                ; no: again, can't make further optimization
  631.         cmp.w #0,A6                ; how about this?
  632.         bne.s NLOOP                ; no: the best-laid plans of mice and men...
  633.         cmp.w A2,D5                ; is there no check on the column?
  634.         bne.s NLOOP                ; not a power-of-two columns; rats!
  635.  
  636.         move.w A0,D6                ; grab the base address of the source
  637.         and.b #7,D6                ; select the low three bits
  638.         bne.s NLOOP                ; doesn't sit on a byte boundary; phooey
  639.  
  640.         move.w A1,D6                ; now try the base of the destination
  641.         and.b #7,D6                ; and select its bit offset
  642.         beq.s SCREEN                ; yes!  do extra-special loop!
  643.  
  644. ;
  645. ; fast, but not super-fast loop, used when both source and destination bitmaps have strides which are
  646. ; powers of two.
  647. ;
  648.  
  649. NLOOP                        ; here for another time around
  650.         cmp.l A4,D0                ; is row in bounds?
  651.         bge.s NNEXT                ; no: clip this
  652.  
  653. NLOOPROW                    ; here when we know the row number is OK
  654.         move.w D0,D6                ; copy the sequence element
  655.         and.w D5,D6                ; find just the column number
  656.  
  657.         cmp.w A2,D6                ; too far to the right? (past oCols?)
  658.         bgt.s NNEXT                ; yes: skip out
  659.  
  660.         move.l D0,D4                ; we know element will be used; copy it
  661.         sub.w D6,D4                ; remove column's bits
  662.         lsr.l D2,D4                ; shift down to row, NOT right-justified
  663.  
  664.         move.w A5,D7                ; get log2 of stride per row (in bits)
  665.         move.l D4,D1                ; make a working copy of the row number
  666.         lsl.l D7,D1                ; * stride/row is source row's offset in bits
  667.         add.l D6,D1                ; add in column offset (bits)
  668.         add.l A0,D1                ; plus base of bitmap (bits [sic])
  669.         move.b D1,D7                ; save the bottom three bits for the BTST
  670.         lsr.l #3,D1                ; while we shift down to a byte address
  671.         move.l D1,A3                ; and save that for the test, too
  672.         not.b D7                ; get right bit number (compute #7-D7)
  673.  
  674.         move.w A6,D1                ; extract log2 of destination stride
  675.         lsl.l D1,D4                ; stride*row number = dest row's offset in bits
  676.         add.l D6,D4                ; add in column bit offset
  677.         add.l A1,D4                ; and base address, also in bits
  678.         move.b D4,D6                ; set aside the bit displacement
  679.         lsr.l #3,D4                ; make a byte displacement
  680.         not.b D6                ; get right bit number (compute #7-D6)
  681.  
  682.         btst D7,(A3)                ; test the D7th bit of source byte
  683.         move.l D4,A3                ; point to target byte (don't ruin CC from btst)
  684.         bne.s NSETON                ; if on, go set destination on
  685.         bclr D6,(A3)                ; else clear destination bit
  686.  
  687. NNEXT                        ; jump here if D0 not in bounds
  688.         lsr.l #1,D0                ; slide one bit to the right
  689.         bhi.s NLOOPROW                ; if no carry out, but not zero, loop
  690.         eor.l D3,D0                ; flip magic bits...
  691.         cmp.l D3,D0                ; ...but has this brought us to square 1?
  692.         bne.s NLOOP                ; if not, loop back; else...
  693.         bra.s DONE                ; ...we're finished
  694.  
  695. NSETON
  696.         bset D6,(A3)                ; source bit was on: set destination on
  697.         lsr.l #1,D0                ; slide one bit to the right
  698.         bhi.s NLOOPROW                ; if no carry out, but not zero, loop
  699.         eor.l D3,D0                ; flip magic bits...
  700.         cmp.l D3,D0                ; ...but has this brought us to square 1?
  701.         bne.s NLOOP                ; if not, loop back; else fall through
  702.         bra.s DONE                ; and finish
  703.  
  704. ;
  705. ; -----------------------------------------------------------------------------------
  706. ;
  707. ; super-special case, which happens to hold for the whole mac screen -- or subsets
  708. ; of it which are as wide as the screen. here, we've found that the shift counts
  709. ; in D2, A5, and A6 can all be collapsed to zero.  and D5 equals A2, so there's
  710. ; no need to check whether D6 is in limits -- or even take it out of D0!  so, this loop
  711. ; is the NLOOP code without the shifts or the check on the column number.  should
  712. ; run like a bat; have you ever seen a bat run?
  713. ;
  714. ; oh, yes, one further restriction -- the addresses in A0 and A1 must point to
  715. ; integral byte addresses with no bit offset.  (this still holds for full-screen
  716. ; copies.)  because both the source and destination are byte-aligned, we can skip
  717. ; the ritual Negation Of The Bit Offset which the 68000 usually demands.
  718.  
  719. SCREEN                        ; here to set up to do the whole screen, or at least its width
  720.         move.l A0,D6                ; take the base source address...
  721.         lsr.l #3,D6                ; ... and make it a byte address
  722.         move.l D6,A0                ; replace pointer
  723.  
  724.         move.l A1,D6                ; now do the same...
  725.         lsr.l #3,D6                ; ...for...
  726.         move.l D6,A1                ; ...the destination address
  727.  
  728.         bra.s N2LOOP                ; jump into loop
  729.  
  730. N2HEAD                        ; here when we shifted and a bit carried out
  731.         eor.l D3,D0                ; flip magic bits to make the sequence work
  732.  
  733. N2LOOP                        ; here for another time around
  734.         cmp.l A4,D0                ; is row in bounds?
  735.         bge.s N2NEXT                ; no: clip this
  736.  
  737. N2LOOPROW                    ; here when we know the row number is OK
  738.         move.l D0,D1                ; copy row number, shifted up, plus column offset
  739.         lsr.l #3,D1                ; while we shift down to a word offset
  740.  
  741.         btst D0,0(A0,D1)            ; test bit of source byte
  742.         bne.s N2SETON                ; if on, go set destination on
  743.         bclr D0,0(A1,D1)            ; else clear destination bit
  744.  
  745. N2NEXT                        ; jump here if D0 not in bounds
  746.         lsr.l #1,D0                ; slide one bit to the right
  747.         bhi.s N2LOOPROW                ; if no carry out, but not zero, loop
  748.         bne.s N2HEAD                ; if carry out, but not zero, loop earlier
  749.         bra.s N2DONE                ; 0 means next sequence element would have been D3
  750.  
  751. N2SETON
  752.         bset D0,0(A1,D1)            ; source bit was on: set destination on
  753.         lsr.l #1,D0                ; slide one bit to the right
  754.         bhi.s N2LOOPROW                ; if no carry out, but not zero, loop
  755.         bne.s N2HEAD                ; if carry out, but not zero, loop earlier
  756.                                         ; zero means the loop has closed on itself
  757.  
  758. ;
  759. ; because our bit-numbering isn't like that of the other two loops, we set up D0 and D1
  760. ; ourselves before joining a bit late with the common code to get the last bit.
  761. ;
  762.  
  763. N2DONE
  764.         move.l (SP)+,A6                ; restore the stack frame pointer
  765.  
  766.         move.w srcOurs+oLbits(A6),D0    ; pick up bit offset of left margin
  767.         move.w dstOurs+oLbits(A6),D1    ; and ditto for target
  768.         bra DONEA                ; go do the first bit, which the sequence doesn't cover
  769.  
  770. ;
  771. ; -----------------------------------------------------------------------------------
  772. ;
  773.  
  774. ; mulchk -- see if we can do without multiply instructions.
  775. ;
  776. ; calling sequence:
  777. ;       A5 holds the source stride
  778. ;       A6 holds the destination stride
  779. ;       clr.w -(SP)                ; reserve room for boolean function return
  780. ;       bsr MULCHK                ; go check things out
  781. ;       tst.w (SP)+                ; test result
  782. ;       bne.s SHIFT                ; if non-zero, we can shift and not multiply
  783. ;
  784. ;       (if we can shift, A5 and A6 have been turned into shift counts)
  785. ;
  786. ; registers used: none  (A5, A6)
  787.  
  788. MULCHK
  789.  
  790.         movem.l D0-D3,-(SP)            ; stack caller's registers
  791.         move.l A5,D0                ; take the source stride
  792.         bsr BITWIDTH                ; take log base 2
  793.         move.l #1,D1                ; pick up a one...
  794.         lsl.l D0,D1                ; ...and try to recreate the stride
  795.         cmp.l A5,D1                ; does it come out the same?
  796.         bne.s NOMULCHK                ; nope -- bag it
  797.         move.w D0,D3                ; save magic logarithm of source stride
  798.  
  799.         move.l A6,D0                ; yes -- now how about destination stride?
  800.         bsr BITWIDTH                ; convert that one, also
  801.         move.l #1,D1                ; again, try a single bit...
  802.         lsl.l D0,D1                ; ...and see if original # was 1 bit
  803.         cmp.l A6,D1                ; how'd it come out?
  804.         bne.s NOMULCHK                ; doesn't match -- bag this
  805.  
  806. ;
  807. ; we can shift instead of multiplying.  change address registers & tell our caller.
  808. ;
  809.         move.w D3,A5                ; set up shift for source stride
  810.         move.w D0,A6                ; and for destination stride
  811.         st 4+16(SP)                ; tell our caller what's what
  812.         bra.s MULRET                ; and return
  813.  
  814. NOMULCHK
  815.  
  816.         sf 4+16(SP)                ; tell caller we can't optimize
  817. MULRET                        ; here to return; result set
  818.         movem.l (SP)+,D0-D3            ; pop some registers
  819.         rts                    ; all set
  820.  
  821. ;
  822. ; -----------------------------------------------------------------------------------
  823. ;
  824. ; table of (longword) masks to XOR in strange Knuthian algorithm.  the first table
  825. ; entry is for a bit-width of two, so the table actually starts two bytes before
  826. ; that.     hardware jocks among you may recognize this scheme as the software analog
  827. ; of a "maximum-length sequence generator".
  828. ;
  829. ; to save a bit of room, masks are packed in bytes, but should be aligned as
  830. ; described in the code before being used.
  831. ;
  832.  
  833. table   .equ *-2                ; first element is #2
  834. .byte   3o                    ; 2
  835. .byte   3o                    ; 3
  836. .byte   3o                    ; 4
  837. .byte   5o                    ; 5
  838. .byte   3o                    ; 6
  839. .byte   3o                    ; 7
  840. .byte   27o                    ; 8
  841. .byte   21o                    ; 9
  842. .byte   11o                    ; 10
  843. .byte   5o                    ; 11
  844. .byte   145o                    ; 12
  845. .byte   33o                    ; 13
  846. .byte   65o                    ; 14
  847. .byte   3o                    ; 15
  848. .byte   55o                    ; 16
  849. .byte   11o                    ; 17
  850. .byte   201o                    ; 18
  851. .byte   71o                    ; 19
  852. .byte   11o                    ; 20
  853. .byte   5o                    ; 21
  854. .byte   3o                    ; 22
  855. .byte   41o                    ; 23
  856. .byte   33o                    ; 24
  857. .byte   11o                    ; 25
  858. .byte   161o                    ; 26
  859. .byte   71o                    ; 27
  860. .byte   11o                    ; 28
  861. .byte   5o                    ; 29
  862. .byte   145o                    ; 30
  863. .byte   11o                    ; 31
  864. .byte   243o                    ; 32
  865. .align 2
  866.  
  867. ;
  868. ; -----------------------------------------------------------------------------------
  869. ;
  870. ; convert -- convert a parameter bitMap and rectangle to our internal form.
  871. ;
  872. ; calling sequence:
  873. ;       lea bitMap,A0                ; point to the bitmap
  874. ;       lea rect,A1                ; and the rectangle inside it
  875. ;       lea ours,A2                ; and our data structure
  876. ;       bsr CONVERT                ; call us
  877. ;
  878. ; when done, all fields of the "ours" structure are filled in:
  879. ;       oBase is the address of the first byte in which any bits are to be changed
  880. ;       oLbits is the number of bits into that first byte which are ignored
  881. ;       oStride is the stride from one row to the next, in bits
  882. ;       oCols is the number of columns in the rectangle
  883. ;       oRows is the number of rows
  884. ;
  885. ; registers used: D0, D1, D2
  886. ;
  887.  
  888. CONVERT
  889.  
  890. ;
  891. ; save the starting word and bit address of the stuff:
  892. ;
  893.        move.w top(A1),D0            ; pick up top of inner rectangle
  894.        sub.w bounds+top(A0),D0            ; figure rows to skip within bitmap
  895.        mulu rowbytes(A0),D0            ; compute bytes to skip (relative offset)
  896.  
  897.        add.l baseaddr(A0),D0            ; find absolute address of first row to use
  898.  
  899.        move.w left(A1),D1            ; pick up left coordinate of inner rect
  900.        sub.w bounds+left(A0),D1            ; find columns to skip
  901.        move.w D1,D2                ; copy that
  902.        and.w #7,D2                ; compute bits to skip in first byte
  903.        move.w D2,oLbits(A2)            ; save that in the structure
  904.  
  905.        lsr.w #3,D1                ; convert column count from bits to bytes
  906.        ext.l D1                    ; convert to a long value, so we can...
  907.        add.l D1,D0                ; add to row start in bitmap to find 1st byte
  908.        move.l D0,oBase(A2)            ; save that in the structure
  909.  
  910. ;
  911. ; save the stride of the bitmap; this is the same as for the original, but in bits.
  912. ;
  913.        move.w rowbytes(A0),D0            ; pick up the stride
  914.        lsl.w #3,D0                ; multiply by eight to get a bit stride
  915.        move.w D0,oStride(A2)            ; stick it in the target structure
  916.  
  917. ;
  918. ; save the number of rows and columns.
  919. ;
  920.         move.w bottom(A1),D0            ; get the bottom of the rectangle
  921.         sub.w top(A1),D0            ; less the top coordinate
  922.         sub.w #1,D0                ; get number of highest row (1st is zero)
  923.         bmi.s CERROR                ; nothing to do?  (note: 0 IS ok)
  924.         move.w D0,oRows(A2);            ; save that in the structure
  925.  
  926.         move.w right(A1),D0            ; get the right edge of the rectangle
  927.         sub.w left(A1),D0            ; less the left coordinate
  928.         sub.w #1,D0                ; make it zero-based
  929.         bmi CERROR                ; nothing to do here?
  930.         move.w D0,oCols(A2)            ; save that in the structure
  931.  
  932. ;
  933. ; all done.  return.
  934. ;
  935.         rts
  936.  
  937. ;
  938. ; error found in CONVERT.  pop return and jump to the error routine, such as it is.
  939. ;
  940. CERROR
  941.         addq.l #4,SP                ; pop four bytes of return address.
  942.         bra.s ERROR                ; return silently
  943.  
  944. ;
  945. ; -----------------------------------------------------------------------------------
  946. ;
  947. ; log2 -- find the ceiling of the log, base 2, of a number.
  948. ; bitwidth -- find how many bits wide a number is
  949. ;
  950. ; calling sequence:
  951. ;       move.l N,D0                ; store the number in D0
  952. ;       bsr LOG2                ; call us
  953. ;       move.w D0,...                ; D0 contains the word result
  954. ;
  955. ; registers used: D2, (D0)
  956. ;
  957.  
  958. BITWIDTH
  959.         sub.l #1,D0                ; so 2**n works right (sigh)
  960. LOG2
  961.         tst.l D0                ; did they pass us a zero?
  962.         beq.s LOGDONE                ; call log2(0) zero -- what the heck...
  963.         beq.s LOGDONE                ; if D0 was one, answer is zero
  964.         move.w #32,D2                ; initialize count
  965. LOG2LP
  966.         lsl.l #1,D0                ; slide bits to the left by one
  967.         dbcs D2,LOG2LP                ; decrement and loop until a bit falls off
  968.  
  969.         move.w D2,D0                ; else save our value where we promised it
  970. LOGDONE                        ; here with final value in D0
  971.         rts                    ; and return
  972.  
  973. .end    ; procedure dissBits
  974.