Initial commit

1 files changed, 797 insertions, 0 deletions

diff --git a/vendor/x11iraf/ximtool/quant.c b/vendor/x11iraf/ximtool/quant.c
new file mode 100644
index 00000000..34514a50
--- /dev/null
+++ b/vendor/x11iraf/ximtool/quant.c
@@ -0,0 +1,797 @@
+#include <stdio.h>
+
+/* QUANT.C -- Quantize the colors in a pixmap down to a specified number.
+** This code is largely stolen from PBMPlus by Jef Poskanzer.
+**
+** ORIGINAL COPYRIGHT NOTICE:
+**
+** Copyright (C) 1989, 1991 by Jef Poskanzer.
+**
+** Permission to use, copy, modify, and distribute this software and its
+** documentation for any purpose and without fee is hereby granted, provided
+** that the above copyright notice appear in all copies and that both that
+** copyright notice and this permission notice appear in supporting
+** documentation.  This software is provided "as is" without express or
+** implied warranty.
+*/
+
+#undef max
+#define max(a,b) ((a) > (b) ? (a) : (b))
+#undef min
+#define min(a,b) ((a) < (b) ? (a) : (b))
+#undef abs
+#define abs(a) ((a) >= 0 ? (a) : -(a))
+#undef odd
+#define odd(n) ((n) & 1)
+
+#ifdef HPUX 
+#define random()	rand()
+#define srandom(x)	srand(x)
+#endif
+
+typedef unsigned char byte;
+typedef unsigned char pixval;
+
+#define PPM_MAXMAXVAL 255
+typedef struct { pixval r, g, b; } pixel;
+
+#define PPM_GETR(p) ((p).r)
+#define PPM_GETG(p) ((p).g)
+#define PPM_GETB(p) ((p).b)
+
+#define PPM_ASSIGN(p,red,grn,blu) \
+  { (p).r = (red); (p).g = (grn); (p).b = (blu); }
+
+#define PPM_EQUAL(p,q) ( (p).r == (q).r && (p).g == (q).g && (p).b == (q).b )
+
+/* Color scaling macro -- to make writing ppmtowhatever easier. */
+#define PPM_DEPTH(newp,p,oldmaxval,newmaxval) \
+    PPM_ASSIGN( (newp), \
+                (int) PPM_GETR(p) * (newmaxval) / (oldmaxval), \
+                (int) PPM_GETG(p) * (newmaxval) / (oldmaxval), \
+                (int) PPM_GETB(p) * (newmaxval) / (oldmaxval) )
+
+/* Luminance macro, using only integer ops.  Returns an int (*256)  JHB */
+#define PPM_LUMIN(p) \
+  ( 77 * PPM_GETR(p) + 150 * PPM_GETG(p) + 29 * PPM_GETB(p) )
+
+
+/* Color histogram stuff. */
+typedef struct colorhist_item *colorhist_vector;
+struct colorhist_item {
+	pixel color;
+	int	value;
+};
+
+typedef struct colorhist_list_item *colorhist_list;
+struct colorhist_list_item {
+	struct colorhist_item ch;
+	colorhist_list next;
+};
+
+
+/* Color hash table stuff. */
+
+typedef colorhist_list	*colorhash_table;
+
+#define MAXCOLORS 	32767
+#define FS_SCALE 	1024
+#define HASH_SIZE 20023
+
+#define LARGE_LUM
+#define REP_AVERAGE_PIXELS
+
+#define hashPixel(p)  ((((int) PPM_GETR(p) * 33023 +    \
+                            (int) PPM_GETG(p) * 30013 +    \
+                            (int) PPM_GETB(p) * 27011) & 0x7fffffff)   \
+                          % HASH_SIZE)
+
+
+typedef struct box *box_vector;
+struct box {
+	int	ind;
+	int	colors;
+	int	sum;
+};
+
+static colorhist_vector medianCut (),  colorHashToColorHist ();
+static colorhist_vector computeColorHist ();
+static colorhash_table  computeColorHash (), colorHistToColorHash ();
+static colorhash_table  allocColorHash ();
+static int 		redCompare(), greenCompare(), blueCompare();
+static int 		lookupColor (), addToColorHash (), sumCompare();
+static void 		freeColorHash (), addToColorHist(),freeColorHist();
+
+
+
+/* PPMQUANT --  Quantize an image with a given colormap to a new number of
+ * colors, modifies the image in place.  Floyd-Steinberg dithering isn't
+ * current enabled because of speed but can be turned on later.  Modified
+ * from the original code in the PBMplus package by Jef Poskanzer.
+ */
+
+int
+ppmquant (image, r, g, b, nx, ny, ncolors, newcolors)
+byte 	*image;				/* image pixels (i.e. cmap indices) */
+byte	*r, *g, *b;			/* colormap			    */
+int  	nx, ny;				/* image dimensions                 */
+int	ncolors;			/* current number of colors         */
+int	newcolors;			/* requested number of colors       */
+{
+	register pixel *pP;
+	register long	sr, sg, sb, err;
+	register int	i, col, limitcol, index = 0;
+	byte	 *pix = image;
+	pixel    **pixels;
+	pixval   maxval = 255, newmaxval;
+	int	 rows, cols, row;
+	int	 colors;
+	int	 floyd = 0, usehash;
+	colorhist_vector chv, colormap;
+	colorhash_table cht;
+	long	*thisrerr, *thisgerr, *thisberr;
+	long	*nextrerr, *nextgerr, *nextberr, *temperr;
+	int	fs_direction;
+
+  	/* Reformat into 2-dimensional array of pixel structures */
+	rows = ny;
+	cols = nx;
+  	pixels = (pixel **) malloc (rows * sizeof(pixel *));
+  	if (!pixels) 
+	    return;
+
+  	for (row=0; row<rows; row++) {
+    	    pixels[row] = (pixel *) malloc(cols * sizeof(pixel));
+    	    if (!pixels[row])
+		return;
+
+    	    for (col=0, pP=pixels[row]; col<cols; col++, pP++) {
+      	        pP->r = (pixval) r[*pix];
+      	        pP->g = (pixval) g[*pix];
+      	        pP->b = (pixval) b[*pix];
+		pix++;
+    	    }
+  	}
+
+
+	/* Step 2: attempt to make a histogram of the colors, unclustered.
+	** If at first we don't succeed, lower maxval to increase color
+	** coherence and try again.  This will eventually terminate, with
+	** maxval at worst 15, since 32^3 is approximately MAXCOLORS.
+	*/
+	for  (; ;)  {
+	    chv = computeColorHist(pixels, cols, rows, MAXCOLORS, &colors) ;
+	    if  (chv != (colorhist_vector) 0) 
+	        break;
+	    newmaxval = maxval / 2;
+	    for  (row = 0; row < rows; ++row) 
+	        for  (col = 0, pP = pixels[row]; col < cols; ++col, ++pP) 
+	            PPM_DEPTH (*pP, *pP, maxval, newmaxval) ;
+	    maxval = newmaxval;
+	}
+
+	/* Step 3: apply median-cut to histogram, making the new colormap.
+	*/
+	colormap = medianCut (chv, colors, rows * cols, maxval, newcolors) ;
+	freeColorHist (chv) ;
+
+	/* Step 4: map the colors in the image to their closest match in the
+    	** new colormap, and write 'em out.
+    	*/
+	cht = allocColorHash ();
+	usehash = 1;
+	pix = image;
+	if  (floyd)  {
+	    /* Initialize Floyd-Steinberg error vectors. */
+	    thisrerr = (long *) calloc (cols + 2, sizeof(long) );
+	    nextrerr = (long *) calloc (cols + 2, sizeof(long) );
+	    thisgerr = (long *) calloc (cols + 2, sizeof(long) );
+	    nextgerr = (long *) calloc (cols + 2, sizeof(long) );
+	    thisberr = (long *) calloc (cols + 2, sizeof(long) );
+	    nextberr = (long *) calloc (cols + 2, sizeof(long) );
+	    srandom ((int)  (time (0)  ^ getpid ()) ) ;
+	    for  (col = 0; col < cols + 2; ++col)  {
+	    	thisrerr[col] = random () % (FS_SCALE * 2)  - FS_SCALE;
+	    	thisgerr[col] = random () % (FS_SCALE * 2)  - FS_SCALE;
+	    	thisberr[col] = random () % (FS_SCALE * 2)  - FS_SCALE;
+	    	/* (random errors in [-1 .. 1]) */
+	    }
+	    fs_direction = 1;
+	}
+	for  (row = 0; row < rows; ++row)  {
+	    if  (floyd) 
+	    	for  (col = 0; col < cols + 2; ++col) 
+	    	    nextrerr[col] = nextgerr[col] = nextberr[col] = 0;
+	    if  ( (!floyd)  || fs_direction)  {
+	    	col = 0;
+	    	limitcol = cols;
+	    	pP = pixels[row];
+	    } else {
+	    	col = cols - 1;
+	    	limitcol = -1;
+	    	pP = &(pixels[row][col]);
+	    }
+	    do {
+	    	if  (floyd)  {
+	    	    /* Use Floyd-Steinberg errors to adjust actual color. */
+	    	    sr = PPM_GETR(*pP) + thisrerr[col + 1] / FS_SCALE;
+	    	    sg = PPM_GETG(*pP) + thisgerr[col + 1] / FS_SCALE;
+	    	    sb = PPM_GETB(*pP) + thisberr[col + 1] / FS_SCALE;
+	    	    if  (sr < 0) 
+	    	    	sr = 0;
+	    	    else if  (sr > maxval) 
+	    	    	sr = maxval;
+	    	    if  (sg < 0) 
+	    	    	sg = 0;
+	    	    else if  (sg > maxval) 
+	    	    	sg = maxval;
+	    	    if  (sb < 0) 
+	    	    	sb = 0;
+	    	    else if  (sb > maxval) 
+	    	    	sb = maxval;
+	    	    PPM_ASSIGN (*pP, sr, sg, sb) ;
+	    	}
+
+	    	/* Check hash table to see if we have already matched this
+		 * color. 
+		 */
+	    	index = lookupColor (cht, pP) ;
+	    	if  (index == -1) { /* No; search colormap for closest match. */
+	    	    register int	i, r1, g1, b1, r2, g2, b2;
+	    	    register long	dist, newdist;
+	    	    r1 = PPM_GETR (*pP) ;
+	    	    g1 = PPM_GETG (*pP) ;
+	    	    b1 = PPM_GETB (*pP) ;
+	    	    dist = 2000000000;
+	    	    for  (i = 0; i < newcolors; ++i)  {
+	    	    	r2 = PPM_GETR (colormap[i].color) ;
+	    	    	g2 = PPM_GETG (colormap[i].color) ;
+	    	    	b2 = PPM_GETB (colormap[i].color) ;
+	    	    	newdist =  (r1 - r2)  *  (r1 - r2)  + 
+	    	    	     (g1 - g2)  *  (g1 - g2)  + 
+	    	    	     (b1 - b2)  *  (b1 - b2) ;
+	    	    	if  (newdist < dist)  {
+	    	    	    index = i;
+	    	    	    dist = newdist;
+	    	    	}
+	    	    }
+	    	    if  (usehash)  {
+	    	    	if  (addToColorHash (cht, pP, index)  < 0)  {
+	    	    	    usehash = 0;
+	    	    	}
+	    	    }
+	    	}
+
+	    	if  (floyd)  {
+	    	    /* Propagate Floyd-Steinberg error terms. */
+	    	    if  (fs_direction)  {
+	    	    	err =  (sr - (long) PPM_GETR (colormap[index].color)) * FS_SCALE;
+	    	    	thisrerr[col + 2] +=  (err * 7)  / 16;
+	    	    	nextrerr[col    ] +=  (err * 3)  / 16;
+	    	    	nextrerr[col + 1] +=  (err * 5)  / 16;
+	    	    	nextrerr[col + 2] +=  (err    )  / 16;
+	    	    	err =  (sg - (long) PPM_GETG (colormap[index].color)) * FS_SCALE;
+	    	    	thisgerr[col + 2] +=  (err * 7)  / 16;
+	    	    	nextgerr[col    ] +=  (err * 3)  / 16;
+	    	    	nextgerr[col + 1] +=  (err * 5)  / 16;
+	    	    	nextgerr[col + 2] +=  (err    )  / 16;
+	    	    	err =  (sb - (long) PPM_GETB (colormap[index].color)) * FS_SCALE;
+	    	    	thisberr[col + 2] +=  (err * 7)  / 16;
+	    	    	nextberr[col    ] +=  (err * 3)  / 16;
+	    	    	nextberr[col + 1] +=  (err * 5)  / 16;
+	    	    	nextberr[col + 2] +=  (err    )  / 16;
+	    	    } else {
+
+	    	    	err =  (sr - (long) PPM_GETR (colormap[index].color)) * FS_SCALE;
+	    	    	thisrerr[col    ] +=  (err * 7)  / 16;
+	    	    	nextrerr[col + 2] +=  (err * 3)  / 16;
+	    	    	nextrerr[col + 1] +=  (err * 5)  / 16;
+	    	    	nextrerr[col    ] +=  (err    )  / 16;
+	    	    	err =  (sg - (long) PPM_GETG (colormap[index].color)) * FS_SCALE;
+	    	    	thisgerr[col    ] +=  (err * 7)  / 16;
+	    	    	nextgerr[col + 2] +=  (err * 3)  / 16;
+	    	    	nextgerr[col + 1] +=  (err * 5)  / 16;
+	    	    	nextgerr[col    ] +=  (err    )  / 16;
+	    	    	err =  (sb - (long) PPM_GETB (colormap[index].color)) * FS_SCALE;
+	    	    	thisberr[col    ] +=  (err * 7)  / 16;
+	    	    	nextberr[col + 2] +=  (err * 3)  / 16;
+	    	    	nextberr[col + 1] +=  (err * 5)  / 16;
+	    	    	nextberr[col    ] +=  (err    )  / 16;
+	    	    }
+	    	}
+
+	    	*pP = colormap[index].color;
+		*pix++ = index;			  /* save the new image index */
+
+	    	if  ( (!floyd)  || fs_direction)  {
+	    	    ++col;
+	    	    ++pP;
+	    	} else {
+	    	    --col;
+	    	    --pP;
+	    	}
+	    } while  (col != limitcol) ;
+
+	    if  (floyd)  {
+	    	temperr = thisrerr;
+	    	thisrerr = nextrerr;
+	    	nextrerr = temperr;
+	    	temperr = thisgerr;
+	    	thisgerr = nextgerr;
+	    	nextgerr = temperr;
+	    	temperr = thisberr;
+	    	thisberr = nextberr;
+	    	nextberr = temperr;
+	    	fs_direction = !fs_direction;
+	    }
+
+	}
+
+  	/* Rescale and load the new colormap. */
+  	for (i=0; i<newcolors; i++) {
+    	    PPM_DEPTH(colormap[i].color, colormap[i].color, maxval, 255);
+    	    r[i] = PPM_GETR (colormap[i].color);
+    	    g[i] = PPM_GETG (colormap[i].color);
+    	    b[i] = PPM_GETB (colormap[i].color);
+  	}
+
+  	/* Free the pixels array. */
+  	for (i=0; i<rows; i++) free (pixels[i]);
+  	free (pixels);
+
+  	/* Free cht and colormap. */
+  	freeColorHist (colormap);
+  	freeColorHash (cht);
+
+	return (0) ;
+}
+
+
+/*
+** Here is the fun part, the median-cut colormap generator.  This is based
+** on Paul Heckbert's paper "Color Image Quantization for Frame Buffer
+** Display", SIGGRAPH '82 Proceedings, page 297.
+*/
+
+static colorhist_vector
+medianCut (chv, colors, sum, maxval, newcolors) 
+colorhist_vector chv;
+int	colors, sum, newcolors;
+pixval maxval;
+{
+	colorhist_vector colormap;
+	box_vector bv;
+	register int	bi, i;
+	int	boxes;
+
+	bv = (box_vector) malloc (sizeof(struct box)  * newcolors) ;
+	colormap = 
+	    (colorhist_vector) malloc (sizeof(struct colorhist_item)  * newcolors) ;
+	if  (bv == (box_vector) 0 || colormap == (colorhist_vector) 0) 
+	    perror ("out of memory") ;
+	for  (i = 0; i < newcolors; ++i) 
+	    PPM_ASSIGN (colormap[i].color, 0, 0, 0) ;
+
+	/*
+    	** Set up the initial box.
+    	*/
+	bv[0].ind = 0;
+	bv[0].colors = colors;
+	bv[0].sum = sum;
+	boxes = 1;
+
+	/*
+    	** Main loop: split boxes until we have enough.
+    	*/
+	while  (boxes < newcolors)  {
+	    register int	indx, clrs;
+	    int	sm;
+	    register int	minr, maxr, ming, maxg, minb, maxb, v;
+	    int	halfsum, lowersum;
+
+	    /*
+	    ** Find the first splittable box.
+	    */
+	    for  (bi = 0; bi < boxes; ++bi) 
+	    	if  (bv[bi].colors >= 2) 
+	    	    break;
+	    if  (bi == boxes) 
+	    	break;	/* ran out of colors! */
+	    indx = bv[bi].ind;
+	    clrs = bv[bi].colors;
+	    sm = bv[bi].sum;
+
+	    /*
+	    ** Go through the box finding the minimum and maximum of each
+	    ** component - the boundaries of the box.
+	    */
+	    minr = maxr = PPM_GETR (chv[indx].color) ;
+	    ming = maxg = PPM_GETG (chv[indx].color) ;
+	    minb = maxb = PPM_GETB (chv[indx].color) ;
+	    for  (i = 1; i < clrs; ++i)  {
+	    	v = PPM_GETR (chv[indx + i].color) ;
+	    	if  (v < minr) 
+	    	    minr = v;
+	    	if  (v > maxr) 
+	    	    maxr = v;
+	    	v = PPM_GETG (chv[indx + i].color) ;
+	    	if  (v < ming) 
+	    	    ming = v;
+	    	if  (v > maxg) 
+	    	    maxg = v;
+	    	v = PPM_GETB (chv[indx + i].color) ;
+	    	if  (v < minb) 
+	    	    minb = v;
+	    	if  (v > maxb) 
+	    	    maxb = v;
+	    }
+
+	    /*
+	    ** Find the largest dimension, and sort by that component.  I have
+	    ** included two methods for determining the "largest" dimension;
+	    ** first by simply comparing the range in RGB space, and second
+	    ** by transforming into luminosities before the comparison.  You
+	    ** can switch which method is used by switching the commenting on
+	    ** the LARGE_ defines at the beginning of this source file.
+	    */
+	     {
+      		/* LARGE_LUM version */
+
+	    	pixel p;
+	    	float	rl, gl, bl;
+
+	    	PPM_ASSIGN(p, maxr - minr, 0, 0);
+	    	rl = PPM_LUMIN(p);
+	    	PPM_ASSIGN(p, 0, maxg - ming, 0);
+	    	gl = PPM_LUMIN(p);
+	    	PPM_ASSIGN(p, 0, 0, maxb - minb);
+	    	bl = PPM_LUMIN(p);
+
+	    	if  (rl >= gl && rl >= bl) 
+	    	    qsort(
+	    	        (char *)&(chv[indx]),clrs,sizeof(struct colorhist_item),
+	    	        redCompare) ;
+	    	else if  (gl >= bl) 
+	    	    qsort(
+	    	        (char *)&(chv[indx]),clrs,sizeof(struct colorhist_item),
+	    	        greenCompare) ;
+	    	else
+	    	    qsort(
+	    	        (char *)&(chv[indx]),clrs,sizeof(struct colorhist_item),
+	    	        blueCompare) ;
+	    }
+
+	    /*
+	    ** Now find the median based on the counts, so that about half the
+	    ** pixels (not colors, pixels) are in each subdivision.
+	    */
+	    lowersum = chv[indx].value;
+	    halfsum = sm / 2;
+	    for  (i = 1; i < clrs - 1; ++i)  {
+	    	if  (lowersum >= halfsum) 
+	    	    break;
+	    	lowersum += chv[indx + i].value;
+	    }
+
+	    /*
+	    ** Split the box, and sort to bring the biggest boxes to the top.
+	    */
+	    bv[bi].colors = i;
+	    bv[bi].sum = lowersum;
+	    bv[boxes].ind = indx + i;
+	    bv[boxes].colors = clrs - i;
+	    bv[boxes].sum = sm - lowersum;
+	    ++boxes;
+	    qsort ((char *) bv, boxes, sizeof(struct box) , sumCompare) ;
+	}
+
+	/*
+        ** Ok, we've got enough boxes.  Now choose a representative color for
+        ** each box.  There are a number of possible ways to make this choice.
+        ** One would be to choose the center of the box; this ignores any
+        ** structure within the boxes.  Another method would be to average all
+	** the colors in the box - this is the method specified in Heckbert's
+	** paper.  A third method is to average all the pixels in the box. You
+	** can switch which method is used by switching the commenting on the
+	** REP_ defines at the beginning of this source file.
+        */
+	for  (bi = 0; bi < boxes; ++bi)  {
+    	    /* REP_AVERAGE_PIXELS version */
+
+	    register int	indx = bv[bi].ind;
+	    register int	clrs = bv[bi].colors;
+	    register long	r = 0, g = 0, b = 0, sum = 0;
+
+	    for  (i = 0; i < clrs; ++i)  {
+	    	r += PPM_GETR (chv[indx + i].color)  * chv[indx + i].value;
+	    	g += PPM_GETG (chv[indx + i].color)  * chv[indx + i].value;
+	    	b += PPM_GETB (chv[indx + i].color)  * chv[indx + i].value;
+	    	sum += chv[indx + i].value;
+	    }
+	    r = r / sum;
+	    if  (r > maxval) 
+	    	r = maxval;	/* avoid math errors */
+	    g = g / sum;
+	    if  (g > maxval) 
+	    	g = maxval;
+	    b = b / sum;
+	    if  (b > maxval) 
+	    	b = maxval;
+	    PPM_ASSIGN (colormap[bi].color, r, g, b) ;
+	}
+
+	/* All done.  */
+	return colormap;
+}
+
+
+static int	
+redCompare (ch1, ch2) 
+colorhist_vector ch1, ch2;
+{
+	return (int) PPM_GETR (ch1->color)  - (int) PPM_GETR (ch2->color) ;
+}
+
+
+static int	
+greenCompare (ch1, ch2) 
+colorhist_vector ch1, ch2;
+{
+	return (int) PPM_GETG (ch1->color)  - (int) PPM_GETG (ch2->color) ;
+}
+
+
+static int	
+blueCompare (ch1, ch2) 
+colorhist_vector ch1, ch2;
+{
+	return (int) PPM_GETB (ch1->color)  - (int) PPM_GETB (ch2->color) ;
+}
+
+
+static int	
+sumCompare (b1, b2) 
+box_vector b1, b2;
+{
+	return b2->sum - b1->sum;
+}
+
+
+static colorhist_vector
+computeColorHist (pixels, cols, rows, maxcolors, colorsP) 
+pixel**pixels;
+int	cols, rows, maxcolors;
+int*colorsP;
+{
+	colorhash_table cht;
+	colorhist_vector chv;
+
+	cht = computeColorHash (pixels, cols, rows, maxcolors, colorsP) ;
+	if  (cht == (colorhash_table) 0) 
+	    return (colorhist_vector) 0;
+	chv = colorHashToColorHist (cht, maxcolors) ;
+	freeColorHash (cht) ;
+	return chv;
+}
+
+
+static void
+addToColorHist (chv, colorsP, maxcolors, colorP, value, position) 
+colorhist_vector chv;
+pixel*colorP;
+int*colorsP;
+int	maxcolors, value, position;
+{
+	int	i, j;
+
+	/* Search colorhist for the color. */
+	for  (i = 0; i < *colorsP; ++i) 
+	    if  (PPM_EQUAL (chv[i].color, *colorP) )  {
+	    	/* Found it - move to new slot. */
+	    	if  (position > i)  {
+	    	    for  (j = i; j < position; ++j) 
+	    	    	chv[j] = chv[j + 1];
+	    	} else if  (position < i)  {
+	    	    for  (j = i; j > position; --j) 
+	    	    	chv[j] = chv[j - 1];
+	    	}
+	    	chv[position].color = *colorP;
+	    	chv[position].value = value;
+	    	return;
+	    }
+	if  (*colorsP < maxcolors)  {
+	    /* Didn't find it, but there's room to add it; so do so. */
+	    for  (i = *colorsP; i > position; --i) 
+	    	chv[i] = chv[i - 1];
+	    chv[position].color = *colorP;
+	    chv[position].value = value;
+	    ++(*colorsP);
+	}
+}
+
+
+static colorhash_table
+computeColorHash (pixels, cols, rows, maxcolors, colorsP) 
+pixel**pixels;
+int	cols, rows, maxcolors;
+int*colorsP;
+{
+	colorhash_table cht;
+	register pixel*pP;
+	colorhist_list chl;
+	int	col, row, hash;
+
+	cht = allocColorHash ();
+	*colorsP = 0;
+
+	/* Go through the entire image, building a hash table of colors. */
+	for  (row = 0; row < rows; ++row) 
+	    for  (col = 0, pP = pixels[row]; col < cols; ++col, ++pP)  {
+	    	hash = hashPixel (*pP) ;
+	    	for  (chl=cht[hash]; chl != (colorhist_list) 0; chl=chl->next) 
+	    	    if  (PPM_EQUAL (chl->ch.color, *pP) ) 
+	    	    	break;
+	    	if  (chl != (colorhist_list) 0) 
+	    	    ++(chl->ch.value);
+	    	else
+	    	 {
+	    	    if  (++(*colorsP) > maxcolors)  {
+	    	    	freeColorHash (cht) ;
+	    	    	return (colorhash_table) 0;
+	    	    }
+	    	    chl = (colorhist_list) 
+			malloc (sizeof(struct colorhist_list_item));
+	    	    if  (chl == 0) 
+	    	    	perror ("out of memory computing hash table") ;
+	    	    chl->ch.color = *pP;
+	    	    chl->ch.value = 1;
+	    	    chl->next = cht[hash];
+	    	    cht[hash] = chl;
+	    	}
+	    }
+
+	return cht;
+}
+
+
+static colorhash_table
+allocColorHash ()
+{
+	colorhash_table cht;
+	int	i;
+
+	cht = (colorhash_table) malloc (HASH_SIZE * sizeof(colorhist_list)) ;
+	if  (cht == 0) 
+	    perror ("out of memory allocating hash table") ;
+
+	for  (i = 0; i < HASH_SIZE; ++i) 
+	    cht[i] = (colorhist_list) 0;
+
+	return cht;
+}
+
+
+static int
+addToColorHash (cht, colorP, value) 
+colorhash_table cht;
+pixel*colorP;
+int	value;
+{
+	register int	hash;
+	register colorhist_list chl;
+
+	chl = (colorhist_list) malloc (sizeof(struct colorhist_list_item) ) ;
+	if  (chl == 0) 
+	    return - 1;
+	hash = hashPixel (*colorP) ;
+	chl->ch.color = *colorP;
+	chl->ch.value = value;
+	chl->next = cht[hash];
+	cht[hash] = chl;
+	return 0;
+}
+
+
+static colorhist_vector
+colorHashToColorHist (cht, maxcolors) 
+colorhash_table cht;
+int	maxcolors;
+{
+	colorhist_vector chv;
+	colorhist_list chl;
+	int	i, j;
+
+	/* Now collate the hash table into a simple colorhist array. */
+	chv = (colorhist_vector) malloc (maxcolors * sizeof(struct colorhist_item) ) ;
+	/* (Leave room for expansion by caller.) */
+	if  (chv == (colorhist_vector) 0) 
+	    perror ("out of memory generating histogram") ;
+
+	/* Loop through the hash table. */
+	j = 0;
+	for  (i = 0; i < HASH_SIZE; ++i) 
+	    for  (chl = cht[i]; chl != (colorhist_list) 0; chl = chl->next)  {
+	    	/* Add the new entry. */
+	    	chv[j] = chl->ch;
+	    	++j;
+	    }
+
+	/* All done. */
+	return chv;
+}
+
+
+static colorhash_table
+colorHistToColorHash (chv, colors) 
+colorhist_vector chv;
+int	colors;
+{
+	colorhash_table cht;
+	int	i, hash;
+	pixel color;
+	colorhist_list chl;
+
+	cht = allocColorHash ();
+
+	for  (i = 0; i < colors; ++i)  {
+	    color = chv[i].color;
+	    hash = hashPixel (color) ;
+	    for  (chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next) 
+/*
+	    	if  (PPM_EQUAL (chl->ch.color, color) ) 
+	    	    pm_error(
+	    	        "same color found twice - %d %d %d", PPM_GETR(color),
+	    	        PPM_GETG(color), PPM_GETB(color)) ;
+*/
+	    chl = (colorhist_list) malloc (sizeof(struct colorhist_list_item) ) ;
+	    if  (chl == (colorhist_list) 0) 
+	    	perror ("out of memory") ;
+	    chl->ch.color = color;
+	    chl->ch.value = i;
+	    chl->next = cht[hash];
+	    cht[hash] = chl;
+	}
+
+	return cht;
+}
+
+
+static int
+lookupColor (cht, colorP) 
+colorhash_table cht;
+pixel*colorP;
+{
+	int	hash;
+	colorhist_list chl;
+
+	hash = hashPixel (*colorP) ;
+	for  (chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next) 
+	    if  (PPM_EQUAL (chl->ch.color, *colorP) ) 
+	    	return chl->ch.value;
+
+	return - 1;
+}
+
+
+static void
+freeColorHist (chv) 
+colorhist_vector chv;
+{
+	free ((char *) chv) ;
+}
+
+
+static void
+freeColorHash (cht) 
+colorhash_table cht;
+{
+	int	i;
+	colorhist_list chl, chlnext;
+
+	for  (i = 0; i < HASH_SIZE; ++i) 
+	    for  (chl = cht[i]; chl != (colorhist_list) 0; chl = chlnext)  {
+	    	chlnext = chl->next;
+	    	free ((char *) chl) ;
+	    }
+	free ((char *) cht) ;
+}