ReactOS  0.4.14-dev-384-g5b37caa
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 
148 typedef UINT16 histcell; /* histogram cell; prefer an unsigned type */
149 
150 typedef histcell FAR * histptr; /* for pointers to histogram cells */
151 
152 typedef histcell hist1d[HIST_C2_ELEMS]; /* typedefs for the array */
153 typedef hist1d FAR * hist2d; /* type for the 2nd-level pointers */
154 typedef 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
182 typedef INT16 FSERROR; /* 16 bits should be enough */
183 typedef int LOCFSERROR; /* use 'int' for calculation temps */
184 #else
185 typedef INT32 FSERROR; /* may need more than 16 bits */
186 typedef INT32 LOCFSERROR; /* be sure calculation temps are big enough */
187 #endif
188 
189 typedef FSERROR FAR *FSERRPTR; /* pointer to error array (in FAR storage!) */
190 
191 
192 /* Private subobject */
193 
194 typedef 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 
212 typedef 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 
224 METHODDEF(void)
225 prescan_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;
234  JDIMENSION width = cinfo->output_width;
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 
259 typedef 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 */
265  INT32 volume;
266  /* The number of nonzero histogram cells within this box */
267  long colorcount;
268 } box;
269 
270 typedef box * boxptr;
271 
272 
273 LOCAL(boxptr)
274 find_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 
293 LOCAL(boxptr)
294 find_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 
313 LOCAL(void)
314 update_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 
424 LOCAL(int)
425 median_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 
499 LOCAL(void)
500 compute_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 
539 LOCAL(void)
540 select_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 
646 LOCAL(int)
647 find_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 
775 LOCAL(void)
776 find_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 
855 LOCAL(void)
856 fill_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 
915 METHODDEF(void)
916 pass2_no_dither (j_decompress_ptr cinfo,
917  JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows)
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;
927  JDIMENSION width = cinfo->output_width;
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 
949 METHODDEF(void)
950 pass2_fs_dither (j_decompress_ptr cinfo,
951  JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows)
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;
967  JDIMENSION width = cinfo->output_width;
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 
1108 LOCAL(void)
1109 init_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 
1143 METHODDEF(void)
1144 finish_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 
1156 METHODDEF(void)
1157 finish_pass2 (j_decompress_ptr cinfo)
1158 {
1159  /* no work */
1160 }
1161 
1162 
1163 /*
1164  * Initialize for each processing pass.
1165  */
1166 
1167 METHODDEF(void)
1168 start_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 
1230 METHODDEF(void)
1231 new_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 
1244 GLOBAL(void)
1245 jinit_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 */
GLint GLint GLsizei width
Definition: gl.h:1546
#define TRUE
Definition: types.h:120
char JSAMPLE
Definition: jmorecfg.h:74
JSAMPLE FAR * JSAMPROW
Definition: jpeglib.h:75
#define ERREXIT(msg)
Definition: rdjpgcom.c:72
static GLenum which
Definition: wgl_font.c:159
GLuint GLuint GLsizei count
Definition: gl.h:1545
int desired
Definition: jpeglib.h:1116
boolean enable_2pass_quant
Definition: jpeglib.h:499
struct jpeg_common_struct * j_common_ptr
Definition: jpeglib.h:284
GLdouble n
Definition: glext.h:7729
GLenum GLsizei GLenum GLenum const GLvoid * table
Definition: glext.h:5644
#define GETJSAMPLE(value)
Definition: jmorecfg.h:78
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
JDIMENSION output_width
Definition: jpeglib.h:507
#define MAXJSAMPLE
Definition: jmorecfg.h:83
#define SHIFT_TEMPS
Definition: jpegint.h:301
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
#define SIZEOF(_ar)
Definition: calc.h:97
#define JPOOL_IMAGE
Definition: jpeglib.h:808
#define FAR
Definition: guiddef.h:36
static PVOID ptr
Definition: dispmode.c:27
static CRYPT_DATA_BLOB b1[]
Definition: msg.c:573
#define TRACEMS1(cinfo, lvl, code, p1)
Definition: jerror.h:268
smooth NULL
Definition: ftsmooth.c:416
unsigned int dir
Definition: maze.c:112
#define LOCAL(type)
Definition: jmorecfg.h:289
JSAMPLE * sample_range_limit
Definition: jpeglib.h:642
__kernel_size_t size_t
Definition: linux.h:237
struct jpeg_color_quantizer * cquantize
Definition: jpeglib.h:688
if(!(yy_init))
Definition: macro.lex.yy.c:714
int JSAMPARRAY int int num_rows
Definition: jpegint.h:412
static FILE * out
Definition: regtests2xml.c:44
#define for
Definition: utility.h:88
J_DITHER_MODE dither_mode
Definition: jpeglib.h:493
static const WCHAR L[]
Definition: oid.c:1250
#define ERREXIT1(cinfo, code, p1)
Definition: jerror.h:212
JSAMPARRAY colormap
Definition: jpeglib.h:527
JSAMPROW * JSAMPARRAY
Definition: jpeglib.h:76
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
#define GLOBAL(type)
Definition: jmorecfg.h:291
#define METHODDEF(type)
Definition: jmorecfg.h:287
GLuint in
Definition: glext.h:9616
#define RIGHT_SHIFT(x, shft)
Definition: jpegint.h:302
unsigned short UINT16
jpeg_component_info JCOEFPTR JSAMPARRAY output_buf
Definition: jdct.h:238
unsigned int JDIMENSION
Definition: jmorecfg.h:229
signed int INT32
static CRYPT_DATA_BLOB b2[]
Definition: msg.c:582
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
Definition: palette.c:467
#define FMEMZERO(target, size)
Definition: jpegint.h:361
signed short INT16