/* GDK - The GIMP Drawing Kit
 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the Free
 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/* Color Context module
 * Copyright 1994,1995 John L. Cwikla
 * Copyright (C) 1997 by Ripley Software Development
 * Copyright (C) 1997 by Federico Mena (port to Gtk/Gdk)
 */

/* Copyright 1994,1995 John L. Cwikla
 *
 * Permission to use, copy, modify, distribute, and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appears in all copies and that
 * both that copyright notice and this permission notice appear in
 * supporting documentation, and that the name of John L. Cwikla or
 * Wolfram Research, Inc not be used in advertising or publicity
 * pertaining to distribution of the software without specific, written
 * prior permission.  John L. Cwikla and Wolfram Research, Inc make no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 * John L. Cwikla and Wolfram Research, Inc disclaim all warranties with
 * regard to this software, including all implied warranties of
 * merchantability and fitness, in no event shall John L. Cwikla or
 * Wolfram Research, Inc 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 tortious action, arising out of or in connection with the use or
 * performance of this software.
 *
 * Author:
 *  John L. Cwikla
 *  X Programmer
 *  Wolfram Research Inc.
 *
 *  cwikla@wri.com
 */

/* NOTES:
 *
 * - When a CC is destroyed, remember to destroy the hash table properly.
 */


#include <X11/Xlib.h>
#include <stdlib.h>
#include <string.h>
#include "gdk.h"
#include "gdkprivate.h"
#include "gdkx.h"


#define MAX_IMAGE_COLORS 256


static guint
hash_color(gpointer key)
{
	GdkColor *color = key;

	return (color->red * 33023 + color->green * 30013 + color->blue * 27011);
}

static gint
compare_colors(gpointer a, gpointer b)
{
	GdkColor *aa = a;
	GdkColor *bb = b;

	return ((aa->red == bb->red) && (aa->green == bb->green) && (aa->blue == bb->blue));
}

static void
free_hash_entry(gpointer key, gpointer value, gpointer user_data)
{
	g_free(key); /* key and value are the same GdkColor */
}

static int
pixel_sort(const void *a, const void *b)
{
	return ((GdkColor *) a)->pixel - ((GdkColor *) b)->pixel;
}

/* XXX: This function does an XQueryColors() the hard way, because there is
 * no corresponding function in Gdk.
 */

static void
my_x_query_colors(GdkColormap *colormap,
		  GdkColor    *colors,
		  gint         ncolors)
{
	XColor *xcolors;
	gint    i;

	xcolors = g_new(XColor, ncolors);
	for (i = 0; i < ncolors; i++)
		xcolors[i].pixel = colors[i].pixel;

	XQueryColors(gdk_display, GDK_COLORMAP_XCOLORMAP(colormap), xcolors, ncolors);

	for (i = 0; i < ncolors; i++) {
		colors[i].red   = xcolors[i].red;
		colors[i].green = xcolors[i].green;
		colors[i].blue  = xcolors[i].blue;
	}

	g_free(xcolors);
}

static void
query_colors(GdkColorContextPrivate *cc)
{
	gint i;

	cc->cmap = g_new(GdkColor, cc->num_colors);

	for (i = 0; i < cc->num_colors; i++)
		cc->cmap[i].pixel = cc->clut ? cc->clut[i] : cc->std_cmap.base_pixel + i;

	my_x_query_colors(cc->colormap, cc->cmap, cc->num_colors);
	
	qsort(cc->cmap, cc->num_colors, sizeof(GdkColor), pixel_sort);
}

static void
init_bw(GdkColorContextPrivate *cc)
{
	GdkColor color;

	g_warning("init_bw: failed to allocate colors, falling back to black and white");

	cc->mode = GDK_CC_MODE_BW;

	color.red = color.green = color.blue = 0;
	if (!gdk_color_alloc(cc->colormap, &color))
		cc->black_pixel = 0;
	else
		cc->black_pixel = color.pixel;

	color.red = color.green = color.blue = 0xffff;
	if (!gdk_color_alloc(cc->colormap, &color))
		cc->white_pixel = cc->black_pixel ? 0 : 1;
	else
		cc->white_pixel = color.pixel;

	cc->num_colors = 2;
}

static void
init_gray(GdkColorContextPrivate *cc)
{
	GdkColor *clrs, *cstart;
	gint i;
	gdouble dinc;

	cc->num_colors = GDK_VISUAL_XVISUAL(cc->visual)->map_entries;

	cc->clut = g_new(gulong, cc->num_colors);
	cstart = g_new(GdkColor, cc->num_colors);

retrygray:

	dinc = 65535.0 / (cc->num_colors - 1);

	clrs = cstart;

	for (i = 0; i < cc->num_colors; i++) {
		clrs->red = clrs->green = clrs->blue = dinc * i;

		if (!gdk_color_alloc(cc->colormap, clrs)) {
			gdk_colors_free(cc->colormap, cc->clut, i, 0);

			cc->num_colors /= 2;

			if (cc->num_colors > 1)
				goto retrygray;
			else {
				g_free(cc->clut);
				cc->clut = NULL;
				init_bw(cc);
				g_free(cstart);
				return;
			}
		}

		cc->clut[i] = clrs++->pixel;
	}

	g_free(cstart);

	/* XXX: is this the right thing to do? */
	cc->std_cmap.colormap = GDK_COLORMAP_XCOLORMAP(cc->colormap);
	cc->std_cmap.base_pixel = 0;
	cc->std_cmap.red_max = cc->num_colors - 1;
	cc->std_cmap.green_max = 0;
	cc->std_cmap.blue_max = 0;
	cc->std_cmap.red_mult = 1;
	cc->std_cmap.green_mult = 0;
	cc->std_cmap.blue_mult = 0;

	cc->white_pixel = WhitePixel(cc->xdisplay, gdk_screen);
	cc->black_pixel = BlackPixel(cc->xdisplay, gdk_screen);

	query_colors(cc);

	cc->mode = GDK_CC_MODE_MY_GRAY;
}

static void
init_color(GdkColorContextPrivate *cc)
{
	gint cubeval;

	cubeval = 1;
	while ((cubeval * cubeval * cubeval) < GDK_VISUAL_XVISUAL(cc->visual)->map_entries)
		cubeval++;
	cubeval--;

	cc->num_colors = cubeval * cubeval * cubeval;

	cc->std_cmap.red_max    = cubeval - 1;
	cc->std_cmap.green_max  = cubeval - 1;
	cc->std_cmap.blue_max   = cubeval - 1;
	cc->std_cmap.red_mult   = cubeval * cubeval;
	cc->std_cmap.green_mult = cubeval;
	cc->std_cmap.blue_mult  = 1;
	cc->std_cmap.base_pixel = 0;

	cc->white_pixel = WhitePixel(cc->xdisplay, gdk_screen);
	cc->black_pixel = BlackPixel(cc->xdisplay, gdk_screen);
	cc->num_colors = DisplayCells(cc->xdisplay, gdk_screen);

	/* a CLUT for storing allocated pixel indices */

	cc->max_colors = cc->num_colors;
	cc->clut = g_new(gulong, cc->max_colors);

	for (cubeval = 0; cubeval < cc->max_colors; cubeval++)
		cc->clut[cubeval] = cubeval;

	query_colors(cc);

	cc->mode = GDK_CC_MODE_STD_CMAP;
}


static void
init_true_color(GdkColorContextPrivate *cc)
{
	gulong rmask, gmask, bmask;

	cc->mode = GDK_CC_MODE_TRUE;

	/* Red */

	rmask = cc->masks.red = cc->visual->red_mask;

	cc->shifts.red = 0;
	cc->bits.red = 0;

	while (!(rmask & 1)) {
		rmask >>= 1;
		cc->shifts.red++;
	}

	while (rmask & 1) {
		rmask >>= 1;
		cc->bits.red++;
	}

	/* Green */

	gmask = cc->masks.green = cc->visual->green_mask;

	cc->shifts.green = 0;
	cc->bits.green = 0;

	while (!(gmask & 1)) {
		gmask >>= 1;
		cc->shifts.green++;
	}

	while (gmask & 1) {
		gmask >>= 1;
		cc->bits.green++;
	}

	/* Blue */

	bmask = cc->masks.blue = cc->visual->blue_mask;

	cc->shifts.blue = 0;
	cc->bits.blue = 0;

	while (!(bmask & 1)) {
		bmask >>= 1;
		cc->shifts.blue++;
	}

	while (bmask & 1) {
		bmask >>= 1;
		cc->bits.blue++;
	}

	cc->num_colors = (cc->visual->red_mask | cc->visual->green_mask | cc->visual->blue_mask) + 1;
	cc->white_pixel = WhitePixel(cc->xdisplay, gdk_screen);
	cc->black_pixel = BlackPixel(cc->xdisplay, gdk_screen);
}

static void
init_direct_color(GdkColorContextPrivate *cc)
{
	gint n, count;
	GdkColor *clrs, *cstart;
	gulong rval, gval, bval;
	gulong *rtable;
	gulong *gtable;
	gulong *btable;
	gdouble dinc;

	init_true_color(cc); /* for shift stuff */

	rval = cc->visual->red_mask >> cc->shifts.red;
	gval = cc->visual->green_mask >> cc->shifts.green;
	bval = cc->visual->blue_mask >> cc->shifts.blue;

	rtable = g_new(gulong, rval + 1);
	gtable = g_new(gulong, gval + 1);
	btable = g_new(gulong, bval + 1);

	cc->max_entry = MAX(rval, gval);
	cc->max_entry = MAX(cc->max_entry, bval);

	cstart = g_new(GdkColor, cc->max_entry + 1);
	cc->clut = g_new(gulong, cc->max_entry + 1);

retrydirect:

	for (n = 0; n < rval; n++)
		rtable[n] = rval ? (65535.0 / rval * n) : 0;

	for (n = 0; n < gval; n++)
		gtable[n] = gval ? (65535.0 / gval * n) : 0;

	for (n = 0; n < bval; n++)
		btable[n] = bval ? (65535.0 / bval * n) : 0;

	cc->max_entry = MAX(rval, gval);
	cc->max_entry = MAX(cc->max_entry, bval);

	count = 0;
	clrs = cstart;
	cc->num_colors = (rval + 1) * (gval + 1) * (bval + 1);

	for (n = 0; n < cc->max_entry; n++) {
		dinc = (double) n / cc->max_entry;

		clrs->red   = rtable[(int) (dinc * rval)];
		clrs->green = gtable[(int) (dinc * gval)];
		clrs->blue  = btable[(int) (dinc * bval)];

		if (gdk_color_alloc(cc->colormap, clrs)) {
			cc->clut[count++] = clrs->pixel;
			clrs++;
		} else {
			gdk_colors_free(cc->colormap, cc->clut, count, 0);

			rval >>= 1;
			gval >>= 1;
			bval >>= 1;

			cc->masks.red   = (cc->masks.red >> 1) & cc->visual->red_mask;
			cc->masks.green = (cc->masks.green >> 1) & cc->visual->green_mask;
			cc->masks.blue  = (cc->masks.blue >> 1) & cc->visual->blue_mask;

			cc->shifts.red++;
			cc->shifts.green++;
			cc->shifts.blue++;

			cc->bits.red--;
			cc->bits.green--;
			cc->bits.blue--;

			cc->num_colors = (rval + 1) * (gval + 1) * (bval + 1);

			if (cc->num_colors >1)
				goto retrydirect;
			else {
				g_free(cc->clut);
				cc->clut = NULL;
				init_bw(cc);
				break;
			}
		}
	}

	/* Update allocated color count; original num_colors is max_entry, which
	 * is not necessarily the same as the really allocated number of colors.
	 */

	cc->num_colors = count;

	g_free(rtable);
	g_free(gtable);
	g_free(btable);
	g_free(cstart);
}

static void
init_palette(GdkColorContextPrivate *cc)
{
	/* restore correct mode for this cc */
	
	switch (cc->visual->type) {
		case GDK_VISUAL_STATIC_GRAY:
		case GDK_VISUAL_GRAYSCALE:
			if (GDK_VISUAL_XVISUAL(cc->visual)->map_entries == 2)
				cc->mode = GDK_CC_MODE_BW;
			else
				cc->mode = GDK_CC_MODE_MY_GRAY;
			break;

		case GDK_VISUAL_TRUE_COLOR:
		case GDK_VISUAL_DIRECT_COLOR:
			cc->mode = GDK_CC_MODE_TRUE;
			break;

		case GDK_VISUAL_STATIC_COLOR:
		case GDK_VISUAL_PSEUDO_COLOR:
			cc->mode = GDK_CC_MODE_STD_CMAP;
			break;

		default:
			cc->mode = GDK_CC_MODE_UNDEFINED;
			break;
	}

	/* previous palette */

	if (cc->num_palette)
		g_free(cc->palette);

	if (cc->fast_dither)
		g_free(cc->fast_dither);

	/* clear hash table if present */

	if (cc->color_hash) {
		/* XXX: quick-and-dirty way to remove everything */

		g_hash_table_destroy(cc->color_hash);
		cc->color_hash = g_hash_table_new(hash_color, compare_colors);
	}

	cc->palette = NULL;
	cc->num_palette = 0;
	cc->fast_dither = NULL;
}

GdkColorContext *
gdk_color_context_new(GdkVisual   *visual,
		      GdkColormap *colormap)
{
	gint use_private_colormap = FALSE; /* XXX: maybe restore full functionality later? */
	GdkColorContextPrivate *cc;
	gint retry_count;
	GdkColormap *default_colormap;

	g_assert(visual != NULL);
	g_assert(colormap != NULL);
	
	cc = g_new(GdkColorContextPrivate, 1);
	
	cc->xdisplay = gdk_display;
	cc->visual = visual;
	cc->colormap = colormap;
	cc->clut = NULL;
	cc->cmap = NULL;
	cc->mode = GDK_CC_MODE_UNDEFINED;
	cc->need_to_free_colormap = FALSE;

	cc->color_hash = NULL;
	cc->palette = NULL;
	cc->num_palette = 0;
	cc->fast_dither = NULL;

	default_colormap = gdk_colormap_get_system();

	retry_count = 0;

	while (retry_count < 2) {
		/* Only create a private colormap if the visual found isn't equal
		 * to the default visual and we don't have a private colormap,
		 * -or- if we are instructed to create a private colormap (which
		 * never is the case for XmHTML).
		 */

		if (use_private_colormap
		    || ((cc->visual != gdk_visual_get_system()) /* default visual? */
			&& (GDK_COLORMAP_XCOLORMAP(colormap) == GDK_COLORMAP_XCOLORMAP(default_colormap)))) {
			g_warning("gdk_color_context_new: non-default visual detected, "
				  "using private colormap");

			cc->colormap = gdk_colormap_new(cc->visual, FALSE);

			cc->need_to_free_colormap = (GDK_COLORMAP_XCOLORMAP(colormap)
						     != GDK_COLORMAP_XCOLORMAP(default_colormap));
		}

		switch (visual->type) {
			case GDK_VISUAL_STATIC_GRAY:
			case GDK_VISUAL_GRAYSCALE:
				if (gdk_debug_level >= 1)
					g_print("gdk_color_context_new: visual class is %s",
						(visual->type == GDK_VISUAL_STATIC_GRAY) ?
						"GDK_VISUAL_STATIC_GRAY" :
						"GDK_VISUAL_GRAYSCALE");

				if (GDK_VISUAL_XVISUAL(cc->visual)->map_entries == 2)
					init_bw(cc);
				else
					init_gray(cc);

				break;

			case GDK_VISUAL_TRUE_COLOR: /* shifts */
				if (gdk_debug_level >= 1)
					g_print("gdk_color_context_new: visual class is "
						 "GDK_VISUAL_TRUE_COLOR");

				init_true_color(cc);
				break;

			case GDK_VISUAL_DIRECT_COLOR: /* shifts and fake CLUT */
				if (gdk_debug_level >= 1)
					g_print("gdk_color_context_new: visual class is "
						 "GDK_VISUAL_DIRECT_COLOR");

				init_direct_color(cc);
				break;

			case GDK_VISUAL_STATIC_COLOR:
			case GDK_VISUAL_PSEUDO_COLOR:
				if (gdk_debug_level >= 1)
					g_print("gdk_color_context_new: visual class is %s",
						(visual->type == GDK_VISUAL_STATIC_COLOR) ?
						"GDK_VISUAL_STATIC_COLOR" :
						"GDK_VISUAL_PSEUDO_COLOR");

				init_color(cc);
				break;

			default:
				g_assert_not_reached();
		}

		if ((cc->mode == GDK_CC_MODE_BW) && (cc->visual->depth > 1)) {
			use_private_colormap = TRUE;
			retry_count++;
		} else
			break;
	}

	/* no. of colors allocated yet */

	cc->num_allocated = 0;

	if (gdk_debug_level >= 1)
		g_print("gdk_color_context_new: screen depth is %i, no. of colors is %i",
			cc->visual->depth, cc->num_colors);

	/* check if we need to initialize a hash table */

	if ((cc->mode == GDK_CC_MODE_STD_CMAP) || (cc->mode == GDK_CC_MODE_UNDEFINED))
		cc->color_hash = g_hash_table_new(hash_color, compare_colors);

	return (GdkColorContext *) cc;
}

GdkColorContext *
gdk_color_context_new_mono(GdkVisual   *visual,
			   GdkColormap *colormap)
{
	GdkColorContextPrivate *cc;

	g_assert(visual != NULL);
	g_assert(colormap != NULL);

	cc = g_new(GdkColorContextPrivate, 1);

	cc->xdisplay = gdk_display;
	cc->visual = visual;
	cc->colormap = colormap;
	cc->clut = NULL;
	cc->cmap = NULL;
	cc->mode = GDK_CC_MODE_UNDEFINED;
	cc->need_to_free_colormap = FALSE;

	init_bw(cc);

	return (GdkColorContext *) cc;
}

/* This doesn't currently free black/white, hmm... */

void
gdk_color_context_free(GdkColorContext *cc)
{
	GdkColorContextPrivate *ccp;
	
	g_assert(cc != NULL);

	ccp = (GdkColorContextPrivate *) cc;

	if ((ccp->visual->type == GDK_VISUAL_STATIC_COLOR)
	    || (ccp->visual->type == GDK_VISUAL_PSEUDO_COLOR)) {
		gdk_colors_free(ccp->colormap, ccp->clut, ccp->num_allocated, 0);
		g_free(ccp->clut);
	} else if (ccp->clut != NULL) {
		gdk_colors_free(ccp->colormap, ccp->clut, ccp->num_colors, 0);
		g_free(ccp->clut);
	}

	if (ccp->cmap != NULL)
		g_free(ccp->cmap);

	if (ccp->need_to_free_colormap)
		gdk_colormap_destroy(ccp->colormap);

	/* free any palette that has been associated with this GdkColorContext */

	init_palette(ccp);

	if (ccp->color_hash) {
		g_hash_table_foreach(ccp->color_hash,
				     free_hash_entry,
				     NULL);
		g_hash_table_destroy(ccp->color_hash);
	}

	g_free(cc);
}

gulong
gdk_color_context_get_pixel(GdkColorContext *cc,
			    gushort          red,
			    gushort          green,
			    gushort          blue,
			    gint            *failed)
{
	GdkColorContextPrivate *ccp;
	
	g_assert(cc != NULL);
	g_assert(failed != NULL);

	ccp = (GdkColorContextPrivate *) cc;

	*failed = FALSE;

	switch (ccp->mode) {
		case GDK_CC_MODE_BW: {
			gdouble value;

			red   <<= 8;
			green <<= 8;
			blue  <<= 8;

			value = red / 65535.0 * 0.30
				+ green / 65535.0 * 0.59
				+ blue / 65535.0 * 0.11;

			if (value > 0.5)
				return ccp->white_pixel;

			return ccp->black_pixel;
		}

		case GDK_CC_MODE_MY_GRAY: {
			gulong ired, igreen, iblue;

			red   <<= 8;
			green <<= 8;
			blue  <<= 8;

			red   = red * 0.30 + green * 0.59 + blue * 0.11;
			green = 0;
			blue  = 0;

			if ((ired = red * (ccp->std_cmap.red_max + 1) / 0xffff)
			    > ccp->std_cmap.red_max)
				ired = ccp->std_cmap.red_max;

			ired *= ccp->std_cmap.red_mult;

			if ((igreen = green * (ccp->std_cmap.green_max + 1) / 0xffff)
			    > ccp->std_cmap.green_max)
				igreen = ccp->std_cmap.green_max;

			igreen *= ccp->std_cmap.green_mult;

			if ((iblue = blue * (ccp->std_cmap.blue_max + 1) / 0xffff)
			    > ccp->std_cmap.blue_max)
				iblue = ccp->std_cmap.blue_max;

			iblue *= ccp->std_cmap.blue_mult;

			if (ccp->clut != NULL)
				return ccp->clut[ccp->std_cmap.base_pixel + ired + igreen + iblue];

			return ccp->std_cmap.base_pixel + ired + igreen + iblue;
		}

		case GDK_CC_MODE_TRUE: {
			gulong ired, igreen, iblue;

			red   <<= 8;
			green <<= 8;
			blue  <<= 8;

			if (ccp->clut == NULL) {
				red   >>= 16 - ccp->bits.red;
				green >>= 16 - ccp->bits.green;
				blue  >>= 16 - ccp->bits.blue;

				ired   = (red << ccp->shifts.red) & ccp->masks.red;
				igreen = (green << ccp->shifts.green) & ccp->masks.green;
				iblue  = (blue << ccp->shifts.blue) & ccp->masks.blue;

				return ired | igreen | iblue;
			}

			ired   = ccp->clut[red * ccp->max_entry / 65535] & ccp->masks.red;
			igreen = ccp->clut[green * ccp->max_entry / 65535] & ccp->masks.green;
			iblue  = ccp->clut[blue * ccp->max_entry / 65535] & ccp->masks.blue;

			return ired | igreen | iblue;
		}

		case GDK_CC_MODE_PALETTE:
			return gdk_color_context_get_pixel_from_palette(cc, &red, &green, &blue, failed);

		case GDK_CC_MODE_STD_CMAP:
		default: {
			GdkColor color;
			GdkColor *result;

			red   <<= 8;
			green <<= 8;
			blue  <<= 8;

			color.red   = red;
			color.green = green;
			color.blue  = blue;

			result = g_hash_table_lookup(ccp->color_hash, &color);

			if (!result) {
				color.red   = red;
				color.green = green;
				color.blue  = blue;
				color.pixel = 0;

				if (!gdk_color_alloc(ccp->colormap, &color))
					*failed = TRUE;
				else {
					GdkColor *cnew;
					
					/* XXX: the following comment comes directly from
					 * XCC.c.  I don't know if it is relevant for
					 * gdk_color_alloc() as it is for XAllocColor()
					 * - Federico
					 */
					/*
					 * I can't figure this out entirely, but it *is* possible
					 * that XAllocColor succeeds, even if the number of
					 * allocations we've made exceeds the number of available
					 * colors in the current colormap. And therefore it
					 * might be necessary for us to resize the CLUT.
					 */

					if (ccp->num_allocated == ccp->max_colors) {
						ccp->max_colors *= 2;

						if (gdk_debug_level >= 1)
							g_print("gdk_color_context_get_pixel: "
								"resizing CLUT to %i entries",
								ccp->max_colors);

						ccp->clut = g_realloc(ccp->clut,
								      ccp->max_colors * sizeof(gulong));
					}

					/* Key and value are the same color structure */

					cnew = g_new(GdkColor, 1);
					*cnew = color;
					g_hash_table_insert(ccp->color_hash, cnew, cnew);

					ccp->clut[ccp->num_allocated] = color.pixel;
					ccp->num_allocated++;
					return color.pixel;
				}
			}
			
			return result->pixel;
		}
	}
}

void
gdk_color_context_get_pixels(GdkColorContext *cc,
			     gushort         *reds,
			     gushort         *greens,
			     gushort         *blues,
			     gint             ncolors,
			     gulong          *colors,
			     gint            *nallocated)
{
	GdkColorContextPrivate *ccp;
	gint i, k, idx;
	gint cmapsize, ncols = 0, nopen = 0, counter = 0;
	gint bad_alloc = FALSE;
	gint failed[MAX_IMAGE_COLORS], allocated[MAX_IMAGE_COLORS];
	GdkColor defs[MAX_IMAGE_COLORS], cmap[MAX_IMAGE_COLORS];
	gint exact_col = 0, subst_col = 0, close_col = 0, black_col = 0;

	g_assert(cc != NULL);
	g_assert(reds != NULL);
	g_assert(greens != NULL);
	g_assert(blues != NULL);
	g_assert(colors != NULL);
	g_assert(nallocated != NULL);

	ccp = (GdkColorContextPrivate *) cc;

	memset(defs, 0, MAX_IMAGE_COLORS * sizeof(GdkColor));
	memset(failed, 0, MAX_IMAGE_COLORS * sizeof(gint));
	memset(allocated, 0, MAX_IMAGE_COLORS * sizeof(gint));

	/* Will only have a value if used by the progressive image loader */

	ncols = *nallocated;

	*nallocated = 0;

	/* First allocate all pixels */

	for (i = 0; i < ncolors; i++) {
		/* colors[i] is only zero if the pixel at that location hasn't
		 * been allocated yet.  This is a sanity check required for proper
		 * color allocation by the progressive image loader
		 */

		if (colors[i] == 0) {
			defs[i].red   = reds[i];
			defs[i].green = greens[i];
			defs[i].blue  = blues[i];

			colors[i] = gdk_color_context_get_pixel(cc, reds[i], greens[i], blues[i],
								&bad_alloc);

			/* successfully allocated, store it */

			if (!bad_alloc) {
				defs[i].pixel = colors[i];
				allocated[ncols++] = colors[i];
			} else
				failed[nopen++] = i;
		}
	}

	*nallocated = ncols;

	/* all colors available, all done */

	if ((ncols == ncolors) || (nopen == 0)) {
		if (gdk_debug_level >= 1)
			g_print("gdk_color_context_get_pixels: got all %i colors; "
				"(%i colors allocated so far", ncolors, ccp->num_allocated);

		return;
	}

	/* The fun part.  We now try to allocate the colors we couldn't allocate
	 * directly.  The first step will map a color onto its nearest color
	 * that has been allocated (either by us or someone else).  If any colors
	 * remain unallocated, we map these onto the colors that we have allocated
	 * ourselves.
	 */

	/* read up to MAX_IMAGE_COLORS colors of the current colormap */

	cmapsize = MIN(ccp->num_colors, MAX_IMAGE_COLORS);

	/* see if the colormap has any colors to read */

	if (cmapsize < 0) {
		g_warning("gdk_color_context_get_pixels: oops!  no colors available, "
			  "your images will look *really* ugly.");

		return;
	}

#ifdef DEBUG
	exact_col = ncols;
#endif

	/* initialize pixels */

	for (i = 0; i < cmapsize; i++) {
		cmap[i].pixel = i;
		cmap[i].red = cmap[i].green = cmap[i].blue = 0;
	}

	/* read the colormap */

	my_x_query_colors(ccp->colormap, cmap, cmapsize);

	/* speedup: downscale here instead of in the matching code */

	for (i = 0; i < cmapsize; i++) {
		cmap[i].red   >>= 8;
		cmap[i].green >>= 8;
		cmap[i].blue  >>= 8;
	}

	/* get a close match for any unallocated colors */

	counter = nopen;
	nopen = 0;
	idx = 0;

	do {
		gint d, j, mdist, close, ri, gi, bi;
		gint rd, gd, bd;

		i = failed[idx];

		mdist = 1000000;
		close = -1;

		/* Store these vals.  Small performance increase as this skips three
		 * indexing operations in the loop code.
		 */

		ri = reds[i];
		gi = greens[i];
		bi = blues[i];

		/* Walk all colors in the colormap and see which one is the
		 * closest.  Uses plain least squares.
		 */

		for (j = 0; (j < cmapsize) && (mdist != 0); j++) {
			rd = ri - cmap[j].red;
			gd = gi - cmap[j].green;
			bd = bi - cmap[j].blue;

			d = rd * rd + gd * gd + bd * bd;

			if (d < mdist) {
				close = j;
				mdist = d;
			}
		}

		if (close != -1) {
			rd = cmap[close].red;
			gd = cmap[close].green;
			bd = cmap[close].blue;

			/* allocate */

			colors[i] = gdk_color_context_get_pixel(cc, rd, gd, bd, &bad_alloc);

			/* store */

			if (!bad_alloc) {
				defs[i] = cmap[close];
				defs[i].pixel = colors[i];
				allocated[ncols++] = colors[i];
#ifdef DEBUG
				close_col++;
#endif
			} else
				failed[nopen++] = i;
		} else
			failed[nopen++] = i;
		/* deal with in next stage if allocation failed */
	} while (++idx < counter);

	*nallocated = ncols;

	/* This is the maximum no. of allocated colors.  See also the nopen == 0
	 * note above.
	 */

	if ((ncols == ncolors) || (nopen == 0)) {
		if (gdk_debug_level >= 1)
			g_print("gdk_color_context_get_pixels: got %i colors, %i exact and "
				"%i close (%i colors allocated so far)",
				ncolors, exact_col, close_col, ccp->num_allocated);

		return;
	}

	/* Now map any remaining unallocated pixels into the colors we did get */

	idx = 0;

	do {
		gint d, mdist, close, ri, gi, bi;
		gint j, rd, gd, bd;

		i = failed[idx];

		mdist = 1000000;
		close = -1;

		/* store */

		ri = reds[i];
		gi = greens[i];
		bi = blues[i];

		/* search allocated colors */

		for (j = 0; (j < ncols) && (mdist != 0); j++) {
			k = allocated[j];

			rd = ri - defs[k].red;
			gd = gi - defs[k].green;
			bd = bi - defs[k].blue;

			d = rd * rd + gd * gd + bd * bd;

			if (d < mdist) {
				close = k;
				mdist = d;
			}
		}

		if (close < 0) {
			/* too bad, map to black */

			defs[i].pixel = ccp->black_pixel;
			defs[i].red = defs[i].green = defs[i].blue = 0;
#ifdef DEBUG
			black_col++;
#endif
		} else {
			defs[i] = defs[close];
#ifdef DEBUG
			subst_col++;
#endif
		}

		colors[i] = defs[i].pixel;
	} while (++idx < nopen);

	if (gdk_debug_level >= 1)
		g_print("gdk_color_context_get_pixels: got %i colors, %i exact, %i close, "
			"%i substituted, %i to black (%i colors allocated so far)",
			ncolors, exact_col, close_col, subst_col, black_col, ccp->num_allocated);
}

void
gdk_color_context_get_pixels_incremental(GdkColorContext *cc,
					 gushort         *reds,
					 gushort         *greens,
					 gushort         *blues,
					 gint             ncolors,
					 gint            *used,
					 gulong          *colors,
					 gint            *nallocated)
{
	GdkColorContextPrivate *ccp;
	gint i, k, idx;
	gint cmapsize, ncols = 0, nopen = 0, counter = 0;
	gint bad_alloc = FALSE;
	gint failed[MAX_IMAGE_COLORS], allocated[MAX_IMAGE_COLORS];
	GdkColor defs[MAX_IMAGE_COLORS], cmap[MAX_IMAGE_COLORS];
	gint exact_col = 0, subst_col = 0, close_col = 0, black_col = 0;

	g_assert(cc != NULL);
	g_assert(reds != NULL);
	g_assert(greens != NULL);
	g_assert(blues != NULL);
	g_assert(used != NULL);
	g_assert(colors != NULL);
	g_assert(nallocated != NULL);

	ccp = (GdkColorContextPrivate *) cc;

	memset(defs, 0, MAX_IMAGE_COLORS * sizeof(GdkColor));
	memset(failed, 0, MAX_IMAGE_COLORS * sizeof(gint));
	memset(allocated, 0, MAX_IMAGE_COLORS * sizeof(gint));

	/* Will only have a value if used by the progressive image loader */

	ncols = *nallocated;

	*nallocated = 0;

	/* First allocate all pixels */

	for (i = 0; i < ncolors; i++) {
		/* used[i] is only -1 if the pixel at that location hasn't
		 * been allocated yet.  This is a sanity check required for proper
		 * color allocation by the progressive image loader.
		 * When colors[i] == 0 it indicates the slot is available for
		 * allocation.
		 */

		if (used[i] != FALSE) {
			if (colors[i] == 0) {
				defs[i].red   = reds[i];
				defs[i].green = greens[i];
				defs[i].blue  = blues[i];

				colors[i] = gdk_color_context_get_pixel(cc, reds[i], greens[i], blues[i], &bad_alloc);

				/* successfully allocated, store it */

				if (!bad_alloc) {
					defs[i].pixel = colors[i];
					allocated[ncols++] = colors[i];
				} else
					failed[nopen++] = i;
			}
#ifdef DEBUG
			else
				if (gdk_debug_level >= 1)
					g_print("gdk_color_context_get_pixels_incremental: "
						"pixel at slot %i already allocated, skipping", i);
#endif
		}
	}

	*nallocated = ncols;

	if ((ncols == ncolors) || (nopen == 0)) {
		if (gdk_debug_level >= 1)
			g_print("gdk_color_context_get_pixels_incremental: got all %i colors "
				"(%i colors allocated so far)",
				ncolors, ccp->num_allocated);

		return;
	}

	cmapsize = MIN(ccp->num_colors, MAX_IMAGE_COLORS);

	if (cmapsize < 0) {
		g_warning("gdk_color_context_get_pixels_incremental: oops!  "
			  "No colors available images will look *really* ugly.");
		return;
	}

#ifdef DEBUG
	exact_col = ncols;
#endif

	/* initialize pixels */

	for (i = 0; i < cmapsize; i++) {
		cmap[i].pixel = i;
		cmap[i].red = cmap[i].green = cmap[i].blue = 0;
	}

	/* read and downscale */

	my_x_query_colors(ccp->colormap, cmap, cmapsize);

	for (i = 0; i < cmapsize; i++) {
		cmap[i].red   >>= 8;
		cmap[i].green >>= 8;
		cmap[i].blue  >>= 8;
	}

	/* now match any unallocated colors */

	counter = nopen;
	nopen = 0;
	idx = 0;

	do {
		gint d, j, mdist, close, ri, gi, bi;
		gint rd, gd, bd;

		i = failed[idx];

		mdist = 1000000;
		close = -1;

		/* store */

		ri = reds[i];
		gi = greens[i];
		bi = blues[i];

		for (j = 0; (j < cmapsize) && (mdist != 0); j++) {
			rd = ri - cmap[j].red;
			gd = gi - cmap[j].green;
			bd = bi - cmap[j].blue;

			d = rd * rd + gd * gd + bd * bd;

			if (d < mdist) {
				close = j;
				mdist = d;
			}
		}

		if (close != -1) {
			rd = cmap[close].red;
			gd = cmap[close].green;
			bd = cmap[close].blue;

			/* allocate */

			colors[i] = gdk_color_context_get_pixel(cc, rd, gd, bd, &bad_alloc);

			/* store */

			if (!bad_alloc) {
				defs[i] = cmap[close];
				defs[i].pixel = colors[i];
				allocated[ncols++] = colors[i];
#ifdef DEBUG
				close_col++;
#endif
			} else
				failed[nopen++] = i;
		} else
			failed[nopen++] = i;
		/* deal with in next stage if allocation failed */
	} while (++idx < counter);

	*nallocated = ncols;

	if ((ncols == ncolors) || (nopen == 0)) {
		if (gdk_debug_level >= 1)
			g_print("gdk_color_context_get_pixels_incremental: "
				"got %i colors, %i exact and %i close "
				"(%i colors allocated so far)",
				ncolors, exact_col, close_col, ccp->num_allocated);

		return;
	}

	/* map remaining unallocated pixels into colors we did get */

	idx = 0;

	do {
		gint d, mdist, close, ri, gi, bi;
		gint j, rd, gd, bd;

		i = failed[idx];

		mdist = 1000000;
		close = -1;

		ri = reds[i];
		gi = greens[i];
		bi = blues[i];

		/* search allocated colors */

		for (j = 0; (j < ncols) && (mdist != 0); j++) {
			k = allocated[j];

			/* downscale */

			rd = ri - defs[k].red;
			gd = gi - defs[k].green;
			bd = bi - defs[k].blue;

			d = rd * rd + gd * gd + bd * bd;

			if (d < mdist) {
				close = k;
				mdist = d;
			}
		}

		if (close < 0) {
			/* too bad, map to black */

			defs[i].pixel = ccp->black_pixel;
			defs[i].red = defs[i].green = defs[i].blue = 0;
#ifdef DEBUG
			black_col++;
#endif
		} else {
			defs[i] = defs[close];
#ifdef DEBUG
			subst_col++;
#endif
		}

		colors[i] = defs[i].pixel;
	} while (++idx < nopen);

	if (gdk_debug_level >= 1)
		g_print("gdk_color_context_get_pixels_incremental: "
			"got %i colors, %i exact, %i close, %i substituted, %i to black "
			"(%i colors allocated so far)",
			ncolors, exact_col, close_col, subst_col, black_col, ccp->num_allocated);
}

gint
gdk_color_context_get_num_colors(GdkColorContext *cc)
{
	g_assert(cc != NULL);
	
	return ((GdkColorContextPrivate *) cc)->num_colors;
}

gint
gdk_color_context_query_color(GdkColorContext *cc,
			      GdkColor        *color)
{
	return gdk_color_context_query_colors(cc, color, 1);
}

gint
gdk_color_context_query_colors(GdkColorContext *cc,
			       GdkColor        *colors,
			       gint             num_colors)
{
	GdkColorContextPrivate *ccp;
	gint i;
	GdkColor *tc;
	
	g_assert(cc != NULL);
	g_assert(colors != NULL);

	ccp = (GdkColorContextPrivate *) cc;

	switch (ccp->mode) {
		case GDK_CC_MODE_BW:
			for (i = 0, tc = colors; i < num_colors; i++, tc++) {
				if (tc->pixel == ccp->white_pixel)
					tc->red = tc->green = tc->blue = 65535;
				else
					tc->red = tc->green = tc->blue = 0;
			}
			break;

		case GDK_CC_MODE_TRUE:
			if (ccp->clut == NULL)
				for (i = 0, tc = colors; i < num_colors; i++, tc++) {
					tc->red   = (tc->pixel & ccp->masks.red) * 65535 / ccp->masks.red;
					tc->green = (tc->pixel & ccp->masks.green) * 65535 / ccp->masks.green;
					tc->blue  = (tc->pixel & ccp->masks.blue) * 65535 / ccp->masks.blue;
				}
			else {
				my_x_query_colors(ccp->colormap, colors, num_colors);
				return 1;
			}
			break;

		case GDK_CC_MODE_STD_CMAP:
		default:
			if (ccp->cmap == NULL) {
				my_x_query_colors(ccp->colormap, colors, num_colors);
				return 1;
			} else {
				gint first, last, half;
				gulong half_pixel;

				for (i = 0, tc = colors; i < num_colors; i++) {
					first = 0;
					last = ccp->num_colors - 1;

					while (first <= last) {
						half = (first + last) / 2;
						half_pixel = ccp->cmap[half].pixel;

						if (tc->pixel == half_pixel) {
							tc->red   = ccp->cmap[half].red;
							tc->green = ccp->cmap[half].green;
							tc->blue  = ccp->cmap[half].blue;
							first = last + 1; /* false break */
						} else {
							if (tc->pixel > half_pixel)
								first = half + 1;
							else
								last = half - 1;
						}
					}
				}
				return 1;
			}
			break;
	}
	return 1;
}

gint
gdk_color_context_add_palette(GdkColorContext *cc,
			      GdkColor        *palette,
			      gint             num_palette)
{
	GdkColorContextPrivate *ccp;
	gint i, j, erg;
	gushort r, g, b;
	gulong pixel[1];

	g_assert(cc != NULL);

	ccp = (GdkColorContextPrivate *) cc;

	/* initialize this palette (will also erase previous palette as well) */

	init_palette(ccp);

	/* restore previous mode if we aren't adding a new palette */

	if (num_palette == 0) {
		/* GDK_CC_MODE_STD_CMAP uses a hash table, so we'd better initialize one */

		/* XXX: here, the hash table is already initialized */

		return 0;
	}

	/* Initialize a hash table for this palette (we need one for allocating
	 * the pixels in the palette using the current settings)
	 */

	if (ccp->color_hash == NULL)
		ccp->color_hash = g_hash_table_new(hash_color, compare_colors);

	/* copy incoming palette */

	ccp->palette = g_new0(GdkColor, num_palette);

	j = 0;

	for (i = 0; i < num_palette; i++) {
		erg = 0;
		pixel[0] = 0;

		/* try to allocate this color */

		r = palette[i].red;
		g = palette[i].green;
		b = palette[i].blue;

		gdk_color_context_get_pixels(cc, &r, &g, &b, 1, pixel, &erg);

		/* only store if we succeed */

		if (erg) {
			/* store in palette */

			ccp->palette[j].red   = r;
			ccp->palette[j].green = g;
			ccp->palette[j].blue  = b;
			ccp->palette[j].pixel = pixel[0];

			/* move to next slot */

			j++;
		}
	}

	/* resize to fit */

	if (j != num_palette)
		ccp->palette = g_realloc(ccp->palette, j * sizeof(GdkColor));

	/* clear the hash table, we don't use it when dithering */

	if (ccp->color_hash) {
		g_hash_table_destroy(ccp->color_hash);
		ccp->color_hash = NULL;
	}

	/* store real palette size */

	ccp->num_palette = j;

	/* switch to palette mode */

	ccp->mode = GDK_CC_MODE_PALETTE;

	/* sort palette */

	qsort(ccp->palette, ccp->num_palette, sizeof(GdkColor), pixel_sort);

	ccp->fast_dither = NULL;

	return j;
}

void
gdk_color_context_init_dither(GdkColorContext *cc)
{
	GdkColorContextPrivate *ccp;
	gint rr, gg, bb, err, erg, erb;
	gint success = FALSE;

	g_assert(cc != NULL);

	ccp = (GdkColorContextPrivate *) cc;

	/* now we can initialize the fast dither matrix */

	if(ccp->fast_dither == NULL)
		ccp->fast_dither = g_new(GdkColorContextDither, 1);

	/* Fill it.  We ignore unsuccessful allocations, they are just mapped
	 * to black instead */

	for (rr = 0; rr < 32; rr++)
		for (gg = 0; gg < 32; gg++)
			for (bb = 0; bb < 32; bb++) {
				err = (rr << 3) | (rr >> 2);
				erg = (gg << 3) | (gg >> 2);
				erb = (bb << 3) | (bb >> 2);

				ccp->fast_dither->fast_rgb[rr][gg][bb] =
					gdk_color_context_get_index_from_palette(cc, &err, &erg, &erb, &success);
				ccp->fast_dither->fast_err[rr][gg][bb] = err;
				ccp->fast_dither->fast_erg[rr][gg][bb] = erg;
				ccp->fast_dither->fast_erb[rr][gg][bb] = erb;
			}
}

void
gdk_color_context_free_dither(GdkColorContext *cc)
{
	GdkColorContextPrivate *ccp;

	g_assert(cc != NULL);

	ccp = (GdkColorContextPrivate *) cc;

	if (ccp->fast_dither)
		g_free(ccp->fast_dither);

	ccp->fast_dither = NULL;
}

gulong
gdk_color_context_get_pixel_from_palette(GdkColorContext *cc,
					 gushort         *red,
					 gushort         *green,
					 gushort         *blue,
					 gint            *failed)
{
	GdkColorContextPrivate *ccp;
	gulong pixel = 0;
	gint dif, dr, dg, db, j = -1;
	gint mindif = 0x7fffffff;
	gint err = 0, erg = 0, erb = 0;
	gint i;

	g_assert(cc != NULL);
	g_assert(red != NULL);
	g_assert(green != NULL);
	g_assert(blue != NULL);
	g_assert(failed != NULL);

	ccp = (GdkColorContextPrivate *) cc;

	*failed = FALSE;

	for (i = 0; i < ccp->num_palette; i++) {
		dr = *red - ccp->palette[i].red;
		dg = *green - ccp->palette[i].green;
		db = *blue - ccp->palette[i].blue;

		dif = dr * dr + dg * dg + db * db;
		
		if (dif < mindif) {
			mindif = dif;
			j = i;
			pixel = ccp->palette[i].pixel;
			err = dr;
			erg = dg;
			erb = db;

			if (mindif == 0)
				break;
		}
	}

	/* we failed to map onto a color */

	if (j == -1)
		*failed = TRUE;
	else {
		*red   = ABS(err);
		*green = ABS(erg);
		*blue  = ABS(erb);
	}

	return pixel;
}

guchar
gdk_color_context_get_index_from_palette(GdkColorContext *cc,
					 gint            *red,
					 gint            *green,
					 gint            *blue,
					 gint            *failed)
{
	GdkColorContextPrivate *ccp;
	gint dif, dr, dg, db, j = -1;
	gint mindif = 0x7fffffff;
	gint err = 0, erg = 0, erb = 0;
	gint i;

	g_assert(cc != NULL);
	g_assert(red != NULL);
	g_assert(green != NULL);
	g_assert(blue != NULL);
	g_assert(failed != NULL);

	ccp = (GdkColorContextPrivate *) cc;

	*failed = FALSE;

	for (i = 0; i < ccp->num_palette; i++) {
		dr = *red - ccp->palette[i].red;
		dg = *green - ccp->palette[i].green;
		db = *blue - ccp->palette[i].blue;

		dif = dr * dr + dg * dg + db * db;

		if (dif < mindif) {
			mindif = dif;
			j = i;
			err = dr;
			erg = dg;
			erb = db;

			if (mindif == 0)
				break;
		}
	}

	/* we failed to map onto a color */

	if (j == -1) {
		*failed = TRUE;
		j = 0;
	} else {
		/* return error fractions */

		*red   = err;
		*green = erg;
		*blue  = erb;
	}

	return j;
}