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 "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 128
/*
 * Maximum size of a gradient name including the \0.
 */
#define GRADIENT_NAME_SIZE 512

/*
 * 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;

typedef struct {
    Tk_Uid	name;		/* Gradient spec. */
    Colormap	colormap;	/* Colormap used for allocating gradient
				 * colors. */
    Screen	*screen;	/* Screen on which gradient will be drawn. */
} GradientKey;


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");
	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");
      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, sizeof(GradientKey)/sizeof(int));
}


/*
 *----------------------------------------------------------------------
 *
 * 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");
    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(Tk_Window	tkwin,
		   ZnGradient	*grad,
		   ZnReal	position,
		   int		*alpha)
{
  int			index, min, max;
  ZnGradientColor	*color, *next_color;
  XColor		*shade=NULL;
  ZnReal		tt;
  
  if ((grad->num_colors == 1) || (position < 0.0)) {
    if (alpha) {
      *alpha = grad->colors[0]->alpha;
    }
    return grad->colors[0]->shades[0];
  }
  if (position >= 100.0) {
    if (alpha) {
      *alpha = grad->colors[grad->num_colors-1]->alpha;
    }
    shade = grad->colors[grad->num_colors-1]->shades[0];
  }
  else {
    min = 0;
    max = grad->num_colors-1;
    index = (max + min) / 2;
    while (max - min != 1) {
      if (grad->colors[index]->position < position) {
	min = index;
      }
      else {
	max = index;
      }
      index = (max + min) / 2;
    }
    /*printf("color index %d ", index);*/
    color = grad->colors[index];
    next_color = grad->colors[index+1];
    tt = (grad->num_shades * (position - (ZnReal) color->position) /
	  (ZnReal) (next_color->position - color->position));
    index = (int) tt;
    /*printf("shade index %d %g\n", index, tt);*/
    shade = color->shades[index];
    if (alpha) {
      *alpha = ((next_color->alpha-color->alpha) * (position - (ZnReal) color->position) /
		(ZnReal) (next_color->position - color->position));
    }
  }

  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. This function allocate
 *	the base color and the two end colors in an attempt
 *	to use only actually needed resources. The function
 *	ZnGetGradientColor asserts that all the colors
 *	get allocated when needed.
 *	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)
{
  XColor	*base, light_color, dark_color;
  char		color_name[COLOR_NAME_SIZE];
  int		tmp1, tmp2;
  
  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);

  sprintf(color_name, "#%02x%02x%02x|#%02x%02x%02x 50|#%02x%02x%02x%%%d",
	  dark_color.red/256, dark_color.green/256, dark_color.blue/256,
	  base->red/256, base->green/256, base->blue/256,
	  light_color.red/256, light_color.green/256, light_color.blue/256,
	  RELIEF_STEPS);

  return ZnGetGradient(interp, tkwin, color_name);
}


/*
 *----------------------------------------------------------------------
 *
 * RealizeGradient --
 *
 *	This procedure allocate the shades still unallocated in
 *	a gradient. The milestone  colors are always allocated
 *	during the gradient's creation.
 *
 *----------------------------------------------------------------------
 */
static void
RealizeGradient(ZnGradient	*grad,
		Tk_Window	tkwin)
{
  int			i, j, num_colors, num_shades;
  int			red_range, green_range, blue_range;
  ZnGradientColor	*first, *last;
  XColor		color;
  
  /*printf("realizing gradient with %d(%d) colors\n",
    grad->num_colors, BORDER_STEPS);*/
  num_colors = grad->num_colors;
  num_shades = grad->num_shades;
  for (i = 0; i < grad->num_colors-1; i++) {
    first = grad->colors[i];
    last = grad->colors[i+1];
    /*printf("first color :  %d %d %d, last color : %d %d %d\n",
	   first->shades[0]->red, first->shades[0]->green, first->shades[0]->blue,
	   last->shades[0]->red, last->shades[0]->green, last->shades[0]->blue);*/
    red_range = (int) last->shades[0]->red - (int) first->shades[0]->red;
    green_range = (int) last->shades[0]->green - (int) first->shades[0]->green;
    blue_range = (int) last->shades[0]->blue - (int) first->shades[0]->blue;
    for (j = 1; j < num_shades; j++) {
      color.red =(int) first->shades[0]->red +  red_range * j/num_shades;
      color.green = (int) first->shades[0]->green + green_range * j/num_shades;
      color.blue = (int) first->shades[0]->blue + blue_range * j/num_shades;
      first->shades[j] = ZnGetColorByValue(tkwin, &color);
    }
  }
}


/*
 *--------------------------------------------------------------
 *
 * 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.  This function allocate
 *	the milestone colors in an attempt to use only
 *	actually needed resources. The function
 *	ZnGetGradientColor asserts that all the colors
 *	get allocated when needed.
 *	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)
{
  GradientKey	key;
  Tcl_HashEntry	*hash;
  ZnGradient	*grad;
  int		i, j, new, num_colors, num_shades;
  char		type, *scan_ptr;
  int		num_tok, angle;
  double	x, y;
  char		*color_ptr, color_name[COLOR_NAME_SIZE];
  char		buffer[GRADIENT_NAME_SIZE];
  
  if (!initialized) {
    ColorInit();
  }
  
  /*
   * First, check to see if there's already a gradient that will work
   * for this request.
   */  
  name = Tk_GetUid(name);
  key.name = name;
  key.colormap = Tk_Colormap(tkwin);
  key.screen = Tk_Screen(tkwin);
  
  hash = Tcl_CreateHashEntry(&gradient_table, (char *) &key, &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);
    /*
     * Try to obtain how many shades sould be drawn.
     */
    num_shades = 2; /* Minimum needed to have the start and mid range color */
    if ((scan_ptr = strchr(buffer, '%'))) {
      sscanf(scan_ptr, "%%%d", &num_shades);
      /*printf("num shades = %d\n", num_shades);*/
      *scan_ptr = '\0';
    }
    if (num_shades < 2) {
      num_shades = 2;
    }
    else {
      /*
       * Keep num_shades even.
       */
      num_shades /= 2;
      num_shades *= 2;
    }
    /*
     * 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';
    }
    /*
     * 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_shades = num_shades;
    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++) {
      if (i != num_colors - 1) {
	grad->colors[i] = (ZnGradientColor *) ZnMalloc(sizeof(ZnGradientColor) +
						       sizeof(XColor *)*(num_shades-1));
      }
      else {
	grad->colors[i] = (ZnGradientColor *) ZnMalloc(sizeof(ZnGradientColor));
      }
      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,
		       &grad->colors[i]->position,
		       &grad->colors[i]->control);
      if (num_tok == 0) {
	Tcl_AppendResult(interp, "incorrect gradient format \"",
			 name, "\",", NULL);
      grad_err:
	Tcl_DeleteHashEntry(hash);
	for (j = i; j >= 0; j--) {
	  ZnFree(grad->colors[j]);
	}
	ZnFree(grad);
	return NULL;
      }
      color_ptr = strchr(color_name, ':');
      if (color_ptr) {
	*color_ptr = 0;
      }
      grad->colors[i]->shades[0] = ZnGetColor(interp, tkwin, Tk_GetUid(color_name));
      if (color_ptr) {
	*color_ptr = ':';
      }
      if (grad->colors[i]->shades[0] == NULL) {
	Tcl_AppendResult(interp, " in gradient,", NULL);
	goto grad_err;
      }
      if (color_ptr) {
	grad->colors[i]->alpha = atoi(color_ptr+1);
      }
      if (i != num_colors - 1) {
	for (j = 1; j < num_shades-1; j++) {
	  grad->colors[i]->shades[j] = NULL;
	}
      }
      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 < 0) ||
	    (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 < 0) {
	grad->colors[i]->control = 0;
      }
      if (grad->colors[i]->control > 100) {
	grad->colors[i]->control = 100;
      }
      if (grad->colors[i]->alpha < 0) {
	grad->colors[i]->alpha = 0;
      }
      if (grad->colors[i]->alpha > 100) {
	grad->colors[i]->alpha = 100;
      }
      scan_ptr = strtok(NULL, "|");
    }
  }
  
  RealizeGradient(grad, tkwin);

  return grad;
}


/*
 *--------------------------------------------------------------
 *
 * ZnNameOfColorGradient --
 *
 *	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 ((GradientKey *) grad->hash->key.words)->name;
}


/*
 *--------------------------------------------------------------
 *
 * 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, j;
  
  grad->ref_count--;
  if (grad->ref_count == 0) {
    Tcl_DeleteHashEntry(grad->hash);
    for (i = 0; i < grad->num_colors-1; i++) {
      for (j = 0; j < grad->num_shades; j++) {
	if (grad->colors[i]->shades[j] != NULL) {
	  ZnFreeColor(grad->colors[i]->shades[j]);
	}
      }
      ZnFree(grad->colors[i]);
    }
    ZnFreeColor(grad->colors[grad->num_colors-1]->shades[0]);
    ZnFree(grad->colors[grad->num_colors-1]);
    ZnFree(grad);
  }
}