1 /* TODO: oim and nim in the lower level functions;
2 correct use of stub (sigh). */
3
4 /* 2.0.12: a new adaptation from the same original, this time
5 by Barend Gehrels. My attempt to incorporate alpha channel
6 into the result worked poorly and degraded the quality of
7 palette conversion even when the source contained no
8 alpha channel data. This version does not attempt to produce
9 an output file with transparency in some of the palette
10 indexes, which, in practice, doesn't look so hot anyway. TBB */
11
12 /*
13 * gd_topal, adapted from jquant2.c
14 *
15 * Copyright (C) 1991-1996, Thomas G. Lane.
16 * This file is part of the Independent JPEG Group's software.
17 * For conditions of distribution and use, see the accompanying README file.
18 *
19 * This file contains 2-pass color quantization (color mapping) routines.
20 * These routines provide selection of a custom color map for an image,
21 * followed by mapping of the image to that color map, with optional
22 * Floyd-Steinberg dithering.
23 * It is also possible to use just the second pass to map to an arbitrary
24 * externally-given color map.
25 *
26 * Note: ordered dithering is not supported, since there isn't any fast
27 * way to compute intercolor distances; it's unclear that ordered dither's
28 * fundamental assumptions even hold with an irregularly spaced color map.
29 */
30
31 #ifdef ORIGINAL_LIB_JPEG
32
33 #define JPEG_INTERNALS
34
35 #include "jinclude.h"
36 #include "jpeglib.h"
37
38 #else
39
40 /*
41 * THOMAS BOUTELL & BAREND GEHRELS, february 2003
42 * adapted the code to work within gd rather than within libjpeg.
43 * If it is not working, it's not Thomas G. Lane's fault.
44 */
45
46 /*
47 SETTING THIS ONE CAUSES STRIPED IMAGE
48 to be done: solve this
49 #define ORIGINAL_LIB_JPEG_REVERSE_ODD_ROWS
50 */
51
52 #include <string.h>
53 #include "gd.h"
54 #include "gdhelpers.h"
55
56 /* (Re)define some defines known by libjpeg */
57 #define QUANT_2PASS_SUPPORTED
58
59 #define RGB_RED 0
60 #define RGB_GREEN 1
61 #define RGB_BLUE 2
62
63 #define JSAMPLE unsigned char
64 #define MAXJSAMPLE (gdMaxColors-1)
65 #define BITS_IN_JSAMPLE 8
66
67 #define JSAMPROW int*
68 #define JDIMENSION int
69
70 #define METHODDEF(type) static type
71 #define LOCAL(type) static type
72
73
74 /* We assume that right shift corresponds to signed division by 2 with
75 * rounding towards minus infinity. This is correct for typical "arithmetic
76 * shift" instructions that shift in copies of the sign bit. But some
77 * C compilers implement >> with an unsigned shift. For these machines you
78 * must define RIGHT_SHIFT_IS_UNSIGNED.
79 * RIGHT_SHIFT provides a proper signed right shift of an INT32 quantity.
80 * It is only applied with constant shift counts. SHIFT_TEMPS must be
81 * included in the variables of any routine using RIGHT_SHIFT.
82 */
83
84 #ifdef RIGHT_SHIFT_IS_UNSIGNED
85 #define SHIFT_TEMPS INT32 shift_temp;
86 #define RIGHT_SHIFT(x,shft) \
87 ((shift_temp = (x)) < 0 ? \
88 (shift_temp >> (shft)) | ((~((INT32) 0)) << (32-(shft))) : \
89 (shift_temp >> (shft)))
90 #else
91 #define SHIFT_TEMPS
92 #define RIGHT_SHIFT(x,shft) ((x) >> (shft))
93 #endif
94
95
96 #define range_limit(x) { if(x<0) x=0; if (x>255) x=255; }
97
98
99 #ifndef INT16
100 #define INT16 short
101 #endif
102
103 #ifndef UINT16
104 #define UINT16 unsigned short
105 #endif
106
107 #ifndef INT32
108 #define INT32 int
109 #endif
110
111 #ifndef FAR
112 #define FAR
113 #endif
114
115
116
117 #ifndef boolean
118 #define boolean int
119 #endif
120
121 #ifndef TRUE
122 #define TRUE 1
123 #endif
124
125 #ifndef FALSE
126 #define FALSE 0
127 #endif
128
129
130 #define input_buf (oim->tpixels)
131 #define output_buf (nim->pixels)
132
133 #endif
134
135 #ifdef QUANT_2PASS_SUPPORTED
136
137
138 /*
139 * This module implements the well-known Heckbert paradigm for color
140 * quantization. Most of the ideas used here can be traced back to
141 * Heckbert's seminal paper
142 * Heckbert, Paul. "Color Image Quantization for Frame Buffer Display",
143 * Proc. SIGGRAPH '82, Computer Graphics v.16 #3 (July 1982), pp 297-304.
144 *
145 * In the first pass over the image, we accumulate a histogram showing the
146 * usage count of each possible color. To keep the histogram to a reasonable
147 * size, we reduce the precision of the input; typical practice is to retain
148 * 5 or 6 bits per color, so that 8 or 4 different input values are counted
149 * in the same histogram cell.
150 *
151 * Next, the color-selection step begins with a box representing the whole
152 * color space, and repeatedly splits the "largest" remaining box until we
153 * have as many boxes as desired colors. Then the mean color in each
154 * remaining box becomes one of the possible output colors.
155 *
156 * The second pass over the image maps each input pixel to the closest output
157 * color (optionally after applying a Floyd-Steinberg dithering correction).
158 * This mapping is logically trivial, but making it go fast enough requires
159 * considerable care.
160 *
161 * Heckbert-style quantizers vary a good deal in their policies for choosing
162 * the "largest" box and deciding where to cut it. The particular policies
163 * used here have proved out well in experimental comparisons, but better ones
164 * may yet be found.
165 *
166 * In earlier versions of the IJG code, this module quantized in YCbCr color
167 * space, processing the raw upsampled data without a color conversion step.
168 * This allowed the color conversion math to be done only once per colormap
169 * entry, not once per pixel. However, that optimization precluded other
170 * useful optimizations (such as merging color conversion with upsampling)
171 * and it also interfered with desired capabilities such as quantizing to an
172 * externally-supplied colormap. We have therefore abandoned that approach.
173 * The present code works in the post-conversion color space, typically RGB.
174 *
175 * To improve the visual quality of the results, we actually work in scaled
176 * RGB space, giving G distances more weight than R, and R in turn more than
177 * B. To do everything in integer math, we must use integer scale factors.
178 * The 2/3/1 scale factors used here correspond loosely to the relative
179 * weights of the colors in the NTSC grayscale equation.
180 * If you want to use this code to quantize a non-RGB color space, you'll
181 * probably need to change these scale factors.
182 */
183
184 #define R_SCALE 2 /* scale R distances by this much */
185 #define G_SCALE 3 /* scale G distances by this much */
186 #define B_SCALE 1 /* and B by this much */
187
188 /* Relabel R/G/B as components 0/1/2, respecting the RGB ordering defined
189 * in jmorecfg.h. As the code stands, it will do the right thing for R,G,B
190 * and B,G,R orders. If you define some other weird order in jmorecfg.h,
191 * you'll get compile errors until you extend this logic. In that case
192 * you'll probably want to tweak the histogram sizes too.
193 */
194
195 #if RGB_RED == 0
196 #define C0_SCALE R_SCALE
197 #endif
198 #if RGB_BLUE == 0
199 #define C0_SCALE B_SCALE
200 #endif
201 #if RGB_GREEN == 1
202 #define C1_SCALE G_SCALE
203 #endif
204 #if RGB_RED == 2
205 #define C2_SCALE R_SCALE
206 #endif
207 #if RGB_BLUE == 2
208 #define C2_SCALE B_SCALE
209 #endif
210
211
212 /*
213 * First we have the histogram data structure and routines for creating it.
214 *
215 * The number of bits of precision can be adjusted by changing these symbols.
216 * We recommend keeping 6 bits for G and 5 each for R and B.
217 * If you have plenty of memory and cycles, 6 bits all around gives marginally
218 * better results; if you are short of memory, 5 bits all around will save
219 * some space but degrade the results.
220 * To maintain a fully accurate histogram, we'd need to allocate a "long"
221 * (preferably unsigned long) for each cell. In practice this is overkill;
222 * we can get by with 16 bits per cell. Few of the cell counts will overflow,
223 * and clamping those that do overflow to the maximum value will give close-
224 * enough results. This reduces the recommended histogram size from 256Kb
225 * to 128Kb, which is a useful savings on PC-class machines.
226 * (In the second pass the histogram space is re-used for pixel mapping data;
227 * in that capacity, each cell must be able to store zero to the number of
228 * desired colors. 16 bits/cell is plenty for that too.)
229 * Since the JPEG code is intended to run in small memory model on 80x86
230 * machines, we can't just allocate the histogram in one chunk. Instead
231 * of a true 3-D array, we use a row of pointers to 2-D arrays. Each
232 * pointer corresponds to a C0 value (typically 2^5 = 32 pointers) and
233 * each 2-D array has 2^6*2^5 = 2048 or 2^6*2^6 = 4096 entries. Note that
234 * on 80x86 machines, the pointer row is in near memory but the actual
235 * arrays are in far memory (same arrangement as we use for image arrays).
236 */
237
238 #define MAXNUMCOLORS (MAXJSAMPLE+1) /* maximum size of colormap */
239
240 /* These will do the right thing for either R,G,B or B,G,R color order,
241 * but you may not like the results for other color orders.
242 */
243 #define HIST_C0_BITS 5 /* bits of precision in R/B histogram */
244 #define HIST_C1_BITS 6 /* bits of precision in G histogram */
245 #define HIST_C2_BITS 5 /* bits of precision in B/R histogram */
246
247 /* Number of elements along histogram axes. */
248 #define HIST_C0_ELEMS (1<<HIST_C0_BITS)
249 #define HIST_C1_ELEMS (1<<HIST_C1_BITS)
250 #define HIST_C2_ELEMS (1<<HIST_C2_BITS)
251
252 /* These are the amounts to shift an input value to get a histogram index. */
253 #define C0_SHIFT (BITS_IN_JSAMPLE-HIST_C0_BITS)
254 #define C1_SHIFT (BITS_IN_JSAMPLE-HIST_C1_BITS)
255 #define C2_SHIFT (BITS_IN_JSAMPLE-HIST_C2_BITS)
256
257
258 typedef UINT16 histcell; /* histogram cell; prefer an unsigned type */
259
260 typedef histcell FAR *histptr; /* for pointers to histogram cells */
261
262 typedef histcell hist1d[HIST_C2_ELEMS]; /* typedefs for the array */
263 typedef hist1d FAR *hist2d; /* type for the 2nd-level pointers */
264 typedef hist2d *hist3d; /* type for top-level pointer */
265
266
267 /* Declarations for Floyd-Steinberg dithering.
268 *
269 * Errors are accumulated into the array fserrors[], at a resolution of
270 * 1/16th of a pixel count. The error at a given pixel is propagated
271 * to its not-yet-processed neighbors using the standard F-S fractions,
272 * ... (here) 7/16
273 * 3/16 5/16 1/16
274 * We work left-to-right on even rows, right-to-left on odd rows.
275 *
276 * We can get away with a single array (holding one row's worth of errors)
277 * by using it to store the current row's errors at pixel columns not yet
278 * processed, but the next row's errors at columns already processed. We
279 * need only a few extra variables to hold the errors immediately around the
280 * current column. (If we are lucky, those variables are in registers, but
281 * even if not, they're probably cheaper to access than array elements are.)
282 *
283 * The fserrors[] array has (#columns + 2) entries; the extra entry at
284 * each end saves us from special-casing the first and last pixels.
285 * Each entry is three values long, one value for each color component.
286 *
287 * Note: on a wide image, we might not have enough room in a PC's near data
288 * segment to hold the error array; so it is allocated with alloc_large.
289 */
290
291 #if BITS_IN_JSAMPLE == 8
292 typedef INT16 FSERROR; /* 16 bits should be enough */
293 typedef int LOCFSERROR; /* use 'int' for calculation temps */
294 #else
295 typedef INT32 FSERROR; /* may need more than 16 bits */
296 typedef INT32 LOCFSERROR; /* be sure calculation temps are big enough */
297 #endif
298
299 typedef FSERROR FAR *FSERRPTR; /* pointer to error array (in FAR storage!) */
300
301
302 /* Private subobject */
303
304 typedef struct
305 {
306 #ifdef ORIGINAL_LIB_JPEG
307 struct jpeg_color_quantizer pub; /* public fields */
308
309 /* Space for the eventually created colormap is stashed here */
310 JSAMPARRAY sv_colormap; /* colormap allocated at init time */
311 int desired; /* desired # of colors = size of colormap */
312 boolean needs_zeroed; /* TRUE if next pass must zero histogram */
313 #endif
314
315 /* Variables for accumulating image statistics */
316 hist3d histogram; /* pointer to the histogram */
317
318
319 /* Variables for Floyd-Steinberg dithering */
320 FSERRPTR fserrors; /* accumulated errors */
321
322 boolean on_odd_row; /* flag to remember which row we are on */
323 int *error_limiter; /* table for clamping the applied error */
324 #ifndef ORIGINAL_LIB_JPEG
325 int *error_limiter_storage; /* gdMalloc'd storage for the above */
326 #endif
327 }
328 my_cquantizer;
329
330 typedef my_cquantizer *my_cquantize_ptr;
331
332
333 /*
334 * Prescan some rows of pixels.
335 * In this module the prescan simply updates the histogram, which has been
336 * initialized to zeroes by start_pass.
337 * An output_buf parameter is required by the method signature, but no data
338 * is actually output (in fact the buffer controller is probably passing a
339 * NULL pointer).
340 */
341
342 METHODDEF (void)
343 #ifndef ORIGINAL_LIB_JPEG
prescan_quantize(gdImagePtr oim,gdImagePtr nim,my_cquantize_ptr cquantize)344 prescan_quantize (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
345 {
346 #else
347 prescan_quantize (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
348 JSAMPARRAY output_buf, int num_rows)
349 {
350 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
351 #endif
352 register JSAMPROW ptr;
353 register histptr histp;
354 register hist3d histogram = cquantize->histogram;
355 int row;
356 JDIMENSION col;
357 #ifdef ORIGINAL_LIB_JPEG
358 JDIMENSION width = cinfo->output_width;
359 #else
360 int width = oim->sx;
361 int num_rows = oim->sy;
362 #endif
363
364 for (row = 0; row < num_rows; row++)
365 {
366 ptr = input_buf[row];
367 for (col = width; col > 0; col--)
368 {
369 #ifdef ORIGINAL_LIB_JPEG
370 int r = GETJSAMPLE (ptr[0]) >> C0_SHIFT;
371 int g = GETJSAMPLE (ptr[1]) >> C1_SHIFT;
372 int b = GETJSAMPLE (ptr[2]) >> C2_SHIFT;
373 #else
374 int r = gdTrueColorGetRed (*ptr) >> C0_SHIFT;
375 int g = gdTrueColorGetGreen (*ptr) >> C1_SHIFT;
376 int b = gdTrueColorGetBlue (*ptr) >> C2_SHIFT;
377 /* 2.0.12: Steven Brown: support a single totally transparent
378 color in the original. */
379 if ((oim->transparent >= 0) && (*ptr == oim->transparent))
380 {
381 ptr++;
382 continue;
383 }
384 #endif
385 /* get pixel value and index into the histogram */
386 histp = &histogram[r][g][b];
387 /* increment, check for overflow and undo increment if so. */
388 if (++(*histp) == 0)
389 (*histp)--;
390 #ifdef ORIGINAL_LIB_JPEG
391 ptr += 3;
392 #else
393 ptr++;
394 #endif
395 }
396 }
397 }
398
399
400 /*
401 * Next we have the really interesting routines: selection of a colormap
402 * given the completed histogram.
403 * These routines work with a list of "boxes", each representing a rectangular
404 * subset of the input color space (to histogram precision).
405 */
406
407 typedef struct
408 {
409 /* The bounds of the box (inclusive); expressed as histogram indexes */
410 int c0min, c0max;
411 int c1min, c1max;
412 int c2min, c2max;
413 /* The volume (actually 2-norm) of the box */
414 INT32 volume;
415 /* The number of nonzero histogram cells within this box */
416 long colorcount;
417 }
418 box;
419
420 typedef box *boxptr;
421
422
423 LOCAL (boxptr) find_biggest_color_pop (boxptr boxlist, int numboxes)
424 /* Find the splittable box with the largest color population */
425 /* Returns NULL if no splittable boxes remain */
426 {
427 register boxptr boxp;
428 register int i;
429 register long maxc = 0;
430 boxptr which = NULL;
431
432 for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++)
433 {
434 if (boxp->colorcount > maxc && boxp->volume > 0)
435 {
436 which = boxp;
437 maxc = boxp->colorcount;
438 }
439 }
440 return which;
441 }
442
443
444 LOCAL (boxptr) find_biggest_volume (boxptr boxlist, int numboxes)
445 /* Find the splittable box with the largest (scaled) volume */
446 /* Returns NULL if no splittable boxes remain */
447 {
448 register boxptr boxp;
449 register int i;
450 register INT32 maxv = 0;
451 boxptr which = NULL;
452
453 for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++)
454 {
455 if (boxp->volume > maxv)
456 {
457 which = boxp;
458 maxv = boxp->volume;
459 }
460 }
461 return which;
462 }
463
464
465 LOCAL (void)
466 #ifndef ORIGINAL_LIB_JPEG
467 update_box (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize, boxptr boxp)
468 {
469 #else
470 update_box (j_decompress_ptr cinfo, boxptr boxp)
471 /* Shrink the min/max bounds of a box to enclose only nonzero elements, */
472 /* and recompute its volume and population */
473 {
474 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
475 #endif
476 hist3d histogram = cquantize->histogram;
477 histptr histp;
478 int c0, c1, c2;
479 int c0min, c0max, c1min, c1max, c2min, c2max;
480 INT32 dist0, dist1, dist2;
481 long ccount;
482
483 c0min = boxp->c0min;
484 c0max = boxp->c0max;
485 c1min = boxp->c1min;
486 c1max = boxp->c1max;
487 c2min = boxp->c2min;
488 c2max = boxp->c2max;
489
490 if (c0max > c0min)
491 for (c0 = c0min; c0 <= c0max; c0++)
492 for (c1 = c1min; c1 <= c1max; c1++)
493 {
494 histp = &histogram[c0][c1][c2min];
495 for (c2 = c2min; c2 <= c2max; c2++)
496 if (*histp++ != 0)
497 {
498 boxp->c0min = c0min = c0;
499 goto have_c0min;
500 }
501 }
502 have_c0min:
503 if (c0max > c0min)
504 for (c0 = c0max; c0 >= c0min; c0--)
505 for (c1 = c1min; c1 <= c1max; c1++)
506 {
507 histp = &histogram[c0][c1][c2min];
508 for (c2 = c2min; c2 <= c2max; c2++)
509 if (*histp++ != 0)
510 {
511 boxp->c0max = c0max = c0;
512 goto have_c0max;
513 }
514 }
515 have_c0max:
516 if (c1max > c1min)
517 for (c1 = c1min; c1 <= c1max; c1++)
518 for (c0 = c0min; c0 <= c0max; c0++)
519 {
520 histp = &histogram[c0][c1][c2min];
521 for (c2 = c2min; c2 <= c2max; c2++)
522 if (*histp++ != 0)
523 {
524 boxp->c1min = c1min = c1;
525 goto have_c1min;
526 }
527 }
528 have_c1min:
529 if (c1max > c1min)
530 for (c1 = c1max; c1 >= c1min; c1--)
531 for (c0 = c0min; c0 <= c0max; c0++)
532 {
533 histp = &histogram[c0][c1][c2min];
534 for (c2 = c2min; c2 <= c2max; c2++)
535 if (*histp++ != 0)
536 {
537 boxp->c1max = c1max = c1;
538 goto have_c1max;
539 }
540 }
541 have_c1max:
542 if (c2max > c2min)
543 for (c2 = c2min; c2 <= c2max; c2++)
544 for (c0 = c0min; c0 <= c0max; c0++)
545 {
546 histp = &histogram[c0][c1min][c2];
547 for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)
548 if (*histp != 0)
549 {
550 boxp->c2min = c2min = c2;
551 goto have_c2min;
552 }
553 }
554 have_c2min:
555 if (c2max > c2min)
556 for (c2 = c2max; c2 >= c2min; c2--)
557 for (c0 = c0min; c0 <= c0max; c0++)
558 {
559 histp = &histogram[c0][c1min][c2];
560 for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)
561 if (*histp != 0)
562 {
563 boxp->c2max = c2max = c2;
564 goto have_c2max;
565 }
566 }
567 have_c2max:
568
569 /* Update box volume.
570 * We use 2-norm rather than real volume here; this biases the method
571 * against making long narrow boxes, and it has the side benefit that
572 * a box is splittable iff norm > 0.
573 * Since the differences are expressed in histogram-cell units,
574 * we have to shift back to JSAMPLE units to get consistent distances;
575 * after which, we scale according to the selected distance scale factors.
576 */
577 dist0 = ((c0max - c0min) << C0_SHIFT) * C0_SCALE;
578 dist1 = ((c1max - c1min) << C1_SHIFT) * C1_SCALE;
579 dist2 = ((c2max - c2min) << C2_SHIFT) * C2_SCALE;
580 boxp->volume = dist0 * dist0 + dist1 * dist1 + dist2 * dist2;
581
582 /* Now scan remaining volume of box and compute population */
583 ccount = 0;
584 for (c0 = c0min; c0 <= c0max; c0++)
585 for (c1 = c1min; c1 <= c1max; c1++)
586 {
587 histp = &histogram[c0][c1][c2min];
588 for (c2 = c2min; c2 <= c2max; c2++, histp++)
589 if (*histp != 0)
590 {
591 ccount++;
592 }
593 }
594 boxp->colorcount = ccount;
595 }
596
597
598 LOCAL (int)
599 #ifdef ORIGINAL_LIB_JPEG
600 median_cut (j_decompress_ptr cinfo, boxptr boxlist, int numboxes,
601 int desired_colors)
602 #else
603 median_cut (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize,
604 boxptr boxlist, int numboxes, int desired_colors)
605 #endif
606 /* Repeatedly select and split the largest box until we have enough boxes */
607 {
608 int n, lb;
609 int c0, c1, c2, cmax;
610 register boxptr b1, b2;
611
612 while (numboxes < desired_colors)
613 {
614 /* Select box to split.
615 * Current algorithm: by population for first half, then by volume.
616 */
617 if (numboxes * 2 <= desired_colors)
618 {
619 b1 = find_biggest_color_pop (boxlist, numboxes);
620 }
621 else
622 {
623 b1 = find_biggest_volume (boxlist, numboxes);
624 }
625 if (b1 == NULL) /* no splittable boxes left! */
626 break;
627 b2 = &boxlist[numboxes]; /* where new box will go */
628 /* Copy the color bounds to the new box. */
629 b2->c0max = b1->c0max;
630 b2->c1max = b1->c1max;
631 b2->c2max = b1->c2max;
632 b2->c0min = b1->c0min;
633 b2->c1min = b1->c1min;
634 b2->c2min = b1->c2min;
635 /* Choose which axis to split the box on.
636 * Current algorithm: longest scaled axis.
637 * See notes in update_box about scaling distances.
638 */
639 c0 = ((b1->c0max - b1->c0min) << C0_SHIFT) * C0_SCALE;
640 c1 = ((b1->c1max - b1->c1min) << C1_SHIFT) * C1_SCALE;
641 c2 = ((b1->c2max - b1->c2min) << C2_SHIFT) * C2_SCALE;
642 /* We want to break any ties in favor of green, then red, blue last.
643 * This code does the right thing for R,G,B or B,G,R color orders only.
644 */
645 #if RGB_RED == 0
646 cmax = c1;
647 n = 1;
648 if (c0 > cmax)
649 {
650 cmax = c0;
651 n = 0;
652 }
653 if (c2 > cmax)
654 {
655 n = 2;
656 }
657 #else
658 cmax = c1;
659 n = 1;
660 if (c2 > cmax)
661 {
662 cmax = c2;
663 n = 2;
664 }
665 if (c0 > cmax)
666 {
667 n = 0;
668 }
669 #endif
670 /* Choose split point along selected axis, and update box bounds.
671 * Current algorithm: split at halfway point.
672 * (Since the box has been shrunk to minimum volume,
673 * any split will produce two nonempty subboxes.)
674 * Note that lb value is max for lower box, so must be < old max.
675 */
676 switch (n)
677 {
678 case 0:
679 lb = (b1->c0max + b1->c0min) / 2;
680 b1->c0max = lb;
681 b2->c0min = lb + 1;
682 break;
683 case 1:
684 lb = (b1->c1max + b1->c1min) / 2;
685 b1->c1max = lb;
686 b2->c1min = lb + 1;
687 break;
688 case 2:
689 lb = (b1->c2max + b1->c2min) / 2;
690 b1->c2max = lb;
691 b2->c2min = lb + 1;
692 break;
693 }
694 /* Update stats for boxes */
695 #ifdef ORIGINAL_LIB_JPEG
696 update_box (cinfo, b1);
697 update_box (cinfo, b2);
698 #else
699 update_box (oim, nim, cquantize, b1);
700 update_box (oim, nim, cquantize, b2);
701 #endif
702 numboxes++;
703 }
704 return numboxes;
705 }
706
707
708 LOCAL (void)
709 #ifndef ORIGINAL_LIB_JPEG
710 compute_color (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize,
711 boxptr boxp, int icolor)
712 {
713 #else
714 compute_color (j_decompress_ptr cinfo, boxptr boxp, int icolor)
715 /* Compute representative color for a box, put it in colormap[icolor] */
716 {
717 /* Current algorithm: mean weighted by pixels (not colors) */
718 /* Note it is important to get the rounding correct! */
719 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
720 #endif
721 hist3d histogram = cquantize->histogram;
722 histptr histp;
723 int c0, c1, c2;
724 int c0min, c0max, c1min, c1max, c2min, c2max;
725 long count = 0; /* 2.0.28: = 0 */
726 long total = 0;
727 long c0total = 0;
728 long c1total = 0;
729 long c2total = 0;
730
731 c0min = boxp->c0min;
732 c0max = boxp->c0max;
733 c1min = boxp->c1min;
734 c1max = boxp->c1max;
735 c2min = boxp->c2min;
736 c2max = boxp->c2max;
737
738 for (c0 = c0min; c0 <= c0max; c0++)
739 for (c1 = c1min; c1 <= c1max; c1++)
740 {
741 histp = &histogram[c0][c1][c2min];
742 for (c2 = c2min; c2 <= c2max; c2++)
743 {
744 if ((count = *histp++) != 0)
745 {
746 total += count;
747 c0total +=
748 ((c0 << C0_SHIFT) + ((1 << C0_SHIFT) >> 1)) * count;
749 c1total +=
750 ((c1 << C1_SHIFT) + ((1 << C1_SHIFT) >> 1)) * count;
751 c2total +=
752 ((c2 << C2_SHIFT) + ((1 << C2_SHIFT) >> 1)) * count;
753 }
754 }
755 }
756
757 #ifdef ORIGINAL_LIB_JPEG
758 cinfo->colormap[0][icolor] = (JSAMPLE) ((c0total + (total >> 1)) / total);
759 cinfo->colormap[1][icolor] = (JSAMPLE) ((c1total + (total >> 1)) / total);
760 cinfo->colormap[2][icolor] = (JSAMPLE) ((c2total + (total >> 1)) / total);
761 #else
762 /* 2.0.16: Paul den Dulk found an occasion where total can be 0 */
763 if (count)
764 {
765 nim->red[icolor] = (int) ((c0total + (total >> 1)) / total);
766 nim->green[icolor] = (int) ((c1total + (total >> 1)) / total);
767 nim->blue[icolor] = (int) ((c2total + (total >> 1)) / total);
768 }
769 else
770 {
771 nim->red[icolor] = 255;
772 nim->green[icolor] = 255;
773 nim->blue[icolor] = 255;
774 }
775 nim->open[icolor] = 0;
776 #endif
777 }
778
779
780 LOCAL (void)
781 #ifdef ORIGINAL_LIB_JPEG
782 select_colors (j_decompress_ptr cinfo, int desired_colors)
783 #else
784 select_colors (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize, int desired_colors)
785 #endif
786 /* Master routine for color selection */
787 {
788 boxptr boxlist;
789 int numboxes;
790 int i;
791
792 /* Allocate workspace for box list */
793 #ifdef ORIGINAL_LIB_JPEG
794 boxlist = (boxptr) (*cinfo->mem->alloc_small)
795 ((j_common_ptr) cinfo, JPOOL_IMAGE, desired_colors * SIZEOF (box));
796 #else
797 boxlist = (boxptr) safe_emalloc(desired_colors, sizeof (box), 1);
798 #endif
799 /* Initialize one box containing whole space */
800 numboxes = 1;
801 boxlist[0].c0min = 0;
802 boxlist[0].c0max = MAXJSAMPLE >> C0_SHIFT;
803 boxlist[0].c1min = 0;
804 boxlist[0].c1max = MAXJSAMPLE >> C1_SHIFT;
805 boxlist[0].c2min = 0;
806 boxlist[0].c2max = MAXJSAMPLE >> C2_SHIFT;
807 #ifdef ORIGINAL_LIB_JPEG
808 /* Shrink it to actually-used volume and set its statistics */
809 update_box (cinfo, &boxlist[0]);
810 /* Perform median-cut to produce final box list */
811 numboxes = median_cut (cinfo, boxlist, numboxes, desired_colors);
812 /* Compute the representative color for each box, fill colormap */
813 for (i = 0; i < numboxes; i++)
814 compute_color (cinfo, &boxlist[i], i);
815 cinfo->actual_number_of_colors = numboxes;
816 TRACEMS1 (cinfo, 1, JTRC_QUANT_SELECTED, numboxes);
817 #else
818 /* Shrink it to actually-used volume and set its statistics */
819 update_box (oim, nim, cquantize, &boxlist[0]);
820 /* Perform median-cut to produce final box list */
821 numboxes = median_cut (oim, nim, cquantize, boxlist, numboxes, desired_colors);
822 /* Compute the representative color for each box, fill colormap */
823 for (i = 0; i < numboxes; i++)
824 compute_color (oim, nim, cquantize, &boxlist[i], i);
825 nim->colorsTotal = numboxes;
826
827 /* If we had a pure transparency color, add it as the last palette entry.
828 * Skip incrementing the color count so that the dither / matching phase
829 * won't use it on pixels that shouldn't have been transparent. We'll
830 * increment it after all that finishes. */
831 if (oim->transparent >= 0)
832 {
833 /* Save the transparent color. */
834 nim->red[nim->colorsTotal] = gdTrueColorGetRed (oim->transparent);
835 nim->green[nim->colorsTotal] = gdTrueColorGetGreen (oim->transparent);
836 nim->blue[nim->colorsTotal] = gdTrueColorGetBlue (oim->transparent);
837 nim->alpha[nim->colorsTotal] = gdAlphaTransparent;
838 nim->open[nim->colorsTotal] = 0;
839 }
840
841 gdFree (boxlist);
842 #endif
843 }
844
845
846 /*
847 * These routines are concerned with the time-critical task of mapping input
848 * colors to the nearest color in the selected colormap.
849 *
850 * We re-use the histogram space as an "inverse color map", essentially a
851 * cache for the results of nearest-color searches. All colors within a
852 * histogram cell will be mapped to the same colormap entry, namely the one
853 * closest to the cell's center. This may not be quite the closest entry to
854 * the actual input color, but it's almost as good. A zero in the cache
855 * indicates we haven't found the nearest color for that cell yet; the array
856 * is cleared to zeroes before starting the mapping pass. When we find the
857 * nearest color for a cell, its colormap index plus one is recorded in the
858 * cache for future use. The pass2 scanning routines call fill_inverse_cmap
859 * when they need to use an unfilled entry in the cache.
860 *
861 * Our method of efficiently finding nearest colors is based on the "locally
862 * sorted search" idea described by Heckbert and on the incremental distance
863 * calculation described by Spencer W. Thomas in chapter III.1 of Graphics
864 * Gems II (James Arvo, ed. Academic Press, 1991). Thomas points out that
865 * the distances from a given colormap entry to each cell of the histogram can
866 * be computed quickly using an incremental method: the differences between
867 * distances to adjacent cells themselves differ by a constant. This allows a
868 * fairly fast implementation of the "brute force" approach of computing the
869 * distance from every colormap entry to every histogram cell. Unfortunately,
870 * it needs a work array to hold the best-distance-so-far for each histogram
871 * cell (because the inner loop has to be over cells, not colormap entries).
872 * The work array elements have to be INT32s, so the work array would need
873 * 256Kb at our recommended precision. This is not feasible in DOS machines.
874 *
875 * To get around these problems, we apply Thomas' method to compute the
876 * nearest colors for only the cells within a small subbox of the histogram.
877 * The work array need be only as big as the subbox, so the memory usage
878 * problem is solved. Furthermore, we need not fill subboxes that are never
879 * referenced in pass2; many images use only part of the color gamut, so a
880 * fair amount of work is saved. An additional advantage of this
881 * approach is that we can apply Heckbert's locality criterion to quickly
882 * eliminate colormap entries that are far away from the subbox; typically
883 * three-fourths of the colormap entries are rejected by Heckbert's criterion,
884 * and we need not compute their distances to individual cells in the subbox.
885 * The speed of this approach is heavily influenced by the subbox size: too
886 * small means too much overhead, too big loses because Heckbert's criterion
887 * can't eliminate as many colormap entries. Empirically the best subbox
888 * size seems to be about 1/512th of the histogram (1/8th in each direction).
889 *
890 * Thomas' article also describes a refined method which is asymptotically
891 * faster than the brute-force method, but it is also far more complex and
892 * cannot efficiently be applied to small subboxes. It is therefore not
893 * useful for programs intended to be portable to DOS machines. On machines
894 * with plenty of memory, filling the whole histogram in one shot with Thomas'
895 * refined method might be faster than the present code --- but then again,
896 * it might not be any faster, and it's certainly more complicated.
897 */
898
899
900 /* log2(histogram cells in update box) for each axis; this can be adjusted */
901 #define BOX_C0_LOG (HIST_C0_BITS-3)
902 #define BOX_C1_LOG (HIST_C1_BITS-3)
903 #define BOX_C2_LOG (HIST_C2_BITS-3)
904
905 #define BOX_C0_ELEMS (1<<BOX_C0_LOG) /* # of hist cells in update box */
906 #define BOX_C1_ELEMS (1<<BOX_C1_LOG)
907 #define BOX_C2_ELEMS (1<<BOX_C2_LOG)
908
909 #define BOX_C0_SHIFT (C0_SHIFT + BOX_C0_LOG)
910 #define BOX_C1_SHIFT (C1_SHIFT + BOX_C1_LOG)
911 #define BOX_C2_SHIFT (C2_SHIFT + BOX_C2_LOG)
912
913
914 /*
915 * The next three routines implement inverse colormap filling. They could
916 * all be folded into one big routine, but splitting them up this way saves
917 * some stack space (the mindist[] and bestdist[] arrays need not coexist)
918 * and may allow some compilers to produce better code by registerizing more
919 * inner-loop variables.
920 */
921
922 LOCAL (int)
923 find_nearby_colors (
924 #ifdef ORIGINAL_LIB_JPEG
925 j_decompress_ptr cinfo,
926 #else
927 gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize,
928 #endif
929 int minc0, int minc1, int minc2, JSAMPLE colorlist[])
930 /* Locate the colormap entries close enough to an update box to be candidates
931 * for the nearest entry to some cell(s) in the update box. The update box
932 * is specified by the center coordinates of its first cell. The number of
933 * candidate colormap entries is returned, and their colormap indexes are
934 * placed in colorlist[].
935 * This routine uses Heckbert's "locally sorted search" criterion to select
936 * the colors that need further consideration.
937 */
938 {
939 #ifdef ORIGINAL_LIB_JPEG
940 int numcolors = cinfo->actual_number_of_colors;
941 #else
942 int numcolors = nim->colorsTotal;
943 #endif
944 int maxc0, maxc1, maxc2;
945 int centerc0, centerc1, centerc2;
946 int i, x, ncolors;
947 INT32 minmaxdist, min_dist, max_dist, tdist;
948 INT32 mindist[MAXNUMCOLORS]; /* min distance to colormap entry i */
949
950 /* Compute true coordinates of update box's upper corner and center.
951 * Actually we compute the coordinates of the center of the upper-corner
952 * histogram cell, which are the upper bounds of the volume we care about.
953 * Note that since ">>" rounds down, the "center" values may be closer to
954 * min than to max; hence comparisons to them must be "<=", not "<".
955 */
956 maxc0 = minc0 + ((1 << BOX_C0_SHIFT) - (1 << C0_SHIFT));
957 centerc0 = (minc0 + maxc0) >> 1;
958 maxc1 = minc1 + ((1 << BOX_C1_SHIFT) - (1 << C1_SHIFT));
959 centerc1 = (minc1 + maxc1) >> 1;
960 maxc2 = minc2 + ((1 << BOX_C2_SHIFT) - (1 << C2_SHIFT));
961 centerc2 = (minc2 + maxc2) >> 1;
962
963 /* For each color in colormap, find:
964 * 1. its minimum squared-distance to any point in the update box
965 * (zero if color is within update box);
966 * 2. its maximum squared-distance to any point in the update box.
967 * Both of these can be found by considering only the corners of the box.
968 * We save the minimum distance for each color in mindist[];
969 * only the smallest maximum distance is of interest.
970 */
971 minmaxdist = 0x7FFFFFFFL;
972
973 for (i = 0; i < numcolors; i++)
974 {
975 /* We compute the squared-c0-distance term, then add in the other two. */
976 #ifdef ORIGINAL_LIB_JPEG
977 x = GETJSAMPLE (cinfo->colormap[0][i]);
978 #else
979 x = nim->red[i];
980 #endif
981 if (x < minc0)
982 {
983 tdist = (x - minc0) * C0_SCALE;
984 min_dist = tdist * tdist;
985 tdist = (x - maxc0) * C0_SCALE;
986 max_dist = tdist * tdist;
987 }
988 else if (x > maxc0)
989 {
990 tdist = (x - maxc0) * C0_SCALE;
991 min_dist = tdist * tdist;
992 tdist = (x - minc0) * C0_SCALE;
993 max_dist = tdist * tdist;
994 }
995 else
996 {
997 /* within cell range so no contribution to min_dist */
998 min_dist = 0;
999 if (x <= centerc0)
1000 {
1001 tdist = (x - maxc0) * C0_SCALE;
1002 max_dist = tdist * tdist;
1003 }
1004 else
1005 {
1006 tdist = (x - minc0) * C0_SCALE;
1007 max_dist = tdist * tdist;
1008 }
1009 }
1010
1011 #ifdef ORIGINAL_LIB_JPEG
1012 x = GETJSAMPLE (cinfo->colormap[1][i]);
1013 #else
1014 x = nim->green[i];
1015 #endif
1016 if (x < minc1)
1017 {
1018 tdist = (x - minc1) * C1_SCALE;
1019 min_dist += tdist * tdist;
1020 tdist = (x - maxc1) * C1_SCALE;
1021 max_dist += tdist * tdist;
1022 }
1023 else if (x > maxc1)
1024 {
1025 tdist = (x - maxc1) * C1_SCALE;
1026 min_dist += tdist * tdist;
1027 tdist = (x - minc1) * C1_SCALE;
1028 max_dist += tdist * tdist;
1029 }
1030 else
1031 {
1032 /* within cell range so no contribution to min_dist */
1033 if (x <= centerc1)
1034 {
1035 tdist = (x - maxc1) * C1_SCALE;
1036 max_dist += tdist * tdist;
1037 }
1038 else
1039 {
1040 tdist = (x - minc1) * C1_SCALE;
1041 max_dist += tdist * tdist;
1042 }
1043 }
1044
1045 #ifdef ORIGINAL_LIB_JPEG
1046 x = GETJSAMPLE (cinfo->colormap[2][i]);
1047 #else
1048 x = nim->blue[i];
1049 #endif
1050 if (x < minc2)
1051 {
1052 tdist = (x - minc2) * C2_SCALE;
1053 min_dist += tdist * tdist;
1054 tdist = (x - maxc2) * C2_SCALE;
1055 max_dist += tdist * tdist;
1056 }
1057 else if (x > maxc2)
1058 {
1059 tdist = (x - maxc2) * C2_SCALE;
1060 min_dist += tdist * tdist;
1061 tdist = (x - minc2) * C2_SCALE;
1062 max_dist += tdist * tdist;
1063 }
1064 else
1065 {
1066 /* within cell range so no contribution to min_dist */
1067 if (x <= centerc2)
1068 {
1069 tdist = (x - maxc2) * C2_SCALE;
1070 max_dist += tdist * tdist;
1071 }
1072 else
1073 {
1074 tdist = (x - minc2) * C2_SCALE;
1075 max_dist += tdist * tdist;
1076 }
1077 }
1078
1079 mindist[i] = min_dist; /* save away the results */
1080 if (max_dist < minmaxdist)
1081 minmaxdist = max_dist;
1082 }
1083
1084 /* Now we know that no cell in the update box is more than minmaxdist
1085 * away from some colormap entry. Therefore, only colors that are
1086 * within minmaxdist of some part of the box need be considered.
1087 */
1088 ncolors = 0;
1089 for (i = 0; i < numcolors; i++)
1090 {
1091 if (mindist[i] <= minmaxdist)
1092 colorlist[ncolors++] = (JSAMPLE) i;
1093 }
1094 return ncolors;
1095 }
1096
1097
1098 LOCAL (void) find_best_colors (
1099 #ifdef ORIGINAL_LIB_JPEG
1100 j_decompress_ptr cinfo,
1101 #else
1102 gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize,
1103 #endif
1104 int minc0, int minc1, int minc2,
1105 int numcolors, JSAMPLE colorlist[],
1106 JSAMPLE bestcolor[])
1107 /* Find the closest colormap entry for each cell in the update box,
1108 * given the list of candidate colors prepared by find_nearby_colors.
1109 * Return the indexes of the closest entries in the bestcolor[] array.
1110 * This routine uses Thomas' incremental distance calculation method to
1111 * find the distance from a colormap entry to successive cells in the box.
1112 */
1113 {
1114 int ic0, ic1, ic2;
1115 int i, icolor;
1116 register INT32 *bptr; /* pointer into bestdist[] array */
1117 JSAMPLE *cptr; /* pointer into bestcolor[] array */
1118 INT32 dist0, dist1; /* initial distance values */
1119 register INT32 dist2; /* current distance in inner loop */
1120 INT32 xx0, xx1; /* distance increments */
1121 register INT32 xx2;
1122 INT32 inc0, inc1, inc2; /* initial values for increments */
1123 /* This array holds the distance to the nearest-so-far color for each cell */
1124 INT32 bestdist[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS];
1125
1126 /* Initialize best-distance for each cell of the update box */
1127 bptr = bestdist;
1128 for (i = BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS - 1; i >= 0; i--)
1129 *bptr++ = 0x7FFFFFFFL;
1130
1131 /* For each color selected by find_nearby_colors,
1132 * compute its distance to the center of each cell in the box.
1133 * If that's less than best-so-far, update best distance and color number.
1134 */
1135
1136 /* Nominal steps between cell centers ("x" in Thomas article) */
1137 #define STEP_C0 ((1 << C0_SHIFT) * C0_SCALE)
1138 #define STEP_C1 ((1 << C1_SHIFT) * C1_SCALE)
1139 #define STEP_C2 ((1 << C2_SHIFT) * C2_SCALE)
1140
1141 for (i = 0; i < numcolors; i++)
1142 {
1143 int r, g, b;
1144 #ifdef ORIGINAL_LIB_JPEG
1145
1146 icolor = GETJSAMPLE (colorlist[i]);
1147 r = GETJSAMPLE (cinfo->colormap[0][icolor]);
1148 g = GETJSAMPLE (cinfo->colormap[1][icolor]);
1149 b = GETJSAMPLE (cinfo->colormap[2][icolor]);
1150 #else
1151 icolor = colorlist[i];
1152 r = nim->red[icolor];
1153 g = nim->green[icolor];
1154 b = nim->blue[icolor];
1155 #endif
1156
1157 /* Compute (square of) distance from minc0/c1/c2 to this color */
1158 inc0 = (minc0 - r) * C0_SCALE;
1159 dist0 = inc0 * inc0;
1160 inc1 = (minc1 - g) * C1_SCALE;
1161 dist0 += inc1 * inc1;
1162 inc2 = (minc2 - b) * C2_SCALE;
1163 dist0 += inc2 * inc2;
1164 /* Form the initial difference increments */
1165 inc0 = inc0 * (2 * STEP_C0) + STEP_C0 * STEP_C0;
1166 inc1 = inc1 * (2 * STEP_C1) + STEP_C1 * STEP_C1;
1167 inc2 = inc2 * (2 * STEP_C2) + STEP_C2 * STEP_C2;
1168 /* Now loop over all cells in box, updating distance per Thomas method */
1169 bptr = bestdist;
1170 cptr = bestcolor;
1171 xx0 = inc0;
1172 for (ic0 = BOX_C0_ELEMS - 1; ic0 >= 0; ic0--)
1173 {
1174 dist1 = dist0;
1175 xx1 = inc1;
1176 for (ic1 = BOX_C1_ELEMS - 1; ic1 >= 0; ic1--)
1177 {
1178 dist2 = dist1;
1179 xx2 = inc2;
1180 for (ic2 = BOX_C2_ELEMS - 1; ic2 >= 0; ic2--)
1181 {
1182 if (dist2 < *bptr)
1183 {
1184 *bptr = dist2;
1185 *cptr = (JSAMPLE) icolor;
1186 }
1187 dist2 += xx2;
1188 xx2 += 2 * STEP_C2 * STEP_C2;
1189 bptr++;
1190 cptr++;
1191 }
1192 dist1 += xx1;
1193 xx1 += 2 * STEP_C1 * STEP_C1;
1194 }
1195 dist0 += xx0;
1196 xx0 += 2 * STEP_C0 * STEP_C0;
1197 }
1198 }
1199 }
1200
1201
1202 LOCAL (void)
1203 fill_inverse_cmap (
1204 #ifdef ORIGINAL_LIB_JPEG
1205 j_decompress_ptr cinfo,
1206 #else
1207 gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize,
1208 #endif
1209 int c0, int c1, int c2)
1210 /* Fill the inverse-colormap entries in the update box that contains */
1211 /* histogram cell c0/c1/c2. (Only that one cell MUST be filled, but */
1212 /* we can fill as many others as we wish.) */
1213 {
1214 #ifdef ORIGINAL_LIB_JPEG
1215 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1216 #endif
1217 hist3d histogram = cquantize->histogram;
1218 int minc0, minc1, minc2; /* lower left corner of update box */
1219 int ic0, ic1, ic2;
1220 register JSAMPLE *cptr; /* pointer into bestcolor[] array */
1221 register histptr cachep; /* pointer into main cache array */
1222 /* This array lists the candidate colormap indexes. */
1223 JSAMPLE colorlist[MAXNUMCOLORS];
1224 int numcolors; /* number of candidate colors */
1225 /* This array holds the actually closest colormap index for each cell. */
1226 JSAMPLE bestcolor[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS];
1227
1228 /* Convert cell coordinates to update box ID */
1229 c0 >>= BOX_C0_LOG;
1230 c1 >>= BOX_C1_LOG;
1231 c2 >>= BOX_C2_LOG;
1232
1233 /* Compute true coordinates of update box's origin corner.
1234 * Actually we compute the coordinates of the center of the corner
1235 * histogram cell, which are the lower bounds of the volume we care about.
1236 */
1237 minc0 = (c0 << BOX_C0_SHIFT) + ((1 << C0_SHIFT) >> 1);
1238 minc1 = (c1 << BOX_C1_SHIFT) + ((1 << C1_SHIFT) >> 1);
1239 minc2 = (c2 << BOX_C2_SHIFT) + ((1 << C2_SHIFT) >> 1);
1240
1241 /* Determine which colormap entries are close enough to be candidates
1242 * for the nearest entry to some cell in the update box.
1243 */
1244 #ifdef ORIGINAL_LIB_JPEG
1245 numcolors = find_nearby_colors (cinfo, minc0, minc1, minc2, colorlist);
1246
1247 /* Determine the actually nearest colors. */
1248 find_best_colors (cinfo, minc0, minc1, minc2, numcolors, colorlist,
1249 bestcolor);
1250 #else
1251 numcolors =
1252 find_nearby_colors (oim, nim, cquantize, minc0, minc1, minc2, colorlist);
1253 find_best_colors (oim, nim, cquantize, minc0, minc1, minc2, numcolors,
1254 colorlist, bestcolor);
1255 #endif
1256
1257 /* Save the best color numbers (plus 1) in the main cache array */
1258 c0 <<= BOX_C0_LOG; /* convert ID back to base cell indexes */
1259 c1 <<= BOX_C1_LOG;
1260 c2 <<= BOX_C2_LOG;
1261 cptr = bestcolor;
1262 for (ic0 = 0; ic0 < BOX_C0_ELEMS; ic0++)
1263 {
1264 for (ic1 = 0; ic1 < BOX_C1_ELEMS; ic1++)
1265 {
1266 cachep = &histogram[c0 + ic0][c1 + ic1][c2];
1267 for (ic2 = 0; ic2 < BOX_C2_ELEMS; ic2++)
1268 {
1269 #ifdef ORIGINAL_LIB_JPEG
1270 *cachep++ = (histcell) (GETJSAMPLE (*cptr++) + 1);
1271 #else
1272 *cachep++ = (histcell) ((*cptr++) + 1);
1273 #endif
1274 }
1275 }
1276 }
1277 }
1278
1279
1280 /*
1281 * Map some rows of pixels to the output colormapped representation.
1282 */
1283
1284 METHODDEF (void)
1285 #ifndef ORIGINAL_LIB_JPEG
1286 pass2_no_dither (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
1287 {
1288 register int *inptr;
1289 register unsigned char *outptr;
1290 int width = oim->sx;
1291 int num_rows = oim->sy;
1292 #else
1293 pass2_no_dither (j_decompress_ptr cinfo,
1294 JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows)
1295 /* This version performs no dithering */
1296 {
1297 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1298 register JSAMPROW inptr, outptr;
1299 JDIMENSION width = cinfo->output_width;
1300 #endif
1301 hist3d histogram = cquantize->histogram;
1302 register int c0, c1, c2;
1303 int row;
1304 JDIMENSION col;
1305 register histptr cachep;
1306
1307
1308 for (row = 0; row < num_rows; row++)
1309 {
1310 inptr = input_buf[row];
1311 outptr = output_buf[row];
1312 for (col = width; col > 0; col--)
1313 {
1314 /* get pixel value and index into the cache */
1315 int r, g, b;
1316 #ifdef ORIGINAL_LIB_JPEG
1317 r = GETJSAMPLE (*inptr++);
1318 g = GETJSAMPLE (*inptr++);
1319 b = GETJSAMPLE (*inptr++);
1320 #else
1321 r = gdTrueColorGetRed (*inptr);
1322 g = gdTrueColorGetGreen (*inptr);
1323 /*
1324 2.0.24: inptr must not be incremented until after
1325 transparency check, if any. Thanks to "Super Pikeman."
1326 */
1327 b = gdTrueColorGetBlue (*inptr);
1328
1329 /* If the pixel is transparent, we assign it the palette index that
1330 * will later be added at the end of the palette as the transparent
1331 * index. */
1332 if ((oim->transparent >= 0) && (oim->transparent == *inptr))
1333 {
1334 *outptr++ = nim->colorsTotal;
1335 inptr++;
1336 continue;
1337 }
1338 inptr++;
1339 #endif
1340 c0 = r >> C0_SHIFT;
1341 c1 = g >> C1_SHIFT;
1342 c2 = b >> C2_SHIFT;
1343 cachep = &histogram[c0][c1][c2];
1344 /* If we have not seen this color before, find nearest colormap entry */
1345 /* and update the cache */
1346 if (*cachep == 0)
1347 #ifdef ORIGINAL_LIB_JPEG
1348 fill_inverse_cmap (cinfo, c0, c1, c2);
1349 #else
1350 fill_inverse_cmap (oim, nim, cquantize, c0, c1, c2);
1351 #endif
1352 /* Now emit the colormap index for this cell */
1353 #ifdef ORIGINAL_LIB_JPEG
1354 *outptr++ = (JSAMPLE) (*cachep - 1);
1355 #else
1356 *outptr++ = (*cachep - 1);
1357 #endif
1358 }
1359 }
1360 }
1361
1362
1363 METHODDEF (void)
1364 #ifndef ORIGINAL_LIB_JPEG
1365 pass2_fs_dither (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
1366 {
1367 #else
1368 pass2_fs_dither (j_decompress_ptr cinfo,
1369 JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows)
1370 /* This version performs Floyd-Steinberg dithering */
1371 {
1372 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1373 JSAMPROW inptr; /* => current input pixel */
1374 #endif
1375 hist3d histogram = cquantize->histogram;
1376 register LOCFSERROR cur0, cur1, cur2; /* current error or pixel value */
1377 LOCFSERROR belowerr0, belowerr1, belowerr2; /* error for pixel below cur */
1378 LOCFSERROR bpreverr0, bpreverr1, bpreverr2; /* error for below/prev col */
1379 register FSERRPTR errorptr; /* => fserrors[] at column before current */
1380 histptr cachep;
1381 int dir; /* +1 or -1 depending on direction */
1382 int dir3; /* 3*dir, for advancing inptr & errorptr */
1383 int row;
1384 JDIMENSION col;
1385 #ifdef ORIGINAL_LIB_JPEG
1386 JSAMPROW outptr; /* => current output pixel */
1387 JDIMENSION width = cinfo->output_width;
1388 JSAMPLE *range_limit = cinfo->sample_range_limit;
1389 JSAMPROW colormap0 = cinfo->colormap[0];
1390 JSAMPROW colormap1 = cinfo->colormap[1];
1391 JSAMPROW colormap2 = cinfo->colormap[2];
1392 #else
1393 int *inptr; /* => current input pixel */
1394 unsigned char *outptr; /* => current output pixel */
1395 int width = oim->sx;
1396 int num_rows = oim->sy;
1397 int *colormap0 = nim->red;
1398 int *colormap1 = nim->green;
1399 int *colormap2 = nim->blue;
1400 #endif
1401 int *error_limit = cquantize->error_limiter;
1402
1403
1404 SHIFT_TEMPS for (row = 0; row < num_rows; row++)
1405 {
1406 inptr = input_buf[row];
1407 outptr = output_buf[row];
1408 if (cquantize->on_odd_row)
1409 {
1410 /* work right to left in this row */
1411 inptr += (width - 1) * 3; /* so point to rightmost pixel */
1412 outptr += width - 1;
1413 dir = -1;
1414 dir3 = -3;
1415 errorptr = cquantize->fserrors + (width + 1) * 3; /* => entry after last column */
1416 #ifdef ORIGINAL_LIB_JPEG_REVERSE_ODD_ROWS
1417 cquantize->on_odd_row = FALSE; /* flip for next time */
1418 #endif
1419 }
1420 else
1421 {
1422 /* work left to right in this row */
1423 dir = 1;
1424 dir3 = 3;
1425 errorptr = cquantize->fserrors; /* => entry before first real column */
1426 #ifdef ORIGINAL_LIB_JPEG_REVERSE_ODD_ROWS
1427 cquantize->on_odd_row = TRUE; /* flip for next time */
1428 #endif
1429 }
1430 /* Preset error values: no error propagated to first pixel from left */
1431 cur0 = cur1 = cur2 = 0;
1432 /* and no error propagated to row below yet */
1433 belowerr0 = belowerr1 = belowerr2 = 0;
1434 bpreverr0 = bpreverr1 = bpreverr2 = 0;
1435
1436 for (col = width; col > 0; col--)
1437 {
1438
1439 /* If this pixel is transparent, we want to assign it to the special
1440 * transparency color index past the end of the palette rather than
1441 * go through matching / dithering. */
1442 if ((oim->transparent >= 0) && (*inptr == oim->transparent))
1443 {
1444 *outptr = nim->colorsTotal;
1445 errorptr[0] = 0;
1446 errorptr[1] = 0;
1447 errorptr[2] = 0;
1448 errorptr[3] = 0;
1449 inptr += dir;
1450 outptr += dir;
1451 errorptr += dir3;
1452 continue;
1453 }
1454 /* curN holds the error propagated from the previous pixel on the
1455 * current line. Add the error propagated from the previous line
1456 * to form the complete error correction term for this pixel, and
1457 * round the error term (which is expressed * 16) to an integer.
1458 * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct
1459 * for either sign of the error value.
1460 * Note: errorptr points to *previous* column's array entry.
1461 */
1462 cur0 = RIGHT_SHIFT (cur0 + errorptr[dir3 + 0] + 8, 4);
1463 cur1 = RIGHT_SHIFT (cur1 + errorptr[dir3 + 1] + 8, 4);
1464 cur2 = RIGHT_SHIFT (cur2 + errorptr[dir3 + 2] + 8, 4);
1465 /* Limit the error using transfer function set by init_error_limit.
1466 * See comments with init_error_limit for rationale.
1467 */
1468 cur0 = error_limit[cur0];
1469 cur1 = error_limit[cur1];
1470 cur2 = error_limit[cur2];
1471 /* Form pixel value + error, and range-limit to 0..MAXJSAMPLE.
1472 * The maximum error is +- MAXJSAMPLE (or less with error limiting);
1473 * this sets the required size of the range_limit array.
1474 */
1475 #ifdef ORIGINAL_LIB_JPEG
1476 cur0 += GETJSAMPLE (inptr[0]);
1477 cur1 += GETJSAMPLE (inptr[1]);
1478 cur2 += GETJSAMPLE (inptr[2]);
1479 cur0 = GETJSAMPLE (range_limit[cur0]);
1480 cur1 = GETJSAMPLE (range_limit[cur1]);
1481 cur2 = GETJSAMPLE (range_limit[cur2]);
1482 #else
1483 cur0 += gdTrueColorGetRed (*inptr);
1484 cur1 += gdTrueColorGetGreen (*inptr);
1485 cur2 += gdTrueColorGetBlue (*inptr);
1486 range_limit (cur0);
1487 range_limit (cur1);
1488 range_limit (cur2);
1489 #endif
1490
1491 /* Index into the cache with adjusted pixel value */
1492 cachep =
1493 &histogram[cur0 >> C0_SHIFT][cur1 >> C1_SHIFT][cur2 >> C2_SHIFT];
1494 /* If we have not seen this color before, find nearest colormap */
1495 /* entry and update the cache */
1496 if (*cachep == 0)
1497 #ifdef ORIGINAL_LIB_JPEG
1498 fill_inverse_cmap (cinfo, cur0 >> C0_SHIFT, cur1 >> C1_SHIFT,
1499 cur2 >> C2_SHIFT);
1500 #else
1501 fill_inverse_cmap (oim, nim, cquantize, cur0 >> C0_SHIFT,
1502 cur1 >> C1_SHIFT, cur2 >> C2_SHIFT);
1503 #endif
1504 /* Now emit the colormap index for this cell */
1505 {
1506 register int pixcode = *cachep - 1;
1507 *outptr = (JSAMPLE) pixcode;
1508 /* Compute representation error for this pixel */
1509 #define GETJSAMPLE
1510 cur0 -= GETJSAMPLE (colormap0[pixcode]);
1511 cur1 -= GETJSAMPLE (colormap1[pixcode]);
1512 cur2 -= GETJSAMPLE (colormap2[pixcode]);
1513 #undef GETJSAMPLE
1514 }
1515 /* Compute error fractions to be propagated to adjacent pixels.
1516 * Add these into the running sums, and simultaneously shift the
1517 * next-line error sums left by 1 column.
1518 */
1519 {
1520 register LOCFSERROR bnexterr, delta;
1521
1522 bnexterr = cur0; /* Process component 0 */
1523 delta = cur0 * 2;
1524 cur0 += delta; /* form error * 3 */
1525 errorptr[0] = (FSERROR) (bpreverr0 + cur0);
1526 cur0 += delta; /* form error * 5 */
1527 bpreverr0 = belowerr0 + cur0;
1528 belowerr0 = bnexterr;
1529 cur0 += delta; /* form error * 7 */
1530 bnexterr = cur1; /* Process component 1 */
1531 delta = cur1 * 2;
1532 cur1 += delta; /* form error * 3 */
1533 errorptr[1] = (FSERROR) (bpreverr1 + cur1);
1534 cur1 += delta; /* form error * 5 */
1535 bpreverr1 = belowerr1 + cur1;
1536 belowerr1 = bnexterr;
1537 cur1 += delta; /* form error * 7 */
1538 bnexterr = cur2; /* Process component 2 */
1539 delta = cur2 * 2;
1540 cur2 += delta; /* form error * 3 */
1541 errorptr[2] = (FSERROR) (bpreverr2 + cur2);
1542 cur2 += delta; /* form error * 5 */
1543 bpreverr2 = belowerr2 + cur2;
1544 belowerr2 = bnexterr;
1545 cur2 += delta; /* form error * 7 */
1546 }
1547 /* At this point curN contains the 7/16 error value to be propagated
1548 * to the next pixel on the current line, and all the errors for the
1549 * next line have been shifted over. We are therefore ready to move on.
1550 */
1551 #ifdef ORIGINAL_LIB_JPEG
1552 inptr += dir3; /* Advance pixel pointers to next column */
1553 #else
1554 inptr += dir; /* Advance pixel pointers to next column */
1555 #endif
1556 outptr += dir;
1557 errorptr += dir3; /* advance errorptr to current column */
1558 }
1559 /* Post-loop cleanup: we must unload the final error values into the
1560 * final fserrors[] entry. Note we need not unload belowerrN because
1561 * it is for the dummy column before or after the actual array.
1562 */
1563 errorptr[0] = (FSERROR) bpreverr0; /* unload prev errs into array */
1564 errorptr[1] = (FSERROR) bpreverr1;
1565 errorptr[2] = (FSERROR) bpreverr2;
1566 }
1567 }
1568
1569
1570 /*
1571 * Initialize the error-limiting transfer function (lookup table).
1572 * The raw F-S error computation can potentially compute error values of up to
1573 * +- MAXJSAMPLE. But we want the maximum correction applied to a pixel to be
1574 * much less, otherwise obviously wrong pixels will be created. (Typical
1575 * effects include weird fringes at color-area boundaries, isolated bright
1576 * pixels in a dark area, etc.) The standard advice for avoiding this problem
1577 * is to ensure that the "corners" of the color cube are allocated as output
1578 * colors; then repeated errors in the same direction cannot cause cascading
1579 * error buildup. However, that only prevents the error from getting
1580 * completely out of hand; Aaron Giles reports that error limiting improves
1581 * the results even with corner colors allocated.
1582 * A simple clamping of the error values to about +- MAXJSAMPLE/8 works pretty
1583 * well, but the smoother transfer function used below is even better. Thanks
1584 * to Aaron Giles for this idea.
1585 */
1586
1587 LOCAL (void)
1588 #ifdef ORIGINAL_LIB_JPEG
1589 init_error_limit (j_decompress_ptr cinfo)
1590 #else
1591 init_error_limit (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
1592 #endif
1593 /* Allocate and fill in the error_limiter table */
1594 {
1595 int *table;
1596 int in, out;
1597 #ifdef ORIGINAL_LIB_JPEG
1598 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1599 table = (int *) (*cinfo->mem->alloc_small)
1600 ((j_common_ptr) cinfo, JPOOL_IMAGE, (MAXJSAMPLE * 2 + 1) * SIZEOF (int));
1601 #else
1602 cquantize->error_limiter_storage =
1603 (int *) safe_emalloc ((MAXJSAMPLE * 2 + 1), sizeof (int), 0);
1604 if (!cquantize->error_limiter_storage)
1605 {
1606 return;
1607 }
1608 table = cquantize->error_limiter_storage;
1609 #endif
1610
1611 table += MAXJSAMPLE; /* so can index -MAXJSAMPLE .. +MAXJSAMPLE */
1612 cquantize->error_limiter = table;
1613
1614 #define STEPSIZE ((MAXJSAMPLE+1)/16)
1615 /* Map errors 1:1 up to +- MAXJSAMPLE/16 */
1616 out = 0;
1617 for (in = 0; in < STEPSIZE; in++, out++)
1618 {
1619 table[in] = out;
1620 table[-in] = -out;
1621 }
1622 /* Map errors 1:2 up to +- 3*MAXJSAMPLE/16 */
1623 for (; in < STEPSIZE * 3; in++, out += (in & 1) ? 0 : 1)
1624 {
1625 table[in] = out;
1626 table[-in] = -out;
1627 }
1628 /* Clamp the rest to final out value (which is (MAXJSAMPLE+1)/8) */
1629 for (; in <= MAXJSAMPLE; in++)
1630 {
1631 table[in] = out;
1632 table[-in] = -out;
1633 }
1634 #undef STEPSIZE
1635 }
1636
1637
1638 /*
1639 * Finish up at the end of each pass.
1640 */
1641
1642 #ifdef ORIGINAL_LIB_JPEG
1643 METHODDEF (void)
1644 finish_pass1 (j_decompress_ptr cinfo)
1645 {
1646 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1647
1648 /* Select the representative colors and fill in cinfo->colormap */
1649 cinfo->colormap = cquantize->sv_colormap;
1650 select_colors (cinfo, cquantize->desired);
1651 /* Force next pass to zero the color index table */
1652 cquantize->needs_zeroed = TRUE;
1653 }
1654
1655
1656 METHODDEF (void)
1657 finish_pass2 (j_decompress_ptr cinfo)
1658 {
1659 /* no work */
1660 }
1661
1662 /*
1663 * Initialize for each processing pass.
1664 */
1665
1666 METHODDEF (void)
1667 start_pass_2_quant (j_decompress_ptr cinfo, boolean is_pre_scan)
1668 {
1669 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1670 hist3d histogram = cquantize->histogram;
1671 int i;
1672
1673 /* Only F-S dithering or no dithering is supported. */
1674 /* If user asks for ordered dither, give him F-S. */
1675 if (cinfo->dither_mode != JDITHER_NONE)
1676 cinfo->dither_mode = JDITHER_FS;
1677
1678 if (is_pre_scan)
1679 {
1680 /* Set up method pointers */
1681 cquantize->pub.color_quantize = prescan_quantize;
1682 cquantize->pub.finish_pass = finish_pass1;
1683 cquantize->needs_zeroed = TRUE; /* Always zero histogram */
1684 }
1685 else
1686 {
1687 /* Set up method pointers */
1688 if (cinfo->dither_mode == JDITHER_FS)
1689 cquantize->pub.color_quantize = pass2_fs_dither;
1690 else
1691 cquantize->pub.color_quantize = pass2_no_dither;
1692 cquantize->pub.finish_pass = finish_pass2;
1693
1694 /* Make sure color count is acceptable */
1695 i = cinfo->actual_number_of_colors;
1696 if (i < 1)
1697 ERREXIT1 (cinfo, JERR_QUANT_FEW_COLORS, 1);
1698 if (i > MAXNUMCOLORS)
1699 ERREXIT1 (cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS);
1700
1701 if (cinfo->dither_mode == JDITHER_FS)
1702 {
1703 size_t arraysize = (size_t) ((cinfo->output_width + 2) *
1704 (3 * SIZEOF (FSERROR)));
1705 /* Allocate Floyd-Steinberg workspace if we didn't already. */
1706 if (cquantize->fserrors == NULL)
1707 cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large)
1708 ((j_common_ptr) cinfo, JPOOL_IMAGE, arraysize);
1709 /* Initialize the propagated errors to zero. */
1710 jzero_far ((void FAR *) cquantize->fserrors, arraysize);
1711 /* Make the error-limit table if we didn't already. */
1712 if (cquantize->error_limiter == NULL)
1713 init_error_limit (cinfo);
1714 cquantize->on_odd_row = FALSE;
1715 }
1716
1717 }
1718 /* Zero the histogram or inverse color map, if necessary */
1719 if (cquantize->needs_zeroed)
1720 {
1721 for (i = 0; i < HIST_C0_ELEMS; i++)
1722 {
1723 jzero_far ((void FAR *) histogram[i],
1724 HIST_C1_ELEMS * HIST_C2_ELEMS * SIZEOF (histcell));
1725 }
1726 cquantize->needs_zeroed = FALSE;
1727 }
1728 }
1729
1730
1731 /*
1732 * Switch to a new external colormap between output passes.
1733 */
1734
1735 METHODDEF (void)
1736 new_color_map_2_quant (j_decompress_ptr cinfo)
1737 {
1738 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1739
1740 /* Reset the inverse color map */
1741 cquantize->needs_zeroed = TRUE;
1742 }
1743 #else
1744 static void
1745 zeroHistogram (hist3d histogram)
1746 {
1747 int i;
1748 /* Zero the histogram or inverse color map */
1749 for (i = 0; i < HIST_C0_ELEMS; i++)
1750 {
1751 memset (histogram[i],
1752 0, HIST_C1_ELEMS * HIST_C2_ELEMS * sizeof (histcell));
1753 }
1754 }
1755 #endif
1756
1757 static void gdImageTrueColorToPaletteBody (gdImagePtr oim, int dither, int colorsWanted, gdImagePtr *cimP);
1758
1759 gdImagePtr gdImageCreatePaletteFromTrueColor (gdImagePtr im, int dither, int colorsWanted)
1760 {
1761 gdImagePtr nim;
1762 gdImageTrueColorToPaletteBody(im, dither, colorsWanted, &nim);
1763 return nim;
1764 }
1765
1766 void gdImageTrueColorToPalette (gdImagePtr im, int dither, int colorsWanted)
1767 {
1768 gdImageTrueColorToPaletteBody(im, dither, colorsWanted, 0);
1769 }
1770
1771 /*
1772 * Module initialization routine for 2-pass color quantization.
1773 */
1774
1775 #ifdef ORIGINAL_LIB_JPEG
1776 GLOBAL (void)
1777 jinit_2pass_quantizer (j_decompress_ptr cinfo)
1778 #else
1779 static void gdImageTrueColorToPaletteBody (gdImagePtr oim, int dither, int colorsWanted, gdImagePtr *cimP)
1780 #endif
1781 {
1782 my_cquantize_ptr cquantize = NULL;
1783 int i;
1784
1785 #ifndef ORIGINAL_LIB_JPEG
1786 /* Allocate the JPEG palette-storage */
1787 size_t arraysize;
1788 int maxColors = gdMaxColors;
1789 gdImagePtr nim;
1790 if (cimP) {
1791 nim = gdImageCreate(oim->sx, oim->sy);
1792 *cimP = nim;
1793 if (!nim) {
1794 return;
1795 }
1796 } else {
1797 nim = oim;
1798 }
1799 if (!oim->trueColor)
1800 {
1801 /* (Almost) nothing to do! */
1802 if (cimP) {
1803 gdImageCopy(nim, oim, 0, 0, 0, 0, oim->sx, oim->sy);
1804 *cimP = nim;
1805 }
1806 return;
1807 }
1808
1809 /* If we have a transparent color (the alphaless mode of transparency), we
1810 * must reserve a palette entry for it at the end of the palette. */
1811 if (oim->transparent >= 0)
1812 {
1813 maxColors--;
1814 }
1815 if (colorsWanted > maxColors)
1816 {
1817 colorsWanted = maxColors;
1818 }
1819 if (!cimP) {
1820 nim->pixels = gdCalloc (sizeof (unsigned char *), oim->sy);
1821 if (!nim->pixels)
1822 {
1823 /* No can do */
1824 goto outOfMemory;
1825 }
1826 for (i = 0; (i < nim->sy); i++)
1827 {
1828 nim->pixels[i] = gdCalloc (sizeof (unsigned char *), oim->sx);
1829 if (!nim->pixels[i])
1830 {
1831 goto outOfMemory;
1832 }
1833 }
1834 }
1835 #endif
1836
1837 #ifdef ORIGINAL_LIB_JPEG
1838 cquantize = (my_cquantize_ptr)
1839 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
1840 SIZEOF (my_cquantizer));
1841 cinfo->cquantize = (struct jpeg_color_quantizer *) cquantize;
1842 cquantize->pub.start_pass = start_pass_2_quant;
1843 cquantize->pub.new_color_map = new_color_map_2_quant;
1844 /* Make sure jdmaster didn't give me a case I can't handle */
1845 if (cinfo->out_color_components != 3)
1846 ERREXIT (cinfo, JERR_NOTIMPL);
1847 #else
1848 cquantize = (my_cquantize_ptr) gdCalloc (sizeof (my_cquantizer), 1);
1849 if (!cquantize)
1850 {
1851 /* No can do */
1852 goto outOfMemory;
1853 }
1854 #endif
1855 cquantize->fserrors = NULL; /* flag optional arrays not allocated */
1856 cquantize->error_limiter = NULL;
1857
1858
1859 /* Allocate the histogram/inverse colormap storage */
1860 #ifdef ORIGINAL_LIB_JPEG
1861 cquantize->histogram = (hist3d) (*cinfo->mem->alloc_small)
1862 ((j_common_ptr) cinfo, JPOOL_IMAGE, HIST_C0_ELEMS * SIZEOF (hist2d));
1863 for (i = 0; i < HIST_C0_ELEMS; i++)
1864 {
1865 cquantize->histogram[i] = (hist2d) (*cinfo->mem->alloc_large)
1866 ((j_common_ptr) cinfo, JPOOL_IMAGE,
1867 HIST_C1_ELEMS * HIST_C2_ELEMS * SIZEOF (histcell));
1868 }
1869 cquantize->needs_zeroed = TRUE; /* histogram is garbage now */
1870 #else
1871 cquantize->histogram = (hist3d) safe_emalloc (HIST_C0_ELEMS, sizeof (hist2d), 0);
1872 for (i = 0; i < HIST_C0_ELEMS; i++)
1873 {
1874 cquantize->histogram[i] =
1875 (hist2d) safe_emalloc (HIST_C1_ELEMS * HIST_C2_ELEMS, sizeof (histcell), 0);
1876 if (!cquantize->histogram[i])
1877 {
1878 goto outOfMemory;
1879 }
1880 }
1881 #endif
1882
1883 #ifdef ORIGINAL_LIB_JPEG
1884 /* Allocate storage for the completed colormap, if required.
1885 * We do this now since it is FAR storage and may affect
1886 * the memory manager's space calculations.
1887 */
1888 if (cinfo->enable_2pass_quant)
1889 {
1890 /* Make sure color count is acceptable */
1891 int desired = cinfo->desired_number_of_colors;
1892 /* Lower bound on # of colors ... somewhat arbitrary as long as > 0 */
1893 if (desired < 8)
1894 ERREXIT1 (cinfo, JERR_QUANT_FEW_COLORS, 8);
1895 /* Make sure colormap indexes can be represented by JSAMPLEs */
1896 if (desired > MAXNUMCOLORS)
1897 ERREXIT1 (cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS);
1898 cquantize->sv_colormap = (*cinfo->mem->alloc_sarray)
1899 ((j_common_ptr) cinfo, JPOOL_IMAGE, (JDIMENSION) desired,
1900 (JDIMENSION) 3);
1901 cquantize->desired = desired;
1902 }
1903 else
1904 cquantize->sv_colormap = NULL;
1905
1906 /* Only F-S dithering or no dithering is supported. */
1907 /* If user asks for ordered dither, give him F-S. */
1908 if (cinfo->dither_mode != JDITHER_NONE)
1909 cinfo->dither_mode = JDITHER_FS;
1910
1911 /* Allocate Floyd-Steinberg workspace if necessary.
1912 * This isn't really needed until pass 2, but again it is FAR storage.
1913 * Although we will cope with a later change in dither_mode,
1914 * we do not promise to honor max_memory_to_use if dither_mode changes.
1915 */
1916 if (cinfo->dither_mode == JDITHER_FS)
1917 {
1918 cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large)
1919 ((j_common_ptr) cinfo, JPOOL_IMAGE,
1920 (size_t) ((cinfo->output_width + 2) * (3 * SIZEOF (FSERROR))));
1921 /* Might as well create the error-limiting table too. */
1922 init_error_limit (cinfo);
1923 }
1924 #else
1925
1926 cquantize->fserrors = (FSERRPTR) safe_emalloc (3, sizeof (FSERROR), 0);
1927 init_error_limit (oim, nim, cquantize);
1928 arraysize = (size_t) ((nim->sx + 2) * (3 * sizeof (FSERROR)));
1929 /* Allocate Floyd-Steinberg workspace. */
1930 cquantize->fserrors = gdRealloc(cquantize->fserrors, arraysize);
1931 memset(cquantize->fserrors, 0, arraysize);
1932 if (!cquantize->fserrors)
1933 {
1934 goto outOfMemory;
1935 }
1936 cquantize->on_odd_row = FALSE;
1937
1938 /* Do the work! */
1939 zeroHistogram (cquantize->histogram);
1940 prescan_quantize (oim, nim, cquantize);
1941 /* TBB 2.0.5: pass colorsWanted, not 256! */
1942 select_colors (oim, nim, cquantize, colorsWanted);
1943 zeroHistogram (cquantize->histogram);
1944 if (dither)
1945 {
1946 pass2_fs_dither (oim, nim, cquantize);
1947 }
1948 else
1949 {
1950 pass2_no_dither (oim, nim, cquantize);
1951 }
1952 #if 0 /* 2.0.12; we no longer attempt full alpha in palettes */
1953 if (cquantize->transparentIsPresent)
1954 {
1955 int mt = -1;
1956 int mtIndex = -1;
1957 for (i = 0; (i < im->colorsTotal); i++)
1958 {
1959 if (im->alpha[i] > mt)
1960 {
1961 mtIndex = i;
1962 mt = im->alpha[i];
1963 }
1964 }
1965 for (i = 0; (i < im->colorsTotal); i++)
1966 {
1967 if (im->alpha[i] == mt)
1968 {
1969 im->alpha[i] = gdAlphaTransparent;
1970 }
1971 }
1972 }
1973 if (cquantize->opaqueIsPresent)
1974 {
1975 int mo = 128;
1976 int moIndex = -1;
1977 for (i = 0; (i < im->colorsTotal); i++)
1978 {
1979 if (im->alpha[i] < mo)
1980 {
1981 moIndex = i;
1982 mo = im->alpha[i];
1983 }
1984 }
1985 for (i = 0; (i < im->colorsTotal); i++)
1986 {
1987 if (im->alpha[i] == mo)
1988 {
1989 im->alpha[i] = gdAlphaOpaque;
1990 }
1991 }
1992 }
1993 #endif
1994
1995 /* If we had a 'transparent' color, increment the color count so it's
1996 * officially in the palette and convert the transparent variable to point to
1997 * an index rather than a color (Its data already exists and transparent
1998 * pixels have already been mapped to it by this point, it is done late as to
1999 * avoid color matching / dithering with it). */
2000 if (oim->transparent >= 0)
2001 {
2002 nim->transparent = nim->colorsTotal;
2003 nim->colorsTotal++;
2004 }
2005
2006 /* Success! Get rid of the truecolor image data. */
2007 if (!cimP) {
2008 oim->trueColor = 0;
2009 /* Junk the truecolor pixels */
2010 for (i = 0; i < oim->sy; i++)
2011 {
2012 gdFree (oim->tpixels[i]);
2013 }
2014 gdFree (oim->tpixels);
2015 oim->tpixels = 0;
2016 }
2017 goto success;
2018 /* Tediously free stuff. */
2019 outOfMemory:
2020 if (oim->trueColor)
2021 {
2022 if (!cimP) {
2023 /* On failure only */
2024 for (i = 0; i < nim->sy; i++)
2025 {
2026 if (nim->pixels[i])
2027 {
2028 gdFree (nim->pixels[i]);
2029 }
2030 }
2031 if (nim->pixels)
2032 {
2033 gdFree (nim->pixels);
2034 }
2035 nim->pixels = 0;
2036 } else {
2037 gdImageDestroy(nim);
2038 *cimP = 0;
2039 }
2040 }
2041 success:
2042 for (i = 0; i < HIST_C0_ELEMS; i++)
2043 {
2044 if (cquantize->histogram[i])
2045 {
2046 gdFree (cquantize->histogram[i]);
2047 }
2048 }
2049 if (cquantize->histogram)
2050 {
2051 gdFree (cquantize->histogram);
2052 }
2053 if (cquantize->fserrors)
2054 {
2055 gdFree (cquantize->fserrors);
2056 }
2057 if (cquantize->error_limiter_storage)
2058 {
2059 gdFree (cquantize->error_limiter_storage);
2060 }
2061 if (cquantize)
2062 {
2063 gdFree (cquantize);
2064 }
2065
2066 #endif
2067 }
2068
2069
2070 #endif
2071
