src/px/clrtab.c

#ifndef lint
static const char       RCSid[] = "$Id$";
#endif
/*
 * Simple median-cut color quantization based on colortab.c
 */

#include "standard.h"

#include "color.h"
                                /* histogram resolution */
#define NRED            36
#define NGRN            48
#define NBLU            24
#define HMAX            NGRN
                                /* minimum box count for adaptive partition */
#define MINSAMP         7
                                /* color partition */
#define set_branch(p,c) ((c)<<2|(p))
#define part(cn)        ((cn)>>2)
#define prim(cn)        ((cn)&3)
                                /* our color table (global) */
extern BYTE     clrtab[256][3];
                                /* histogram of colors / color assignments */
static unsigned histo[NRED][NGRN][NBLU];
#define cndx(c)         histo[((c)[RED]*NRED)>>8][((c)[GRN]*NGRN)>>8][((c)[BLU]*NBLU)>>8]
                                /* initial color cube boundary */
static int      CLRCUBE[3][2] = {0,NRED,0,NGRN,0,NBLU};
                                /* maximum propagated error during dithering */
#define MAXERR          20
                                /* define CLOSEST to get closest colors */
#ifndef CLOSEST
#ifdef SPEED
#if  SPEED > 8
#define CLOSEST         1       /* this step takes a little longer */
#endif
#endif
#endif

static  cut(), mktabent(), closest(), addneigh(), setclosest();
static int      split();
static unsigned dist();


new_histo(n)            /* clear our histogram */
int     n;
{
        bzero((char *)histo, sizeof(histo));
        return(0);
}


cnt_pixel(col)          /* add pixel to our histogram */
register BYTE   col[];
{
        cndx(col)++;
}


cnt_colrs(cs, n)                /* add a scanline to our histogram */
register COLR   *cs;
register int    n;
{
        while (n-- > 0) {
                cndx(cs[0])++;
                cs++;
        }
}


new_clrtab(ncolors)             /* make new color table using ncolors */
int     ncolors;
{
        if (ncolors < 1)
                return(0);
        if (ncolors > 256)
                ncolors = 256;
                                /* partition color space */
        cut(CLRCUBE, 0, ncolors);
#ifdef CLOSEST
        closest(ncolors);       /* ensure colors picked are closest */
#endif
                                /* reset dithering function */
        dith_colrs((BYTE *)NULL, (COLR *)NULL, 0);
                                /* return new color table size */
        return(ncolors);
}


int
map_pixel(col)                  /* get pixel for color */
register BYTE   col[];
{
    return(cndx(col));
}


map_colrs(bs, cs, n)            /* convert a scanline to color index values */
register BYTE   *bs;
register COLR   *cs;
register int    n;
{
        while (n-- > 0) {
                *bs++ = cndx(cs[0]);
                cs++;
        }
}


dith_colrs(bs, cs, n)           /* convert scanline to dithered index values */
register BYTE   *bs;
register COLR   *cs;
int     n;
{
        static short    (*cerr)[3] = NULL;
        static int      N = 0;
        int     err[3], errp[3];
        register int    x, i;

        if (n != N) {           /* get error propogation array */
                if (N) {
                        free((void *)cerr);
                        cerr = NULL;
                }
                if (n)
                        cerr = (short (*)[3])malloc(3*n*sizeof(short));
                if (cerr == NULL) {
                        N = 0;
                        map_colrs(bs, cs, n);
                        return;
                }
                N = n;
                bzero((char *)cerr, 3*N*sizeof(short));
        }
        err[0] = err[1] = err[2] = 0;
        for (x = 0; x < n; x++) {
                for (i = 0; i < 3; i++) {       /* dither value */
                        errp[i] = err[i];
                        err[i] += cerr[x][i];
#ifdef MAXERR
                        if (err[i] > MAXERR) err[i] = MAXERR;
                        else if (err[i] < -MAXERR) err[i] = -MAXERR;
#endif
                        err[i] += cs[x][i];
                        if (err[i] < 0) err[i] = 0;
                        else if (err[i] > 255) err[i] = 255;
                }
                bs[x] = cndx(err);
                for (i = 0; i < 3; i++) {       /* propagate error */
                        err[i] -= clrtab[bs[x]][i];
                        err[i] /= 3;
                        cerr[x][i] = err[i] + errp[i];
                }
        }
}


static
cut(box, c0, c1)                        /* partition color space */
register int    box[3][2];
int     c0, c1;
{
        register int    branch;
        int     kb[3][2];
        
        if (c1-c0 <= 1) {               /* assign pixel */
                mktabent(c0, box);
                return;
        }
                                        /* split box */
        branch = split(box);
        bcopy((char *)box, (char *)kb, sizeof(kb));
                                                /* do left (lesser) branch */
        kb[prim(branch)][1] = part(branch);
        cut(kb, c0, (c0+c1)>>1);
                                                /* do right branch */
        kb[prim(branch)][0] = part(branch);
        kb[prim(branch)][1] = box[prim(branch)][1];
        cut(kb, (c0+c1)>>1, c1);
}


static int
split(box)                              /* find median cut for box */
register int    box[3][2];
{
#define c0      r
        register int    r, g, b;
        int     pri;
        long    t[HMAX], med;
                                        /* find dominant axis */
        pri = RED;
        if (box[GRN][1]-box[GRN][0] > box[pri][1]-box[pri][0])
                pri = GRN;
        if (box[BLU][1]-box[BLU][0] > box[pri][1]-box[pri][0])
                pri = BLU;
                                        /* sum histogram over box */
        med = 0;
        switch (pri) {
        case RED:
                for (r = box[RED][0]; r < box[RED][1]; r++) {
                        t[r] = 0;
                        for (g = box[GRN][0]; g < box[GRN][1]; g++)
                                for (b = box[BLU][0]; b < box[BLU][1]; b++)
                                        t[r] += histo[r][g][b];
                        med += t[r];
                }
                break;
        case GRN:
                for (g = box[GRN][0]; g < box[GRN][1]; g++) {
                        t[g] = 0;
                        for (b = box[BLU][0]; b < box[BLU][1]; b++)
                                for (r = box[RED][0]; r < box[RED][1]; r++)
                                        t[g] += histo[r][g][b];
                        med += t[g];
                }
                break;
        case BLU:
                for (b = box[BLU][0]; b < box[BLU][1]; b++) {
                        t[b] = 0;
                        for (r = box[RED][0]; r < box[RED][1]; r++)
                                for (g = box[GRN][0]; g < box[GRN][1]; g++)
                                        t[b] += histo[r][g][b];
                        med += t[b];
                }
                break;
        }
        if (med < MINSAMP)              /* if too sparse, split at midpoint */
                return(set_branch(pri,(box[pri][0]+box[pri][1])>>1));
                                        /* find median position */
        med >>= 1;
        for (c0 = box[pri][0]; med > 0; c0++)
                med -= t[c0];
        if (c0 > (box[pri][0]+box[pri][1])>>1)  /* if past the midpoint */
                c0--;                           /* part left of median */
        return(set_branch(pri,c0));
#undef c0
}


static
mktabent(p, box)        /* compute average color for box and assign */
int     p;
register int    box[3][2];
{
        unsigned long   sum[3];
        unsigned        r, g;
        unsigned long   n;
        register unsigned       b, c;
                                                /* sum pixels in box */
        n = 0;
        sum[RED] = sum[GRN] = sum[BLU] = 0;
        for (r = box[RED][0]; r < box[RED][1]; r++)
            for (g = box[GRN][0]; g < box[GRN][1]; g++)
                for (b = box[BLU][0]; b < box[BLU][1]; b++) {
                    if (c = histo[r][g][b]) {
                        n += c;
                        sum[RED] += (long)c*r;
                        sum[GRN] += (long)c*g;
                        sum[BLU] += (long)c*b;
                    }
                    histo[r][g][b] = p;         /* assign pixel */
                }
        if (n >= (1L<<23)/HMAX) {               /* avoid overflow */
                sum[RED] /= n;
                sum[GRN] /= n;
                sum[BLU] /= n;
                n = 1;
        }
        if (n) {                                /* compute average */
                clrtab[p][RED] = sum[RED]*256/NRED/n;
                clrtab[p][GRN] = sum[GRN]*256/NGRN/n;
                clrtab[p][BLU] = sum[BLU]*256/NBLU/n;
        } else {                                /* empty box -- use midpoint */
                clrtab[p][RED] = (box[RED][0]+box[RED][1])*256/NRED/2;
                clrtab[p][GRN] = (box[GRN][0]+box[GRN][1])*256/NGRN/2;
                clrtab[p][BLU] = (box[BLU][0]+box[BLU][1])*256/NBLU/2;
        }
}


#ifdef CLOSEST
#define NBSIZ           32
static
closest(n)                      /* make sure we have the closest colors */
int     n;
{
        BYTE    *neigh[256];
        register int    r, g, b;
#define i r
                                        /* get space for neighbor lists */
        for (i = 0; i < n; i++) {
                if ((neigh[i] = (BYTE *)malloc(NBSIZ)) == NULL) {
                        while (i--)
                                free(neigh[i]);
                        return;                 /* ENOMEM -- abandon effort */
                }
                neigh[i][0] = i;                /* identity is terminator */
        }
                                        /* make neighbor lists */
        for (r = 0; r < NRED; r++)
            for (g = 0; g < NGRN; g++)
                for (b = 0; b < NBLU; b++) {
                    if (r < NRED-1 && histo[r][g][b] != histo[r+1][g][b])
                        addneigh(neigh, histo[r][g][b], histo[r+1][g][b]);
                    if (g < NGRN-1 && histo[r][g][b] != histo[r][g+1][b])
                        addneigh(neigh, histo[r][g][b], histo[r][g+1][b]);
                    if (b < NBLU-1 && histo[r][g][b] != histo[r][g][b+1])
                        addneigh(neigh, histo[r][g][b], histo[r][g][b+1]);
                }
                                        /* assign closest values */
        for (r = 0; r < NRED; r++)
            for (g = 0; g < NGRN; g++)
                for (b = 0; b < NBLU; b++)
                    setclosest(neigh, r, g, b);
                                        /* free neighbor lists */
        for (i = 0; i < n; i++)
                free(neigh[i]);
#undef i
}


static
addneigh(nl, i, j)              /* i and j are neighbors; add them to list */
register BYTE   *nl[];
register int    i;
int     j;
{
        int     nc;
        char    *nnl;
        register int    t;
        
        for (nc = 0; nc < 2; nc++) {            /* do both neighbors */
                for (t = 0; nl[i][t] != i; t++)
                        if (nl[i][t] == j)
                                break;          /* in list already */
                if (nl[i][t] == i) {            /* add to list */
                        nl[i][t++] = j;
                        if (t % NBSIZ == 0) {   /* enlarge list */
                                if ((nnl = realloc(nl[i], t+NBSIZ)) == NULL)
                                        t--;
                                else
                                        nl[i] = (BYTE *)nnl;
                        }
                        nl[i][t] = i;           /* terminator */
                }
                t = i; i = j; j = t;            /* swap and do it again */
        }
}


static unsigned
dist(col, r, g, b)              /* find distance from clrtab entry to r,g,b */
register BYTE   col[3];
int     r, g, b;
{
        register int    tmp;
        register unsigned       sum;
        
        tmp = col[RED]*NRED/256 - r;
        sum = tmp*tmp;
        tmp = col[GRN]*NGRN/256 - g;
        sum += tmp*tmp;
        tmp = col[BLU]*NBLU/256 - b;
        sum += tmp*tmp;
        return(sum);
}


static
setclosest(nl, r, g, b)         /* find index closest to color and assign */
BYTE    *nl[];
int     r, g, b;
{
        int     ident;
        unsigned        min;
        register unsigned       d;
        register BYTE   *p;
                                        /* get starting value */
        min = dist(clrtab[ident=histo[r][g][b]], r, g, b);
                                        /* find minimum */
        for (p = nl[ident]; *p != ident; p++)
                if ((d = dist(clrtab[*p], r, g, b)) < min) {
                        min = d;
                        histo[r][g][b] = *p;
                }
}
#endif
Revision:	2.12
Committed:	Sat Feb 22 02:07:27 2003 UTC (21 years, 2 months ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad3R5
Changes since 2.11:	+2 -5 lines
Log Message:	Changes and check-in for 3.5 release Includes new source files and modifications not recorded for many years See ray/doc/notes/ReleaseNotes for notes between 3.1 and 3.5 release
#	User	Rev	Content
1	greg	2.1	#ifndef lint
2	greg	2.12	static const char RCSid[] = "$Id$";
3	greg	2.1	#endif
4			/*
5			* Simple median-cut color quantization based on colortab.c
6			*/
7
8			#include "standard.h"
9
10			#include "color.h"
11			/* histogram resolution */
12			#define NRED 36
13			#define NGRN 48
14			#define NBLU 24
15			#define HMAX NGRN
16			/* minimum box count for adaptive partition */
17			#define MINSAMP 7
18			/* color partition */
19			#define set_branch(p,c) ((c)<<2\|(p))
20			#define part(cn) ((cn)>>2)
21			#define prim(cn) ((cn)&3)
22			/* our color table (global) */
23	greg	2.10	extern BYTE clrtab[256][3];
24	greg	2.1	/* histogram of colors / color assignments */
25			static unsigned histo[NRED][NGRN][NBLU];
26			#define cndx(c) histo[((c)[RED]NRED)>>8][((c)[GRN]NGRN)>>8][((c)[BLU]*NBLU)>>8]
27			/* initial color cube boundary */
28			static int CLRCUBE[3][2] = {0,NRED,0,NGRN,0,NBLU};
29			/* maximum propagated error during dithering */
30			#define MAXERR 20
31	greg	2.2	/* define CLOSEST to get closest colors */
32	greg	2.4	#ifndef CLOSEST
33			#ifdef SPEED
34			#if SPEED > 8
35			#define CLOSEST 1 /* this step takes a little longer */
36			#endif
37			#endif
38			#endif
39	greg	2.1
40	greg	2.11	static cut(), mktabent(), closest(), addneigh(), setclosest();
41			static int split();
42			static unsigned dist();
43
44	greg	2.1
45	greg	2.10	new_histo(n) /* clear our histogram */
46			int n;
47	greg	2.1	{
48			bzero((char *)histo, sizeof(histo));
49	greg	2.10	return(0);
50	greg	2.1	}
51
52
53			cnt_pixel(col) /* add pixel to our histogram */
54			register BYTE col[];
55			{
56			cndx(col)++;
57			}
58
59
60			cnt_colrs(cs, n) /* add a scanline to our histogram */
61			register COLR *cs;
62			register int n;
63			{
64			while (n-- > 0) {
65			cndx(cs[0])++;
66			cs++;
67			}
68			}
69
70
71			new_clrtab(ncolors) /* make new color table using ncolors */
72			int ncolors;
73			{
74			if (ncolors < 1)
75			return(0);
76			if (ncolors > 256)
77			ncolors = 256;
78			/* partition color space */
79			cut(CLRCUBE, 0, ncolors);
80	greg	2.2	#ifdef CLOSEST
81			closest(ncolors); /* ensure colors picked are closest */
82			#endif
83	greg	2.9	/* reset dithering function */
84			dith_colrs((BYTE )NULL, (COLR )NULL, 0);
85	greg	2.1	/* return new color table size */
86			return(ncolors);
87			}
88
89
90			int
91			map_pixel(col) /* get pixel for color */
92			register BYTE col[];
93			{
94			return(cndx(col));
95			}
96
97
98			map_colrs(bs, cs, n) /* convert a scanline to color index values */
99			register BYTE *bs;
100			register COLR *cs;
101			register int n;
102			{
103			while (n-- > 0) {
104			*bs++ = cndx(cs[0]);
105			cs++;
106			}
107			}
108
109
110			dith_colrs(bs, cs, n) /* convert scanline to dithered index values */
111			register BYTE *bs;
112			register COLR *cs;
113			int n;
114			{
115	greg	2.8	static short (*cerr)[3] = NULL;
116	greg	2.1	static int N = 0;
117			int err[3], errp[3];
118			register int x, i;
119
120			if (n != N) { /* get error propogation array */
121	greg	2.8	if (N) {
122	greg	2.12	free((void *)cerr);
123	greg	2.8	cerr = NULL;
124			}
125			if (n)
126	greg	2.1	cerr = (short ()[3])malloc(3n*sizeof(short));
127			if (cerr == NULL) {
128			N = 0;
129			map_colrs(bs, cs, n);
130			return;
131			}
132			N = n;
133			bzero((char )cerr, 3N*sizeof(short));
134			}
135			err[0] = err[1] = err[2] = 0;
136			for (x = 0; x < n; x++) {
137			for (i = 0; i < 3; i++) { /* dither value */
138			errp[i] = err[i];
139			err[i] += cerr[x][i];
140			#ifdef MAXERR
141			if (err[i] > MAXERR) err[i] = MAXERR;
142			else if (err[i] < -MAXERR) err[i] = -MAXERR;
143			#endif
144			err[i] += cs[x][i];
145			if (err[i] < 0) err[i] = 0;
146			else if (err[i] > 255) err[i] = 255;
147			}
148			bs[x] = cndx(err);
149			for (i = 0; i < 3; i++) { /* propagate error */
150			err[i] -= clrtab[bs[x]][i];
151			err[i] /= 3;
152			cerr[x][i] = err[i] + errp[i];
153			}
154			}
155			}
156
157
158			static
159			cut(box, c0, c1) /* partition color space */
160			register int box[3][2];
161			int c0, c1;
162			{
163			register int branch;
164			int kb[3][2];
165
166			if (c1-c0 <= 1) { /* assign pixel */
167			mktabent(c0, box);
168			return;
169			}
170			/* split box */
171			branch = split(box);
172			bcopy((char )box, (char )kb, sizeof(kb));
173			/* do left (lesser) branch */
174			kb[prim(branch)][1] = part(branch);
175			cut(kb, c0, (c0+c1)>>1);
176			/* do right branch */
177			kb[prim(branch)][0] = part(branch);
178			kb[prim(branch)][1] = box[prim(branch)][1];
179			cut(kb, (c0+c1)>>1, c1);
180			}
181
182
183			static int
184			split(box) /* find median cut for box */
185			register int box[3][2];
186			{
187			#define c0 r
188			register int r, g, b;
189			int pri;
190	greg	2.6	long t[HMAX], med;
191	greg	2.1	/* find dominant axis */
192			pri = RED;
193			if (box[GRN][1]-box[GRN][0] > box[pri][1]-box[pri][0])
194			pri = GRN;
195			if (box[BLU][1]-box[BLU][0] > box[pri][1]-box[pri][0])
196			pri = BLU;
197			/* sum histogram over box */
198			med = 0;
199			switch (pri) {
200			case RED:
201			for (r = box[RED][0]; r < box[RED][1]; r++) {
202			t[r] = 0;
203			for (g = box[GRN][0]; g < box[GRN][1]; g++)
204			for (b = box[BLU][0]; b < box[BLU][1]; b++)
205			t[r] += histo[r][g][b];
206			med += t[r];
207			}
208			break;
209			case GRN:
210			for (g = box[GRN][0]; g < box[GRN][1]; g++) {
211			t[g] = 0;
212			for (b = box[BLU][0]; b < box[BLU][1]; b++)
213			for (r = box[RED][0]; r < box[RED][1]; r++)
214			t[g] += histo[r][g][b];
215			med += t[g];
216			}
217			break;
218			case BLU:
219			for (b = box[BLU][0]; b < box[BLU][1]; b++) {
220			t[b] = 0;
221			for (r = box[RED][0]; r < box[RED][1]; r++)
222			for (g = box[GRN][0]; g < box[GRN][1]; g++)
223			t[b] += histo[r][g][b];
224			med += t[b];
225			}
226			break;
227			}
228			if (med < MINSAMP) /* if too sparse, split at midpoint */
229			return(set_branch(pri,(box[pri][0]+box[pri][1])>>1));
230			/* find median position */
231			med >>= 1;
232			for (c0 = box[pri][0]; med > 0; c0++)
233			med -= t[c0];
234			if (c0 > (box[pri][0]+box[pri][1])>>1) /* if past the midpoint */
235			c0--; /* part left of median */
236			return(set_branch(pri,c0));
237			#undef c0
238			}
239
240
241			static
242			mktabent(p, box) /* compute average color for box and assign */
243			int p;
244			register int box[3][2];
245			{
246	greg	2.5	unsigned long sum[3];
247	greg	2.7	unsigned r, g;
248			unsigned long n;
249	greg	2.5	register unsigned b, c;
250	greg	2.1	/* sum pixels in box */
251			n = 0;
252			sum[RED] = sum[GRN] = sum[BLU] = 0;
253			for (r = box[RED][0]; r < box[RED][1]; r++)
254			for (g = box[GRN][0]; g < box[GRN][1]; g++)
255			for (b = box[BLU][0]; b < box[BLU][1]; b++) {
256			if (c = histo[r][g][b]) {
257			n += c;
258			sum[RED] += (long)c*r;
259			sum[GRN] += (long)c*g;
260			sum[BLU] += (long)c*b;
261			}
262			histo[r][g][b] = p; /* assign pixel */
263			}
264	greg	2.7	if (n >= (1L<<23)/HMAX) { /* avoid overflow */
265	greg	2.5	sum[RED] /= n;
266			sum[GRN] /= n;
267			sum[BLU] /= n;
268			n = 1;
269			}
270	greg	2.1	if (n) { /* compute average */
271			clrtab[p][RED] = sum[RED]*256/NRED/n;
272			clrtab[p][GRN] = sum[GRN]*256/NGRN/n;
273			clrtab[p][BLU] = sum[BLU]*256/NBLU/n;
274			} else { /* empty box -- use midpoint */
275			clrtab[p][RED] = (box[RED][0]+box[RED][1])*256/NRED/2;
276			clrtab[p][GRN] = (box[GRN][0]+box[GRN][1])*256/NGRN/2;
277			clrtab[p][BLU] = (box[BLU][0]+box[BLU][1])*256/NBLU/2;
278			}
279			}
280	greg	2.2
281
282			#ifdef CLOSEST
283			#define NBSIZ 32
284			static
285			closest(n) /* make sure we have the closest colors */
286			int n;
287			{
288			BYTE *neigh[256];
289			register int r, g, b;
290			#define i r
291			/* get space for neighbor lists */
292			for (i = 0; i < n; i++) {
293			if ((neigh[i] = (BYTE *)malloc(NBSIZ)) == NULL) {
294			while (i--)
295			free(neigh[i]);
296			return; /* ENOMEM -- abandon effort */
297			}
298			neigh[i][0] = i; /* identity is terminator */
299			}
300			/* make neighbor lists */
301	greg	2.3	for (r = 0; r < NRED; r++)
302			for (g = 0; g < NGRN; g++)
303			for (b = 0; b < NBLU; b++) {
304			if (r < NRED-1 && histo[r][g][b] != histo[r+1][g][b])
305	greg	2.2	addneigh(neigh, histo[r][g][b], histo[r+1][g][b]);
306	greg	2.3	if (g < NGRN-1 && histo[r][g][b] != histo[r][g+1][b])
307	greg	2.2	addneigh(neigh, histo[r][g][b], histo[r][g+1][b]);
308	greg	2.3	if (b < NBLU-1 && histo[r][g][b] != histo[r][g][b+1])
309	greg	2.2	addneigh(neigh, histo[r][g][b], histo[r][g][b+1]);
310			}
311			/* assign closest values */
312			for (r = 0; r < NRED; r++)
313			for (g = 0; g < NGRN; g++)
314			for (b = 0; b < NBLU; b++)
315			setclosest(neigh, r, g, b);
316			/* free neighbor lists */
317			for (i = 0; i < n; i++)
318			free(neigh[i]);
319			#undef i
320			}
321
322
323			static
324			addneigh(nl, i, j) /* i and j are neighbors; add them to list */
325			register BYTE *nl[];
326			register int i;
327			int j;
328			{
329			int nc;
330			char *nnl;
331			register int t;
332
333			for (nc = 0; nc < 2; nc++) { /* do both neighbors */
334			for (t = 0; nl[i][t] != i; t++)
335			if (nl[i][t] == j)
336			break; /* in list already */
337			if (nl[i][t] == i) { /* add to list */
338			nl[i][t++] = j;
339			if (t % NBSIZ == 0) { /* enlarge list */
340			if ((nnl = realloc(nl[i], t+NBSIZ)) == NULL)
341			t--;
342			else
343			nl[i] = (BYTE *)nnl;
344			}
345			nl[i][t] = i; /* terminator */
346			}
347			t = i; i = j; j = t; /* swap and do it again */
348			}
349			}
350
351
352			static unsigned
353			dist(col, r, g, b) /* find distance from clrtab entry to r,g,b */
354			register BYTE col[3];
355			int r, g, b;
356			{
357	greg	2.4	register int tmp;
358	greg	2.2	register unsigned sum;
359
360			tmp = col[RED]*NRED/256 - r;
361			sum = tmp*tmp;
362			tmp = col[GRN]*NGRN/256 - g;
363			sum += tmp*tmp;
364			tmp = col[BLU]*NBLU/256 - b;
365			sum += tmp*tmp;
366			return(sum);
367			}
368
369
370			static
371			setclosest(nl, r, g, b) /* find index closest to color and assign */
372			BYTE *nl[];
373			int r, g, b;
374			{
375			int ident;
376			unsigned min;
377			register unsigned d;
378			register BYTE *p;
379			/* get starting value */
380			min = dist(clrtab[ident=histo[r][g][b]], r, g, b);
381			/* find minimum */
382			for (p = nl[ident]; *p != ident; p++)
383			if ((d = dist(clrtab[*p], r, g, b)) < min) {
384			min = d;
385			histo[r][g][b] = *p;
386			}
387			}
388			#endif