TweetFollow Us on Twitter

June 95 - Custom Color Search Procedures

Custom Color Search Procedures


[IMAGE 066-080_Wintermyre_final1.GIF]

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.


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.*

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.)

[IMAGE 066-080_Wintermyre_final2.GIF]

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.

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).

[IMAGE 066-080_Wintermyre_final3.GIF]

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

    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."


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?


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:

         (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.

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):
    WITH rgb DO
            red := 0;   { Set red and blue RGB components to 0, }
            blue := 0   { keeping only the green component. }
    GreenSepProc := FALSE

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):
BEGIN := BSR(, 1);     { Shift right to divide by 2. }
    DarkenBluesProc := FALSE

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;
    NothingSearchProc := FALSE

(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 TypesrcCopyditherCopySearch Procedure
Macintosh IIci, Apple 8*24 card215783
Macintosh Quadra 800, built-in video82123

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.


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.)

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;
        i:          INTEGER;
        gdh:        GDHandle;
        colorTab:   CTabHandle;
    { 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 ( = &
                            ( = &
                            ( = THEN 
                            { We found the color, so pass back its }
                            { index and return TRUE. }
                            position := i;
                            BruteSearchProc := TRUE;

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

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.

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.

[IMAGE 066-080_Wintermyre_final4.GIF]

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

    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 }

    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 }

    { 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 }
    RGBHashTablePtr = ^RGBHashTable;

    gRGBHash: RGBHashTablePtr;      { Global hash table pointer }

Listing 6. Checking the validity of the hash table

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

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);
        compressedRGB:  RGBCompressedColor;
        hashIndex:      INTEGER;
    { 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
            { Store color data in next available node. }
            WITH table[nextEntry] DO
                    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

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

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);
        state:      SignedByte;
        i:          INTEGER;
    { Save state of color table handle and lock it. }
    state := HGetState(Handle(ctab));

    { Clear hash table to empty. }

    WITH ctab^^ DO
            { 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)

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

Listing 9. Searching the hash table

FUNCTION RGBHashSearch (rgbHash: RGBHashTablePtr; rgb: RGBColor; 
      VAR index: LONGINT): BOOLEAN;
        compressedRGB:  RGBCompressedColor;
        hashIndex:      INTEGER;
        chainIndex:     INTEGER;
        nextIndex:      INTEGER;
    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
        { 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   
                  { If so, pass back its CLUT index and return TRUE }
                    index := table[chainIndex].index;
                    RGBHashSearch := TRUE;
            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  

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.


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. }

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

{ Remove search procedure right after drawing. }

Table 2. Comparison of search procedure speeds

Machine TypeProcedureProcedureProcedure
Macintosh IIci, Apple 8*24 card832234175
Macintosh Quadra 800, built-in video2369148

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.)

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.


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!)

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.


  • 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 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. *


Community Search:
MacTech Search:

Software Updates via MacUpdate

Skype - Voice-over-internet ph...
Skype allows you to talk to friends, family and co-workers across the Internet without the inconvenience of long distance telephone charges. Using peer-to-peer data transmission technology, Skype... Read more
PushPal 3.0 - Mirror Android notificatio...
PushPal is a client for Pushbullet, which automatically shows you all of your phone's notifications right on your computer. This means you can see who's calling or read text messages even if your... Read more
Logic Pro X 10.1.1 - Music creation and...
Apple Logic Pro X is the most advanced version of Logic ever. Sophisticated new tools for professional songwriting, editing, and mixing are built around a modern interface that's designed to get... Read more
VLC Media Player 2.2.0 - Popular multime...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more
Sound Studio 4.7.8 - Robust audio record...
Sound Studio lets you easily record and professionally edit audio on your Mac. Easily rip vinyls and digitize cassette tapes, or record lectures and voice memos. Prepare for live shows with live... Read more
LibreOffice - Free, open-source...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
VueScan 9.5.03 - Scanner software with a...
VueScan is a scanning program that works with most high-quality flatbed and film scanners to produce scans that have excellent color fidelity and color balance. VueScan is easy to use, and has... Read more
Freeway Pro 7.0.3 - Drag-and-drop Web de...
Freeway Pro lets you build websites with speed and precision... without writing a line of code! With its user-oriented drag-and-drop interface, Freeway Pro helps you piece together the website of... Read more
Cloud 3.3.0 - File sharing from your men...
Cloud is simple file sharing for the Mac. Drag a file from your Mac to the CloudApp icon in the menubar and we take care of the rest. A link to the file will automatically be copied to your clipboard... Read more
Cyberduck 4.6.5 - FTP and SFTP browser....
Cyberduck is a robust FTP/FTP-TLS/SFTP browser for the Mac whose lack of visual clutter and cleverly intuitive features make it easy to use. Support for external editors and system technologies such... Read more

The first ever action 3D card battler Al...
On the other hand, you probably haven’t played an action 3D card battler – until now. Step forward, All Star Legion. All Star Legion is a 3D QTE-based action RPG card battler, but fear not – the game itself isn’t as convoluted as its description.... | Read more »
Travel Back to the 1980s With the Making...
Headup Games has released a hilarious making of video for its upcoming title, Pixel Heroes: Byte & Magic. The game is a RPG/Roguelike where you control three heroes set to save the township of Pixton from an evil cult called The Sons of Dawn.... | Read more »
Heavenstrike Rivals Review
Heavenstrike Rivals Review By Campbell Bird on March 2nd, 2015 Our Rating: :: HEAVENLY STRATEGICUniversal App - Designed for iPhone and iPad Despite a few flaws, this free-to-play strategy game is a fun mix of new and old strategy... | Read more »
Get The Whole Story – Lone Wolf Complete...
Get The Whole Story – Lone Wolf Complete is Now Available and On Sale Posted by Jessica Fisher on February 27th, 2015 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Who Wore it Best? The Counting Dead vs....
Like it or not, the “clicker” genre, popularized by cute distractions like Candy Box and Cookie Clicker, seems like it’s here to stay. So Who Wore it Best? takes a look at two recent examples: The Counting Dead and AdVenture Capitalist. | Read more »
Card Crawl, the Mini Deck Building Game,...
Card Crawl, the Mini Deck Building Game, is Coming Soon Posted by Jessica Fisher on February 27th, 2015 [ permalink ] Tinytouchtales and Mexer have announced their new game, | Read more »
Witness an all new puzzle mechanic in Bl...
Well, BlastBall MAX is not one of those games and is bucking trends such as timers, elements of randomness, and tacked-on mechanics in favor of pure puzzle gameplay. When you first boot up the game you’ll see a grid made up of squares that are each... | Read more »
This Princess Has a Dragon and She isn’t...
This Princess Has a Dragon and She isn’t Afraid to Useit. | Read more »
Mecha Showdown Review
Mecha Showdown Review By Lee Hamlet on February 27th, 2015 Our Rating: :: IN A SPINUniversal App - Designed for iPhone and iPad Mecha Showdown replaces traditional buttons with a slot machine mechanic in this robot fighting game,... | Read more »
Reliance Games and Dreamworks Unveil Rea...
Reliance Games and Dreamworks Unveil Real Steel Champions Posted by Ellis Spice on February 27th, 2015 [ permalink ] Reliance Games and Dreamworks have announced that a third game in | Read more »

Price Scanner via

27-inch 3.5GHz 5K iMac in stock today and on...
 B&H Photo has the 27″ 3.5GHz 5K iMac in stock today and on sale for $2299 including free shipping plus NY sales tax only. Their price is $200 off MSRP, and it’s the lowest price available for... Read more
Apple Launches Free Web-Based Pages and Other...
Apple’s new Web-only access to iWork productivity apps is a free level of iCloud service available to anyone, including people who don’t own or use Apple devices. The service includes access to Apple... Read more
Survey Reveals Solid State Disk (SSD) Technol...
In a recent SSD technology use survey, Kroll Ontrack, a firm specializing in data recovery, found that while nearly 90 percent of respondents leverage the performance and reliability benefits of SSD... Read more
Save up to $600 with Apple refurbished Mac Pr...
The Apple Store is offering Apple Certified Refurbished Mac Pros for up to $600 off the cost of new models. An Apple one-year warranty is included with each Mac Pro, and shipping is free. The... Read more
Updated Mac Price Trackers
We’ve updated our Mac Price Trackers with the latest information on prices, bundles, and availability on systems from Apple’s authorized internet/catalog resellers: - 15″ MacBook Pros - 13″ MacBook... Read more
Apple CEO Tim Cook to Deliver 2015 George Was...
Apple CEO Tim Cook will deliver the George Washington University’s Commencement address to GWU grads on May 17, at which time he will also be awarded an honorary doctorate of public service from the... Read more
Apple restocks refurbished Mac minis for up t...
The Apple Store has restocked Apple Certified Refurbished 2014 Mac minis, with models available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: - 1.4GHz... Read more
Save up to $50 on iPad Air 2s, NY tax only, f...
 B&H Photo has iPad Air 2s on sale for $50 off MSRP including free shipping plus NY sales tax only: - 16GB iPad Air 2 WiFi: $469.99 $30 off - 64GB iPad Air 2 WiFi: $549 $50 off - 128GB iPad Air 2... Read more
16GB iPad Air 2 on sale for $447, save $52
Walmart has the 16GB iPad Air 2 WiFi on sale for $446.99 on their online store for a limited time. Choose free shipping or free local store pickup (if available). Sale price for online orders only,... Read more
iMacs on sale for up to $205 off MSRP
B&H Photo has 21″ and 27″ iMacs on sale for up to $205 off MSRP including free shipping plus NY sales tax only: - 21″ 1.4GHz iMac: $1029 $70 off - 21″ 2.7GHz iMac: $1199 $100 off - 21″ 2.9GHz... Read more

Jobs Board

Sr. Technical Services Consultant, *Apple*...
**Job Summary** Apple Professional Services (APS) has an opening for a senior technical position that contributes to Apple 's efforts for strategic and transactional Read more
Event Director, *Apple* Retail Marketing -...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global engagement strategy and team. Delivering an overarching brand Read more
*Apple* Pay - Site Reliability Engineer - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.