4 * This file was part of the Independent JPEG Group's software:
5 * Copyright (C) 1991-1996, Thomas G. Lane.
6 * libjpeg-turbo Modifications:
7 * Copyright (C) 2009, 2014-2015, 2020, 2022-2023, D. R. Commander.
8 * For conditions of distribution and use, see the accompanying README.ijg
11 * This file contains 2-pass color quantization (color mapping) routines.
12 * These routines provide selection of a custom color map for an image,
13 * followed by mapping of the image to that color map, with optional
14 * Floyd-Steinberg dithering.
15 * It is also possible to use just the second pass to map to an arbitrary
16 * externally-given color map.
18 * Note: ordered dithering is not supported, since there isn't any fast
19 * way to compute intercolor distances; it's unclear that ordered dither's
20 * fundamental assumptions even hold with an irregularly spaced color map.
23 #define JPEG_INTERNALS
26 #include "jsamplecomp.h"
28 #if defined(QUANT_2PASS_SUPPORTED) && BITS_IN_JSAMPLE != 16
32 * This module implements the well-known Heckbert paradigm for color
33 * quantization. Most of the ideas used here can be traced back to
34 * Heckbert's seminal paper
35 * Heckbert, Paul. "Color Image Quantization for Frame Buffer Display",
36 * Proc. SIGGRAPH '82, Computer Graphics v.16 #3 (July 1982), pp 297-304.
38 * In the first pass over the image, we accumulate a histogram showing the
39 * usage count of each possible color. To keep the histogram to a reasonable
40 * size, we reduce the precision of the input; typical practice is to retain
41 * 5 or 6 bits per color, so that 8 or 4 different input values are counted
42 * in the same histogram cell.
44 * Next, the color-selection step begins with a box representing the whole
45 * color space, and repeatedly splits the "largest" remaining box until we
46 * have as many boxes as desired colors. Then the mean color in each
47 * remaining box becomes one of the possible output colors.
49 * The second pass over the image maps each input pixel to the closest output
50 * color (optionally after applying a Floyd-Steinberg dithering correction).
51 * This mapping is logically trivial, but making it go fast enough requires
54 * Heckbert-style quantizers vary a good deal in their policies for choosing
55 * the "largest" box and deciding where to cut it. The particular policies
56 * used here have proved out well in experimental comparisons, but better ones
59 * In earlier versions of the IJG code, this module quantized in YCbCr color
60 * space, processing the raw upsampled data without a color conversion step.
61 * This allowed the color conversion math to be done only once per colormap
62 * entry, not once per pixel. However, that optimization precluded other
63 * useful optimizations (such as merging color conversion with upsampling)
64 * and it also interfered with desired capabilities such as quantizing to an
65 * externally-supplied colormap. We have therefore abandoned that approach.
66 * The present code works in the post-conversion color space, typically RGB.
68 * To improve the visual quality of the results, we actually work in scaled
69 * RGB space, giving G distances more weight than R, and R in turn more than
70 * B. To do everything in integer math, we must use integer scale factors.
71 * The 2/3/1 scale factors used here correspond loosely to the relative
72 * weights of the colors in the NTSC grayscale equation.
73 * If you want to use this code to quantize a non-RGB color space, you'll
74 * probably need to change these scale factors.
77 #define R_SCALE 2 /* scale R distances by this much */
78 #define G_SCALE 3 /* scale G distances by this much */
79 #define B_SCALE 1 /* and B by this much */
81 static const int c_scales
[3] = { R_SCALE
, G_SCALE
, B_SCALE
};
82 #define C0_SCALE c_scales[rgb_red[cinfo->out_color_space]]
83 #define C1_SCALE c_scales[rgb_green[cinfo->out_color_space]]
84 #define C2_SCALE c_scales[rgb_blue[cinfo->out_color_space]]
87 * First we have the histogram data structure and routines for creating it.
89 * The number of bits of precision can be adjusted by changing these symbols.
90 * We recommend keeping 6 bits for G and 5 each for R and B.
91 * If you have plenty of memory and cycles, 6 bits all around gives marginally
92 * better results; if you are short of memory, 5 bits all around will save
93 * some space but degrade the results.
94 * To maintain a fully accurate histogram, we'd need to allocate a "long"
95 * (preferably unsigned long) for each cell. In practice this is overkill;
96 * we can get by with 16 bits per cell. Few of the cell counts will overflow,
97 * and clamping those that do overflow to the maximum value will give close-
98 * enough results. This reduces the recommended histogram size from 256Kb
99 * to 128Kb, which is a useful savings on PC-class machines.
100 * (In the second pass the histogram space is re-used for pixel mapping data;
101 * in that capacity, each cell must be able to store zero to the number of
102 * desired colors. 16 bits/cell is plenty for that too.)
103 * Since the JPEG code is intended to run in small memory model on 80x86
104 * machines, we can't just allocate the histogram in one chunk. Instead
105 * of a true 3-D array, we use a row of pointers to 2-D arrays. Each
106 * pointer corresponds to a C0 value (typically 2^5 = 32 pointers) and
107 * each 2-D array has 2^6*2^5 = 2048 or 2^6*2^6 = 4096 entries.
110 #define MAXNUMCOLORS (_MAXJSAMPLE + 1) /* maximum size of colormap */
112 /* These will do the right thing for either R,G,B or B,G,R color order,
113 * but you may not like the results for other color orders.
115 #define HIST_C0_BITS 5 /* bits of precision in R/B histogram */
116 #define HIST_C1_BITS 6 /* bits of precision in G histogram */
117 #define HIST_C2_BITS 5 /* bits of precision in B/R histogram */
119 /* Number of elements along histogram axes. */
120 #define HIST_C0_ELEMS (1 << HIST_C0_BITS)
121 #define HIST_C1_ELEMS (1 << HIST_C1_BITS)
122 #define HIST_C2_ELEMS (1 << HIST_C2_BITS)
124 /* These are the amounts to shift an input value to get a histogram index. */
125 #define C0_SHIFT (BITS_IN_JSAMPLE - HIST_C0_BITS)
126 #define C1_SHIFT (BITS_IN_JSAMPLE - HIST_C1_BITS)
127 #define C2_SHIFT (BITS_IN_JSAMPLE - HIST_C2_BITS)
130 typedef UINT16 histcell
; /* histogram cell; prefer an unsigned type */
132 typedef histcell
*histptr
; /* for pointers to histogram cells */
134 typedef histcell hist1d
[HIST_C2_ELEMS
]; /* typedefs for the array */
135 typedef hist1d
*hist2d
; /* type for the 2nd-level pointers */
136 typedef hist2d
*hist3d
; /* type for top-level pointer */
139 /* Declarations for Floyd-Steinberg dithering.
141 * Errors are accumulated into the array fserrors[], at a resolution of
142 * 1/16th of a pixel count. The error at a given pixel is propagated
143 * to its not-yet-processed neighbors using the standard F-S fractions,
146 * We work left-to-right on even rows, right-to-left on odd rows.
148 * We can get away with a single array (holding one row's worth of errors)
149 * by using it to store the current row's errors at pixel columns not yet
150 * processed, but the next row's errors at columns already processed. We
151 * need only a few extra variables to hold the errors immediately around the
152 * current column. (If we are lucky, those variables are in registers, but
153 * even if not, they're probably cheaper to access than array elements are.)
155 * The fserrors[] array has (#columns + 2) entries; the extra entry at
156 * each end saves us from special-casing the first and last pixels.
157 * Each entry is three values long, one value for each color component.
160 #if BITS_IN_JSAMPLE == 8
161 typedef INT16 FSERROR
; /* 16 bits should be enough */
162 typedef int LOCFSERROR
; /* use 'int' for calculation temps */
164 typedef JLONG FSERROR
; /* may need more than 16 bits */
165 typedef JLONG LOCFSERROR
; /* be sure calculation temps are big enough */
168 typedef FSERROR
*FSERRPTR
; /* pointer to error array */
171 /* Private subobject */
174 struct jpeg_color_quantizer pub
; /* public fields */
176 /* Space for the eventually created colormap is stashed here */
177 _JSAMPARRAY sv_colormap
; /* colormap allocated at init time */
178 int desired
; /* desired # of colors = size of colormap */
180 /* Variables for accumulating image statistics */
181 hist3d histogram
; /* pointer to the histogram */
183 boolean needs_zeroed
; /* TRUE if next pass must zero histogram */
185 /* Variables for Floyd-Steinberg dithering */
186 FSERRPTR fserrors
; /* accumulated errors */
187 boolean on_odd_row
; /* flag to remember which row we are on */
188 int *error_limiter
; /* table for clamping the applied error */
191 typedef my_cquantizer
*my_cquantize_ptr
;
195 * Prescan some rows of pixels.
196 * In this module the prescan simply updates the histogram, which has been
197 * initialized to zeroes by start_pass.
198 * An output_buf parameter is required by the method signature, but no data
199 * is actually output (in fact the buffer controller is probably passing a
204 prescan_quantize(j_decompress_ptr cinfo
, _JSAMPARRAY input_buf
,
205 _JSAMPARRAY output_buf
, int num_rows
)
207 my_cquantize_ptr cquantize
= (my_cquantize_ptr
)cinfo
->cquantize
;
208 register _JSAMPROW ptr
;
209 register histptr histp
;
210 register hist3d histogram
= cquantize
->histogram
;
213 JDIMENSION width
= cinfo
->output_width
;
215 for (row
= 0; row
< num_rows
; row
++) {
216 ptr
= input_buf
[row
];
217 for (col
= width
; col
> 0; col
--) {
218 /* get pixel value and index into the histogram */
219 histp
= &histogram
[ptr
[0] >> C0_SHIFT
]
221 [ptr
[2] >> C2_SHIFT
];
222 /* increment, check for overflow and undo increment if so. */
232 * Next we have the really interesting routines: selection of a colormap
233 * given the completed histogram.
234 * These routines work with a list of "boxes", each representing a rectangular
235 * subset of the input color space (to histogram precision).
239 /* The bounds of the box (inclusive); expressed as histogram indexes */
243 /* The volume (actually 2-norm) of the box */
245 /* The number of nonzero histogram cells within this box */
253 find_biggest_color_pop(boxptr boxlist
, int numboxes
)
254 /* Find the splittable box with the largest color population */
255 /* Returns NULL if no splittable boxes remain */
257 register boxptr boxp
;
259 register long maxc
= 0;
262 for (i
= 0, boxp
= boxlist
; i
< numboxes
; i
++, boxp
++) {
263 if (boxp
->colorcount
> maxc
&& boxp
->volume
> 0) {
265 maxc
= boxp
->colorcount
;
273 find_biggest_volume(boxptr boxlist
, int numboxes
)
274 /* Find the splittable box with the largest (scaled) volume */
275 /* Returns NULL if no splittable boxes remain */
277 register boxptr boxp
;
279 register JLONG maxv
= 0;
282 for (i
= 0, boxp
= boxlist
; i
< numboxes
; i
++, boxp
++) {
283 if (boxp
->volume
> maxv
) {
293 update_box(j_decompress_ptr cinfo
, boxptr boxp
)
294 /* Shrink the min/max bounds of a box to enclose only nonzero elements, */
295 /* and recompute its volume and population */
297 my_cquantize_ptr cquantize
= (my_cquantize_ptr
)cinfo
->cquantize
;
298 hist3d histogram
= cquantize
->histogram
;
301 int c0min
, c0max
, c1min
, c1max
, c2min
, c2max
;
302 JLONG dist0
, dist1
, dist2
;
305 c0min
= boxp
->c0min
; c0max
= boxp
->c0max
;
306 c1min
= boxp
->c1min
; c1max
= boxp
->c1max
;
307 c2min
= boxp
->c2min
; c2max
= boxp
->c2max
;
310 for (c0
= c0min
; c0
<= c0max
; c0
++)
311 for (c1
= c1min
; c1
<= c1max
; c1
++) {
312 histp
= &histogram
[c0
][c1
][c2min
];
313 for (c2
= c2min
; c2
<= c2max
; c2
++)
315 boxp
->c0min
= c0min
= c0
;
321 for (c0
= c0max
; c0
>= c0min
; c0
--)
322 for (c1
= c1min
; c1
<= c1max
; c1
++) {
323 histp
= &histogram
[c0
][c1
][c2min
];
324 for (c2
= c2min
; c2
<= c2max
; c2
++)
326 boxp
->c0max
= c0max
= c0
;
332 for (c1
= c1min
; c1
<= c1max
; c1
++)
333 for (c0
= c0min
; c0
<= c0max
; c0
++) {
334 histp
= &histogram
[c0
][c1
][c2min
];
335 for (c2
= c2min
; c2
<= c2max
; c2
++)
337 boxp
->c1min
= c1min
= c1
;
343 for (c1
= c1max
; c1
>= c1min
; c1
--)
344 for (c0
= c0min
; c0
<= c0max
; c0
++) {
345 histp
= &histogram
[c0
][c1
][c2min
];
346 for (c2
= c2min
; c2
<= c2max
; c2
++)
348 boxp
->c1max
= c1max
= c1
;
354 for (c2
= c2min
; c2
<= c2max
; c2
++)
355 for (c0
= c0min
; c0
<= c0max
; c0
++) {
356 histp
= &histogram
[c0
][c1min
][c2
];
357 for (c1
= c1min
; c1
<= c1max
; c1
++, histp
+= HIST_C2_ELEMS
)
359 boxp
->c2min
= c2min
= c2
;
365 for (c2
= c2max
; c2
>= c2min
; c2
--)
366 for (c0
= c0min
; c0
<= c0max
; c0
++) {
367 histp
= &histogram
[c0
][c1min
][c2
];
368 for (c1
= c1min
; c1
<= c1max
; c1
++, histp
+= HIST_C2_ELEMS
)
370 boxp
->c2max
= c2max
= c2
;
376 /* Update box volume.
377 * We use 2-norm rather than real volume here; this biases the method
378 * against making long narrow boxes, and it has the side benefit that
379 * a box is splittable iff norm > 0.
380 * Since the differences are expressed in histogram-cell units,
381 * we have to shift back to _JSAMPLE units to get consistent distances;
382 * after which, we scale according to the selected distance scale factors.
384 dist0
= ((c0max
- c0min
) << C0_SHIFT
) * C0_SCALE
;
385 dist1
= ((c1max
- c1min
) << C1_SHIFT
) * C1_SCALE
;
386 dist2
= ((c2max
- c2min
) << C2_SHIFT
) * C2_SCALE
;
387 boxp
->volume
= dist0
* dist0
+ dist1
* dist1
+ dist2
* dist2
;
389 /* Now scan remaining volume of box and compute population */
391 for (c0
= c0min
; c0
<= c0max
; c0
++)
392 for (c1
= c1min
; c1
<= c1max
; c1
++) {
393 histp
= &histogram
[c0
][c1
][c2min
];
394 for (c2
= c2min
; c2
<= c2max
; c2
++, histp
++)
399 boxp
->colorcount
= ccount
;
404 median_cut(j_decompress_ptr cinfo
, boxptr boxlist
, int numboxes
,
406 /* Repeatedly select and split the largest box until we have enough boxes */
409 int c0
, c1
, c2
, cmax
;
410 register boxptr b1
, b2
;
412 while (numboxes
< desired_colors
) {
413 /* Select box to split.
414 * Current algorithm: by population for first half, then by volume.
416 if (numboxes
* 2 <= desired_colors
) {
417 b1
= find_biggest_color_pop(boxlist
, numboxes
);
419 b1
= find_biggest_volume(boxlist
, numboxes
);
421 if (b1
== NULL
) /* no splittable boxes left! */
423 b2
= &boxlist
[numboxes
]; /* where new box will go */
424 /* Copy the color bounds to the new box. */
425 b2
->c0max
= b1
->c0max
; b2
->c1max
= b1
->c1max
; b2
->c2max
= b1
->c2max
;
426 b2
->c0min
= b1
->c0min
; b2
->c1min
= b1
->c1min
; b2
->c2min
= b1
->c2min
;
427 /* Choose which axis to split the box on.
428 * Current algorithm: longest scaled axis.
429 * See notes in update_box about scaling distances.
431 c0
= ((b1
->c0max
- b1
->c0min
) << C0_SHIFT
) * C0_SCALE
;
432 c1
= ((b1
->c1max
- b1
->c1min
) << C1_SHIFT
) * C1_SCALE
;
433 c2
= ((b1
->c2max
- b1
->c2min
) << C2_SHIFT
) * C2_SCALE
;
434 /* We want to break any ties in favor of green, then red, blue last.
435 * This code does the right thing for R,G,B or B,G,R color orders only.
437 if (rgb_red
[cinfo
->out_color_space
] == 0) {
439 if (c0
> cmax
) { cmax
= c0
; n
= 0; }
440 if (c2
> cmax
) { n
= 2; }
443 if (c2
> cmax
) { cmax
= c2
; n
= 2; }
444 if (c0
> cmax
) { n
= 0; }
446 /* Choose split point along selected axis, and update box bounds.
447 * Current algorithm: split at halfway point.
448 * (Since the box has been shrunk to minimum volume,
449 * any split will produce two nonempty subboxes.)
450 * Note that lb value is max for lower box, so must be < old max.
454 lb
= (b1
->c0max
+ b1
->c0min
) / 2;
459 lb
= (b1
->c1max
+ b1
->c1min
) / 2;
464 lb
= (b1
->c2max
+ b1
->c2min
) / 2;
469 /* Update stats for boxes */
470 update_box(cinfo
, b1
);
471 update_box(cinfo
, b2
);
479 compute_color(j_decompress_ptr cinfo
, boxptr boxp
, int icolor
)
480 /* Compute representative color for a box, put it in colormap[icolor] */
482 /* Current algorithm: mean weighted by pixels (not colors) */
483 /* Note it is important to get the rounding correct! */
484 my_cquantize_ptr cquantize
= (my_cquantize_ptr
)cinfo
->cquantize
;
485 hist3d histogram
= cquantize
->histogram
;
488 int c0min
, c0max
, c1min
, c1max
, c2min
, c2max
;
495 c0min
= boxp
->c0min
; c0max
= boxp
->c0max
;
496 c1min
= boxp
->c1min
; c1max
= boxp
->c1max
;
497 c2min
= boxp
->c2min
; c2max
= boxp
->c2max
;
499 for (c0
= c0min
; c0
<= c0max
; c0
++)
500 for (c1
= c1min
; c1
<= c1max
; c1
++) {
501 histp
= &histogram
[c0
][c1
][c2min
];
502 for (c2
= c2min
; c2
<= c2max
; c2
++) {
503 if ((count
= *histp
++) != 0) {
505 c0total
+= ((c0
<< C0_SHIFT
) + ((1 << C0_SHIFT
) >> 1)) * count
;
506 c1total
+= ((c1
<< C1_SHIFT
) + ((1 << C1_SHIFT
) >> 1)) * count
;
507 c2total
+= ((c2
<< C2_SHIFT
) + ((1 << C2_SHIFT
) >> 1)) * count
;
512 ((_JSAMPARRAY
)cinfo
->colormap
)[0][icolor
] =
513 (_JSAMPLE
)((c0total
+ (total
>> 1)) / total
);
514 ((_JSAMPARRAY
)cinfo
->colormap
)[1][icolor
] =
515 (_JSAMPLE
)((c1total
+ (total
>> 1)) / total
);
516 ((_JSAMPARRAY
)cinfo
->colormap
)[2][icolor
] =
517 (_JSAMPLE
)((c2total
+ (total
>> 1)) / total
);
522 select_colors(j_decompress_ptr cinfo
, int desired_colors
)
523 /* Master routine for color selection */
529 /* Allocate workspace for box list */
530 boxlist
= (boxptr
)(*cinfo
->mem
->alloc_small
)
531 ((j_common_ptr
)cinfo
, JPOOL_IMAGE
, desired_colors
* sizeof(box
));
532 /* Initialize one box containing whole space */
534 boxlist
[0].c0min
= 0;
535 boxlist
[0].c0max
= _MAXJSAMPLE
>> C0_SHIFT
;
536 boxlist
[0].c1min
= 0;
537 boxlist
[0].c1max
= _MAXJSAMPLE
>> C1_SHIFT
;
538 boxlist
[0].c2min
= 0;
539 boxlist
[0].c2max
= _MAXJSAMPLE
>> C2_SHIFT
;
540 /* Shrink it to actually-used volume and set its statistics */
541 update_box(cinfo
, &boxlist
[0]);
542 /* Perform median-cut to produce final box list */
543 numboxes
= median_cut(cinfo
, boxlist
, numboxes
, desired_colors
);
544 /* Compute the representative color for each box, fill colormap */
545 for (i
= 0; i
< numboxes
; i
++)
546 compute_color(cinfo
, &boxlist
[i
], i
);
547 cinfo
->actual_number_of_colors
= numboxes
;
548 TRACEMS1(cinfo
, 1, JTRC_QUANT_SELECTED
, numboxes
);
553 * These routines are concerned with the time-critical task of mapping input
554 * colors to the nearest color in the selected colormap.
556 * We re-use the histogram space as an "inverse color map", essentially a
557 * cache for the results of nearest-color searches. All colors within a
558 * histogram cell will be mapped to the same colormap entry, namely the one
559 * closest to the cell's center. This may not be quite the closest entry to
560 * the actual input color, but it's almost as good. A zero in the cache
561 * indicates we haven't found the nearest color for that cell yet; the array
562 * is cleared to zeroes before starting the mapping pass. When we find the
563 * nearest color for a cell, its colormap index plus one is recorded in the
564 * cache for future use. The pass2 scanning routines call fill_inverse_cmap
565 * when they need to use an unfilled entry in the cache.
567 * Our method of efficiently finding nearest colors is based on the "locally
568 * sorted search" idea described by Heckbert and on the incremental distance
569 * calculation described by Spencer W. Thomas in chapter III.1 of Graphics
570 * Gems II (James Arvo, ed. Academic Press, 1991). Thomas points out that
571 * the distances from a given colormap entry to each cell of the histogram can
572 * be computed quickly using an incremental method: the differences between
573 * distances to adjacent cells themselves differ by a constant. This allows a
574 * fairly fast implementation of the "brute force" approach of computing the
575 * distance from every colormap entry to every histogram cell. Unfortunately,
576 * it needs a work array to hold the best-distance-so-far for each histogram
577 * cell (because the inner loop has to be over cells, not colormap entries).
578 * The work array elements have to be JLONGs, so the work array would need
579 * 256Kb at our recommended precision. This is not feasible in DOS machines.
581 * To get around these problems, we apply Thomas' method to compute the
582 * nearest colors for only the cells within a small subbox of the histogram.
583 * The work array need be only as big as the subbox, so the memory usage
584 * problem is solved. Furthermore, we need not fill subboxes that are never
585 * referenced in pass2; many images use only part of the color gamut, so a
586 * fair amount of work is saved. An additional advantage of this
587 * approach is that we can apply Heckbert's locality criterion to quickly
588 * eliminate colormap entries that are far away from the subbox; typically
589 * three-fourths of the colormap entries are rejected by Heckbert's criterion,
590 * and we need not compute their distances to individual cells in the subbox.
591 * The speed of this approach is heavily influenced by the subbox size: too
592 * small means too much overhead, too big loses because Heckbert's criterion
593 * can't eliminate as many colormap entries. Empirically the best subbox
594 * size seems to be about 1/512th of the histogram (1/8th in each direction).
596 * Thomas' article also describes a refined method which is asymptotically
597 * faster than the brute-force method, but it is also far more complex and
598 * cannot efficiently be applied to small subboxes. It is therefore not
599 * useful for programs intended to be portable to DOS machines. On machines
600 * with plenty of memory, filling the whole histogram in one shot with Thomas'
601 * refined method might be faster than the present code --- but then again,
602 * it might not be any faster, and it's certainly more complicated.
606 /* log2(histogram cells in update box) for each axis; this can be adjusted */
607 #define BOX_C0_LOG (HIST_C0_BITS - 3)
608 #define BOX_C1_LOG (HIST_C1_BITS - 3)
609 #define BOX_C2_LOG (HIST_C2_BITS - 3)
611 #define BOX_C0_ELEMS (1 << BOX_C0_LOG) /* # of hist cells in update box */
612 #define BOX_C1_ELEMS (1 << BOX_C1_LOG)
613 #define BOX_C2_ELEMS (1 << BOX_C2_LOG)
615 #define BOX_C0_SHIFT (C0_SHIFT + BOX_C0_LOG)
616 #define BOX_C1_SHIFT (C1_SHIFT + BOX_C1_LOG)
617 #define BOX_C2_SHIFT (C2_SHIFT + BOX_C2_LOG)
621 * The next three routines implement inverse colormap filling. They could
622 * all be folded into one big routine, but splitting them up this way saves
623 * some stack space (the mindist[] and bestdist[] arrays need not coexist)
624 * and may allow some compilers to produce better code by registerizing more
625 * inner-loop variables.
629 find_nearby_colors(j_decompress_ptr cinfo
, int minc0
, int minc1
, int minc2
,
630 _JSAMPLE colorlist
[])
631 /* Locate the colormap entries close enough to an update box to be candidates
632 * for the nearest entry to some cell(s) in the update box. The update box
633 * is specified by the center coordinates of its first cell. The number of
634 * candidate colormap entries is returned, and their colormap indexes are
635 * placed in colorlist[].
636 * This routine uses Heckbert's "locally sorted search" criterion to select
637 * the colors that need further consideration.
640 int numcolors
= cinfo
->actual_number_of_colors
;
641 int maxc0
, maxc1
, maxc2
;
642 int centerc0
, centerc1
, centerc2
;
644 JLONG minmaxdist
, min_dist
, max_dist
, tdist
;
645 JLONG mindist
[MAXNUMCOLORS
]; /* min distance to colormap entry i */
647 /* Compute true coordinates of update box's upper corner and center.
648 * Actually we compute the coordinates of the center of the upper-corner
649 * histogram cell, which are the upper bounds of the volume we care about.
650 * Note that since ">>" rounds down, the "center" values may be closer to
651 * min than to max; hence comparisons to them must be "<=", not "<".
653 maxc0
= minc0
+ ((1 << BOX_C0_SHIFT
) - (1 << C0_SHIFT
));
654 centerc0
= (minc0
+ maxc0
) >> 1;
655 maxc1
= minc1
+ ((1 << BOX_C1_SHIFT
) - (1 << C1_SHIFT
));
656 centerc1
= (minc1
+ maxc1
) >> 1;
657 maxc2
= minc2
+ ((1 << BOX_C2_SHIFT
) - (1 << C2_SHIFT
));
658 centerc2
= (minc2
+ maxc2
) >> 1;
660 /* For each color in colormap, find:
661 * 1. its minimum squared-distance to any point in the update box
662 * (zero if color is within update box);
663 * 2. its maximum squared-distance to any point in the update box.
664 * Both of these can be found by considering only the corners of the box.
665 * We save the minimum distance for each color in mindist[];
666 * only the smallest maximum distance is of interest.
668 minmaxdist
= 0x7FFFFFFFL
;
670 for (i
= 0; i
< numcolors
; i
++) {
671 /* We compute the squared-c0-distance term, then add in the other two. */
672 x
= ((_JSAMPARRAY
)cinfo
->colormap
)[0][i
];
674 tdist
= (x
- minc0
) * C0_SCALE
;
675 min_dist
= tdist
* tdist
;
676 tdist
= (x
- maxc0
) * C0_SCALE
;
677 max_dist
= tdist
* tdist
;
678 } else if (x
> maxc0
) {
679 tdist
= (x
- maxc0
) * C0_SCALE
;
680 min_dist
= tdist
* tdist
;
681 tdist
= (x
- minc0
) * C0_SCALE
;
682 max_dist
= tdist
* tdist
;
684 /* within cell range so no contribution to min_dist */
687 tdist
= (x
- maxc0
) * C0_SCALE
;
688 max_dist
= tdist
* tdist
;
690 tdist
= (x
- minc0
) * C0_SCALE
;
691 max_dist
= tdist
* tdist
;
695 x
= ((_JSAMPARRAY
)cinfo
->colormap
)[1][i
];
697 tdist
= (x
- minc1
) * C1_SCALE
;
698 min_dist
+= tdist
* tdist
;
699 tdist
= (x
- maxc1
) * C1_SCALE
;
700 max_dist
+= tdist
* tdist
;
701 } else if (x
> maxc1
) {
702 tdist
= (x
- maxc1
) * C1_SCALE
;
703 min_dist
+= tdist
* tdist
;
704 tdist
= (x
- minc1
) * C1_SCALE
;
705 max_dist
+= tdist
* tdist
;
707 /* within cell range so no contribution to min_dist */
709 tdist
= (x
- maxc1
) * C1_SCALE
;
710 max_dist
+= tdist
* tdist
;
712 tdist
= (x
- minc1
) * C1_SCALE
;
713 max_dist
+= tdist
* tdist
;
717 x
= ((_JSAMPARRAY
)cinfo
->colormap
)[2][i
];
719 tdist
= (x
- minc2
) * C2_SCALE
;
720 min_dist
+= tdist
* tdist
;
721 tdist
= (x
- maxc2
) * C2_SCALE
;
722 max_dist
+= tdist
* tdist
;
723 } else if (x
> maxc2
) {
724 tdist
= (x
- maxc2
) * C2_SCALE
;
725 min_dist
+= tdist
* tdist
;
726 tdist
= (x
- minc2
) * C2_SCALE
;
727 max_dist
+= tdist
* tdist
;
729 /* within cell range so no contribution to min_dist */
731 tdist
= (x
- maxc2
) * C2_SCALE
;
732 max_dist
+= tdist
* tdist
;
734 tdist
= (x
- minc2
) * C2_SCALE
;
735 max_dist
+= tdist
* tdist
;
739 mindist
[i
] = min_dist
; /* save away the results */
740 if (max_dist
< minmaxdist
)
741 minmaxdist
= max_dist
;
744 /* Now we know that no cell in the update box is more than minmaxdist
745 * away from some colormap entry. Therefore, only colors that are
746 * within minmaxdist of some part of the box need be considered.
749 for (i
= 0; i
< numcolors
; i
++) {
750 if (mindist
[i
] <= minmaxdist
)
751 colorlist
[ncolors
++] = (_JSAMPLE
)i
;
758 find_best_colors(j_decompress_ptr cinfo
, int minc0
, int minc1
, int minc2
,
759 int numcolors
, _JSAMPLE colorlist
[], _JSAMPLE bestcolor
[])
760 /* Find the closest colormap entry for each cell in the update box,
761 * given the list of candidate colors prepared by find_nearby_colors.
762 * Return the indexes of the closest entries in the bestcolor[] array.
763 * This routine uses Thomas' incremental distance calculation method to
764 * find the distance from a colormap entry to successive cells in the box.
769 register JLONG
*bptr
; /* pointer into bestdist[] array */
770 _JSAMPLE
*cptr
; /* pointer into bestcolor[] array */
771 JLONG dist0
, dist1
; /* initial distance values */
772 register JLONG dist2
; /* current distance in inner loop */
773 JLONG xx0
, xx1
; /* distance increments */
775 JLONG inc0
, inc1
, inc2
; /* initial values for increments */
776 /* This array holds the distance to the nearest-so-far color for each cell */
777 JLONG bestdist
[BOX_C0_ELEMS
* BOX_C1_ELEMS
* BOX_C2_ELEMS
];
779 /* Initialize best-distance for each cell of the update box */
781 for (i
= BOX_C0_ELEMS
* BOX_C1_ELEMS
* BOX_C2_ELEMS
- 1; i
>= 0; i
--)
782 *bptr
++ = 0x7FFFFFFFL
;
784 /* For each color selected by find_nearby_colors,
785 * compute its distance to the center of each cell in the box.
786 * If that's less than best-so-far, update best distance and color number.
789 /* Nominal steps between cell centers ("x" in Thomas article) */
790 #define STEP_C0 ((1 << C0_SHIFT) * C0_SCALE)
791 #define STEP_C1 ((1 << C1_SHIFT) * C1_SCALE)
792 #define STEP_C2 ((1 << C2_SHIFT) * C2_SCALE)
794 for (i
= 0; i
< numcolors
; i
++) {
795 icolor
= colorlist
[i
];
796 /* Compute (square of) distance from minc0/c1/c2 to this color */
797 inc0
= (minc0
- ((_JSAMPARRAY
)cinfo
->colormap
)[0][icolor
]) * C0_SCALE
;
799 inc1
= (minc1
- ((_JSAMPARRAY
)cinfo
->colormap
)[1][icolor
]) * C1_SCALE
;
800 dist0
+= inc1
* inc1
;
801 inc2
= (minc2
- ((_JSAMPARRAY
)cinfo
->colormap
)[2][icolor
]) * C2_SCALE
;
802 dist0
+= inc2
* inc2
;
803 /* Form the initial difference increments */
804 inc0
= inc0
* (2 * STEP_C0
) + STEP_C0
* STEP_C0
;
805 inc1
= inc1
* (2 * STEP_C1
) + STEP_C1
* STEP_C1
;
806 inc2
= inc2
* (2 * STEP_C2
) + STEP_C2
* STEP_C2
;
807 /* Now loop over all cells in box, updating distance per Thomas method */
811 for (ic0
= BOX_C0_ELEMS
- 1; ic0
>= 0; ic0
--) {
814 for (ic1
= BOX_C1_ELEMS
- 1; ic1
>= 0; ic1
--) {
817 for (ic2
= BOX_C2_ELEMS
- 1; ic2
>= 0; ic2
--) {
820 *cptr
= (_JSAMPLE
)icolor
;
823 xx2
+= 2 * STEP_C2
* STEP_C2
;
828 xx1
+= 2 * STEP_C1
* STEP_C1
;
831 xx0
+= 2 * STEP_C0
* STEP_C0
;
838 fill_inverse_cmap(j_decompress_ptr cinfo
, int c0
, int c1
, int c2
)
839 /* Fill the inverse-colormap entries in the update box that contains */
840 /* histogram cell c0/c1/c2. (Only that one cell MUST be filled, but */
841 /* we can fill as many others as we wish.) */
843 my_cquantize_ptr cquantize
= (my_cquantize_ptr
)cinfo
->cquantize
;
844 hist3d histogram
= cquantize
->histogram
;
845 int minc0
, minc1
, minc2
; /* lower left corner of update box */
847 register _JSAMPLE
*cptr
; /* pointer into bestcolor[] array */
848 register histptr cachep
; /* pointer into main cache array */
849 /* This array lists the candidate colormap indexes. */
850 _JSAMPLE colorlist
[MAXNUMCOLORS
];
851 int numcolors
; /* number of candidate colors */
852 /* This array holds the actually closest colormap index for each cell. */
853 _JSAMPLE bestcolor
[BOX_C0_ELEMS
* BOX_C1_ELEMS
* BOX_C2_ELEMS
];
855 /* Convert cell coordinates to update box ID */
860 /* Compute true coordinates of update box's origin corner.
861 * Actually we compute the coordinates of the center of the corner
862 * histogram cell, which are the lower bounds of the volume we care about.
864 minc0
= (c0
<< BOX_C0_SHIFT
) + ((1 << C0_SHIFT
) >> 1);
865 minc1
= (c1
<< BOX_C1_SHIFT
) + ((1 << C1_SHIFT
) >> 1);
866 minc2
= (c2
<< BOX_C2_SHIFT
) + ((1 << C2_SHIFT
) >> 1);
868 /* Determine which colormap entries are close enough to be candidates
869 * for the nearest entry to some cell in the update box.
871 numcolors
= find_nearby_colors(cinfo
, minc0
, minc1
, minc2
, colorlist
);
873 /* Determine the actually nearest colors. */
874 find_best_colors(cinfo
, minc0
, minc1
, minc2
, numcolors
, colorlist
,
877 /* Save the best color numbers (plus 1) in the main cache array */
878 c0
<<= BOX_C0_LOG
; /* convert ID back to base cell indexes */
882 for (ic0
= 0; ic0
< BOX_C0_ELEMS
; ic0
++) {
883 for (ic1
= 0; ic1
< BOX_C1_ELEMS
; ic1
++) {
884 cachep
= &histogram
[c0
+ ic0
][c1
+ ic1
][c2
];
885 for (ic2
= 0; ic2
< BOX_C2_ELEMS
; ic2
++) {
886 *cachep
++ = (histcell
)((*cptr
++) + 1);
894 * Map some rows of pixels to the output colormapped representation.
898 pass2_no_dither(j_decompress_ptr cinfo
, _JSAMPARRAY input_buf
,
899 _JSAMPARRAY output_buf
, int num_rows
)
900 /* This version performs no dithering */
902 my_cquantize_ptr cquantize
= (my_cquantize_ptr
)cinfo
->cquantize
;
903 hist3d histogram
= cquantize
->histogram
;
904 register _JSAMPROW inptr
, outptr
;
905 register histptr cachep
;
906 register int c0
, c1
, c2
;
909 JDIMENSION width
= cinfo
->output_width
;
911 for (row
= 0; row
< num_rows
; row
++) {
912 inptr
= input_buf
[row
];
913 outptr
= output_buf
[row
];
914 for (col
= width
; col
> 0; col
--) {
915 /* get pixel value and index into the cache */
916 c0
= (*inptr
++) >> C0_SHIFT
;
917 c1
= (*inptr
++) >> C1_SHIFT
;
918 c2
= (*inptr
++) >> C2_SHIFT
;
919 cachep
= &histogram
[c0
][c1
][c2
];
920 /* If we have not seen this color before, find nearest colormap entry */
921 /* and update the cache */
923 fill_inverse_cmap(cinfo
, c0
, c1
, c2
);
924 /* Now emit the colormap index for this cell */
925 *outptr
++ = (_JSAMPLE
)(*cachep
- 1);
932 pass2_fs_dither(j_decompress_ptr cinfo
, _JSAMPARRAY input_buf
,
933 _JSAMPARRAY output_buf
, int num_rows
)
934 /* This version performs Floyd-Steinberg dithering */
936 my_cquantize_ptr cquantize
= (my_cquantize_ptr
)cinfo
->cquantize
;
937 hist3d histogram
= cquantize
->histogram
;
938 register LOCFSERROR cur0
, cur1
, cur2
; /* current error or pixel value */
939 LOCFSERROR belowerr0
, belowerr1
, belowerr2
; /* error for pixel below cur */
940 LOCFSERROR bpreverr0
, bpreverr1
, bpreverr2
; /* error for below/prev col */
941 register FSERRPTR errorptr
; /* => fserrors[] at column before current */
942 _JSAMPROW inptr
; /* => current input pixel */
943 _JSAMPROW outptr
; /* => current output pixel */
945 int dir
; /* +1 or -1 depending on direction */
946 int dir3
; /* 3*dir, for advancing inptr & errorptr */
949 JDIMENSION width
= cinfo
->output_width
;
950 _JSAMPLE
*range_limit
= (_JSAMPLE
*)cinfo
->sample_range_limit
;
951 int *error_limit
= cquantize
->error_limiter
;
952 _JSAMPROW colormap0
= ((_JSAMPARRAY
)cinfo
->colormap
)[0];
953 _JSAMPROW colormap1
= ((_JSAMPARRAY
)cinfo
->colormap
)[1];
954 _JSAMPROW colormap2
= ((_JSAMPARRAY
)cinfo
->colormap
)[2];
957 for (row
= 0; row
< num_rows
; row
++) {
958 inptr
= input_buf
[row
];
959 outptr
= output_buf
[row
];
960 if (cquantize
->on_odd_row
) {
961 /* work right to left in this row */
962 inptr
+= (width
- 1) * 3; /* so point to rightmost pixel */
966 errorptr
= cquantize
->fserrors
+ (width
+ 1) * 3; /* => entry after last column */
967 cquantize
->on_odd_row
= FALSE
; /* flip for next time */
969 /* work left to right in this row */
972 errorptr
= cquantize
->fserrors
; /* => entry before first real column */
973 cquantize
->on_odd_row
= TRUE
; /* flip for next time */
975 /* Preset error values: no error propagated to first pixel from left */
976 cur0
= cur1
= cur2
= 0;
977 /* and no error propagated to row below yet */
978 belowerr0
= belowerr1
= belowerr2
= 0;
979 bpreverr0
= bpreverr1
= bpreverr2
= 0;
981 for (col
= width
; col
> 0; col
--) {
982 /* curN holds the error propagated from the previous pixel on the
983 * current line. Add the error propagated from the previous line
984 * to form the complete error correction term for this pixel, and
985 * round the error term (which is expressed * 16) to an integer.
986 * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct
987 * for either sign of the error value.
988 * Note: errorptr points to *previous* column's array entry.
990 cur0
= RIGHT_SHIFT(cur0
+ errorptr
[dir3
+ 0] + 8, 4);
991 cur1
= RIGHT_SHIFT(cur1
+ errorptr
[dir3
+ 1] + 8, 4);
992 cur2
= RIGHT_SHIFT(cur2
+ errorptr
[dir3
+ 2] + 8, 4);
993 /* Limit the error using transfer function set by init_error_limit.
994 * See comments with init_error_limit for rationale.
996 cur0
= error_limit
[cur0
];
997 cur1
= error_limit
[cur1
];
998 cur2
= error_limit
[cur2
];
999 /* Form pixel value + error, and range-limit to 0.._MAXJSAMPLE.
1000 * The maximum error is +- _MAXJSAMPLE (or less with error limiting);
1001 * this sets the required size of the range_limit array.
1006 cur0
= range_limit
[cur0
];
1007 cur1
= range_limit
[cur1
];
1008 cur2
= range_limit
[cur2
];
1009 /* Index into the cache with adjusted pixel value */
1011 &histogram
[cur0
>> C0_SHIFT
][cur1
>> C1_SHIFT
][cur2
>> C2_SHIFT
];
1012 /* If we have not seen this color before, find nearest colormap */
1013 /* entry and update the cache */
1015 fill_inverse_cmap(cinfo
, cur0
>> C0_SHIFT
, cur1
>> C1_SHIFT
,
1017 /* Now emit the colormap index for this cell */
1019 register int pixcode
= *cachep
- 1;
1020 *outptr
= (_JSAMPLE
)pixcode
;
1021 /* Compute representation error for this pixel */
1022 cur0
-= colormap0
[pixcode
];
1023 cur1
-= colormap1
[pixcode
];
1024 cur2
-= colormap2
[pixcode
];
1026 /* Compute error fractions to be propagated to adjacent pixels.
1027 * Add these into the running sums, and simultaneously shift the
1028 * next-line error sums left by 1 column.
1031 register LOCFSERROR bnexterr
;
1033 bnexterr
= cur0
; /* Process component 0 */
1034 errorptr
[0] = (FSERROR
)(bpreverr0
+ cur0
* 3);
1035 bpreverr0
= belowerr0
+ cur0
* 5;
1036 belowerr0
= bnexterr
;
1038 bnexterr
= cur1
; /* Process component 1 */
1039 errorptr
[1] = (FSERROR
)(bpreverr1
+ cur1
* 3);
1040 bpreverr1
= belowerr1
+ cur1
* 5;
1041 belowerr1
= bnexterr
;
1043 bnexterr
= cur2
; /* Process component 2 */
1044 errorptr
[2] = (FSERROR
)(bpreverr2
+ cur2
* 3);
1045 bpreverr2
= belowerr2
+ cur2
* 5;
1046 belowerr2
= bnexterr
;
1049 /* At this point curN contains the 7/16 error value to be propagated
1050 * to the next pixel on the current line, and all the errors for the
1051 * next line have been shifted over. We are therefore ready to move on.
1053 inptr
+= dir3
; /* Advance pixel pointers to next column */
1055 errorptr
+= dir3
; /* advance errorptr to current column */
1057 /* Post-loop cleanup: we must unload the final error values into the
1058 * final fserrors[] entry. Note we need not unload belowerrN because
1059 * it is for the dummy column before or after the actual array.
1061 errorptr
[0] = (FSERROR
)bpreverr0
; /* unload prev errs into array */
1062 errorptr
[1] = (FSERROR
)bpreverr1
;
1063 errorptr
[2] = (FSERROR
)bpreverr2
;
1069 * Initialize the error-limiting transfer function (lookup table).
1070 * The raw F-S error computation can potentially compute error values of up to
1071 * +- _MAXJSAMPLE. But we want the maximum correction applied to a pixel to be
1072 * much less, otherwise obviously wrong pixels will be created. (Typical
1073 * effects include weird fringes at color-area boundaries, isolated bright
1074 * pixels in a dark area, etc.) The standard advice for avoiding this problem
1075 * is to ensure that the "corners" of the color cube are allocated as output
1076 * colors; then repeated errors in the same direction cannot cause cascading
1077 * error buildup. However, that only prevents the error from getting
1078 * completely out of hand; Aaron Giles reports that error limiting improves
1079 * the results even with corner colors allocated.
1080 * A simple clamping of the error values to about +- _MAXJSAMPLE/8 works pretty
1081 * well, but the smoother transfer function used below is even better. Thanks
1082 * to Aaron Giles for this idea.
1086 init_error_limit(j_decompress_ptr cinfo
)
1087 /* Allocate and fill in the error_limiter table */
1089 my_cquantize_ptr cquantize
= (my_cquantize_ptr
)cinfo
->cquantize
;
1093 table
= (int *)(*cinfo
->mem
->alloc_small
)
1094 ((j_common_ptr
)cinfo
, JPOOL_IMAGE
, (_MAXJSAMPLE
* 2 + 1) * sizeof(int));
1095 table
+= _MAXJSAMPLE
; /* so can index -_MAXJSAMPLE .. +_MAXJSAMPLE */
1096 cquantize
->error_limiter
= table
;
1098 #define STEPSIZE ((_MAXJSAMPLE + 1) / 16)
1099 /* Map errors 1:1 up to +- _MAXJSAMPLE/16 */
1101 for (in
= 0; in
< STEPSIZE
; in
++, out
++) {
1102 table
[in
] = out
; table
[-in
] = -out
;
1104 /* Map errors 1:2 up to +- 3*_MAXJSAMPLE/16 */
1105 for (; in
< STEPSIZE
* 3; in
++, out
+= (in
& 1) ? 0 : 1) {
1106 table
[in
] = out
; table
[-in
] = -out
;
1108 /* Clamp the rest to final out value (which is (_MAXJSAMPLE+1)/8) */
1109 for (; in
<= _MAXJSAMPLE
; in
++) {
1110 table
[in
] = out
; table
[-in
] = -out
;
1117 * Finish up at the end of each pass.
1121 finish_pass1(j_decompress_ptr cinfo
)
1123 my_cquantize_ptr cquantize
= (my_cquantize_ptr
)cinfo
->cquantize
;
1125 /* Select the representative colors and fill in cinfo->colormap */
1126 cinfo
->colormap
= (JSAMPARRAY
)cquantize
->sv_colormap
;
1127 select_colors(cinfo
, cquantize
->desired
);
1128 /* Force next pass to zero the color index table */
1129 cquantize
->needs_zeroed
= TRUE
;
1134 finish_pass2(j_decompress_ptr cinfo
)
1141 * Initialize for each processing pass.
1145 start_pass_2_quant(j_decompress_ptr cinfo
, boolean is_pre_scan
)
1147 my_cquantize_ptr cquantize
= (my_cquantize_ptr
)cinfo
->cquantize
;
1148 hist3d histogram
= cquantize
->histogram
;
1151 /* Only F-S dithering or no dithering is supported. */
1152 /* If user asks for ordered dither, give them F-S. */
1153 if (cinfo
->dither_mode
!= JDITHER_NONE
)
1154 cinfo
->dither_mode
= JDITHER_FS
;
1157 /* Set up method pointers */
1158 cquantize
->pub
._color_quantize
= prescan_quantize
;
1159 cquantize
->pub
.finish_pass
= finish_pass1
;
1160 cquantize
->needs_zeroed
= TRUE
; /* Always zero histogram */
1162 /* Set up method pointers */
1163 if (cinfo
->dither_mode
== JDITHER_FS
)
1164 cquantize
->pub
._color_quantize
= pass2_fs_dither
;
1166 cquantize
->pub
._color_quantize
= pass2_no_dither
;
1167 cquantize
->pub
.finish_pass
= finish_pass2
;
1169 /* Make sure color count is acceptable */
1170 i
= cinfo
->actual_number_of_colors
;
1172 ERREXIT1(cinfo
, JERR_QUANT_FEW_COLORS
, 1);
1173 if (i
> MAXNUMCOLORS
)
1174 ERREXIT1(cinfo
, JERR_QUANT_MANY_COLORS
, MAXNUMCOLORS
);
1176 if (cinfo
->dither_mode
== JDITHER_FS
) {
1178 (size_t)((cinfo
->output_width
+ 2) * (3 * sizeof(FSERROR
)));
1179 /* Allocate Floyd-Steinberg workspace if we didn't already. */
1180 if (cquantize
->fserrors
== NULL
)
1181 cquantize
->fserrors
= (FSERRPTR
)(*cinfo
->mem
->alloc_large
)
1182 ((j_common_ptr
)cinfo
, JPOOL_IMAGE
, arraysize
);
1183 /* Initialize the propagated errors to zero. */
1184 jzero_far((void *)cquantize
->fserrors
, arraysize
);
1185 /* Make the error-limit table if we didn't already. */
1186 if (cquantize
->error_limiter
== NULL
)
1187 init_error_limit(cinfo
);
1188 cquantize
->on_odd_row
= FALSE
;
1192 /* Zero the histogram or inverse color map, if necessary */
1193 if (cquantize
->needs_zeroed
) {
1194 for (i
= 0; i
< HIST_C0_ELEMS
; i
++) {
1195 jzero_far((void *)histogram
[i
],
1196 HIST_C1_ELEMS
* HIST_C2_ELEMS
* sizeof(histcell
));
1198 cquantize
->needs_zeroed
= FALSE
;
1204 * Switch to a new external colormap between output passes.
1208 new_color_map_2_quant(j_decompress_ptr cinfo
)
1210 my_cquantize_ptr cquantize
= (my_cquantize_ptr
)cinfo
->cquantize
;
1212 /* Reset the inverse color map */
1213 cquantize
->needs_zeroed
= TRUE
;
1218 * Module initialization routine for 2-pass color quantization.
1222 _jinit_2pass_quantizer(j_decompress_ptr cinfo
)
1224 my_cquantize_ptr cquantize
;
1227 if (cinfo
->data_precision
!= BITS_IN_JSAMPLE
)
1228 ERREXIT1(cinfo
, JERR_BAD_PRECISION
, cinfo
->data_precision
);
1230 cquantize
= (my_cquantize_ptr
)
1231 (*cinfo
->mem
->alloc_small
) ((j_common_ptr
)cinfo
, JPOOL_IMAGE
,
1232 sizeof(my_cquantizer
));
1233 cinfo
->cquantize
= (struct jpeg_color_quantizer
*)cquantize
;
1234 cquantize
->pub
.start_pass
= start_pass_2_quant
;
1235 cquantize
->pub
.new_color_map
= new_color_map_2_quant
;
1236 cquantize
->fserrors
= NULL
; /* flag optional arrays not allocated */
1237 cquantize
->error_limiter
= NULL
;
1239 /* Make sure jdmaster didn't give me a case I can't handle */
1240 if (cinfo
->out_color_components
!= 3 ||
1241 cinfo
->out_color_space
== JCS_RGB565
|| cinfo
->master
->lossless
)
1242 ERREXIT(cinfo
, JERR_NOTIMPL
);
1244 /* Allocate the histogram/inverse colormap storage */
1245 cquantize
->histogram
= (hist3d
)(*cinfo
->mem
->alloc_small
)
1246 ((j_common_ptr
)cinfo
, JPOOL_IMAGE
, HIST_C0_ELEMS
* sizeof(hist2d
));
1247 for (i
= 0; i
< HIST_C0_ELEMS
; i
++) {
1248 cquantize
->histogram
[i
] = (hist2d
)(*cinfo
->mem
->alloc_large
)
1249 ((j_common_ptr
)cinfo
, JPOOL_IMAGE
,
1250 HIST_C1_ELEMS
* HIST_C2_ELEMS
* sizeof(histcell
));
1252 cquantize
->needs_zeroed
= TRUE
; /* histogram is garbage now */
1254 /* Allocate storage for the completed colormap, if required.
1255 * We do this now since it may affect the memory manager's space
1258 if (cinfo
->enable_2pass_quant
) {
1259 /* Make sure color count is acceptable */
1260 int desired
= cinfo
->desired_number_of_colors
;
1261 /* Lower bound on # of colors ... somewhat arbitrary as long as > 0 */
1263 ERREXIT1(cinfo
, JERR_QUANT_FEW_COLORS
, 8);
1264 /* Make sure colormap indexes can be represented by _JSAMPLEs */
1265 if (desired
> MAXNUMCOLORS
)
1266 ERREXIT1(cinfo
, JERR_QUANT_MANY_COLORS
, MAXNUMCOLORS
);
1267 cquantize
->sv_colormap
= (_JSAMPARRAY
)(*cinfo
->mem
->alloc_sarray
)
1268 ((j_common_ptr
)cinfo
, JPOOL_IMAGE
, (JDIMENSION
)desired
, (JDIMENSION
)3);
1269 cquantize
->desired
= desired
;
1271 cquantize
->sv_colormap
= NULL
;
1273 /* Only F-S dithering or no dithering is supported. */
1274 /* If user asks for ordered dither, give them F-S. */
1275 if (cinfo
->dither_mode
!= JDITHER_NONE
)
1276 cinfo
->dither_mode
= JDITHER_FS
;
1278 /* Allocate Floyd-Steinberg workspace if necessary.
1279 * This isn't really needed until pass 2, but again it may affect the memory
1280 * manager's space calculations. Although we will cope with a later change
1281 * in dither_mode, we do not promise to honor max_memory_to_use if
1282 * dither_mode changes.
1284 if (cinfo
->dither_mode
== JDITHER_FS
) {
1285 cquantize
->fserrors
= (FSERRPTR
)(*cinfo
->mem
->alloc_large
)
1286 ((j_common_ptr
)cinfo
, JPOOL_IMAGE
,
1287 (size_t)((cinfo
->output_width
+ 2) * (3 * sizeof(FSERROR
))));
1288 /* Might as well create the error-limiting table too. */
1289 init_error_limit(cinfo
);
1293 #endif /* defined(QUANT_2PASS_SUPPORTED) && BITS_IN_JSAMPLE != 16 */