free (piCount) ;
     free (plp) ;

     return hPalette ;
}

/*-------------------------------------------------------
   Structures used for implementing median cut algorithm
  -------------------------------------------------------*/

typedef struct           // defines dimension of a box
{
     int Rmin, Rmax, Gmin, Gmax, Bmin, Bmax ;
}
MINMAX ;

typedef struct           // for Compare routine for qsort
{
     int     iBoxCount ;
     RGBQUAD rgbBoxAv ;
}
BOXES ;

/*----------------------------
   FindAverageColor: In a box
  ----------------------------*/

static int FindAverageColor (int * piCount, MINMAX mm, 
                             int iRes, RGBQUAD * prgb)
{
     int R, G, B, iR, iG, iB, iTotal, iCount ;

          // Initialize some variables

     iTotal = iR = iG = iB = 0 ;
          
          // Loop through all colors in the box
          
     for (R = mm.Rmin ; R <= mm.Rmax ; R++)
     for (G = mm.Gmin ; G <= mm.Gmax ; G++)
     for (B = mm.Bmin ; B <= mm.Bmax ; B++)
     {
               // Get the number of pixels of that color

          iCount = piCount [PACK_RGB (R, G, B, iRes)] ;

               // Weight the pixel count by the color value

          iR += iCount * R ;
          iG += iCount * G ;
          iB += iCount * B ;

          iTotal += iCount ;
     }
          // Find the average color

     prgb->rgbRed   = (BYTE) ((iR / iTotal) << (8 - iRes)) ;
     prgb->rgbGreen = (BYTE) ((iG / iTotal) << (8 - iRes)) ;
     prgb->rgbBlue  = (BYTE) ((iB / iTotal) << (8 - iRes)) ;

          // Return the total number of pixels in the box
     
     return iTotal ;
}

/*------------------------------
   CutBox:  Divide a box in two
  ------------------------------*/

static void CutBox (int * piCount, int iBoxCount, MINMAX mm,
                    int iRes, int iLevel, BOXES * pboxes, int * piEntry)
{
     int    iCount, R, G, B ;
     MINMAX mmNew ;
     
          // If the box is empty, return 

     if (iBoxCount == 0)
          return ;

          // If the nesting level is 8, or the box is one pixel, we're ready
          //   to find the average color in the box and save it along with
          //   the number of pixels of that color

     if (iLevel == 8 || (mm.Rmin == mm.Rmax && 
                         mm.Gmin == mm.Gmax && 
                         mm.Bmin == mm.Bmax))
     {
          pboxes[*piEntry].iBoxCount = 
               FindAverageColor (piCount, mm, iRes, &pboxes[*piEntry].rgbBoxAv) ;

          (*piEntry) ++ ;
     }
          // Otherwise, if blue is the largest side, split it

     else if ((mm.Bmax - mm.Bmin > mm.Rmax - mm.Rmin) && 
              (mm.Bmax - mm.Bmin > mm.Gmax - mm.Gmin))
     {
               // Initialize a counter and loop through the blue side

          iCount = 0 ;

          for (B = mm.Bmin ; B < mm.Bmax ; B++)
          {
                    // Accumulate all the pixels for each successive blue value

               for (R = mm.Rmin ; R <= mm.Rmax ; R++)
               for (G = mm.Gmin ; G <= mm.Gmax ; G++)
                    iCount += piCount [PACK_RGB (R, G, B, iRes)] ;

                    // If it's more than half the box count, we're there

               if (iCount >= iBoxCount / 2)
                    break ;

                    // If the next blue value will be the max, we're there

               if (B == mm.Bmax - 1)
                    break ;
          }
               // Cut the two split boxes.
               //   The second argument to CutBox is the new box count.
               //   The third argument is the new min and max values.

          mmNew = mm ;
          mmNew.Bmin = mm.Bmin ;
          mmNew.Bmax = B ;

          CutBox (piCount, iCount, mmNew, iRes, iLevel + 1, 
                  pboxes, piEntry) ;

          mmNew.Bmin = B + 1 ;
          mmNew.Bmax = mm.Bmax ;

          CutBox (piCount, iBoxCount - iCount, mmNew, iRes, iLevel + 1,
                  pboxes, piEntry) ;
     }
          // Otherwise, if red is the largest side, split it (just like blue)

     else if (mm.Rmax - mm.Rmin > mm.Gmax - mm.Gmin)
     {
          iCount = 0 ;

          for (R = mm.Rmin ; R < mm.Rmax ; R++)
          {
               for (B = mm.Bmin ; B <= mm.Bmax ; B++)
               for (G = mm.Gmin ; G <= mm.Gmax ; G++)
                    iCount += piCount [PACK_RGB (R, G, B, iRes)] ;

               if (iCount >= iBoxCount / 2)
                    break ;

               if (R == mm.Rmax - 1)
                    break ;
          }
          mmNew = mm ;
          mmNew.Rmin = mm.Rmin ;
          mmNew.Rmax = R ;

          CutBox (piCount, iCount, mmNew, iRes, iLevel + 1, 
                  pboxes, piEntry) ;

          mmNew.Rmin = R + 1 ;
          mmNew.Rmax = mm.Rmax ;

          CutBox (piCount, iBoxCount - iCount, mmNew, iRes, iLevel + 1,
                  pboxes, piEntry) ;
     }
          // Otherwise, split along the green size
     else 
     {
          iCount = 0 ;

          for (G = mm.Gmin ; G < mm.Gmax ; G++)
          {
               for (B = mm.Bmin ; B <= mm.Bmax ; B++)
               for (R = mm.Rmin ; R <= mm.Rmax ; R++)
                    iCount += piCount [PACK_RGB (R, G, B, iRes)] ;

               if (iCount >= iBoxCount / 2)
                    break ;

               if (G == mm.Gmax - 1)
                    break ;
          }
          mmNew = mm ;
          mmNew.Gmin = mm.Gmin ;
          mmNew.Gmax = G ;

          CutBox (piCount, iCount, mmNew, iRes, iLevel + 1, 
                  pboxes, piEntry) ;

          mmNew.Gmin = G + 1 ;
          mmNew.Gmax = mm.Gmax ;

          CutBox (piCount, iBoxCount - iCount, mmNew, iRes, iLevel + 1,
                  pboxes, piEntry) ;
     }
}

/*---------------------------
   Compare routine for qsort
  ---------------------------*/

static int Compare (const BOXES * pbox1, const BOXES * pbox2)
{
     return pbox1->iBoxCount - pbox2->iBoxCount ;
}

/*-----------------------------------------------------------------
   DibPalMedianCut:  Creates palette based on median cut algorithm
  -----------------------------------------------------------------*/

HPALETTE DibPalMedianCut (HDIB hdib, int iRes)
{
     BOXES        boxes [256] ;
     HPALETTE     hPalette ;
     int          i, iArraySize, iCount, R, G, B, iTotCount, iDim, iEntry = 0 ;
     int        * piCount ;
     LOGPALETTE * plp ;
     MINMAX       mm ;

          // Validity checks
    
     if (DibBitCount (hdib) < 16)
          return NULL ;

     if (iRes < 3 || iRes > 8)
          return NULL ;

          // Accumulate counts of pixel colors

     iArraySize = 1 << (3 * iRes) ;

     if (NULL == (piCount = calloc (iArraySize, sizeof (int))))
          return NULL ;

     AccumColorCounts (hdib, piCount, iRes) ;

          // Find the dimensions of the total box

     iDim = 1 << iRes ;

     mm.Rmin = mm.Gmin = mm.Bmin = iDim - 1 ;
     mm.Rmax = mm.Gmax = mm.Bmax = 0 ;

     iTotCount = 0 ;

     for (R = 0 ; R < iDim ; R++)
     for (G = 0 ; G < iDim ; G++)
     for (B = 0 ; B < iDim ; B++)
          if ((iCount = piCount [PACK_RGB (R, G, B, iRes)]) > 0)
          {
               iTotCount += iCount ;

               if (R < mm.Rmin) mm.Rmin = R ;
               if (G < mm.Gmin) mm.Gmin = G ;
               if (B < mm.Bmin) mm.Bmin = B ;

               if (R > mm.Rmax) mm.Rmax = R ;
               if (G > mm.Gmax) mm.Gmax = G ;
               if (B > mm.Bmax) mm.Bmax = B ;
          }

          // Cut the first box (iterative function).
          //   On return, the boxes structure will have up to 256 RGB values, 
          //        one for each of the boxes, and the number of pixels in
          //        each box.
          //   The iEntry value will indicate the number of non-empty boxes.

     CutBox (piCount, iTotCount, mm, iRes, 0, boxes, &iEntry) ;
     free (piCount) ;

          // Sort the RGB table by the number of pixels for each color

     qsort (boxes, iEntry, sizeof (BOXES), Compare) ;

     plp = malloc (sizeof (LOGPALETTE) + (iEntry - 1) * sizeof (PALETTEENTRY)) ;

     if (plp == NULL)
          return NULL ;

     plp->palVersion    = 0x0300 ;
     plp->palNumEntries = iEntry ;

     for (i = 0 ; i < iEntry ; i++)
     {
          plp->palPalEntry[i].peRed   = boxes[i].rgbBoxAv.rgbRed ;
          plp->palPalEntry[i].peGreen = boxes[i].rgbBoxAv.rgbGreen ;
          plp->palPalEntry[i].peBlue  = boxes[i].rgbBoxAv.rgbBlue ;
          plp->palPalEntry[i].peFlags = 0 ;
     }

     hPalette = CreatePalette (plp) ;

     free (plp) ;
     return hPalette ;
}