“Screen Sleep in Assembly”

By Steve Brecher, President, Software Supply, MacTutor Contributing Editor

BASIC Sort

David Smith, Editor of MacTutor, laments, "I wrote an MS BASIC program that sorts an array of some 600 items (names). It takes over an hour! Absurd. It's a simple bubble sort."

Q. How much time can be saved by an alternate sort algorithm in BASIC?

A. The bubble sort is a notoriously poor performer except on very small arrays. Sorting algorithms and their performance are a well-studied subfield of computer science. Two clever algorithms that have become popular outside of academia are ShellSort and QuickSort; I'll discuss QuickSort because I'm more familiar with it.

In its pure form, QuickSort is a simple recursive algorithm that uses a "divide and conquer" technique. Consider the elements of the array to be sorted as laid out horizontally, so we can talk of the left and right portions of the array. If it is the case that (1) some element of the array, called the partitioning element, is already in its final position; (2) all the elements to the left of the partioning element are less than or equal to the partitioning element; and (3) all the elements to the right of it are greater than or equal to it; then all we need to do is to sort the subset of elements to the left of the partitioning element and then sort the subset to the right. Quicksort consists of a simple sub-algorithm to set up the partitioning as specified above, followed by two recursive calls to itself to sort the left and right partitions.

While Quicksort is very simple and a good performer in many cases, it has some drawbacks: recursion is often inefficient or (as in the case of MS BASIC 2.0) not available; and in some instances -- e.g., when the data happen to be already in the proper order before sorting -- Quicksort performance degenerates. (Yes, the original Quicksort routine actually "prefers" randomly-ordered data!) So, improvements have been made -- at the cost of adding some complexity to the algorithm.

The optimized Quicksort algorithm that I have ported to MS BASIC was developed by Robert Sedgewick from C. A. R. Hoare's original algorithm. It makes the following improvements: (1) it uses a more complex partitioning sub-algorithm to enhance performance and avoid worst-case degeneration; (2) it avoids recursion; and (3) it uses a simple algorithm called an insertion sort when the sizes of the left and right subarrays become "small"; the insertion sort is more efficient than Quicksort on small arrays.

The MS BASIC routine, including references to a paper and book by Sedgewick, is shown in Listing 1. The routine takes about a minute to sort 600 strings having an average length of 18.2 characters. The Sort subprogram could be easily adapted to sort a numeric array instead of a string array by removing all occurrances of the "$" character.

TextEdit & Dialogs

Last month, we provided an overview of TextEdit, the Mac's built-in text processing facility. Application programmers are not the only ones to make use of TextEdit facilities; TextEdit is also used by the Dialog Manager to display and handle the editing of text items in dialog boxes. An anonymous caller to MacTutor's offices asked:

Q. How can I change the font size used in dialog editText items? Simply changing the txSize field in the dialog's TERec doesn't seem to work.

A. Changing the value in the txSize field will work -- but the timing is crucial.

To simplify the discussion, let's assume for the moment that we're talking about modal dialogs. Assume that the dialog contains a variety of items including controls and statText items as well as editText items. We want one or more of the editText items to echo the user's keystrokes in a font size other than the default.

We create the dialog with NewDialog or GetNewDialog. At this point the dialog's window and controls are drawn (although they may not be visible if we've made the dialog invisible). None of the other items are drawn at this time; instead an update for the dialog window is generated. Typically, at this point we'd call ModalDialog in a loop, and after each call check the itemHit value to see what we must do to deal with the item. When ModalDialog is first called, it will handle the update event that was generated when the dialog was created, i.e., it will draw the dialog's items.

The Dialog Manager uses TextEdit not only to handle editText items, but also to draw statText items. And it uses only one TERec for all text items in a given dialog, changing the TERec's contents as required as the current item changes. Therefore, if before calling ModalDialog we get the address of the dialog's TERec from the textH handle in the DialogRecord and change the txSize field in the TERec, then all the statText items will be drawn in that size. We'll have achieved our purpose of changing the size of editText key echos, but with an upleasant side effect upon the statText items.

What we should do, then, is to write a filterProc and pass its address to ModalDialog. Our filterProc will be able to inspect each event before ModalDialog acts upon it. If the event is a keyDown (key press), then we can go ahead and change the txSize field in the dialog's TERec. Optionally, before doing so, we can check the editField value in the DialogRecord to see whether we want to change the size in the specific editText item that is current. If we've previously changed the size, but the current editText item is not one for which we want it changed, or the event is not a keyDown, we should change the size back to the default. The default value in the txSize field is 0, so all that's required to undo our change is to clear txSize.

For modeless dialogs, we can change the txSize field just before calling DialogSelect if the event we're passing to DialogSelect is a keyDown. Whatever our filterProc was doing for a modal dialog, for a modeless dialog we can do between calling IsDialogEvent and calling DialogSelect.

Finding a Finder

Another anonymous caller to MacTutor (I'd like to give credit to questioners, but our Editor forgets to take their names) happened to ask questions about Finder and MiniFinder that I'd just been researching on my own behalf. In particular, I was having trouble figuring out how MiniFinder overrides the normal process that occurs when a program quits. Thanks to Bill Steinberg, Sysop of the Mac User's Forum on CompuServe MAUG for pointing out the INIT 4 resource described below (MAUG is a trademark of MCU, Inc.; Bill Steinberg is not a trademark and may be freely abused.)

Q. How does the Mac know to run Finder when an application quits? And if MiniFinder is installed, how does it know to run that instead?

A. There is a system global at address $2E0 called FinderName. It is 16 bytes long, and its contents are interpreted as a Pascal-format string, i.e., length byte followed by characters. Thus, the name stored there can be at most 15 characters long. At boot time the string "Finder" is stored in FinderName.

An application quits by invoking the ExitToShell trap (or by executing an RTS instruction, which invokes ExitToShell indirectly). ExitToShell passes the FinderName address to the Launch routine as a pointer to the name of the application to be launched. As noted, normally that name is "Finder," so Finder is launched.

If a program wants to replace Finder as the default "shell," all it need do is copy the filename of the replacement to FinderName (in Pascal string format). Henceforth, when ExitToShell is executed, the replacement program will be launched. Note that the user will never be able to get back to Finder unless the replacement program gives him a means to do so, either by launching Finder directly or by restoring the contents of FinderName to "Finder."

But, there is an exception to this scheme. The new Finder (4.1) provides an optional Finder replacement of its own, MiniFinder. Apple needed a mechanism to run MiniFinder if it is installed, or Finder if MiniFinder is not installed. What they did was to include an INIT resource (ID 4) in the system file.

An INIT resource is executed once, at system startup. INIT 4 installs a RAM patch to the OpenResFile (open resource file) trap. The patch code looks at the address of the filename that is being passed to OpenResFile. If that address is equal to FinderName, and if MiniFinder is present on the system disk, then the patch replaces the filename address with the address of the name "MiniFinder." The effect is that if MiniFinder is installed, the contents of FinderName is ignored. Note that Launch must do an OpenResFile on the application to be launched.

The net effect of this is that the presence of MiniFinder completely overrides FinderName, and there is no way to replace MiniFinder with an alternate except to remove MiniFinder.

You might have noticed also that when Finder launches an application on a system disk that is not the current system disk, the application disk will become the new system disk. But this is not true of MiniFinder: the disk from which MiniFinder was originally launched remains the system disk even if the application disk has a system on it.

The reason for this is that Finder takes action, before launching the application, to switch systems; but MiniFinder does not do this. Before the launch, Finder checks to see if "System" and "Finder" exist on the application disk (if it's not the current system disk). If they do exist, then Finder closes the current system file (CloseResFile with an argument of 0), changes the contents of global variable BootDrive to reflect the new system disk, and does an InitResources to establish the new system file.

Low-level I/O

This and the following questions are paraphrased from exchanges in which I was involved in the Mac Developer's Forum on CompuServe. This question was occasioned by the sixth paragraph of "Writing Your Own Device Drivers" on p. 25 of the Device Manager section of Inside Macintosh.

Q. Inside Macintosh implies that a device driver must handle asynchronous or immediate requests differently from normal ones. How can the driver deter- mine whether those attributes apply to the I/O request?

A. In fact, the driver does not need to know whether its current request is asynchronous and/or immediate. (But if it did want to know, it could examine the ioTrap field of the parameter block).

First, a brief review of some terminology. An asynchronous I/O request is one that will allow control to be returned to the requesting application before the request has been completed. Compare with a syn- chronous request, which is completely processed before the I/O Manager returns from the trap which issued the request. An asynchronous request is made by setting bit 10 of the trap word; in assembly language this is done by coding ",ASYNC" after the trap macro.

An immediate request is one that will not be put on the device driver's queue of pending requests; instead, it will be given to the driver immediately, ahead of any normal requests that may be in its queue. An immediate request is made by setting bit 9 of the trap word; in assembly language this is done by coding ",IMMED" after the trap macro.

There is an ambiguity in the two uses of the word "asynchronous" at the bottom of p. 25 of the Device Manager section. As I read it, an "asynchronous call" is the result of a trap with the ASYNC bit set; on the other hand, "asynchronous portions of the [driver] routines" are those portions which execute at interrupt level. Hence at a prime, control, or status entry point, all registers are available regardless of whether the trap is ASYNC (assuming that the entry point is not shared by interrupt handling code); conversely, interrupt handling code must preserve registers D4-D7/A4-A7 regardless of what kind of trap initiated the I/O.

On p. 26, IM is wrong in saying that IMMED-invoked routines must return via RTS rather than via IODone. IODone looks at the IMMED bit in the trap word and, if it's set, does not dequeue the request (because it's not on the queue) nor does it check to see if the driver has more work waiting in the queue. If IMMED is set, all IODone does is unlock the driver (make it relocateable) provided that it's not in ROM and its dNeedLock bit is clear.

In short, the driver needn't be concerned with whether the I/O request is asynchronous or immediate; the I/O OS routines those concerns.

Relocateable Code

Q. If I have a data area in my program, such as

Data:  DC.B  'This is some data'

how can I force the MDS assembler to let me use the instruction Move.L #Data,(A1) ? It issues an error message. But I don't want the extra overhead of

Lea      Data,A0
 Move.L A0,(A1)

A. MDS won't assemble absolute (non-relocateable) code. For

       Move.L  #Data,(A1) 

to work, Data would have to be at an absolute address known at assembly time or at link time. But the address of a code segment is not known until the segment is loaded at execution time -- that's a characteristic of the Mac system architecture (not merely of MDS).

If it's any consolation,

        Lea        Data,A0
         Move.L  A0,(A1) 

takes the same amount of memory and the same execution time as what you wanted to do -- the only cost is an additional line of source code.

Length of Relocateable Block

Q. I'm adding to a resource fork of a file using AddResource. How do I tell the Resource Manager the length of the new resource's data?

A. The length is that of the data to which the handle refers, i.e., what would be returned by GetHandleSize. The length of data referred to by a handle is determinable from the contents of Memory Manager data structures. If you're interested in how the Memory Manager keeps track of block lengths, see "Structure of Blocks" starting on p. 20 of the Memory Manager section of Inside Macintosh.

Replacing a File

Q. I'm using SFPutFile in the process of creating a file. If a file of the same name as specified by the user already exists, how do I know? I don't see anything in the sfReply record that would tell me. What am I missing?

A. You're not missing anything. SFPutFile will ask the user to confirm his choice of name if the filename is already in use on the volume, but it doesn't tell your program of that fact. There are several approaches you can use, all with basically the same effect, such as:

(1) Create the file. If you get a dupFNErr code (file already exists), issue a SetEOF call to set the logical end-of-file point to zero.

(2) Delete the file. If you get a fnfErr code (file not found), ignore it. Then create the file.

(3) Issue a GetFileInfo request. If you get a fnfErr code, you know the file doesn't pre-exist.

Putting Screen to Sleep

Darkening the screen while the Mac is powered up but not in use is a good idea; it prevents the screen image from "burning" into the phosphor coating.

Q. I'm writing a 'screensaver" routine to black out the screen after a period of inactivity. After saving the current grafPort and opening my own, I set the bkPat to black and do an EraseRect on the portRect. That works ok to blank out the screen; but restoring the previous grafPort doesn't restore the previous screen image. How can I restore it?

A. To get the old display back again, you have to use Window Manager facilities to update the desktop and windows, and DrawMenuBar to refresh the menu bar. Listing 2 shows an MDS Assembler routine that puts the screen "to sleep" with a randomly moving Apple symbol until the mouse is clicked or a key is pressed.

QuickDraw Globals

Q. I'm having trouble locating the QuickDraw global variables in assembler. Where are they?

A. Assuming that your program has initialized QuickDraw in the conventional manner, i.e.,

Pea -4(A5)
  _InitGraf

then A5 contains a pointer to the address of the "first" field of the QuickDraw global area. Another way to think of it is that A5 is a "handle" to the QuickDraw globals in the sense of a pointer to a pointer (but not in the strict Memory Manager sense). After

        Move.L  (A5),A0 

A0 contains the address of the "first" field in the QuickDraw global area. I put "first" in quotes because it's the first field (namely, thePort) as listed in Inside Macintosh, QuickDraw section p. 34; but with respect to order in memory, it's last (highest address). In other words, after executing the above instruction, the following would hold:

Move.L (A0),A1 ;A1 contains address of
                         ;the current grafPort
Lea -8(A0),A1   ;A1 contains address of
                         ;white pattern
Lea -16(A0),A1 ;A1 contains address of
                         ;black pattern
...etc.

Listing 1
; SCREEEN_SLEEP
;© by Steve Brecher for MacTutor 1985
;
; Darkens the screen except for a randomly-moving Apple ;symbol. Returns 
when the mouse button is pushed or when a ;key is pressed.   The mouse 
click or keypress event is ;removed from the event queue.
;
; D0/D1/D2/A0/A1 are destroyed; other registers are ;preserved.
;
 Include MDS:MacTraps.D
 Include MDS:SysEqu.D
 Include MDS:ToolEqu.D
 Include MDS:QuickEqu.D

 XDEF Sleep

mDownMask   Equ  2      ;Equate files missing these...
keyDownMask Equ  8

    Macro   Pop Dest =
    Move    (SP)+,{Dest}
    |
    Macro   Pop.L Dest =
      Move.L   (SP)+,{Dest}
    |
    Macro   Push Src =
      Move     {Src},-(SP)
    |
    Macro   Push.L Src =
      Move.L   {Src},-(SP)
    |

Sleep
 Push.L   A2       ;save
 _HideCursor     ;sleepy screens show no                       ;cursors
 SubQ     #4,SP    ;space to store old grafPort                
 ;address
 Push.L   SP       ;pass address of space to                   
 ;_GetPort
 _GetPort        ;get the old grafPort addr  MoveQ       #portRec,D0 
 ;size of a grafPort record
 _NewHandle      ;allocate on heap
 _Hlock          ;bolt it down
 Move.L  (A0),A2 ;get pointer from handle
 Push.L   A0       ;save handle for later
 Push.L   A2
 _OpenPort       ;default values to grafPort,                  
 ;make it current
 Pea     portRect(A2)
 _PaintRect      ;paint with default fillPat =                 
 ;black
 Bsr.S    RandApple  ;move an Apple around 'til                
 ;click or key
 Pop.L    A0       ;handle to our grafPort
 _DisposHandle   ;bye, grafPort
 _DrawMenuBar    ;restore the menu bar
 Clr.L    -(SP)    ;indicate desktop to PaintOne
 Push.L   GrayRgn  ;the region to be painted =                 
 ;whole desktop
 _PaintOne       ;repaint the desktop
 SubQ     #4,SP    ;space for FrontWindow result
 _FrontWindow    ;get parameter for  ;PaintBehind
 Push.L   GrayRgn  ;clobbered region = whole                   
 ;desktop
 _PaintBehind    ;repaint windows (if any)
 _ShowCursor     ;wake up cursor
 _SetPort        ;restore previous grafPort                    ;from 
stack
 Pop.L    A2       ;restore register
Rts

; Bop an Apple symbol randomly about the screen, moving it 
; once a second.  A2 is presumed to have the address of the 
; current grafPort, with full-screen bounds.  Note that the 
; Apple's bottom will rest on the character baseline (where 
; _MoveTo puts the pen) and its left edge will be at the pen 
; position.  To avoid clipped Apples we keep the pen position at ; least 
an "Apple-height" below the top and at least an 
; "Apple-width" from the right edge.  We get the width with 
; _Charwidth, and assume height=width.
;

RandApple
 MoveM.L  D3/D4,-(SP)
 Link     A6,#-evtBlkSize ;allocate space for local            
 ;EventRcd
 Move     #srcXor,txMode(A2) ;drawing a char will invert
 Clr.L    -(SP)    ;word for width, with 0 word                
 ;underneath
 Push     #appleMark ;char code for bitten apple
 _CharWidth      ;(SP) hi word = Apple width (&                
 ;approx height)
@0 SubQ     #2,SP
 _Random
 MoveQ    #0,D3    ;to get upper word of D3 clear
 Pop      D3       ;D3.L has a random 16-bit                   
 ;value
 Move     portRect+bottom(A2),D0 ;height of screen
 Sub      (SP),D0  ;less approx height of Apple                
 ;(it's sorta square)
 Divu     D0,D3    ;divide by height of allowable              
 ;pen range
 Add.L    (SP),D3  ;add Apple height to                        ;remainder 
in high word
 SubQ     #2,SP    ;now similar logic for                      ;horizontal 
coordinate...
 _Random
 MoveQ    #0,D1
 Pop      D1
 Move     portRect+right(A2),D0
 Sub      (SP),D0 ;keep pen at least ;Apple-width from right edge
 Divu     D0,D1
 Swap     D1       ;get remainder in low word
 Move     D1,D3    ;D3 hi = vertical, D3 lo =                  
 ;horizontal
 Push.L   D3       ;pass coordinates to                        ;MoveTo...
 _MoveTo         ;position pen to  draw the                    ;apple
 MoveQ   #60,D4  ;one second worth of ticks...
 Add.L    Ticks,D4 ;+ current time, get ending                 
 ;time
 Push     #appleMark
 _DrawChar       ;draw the apple (note: moves                  
 ;pen)
@1 Lea      -evtBlkSize(A6),A0
 MoveQ    #mDownMask!keyDownMask,D0
 _GetOSEvent     ;mouse click or keypress?
 Beq.S    @2     ;branch if so, our cue to exit
 Cmp.L    Ticks,D4 ;time to move the apple?
 Bhi.S    @1     ;branch if not
 Push.L   D3     ;yes, reposition (do a                        ;"backspace")...
 _MoveTo           ;...back to where the apple                 
 ;was drawn
 Push     #appleMark
 _DrawChar       ;redraw to erase (srcXor)
 Bra.S    @0     ;go find another spot for the                 
 ;apple
@2 Unlk     A6
 MoveM.L  (SP)+,D3/D4
Rts

Listing 2
REM Set up test data for Sort routine; do a timed call
REM and verify that routine worked.
    DIM Test$(599)  ' 600 strings
    TotLen = 0
    FOR I% = 0 TO 599
        Test$(I%) = STR$(RND)
        TotLen = TotLen + LEN(Test$(I%))
    NEXT
    PRINT USING "Average length of the 600 strings 
            is ##.#";TotLen/600
    PRINT "Sorting..."
    Start = TIMER
    CALL Sort(Test$())
    PRINT "Sort took";TIMER-Start;"seconds; checking 
            correctness..."
    FOR I% = 0 TO 598
        IF TEST$(I%) > TEST$(I%+1) THEN PRINT "Oops, didn't
               work!" : END
    NEXT
    PRINT "It worked!"
    END
REM ---------------Sort Subprogram follows---------------------
REM
    SUB Sort(S$(1)) STATIC
REM
REM Optimized Quicksort subprogram to sort
REM an array of strings into ascending order.
REM Algorithm adapted from:
REM Sedgewick, Com. of the ACM, V21 N10, Oct. 1978
REM and corrigendum, V22 N6, Jun. 1979
REM Also see Chapter 9 of Sedgewick, "Algorithms",
REM Addison-Wesley, 1983, ISBN 0-201-6672-6
REM
REM Rather than use recursion, use a stack of array 
REM   partitions --
REM The "Dimmed" kludge seems to be required to get 
REM   a truly local array
REM in a SUB that may be called more than once:
    IF NOT Dimmed THEN DIM Stack%(15,2)  
               ' 15 handles 32,768 elements
    Dimmed = 1
REM
REM Sedgewick's "M" parameter, which determines when to 
REM  stop Quicksorting and
REM finish up with an insertion sort on entire 
REM  array (an optimization):
    Insertion% = 10
REM
    L% = LBOUND(S$)  ' "left" subscript
    R% = UBOUND(S$)  ' "right" subscript
    IF L% = R% THEN EXIT SUB ' One element is easy to sort!
    IF R% - L% < Insertion% THEN GOTO InsertionSort
    StackPtr% = 0
REM Initialize for partitioning the subarray such 
REM  that the partitioning
REM element S$(L%) is the median of:  old S$(L%), 
REM  S$(Middle%), S$(R%)
PartInit:
    Middle% = (L%+R%) / 2
REM Lines beginning with "Temp$ =" are exchanges of
REM   array elements
    Temp$ = S$(Middle%) : S$(Middle%) = S$(L%) 
     S$(L%) = Temp$
    IF S$(L%+1) <= S$(R%) THEN GOTO P2
    Temp$ = S$(L%+1) : S$(L%+1) = S$(R%) : S$(R%) = Temp$
P2:
    IF S$(L%) <= S$(R%) THEN GOTO P3
    Temp$ = S$(L%) : S$(L%) = S$(R%) : S$(R%) = Temp$
P3:
    IF S$(L%+1) <= S$(L%) THEN GOTO Partition
    Temp$ = S$(L%+1) : S$(L%+1) = S$(L%) : S$(L%) = Temp$
Partition:
    I% = L%+1
    J% = R%
    Partitioner$ = S$(L%)
IncI:
    I% = I% + 1
    IF Partitioner$ >= S$(I%) THEN GOTO IncI
DecJ:
    J% = J% - 1
    IF S$(J%) > Partitioner$ THEN GOTO DecJ
    IF I% >= J% THEN GOTO GotIJ
    Temp$ = S$(I%) : S$(I%) = S$(J%) : S$(J%) = Temp$
    GOTO IncI
GotIJ:
    S$(L%) = S$(J%)
    S$(J%) = Partitioner$
REM Determine what to do next depending on relative and 
REM absolute sizes of subarrays
    NL% = J% - L%          ' size of left subarray
    NRM1% = R% - I%     ' (size of right subarray) - 1
    IF NL% > NRM1% THEN GOTO BigLeft
REM Right subarray is larger
    IF NRM1% < Insertion% THEN GOTO CheckStack
    IF NL% > Insertion% THEN GOTO LeftNext
REM Partition right subarray next
    L% = I%
    GOTO PartInit
REM Left subarray is larger (or equal)
BigLeft:
    IF NL% <= Insertion% THEN GOTO CheckStack
    IF NRM1% >= Insertion% THEN GOTO RightNext
    R% = J% - 1
    GOTO PartInit
REM "Push" right subarray, partition left subarray next
LeftNext:
    StackPtr% = StackPtr% + 1
    Stack%(StackPtr%,1) = I%
    Stack%(StackPtr%,2) = R%
    R% = J% - 1
    GOTO PartInit
REM "Push" left subarray, partition right subarray next
RightNext:
    StackPtr% = StackPtr% + 1
    Stack%(StackPtr%,1) = L%
    Stack%(StackPtr%,2) = J% - 1
    L% = I%
    GOTO PartInit
REM If stack not empty, pop and partition; else finish
REM   with insertion sort
CheckStack:
    IF StackPtr% = 0 GOTO InsertionSort
REM Pop subarray specifier stack into L%, R%
    L% = Stack%(StackPtr%, 1)
    R% = Stack%(StackPtr%, 2)
    StackPtr% = StackPtr% - 1
    GOTO PartInit
REM
REM Insertion sort on entire array
REM
InsertionSort:
    FOR I% = UBOUND(S$)-1 TO LBOUND(S$) STEP -1
        IF S$(I%+1) > S$(I%) THEN GOTO Loop
        Work$ = S$(I%)
        J% = I% + 1
Slide: S$(J%-1) = S$(J%)
        J% = J% + 1
        IF J% <= UBOUND(S$) THEN IF Work$ >= S$(J%) 
                THEN GOTO Slide
        S$(J%-1) = Work$
Loop: NEXT
    END SUB
REM------------End of Sort subprogram------------