PICT Rotation with Copybits

By Robert B. Denny, Alisa Systems, Inc., MacTutor Editorial Board

A few years ago, I was studying the Smalltalk-80 language when I came across a novel image rotation algorithm [see Goldberg & Robson, Smalltalk-80: The Language and its Implementation (Addison Wesley, 1983), pp408-410]. It typifies the sorts of things that result from applying mathematics to software design.

The C Workshop is due for some less advanced articles, so here's the first. It serves two purposes: to illustrate a simple application which uses a runtime library, and to demonstrate QuickDraw bit-maps and the powerful CopyBits() toolbox service. We'll do this with an implementation of the image rotation algorithm.

A Simple Application

Most C language systems provide glass teletype simulation, where one or more windows can act like TTY's via the "standard library" (stdio) calls such as scanf() and printf(). This makes it possible, in many cases, to build and run C applications which use text commands and output on the Mac.

If the stdio library permits access to the window record for the TTY window, you can let the library open the window, then experiment with QuickDraw services on that window. You don't have to start out with a "full-blown" application which uses event loops, textEdit, etc. The thing to remember is that the run-time library turns C into a high-level language which has easy access to the toolbox. In this column we use the Consulair Mac-C system; most other systems have similar support in their libraries.

Here is the classic "Hello World" program in Mac-C, with added QuickDraw commands to draw nested boxes in the glass teletype window:

#include"Lib:stdio.h"/* Normally required */
#include"Lib:MacDefs.h" /* Toolbox */
#include"Lib:QuickDraw.h" 
#include"Lib:Window.h"  

main()
 {
 Rect frame;
 int j, k;
 char buf[8];
 
 printf("Hello world!\n");
 for(j = 10; j < 100; j += 10)
 {
 k = 2 * j;
 SetRect (&frame, 240 - k, 110 - j,  240+k, 110 + j);
 FrameRect (&frame);
 }
 gets(buf); /* Wait for <Ret> then exit */
 }  /* End of program */

In this application, the Mac-C library opens a glass teletype window for use as stdout. It's the only window, so it's always the current "port". Thus, QuickDraw operations will be performed on the contents of that window. You don't need direct access to the window data. Here's what the screen looks like:

QuickDraw Bit Maps

A window is a special case of a QuickDraw port. Most QuickDraw services operate on the "current" port as established by a call to SetPort(). In the above application, the run-time library creates the window, and makes its contents the current port. By the time main() is called by the library, the window contents are ready for drawing.

A port is described by a data structure called a grafPort. One of the components of a grafPort is a small data structure called a bitMap. Contrary to common usage, a bit map is not the memory area which contains the image bits (pixels). Rather, it describes that area. The image is kept in a bit image.. In C, the definition of a bitMap is:

struct __BM
 {
 char *baseAddr; /* -> bit image */
 unsigned rowBytes;/* MUST BE EVEN */
 Rect bounds;    /* Boundary Rectangle */
 }
#typedef  struct __BM  bitMap

The baseAddr field points to the memory address of the bit image. For ports whose bit images are on the screen, baseAddr always contains the address of the screen memory ($7A700 on 512K Mac). It is possible to "draw" into a bit image other than the screen. Simply set up a grafPort with a bitmap pointing to your own bit image area, make it the current port, and draw away. This is how the printing system works; the image is drawn into a small bit image a strip at a time, and then transmitted to the imagewriter. The same commands draw to any bit image.

The rowBytes field describes the geometry of the bit image, in particular, the number of bytes that make up each row of the bit image. The value must be even; each row must be made up of an integral number of 16-bit words. This seems to imply that bit images must always be a multiple of 16 bits wide. This is not the case, as we'll see now.

The bounds field establishes the actual dimensions of the bit image and the "local" coordinate system for the image. There is no restriction that the upper left corner of a bit image must be at coordinates (0,0) or that the origin coordinates must be positive. The dimensions of the bounds rectangle set the "logical" size of the bit image, as opposed to the "physical" size indicated by rowBytes and the total size of the bit image array.

It's possible to work with on-screen windows without coming into direct contact with bitMaps. The image rotation algorithm uses the "blitting" service CopyBits() to perform manipulations involving bitMaps. The image being rotated is kept in a screen bit image so you can observe the rotation while it's in progress. Just remember that the window record contains the grafPort which contains the bitMap, which describes the "chalkboard" bit image.

Image Rotation Using CopyBits

Ever wonder how MacPaint can rotate images so fast? Rotation of an image by a multiple of 90 degrees is a useful operation, and its easier than you might think. The algorithm about to be described uses a clever sequence of bit transfer operations to rotate a square image whose sides are 2n bits in length, for integral n. It can be generalized to operations on arbitrary rectangles, as is done in MacPaint. Note how MacPaint does not rotate about the "center" of an image.

The algorithm consists of a series of permutations on the image. The left and right halves are swapped, followed by an exchange of the upper-left and lower-right quadrants of the swapped image. Then the four quadrants themselves are permuted in the same way, then divided into quadrants and the resulting sixteen cells are permuted, etc. The process completes when the cell size has reduced to two by two bits.

If you wrote a routine to implement the above method literally, it would take geometrically increasing time as the bit image size increased. Specifically, for an image 2n bits on a side, it would take

 npermutations = 1 + 4 + 16 + ... + 4n-1

to complete the rotation. This would render the algorithm a laboratory curiosity.

The amazing feature of the actual algorithm is its ability to perform all cell permutations for a given cell size in parallel ! This means that execution time is proportional to log2(n), where the image is 2n bits on a side. The penalty is that storage is required for two additional bit images the same size as the image to be rotated.

Figure 1 shows what it looks like when the Liberty Bell (Copyright 1984, T/Maker Graphics, used with permission) is rotated as a 256 x 256 bit image. Each pixel is mapped to a 2-pixel square on the LaserWriter used to produce MacTutor. The rotation takes log2(256) =8 steps.

Now lets get down to business. Besides the image itself, the algorithm requires two bit images the same size as the transform image. One, called mask, contains 1's in the upper left quadrant of each cell, 0's elsewhere. The other, called temp is used for scratch storage.

Each major step in a permutation is accomplished via a series of bit-transfer (blit) operations involving the three bit images. On the Mac, blitting is done via the powerful CopyBits() service, which can copy a bit image with coordinate translation and size scaling. The major steps in a permutation are (1) swap left and right cell halves, (2) exchange lower-right and upper-left quadrants of each cell and (3) refine the mask in preparation for the next cell subdivision.

Figures 2, 3 and 4 show the bit transfers needed for the major steps of the first permutation. Each bit transfer is a single CopyBits() operation. The gray areas show the destination rectangles for each CopyBits(). Keep in mind that the destination is clipped to the bounds in its bitMap.

Adventures With CopyBits()

The image rotation demo program described below makes heavy use of the QuickDraw CopyBits() service. Success followed several adventures which I'll describe. Well, I won't describe the first adventure ... I'm embarassed. The other two adventures relate to the first blit of the mask refinement phase, where the entire mask is copied and shrunk into the upper-left 128 by 128 bit quadrant (see Fig. 4).

First, I was relieved to discover that CopyBits() works when the source and destination are the same bit image, as long as the destination Rect is to the left and above the source Rect. Specifically, mask refinement step 1 takes a single CopyBits(). That's the good news.

Now for the bad news. I discovered another feature (read that as "bug") in CopyBits(). Mask refinement starts by copying the entire mask into the upper left quadrant. The image is reduced to one half its size. Most of the time.

The first permutation uses a mask with a single 128-bit black square in the upper left quadrant, which should shrink to a 64-bit black square on the first refinement blit (see Fig. 4 again). It doesn't. Instead, the resulting black rectangle is 65 bits on a side. The scaling feature of CopyBits does not scale accurately or consistently, even if the scaling factor is a power of 2! This "small" error caused the rotation algorithm to fail miserably.

Fortunately, the solution is simple. Fake CopyBits by supplying a source Rect that is one bit larger on the right and bottom edges, making the reduction slightly more than 50%. Ugly, yes, but it works & anything more general or rigorous is likely to be a lot more complex. It's not a panacea, so beware. Don't take image reductions made by CopyBits() for granted; test the results for accuracy.

Fig. 5 Screen Dump

A Demonstration Program

We finish up with the C code for a demonstration of the algorithm. The program was used to produce the Liberty Bell transformation images of Figure 1. It may be used to transform any PICT resource that will fit within the 256 by 256 bit area. Simply paste the image into the scrapbook and then cut it out using the Resource Editor. Save it in a resource file, then change the program code to open that resource file and get the proper resource by its ID. For the sample, I put the T/Maker Liberty Bell into a resource file named "Bell" with a resource ID of 1024.

The program opens up 2 windows, one for TTY simulation, the other for displaying the image during rotation. The altStart entry point is used to supress the default TTY window. Later the setTTY() function hooks the "custom" TTY window up to stdout. The screen looks like figure 5 after the first permutation (see next page).

Before the Liberty Bell is loaded into the image window, the window is used to draw the initial mask image. The mask and temp images don't need a grafPort, so they are described by simple bitMaps. This means that QuickDraw can't be used to draw into them directly. So the "seed" mask is drawn into the image window with FillRect(), then blitted to the mask image, after which the window is erased in preparation for loading the PICT.

Next the resource file is opened and the PICT-1024 resource is read in with GetResource() and locked down. Then DrawPict() is called to paint the picture into the image window.

Before the picture is drawn, the PICT's bounds Rect is used to calculate the border needed to center it in the 256 by 256 bit image. Afterward, the PICT is unlocked and disposed. Finally, the rotation is performed, optionally in steps controlled by gets() calls.

/*
 * Rotate.C - Demonstrate Smalltalk Image Rotation Algorithm
 *
 * Written by:
 * Robert B. Denny, Alisa Systems, Inc.
 * September, 1985
 *
 * LINKER COMMAND PROCEDURE (Consulair Mac C V4.0, either
 *           Consulair or MDS linker)
 * --
 * /Output  Dev:Rotate
 * /Type  'APPL'  '????'
 * Dev:Rotate.REL
 * Lib:Standard Library
 *
 * $
 * --
 *
 * Copyright (C) 1985, MacTutor Magazine
 *
 * Permission granted to use only for non-commercial purposes.
 * This notice must be included in any copies made hereof.
 * All rights otherwise reserved.
 *
 * Warning: This code was edited for publication 
 */

/*
 * Included files
 */
#include  "Lib:Stdio.h"                            /* Required when using 
stdio library */
#include  "Lib:MacCDefs.h"                 /* Has Consulair specials 
*/
#include  "Lib:MacDefs.h"                   /* Basic toolbox definitions 
*/
#include  "Lib:QuickDraw.h"               /* QuickDraw structs and consts 
*/
#include  "Lib:Window.h"                     /* Window Manager structs 
& consts */

/*
 * Definitions & Parameters
 */
#define  plainDBox  2/* My H files must be old ... */
#define  noGrowDocProc  4 /* ... these names match Inside Mac */
#define  srcAnd  notSrcBic/* A more reasonable name */
#define  TRUE  1 /* I use the following everywhere */
#define  FALSE  0
#define  byte  unsigned  char
#define  word  unsigned  int
#define  longword  unsigned  long

/*
 * The following definitions control key aspects of the program, which 
you may change.  You only need
 * change these definitions.
 */
#define  PICT_FILE  "Bell"/* Name of resource file containing PICT */
#define  PICT_ID  1024  /* Resource ID of PICT */

/*
 * Static Variables
 */
static  BitMap maskBits  =  {0, 32, 0, 0, 256, 256};     /* Mask bitmap 
- baseAddr set at runtime */
static  BitMap tempBits  =  {0, 32, 0, 0, 256, 256};     /* Temp bitmap 
- baseAddr set at runtime */
static  Rect hackRect  =  {0, 0, 257, 257};  /* Used in CopyBits hack 
(see article text) */

static  WindowPtr  imageWindow;  /* --> image window's grafPort & data 
*/
static  Rect iwRect  =  {45, 231, 301, 487}; /* Location of image window 
on screen */

static  WindowPtr  ttyWindow; /* --> TTY window's grafPort & data */
static  Rect twRect  =  {45, 15, 235, 185};  /* Location of control window 
on screen */

/*
 * Main Program
 */
main()
 {
 /*
  *Automatics
  */
 char  buf[80];  /* Used to receive gets() responses */
 word  step;/* TRUE means single step transformation */
 Rect  xRect,  yRect;/* Scratch Rect's used in rotation */
 PicHandle  srcPict; /* Handle to PICT resource */
 word  picWidth,  picHeight;/* PICT dimensions, pixels */
 word  half_cell;/* Half-cell size, pixels */
 BitMap  *ibp;   /* Often used pointer to image window bitMap */
 Rect  *irp;/* Often used pointer to image window portRect */
 
 /*
  * Begin code
  */
 HideCursor ();  /* No mouse used here */
 
 /*
  * Create custom TTY window, clear it out & attach to stdout
  */
 ttyWindow = newWindow (0, &twRect, "\007Control", TRUE, /* Make TTY 
window */
 noGrowDocProc, -1, FALSE, 0);
 SetTTY(ttyWindow);/* Hook this window up to stdout */
 ClearTTY(ttyWindow);/* Clear it out, just for fun */
 
 /*
  * Create the image window and make pointers to its bitMap and portRect, 
used often below.
  */
 imageWindow = newWindow (0, &iwRect, 0, TRUE,     /* Make image window 
*/
 plainDBox, -1, FALSE, 0);
 ibp = &(imageWindow->portBits); /* --> image window's bitMap */
 irp = &(imageWindow->portRect); /* --> image window's portRect */
 
 /*
  * Allocate bit image space for temp and mask, fill in bitMaps with 
the array addresses.
  */
 maskBits.baseAddr = (Ptr)calloc(4096, sizeof(word));    /* Allocate 
mask bit image area */
 tempBits.baseAddr = (Ptr)calloc(4096, sizeof(word));    /* Allocate 
temp bit image area */
 
 /*
  * Paint starting mask into image window, then transfer to mask bit 
image.  Erase
  * image window when done.
  */
 PenNormal ();   /* Reset graphics pen to black, etc. */
 SetPort (imageWindow); /* Prepare to draw in image window */
 SetRect (&xRect, 0, 0, 128, 128); /* Upper left quadrant */
 PaintRect (&xRect); /* Fill it in with black.  Now have initial mask 
*/
 CopyBits (ibp, &maskBits, irp, &(maskBits.bounds), srcCopy, 0);  /* 
Transfer mask pattern to its bit image */
 EraseRect (irp);/* Clear out the image window */ 

 /*
  * Load the PICT, compute target Rect to center in image window, then 
draw it there.
  */
 OpenResFile (PICT_FILE); /* Open the resource file */
 srcPict = GetResource ('PICT', PICT_ID);    /* Load PICT resource */
 HLock (srcPict);/* Lock resource ... */
 irp = &((*srcPict)->picFrame);  /* Pointer to PICT's bounds Rect */
 picWidth = (irp->right - irp->left);/* Compute PICT width */
 picHeight = (irp->bottom - irp->top); /* Compute PICT height */
 xRect.left = (256 - picWidth) >> 1; /* Form PICT-size Rect centered 
in image window */
 xRect.top = (256 - picHeight) >> 1; /* (Could do this with InsetRect 
() ) */
 xRect.right = xRect.left + picWidth;
 xRect.bottom = xRect.top + picHeight;
 DrawPicture (srcPict, &xRect);  /* Draw picture into target Rect in 
image window */
 HUnlock (srcPict);/* Unlock the resource, we no longer need it */
 DisposHandle (srcPict);  /* Trash the resource */
 
 /*
  * Hook up "stdout" to our custom TTY window and query user about single 
stepping
  */
 SetTTY(ttyWindow);/* Attach stdout to TTY window */
 puts("Single step [Y/N]? "); /* Pop the question */
 gets(buf); /* Get the answer */
 puts("\n");/* Echo newline (Consulair quirk) */
 step = (toupper(buf[0]) == 'Y') ? TRUE : FALSE;   /* Translate answer 
to boolean */
 
 /*
  * Begin the rotation algorithm
  */
 irp = &(imageWindow->portRect); /* --> image window portRect -- used 
often */
 half_cell = 128;/* Initialize half-cell dimension */
 while(half_cell)/* Main loop */
 {
 if(step) /* If single-stepping */
 {
 puts("<Return> to step: ");/* Wait for <return> to step */
 gets(buf);
 puts("\n");
 }
 
 SetRect (&xRect, 0, 0, 256, 256);    /* Initialize scratch  */
 SetRect (&yRect, 0, 0, 256, 256);    /* rectangles to image coord's 
*/
 /*
  *Phase 1 - Swap left and right cell halves
  */
 CopyBits (&maskBits, &tempBits, &xRect, &xRect, srcCopy, 0);
 OffsetRect (&yRect, 0, half_cell);
 CopyBits (&maskBits, &tempBits, &xRect, &yRect, srcOr, 0);
 CopyBits (ibp, &tempBits, irp, &xRect, srcAnd, 0);
 CopyBits (&tempBits, ibp, &xRect, irp, srcXor, 0);
 OffsetRect (&yRect, -half_cell, -half_cell);
 CopyBits (ibp, &tempBits, irp, &yRect, srcXor, 0);
 CopyBits (ibp, ibp, irp, &yRect, srcOr, 0);
 OffsetRect (&yRect, half_cell << 1, 0);
 CopyBits (&tempBits, ibp, &xRect, &yRect, srcXor, 0);
 /*
  *Phase 2 - Exchange lower-right and upper-left 
  *     cell quadrants  */
 wait(500); /* Delay to allow seeing each phase */
 CopyBits (ibp, &tempBits, irp, &xRect, srcCopy, 0);
 OffsetRect (&yRect, -(half_cell << 1), -half_cell);
 CopyBits (ibp, &tempBits, irp, &yRect, srcXor, 0);
 CopyBits (&maskBits, &tempBits, &xRect, &xRect, srcAnd, 0);
 CopyBits (&tempBits, ibp, &xRect, irp, srcXor, 0);
 OffsetRect (&yRect, half_cell << 1, half_cell << 1);
 CopyBits (&tempBits, ibp, &xRect, &yRect, srcXor, 0);
 /*
  *Phase 3 - Refine mask for next smaller cell size
  */
 half_cell >>= 1;/* Reduce cell size by 1/2 */
 SetRect  (&xRect, 0, 0, 128, 128);            /* Refine mask */
 SetRect  (&yRect, 0, 128, 128, 256);
 CopyBits (&maskBits, &maskBits, &hackRect, &xRect, srcCopy, 0);
 CopyBits (&maskBits, &maskBits, &xRect, &yRect, srcCopy, 0);
 SetRect  (&xRect, 0, 0, 128, 256);
 SetRect  (&yRect, 128, 0, 256, 256);
 CopyBits (&maskBits, &maskBits, &xRect, &yRect, srcCopy, 0);
 }
 puts("<Return> to exit: ");
 gets(buf);
 } /*  END OF PROGRAM  */