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
344 : prescan_quantize (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
345 9 : {
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 9 : 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 9 : int width = oim->sx;
361 9 : int num_rows = oim->sy;
362 : #endif
363 :
364 1139 : for (row = 0; row < num_rows; row++)
365 : {
366 1130 : ptr = input_buf[row];
367 237776 : 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 236646 : int r = gdTrueColorGetRed (*ptr) >> C0_SHIFT;
375 236646 : int g = gdTrueColorGetGreen (*ptr) >> C1_SHIFT;
376 236646 : int b = gdTrueColorGetBlue (*ptr) >> C2_SHIFT;
377 : /* 2.0.12: Steven Brown: support a single totally transparent
378 : color in the original. */
379 236646 : if ((oim->transparent >= 0) && (*ptr == oim->transparent))
380 : {
381 6912 : ptr++;
382 6912 : continue;
383 : }
384 : #endif
385 : /* get pixel value and index into the histogram */
386 229734 : histp = &histogram[r][g][b];
387 : /* increment, check for overflow and undo increment if so. */
388 229734 : if (++(*histp) == 0)
389 0 : (*histp)--;
390 : #ifdef ORIGINAL_LIB_JPEG
391 : ptr += 3;
392 : #else
393 229734 : ptr++;
394 : #endif
395 : }
396 : }
397 9 : }
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 517 : {
427 : register boxptr boxp;
428 : register int i;
429 517 : register long maxc = 0;
430 517 : boxptr which = NULL;
431 :
432 33546 : for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++)
433 : {
434 33029 : if (boxp->colorcount > maxc && boxp->volume > 0)
435 : {
436 1825 : which = boxp;
437 1825 : maxc = boxp->colorcount;
438 : }
439 : }
440 517 : 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 508 : {
448 : register boxptr boxp;
449 : register int i;
450 508 : register INT32 maxv = 0;
451 508 : boxptr which = NULL;
452 :
453 98044 : for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++)
454 : {
455 97536 : if (boxp->volume > maxv)
456 : {
457 1469 : which = boxp;
458 1469 : maxv = boxp->volume;
459 : }
460 : }
461 508 : 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 2051 : {
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 2051 : 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 2051 : c0min = boxp->c0min;
484 2051 : c0max = boxp->c0max;
485 2051 : c1min = boxp->c1min;
486 2051 : c1max = boxp->c1max;
487 2051 : c2min = boxp->c2min;
488 2051 : c2max = boxp->c2max;
489 :
490 2051 : if (c0max > c0min)
491 993 : for (c0 = c0min; c0 <= c0max; c0++)
492 7721 : for (c1 = c1min; c1 <= c1max; c1++)
493 : {
494 7449 : histp = &histogram[c0][c1][c2min];
495 182986 : for (c2 = c2min; c2 <= c2max; c2++)
496 176257 : if (*histp++ != 0)
497 : {
498 720 : boxp->c0min = c0min = c0;
499 720 : goto have_c0min;
500 : }
501 : }
502 2051 : have_c0min:
503 2051 : if (c0max > c0min)
504 963 : for (c0 = c0max; c0 >= c0min; c0--)
505 12172 : for (c1 = c1min; c1 <= c1max; c1++)
506 : {
507 11896 : histp = &histogram[c0][c1][c2min];
508 333168 : for (c2 = c2min; c2 <= c2max; c2++)
509 321958 : if (*histp++ != 0)
510 : {
511 686 : boxp->c0max = c0max = c0;
512 686 : goto have_c0max;
513 : }
514 : }
515 2051 : have_c0max:
516 2051 : if (c1max > c1min)
517 1838 : for (c1 = c1min; c1 <= c1max; c1++)
518 5313 : for (c0 = c0min; c0 <= c0max; c0++)
519 : {
520 4984 : histp = &histogram[c0][c1][c2min];
521 97213 : for (c2 = c2min; c2 <= c2max; c2++)
522 93737 : if (*histp++ != 0)
523 : {
524 1508 : boxp->c1min = c1min = c1;
525 1508 : goto have_c1min;
526 : }
527 : }
528 2051 : have_c1min:
529 2051 : if (c1max > c1min)
530 1861 : for (c1 = c1max; c1 >= c1min; c1--)
531 6415 : for (c0 = c0min; c0 <= c0max; c0++)
532 : {
533 5911 : histp = &histogram[c0][c1][c2min];
534 131615 : for (c2 = c2min; c2 <= c2max; c2++)
535 127060 : if (*histp++ != 0)
536 : {
537 1356 : boxp->c1max = c1max = c1;
538 1356 : goto have_c1max;
539 : }
540 : }
541 2051 : have_c1max:
542 2051 : if (c2max > c2min)
543 2704 : for (c2 = c2min; c2 <= c2max; c2++)
544 9091 : for (c0 = c0min; c0 <= c0max; c0++)
545 : {
546 8208 : histp = &histogram[c0][c1min][c2];
547 167649 : for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)
548 161261 : if (*histp != 0)
549 : {
550 1820 : boxp->c2min = c2min = c2;
551 1820 : goto have_c2min;
552 : }
553 : }
554 2051 : have_c2min:
555 2051 : if (c2max > c2min)
556 2490 : for (c2 = c2max; c2 >= c2min; c2--)
557 6799 : for (c0 = c0min; c0 <= c0max; c0++)
558 : {
559 6006 : histp = &histogram[c0][c1min][c2];
560 122084 : for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)
561 117774 : if (*histp != 0)
562 : {
563 1696 : boxp->c2max = c2max = c2;
564 1696 : goto have_c2max;
565 : }
566 : }
567 2051 : 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 2051 : dist0 = ((c0max - c0min) << C0_SHIFT) * C0_SCALE;
578 2051 : dist1 = ((c1max - c1min) << C1_SHIFT) * C1_SCALE;
579 2051 : dist2 = ((c2max - c2min) << C2_SHIFT) * C2_SCALE;
580 2051 : boxp->volume = dist0 * dist0 + dist1 * dist1 + dist2 * dist2;
581 :
582 : /* Now scan remaining volume of box and compute population */
583 2051 : ccount = 0;
584 5792 : for (c0 = c0min; c0 <= c0max; c0++)
585 32535 : for (c1 = c1min; c1 <= c1max; c1++)
586 : {
587 28794 : histp = &histogram[c0][c1][c2min];
588 537134 : for (c2 = c2min; c2 <= c2max; c2++, histp++)
589 508340 : if (*histp != 0)
590 : {
591 20411 : ccount++;
592 : }
593 : }
594 2051 : boxp->colorcount = ccount;
595 2051 : }
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 9 : {
608 : int n, lb;
609 : int c0, c1, c2, cmax;
610 : register boxptr b1, b2;
611 :
612 1039 : while (numboxes < desired_colors)
613 : {
614 : /* Select box to split.
615 : * Current algorithm: by population for first half, then by volume.
616 : */
617 1025 : if (numboxes * 2 <= desired_colors)
618 : {
619 517 : b1 = find_biggest_color_pop (boxlist, numboxes);
620 : }
621 : else
622 : {
623 508 : b1 = find_biggest_volume (boxlist, numboxes);
624 : }
625 1025 : if (b1 == NULL) /* no splittable boxes left! */
626 4 : break;
627 1021 : b2 = &boxlist[numboxes]; /* where new box will go */
628 : /* Copy the color bounds to the new box. */
629 1021 : b2->c0max = b1->c0max;
630 1021 : b2->c1max = b1->c1max;
631 1021 : b2->c2max = b1->c2max;
632 1021 : b2->c0min = b1->c0min;
633 1021 : b2->c1min = b1->c1min;
634 1021 : 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 1021 : c0 = ((b1->c0max - b1->c0min) << C0_SHIFT) * C0_SCALE;
640 1021 : c1 = ((b1->c1max - b1->c1min) << C1_SHIFT) * C1_SCALE;
641 1021 : 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 1021 : cmax = c1;
647 1021 : n = 1;
648 1021 : if (c0 > cmax)
649 : {
650 443 : cmax = c0;
651 443 : n = 0;
652 : }
653 1021 : if (c2 > cmax)
654 : {
655 200 : 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 1021 : switch (n)
677 : {
678 : case 0:
679 431 : lb = (b1->c0max + b1->c0min) / 2;
680 431 : b1->c0max = lb;
681 431 : b2->c0min = lb + 1;
682 431 : break;
683 : case 1:
684 390 : lb = (b1->c1max + b1->c1min) / 2;
685 390 : b1->c1max = lb;
686 390 : b2->c1min = lb + 1;
687 390 : break;
688 : case 2:
689 200 : lb = (b1->c2max + b1->c2min) / 2;
690 200 : b1->c2max = lb;
691 200 : 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 1021 : update_box (oim, nim, cquantize, b1);
700 1021 : update_box (oim, nim, cquantize, b2);
701 : #endif
702 1021 : numboxes++;
703 : }
704 9 : 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 1030 : {
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 1030 : hist3d histogram = cquantize->histogram;
722 : histptr histp;
723 : int c0, c1, c2;
724 : int c0min, c0max, c1min, c1max, c2min, c2max;
725 1030 : long count = 0; /* 2.0.28: = 0 */
726 1030 : long total = 0;
727 1030 : long c0total = 0;
728 1030 : long c1total = 0;
729 1030 : long c2total = 0;
730 :
731 1030 : c0min = boxp->c0min;
732 1030 : c0max = boxp->c0max;
733 1030 : c1min = boxp->c1min;
734 1030 : c1max = boxp->c1max;
735 1030 : c2min = boxp->c2min;
736 1030 : c2max = boxp->c2max;
737 :
738 2122 : for (c0 = c0min; c0 <= c0max; c0++)
739 4575 : for (c1 = c1min; c1 <= c1max; c1++)
740 : {
741 3483 : histp = &histogram[c0][c1][c2min];
742 72321 : for (c2 = c2min; c2 <= c2max; c2++)
743 : {
744 68838 : if ((count = *histp++) != 0)
745 : {
746 2079 : total += count;
747 2079 : c0total +=
748 : ((c0 << C0_SHIFT) + ((1 << C0_SHIFT) >> 1)) * count;
749 2079 : c1total +=
750 : ((c1 << C1_SHIFT) + ((1 << C1_SHIFT) >> 1)) * count;
751 2079 : 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 1030 : if (count)
764 : {
765 1026 : nim->red[icolor] = (int) ((c0total + (total >> 1)) / total);
766 1026 : nim->green[icolor] = (int) ((c1total + (total >> 1)) / total);
767 1026 : nim->blue[icolor] = (int) ((c2total + (total >> 1)) / total);
768 : }
769 : else
770 : {
771 4 : nim->red[icolor] = 255;
772 4 : nim->green[icolor] = 255;
773 4 : nim->blue[icolor] = 255;
774 : }
775 1030 : nim->open[icolor] = 0;
776 : #endif
777 1030 : }
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 9 : {
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 9 : boxlist = (boxptr) safe_emalloc(desired_colors, sizeof (box), 1);
798 : #endif
799 : /* Initialize one box containing whole space */
800 9 : numboxes = 1;
801 9 : boxlist[0].c0min = 0;
802 9 : boxlist[0].c0max = MAXJSAMPLE >> C0_SHIFT;
803 9 : boxlist[0].c1min = 0;
804 9 : boxlist[0].c1max = MAXJSAMPLE >> C1_SHIFT;
805 9 : boxlist[0].c2min = 0;
806 9 : 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 9 : update_box (oim, nim, cquantize, &boxlist[0]);
820 : /* Perform median-cut to produce final box list */
821 9 : numboxes = median_cut (oim, nim, cquantize, boxlist, numboxes, desired_colors);
822 : /* Compute the representative color for each box, fill colormap */
823 1039 : for (i = 0; i < numboxes; i++)
824 1030 : compute_color (oim, nim, cquantize, &boxlist[i], i);
825 9 : 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 9 : if (oim->transparent >= 0)
832 : {
833 : /* Save the transparent color. */
834 1 : nim->red[nim->colorsTotal] = gdTrueColorGetRed (oim->transparent);
835 1 : nim->green[nim->colorsTotal] = gdTrueColorGetGreen (oim->transparent);
836 1 : nim->blue[nim->colorsTotal] = gdTrueColorGetBlue (oim->transparent);
837 1 : nim->alpha[nim->colorsTotal] = gdAlphaTransparent;
838 1 : nim->open[nim->colorsTotal] = 0;
839 : }
840 :
841 9 : gdFree (boxlist);
842 : #endif
843 9 : }
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 240 : {
939 : #ifdef ORIGINAL_LIB_JPEG
940 : int numcolors = cinfo->actual_number_of_colors;
941 : #else
942 240 : 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 240 : maxc0 = minc0 + ((1 << BOX_C0_SHIFT) - (1 << C0_SHIFT));
957 240 : centerc0 = (minc0 + maxc0) >> 1;
958 240 : maxc1 = minc1 + ((1 << BOX_C1_SHIFT) - (1 << C1_SHIFT));
959 240 : centerc1 = (minc1 + maxc1) >> 1;
960 240 : maxc2 = minc2 + ((1 << BOX_C2_SHIFT) - (1 << C2_SHIFT));
961 240 : 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 240 : minmaxdist = 0x7FFFFFFFL;
972 :
973 59645 : 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 59405 : x = nim->red[i];
980 : #endif
981 59405 : if (x < minc0)
982 : {
983 26840 : tdist = (x - minc0) * C0_SCALE;
984 26840 : min_dist = tdist * tdist;
985 26840 : tdist = (x - maxc0) * C0_SCALE;
986 26840 : max_dist = tdist * tdist;
987 : }
988 32565 : else if (x > maxc0)
989 : {
990 22308 : tdist = (x - maxc0) * C0_SCALE;
991 22308 : min_dist = tdist * tdist;
992 22308 : tdist = (x - minc0) * C0_SCALE;
993 22308 : max_dist = tdist * tdist;
994 : }
995 : else
996 : {
997 : /* within cell range so no contribution to min_dist */
998 10257 : min_dist = 0;
999 10257 : if (x <= centerc0)
1000 : {
1001 5024 : tdist = (x - maxc0) * C0_SCALE;
1002 5024 : max_dist = tdist * tdist;
1003 : }
1004 : else
1005 : {
1006 5233 : tdist = (x - minc0) * C0_SCALE;
1007 5233 : max_dist = tdist * tdist;
1008 : }
1009 : }
1010 :
1011 : #ifdef ORIGINAL_LIB_JPEG
1012 : x = GETJSAMPLE (cinfo->colormap[1][i]);
1013 : #else
1014 59405 : x = nim->green[i];
1015 : #endif
1016 59405 : if (x < minc1)
1017 : {
1018 23917 : tdist = (x - minc1) * C1_SCALE;
1019 23917 : min_dist += tdist * tdist;
1020 23917 : tdist = (x - maxc1) * C1_SCALE;
1021 23917 : max_dist += tdist * tdist;
1022 : }
1023 35488 : else if (x > maxc1)
1024 : {
1025 24532 : tdist = (x - maxc1) * C1_SCALE;
1026 24532 : min_dist += tdist * tdist;
1027 24532 : tdist = (x - minc1) * C1_SCALE;
1028 24532 : max_dist += tdist * tdist;
1029 : }
1030 : else
1031 : {
1032 : /* within cell range so no contribution to min_dist */
1033 10956 : if (x <= centerc1)
1034 : {
1035 5728 : tdist = (x - maxc1) * C1_SCALE;
1036 5728 : max_dist += tdist * tdist;
1037 : }
1038 : else
1039 : {
1040 5228 : tdist = (x - minc1) * C1_SCALE;
1041 5228 : max_dist += tdist * tdist;
1042 : }
1043 : }
1044 :
1045 : #ifdef ORIGINAL_LIB_JPEG
1046 : x = GETJSAMPLE (cinfo->colormap[2][i]);
1047 : #else
1048 59405 : x = nim->blue[i];
1049 : #endif
1050 59405 : if (x < minc2)
1051 : {
1052 22515 : tdist = (x - minc2) * C2_SCALE;
1053 22515 : min_dist += tdist * tdist;
1054 22515 : tdist = (x - maxc2) * C2_SCALE;
1055 22515 : max_dist += tdist * tdist;
1056 : }
1057 36890 : else if (x > maxc2)
1058 : {
1059 27415 : tdist = (x - maxc2) * C2_SCALE;
1060 27415 : min_dist += tdist * tdist;
1061 27415 : tdist = (x - minc2) * C2_SCALE;
1062 27415 : max_dist += tdist * tdist;
1063 : }
1064 : else
1065 : {
1066 : /* within cell range so no contribution to min_dist */
1067 9475 : if (x <= centerc2)
1068 : {
1069 4936 : tdist = (x - maxc2) * C2_SCALE;
1070 4936 : max_dist += tdist * tdist;
1071 : }
1072 : else
1073 : {
1074 4539 : tdist = (x - minc2) * C2_SCALE;
1075 4539 : max_dist += tdist * tdist;
1076 : }
1077 : }
1078 :
1079 59405 : mindist[i] = min_dist; /* save away the results */
1080 59405 : if (max_dist < minmaxdist)
1081 1315 : 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 240 : ncolors = 0;
1089 59645 : for (i = 0; i < numcolors; i++)
1090 : {
1091 59405 : if (mindist[i] <= minmaxdist)
1092 13482 : colorlist[ncolors++] = (JSAMPLE) i;
1093 : }
1094 240 : 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 240 : {
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 240 : bptr = bestdist;
1128 30960 : for (i = BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS - 1; i >= 0; i--)
1129 30720 : *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 13722 : 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 13482 : icolor = colorlist[i];
1152 13482 : r = nim->red[icolor];
1153 13482 : g = nim->green[icolor];
1154 13482 : b = nim->blue[icolor];
1155 : #endif
1156 :
1157 : /* Compute (square of) distance from minc0/c1/c2 to this color */
1158 13482 : inc0 = (minc0 - r) * C0_SCALE;
1159 13482 : dist0 = inc0 * inc0;
1160 13482 : inc1 = (minc1 - g) * C1_SCALE;
1161 13482 : dist0 += inc1 * inc1;
1162 13482 : inc2 = (minc2 - b) * C2_SCALE;
1163 13482 : dist0 += inc2 * inc2;
1164 : /* Form the initial difference increments */
1165 13482 : inc0 = inc0 * (2 * STEP_C0) + STEP_C0 * STEP_C0;
1166 13482 : inc1 = inc1 * (2 * STEP_C1) + STEP_C1 * STEP_C1;
1167 13482 : inc2 = inc2 * (2 * STEP_C2) + STEP_C2 * STEP_C2;
1168 : /* Now loop over all cells in box, updating distance per Thomas method */
1169 13482 : bptr = bestdist;
1170 13482 : cptr = bestcolor;
1171 13482 : xx0 = inc0;
1172 67410 : for (ic0 = BOX_C0_ELEMS - 1; ic0 >= 0; ic0--)
1173 : {
1174 53928 : dist1 = dist0;
1175 53928 : xx1 = inc1;
1176 485352 : for (ic1 = BOX_C1_ELEMS - 1; ic1 >= 0; ic1--)
1177 : {
1178 431424 : dist2 = dist1;
1179 431424 : xx2 = inc2;
1180 2157120 : for (ic2 = BOX_C2_ELEMS - 1; ic2 >= 0; ic2--)
1181 : {
1182 1725696 : if (dist2 < *bptr)
1183 : {
1184 119277 : *bptr = dist2;
1185 119277 : *cptr = (JSAMPLE) icolor;
1186 : }
1187 1725696 : dist2 += xx2;
1188 1725696 : xx2 += 2 * STEP_C2 * STEP_C2;
1189 1725696 : bptr++;
1190 1725696 : cptr++;
1191 : }
1192 431424 : dist1 += xx1;
1193 431424 : xx1 += 2 * STEP_C1 * STEP_C1;
1194 : }
1195 53928 : dist0 += xx0;
1196 53928 : xx0 += 2 * STEP_C0 * STEP_C0;
1197 : }
1198 : }
1199 240 : }
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 240 : {
1214 : #ifdef ORIGINAL_LIB_JPEG
1215 : my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1216 : #endif
1217 240 : 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 240 : c0 >>= BOX_C0_LOG;
1230 240 : c1 >>= BOX_C1_LOG;
1231 240 : 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 240 : minc0 = (c0 << BOX_C0_SHIFT) + ((1 << C0_SHIFT) >> 1);
1238 240 : minc1 = (c1 << BOX_C1_SHIFT) + ((1 << C1_SHIFT) >> 1);
1239 240 : 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 240 : numcolors =
1252 : find_nearby_colors (oim, nim, cquantize, minc0, minc1, minc2, colorlist);
1253 240 : 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 240 : c0 <<= BOX_C0_LOG; /* convert ID back to base cell indexes */
1259 240 : c1 <<= BOX_C1_LOG;
1260 240 : c2 <<= BOX_C2_LOG;
1261 240 : cptr = bestcolor;
1262 1200 : for (ic0 = 0; ic0 < BOX_C0_ELEMS; ic0++)
1263 : {
1264 8640 : for (ic1 = 0; ic1 < BOX_C1_ELEMS; ic1++)
1265 : {
1266 7680 : cachep = &histogram[c0 + ic0][c1 + ic1][c2];
1267 38400 : for (ic2 = 0; ic2 < BOX_C2_ELEMS; ic2++)
1268 : {
1269 : #ifdef ORIGINAL_LIB_JPEG
1270 : *cachep++ = (histcell) (GETJSAMPLE (*cptr++) + 1);
1271 : #else
1272 30720 : *cachep++ = (histcell) ((*cptr++) + 1);
1273 : #endif
1274 : }
1275 : }
1276 : }
1277 240 : }
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 0 : {
1288 : register int *inptr;
1289 : register unsigned char *outptr;
1290 0 : int width = oim->sx;
1291 0 : 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 0 : hist3d histogram = cquantize->histogram;
1302 : register int c0, c1, c2;
1303 : int row;
1304 : JDIMENSION col;
1305 : register histptr cachep;
1306 :
1307 :
1308 0 : for (row = 0; row < num_rows; row++)
1309 : {
1310 0 : inptr = input_buf[row];
1311 0 : outptr = output_buf[row];
1312 0 : 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 0 : r = gdTrueColorGetRed (*inptr);
1322 0 : 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 0 : 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 0 : if ((oim->transparent >= 0) && (oim->transparent == *(inptr - 1)))
1333 : {
1334 0 : *outptr++ = nim->colorsTotal;
1335 0 : inptr++;
1336 0 : continue;
1337 : }
1338 0 : inptr++;
1339 : #endif
1340 0 : c0 = r >> C0_SHIFT;
1341 0 : c1 = g >> C1_SHIFT;
1342 0 : c2 = b >> C2_SHIFT;
1343 0 : cachep = &histogram[c0][c1][c2];
1344 : /* If we have not seen this color before, find nearest colormap entry */
1345 : /* and update the cache */
1346 0 : if (*cachep == 0)
1347 : #ifdef ORIGINAL_LIB_JPEG
1348 : fill_inverse_cmap (cinfo, c0, c1, c2);
1349 : #else
1350 0 : 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 0 : *outptr++ = (*cachep - 1);
1357 : #endif
1358 : }
1359 : }
1360 0 : }
1361 :
1362 :
1363 : METHODDEF (void)
1364 : #ifndef ORIGINAL_LIB_JPEG
1365 : pass2_fs_dither (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
1366 9 : {
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 9 : 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 9 : int width = oim->sx;
1396 9 : int num_rows = oim->sy;
1397 9 : int *colormap0 = nim->red;
1398 9 : int *colormap1 = nim->green;
1399 9 : int *colormap2 = nim->blue;
1400 : #endif
1401 9 : int *error_limit = cquantize->error_limiter;
1402 :
1403 :
1404 1139 : SHIFT_TEMPS for (row = 0; row < num_rows; row++)
1405 : {
1406 1130 : inptr = input_buf[row];
1407 1130 : outptr = output_buf[row];
1408 1130 : if (cquantize->on_odd_row)
1409 : {
1410 : /* work right to left in this row */
1411 0 : inptr += (width - 1) * 3; /* so point to rightmost pixel */
1412 0 : outptr += width - 1;
1413 0 : dir = -1;
1414 0 : dir3 = -3;
1415 0 : 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 1130 : dir = 1;
1424 1130 : dir3 = 3;
1425 1130 : 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 1130 : cur0 = cur1 = cur2 = 0;
1432 : /* and no error propagated to row below yet */
1433 1130 : belowerr0 = belowerr1 = belowerr2 = 0;
1434 1130 : bpreverr0 = bpreverr1 = bpreverr2 = 0;
1435 :
1436 237776 : 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 236646 : if ((oim->transparent >= 0) && (*inptr == oim->transparent))
1443 : {
1444 6912 : *outptr = nim->colorsTotal;
1445 6912 : errorptr[0] = 0;
1446 6912 : errorptr[1] = 0;
1447 6912 : errorptr[2] = 0;
1448 6912 : errorptr[3] = 0;
1449 6912 : inptr += dir;
1450 6912 : outptr += dir;
1451 6912 : errorptr += dir3;
1452 6912 : 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 229734 : cur0 = RIGHT_SHIFT (cur0 + errorptr[dir3 + 0] + 8, 4);
1463 229734 : cur1 = RIGHT_SHIFT (cur1 + errorptr[dir3 + 1] + 8, 4);
1464 229734 : 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 229734 : cur0 = error_limit[cur0];
1469 229734 : cur1 = error_limit[cur1];
1470 229734 : 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 229734 : cur0 += gdTrueColorGetRed (*inptr);
1484 229734 : cur1 += gdTrueColorGetGreen (*inptr);
1485 229734 : cur2 += gdTrueColorGetBlue (*inptr);
1486 229734 : range_limit (cur0);
1487 229734 : range_limit (cur1);
1488 229734 : range_limit (cur2);
1489 : #endif
1490 :
1491 : /* Index into the cache with adjusted pixel value */
1492 229734 : 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 229734 : 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 240 : 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 229734 : register int pixcode = *cachep - 1;
1507 229734 : *outptr = (JSAMPLE) pixcode;
1508 : /* Compute representation error for this pixel */
1509 : #define GETJSAMPLE
1510 229734 : cur0 -= GETJSAMPLE (colormap0[pixcode]);
1511 229734 : cur1 -= GETJSAMPLE (colormap1[pixcode]);
1512 229734 : 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 229734 : bnexterr = cur0; /* Process component 0 */
1523 229734 : delta = cur0 * 2;
1524 229734 : cur0 += delta; /* form error * 3 */
1525 229734 : errorptr[0] = (FSERROR) (bpreverr0 + cur0);
1526 229734 : cur0 += delta; /* form error * 5 */
1527 229734 : bpreverr0 = belowerr0 + cur0;
1528 229734 : belowerr0 = bnexterr;
1529 229734 : cur0 += delta; /* form error * 7 */
1530 229734 : bnexterr = cur1; /* Process component 1 */
1531 229734 : delta = cur1 * 2;
1532 229734 : cur1 += delta; /* form error * 3 */
1533 229734 : errorptr[1] = (FSERROR) (bpreverr1 + cur1);
1534 229734 : cur1 += delta; /* form error * 5 */
1535 229734 : bpreverr1 = belowerr1 + cur1;
1536 229734 : belowerr1 = bnexterr;
1537 229734 : cur1 += delta; /* form error * 7 */
1538 229734 : bnexterr = cur2; /* Process component 2 */
1539 229734 : delta = cur2 * 2;
1540 229734 : cur2 += delta; /* form error * 3 */
1541 229734 : errorptr[2] = (FSERROR) (bpreverr2 + cur2);
1542 229734 : cur2 += delta; /* form error * 5 */
1543 229734 : bpreverr2 = belowerr2 + cur2;
1544 229734 : belowerr2 = bnexterr;
1545 229734 : 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 229734 : inptr += dir; /* Advance pixel pointers to next column */
1555 : #endif
1556 229734 : outptr += dir;
1557 229734 : 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 1130 : errorptr[0] = (FSERROR) bpreverr0; /* unload prev errs into array */
1564 1130 : errorptr[1] = (FSERROR) bpreverr1;
1565 1130 : errorptr[2] = (FSERROR) bpreverr2;
1566 : }
1567 9 : }
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 9 : {
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 9 : cquantize->error_limiter_storage =
1603 : (int *) safe_emalloc ((MAXJSAMPLE * 2 + 1), sizeof (int), 0);
1604 9 : if (!cquantize->error_limiter_storage)
1605 : {
1606 0 : return;
1607 : }
1608 9 : table = cquantize->error_limiter_storage;
1609 : #endif
1610 :
1611 9 : table += MAXJSAMPLE; /* so can index -MAXJSAMPLE .. +MAXJSAMPLE */
1612 9 : cquantize->error_limiter = table;
1613 :
1614 : #define STEPSIZE ((MAXJSAMPLE+1)/16)
1615 : /* Map errors 1:1 up to +- MAXJSAMPLE/16 */
1616 9 : out = 0;
1617 153 : for (in = 0; in < STEPSIZE; in++, out++)
1618 : {
1619 144 : table[in] = out;
1620 144 : table[-in] = -out;
1621 : }
1622 : /* Map errors 1:2 up to +- 3*MAXJSAMPLE/16 */
1623 297 : for (; in < STEPSIZE * 3; in++, out += (in & 1) ? 0 : 1)
1624 : {
1625 288 : table[in] = out;
1626 288 : table[-in] = -out;
1627 : }
1628 : /* Clamp the rest to final out value (which is (MAXJSAMPLE+1)/8) */
1629 1881 : for (; in <= MAXJSAMPLE; in++)
1630 : {
1631 1872 : table[in] = out;
1632 1872 : 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 18 : {
1747 : int i;
1748 : /* Zero the histogram or inverse color map */
1749 594 : for (i = 0; i < HIST_C0_ELEMS; i++)
1750 : {
1751 576 : memset (histogram[i],
1752 : 0, HIST_C1_ELEMS * HIST_C2_ELEMS * sizeof (histcell));
1753 : }
1754 18 : }
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 4 : {
1761 : gdImagePtr nim;
1762 4 : gdImageTrueColorToPaletteBody(im, dither, colorsWanted, &nim);
1763 4 : return nim;
1764 : }
1765 :
1766 : void gdImageTrueColorToPalette (gdImagePtr im, int dither, int colorsWanted)
1767 6 : {
1768 6 : gdImageTrueColorToPaletteBody(im, dither, colorsWanted, 0);
1769 6 : }
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 10 : {
1782 10 : 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 10 : int maxColors = gdMaxColors;
1789 : gdImagePtr nim;
1790 10 : if (cimP) {
1791 4 : nim = gdImageCreate(oim->sx, oim->sy);
1792 4 : *cimP = nim;
1793 4 : if (!nim) {
1794 0 : return;
1795 : }
1796 : } else {
1797 6 : nim = oim;
1798 : }
1799 10 : if (!oim->trueColor)
1800 : {
1801 : /* (Almost) nothing to do! */
1802 1 : if (cimP) {
1803 0 : gdImageCopy(nim, oim, 0, 0, 0, 0, oim->sx, oim->sy);
1804 0 : *cimP = nim;
1805 : }
1806 1 : 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 9 : if (oim->transparent >= 0)
1812 : {
1813 1 : maxColors--;
1814 : }
1815 9 : if (colorsWanted > maxColors)
1816 : {
1817 1 : colorsWanted = maxColors;
1818 : }
1819 9 : if (!cimP) {
1820 5 : nim->pixels = gdCalloc (sizeof (unsigned char *), oim->sy);
1821 5 : if (!nim->pixels)
1822 : {
1823 : /* No can do */
1824 0 : goto outOfMemory;
1825 : }
1826 586 : for (i = 0; (i < nim->sy); i++)
1827 : {
1828 581 : nim->pixels[i] = gdCalloc (sizeof (unsigned char *), oim->sx);
1829 581 : if (!nim->pixels[i])
1830 : {
1831 0 : 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 9 : cquantize = (my_cquantize_ptr) gdCalloc (sizeof (my_cquantizer), 1);
1849 9 : if (!cquantize)
1850 : {
1851 : /* No can do */
1852 0 : goto outOfMemory;
1853 : }
1854 : #endif
1855 9 : cquantize->fserrors = NULL; /* flag optional arrays not allocated */
1856 9 : 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 9 : cquantize->histogram = (hist3d) safe_emalloc (HIST_C0_ELEMS, sizeof (hist2d), 0);
1872 297 : for (i = 0; i < HIST_C0_ELEMS; i++)
1873 : {
1874 288 : cquantize->histogram[i] =
1875 : (hist2d) safe_emalloc (HIST_C1_ELEMS * HIST_C2_ELEMS, sizeof (histcell), 0);
1876 288 : if (!cquantize->histogram[i])
1877 : {
1878 0 : 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 9 : cquantize->fserrors = (FSERRPTR) safe_emalloc (3, sizeof (FSERROR), 0);
1927 9 : init_error_limit (oim, nim, cquantize);
1928 9 : arraysize = (size_t) ((nim->sx + 2) * (3 * sizeof (FSERROR)));
1929 : /* Allocate Floyd-Steinberg workspace. */
1930 9 : cquantize->fserrors = gdRealloc(cquantize->fserrors, arraysize);
1931 9 : memset(cquantize->fserrors, 0, arraysize);
1932 9 : if (!cquantize->fserrors)
1933 : {
1934 0 : goto outOfMemory;
1935 : }
1936 9 : cquantize->on_odd_row = FALSE;
1937 :
1938 : /* Do the work! */
1939 9 : zeroHistogram (cquantize->histogram);
1940 9 : prescan_quantize (oim, nim, cquantize);
1941 : /* TBB 2.0.5: pass colorsWanted, not 256! */
1942 9 : select_colors (oim, nim, cquantize, colorsWanted);
1943 9 : zeroHistogram (cquantize->histogram);
1944 9 : if (dither)
1945 : {
1946 9 : pass2_fs_dither (oim, nim, cquantize);
1947 : }
1948 : else
1949 : {
1950 0 : 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 9 : if (oim->transparent >= 0)
2001 : {
2002 1 : nim->transparent = nim->colorsTotal;
2003 1 : nim->colorsTotal++;
2004 : }
2005 :
2006 : /* Success! Get rid of the truecolor image data. */
2007 9 : if (!cimP) {
2008 5 : oim->trueColor = 0;
2009 : /* Junk the truecolor pixels */
2010 586 : for (i = 0; i < oim->sy; i++)
2011 : {
2012 581 : gdFree (oim->tpixels[i]);
2013 : }
2014 5 : gdFree (oim->tpixels);
2015 5 : oim->tpixels = 0;
2016 : }
2017 9 : goto success;
2018 : /* Tediously free stuff. */
2019 0 : outOfMemory:
2020 0 : if (oim->trueColor)
2021 : {
2022 0 : if (!cimP) {
2023 : /* On failure only */
2024 0 : for (i = 0; i < nim->sy; i++)
2025 : {
2026 0 : if (nim->pixels[i])
2027 : {
2028 0 : gdFree (nim->pixels[i]);
2029 : }
2030 : }
2031 0 : if (nim->pixels)
2032 : {
2033 0 : gdFree (nim->pixels);
2034 : }
2035 0 : nim->pixels = 0;
2036 : } else {
2037 0 : gdImageDestroy(nim);
2038 0 : *cimP = 0;
2039 : }
2040 : }
2041 9 : success:
2042 297 : for (i = 0; i < HIST_C0_ELEMS; i++)
2043 : {
2044 288 : if (cquantize->histogram[i])
2045 : {
2046 288 : gdFree (cquantize->histogram[i]);
2047 : }
2048 : }
2049 9 : if (cquantize->histogram)
2050 : {
2051 9 : gdFree (cquantize->histogram);
2052 : }
2053 9 : if (cquantize->fserrors)
2054 : {
2055 9 : gdFree (cquantize->fserrors);
2056 : }
2057 9 : if (cquantize->error_limiter_storage)
2058 : {
2059 9 : gdFree (cquantize->error_limiter_storage);
2060 : }
2061 9 : if (cquantize)
2062 : {
2063 9 : gdFree (cquantize);
2064 : }
2065 :
2066 : #endif
2067 : }
2068 :
2069 :
2070 : /* bring the palette colors in im2 to be closer to im1
2071 : *
2072 : */
2073 : int gdImageColorMatch (gdImagePtr im1, gdImagePtr im2)
2074 5 : {
2075 : unsigned long *buf; /* stores our calculations */
2076 : unsigned long *bp; /* buf ptr */
2077 : int color, rgb;
2078 : int x,y;
2079 : int count;
2080 :
2081 5 : if( !im1->trueColor ) {
2082 1 : return -1; /* im1 must be True Color */
2083 : }
2084 4 : if( im2->trueColor ) {
2085 1 : return -2; /* im2 must be indexed */
2086 : }
2087 3 : if( (im1->sx != im2->sx) || (im1->sy != im2->sy) ) {
2088 1 : return -3; /* the images are meant to be the same dimensions */
2089 : }
2090 2 : if (im2->colorsTotal<1) {
2091 1 : return -4; /* At least 1 color must be allocated */
2092 : }
2093 :
2094 1 : buf = (unsigned long *)safe_emalloc(sizeof(unsigned long), 5 * im2->colorsTotal, 0);
2095 1 : memset( buf, 0, sizeof(unsigned long) * 5 * im2->colorsTotal );
2096 :
2097 111 : for (x=0; x<im1->sx; x++) {
2098 2310 : for( y=0; y<im1->sy; y++ ) {
2099 2200 : color = im2->pixels[y][x];
2100 2200 : rgb = im1->tpixels[y][x];
2101 2200 : bp = buf + (color * 5);
2102 2200 : (*(bp++))++;
2103 2200 : *(bp++) += gdTrueColorGetRed(rgb);
2104 2200 : *(bp++) += gdTrueColorGetGreen(rgb);
2105 2200 : *(bp++) += gdTrueColorGetBlue(rgb);
2106 2200 : *(bp++) += gdTrueColorGetAlpha(rgb);
2107 : }
2108 : }
2109 1 : bp = buf;
2110 2 : for (color=0; color<im2->colorsTotal; color++) {
2111 1 : count = *(bp++);
2112 1 : if( count > 0 ) {
2113 1 : im2->red[color] = *(bp++) / count;
2114 1 : im2->green[color] = *(bp++) / count;
2115 1 : im2->blue[color] = *(bp++) / count;
2116 1 : im2->alpha[color] = *(bp++) / count;
2117 : } else {
2118 0 : bp += 4;
2119 : }
2120 : }
2121 1 : gdFree(buf);
2122 1 : return 0;
2123 : }
2124 :
2125 :
2126 : #endif
|
