1 /*
2 * Apply median cut on an image.
3 *
4 * tiffmedian [-c n] [-f] input output
5 * -C n - set colortable size. Default is 256.
6 * -f - use Floyd-Steinberg dithering.
7 * -c lzw - compress output with LZW
8 * -c none - use no compression on output
9 * -c packbits - use packbits compression on output
10 * -r n - create output with n rows/strip of data
11 * (by default the compression scheme and rows/strip are taken
12 * from the input file)
13 *
14 * Notes:
15 *
16 * [1] Floyd-Steinberg dither:
17 * I should point out that the actual fractions we used were, assuming
18 * you are at X, moving left to right:
19 *
20 * X 7/16
21 * 3/16 5/16 1/16
22 *
23 * Note that the error goes to four neighbors, not three. I think this
24 * will probably do better (at least for black and white) than the
25 * 3/8-3/8-1/4 distribution, at the cost of greater processing. I have
26 * seen the 3/8-3/8-1/4 distribution described as "our" algorithm before,
27 * but I have no idea who the credit really belongs to.
28
29 * Also, I should add that if you do zig-zag scanning (see my immediately
30 * previous message), it is sufficient (but not quite as good) to send
31 * half the error one pixel ahead (e.g. to the right on lines you scan
32 * left to right), and half one pixel straight down. Again, this is for
33 * black and white; I've not tried it with color.
34 * --
35 * Lou Steinberg
36 *
37 * [2] Color Image Quantization for Frame Buffer Display, Paul Heckbert,
38 * Siggraph '82 proceedings, pp. 297-307
39 */
40
41 #include "tif_config.h"
42 #include "libport.h"
43
44 #include <stdio.h>
45 #include <stdlib.h>
46 #include <string.h>
47
48 #ifdef HAVE_UNISTD_H
49 # include <unistd.h>
50 #endif
51
52 #include "tiffio.h"
53
54 #ifndef EXIT_SUCCESS
55 #define EXIT_SUCCESS 0
56 #endif
57 #ifndef EXIT_FAILURE
58 #define EXIT_FAILURE 1
59 #endif
60
61 #define MAX_CMAP_SIZE 256
62
63 #define streq(a,b) (strcmp(a,b) == 0)
64 #define strneq(a,b,n) (strncmp(a,b,n) == 0)
65
66 #define COLOR_DEPTH 8
67 #define MAX_COLOR 256
68
69 #define B_DEPTH 5 /* # bits/pixel to use */
70 #define B_LEN (1L<<B_DEPTH)
71
72 #define C_DEPTH 2
73 #define C_LEN (1L<<C_DEPTH) /* # cells/color to use */
74
75 #define COLOR_SHIFT (COLOR_DEPTH-B_DEPTH)
76
77 typedef struct colorbox {
78 struct colorbox *next, *prev;
79 int rmin, rmax;
80 int gmin, gmax;
81 int bmin, bmax;
82 uint32_t total;
83 } Colorbox;
84
85 typedef struct {
86 int num_ents;
87 int entries[MAX_CMAP_SIZE][2];
88 } C_cell;
89
90 static uint16_t rm[MAX_CMAP_SIZE], gm[MAX_CMAP_SIZE], bm[MAX_CMAP_SIZE];
91 static int num_colors;
92 static uint32_t histogram[B_LEN][B_LEN][B_LEN];
93 static Colorbox *freeboxes;
94 static Colorbox *usedboxes;
95 static C_cell **ColorCells;
96 static TIFF *in, *out;
97 static uint32_t rowsperstrip = (uint32_t) -1;
98 static uint16_t compression = (uint16_t) -1;
99 static uint16_t bitspersample = 1;
100 static uint16_t samplesperpixel;
101 static uint32_t imagewidth;
102 static uint32_t imagelength;
103 static uint16_t predictor = 0;
104
105 static void get_histogram(TIFF*, Colorbox*);
106 static void splitbox(Colorbox*);
107 static void shrinkbox(Colorbox*);
108 static void map_colortable(void);
109 static void quant(TIFF*, TIFF*);
110 static void quant_fsdither(TIFF*, TIFF*);
111 static Colorbox* largest_box(void);
112
113 static void usage(int);
114 static int processCompressOptions(char*);
115
116 #define CopyField(tag, v) \
117 if (TIFFGetField(in, tag, &v)) TIFFSetField(out, tag, v)
118
119 int
main(int argc,char * argv[])120 main(int argc, char* argv[])
121 {
122 int i, dither = 0;
123 uint16_t shortv, config, photometric;
124 Colorbox *box_list, *ptr;
125 float floatv;
126 uint32_t longv;
127 int c;
128 #if !HAVE_DECL_OPTARG
129 extern int optind;
130 extern char* optarg;
131 #endif
132
133 num_colors = MAX_CMAP_SIZE;
134 while ((c = getopt(argc, argv, "c:C:r:fh")) != -1)
135 switch (c) {
136 case 'c': /* compression scheme */
137 if (!processCompressOptions(optarg))
138 usage(EXIT_FAILURE);
139 break;
140 case 'C': /* set colormap size */
141 num_colors = atoi(optarg);
142 if (num_colors > MAX_CMAP_SIZE) {
143 fprintf(stderr,
144 "-c: colormap too big, max %d\n",
145 MAX_CMAP_SIZE);
146 usage(EXIT_FAILURE);
147 }
148 break;
149 case 'f': /* dither */
150 dither = 1;
151 break;
152 case 'r': /* rows/strip */
153 rowsperstrip = atoi(optarg);
154 break;
155 case 'h':
156 usage(EXIT_SUCCESS);
157 /*NOTREACHED*/
158 break;
159 case '?':
160 usage(EXIT_FAILURE);
161 /*NOTREACHED*/
162 break;
163 }
164 if (argc - optind != 2)
165 usage(EXIT_FAILURE);
166 in = TIFFOpen(argv[optind], "r");
167 if (in == NULL)
168 return (EXIT_FAILURE);
169 TIFFGetField(in, TIFFTAG_IMAGEWIDTH, &imagewidth);
170 TIFFGetField(in, TIFFTAG_IMAGELENGTH, &imagelength);
171 TIFFGetField(in, TIFFTAG_BITSPERSAMPLE, &bitspersample);
172 TIFFGetField(in, TIFFTAG_SAMPLESPERPIXEL, &samplesperpixel);
173 if (bitspersample != 8 && bitspersample != 16) {
174 fprintf(stderr, "%s: Image must have at least 8-bits/sample\n",
175 argv[optind]);
176 return (EXIT_FAILURE);
177 }
178 if (!TIFFGetField(in, TIFFTAG_PHOTOMETRIC, &photometric) ||
179 photometric != PHOTOMETRIC_RGB || samplesperpixel < 3) {
180 fprintf(stderr, "%s: Image must have RGB data\n", argv[optind]);
181 return (EXIT_FAILURE);
182 }
183 TIFFGetField(in, TIFFTAG_PLANARCONFIG, &config);
184 if (config != PLANARCONFIG_CONTIG) {
185 fprintf(stderr, "%s: Can only handle contiguous data packing\n",
186 argv[optind]);
187 return (EXIT_FAILURE);
188 }
189
190 /*
191 * STEP 1: create empty boxes
192 */
193 usedboxes = NULL;
194 box_list = freeboxes = (Colorbox *)_TIFFmalloc(num_colors*sizeof (Colorbox));
195 freeboxes[0].next = &freeboxes[1];
196 freeboxes[0].prev = NULL;
197 for (i = 1; i < num_colors-1; ++i) {
198 freeboxes[i].next = &freeboxes[i+1];
199 freeboxes[i].prev = &freeboxes[i-1];
200 }
201 freeboxes[num_colors-1].next = NULL;
202 freeboxes[num_colors-1].prev = &freeboxes[num_colors-2];
203
204 /*
205 * STEP 2: get histogram, initialize first box
206 */
207 ptr = freeboxes;
208 freeboxes = ptr->next;
209 if (freeboxes)
210 freeboxes->prev = NULL;
211 ptr->next = usedboxes;
212 usedboxes = ptr;
213 if (ptr->next)
214 ptr->next->prev = ptr;
215 get_histogram(in, ptr);
216
217 /*
218 * STEP 3: continually subdivide boxes until no more free
219 * boxes remain or until all colors assigned.
220 */
221 while (freeboxes != NULL) {
222 ptr = largest_box();
223 if (ptr != NULL)
224 splitbox(ptr);
225 else
226 freeboxes = NULL;
227 }
228
229 /*
230 * STEP 4: assign colors to all boxes
231 */
232 for (i = 0, ptr = usedboxes; ptr != NULL; ++i, ptr = ptr->next) {
233 rm[i] = ((ptr->rmin + ptr->rmax) << COLOR_SHIFT) / 2;
234 gm[i] = ((ptr->gmin + ptr->gmax) << COLOR_SHIFT) / 2;
235 bm[i] = ((ptr->bmin + ptr->bmax) << COLOR_SHIFT) / 2;
236 }
237
238 /* We're done with the boxes now */
239 _TIFFfree(box_list);
240 freeboxes = usedboxes = NULL;
241
242 /*
243 * STEP 5: scan histogram and map all values to closest color
244 */
245 /* 5a: create cell list as described in Heckbert[2] */
246 ColorCells = (C_cell **)_TIFFmalloc(C_LEN*C_LEN*C_LEN*sizeof (C_cell*));
247 _TIFFmemset(ColorCells, 0, C_LEN*C_LEN*C_LEN*sizeof (C_cell*));
248 /* 5b: create mapping from truncated pixel space to color
249 table entries */
250 map_colortable();
251
252 /*
253 * STEP 6: scan image, match input values to table entries
254 */
255 out = TIFFOpen(argv[optind+1], "w");
256 if (out == NULL)
257 return (EXIT_FAILURE);
258
259 CopyField(TIFFTAG_SUBFILETYPE, longv);
260 CopyField(TIFFTAG_IMAGEWIDTH, longv);
261 TIFFSetField(out, TIFFTAG_BITSPERSAMPLE, (short)COLOR_DEPTH);
262 if (compression != (uint16_t)-1) {
263 TIFFSetField(out, TIFFTAG_COMPRESSION, compression);
264 switch (compression) {
265 case COMPRESSION_LZW:
266 case COMPRESSION_DEFLATE:
267 if (predictor != 0)
268 TIFFSetField(out, TIFFTAG_PREDICTOR, predictor);
269 break;
270 }
271 } else
272 CopyField(TIFFTAG_COMPRESSION, compression);
273 TIFFSetField(out, TIFFTAG_PHOTOMETRIC, (short)PHOTOMETRIC_PALETTE);
274 CopyField(TIFFTAG_ORIENTATION, shortv);
275 TIFFSetField(out, TIFFTAG_SAMPLESPERPIXEL, (short)1);
276 CopyField(TIFFTAG_PLANARCONFIG, shortv);
277 TIFFSetField(out, TIFFTAG_ROWSPERSTRIP,
278 TIFFDefaultStripSize(out, rowsperstrip));
279 CopyField(TIFFTAG_MINSAMPLEVALUE, shortv);
280 CopyField(TIFFTAG_MAXSAMPLEVALUE, shortv);
281 CopyField(TIFFTAG_RESOLUTIONUNIT, shortv);
282 CopyField(TIFFTAG_XRESOLUTION, floatv);
283 CopyField(TIFFTAG_YRESOLUTION, floatv);
284 CopyField(TIFFTAG_XPOSITION, floatv);
285 CopyField(TIFFTAG_YPOSITION, floatv);
286
287 if (dither)
288 quant_fsdither(in, out);
289 else
290 quant(in, out);
291 /*
292 * Scale colormap to TIFF-required 16-bit values.
293 */
294 #define SCALE(x) (((x)*((1L<<16)-1))/255)
295 for (i = 0; i < MAX_CMAP_SIZE; ++i) {
296 rm[i] = SCALE(rm[i]);
297 gm[i] = SCALE(gm[i]);
298 bm[i] = SCALE(bm[i]);
299 }
300 TIFFSetField(out, TIFFTAG_COLORMAP, rm, gm, bm);
301 (void) TIFFClose(out);
302 return (EXIT_SUCCESS);
303 }
304
305 static int
processCompressOptions(char * opt)306 processCompressOptions(char* opt)
307 {
308 if (streq(opt, "none"))
309 compression = COMPRESSION_NONE;
310 else if (streq(opt, "packbits"))
311 compression = COMPRESSION_PACKBITS;
312 else if (strneq(opt, "lzw", 3)) {
313 char* cp = strchr(opt, ':');
314 if (cp)
315 predictor = atoi(cp+1);
316 compression = COMPRESSION_LZW;
317 } else if (strneq(opt, "zip", 3)) {
318 char* cp = strchr(opt, ':');
319 if (cp)
320 predictor = atoi(cp+1);
321 compression = COMPRESSION_DEFLATE;
322 } else
323 return (0);
324 return (1);
325 }
326
327 static const char usage_info[] =
328 "Apply the median cut algorithm to an RGB TIFF file\n\n"
329 "usage: tiffmedian [options] input.tif output.tif\n"
330 "where options are:\n"
331 " -r # make each strip have no more than # rows\n"
332 " -C # create a colormap with # entries\n"
333 " -f use Floyd-Steinberg dithering\n"
334 "\n"
335 #ifdef LZW_SUPPORT
336 " -c lzw[:opts] compress output with Lempel-Ziv & Welch encoding\n"
337 /* " LZW options:" */
338 " # set predictor value\n"
339 " For example, -c lzw:2 to get LZW-encoded data with horizontal differencing\n"
340 #endif
341 #ifdef ZIP_SUPPORT
342 " -c zip[:opts] compress output with deflate encoding\n"
343 /* " Deflate (ZIP) options:" */
344 " # set predictor value\n"
345 #endif
346 #ifdef PACKBITS_SUPPORT
347 " -c packbits compress output with packbits encoding\n"
348 #endif
349 #if defined(LZW_SUPPORT) || defined(ZIP_SUPPORT) || defined(PACKBITS_SUPPORT)
350 " -c none use no compression algorithm on output\n"
351 #endif
352 "\n"
353 ;
354
355 static void
usage(int code)356 usage(int code)
357 {
358 FILE * out = (code == EXIT_SUCCESS) ? stdout : stderr;
359
360 fprintf(out, "%s\n\n", TIFFGetVersion());
361 fprintf(out, "%s", usage_info);
362 exit(code);
363 }
364
365 static void
get_histogram(TIFF * in,Colorbox * box)366 get_histogram(TIFF* in, Colorbox* box)
367 {
368 register unsigned char *inptr;
369 register int red, green, blue;
370 register uint32_t j, i;
371 unsigned char *inputline;
372
373 inputline = (unsigned char *)_TIFFmalloc(TIFFScanlineSize(in));
374 if (inputline == NULL) {
375 fprintf(stderr, "No space for scanline buffer\n");
376 exit(EXIT_FAILURE);
377 }
378 box->rmin = box->gmin = box->bmin = 999;
379 box->rmax = box->gmax = box->bmax = -1;
380 box->total = imagewidth * imagelength;
381
382 { register uint32_t *ptr = &histogram[0][0][0];
383 for (i = B_LEN*B_LEN*B_LEN; i-- > 0;)
384 *ptr++ = 0;
385 }
386 for (i = 0; i < imagelength; i++) {
387 if (TIFFReadScanline(in, inputline, i, 0) <= 0)
388 break;
389 inptr = inputline;
390 for (j = imagewidth; j-- > 0;) {
391 red = (*inptr++) & 0xff >> COLOR_SHIFT;
392 green = (*inptr++) & 0xff >> COLOR_SHIFT;
393 blue = (*inptr++) & 0xff >> COLOR_SHIFT;
394 if ((red | green | blue) >= B_LEN) {
395 fprintf(stderr,
396 "Logic error. "
397 "Histogram array overflow!\n");
398 exit(EXIT_FAILURE);
399 }
400 if (red < box->rmin)
401 box->rmin = red;
402 if (red > box->rmax)
403 box->rmax = red;
404 if (green < box->gmin)
405 box->gmin = green;
406 if (green > box->gmax)
407 box->gmax = green;
408 if (blue < box->bmin)
409 box->bmin = blue;
410 if (blue > box->bmax)
411 box->bmax = blue;
412 histogram[red][green][blue]++;
413 }
414 }
415 _TIFFfree(inputline);
416 }
417
418 static Colorbox *
largest_box(void)419 largest_box(void)
420 {
421 register Colorbox *p, *b;
422 register uint32_t size;
423
424 b = NULL;
425 size = 0;
426 for (p = usedboxes; p != NULL; p = p->next)
427 if ((p->rmax > p->rmin || p->gmax > p->gmin ||
428 p->bmax > p->bmin) && p->total > size)
429 size = (b = p)->total;
430 return (b);
431 }
432
433 static void
splitbox(Colorbox * ptr)434 splitbox(Colorbox* ptr)
435 {
436 uint32_t hist2[B_LEN];
437 int first=0, last=0;
438 register Colorbox *new;
439 register uint32_t *iptr, *histp;
440 register int i, j;
441 register int ir,ig,ib;
442 register uint32_t sum, sum1, sum2;
443 enum { RED, GREEN, BLUE } axis;
444
445 /*
446 * See which axis is the largest, do a histogram along that
447 * axis. Split at median point. Contract both new boxes to
448 * fit points and return
449 */
450 i = ptr->rmax - ptr->rmin;
451 if (i >= ptr->gmax - ptr->gmin && i >= ptr->bmax - ptr->bmin)
452 axis = RED;
453 else if (ptr->gmax - ptr->gmin >= ptr->bmax - ptr->bmin)
454 axis = GREEN;
455 else
456 axis = BLUE;
457 /* get histogram along longest axis */
458 switch (axis) {
459 case RED:
460 histp = &hist2[ptr->rmin];
461 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
462 *histp = 0;
463 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
464 iptr = &histogram[ir][ig][ptr->bmin];
465 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
466 *histp += *iptr++;
467 }
468 histp++;
469 }
470 first = ptr->rmin;
471 last = ptr->rmax;
472 break;
473 case GREEN:
474 histp = &hist2[ptr->gmin];
475 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
476 *histp = 0;
477 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
478 iptr = &histogram[ir][ig][ptr->bmin];
479 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
480 *histp += *iptr++;
481 }
482 histp++;
483 }
484 first = ptr->gmin;
485 last = ptr->gmax;
486 break;
487 case BLUE:
488 histp = &hist2[ptr->bmin];
489 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) {
490 *histp = 0;
491 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
492 iptr = &histogram[ir][ptr->gmin][ib];
493 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
494 *histp += *iptr;
495 iptr += B_LEN;
496 }
497 }
498 histp++;
499 }
500 first = ptr->bmin;
501 last = ptr->bmax;
502 break;
503 }
504 /* find median point */
505 sum2 = ptr->total / 2;
506 histp = &hist2[first];
507 sum = 0;
508 for (i = first; i <= last && (sum += *histp++) < sum2; ++i)
509 ;
510 if (i == first)
511 i++;
512
513 /* Create new box, re-allocate points */
514 new = freeboxes;
515 freeboxes = new->next;
516 if (freeboxes)
517 freeboxes->prev = NULL;
518 if (usedboxes)
519 usedboxes->prev = new;
520 new->next = usedboxes;
521 usedboxes = new;
522
523 histp = &hist2[first];
524 for (sum1 = 0, j = first; j < i; j++)
525 sum1 += *histp++;
526 for (sum2 = 0, j = i; j <= last; j++)
527 sum2 += *histp++;
528 new->total = sum1;
529 ptr->total = sum2;
530
531 new->rmin = ptr->rmin;
532 new->rmax = ptr->rmax;
533 new->gmin = ptr->gmin;
534 new->gmax = ptr->gmax;
535 new->bmin = ptr->bmin;
536 new->bmax = ptr->bmax;
537 switch (axis) {
538 case RED:
539 new->rmax = i-1;
540 ptr->rmin = i;
541 break;
542 case GREEN:
543 new->gmax = i-1;
544 ptr->gmin = i;
545 break;
546 case BLUE:
547 new->bmax = i-1;
548 ptr->bmin = i;
549 break;
550 }
551 shrinkbox(new);
552 shrinkbox(ptr);
553 }
554
555 static void
shrinkbox(Colorbox * box)556 shrinkbox(Colorbox* box)
557 {
558 register uint32_t *histp;
559 register int ir, ig, ib;
560
561 if (box->rmax > box->rmin) {
562 for (ir = box->rmin; ir <= box->rmax; ++ir)
563 for (ig = box->gmin; ig <= box->gmax; ++ig) {
564 histp = &histogram[ir][ig][box->bmin];
565 for (ib = box->bmin; ib <= box->bmax; ++ib)
566 if (*histp++ != 0) {
567 box->rmin = ir;
568 goto have_rmin;
569 }
570 }
571 have_rmin:
572 if (box->rmax > box->rmin)
573 for (ir = box->rmax; ir >= box->rmin; --ir)
574 for (ig = box->gmin; ig <= box->gmax; ++ig) {
575 histp = &histogram[ir][ig][box->bmin];
576 ib = box->bmin;
577 for (; ib <= box->bmax; ++ib)
578 if (*histp++ != 0) {
579 box->rmax = ir;
580 goto have_rmax;
581 }
582 }
583 }
584 have_rmax:
585 if (box->gmax > box->gmin) {
586 for (ig = box->gmin; ig <= box->gmax; ++ig)
587 for (ir = box->rmin; ir <= box->rmax; ++ir) {
588 histp = &histogram[ir][ig][box->bmin];
589 for (ib = box->bmin; ib <= box->bmax; ++ib)
590 if (*histp++ != 0) {
591 box->gmin = ig;
592 goto have_gmin;
593 }
594 }
595 have_gmin:
596 if (box->gmax > box->gmin)
597 for (ig = box->gmax; ig >= box->gmin; --ig)
598 for (ir = box->rmin; ir <= box->rmax; ++ir) {
599 histp = &histogram[ir][ig][box->bmin];
600 ib = box->bmin;
601 for (; ib <= box->bmax; ++ib)
602 if (*histp++ != 0) {
603 box->gmax = ig;
604 goto have_gmax;
605 }
606 }
607 }
608 have_gmax:
609 if (box->bmax > box->bmin) {
610 for (ib = box->bmin; ib <= box->bmax; ++ib)
611 for (ir = box->rmin; ir <= box->rmax; ++ir) {
612 histp = &histogram[ir][box->gmin][ib];
613 for (ig = box->gmin; ig <= box->gmax; ++ig) {
614 if (*histp != 0) {
615 box->bmin = ib;
616 goto have_bmin;
617 }
618 histp += B_LEN;
619 }
620 }
621 have_bmin:
622 if (box->bmax > box->bmin)
623 for (ib = box->bmax; ib >= box->bmin; --ib)
624 for (ir = box->rmin; ir <= box->rmax; ++ir) {
625 histp = &histogram[ir][box->gmin][ib];
626 ig = box->gmin;
627 for (; ig <= box->gmax; ++ig) {
628 if (*histp != 0) {
629 box->bmax = ib;
630 goto have_bmax;
631 }
632 histp += B_LEN;
633 }
634 }
635 }
636 have_bmax:
637 ;
638 }
639
640 static C_cell *
create_colorcell(int red,int green,int blue)641 create_colorcell(int red, int green, int blue)
642 {
643 register int ir, ig, ib, i;
644 register C_cell *ptr;
645 int mindist, next_n;
646 register int tmp, dist, n;
647
648 ir = red >> (COLOR_DEPTH-C_DEPTH);
649 ig = green >> (COLOR_DEPTH-C_DEPTH);
650 ib = blue >> (COLOR_DEPTH-C_DEPTH);
651 ptr = (C_cell *)_TIFFmalloc(sizeof (C_cell));
652 *(ColorCells + ir*C_LEN*C_LEN + ig*C_LEN + ib) = ptr;
653 ptr->num_ents = 0;
654
655 /*
656 * Step 1: find all colors inside this cell, while we're at
657 * it, find distance of centermost point to furthest corner
658 */
659 mindist = 99999999;
660 for (i = 0; i < num_colors; ++i) {
661 if (rm[i]>>(COLOR_DEPTH-C_DEPTH) != ir ||
662 gm[i]>>(COLOR_DEPTH-C_DEPTH) != ig ||
663 bm[i]>>(COLOR_DEPTH-C_DEPTH) != ib)
664 continue;
665 ptr->entries[ptr->num_ents][0] = i;
666 ptr->entries[ptr->num_ents][1] = 0;
667 ++ptr->num_ents;
668 tmp = rm[i] - red;
669 if (tmp < (MAX_COLOR/C_LEN/2))
670 tmp = MAX_COLOR/C_LEN-1 - tmp;
671 dist = tmp*tmp;
672 tmp = gm[i] - green;
673 if (tmp < (MAX_COLOR/C_LEN/2))
674 tmp = MAX_COLOR/C_LEN-1 - tmp;
675 dist += tmp*tmp;
676 tmp = bm[i] - blue;
677 if (tmp < (MAX_COLOR/C_LEN/2))
678 tmp = MAX_COLOR/C_LEN-1 - tmp;
679 dist += tmp*tmp;
680 if (dist < mindist)
681 mindist = dist;
682 }
683
684 /*
685 * Step 3: find all points within that distance to cell.
686 */
687 for (i = 0; i < num_colors; ++i) {
688 if (rm[i] >> (COLOR_DEPTH-C_DEPTH) == ir &&
689 gm[i] >> (COLOR_DEPTH-C_DEPTH) == ig &&
690 bm[i] >> (COLOR_DEPTH-C_DEPTH) == ib)
691 continue;
692 dist = 0;
693 if ((tmp = red - rm[i]) > 0 ||
694 (tmp = rm[i] - (red + MAX_COLOR/C_LEN-1)) > 0 )
695 dist += tmp*tmp;
696 if ((tmp = green - gm[i]) > 0 ||
697 (tmp = gm[i] - (green + MAX_COLOR/C_LEN-1)) > 0 )
698 dist += tmp*tmp;
699 if ((tmp = blue - bm[i]) > 0 ||
700 (tmp = bm[i] - (blue + MAX_COLOR/C_LEN-1)) > 0 )
701 dist += tmp*tmp;
702 if (dist < mindist) {
703 ptr->entries[ptr->num_ents][0] = i;
704 ptr->entries[ptr->num_ents][1] = dist;
705 ++ptr->num_ents;
706 }
707 }
708
709 /*
710 * Sort color cells by distance, use cheap exchange sort
711 */
712 for (n = ptr->num_ents - 1; n > 0; n = next_n) {
713 next_n = 0;
714 for (i = 0; i < n; ++i)
715 if (ptr->entries[i][1] > ptr->entries[i+1][1]) {
716 tmp = ptr->entries[i][0];
717 ptr->entries[i][0] = ptr->entries[i+1][0];
718 ptr->entries[i+1][0] = tmp;
719 tmp = ptr->entries[i][1];
720 ptr->entries[i][1] = ptr->entries[i+1][1];
721 ptr->entries[i+1][1] = tmp;
722 next_n = i;
723 }
724 }
725 return (ptr);
726 }
727
728 static void
map_colortable(void)729 map_colortable(void)
730 {
731 register uint32_t *histp = &histogram[0][0][0];
732 register C_cell *cell;
733 register int j, tmp, d2, dist;
734 int ir, ig, ib, i;
735
736 for (ir = 0; ir < B_LEN; ++ir)
737 for (ig = 0; ig < B_LEN; ++ig)
738 for (ib = 0; ib < B_LEN; ++ib, histp++) {
739 if (*histp == 0) {
740 *histp = -1;
741 continue;
742 }
743 cell = *(ColorCells +
744 (((ir>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2) +
745 ((ig>>(B_DEPTH-C_DEPTH)) << C_DEPTH) +
746 (ib>>(B_DEPTH-C_DEPTH))));
747 if (cell == NULL )
748 cell = create_colorcell(
749 ir << COLOR_SHIFT,
750 ig << COLOR_SHIFT,
751 ib << COLOR_SHIFT);
752 dist = 9999999;
753 for (i = 0; i < cell->num_ents &&
754 dist > cell->entries[i][1]; ++i) {
755 j = cell->entries[i][0];
756 d2 = rm[j] - (ir << COLOR_SHIFT);
757 d2 *= d2;
758 tmp = gm[j] - (ig << COLOR_SHIFT);
759 d2 += tmp*tmp;
760 tmp = bm[j] - (ib << COLOR_SHIFT);
761 d2 += tmp*tmp;
762 if (d2 < dist) {
763 dist = d2;
764 *histp = j;
765 }
766 }
767 }
768 }
769
770 /*
771 * straight quantization. Each pixel is mapped to the colors
772 * closest to it. Color values are rounded to the nearest color
773 * table entry.
774 */
775 static void
quant(TIFF * in,TIFF * out)776 quant(TIFF* in, TIFF* out)
777 {
778 unsigned char *outline, *inputline;
779 register unsigned char *outptr, *inptr;
780 register uint32_t i, j;
781 register int red, green, blue;
782
783 inputline = (unsigned char *)_TIFFmalloc(TIFFScanlineSize(in));
784 outline = (unsigned char *)_TIFFmalloc(imagewidth);
785 for (i = 0; i < imagelength; i++) {
786 if (TIFFReadScanline(in, inputline, i, 0) <= 0)
787 break;
788 inptr = inputline;
789 outptr = outline;
790 for (j = 0; j < imagewidth; j++) {
791 red = *inptr++ >> COLOR_SHIFT;
792 green = *inptr++ >> COLOR_SHIFT;
793 blue = *inptr++ >> COLOR_SHIFT;
794 *outptr++ = (unsigned char)histogram[red][green][blue];
795 }
796 if (TIFFWriteScanline(out, outline, i, 0) < 0)
797 break;
798 }
799 _TIFFfree(inputline);
800 _TIFFfree(outline);
801 }
802
803 #define SWAP(type,a,b) { type p; p = a; a = b; b = p; }
804
805 #define GetInputLine(tif, row, bad) \
806 do { \
807 if (TIFFReadScanline(tif, inputline, row, 0) <= 0) \
808 bad; \
809 inptr = inputline; \
810 nextptr = nextline; \
811 for (j = 0; j < imagewidth; ++j) { \
812 *nextptr++ = *inptr++; \
813 *nextptr++ = *inptr++; \
814 *nextptr++ = *inptr++; \
815 } \
816 } while (0);
817 #define GetComponent(raw, cshift, c) \
818 do { \
819 cshift = raw; \
820 if (cshift < 0) \
821 cshift = 0; \
822 else if (cshift >= MAX_COLOR) \
823 cshift = MAX_COLOR-1; \
824 c = cshift; \
825 cshift >>= COLOR_SHIFT; \
826 } while (0);
827
828 static void
quant_fsdither(TIFF * in,TIFF * out)829 quant_fsdither(TIFF* in, TIFF* out)
830 {
831 unsigned char *outline, *inputline, *inptr;
832 short *thisline, *nextline;
833 register unsigned char *outptr;
834 register short *thisptr, *nextptr;
835 register uint32_t i, j;
836 uint32_t imax, jmax;
837 int lastline, lastpixel;
838
839 imax = imagelength - 1;
840 jmax = imagewidth - 1;
841 inputline = (unsigned char *)_TIFFmalloc(TIFFScanlineSize(in));
842 thisline = (short *)_TIFFmalloc(imagewidth * 3 * sizeof (short));
843 nextline = (short *)_TIFFmalloc(imagewidth * 3 * sizeof (short));
844 outline = (unsigned char *) _TIFFmalloc(TIFFScanlineSize(out));
845
846 GetInputLine(in, 0, goto bad); /* get first line */
847 for (i = 1; i <= imagelength; ++i) {
848 SWAP(short *, thisline, nextline);
849 lastline = (i >= imax);
850 if (i <= imax)
851 GetInputLine(in, i, break);
852 thisptr = thisline;
853 nextptr = nextline;
854 outptr = outline;
855 for (j = 0; j < imagewidth; ++j) {
856 int red, green, blue;
857 register int oval, r2, g2, b2;
858
859 lastpixel = (j == jmax);
860 GetComponent(*thisptr++, r2, red);
861 GetComponent(*thisptr++, g2, green);
862 GetComponent(*thisptr++, b2, blue);
863 oval = histogram[r2][g2][b2];
864 if (oval == -1) {
865 int ci;
866 register int cj, tmp, d2, dist;
867 register C_cell *cell;
868
869 cell = *(ColorCells +
870 (((r2>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2) +
871 ((g2>>(B_DEPTH-C_DEPTH)) << C_DEPTH ) +
872 (b2>>(B_DEPTH-C_DEPTH))));
873 if (cell == NULL)
874 cell = create_colorcell(red,
875 green, blue);
876 dist = 9999999;
877 for (ci = 0; ci < cell->num_ents && dist > cell->entries[ci][1]; ++ci) {
878 cj = cell->entries[ci][0];
879 d2 = (rm[cj] >> COLOR_SHIFT) - r2;
880 d2 *= d2;
881 tmp = (gm[cj] >> COLOR_SHIFT) - g2;
882 d2 += tmp*tmp;
883 tmp = (bm[cj] >> COLOR_SHIFT) - b2;
884 d2 += tmp*tmp;
885 if (d2 < dist) {
886 dist = d2;
887 oval = cj;
888 }
889 }
890 histogram[r2][g2][b2] = oval;
891 }
892 *outptr++ = oval;
893 red -= rm[oval];
894 green -= gm[oval];
895 blue -= bm[oval];
896 if (!lastpixel) {
897 thisptr[0] += blue * 7 / 16;
898 thisptr[1] += green * 7 / 16;
899 thisptr[2] += red * 7 / 16;
900 }
901 if (!lastline) {
902 if (j != 0) {
903 nextptr[-3] += blue * 3 / 16;
904 nextptr[-2] += green * 3 / 16;
905 nextptr[-1] += red * 3 / 16;
906 }
907 nextptr[0] += blue * 5 / 16;
908 nextptr[1] += green * 5 / 16;
909 nextptr[2] += red * 5 / 16;
910 if (!lastpixel) {
911 nextptr[3] += blue / 16;
912 nextptr[4] += green / 16;
913 nextptr[5] += red / 16;
914 }
915 nextptr += 3;
916 }
917 }
918 if (TIFFWriteScanline(out, outline, i-1, 0) < 0)
919 break;
920 }
921 bad:
922 _TIFFfree(inputline);
923 _TIFFfree(thisline);
924 _TIFFfree(nextline);
925 _TIFFfree(outline);
926 }
927 /*
928 * Local Variables:
929 * mode: c
930 * c-basic-offset: 8
931 * fill-column: 78
932 * End:
933 */
934