Mercurial > hg > xemacs-beta

comparison src/imgproc.c @ 269:b2472a1930f2 r20-5b33

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r20-5b33
author cvs
date Mon, 13 Aug 2007 10:27:19 +0200
parents 966663fcf606
children c5d627a313b1
comparison
equal deleted inserted replaced
268:6ced69ccd85f 269:b2472a1930f2
42 42
43 #include <config.h> 43 #include <config.h>
44 #include "lisp.h" 44 #include "lisp.h"
45 #include "imgproc.h" 45 #include "imgproc.h"
46 46
47 static void get_histogram(quant_table *qt, unsigned char *pic, 47 static void
48 int width, int height, Colorbox* box) 48 get_histogram(quant_table *qt, unsigned char *pic,
49 int width, int height, Colorbox* box)
49 { 50 {
50 register unsigned char *inptr; 51 register unsigned char *inptr;
51 register int red, green, blue; 52 register int red, green, blue;
52 register unsigned int j, i; 53 register unsigned int j, i;
53 54
54 box->rmin = box->gmin = box->bmin = 999; 55 box->rmin = box->gmin = box->bmin = 999;
55 box->rmax = box->gmax = box->bmax = -1; 56 box->rmax = box->gmax = box->bmax = -1;
56 box->total = width * height; 57 box->total = width * height;
57 58
58 {
59 register int *ptr = &(qt->histogram[0][0][0]);
60 for (i = B_LEN*B_LEN*B_LEN; i-- > 0;)
61 *ptr++ = 0;
62 }
63 inptr = pic; 59 inptr = pic;
64 for (i = 0; i < height; i++) { 60 for (i = 0; i < height; i++)
65 for (j = width; j-- > 0;) { 61 {
66 red = *inptr++ >> COLOR_SHIFT; 62 for (j = width; j-- > 0;)
67 green = *inptr++ >> COLOR_SHIFT; 63 {
68 blue = *inptr++ >> COLOR_SHIFT; 64 red = *inptr++ >> COLOR_SHIFT;
69 if (red < box->rmin) 65 green = *inptr++ >> COLOR_SHIFT;
70 box->rmin = red; 66 blue = *inptr++ >> COLOR_SHIFT;
71 if (red > box->rmax) 67 if (red < box->rmin)
72 box->rmax = red; 68 box->rmin = red;
73 if (green < box->gmin) 69 if (red > box->rmax)
74 box->gmin = green; 70 box->rmax = red;
75 if (green > box->gmax) 71 if (green < box->gmin)
76 box->gmax = green; 72 box->gmin = green;
77 if (blue < box->bmin) 73 if (green > box->gmax)
78 box->bmin = blue; 74 box->gmax = green;
79 if (blue > box->bmax) 75 if (blue < box->bmin)
80 box->bmax = blue; 76 box->bmin = blue;
81 qt->histogram[red][green][blue]++; 77 if (blue > box->bmax)
82 } 78 box->bmax = blue;
83 } 79 qt->histogram[red][green][blue]++;
80 }
81 }
84 } 82 }
85 83
86 static Colorbox * 84 static Colorbox *
87 largest_box(quant_table *qt) 85 largest_box(quant_table *qt)
88 { 86 {
101 static void 99 static void
102 shrinkbox(quant_table *qt, Colorbox* box) 100 shrinkbox(quant_table *qt, Colorbox* box)
103 { 101 {
104 register int *histp, ir, ig, ib; 102 register int *histp, ir, ig, ib;
105 103
106 if (box->rmax > box->rmin) { 104 if (box->rmax > box->rmin)
107 for (ir = box->rmin; ir <= box->rmax; ++ir) 105 {
108 for (ig = box->gmin; ig <= box->gmax; ++ig) { 106 for (ir = box->rmin; ir <= box->rmax; ++ir)
109 histp = &(qt->histogram[ir][ig][box->bmin]); 107 for (ig = box->gmin; ig <= box->gmax; ++ig)
110 for (ib = box->bmin; ib <= box->bmax; ++ib) 108 {
111 if (*histp++ != 0) { 109 histp = &(qt->histogram[ir][ig][box->bmin]);
112 box->rmin = ir; 110 for (ib = box->bmin; ib <= box->bmax; ++ib)
113 goto have_rmin; 111 if (*histp++ != 0)
112 {
113 box->rmin = ir;
114 goto have_rmin;
115 }
114 } 116 }
115 } 117 have_rmin:
116 have_rmin: 118 if (box->rmax > box->rmin)
117 if (box->rmax > box->rmin) 119 for (ir = box->rmax; ir >= box->rmin; --ir)
118 for (ir = box->rmax; ir >= box->rmin; --ir) 120 for (ig = box->gmin; ig <= box->gmax; ++ig)
119 for (ig = box->gmin; ig <= box->gmax; ++ig) { 121 {
120 histp = &(qt->histogram[ir][ig][box->bmin]); 122 histp = &(qt->histogram[ir][ig][box->bmin]);
121 ib = box->bmin; 123 ib = box->bmin;
122 for (; ib <= box->bmax; ++ib) 124 for (; ib <= box->bmax; ++ib)
123 if (*histp++ != 0) { 125 if (*histp++ != 0)
124 box->rmax = ir; 126 {
125 goto have_rmax; 127 box->rmax = ir;
126 } 128 goto have_rmax;
127 } 129 }
128 } 130 }
131 }
129 have_rmax: 132 have_rmax:
130 if (box->gmax > box->gmin) { 133 if (box->gmax > box->gmin)
131 for (ig = box->gmin; ig <= box->gmax; ++ig) 134 {
132 for (ir = box->rmin; ir <= box->rmax; ++ir) { 135 for (ig = box->gmin; ig <= box->gmax; ++ig)
133 histp = &(qt->histogram[ir][ig][box->bmin]); 136 for (ir = box->rmin; ir <= box->rmax; ++ir)
134 for (ib = box->bmin; ib <= box->bmax; ++ib) 137 {
135 if (*histp++ != 0) { 138 histp = &(qt->histogram[ir][ig][box->bmin]);
136 box->gmin = ig; 139 for (ib = box->bmin; ib <= box->bmax; ++ib)
137 goto have_gmin; 140 if (*histp++ != 0)
141 {
142 box->gmin = ig;
143 goto have_gmin;
144 }
138 } 145 }
139 } 146 have_gmin:
140 have_gmin: 147 if (box->gmax > box->gmin)
141 if (box->gmax > box->gmin) 148 for (ig = box->gmax; ig >= box->gmin; --ig)
142 for (ig = box->gmax; ig >= box->gmin; --ig) 149 for (ir = box->rmin; ir <= box->rmax; ++ir)
143 for (ir = box->rmin; ir <= box->rmax; ++ir) { 150 {
144 histp = &(qt->histogram[ir][ig][box->bmin]); 151 histp = &(qt->histogram[ir][ig][box->bmin]);
145 ib = box->bmin; 152 ib = box->bmin;
146 for (; ib <= box->bmax; ++ib) 153 for (; ib <= box->bmax; ++ib)
147 if (*histp++ != 0) { 154 if (*histp++ != 0)
148 box->gmax = ig; 155 {
149 goto have_gmax; 156 box->gmax = ig;
150 } 157 goto have_gmax;
151 } 158 }
152 } 159 }
160 }
153 have_gmax: 161 have_gmax:
154 if (box->bmax > box->bmin) { 162 if (box->bmax > box->bmin)
155 for (ib = box->bmin; ib <= box->bmax; ++ib) 163 {
156 for (ir = box->rmin; ir <= box->rmax; ++ir) { 164 for (ib = box->bmin; ib <= box->bmax; ++ib)
157 histp = &(qt->histogram[ir][box->gmin][ib]); 165 for (ir = box->rmin; ir <= box->rmax; ++ir)
158 for (ig = box->gmin; ig <= box->gmax; ++ig) { 166 {
159 if (*histp != 0) { 167 histp = &(qt->histogram[ir][box->gmin][ib]);
160 box->bmin = ib; 168 for (ig = box->gmin; ig <= box->gmax; ++ig)
161 goto have_bmin; 169 {
170 if (*histp != 0)
171 {
172 box->bmin = ib;
173 goto have_bmin;
174 }
175 histp += B_LEN;
176 }
162 } 177 }
163 histp += B_LEN; 178 have_bmin:
164 } 179 if (box->bmax > box->bmin)
165 } 180 for (ib = box->bmax; ib >= box->bmin; --ib)
166 have_bmin: 181 for (ir = box->rmin; ir <= box->rmax; ++ir)
167 if (box->bmax > box->bmin) 182 {
168 for (ib = box->bmax; ib >= box->bmin; --ib) 183 histp = &(qt->histogram[ir][box->gmin][ib]);
169 for (ir = box->rmin; ir <= box->rmax; ++ir) { 184 ig = box->gmin;
170 histp = &(qt->histogram[ir][box->gmin][ib]); 185 for (; ig <= box->gmax; ++ig)
171 ig = box->gmin; 186 {
172 for (; ig <= box->gmax; ++ig) { 187 if (*histp != 0)
173 if (*histp != 0) { 188 {
174 box->bmax = ib; 189 box->bmax = ib;
175 goto have_bmax; 190 goto have_bmax;
176 } 191 }
177 histp += B_LEN; 192 histp += B_LEN;
178 } 193 }
179 } 194 }
180 } 195 }
181 have_bmax: 196 have_bmax:
182 ; 197 ;
183 } 198 }
184 199
185 static void 200 static void
205 else if (ptr->gmax - ptr->gmin >= ptr->bmax - ptr->bmin) 220 else if (ptr->gmax - ptr->gmin >= ptr->bmax - ptr->bmin)
206 axis = GREEN; 221 axis = GREEN;
207 else 222 else
208 axis = BLUE; 223 axis = BLUE;
209 /* get histogram along longest axis */ 224 /* get histogram along longest axis */
210 switch (axis) { 225 switch (axis)
211 case RED: 226 {
212 histp = &hist2[ptr->rmin]; 227 case RED:
213 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) { 228 histp = &hist2[ptr->rmin];
214 *histp = 0; 229 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir)
215 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) { 230 {
216 iptr = &(qt->histogram[ir][ig][ptr->bmin]); 231 *histp = 0;
217 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) 232 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig)
218 *histp += *iptr++; 233 {
219 } 234 iptr = &(qt->histogram[ir][ig][ptr->bmin]);
220 histp++; 235 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
221 } 236 *histp += *iptr++;
222 first = ptr->rmin; 237 }
223 last = ptr->rmax; 238 histp++;
224 break;
225 case GREEN:
226 histp = &hist2[ptr->gmin];
227 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
228 *histp = 0;
229 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
230 iptr = &(qt->histogram[ir][ig][ptr->bmin]);
231 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
232 *histp += *iptr++;
233 }
234 histp++;
235 }
236 first = ptr->gmin;
237 last = ptr->gmax;
238 break;
239 case BLUE:
240 histp = &hist2[ptr->bmin];
241 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) {
242 *histp = 0;
243 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
244 iptr = &(qt->histogram[ir][ptr->gmin][ib]);
245 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
246 *histp += *iptr;
247 iptr += B_LEN;
248 } 239 }
249 } 240 first = ptr->rmin;
250 histp++; 241 last = ptr->rmax;
251 } 242 break;
252 first = ptr->bmin; 243 case GREEN:
253 last = ptr->bmax; 244 histp = &hist2[ptr->gmin];
254 break; 245 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig)
255 } 246 {
247 *histp = 0;
248 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir)
249 {
250 iptr = &(qt->histogram[ir][ig][ptr->bmin]);
251 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
252 *histp += *iptr++;
253 }
254 histp++;
255 }
256 first = ptr->gmin;
257 last = ptr->gmax;
258 break;
259 case BLUE:
260 histp = &hist2[ptr->bmin];
261 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
262 {
263 *histp = 0;
264 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir)
265 {
266 iptr = &(qt->histogram[ir][ptr->gmin][ib]);
267 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig)
268 {
269 *histp += *iptr;
270 iptr += B_LEN;
271 }
272 }
273 histp++;
274 }
275 first = ptr->bmin;
276 last = ptr->bmax;
277 break;
278 }
256 /* find median point */ 279 /* find median point */
257 sum2 = ptr->total / 2; 280 sum2 = ptr->total / 2;
258 histp = &hist2[first]; 281 histp = &hist2[first];
259 sum = 0; 282 sum = 0;
260 for (i = first; i <= last && (sum += *histp++) < sum2; ++i) 283 for (i = first; i <= last && (sum += *histp++) < sum2; ++i)
284 new->rmax = ptr->rmax; 307 new->rmax = ptr->rmax;
285 new->gmin = ptr->gmin; 308 new->gmin = ptr->gmin;
286 new->gmax = ptr->gmax; 309 new->gmax = ptr->gmax;
287 new->bmin = ptr->bmin; 310 new->bmin = ptr->bmin;
288 new->bmax = ptr->bmax; 311 new->bmax = ptr->bmax;
289 switch (axis) { 312 switch (axis)
290 case RED: 313 {
291 new->rmax = i-1; 314 case RED:
292 ptr->rmin = i; 315 new->rmax = i-1;
293 break; 316 ptr->rmin = i;
294 case GREEN: 317 break;
295 new->gmax = i-1; 318 case GREEN:
296 ptr->gmin = i; 319 new->gmax = i-1;
297 break; 320 ptr->gmin = i;
298 case BLUE: 321 break;
299 new->bmax = i-1; 322 case BLUE:
300 ptr->bmin = i; 323 new->bmax = i-1;
301 break; 324 ptr->bmin = i;
302 } 325 break;
303 shrinkbox(qt, new); 326 }
304 shrinkbox(qt, ptr); 327 shrinkbox (qt, new);
328 shrinkbox (qt, ptr);
305 } 329 }
306 330
307 331
308 static C_cell * 332 static C_cell *
309 create_colorcell(quant_table *qt, int num_colors, int red, int green, int blue) 333 create_colorcell(quant_table *qt, int num_colors, int red, int green, int blue)
323 /* 347 /*
324 * Step 1: find all colors inside this cell, while we're at 348 * Step 1: find all colors inside this cell, while we're at
325 * it, find distance of centermost point to furthest corner 349 * it, find distance of centermost point to furthest corner
326 */ 350 */
327 mindist = 99999999; 351 mindist = 99999999;
328 for (i = 0; i < num_colors; ++i) { 352 for (i = 0; i < num_colors; ++i)
329 if (qt->rm[i]>>(COLOR_DEPTH-C_DEPTH) != ir || 353 {
330 qt->gm[i]>>(COLOR_DEPTH-C_DEPTH) != ig || 354 if (qt->rm[i]>>(COLOR_DEPTH-C_DEPTH) != ir ||
331 qt->bm[i]>>(COLOR_DEPTH-C_DEPTH) != ib) 355 qt->gm[i]>>(COLOR_DEPTH-C_DEPTH) != ig ||
332 continue; 356 qt->bm[i]>>(COLOR_DEPTH-C_DEPTH) != ib)
333 ptr->entries[ptr->num_ents][0] = i; 357 continue;
334 ptr->entries[ptr->num_ents][1] = 0; 358 ptr->entries[ptr->num_ents][0] = i;
335 ++ptr->num_ents; 359 ptr->entries[ptr->num_ents][1] = 0;
336 tmp = qt->rm[i] - red; 360 ++ptr->num_ents;
337 if (tmp < (MAX_COLOR/C_LEN/2)) 361 tmp = qt->rm[i] - red;
338 tmp = MAX_COLOR/C_LEN-1 - tmp; 362 if (tmp < (MAX_COLOR/C_LEN/2))
339 dist = tmp*tmp; 363 tmp = MAX_COLOR/C_LEN-1 - tmp;
340 tmp = qt->gm[i] - green; 364 dist = tmp*tmp;
341 if (tmp < (MAX_COLOR/C_LEN/2)) 365 tmp = qt->gm[i] - green;
342 tmp = MAX_COLOR/C_LEN-1 - tmp; 366 if (tmp < (MAX_COLOR/C_LEN/2))
343 dist += tmp*tmp; 367 tmp = MAX_COLOR/C_LEN-1 - tmp;
344 tmp = qt->bm[i] - blue; 368 dist += tmp*tmp;
345 if (tmp < (MAX_COLOR/C_LEN/2)) 369 tmp = qt->bm[i] - blue;
346 tmp = MAX_COLOR/C_LEN-1 - tmp; 370 if (tmp < (MAX_COLOR/C_LEN/2))
347 dist += tmp*tmp; 371 tmp = MAX_COLOR/C_LEN-1 - tmp;
348 if (dist < mindist) 372 dist += tmp*tmp;
349 mindist = dist; 373 if (dist < mindist)
350 } 374 mindist = dist;
375 }
351 376
352 /* 377 /*
353 * Step 3: find all points within that distance to cell. 378 * Step 3: find all points within that distance to cell.
354 */ 379 */
355 for (i = 0; i < num_colors; ++i) { 380 for (i = 0; i < num_colors; ++i)
356 if (qt->rm[i] >> (COLOR_DEPTH-C_DEPTH) == ir && 381 {
357 qt->gm[i] >> (COLOR_DEPTH-C_DEPTH) == ig && 382 if (qt->rm[i] >> (COLOR_DEPTH-C_DEPTH) == ir &&
358 qt->bm[i] >> (COLOR_DEPTH-C_DEPTH) == ib) 383 qt->gm[i] >> (COLOR_DEPTH-C_DEPTH) == ig &&
359 continue; 384 qt->bm[i] >> (COLOR_DEPTH-C_DEPTH) == ib)
360 dist = 0; 385 continue;
361 if ((tmp = red - qt->rm[i]) > 0 || 386 dist = 0;
362 (tmp = qt->rm[i] - (red + MAX_COLOR/C_LEN-1)) > 0 ) 387 if ((tmp = red - qt->rm[i]) > 0 ||
363 dist += tmp*tmp; 388 (tmp = qt->rm[i] - (red + MAX_COLOR/C_LEN-1)) > 0 )
364 if ((tmp = green - qt->gm[i]) > 0 || 389 dist += tmp*tmp;
365 (tmp = qt->gm[i] - (green + MAX_COLOR/C_LEN-1)) > 0 ) 390 if ((tmp = green - qt->gm[i]) > 0 ||
366 dist += tmp*tmp; 391 (tmp = qt->gm[i] - (green + MAX_COLOR/C_LEN-1)) > 0 )
367 if ((tmp = blue - qt->bm[i]) > 0 || 392 dist += tmp*tmp;
368 (tmp = qt->bm[i] - (blue + MAX_COLOR/C_LEN-1)) > 0 ) 393 if ((tmp = blue - qt->bm[i]) > 0 ||
369 dist += tmp*tmp; 394 (tmp = qt->bm[i] - (blue + MAX_COLOR/C_LEN-1)) > 0 )
370 if (dist < mindist) { 395 dist += tmp*tmp;
371 ptr->entries[ptr->num_ents][0] = i; 396 if (dist < mindist)
372 ptr->entries[ptr->num_ents][1] = dist; 397 {
373 ++ptr->num_ents; 398 ptr->entries[ptr->num_ents][0] = i;
374 } 399 ptr->entries[ptr->num_ents][1] = dist;
375 } 400 ++ptr->num_ents;
401 }
402 }
376 403
377 /* 404 /*
378 * Sort color cells by distance, use cheap exchange sort 405 * Sort color cells by distance, use cheap exchange sort
379 */ 406 */
380 for (n = ptr->num_ents - 1; n > 0; n = next_n) { 407 for (n = ptr->num_ents - 1; n > 0; n = next_n)
381 next_n = 0; 408 {
382 for (i = 0; i < n; ++i) 409 next_n = 0;
383 if (ptr->entries[i][1] > ptr->entries[i+1][1]) { 410 for (i = 0; i < n; ++i)
384 tmp = ptr->entries[i][0]; 411 if (ptr->entries[i][1] > ptr->entries[i+1][1])
385 ptr->entries[i][0] = ptr->entries[i+1][0]; 412 {
386 ptr->entries[i+1][0] = tmp; 413 tmp = ptr->entries[i][0];
387 tmp = ptr->entries[i][1]; 414 ptr->entries[i][0] = ptr->entries[i+1][0];
388 ptr->entries[i][1] = ptr->entries[i+1][1]; 415 ptr->entries[i+1][0] = tmp;
389 ptr->entries[i+1][1] = tmp; 416 tmp = ptr->entries[i][1];
390 next_n = i; 417 ptr->entries[i][1] = ptr->entries[i+1][1];
391 } 418 ptr->entries[i+1][1] = tmp;
392 } 419 next_n = i;
420 }
421 }
393 return (ptr); 422 return (ptr);
394 } 423 }
395 424
396 static int 425 static int
397 map_colortable(quant_table *qt, int num_colors) 426 map_colortable(quant_table *qt, int num_colors)
401 register int j, tmp, d2, dist; 430 register int j, tmp, d2, dist;
402 int ir, ig, ib, i; 431 int ir, ig, ib, i;
403 432
404 for (ir = 0; ir < B_LEN; ++ir) 433 for (ir = 0; ir < B_LEN; ++ir)
405 for (ig = 0; ig < B_LEN; ++ig) 434 for (ig = 0; ig < B_LEN; ++ig)
406 for (ib = 0; ib < B_LEN; ++ib, histp++) { 435 for (ib = 0; ib < B_LEN; ++ib, histp++)
407 if (*histp == 0) { 436 {
408 *histp = -1; 437 if (*histp == 0)
409 continue; 438 {
439 *histp = -1;
440 continue;
441 }
442 cell = *(qt->ColorCells +
443 (((ir>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2) +
444 ((ig>>(B_DEPTH-C_DEPTH)) << C_DEPTH) +
445 (ib>>(B_DEPTH-C_DEPTH))));
446 if (cell == NULL )
447 cell = create_colorcell (qt, num_colors,
448 ir << COLOR_SHIFT,
449 ig << COLOR_SHIFT,
450 ib << COLOR_SHIFT);
451 if (cell == NULL) /* memory exhausted! punt! */
452 return -1;
453 dist = 9999999;
454 for (i = 0; i < cell->num_ents &&
455 dist > cell->entries[i][1]; ++i)
456 {
457 j = cell->entries[i][0];
458 d2 = qt->rm[j] - (ir << COLOR_SHIFT);
459 d2 *= d2;
460 tmp = qt->gm[j] - (ig << COLOR_SHIFT);
461 d2 += tmp*tmp;
462 tmp = qt->bm[j] - (ib << COLOR_SHIFT);
463 d2 += tmp*tmp;
464 if (d2 < dist)
465 {
466 dist = d2;
467 *histp = j;
468 }
469 }
410 } 470 }
411 cell = *(qt->ColorCells +
412 (((ir>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2) +
413 ((ig>>(B_DEPTH-C_DEPTH)) << C_DEPTH) +
414 (ib>>(B_DEPTH-C_DEPTH))));
415 if (cell == NULL )
416 cell = create_colorcell(qt, num_colors,
417 ir << COLOR_SHIFT,
418 ig << COLOR_SHIFT,
419 ib << COLOR_SHIFT);
420 if (cell == NULL) /* memory exhausted! punt! */
421 return -1;
422 dist = 9999999;
423 for (i = 0; i < cell->num_ents &&
424 dist > cell->entries[i][1]; ++i) {
425 j = cell->entries[i][0];
426 d2 = qt->rm[j] - (ir << COLOR_SHIFT);
427 d2 *= d2;
428 tmp = qt->gm[j] - (ig << COLOR_SHIFT);
429 d2 += tmp*tmp;
430 tmp = qt->bm[j] - (ib << COLOR_SHIFT);
431 d2 += tmp*tmp;
432 if (d2 < dist) {
433 dist = d2;
434 *histp = j;
435 }
436 }
437 }
438 return 0; 471 return 0;
439 } 472 }
440 473
441 quant_table *EImage_build_quantable(unsigned char *eimage, int width, int height, int num_colors) 474 quant_table *
475 build_EImage_quantable(unsigned char *eimage, int width, int height, int num_colors)
442 { 476 {
443 quant_table *qt; 477 quant_table *qt;
444 Colorbox *box_list, *ptr; 478 Colorbox *box_list, *ptr;
445 int i,res; 479 int i,res;
446 480
447 qt = (quant_table*)xmalloc(sizeof(quant_table)); 481 qt = (quant_table*)xmalloc_and_zero (sizeof(quant_table));
448 if (qt == NULL) return NULL; 482 if (qt == NULL) return NULL;
449 483
450 assert (num_colors < 257 && num_colors > 2); 484 assert (num_colors < 257 && num_colors > 2);
451 /* 485 /*
452 * STEP 1: create empty boxes 486 * STEP 1: create empty boxes
453 */ 487 */
454 qt->usedboxes = NULL; 488 qt->usedboxes = NULL;
455 box_list = qt->freeboxes = (Colorbox *)xmalloc(num_colors*sizeof (Colorbox)); 489 box_list = qt->freeboxes = (Colorbox *)xmalloc (num_colors*sizeof (Colorbox));
456 qt->freeboxes[0].next = &(qt->freeboxes[1]); 490 qt->freeboxes[0].next = &(qt->freeboxes[1]);
457 qt->freeboxes[0].prev = NULL; 491 qt->freeboxes[0].prev = NULL;
458 for (i = 1; i < num_colors-1; ++i) { 492 for (i = 1; i < num_colors-1; ++i)
459 qt->freeboxes[i].next = &(qt->freeboxes[i+1]); 493 {
460 qt->freeboxes[i].prev = &(qt->freeboxes[i-1]); 494 qt->freeboxes[i].next = &(qt->freeboxes[i+1]);
461 } 495 qt->freeboxes[i].prev = &(qt->freeboxes[i-1]);
496 }
462 qt->freeboxes[num_colors-1].next = NULL; 497 qt->freeboxes[num_colors-1].next = NULL;
463 qt->freeboxes[num_colors-1].prev = &(qt->freeboxes[num_colors-2]); 498 qt->freeboxes[num_colors-1].prev = &(qt->freeboxes[num_colors-2]);
464 499
465 /* 500 /*
466 * STEP 2: get histogram, initialize first box 501 * STEP 2: get histogram, initialize first box
471 qt->freeboxes->prev = NULL; 506 qt->freeboxes->prev = NULL;
472 ptr->next = qt->usedboxes; 507 ptr->next = qt->usedboxes;
473 qt->usedboxes = ptr; 508 qt->usedboxes = ptr;
474 if (ptr->next) 509 if (ptr->next)
475 ptr->next->prev = ptr; 510 ptr->next->prev = ptr;
476 get_histogram(qt, eimage, width, height, ptr); 511 get_histogram (qt, eimage, width, height, ptr);
477 512
478 /* 513 /*
479 * STEP 3: continually subdivide boxes until no more free 514 * STEP 3: continually subdivide boxes until no more free
480 * boxes remain or until all colors assigned. 515 * boxes remain or until all colors assigned.
481 */ 516 */
482 while (qt->freeboxes != NULL) { 517 while (qt->freeboxes != NULL)
483 ptr = largest_box(qt); 518 {
484 if (ptr != NULL) 519 ptr = largest_box(qt);
485 splitbox(qt, ptr); 520 if (ptr != NULL)
486 else 521 splitbox (qt, ptr);
487 qt->freeboxes = NULL; 522 else
488 } 523 qt->freeboxes = NULL;
524 }
489 525
490 /* 526 /*
491 * STEP 4: assign colors to all boxes 527 * STEP 4: assign colors to all boxes
492 */ 528 */
493 for (i = 0, ptr = qt->usedboxes; ptr != NULL; ++i, ptr = ptr->next) { 529 for (i = 0, ptr = qt->usedboxes; ptr != NULL; ++i, ptr = ptr->next)
494 qt->rm[i] = ((ptr->rmin + ptr->rmax) << COLOR_SHIFT) / 2; 530 {
495 qt->gm[i] = ((ptr->gmin + ptr->gmax) << COLOR_SHIFT) / 2; 531 qt->rm[i] = ((ptr->rmin + ptr->rmax) << COLOR_SHIFT) / 2;
496 qt->bm[i] = ((ptr->bmin + ptr->bmax) << COLOR_SHIFT) / 2; 532 qt->gm[i] = ((ptr->gmin + ptr->gmax) << COLOR_SHIFT) / 2;
497 qt->um[i] = ptr->total; 533 qt->bm[i] = ((ptr->bmin + ptr->bmax) << COLOR_SHIFT) / 2;
498 } 534 qt->um[i] = ptr->total;
535 }
499 qt->num_active_colors = i; 536 qt->num_active_colors = i;
500 537
501 /* We're done with the boxes now */ 538 /* We're done with the boxes now */
502 xfree(box_list); 539 xfree (box_list);
503 qt->freeboxes = qt->usedboxes = NULL; 540 qt->freeboxes = qt->usedboxes = NULL;
504 541
505 /* 542 /*
506 * STEP 5: scan histogram and map all values to closest color 543 * STEP 5: scan histogram and map all values to closest color
507 */ 544 */
508 /* 5a: create cell list as described in Heckbert */ 545 /* 5a: create cell list as described in Heckbert */
509 qt->ColorCells = (C_cell **)xmalloc(C_LEN*C_LEN*C_LEN*sizeof (C_cell*)); 546 qt->ColorCells = (C_cell **)xmalloc_and_zero (C_LEN*C_LEN*C_LEN*sizeof (C_cell*));
510 memset(qt->ColorCells, 0, C_LEN*C_LEN*C_LEN*sizeof (C_cell*));
511 /* 5b: create mapping from truncated pixel space to color 547 /* 5b: create mapping from truncated pixel space to color
512 table entries */ 548 table entries */
513 res = map_colortable(qt, num_colors); 549 res = map_colortable (qt, num_colors);
514 550
515 /* 5c: done with ColorCells */ 551 /* 5c: done with ColorCells */
516 for (i = 0; i < C_LEN*C_LEN*C_LEN; i++) if (qt->ColorCells[i]) xfree(qt->ColorCells[i]); 552 for (i = 0; i < C_LEN*C_LEN*C_LEN; i++)
517 xfree(qt->ColorCells); 553 if (qt->ColorCells[i]) xfree (qt->ColorCells[i]);
554 xfree (qt->ColorCells);
518 555
519 if (res) { 556 if (res)
520 /* we failed in memory allocation, so clean up an leave */ 557 {
521 xfree(qt); 558 /* we failed in memory allocation, so clean up an leave */
522 return NULL; 559 xfree(qt);
523 } 560 return NULL;
561 }
524 562
525 return qt; 563 return qt;
526 } 564 }