ReactOS 0.4.15-dev-8349-g6f277e9
jquant2.c
Go to the documentation of this file.
1/*
2 * jquant2.c
3 *
4 * Copyright (C) 1991-1996, Thomas G. Lane.
5 * Modified 2011 by Guido Vollbeding.
6 * This file is part of the Independent JPEG Group's software.
7 * For conditions of distribution and use, see the accompanying README file.
8 *
9 * This file contains 2-pass color quantization (color mapping) routines.
10 * These routines provide selection of a custom color map for an image,
11 * followed by mapping of the image to that color map, with optional
12 * Floyd-Steinberg dithering.
13 * It is also possible to use just the second pass to map to an arbitrary
14 * externally-given color map.
15 *
16 * Note: ordered dithering is not supported, since there isn't any fast
17 * way to compute intercolor distances; it's unclear that ordered dither's
18 * fundamental assumptions even hold with an irregularly spaced color map.
19 */
20
21#define JPEG_INTERNALS
22#include "jinclude.h"
23#include "jpeglib.h"
24
25#ifdef QUANT_2PASS_SUPPORTED
26
27
28/*
29 * This module implements the well-known Heckbert paradigm for color
30 * quantization. Most of the ideas used here can be traced back to
31 * Heckbert's seminal paper
32 * Heckbert, Paul. "Color Image Quantization for Frame Buffer Display",
33 * Proc. SIGGRAPH '82, Computer Graphics v.16 #3 (July 1982), pp 297-304.
34 *
35 * In the first pass over the image, we accumulate a histogram showing the
36 * usage count of each possible color. To keep the histogram to a reasonable
37 * size, we reduce the precision of the input; typical practice is to retain
38 * 5 or 6 bits per color, so that 8 or 4 different input values are counted
39 * in the same histogram cell.
40 *
41 * Next, the color-selection step begins with a box representing the whole
42 * color space, and repeatedly splits the "largest" remaining box until we
43 * have as many boxes as desired colors. Then the mean color in each
44 * remaining box becomes one of the possible output colors.
45 *
46 * The second pass over the image maps each input pixel to the closest output
47 * color (optionally after applying a Floyd-Steinberg dithering correction).
48 * This mapping is logically trivial, but making it go fast enough requires
49 * considerable care.
50 *
51 * Heckbert-style quantizers vary a good deal in their policies for choosing
52 * the "largest" box and deciding where to cut it. The particular policies
53 * used here have proved out well in experimental comparisons, but better ones
54 * may yet be found.
55 *
56 * In earlier versions of the IJG code, this module quantized in YCbCr color
57 * space, processing the raw upsampled data without a color conversion step.
58 * This allowed the color conversion math to be done only once per colormap
59 * entry, not once per pixel. However, that optimization precluded other
60 * useful optimizations (such as merging color conversion with upsampling)
61 * and it also interfered with desired capabilities such as quantizing to an
62 * externally-supplied colormap. We have therefore abandoned that approach.
63 * The present code works in the post-conversion color space, typically RGB.
64 *
65 * To improve the visual quality of the results, we actually work in scaled
66 * RGB space, giving G distances more weight than R, and R in turn more than
67 * B. To do everything in integer math, we must use integer scale factors.
68 * The 2/3/1 scale factors used here correspond loosely to the relative
69 * weights of the colors in the NTSC grayscale equation.
70 * If you want to use this code to quantize a non-RGB color space, you'll
71 * probably need to change these scale factors.
72 */
73
74#define R_SCALE 2 /* scale R distances by this much */
75#define G_SCALE 3 /* scale G distances by this much */
76#define B_SCALE 1 /* and B by this much */
77
78/* Relabel R/G/B as components 0/1/2, respecting the RGB ordering defined
79 * in jmorecfg.h. As the code stands, it will do the right thing for R,G,B
80 * and B,G,R orders. If you define some other weird order in jmorecfg.h,
81 * you'll get compile errors until you extend this logic. In that case
82 * you'll probably want to tweak the histogram sizes too.
83 */
84
85#if RGB_RED == 0
86#define C0_SCALE R_SCALE
87#endif
88#if RGB_BLUE == 0
89#define C0_SCALE B_SCALE
90#endif
91#if RGB_GREEN == 1
92#define C1_SCALE G_SCALE
93#endif
94#if RGB_RED == 2
95#define C2_SCALE R_SCALE
96#endif
97#if RGB_BLUE == 2
98#define C2_SCALE B_SCALE
99#endif
100
101
102/*
103 * First we have the histogram data structure and routines for creating it.
104 *
105 * The number of bits of precision can be adjusted by changing these symbols.
106 * We recommend keeping 6 bits for G and 5 each for R and B.
107 * If you have plenty of memory and cycles, 6 bits all around gives marginally
108 * better results; if you are short of memory, 5 bits all around will save
109 * some space but degrade the results.
110 * To maintain a fully accurate histogram, we'd need to allocate a "long"
111 * (preferably unsigned long) for each cell. In practice this is overkill;
112 * we can get by with 16 bits per cell. Few of the cell counts will overflow,
113 * and clamping those that do overflow to the maximum value will give close-
114 * enough results. This reduces the recommended histogram size from 256Kb
115 * to 128Kb, which is a useful savings on PC-class machines.
116 * (In the second pass the histogram space is re-used for pixel mapping data;
117 * in that capacity, each cell must be able to store zero to the number of
118 * desired colors. 16 bits/cell is plenty for that too.)
119 * Since the JPEG code is intended to run in small memory model on 80x86
120 * machines, we can't just allocate the histogram in one chunk. Instead
121 * of a true 3-D array, we use a row of pointers to 2-D arrays. Each
122 * pointer corresponds to a C0 value (typically 2^5 = 32 pointers) and
123 * each 2-D array has 2^6*2^5 = 2048 or 2^6*2^6 = 4096 entries. Note that
124 * on 80x86 machines, the pointer row is in near memory but the actual
125 * arrays are in far memory (same arrangement as we use for image arrays).
126 */
127
128#define MAXNUMCOLORS (MAXJSAMPLE+1) /* maximum size of colormap */
129
130/* These will do the right thing for either R,G,B or B,G,R color order,
131 * but you may not like the results for other color orders.
132 */
133#define HIST_C0_BITS 5 /* bits of precision in R/B histogram */
134#define HIST_C1_BITS 6 /* bits of precision in G histogram */
135#define HIST_C2_BITS 5 /* bits of precision in B/R histogram */
136
137/* Number of elements along histogram axes. */
138#define HIST_C0_ELEMS (1<<HIST_C0_BITS)
139#define HIST_C1_ELEMS (1<<HIST_C1_BITS)
140#define HIST_C2_ELEMS (1<<HIST_C2_BITS)
141
142/* These are the amounts to shift an input value to get a histogram index. */
143#define C0_SHIFT (BITS_IN_JSAMPLE-HIST_C0_BITS)
144#define C1_SHIFT (BITS_IN_JSAMPLE-HIST_C1_BITS)
145#define C2_SHIFT (BITS_IN_JSAMPLE-HIST_C2_BITS)
146
147
148typedef UINT16 histcell; /* histogram cell; prefer an unsigned type */
149
150typedef histcell FAR * histptr; /* for pointers to histogram cells */
151
152typedef histcell hist1d[HIST_C2_ELEMS]; /* typedefs for the array */
153typedef hist1d FAR * hist2d; /* type for the 2nd-level pointers */
154typedef hist2d * hist3d; /* type for top-level pointer */
155
156
157/* Declarations for Floyd-Steinberg dithering.
158 *
159 * Errors are accumulated into the array fserrors[], at a resolution of
160 * 1/16th of a pixel count. The error at a given pixel is propagated
161 * to its not-yet-processed neighbors using the standard F-S fractions,
162 * ... (here) 7/16
163 * 3/16 5/16 1/16
164 * We work left-to-right on even rows, right-to-left on odd rows.
165 *
166 * We can get away with a single array (holding one row's worth of errors)
167 * by using it to store the current row's errors at pixel columns not yet
168 * processed, but the next row's errors at columns already processed. We
169 * need only a few extra variables to hold the errors immediately around the
170 * current column. (If we are lucky, those variables are in registers, but
171 * even if not, they're probably cheaper to access than array elements are.)
172 *
173 * The fserrors[] array has (#columns + 2) entries; the extra entry at
174 * each end saves us from special-casing the first and last pixels.
175 * Each entry is three values long, one value for each color component.
176 *
177 * Note: on a wide image, we might not have enough room in a PC's near data
178 * segment to hold the error array; so it is allocated with alloc_large.
179 */
180
181#if BITS_IN_JSAMPLE == 8
182typedef INT16 FSERROR; /* 16 bits should be enough */
183typedef int LOCFSERROR; /* use 'int' for calculation temps */
184#else
185typedef INT32 FSERROR; /* may need more than 16 bits */
186typedef INT32 LOCFSERROR; /* be sure calculation temps are big enough */
187#endif
188
189typedef FSERROR FAR *FSERRPTR; /* pointer to error array (in FAR storage!) */
190
191
192/* Private subobject */
193
194typedef struct {
195 struct jpeg_color_quantizer pub; /* public fields */
196
197 /* Space for the eventually created colormap is stashed here */
198 JSAMPARRAY sv_colormap; /* colormap allocated at init time */
199 int desired; /* desired # of colors = size of colormap */
200
201 /* Variables for accumulating image statistics */
202 hist3d histogram; /* pointer to the histogram */
203
204 boolean needs_zeroed; /* TRUE if next pass must zero histogram */
205
206 /* Variables for Floyd-Steinberg dithering */
207 FSERRPTR fserrors; /* accumulated errors */
208 boolean on_odd_row; /* flag to remember which row we are on */
209 int * error_limiter; /* table for clamping the applied error */
210} my_cquantizer;
211
212typedef my_cquantizer * my_cquantize_ptr;
213
214
215/*
216 * Prescan some rows of pixels.
217 * In this module the prescan simply updates the histogram, which has been
218 * initialized to zeroes by start_pass.
219 * An output_buf parameter is required by the method signature, but no data
220 * is actually output (in fact the buffer controller is probably passing a
221 * NULL pointer).
222 */
223
224METHODDEF(void)
225prescan_quantize (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
227{
228 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
229 register JSAMPROW ptr;
230 register histptr histp;
231 register hist3d histogram = cquantize->histogram;
232 int row;
233 JDIMENSION col;
235
236 for (row = 0; row < num_rows; row++) {
237 ptr = input_buf[row];
238 for (col = width; col > 0; col--) {
239 /* get pixel value and index into the histogram */
240 histp = & histogram[GETJSAMPLE(ptr[0]) >> C0_SHIFT]
241 [GETJSAMPLE(ptr[1]) >> C1_SHIFT]
242 [GETJSAMPLE(ptr[2]) >> C2_SHIFT];
243 /* increment, check for overflow and undo increment if so. */
244 if (++(*histp) <= 0)
245 (*histp)--;
246 ptr += 3;
247 }
248 }
249}
250
251
252/*
253 * Next we have the really interesting routines: selection of a colormap
254 * given the completed histogram.
255 * These routines work with a list of "boxes", each representing a rectangular
256 * subset of the input color space (to histogram precision).
257 */
258
259typedef struct {
260 /* The bounds of the box (inclusive); expressed as histogram indexes */
261 int c0min, c0max;
262 int c1min, c1max;
263 int c2min, c2max;
264 /* The volume (actually 2-norm) of the box */
266 /* The number of nonzero histogram cells within this box */
267 long colorcount;
268} box;
269
270typedef box * boxptr;
271
272
273LOCAL(boxptr)
274find_biggest_color_pop (boxptr boxlist, int numboxes)
275/* Find the splittable box with the largest color population */
276/* Returns NULL if no splittable boxes remain */
277{
278 register boxptr boxp;
279 register int i;
280 register long maxc = 0;
281 boxptr which = NULL;
282
283 for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) {
284 if (boxp->colorcount > maxc && boxp->volume > 0) {
285 which = boxp;
286 maxc = boxp->colorcount;
287 }
288 }
289 return which;
290}
291
292
293LOCAL(boxptr)
294find_biggest_volume (boxptr boxlist, int numboxes)
295/* Find the splittable box with the largest (scaled) volume */
296/* Returns NULL if no splittable boxes remain */
297{
298 register boxptr boxp;
299 register int i;
300 register INT32 maxv = 0;
301 boxptr which = NULL;
302
303 for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) {
304 if (boxp->volume > maxv) {
305 which = boxp;
306 maxv = boxp->volume;
307 }
308 }
309 return which;
310}
311
312
313LOCAL(void)
314update_box (j_decompress_ptr cinfo, boxptr boxp)
315/* Shrink the min/max bounds of a box to enclose only nonzero elements, */
316/* and recompute its volume and population */
317{
318 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
319 hist3d histogram = cquantize->histogram;
320 histptr histp;
321 int c0,c1,c2;
322 int c0min,c0max,c1min,c1max,c2min,c2max;
323 INT32 dist0,dist1,dist2;
324 long ccount;
325
326 c0min = boxp->c0min; c0max = boxp->c0max;
327 c1min = boxp->c1min; c1max = boxp->c1max;
328 c2min = boxp->c2min; c2max = boxp->c2max;
329
330 if (c0max > c0min)
331 for (c0 = c0min; c0 <= c0max; c0++)
332 for (c1 = c1min; c1 <= c1max; c1++) {
333 histp = & histogram[c0][c1][c2min];
334 for (c2 = c2min; c2 <= c2max; c2++)
335 if (*histp++ != 0) {
336 boxp->c0min = c0min = c0;
337 goto have_c0min;
338 }
339 }
340 have_c0min:
341 if (c0max > c0min)
342 for (c0 = c0max; c0 >= c0min; c0--)
343 for (c1 = c1min; c1 <= c1max; c1++) {
344 histp = & histogram[c0][c1][c2min];
345 for (c2 = c2min; c2 <= c2max; c2++)
346 if (*histp++ != 0) {
347 boxp->c0max = c0max = c0;
348 goto have_c0max;
349 }
350 }
351 have_c0max:
352 if (c1max > c1min)
353 for (c1 = c1min; c1 <= c1max; c1++)
354 for (c0 = c0min; c0 <= c0max; c0++) {
355 histp = & histogram[c0][c1][c2min];
356 for (c2 = c2min; c2 <= c2max; c2++)
357 if (*histp++ != 0) {
358 boxp->c1min = c1min = c1;
359 goto have_c1min;
360 }
361 }
362 have_c1min:
363 if (c1max > c1min)
364 for (c1 = c1max; c1 >= c1min; c1--)
365 for (c0 = c0min; c0 <= c0max; c0++) {
366 histp = & histogram[c0][c1][c2min];
367 for (c2 = c2min; c2 <= c2max; c2++)
368 if (*histp++ != 0) {
369 boxp->c1max = c1max = c1;
370 goto have_c1max;
371 }
372 }
373 have_c1max:
374 if (c2max > c2min)
375 for (c2 = c2min; c2 <= c2max; c2++)
376 for (c0 = c0min; c0 <= c0max; c0++) {
377 histp = & histogram[c0][c1min][c2];
378 for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)
379 if (*histp != 0) {
380 boxp->c2min = c2min = c2;
381 goto have_c2min;
382 }
383 }
384 have_c2min:
385 if (c2max > c2min)
386 for (c2 = c2max; c2 >= c2min; c2--)
387 for (c0 = c0min; c0 <= c0max; c0++) {
388 histp = & histogram[c0][c1min][c2];
389 for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)
390 if (*histp != 0) {
391 boxp->c2max = c2max = c2;
392 goto have_c2max;
393 }
394 }
395 have_c2max:
396
397 /* Update box volume.
398 * We use 2-norm rather than real volume here; this biases the method
399 * against making long narrow boxes, and it has the side benefit that
400 * a box is splittable iff norm > 0.
401 * Since the differences are expressed in histogram-cell units,
402 * we have to shift back to JSAMPLE units to get consistent distances;
403 * after which, we scale according to the selected distance scale factors.
404 */
405 dist0 = ((c0max - c0min) << C0_SHIFT) * C0_SCALE;
406 dist1 = ((c1max - c1min) << C1_SHIFT) * C1_SCALE;
407 dist2 = ((c2max - c2min) << C2_SHIFT) * C2_SCALE;
408 boxp->volume = dist0*dist0 + dist1*dist1 + dist2*dist2;
409
410 /* Now scan remaining volume of box and compute population */
411 ccount = 0;
412 for (c0 = c0min; c0 <= c0max; c0++)
413 for (c1 = c1min; c1 <= c1max; c1++) {
414 histp = & histogram[c0][c1][c2min];
415 for (c2 = c2min; c2 <= c2max; c2++, histp++)
416 if (*histp != 0) {
417 ccount++;
418 }
419 }
420 boxp->colorcount = ccount;
421}
422
423
424LOCAL(int)
425median_cut (j_decompress_ptr cinfo, boxptr boxlist, int numboxes,
426 int desired_colors)
427/* Repeatedly select and split the largest box until we have enough boxes */
428{
429 int n,lb;
430 int c0,c1,c2,cmax;
431 register boxptr b1,b2;
432
433 while (numboxes < desired_colors) {
434 /* Select box to split.
435 * Current algorithm: by population for first half, then by volume.
436 */
437 if (numboxes*2 <= desired_colors) {
438 b1 = find_biggest_color_pop(boxlist, numboxes);
439 } else {
440 b1 = find_biggest_volume(boxlist, numboxes);
441 }
442 if (b1 == NULL) /* no splittable boxes left! */
443 break;
444 b2 = &boxlist[numboxes]; /* where new box will go */
445 /* Copy the color bounds to the new box. */
446 b2->c0max = b1->c0max; b2->c1max = b1->c1max; b2->c2max = b1->c2max;
447 b2->c0min = b1->c0min; b2->c1min = b1->c1min; b2->c2min = b1->c2min;
448 /* Choose which axis to split the box on.
449 * Current algorithm: longest scaled axis.
450 * See notes in update_box about scaling distances.
451 */
452 c0 = ((b1->c0max - b1->c0min) << C0_SHIFT) * C0_SCALE;
453 c1 = ((b1->c1max - b1->c1min) << C1_SHIFT) * C1_SCALE;
454 c2 = ((b1->c2max - b1->c2min) << C2_SHIFT) * C2_SCALE;
455 /* We want to break any ties in favor of green, then red, blue last.
456 * This code does the right thing for R,G,B or B,G,R color orders only.
457 */
458#if RGB_RED == 0
459 cmax = c1; n = 1;
460 if (c0 > cmax) { cmax = c0; n = 0; }
461 if (c2 > cmax) { n = 2; }
462#else
463 cmax = c1; n = 1;
464 if (c2 > cmax) { cmax = c2; n = 2; }
465 if (c0 > cmax) { n = 0; }
466#endif
467 /* Choose split point along selected axis, and update box bounds.
468 * Current algorithm: split at halfway point.
469 * (Since the box has been shrunk to minimum volume,
470 * any split will produce two nonempty subboxes.)
471 * Note that lb value is max for lower box, so must be < old max.
472 */
473 switch (n) {
474 case 0:
475 lb = (b1->c0max + b1->c0min) / 2;
476 b1->c0max = lb;
477 b2->c0min = lb+1;
478 break;
479 case 1:
480 lb = (b1->c1max + b1->c1min) / 2;
481 b1->c1max = lb;
482 b2->c1min = lb+1;
483 break;
484 case 2:
485 lb = (b1->c2max + b1->c2min) / 2;
486 b1->c2max = lb;
487 b2->c2min = lb+1;
488 break;
489 }
490 /* Update stats for boxes */
491 update_box(cinfo, b1);
492 update_box(cinfo, b2);
493 numboxes++;
494 }
495 return numboxes;
496}
497
498
499LOCAL(void)
500compute_color (j_decompress_ptr cinfo, boxptr boxp, int icolor)
501/* Compute representative color for a box, put it in colormap[icolor] */
502{
503 /* Current algorithm: mean weighted by pixels (not colors) */
504 /* Note it is important to get the rounding correct! */
505 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
506 hist3d histogram = cquantize->histogram;
507 histptr histp;
508 int c0,c1,c2;
509 int c0min,c0max,c1min,c1max,c2min,c2max;
510 long count;
511 long total = 0;
512 long c0total = 0;
513 long c1total = 0;
514 long c2total = 0;
515
516 c0min = boxp->c0min; c0max = boxp->c0max;
517 c1min = boxp->c1min; c1max = boxp->c1max;
518 c2min = boxp->c2min; c2max = boxp->c2max;
519
520 for (c0 = c0min; c0 <= c0max; c0++)
521 for (c1 = c1min; c1 <= c1max; c1++) {
522 histp = & histogram[c0][c1][c2min];
523 for (c2 = c2min; c2 <= c2max; c2++) {
524 if ((count = *histp++) != 0) {
525 total += count;
526 c0total += ((c0 << C0_SHIFT) + ((1<<C0_SHIFT)>>1)) * count;
527 c1total += ((c1 << C1_SHIFT) + ((1<<C1_SHIFT)>>1)) * count;
528 c2total += ((c2 << C2_SHIFT) + ((1<<C2_SHIFT)>>1)) * count;
529 }
530 }
531 }
532
533 cinfo->colormap[0][icolor] = (JSAMPLE) ((c0total + (total>>1)) / total);
534 cinfo->colormap[1][icolor] = (JSAMPLE) ((c1total + (total>>1)) / total);
535 cinfo->colormap[2][icolor] = (JSAMPLE) ((c2total + (total>>1)) / total);
536}
537
538
539LOCAL(void)
540select_colors (j_decompress_ptr cinfo, int desired_colors)
541/* Master routine for color selection */
542{
543 boxptr boxlist;
544 int numboxes;
545 int i;
546
547 /* Allocate workspace for box list */
548 boxlist = (boxptr) (*cinfo->mem->alloc_small)
549 ((j_common_ptr) cinfo, JPOOL_IMAGE, desired_colors * SIZEOF(box));
550 /* Initialize one box containing whole space */
551 numboxes = 1;
552 boxlist[0].c0min = 0;
553 boxlist[0].c0max = MAXJSAMPLE >> C0_SHIFT;
554 boxlist[0].c1min = 0;
555 boxlist[0].c1max = MAXJSAMPLE >> C1_SHIFT;
556 boxlist[0].c2min = 0;
557 boxlist[0].c2max = MAXJSAMPLE >> C2_SHIFT;
558 /* Shrink it to actually-used volume and set its statistics */
559 update_box(cinfo, & boxlist[0]);
560 /* Perform median-cut to produce final box list */
561 numboxes = median_cut(cinfo, boxlist, numboxes, desired_colors);
562 /* Compute the representative color for each box, fill colormap */
563 for (i = 0; i < numboxes; i++)
564 compute_color(cinfo, & boxlist[i], i);
565 cinfo->actual_number_of_colors = numboxes;
566 TRACEMS1(cinfo, 1, JTRC_QUANT_SELECTED, numboxes);
567}
568
569
570/*
571 * These routines are concerned with the time-critical task of mapping input
572 * colors to the nearest color in the selected colormap.
573 *
574 * We re-use the histogram space as an "inverse color map", essentially a
575 * cache for the results of nearest-color searches. All colors within a
576 * histogram cell will be mapped to the same colormap entry, namely the one
577 * closest to the cell's center. This may not be quite the closest entry to
578 * the actual input color, but it's almost as good. A zero in the cache
579 * indicates we haven't found the nearest color for that cell yet; the array
580 * is cleared to zeroes before starting the mapping pass. When we find the
581 * nearest color for a cell, its colormap index plus one is recorded in the
582 * cache for future use. The pass2 scanning routines call fill_inverse_cmap
583 * when they need to use an unfilled entry in the cache.
584 *
585 * Our method of efficiently finding nearest colors is based on the "locally
586 * sorted search" idea described by Heckbert and on the incremental distance
587 * calculation described by Spencer W. Thomas in chapter III.1 of Graphics
588 * Gems II (James Arvo, ed. Academic Press, 1991). Thomas points out that
589 * the distances from a given colormap entry to each cell of the histogram can
590 * be computed quickly using an incremental method: the differences between
591 * distances to adjacent cells themselves differ by a constant. This allows a
592 * fairly fast implementation of the "brute force" approach of computing the
593 * distance from every colormap entry to every histogram cell. Unfortunately,
594 * it needs a work array to hold the best-distance-so-far for each histogram
595 * cell (because the inner loop has to be over cells, not colormap entries).
596 * The work array elements have to be INT32s, so the work array would need
597 * 256Kb at our recommended precision. This is not feasible in DOS machines.
598 *
599 * To get around these problems, we apply Thomas' method to compute the
600 * nearest colors for only the cells within a small subbox of the histogram.
601 * The work array need be only as big as the subbox, so the memory usage
602 * problem is solved. Furthermore, we need not fill subboxes that are never
603 * referenced in pass2; many images use only part of the color gamut, so a
604 * fair amount of work is saved. An additional advantage of this
605 * approach is that we can apply Heckbert's locality criterion to quickly
606 * eliminate colormap entries that are far away from the subbox; typically
607 * three-fourths of the colormap entries are rejected by Heckbert's criterion,
608 * and we need not compute their distances to individual cells in the subbox.
609 * The speed of this approach is heavily influenced by the subbox size: too
610 * small means too much overhead, too big loses because Heckbert's criterion
611 * can't eliminate as many colormap entries. Empirically the best subbox
612 * size seems to be about 1/512th of the histogram (1/8th in each direction).
613 *
614 * Thomas' article also describes a refined method which is asymptotically
615 * faster than the brute-force method, but it is also far more complex and
616 * cannot efficiently be applied to small subboxes. It is therefore not
617 * useful for programs intended to be portable to DOS machines. On machines
618 * with plenty of memory, filling the whole histogram in one shot with Thomas'
619 * refined method might be faster than the present code --- but then again,
620 * it might not be any faster, and it's certainly more complicated.
621 */
622
623
624/* log2(histogram cells in update box) for each axis; this can be adjusted */
625#define BOX_C0_LOG (HIST_C0_BITS-3)
626#define BOX_C1_LOG (HIST_C1_BITS-3)
627#define BOX_C2_LOG (HIST_C2_BITS-3)
628
629#define BOX_C0_ELEMS (1<<BOX_C0_LOG) /* # of hist cells in update box */
630#define BOX_C1_ELEMS (1<<BOX_C1_LOG)
631#define BOX_C2_ELEMS (1<<BOX_C2_LOG)
632
633#define BOX_C0_SHIFT (C0_SHIFT + BOX_C0_LOG)
634#define BOX_C1_SHIFT (C1_SHIFT + BOX_C1_LOG)
635#define BOX_C2_SHIFT (C2_SHIFT + BOX_C2_LOG)
636
637
638/*
639 * The next three routines implement inverse colormap filling. They could
640 * all be folded into one big routine, but splitting them up this way saves
641 * some stack space (the mindist[] and bestdist[] arrays need not coexist)
642 * and may allow some compilers to produce better code by registerizing more
643 * inner-loop variables.
644 */
645
646LOCAL(int)
647find_nearby_colors (j_decompress_ptr cinfo, int minc0, int minc1, int minc2,
648 JSAMPLE colorlist[])
649/* Locate the colormap entries close enough to an update box to be candidates
650 * for the nearest entry to some cell(s) in the update box. The update box
651 * is specified by the center coordinates of its first cell. The number of
652 * candidate colormap entries is returned, and their colormap indexes are
653 * placed in colorlist[].
654 * This routine uses Heckbert's "locally sorted search" criterion to select
655 * the colors that need further consideration.
656 */
657{
658 int numcolors = cinfo->actual_number_of_colors;
659 int maxc0, maxc1, maxc2;
660 int centerc0, centerc1, centerc2;
661 int i, x, ncolors;
662 INT32 minmaxdist, min_dist, max_dist, tdist;
663 INT32 mindist[MAXNUMCOLORS]; /* min distance to colormap entry i */
664
665 /* Compute true coordinates of update box's upper corner and center.
666 * Actually we compute the coordinates of the center of the upper-corner
667 * histogram cell, which are the upper bounds of the volume we care about.
668 * Note that since ">>" rounds down, the "center" values may be closer to
669 * min than to max; hence comparisons to them must be "<=", not "<".
670 */
671 maxc0 = minc0 + ((1 << BOX_C0_SHIFT) - (1 << C0_SHIFT));
672 centerc0 = (minc0 + maxc0) >> 1;
673 maxc1 = minc1 + ((1 << BOX_C1_SHIFT) - (1 << C1_SHIFT));
674 centerc1 = (minc1 + maxc1) >> 1;
675 maxc2 = minc2 + ((1 << BOX_C2_SHIFT) - (1 << C2_SHIFT));
676 centerc2 = (minc2 + maxc2) >> 1;
677
678 /* For each color in colormap, find:
679 * 1. its minimum squared-distance to any point in the update box
680 * (zero if color is within update box);
681 * 2. its maximum squared-distance to any point in the update box.
682 * Both of these can be found by considering only the corners of the box.
683 * We save the minimum distance for each color in mindist[];
684 * only the smallest maximum distance is of interest.
685 */
686 minmaxdist = 0x7FFFFFFFL;
687
688 for (i = 0; i < numcolors; i++) {
689 /* We compute the squared-c0-distance term, then add in the other two. */
690 x = GETJSAMPLE(cinfo->colormap[0][i]);
691 if (x < minc0) {
692 tdist = (x - minc0) * C0_SCALE;
693 min_dist = tdist*tdist;
694 tdist = (x - maxc0) * C0_SCALE;
695 max_dist = tdist*tdist;
696 } else if (x > maxc0) {
697 tdist = (x - maxc0) * C0_SCALE;
698 min_dist = tdist*tdist;
699 tdist = (x - minc0) * C0_SCALE;
700 max_dist = tdist*tdist;
701 } else {
702 /* within cell range so no contribution to min_dist */
703 min_dist = 0;
704 if (x <= centerc0) {
705 tdist = (x - maxc0) * C0_SCALE;
706 max_dist = tdist*tdist;
707 } else {
708 tdist = (x - minc0) * C0_SCALE;
709 max_dist = tdist*tdist;
710 }
711 }
712
713 x = GETJSAMPLE(cinfo->colormap[1][i]);
714 if (x < minc1) {
715 tdist = (x - minc1) * C1_SCALE;
716 min_dist += tdist*tdist;
717 tdist = (x - maxc1) * C1_SCALE;
718 max_dist += tdist*tdist;
719 } else if (x > maxc1) {
720 tdist = (x - maxc1) * C1_SCALE;
721 min_dist += tdist*tdist;
722 tdist = (x - minc1) * C1_SCALE;
723 max_dist += tdist*tdist;
724 } else {
725 /* within cell range so no contribution to min_dist */
726 if (x <= centerc1) {
727 tdist = (x - maxc1) * C1_SCALE;
728 max_dist += tdist*tdist;
729 } else {
730 tdist = (x - minc1) * C1_SCALE;
731 max_dist += tdist*tdist;
732 }
733 }
734
735 x = GETJSAMPLE(cinfo->colormap[2][i]);
736 if (x < minc2) {
737 tdist = (x - minc2) * C2_SCALE;
738 min_dist += tdist*tdist;
739 tdist = (x - maxc2) * C2_SCALE;
740 max_dist += tdist*tdist;
741 } else if (x > maxc2) {
742 tdist = (x - maxc2) * C2_SCALE;
743 min_dist += tdist*tdist;
744 tdist = (x - minc2) * C2_SCALE;
745 max_dist += tdist*tdist;
746 } else {
747 /* within cell range so no contribution to min_dist */
748 if (x <= centerc2) {
749 tdist = (x - maxc2) * C2_SCALE;
750 max_dist += tdist*tdist;
751 } else {
752 tdist = (x - minc2) * C2_SCALE;
753 max_dist += tdist*tdist;
754 }
755 }
756
757 mindist[i] = min_dist; /* save away the results */
758 if (max_dist < minmaxdist)
759 minmaxdist = max_dist;
760 }
761
762 /* Now we know that no cell in the update box is more than minmaxdist
763 * away from some colormap entry. Therefore, only colors that are
764 * within minmaxdist of some part of the box need be considered.
765 */
766 ncolors = 0;
767 for (i = 0; i < numcolors; i++) {
768 if (mindist[i] <= minmaxdist)
769 colorlist[ncolors++] = (JSAMPLE) i;
770 }
771 return ncolors;
772}
773
774
775LOCAL(void)
776find_best_colors (j_decompress_ptr cinfo, int minc0, int minc1, int minc2,
777 int numcolors, JSAMPLE colorlist[], JSAMPLE bestcolor[])
778/* Find the closest colormap entry for each cell in the update box,
779 * given the list of candidate colors prepared by find_nearby_colors.
780 * Return the indexes of the closest entries in the bestcolor[] array.
781 * This routine uses Thomas' incremental distance calculation method to
782 * find the distance from a colormap entry to successive cells in the box.
783 */
784{
785 int ic0, ic1, ic2;
786 int i, icolor;
787 register INT32 * bptr; /* pointer into bestdist[] array */
788 JSAMPLE * cptr; /* pointer into bestcolor[] array */
789 INT32 dist0, dist1; /* initial distance values */
790 register INT32 dist2; /* current distance in inner loop */
791 INT32 xx0, xx1; /* distance increments */
792 register INT32 xx2;
793 INT32 inc0, inc1, inc2; /* initial values for increments */
794 /* This array holds the distance to the nearest-so-far color for each cell */
795 INT32 bestdist[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS];
796
797 /* Initialize best-distance for each cell of the update box */
798 bptr = bestdist;
799 for (i = BOX_C0_ELEMS*BOX_C1_ELEMS*BOX_C2_ELEMS-1; i >= 0; i--)
800 *bptr++ = 0x7FFFFFFFL;
801
802 /* For each color selected by find_nearby_colors,
803 * compute its distance to the center of each cell in the box.
804 * If that's less than best-so-far, update best distance and color number.
805 */
806
807 /* Nominal steps between cell centers ("x" in Thomas article) */
808#define STEP_C0 ((1 << C0_SHIFT) * C0_SCALE)
809#define STEP_C1 ((1 << C1_SHIFT) * C1_SCALE)
810#define STEP_C2 ((1 << C2_SHIFT) * C2_SCALE)
811
812 for (i = 0; i < numcolors; i++) {
813 icolor = GETJSAMPLE(colorlist[i]);
814 /* Compute (square of) distance from minc0/c1/c2 to this color */
815 inc0 = (minc0 - GETJSAMPLE(cinfo->colormap[0][icolor])) * C0_SCALE;
816 dist0 = inc0*inc0;
817 inc1 = (minc1 - GETJSAMPLE(cinfo->colormap[1][icolor])) * C1_SCALE;
818 dist0 += inc1*inc1;
819 inc2 = (minc2 - GETJSAMPLE(cinfo->colormap[2][icolor])) * C2_SCALE;
820 dist0 += inc2*inc2;
821 /* Form the initial difference increments */
822 inc0 = inc0 * (2 * STEP_C0) + STEP_C0 * STEP_C0;
823 inc1 = inc1 * (2 * STEP_C1) + STEP_C1 * STEP_C1;
824 inc2 = inc2 * (2 * STEP_C2) + STEP_C2 * STEP_C2;
825 /* Now loop over all cells in box, updating distance per Thomas method */
826 bptr = bestdist;
827 cptr = bestcolor;
828 xx0 = inc0;
829 for (ic0 = BOX_C0_ELEMS-1; ic0 >= 0; ic0--) {
830 dist1 = dist0;
831 xx1 = inc1;
832 for (ic1 = BOX_C1_ELEMS-1; ic1 >= 0; ic1--) {
833 dist2 = dist1;
834 xx2 = inc2;
835 for (ic2 = BOX_C2_ELEMS-1; ic2 >= 0; ic2--) {
836 if (dist2 < *bptr) {
837 *bptr = dist2;
838 *cptr = (JSAMPLE) icolor;
839 }
840 dist2 += xx2;
841 xx2 += 2 * STEP_C2 * STEP_C2;
842 bptr++;
843 cptr++;
844 }
845 dist1 += xx1;
846 xx1 += 2 * STEP_C1 * STEP_C1;
847 }
848 dist0 += xx0;
849 xx0 += 2 * STEP_C0 * STEP_C0;
850 }
851 }
852}
853
854
855LOCAL(void)
856fill_inverse_cmap (j_decompress_ptr cinfo, int c0, int c1, int c2)
857/* Fill the inverse-colormap entries in the update box that contains */
858/* histogram cell c0/c1/c2. (Only that one cell MUST be filled, but */
859/* we can fill as many others as we wish.) */
860{
861 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
862 hist3d histogram = cquantize->histogram;
863 int minc0, minc1, minc2; /* lower left corner of update box */
864 int ic0, ic1, ic2;
865 register JSAMPLE * cptr; /* pointer into bestcolor[] array */
866 register histptr cachep; /* pointer into main cache array */
867 /* This array lists the candidate colormap indexes. */
868 JSAMPLE colorlist[MAXNUMCOLORS];
869 int numcolors; /* number of candidate colors */
870 /* This array holds the actually closest colormap index for each cell. */
871 JSAMPLE bestcolor[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS];
872
873 /* Convert cell coordinates to update box ID */
874 c0 >>= BOX_C0_LOG;
875 c1 >>= BOX_C1_LOG;
876 c2 >>= BOX_C2_LOG;
877
878 /* Compute true coordinates of update box's origin corner.
879 * Actually we compute the coordinates of the center of the corner
880 * histogram cell, which are the lower bounds of the volume we care about.
881 */
882 minc0 = (c0 << BOX_C0_SHIFT) + ((1 << C0_SHIFT) >> 1);
883 minc1 = (c1 << BOX_C1_SHIFT) + ((1 << C1_SHIFT) >> 1);
884 minc2 = (c2 << BOX_C2_SHIFT) + ((1 << C2_SHIFT) >> 1);
885
886 /* Determine which colormap entries are close enough to be candidates
887 * for the nearest entry to some cell in the update box.
888 */
889 numcolors = find_nearby_colors(cinfo, minc0, minc1, minc2, colorlist);
890
891 /* Determine the actually nearest colors. */
892 find_best_colors(cinfo, minc0, minc1, minc2, numcolors, colorlist,
893 bestcolor);
894
895 /* Save the best color numbers (plus 1) in the main cache array */
896 c0 <<= BOX_C0_LOG; /* convert ID back to base cell indexes */
897 c1 <<= BOX_C1_LOG;
898 c2 <<= BOX_C2_LOG;
899 cptr = bestcolor;
900 for (ic0 = 0; ic0 < BOX_C0_ELEMS; ic0++) {
901 for (ic1 = 0; ic1 < BOX_C1_ELEMS; ic1++) {
902 cachep = & histogram[c0+ic0][c1+ic1][c2];
903 for (ic2 = 0; ic2 < BOX_C2_ELEMS; ic2++) {
904 *cachep++ = (histcell) (GETJSAMPLE(*cptr++) + 1);
905 }
906 }
907 }
908}
909
910
911/*
912 * Map some rows of pixels to the output colormapped representation.
913 */
914
915METHODDEF(void)
916pass2_no_dither (j_decompress_ptr cinfo,
918/* This version performs no dithering */
919{
920 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
921 hist3d histogram = cquantize->histogram;
922 register JSAMPROW inptr, outptr;
923 register histptr cachep;
924 register int c0, c1, c2;
925 int row;
926 JDIMENSION col;
928
929 for (row = 0; row < num_rows; row++) {
930 inptr = input_buf[row];
931 outptr = output_buf[row];
932 for (col = width; col > 0; col--) {
933 /* get pixel value and index into the cache */
934 c0 = GETJSAMPLE(*inptr++) >> C0_SHIFT;
935 c1 = GETJSAMPLE(*inptr++) >> C1_SHIFT;
936 c2 = GETJSAMPLE(*inptr++) >> C2_SHIFT;
937 cachep = & histogram[c0][c1][c2];
938 /* If we have not seen this color before, find nearest colormap entry */
939 /* and update the cache */
940 if (*cachep == 0)
941 fill_inverse_cmap(cinfo, c0,c1,c2);
942 /* Now emit the colormap index for this cell */
943 *outptr++ = (JSAMPLE) (*cachep - 1);
944 }
945 }
946}
947
948
949METHODDEF(void)
950pass2_fs_dither (j_decompress_ptr cinfo,
952/* This version performs Floyd-Steinberg dithering */
953{
954 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
955 hist3d histogram = cquantize->histogram;
956 register LOCFSERROR cur0, cur1, cur2; /* current error or pixel value */
957 LOCFSERROR belowerr0, belowerr1, belowerr2; /* error for pixel below cur */
958 LOCFSERROR bpreverr0, bpreverr1, bpreverr2; /* error for below/prev col */
959 register FSERRPTR errorptr; /* => fserrors[] at column before current */
960 JSAMPROW inptr; /* => current input pixel */
961 JSAMPROW outptr; /* => current output pixel */
962 histptr cachep;
963 int dir; /* +1 or -1 depending on direction */
964 int dir3; /* 3*dir, for advancing inptr & errorptr */
965 int row;
966 JDIMENSION col;
968 JSAMPLE *range_limit = cinfo->sample_range_limit;
969 int *error_limit = cquantize->error_limiter;
970 JSAMPROW colormap0 = cinfo->colormap[0];
971 JSAMPROW colormap1 = cinfo->colormap[1];
972 JSAMPROW colormap2 = cinfo->colormap[2];
974
975 for (row = 0; row < num_rows; row++) {
976 inptr = input_buf[row];
977 outptr = output_buf[row];
978 if (cquantize->on_odd_row) {
979 /* work right to left in this row */
980 inptr += (width-1) * 3; /* so point to rightmost pixel */
981 outptr += width-1;
982 dir = -1;
983 dir3 = -3;
984 errorptr = cquantize->fserrors + (width+1)*3; /* => entry after last column */
985 cquantize->on_odd_row = FALSE; /* flip for next time */
986 } else {
987 /* work left to right in this row */
988 dir = 1;
989 dir3 = 3;
990 errorptr = cquantize->fserrors; /* => entry before first real column */
991 cquantize->on_odd_row = TRUE; /* flip for next time */
992 }
993 /* Preset error values: no error propagated to first pixel from left */
994 cur0 = cur1 = cur2 = 0;
995 /* and no error propagated to row below yet */
996 belowerr0 = belowerr1 = belowerr2 = 0;
997 bpreverr0 = bpreverr1 = bpreverr2 = 0;
998
999 for (col = width; col > 0; col--) {
1000 /* curN holds the error propagated from the previous pixel on the
1001 * current line. Add the error propagated from the previous line
1002 * to form the complete error correction term for this pixel, and
1003 * round the error term (which is expressed * 16) to an integer.
1004 * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct
1005 * for either sign of the error value.
1006 * Note: errorptr points to *previous* column's array entry.
1007 */
1008 cur0 = RIGHT_SHIFT(cur0 + errorptr[dir3+0] + 8, 4);
1009 cur1 = RIGHT_SHIFT(cur1 + errorptr[dir3+1] + 8, 4);
1010 cur2 = RIGHT_SHIFT(cur2 + errorptr[dir3+2] + 8, 4);
1011 /* Limit the error using transfer function set by init_error_limit.
1012 * See comments with init_error_limit for rationale.
1013 */
1014 cur0 = error_limit[cur0];
1015 cur1 = error_limit[cur1];
1016 cur2 = error_limit[cur2];
1017 /* Form pixel value + error, and range-limit to 0..MAXJSAMPLE.
1018 * The maximum error is +- MAXJSAMPLE (or less with error limiting);
1019 * this sets the required size of the range_limit array.
1020 */
1021 cur0 += GETJSAMPLE(inptr[0]);
1022 cur1 += GETJSAMPLE(inptr[1]);
1023 cur2 += GETJSAMPLE(inptr[2]);
1024 cur0 = GETJSAMPLE(range_limit[cur0]);
1025 cur1 = GETJSAMPLE(range_limit[cur1]);
1026 cur2 = GETJSAMPLE(range_limit[cur2]);
1027 /* Index into the cache with adjusted pixel value */
1028 cachep = & histogram[cur0>>C0_SHIFT][cur1>>C1_SHIFT][cur2>>C2_SHIFT];
1029 /* If we have not seen this color before, find nearest colormap */
1030 /* entry and update the cache */
1031 if (*cachep == 0)
1032 fill_inverse_cmap(cinfo, cur0>>C0_SHIFT,cur1>>C1_SHIFT,cur2>>C2_SHIFT);
1033 /* Now emit the colormap index for this cell */
1034 { register int pixcode = *cachep - 1;
1035 *outptr = (JSAMPLE) pixcode;
1036 /* Compute representation error for this pixel */
1037 cur0 -= GETJSAMPLE(colormap0[pixcode]);
1038 cur1 -= GETJSAMPLE(colormap1[pixcode]);
1039 cur2 -= GETJSAMPLE(colormap2[pixcode]);
1040 }
1041 /* Compute error fractions to be propagated to adjacent pixels.
1042 * Add these into the running sums, and simultaneously shift the
1043 * next-line error sums left by 1 column.
1044 */
1045 { register LOCFSERROR bnexterr, delta;
1046
1047 bnexterr = cur0; /* Process component 0 */
1048 delta = cur0 * 2;
1049 cur0 += delta; /* form error * 3 */
1050 errorptr[0] = (FSERROR) (bpreverr0 + cur0);
1051 cur0 += delta; /* form error * 5 */
1052 bpreverr0 = belowerr0 + cur0;
1053 belowerr0 = bnexterr;
1054 cur0 += delta; /* form error * 7 */
1055 bnexterr = cur1; /* Process component 1 */
1056 delta = cur1 * 2;
1057 cur1 += delta; /* form error * 3 */
1058 errorptr[1] = (FSERROR) (bpreverr1 + cur1);
1059 cur1 += delta; /* form error * 5 */
1060 bpreverr1 = belowerr1 + cur1;
1061 belowerr1 = bnexterr;
1062 cur1 += delta; /* form error * 7 */
1063 bnexterr = cur2; /* Process component 2 */
1064 delta = cur2 * 2;
1065 cur2 += delta; /* form error * 3 */
1066 errorptr[2] = (FSERROR) (bpreverr2 + cur2);
1067 cur2 += delta; /* form error * 5 */
1068 bpreverr2 = belowerr2 + cur2;
1069 belowerr2 = bnexterr;
1070 cur2 += delta; /* form error * 7 */
1071 }
1072 /* At this point curN contains the 7/16 error value to be propagated
1073 * to the next pixel on the current line, and all the errors for the
1074 * next line have been shifted over. We are therefore ready to move on.
1075 */
1076 inptr += dir3; /* Advance pixel pointers to next column */
1077 outptr += dir;
1078 errorptr += dir3; /* advance errorptr to current column */
1079 }
1080 /* Post-loop cleanup: we must unload the final error values into the
1081 * final fserrors[] entry. Note we need not unload belowerrN because
1082 * it is for the dummy column before or after the actual array.
1083 */
1084 errorptr[0] = (FSERROR) bpreverr0; /* unload prev errs into array */
1085 errorptr[1] = (FSERROR) bpreverr1;
1086 errorptr[2] = (FSERROR) bpreverr2;
1087 }
1088}
1089
1090
1091/*
1092 * Initialize the error-limiting transfer function (lookup table).
1093 * The raw F-S error computation can potentially compute error values of up to
1094 * +- MAXJSAMPLE. But we want the maximum correction applied to a pixel to be
1095 * much less, otherwise obviously wrong pixels will be created. (Typical
1096 * effects include weird fringes at color-area boundaries, isolated bright
1097 * pixels in a dark area, etc.) The standard advice for avoiding this problem
1098 * is to ensure that the "corners" of the color cube are allocated as output
1099 * colors; then repeated errors in the same direction cannot cause cascading
1100 * error buildup. However, that only prevents the error from getting
1101 * completely out of hand; Aaron Giles reports that error limiting improves
1102 * the results even with corner colors allocated.
1103 * A simple clamping of the error values to about +- MAXJSAMPLE/8 works pretty
1104 * well, but the smoother transfer function used below is even better. Thanks
1105 * to Aaron Giles for this idea.
1106 */
1107
1108LOCAL(void)
1109init_error_limit (j_decompress_ptr cinfo)
1110/* Allocate and fill in the error_limiter table */
1111{
1112 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1113 int * table;
1114 int in, out;
1115
1116 table = (int *) (*cinfo->mem->alloc_small)
1117 ((j_common_ptr) cinfo, JPOOL_IMAGE, (MAXJSAMPLE*2+1) * SIZEOF(int));
1118 table += MAXJSAMPLE; /* so can index -MAXJSAMPLE .. +MAXJSAMPLE */
1119 cquantize->error_limiter = table;
1120
1121#define STEPSIZE ((MAXJSAMPLE+1)/16)
1122 /* Map errors 1:1 up to +- MAXJSAMPLE/16 */
1123 out = 0;
1124 for (in = 0; in < STEPSIZE; in++, out++) {
1125 table[in] = out; table[-in] = -out;
1126 }
1127 /* Map errors 1:2 up to +- 3*MAXJSAMPLE/16 */
1128 for (; in < STEPSIZE*3; in++, out += (in&1) ? 0 : 1) {
1129 table[in] = out; table[-in] = -out;
1130 }
1131 /* Clamp the rest to final out value (which is (MAXJSAMPLE+1)/8) */
1132 for (; in <= MAXJSAMPLE; in++) {
1133 table[in] = out; table[-in] = -out;
1134 }
1135#undef STEPSIZE
1136}
1137
1138
1139/*
1140 * Finish up at the end of each pass.
1141 */
1142
1143METHODDEF(void)
1144finish_pass1 (j_decompress_ptr cinfo)
1145{
1146 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1147
1148 /* Select the representative colors and fill in cinfo->colormap */
1149 cinfo->colormap = cquantize->sv_colormap;
1150 select_colors(cinfo, cquantize->desired);
1151 /* Force next pass to zero the color index table */
1152 cquantize->needs_zeroed = TRUE;
1153}
1154
1155
1156METHODDEF(void)
1157finish_pass2 (j_decompress_ptr cinfo)
1158{
1159 /* no work */
1160}
1161
1162
1163/*
1164 * Initialize for each processing pass.
1165 */
1166
1167METHODDEF(void)
1168start_pass_2_quant (j_decompress_ptr cinfo, boolean is_pre_scan)
1169{
1170 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1171 hist3d histogram = cquantize->histogram;
1172 int i;
1173
1174 /* Only F-S dithering or no dithering is supported. */
1175 /* If user asks for ordered dither, give him F-S. */
1176 if (cinfo->dither_mode != JDITHER_NONE)
1177 cinfo->dither_mode = JDITHER_FS;
1178
1179 if (is_pre_scan) {
1180 /* Set up method pointers */
1181 cquantize->pub.color_quantize = prescan_quantize;
1182 cquantize->pub.finish_pass = finish_pass1;
1183 cquantize->needs_zeroed = TRUE; /* Always zero histogram */
1184 } else {
1185 /* Set up method pointers */
1186 if (cinfo->dither_mode == JDITHER_FS)
1187 cquantize->pub.color_quantize = pass2_fs_dither;
1188 else
1189 cquantize->pub.color_quantize = pass2_no_dither;
1190 cquantize->pub.finish_pass = finish_pass2;
1191
1192 /* Make sure color count is acceptable */
1193 i = cinfo->actual_number_of_colors;
1194 if (i < 1)
1195 ERREXIT1(cinfo, JERR_QUANT_FEW_COLORS, 1);
1196 if (i > MAXNUMCOLORS)
1197 ERREXIT1(cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS);
1198
1199 if (cinfo->dither_mode == JDITHER_FS) {
1200 size_t arraysize = (size_t) ((cinfo->output_width + 2) *
1201 (3 * SIZEOF(FSERROR)));
1202 /* Allocate Floyd-Steinberg workspace if we didn't already. */
1203 if (cquantize->fserrors == NULL)
1204 cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large)
1205 ((j_common_ptr) cinfo, JPOOL_IMAGE, arraysize);
1206 /* Initialize the propagated errors to zero. */
1207 FMEMZERO((void FAR *) cquantize->fserrors, arraysize);
1208 /* Make the error-limit table if we didn't already. */
1209 if (cquantize->error_limiter == NULL)
1210 init_error_limit(cinfo);
1211 cquantize->on_odd_row = FALSE;
1212 }
1213
1214 }
1215 /* Zero the histogram or inverse color map, if necessary */
1216 if (cquantize->needs_zeroed) {
1217 for (i = 0; i < HIST_C0_ELEMS; i++) {
1218 FMEMZERO((void FAR *) histogram[i],
1219 HIST_C1_ELEMS*HIST_C2_ELEMS * SIZEOF(histcell));
1220 }
1221 cquantize->needs_zeroed = FALSE;
1222 }
1223}
1224
1225
1226/*
1227 * Switch to a new external colormap between output passes.
1228 */
1229
1230METHODDEF(void)
1231new_color_map_2_quant (j_decompress_ptr cinfo)
1232{
1233 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1234
1235 /* Reset the inverse color map */
1236 cquantize->needs_zeroed = TRUE;
1237}
1238
1239
1240/*
1241 * Module initialization routine for 2-pass color quantization.
1242 */
1243
1244GLOBAL(void)
1245jinit_2pass_quantizer (j_decompress_ptr cinfo)
1246{
1247 my_cquantize_ptr cquantize;
1248 int i;
1249
1250 cquantize = (my_cquantize_ptr)
1251 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
1252 SIZEOF(my_cquantizer));
1253 cinfo->cquantize = (struct jpeg_color_quantizer *) cquantize;
1254 cquantize->pub.start_pass = start_pass_2_quant;
1255 cquantize->pub.new_color_map = new_color_map_2_quant;
1256 cquantize->fserrors = NULL; /* flag optional arrays not allocated */
1257 cquantize->error_limiter = NULL;
1258
1259 /* Make sure jdmaster didn't give me a case I can't handle */
1260 if (cinfo->out_color_components != 3)
1261 ERREXIT(cinfo, JERR_NOTIMPL);
1262
1263 /* Allocate the histogram/inverse colormap storage */
1264 cquantize->histogram = (hist3d) (*cinfo->mem->alloc_small)
1265 ((j_common_ptr) cinfo, JPOOL_IMAGE, HIST_C0_ELEMS * SIZEOF(hist2d));
1266 for (i = 0; i < HIST_C0_ELEMS; i++) {
1267 cquantize->histogram[i] = (hist2d) (*cinfo->mem->alloc_large)
1268 ((j_common_ptr) cinfo, JPOOL_IMAGE,
1269 HIST_C1_ELEMS*HIST_C2_ELEMS * SIZEOF(histcell));
1270 }
1271 cquantize->needs_zeroed = TRUE; /* histogram is garbage now */
1272
1273 /* Allocate storage for the completed colormap, if required.
1274 * We do this now since it is FAR storage and may affect
1275 * the memory manager's space calculations.
1276 */
1277 if (cinfo->enable_2pass_quant) {
1278 /* Make sure color count is acceptable */
1279 int desired = cinfo->desired_number_of_colors;
1280 /* Lower bound on # of colors ... somewhat arbitrary as long as > 0 */
1281 if (desired < 8)
1282 ERREXIT1(cinfo, JERR_QUANT_FEW_COLORS, 8);
1283 /* Make sure colormap indexes can be represented by JSAMPLEs */
1284 if (desired > MAXNUMCOLORS)
1285 ERREXIT1(cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS);
1286 cquantize->sv_colormap = (*cinfo->mem->alloc_sarray)
1288 cquantize->desired = desired;
1289 } else
1290 cquantize->sv_colormap = NULL;
1291
1292 /* Only F-S dithering or no dithering is supported. */
1293 /* If user asks for ordered dither, give him F-S. */
1294 if (cinfo->dither_mode != JDITHER_NONE)
1295 cinfo->dither_mode = JDITHER_FS;
1296
1297 /* Allocate Floyd-Steinberg workspace if necessary.
1298 * This isn't really needed until pass 2, but again it is FAR storage.
1299 * Although we will cope with a later change in dither_mode,
1300 * we do not promise to honor max_memory_to_use if dither_mode changes.
1301 */
1302 if (cinfo->dither_mode == JDITHER_FS) {
1303 cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large)
1304 ((j_common_ptr) cinfo, JPOOL_IMAGE,
1305 (size_t) ((cinfo->output_width + 2) * (3 * SIZEOF(FSERROR))));
1306 /* Might as well create the error-limiting table too. */
1307 init_error_limit(cinfo);
1308 }
1309}
1310
1311#endif /* QUANT_2PASS_SUPPORTED */
unsigned short UINT16
signed int INT32
signed short INT16
unsigned int dir
Definition: maze.c:112
#define SIZEOF(_ar)
Definition: calc.h:97
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
#define FAR
Definition: zlib.h:34
static int median_cut(unsigned char *image, unsigned int width, unsigned int height, unsigned int stride, int desired, unsigned int *colors)
Definition: palette.c:607
struct png_info_def *typedef unsigned char **typedef struct png_info_def *typedef struct png_info_def *typedef struct png_info_def *typedef unsigned char ** row
Definition: typeof.h:78
__kernel_size_t size_t
Definition: linux.h:237
size_t total
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLint GLint GLsizei width
Definition: gl.h:1546
GLdouble n
Definition: glext.h:7729
GLuint in
Definition: glext.h:9616
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
jpeg_component_info JCOEFPTR JSAMPARRAY output_buf
Definition: jdct.h:239
#define TRACEMS1(cinfo, lvl, code, p1)
Definition: jerror.h:268
#define ERREXIT1(cinfo, code, p1)
Definition: jerror.h:212
unsigned int JDIMENSION
Definition: jmorecfg.h:229
#define MAXJSAMPLE
Definition: jmorecfg.h:83
char JSAMPLE
Definition: jmorecfg.h:74
#define LOCAL(type)
Definition: jmorecfg.h:289
#define METHODDEF(type)
Definition: jmorecfg.h:287
#define GLOBAL(type)
Definition: jmorecfg.h:291
#define GETJSAMPLE(value)
Definition: jmorecfg.h:78
#define SHIFT_TEMPS
Definition: jpegint.h:301
#define FMEMZERO(target, size)
Definition: jpegint.h:368
int JSAMPARRAY int int num_rows
Definition: jpegint.h:421
#define RIGHT_SHIFT(x, shft)
Definition: jpegint.h:302
struct jpeg_common_struct * j_common_ptr
Definition: jpeglib.h:284
@ JDITHER_NONE
Definition: jpeglib.h:256
@ JDITHER_FS
Definition: jpeglib.h:258
int desired
Definition: jpeglib.h:1119
JSAMPROW * JSAMPARRAY
Definition: jpeglib.h:76
JSAMPLE FAR * JSAMPROW
Definition: jpeglib.h:75
#define JPOOL_IMAGE
Definition: jpeglib.h:808
if(dx< 0)
Definition: linetemp.h:194
#define for
Definition: utility.h:88
static PVOID ptr
Definition: dispmode.c:27
static CRYPT_DATA_BLOB b2[]
Definition: msg.c:582
static CRYPT_DATA_BLOB b1[]
Definition: msg.c:573
#define ERREXIT(msg)
Definition: rdjpgcom.c:72
static FILE * out
Definition: regtests2xml.c:44
Definition: palette.c:468
JSAMPARRAY colormap
Definition: jpeglib.h:527
JSAMPLE * sample_range_limit
Definition: jpeglib.h:642
boolean enable_2pass_quant
Definition: jpeglib.h:499
JDIMENSION output_width
Definition: jpeglib.h:507
J_DITHER_MODE dither_mode
Definition: jpeglib.h:493
struct jpeg_color_quantizer * cquantize
Definition: jpeglib.h:688
static GLenum which
Definition: wgl_font.c:159