[xfishtank.git] / medcut.c

#include <stdio.h>
#include <stdlib.h>
#include "medcut.h"

#define RED     0
#define GREEN   1
#define BLUE    2

#define FindHash(red, green, blue, h_ptr) \
	h_ptr = Hash[((red * 299) + (green * 587) + (blue * 114)) / 1000 * NCells / 256]; \
	while(h_ptr != NULL) \
	{ \
		if ((h_ptr->pixel[RED] == red)&& \
		    (h_ptr->pixel[GREEN] == green)&& \
		    (h_ptr->pixel[BLUE] == blue)) \
		{ \
			break; \
		} \
		h_ptr = h_ptr->hash_next; \
	}

struct color_rec {
    int pixel[3];
    int box_num;
    struct color_rec *hash_next;
    struct color_rec *next;
} *Hash[256];
struct c_box_rec {
    int min_pix[3];
    int max_pix[3];
    int count;
    struct color_rec *c_data;
} C_boxes[256];

int BoxCount;
struct color_rec *hash_ptr;
struct color_rec *tptr;
static int Width, Height;
int ColorCnt;
int NCells;
struct color_rec *Tptr;


void
InitMinMax(boxnum)
int boxnum;
{
    C_boxes[boxnum].min_pix[RED] = 256;
    C_boxes[boxnum].max_pix[RED] = 0;
    C_boxes[boxnum].min_pix[GREEN] = 256;
    C_boxes[boxnum].max_pix[GREEN] = 0;
    C_boxes[boxnum].min_pix[BLUE] = 256;
    C_boxes[boxnum].max_pix[BLUE] = 0;
}


struct color_rec *
AddHash(red, green, blue)
int red, green, blue;
{
    int lum;

    lum = ((red * 299) + (green * 587) + (blue * 114)) / 1000 * NCells / 256;;
    hash_ptr = (struct color_rec *) malloc(sizeof(struct color_rec));
    if (hash_ptr == NULL) {
	fprintf(stderr, "Cannot malloc %dth color\n", ColorCnt);
	exit(1);
    }
    hash_ptr->pixel[RED] = red;
    hash_ptr->pixel[GREEN] = green;
    hash_ptr->pixel[BLUE] = blue;
    hash_ptr->box_num = 0;
    hash_ptr->next = NULL;
    hash_ptr->hash_next = Hash[lum];
    Hash[lum] = hash_ptr;
    return (hash_ptr);
}


void
AddColor(cptr, boxnum)
struct color_rec *cptr;
int boxnum;
{
    struct color_rec *ptr;

    while (cptr != NULL) {
	ptr = cptr;
	cptr = cptr->next;
	ptr->box_num = boxnum;
	ptr->next = C_boxes[boxnum].c_data;
	C_boxes[boxnum].c_data = ptr;
	if (ptr->pixel[RED] < C_boxes[boxnum].min_pix[RED])
	    C_boxes[boxnum].min_pix[RED] = ptr->pixel[RED];
	if (ptr->pixel[RED] > C_boxes[boxnum].max_pix[RED])
	    C_boxes[boxnum].max_pix[RED] = ptr->pixel[RED];
	if (ptr->pixel[GREEN] < C_boxes[boxnum].min_pix[GREEN])
	    C_boxes[boxnum].min_pix[GREEN] = ptr->pixel[GREEN];
	if (ptr->pixel[GREEN] > C_boxes[boxnum].max_pix[GREEN])
	    C_boxes[boxnum].max_pix[GREEN] = ptr->pixel[GREEN];
	if (ptr->pixel[BLUE] < C_boxes[boxnum].min_pix[BLUE])
	    C_boxes[boxnum].min_pix[BLUE] = ptr->pixel[BLUE];
	if (ptr->pixel[BLUE] > C_boxes[boxnum].max_pix[BLUE])
	    C_boxes[boxnum].max_pix[BLUE] = ptr->pixel[BLUE];
    }
}


void
CountColors(data, colrs)
unsigned char *data;
struct colr_data *colrs;
{
    unsigned char *dptr;
    register int i, j;
    int red, green, blue;
    register struct color_rec *tptr;

    InitMinMax(0);
    C_boxes[0].c_data = NULL;
    tptr = C_boxes[0].c_data;
    ColorCnt = 0;

    dptr = data;

    for (j = 0; j < Height; j++) {
	for (i = 0; i < Width; i++) {
	    red = colrs[(int) *dptr].red;
	    green = colrs[(int) *dptr].green;
	    blue = colrs[(int) *dptr].blue;
	    FindHash(red, green, blue, tptr);
	    if (tptr == NULL) {
		tptr = AddHash(red, green, blue);
		tptr->next = NULL;
		AddColor(tptr, 0);
		ColorCnt++;
	    }
	    dptr++;
	}
    }
}


int
FindTarget(tptr)
int *tptr;
{
    int range, i, indx;

    range = 0;
    for (i = 0; i < BoxCount; i++) {
	int rr, gr, br;

	rr = C_boxes[i].max_pix[RED] - C_boxes[i].min_pix[RED];
	gr = C_boxes[i].max_pix[GREEN] - C_boxes[i].min_pix[GREEN];
	br = C_boxes[i].max_pix[BLUE] - C_boxes[i].min_pix[BLUE];
	if (rr > range) {
	    range = rr;
	    *tptr = i;
	    indx = RED;
	}
	if (gr > range) {
	    range = gr;
	    *tptr = i;
	    indx = GREEN;
	}
	if (br > range) {
	    range = br;
	    *tptr = i;
	    indx = BLUE;
	}
    }
    return (indx);
}


void
SplitBox(boxnum, color_indx)
int boxnum, color_indx;
{
    struct color_rec *low, *high;
    struct color_rec *data;
    int med_cnt, split_val;
    int low_cnt, high_cnt;
    int Low_cnt, High_cnt;
    int Greater, Lesser;

    Greater = BoxCount++;
    Lesser = boxnum;
    InitMinMax(Lesser);
    InitMinMax(Greater);
    data = C_boxes[boxnum].c_data;
    med_cnt = C_boxes[boxnum].count / 2;
    C_boxes[Lesser].c_data = NULL;
    C_boxes[Greater].c_data = NULL;
    Low_cnt = 0;
    High_cnt = 0;
    while (med_cnt > 0) {
	if (data->pixel[color_indx] < data->next->pixel[color_indx]) {
	    low = data;
	    high = data->next;
	    data = high->next;
	} else {
	    high = data;
	    low = data->next;
	    data = low->next;
	}
	low->next = NULL;
	high->next = NULL;
	low_cnt = 1;
	high_cnt = 1;
	split_val = low->pixel[color_indx];
	while (data != NULL) {
	    tptr = data;
	    data = data->next;
	    if (tptr->pixel[color_indx] > split_val) {
		tptr->next = high;
		high = tptr;
		high_cnt++;
	    } else {
		tptr->next = low;
		low = tptr;
		low_cnt++;
	    }
	}			/* end while data->next != NULL */
	if (low_cnt <= med_cnt) {
	    AddColor(low, Lesser);
	    Low_cnt += low_cnt;
	    med_cnt -= low_cnt;
	    if (med_cnt == 0) {
		AddColor(high, Greater);
		High_cnt += high_cnt;
	    }
	    data = high;
	} else {
	    AddColor(high, Greater);
	    High_cnt += high_cnt;
	    data = low;
	}
    }				/* end while med_cnt */
    C_boxes[Lesser].count = Low_cnt;
    C_boxes[Greater].count = High_cnt;

}


void
SplitColors(e_cnt)
int e_cnt;
{
    if (ColorCnt < e_cnt) {
	int i;

	tptr = C_boxes[0].c_data;
	for (i = 0; i < ColorCnt; i++) {
	    hash_ptr = tptr;
	    tptr = tptr->next;
	    C_boxes[i].c_data = hash_ptr;
	    C_boxes[i].count = 1;
	    hash_ptr->box_num = i;
	    hash_ptr->next = NULL;
	}
	BoxCount = ColorCnt;
    } else {
	BoxCount = 1;
	while (BoxCount < e_cnt) {
	    int target, color_indx;

	    target = 0;
	    color_indx = 0;
	    color_indx = FindTarget(&target);
	    SplitBox(target, color_indx);
	}
    }
}


/*
 * Colors passed in 0-65535, internally are 0-255
 */
void
ConvertColor(rp, gp, bp)
int *rp, *gp, *bp;
{
    struct color_rec *cptr;
    register struct color_rec *hash_ptr;
    int indx;
    int red, green, blue;
    int Tred, Tgreen, Tblue;
    int c_cnt;

    red = *rp / NCells;
    green = *gp / NCells;
    blue = *bp / NCells;
    FindHash(red, green, blue, hash_ptr);
    if (hash_ptr == NULL) {
	fprintf(stderr, "Unknown color (%d,%d,%d)\n", red, green, blue);
	hash_ptr = Hash[0];
    }
    indx = hash_ptr->box_num;
    cptr = C_boxes[indx].c_data;
    c_cnt = 0;
    Tred = Tgreen = Tblue = 0;
    while (cptr != NULL) {
	Tred += cptr->pixel[RED];
	Tgreen += cptr->pixel[GREEN];
	Tblue += cptr->pixel[BLUE];
	c_cnt++;
	cptr = cptr->next;
    }
    if (c_cnt) {
	red = Tred / c_cnt;
	green = Tgreen / c_cnt;
	blue = Tblue / c_cnt;
    }

    *rp = red * NCells;
    *gp = green * NCells;
    *bp = blue * NCells;
}


void
ConvertData(data, colrs)
unsigned char *data;
struct colr_data *colrs;
{
    unsigned char *dptr;
    register int i, j;
    int red, green, blue;
    register struct color_rec *hash_ptr;

    dptr = data;

    for (j = 0; j < Height; j++) {
	for (i = 0; i < Width; i++) {
	    red = colrs[(int) *dptr].red;
	    green = colrs[(int) *dptr].green;
	    blue = colrs[(int) *dptr].blue;
	    FindHash(red, green, blue, hash_ptr);
	    if (hash_ptr == NULL) {
		fprintf(stderr, "Unknown color (%d,%d,%d)\n", red, green, blue);
		hash_ptr = Hash[0];
	    }
	    *dptr++ = (unsigned char) hash_ptr->box_num;
	}
    }
}


void
PrintColormap(e_cnt, colrs)
int e_cnt;
struct colr_data *colrs;
{
    int i;

    for (i = 0; i < BoxCount; i++) {
	int Tred, Tgreen, Tblue;
	int c_cnt;

	c_cnt = 0;
	Tred = Tgreen = Tblue = 0;
	tptr = C_boxes[i].c_data;
	while (tptr != NULL) {
	    Tred += tptr->pixel[RED];
	    Tgreen += tptr->pixel[GREEN];
	    Tblue += tptr->pixel[BLUE];
	    c_cnt++;
	    tptr = tptr->next;
	}
	colrs[i].red = Tred / c_cnt;
	colrs[i].green = Tgreen / c_cnt;
	colrs[i].blue = Tblue / c_cnt;
    }
    for (i = BoxCount; i < e_cnt; i++) {
	colrs[i].red = 0;
	colrs[i].green = 0;
	colrs[i].blue = 0;
    }
}


void
MedianCut(data, w, h, colrs, start_cnt, end_cnt)
unsigned char *data;
int *w, *h;
struct colr_data *colrs;
int start_cnt, end_cnt;
{
    int i;

    Width = *w;
    Height = *h;
    NCells = start_cnt;
    BoxCount = 0;
    ColorCnt = 0;
    for (i = 0; i < 256; i++) {
	Hash[i] = NULL;
	C_boxes[i].c_data = NULL;
	C_boxes[i].count = 0;
    }
    CountColors(data, colrs);
    C_boxes[0].count = ColorCnt;
    SplitColors(end_cnt);
    ConvertData(data, colrs);
    PrintColormap(end_cnt, colrs);
    for (i = 0; i < 256; i++) {
	hash_ptr = Hash[i];
	while (hash_ptr != NULL) {
	    tptr = hash_ptr;
	    hash_ptr = hash_ptr->hash_next;
	    free((char *) tptr);
	}
    }
}


void
MedianInit()
{
    int i;

    NCells = 256;
    BoxCount = 0;
    ColorCnt = 0;
    for (i = 0; i < 256; i++) {
	Hash[i] = NULL;
	C_boxes[i].c_data = NULL;
	C_boxes[i].count = 0;
    }
    InitMinMax(0);
    C_boxes[0].c_data = NULL;
    Tptr = C_boxes[0].c_data;
}


/*
 * colrs are passed on 0-65535, but this median cut only deals with
 * 0-255.
 */
void
MedianCount(data, w, h, colrs)
unsigned char *data;
int w, h;
struct colr_data *colrs;
{
    unsigned char *dptr;
    register int i, j;
    int red, green, blue;

    Width = w;
    Height = h;
    dptr = data;

    for (j = 0; j < Height; j++) {
	for (i = 0; i < Width; i++) {
	    red = colrs[(int) *dptr].red / NCells;
	    green = colrs[(int) *dptr].green / NCells;
	    blue = colrs[(int) *dptr].blue / NCells;
	    FindHash(red, green, blue, tptr);
	    if (tptr == NULL) {
		tptr = AddHash(red, green, blue);
		tptr->next = NULL;
		AddColor(tptr, 0);
		ColorCnt++;
	    }
	    dptr++;
	}
    }
}


void
MedianSplit(end_cnt)
int end_cnt;
{
    C_boxes[0].count = ColorCnt;
    SplitColors(end_cnt);
}


void
MedianConvert(data, w, h, colrs)
unsigned char *data;
int w, h;
struct colr_data *colrs;
{
    Width = w;
    Height = h;
    ConvertData(data, colrs);
}


void
MedianMerge(colrs, end_cnt)
struct colr_data *colrs;
int end_cnt;
{
    int i;

    PrintColormap(end_cnt, colrs);
    for (i = 0; i < 256; i++) {
	hash_ptr = Hash[i];
	while (hash_ptr != NULL) {
	    tptr = hash_ptr;
	    hash_ptr = hash_ptr->hash_next;
	    free((char *) tptr);
	}
    }
}
Commit	Line	Data
2ac45f02 MG	1	#include <stdio.h>
	2	#include <stdlib.h>
	3	#include "medcut.h"
	4
	5	#define RED 0
	6	#define GREEN 1
	7	#define BLUE 2
	8
	9	#define FindHash(red, green, blue, h_ptr) \
	10	h_ptr = Hash[((red * 299) + (green * 587) + (blue * 114)) / 1000 * NCells / 256]; \
	11	while(h_ptr != NULL) \
	12	{ \
	13	if ((h_ptr->pixel[RED] == red)&& \
	14	(h_ptr->pixel[GREEN] == green)&& \
	15	(h_ptr->pixel[BLUE] == blue)) \
	16	{ \
	17	break; \
	18	} \
	19	h_ptr = h_ptr->hash_next; \
	20	}
	21
	22	struct color_rec {
	23	int pixel[3];
	24	int box_num;
	25	struct color_rec *hash_next;
	26	struct color_rec *next;
	27	} *Hash[256];
	28	struct c_box_rec {
	29	int min_pix[3];
	30	int max_pix[3];
	31	int count;
	32	struct color_rec *c_data;
	33	} C_boxes[256];
	34
	35	int BoxCount;
	36	struct color_rec *hash_ptr;
	37	struct color_rec *tptr;
	38	static int Width, Height;
	39	int ColorCnt;
	40	int NCells;
	41	struct color_rec *Tptr;
	42
	43
	44	void
	45	InitMinMax(boxnum)
	46	int boxnum;
	47	{
	48	C_boxes[boxnum].min_pix[RED] = 256;
	49	C_boxes[boxnum].max_pix[RED] = 0;
	50	C_boxes[boxnum].min_pix[GREEN] = 256;
	51	C_boxes[boxnum].max_pix[GREEN] = 0;
	52	C_boxes[boxnum].min_pix[BLUE] = 256;
	53	C_boxes[boxnum].max_pix[BLUE] = 0;
	54	}
	55
	56
	57	struct color_rec *
	58	AddHash(red, green, blue)
	59	int red, green, blue;
	60	{
	61	int lum;
	62
	63	lum = ((red * 299) + (green * 587) + (blue * 114)) / 1000 * NCells / 256;;
	64	hash_ptr = (struct color_rec *) malloc(sizeof(struct color_rec));
65	if (hash_ptr == NULL) {
66	fprintf(stderr, "Cannot malloc %dth color\n", ColorCnt);
67	exit(1);
68	}
69	hash_ptr->pixel[RED] = red;
70	hash_ptr->pixel[GREEN] = green;
71	hash_ptr->pixel[BLUE] = blue;
72	hash_ptr->box_num = 0;
73	hash_ptr->next = NULL;
74	hash_ptr->hash_next = Hash[lum];
75	Hash[lum] = hash_ptr;
76	return (hash_ptr);
77	}
78
79
80	void
81	AddColor(cptr, boxnum)
82	struct color_rec *cptr;
83	int boxnum;
84	{
85	struct color_rec *ptr;
86
87	while (cptr != NULL) {
88	ptr = cptr;
89	cptr = cptr->next;
90	ptr->box_num = boxnum;
91	ptr->next = C_boxes[boxnum].c_data;
92	C_boxes[boxnum].c_data = ptr;
93	if (ptr->pixel[RED] < C_boxes[boxnum].min_pix[RED])
94	C_boxes[boxnum].min_pix[RED] = ptr->pixel[RED];
95	if (ptr->pixel[RED] > C_boxes[boxnum].max_pix[RED])
96	C_boxes[boxnum].max_pix[RED] = ptr->pixel[RED];
97	if (ptr->pixel[GREEN] < C_boxes[boxnum].min_pix[GREEN])
98	C_boxes[boxnum].min_pix[GREEN] = ptr->pixel[GREEN];
99	if (ptr->pixel[GREEN] > C_boxes[boxnum].max_pix[GREEN])
100	C_boxes[boxnum].max_pix[GREEN] = ptr->pixel[GREEN];
101	if (ptr->pixel[BLUE] < C_boxes[boxnum].min_pix[BLUE])
102	C_boxes[boxnum].min_pix[BLUE] = ptr->pixel[BLUE];
103	if (ptr->pixel[BLUE] > C_boxes[boxnum].max_pix[BLUE])
104	C_boxes[boxnum].max_pix[BLUE] = ptr->pixel[BLUE];
105	}
106	}
107
108
109	void
110	CountColors(data, colrs)
111	unsigned char *data;
112	struct colr_data *colrs;
113	{
114	unsigned char *dptr;
115	register int i, j;
116	int red, green, blue;
117	register struct color_rec *tptr;
118
119	InitMinMax(0);
120	C_boxes[0].c_data = NULL;
121	tptr = C_boxes[0].c_data;
122	ColorCnt = 0;
123
124	dptr = data;
125
126	for (j = 0; j < Height; j++) {
127	for (i = 0; i < Width; i++) {
128	red = colrs[(int) *dptr].red;
129	green = colrs[(int) *dptr].green;
130	blue = colrs[(int) *dptr].blue;
131	FindHash(red, green, blue, tptr);
132	if (tptr == NULL) {
133	tptr = AddHash(red, green, blue);
134	tptr->next = NULL;
135	AddColor(tptr, 0);
136	ColorCnt++;
137	}
138	dptr++;
139	}
140	}
141	}
142
143
144	int
145	FindTarget(tptr)
146	int *tptr;
147	{
148	int range, i, indx;
149
150	range = 0;
151	for (i = 0; i < BoxCount; i++) {
152	int rr, gr, br;
153
154	rr = C_boxes[i].max_pix[RED] - C_boxes[i].min_pix[RED];
155	gr = C_boxes[i].max_pix[GREEN] - C_boxes[i].min_pix[GREEN];
156	br = C_boxes[i].max_pix[BLUE] - C_boxes[i].min_pix[BLUE];
157	if (rr > range) {
158	range = rr;
159	*tptr = i;
160	indx = RED;
161	}
162	if (gr > range) {
163	range = gr;
164	*tptr = i;
165	indx = GREEN;
166	}
167	if (br > range) {
168	range = br;
169	*tptr = i;
170	indx = BLUE;
171	}
172	}
173	return (indx);
174	}
175
176
177	void
178	SplitBox(boxnum, color_indx)
179	int boxnum, color_indx;
180	{
181	struct color_rec low, high;
182	struct color_rec *data;
183	int med_cnt, split_val;
184	int low_cnt, high_cnt;
185	int Low_cnt, High_cnt;
186	int Greater, Lesser;
187
188	Greater = BoxCount++;
189	Lesser = boxnum;
190	InitMinMax(Lesser);
191	InitMinMax(Greater);
192	data = C_boxes[boxnum].c_data;
193	med_cnt = C_boxes[boxnum].count / 2;
194	C_boxes[Lesser].c_data = NULL;
195	C_boxes[Greater].c_data = NULL;
196	Low_cnt = 0;
197	High_cnt = 0;
198	while (med_cnt > 0) {
199	if (data->pixel[color_indx] < data->next->pixel[color_indx]) {
200	low = data;
201	high = data->next;
202	data = high->next;
203	} else {
204	high = data;
205	low = data->next;
206	data = low->next;
207	}
208	low->next = NULL;
209	high->next = NULL;
210	low_cnt = 1;
211	high_cnt = 1;
212	split_val = low->pixel[color_indx];
213	while (data != NULL) {
214	tptr = data;
215	data = data->next;
216	if (tptr->pixel[color_indx] > split_val) {
217	tptr->next = high;
218	high = tptr;
219	high_cnt++;
220	} else {
221	tptr->next = low;
222	low = tptr;
223	low_cnt++;
224	}
225	} /* end while data->next != NULL */
226	if (low_cnt <= med_cnt) {
227	AddColor(low, Lesser);
228	Low_cnt += low_cnt;
229	med_cnt -= low_cnt;
230	if (med_cnt == 0) {
231	AddColor(high, Greater);
232	High_cnt += high_cnt;
233	}
234	data = high;
235	} else {
236	AddColor(high, Greater);
237	High_cnt += high_cnt;
238	data = low;
239	}
240	} /* end while med_cnt */
241	C_boxes[Lesser].count = Low_cnt;
242	C_boxes[Greater].count = High_cnt;
243
244	}
245
246
247	void
248	SplitColors(e_cnt)
249	int e_cnt;
250	{
251	if (ColorCnt < e_cnt) {
252	int i;
253
254	tptr = C_boxes[0].c_data;
255	for (i = 0; i < ColorCnt; i++) {
256	hash_ptr = tptr;
257	tptr = tptr->next;
258	C_boxes[i].c_data = hash_ptr;
259	C_boxes[i].count = 1;
260	hash_ptr->box_num = i;
261	hash_ptr->next = NULL;
262	}
263	BoxCount = ColorCnt;
264	} else {
265	BoxCount = 1;
266	while (BoxCount < e_cnt) {
267	int target, color_indx;
268
269	target = 0;
270	color_indx = 0;
271	color_indx = FindTarget(&target);
272	SplitBox(target, color_indx);
273	}
274	}
275	}
276
277
278	/*
279	* Colors passed in 0-65535, internally are 0-255
280	*/
281	void
282	ConvertColor(rp, gp, bp)
283	int rp, gp, *bp;
284	{
285	struct color_rec *cptr;
286	register struct color_rec *hash_ptr;
287	int indx;
288	int red, green, blue;
289	int Tred, Tgreen, Tblue;
290	int c_cnt;
291
292	red = *rp / NCells;
293	green = *gp / NCells;
294	blue = *bp / NCells;
295	FindHash(red, green, blue, hash_ptr);
296	if (hash_ptr == NULL) {
297	fprintf(stderr, "Unknown color (%d,%d,%d)\n", red, green, blue);
298	hash_ptr = Hash[0];
299	}
300	indx = hash_ptr->box_num;
301	cptr = C_boxes[indx].c_data;
302	c_cnt = 0;
303	Tred = Tgreen = Tblue = 0;
304	while (cptr != NULL) {
305	Tred += cptr->pixel[RED];
306	Tgreen += cptr->pixel[GREEN];
307	Tblue += cptr->pixel[BLUE];
308	c_cnt++;
309	cptr = cptr->next;
310	}
311	if (c_cnt) {
312	red = Tred / c_cnt;
313	green = Tgreen / c_cnt;
314	blue = Tblue / c_cnt;
315	}
316
317	rp = red NCells;
318	gp = green NCells;
319	bp = blue NCells;
320	}
321
322
323	void
324	ConvertData(data, colrs)
325	unsigned char *data;
326	struct colr_data *colrs;
327	{
328	unsigned char *dptr;
329	register int i, j;
330	int red, green, blue;
331	register struct color_rec *hash_ptr;
332
333	dptr = data;
334
335	for (j = 0; j < Height; j++) {
336	for (i = 0; i < Width; i++) {
337	red = colrs[(int) *dptr].red;
338	green = colrs[(int) *dptr].green;
339	blue = colrs[(int) *dptr].blue;
340	FindHash(red, green, blue, hash_ptr);
341	if (hash_ptr == NULL) {
342	fprintf(stderr, "Unknown color (%d,%d,%d)\n", red, green, blue);
343	hash_ptr = Hash[0];
344	}
345	*dptr++ = (unsigned char) hash_ptr->box_num;
346	}
347	}
348	}
349
350
351	void
352	PrintColormap(e_cnt, colrs)
353	int e_cnt;
354	struct colr_data *colrs;
355	{
356	int i;
357
358	for (i = 0; i < BoxCount; i++) {
359	int Tred, Tgreen, Tblue;
360	int c_cnt;
361
362	c_cnt = 0;
363	Tred = Tgreen = Tblue = 0;
364	tptr = C_boxes[i].c_data;
365	while (tptr != NULL) {
366	Tred += tptr->pixel[RED];
367	Tgreen += tptr->pixel[GREEN];
368	Tblue += tptr->pixel[BLUE];
369	c_cnt++;
370	tptr = tptr->next;
371	}
372	colrs[i].red = Tred / c_cnt;
373	colrs[i].green = Tgreen / c_cnt;
374	colrs[i].blue = Tblue / c_cnt;
375	}
376	for (i = BoxCount; i < e_cnt; i++) {
377	colrs[i].red = 0;
378	colrs[i].green = 0;
379	colrs[i].blue = 0;
380	}
381	}
382
383
384	void
385	MedianCut(data, w, h, colrs, start_cnt, end_cnt)
386	unsigned char *data;
387	int w, h;
388	struct colr_data *colrs;
389	int start_cnt, end_cnt;
390	{
391	int i;
392
393	Width = *w;
394	Height = *h;
395	NCells = start_cnt;
396	BoxCount = 0;
397	ColorCnt = 0;
398	for (i = 0; i < 256; i++) {
399	Hash[i] = NULL;
400	C_boxes[i].c_data = NULL;
401	C_boxes[i].count = 0;
402	}
403	CountColors(data, colrs);
404	C_boxes[0].count = ColorCnt;
405	SplitColors(end_cnt);
406	ConvertData(data, colrs);
407	PrintColormap(end_cnt, colrs);
408	for (i = 0; i < 256; i++) {
409	hash_ptr = Hash[i];
410	while (hash_ptr != NULL) {
411	tptr = hash_ptr;
412	hash_ptr = hash_ptr->hash_next;
413	free((char *) tptr);
414	}
415	}
416	}
417
418
419	void
420	MedianInit()
421	{
422	int i;
423
424	NCells = 256;
425	BoxCount = 0;
426	ColorCnt = 0;
427	for (i = 0; i < 256; i++) {
428	Hash[i] = NULL;
429	C_boxes[i].c_data = NULL;
430	C_boxes[i].count = 0;
431	}
432	InitMinMax(0);
433	C_boxes[0].c_data = NULL;
434	Tptr = C_boxes[0].c_data;
435	}
436
437
438	/*
439	* colrs are passed on 0-65535, but this median cut only deals with
440	* 0-255.
441	*/
442	void
443	MedianCount(data, w, h, colrs)
444	unsigned char *data;
445	int w, h;
446	struct colr_data *colrs;
447	{
448	unsigned char *dptr;
449	register int i, j;
450	int red, green, blue;
451
452	Width = w;
453	Height = h;
454	dptr = data;
455
456	for (j = 0; j < Height; j++) {
457	for (i = 0; i < Width; i++) {
458	red = colrs[(int) *dptr].red / NCells;
459	green = colrs[(int) *dptr].green / NCells;
460	blue = colrs[(int) *dptr].blue / NCells;
461	FindHash(red, green, blue, tptr);
462	if (tptr == NULL) {
463	tptr = AddHash(red, green, blue);
464	tptr->next = NULL;
465	AddColor(tptr, 0);
466	ColorCnt++;
467	}
468	dptr++;
469	}
470	}
471	}
472
473
474	void
475	MedianSplit(end_cnt)
476	int end_cnt;
477	{
478	C_boxes[0].count = ColorCnt;
479	SplitColors(end_cnt);
480	}
481
482
483	void
484	MedianConvert(data, w, h, colrs)
485	unsigned char *data;
486	int w, h;
487	struct colr_data *colrs;
488	{
489	Width = w;
490	Height = h;
491	ConvertData(data, colrs);
492	}
493
494
495	void
496	MedianMerge(colrs, end_cnt)
497	struct colr_data *colrs;
498	int end_cnt;
499	{
500	int i;
501
502	PrintColormap(end_cnt, colrs);
503	for (i = 0; i < 256; i++) {
504	hash_ptr = Hash[i];
505	while (hash_ptr != NULL) {
506	tptr = hash_ptr;
507	hash_ptr = hash_ptr->hash_next;
508	free((char *) tptr);
509	}
510	}
511	}