/*
 * CDE - Common Desktop Environment
 *
 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
 *
 * These libraries and programs are free software; you can
 * redistribute them and/or modify them under the terms of the GNU
 * Lesser General Public License as published by the Free Software
 * Foundation; either version 2 of the License, or (at your option)
 * any later version.
 *
 * These libraries and programs are distributed in the hope that
 * they will be useful, but WITHOUT ANY WARRANTY; without even the
 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 * PURPOSE. See the GNU Lesser General Public License for more
 * details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with these libraries and programs; if not, write
 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
 * Floor, Boston, MA 02110-1301 USA
 */
/* $XConsortium: ildither.c /main/5 1996/06/19 12:21:43 ageorge $ */
/**---------------------------------------------------------------------
***	
***    (c)Copyright 1991 Hewlett-Packard Co.
***    
***                             RESTRICTED RIGHTS LEGEND
***    Use, duplication, or disclosure by the U.S. Government is subject to
***    restrictions as set forth in sub-paragraph (c)(1)(ii) of the Rights in
***    Technical Data and Computer Software clause in DFARS 252.227-7013.
***                             Hewlett-Packard Company
***                             3000 Hanover Street
***                             Palo Alto, CA 94304 U.S.A.
***    Rights for non-DOD U.S. Government Departments and Agencies are as set
***    forth in FAR 52.227-19(c)(1,2).
***
***-------------------------------------------------------------------*/

    /*  Contains ilConvertRGBToPalette(), called by ilConvert() to convert the RGB pipe
        image to a palette image.  Contains dither / error diffusion code, but also
        code (from John Francis) for converting by finding the best "n" colors.
    */

#include <stdlib.h>

#include "ilint.h"
#include "ilpipelem.h"
#include "ilconvert.h"
#include "ilerrors.h"

/*  =========================== COLOR DITHER CODE =============================== */ 

        /*  Area dither: derived from software simulation of ELK hardware dither.
            Basically, use an 8x8 dither.
            For each pixel, fetch "kernel" based on position within image, mod 8.
            For each RGB, index into separate tables (which are index * "# levels - 1" 
            plus a litte), add kernel, and divide by 256.  Depending on the value of 
            "kernel", this will yield a RGB value which is +/- the "color slammed" value, 
            thus dithering.  See John Beck for details (or other ELK heavy).
        */

    /*  Multiply tables.  Each entry "i" (0..255) gives the value of:
            i * (mulFactor - 1) * 256/255
        (truncated).  Calculated by:

            main ()
            {   int     i, j, k;
                #define MULFACTOR 4
                i = 0;
                printf ("static unsigned short ilMul%d[256] = {\n", MULFACTOR);
                for (i = 0; i < 256; i++) {
                    printf ("%4d", (int)((double)i * (MULFACTOR-1) * (double)256 / (double)255));
                    if (i < 255) printf (",");
                    if ((i % 16) == 15) printf ("\n");
                    }
                printf ("};\n");
            }
    */

    /*  Tables generated by /il/util/gendithertables.c .
        "ilDitherKernel" was truncated to be 8 by 8.
    */

IL_PRIVATE const unsigned int _ilDitherKernel[64] = {
  2, 194,  50, 242,  14, 206,  62, 254,
130,  66, 178, 114, 142,  78, 190, 126,
 34, 226,  18, 210,  46, 238,  30, 222,
162,  98, 146,  82, 174, 110, 158,  94,
 10, 202,  58, 250,   6, 198,  54, 246,
138,  74, 186, 122, 134,  70, 182, 118,
 42, 234,  26, 218,  38, 230,  22, 214,
170, 106, 154,  90, 166, 102, 150,  86
};

IL_PRIVATE const unsigned short _ilMul8[256] = {
   0,   7,  14,  21,  28,  35,  42,  49,  56,  63,  70,  77,  84,  91,  98, 105,
 112, 119, 126, 133, 140, 147, 154, 161, 168, 175, 182, 189, 196, 203, 210, 217,
 224, 231, 238, 245, 252, 260, 267, 274, 281, 288, 295, 302, 309, 316, 323, 330,
 337, 344, 351, 358, 365, 372, 379, 386, 393, 400, 407, 414, 421, 428, 435, 442,
 449, 456, 463, 470, 477, 484, 491, 498, 505, 513, 520, 527, 534, 541, 548, 555,
 562, 569, 576, 583, 590, 597, 604, 611, 618, 625, 632, 639, 646, 653, 660, 667,
 674, 681, 688, 695, 702, 709, 716, 723, 730, 737, 744, 751, 758, 765, 773, 780,
 787, 794, 801, 808, 815, 822, 829, 836, 843, 850, 857, 864, 871, 878, 885, 892,
 899, 906, 913, 920, 927, 934, 941, 948, 955, 962, 969, 976, 983, 990, 997,1004,
1011,1018,1026,1033,1040,1047,1054,1061,1068,1075,1082,1089,1096,1103,1110,1117,
1124,1131,1138,1145,1152,1159,1166,1173,1180,1187,1194,1201,1208,1215,1222,1229,
1236,1243,1250,1257,1264,1271,1278,1286,1293,1300,1307,1314,1321,1328,1335,1342,
1349,1356,1363,1370,1377,1384,1391,1398,1405,1412,1419,1426,1433,1440,1447,1454,
1461,1468,1475,1482,1489,1496,1503,1510,1517,1524,1531,1539,1546,1553,1560,1567,
1574,1581,1588,1595,1602,1609,1616,1623,1630,1637,1644,1651,1658,1665,1672,1679,
1686,1693,1700,1707,1714,1721,1728,1735,1742,1749,1756,1763,1770,1777,1784,1792
};

IL_PRIVATE const unsigned short _ilMul4[256] = {
   0,   3,   6,   9,  12,  15,  18,  21,  24,  27,  30,  33,  36,  39,  42,  45,
  48,  51,  54,  57,  60,  63,  66,  69,  72,  75,  78,  81,  84,  87,  90,  93,
  96,  99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 129, 132, 135, 138, 141,
 144, 147, 150, 153, 156, 159, 162, 165, 168, 171, 174, 177, 180, 183, 186, 189,
 192, 195, 198, 201, 204, 207, 210, 213, 216, 219, 222, 225, 228, 231, 234, 237,
 240, 243, 246, 249, 252, 256, 259, 262, 265, 268, 271, 274, 277, 280, 283, 286,
 289, 292, 295, 298, 301, 304, 307, 310, 313, 316, 319, 322, 325, 328, 331, 334,
 337, 340, 343, 346, 349, 352, 355, 358, 361, 364, 367, 370, 373, 376, 379, 382,
 385, 388, 391, 394, 397, 400, 403, 406, 409, 412, 415, 418, 421, 424, 427, 430,
 433, 436, 439, 442, 445, 448, 451, 454, 457, 460, 463, 466, 469, 472, 475, 478,
 481, 484, 487, 490, 493, 496, 499, 502, 505, 508, 512, 515, 518, 521, 524, 527,
 530, 533, 536, 539, 542, 545, 548, 551, 554, 557, 560, 563, 566, 569, 572, 575,
 578, 581, 584, 587, 590, 593, 596, 599, 602, 605, 608, 611, 614, 617, 620, 623,
 626, 629, 632, 635, 638, 641, 644, 647, 650, 653, 656, 659, 662, 665, 668, 671,
 674, 677, 680, 683, 686, 689, 692, 695, 698, 701, 704, 707, 710, 713, 716, 719,
 722, 725, 728, 731, 734, 737, 740, 743, 746, 749, 752, 755, 758, 761, 764, 768
};

static const unsigned short _ilMul2[256] = {
   0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,
  16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  30,  31,
  32,  33,  34,  35,  36,  37,  38,  39,  40,  41,  42,  43,  44,  45,  46,  47,
  48,  49,  50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  60,  61,  62,  63,
  64,  65,  66,  67,  68,  69,  70,  71,  72,  73,  74,  75,  76,  77,  78,  79,
  80,  81,  82,  83,  84,  85,  86,  87,  88,  89,  90,  91,  92,  93,  94,  95,
  96,  97,  98,  99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127,
 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143,
 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,
 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175,
 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,
 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,
 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,
 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 256
};


        /*  Private data for cvt to palette: first part set when element added. */
typedef struct {
    ilBool          diffusion;              /* true if error diffusion; else dither */
    ilPtr           pTranslate;             /* ptr to lookup table (image) */
    ilByte          translate [256];        /* identity image if no mapImage given */
    unsigned short *pPalette;               /* palette to destroy or null */
    long           *pColorTable;            /* color lookup table (diffusion) or null */
    int             shifts[3];              /* RGB right shifts for diffusion */
    int             nColors;                /* for "choose colors": nColors to fit to */
    const unsigned short *pMulTable[3];           /* dither other than 484 only: pMul? */

        /*  Below data inited by Init() function. */
    long            width;                  /* width of src/dst images */
    long            srcRowBytes;            /* bytes/row of src image */
    ilPtr           pSrcPixels;             /* ptr to start of src pixels */
    long            dstRowBytes;            /* bytes/row of dst image */
    ilPtr           pDstPixels;             /* ptr to start of dst pixels */
    long            y;                      /* current logical line within the image */
    int            *pErrors;                /* error buffer (diffusion) or null */
    } ilDitherPrivRec, *ilDitherPrivPtr;


        /*  Init() function: init the counter of "y" within private; load image pixel
            address and rowBytes into private for faster reference in Execute().
        */
static ilError ilInitDitherRGB (
    ilDitherPrivPtr     pPriv,
    ilImageInfo        *pSrcImage,
    ilImageInfo        *pDstImage
    )
{

    pPriv->width = pSrcImage->width;
    pPriv->srcRowBytes = pSrcImage->plane[0].nBytesPerRow;
    pPriv->pSrcPixels = pSrcImage->plane[0].pPixels;
    pPriv->dstRowBytes = pDstImage->plane[0].nBytesPerRow;
    pPriv->pDstPixels = pDstImage->plane[0].pPixels;
    pPriv->y = 0;

        /*  If error diffusion, create an error buffer: 3 ints (1 per R/G/B), width + 2 
            for easy access to first / last value in line (point + 3 into it).
        */
    if (pPriv->diffusion) {
        pPriv->pErrors = (int *)IL_MALLOC_ZERO (sizeof (int) * 3 * (pPriv->width + 2));
        if (!pPriv->pErrors)
            return IL_ERROR_MALLOC;
        }
    return IL_OK;
}

        /*  Destroy() function: free pPriv->pPalette. */
static ilError ilDestroyDitherRGB (
    ilDitherPrivPtr     pPriv
    )
{
    if (pPriv->pPalette)
       IL_FREE (pPriv->pPalette);
    if (pPriv->pColorTable)
       IL_FREE (pPriv->pColorTable);
    return IL_OK;
}

        /*  Cleanup() function: only if diffusion: free pPriv->pErrors. */
static ilError ilCleanupDitherRGB (
    ilDitherPrivPtr     pPriv
    )
{
    if (pPriv->pErrors)
       IL_FREE (pPriv->pErrors);
    return IL_OK;
}


        /*  ---------------------- ilExecuteDitherRGB ------------------------ */
        /*  Execute() function: dither (IL_DITHER) to arbitrary powers of 2, based
            on shift values and pointers to "mul" tables in private using an 8x8 matrix.
        */
static ilError ilExecuteDitherRGB (
    ilExecuteData          *pData,
    long                    dstLine,
    long                   *pNLines
    )
{
ilDitherPrivPtr             pPriv;
long                        nLinesM1;
long                        srcRowBytes, dstRowBytes;
ilPtr                       pSrcLine, pDstLine;
long               x, yMod8Times8, width;
const unsigned short *pMulR, *pMulG, *pMulB;
ilPtr              pSrc, pDst, pTranslate;
unsigned long      pixel, kernel;
int                upShiftR, upShiftG;

    pPriv = (ilDitherPrivPtr)pData->pPrivate;
    width = pPriv->width;
    srcRowBytes = pPriv->srcRowBytes;
    pSrcLine = pPriv->pSrcPixels + pData->srcLine * srcRowBytes;
    dstRowBytes = pPriv->dstRowBytes;
    pDstLine = pPriv->pDstPixels + dstLine * dstRowBytes;

    yMod8Times8 = (pPriv->y & 7) << 3;
    nLinesM1 = *pNLines;
    if (nLinesM1 <= 0)
        return IL_OK;
    pPriv->y += nLinesM1;
    nLinesM1--;

        /*  Do dither; see comments above for overall approach */
    pTranslate = pPriv->pTranslate;
    upShiftR = 8 - pPriv->shifts[1];
    upShiftG = 8 - pPriv->shifts[2];
    pMulR = pPriv->pMulTable[0];
    pMulG = pPriv->pMulTable[1];
    pMulB = pPriv->pMulTable[2];

    do {
        pSrc = pSrcLine;
        pSrcLine += srcRowBytes;
        pDst = pDstLine;
        pDstLine += dstRowBytes;
        x = 0;
        while (x < width) {
            kernel = _ilDitherKernel [yMod8Times8 | (x & 7)];
            x++;
            pixel = ((pMulR[*pSrc++] + kernel) >> 8) << upShiftR;
            pixel += (pMulG[*pSrc++] + kernel) >> 8;
            pixel <<= upShiftG;
            pixel += (pMulB[*pSrc++] + kernel) >> 8;
            *pDst++ = pTranslate[pixel];
            }
        yMod8Times8 += (1 << 3);
        if (yMod8Times8 >= (8 << 3))
            yMod8Times8 = 0;
        } while (--nLinesM1 >= 0);

    return IL_OK;
}

        /*  ---------------------- ilExecuteDitherRGBTo484 ------------------------ */
        /*  Execute() function: dither to 484 and pack the given # of src lines. 
        */
static ilError ilExecuteDitherRGBTo484 (
    ilExecuteData          *pData,
    long                    dstLine,
    long                   *pNLines
    )
{
ilDitherPrivPtr             pPriv;
long                        nLinesM1;
long                        srcRowBytes, dstRowBytes;
ilPtr                       pSrcLine, pDstLine;
long               x, yMod8Times8, width;
const unsigned short    *pMul8, *pMul4;
ilPtr              pSrc, pDst, pTranslate;
unsigned long      pixel, kernel;

    pPriv = (ilDitherPrivPtr)pData->pPrivate;
    width = pPriv->width;
    srcRowBytes = pPriv->srcRowBytes;
    pSrcLine = pPriv->pSrcPixels + pData->srcLine * srcRowBytes;
    dstRowBytes = pPriv->dstRowBytes;
    pDstLine = pPriv->pDstPixels + dstLine * dstRowBytes;

    yMod8Times8 = (pPriv->y & 7) << 3;
    nLinesM1 = *pNLines;
    if (nLinesM1 <= 0)
        return IL_OK;
    pPriv->y += nLinesM1;
    nLinesM1--;

        /*  Do dither; see comments above for overall approach */
    pTranslate = pPriv->pTranslate;
    pMul4 = _ilMul4;
    pMul8 = _ilMul8;
    do {
        pSrc = pSrcLine;
        pSrcLine += srcRowBytes;
        pDst = pDstLine;
        pDstLine += dstRowBytes;
        x = 0;
        while (x < width) {
            kernel = _ilDitherKernel [yMod8Times8 | (x & 7)];
            x++;
            pixel = ((pMul4[*pSrc++] + kernel) >> 8) << 3;
            pixel += (pMul8[*pSrc++] + kernel) >> 8;
            pixel <<= 2;
            pixel += (pMul4[*pSrc++] + kernel) >> 8;
            *pDst++ = pTranslate[pixel];
            }
        yMod8Times8 += (1 << 3);
        if (yMod8Times8 >= (8 << 3))
            yMod8Times8 = 0;
        } while (--nLinesM1 >= 0);

    return IL_OK;
}


/*  =========================== COLOR DIFFUSION CODE =============================== */ 


        /*  ---------------------- ilExecuteDiffusionRGB ------------------------ */
        /*  Execute() function: error diffuse and pack the given # of src lines. 
        */
static ilError ilExecuteDiffusionRGB (
    ilExecuteData          *pData,
    long                    dstLine,
    long                   *pNLines
    )
{
ilDitherPrivPtr             pPriv;
long                        srcRowBytes, dstRowBytes;
long                        nLinesM1, nPixelsM1, nPixelsM1Init;
int                red, green, blue;
int                redAboveError, greenAboveError, blueAboveError;
int                redAboveLeftError, greenAboveLeftError, blueAboveLeftError;
int                redAboveRightError, greenAboveRightError, blueAboveRightError;
int                         redRShift, greenRShift, blueRShift;
long               pixel;
int               *pError;
ilPtr              pSrc;
long                       *pColorTable;
ilPtr                       pDst, pSrcLine, pDstLine;

    pPriv = (ilDitherPrivPtr)pData->pPrivate;
    srcRowBytes = pPriv->srcRowBytes;
    pSrcLine = pPriv->pSrcPixels + pData->srcLine * srcRowBytes;
    dstRowBytes = pPriv->dstRowBytes;
    pDstLine = pPriv->pDstPixels + dstLine * dstRowBytes;

    nLinesM1 = *pNLines - 1;
    nPixelsM1Init = pPriv->width - 1;
    pColorTable = pPriv->pColorTable;

    redRShift = pPriv->shifts[0];
    greenRShift = pPriv->shifts[1];
    blueRShift = pPriv->shifts[2];

    do {
        pSrc = pSrcLine;
        pSrcLine += srcRowBytes;
        pDst = pDstLine;
        pDstLine += dstRowBytes;
        nPixelsM1 = nPixelsM1Init;

        pError = pPriv->pErrors;
        red = redAboveError = 0;
        redAboveRightError = *pError;
        green = greenAboveError = 0;
        greenAboveRightError = *(pError + 1);
        blue = blueAboveError = 0;
        blueAboveRightError = *(pError + 2);

            /*  Do Floyd-Steinberg error diffusion.  For each pixel, "color slam" to
                pack RGB into "pixel", then use pixel as index into pColorTable to
                find out what actual RGB value that pseudo-color pixel represents.
                Subtract the actual from the original (desired) value to determine the
                error, and save error in red/green/blue, and in error buffer (*pError)
                    Factor in errors from surrounding pixels using: 7/16 of left,
                1/16 of above left, 5/16 of above and 3/16 of above right.  Effectively
                multiply by each, doing successive adds, then >> 4 for / 16.
            */
        do {
            redAboveLeftError = redAboveError;
            redAboveError = redAboveRightError;
            redAboveRightError = *(pError + 3);
            pixel = red;
            red += redAboveError;
            pixel += red;
            red += redAboveRightError;
            pixel += red;
            red = *pSrc++ + ((pixel + pixel + red + redAboveLeftError) >> 4);
            if (red >> 8) goto edClipR;
edClipRetR:

            greenAboveLeftError = greenAboveError;
            greenAboveError = greenAboveRightError;
            greenAboveRightError = *(pError + 4);
            pixel = green;
            green += greenAboveError;
            pixel += green;
            green += greenAboveRightError;
            pixel += green;
            green = *pSrc++ + ((pixel + pixel + green + greenAboveLeftError) >> 4);
            if (green >> 8) goto edClipG;
edClipRetG:

            blueAboveLeftError = blueAboveError;
            blueAboveError = blueAboveRightError;
            blueAboveRightError = *(pError + 5);
            pixel = blue;
            blue += blueAboveError;
            pixel += blue;
            blue += blueAboveRightError;
            pixel += blue;
            blue = *pSrc++ + ((pixel + pixel + blue + blueAboveLeftError) >> 4);
            if (blue >> 8) goto edClipB;
edClipRetB:

                /*  Color slam to find 8 bit pixel to use. */
            pixel = (red >> redRShift);
            pixel <<= (8 - greenRShift);
            pixel |= (green >> greenRShift);
            pixel <<= (8 - blueRShift);
            pixel |= (blue >> blueRShift);
            pixel = pColorTable[pixel];
            *pDst++ = pixel;

            pixel >>= 8;
            red -= ((ilByte)pixel);
            *pError++ = red;
            pixel >>= 8;
            green -= ((ilByte)pixel);
            *pError++ = green;
            blue -= (ilByte)(pixel >> 8);
            *pError++ = blue;
            } while (--nPixelsM1 >= 0);
        } while (--nLinesM1 >= 0);

    return IL_OK;

        /*  Goto points for RGB value out of range (the exceptional case); done this
            way for significant performance gain, due to not taking the branch.
        */
edClipR:    if (red < 0) red = 0; else red = 255;
            goto edClipRetR;
edClipG:    if (green < 0) green = 0; else green = 255;
            goto edClipRetG;
edClipB:    if (blue < 0) blue = 0; else blue = 255;
            goto edClipRetB;
}

        /*  ---------------------- ilExecuteDiffusion484 ------------------------ */
        /*  Execute() function: error diffuse, specific to levels 484.
        */
static ilError ilExecuteDiffusion484 (
    ilExecuteData          *pData,
    long                    dstLine,
    long                   *pNLines
    )
{
ilDitherPrivPtr             pPriv;
long                        srcRowBytes, dstRowBytes;
long                        nLinesM1, nPixelsM1, nPixelsM1Init;
int                red, green, blue;
int                redAboveError, greenAboveError, blueAboveError;
int                redAboveLeftError, greenAboveLeftError, blueAboveLeftError;
int                redAboveRightError, greenAboveRightError, blueAboveRightError;
long               pixel;
int               *pError;
ilPtr              pSrc;
long                       *pColorTable;
ilPtr                       pDst, pSrcLine, pDstLine;

    pPriv = (ilDitherPrivPtr)pData->pPrivate;
    srcRowBytes = pPriv->srcRowBytes;
    pSrcLine = pPriv->pSrcPixels + pData->srcLine * srcRowBytes;
    dstRowBytes = pPriv->dstRowBytes;
    pDstLine = pPriv->pDstPixels + dstLine * dstRowBytes;

    nLinesM1 = *pNLines - 1;
    nPixelsM1Init = pPriv->width - 1;
    pColorTable = pPriv->pColorTable;

        /*  Error diffusion, same as general case above, but # levels of RGB = 484. */
    do {
        pSrc = pSrcLine;
        pSrcLine += srcRowBytes;
        pDst = pDstLine;
        pDstLine += dstRowBytes;
        nPixelsM1 = nPixelsM1Init;

        pError = pPriv->pErrors;
        red = redAboveError = 0;
        redAboveRightError = *pError;
        green = greenAboveError = 0;
        greenAboveRightError = *(pError + 1);
        blue = blueAboveError = 0;
        blueAboveRightError = *(pError + 2);

        do {
            redAboveLeftError = redAboveError;
            redAboveError = redAboveRightError;
            redAboveRightError = *(pError + 3);
            pixel = red;
            red += redAboveError;
            pixel += red;
            red += redAboveRightError;
            pixel += red;
            red = *pSrc++ + ((pixel + pixel + red + redAboveLeftError) >> 4);
            if (red >> 8) goto edClipR;
edClipRetR:

            greenAboveLeftError = greenAboveError;
            greenAboveError = greenAboveRightError;
            greenAboveRightError = *(pError + 4);
            pixel = green;
            green += greenAboveError;
            pixel += green;
            green += greenAboveRightError;
            pixel += green;
            green = *pSrc++ + ((pixel + pixel + green + greenAboveLeftError) >> 4);
            if (green >> 8) goto edClipG;
edClipRetG:

            blueAboveLeftError = blueAboveError;
            blueAboveError = blueAboveRightError;
            blueAboveRightError = *(pError + 5);
            pixel = blue;
            blue += blueAboveError;
            pixel += blue;
            blue += blueAboveRightError;
            pixel += blue;
            blue = *pSrc++ + ((pixel + pixel + blue + blueAboveLeftError) >> 4);
            if (blue >> 8) goto edClipB;
edClipRetB:

                /*  Color slam to find 8 bit pixel to use. */
            pixel = (red >> 6);
            pixel <<= 3;
            pixel |= (green >> 5);
            pixel <<= 2;
            pixel |= (blue >> 6);
            pixel = pColorTable[pixel];
            *pDst++ = pixel;

            pixel >>= 8;
            red -= ((ilByte)pixel);
            *pError++ = red;
            pixel >>= 8;
            green -= ((ilByte)pixel);
            *pError++ = green;
            blue -= (ilByte)(pixel >> 8);
            *pError++ = blue;
            } while (--nPixelsM1 >= 0);
        } while (--nLinesM1 >= 0);

    return IL_OK;

        /*  Goto points for RGB value out of range (the exceptional case); done this
            way for significant performance gain, due to not taking the branch.
        */
edClipR:   if (red < 0) red = 0; else red = 255;
            goto edClipRetR;
edClipG:   if (green < 0) green = 0; else green = 255;
            goto edClipRetG;
edClipB:   if (blue < 0) blue = 0; else blue = 255;
            goto edClipRetB;
}


        /*  -------------------- ilExecuteQuickDiffusionRGB --------------------- */
        /*  Execute() function for "quick" dithering
        */
static ilError ilExecuteQuickDiffusionRGB (
    ilExecuteData          *pData,
    long                    dstLine,
    long                   *pNLines
    )
{
ilDitherPrivPtr             pPriv;
long                        srcRowBytes, dstRowBytes;
long                        nLinesM1, nPixelsM1, nPixelsM1Init;
int                red, green, blue;
int                redRShift, greenRShift, blueRShift;
long               pixel;
int               *pError;
ilPtr              pSrc;
long              *pColorTable;
ilPtr                       pDst, pSrcLine, pDstLine;

        /*  Same as regular diffusion above, except spread the errors in a simpler and
            quicker way: 1/2 of error from pixel to left, 1/2 from pixel above.
        */
    pPriv = (ilDitherPrivPtr)pData->pPrivate;
    srcRowBytes = pPriv->srcRowBytes;
    pSrcLine = pPriv->pSrcPixels + pData->srcLine * srcRowBytes;
    dstRowBytes = pPriv->dstRowBytes;
    pDstLine = pPriv->pDstPixels + dstLine * dstRowBytes;

    nLinesM1 = *pNLines - 1;
    nPixelsM1Init = pPriv->width - 1;
    pColorTable = pPriv->pColorTable;

    redRShift = pPriv->shifts[0];
    greenRShift = pPriv->shifts[1];
    blueRShift = pPriv->shifts[2];

    do {
        pSrc = pSrcLine;
        pSrcLine += srcRowBytes;
        pDst = pDstLine;
        pDstLine += dstRowBytes;
        nPixelsM1 = nPixelsM1Init;

        pError = pPriv->pErrors;
        red = green = blue = 0;

        do {
            red = *pSrc++ + ((red + pError[0]) >> 1);
            if (red >> 8) goto qdClipR;
qdClipRetR:
            green = *pSrc++ + ((green + pError[1]) >> 1);
            if (green >> 8) goto qdClipG;
qdClipRetG:
            blue = *pSrc++ + ((blue + pError[2]) >> 1);
            if (blue >> 8) goto qdClipB;
qdClipRetB:

                /*  Color slam to find 8 bit pixel to use. */
            pixel = (red >> redRShift);
            pixel <<= (8 - greenRShift);
            pixel |= (green >> greenRShift);
            pixel <<= (8 - blueRShift);
            pixel |= (blue >> blueRShift);
            pixel = pColorTable[pixel];
            *pDst++ = pixel;

            pixel >>= 8;
            red -= ((ilByte)pixel);
            *pError++ = red;
            pixel >>= 8;
            green -= ((ilByte)pixel);
            *pError++ = green;
            blue -= (ilByte)(pixel >> 8);
            *pError++ = blue;
            } while (--nPixelsM1 >= 0);
        } while (--nLinesM1 >= 0);

    return IL_OK;

        /*  Goto points for RGB value out of range (the exceptional case); done this
            way for significant performance gain, due to not taking the branch.
        */
qdClipR:    if (red < 0) red = 0; else red = 255;
            goto qdClipRetR;
qdClipG:    if (green < 0) green = 0; else green = 255;
            goto qdClipRetG;
qdClipB:    if (blue < 0) blue = 0; else blue = 255;
            goto qdClipRetB;
}

/*  =========================== CHOOSE COLORS CODE =============================== */ 

static double weight[3] = {0.299, 0.587, 0.114};

    /*  Private data types used by assorted ConverterExecute pipe filter private functions. */

typedef struct {
    unsigned long           number;
    unsigned long           moment[3];
    } convertBoxTotalRec;

typedef struct {
    unsigned char           lower[3];       /* Lower bounds for box (along each axis) */
    unsigned char           upper[3];       /* Upper bounds for box (along each axis) */
    unsigned char           index;          /* Which box will be chosen as next split */
    unsigned char           plane;          /* Axis & Position of optimum split plane */
    double                  split;          /* The best split available for named box */
    } convertBoxRec;

typedef struct {
    convertBoxTotalRec      total;
    unsigned long int       slice[3][32];
    } convertBoxCountRec;


        /*  --------------------------- CountBox --------------------------- */
        /*  Count the number of occupied cells in a specified subbox.
        */

static unsigned long CountBox (
    convertBoxRec          *pBox,
    unsigned long          *Ftable,
    convertBoxCountRec     *count
    )
{
int              axis, plane, index, rgb[3];

    count->total.number = 0;
    for ( axis = 0 ; axis < 3 ; axis++ ) {
        rgb[axis] = pBox->lower[axis];
        count->total.moment[axis] = 0;
        for ( plane = 0 ; plane < 32 ; plane++ ) count->slice[axis][plane] = 0;
    }

L:  for ( index = 0, axis = 0 ; axis < 3 ; axis++ ) index = (index << 5) + rgb[axis];

    if ( Ftable[index] ) {
        count->total.number += Ftable[index];
        for ( axis = 0 ; axis < 3 ; axis++ ) count->slice[axis][rgb[axis]] += Ftable[index];
    }

    for ( axis = 2 ; axis >= 0 ; axis-- ) {
        if ( ++rgb[axis] <= pBox->upper[axis] ) goto L;
        rgb[axis] = pBox->lower[axis];
    }

    for ( axis = 0 ; axis < 3 ; axis++ )
     for ( plane = 0 ; plane < 32 ; plane++ )
      count->total.moment[axis] += count->slice[axis][plane]*plane;
#if 0
printf("CountBox: %2d:%-2d %2d:%-2d %2d:%-2d %8d\n",
        pBox->lower[0], pBox->upper[0], pBox->lower[1], pBox->upper[1],
        pBox->lower[2], pBox->upper[2], count->total.number );
#endif
    return count->total.number;
}

static int ScanBox(
    int                     box,
    unsigned long          *Ftable,
    convertBoxRec          *BoxTable,
    int                     nBoxes,
    int                     nColors
    )
{
convertBoxTotalRec          total, part1, part2;
convertBoxCountRec          count;
convertBoxRec               slice;
convertBoxRec     *pBox = &BoxTable[box];
double                      temp, ssq1 = 0.0f, ssq2;
int                axis, plane, rgb, n;

    if ( CountBox( pBox, Ftable, &count ) ) {

        total = count.total;
        while ( count.slice[0][pBox->lower[0]] == 0 ) pBox->lower[0]++;
        while ( count.slice[0][pBox->upper[0]] == 0 ) pBox->upper[0]--;
        while ( count.slice[1][pBox->lower[1]] == 0 ) pBox->lower[1]++;
        while ( count.slice[1][pBox->upper[1]] == 0 ) pBox->upper[1]--;
        while ( count.slice[2][pBox->lower[2]] == 0 ) pBox->lower[2]++;
        while ( count.slice[2][pBox->upper[2]] == 0 ) pBox->upper[2]--;

        slice       = *pBox;
        slice.split =  0.0 ;
        slice.index =  box ;

        for ( axis = 0 ; axis < 3 ; axis++ )
          if ( pBox->upper[axis] > pBox->lower[axis] ) {

            part1.number    = 0;
            part1.moment[0] = 0;
            part1.moment[1] = 0;
            part1.moment[2] = 0;
            part2 = total;

            for ( plane = pBox->lower[axis] ; ; plane++ ) {
                slice.lower[axis] = plane;
                slice.upper[axis] = plane;
                if ( !CountBox( &slice, Ftable, &count ) ) continue;
                slice.lower[axis] = pBox->lower[axis];
                ssq1 = 0.0;
                ssq2 = 0.0;
                for ( rgb = 0 ; rgb < 3 ; rgb++ ) {
                    temp  = weight[rgb]*(part1.moment[rgb] += count.total.moment[rgb]);
                    ssq1 += temp*temp;
                    temp  = weight[rgb]*(part2.moment[rgb] -= count.total.moment[rgb]);
                    ssq2 += temp*temp;
                }
                part1.number += count.total.number;
                part2.number -= count.total.number;
                if ( part2.number == 0 ) break;

                temp = (ssq1 / part1.number) + (ssq2 / part2.number);
                if ( slice.split < temp ) {
                    slice.split = temp;
                    slice.plane = (axis << 5) | plane;
                }
            }
        }

        if ( (slice.split -= ssq1 / total.number) > BoxTable[n = nColors - 1].split ) {

            while ( (--n >= nBoxes) && (slice.split > BoxTable[n].split) ) BoxTable[n+1] = BoxTable[n];
            BoxTable[++n] = slice;
        }
#if 0
        printf( "      Adjusted box %3d [%2d:%-2d %2d:%-2d %2d:%-2d] @ %1d.%-2d  %10.0lf\n",
                 box, slice.lower[0], slice.upper[0], slice.lower[1],
                      slice.upper[1], slice.lower[2], slice.upper[2],
                      slice.plane >> 5, slice.plane & 31, slice.split );
#endif
    }
    return (BoxTable[nBoxes].split > 0.0);
}
  

    /*  --------------------- ilChooseColorsExecute ------------------------- */
    /*  Execute() pipe element function for IL_CHOOSE_COLORS option.
    */
static ilError ilChooseColorsExecute (
    ilExecuteData          *pData,
    long                    dstLine,
    long                   *pNLines
    )
{
ilDitherPrivPtr    pPriv;
long                        srcRowBytes, dstRowBytes, nRowsM1, nLinesM1;
long                        width, height;
ilPtr                       pSrcLine, pDstLine;
long               rowCount;
ilPtr              pSrc, pDst;
unsigned short    *pPalette;
int                         nBoxes, nColors;
int                         index, axis, plane, inner, outer;
unsigned long              *Ftable;
convertBoxRec               box[256];
convertBoxTotalRec          total[256];

        /*  Get pointers to src, dst scan lines, bytes/row (aka "stride"),
            and width, # lines minus 1 (M1).
        */

    pPriv = (ilDitherPrivPtr)pData->pPrivate;
    pPalette = pPriv->pPalette;
    nColors  = pPriv->nColors;
    width = pPriv->width;
    height = *pNLines;

    srcRowBytes = pPriv->srcRowBytes;
    dstRowBytes = pPriv->dstRowBytes;

    if ( !(Ftable = (unsigned long *) calloc( sizeof *Ftable, 32*32*32 )) )
      return IL_ERROR_MALLOC;

    pSrcLine = pPriv->pSrcPixels + pData->srcLine * srcRowBytes;

    nRowsM1 = width - 1;
    nLinesM1 = height - 1;
    do {
        pSrc = pSrcLine;
        pSrcLine += srcRowBytes;
        rowCount = nRowsM1;
        do {
            ilByte  R, G, B;

            R = *pSrc++;        /* red */
            G = *pSrc++;        /* green */
            B = *pSrc++;        /* blue */
            Ftable[((R & 0xF8) << 7) + ((G & 0xF8) << 2) + ((B & 0xF8) >> 3)]++;
        } while (--rowCount >= 0);
    } while (--nLinesM1 >= 0);

    box[0].lower[0] = box[0].lower[1] = box[0].lower[2] =  0;
    box[0].upper[0] = box[0].upper[1] = box[0].upper[2] = 31;
    for ( index = 0 ; index < 256 ; index++ ) box[index].split = 0.0;

    if ( (nBoxes = 1) < nColors ) while ( 1 ) {
        if ( !ScanBox( nBoxes-1, Ftable, box, nBoxes, nColors ) ) break;
        index = box[nBoxes].index;
        plane = box[nBoxes].plane & 31;
        axis  = box[nBoxes].plane >> 5;
        box[nBoxes] = box[index];
        box[nBoxes].upper[axis] = plane;
        box[ index].lower[axis] = plane + 1;
        if ( ++nBoxes == nColors ) break;
        ScanBox( index, Ftable, box, nBoxes, nColors );
    }

    for ( index = 0 ; index < nBoxes ; index++ ) {
        convertBoxCountRec       count;

        CountBox( &box[index], Ftable, &count );
        pPalette[ 0  + index] = (2048.0*count.total.moment[0])/count.total.number + 1024.0;
        pPalette[256 + index] = (2048.0*count.total.moment[1])/count.total.number + 1024.0;
        pPalette[512 + index] = (2048.0*count.total.moment[2])/count.total.number + 1024.0;
    }

    for ( outer = 0 ; outer < nBoxes ; outer++ ) {
        convertBoxRec  *pBox = &box[outer];
        int             R, G, B;
        int                      rgb_inner, rgb_outer, rgb_limit;
        unsigned char            multiple, candidate[256];
        double                   ssq_inner, ssq_outer, distance;

        multiple = 0;
        candidate[outer] = 1;
        for ( inner = 0 ; inner < nBoxes ; inner++ ) {

            if ( inner == outer ) continue;
            candidate[inner] = 0;
            ssq_inner = 0.0;
            ssq_outer = 0.0;
            for ( axis = 0 ; axis < 3 ; axis++ ) {
                rgb_inner = pPalette[inner + (axis << 8)];
                rgb_outer = pPalette[outer + (axis << 8)];
                rgb_limit = (((rgb_inner < rgb_outer) ? pBox->lower[axis] : pBox->upper[axis]) << 11) + 0x0400;
                distance = weight[axis]*(rgb_limit - rgb_inner); ssq_inner += distance*distance;
                distance = weight[axis]*(rgb_limit - rgb_outer); ssq_outer += distance*distance;
            }
            if ( ssq_inner < ssq_outer ) candidate[inner] = multiple = 1;
        }

        for ( R = pBox->lower[0] ; R <= pBox->upper[0] ; R++ )
         for ( G = pBox->lower[1] ; G <= pBox->upper[1] ; G++ )
          for ( B = pBox->lower[2] ; B <= pBox->upper[2] ; B++ )
           if ( multiple ) {
            index = (R << 10) + (G << 5) + B;
            ssq_outer = 1.0e12;
            for ( inner = 0 ; inner < nBoxes ; inner++ ) if ( candidate[inner] ) {
                distance = weight[0]*(((R << 11) + 0x0400) - pPalette[inner +  0 ]); ssq_inner  = distance*distance;
                distance = weight[1]*(((G << 11) + 0x0400) - pPalette[inner + 256]); ssq_inner += distance*distance;
                distance = weight[2]*(((B << 11) + 0x0400) - pPalette[inner + 512]); ssq_inner += distance*distance;
                if ( ssq_inner < ssq_outer ) {ssq_outer = ssq_inner; Ftable[index] = inner;}
            }
        } else Ftable[(R << 10) + (G << 5) + B] = outer;
    }

    for ( index = 0 ; index < nBoxes ; index++ )
        total[index].number = total[index].moment[0] = total[index].moment[1] = total[index].moment[2] = 0;

    pSrcLine = pPriv->pSrcPixels + pData->srcLine * srcRowBytes;
    pDstLine = pPriv->pDstPixels + dstLine * dstRowBytes;

    nRowsM1 = width - 1;
    nLinesM1 = height - 1;
    do {
        pSrc = pSrcLine;
        pSrcLine += srcRowBytes;
        pDst = pDstLine;
        pDstLine += dstRowBytes;
        rowCount = nRowsM1;
        do {
            ilByte  R, G, B, P;

            R = *pSrc++;        /* red */
            G = *pSrc++;        /* green */
            B = *pSrc++;        /* blue */
            P = Ftable[((R & 0xF8) << 7) + ((G & 0xF8) << 2) + ((B & 0xF8) >> 3)];
            *pDst++ = P;
            total[P].number    += 1;
            total[P].moment[0] += R;
            total[P].moment[1] += G;
            total[P].moment[2] += B;
        } while (--rowCount >= 0);
    } while (--nLinesM1 >= 0);

    for ( index = 0 ; index < nBoxes ; index++ ) {
        pPalette[ 0  + index] = (256.0*total[index].moment[0])/total[index].number;
        pPalette[256 + index] = (256.0*total[index].moment[1])/total[index].number;
        pPalette[512 + index] = (256.0*total[index].moment[2])/total[index].number;
    }

    free( Ftable );
    return IL_OK;
}


/*  =========================== "MAINLINE" FUNCTION  =============================== */ 

    /*  ---------------------------- ilConvertRGBToPalette ----------------------- */
    /*  Convert from source type (pDes->type) == RGB to Palette.
        pFormat points to the source format; on return, *pFormat is updated
        to the dst format. *pDes ->the src (pipe) des; on return *pDes is the new des.
    */
IL_PRIVATE ilBool _ilConvertRGBToPalette (
    ilPipe                  pipe,
    ilPipeInfo             *pInfo,
    ilImageDes    *pDes,
    ilImageFormat          *pFormat,
    int                     option,
    ilConvertToPaletteInfo *pData
    )
{
    ilDitherPrivPtr pPriv;
    ilDstElementData        dstData;
    ilSrcElementData        srcData;
    ilError                 (*executeFunction)(), (*cleanupFunction)();
    ilPtr                   pTranslate;
    unsigned short         *pPalette;
    long                   *pColorTable;
    ilBool                  diffusion, chooseColors;
    int                     i, shifts[3] = { 0, 0, 0 }, nColors = 0;
    const unsigned short         *pMulTable[3] = { NULL, NULL, NULL };      /* dither other than 484 only: pMul? */
    static ilConvertToPaletteInfo  defaultConvert = 
                                  {IL_DIFFUSION, { 4, 8, 4 }, 8, IL_PALETTE, (ilObject)NULL};


        /*  Init to null those things freed by "cleanup" if error. */
    pPalette = (unsigned short *)NULL;
    pColorTable = (long *)NULL;

        /*  Get format = planar order, 8 bits / pixel, or error.
            Src image already guaranteed to be 256-level RGB image.
        */
    if ((pFormat->nBitsPerSample[0] != 8)
     || (pFormat->nBitsPerSample[1] != 8)
     || (pFormat->nBitsPerSample[2] != 8)
     || (pFormat->sampleOrder != IL_SAMPLE_PIXELS)) {
        if (!ilConvert (pipe, (ilImageDes *)NULL, IL_FORMAT_3BYTE_PIXEL, 0, NULL))
            return FALSE;
        }

        /*  Validate option code; default pData if not present */
    if ((option != 0) && (option != IL_CONVERT_TO_PALETTE))
        return ilDeclarePipeInvalid (pipe, IL_ERROR_INVALID_OPTION);
    if (!pData)
        pData = &defaultConvert;

        /*  Validate and choose pipe functions based on convert method. */
    switch (pData->method) {
      case IL_AREA_DITHER:
        if (pData->kernelSize != 8)
            return ilDeclarePipeInvalid (pipe, IL_ERROR_CONVERT_TO_PALETTE);
        if ((pData->levels[0] == 4)
         && (pData->levels[1] == 8) 
         && (pData->levels[2] == 4))
            executeFunction = ilExecuteDitherRGBTo484;
        else {
                /*  Not 484 dithering: each level must be 2, 4 or 8; product <= 256.
                    Set pMulTable and shifts based on # of levels each component.
                */
            if ((pData->levels[0] * pData->levels[1] * pData->levels[2]) > 256)
                return ilDeclarePipeInvalid (pipe, IL_ERROR_CONVERT_TO_PALETTE);
            for (i = 0; i < 3; i++)
                switch ((unsigned short)pData->levels[i]) {
                  case 2: shifts[i] = 7; pMulTable[i] = _ilMul2; break;
                  case 4: shifts[i] = 6; pMulTable[i] = _ilMul4; break;
                  case 8: shifts[i] = 5; pMulTable[i] = _ilMul8; break;
                  default: return ilDeclarePipeInvalid (pipe,IL_ERROR_CONVERT_TO_PALETTE);
                  }
            executeFunction = ilExecuteDitherRGB;
            }
        cleanupFunction = IL_NPF;
        diffusion = FALSE;
        chooseColors = FALSE;
        break;

        /*  (Quick) diffusion: all powers of 2 levels (min = 2) supported; product of all 
            levels <= 256, so 64 is max level for any one.  Store shifts = 8 - # bits.
        */
      case IL_DIFFUSION:
      case IL_QUICK_DIFFUSION:
        for (i = 0; i < 3; i++)
            switch ((unsigned short)pData->levels[i]) {
              case 2: shifts[i] = 7; break;
              case 4: shifts[i] = 6; break;
              case 8: shifts[i] = 5; break;
              case 16: shifts[i] = 4; break;
              case 32: shifts[i] = 3; break;
              case 64: shifts[i] = 2; break;
              default: return ilDeclarePipeInvalid (pipe, IL_ERROR_CONVERT_TO_PALETTE);
              }
        if ((pData->levels[0] * pData->levels[1] * pData->levels[2]) > 256)
            return ilDeclarePipeInvalid (pipe, IL_ERROR_CONVERT_TO_PALETTE);
        cleanupFunction = ilCleanupDitherRGB;
        diffusion = TRUE;
        chooseColors = FALSE;
        if (pData->method == IL_DIFFUSION)
            if ((pData->levels[0]==4) && (pData->levels[1]==8) && (pData->levels[2]==4))
                 executeFunction = ilExecuteDiffusion484;
            else executeFunction = ilExecuteDiffusionRGB;
        else executeFunction = ilExecuteQuickDiffusionRGB;
        break;

        /*  Choose colors: use the "best" pData->levels[0] (1..255) colors and fit to them.
            mapImage, dstType and kernelSize are ignored.  Need a single strip, so set
            srcData to request a single strip (height = image, constantStrip = TRUE).
        */
      case IL_CHOOSE_COLORS:
        nColors = pData->levels[0];
        if ((nColors < 1) 
         || (nColors > 256)
         || pData->mapImage 
         || (pData->dstType != IL_PALETTE))
            return ilDeclarePipeInvalid (pipe, IL_ERROR_CONVERT_TO_PALETTE);
        executeFunction = ilChooseColorsExecute;
        cleanupFunction = IL_NPF;
        diffusion = FALSE;
        chooseColors = TRUE;
        srcData.consumerImage = (ilObject)NULL;
        srcData.stripHeight = pInfo->height;        /* need one strip = whole image */
        srcData.constantStrip = TRUE;
        srcData.minBufferHeight = 0;
        break;

      default:
        return ilDeclarePipeInvalid (pipe, IL_ERROR_CONVERT_TO_PALETTE);
        }

        /*  If mapImage given, validate it and point to its pixels.  If not given,
            pTranslate becomes null and will point to "identity" mapImage below.
        */
    pTranslate = (ilPtr)NULL;
    if (pData->mapImage && !chooseColors) {
        ilImageInfo *pInfo;
        if (!ilQueryClientImage (pData->mapImage, &pInfo, 0)
         || (pInfo->width != 256) || (pInfo->height != 1) 
         || (pInfo->pDes->compression != IL_UNCOMPRESSED)
         || (pInfo->pDes->nSamplesPerPixel != 1)
         || (pInfo->pFormat->nBitsPerSample[0] != 8))
            return ilDeclarePipeInvalid (pipe, IL_ERROR_MAP_IMAGE);
        pTranslate = pInfo->plane[0].pPixels;
        }

        /*  If diffusion: init table: indexed by a pixel packed as <R><G><B><P>, each
            with number of levels "n?Levels" (must be a power of 2), * 4.  The red, green,
            blue and pixel values appear in that order; table is indexed by pixel*4.
            "pixel" is the translated pixel, i.e. pTranslate[pixel].
            Note that this table has same values as palette, except 0..255 and ordered
            with r/g/b/pixel together, instead of 0..65535 and rgb spread apart.
        */
    if (diffusion) {
        int            i, index;
        int                     red, green, blue;
        int                     redLevel, greenLevel, blueLevel;
        long *pColorTemp;
        pColorTable = (long *)IL_MALLOC (sizeof (long) * 256);
        if (!pColorTable) {
            ilDeclarePipeInvalid (pipe, IL_ERROR_MALLOC);
            goto cleanup;
            }
        pColorTemp = pColorTable;
        for (index = 0, red = 0; red < pData->levels[0]; red++) {
            redLevel = 255 * red / (pData->levels[0] - 1);
            for (green = 0; green < pData->levels[1]; green++) {
                greenLevel = 255 * green / (pData->levels[1] - 1);
                for (blue = 0; blue < pData->levels[2]; blue++) {
                    blueLevel = 255 * blue / (pData->levels[2] - 1);
                    i = (blueLevel << 24) | (greenLevel << 16) | (redLevel << 8);
                    if (pTranslate)
                         i |= pTranslate[index];
                    else i |= index;
                    *pColorTemp++ = i;
                    index++;
                    }
                }
            }
        }

        /*  alloc pPalette unless not palette dst; init with ramp if not choosing */
    if ((pData->dstType == IL_PALETTE) || chooseColors) {
        pPalette = (unsigned short *)IL_MALLOC_ZERO (3 * 256 * sizeof(unsigned short));
        if (!pPalette) {
            ilDeclarePipeInvalid (pipe, IL_ERROR_MALLOC);
            goto cleanup;
            }
       if (!chooseColors) {
            int            red, green, blue;
            int            redLevel, greenLevel, blueLevel;
            unsigned short *pPal;

            pPal = pPalette;
            for (red = 0; red < pData->levels[0]; red++) {
                redLevel = 65535 * red / (pData->levels[0] - 1);
                for (green = 0; green < pData->levels[1]; green++) {
                    greenLevel = 65535 * green / (pData->levels[1] - 1);
                    for (blue = 0; blue < pData->levels[2]; blue++) {
                        blueLevel = 65535 * blue / (pData->levels[2] - 1);
                        pPal [0]   = redLevel;
                        pPal [256] = greenLevel;
                        pPal [512] = blueLevel;
                        pPal++;
                        }
                    }
                }
            }
        }   /* END create palette */

        /*  Add filter to write byte palette or private type image. If the type is 
            "palette", mark as being dithered unless colors choosen.
        */
    if (chooseColors)
        *pDes = *IL_DES_PALETTE;
    else {
        *pDes = *IL_DES_GRAY;
        pDes->type = pData->dstType;
        if (pDes->type == IL_PALETTE) {
            pDes->flags = IL_DITHERED_PALETTE;
            pDes->typeInfo.palette.levels[0] = pData->levels[0];
            pDes->typeInfo.palette.levels[1] = pData->levels[1];
            pDes->typeInfo.palette.levels[2] = pData->levels[2];
            }
        }
    *pFormat = *IL_FORMAT_BYTE;
    dstData.producerObject = (ilObject)NULL;
    dstData.pDes = pDes;
    dstData.pFormat = pFormat;
    dstData.width = pInfo->width;
    dstData.height = pInfo->height;
    dstData.stripHeight = 0;
    dstData.constantStrip = FALSE;
    dstData.pPalette = pPalette;
    pPriv = (ilDitherPrivPtr)ilAddPipeElement (pipe, IL_FILTER, sizeof(ilDitherPrivRec), 0,
            (chooseColors) ? &srcData : (ilSrcElementData *)NULL, &dstData, 
            ilInitDitherRGB, cleanupFunction, ilDestroyDitherRGB, executeFunction, NULL, 0);
    if (!pPriv)
        goto cleanup;

        /*  Init pPriv; point pTranslate to identity image if no mapImage given.
            Store stuff from above into *pPriv even if not needed for this case.
        */
    pPriv->diffusion = diffusion;
    if (pTranslate)
        pPriv->pTranslate = pTranslate;
    else if (!chooseColors) {
        int     i;
        pPriv->pTranslate = pPriv->translate;
        for (i = 0; i < 256; i++)
            pPriv->translate[i] = i;
        }
    pPriv->pPalette = pPalette;
    pPriv->pColorTable = pColorTable;
    pPriv->shifts[0] = shifts[0];
    pPriv->shifts[1] = shifts[1];
    pPriv->shifts[2] = shifts[2];
    pPriv->pMulTable[0] = pMulTable[0];
    pPriv->pMulTable[1] = pMulTable[1];
    pPriv->pMulTable[2] = pMulTable[2];
    pPriv->nColors = nColors;
    return TRUE;

    /*  goto point if error: free anything that has been malloc'd; return false */
cleanup:
    if (pPalette) IL_FREE (pPalette);
    if (pColorTable) IL_FREE (pColorTable);
    return FALSE;
}



