Related Info: Quickdraw Color Quickdraw

No Filthy PICTs For Hashers

By Martin Minow, Arlington, MA

Introduction

I’m a hasher. No, not illegal drugs, but rather a more honorable habit: I’m a member of the Hash House Harriers, sometimes called “a drinking club with a running problem” and “the Hell’s Angels of jogging.” The Hash started over 50 years ago in Kuala Lumpur and we may be the world’s largest running club (we’re certainly the world’s most disorganized).

When I made the mistake of showing up late for our annual meeting, I found to my horror that I’d been chosen editor of our newsletter. I accepted, realizing that it is perhaps not a coincidence that one of the definitions for “hash” in the Oxford English Dictionary is “waste paper of the lowest quality” -- you will not mistake the Boston Hash Trash for Sports Illustrated; you probably won’t mistake it for MacTutor, either.

Well, I scouted out my new empire and discovered that our club’s logo had gone through the copier far too many times. In fact, the best copy I could find of the logo was on a 6-year old t-shirt.

So, I digitized the t-shirt -- what would you do? Unfortunately, the digitized picture had a lot of background noise: squashed mosquitos, lint, and dried runner’s drool. A long evening with a drawing program’s Erase tool gave me something I could use for the newsletter (the Hash does not have high standards). However, I didn’t want to spend the rest of my life taking little bits of filth out of that drawing and decided that writing a noise-removal application would give me a better-looking logo than my friends deserved.

Actually, the problem turned out to be fairly interesting. The application reads a black-and-white 300 dpi image from a PICT file, removes (oh so slowly) small blobs of pixels and writes a cleaned PICT file. While it isn’t a complete application -- no scrolling, no printing, 300 dpi black and white image only -- it did exactly what I needed, even if the original implementation required over an hour on a Mac SE to clean the logo.

The Application

The application is straight-forward: when the user opens a PICT file, it creates a new window and reads the picture into an associated offscreen GrafPort. The function that does this is in the file ReadPict.c while the GrafPort’s creator, taken from Macintosh Tech Note 41 without too much change, is in OffscreenGrafPort.c.

I used code from Tech Note 154 to write the PICT reader. It works by substituting a private procedure for the function QuickDraw uses to access the contents of a PICT resource. My function just reads the information from the input file. This worked fine, except for one tiny problem: the t-shirt was digitized at 300 dpi but the picture frame assumed a 72 dpi (screen resolution) universe. When my program read the data, it threw away a lot of information.

The trick is to create the offscreen bitmap 4 times as large as the original file. (This isn’t a real solution: to do this properly, you must examine the contents of the PICT file to determine the actual dimensions. I didn’t have to figure out how to do this, so you’ll have to solve that problem if you want this to be a general application.)

After reading the picture, the user can set the threshold and start the cleanup process. When it completes, the application writes the picture into a PICT file. You can then use a drawing program to touch-up the picture. CleanPICT took care of the small fluff so you can use your judgement to remove larger clumps.

Figure 1 shows the result of applying the CleanPict algorithm to a small piece of the club logo:

Figure 1. Before & After

The Cleanup Algorithm

The cleanup algorithm itself is defined in file CleanPICT.c. It has two parts: a top-level that skips over continuous runs of the same color (CleanPICT removes black spots from a white background, and white dropouts from a black area) and a recursive routine that examines an island starting at a particular point. When the top-level spots a transition between black and white, it checks whether it’s processed this pixel already and, if not, calls the do_pixel() subroutine that does all the work. Note that the Macintosh Toolbox SeedFill function cannot be used as this program must also handle islands of background pixels entirely surrounded by foreground.

do_pixel() is a recursive function that implements a classic “maze-solution” algorithm. Remember, it’s looking for an island of black pixels completely surrounded by a white background (or vice-versa). If the island is too large, it is not a suitable candidate for removal. The algorithm then is merely:

1. If we’re tracing a long-skinny island, we might have fallen off the edge of the island array. If so, return FALSE: this can’t be an island.

2. If we’ve seen this location already, we’ve already marked this pixel as part of the island: just return TRUE to the caller to look at other pixels.

3. Make sure the pixel is inside the picture rectangle. If not, return FALSE: this can’t be an island. This test would not be needed if we could be certain that the entire picture was bordered by a one-pixel frame in the background color.

4. Finally, look at the pixel itself. If it is not the island color, we’re looking at background. We’ve reached the edge of the island: return TRUE to look at other pixels.

5. Otherwise, this pixel is part of the island. Mark it in the island map and increment the area of the of this island. If we’ve exceeded the threshold, fail: the island is too big.

6. We’ve just extended the island. Call do_pixel() recursively to look at this pixel’s four neighbors (East, South, West, and North). If any recursive call fails, this cannot be an island. Note that the program looks forward and down in the picture first so it fails quickly when we’re just to the left of a large area (remember, the outer quick-scan loop goes from left to right). Return TRUE if all recursive calls succeed; return FALSE if any fail.

7. If the top-level call to do_pixel() succeeds, this is an island that is smaller than the user’s threshold. Call a procedure to erase it.

That’s all there is to CleanPICT. If you understood that, you join a small, select, group that does not include the MacTutor editorial staff, so here’s a sample run through the code [we understood it, but felt an example with figures would help.-ed]: We start with this blob:

The “top-level” code zips along until it encounters a transition from white (background) to black (a possible island) and calls the recursive “search” procedure with the current pixel pointing to :

The process then follows the six steps of the algorithm as outlined above:

1. Did we fall off of the island? No, so continue.

2. Have we been here already? No, so continue.

3. Are we still inside the PICT rectangle? Yes, so continue.

4. Is this an island pixel? Yes, so continue.

5. Mark this island pixel in the “found” map and increment the threshold counter. As we haven’t exceeded the threshold, continue. If we exceed the threshold, return FALSE to fail.

6. Now, call do_pixel() for the pixel to the East of . If it succeeds, call for the pixel to the South, then West, then North. If any of these subroutine calls fail, then return failure. If all succeed, then return success. The first recursive call looks to the East and examines pixel ¡.

When do_pixel() is called at ¡, it sees that this is not part of the island and returns TRUE. The previous instance of do_pixel() then continues with the pixel South of at ½:

The calls continue, examining and reexamining the pixels. Eventually, all calls succeed and the top-level (called at ) succeeds. The “seen map” then identifies the entire island. Note that some pixels are examined more than once. For example, the instance of do_pixel() centered on island pixel ½ examines the original pixel . The pixels (island and background) are examined in the following order:

The call from examines ¡, ½, «, and »; while the call of do_pixel() centered on ½ examines , ƒ, , and º. (Note that º. is actually and the algorithm exits with success as this pixel has already been seen.)

If you’ve never worked with recursive algorithms before, you might want to trace through a small example -- say only one or two pixels -- so you can see that the algorithm always terminates. You might find it interesting to see how many times the same pixel is re-examined: can you speed up do_pixel() by fiddling with the algorithm to prevent these expensive subroutine calls? Can you speed it up significantly by a different algorithm, perhaps the region-based technique described in MacTutor Vol. 3, No. 10 (reprinted in The Essential MacTutor) or by basing a search routine on the Mac Toolbox SeedFill function?

The rest of the program is the usual Macintosh stuff; some of which might prove useful. If you collect snibbits of code, you might want to look at the following:

• Code in ReadPICT.c that reads, writes, and scales the picture so it appears on-screen in the correct proportion.

• A simple animated cursor that flashes during processing.

• Code scattered between the main program and the top-level of the picture cleaner that allows the application to co-exist with the rest of the Macintosh. You don’t want to copy the code, but rather the design philosophy.

Get it Right, then Make it Fast

After finishing the program and article, I passed a copy to Mike Morton, who has written a number of articles for MacTutor on graphics programming. He was kind enough to mess with the algorithm (keeping copious notes about performance). The results were interesting: by making a few fairly small changes to the program, the pixel cleaner went from 2.6 msec./pixel to 1.8 msec./pixel (for all pixels that used the recursive algorithm). Mike suggested a number of changes, but I only implemented three:

• The program must check that the pixel indexes are within the dimensions of the vector used to check whether pixels have been seen. The original check was

 (x >= (-XMID) && x < XMID)

Mike’s change was

   if (((unsigned) (x + XMID)) < (2 * XMID))

Casting the value to unsigned and comparing against twice the limit trades addition by a constant against a comparison and branch, giving a 2% improvement in performance.

• A much bigger win (Mike found a 60% improvement) came from replacing calls to the Macintosh bit-manipulation routines by hand-coded assembly-language functions. On my Mac-SE, using the internal routines caused the program to run about 28% faster than when it used the toolbox routines.

• Another big win (14%, according to Mike) came from minimizing screen updates. Instead of repainting the screen each time a pixel island was erased, the program builds an update region and forces an update event after every tenth change. On my system, updating after ten changes caused the program to run about 10% faster then updating after every change.

The combination of these two changes resulted in the program running about 40% faster. Compiling the program with built-in floating-point (68020/68881) gave an additional 10% speedup.

As the section title indicates; you shouldn’t do this sort of optimization until the program itself works. It is also wise to instrument your programs so you don’t put lots of work into improving the 99% of the code that doesn’t affect performance.

Acknowledgements

Thanks to several good folk on Usenet who explained to me how to read a 300 dpi picture into an offscreen bitmap without losing data and the nice people at Apple who write TechNotes. Thanks, especially, to Mike Morton for vetting the article and showing how I could make it run almost twice as fast.

Thanks also to my good friends in the Boston Hash House Harriers, without whose help this program would not have been necessary. If you’re in the neighborhood, join us for a run. Remember: if you have half a mind to run with the hash; well, that’s all it takes.

On On.

Listing:  CleanPICT.h

/* CleanPICT.h   */
/*
 * Common definitions for CleanPICT
 */
#define NIL ((void *) 0)
#include “OffscreenGrafPort.h”
#define width(r) ((r).right - (r).left)
#define height(r)((r).bottom - (r).top)

/*
 * MAGIC converts between the PICT bitmap (which is at
 * 300 dpi) and the screen at 72 dpi.  This should be
 * determined by examining the actual input file so
 * we can handle 72 dpi PICT’s too.
 *
 * Note: this is specific to the actual picture -- for
 * some pictures, you don’t want this.  If you are
 * trying to clean a picture and nothing seems to be
 * happening, you might try either changing MAGIC to one
 * or try multiplying the threshold by four.
 */
#define MAGIC    4
/*
 * XMAX and YMAX dimension the bit-array that marks
 * the island.  These values should be about twice
 * the size of the largest expected threshold.
 * In any case (XMAX * YMAX) must not exceed 32767.
 * By making XMAX and YMAX powers of two, we can
 * replace multiplies by shifts for a significant
 * speed-up.  If max is too high, the program will
 * run slower (due to the time needed to empty the
 * seen map); if too small, some long thin islands
 * won’t be removed.
 */
#define LOG_XMAX  5
#define LOG_YMAX  5
#define XMAX(1 << LOG_XMAX) 
 /* Maximum  pixels*/
#define YMAX(1 << LOG_YMAX)
 /* Maximum  pixels*/
#define THRESHOLD8 
 /* Default threshold*/

typedef unsigned longUlong;

/*
 * State controls the interaction between the
 * pixel cleaner and the event loop.
 */
enum State {
 Idle = 0,/* Must be zero */
 Init,  /* Initialize a new cleaning */
 Working/* Cleaning is in progress */
};

/*
 * All the information about a document is stored here.
 * Note that, when the toolbox selects a window, we can
 * immediately recover the document.  This lets us work
 * on multiple documents, which is probably useless
 * even though it’s easy to do.
 */
typedef struct {
 WindowRecord  window; /* Watch process here */
 GrafPtrpictPort; /* The PICT itself */
 Rect   pictSize; /* The picture’s bounds */
 enum State state; /* What’s up, DOC? */
 short  threshold; /* Island threshold */
 Booleandirty; /* TRUE if need write */
 Str255 fileName; /* PICT’s file name */
 /*
  * The count variable is incremented whenever an island
  * point is seen.  If it exceeds threshold, this is
  * not an erasable island.
  */
 short  count;
 /*
  * The center variable defines the point currently
  * being examined as a potential island.  This variable
  * is in the DOC.pictPort coordinate space.
  */
 Point  center;
 /*
  * These two values define the bottom of the PICT:
  * we don’t look at the last row or column.  These
  * probably should be Ulong’s
  */
 short  bottom;
 short  right;
 /*
  * The island variable defines the “color” we’re looking
  * for: this needs some work to handle color PICT’s.
  */
 Booleanisland;
 /*
  * The updateRect tracks the pixels that need to be
  * changed on screen.  updateCount is used to determine
  * when to force an update.
  */
 RgnHandle thisUpdateRgn; /* The current island */
 RgnHandle updateRgn;/* This needs updating */
 short updateCount;/* When this overflows */
 /*
  * Here are some statistics for user-friendlyness.
  */
 Ulong examined; /* Points closely watched   */
 Ulong found; /* Islands erased    */
 Ulong start; /* When cleaning started */
 Ulong elapsed; /* Elapsed seconds */
 Ulong elapsed_shown;/* On about window*/
} DocumentRecord, *DocumentPtr;

/*
 * The current window is always stored in a local
 * WindowPtr variable named “window.”  If it’s ours,
 * we can access the document by casting window to
 * DocumentPtr and de-referencing it.
 */
#define DOC (*((DocumentPtr) window))

void    clean_picture(WindowPtr, Boolean);
OSErr   read_picture(WindowPtr, int);
void    update_picture(WindowPtr);
void    write_picture(WindowPtr, int);
void    make_about_window(WindowPtr);

#define pstrcpy(out, in) \
 BlockMove((in), (out), ((unsigned char *)(in))[0] + 1)
void    pstrcat(void *, void *);
#define WATCH_CURSOR SetCursor(*GetCursor(watchCursor))
#define ARROW_CURSOR SetCursor(&arrow)

Listing:  CleanMain.c

/*  CleanMain.c    */
/*
 * Copyright © 1989, 1990 Martin Minow and MacTutor.
 *
 * You may use this software in any application and
 * redistribute this source without restriction as long
 * as this copyright and permission notice remains intact
 * and the source is not redistributed for profit and you
 * assume all responsibility for the proper operation of
 * this software.
 *
 * Written in Think C.  Set Tabs every 2 characters.
 *
 * Operation:
 * CleanPICT can read a digitized image stored in a PICT
 * file (black and white at 300 dpi only) into a work
 * area.  It then examines the picture for noise (islands
 * of pixels completely surrounded by the other color)
 * that are smaller than a selectable threshold. It can
 * then write the cleaned image to a file.  Note that it
 * can eliminate islands of white pixels enclosed by the
 * black image, as well as islands of black pixels on
 * the white background.
 *
 * Limitations:
 * CleanPICT was developed to clean out one specific
 * image (a 300 dpi scanned image).  It is extremely slow
 * (that PICT requires over an hour on a Mac SE).
 * CleanPICT keeps the entire PICT in memory, and
 * consequently needs a 1,200 K partition.  It requires
 * a 4 Mb computer when run under Multifinder with the
 * Think C debugger.
 *
 * Homework assignment:
 * Generalize to arbitrary PICTs (72 dpi resolution, etc.)
 * Generalize to color.
 * Speed up.
 * Use a work file to minimize memory requirement.
 */

#include “CleanPICT.h”

/*
 * Menu organization
 */
enum Menus {
 MENU_Apple = 1,
 MENU_File= 256,
 MENU_Edit= 257
};

enum Apple_Menu {
 Apple_About = 1
};

enum File_Menu {
 File_Open= 1,
 File_Clean,
 File_Set,
 File_Close,
 File_SaveAs,
 File_Debug,
 Unused,
  File_Quit
};

enum Edit_Menu {
 Edit_Undo,
 Edit_Unused,
 Edit_Cut,
 Edit_Copy,
 Edit_Paste,
 Edit_Clear
};

/*
 * Various stuff in the resource file.
 */
enum {
 WIND_About = 1000,
 DLOG_Set_Threshold = 1000,
 ALRT_Advise = 2000,
 CURS_Spin = 2000,
 STRS_Info = 1
};

/*
 * Dialog and Alert item lists.
 */
enum { /* DLOG_Set_Threshold */
 Thresh_OK = 1,
 Thresh_Cancel,
 Thresh_Text,
 Thresh_Value
};

enum { /* ALRT_Advise */
 Advise_Save = 1,
 Advise_Discard,
 Advise_Cancel
};

/*
 * isOurWindow is TRUE if its argument is our document.
 * isAboutWindow is TRUE if its argument is the progress
 * window.
 */
#define isOurWindow(window) ( \
 (window) != NIL \
 && ((WindowPeek) (window))->windowKind == userKind \
 && (window) != aboutWindow \
  )
#define isAboutWindow(window) ( \
 (window) != NIL && (window) == aboutWindow \
 )

MenuHandleappleMenu;
MenuHandlefileMenu;
MenuHandleeditMenu;
WindowPtr aboutWindow;
CursHandlespinCursor[2];

void    main(void);
Boolean do_mouse(EventRecord);
void    do_command(long);
void    adjust_menus(WindowPtr);
void    adjust_edit_menu(Boolean);
Boolean handle_events(void);
void    do_command(long);
void    setup(void);
void    do_about(void);
void    open_document(void);
WindowPtr new_document(Str255);
Boolean close_document(WindowPtr);
void    save_document(WindowPtr);
void    set_threshold(WindowPtr);
void    spin_cursor(void);
void    show_progress(WindowPtr);
void    display_statistics(WindowPtr, Boolean);

/*
 * main()
 * Initialize the program and run the event loop.
 */
void main()
{
 EventRecord event;
 WindowPtr window;
 GrafPtr save_port;
 Rect  box;
 long choice;
 Boolean quitNow;/* <CMD>. seen */

 setup();
 quitNow = FALSE;
 for (;;) {
 SystemTask();
 while (GetNextEvent(everyEvent, &event)
  && event.what != nullEvent) {
 if (event.what == activateEvt
  || event.what == updateEvt)
   window = (WindowPtr) event.message;
 else {
 window = FrontWindow();
 }
 switch (event.what) {
 case mouseDown:
 do_mouse(event);
 break;
 case activateEvt:
 if (isOurWindow(window) && aboutWindow != NIL)
 SetWRefCon(aboutWindow, window);
 break;
 case updateEvt:
 GetPort(&save_port);
 SetPort(window);
 BeginUpdate(window);
 if (!EmptyRgn((*window).visRgn)) {
 EraseRect(&window->portRect);
 if (isOurWindow(window)) {
 /*
  * Note that this must track the screen
  * display procedure in invert_seen_map().
  */
 CopyOSGrafPort(
 DOC.pictPort, window, window->visRgn);
 }
 else if (isAboutWindow(window))
 display_statistics(window, TRUE);
 }
 EndUpdate(window);
 SetPort(save_port);
 break;
 case keyDown:
 if ((event.message & charCodeMask) == ‘.’
  && (event.modifiers & cmdKey) != 0) {
   FlushEvents(keyDown | autoKey, 0);
   quitNow = TRUE;
 ARROW_CURSOR;
 }
 else if ((event.modifiers & cmdKey) != 0) {
 if (event.what == keyDown) {
 choice = MenuKey(
 event.message & charCodeMask);
 if (HiWord(choice) != 0)
 do_command(choice);
 else {
 SysBeep(10);  /* Bogus <cmd> */
 }
 }
 }
 break;
 default:
 break;
 }
 }
 /*
  * We do the actual cleaning when the
  * machine is otherwise idle.
  */
 window = FrontWindow();
 if (isAboutWindow(window))
 window = (WindowPtr) GetWRefCon(window);
 if (isOurWindow(window)) {
 clean_picture(window, quitNow);
 if (DOC.state == Working) {
 if (aboutWindow != NIL)
 display_statistics(aboutWindow, FALSE);
 spin_cursor();
 show_progress(window);
 }
 else {
 quitNow = FALSE;
 }
 }
 }
}

/*
 * do_mouse(event)
 * Process a mouse button press, calling handlers as
 * needed.
 */
static Boolean do_mouse(event)
EventRecord event;
{
 WindowPtrwindow;
 register int  which_part;
 Rect   box;
 
 which_part = FindWindow(event.where, &window);
 if (which_part == inMenuBar
  && isOurWindow(window) == FALSE)
 window = FrontWindow();
 adjust_menus(window);
 switch (which_part) {
 case inDesk:
 SysBeep(2);
 break;
 case inMenuBar:
 ARROW_CURSOR;
 do_command(MenuSelect(event.where));
 break;
 case inDrag:
 box = screenBits.bounds;
 box.top += GetMBarHeight();
 InsetRect(&box, 4, 4);
 DragWindow(window, event.where, &box);
 break;
 case inContent:
 if (FrontWindow() != window)
 SelectWindow(window);
 else {
 SetPort(window);
 }
 break;
 case inGoAway:
 if (isOurWindow(window)
  && TrackGoAway(window, event.where)) {
 close_document(window);
 if (aboutWindow != NIL)
 SetWRefCon(aboutWindow, NIL);
 }
 else if (isAboutWindow(window)
  && TrackGoAway(window, event.where)) {
   DisposeWindow(window);
   aboutWindow = NIL;
 }
 break;
 }
 return (FALSE);
}

/*
 * do_command()
 * Process a menu command.
 */
void do_command(choice)
long    choice;
{
 WindowPtrwindow;
 int    item;
 long   new;
 GrafPtrsave_port;
 Str255 name;

 window = FrontWindow();
 item = LoWord(choice);
 switch (HiWord(choice)) {
 case MENU_Apple:
 GetItem(appleMenu, item, &name);
 if (item == Apple_About)
 make_about_window(window);
 else {
 adjust_edit_menu(TRUE);
 GetPort(&save_port);
 OpenDeskAcc(name);
 SetPort(save_port);
 adjust_edit_menu(FALSE);
 }
 break;
 case MENU_File:
 if (isAboutWindow(window))
 window = (WindowPtr) GetWRefCon(window);
 switch (item) {
 case File_Open: open_document();  break;
 case File_Clean:
 if (isOurWindow(window) && DOC.state == Idle)
 DOC.state = Init;
 break;
 case File_Close:close_document(window);
 break;
 case File_Set:  set_threshold(window);
 break;
 case File_SaveAs:
 if (isOurWindow(window) == FALSE
  || DOC.state != Idle)
 SysBeep(10);
 else {
 save_document(window);
 }
 break;
 case File_Debug:Debugger();
 break;
 case File_Quit:
 /*
  * A motion to adjourn is always in order.
  */
 while (isOurWindow(window)) {
 if (close_document(window) == FALSE)
 goto no_exit;
 window = FrontWindow();
 }
 ExitToShell();
no_exit:break;
 }
 default:
 break;
 }
 HiliteMenu(0);
}

void make_about_window(window)
WindowPtr window;
{
 if (aboutWindow == NIL) {
 aboutWindow =
 GetNewWindow(WIND_About, NIL, -1L);
 if (aboutWindow != NIL)
 SetWRefCon(aboutWindow, window);
 }
 if (aboutWindow != NIL)
 SelectWindow(aboutWindow);
}

/*
 * adjust_menus()
 * Enable and disable menu items as needed.
 */
static void adjust_menus(window)
WindowPtr window;
{
 if (isAboutWindow(window))
 window = (WindowPtr) GetWRefCon(window);
 if (isOurWindow(window)) {
 EnableItem(fileMenu, File_Clean);
 EnableItem(fileMenu, File_Set);
 EnableItem(fileMenu, File_Close);
 if (DOC.state == Idle)
 EnableItem(fileMenu, File_SaveAs);
 else {
 DisableItem(fileMenu, File_SaveAs);
 }
 CheckItem(fileMenu, File_Clean,
 DOC.state == Working);
 }
 else {
 DisableItem(fileMenu, File_Clean);
 DisableItem(fileMenu, File_Set);
 DisableItem(fileMenu, File_Close);
 DisableItem(fileMenu, File_SaveAs);
 }
 adjust_edit_menu(FALSE);
}

/*
 * adjust_edit_menu()
 * Fiddle the Edit menu.  Mostly, enable
 * everything when switching to a desk accessory.
 * Note that CleanPict doesn’t have anything
 * “editable” -- it would be reasonable to allow
 * moving the progress info to the Clipboard, though.
 */
void adjust_edit_menu(enable)
Boolean enable;
{
 if (enable) {
 EnableItem(editMenu, Edit_Undo);
 EnableItem(editMenu, Edit_Cut);
 EnableItem(editMenu, Edit_Copy);
 EnableItem(editMenu, Edit_Paste);
 EnableItem(editMenu, Edit_Clear);
 }
 else {
 DisableItem(editMenu, Edit_Undo);
 DisableItem(editMenu, Edit_Cut);
 DisableItem(editMenu, Edit_Copy);
 DisableItem(editMenu, Edit_Paste);
 DisableItem(editMenu, Edit_Clear);
 }
}

/*
 * open_document()
 * Ask for a file (only allow PICT files).  Read the
 * picture into a new window/document.
 */ 
void open_document()
{
 WindowPtrwindow;
 SFReplyreply;
 int    file;
 OSErr  status;
 static Point    where = { 85, 85 };
 SFTypeList typeList = { ‘PICT’ };

 SFGetFile(
 where, /* Where on the screen*/
 NIL,  /* Unused */
 NIL,  /* no file filter  */
 1, /* Allow one file type*/
 typeList, /* according to the list*/
 NIL, /* no dialog hook   */
 &reply /* reply goes here*/
 );
 if (reply.good) {
 WATCH_CURSOR;
 SetVol(NIL, reply.vRefNum);
   status = FSOpen(reply.fName, reply.vRefNum, &file);
   if (status != noErr)
   SysBeep(10);
   else {
 window = new_document(reply.fName);
 if (window == NIL)
 SysBeep(10); /* No memory */
 else {
 status = read_picture(window, file);
 if (status != noErr) {
 DebugStr(“\pread_picture failed”);
 }
 }
 FSClose(file);
 }
 ARROW_CURSOR;
 }
}

/*
 * close_document()
 * Close the document in the current (front) window.
 * Dump picture. Return TRUE on success, FALSE if
 * the user cancels.
 */
Boolean close_document(window)
WindowPtr window;
{
 short  size;
 Cell   cell;

 if (isOurWindow(window) == FALSE)
 return (TRUE);
 if (DOC.dirty) {
 ParamText(DOC.fileName, NIL, NIL, NIL);
 switch (CautionAlert(ALRT_Advise, NIL)) {
 case Advise_Save:
 save_document(window);
 break;
 case Advise_Discard:
 break;
 case Advise_Cancel:
 return (FALSE);
 }
 }
 WATCH_CURSOR;
 DeleteOSGrafPort(DOC.pictPort);
 CloseWindow(window);
 DisposPtr(window);
 window = NIL;
 CheckItem(fileMenu, File_Clean, FALSE);
 ARROW_CURSOR;
 return (TRUE);
}

/*
 * new_document()
 * Build a document: get memory for the WindowRecord and
 * our attached information.  Offset the window with
 * respect to other windows and make the window.  If
 * this succeeds, read the picture.
 */
WindowPtr new_document(title)
Str255  title;
{
 WindowPtrwindow;
 DocumentPtrdoc;
 Rect   box;
 static longsequence;/* Identify windows     */
 
 doc = (DocumentPtr) NewPtrClear(sizeof (DocumentRecord));
 if (doc == NIL)
 return (NIL);
 /*
  * Start with a tiny window: the picture reader
  * sets the correct size.
  */
 SetRect(&box, 0, GetMBarHeight() * 2, 32, 0);
 box.bottom = box.top + 32;
 window = NewWindow(
 doc, /* Allocated storage*/
 &box, /* Display Rect    */
 title, /* Title */
 FALSE, /* Invisible on creation */
 noGrowDocProc, /* Window type   */
 -1L,  /* Show in front   */
 TRUE, /* GoAway box */
 ++sequence /* RefCon(debug only) */
 );
 if (window == NIL) {
 DisposPtr(doc);
 return (NIL);
 }
 pstrcpy(DOC.fileName, title);
 DOC.threshold = THRESHOLD;
 SetPort(window);
 return (window);
}

/*
 * save_document()
 * Write the current picture as a PICT.  The creator
 * is hard-wired for Canvas.
 */
void save_document(window)
WindowPtr window;
{
 SFReplyreply;
 int    file;
 OSErr  status;
 static Point    where = { 85, 85 };
 SFTypeList typeList = { ‘PICT’ };
 Str255 default_filename;
 
 if (isOurWindow(window) == FALSE)
 return;
 pstrcpy(default_filename, “\pNew “);
 pstrcat(default_filename, DOC.fileName);
 SFPutFile(where, “\pSave PICT as”,
 default_filename, NIL, &reply);
 if (reply.good == FALSE)
 goto exit;
 else {
 WATCH_CURSOR;
 (void) FSDelete(reply.fName, reply.vRefNum);
 status = Create(
 reply.fName, /* File name */
 reply.vRefNum,  /* Volume reference */
 ‘DAD2’, /* Creator == Canvas */
 ‘PICT’  /* File type*/
 );
 if (status != noErr) {
 DebugStr(“\pCan’t create file”);
 goto exit;
 }
 status = FSOpen(reply.fName, reply.vRefNum, &file);
 if (status != noErr) {
 DebugStr(“\pCan’t open newly created file”);
 goto exit;
 }
 write_picture(window, file);
 FSClose(file); /* Should check for*/
 FlushVol(NIL, reply.vRefNum);/* Errors here. */
 DOC.dirty = FALSE;
exit:
 ARROW_CURSOR;
 }
}

/*
 * setup()
 * One-time initialization.
 */
void setup()
{
 InitGraf(&thePort);
 InitFonts();
 FlushEvents(everyEvent, 0);
 InitWindows();
 InitMenus();
 TEInit();
 InitDialogs(NIL);
 InitCursor();
 WATCH_CURSOR;
 MaxApplZone();
 appleMenu = GetMenu(MENU_Apple);
 fileMenu = GetMenu(MENU_File);
 editMenu = GetMenu(MENU_Edit);
 spinCursor[0] =
 (CursHandle) GetResource(‘CURS’, CURS_Spin);
 spinCursor[1] =
 (CursHandle) GetResource(‘CURS’, CURS_Spin + 1);
 AddResMenu(appleMenu, ‘DRVR’);
 InsertMenu(appleMenu, 0);
 InsertMenu(fileMenu, 0);
 InsertMenu(editMenu, 0);
 DrawMenuBar();
 ARROW_CURSOR;
}

/*
 * pstrcat()
 * Concatenate a pascal string to another.
 */
void pstrcat(out, in)
void    *out;
void    *in;
{
 long   start;
 long   length;  
 
 start = ((unsigned char *) out)[0];
 length = ((unsigned char *) in)[0];
 if ((start + length) > 255)
 length = 255 - start;
 ((unsigned char *) out)[0] = start + length;
 BlockMove(
 ((unsigned char *) in) + 1,
 ((unsigned char *) out) + start + 1,
 length);
}

/*
 * set_threshold()
 * Ask the user for a threshold value for the current
 * window.
 */
void set_threshold(window)
WindowPtr window;
{
 Str255 work;
 long   newSize;
 GrafPtrold_port;
 DialogPtrdialog;
 int    type;
 Handle handle;
 Rect   box;
 int    item;
 
 if (isOurWindow(window) == FALSE)
 return;
 GetPort(&old_port);
 dialog = GetNewDialog(DLOG_Set_Threshold, NIL, -1L);
 ShowWindow(dialog);
 SetPort(dialog);
again:
 newSize = DOC.threshold;
 NumToString(newSize, work);
 GetDItem(dialog, Thresh_Value, &type, &handle, &box);
 SetIText(handle, work);
 SelIText(dialog, Thresh_Value, 0, 32767);
 ModalDialog(NIL, &item);
 switch (item) {
 case Cancel:
 break;
 case OK:
 GetDItem(dialog, Thresh_Value, &type, &handle, &box);
 GetIText(handle, work);
 StringToNum(work, &newSize);
 if (newSize <= 0 || newSize >= (XMAX * YMAX)) {
 SysBeep(10);
 goto again;
 }
 DOC.threshold = newSize;
 break;
 default: /* Can’t happen */
 break;
 }
 DisposDialog(dialog);
 SetPort(old_port);
}

/*
 * spin_cursor()
 * Blink the cursor: called during idle time.
 */
void spin_cursor()
{
 static int index = 0;
 static Ulong  last = 0;
 long   now;

 GetDateTime(&now);
 if ((now - last) > 0) {
 index = 1 - index;
 SetCursor(*spinCursor[index]);
 last = now;
 }
}

/*
 * show_progress()
 * Update the window title every twenty rows.
 * Note that we will be called several times during
 * any particular row.  There is an interlock to
 * prevent the menu bar from flashing.
 */
void show_progress(window)
WindowPtr window;
{
 Str255 title;
 Ulong  theRow, botRow;
 BooleandoneTwenty;
 static Boolean  needUpdate = FALSE;
 
 doneTwenty = (DOC.center.v % 20) == 0;
 if (needUpdate == doneTwenty) {
 if (needUpdate == FALSE) /* Just leave 20 row? */
 needUpdate = TRUE; /* Get ready for update */
 else { /* Just entered 20 row*/
 theRow = DOC.center.v; /* Want row and bottom */
 botRow = DOC.bottom;/* as long int’s */
 NumToString((theRow * 100) / botRow, title);
 pstrcat(title, “\p% done”);
 SetWTitle(window, title);
 needUpdate = FALSE; /* Skip until next 20 */
 }
 }
}

/*
 * display_statistics shows the result of the examination
 * process.
 */
#define SHOWLINE do { \
 TextBox( \
 &theLine[1], theLine[0], &textRect, teJustLeft); \
 OffsetRect(&textRect, 0, lineSize); \
 theLine[0] = 0; \
 } while (0)

#define LINETEXT(t) do { \
 pstrcpy(theLine, “\p “); \
 pstrcat(theLine, t); \
 } while (0)
#define DRAWVALUE(v) do { \
 NumToString((v), work); \
 if (work[0] == 0)  \
 pstrcat(theLine, “\p0”); \
 else { \
 pstrcat(theLine, work); \
 } \
 } while (0)
#define DRAWTIME(v) do { \
 pstrcat(theLine, “\p:”); \
 leading_zero(theLine, (v), 2); \
 } while (0) 
#define LINEVALUE(before, value, after) do { \
 LINETEXT(before); \
 DRAWVALUE(value); \
 pstrcat(theLine, “\p “); \
 pstrcat(theLine, after); \
 SHOWLINE; \
 } while (0)
#define RATIO(v1, v2, after) do { \
 compute_fraction(work, (v1), (v2)); \
 LINETEXT(work); \
 pstrcat(theLine, “\p “); \
 pstrcat(theLine, after); \
 SHOWLINE; \
 } while (0);

void    compute_fraction(Str255, Ulong, Ulong);
void    leading_zero(Str255, Ulong, int);

/*
 * Display the “About” (and/or statistics) window.
 * This is excessively crude.
 */
void display_statistics(about_window, always)
WindowPtr about_window;
Boolean always;
{
 WindowPtrwindow;
 GrafPtroldPort;
 FontInfo info;
 int    i;
 Booleanmore;
 Str255 work, theLine;
 int    lineSize, lineHeight;
 Rect   textRect;
 Ulong  now, total, temp;
 
 GetPort(&oldPort);
 SetPort(about_window);
 TextFont(geneva);
 TextSize(9);
 GetFontInfo(&info);
 lineHeight = info.ascent + info.descent;
 lineSize = lineHeight + info.leading;
 textRect = thePort->portRect;
 textRect.bottom = textRect.top + lineHeight;
 i = 0;
 window = (WindowPtr) GetWRefCon(about_window);
 if (isOurWindow(window) == FALSE
  || DOC.start == 0) {
 do {
 GetIndString(theLine, STRS_Info, ++i);
 more = (theLine[0] != 0);
 SHOWLINE;
 } while (more);
 }
 else {
  if (DOC.state == Working) {
   GetDateTime(&now);
 DOC.elapsed = now - DOC.start;
 }
 if (always
  || DOC.elapsed != DOC.elapsed_shown) {
 DOC.elapsed_shown = DOC.elapsed;
 do {
 GetIndString(theLine, STRS_Info, ++i);
 more = (theLine[0] != 0);
 SHOWLINE;
 } while (more);
 total = ((Ulong) width(DOC.pictPort->portRect))
 * DOC.center.v;
 LINEVALUE(“\pTotal “, total, “\ppixels.”);
 LINEVALUE(“\pExamined “, DOC.examined, “\ppixels.”);
 LINEVALUE(
 “\pDeleted “, DOC.found, “\pnoise islands.”);
 LINEVALUE(
 “\pElapsed time “, DOC.elapsed, “\pseconds.”);
 LINETEXT(“\pElapsed time “);
 DRAWVALUE(DOC.elapsed / 3600L);
 DRAWTIME((DOC.elapsed / 60L) % 60L);
 DRAWTIME(DOC.elapsed % 60L);
 SHOWLINE;
 RATIO(total, DOC.elapsed, “\ptotal pixels/sec.”);
 RATIO(DOC.examined, DOC.elapsed,
 “\pexamined pixels/sec.” );
 RATIO(
 DOC.found, DOC.examined, “\pfound / examined.”);
 }
 }
 SetPort(oldPort);
}

/*
 * compute_fraction()
 * Convert the result (a ratio) to a printable string.
 */
void compute_fraction(result, numer, denom)
Str255  result;
Ulong   numer;
Ulong   denom;
{
 if (denom == 0)
 pstrcpy(result, “\p<0>”);
 else {
 NumToString(numer / denom, result);
 pstrcat(result, “\p.”);
 leading_zero(
 result, ((numer * 1000L) / denom) % 1000, 3);
 }
}

/*
 * leading_zero()
 * This is a crude function to display a value with
 * leading zeros.
 */
void leading_zero(result, value, field_width)
Str255  result;
Ulong   value;
intfield_width;
{
 Str255 work;
 register int  i;

 NumToString(value, work);
 for (i = work[0]; i < field_width; i++)
 pstrcat(result, “\p0”);
 pstrcat(result, work);
}

Listing:  CleanPICT.c

/* CleanPICT.c   */
/*
 * Copyright © 1989, 1990 Martin Minow and MacTutor.
 *
 * You may use this software in any application and
 * redistribute this source without restriction as long
 * as this copyright and permission notice remains intact
 * and the source is not redistributed for profit and you
 * assume all responsibility for the proper operation of
 * this software.
 *
 * Written in Think C.  Set Tabs every 2 characters.
 */

/*
 * Clean the picture by searching for noise blobs.  A
 * noise blob is defined as an “island” of one color
 * (forground or background) that is completly enclosed
 * by the other color and is smaller than a threshold
 * value.
 *
 * The algorithm uses a recursive “flooding” algorithm
 * (also called a “maze walking” procedure) that uses
 * several local variables.  These are defined as global
 * (file local) -- a “real” implementation would define
 * them in a structure that is allocated by the top-level
 * function and passed as a parameter to the worker bees.
 *
 * At any point in the process, the do_point function
 * examines the north/south/east/west neighbors of the
 * current point (which is known to be in the island
 * color).  If the point is not part of the island,
 * or already seen, the function returns TRUE to continue
 * looking.  Otherwise, this new island point is marked
 * “seen” and the threshold counter incremented.  If 
 * the counter exceeds threshold, the function returns
 * FALSE and the cleanout fails for this point: the
 * island is too big.
 *
 * The process concludes when any subroutine invocation
 * returns FALSE (not an island), or when only background
 * points remain.  A long, thin structure that extends
 * beyond the edge of the seen array or outside the PICT is
 * not an island.
 *
 * Note: this function is disgustingly unoptional and
 * very slow (about 1 second per row on a Mac-SE for
 * an 1800 pixel wide image).  I’m sure that a half-hour
 * reading any decent graphics textbook would improve the
 * code, but it only had to run once so why bother?
 * Remember Gordon Bell’s Law:
 * “Sometimes it’s better to have 20 million instructions
 * by Friday than 20 million instructions per second.”
 * It’s about twice as fast now, thanks to some good
 * ideas from Mike Morton.
 */

#include “CleanPICT.h”
/*
 * These two parameters were used to check performance
 * improvements:
 * USE_TOOLBOX, if defined non-zero, uses the Macintosh
 * bit-manipulation functions.  If zero, CleanPict
 * uses local routines.
 * UPDATE_MAX determines how frequently changes are
 * written to the screen (1 updates each change as
 * it happens, 10 updates every tenth change, etc.).
 */
#define USE_TOOLBOX0
#define UPDATE_MAX 10

/*
 * Some interesting stuff in the current document -- this
 * just saves lots of typing.
 */
#define PICT(DOC.pictPort->portBits)
#define RECT(PICT.bounds)

#define XMID(XMAX / 2)    
 /* Offset to center pixel*/
#define YMID(YMAX / 2)    
 /* Offset to center pixel*/
/*
 * The seen bit-array records the shape of the current
 * island.  This keeps the recursive island search
 * routine from examining the same island point twice,
 * and it marks the island for later erasure.  It is
 * written in this strange manner so we can use the
 * compiler’s structure assignment capability to clear
 * it: this should be faster than a subroutine call to
 * memset(),
 */
typedef struct {
 Ulong  v[XMAX * YMAX / sizeof (Ulong) + 1];
} SeenRecord;
SeenRecord seen_map; /* This is the active map */
static SeenRecordempty_map; /* This clears seen_map */

/*
 * Make sure [x][y] are in range.  By adding <X,Y>MID and
 * casting the value to unsigned, we can save on one
 * comparison.
 */
#define in_seen_map(x, y) ( \
  (((unsigned) ((x) + XMID)) < (2 * XMID)) \
 && (((unsigned) ((y) + YMID)) < (2 * YMID)) \
 )
/*
 * XY() converts offsets from the current pixel into an
 * index into the seen map bit-vector.  The algorithm is
 * ((y + YMID) * XMAX) + (x + XMID)
 * Since XMAX is a small, constant, power of two, the
 * compiler should replace it by a left-shift.  We
 * do this explicitly just in case.
 */
#define XY(x, y) (  \
 (((y) + YMID) << LOG_XMAX) \
  + ((x) + XMID) \
 )
/*
 * These functions manipulate the seen map.  The program
 * uses a single seen map for the entire process, stored
 * in a global vector.  This would work even if the user
 * has multiple pictures open, as the application will
 * switch between pictures only after fully-processing
 * a pixel.
 */
#if USE_TOOLBOX
#define myBitSet(i)BitSet(seen_map.v, (i))
#define myBitClr(i)BitClr(seen_map.v, (i))
#define myBitTst(i)BitTst(seen_map.v, (i))
#else
static void myBitSet(Ulong);
static void myBitClr(Ulong);
static Boolean myBitTst(Ulong);
#endif
#define set_seen(x, y)  myBitSet(XY(x, y))
#define clr_seen(x, y)  myBitClr(XY(x, y))
#define is_seen(x, y) ( \
 in_seen_map(x, y) && myBitTst(XY(x, y)) \
 )

/*
 * The BitOp macro is used to mung the PICT bitmap.
 * Note that x and y are cast to unsigned longs.
 */
#define BitOp(op, x, y) ( \
 op( \
 PICT.baseAddr + ((Ulong) y) * PICT.rowBytes, \
 ((Ulong) x) \
 ) \
 )

#define Pixel(x, y) BitOp(BitTst, x, y)

Boolean do_pixel(WindowPtr, int, int);
void    invert_seen_map(WindowPtr);
Boolean ok_point(WindowPtr, Ulong, Ulong);

extern UlongVIA_ticks(void);

/*
 * Clean out the picture.  Note: the boarder pixels
 * aren’t cleaned.
 */
void clean_picture(window, quit)
WindowPtr window;
Boolean quit;
{
 Booleanthis;
 Ulong  now;

 switch (DOC.state) {
 case Idle:
 return;
 case Init:
 /*
  * This is a new cleanup operation.  Start from
  * the top-left of the document.
  */
 GetDateTime(&DOC.start);
 DOC.elapsed = 0;
 DOC.examined = DOC.found = 0;
 DOC.updateCount = 0;
 DOC.updateRgn = NewRgn();
 DOC.thisUpdateRgn = NewRgn();
 DOC.bottom = RECT.bottom - 1;
 DOC.right = RECT.right - 1;
 DOC.center.v = RECT.top + 1;
 DOC.center.h = RECT.left + 1;
 DOC.state = Working;
 DOC.dirty = TRUE;
 break;
 case Working:
 if (quit || DOC.center.h >= DOC.right) {
 if (quit || ++DOC.center.v >= DOC.bottom) {
finish: if (DOC.updateCount > 0) {
 InvalRgn(DOC.updateRgn);
 DisposeRgn(DOC.updateRgn);
 DisposeRgn(DOC.thisUpdateRgn);
 }
 GetDateTime(&now);
 DOC.elapsed = now - DOC.start;
 SetWTitle(window, DOC.fileName);
 ARROW_CURSOR;
 SysBeep(10);
 DOC.state = Idle;
 make_about_window(window);
 quit = FALSE;
 break;
 }
 DOC.center.h = RECT.left + 1;
 DOC.island = Pixel(RECT.left, DOC.center.v);
 }
 /*
  * Within a row, we skip over a run of the
  * current pixel value, then check the pixel
  * just above this one: if it’s the same flavor,
  * we examined this pixel when we did a previous
  * row and decided it couldn’t be in an island.
  */
 while (DOC.center.h < DOC.right) {
 this = Pixel(DOC.center.h, DOC.center.v);
 if (this != DOC.island)
 goto possible_island;
 ++DOC.center.h;
 }
 break;
possible_island:
 ++DOC.examined; /* Island here?   */
 DOC.count = 0; /* No pixels yet */
 seen_map = empty_map; /* Clear seen map */
 DOC.island = this; /* Island’s color*/
 if (do_pixel(window, 0, 0)){ /* Here we go! */
 invert_seen_map(window); /* Zap the island */
 ++DOC.found;
 /*
  * The current pixel type has changed!
  */
 DOC.island = Pixel(DOC.center.h, DOC.center.v);
 }
 ++DOC.center.h;
 break;
 }
}

/*
 * This is the recursive routine that does all the
 * work.  It looks at the four cardinal neighbors:
 * if seen: continue.
 * else if off the edge of the seen map: return FALSE;
 * else if marked, check whether threshold exceeded.
 * if so, return FALSE,
 * else, call do_pixel for the cardinal point:
 * if it returns false, return FALSE.
 * else (not the same color or all cardinal points
 * already seen) return TRUE.
 * Thus: any invocation of do_pixel that returns FALSE
 * stops the process.
 */
Boolean do_pixel(window, x, y)
WindowPtr window;
register intx;
register inty;
{
 Point  thePoint;

 if (in_seen_map(x, y) == FALSE)
 return (FALSE); /* Fell off the edge */
 if (is_seen(x, y)) /* Have we been here? */
 return (TRUE);   /* Don’t do it twice */
 /*
  * This will need work if the PICT cannot be bounded
  * by a normal Mac Rect.
  */
 thePoint.h = x + DOC.center.h;
 thePoint.v = y + DOC.center.v;
 if (PtInRect(thePoint, &RECT) == FALSE)
 return (TRUE);   /* Fell off the pict */
 else if (Pixel(thePoint.h, thePoint.v) != DOC.island)
 return (TRUE);   /* It’s in the background */
 else {
 set_seen(x, y); /* This is in the island */
 if (++DOC.count > DOC.threshold)
 return (FALSE); /* Island is too big */
 else if (do_pixel(window, x + 1, y    )
   && do_pixel(window, x,     y + 1)
   && do_pixel(window, x - 1, y    )
 && do_pixel(window, x,     y - 1))
   return (TRUE); /* Still in the island */
 else {
 return (FALSE); /* Propogate failure */
 }
 }
}

/*
 * The seen map describes the island: just invert it
 * to clean out the island.
 */
void invert_seen_map(window)
WindowPtr window;
{
 register int    x, y;
 Rect   box;
 BooleanseenTop = FALSE;
 
 for (y = -YMID; y < YMID; y++) {
 for (x = -XMID; x < YMID; x++) {
 if (is_seen(x, y)) {
 if (DOC.island)
 BitOp(
 BitClr, x + DOC.center.h, y + DOC.center.v);
 else {
 BitOp(
 BitSet, x + DOC.center.h, y + DOC.center.v);
 }
 box.right = x;
 box.bottom = y;
 if (seenTop == FALSE) {
 box.left = x;
 box.top = y;
 seenTop = TRUE;
 }
 }
 }
 }
 /*
  * Track the change on the screen image.
  */
 OffsetRect(&box, DOC.center.h, DOC.center.v);
 MapRect( /* Use window environment*/
 &box,  /* This is what changed    */
 &RECT, /* PICT’s boundaries*/
 &window->portRect /* Map to these bounds */
 );
 InsetRect(&box, -1, -1); /* Cover the area */
 /*
  * If the update count is zero, set the update area
  * to this box.  Otherwise, extend the update region
  * to include this island. If the threshold has
  * been reached, draw it onto the screen.  Note that
  * we try to avoid the overhead of a full update
  * event.  If this code changes, be sure to fix the
  * algorithm in the update event handler.
  */
 if (DOC.updateCount++ == 0)
 RectRgn(DOC.updateRgn, &box);
 else {
 RectRgn(DOC.thisUpdateRgn, &box);
 UnionRgn(
 DOC.thisUpdateRgn, DOC.updateRgn, DOC.updateRgn);
 }
 if (DOC.updateCount >= UPDATE_MAX) {
 CopyOSGrafPort(DOC.pictPort, window, DOC.updateRgn);
 DOC.updateCount = 0;
 } 
}

#ifndef myBitSet
/*
 * These functions are adapted from a suggestion by Mike
 * Morton: they implement bit set/clear/test without the
 * overhead of a toolbox call.  Note that they could
 * easily be written in C for portability.
 */
 
static Boolean myBitTst(bitNum)
register Ulong   bitNum;
{
 asm {
 lea    seen_map.v,A0; A0 -> seen map base
 move.w bitNum,D0; D0 := bit offset
 lsr.w  #3,D0    ; D0 := byte offset
 add.w  D0,A0    ; A0 -> correct byte
 not.b  bitNum   ; Flip bit numbering
 moveq  #0,D0    ; Clear result word
 btst   bitNum,(A0); Test the bit
 sne    D0; Set D0 if not equal
 neg.b  D0; flip result
 }
 /* Fall through to return result in D0 */
}

static void myBitSet(bitNum)
register Ulong   bitNum;
{
 asm {
 lea    seen_map.v,A0; A0 -> seen map base
 move.w bitNum,D0; D0 := bit offset
 lsr.w  #3,D0    ; D0 := byte offset
 add.w  D0,A0    ; A0 -> correct byte
 not.b  bitNum   ; Flip bit numbering
 bset   bitNum,(A0); Set the bit
 }
}

static void myBitClr(bitNum)
register Ulong   bitNum;
{
 asm {
 lea    seen_map.v,A0; A0 -> seen map base
 move.w bitNum,D0; D0 := bit offset
 lsr.w  #3,D0    ; D0 := byte offset
 add.w  D0,A0    ; A0 -> correct byte
 not.b  bitNum   ; Flip bit numbering
 bclr   bitNum,(A0); Set the bit
 }
}
#endif

Listing:  OffscreenGrafPort.h

/* OffscreenGrafPort.h */
/*
 * Prototypes for OffscreenGrafPort.c
 */
#ifndef NIL
#define NIL ((void *) 0)
#endif

GrafPtr CreateOSGrafPort(Rect);
void    CopyOSGrafPort(GrafPtr, GrafPtr, RgnHandle);
void    DeleteOSGrafPort(GrafPtr);

Listing:  OffscreenGrafPort.c

/*  OffscreenGrafPort.c  */
#ifdef DOCUMENTATION

Title   GrafPort Handler

Usage

 #include “OffscreenGrafPort.h”

 GrafPtr
 CreateOSGrafPort(rect)
 Rect   rect;
 
 Create a new GrafPort big enought to hold the Rect.
 Note that its storage is not relocatable.  If there
 isn’t enough memory, CreateOSGrafPort will return
 NIL and the GrafPort is -- obviously -- unusable.
 If CreateOSGrafPort succeeds, the function does
 SetPort to the new GrafPtr.

 void
 CopyOSGrafPort(srcPort, dstPort, mask)
 GrafPtrsrcPort;
 GrafPtrdstPort;
 RgnHandlemask;
 
 Copy the contents of the srcPort to the dstPort.
 The entire port is copied.  Note: the picture is
 stretched to fill the dstPort.  If this is
 unsuitable, just call CopyBits yourself.
 
 void
 DeleteOSGrafPort(theOSGrafPort)
 GrafPtrtheOSGrafPort;
 
 Delete the GrafPort created by CreateOSGrafPort().
 
Normal Usage:

 GrafPtrtempPort;
 GrafPtroldPort;
 
 GetPort(&oldPort);
 tempPort = CreateOSGrafPort(rect);
 ... drawing commands ...
 SetPort(oldPort);
 /*
  * Show my stuff
  */
 CopyOSGrafPort(tempPort, FrontWindow(), NIL);
 DeleteOSGrafPort(tempPort);

acknowledgment

 Taken without much change from Mac TechNote 41
 
#endif

#include “OffscreenGrafPort.h”
#ifndef width
#define width(r) ((r).right - (r).left)
#define height(r)((r).bottom - (r).top)
#endif

GrafPtr CreateOSGrafPort(box)
Rect    box;
{
 GrafPtroldPort;
 GrafPtrnewPort;
 long   rowBytes;
 
 /*
  * Build an “empty” port big enough for our picture.
  */
 GetPort(&oldPort);
 newPort = (GrafPtr) NewPtr(sizeof (GrafPort));
 if (newPort == NIL || MemError() != noErr)
 return (NIL);
 OpenPort(newPort);
 newPort->portRect = box;
 newPort->portBits.bounds = box;
 RectRgn(newPort->clipRgn, &box);
 RectRgn(newPort->visRgn, &box);
 rowBytes = ((width(box) + 15) >> 4) << 1;
 newPort->portBits.rowBytes = rowBytes;
 newPort->portBits.baseAddr =
 NewPtr(rowBytes * (long) height(box));
 if (newPort->portBits.baseAddr == NIL
  || MemError() != noErr) {
 SetPort(oldPort);
 ClosePort(newPort);
 DisposPtr(newPort);
 return (NIL);
 }
 /*
  * OpenPort did a SetPort to newPort
  */
 EraseRect(&box);
 return (newPort);
}

/*
 * Copy between ports.  Note that the data is
 * stretched to fill the entire dstPort.
 */
void CopyOSGrafPort(srcPort, dstPort, mask)
GrafPtr srcPort;
GrafPtr dstPort;
RgnHandle mask;
{
 CopyBits(&(*srcPort).portBits, &(*dstPort).portBits,
 &(*srcPort).portRect, &(*dstPort).portRect,
 srcCopy, mask );
}

/*
 * Dispose of the port.
 */
void DeleteOSGrafPort(oldPort)
GrafPtr oldPort;
{
 ClosePort(oldPort);
 DisposPtr((*oldPort).portBits.baseAddr);
 DisposPtr((Ptr) oldPort);
}

Listing:  ReadPICT.c

/*  ReadPICT.c  */
/*
 * Picture I/O -- more or less from TechNote 154.
 *
 * For some reason, the PICT dimensions do not correctly
 * describe the picture: it loses its 300 dpi resolution
 * when read in. MAGIC scales the PICT by a factor of 4.
 * We should get the “real” scale factor by inserting
 * our function into the StdBits bottleneck.
 */
#include “CleanPICT.h”
#include <SysErr.h>

/*
 * See TechNote 27 (original format), and the Essential
 * MacTutor, vol 3, p 417.  (This struct is now unused
 * but, since it typed it in, it might as well stay.)
 */
typedef struct {
 OSType fType; /* ‘DRWG’ for MacPaint files  */
 short  hdrID; /* ‘MD’ for MacPaint format */
 short  version; /* File version */
 short  prRec[60]; /* 120 byte print record */
 Fixed  xOrigin; /* Drawing origin */
 Fixed  yOrigin; /* Drawing origin */
 Fixed  xScale; /* Screen resolution */
 Fixed  yScale; /* Screen resolution */
 short  atrState[31]; /* Drawing attribute state */
 short  lCnt; /* Top-level objects */
 short  lTot; /* Total number of objects */
 long   lSiz; /* Total size of list */
 Fixed  top; /* Box enclosing all objects    */
 Fixed  left;
 Fixed  bottom;
 Fixed  right;
 short  filler1[141]; /* 282 bytes unused     */
} MacDrawHdrRec;

static intPICTfile;/* The file ioRefNum */

/*
 * Use this to peek into the bitmap as it is read in.
 * The peeking is done by jumping into the Debugger.
 */
pascal void myStdBits(
 BitMap *, Rect *, Rect *, int, RgnHandle);
pascal void read_picture_data(Ptr, int);
pascal void write_picture_data(Ptr, int);

/*
 * read_picture() reads the picture from the PICT file,
 * constructing the window at the proper size.
 */
OSErr read_picture(window, theFile)
WindowPtr window;
inttheFile;
{
 PicHandlehandle;
 QDProcsprocedures;
 OSErr  status;
 long   size;
 long   place;
 Rect   box;
 GrafPtroldPort;
 MacDrawHdrRec header;
 
 PICTfile = theFile;
 handle = (PicHandle) NewHandle(sizeof (Picture));
 if (handle == NIL) {
 DebugStr(“\pCan’t get memory for picture”);
 return (MemError());
 }
 /*
  * Read the MacDraw header record -- that was a
  * good idea, but it didn’t work as the headers
  * are garbage.
  */
 if (sizeof header != 512)
 DebugStr(“\pMacDrawHdrRec wrong size!”);
 read_picture_data((Ptr) &header, sizeof header);
 HLock(handle);
 read_picture_data((Ptr) *handle, sizeof (Picture));
 HUnlock(handle);
 box = (**handle).picFrame;
 DOC.pictSize = box;
 box.right *= MAGIC;
 box.bottom *= MAGIC;
 GetPort(&oldPort);
 DOC.pictPort = CreateOSGrafPort(box);
 if (DOC.pictPort == NIL) {
 DebugStr(“\pNo memory for picture”);
 SetPort(oldPort);
 return (MemError());
 }
 SetStdProcs(&procedures);
 DOC.pictPort->grafProcs = &procedures;
 procedures.getPicProc = (Ptr) read_picture_data;
/* procedures.bitsProc = (Ptr) myStdBits;          -- unused */
 DrawPicture(handle, &box);
 DOC.pictPort->grafProcs = NIL;
 DisposHandle((Handle) handle);
 /*
  * Erase a 1-pixel frame around the picture so
  * the island searcher never has to worry about
  * falling off the end of the universe.
  */
 PenPat(white);
 FrameRect(&DOC.pictSize);
 PenNormal();
 SetPort(oldPort);
 /*
  * Check for errors by getting the file position and
  * checking that it is at the end of file.
  */
 if ((status = GetEOF(PICTfile, &size)) != noErr
  || (status = GetFPos(PICTfile, &place)) != noErr) {
   DebugStr(“\pCan’t get EOF or file position”);
   return (status);
 }
 if (size != place) {
 DebugStr(“\pDidn’t read entire picture”);
 return (dsSysErr);
 }
 /*
  * Ok so far.  Now, change the window size so the
  * picture fills the window -- but keep the proportions
  * as close to the original as possible.
  */
 SetRect(&box, 2, GetMBarHeight() * 2, width(DOC.pictSize) + 2, GetMBarHeight() 
* 2 + height(DOC.pictSize) );
 if (box.bottom > (screenBits.bounds.bottom - 2)) {
 box.bottom = screenBits.bounds.bottom - 2;
 size = height(box);
 box.right = box.left
 + ((long) width(box) * size) / height(DOC.pictSize);
 }
 if (box.right > (screenBits.bounds.right - 2)) {
 box.right = screenBits.bounds.right - 2;
 size = width(box);
 box.bottom = box.top
 + ((long) height(box) * size) / width(DOC.pictSize);
 }
 SizeWindow(window, width(box), height(box), TRUE);
 InvalRect(&window->portRect);
 ShowWindow(window);
 return (MemError());
}

/*
 * This should implement a “vanilla” StdBits -- for some
 * reason, though, it “bombs” when it runs to completion:
 * perhaps because it’s called with a NULL argument at
 * eof.  It was only used to check that the created
 * “MAGIC” bitmap is the same size as the bitmap inside
 * of the PICT -- by running the function under the
 * debugger.
 */
pascal void myStdBits(srcBits, srcRect, dstRect, mode, maskRgn)
BitMap  *srcBits;
Rect    *srcRect;
Rect    *dstRect;
short   mode;
RgnHandle maskRgn;
{
 CopyBits(srcBits, &thePort->portBits, 
 srcRect, dstRect, mode, maskRgn);
}

/*
 * Called indirectly to read a chunk of picture data.
 */
pascal void read_picture_data(data_ptr, byte_count)
Ptrdata_ptr;
intbyte_count;
{
 OSErr  status;
 long   count;
 
 count = byte_count;
 status = FSRead(PICTfile, &count, data_ptr);
 if (status != noErr)
 DebugStr(“\pReading picture”);
}

/*
 * write_picture() writes the current picture to a
 * specified (open) file.  It should be redone to
 * add error handling.
 */
void write_picture(window, theFile)
WindowPtr window;
inttheFile;
{
 PicHandlepicHandle;
 QDProcsprocedures;
 int    i;
 long   temp;
 Pictureheader;
 GrafPtrtempPort;
 GrafPtroldPort;

 GetPort(&oldPort);
 PICTfile = theFile;
 /*
  * Write the MacPaint header
  */
 temp = 0L;
 for (i = 0; i < 512; i += sizeof temp)
 write_picture_data((Ptr) &temp, (int) sizeof temp);
 header.picSize = 0;
 header.picFrame = DOC.pictSize;
 write_picture_data((Ptr) &header, (int) sizeof header);
 /*
  * Write the picture by creating a GrafPort with the
  * same dimensions as the original, then drawing the
  * cleaned up picture.
  */
 tempPort = CreateOSGrafPort(DOC.pictSize);
 if (tempPort == NIL) {
 DebugStr(“\pNo space for temp port”);
 return;
 }
 SetStdProcs(&procedures);
 tempPort->grafProcs = &procedures;
 procedures.putPicProc = (Ptr) write_picture_data;
 picHandle = OpenPicture(&tempPort->portRect);
 CopyOSGrafPort(DOC.pictPort, tempPort, NIL);
 ClosePicture();
 KillPicture(picHandle);
 DeleteOSGrafPort(tempPort);
 DOC.pictPort->grafProcs = NIL;
 SetPort(oldPort);
}

/*
 * Called indirectly to write a chunk of picture data.
 */
pascal void write_picture_data(data_ptr, byte_count)
Ptrdata_ptr;
intbyte_count;
{
 OSErr  status;
 long   count;
 
 count = byte_count;
 status = FSWrite(PICTfile, &count, data_ptr);
 if (status != noErr)
 DebugStr(“\pWriting picture”);
}

Listing:  CleanPict.r

*
* Resources for CleanPict
*
CleanPICT.Π.rsrc
APPL????;; APPL, followed by your “signature”

type STR#
Info, 1
3
CleanPICT removes noise from PICT files.
Copyright © 1990 Martin Minow and MacTutor
Version of July 9, 1990

*
* Menus
*
type MBAR=GNRL   ;; The menu bar
, 1000  ;; MBAR_Menu_Bar
.i
3
1 256 257 ;; MENU...

Type MENU ;; Stuff in the menu bar
,1 ;; MENU_Apple
\14
 About CleanPICT
 (-

,256    ;; MENU_File
File
 Open PICT/O\C9
 Clean
 Set Threshold\C9
 Close
 Save As/S\C9
 Debug
 (-
 Quit/Q

,257    ;; MENU_Edit
Edit
 Undo   ;;  1
 (-;;  2
 Cut    ;;  3
 Copy   ;;  4
 Paste  ;;  5
 Clear  ;;  6

*
* The Status (About) Window
*
Type WIND ;; Display window
, 1000  ;; WIND_About
About CleanPICT  ;; Title
100 100 260 360  ;; Top Left Bottom Right
Visible GoAway   ;; Attributes
4;; noGrowDocProc
0;; refCon

*
* Set Threshold Dialog
*
Type DLOG
Set Threshold, 1000;; DLOG_Set_Threshold
Set Threshold
100  100  200 300
inVisible NoGoAway
1
0
1000

Type DITL
Set Threshold, 1000;; DLOG_Set_Threshold
4

BtnItem Enabled  ;; Ok
 71 135  97 184
OK

BtnItem Enabled
 71  34  97  83
Cancel  ;; Cancel

StatText Disabled;; Threshold_Text
 13  17  33 190
Set Island Threshold

EditText Disabled;; Threshold_Value
 40  19  57  87

*
* Ask whether the file should really be discarded.
*
Type ALRT
,2000   ;; ALRT_Advise
100 100 250 400
2000    ;; ALRT_Advise
4444

Type DITL
,2000   ;; ALRT_Advise
4

BtnItem Enabled
 67  37 91 123
Save

BtnItem Enabled
104  37 128 123
Discard

BtnItem Enabled
 85 184 109 270
Cancel

StatText Disabled
 10  69  58 287
Save changes to ^0?

*
* Wait cursors (must be in order).
*
Type CURS = GNRL
, 2000
.h
0000 7878 CCCC CCCC CCCC 7FF8 0CC0 0CC0
7FF8 CCCC CCCC CCCC 7878 0000 0000 0000
0000 7878 CCCC CCCC CCCC 7FF8 0CC0 0CC0
7FF8 CCCC CCCC CCCC 7878 0000 0000 0000 0006 0006

, 2001
.h
0000 7878 CCCC CCCC CCCC 7FF8 0CC0 0CC0
7FF8 CCCC CCCC CCCC 7878 0003 0003 0000
0000 7878 CCCC CCCC CCCC 7FF8 0CC0 0CC0
7FF8 CCCC CCCC CCCC 7878 0003 0003 0000 0006 0006