/*
 * bltColor.c --
 *
 *	This module contains routines for color allocation strategies
 *	used with color images in the BLT toolkit.
 *
 * Copyright 1997-1998 Lucent Technologies, Inc.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation for any purpose and without fee is hereby
 * granted, provided that the above copyright notice appear in all
 * copies and that both that the copyright notice and warranty
 * disclaimer appear in supporting documentation, and that the names
 * of Lucent Technologies any of their entities not be used in
 * advertising or publicity pertaining to distribution of the software
 * without specific, written prior permission.
 *
 * Lucent Technologies disclaims all warranties with regard to this
 * software, including all implied warranties of merchantability and
 * fitness.  In no event shall Lucent Technologies be liable for any
 * special, indirect or consequential damages or any damages
 * whatsoever resulting from loss of use, data or profits, whether in
 * an action of contract, negligence or other tortuous action, arising
 * out of or in connection with the use or performance of this
 * software.
 */

/*
 * Color strategies of 8-bit visuals:
 *
 * Try to "best" represent an N-color image into 8-bit (256 color)
 * colormap.  The simplest method is use the high bits of each RGB
 * value (3 bits for red and green, 2 bits for blue).  But this
 * produces lots of contouring since the distribution of colors tends
 * to be clustered.  Other problems: probably can't allocate even 256
 * colors. Other applications will have already taken some color
 * slots.  Furthermore, we might be displaying several images, and we
 * can't assume that all images are representative of the colors used.
 *
 * If we use a private colormap, we may want to allocate some number
 * of colors from the default colormap to prevent flashing when
 * colormaps are switched.
 *
 * Switches:
 *
 *	-exact boolean		Try to match the colors of the image rather
 *				then generating a "best" color ramp.
 *
 *	-threshold value	Maximum average error. Indicates how far
 *				to reduce the quantized color palette.
 *
 *	-tolerance value	Allow colors within this distance to match.
 *				This will weight allocation towards harder
 *				to match colors, rather than the most
 *				frequent.
 *
 *	-mincolors number	Minimum number of reduced quantized colors.
 *				or color ramp.
 *
 *	-dither	boolean		Turn on/off Floyd-Steinberg dithering.
 *
 *	-keep number		Hint to keep the first N colors in the
 *				in the default colormap.  This only applies to
 *				private colormaps.
 *
 *	-ramp number		Number of colors to use in a linear ramp.
 *
 */

#include "bltInt.h"

#ifndef WIN32

#include "bltHash.h"
#include "bltImage.h"

#define NCOLORS		256

#if 0
static void
GetPaletteSizes(nColors, nRedsPtr, nGreensPtr, nBluesPtr)
    int nColors;		/* Number of colors requested. */
    unsigned int *nRedsPtr;	/* (out) Number of red components. */
    unsigned int *nGreensPtr;	/* (out) Number of green components. */
    unsigned int *nBluesPtr;	/* (out) Number of blue components. */
{
    unsigned int nBlues, nReds, nGreens;

    assert(nColors > 1); 
    nBlues = nReds = nGreens = 0;
    while ((nBlues * nBlues * nBlues) <= nColors) {
	nBlues++;
    }
    nBlues--;
    while ((nReds * nReds * nBlues) <= nColors) {
	nReds++;
    }
    nReds--;
    nGreens = nColors / (nBlues * nReds);

    *nRedsPtr = nReds;
    *nGreensPtr = nGreens;
    *nBluesPtr = nBlues;
}

static void
BuildColorRamp(palettePtr, nColors)
    Pix32 *palettePtr;
    int nColors;
{
    register unsigned int r, g, b;
    unsigned int short red, green, blue;
    unsigned int nReds, nGreens, nBlues;

    GetPaletteSizes(nColors, &nReds, &nGreens, &nBlues);
    for (r = 0; r < nReds; r++) {
	red = (r * USHRT_MAX) / (nReds - 1);
	for (g = 0; g < nGreens; g++) {
	    green = (g * USHRT_MAX) / (nGreens - 1);
	    for (b = 0; b < nBlues; b++) {
		blue = (b * USHRT_MAX) / (nBlues - 1);
		palettePtr->Red = red;
		palettePtr->Green = green;
		palettePtr->Blue = blue;
		palettePtr++;
	    }
	}
    }

}
#endif

/*
 *----------------------------------------------------------------------
 *
 * QueryColormap --
 *
 *	This is for psuedo-color displays only.  Fills an array or
 *	XColors with the color values (RGB and pixel) currently
 *	allocated in the colormap.
 *
 * Results:
 *	The number of colors allocated is returned. The array "colorArr"
 *	will contain the XColor values of each color in the colormap.
 *
 *---------------------------------------------------------------------- 
 */

static int
QueryColormap(display, colorMap, mapColors, numMapColorsPtr)
    Display *display;
    Colormap colorMap;
    XColor mapColors[];
    int *numMapColorsPtr;
{
    unsigned long int pixelValues[NCOLORS];
    int numAvail, numMapColors;
    register int i;
    register XColor *colorPtr;
    register unsigned long *indexPtr;
    int inUse[NCOLORS];

    /* Initially, we assume all color cells are allocated. */
    memset((char *)inUse, 0, sizeof(int) * NCOLORS);

    /*
     * Start allocating color cells.  This will tell us which color cells
     * haven't already been allocated in the colormap.  We'll release the
     * cells as soon as we find out how many there are.
     */
    numAvail = 0;
    for (indexPtr = pixelValues, i = 0; i < NCOLORS; i++, indexPtr++) {
	if (!XAllocColorCells(display, colorMap, False, NULL, 0, indexPtr, 1)) {
	    break;
	}
	inUse[*indexPtr] = TRUE;/* Indicate the cell is unallocated */
	numAvail++;
    }
    XFreeColors(display, colorMap, pixelValues, numAvail, 0);

    /*
     * Put the indices of the cells already allocated into a color array.
     * We'll use the array to query the RGB values of the allocated colors.
     */
    numMapColors = 0;
    colorPtr = mapColors;
    for (i = 0; i < NCOLORS; i++) {
	if (!inUse[i]) {
	    colorPtr->pixel = i;
	    colorPtr->flags = (DoRed | DoGreen | DoBlue);
	    colorPtr++, numMapColors++;
	}
    }
    XQueryColors(display, colorMap, mapColors, numMapColors);
    *numMapColorsPtr = numMapColors;
#ifdef notdef
    fprintf(stderr, "Number of colors (allocated/free) %d/%d\n", numMapColors,
	numAvail);
#endif
    return numAvail;
}

#if 0
static void
FindClosestColor(colorPtr, mapColors, numMapColors)
    ColorInfo *colorPtr;
    XColor mapColors[];
    int numMapColors;
{
    double r, g, b;
    register int i;
    double dist, min;
    XColor *lastMatch;
    register XColor *mapColorPtr;

    min = DBL_MAX;	/* Any color is closer. */
    lastMatch = NULL;

    /* Linear search of color */

    mapColorPtr = mapColors;
    for (i = 0; i < numMapColors; i++, mapColorPtr++) {
	r = (double)mapColorPtr->red - (double)colorPtr->exact.red;
	g = (double)mapColorPtr->green - (double)colorPtr->exact.green;
	b = (double)mapColorPtr->blue - (double)colorPtr->exact.blue;

	dist = (r * r) + (b * b) + (g * g);
	if (dist < min) {
	    min = dist;
	    lastMatch = mapColorPtr;
	}
    }
    colorPtr->best = *lastMatch;
    colorPtr->best.flags = (DoRed | DoGreen | DoBlue);
    colorPtr->error = (float)sqrt(min);
}

static int
CompareColors(a, b)
    void *a, *b;
{
    ColorInfo *i1Ptr, *i2Ptr;

    i1Ptr = *(ColorInfo **) a;
    i2Ptr = *(ColorInfo **) b;
    if (i2Ptr->error > i1Ptr->error) {
	return 1;
    } else if (i2Ptr->error < i1Ptr->error) {
	return -1;
    }
    return 0;
}

static float
MatchColors(colorTabPtr, rgbPtr, numColors, numAvailColors, numMapColors,
    mapColors)
    struct ColorTableStruct *colorTabPtr;
    Pix32 *rgbPtr;
    int numColors;
    int numAvailColors;
    int numMapColors;
    XColor mapColors[NCOLORS];
{
    int numMatched;
    float sum;
    register int i;
    register ColorInfo *colorPtr;

    /*
     * For each quantized color, compute and store the error (i.e
     * the distance from a color that's already been allocated).
     * We'll use this information to sort the colors based upon how
     * badly they match and their frequency to the color image.
     */
    colorPtr = colorTabPtr->colorInfo;
    for (i = 0; i < numColors; i++, colorPtr++, rgbPtr++) {
	colorPtr->index = i;
	colorTabPtr->sortedColors[i] = colorPtr;
	colorPtr->exact.red = rgbPtr->Red;
	colorPtr->exact.green = rgbPtr->Green;
	colorPtr->exact.blue = rgbPtr->Blue;
	colorPtr->exact.flags = (DoRed | DoGreen | DoBlue);
	FindClosestColor(colorPtr, mapColors, numMapColors);
    }

    /* Sort the colors, first by frequency (most to least), then by
     * matching error (worst to best).
     */
    qsort(colorTabPtr->sortedColors, numColors, sizeof(ColorInfo *),
	(QSortCompareProc *)CompareColors);

    for (i = 0; i < numColors; i++) {
	colorPtr = colorTabPtr->sortedColors[i];
	fprintf(stderr, "%d. %04x%04x%04x / %04x%04x%04x = %f (%d)\n", i,
	    colorPtr->exact.red, colorPtr->exact.green, colorPtr->exact.blue,
	    colorPtr->best.red, colorPtr->best.green, colorPtr->best.blue,
	    colorPtr->error, colorPtr->freq);
    }
    sum = 0.0;
    numMatched = 0;
    for (i = numAvailColors; i < numColors; i++) {
	colorPtr = colorTabPtr->sortedColors[i];
	sum += colorPtr->error;
	numMatched++;
    }
    if (numMatched > 0) {
	sum /= numMatched;
    }
    return sum;
}

    
static int
AllocateColors(nImageColors, colorTabPtr, matchOnly)
    int nImageColors;
    struct ColorTableStruct *colorTabPtr;
    int matchOnly;
{
    register int i;
    register ColorInfo *colorPtr;
    unsigned long int pixelValue;

    for (i = 0; i < nImageColors; i++) {
	colorPtr = colorTabPtr->sortedColors[i];
	if (matchOnly) {
	    XAllocColor(colorTabPtr->display, colorTabPtr->colorMap,
		&colorPtr->best);
	    pixelValue = colorPtr->best.pixel;
	} else {
	    colorPtr->allocated = XAllocColor(colorTabPtr->display,
		colorTabPtr->colorMap, &colorPtr->exact);

	    if (colorPtr->allocated) {
		pixelValue = colorPtr->exact.pixel;
	    } else {
		XAllocColor(colorTabPtr->display, colorTabPtr->colorMap,
		    &colorPtr->best);
		pixelValue = colorPtr->best.pixel;
	    }
	}
	colorTabPtr->pixelValues[colorPtr->index] = pixelValue;
    }
    colorTabPtr->nPixels = nImageColors;
    return 1;
}
#endif

ColorTable
Blt_CreateColorTable(tkwin)
    Tk_Window tkwin;
{
    XVisualInfo visualInfo, *visualInfoPtr;
    int nVisuals;
    Visual *visualPtr;
    Display *display;
    struct ColorTableStruct *colorTabPtr;

    display = Tk_Display(tkwin);
    visualPtr = Tk_Visual(tkwin);

    colorTabPtr = Blt_Calloc(1, sizeof(struct ColorTableStruct));
    assert(colorTabPtr);
    colorTabPtr->display = Tk_Display(tkwin);
    colorTabPtr->colorMap = Tk_Colormap(tkwin);

    visualInfo.screen = Tk_ScreenNumber(tkwin);
    visualInfo.visualid = XVisualIDFromVisual(visualPtr);
    visualInfoPtr = XGetVisualInfo(display, VisualScreenMask | VisualIDMask,
	&visualInfo, &nVisuals);

    colorTabPtr->visualInfo = *visualInfoPtr;
    XFree(visualInfoPtr);

    return colorTabPtr;
}

void
Blt_FreeColorTable(colorTabPtr)
    struct ColorTableStruct *colorTabPtr;
{
    if (colorTabPtr == NULL) {
	return;
    }
    if (colorTabPtr->nPixels > 0) {
	XFreeColors(colorTabPtr->display, colorTabPtr->colorMap,
	    colorTabPtr->pixelValues, colorTabPtr->nPixels, 0);
    }
    Blt_Free(colorTabPtr);
}

extern int redAdjust, greenAdjust, blueAdjust;
extern int redMaskShift, greenMaskShift, blueMaskShift;

/*
 *----------------------------------------------------------------------
 *
 * Blt_DirectColorTable --
 *
 *	Creates a color table using the DirectColor visual.  We try
 *	to allocate colors across the color spectrum.
 *
 * Results:
 *
 *
 *----------------------------------------------------------------------
 */
/*ARGSUSED*/
ColorTable
Blt_DirectColorTable(interp, tkwin, image)
    Tcl_Interp *interp;
    Tk_Window tkwin;
    Blt_ColorImage image;
{
    struct ColorTableStruct *colorTabPtr;
    Visual *visualPtr;
    Display *display;
    XColor color;
    int nr, ng, nb;
    int rBand, gBand, bBand;
    int rLast, gLast, bLast;
    unsigned int r, g, b;
    unsigned int value;
    register int i;

    display = Tk_Display(tkwin);
    visualPtr = Tk_Visual(tkwin);

    colorTabPtr = Blt_CreateColorTable(tkwin);
    /*
     * Compute the number of distinct colors in each band
     */
    nr = ((unsigned int)visualPtr->red_mask >> redMaskShift) + 1;
    ng = ((unsigned int)visualPtr->green_mask >> greenMaskShift) + 1;
    nb = ((unsigned int)visualPtr->blue_mask >> blueMaskShift) + 1;

#ifdef notdef
    assert((nr <= visualPtr->map_entries) && (ng <= visualPtr->map_entries) &&
	(nb <= visualPtr->map_entries));
#endif
    rBand = NCOLORS / nr;
    gBand = NCOLORS / ng;
    bBand = NCOLORS / nb;

  retry:
    color.flags = (DoRed | DoGreen | DoBlue);
    rLast = gLast = bLast = 0;
    r = g = b = 0;
    for (i = 0; i < visualPtr->map_entries; i++) {
	if (rLast < NCOLORS) {
	    r = rLast + rBand;
	    if (r > NCOLORS) {
		r = NCOLORS;
	    }
	}
	if (gLast < NCOLORS) {
	    g = gLast + gBand;
	    if (g > NCOLORS) {
		g = NCOLORS;
	    }
	}
	if (bLast < NCOLORS) {
	    b = bLast + bBand;
	    if (b > NCOLORS) {
		b = NCOLORS;
	    }
	}
	color.red = (r - 1) * (NCOLORS + 1);
	color.green = (g - 1) * (NCOLORS + 1);
	color.blue = (b - 1) * (NCOLORS + 1);

	if (!XAllocColor(display, colorTabPtr->colorMap, &color)) {
	    XFreeColors(display, colorTabPtr->colorMap,
		colorTabPtr->pixelValues, i, 0);
	    if ((colorTabPtr->flags & PRIVATE_COLORMAP) == 0) {
		/*
		 * If we can't allocate a color in the default
		 * colormap, try again, this time with a private
		 * colormap.
		 */
		fprintf(stderr, "Need to allocate private colormap\n");
		colorTabPtr->colorMap = Tk_GetColormap(interp, tkwin, ".");

		XSetWindowColormap(display, Tk_WindowId(tkwin),
		    colorTabPtr->colorMap);
		colorTabPtr->flags |= PRIVATE_COLORMAP;
		goto retry;
	    }
#ifdef notdef
	    fprintf(stderr, "Failed to allocate after %d colors\n", i);
#endif
	    Blt_Free(colorTabPtr);
	    return NULL;	/* Ran out of colors in private map? */
	}
	colorTabPtr->pixelValues[i] = color.pixel;
	/*
	 * Fill in pixel values for each band at this intensity
	 */
	value = color.pixel & visualPtr->red_mask;
	while (rLast < r) {
	    colorTabPtr->red[rLast++] = value;
	}
	value = color.pixel & visualPtr->green_mask;
	while (gLast < g) {
	    colorTabPtr->green[gLast++] = value;
	}
	value = color.pixel & visualPtr->blue_mask;
	while (bLast < b) {
	    colorTabPtr->blue[bLast++] = value;
	}
    }
    colorTabPtr->nPixels = i;
    return colorTabPtr;
}

#if 0
/*
 * First attempt:
 *	Allocate colors all the colors in the image (up to NCOLORS). Bail out
 *	on the first failure or if we need more than NCOLORS.
 */
static int
GetUniqueColors(image)
    Blt_ColorImage image;
{
    register int i, nColors;
    register Pix32 *pixelPtr;
    Pix32 color;
    Blt_HashEntry *hPtr;
    int isNew, nPixels;
    int refCount;
    Blt_HashTable colorTable;

    Blt_InitHashTable(&colorTable, BLT_ONE_WORD_KEYS);

    nPixels = Blt_ColorImageWidth(image) * Blt_ColorImageHeight(image);
    nColors = 0;
    pixelPtr = Blt_ColorImageBits(image);
    for (i = 0; i < nPixels; i++, pixelPtr++) {
	color.value = pixelPtr->value;
	color.Alpha = 0xFF;	/* Ignore alpha-channel values */
	hPtr = Blt_CreateHashEntry(&colorTable, (char *)color.value, &isNew);
	if (isNew) {
	    refCount = 1;
	    nColors++;
	} else {
	    refCount = (int)Blt_GetHashValue(hPtr);
	    refCount++;
	}
	Blt_SetHashValue(hPtr, (ClientData)refCount);
    }
    Blt_DeleteHashTable(&colorTable);
    return nColors;
}
#endif

#define Blt_DefaultColormap(tkwin)  \
	DefaultColormap(Tk_Display(tkwin), Tk_ScreenNumber(tkwin))


static void
PrivateColormap(interp, colorTabPtr, image, tkwin)
    Tcl_Interp *interp;
    struct ColorTableStruct *colorTabPtr;
    Blt_ColorImage image;
    Tk_Window tkwin;
{
    int keepColors = 0;
    register int i;
    XColor usedColors[NCOLORS];
    int nUsedColors;
    Colormap colorMap;
    int inUse[NCOLORS];
    XColor *colorPtr;
    /* XColor *imageColors; */

    /*
     * Create a private colormap if one doesn't already exist for the
     * window.
     */

    colorTabPtr->colorMap = colorMap = Tk_Colormap(tkwin);

    nUsedColors = 0;		/* Number of colors allocated */

    if (colorTabPtr->nPixels > 0) {
	XFreeColors(colorTabPtr->display, colorTabPtr->colorMap,
	    colorTabPtr->pixelValues, colorTabPtr->nPixels, 0);
    }
    QueryColormap(colorTabPtr->display, colorMap, usedColors,
	&nUsedColors);
    memset((char *)inUse, 0, sizeof(int) * NCOLORS);
    if ((nUsedColors == 0) && (keepColors > 0)) {

	/*
	 * We're starting with a clean colormap so find out what colors
	 * have been used in the default colormap.
	 */

	QueryColormap(colorTabPtr->display,
	    Blt_DefaultColormap(tkwin), usedColors, &nUsedColors);

	/*
	 * Copy a number of colors from the default colormap into the private
	 * colormap.  We can assume that this is the working set from most
	 * (non-image related) applications. While this doesn't stop our
	 * image from flashing and looking dumb when colormaps are swapped
	 * in and out, at least everything else should remain unaffected.
	 */

	if (nUsedColors > keepColors) {
	    nUsedColors = keepColors;
	}
	/*
	 * We want to allocate colors in the same ordering as the old colormap,
	 * and we can't assume that the colors in the old map were contiguous.
	 * So mark the colormap locations (i.e. pixels) that we find in use.
	 */

    }
    for (colorPtr = usedColors, i = 0; i < nUsedColors; i++, colorPtr++) {
	inUse[colorPtr->pixel] = TRUE;
    }

    /*
     * In an "exact" colormap, we try to allocate as many of colors from the
     * image as we can fit.  If necessary, we'll cheat and reduce the number
     * of colors by quantizing.
     */
    /* imageColors = usedColors + nUsedColors; */

    Tk_SetWindowColormap(tkwin, colorMap);
}

ColorTable
Blt_PseudoColorTable(interp, tkwin, image)
    Tcl_Interp *interp;
    Tk_Window tkwin;
    Blt_ColorImage image;
{
    struct ColorTableStruct *colorTabPtr;
    Colormap defColorMap;
    int usePrivate;

    colorTabPtr = Blt_CreateColorTable(tkwin);
    defColorMap = DefaultColormap(colorTabPtr->display, Tk_ScreenNumber(tkwin));
    if (colorTabPtr->colorMap == defColorMap) {
	fprintf(stderr, "Using default colormap\n");
    }
    /* All other visuals use an 8-bit colormap */
    colorTabPtr->lut = Blt_Malloc(sizeof(unsigned int) * 33 * 33 * 33);
    assert(colorTabPtr->lut);

    usePrivate = TRUE;
    if (usePrivate) {
	PrivateColormap(interp, colorTabPtr, image, tkwin);
    } else {
#ifdef notdef
	ReadOnlyColormap(colorTabPtr, image, tkwin);
#endif
    }
    return colorTabPtr;
}

#ifdef notdef

static void
ConvoleColorImage(srcImage, destImage, kernelPtr)
    Blt_ColorImage srcImage, destImage;
    ConvoleKernel *kernelPtr;
{
    Pix32 *srcPtr, *destPtr;
    Pix32 *src[MAXROWS];
    register int x, y, i, j;
    int red, green, blue;

    /* i = 0 case, ignore left column of pixels */

    srcPtr = Blt_ColorImageBits(srcImage);
    destPtr = Blt_ColorImageBits(destImage);

    width = Blt_ColorImageWidth(srcImage);
    height = Blt_ColorImageHeight(srcImage);

    yOffset = kernelPtr->height / 2;
    xOffset = kernelPtr->width / 2;
    for (y = yOffset; y < (height - yOffset); y++) {
	/* Set up pointers to individual rows */
	for (i = 0; i < kernelPtr->height; i++) {
	    src[i] = srcPtr + (i * width);
	}
	for (x = xOffset; x < (width - xOffset); x++) {
	    red = green = blue = 0;
	    kernPtr = kernelPtr->values;
	    for (i = 0; i < kernelPtr->height; i++) {
		for (j = 0; j < kernelPtr->width; j++) {
		    red += *valuePtr * src[i][j].Red;
		    green += *valuePtr * src[i][j].Green;
		    blue += *valuePtr * src[i][j].Blue;
		    valuePtr++;
		}
	    }
	    destPtr->Red = red / kernelPtr->sum;
	    destPtr->Green = green / kernelPtr->sum;
	    destPtr->Blue = blue / kernelPtr->sum;
	    destPtr++;
	}
	srcPtr += width;
    }
    sum = bot[0].Red +
	red = bot[0].Red + bot[1].Red + mid[1].Red + top[0].Red + top[1].Red;
    green = bot[0].Green + bot[1].Green + mid[1].Green + top[0].Green +
	top[1].Green;
    blue = bot[0].Blue + bot[1].Blue + mid[1].Blue + top[0].Blue + top[1].Blue;
    error = (red / 5) - mid[0].Red;
    redVal = mid[0].Red - (error * blend / blend_divisor);
    error = (green / 5) - mid[0].Green;
    greenVal = mid[0].Green - (error * blend / blend_divisor);
    error = (blue / 5) - mid[0].Blue;
    blueVal = mid[0].Blue - (error * blend / blend_divisor);

    out[0].Red = CLAMP(redVal);
    out[0].Green = CLAMP(greenVal);
    out[0].Blue = CLAMP(blueVal);

    for (i = 1; i < (width - 1); i++) {
	for (chan = 0; chan < 3; chan++) {
	    total = bot[chan][i - 1] + bot[chan][i] + bot[chan][i + 1] +
		mid[chan][i - 1] + mid[chan][i + 1] +
		top[chan][i - 1] + top[chan][i] + top[chan][i + 1];
	    avg = total >> 3;	/* divide by 8 */
	    diff = avg - mid[chan][i];
	    result = mid[chan][i] - (diff * blend / blend_divisor);
	    out[chan][i] = CLAMP(result);
	}
    }
    /* i = in_hdr.xmax case, ignore right column of pixels */
    for (chan = 0; chan < 3; chan++) {
	total = bot[chan][i - 1] + bot[chan][i] +
	    mid[chan][i - 1] +
	    top[chan][i - 1] + top[chan][i];
	avg = total / 5;
	diff = avg - mid[chan][i];
	result = mid[chan][i] - (diff * blend / blend_divisor);
	out[chan][i] = CLAMP(result);
    }
}

static void
DitherRow(srcImage, destImage, lastRow, curRow)
    Blt_ColorImage srcImage, destImage;
    int width, height;
    int bottom, top;
{
    int width, height;

    width = Blt_ColorImageWidth(srcImage);
    topPtr = Blt_ColorImageBits(destPtr) + (width * row);
    rowPtr = topPtr + width;
    botPtr = rowPtr + width;

    for (x = 0; x < width; x++) {

	/* Clamp current error entry */

	midPtr->red = CLAMP(midPtr->red);
	midPtr->blue = CLAMP(midPtr->blue);
	midPtr->green = CLAMP(midPtr->green);

	r = (midPtr->red >> 3) + 1;
	g = (midPtr->green >> 3) + 1;
	b = (midPtr->blue >> 3) + 1;
	index = colorTabPtr->lut[r][g][b];

	redVal = midPtr->red * (NCOLORS + 1);
	greenVal = midPtr->green * (NCOLORS + 1);
	blueVal = midPtr->blue * (NCOLORS + 1);

	error = colorVal - colorMap[index].red;
	if (x < 511) {
	    currRow[x + 1].Red = currRow[x + 1].Red + 7 * error / 16;
	    nextRow[x + 1].Red = nextRow[x + 1].Red + error / 16;
	}
	nextRow[x].Red = nextRow[x].Red + 5 * error / 16;
	if (x > 0) {
	    nextRow[x - 1].Red = nextRow[x - 1].Red + 3 * error / 16;
	}
	error = row[x][c] - colormap[index][c];

	value = srcPtr->channel[i] * error[i];
	value = CLAMP(value);
	destPtr->channel[i] = value;

	/* Closest pixel */
	pixel = PsuedoColorPixel();
	error[RED] = colorPtr->Red - srcPtr->Red * (NCOLORS + 1);

	/* translate pixel to colorInfoPtr to get error */
	colorTabPtr->lut[r][g][b];
	colorPtr = PixelToColorInfo(pixel);
	error = colorPtr->error;

	register rle_pixel *optr;
	register int j;
	register short *thisptr, *nextptr = NULL;
	int chan;
	static int nchan = 0;
	int lastline = 0, lastpixel;
	static int *cval = 0;
	static rle_pixel *pixel = 0;

	if (nchan != in_hdr->ncolors)
	    if (cval) {
		Blt_Free(cval);
		Blt_Free(pixel);
	    }
	nchan = in_hdr->ncolors;
	if (!cval) {
	    if ((cval = Blt_Malloc(nchan * sizeof(int))) == 0)
		    malloc_ERR;
	    if ((pixel = Blt_Malloc(nchan * sizeof(rle_pixel))) == 0)
		malloc_ERR;
	}
	optr = outrow[RLE_RED];

	thisptr = row_top;
	if (row_bottom)
	    nextptr = row_bottom;
	else
	    lastline = 1;

	for (x = 0; x < width; x++) {
	    int cmap_index = 0;

	    lastpixel = (x == (width - 1));
	    val = srcPtr->Red;

	    for (chan = 0; chan < 3; chan++) {
		cval[chan] = *thisptr++;

		/*
		 * Current channel value has been accumulating error,
		 * it could be out of range.
		 */
		if (cval[chan] < 0)
		    cval[chan] = 0;
		else if (cval[chan] > 255)
		    cval[chan] = 255;

		pixel[chan] = cval[chan];
	    }

	    /* find closest color */
	    find_closest(map, nchan, maplen, pixel, &cmap_index);
	    *optr++ = cmap_index;

	    /* thisptr is now looking at pixel to the right of current pixel
	     * nextptr is looking at pixel below current pixel
	     * So, increment thisptr as stuff gets stored.  nextptr gets moved
	     * by one, and indexing is done +/- nchan.
	     */
	    for (chan = 0; chan < nchan; chan++) {
		cval[chan] -= map[chan][cmap_index];

		if (!lastpixel) {
		    thisptr[chan] += cval[chan] * 7 / 16;
		}
		if (!lastline) {
		    if (j != 0) {
			nextptr[-nchan] += cval[chan] * 3 / 16;
		    }
		    nextptr[0] += cval[chan] * 5 / 16;
		    if (!lastpixel) {
			nextptr[nchan] += cval[chan] / 16;
		    }
		    nextptr++;
		}
	    }
	}
    }
}

/********************************************/
static Blt_ColorImage
DoColorDither(pic24, pic8, w, h, rmap, gmap, bmap, rdisp, gdisp, bdisp, maplen)
    byte *pic24, *pic8, *rmap, *gmap, *bmap, *rdisp, *gdisp, *bdisp;
    int w, h, maplen;
{
    /* takes a 24 bit picture, of size w*h, dithers with the colors in
       rdisp, gdisp, bdisp (which have already been allocated),
       and generates an 8-bit w*h image, which it returns.
       ignores input value 'pic8'
       returns NULL on error

       note: the rdisp,gdisp,bdisp arrays should be the 'displayed' colors,
       not the 'desired' colors

       if pic24 is NULL, uses the passed-in pic8 (an 8-bit image) as
       the source, and the rmap,gmap,bmap arrays as the desired colors */

    byte *np, *ep, *newpic;
    short *cache;
    int r2, g2, b2;
    int *thisline, *nextline, *thisptr, *nextptr, *tmpptr;
    int i, j, rerr, gerr, berr, pwide3;
    int imax, jmax;
    int key;
    long cnt1, cnt2;
    int error[512];		/* -255 .. 0 .. +255 */

    /* compute somewhat non-linear floyd-steinberg error mapping table */
    for (i = j = 0; i <= 0x40; i++, j++) {
	error[256 + i] = j;
	error[256 - i] = -j;
    }
    for ( /*empty*/ ; i < 0x80; i++, j += !(i & 1) ? 1 : 0) {
	error[256 + i] = j;
	error[256 - i] = -j;
    }
    for ( /*empty*/ ; i <= 0xff; i++) {
	error[256 + i] = j;
	error[256 - i] = -j;
    }

    cnt1 = cnt2 = 0;
    pwide3 = w * 3;
    imax = h - 1;
    jmax = w - 1;
    ep = (pic24) ? pic24 : pic8;

    /* attempt to malloc things */
    newpic = Blt_Malloc((size_t) (w * h));
    cache = Blt_Calloc((size_t) (2 << 14), sizeof(short));
    thisline = Blt_Malloc(pwide3 * sizeof(int));
    nextline = Blt_Malloc(pwide3 * sizeof(int));
    if (!cache || !newpic || !thisline || !nextline) {
	if (newpic)
	    Blt_Free(newpic);
	if (cache)
	    Blt_Free(cache);
	if (thisline)
	    Blt_Free(thisline);
	if (nextline)
	    Blt_Free(nextline);
	return (byte *) NULL;
    }
    np = newpic;

    /* Get first line of picture in reverse order. */

    srcPtr = Blt_ColorImageBits(image), tempPtr = tempArr;
    for (x = 0; x < width; x++, tempPtr++, srcPtr--) {
	*tempPtr = *srcPtr;
    }

    for (y = 0; y < height; y++) {
	tempPtr = curRowPtr, curRowPtr = nextRowPtr, nextRowPtr = tempPtr;

	if (y != (height - 1)) {/* get next line */
	    for (x = 0; x < width; x++, tempPtr++, srcPtr--)
		*tempPtr = *srcPtr;
	}
    }


    Blt_Free(thisline);
    Blt_Free(nextline);
    Blt_Free(cache);

    return newpic;
}


static void
DitherImage(image)
    Blt_ColorImage image;
{
    int width, height;



}

#endif

#endif /* WIN32 */