path: root/generic/Color.c

/*
 * Color.c -- Color management module.
 *
 * Authors		: Patrick Lecoanet.
 * Creation date	: Thu Dec 16 15:41:53 1999
 *
 * $Id$
 */

/*
 *  Copyright (c) 1999 CENA, Patrick Lecoanet --
 *
 * This code 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 code 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 code; if not, write to the Free
 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 */

/*
 * Most of this file is derived from Tk color code and thus
 * also copyrighted:
 *
 * Copyright (c) 1991-1994 The Regents of the University of California.
 * Copyright (c) 1994-1995 Sun Microsystems, Inc.
 *
 */


#include <malloc.h>
#include <string.h>
#include <stdlib.h>

#include "Types.h"
#include "Image.h"
#include "Color.h"
#include "Geo.h"


/*
 * If a colormap fills up, attempts to allocate new colors from that
 * colormap will fail.  When that happens, we'll just choose the
 * closest color from those that are available in the colormap.
 * One of the following structures will be created for each "stressed"
 * colormap to keep track of the colors that are available in the
 * colormap (otherwise we would have to re-query from the server on
 * each allocation, which would be very slow).  These entries are
 * flushed after a few seconds, since other clients may release or
 * reallocate colors over time.
 */
typedef struct StressedCmap {
  Colormap	colormap;	/* X's token for the colormap. */
  int		num_colors;	/* Number of entries currently active
				 * at *colorPtr. */
  XColor	*color;		/* Pointer to malloc'ed array of all
				 * colors that seem to be available in
				 * the colormap.  Some may not actually
				 * be available, e.g. because they are
				 * read-write for another client;  when
				 * we find this out, we remove them
				 * from the array. */
  struct StressedCmap *next;	/* Next in list of all stressed
				 * colormaps for the display. */
} StressedCmap;

typedef struct StressedDpy {
  Display		*dpy;
  StressedCmap		*stress;
  struct StressedDpy	*next;
} StressedDpy;

static StressedDpy	*stressed_display_list = NULL;


#define COLOR_MAGIC ((unsigned int) 0x46140277)

typedef struct ZnColorInfo {
  XColor	color;		/* Information about this color. */
  unsigned int	magic;		/* Used for quick integrity check on this
				 * structure.   Must always have the
				 * value COLOR_MAGIC. */
  Screen	*screen;	/* Screen where this color is valid.  Used
				 * to delete it, and to find its display. */
  Colormap	colormap;	/* Colormap from which this entry was
				 * allocated. */
  Visual	*visual;	/* Visual associated with colormap. */
  int		ref_count;	/* Number of uses of this structure. */
  Tcl_HashTable	*table;		/* Hash table that indexes this structure
				 * (needed when deleting structure). */
  Tcl_HashEntry	*hash;		/* Pointer to hash table entry for this
				 * structure. (for use in deleting entry). */
} ZnColorInfo;


/*
 * A two-level data structure is used to manage the color database.
 * The top level consists of one entry for each color name that is
 * currently active, and the bottom level contains one entry for each
 * pixel value that is still in use.  The distinction between
 * levels is necessary because the same pixel may have several
 * different names.  There are two hash tables, one used to index into
 * each of the data structures.  The name hash table is used when
 * allocating colors, and the pixel hash table is used when freeing
 * colors.
 */

/*
 * Hash table for name -> ZnColorInfo mapping, and key structure used to
 * index into that table:
 */
static Tcl_HashTable	name_table;

typedef struct {
    Tk_Uid name;		/* Name of desired color. */
    Colormap colormap;		/* Colormap from which color will be
				 * allocated. */
    Display *display;		/* Display for colormap. */
} NameKey;


/*
 * Hash table for value -> ZnColorInfo mapping, and key structure used to
 * index into that table:
 */
static Tcl_HashTable	value_table;

typedef struct {
    int red, green, blue;	/* Values for desired color. */
    Colormap colormap;		/* Colormap from which color will be
				 * allocated. */
    Display *display;		/* Display for colormap. */
} ValueKey;


/*
 * Maximum size of a color name including the \0.
 */
#define COLOR_NAME_SIZE 32
/*
 * Maximum size of a gradient name including the \0.
 */
#define GRADIENT_NAME_SIZE 1024

/*
 * Maximum intensity for a color.
 */
#define MAX_INTENSITY 65535

/*
 * Hash table to map from a gradient's values (color, etc.) to a
 * gradient structure for those values.
 */
static Tcl_HashTable gradient_table;

static int initialized = 0;	/* 0 means static structures haven't been
				 * initialized yet. */


/*
 *----------------------------------------------------------------------
 *
 * GetStressedDisplay --
 *
 *
 *----------------------------------------------------------------------
 */
static StressedDpy *
GetStressedDisplay(Display	*dpy)
{
  StressedDpy	*cur;

  for (cur = stressed_display_list; cur != NULL; cur = cur->next) {
    if (cur->dpy == dpy) {
      break;
    }
  }
  if (cur == NULL) {
    /*
     * Not found, allocate a new one.
     */
    cur = (StressedDpy *) ZnMalloc(sizeof(StressedDpy));
    cur->dpy = dpy;
    cur->stress = NULL;
    cur->next = stressed_display_list;
    stressed_display_list = cur;
  }
  
  return cur;
}


/*
 *----------------------------------------------------------------------
 *
 * DeleteStressedCmap --
 *
 *	This procedure releases the information cached for "colormap"
 *	so that it will be refetched from the X server the next time
 *	it is needed.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	The StressedCmap structure for colormap is deleted;  the
 *	colormap is no longer considered to be "stressed".
 *
 * Note:
 *	This procedure is invoked whenever a color in a colormap is
 *	freed, and whenever a color allocation in a colormap succeeds.
 *	This guarantees that StressedCmap structures are always
 *	deleted before the corresponding Colormap is freed.
 *
 *----------------------------------------------------------------------
 */
static void
DeleteStressedCmap(Display	*display,
		   Colormap	colormap)
{
  StressedDpy	*dpy = GetStressedDisplay(display);
  StressedCmap	*prev, *stress;
  
  for (prev = NULL, stress = dpy->stress; stress != NULL;
       prev = stress, stress = stress->next) {
    if (stress->colormap == colormap) {
      if (prev == NULL) {
	dpy->stress = stress->next;
      }
      else {
	prev->next = stress->next;
      }
      ZnFree(stress->color);
      ZnFree(stress);
      return;
    }
  }
}


/*
 *----------------------------------------------------------------------
 *
 * FindClosestColor --
 *
 *	When Tk can't allocate a color because a colormap has filled
 *	up, this procedure is called to find and allocate the closest
 *	available color in the colormap.
 *
 * Results:
 *	There is no return value, but *actualColorPtr is filled in
 *	with information about the closest available color in tkwin's
 *	colormap.  This color has been allocated via X, so it must
 *	be released by the caller when the caller is done with it.
 *
 * Side effects:
 *	A color is allocated.
 *
 *----------------------------------------------------------------------
 */
static void
FindClosestColor(Tk_Window	tkwin,		/* Window where color will
						 * be used. */
		 XColor		*desired_color,	/* RGB values of color that was
						 * wanted (but unavailable). */
		 XColor		*actual_color)	/* Structure to fill in with
						 * RGB and pixel for closest
						 * available color. */
{
  StressedDpy	*dpy = GetStressedDisplay(Tk_Display(tkwin));
  StressedCmap	*stress;
  double	tmp, distance, closest_dist;
  int		i, closest, num_found;
  XColor	*color;
  Colormap	colormap = Tk_Colormap(tkwin);
  XVisualInfo	template, *vis_info;
  
  /*
   * Find the StressedCmap structure for this colormap, or create
   * a new one if needed.
   */
  for (stress = dpy->stress; ; stress = stress->next) {
    if (stress == NULL) {
      stress = (StressedCmap *) ZnMalloc(sizeof(StressedCmap));
      stress->colormap = colormap;
      template.visualid = XVisualIDFromVisual(Tk_Visual(tkwin));
      vis_info = XGetVisualInfo(Tk_Display(tkwin), VisualIDMask,
				&template, &num_found);
      if (num_found < 1) {
	ZnWarning("FindClosestColor (Zinc) couldn't lookup visual\n");
	abort();
      }
      stress->num_colors = vis_info->colormap_size;
      XFree((char *) vis_info);
      stress->color = (XColor *) ZnMalloc((unsigned)
					     (stress->num_colors*sizeof(XColor)));
      for (i = 0; i < stress->num_colors; i++) {
	stress->color[i].pixel = (unsigned long) i;
      }
      XQueryColors(Tk_Display(tkwin), colormap, stress->color, stress->num_colors);
      stress->next = dpy->stress;
      dpy->stress = stress;
      break;
    }
    if (stress->colormap == colormap) {
      break;
    }
  }
  
  /*
   * Find the color that best approximates the desired one, then
   * try to allocate that color.  If that fails, it must mean that
   * the color was read-write (so we can't use it, since it's owner
   * might change it) or else it was already freed.  Try again,
   * over and over again, until something succeeds.
   */
  while (1)  {
    if (stress->num_colors == 0) {
      ZnWarning("FindClosestColor (Zinc) ran out of colors\n");
      abort();
    }
    closest_dist = 1e30;
    closest = 0;
    for (color = stress->color, i = 0; i < stress->num_colors;
	 color++, i++) {
      /*
       * Use Euclidean distance in RGB space, weighted by Y (of YIQ)
       * as the objective function;  this accounts for differences
       * in the color sensitivity of the eye.
       */
      tmp = 0.30*(((int) desired_color->red) - (int) color->red);
      distance = tmp*tmp;
      tmp = 0.61*(((int) desired_color->green) - (int) color->green);
      distance += tmp*tmp;
      tmp = 0.11*(((int) desired_color->blue) - (int) color->blue);
      distance += tmp*tmp;
      if (distance < closest_dist) {
	closest = i;
	closest_dist = distance;
      }
    }
    if (XAllocColor(Tk_Display(tkwin), colormap, &stress->color[closest]) != 0) {
      *actual_color = stress->color[closest];
      return;
    }
    
    /*
     * Couldn't allocate the color.  Remove it from the table and
     * go back to look for the next best color.
     */
    stress->color[closest] = stress->color[stress->num_colors-1];
    stress->num_colors -= 1;
  }
}


/*
 *----------------------------------------------------------------------
 *
 * CmapStressed --
 *
 *	Check to see whether a given colormap is known to be out
 *	of entries.
 *
 * Results:
 *	1 is returned if "colormap" is stressed (i.e. it has run out
 *	of entries recently), 0 otherwise.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */
#if 0
static ZnBool
CmapStressed(Tk_Window	tkwin,
	     Colormap	colormap)
{
  StressedDpy	*dpy = GetStressedDisplay(Tk_Display(tkwin));
  StressedCmap	*stress;

  for (stress = dpy->stress; stress != NULL; stress = stress->next) {
    if (stress->colormap == colormap) {
      return True;
    }
  }
  return False;
}
#endif


/*
 *----------------------------------------------------------------------
 *
 * ColorInit --
 *
 *	Initialize the structure used for color management.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	Read the code.
 *
 *----------------------------------------------------------------------
 */
static void
ColorInit()
{
  initialized = 1;
  Tcl_InitHashTable(&name_table, sizeof(NameKey)/sizeof(int));
  Tcl_InitHashTable(&value_table, sizeof(ValueKey)/sizeof(int));
  Tcl_InitHashTable(&gradient_table, TCL_STRING_KEYS);
}


/*
 *----------------------------------------------------------------------
 *
 * ZnGetColor --
 *
 *	Given a string name for a color, map the name to a corresponding
 *	XColor structure.
 *
 * Results:
 *	The return value is a pointer to an XColor structure that
 *	indicates the red, blue, and green intensities for the color
 *	given by "name", and also specifies a pixel value to use to
 *	draw in that color.  If an error occurs, NULL is returned and
 *	an error message will be left in interp->result.
 *
 * Side effects:
 *	The color is added to an internal database with a reference count.
 *	For each call to this procedure, there should eventually be a call
 *	to ZnFreeColor so that the database is cleaned up when colors
 *	aren't in use anymore.
 *
 *----------------------------------------------------------------------
 */
XColor *
ZnGetColor(Tcl_Interp	*interp,
	   Tk_Window	tkwin,	/* Window in which color will be used. */
	   Tk_Uid	name)	/* Name of color to allocated (in form
				 * suitable for passing to XParseColor). */
{
  NameKey	name_key;
  Tcl_HashEntry	*name_hash;
  int		new;
  Display	*dpy = Tk_Display(tkwin);
  Colormap	colormap = Tk_Colormap(tkwin);
  XColor	color, screen;
  ZnColorInfo	*tk_col;

  if (!initialized) {
    ColorInit();
  }

  /*
   * First, check to see if there's already a mapping for this color
   * name.
   */
  name = Tk_GetUid(name);
  name_key.name = name;
  name_key.colormap = Tk_Colormap(tkwin);
  name_key.display = Tk_Display(tkwin);
  name_hash = Tcl_CreateHashEntry(&name_table, (char *) &name_key, &new);
  if (!new) {
    tk_col = (ZnColorInfo *) Tcl_GetHashValue(name_hash);
    tk_col->ref_count++;
    /*printf("ZnGetColor cache hit for: %d %d %d\n",
      tk_col->color.red, tk_col->color.green, tk_col->color.blue);*/ 
    return &tk_col->color;
  }

  /*
   * Map from the name to a pixel value.  Call XAllocNamedColor rather than
   * XParseColor for non-# names: this saves a server round-trip for those
   * names.
   */
  if (*name != '#') {
    if (XAllocNamedColor(dpy, colormap, name, &screen, &color) != 0) {
      DeleteStressedCmap(dpy, colormap);
    }
    else {
      /*
       * Couldn't allocate the color.  Try translating the name to
       * a color value, to see whether the problem is a bad color
       * name or a full colormap.  If the colormap is full, then
       * pick an approximation to the desired color.
       */
      if (XLookupColor(dpy, colormap, name, &color, &screen) == 0) {
      col_err:
	if (*name == '#') {
	  Tcl_AppendResult(interp, "invalid color name \"", name,
			   "\"", (char *) NULL);
	}
	else {
	  Tcl_AppendResult(interp, "unknown color name \"", name,
			   "\"", (char *) NULL);
	}
	Tcl_DeleteHashEntry(name_hash);
	return (XColor *) NULL;  
      }
      FindClosestColor(tkwin, &screen, &color);
    }
  }
  else {
    if (XParseColor(dpy, colormap, name, &color) == 0) {
      goto col_err;
    }
    /*printf("parsed color : %d %d %d\n", color.red, color.green, color.blue);*/
    if (XAllocColor(dpy, colormap, &color) != 0) {
      /*printf("alloced color : %d %d %d\n", color.red, color.green, color.blue);*/
      DeleteStressedCmap(dpy, colormap);
    }
    else {
      FindClosestColor(tkwin, &color, &color);
    }
  }
  
  tk_col = (ZnColorInfo *) ZnMalloc(sizeof(ZnColorInfo));
  tk_col->color = color;

  /*
   * Now create a new ZnColorInfo structure and add it to nameTable.
   */  
  tk_col->magic = COLOR_MAGIC;
  tk_col->screen = Tk_Screen(tkwin);
  tk_col->colormap = name_key.colormap;
  tk_col->visual  = Tk_Visual(tkwin);
  tk_col->ref_count = 1;
  tk_col->table = &name_table;
  tk_col->hash = name_hash;
  Tcl_SetHashValue(name_hash, tk_col);
  
  /*printf("ZnGetColor created: %x %x %x\n",
    tk_col->color.red, tk_col->color.green, tk_col->color.blue);*/ 
  return &tk_col->color;
}


/*
 *----------------------------------------------------------------------
 *
 * ZnGetColorByValue --
 *
 *	Given a desired set of red-green-blue intensities for a color,
 *	locate a pixel value to use to draw that color in a given
 *	window.
 *
 * Results:
 *	The return value is a pointer to an XColor structure that
 *	indicates the closest red, blue, and green intensities available
 *	to those specified in colorPtr, and also specifies a pixel
 *	value to use to draw in that color.
 *
 * Side effects:
 *	The color is added to an internal database with a reference count.
 *	For each call to this procedure, there should eventually be a call
 *	to ZnFreeColor, so that the database is cleaned up when colors
 *	aren't in use anymore.
 *
 *----------------------------------------------------------------------
 */
XColor *
ZnGetColorByValue(Tk_Window	tkwin,
		  XColor	*color)
{
  ValueKey	value_key;
  Tcl_HashEntry	*value_hash;
  int		new;
  ZnColorInfo	*tk_col;
  Display	*dpy = Tk_Display(tkwin);
  Colormap	colormap = Tk_Colormap(tkwin);
  
  if (!initialized) {
    ColorInit();
  }
  
  /*printf("ZnGetColorByValue input color: %x %x %x\n",
    color->red, color->green, color->blue);*/ 
   /*
   * First, check to see if there's already a mapping for this color
   * name.
   */
  value_key.red = color->red;
  value_key.green = color->green;
  value_key.blue = color->blue;
  value_key.colormap = Tk_Colormap(tkwin);
  value_key.display = Tk_Display(tkwin);
  value_hash = Tcl_CreateHashEntry(&value_table, (char *) &value_key, &new);
  if (!new) {
    tk_col = (ZnColorInfo *) Tcl_GetHashValue(value_hash);
    tk_col->ref_count++;
    return &tk_col->color;
  }
  
  /*
   * The name isn't currently known.  Find a pixel value 
   * to use to draw that color in a given window.
   */
  tk_col = (ZnColorInfo *) ZnMalloc(sizeof(ZnColorInfo));
  tk_col->color.red = color->red;
  tk_col->color.green = color->green;
  tk_col->color.blue = color->blue;
  if (XAllocColor(dpy, colormap, &tk_col->color) != 0) {
    /*if (tk_col->color.red != color->red ||
	tk_col->color.green != color->green ||
	tk_col->color.blue != color->blue) {
      printf("couleur allouée approximative %d %d %d --> %d %d %d\n",
	     tk_col->color.red, tk_col->color.green, tk_col->color.blue,
	     color->red,  color->green, color->blue);
	     }*/
    DeleteStressedCmap(dpy, colormap);
  }
  else {
    /*printf("ZnGetColorByValue XAllocColor failed\n");*/
    FindClosestColor(tkwin, &tk_col->color, &tk_col->color);
  }
  
  tk_col->magic = COLOR_MAGIC;
  tk_col->screen = Tk_Screen(tkwin);
  tk_col->colormap = value_key.colormap;
  tk_col->visual  = Tk_Visual(tkwin);
  tk_col->ref_count = 1;
  tk_col->table = &value_table;
  tk_col->hash = value_hash;
  Tcl_SetHashValue(value_hash, tk_col);

  /*printf("ZnGetColorByValue created: %x %x %x\n",
    tk_col->color.red, tk_col->color.green, tk_col->color.blue);*/ 
  
  return &tk_col->color;
}


/*
 *--------------------------------------------------------------
 *
 * ZnNameOfColor --
 *
 *	Given a color, return a textual string identifying
 *	the color.
 *
 * Results:
 *	If colorPtr was created by Tk_GetColor, then the return
 *	value is the "string" that was used to create it.
 *	Otherwise the return value is a string that could have
 *	been passed to Tk_GetColor to allocate that color.  The
 *	storage for the returned string is only guaranteed to
 *	persist up until the next call to this procedure.
 *
 * Side effects:
 *	None.
 *
 *--------------------------------------------------------------
 */
char *
ZnNameOfColor(XColor	*color)
{
  register ZnColorInfo *tk_col = (ZnColorInfo *) color;
  static char	   string[20];
  
  if ((tk_col->magic == COLOR_MAGIC) && (tk_col->table == &name_table)) {
    return ((NameKey *) tk_col->hash->key.words)->name;
  }
  sprintf(string, "#%04x%04x%04x", color->red, color->green, color->blue);
  return string;
}


/*
 *----------------------------------------------------------------------
 *
 * ZnFreeColor --
 *
 *	This procedure is called to release a color allocated by
 *	ZnGetColor or ZnGetColorByValue.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	The reference count associated with colorPtr is deleted, and
 *	the color is released to X if there are no remaining uses
 *	for it.
 *
 *----------------------------------------------------------------------
 */
void
ZnFreeColor(XColor	*color)	/* Color to be released.  Must have been
				 * allocated by ZnGetColor or
				 * ZnGetColorByValue. */
{
  ZnColorInfo	*tk_col = (ZnColorInfo *) color;
  Visual	*visual;
  Screen	*screen = tk_col->screen;
  Tk_ErrorHandler handler;

  /*
   * Do a quick sanity check to make sure this color was really
   * allocated by ZnGetColor.
   */
  if (tk_col->magic != COLOR_MAGIC) {
    ZnWarning("ZnFreeColor called with bogus color\n");
    abort();
  }
  
  tk_col->ref_count--;
  if (tk_col->ref_count == 0) {
    /*printf("ZnFreeColor freeing %s\n", ZnNameOfColor(color));*/
    /*
     * Careful!  Don't free black or white, since this will
     * make some servers very unhappy.  Also, there is a bug in
     * some servers (such Sun's X11/NeWS server) where reference
     * counting is performed incorrectly, so that if a color is
     * allocated twice in different places and then freed twice,
     * the second free generates an error (this bug existed as of
     * 10/1/92).  To get around this problem, ignore errors that
     * occur during the free operation.
     */
    visual = tk_col->visual;
    if ((visual->class != StaticGray) && (visual->class != StaticColor) &&
	(tk_col->color.pixel != BlackPixelOfScreen(screen)) &&
	(tk_col->color.pixel != WhitePixelOfScreen(screen))) {
      handler = Tk_CreateErrorHandler(DisplayOfScreen(screen),
				      -1, -1, -1, (Tk_ErrorProc *) NULL,
				      (ClientData) NULL);
      XFreeColors(DisplayOfScreen(screen), tk_col->colormap,
		  &tk_col->color.pixel, 1, 0L);
      Tk_DeleteErrorHandler(handler);
    }
    DeleteStressedCmap(DisplayOfScreen(screen), tk_col->colormap);
    
    Tcl_DeleteHashEntry(tk_col->hash);
    tk_col->magic = 0;
    ZnFree(tk_col);
  }
}


/*
 *----------------------------------------------------------------------
 *
 * RgbToHsv
 * HsvToRgb --
 *
 *----------------------------------------------------------------------
 */
#if 0
static void
RgbToHsv(int	r,
	 int	g,
	 int	b,
	 ZnReal	*h,
	 ZnReal	*s,
	 ZnReal	*v)
{
  ZnReal	max, min, range, rc, gc, bc;

  max = (r > g) ? ((b > r) ? b : r) : ((b > g) ? b : g);
  min = (r < g) ? ((b < r) ? b : r) : ((b < g) ? b : g);
  range = max - min;
  if (max == 0) {
    *s = 0.0;
  }
  else {
    *s = range / max;
  }
  if (*s == 0) {
    *h = 0;
  }
  else {
    rc = (max - r) / range;
    gc = (max - g) / range;
    bc = (max - b) / range;
    *h = (max == r) ? (0.166667*(bc-gc)) : ((max == g) ? (0.166667*(2+rc-bc)) : (0.166667*(4+gc-rc)));
  }
  *v = max/65535.0;
}

static void
HsvToRgb(ZnReal	h,
	 ZnReal	s,
	 ZnReal	v,
	 unsigned short	*r,
	 unsigned short	*g,
	 unsigned short	*b)
{
  int		lv, i, p, q, t;
  ZnReal	f;

  lv = (int) (65535 * v);
  if (s == 0) {
    *r = *g = *b = lv;
    return;
  }
  h *= 6.0;
  if (h >= 6.0) {
    h = 0.0;
  }
  i = (int) h;
  f  = h - i;
  p = (int) (65535 * v * (1 - s));
  q = (int) (65535 * v * (1 - (s * f)));
  t = (int) (65535 * v * (1 - (s * (1 - f))));
  switch (i) {
  case 0:
    *r = lv;
    *g = t;
    *b = p;
    break;
  case 1:
    *r = q;
    *g = lv;
    *b = p;
    break;
  case 2:
    *r = p;
    *g = lv;
    *b = t;
    break;
  case 3:
    *r = p;
    *g = q;
    *b = lv;    
    break;
  case 4:
    *r = t;
    *g = p;
    *b = lv;    
    break;
  case 5:
    *r = lv;
    *g = p;
    *b = q;
    break;
  }
}
#endif

/*
 *----------------------------------------------------------------------
 *
 * ZnGetGradientColor --
 *
 *----------------------------------------------------------------------
 */
XColor *
ZnGetGradientColor(ZnGradient	*grad,
		   ZnReal	position,
		   int		*alpha)
{
  int			index, min, max;
  XColor		*shade=NULL;
  
  if ((grad->num_colors == 1) || (position <= 0.0)) {
    if (alpha) {
      *alpha = grad->colors[0].alpha;
    }
    return grad->colors[0].rgb;
  }
  if (position >= 100.0) {
    if (alpha) {
      *alpha = grad->colors[grad->num_colors-1].alpha;
    }
    shade = grad->colors[grad->num_colors-1].rgb;
  }
  else {
    min = 0;
    max = grad->num_colors-1;
    index = (max + min) / 2;
    while (max - min != 1) {
      /*printf("color index %d, min: %d, max: %d\n", index, min, max);*/
      if (grad->colors[index].position < position) {
	min = index;
      }
      else {
	max = index;
      }
      index = (max + min) / 2;
    }
    shade = grad->colors[index].rgb;
    if (alpha) {
      *alpha = grad->colors[index].alpha;
    }
  }

  return shade;
}


/*
 *--------------------------------------------------------------
 *
 * ZnGradientFlat --
 *
 *	Returns true if the gradient is defined by a single
 *	color.
 *
 *--------------------------------------------------------------
 */
ZnBool
ZnGradientFlat(ZnGradient	*grad)
{
  return (grad->num_colors == 1);
}


/*
 *--------------------------------------------------------------
 *
 * ZnGetReliefGradient --
 *
 *	Create a data structure containing a range of colors
 *	used to display a 3D border. Name contains the base
 *	color for the border. This is a slight variation on
 *	the syntax of a gradient that make life easier in this
 *	simple case.
 *
 * Results:
 *	The return value is a token for a data structure
 *	describing a gradient.  This token may be passed
 *	to the drawing routines.
 *	If an error prevented the gradient from being created
 *	then NULL is returned and an error message will be
 *	left in interp.
 *
 * Side effects:
 *	Data structures, etc. are allocated.
 *	It is the caller's responsibility to eventually call
 *	ZnFreeGradient to release the resources.
 *
 *--------------------------------------------------------------
 */
ZnGradient *
ZnGetReliefGradient(Tcl_Interp	*interp,
		    Tk_Window	tkwin,
		    Tk_Uid	name,
		    int		alpha)
{
  XColor	*base, light_color, dark_color, color;
  char		color_name[COLOR_NAME_SIZE];
  char		buffer[GRADIENT_NAME_SIZE];
  int		j, tmp1, tmp2;
  int		red_range, green_range, blue_range;
  
  base = ZnGetColor(interp, tkwin, name);
  /*
   * Compute the border gradient.
   *
   * Always consider that we are dealing with a color display with
   * enough colors available. If the colormap is full (stressed)
   * then just pray, the susbstitution algorithm may return something
   * adequate ;-).
   *
   * The extremum colors get computed using whichever formula results
   * in the greatest change in color:
   * 1. Lighter color is half-way to white, darker color is half
   *    way to dark.
   * 2. Lighter color is 40% brighter than base, darker color
   *    is 40% darker than base.
   * The first approach works better for unsaturated colors, the
   * second for saturated ones.
   *
   * NOTE: Colors are computed with integers not color shorts which
   * may lead to overflow errors.
   */
  tmp1 = (30 * (int) base->red)/100;
  tmp2 = ((int) base->red)/2;
  dark_color.red = MIN(tmp1, tmp2);
  tmp1 = (30 * (int) base->green)/100;
  tmp2 = ((int) base->green)/2;
  dark_color.green = MIN(tmp1, tmp2);
  tmp1 = (30 * (int) base->blue)/100;
  tmp2 = ((int) base->blue)/2;
  dark_color.blue = MIN(tmp1, tmp2);
  
  tmp1 = MAX_INTENSITY;/*(170 * (int) base->red)/10;*/
  if (tmp1 > MAX_INTENSITY) {
    tmp1 = MAX_INTENSITY;
  }
  tmp2 = (MAX_INTENSITY + (int) base->red)/2;
  light_color.red = MAX(tmp1, tmp2);
  tmp1 = MAX_INTENSITY;/*(170 * (int) base->green)/10;*/
  if (tmp1 > MAX_INTENSITY) {
    tmp1 = MAX_INTENSITY;
  }
  tmp2 = (MAX_INTENSITY + (int) base->green)/2;
  light_color.green = MAX(tmp1, tmp2);
  tmp1 = MAX_INTENSITY;/*(170 * (int) base->blue)/10;*/
  if (tmp1 > MAX_INTENSITY) {
    tmp1 = MAX_INTENSITY;
  }
  tmp2 = (MAX_INTENSITY + (int) base->blue)/2;
  light_color.blue = MAX(tmp1, tmp2);

  buffer[0] = 0;
  sprintf(color_name, "#%02x%02x%02x:%d|",
 	  dark_color.red/256, dark_color.green/256, dark_color.blue/256, alpha);
  red_range = (int) base->red - (int) dark_color.red;
  green_range = (int) base->green - (int) dark_color.green;
  blue_range = (int) base->blue - (int) dark_color.blue;
  strcat(buffer, color_name);
  for (j = 1; j < RELIEF_STEPS; j++) {
    color.red =(int) dark_color.red +  red_range * j/RELIEF_STEPS;
    color.green = (int) dark_color.green + green_range * j/RELIEF_STEPS;
    color.blue = (int) dark_color.blue + blue_range * j/RELIEF_STEPS;
    sprintf(color_name, "#%02x%02x%02x:%d %d|",
	    color.red/256, color.green/256, color.blue/256, alpha, 50/RELIEF_STEPS*j);
    strcat(buffer, color_name);
  }
  sprintf(color_name, "#%02x%02x%02x:%d 50|",
	  base->red/256, base->green/256, base->blue/256, alpha);
  strcat(buffer, color_name);
  red_range = (int) light_color.red - (int) base->red;
  green_range = (int) light_color.green - (int) base->green;
  blue_range = (int) light_color.blue - (int) base->blue;
  for (j = 1; j < RELIEF_STEPS; j++) {
    color.red = (int) base->red +  red_range * j/RELIEF_STEPS;
    color.green = (int) base->green + green_range * j/RELIEF_STEPS;
    color.blue = (int) base->blue + blue_range * j/RELIEF_STEPS;
    sprintf(color_name, "#%02x%02x%02x:%d %d|",
	    color.red/256, color.green/256, color.blue/256, alpha, 50+50/RELIEF_STEPS*j);
    strcat(buffer, color_name);
  }
  sprintf(color_name, "#%02x%02x%02x:%d",
	  light_color.red/256, light_color.green/256, light_color.blue/256, alpha);
  strcat(buffer, color_name);

  /*printf("gradient relief: %s \n", buffer);*/
  return ZnGetGradient(interp, tkwin, buffer);
}


/*
 *--------------------------------------------------------------
 *
 * ZnNameGradient
 * ZnDeleteGradientName --
 *
 *	Save a gradient under a name or suppress the gradient
 *	name binding. The save function returns false if the
 *	name is already in use.
 *
 *--------------------------------------------------------------
 */
ZnBool
ZnNameGradient(Tcl_Interp	*interp,
	       Tk_Window	tkwin,
	       char		*grad_descr,
	       char		*name)
{
  Tcl_HashEntry	*hash;
  int		new;
  ZnGradient	*grad;
  
  grad = ZnGetGradient(interp, tkwin, grad_descr);
  if (!grad) {
    return False;
  }
  
  hash = Tcl_CreateHashEntry(&gradient_table, Tk_GetUid(name), &new);
  if (!new) {
    return False;
  }
  else {
    Tcl_SetHashValue(hash, grad);
  }
  
  return True;
}

void
ZnDeleteGradientName(char	*name)
{
  Tcl_HashEntry	*hash;

  if (!initialized) {
    return;
  }
  
  hash = Tcl_FindHashEntry(&gradient_table, Tk_GetUid(name));
  if (hash) {
    Tcl_DeleteHashEntry(hash);
    ZnFreeGradient((ZnGradient *) Tcl_GetHashValue(hash));
  }
}

/*
 *--------------------------------------------------------------
 *
 * ZnGetGradient --
 *
 *	Create a data structure containing a range of colors
 *	used to display a gradient. 
 *
 * Results:
 *	The return value is a token for a data structure
 *	describing a gradient.  This token may be passed
 *	to the drawing routines.
 *	If an error prevented the gradient from being created
 *	then NULL is returned and an error message will be
 *	left in interp.
 *
 * Side effects:
 *	Data structures, etc. are allocated.
 *	It is the caller's responsibility to eventually call
 *	ZnFreeGradient to release the resources.
 *
 *--------------------------------------------------------------
 */
ZnGradient *
ZnGetGradientByValue(ZnGradient	*grad)
{
  grad->ref_count++;
  return grad;
}


ZnGradient *
ZnGetGradient(Tcl_Interp	*interp,
	      Tk_Window		tkwin,
	      Tk_Uid		name)
{
  Tcl_HashEntry	*hash;
  ZnGradient	*grad;
  int		i, j, new, num_colors;
  char		type, *scan_ptr;
  int		num_tok, angle, position, control;
  double	x, y;
  char		*color_ptr, color_name[COLOR_NAME_SIZE];
  char		buffer[GRADIENT_NAME_SIZE];
  ZnGradientColor *first, *last;
  XColor	color;
  int		red_range, green_range, blue_range;

  if (!name || !*name) {
    return NULL;
  }
  if (!initialized) {
    ColorInit();
  }
  
  /*
   * First, check to see if there's already a gradient that will work
   * for this request.
   */  
  name = Tk_GetUid(name);

  hash = Tcl_CreateHashEntry(&gradient_table, name, &new);
  if (!new) {
    grad = (ZnGradient *) Tcl_GetHashValue(hash);
    grad->ref_count++;
  }
  else {
    /*
     * No satisfactory gradient exists yet.  Initialize a new one.
     */
    if ((name[0] == '/') || (name[0] == '(') || (name[0] == '[')) {
      goto grad_err2;
    }

    strcpy(buffer, name);
    /*
     * Then look at the gradient type.
     */
    type = ZN_AXIAL_GRADIENT;
    angle = 0;
    if ((scan_ptr = strchr(buffer, '/'))) {
      num_tok = sscanf(scan_ptr, "/%d", &angle);
      if (num_tok != 1) {
      grad_err2:
	Tcl_DeleteHashEntry(hash);
	Tcl_AppendResult(interp, "incorrect gradient format \"",
			 name, "\",", NULL);
	return NULL;
      }
      *scan_ptr = '\0';
    }
    else if ((scan_ptr = strchr(buffer, '('))) {
      num_tok = sscanf(scan_ptr, "(%lf %lf", (double *) &x, (double *) &y);
      if (num_tok == 2) {
	type = ZN_RADIAL_GRADIENT;
      }
      else {
	goto grad_err2;
      }
      *scan_ptr = '\0';
    }
    else if ((scan_ptr = strchr(buffer, '['))) {
      num_tok = sscanf(scan_ptr, "[%lf %lf", (double *) &x, (double *) &y);
      if (num_tok == 2) {
	type = ZN_PATH_GRADIENT;
      }
      else {
	goto grad_err2;
      }
      *scan_ptr = '\0';
    }
    /*
     * Next count the colors.
     */
    scan_ptr = buffer;
    num_colors = 1;
    while ((scan_ptr = strchr(scan_ptr, '|'))) {
      num_colors++;
      scan_ptr++;
    }
    /*
     * Create the gradient structure.
     */
    grad = (ZnGradient *) ZnMalloc(sizeof(ZnGradient) +
				   sizeof(ZnGradientColor)*(num_colors-1));
    grad->ref_count = 1;
    grad->num_colors = num_colors;
    grad->type = type;
    if (type == ZN_AXIAL_GRADIENT) {
      grad->g.angle = angle;
    }
    else {
      grad->g.p.x = x;
      grad->g.p.y = y;
    }
    grad->hash = hash;
    Tcl_SetHashValue(hash, grad);

    scan_ptr = strtok(buffer, "|");
    for (i = 0; i < num_colors; i++) {
      grad->colors[i].position = 0;
      grad->colors[i].control = 50;
      grad->colors[i].alpha = 100;
      num_tok = sscanf(scan_ptr, "%s %d %d", color_name, &position, &control);
      if (num_tok > 1) {
	grad->colors[i].position = position;
      }
      if (num_tok > 2) {
	grad->colors[i].control = control;
      }
      if (num_tok == 0) {
	Tcl_AppendResult(interp, "incorrect gradient format \"",
			 name, "\",", NULL);
      grad_err:
	Tcl_DeleteHashEntry(hash);
	for (j = 0; j < i; j++) {
	  ZnFreeColor(grad->colors[j].rgb);
	}
	ZnFree(grad);
	return NULL;
      }
      color_ptr = strchr(color_name, ':');
      if (color_ptr) {
	*color_ptr = 0;
      }
      grad->colors[i].rgb = ZnGetColor(interp, tkwin, Tk_GetUid(color_name));
      if (color_ptr) {
	*color_ptr = ':';
      }
      if (grad->colors[i].rgb == NULL) {
	Tcl_AppendResult(interp, " in gradient,", NULL);
	goto grad_err;
      }
      if (color_ptr) {
	grad->colors[i].alpha = atoi(color_ptr+1);
      }
      if (i == 0) {
	grad->colors[i].position = 0;
      }
      else if (i == num_colors - 1) {
	grad->colors[i].position = 100;
      }
      if ((num_tok > 2) && (i > 0)) {
	if ((grad->colors[i].position > 100) ||
	    (grad->colors[i].position < grad->colors[i-1].position)) {
	  Tcl_AppendResult(interp, "incorrect color position in gradient \"",
			   name, "\",", NULL);
	  goto grad_err;
	}
      }
      if (grad->colors[i].control > 100) {
	grad->colors[i].control = 100;
      }
      if (grad->colors[i].alpha > 100) {
	grad->colors[i].alpha = 100;
      }
      scan_ptr = strtok(NULL, "|");
    }
  }

  /*
   * Compute the mid alpha and mid color values. These will be
   * used by the gradient rendering primitives when a control
   * is not at mid range. The last color has no mid_* values.
   */
  for (i = 0; i < grad->num_colors-1; i++) {
    first = &grad->colors[i];
    last = &grad->colors[i+1];
    red_range = (int) last->rgb->red - (int) first->rgb->red;
    green_range = (int) last->rgb->green - (int) first->rgb->green;
    blue_range = (int) last->rgb->blue - (int) first->rgb->blue;
    color.red =(int) first->rgb->red +  red_range/2;
    color.green = (int) first->rgb->green + green_range/2;
    color.blue = (int) first->rgb->blue + blue_range/2;
    first->mid_rgb = ZnGetColorByValue(tkwin, &color);
    first->mid_alpha = first->alpha + (last->alpha-first->alpha)/2;
  }
  grad->colors[grad->num_colors-1].mid_rgb = NULL;

  return grad;
}


/*
 *--------------------------------------------------------------
 *
 * ZnNameOfGradient --
 *
 *	Given a gradient, return a textual string identifying
 *	the gradient.
 *
 * Results:
 *	The return value is the string that was used to create
 *	the gradient.
 *
 * Side effects:
 *	None.
 *
 *--------------------------------------------------------------
 */
char *
ZnNameOfGradient(ZnGradient	*grad)
{
  return (char *) grad->hash->key.words;
}


/*
 *--------------------------------------------------------------
 *
 * ZnFreeGradient --
 *
 *	This procedure is called when a gradient is no longer
 *	needed.  It frees the resources associated with the
 *	gradient.  After this call, the caller should never
 *	again use the gradient.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	Resources are freed.
 *
 *--------------------------------------------------------------
 */
void
ZnFreeGradient(ZnGradient	*grad)
{
  int	i;
  
  grad->ref_count--;
  if (grad->ref_count == 0) {
    Tcl_DeleteHashEntry(grad->hash);
    for (i = 0; i < grad->num_colors; i++) {
      ZnFreeColor(grad->colors[i].rgb);
      if (grad->colors[i].mid_rgb) {
	ZnFreeColor(grad->colors[i].mid_rgb);
      }
    }
    ZnFree(grad);
  }
}


/*
 *--------------------------------------------------------------
 *
 * ZnComposeAlpha --
 *
 *	This procedure takes two alpha values in percent and
 *	returns the composite value between 0 and 65535.
 *
 *--------------------------------------------------------------
 */
int
ZnComposeAlpha(int	alpha1,
	      int	alpha2)
{
  return (alpha1*alpha2/100)*65535/100;
}