w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

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