Custom Color Search Procedures

JIM WINTERMYRE

Color QuickDraw can be customized for specific tasks in many ways, most commonly by replacing the "bottleneck" procedures at its heart. But another, often overlooked way of customizing Color QuickDraw is by writing and installing custom color search procedures. These procedures are very useful for color separation and other color processing tasks, and for modifying QuickDraw's default drawing behavior to solve particular problems. This article reviews some Color QuickDraw basics, explores how color search procedures work, and presents a sample search procedure.

It's 2 A.M., and you're finally ready to draw your carefully constructed offscreen GWorld to a window. The GWorld is 32 bits deep and has been set up to contain a color ramp using 100 shades of red. You've already created a palette containing the 100 shades of red you need and attached it to your window, so the exact colors will be available on your 256-color screen. You plunk in your call to CopyBits, recompile, and . . . Ack! Instead of the expected smooth red ramp, you get an image with 16 distinct bands of color (see Figure 1 on the inside back cover of this issue).

What happened? How can you get the results you want? This article attempts to answer both of these questions, and a few others along the way. What happened has to do with the way Color QuickDraw converts colors to pixel values, so we'll start with a brief review of how this works. As for getting the results you want, one way is to use a custom color search procedure, which is the main subject of this article.

A QUICK REVIEW OF COLOR IN QUICKDRAW

Before delving into custom color search procedures, let's pause for a quick review of how QuickDraw converts between colors and pixel values. If you're already familiar with this, feel free to skip ahead to the section "Drawbacks of Inverse Tables."

How QuickDraw converts colors to pixel values and vice versa is discussed in Inside Macintosh: Imaging With QuickDraw , and in the Color Manager chapter of Inside Macintosh: Advanced Color Imaging (available on this issue's CD in draft form). Only a brief overview of this complex topic is provided here.*

DIRECT AND INDEXED COLOR
When an application does any drawing with Color QuickDraw, the ultimate result is to change some pixel values in a pixel map somewhere. Color QuickDraw in System 7 (and 32-Bit QuickDraw in earlier systems) supports two distinct types of color pixel maps:direct and indexed . In direct pixel maps (those with pixel depths of 16 or 32 bits) the pixel values in memory specify RGB color information for the pixel directly. For example, the 32-bit direct pixel value $00AABBCC specifies a red component of $AA, a green component of $BB, and a blue component of $CC -- 8 bits of color information each for the red, green, and blue components. (A 16-bit pixel value contains 5 bits of color information for each component.)

Figure 2. Indexed color

In indexed pixel maps (those with pixel depths up to 8 bits) the pixel values in memory don't directly specify the colors at all; instead they specify positions in a table of the available colors, called thecolor lookup table or just color table (sometimes called aCLU T ). Figure 2 shows an example; in this case, the 8-bit pixel value $1C in memory actually represents the RGB color $AAAA BBBB CCCC, found at position $1C in the color table.

Typically, when an application wants to draw in a particular color, it specifies the desired color directly using an RGBColor record, and never deals with pixel values at all. Color QuickDraw and the Color Manager convert between RGBColors and pixel values as needed. If the application is drawing to a direct pixel map, the color information itself is used to build the pixel value, and no color table is involved. On the other hand, if the application is drawing to an indexed pixel map, Color QuickDraw uses the index of the closest-matching color in the color table as the pixel value (this process is calledcolor mapping ). But searching the entire color table for a match every time a pixel value is needed would be far too time-consuming, so the Color Manager uses something called an inverse table to speed up the lookup process.

INVERSE TABLES
An inverse table is something like a "reverse" color table: whereas a color table is used to convert an index to a color, an inverse table is used to convert a given color to an index into a color table. The conversion operation goes like this: You take some of the most significant bits of each color component and concatenate them, then use the resulting number as an index into the inverse table. The entry at that location in the inverse table holds, in turn, the index of the closest-matching available color in the corresponding color table. Figure 3 illustrates the process. Note that the closest-matching color returned by this process need not match the original color exactly, since only a few of the most significant bits were used (the default is 4 bits).

Figure 3. Inverse table with 4-bit resolution

Inverse tables are described in the Color Manager chapter of Inside Macintosh: Advanced Color Imaging. *

The number of bits each color component contributes to the inverse-table index is called theresolution of the inverse table. Higher resolutions would give you greater accuracy in color mapping, but also greatly increase the memory needed to hold the inverse table, so a maximum of 5-bit resolution is allowed. (Since there are three color components, each additional bit of resolution multiplies the size of the table eightfold.) You can use the Color Manager routine MakeITable to create inverse tables with resolutions of 3, 4, or 5 bits per component.

As an aside, Listing 1 shows how to temporarily change the resolution of the current graphics device's inverse table to 5 bits. (To permanently change the inverse table resolution, set the gdResPref field of the GDevice record, set the iTabSeed field of gdITable to the result of GetCTabSeed, and call GDeviceChanged.)

Listing 1. Temporarily changing the resolution of the inverse table

VAR
    gdh:            GDHandle;
    oldITabRes:     INTEGER;

{ Get current graphics device. }
gdh := GetGDevice;

{ Get resolution of current inverse table. }
oldITabRes := gdh^^.gdITable^^.iTabRes;

{ Create a new inverse table at 5-bit resolution. }
MakeITable(NIL, NIL, 5);

{ Draw into a port on this device. }
...

{ Reconstruct inverse table at original resolution. }
MakeITable(NIL, NIL, oldITabRes);

Note that inverse tables aren't found in pixel maps or color graphics ports. They're instead associated withgraphics devices (astute readers may have noticed that the color table in Figure 3 was labeled "Graphics device color table" -- this is why). So when converting RGBColors to indexed pixel values, the Color Manager uses the inverse table in thecurrent graphics device . The implications of this are discussed in "The Importance of the Current Graphics Device."

DRAWBACKS OF INVERSE TABLES

The main problem with using inverse tables for color mapping is that because of their limited resolution, different colors can map to the same inverse table index. Inverse tables actually include some extra, undocumented information to allow the Color Manager to resolve such "hidden colors" -- but examining this extra information is time-consuming, so some speed-sensitive QuickDraw routines don't always use it. One of these routines happens to be CopyBits, which is what accounts for our "100 shades of red" problem.

Let's look at the problem in more detail. The offscreen GWorld holding our image is 32 bits deep, allowing the pixel values to specify RGB colors directly, with a precision of 8 bits per component. When we copy the image to a window on an indexed graphics device, CopyBits uses an inverse table to convert these pixel values from direct to indexed. If our inverse table has a resolution of 4 bits (the default), it can only distinguish 24 = 16 shades of red! (For example, all shades of red from RGB $0000 0000 0000 to $0FFF 0000 0000 will map to the same inverse-table index.) Soeven if all 100 shades are available in the destination device's color table, only 16 of them will actually be found and get drawn on the screen. This is why the actual result in Figure 1 has 16 bands of red instead of a continuum of shades.

The various depth conversion cases are discussed in the book Programming QuickDraw (see "Related Reading" at the end of this article) beginning on page 338. *

One way to deal with this problem would be to increase the resolution of the inverse table to 5 bits, which would give us 32 bands of red instead 16. Another approach would be to use the ditherCopy transfer mode in CopyBits. Both of these methods give better results but don't really solve the problem. After all, since wedo have all the shades of red available, shouldn't there be some way to match the colors exactly?

INTRODUCING COLOR SEARCH PROCEDURES

Knowing that inverse tables might not be adequate for some applications, the QuickDraw engineers designed in a "hook" to allow developers to provide their own color-mapping code. Each GDevice record has its own linked list of customcolor search procedures; there can be any number of such procedures installed for a given graphics device. As defined in the Color Manager chapter ofInside Macintosh: Advanced Color Imaging , a search procedure has the following interface:

FUNCTION SearchProc
         (VAR rgb: RGBColor; VAR position: LONGINT): BOOLEAN;

The rgb parameter is now always a VAR parameter. This was not true for direct-color destinations in 32- Bit QuickDraw prior to System 7. Also, note that Inside Macintosh Volume V incorrectly declared rgb as a value parameter.*

The Color Manager calls the search procedure with the RGB color it's trying to match, and expects the search procedure to do one of three things:

• Match the color -- In this case, the search procedure returns thepixel value for the color in the position parameter, and a result of TRUE. On an indexed graphics device, the position parameter should contain the index of the appropriate color in the graphics device's color table. On a direct graphics device, this parameter should be set to the appropriate direct-color value.
• Modify the color -- In this case, the search procedure modifies the rgb parameter and returns a result of FALSE. Color QuickDraw ignores the position parameter. See the next section for examples of using this technique.
• Do nothing -- In this case, the search procedure simply returns a result of FALSE, leaving its parameters untouched.

The Color Manager runs through the list of search procedures for the current graphics device, calling each procedure in turn until one of them returns TRUE. If no search procedure returns TRUE, it uses the default color-mapping method on the original (or possibly modified) color. For indexed graphics devices, this means using the inverse table. For direct graphics devices, "color mapping" simply involves truncating the RGBColor components to the appropriate size.

When called with an arithmetic transfer mode, CopyBits calls custom color search procedures before the arithmetic operation is performed. You can get around this by doing the desired operation first and then installing the search procedure and using CopyBits with srcCopy mode to display the result. *

The search procedure mechanism provides a solution to our "100 shades of red" problem. If we know where all the shades are located in the current graphics device's color table, we can write a search procedure that returns the correct index for any shade of red we pass to it. This will avoid the bands shown in the actual result in Figure 1 and instead produce the expected result, with the exact colors intended. Of course, this technique can be applied toany image if we know where to find all the colors we need in the color table; we'll examine the technique in more detail later.

MODIFYING SEARCH COLORS
The fact that the desired color is passed to the search procedure through a variable parameter is significant: it means that the procedure can actually modify the color value it receives. In this case, the search procedure should return FALSE, telling QuickDraw to perform the default color mapping on themodified color. This technique opens up several possible uses for search procedures.

One such application is color separation for three-color printing. The snippet called SearchProcs & Color Separation on this issue's CD shows how to do this. To separate all the greens from an image, for instance, you could install a search procedure that sets the red and blue RGB components to 0. Listing 2 shows a simple example.

Listing 2. Search procedure to separate green colors

FUNCTION GreenSepProc (VAR rgb: RGBColor; VAR position: LONGINT):
        BOOLEAN;
BEGIN
    WITH rgb DO
        BEGIN
            red := 0;   { Set red and blue RGB components to 0, }
            blue := 0   { keeping only the green component. }
        END;
    GreenSepProc := FALSE
END;

A similar search procedure could be used to darken or lighten an image. For example, you could use the code in Listing 3 to darken the blue component of an image by a factor of 2.

Listing 3. Search procedure to darken the blue component

FUNCTION DarkenBluesProc (VAR rgb: RGBColor; VAR position: LONGINT):
             BOOLEAN;
BEGIN
    rgb.blue := BSR(rgb.blue, 1);     { Shift right to divide by 2. }
    DarkenBluesProc := FALSE
END;

WHAT'S THE CATCH?
As usual, you do pay a price for all this functionality: search procedures definitely slow down the drawing process. Just how badly depends on several factors. In the case of CopyBits, the speed is most directly affected by the depth of the source and destination pixel maps. If the source pixel map uses indexed color, the search procedure needs to be called only once for each color in the source map's color table. For direct color, it must be called forevery pixel!

Consider the very simplest search procedure -- one that just returns FALSE without doing anything:

FUNCTION NothingSearchProc (VAR rgb: RGBColor;
        VAR position: LONGINT): BOOLEAN;
BEGIN
    NothingSearchProc := FALSE
END;

(A search procedure that did nothing but return TRUE would actually be faster, but would be useless, since the value in the position parameter would be garbage; returning FALSE ensures that at least normal color mapping will take place.) Table 1 compares the speed of a CopyBits operation with and without this search procedure, along with the speed of using the ditherCopy transfer mode in place of srcCopy. The source image is the one shown in Figure 1.

Table 1. Influence of search procedure on CopyBits speed

			srcCopy With
Machine Type	srcCopy	ditherCopy	Search Procedure
Macintosh IIci, Apple 8*24 card	21	57	83
Macintosh Quadra 800, built-in video	8	21	23

Note: Speeds are given in ticks, and are for ten successive calls to CopyBits, copying a 100-by-100-pixel, 32-bit-deep image to an 8-bit screen.

As you can see, CopyBits with an installed search procedure runs just a little slower than a dithered CopyBits. Note that the figures in the table are very rough. Several other factors contribute significantly to the speed difference when a search procedure is installed, such as the size of the source image and the number of colors it contains. You'll also get different results depending on what drawing routines you call with the search procedure installed. But the "dithered CopyBits" rule of thumb seems to work quite well as a general guide.

It's up to you to decide whether the speed penalty for using a custom color search procedure is worth the improved display quality. For image-processing applications, where color accuracy is probably more important than speed, search procedures can be very useful; for applications such as arcade- style video games, which depend on real-time graphics, they're probably not the way to go.

SOLVING THE "SHADES OF RED" PROBLEM

It's very common these days for applications to prepare an image offscreen, using a 32-bit GWorld, before transferring it to the screen for display. Despite the decreasing cost of 24-bit graphics cards, indexed 8-bit color is still a very common configuration, and even users with direct color capability spend a lot of time in 8-bit mode, which can lead to anomalies like the "100 shades of red" problem. As mentioned earlier, we can use a custom color search procedure to draw direct pixel images into indexed graphics devices with exact color reproduction, provided that all of the colors are actually available in the destination device's color table.

The way to make the colors available on the device is of course to use the Palette Manager, attaching a palette of the needed colors to the window you're drawing in. (This works only if other applications aren't "hogging" too many colors.) Getting the right colors from a picture or pixel map won't be discussed in any detail here, but the sample code uses the octree method described in the article "In Search of the Optimal Palette" indevelop Issue 10. It's probably easier to use the built-in popularand median color-sampling methods, but they truncate colors to 5 bits per component,meaning that they won't return separate palette entries for colors that differ only in the lower bits, as our shades of red do. The octree method doesn't truncate the colors, so it can be used to findall the colors in the image (assuming the image contains fewer than 256 colors). Another approach is demonstrated in the snippet CollectPictColors on the CD. Once the colors are available, we can write a search procedure that simply searches the graphics device's color table and returns the index of the requested color. (If the color table doesn't contain all the needed colors, the search procedure may have to return FALSE; QuickDraw will then use the inverse table to map these colors, which can lead to unexpected results. See the section "Evaluating the Results," later in this article, for more on this.)

THE BRUTE-FORCE APPROACH
In true hacker fashion, let's try the brute-force approach first: we can simply scan straight through the current graphics device's color table and stop when we find a match. Listing 4 shows the code.

Listing 4. Brute-force search procedure

FUNCTION BruteSearchProc (VAR theRGB: RGBColor;
        VAR position: LONGINT): BOOLEAN;
    VAR
        i:          INTEGER;
        gdh:        GDHandle;
        colorTab:   CTabHandle;
BEGIN
    { Get handle to current device. }
    gdh := GetGDevice;

    { Get color lookup table from current device. }
    colorTab := gdh^^.gdPMap^^.pmTable;

    { If the color table exists, loop through all its entries until }
    { we find a match. }
    IF colorTab <> NIL THEN
        WITH colorTab^^ DO
            FOR i := 0 TO ctSize DO
                WITH ctTable[i] DO
                    IF (theRGB.red = rgb.red) &
                            (theRGB.green = rgb.green) &
                            (theRGB.blue = rgb.blue) THEN 
                        BEGIN
                            { We found the color, so pass back its }
                            { index and return TRUE. }
                            position := i;
                            BruteSearchProc := TRUE;
                            EXIT(BruteSearchProc)
                        END;

    { We didn't find the color in the table, so return FALSE to }
    { tell QuickDraw to use the default mapping method. }
    BruteSearchProc := FALSE
END;

If we install this search procedure and draw the "100 shades of red" image, it will find all 100 shades and produce the expected image. Unfortunately, it'svery slow: a CopyBits with srcCopy mode using this search procedure takes 30 to 40 times as long as a dithered CopyBits.

HASH TABLES: A BETTER WAY
We can speed up our search procedure by using a hash table instead of a brute-force linear search. (Hash tables are familiar to most of you from basic computer science classes, and are described in any good book on algorithms, such asAlgorithms by Robert Sedgewick.) In our case, we'll use the RGB color value as a hash key to find the corresponding color table index. For our hash function, we'll use the MOD operator to find the remainder of the hash key relative to some suitably chosen prime number. The bigger we make this prime number, the better the performance of the hash function will be. Assuming that the target device uses 8-bit indexed colors (for most images, any lower color depth will yield a color table too small to hold all thecolors we need), we'll be working with a color table of 256 colors. We'll choose 251, a prime number near 256, as the divisor for our hash function. The MODoperator can't operate directly on 48-bit RGBColor records, so we'll use the high-order 8 bits of each color component to form a 32-bit integer of the form $00rrggbb (the same as a 32-bit pixel value) and use that for our key into the hash table.

Figure 4 shows the data structure containing our hash table. RGBHashArray is a zero-based array of records of type RGBHashNode. Each node holds a 32-bit color value (rgbComp), along with the index at which that color is stored in the color table. Nodes whose colors map to the same hash value are chained together in a linked list, with each node'snextfield holding the array index of the next node in the chain (this collision resolution method is calledseparate chaining ). The first kPrimeRecords (251) entries in the hash array hold header nodes for all possible hash values; these point into the rest of the array, which holds the data nodes themselves.

Figure 4. Hash table data structure

The data structure definitions for our hash table are shown in Listing 5. In addition to the array holding the table's contents, there's a short header containing the index of the next available data node along with the color table'sseed value at the time the hash table was built. We can use the latter to keep our hash table synchronized with the color table. Any time QuickDraw changes the contents of the graphics device's color table, it also changes its seed value. Thus if the seed values in the hash table and color table don't match (as checked by the routine in Listing 6), we know the color table has been changed and we need to rebuild our hash table before using it.

Listing 5. Hash table data structures

CONST
    kNumRecords = 256;     { Number of colors in color table }
    kPrimeRecords = 251;   { Number of hash entries }
    kTableSize = kPrimeRecords + kNumRecords - 1;
                            { Total size of (zero-based) hash array }

TYPE
    RGBCompressedColor = LONGINT;{ Color in 32-bit form ($00rrggbb) }

    { Data structure for hash table nodes }
    RGBHashNode = RECORD
        rgbComp:    RGBCompressedColor;
                                     { RGB color in compressed form }
        index:      INTEGER;         { Index of matching color in }
                                     { color table }
        next:       INTEGER      { Array index of next node in list }
    END;

    { Data structure for array to store hash table data }
    RGBHashArray = ARRAY[0..kTableSize] OF RGBHashNode;

    { Data structure for hash table itself }
    RGBHashTable = RECORD
       nextEntry:   INTEGER; { Array index of next unused data node }
       curCTabSeed: LONGINT; { Value of color table seed when hash }
                             { table was created (indicates when }
                             { hash table must be updated) }
        table:      RGBHashArray        { Hash table contents }
    END;
    RGBHashTablePtr = ^RGBHashTable;

VAR
    gRGBHash: RGBHashTablePtr;      { Global hash table pointer }

Listing 6. Checking the validity of the hash table

FUNCTION HashTableNeedsUpdate (ctab: CTabHandle;
       rgbHash: RGBHashTablePtr): BOOLEAN;
BEGIN
    HashTableNeedsUpdate := ctab^^.ctSeed <> rgbHash^.curCTabSeed
END;

There are two straightforward procedures, not shown here, for initializing the hash table and for clearing it out before building or rebuilding its contents (see the code on the CD for details). RGBHashInit zeroes out the entire hash table, while RGBHashClear clears only the list headers, making the table appear empty; there's no need to zero the data nodes themselves.

The procedure for inserting a color into the hash table is shown in Listing 7. It starts by doing some bit manipulation to convert the RGBColor to 32-bit form. It then uses the result to compute the hash-table index for the given color by finding its remainder modulo 251. Next, it fills in the fields of the next available hash node and inserts it at the head of the linked list starting at the computed index. Finally, it increments the hash table's nextEntry field to point to the next hash node in the array.

Listing 7. Inserting a color in the hash table

PROCEDURE RGBHashInsert (rgbHash: RGBHashTablePtr; rgb: RGBColor;
       cTabIndex: INTEGER);
    VAR
        compressedRGB:  RGBCompressedColor;
        hashIndex:      INTEGER;
BEGIN
    { Reduce 48-bit RGB value to 32-bit compressed form. }
    WITH rgb DO
        compressedRGB := BSL(BAND(red, $0000FF00), 8) +
            BAND(green, $0000FF00) + BSR(BAND(blue, $0000FF00), 8);

    { Compute hash-table index. }
    hashIndex := compressedRGB MOD kPrimeRecords;

    WITH rgbHash^ DO
        BEGIN
            { Store color data in next available node. }
            WITH table[nextEntry] DO
                BEGIN
                    rgbComp := compressedRGB;{ Actual RGB color }
                    index := cTabIndex;      { Index in color table }

                    { Insert this node at front of linked list. }
                    next := table[hashIndex].next;
                    table[hashIndex].next := nextEntry
                END;

            { Update to next available node. }
            nextEntry := nextEntry + 1
        END
END;

Building a hash table from the current graphics device's color table is relatively straightforward (Listing 8). First we save the state of the color table handle and lock it in case we do something that moves memory while the handle is dereferenced. (Our code doesn't currently do anything to move memory, but if we should change it in the future so that it does, this precaution ensures that it will still work.) Next we call our RGBHashClear procedure to clear the hash table's list headers to empty, and save thecolor table's seed value so that we can tell when the hash table needs updating. Finally, we step through the contents of the color table, inserting each color into the hash table with RGBHashInsert (Listing 7). Then all that's left is to restore the color tablehandle to its original state, and the hash table is ready for use by our search procedure.

Finally, we get to the real heart of the hash-table search procedure, RGBHashSearch (Listing 9). First we pack the 48-bit RGBColor value into 32 bits. Next, we computethe hash-table index for the given color and retrieve the list header for that hash value. If the list is nonempty, we step through it, comparing the RGB color stored in each node with the color we're looking for. If the colors match, we get the index of the corresponding color table entry from the data node and return TRUE. If we don't find the desired color, we return FALSE to indicate that the color was not in the hash table. Note that this will happen only if the source image contains colors that didn't fit in the color table (an example of this is given in the next section).

Listing 8. Building the hash table

PROCEDURE CTab2Hash (ctab: CTabHandle; rgbHash: RGBHashTablePtr);
    VAR
        state:      SignedByte;
        i:          INTEGER;
BEGIN
    { Save state of color table handle and lock it. }
    state := HGetState(Handle(ctab));
    HLock(Handle(ctab));

    { Clear hash table to empty. }
    RGBHashClear(rgbHash);

    WITH ctab^^ DO
        BEGIN
            { Save current seed value. }
            rgbHash^.curCTabSeed := ctSeed;

            { Step through contents of color table. }
            FOR i := 0 TO ctSize DO
                { Insert each color into hash table with its index. }
                WITH ctTable[i] DO
                    RGBHashInsert(rgbHash, rgb, i)
        END;

    { Restore original state of color table handle. }
    HSetState(Handle(ctab), state)
END;

Listing 9. Searching the hash table

FUNCTION RGBHashSearch (rgbHash: RGBHashTablePtr; rgb: RGBColor; 
      VAR index: LONGINT): BOOLEAN;
    VAR
        compressedRGB:  RGBCompressedColor;
        hashIndex:      INTEGER;
        chainIndex:     INTEGER;
        nextIndex:      INTEGER;
BEGIN
    WITH rgb DO 
        { Reduce 48-bit RGB value to compressed form. }
        compressedRGB := BSL(BAND(red, $0000FF00), 8) +
            BAND(green, $0000FF00) + BSR(BAND(blue, $0000FF00), 8);

    { Compute hash-table index. }
    hashIndex := compressedRGB MOD kPrimeRecords;

    WITH rgbHash^ DO
        BEGIN
        { Get array index of first node in list. }
        chainIndex := table[hashIndex].next;
        WHILE chainIndex <> 0 DO     { Loop till end of list. }
            { Is this the color we want? }
            IF table[chainIndex].rgbComp = compressedRGB THEN   
                BEGIN 
                  { If so, pass back its CLUT index and return TRUE }
                    index := table[chainIndex].index;
                    RGBHashSearch := TRUE;
                    EXIT(RGBHashSearch)
                END
            ELSE            { Otherwise go to the next node. }
                chainIndex := table[chainIndex].next;
        { If we got here, either there were no links at this }
        { hash-table address, or we reached the end of the }
        { list. Both cases indicate that the color is not in the }
        { CLUT, so return FALSE. }
        RGBHashSearch := FALSE  
    END
END;

Listing 10 shows how to install our search procedure for use in a drawing operation (gSearchProcUPP is a universal procedure pointer that points to our search procedure,which is simply a wrapper that calls RGBHashSearch). The Color Manager routines AddSearch and DelSearch, respectively, install and remove a search procedure for the current graphics device. Note that we install our search procedure just before the drawing operations that use it, and remove it immediately afterward. This is because the search procedure will be called forany drawing that occurs on the device it's attached to, and can significantly affect performance. Before installing and using our search procedure, we call our HashTableNeedsUpdate function (Listing 6) to compare the hash table's seedvalue with that in the current color table. The function returns TRUE if the seed values don't agree; this tells us torebuild the hash table with CTab2Hash (Listing 8) before using our search procedure.

Astute readers may wonder what happens if the drawing area spans more than one screen in a multiple-monitor configuration, since search procedures "belong" toparticular devices. Our sample code deals with multiple devices simply by calling DeviceLoopto do its drawing, installing the search procedure only on 8-bit color devices; on any other devices, CopyBits is called with ditherCopy mode.

EVALUATING THE RESULTS

Has all this optimization been worth it? Table 2 compares the speeds of the various search procedures, again using CopyBits in srcCopy mode to copy the image shown in Figure 1 from a 32- bit offscreen GWorld to an 8-bit device. For comparison, the speed of a "nothing" search procedure is also shown. Clearly, the work has paid off -- the hash-table search procedure is over 15 times as fast as the brute-force approach, and is certainly comparable to a dithered CopyBits. In some cases (for example, when drawing an image in a zoomed-in state), our hash table technique is actually as fast as (or faster than) a dithered CopyBits.

Although our hash-table search procedure gives impressive results, there are certainly cases where its performance is less than optimal. The hash table method assumes that all of the colors in the source image can be loaded into the current graphics device's color table. If this condition doesn't hold, the search procedure will still work, but it won't be able to find colors that aren't in the color table, so QuickDraw will use the default inverse-table mapping method for those colors. This can give unexpected results. For example, Figure 5 (on the inside back cover of this issue) shows a version of the "Better Bull's eye" image fromdevelop Issue 1 (from the article "Realistic Color for Real-World Applications"), drawn using the hash-table search procedure.

Listing 10. Installing and removing a search procedure

{ Get color table from current graphics device. }
gdh := GetGDevice;
ctab := gdh^^.gdPMap^^.pmTable;

{ Update hash table if necessary. }
IF HashTableNeedsUpdate(ctab, gRGBHash) THEN
    CTab2Hash(ctab, gRGBHash);

{ Install search procedure right before drawing. }
AddSearch(gSearchProcUPP);

{ Example drawing code }
CopyBits(BitMapPtr(thePixMap^)^, myWindow^.portBits, srcRect,
            destRect, srcCopy, NIL);

{ Remove search procedure right after drawing. }
DelSearch(gSearchProcUPP);

Table 2. Comparison of search procedure speeds

	Nothing	Brute-Force	Hash
Machine Type	Procedure	Procedure	Procedure
Macintosh IIci, Apple 8*24 card	83	2234	175
Macintosh Quadra 800, built-in video	23	691	48

Note: Speeds are given in ticks, and are for ten successive calls to CopyBits, copying a 100-by-100-pixel, 32-bit-deep image to an 8-bit screen.

The image in Figure 5 has more than 256 distinct colors. The results may look all right at first glance, but if we zoom in on the top right corner of the image (Figure 6, also on the inside back cover), we can see unwanted bands of gray. Some of the actual grays that were supposed to appear at these locations were not available in the graphics device's color table. As a result, they were color- mapped to the closest available gray at a 4-bit resolution, resulting in banding.

A similar problem can result if you have several windows displaying different images at once. The frontmost window will display correctly, but the others may not have the correct colors available. Usually this isn't important, since the frontmost window is generally the one you're concerned with. Typically, you should install the search procedure only when drawing in the frontmost window.

Another, more subtle case where our search procedure can give unexpected results is when the destination rectangle passed to CopyBits is smaller than the source rectangle. If the source image uses direct color, CopyBits will average the color values of adjacent pixels to produce the reduced image. This usually gives more visually appealing results than just dropping whole rows of pixels; but in this case, since averaging can produce colors that aren't in the color table, we run into the same kind of problem we've been discussing. (There's no problem when the destination rectangle isbigger than the source rectangle, since CopyBits will simply replicate existing pixels without introducing any new colors into the image.)

MAKING IT BETTER
Our hash-table search procedure is certainly much more efficient than the brute-force approach, but it can be improved still further. The most obvious idea would be to reimplement the code in assembly language for maximum efficiency, although this hampers portability and may not result in much of a speed improvement, depending on how good your compiler is. Another area for improvement might be the hashing algorithm itself: wecould try a different hash function or another method of collision resolution. However,since the hash table in this application is so small, this may not be worth the effort.

A useful extension would be to find the closest match for colors that arenot in the color table. This would alleviate the problems that occur when the image has too many colors to fit in the color table. Abandoning the hash table in favor of a tree-based algorithm might work, but it would be hard to make it as fast as the hash table method. Another approach might be to use some color-quantization algorithm to reduce the total number of colors in the image to 256 -- but of course that would mean changing the actual image data.

NOW IT'S UP TO YOU

Custom color search procedures are one of the least-used methods for customizing Color QuickDraw. In this article, we've seen several practical uses for them -- now it's up to your creativity to find others. (Let us know if you do!)

THE IMPORTANCE OF THE CURRENT GRAPHICS DEVICE
An often misunderstood fact about Color QuickDraw is this: Color QuickDraw uses the current graphics device's color table when converting colors into indexed pixel values, ignoring the color table of the destination pixel map.

The inverse table is built from the color table in the graphics device's pixel map, not the one in the destination pixel map. When you're drawing to the screen, this is not a problem, since the destination pixel map and the current graphics device's pixel map match (the destination pixel map is the device's pixel map). However, it can be a problem when you're drawing offscreen (for example, when using CopyBits to copy one offscreen pixel map to another). If the color table of the destination pixel map doesn't match that of the current graphics device, you won't get the results you expect. The destination pixel map's color table is used only when converting the other way, from a pixel value to a color (for example, when the pixel map is actually displayed on the screen).

One of the nice things about using GWorlds for offscreen graphics is that you don't have to worry about this -- GWorlds always have a graphics device associated with them, and routines such as SetGWorld ensurethat the GWorld's pixel map and the graphics device's pixel map are synchronized for correct color mapping.

RELATED READING

• Inside Macintosh: Advanced Color Imaging, on this issue's CD in draft form and forthcoming in print from Addison-Wesley. See the Color Manager chapter. This is the most thorough documentation in Inside Macintosh for color search procedures and color mapping with inverse tables. You'll also find some useful information in the Palette Manager chapter.
• Inside Macintosh: Imaging With QuickDraw (Addison-Wesley, 1994), Chapter 1, "Introduction to QuickDraw," Chapter 4, "Color QuickDraw," Chapter 5, "Graphics Devices," and Chapter 6, "Offscreen Graphics Worlds."
• Programming QuickDraw by David Surovell, Frederick Hall, and Konstantin Othmer (Addison-Wesley, 1992). Everything you ever wanted to know about QuickDraw. In particular, see "Graphics Devices" in Chapter 3, "Drawing in Color," and see "Pixel Processing Traps" and "Depth Conversion and Dithering" in Chapter 7, "Image Processing with QuickDraw."
• "In Search of the Optimal Palette" by Dave Good and Konstantin Othmer, develop Issue 10. How to use the Picture Utilities Package to obtain a palette with the best colors for displaying an image on an indexed device.
• Macintosh Technical Notes "Principia Off-Screen Graphics Environments" (QD 13) and "Of Time and Space and _CopyBits" (QD 21).

JIM WINTERMYRE (Internet winter@ai.rl.af.mil) is in the Air Force but doesn't get to fly a plane; instead, he gets to fly a Macintosh (he thinks he still deserves hazard pay, though). Officially, he's a Signals Intelligence Systems Engineer, but he always seems to find himself doing Macintosh programming in one form or another. When he's not busy solving the world's problems or coming up with another useless hack (the boundaries between the two have become fuzzy lately), he likes to engage in sports that let him pretend he really does have wheels on his feet. He was recently spotted playing jazz guitar in a smoky little bar in upstate New York. *

Thanks to our technical reviewers Joseph Maurer, Don Moccia, Guillermo Ortiz, and Nick Thompson. *