The Microsoft Windows Palette Manager

Skip to main content (skip navigation menu)
Letterhead logo






The Microsoft Windows Palette Manager

 

Programs using screen resolutions with 256 colours are popular, because they offer a good compromise between memory requirements and speed on the one hand and image quality on the other hand. The burden rests on the shoulders of the application programmer to get most out of these 256 colour resolutions, however. This was fairly easy under DOS, but Microsoft Windows shields you from direct access to the hardware palette. There is only one path to steer your Windows application away from palette troubles: knowledge.

Indeed, many of us would wish the palette to go away. Programming all graphics in a plain RGB format would make some tasks faster and many tasks easier. Additionally, every video adapter sold in the past few years has had an RGB capability. So why not forget about palettes and focus solely on 16-bit and 24-bit RGB modes? The answers are divers:

In short, palettes are still the useful, but for different reasons than in the early days of video hardware. Then, palettes were a good hardware compromise for cheap video cards; today palettes are a compromise for applications that need the quickest graphics and few colours.

section separator

This document explores the Microsoft Windows Palette Manager. The focus of the document is on identity palettes, which are needed for fast animation. Indeed, this document is the fruit of the development of our animation engines EGI and AniSprite, and it led to the development of PaletteMaker.

There are a few features of the Palette Manager (and related technologies) that this document, by intent, does not discuss:

Preliminaries

To start with, palette creation and updating is slow in Microsoft Windows, partly due to the extremely complex interaction of the palette manager, GDI and display drivers (with many internal caches and translation tables that need to be rebuilt) and partly because Microsoft Windows broadcasts a WM_PALETTECHANGED message to all existing (non-child) windows when a new palette is selected. Therefore, avoid palette animation and, if at all possible, use a single palette for the entire application.

Microsoft Windows uses 20 system colours (also referred to as "static colours"). These colours occupy the first 10 and the last 10 slots in the palette (so, in a palette with 256 colours the system colours are 0-9 and 246-255). If you include those system colours in your palette (at the same position as Microsoft Windows puts them), the application can create a so-called "identity palette". Microsoft Windows draws bitmaps much faster if an identity palette is used.

At this point, a few terms specific to Microsoft Windows have been mentioned and it also becomes clear that there are several kinds of palettes. To shed light on the road that lies ahead, let me present a concise glossary of terms.

Glossary of terms

From DIB colour table to system palette


Palette mappings

Figure 1: Palette mappings

In the pipeline from an image (or an animation frame) in DIB format to the computer display, there are three palettes and two mappings from one palette to the next (figure 1):

  1. An 256 colour image consists of a bitmap and a palette. Assume for the moment that these are stored in DIB format. At some point, before an application can display a DIB, it must convert the DIB to a "hardware" representation. For example, the function CreateDIBitmap() creates a device dependent bitmap (DDB) from a DIB. A DDB does not contain colour information, so in the conversion, the colours in the DIB are mapped to the currently selected logical palette.
  2. The logical palette is mapped to the system palette when you realize the logical palette. How this happens depends on the state of the window and the flags of the logical palette. It is discussed in more detail in the next few paragraphs.

Both these mappings cost time. However, you can usually avoid one of these mappings. The goal in fast animation is to avoid both mappings; an "identity palette" achieves this.

Palette realization

Once a palette object has made with CreatePalette(), it must be selected and realized in a device context. Subsequent drawing will be relative to the logical palette only after realization of the palette. It is not enough to just select the palette. Thus the following two function calls are essentially always found as a pair:

    SelectPalette(hdc, hpalette, FALSE);
    RealizePalette(hdc);

In the call to SelectPalette(), the palette is marked as either a "background" palette or as a "possibly-foreground" palette. The latter case indicates that the foreground/background status of the palette depends on the status of the window to which the device context refers: only if the window is the active window or a child of the active window, the palette is indeed a foreground palette.

When a palette is realized, the real work begins: each entry in the logical palette has to be mapped to an entry in the system palette. How this happens depends on the status of the entries of the system palette, the flags of each entry in the logical palette, and whether the logical palette is a foreground or a background palette.

The Palette Manager keeps track of which entries in the system palette are in use and which entries are still available (free). The static colours are considered as "permanently used". Then, for every colour in the logical palette, the Palette Manager finds the closest entry in the system palette.

According to Ron Gery's article, the formula used for the colour comparison is [Gery, 1992]:

|DC| = sqrt( DR² + DG² + DB²)

If an exact match is found, the entry in the logical palette maps to the matching entry in the system palette. When there is no exact match, the Palette Manager tries to allocate a "free" entry in the system palette, and if that fails, it maps the entry to the closest colour in the system palette. The difference between a foreground and a background palette is that at the start of the realization all entries in the system palette (except the static colours) are freed. Therefore, in practice, a foreground palette changes the system palette and a background palette finds a best map to the system palette without changing the system palette. (Actually, realizing a background palette can change one or more entries in the system palette. This occurs, for instance, when the foreground palette has less than 256 unique colours. Ron Gery's article has in depth coverage of these special cases; this appendix ignores them, because identity palettes are always full 256-colour palettes.)

The realization process is actually more complicated than described above because of the flags that every entry in a logical palette may have. The PC_EXPLICIT flag is used to copy an entry from the system palette into the logical palette (rather than the other way around). For palette animation, the entries in the logical palette need the PC_RESERVED flag (palette animation is not further discussed in this paper). If an entry in the logical palette is marked with the PC_NOCOLLAPSE flag, the palette manager allocates a free entry in the system palette if one is available and only uses the closest colour match if there are no (more) free entries in the system palette. The difference with the normal case (with the flags set to zero) is that a free entry is allocated even when an exact match is found.

The RealizePalette() function creates a translation (or mapping) table. A translation table contains 256 indices that map the logical palette to the system palette. This table is then passed to the display driver, which uses it to translate pixel values (relative to the logical palette) to the correct colour indices in the system palette. If the translation table turns out to contain the values 0, 1, 2,... 255 (an identity mapping), no translation is required and the Palette Manager passes NULL to the display driver (hence the performance gain of an identity palette).

The first sentence of the preceding paragraph that said that RealizePalette() creates "a translation table" is not entirely correct. When a palette is realized for the first time, the Palette Manager always calculates the foreground mapping. So if the first realization of a palette is for a background palette, RealizePalette() makes two translation tables: one for the background mapping (which was requested) and one for the foreground mapping. The internal representation of a palette object (in GDI) stores both a foreground and a current mapping (see [Cogswell, 1993]). Inversely, when a palette is realized for the second (or later) time and it is realized in the foreground, the Palette Manager simply copies the previously calculated foreground mapping. The important point here is that the foreground mapping of a palette is calculated once and remains fixed for the life of the palette. To have the foreground mapping recalculated, call UnrealizeObject() on the palette.

Windows 2000 is stricter in deciding who may change the system palette than other versions of Windows. In the other versions of Windows, any window is able to change the system palette (note that realizing a "background palette" may still change the system palette). Not so in Windows 2000: if the window that realizes a logical palette has the WS_EX_TOOLWINDOW extended style set, Windows just won't change the system palette.

Creating an identity palette

As already mentioned above, animation benefits from the use of an identity palette. The criterion for an identity palette is that the logical palette is identical to the system palette. That is, not only do the logical palette and the system palette contain the same colours, they contain these colours at the same positions as well.

The first requirement, the logical and system palettes must contain the same colours, means that the logical palette must contain the 20 "system colours", and it must also contain them at the same position as the system palette. In other words, according to the documentation for the Device Driver Kit 3.1, the palette entries 0 to 9 and 246 to 255 must have the following RGB values:

The Windows "system colours"
 Index   Red  Green  Blue   Colour
  0 0 0 0 black 1 128 0 0 dark red 2 0 128 0 dark green 3 128 128 0 brown (dark yellow/pea green) 4 0 0 128 dark blue 5 128 0 128 dark magenta (lavender) 6 0 128 128 dark cyan 7 192 192 192 light grey 8 192 220 192 pastel green 9 166 202 240† pastel blue 246 255 251 240 soft white 247 160 160 164 medium grey 248 128 128 128 dark grey 249 255 0 0 bright red 250 0 255 0 bright green 251 255 255 0 yellow 252 0 0 255 bright blue 253 255 0 255 magenta 254 0 255 255 cyan 255 255 255 255 white
† Some drivers implement "pastel blue" as RGB(164,200,240).

Once the image file has a palette with the static colours, the next step is to create/select the palette in a way that the mapping of the logical palette to the system palette is one-to-one. There are three hurdles to overcome:

  1. The "colour matching" algorithm of the Palette Manager should be turned off. The Palette Manager should just allocate a new entry in the system palette for every entry in the logical palette. The PC_NOCOLLAPSE flag achieves this.
  2. The 20 entries for the static colours are an exception. They should not have the PC_NOCOLLAPSE flag. In addition, one of the static colours ("pastel blue" at palette index 9) has a slightly different RGB value on several video cards and, starting with Windows 95, up to four other "static" palette entries may also vary. A simple solution is to copy the static colours from the system palette to the logical palette (Microsoft Windows' function GetSystemPaletteEntries()).
  3. When allocating a free entry in the system palette, the Palette Manager prefers to allocate an entry that is not in use by any other palette. If that fails, and if you are realizing a foreground palette, the palette manager overwrites the entries of the other (now background) palette. As a result, when some application creates a palette with less then 256 colours and you start your program after that, the first entries of your palette are allocated at the top of the system palette —while you want all entries in your palette to go to exactly the same positions in the system palette. To avoid this phenomenon, select and realize a dummy full 256-colour palette before the realization of the "real" palette. This process is called "clearing the palette".

With the preceding analysis and the Microsoft Windows SDK documentation, it should not take much effort to create an identity palette. For completeness, the code snippets to clear the system palette and to create an identity palette follow:

Clear the system palette
void ClearSystemPalette(HWND hwnd)
{
  struct {
    WORD palVersion;
    WORD palNumEntries;
    PALETTEENTRY palEntry[256];
  } logpal = {
    0x300,
    256
  };
  HPALETTE hpal;
  HDC hdc;
  int i;

  /* Reset everything in the system palette to black */
  memset(logpal.palEntry, 0, sizeof logpal.palEntry);
  for (i = 0; i < 256; i++)
    logpal.palEntry[i].peFlags = PC_NOCOLLAPSE;

  /* Create, select, realize, deselect, and delete the palette */
  hpal = CreatePalette((LOGPALETTE *)&logpal);
  if (hpal) {
    hdc = GetDC(hwnd);
    hpal = SelectPalette(hdc,hpal,FALSE);
    RealizePalette(hdc);
    hpal = SelectPalette(hdc,hpal,FALSE);
    ReleaseDC(hwnd, hdc);
    DeleteObject(hpal);
  } /* if */
}

The above routine and the next one were adapted from the WinG documentation. The most important change is that the ClearPalette() function takes a window handle as its only parameter and uses it to obtain a device context handle (HDC). The original ClearPalette() function used a "display" device context by passing NULL in the GetDC() function. This raises an interesting issue: is the palette realized in a "display" DC a foreground or a background palette? As it turns out: neither. Another little quirk in the Palette Manager is that it keeps track of which entries in the system palette have ever been allocated. Realizing a palette in a display device context only sets those entries in the system palette that have not ever been set before. However, as was described above as the third "hurdle", it is not enough to only clear those entries.

Creating an identity palette
HPALETTE CreateIdentityPalette(LPRGBQUAD lpRGB)
{
  struct {
    WORD palVersion;
    WORD palNumEntries;
    PALETTEENTRY palEntry[256];
  } logpal = {
    0x300, 256
  };
  int i, nStatCols;

  /* The number of static colours should be 20, but inquire it anyway */
  nStatCols = GetDeviceCaps(hdc, NUMRESERVED);

  /* Copy the entire system palette, though we only need the first 10
   * and the last 10 entries */
  GetSystemPaletteEntries(hdc, 0, 256, logpal.palEntry);

  /* Clear the peFlags of the lower and upper static colours */
  for (i = 0; i < (nStatCols / 2); i++)
    logpal.palEntry[i].peFlags = 0;
  for (i = 256 - (nStatCols / 2); i < 256; i++)
    logpal.palEntry[i].peFlags = 0;

  /* Set the palette entries to the DIB colours */
  for (i = (nStatCols / 2) ; i < 256 - (nStatCols / 2); i++) {
    logpal.palEntry[i].peRed   = lpRGB[i].rgbRed;
    logpal.palEntry[i].peGreen = lpRGB[i].rgbGreen;
    logpal.palEntry[i].peBlue  = lpRGB[i].rgbBlue;
    logpal.palEntry[i].peFlags = PC_NOCOLLAPSE;
  } /* for */

  return CreatePalette((LOGPALETTE *)&logpal);
}

Another detail to cover is when to clear the palette. It is undesirable to clear the palette every time you select and realize your "drawing" palette. Palette realization is quick if it is a foreground palette and if it is the same as the current foreground palette (in other words, the Palette Manager detects that nothing changes, and skips most of the work). But if you clear the palette before selecting the real palette, the Palette Manager will go ahead to create a palette mapping... twice.

As long as an application that realized an identity palette is the foreground application, no other application can break the identity mapping. Only when another program is activated, this program can change the system palette. Also, there is no sense in clearing the palette if our application is not the foreground application. The purpose of clearing the system palette is to help creating an identity palette, and creating and identity palette will probably fail for a background palette. In conclusion, a good time to clear the palette is when your application is activated, i.e. upon reception of the WM_ACTIVATEAPP message with wParam set to 1.

Messages

A palette-aware application should respond to two "palette" messages. The message WM_QUERYNEWPALETTE indicates that a window becomes active. At this time, the window can realize its palette and (if that causes the palette mapping to change) redraw itself. WM_PALETTECHANGED informs all "non-child" windows that the system palette has changed. Therefore a palette aware application should redraw itself. One exception is that a window should ignore the WM_PALETTECHANGED message if its own palette realization (in the foreground) was the cause of the modified system palette. Child windows do not receive palette messages.

Several sources mention a third palette message: WM_PALETTEISCHANGING. Ron Gery describes it as a holdover from an early design of the palette manager and advises you to ignore it. Despite the stern warnings in even recent (Platform) SDK and MFC documentation by Microsoft to not ignore the message, I suggest that you follow Ron Gery's advice. By the way: Windows 95 and Windows 98 appear not to send this message; Windows NT 4.0 and Windows 2000 send it when the active application realizes its logical palette in the foreground (the "active" logical palette) and this active logical palette is different from the last active logical palette (regardless of whether the system palette changed since the last realization).

Windows 95 introduces the message WM_SYSCOLORCHANGE, which is sent when the user changes the desktop colour scheme. The main reason to watch this message is because desktop colour scheme selection may change the static colours. That is, when you get this message, you may want to regenerate your identity palette.

Responding to palette messages
   case WM_PALETTECHANGED:
      if ((HWND)wParam == hwnd)
         break;                 /* do not respond to own message */
      /* otherwise, drop through */
   case WM_QUERYNEWPALETTE:
      /* realize the palette to see whether redrawing is needed */
      hdc = GetDC(hwnd);
      hpal = SelectPalette(hdc, hpal, FALSE);
      result = RealizePalette(hdc);
      /* restore the palette (before releasing the DC) */
      hpal = SelectPalette(hdc, hpal, TRUE);
      RealizePalette(hdc);
      ReleaseDC(hwnd, hdc);
      /* now check for the need to redraw */
      if (result > 0)
         InvalidateRect(hwnd, NULL, TRUE);
      return TRUE;

Drawing in palette mode

Most of this paper is concerned with displaying bitmaps in palette mode (or displaying 256 colour bitmaps). Of course, you may want to draw other graphics, lines, rectangles, text... When you set the colours for the pens or brushes for these graphic primitives, use the PALETTEINDEX() or PALETTERGB() macros. Using the RGB() macro will only pick up one of the twenty system colours in 256 colour modes.

Palettes in RGB modes

If the video card/driver is set to an RGB mode, the hardware does not use a palette. If you wish to display a 256-colour image, you must still create and select/realize a logical palette, so that the system knows how to map the pixel values to RGB colours. Remember that in a 256-colour image, every pixel in the image is one byte, which is an index in a colour table.

Microsoft Windows still supports a Palette Manager in RGB mode, but there are several things that change:

From a programming viewpoint, the biggest change is that in an RGB mode the static colours are gone. The Palette Manager does no longer reserve any entries in the palette.

All in all, there is enough reason to want to know whether the video adapter is in RGB mode or in palette mode (for one thing, if the video adapter is in RGB mode, we'll ignore the static colours and just use the complete palette). Even such a simple question seems not-so-easy to answer reliably in Microsoft Windows. The code snippet below gives the technique that our software uses to detect whether a video mode supports a palette.

Does the video card support a palette?
BOOL IsPaletteDevice(void)
{
  HDC hdc    = GetDC(0);
  int rc     = GetDeviceCaps(hdc,RASTERCAPS);
  int bits   = GetDeviceCaps(hdc,BITSPIXEL);
  int planes = GetDeviceCaps(hdc,PLANES);
  ReleaseDC(0, hdc);
  bits *= planes;       /* bits == flat number of bits per pixel */
  /* The only hardware modes that use a palette are modes
   * with 2, 4, 16 and 256 colours.
   * Microsoft Windows supports palette operations only
   * on displays with 256 colours. That is, in 16-colour
   * mode, you cannot use the palette.
   * So you only need to check for the RC_PALETTE bit if
   * the number of bits per pixel is 8.
   */
  return (rc & RC_PALETTE) != 0 && bits == 8;
}

Palettes and memory DCs

For the sake of simplicity, I have been terribly inaccurate in the description above, by plainly talking about "device contexts" without specifying what kind(s) of display contexts this all applies to. Device contexts (HDCs) usually present yet another layer of complexities in Windows programming. Fortunately, in the case of the Palette Manager, the rules are fairly simple:

Palettes and DIB sections

If you recall figure 1 (reproduced below), you will notice that this paper has, so far, not talked much about the first mapping: from DIB colour table to the logical palette. The assumption was that the application created the logical palette from the DIB colour table and then displayed the DIB with a call to StretchDIBits() or by first creating a DDB and then calling BitBlt().

Palette mappings

And what if the DIB colour table changes in the course of the animation? Well, you make a new logical palette. If you are using BitBlt() you also create a new DDB matching the new logical palette.

However, if the application is using a DIB section, you create a logical palette from the DIB colour table as usual and then also pass the DIB colour table to the DIB section with a call to SetDIBColorTable(). Despite what the "Platform SDK" documentation of RealizePalette() appears to imply, RealizePalette() does not adjust the colour table of the DIB section. (I am referring to the Platform SDK documentation as published on the Microsoft Developer Network CD's; the documentation of this particular function is dated at February 16, 1999).

Of interest is also KnowledgeBase article Q137232, which can be summarized as: a logical palette selected in a DIB section can cause wrong colours to be displayed (or even a general protection fault) unless that logical palette is first selected into a screen DC. This happens because an internal palette structure is not set up until the logical palette is selected into a screen DC. Although the article mentions Windows 95 only and is dated at September 27, 1995, rest assured that this bug is still present in Windows 98 2nd edition (my tests indicate that Windows NT does not have this bug). So any logical palette that you wish to use on a DIB section must be (temporarily) selected in a screen DC before selecting it in the DIB section.

Finally, when using CreateDIBSection() with DIB_PAL_COLORS the internal colour table of the DIB section (the colour table that GetDIBColorTable() returns) is filled with RGB values and not with colour indices. The RGB values are looked up from the logical palette that is selected into the device context that is passed to CreateDIBSection(). In other words, the internal colour table of a DIB section always contain RGB values, regardless of how it was initialized.

As a side note, when drawing into a DIB section you can use the DIBINDEX() macro to select the index in the DIB colour table to draw with. You can also still use the PALETTEINDEX() and PALETTERGB() macros, and these will refer to the logical palette that is selected in the DC. Note however, that the PALETTEINDEX() and PALETTERGB() macros should be avoided for performance reasons. Drawing into a 256-colour DIB section (using GDI) with pens/brushes in colours set with those macros is extremely slow in Windows 95/98 (it is a bit better in Windows NT). It turns out that Windows builds a colour conversion map from the logical palette to the DIB section's colour table for every GDI call.

Concluding thoughts

References

Branch, Chris; "A Palette Spy Utility"; Windows Developer's Journal; August 1996.
A handy tool that finds the mapping of a logical palette to the system palette. Also gives information of undocumented areas of the Palette Manager and GDI. The Palette Spy utility itself can (as of this writing) be downloaded from the source code archives of Windows Developer's Journal. You can also download a modified version here (it includes a short description in a WinHelp file); updated November 1, 1999.
Cogswell, Jeffrey M.; "Undocumented Corner (Exploring Windows Palettes)"; Dr. Dobb's Journal; May 1993 (volume 18, issue 5)
The article covers several internal data structures (inside GDI) that the Palette Manager uses. In relation to this paper, the primary value of this article is that these data structures confirm Ron Gery's statements of the internal operation of the palette realization process.
Finnegan, Fran; "Windows Questions & Answers"; Microsoft Systems Journal; September/October 1991 (volume 6, issue 5).
The article contains a table with the "static" colours the Microsoft Windows 3.0 palette. Of interest is that the table mentions that some drivers use different colours, which are nearly the same as the "gamma corrected" colours from Ron Gery's technical article. In a later column (Microsoft Systems Journal, January/February 1992), Finnegan shows the same table, but without this note.
Gery, Ron; "The Palette Manager: How and Why"; Microsoft Developer Network Technology Group; March 1992.
This article is available on the Microsoft Developer Network CD-ROM. It is not light reading, but if you could follow this paper, you should have little trouble with it. Gery's article is an excellent technical description of palettes in Windows and it covers some details that this paper omits (notably: partial palettes). It comes of age, though. The article does not mention "identity palettes", but it does hint at the increase of BitBlt performance if the logical palette is the same as the system palette. It mentions the importance of clearing the palette, but for the wrong reason. It mentions gamma corrected palettes, but these go against the rules in the Microsoft Windows 3.1 Device Driver Kit. Coverage of non-palette "devices" like memory DCs and DIB sections is lacking, as are changes of the Palette Manager in versions of Windows after 3.1...
Microsoft Corporation; "WinG Programmer's Reference"; 1994.
The documentation for WinG library was the first to explicitly point out the importance of identity palettes. The documentation also gives the correct reason, though in rather vague terms, for clearing the system palette. Unfortunately, the printed code snippets are flawed.
Microsoft Corporation; The DirectX documentation; no title; no date; no document number.
DirectX (versions 5 and 6) comes with Microsoft Word and help files documenting the way DirectX palettes work (in both exclusive and windowed modes). The documentation presents an alternative way to create identity palettes. It also mentions the effect of desktop colour schemes on the "static colours" in the palette.