ReactOS  0.4.15-dev-3720-g4cf9b79
jquant1.c
Go to the documentation of this file.
1 /*
2  * jquant1.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 1-pass color quantization (color mapping) routines.
10  * These routines provide mapping to a fixed color map using equally spaced
11  * color values. Optional Floyd-Steinberg or ordered dithering is available.
12  */
13 
14 #define JPEG_INTERNALS
15 #include "jinclude.h"
16 #include "jpeglib.h"
17 
18 #ifdef QUANT_1PASS_SUPPORTED
19 
20 
21 /*
22  * The main purpose of 1-pass quantization is to provide a fast, if not very
23  * high quality, colormapped output capability. A 2-pass quantizer usually
24  * gives better visual quality; however, for quantized grayscale output this
25  * quantizer is perfectly adequate. Dithering is highly recommended with this
26  * quantizer, though you can turn it off if you really want to.
27  *
28  * In 1-pass quantization the colormap must be chosen in advance of seeing the
29  * image. We use a map consisting of all combinations of Ncolors[i] color
30  * values for the i'th component. The Ncolors[] values are chosen so that
31  * their product, the total number of colors, is no more than that requested.
32  * (In most cases, the product will be somewhat less.)
33  *
34  * Since the colormap is orthogonal, the representative value for each color
35  * component can be determined without considering the other components;
36  * then these indexes can be combined into a colormap index by a standard
37  * N-dimensional-array-subscript calculation. Most of the arithmetic involved
38  * can be precalculated and stored in the lookup table colorindex[].
39  * colorindex[i][j] maps pixel value j in component i to the nearest
40  * representative value (grid plane) for that component; this index is
41  * multiplied by the array stride for component i, so that the
42  * index of the colormap entry closest to a given pixel value is just
43  * sum( colorindex[component-number][pixel-component-value] )
44  * Aside from being fast, this scheme allows for variable spacing between
45  * representative values with no additional lookup cost.
46  *
47  * If gamma correction has been applied in color conversion, it might be wise
48  * to adjust the color grid spacing so that the representative colors are
49  * equidistant in linear space. At this writing, gamma correction is not
50  * implemented by jdcolor, so nothing is done here.
51  */
52 
53 
54 /* Declarations for ordered dithering.
55  *
56  * We use a standard 16x16 ordered dither array. The basic concept of ordered
57  * dithering is described in many references, for instance Dale Schumacher's
58  * chapter II.2 of Graphics Gems II (James Arvo, ed. Academic Press, 1991).
59  * In place of Schumacher's comparisons against a "threshold" value, we add a
60  * "dither" value to the input pixel and then round the result to the nearest
61  * output value. The dither value is equivalent to (0.5 - threshold) times
62  * the distance between output values. For ordered dithering, we assume that
63  * the output colors are equally spaced; if not, results will probably be
64  * worse, since the dither may be too much or too little at a given point.
65  *
66  * The normal calculation would be to form pixel value + dither, range-limit
67  * this to 0..MAXJSAMPLE, and then index into the colorindex table as usual.
68  * We can skip the separate range-limiting step by extending the colorindex
69  * table in both directions.
70  */
71 
72 #define ODITHER_SIZE 16 /* dimension of dither matrix */
73 /* NB: if ODITHER_SIZE is not a power of 2, ODITHER_MASK uses will break */
74 #define ODITHER_CELLS (ODITHER_SIZE*ODITHER_SIZE) /* # cells in matrix */
75 #define ODITHER_MASK (ODITHER_SIZE-1) /* mask for wrapping around counters */
76 
77 typedef int ODITHER_MATRIX[ODITHER_SIZE][ODITHER_SIZE];
78 typedef int (*ODITHER_MATRIX_PTR)[ODITHER_SIZE];
79 
80 static const UINT8 base_dither_matrix[ODITHER_SIZE][ODITHER_SIZE] = {
81  /* Bayer's order-4 dither array. Generated by the code given in
82  * Stephen Hawley's article "Ordered Dithering" in Graphics Gems I.
83  * The values in this array must range from 0 to ODITHER_CELLS-1.
84  */
85  { 0,192, 48,240, 12,204, 60,252, 3,195, 51,243, 15,207, 63,255 },
86  { 128, 64,176,112,140, 76,188,124,131, 67,179,115,143, 79,191,127 },
87  { 32,224, 16,208, 44,236, 28,220, 35,227, 19,211, 47,239, 31,223 },
88  { 160, 96,144, 80,172,108,156, 92,163, 99,147, 83,175,111,159, 95 },
89  { 8,200, 56,248, 4,196, 52,244, 11,203, 59,251, 7,199, 55,247 },
90  { 136, 72,184,120,132, 68,180,116,139, 75,187,123,135, 71,183,119 },
91  { 40,232, 24,216, 36,228, 20,212, 43,235, 27,219, 39,231, 23,215 },
92  { 168,104,152, 88,164,100,148, 84,171,107,155, 91,167,103,151, 87 },
93  { 2,194, 50,242, 14,206, 62,254, 1,193, 49,241, 13,205, 61,253 },
94  { 130, 66,178,114,142, 78,190,126,129, 65,177,113,141, 77,189,125 },
95  { 34,226, 18,210, 46,238, 30,222, 33,225, 17,209, 45,237, 29,221 },
96  { 162, 98,146, 82,174,110,158, 94,161, 97,145, 81,173,109,157, 93 },
97  { 10,202, 58,250, 6,198, 54,246, 9,201, 57,249, 5,197, 53,245 },
98  { 138, 74,186,122,134, 70,182,118,137, 73,185,121,133, 69,181,117 },
99  { 42,234, 26,218, 38,230, 22,214, 41,233, 25,217, 37,229, 21,213 },
100  { 170,106,154, 90,166,102,150, 86,169,105,153, 89,165,101,149, 85 }
101 };
102 
103 
104 /* Declarations for Floyd-Steinberg dithering.
105  *
106  * Errors are accumulated into the array fserrors[], at a resolution of
107  * 1/16th of a pixel count. The error at a given pixel is propagated
108  * to its not-yet-processed neighbors using the standard F-S fractions,
109  * ... (here) 7/16
110  * 3/16 5/16 1/16
111  * We work left-to-right on even rows, right-to-left on odd rows.
112  *
113  * We can get away with a single array (holding one row's worth of errors)
114  * by using it to store the current row's errors at pixel columns not yet
115  * processed, but the next row's errors at columns already processed. We
116  * need only a few extra variables to hold the errors immediately around the
117  * current column. (If we are lucky, those variables are in registers, but
118  * even if not, they're probably cheaper to access than array elements are.)
119  *
120  * The fserrors[] array is indexed [component#][position].
121  * We provide (#columns + 2) entries per component; the extra entry at each
122  * end saves us from special-casing the first and last pixels.
123  *
124  * Note: on a wide image, we might not have enough room in a PC's near data
125  * segment to hold the error array; so it is allocated with alloc_large.
126  */
127 
128 #if BITS_IN_JSAMPLE == 8
129 typedef INT16 FSERROR; /* 16 bits should be enough */
130 typedef int LOCFSERROR; /* use 'int' for calculation temps */
131 #else
132 typedef INT32 FSERROR; /* may need more than 16 bits */
133 typedef INT32 LOCFSERROR; /* be sure calculation temps are big enough */
134 #endif
135 
136 typedef FSERROR FAR *FSERRPTR; /* pointer to error array (in FAR storage!) */
137 
138 
139 /* Private subobject */
140 
141 #define MAX_Q_COMPS 4 /* max components I can handle */
142 
143 typedef struct {
144  struct jpeg_color_quantizer pub; /* public fields */
145 
146  /* Initially allocated colormap is saved here */
147  JSAMPARRAY sv_colormap; /* The color map as a 2-D pixel array */
148  int sv_actual; /* number of entries in use */
149 
150  JSAMPARRAY colorindex; /* Precomputed mapping for speed */
151  /* colorindex[i][j] = index of color closest to pixel value j in component i,
152  * premultiplied as described above. Since colormap indexes must fit into
153  * JSAMPLEs, the entries of this array will too.
154  */
155  boolean is_padded; /* is the colorindex padded for odither? */
156 
157  int Ncolors[MAX_Q_COMPS]; /* # of values alloced to each component */
158 
159  /* Variables for ordered dithering */
160  int row_index; /* cur row's vertical index in dither matrix */
161  ODITHER_MATRIX_PTR odither[MAX_Q_COMPS]; /* one dither array per component */
162 
163  /* Variables for Floyd-Steinberg dithering */
164  FSERRPTR fserrors[MAX_Q_COMPS]; /* accumulated errors */
165  boolean on_odd_row; /* flag to remember which row we are on */
166 } my_cquantizer;
167 
168 typedef my_cquantizer * my_cquantize_ptr;
169 
170 
171 /*
172  * Policy-making subroutines for create_colormap and create_colorindex.
173  * These routines determine the colormap to be used. The rest of the module
174  * only assumes that the colormap is orthogonal.
175  *
176  * * select_ncolors decides how to divvy up the available colors
177  * among the components.
178  * * output_value defines the set of representative values for a component.
179  * * largest_input_value defines the mapping from input values to
180  * representative values for a component.
181  * Note that the latter two routines may impose different policies for
182  * different components, though this is not currently done.
183  */
184 
185 
186 LOCAL(int)
187 select_ncolors (j_decompress_ptr cinfo, int Ncolors[])
188 /* Determine allocation of desired colors to components, */
189 /* and fill in Ncolors[] array to indicate choice. */
190 /* Return value is total number of colors (product of Ncolors[] values). */
191 {
192  int nc = cinfo->out_color_components; /* number of color components */
193  int max_colors = cinfo->desired_number_of_colors;
194  int total_colors, iroot, i, j;
195  boolean changed;
196  long temp;
197  static const int RGB_order[3] = { RGB_GREEN, RGB_RED, RGB_BLUE };
198 
199  /* We can allocate at least the nc'th root of max_colors per component. */
200  /* Compute floor(nc'th root of max_colors). */
201  iroot = 1;
202  do {
203  iroot++;
204  temp = iroot; /* set temp = iroot ** nc */
205  for (i = 1; i < nc; i++)
206  temp *= iroot;
207  } while (temp <= (long) max_colors); /* repeat till iroot exceeds root */
208  iroot--; /* now iroot = floor(root) */
209 
210  /* Must have at least 2 color values per component */
211  if (iroot < 2)
212  ERREXIT1(cinfo, JERR_QUANT_FEW_COLORS, (int) temp);
213 
214  /* Initialize to iroot color values for each component */
215  total_colors = 1;
216  for (i = 0; i < nc; i++) {
217  Ncolors[i] = iroot;
218  total_colors *= iroot;
219  }
220  /* We may be able to increment the count for one or more components without
221  * exceeding max_colors, though we know not all can be incremented.
222  * Sometimes, the first component can be incremented more than once!
223  * (Example: for 16 colors, we start at 2*2*2, go to 3*2*2, then 4*2*2.)
224  * In RGB colorspace, try to increment G first, then R, then B.
225  */
226  do {
227  changed = FALSE;
228  for (i = 0; i < nc; i++) {
229  j = (cinfo->out_color_space == JCS_RGB ? RGB_order[i] : i);
230  /* calculate new total_colors if Ncolors[j] is incremented */
231  temp = total_colors / Ncolors[j];
232  temp *= Ncolors[j]+1; /* done in long arith to avoid oflo */
233  if (temp > (long) max_colors)
234  break; /* won't fit, done with this pass */
235  Ncolors[j]++; /* OK, apply the increment */
236  total_colors = (int) temp;
237  changed = TRUE;
238  }
239  } while (changed);
240 
241  return total_colors;
242 }
243 
244 
245 LOCAL(int)
246 output_value (j_decompress_ptr cinfo, int ci, int j, int maxj)
247 /* Return j'th output value, where j will range from 0 to maxj */
248 /* The output values must fall in 0..MAXJSAMPLE in increasing order */
249 {
250  /* We always provide values 0 and MAXJSAMPLE for each component;
251  * any additional values are equally spaced between these limits.
252  * (Forcing the upper and lower values to the limits ensures that
253  * dithering can't produce a color outside the selected gamut.)
254  */
255  return (int) (((INT32) j * MAXJSAMPLE + maxj/2) / maxj);
256 }
257 
258 
259 LOCAL(int)
260 largest_input_value (j_decompress_ptr cinfo, int ci, int j, int maxj)
261 /* Return largest input value that should map to j'th output value */
262 /* Must have largest(j=0) >= 0, and largest(j=maxj) >= MAXJSAMPLE */
263 {
264  /* Breakpoints are halfway between values returned by output_value */
265  return (int) (((INT32) (2*j + 1) * MAXJSAMPLE + maxj) / (2*maxj));
266 }
267 
268 
269 /*
270  * Create the colormap.
271  */
272 
273 LOCAL(void)
274 create_colormap (j_decompress_ptr cinfo)
275 {
276  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
277  JSAMPARRAY colormap; /* Created colormap */
278  int total_colors; /* Number of distinct output colors */
279  int i,j,k, nci, blksize, blkdist, ptr, val;
280 
281  /* Select number of colors for each component */
282  total_colors = select_ncolors(cinfo, cquantize->Ncolors);
283 
284  /* Report selected color counts */
285  if (cinfo->out_color_components == 3)
286  TRACEMS4(cinfo, 1, JTRC_QUANT_3_NCOLORS,
287  total_colors, cquantize->Ncolors[0],
288  cquantize->Ncolors[1], cquantize->Ncolors[2]);
289  else
290  TRACEMS1(cinfo, 1, JTRC_QUANT_NCOLORS, total_colors);
291 
292  /* Allocate and fill in the colormap. */
293  /* The colors are ordered in the map in standard row-major order, */
294  /* i.e. rightmost (highest-indexed) color changes most rapidly. */
295 
296  colormap = (*cinfo->mem->alloc_sarray)
297  ((j_common_ptr) cinfo, JPOOL_IMAGE,
298  (JDIMENSION) total_colors, (JDIMENSION) cinfo->out_color_components);
299 
300  /* blksize is number of adjacent repeated entries for a component */
301  /* blkdist is distance between groups of identical entries for a component */
302  blkdist = total_colors;
303 
304  for (i = 0; i < cinfo->out_color_components; i++) {
305  /* fill in colormap entries for i'th color component */
306  nci = cquantize->Ncolors[i]; /* # of distinct values for this color */
307  blksize = blkdist / nci;
308  for (j = 0; j < nci; j++) {
309  /* Compute j'th output value (out of nci) for component */
310  val = output_value(cinfo, i, j, nci-1);
311  /* Fill in all colormap entries that have this value of this component */
312  for (ptr = j * blksize; ptr < total_colors; ptr += blkdist) {
313  /* fill in blksize entries beginning at ptr */
314  for (k = 0; k < blksize; k++)
315  colormap[i][ptr+k] = (JSAMPLE) val;
316  }
317  }
318  blkdist = blksize; /* blksize of this color is blkdist of next */
319  }
320 
321  /* Save the colormap in private storage,
322  * where it will survive color quantization mode changes.
323  */
324  cquantize->sv_colormap = colormap;
325  cquantize->sv_actual = total_colors;
326 }
327 
328 
329 /*
330  * Create the color index table.
331  */
332 
333 LOCAL(void)
334 create_colorindex (j_decompress_ptr cinfo)
335 {
336  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
337  JSAMPROW indexptr;
338  int i,j,k, nci, blksize, val, pad;
339 
340  /* For ordered dither, we pad the color index tables by MAXJSAMPLE in
341  * each direction (input index values can be -MAXJSAMPLE .. 2*MAXJSAMPLE).
342  * This is not necessary in the other dithering modes. However, we
343  * flag whether it was done in case user changes dithering mode.
344  */
345  if (cinfo->dither_mode == JDITHER_ORDERED) {
346  pad = MAXJSAMPLE*2;
347  cquantize->is_padded = TRUE;
348  } else {
349  pad = 0;
350  cquantize->is_padded = FALSE;
351  }
352 
353  cquantize->colorindex = (*cinfo->mem->alloc_sarray)
354  ((j_common_ptr) cinfo, JPOOL_IMAGE,
355  (JDIMENSION) (MAXJSAMPLE+1 + pad),
357 
358  /* blksize is number of adjacent repeated entries for a component */
359  blksize = cquantize->sv_actual;
360 
361  for (i = 0; i < cinfo->out_color_components; i++) {
362  /* fill in colorindex entries for i'th color component */
363  nci = cquantize->Ncolors[i]; /* # of distinct values for this color */
364  blksize = blksize / nci;
365 
366  /* adjust colorindex pointers to provide padding at negative indexes. */
367  if (pad)
368  cquantize->colorindex[i] += MAXJSAMPLE;
369 
370  /* in loop, val = index of current output value, */
371  /* and k = largest j that maps to current val */
372  indexptr = cquantize->colorindex[i];
373  val = 0;
374  k = largest_input_value(cinfo, i, 0, nci-1);
375  for (j = 0; j <= MAXJSAMPLE; j++) {
376  while (j > k) /* advance val if past boundary */
377  k = largest_input_value(cinfo, i, ++val, nci-1);
378  /* premultiply so that no multiplication needed in main processing */
379  indexptr[j] = (JSAMPLE) (val * blksize);
380  }
381  /* Pad at both ends if necessary */
382  if (pad)
383  for (j = 1; j <= MAXJSAMPLE; j++) {
384  indexptr[-j] = indexptr[0];
385  indexptr[MAXJSAMPLE+j] = indexptr[MAXJSAMPLE];
386  }
387  }
388 }
389 
390 
391 /*
392  * Create an ordered-dither array for a component having ncolors
393  * distinct output values.
394  */
395 
396 LOCAL(ODITHER_MATRIX_PTR)
397 make_odither_array (j_decompress_ptr cinfo, int ncolors)
398 {
399  ODITHER_MATRIX_PTR odither;
400  int j,k;
401  INT32 num,den;
402 
403  odither = (ODITHER_MATRIX_PTR)
404  (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
405  SIZEOF(ODITHER_MATRIX));
406  /* The inter-value distance for this color is MAXJSAMPLE/(ncolors-1).
407  * Hence the dither value for the matrix cell with fill order f
408  * (f=0..N-1) should be (N-1-2*f)/(2*N) * MAXJSAMPLE/(ncolors-1).
409  * On 16-bit-int machine, be careful to avoid overflow.
410  */
411  den = 2 * ODITHER_CELLS * ((INT32) (ncolors - 1));
412  for (j = 0; j < ODITHER_SIZE; j++) {
413  for (k = 0; k < ODITHER_SIZE; k++) {
414  num = ((INT32) (ODITHER_CELLS-1 - 2*((int)base_dither_matrix[j][k])))
415  * MAXJSAMPLE;
416  /* Ensure round towards zero despite C's lack of consistency
417  * about rounding negative values in integer division...
418  */
419  odither[j][k] = (int) (num<0 ? -((-num)/den) : num/den);
420  }
421  }
422  return odither;
423 }
424 
425 
426 /*
427  * Create the ordered-dither tables.
428  * Components having the same number of representative colors may
429  * share a dither table.
430  */
431 
432 LOCAL(void)
433 create_odither_tables (j_decompress_ptr cinfo)
434 {
435  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
436  ODITHER_MATRIX_PTR odither;
437  int i, j, nci;
438 
439  for (i = 0; i < cinfo->out_color_components; i++) {
440  nci = cquantize->Ncolors[i]; /* # of distinct values for this color */
441  odither = NULL; /* search for matching prior component */
442  for (j = 0; j < i; j++) {
443  if (nci == cquantize->Ncolors[j]) {
444  odither = cquantize->odither[j];
445  break;
446  }
447  }
448  if (odither == NULL) /* need a new table? */
449  odither = make_odither_array(cinfo, nci);
450  cquantize->odither[i] = odither;
451  }
452 }
453 
454 
455 /*
456  * Map some rows of pixels to the output colormapped representation.
457  */
458 
459 METHODDEF(void)
460 color_quantize (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
462 /* General case, no dithering */
463 {
464  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
465  JSAMPARRAY colorindex = cquantize->colorindex;
466  register int pixcode, ci;
467  register JSAMPROW ptrin, ptrout;
468  int row;
469  JDIMENSION col;
470  JDIMENSION width = cinfo->output_width;
471  register int nc = cinfo->out_color_components;
472 
473  for (row = 0; row < num_rows; row++) {
474  ptrin = input_buf[row];
475  ptrout = output_buf[row];
476  for (col = width; col > 0; col--) {
477  pixcode = 0;
478  for (ci = 0; ci < nc; ci++) {
479  pixcode += GETJSAMPLE(colorindex[ci][GETJSAMPLE(*ptrin++)]);
480  }
481  *ptrout++ = (JSAMPLE) pixcode;
482  }
483  }
484 }
485 
486 
487 METHODDEF(void)
488 color_quantize3 (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
490 /* Fast path for out_color_components==3, no dithering */
491 {
492  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
493  register int pixcode;
494  register JSAMPROW ptrin, ptrout;
495  JSAMPROW colorindex0 = cquantize->colorindex[0];
496  JSAMPROW colorindex1 = cquantize->colorindex[1];
497  JSAMPROW colorindex2 = cquantize->colorindex[2];
498  int row;
499  JDIMENSION col;
500  JDIMENSION width = cinfo->output_width;
501 
502  for (row = 0; row < num_rows; row++) {
503  ptrin = input_buf[row];
504  ptrout = output_buf[row];
505  for (col = width; col > 0; col--) {
506  pixcode = GETJSAMPLE(colorindex0[GETJSAMPLE(*ptrin++)]);
507  pixcode += GETJSAMPLE(colorindex1[GETJSAMPLE(*ptrin++)]);
508  pixcode += GETJSAMPLE(colorindex2[GETJSAMPLE(*ptrin++)]);
509  *ptrout++ = (JSAMPLE) pixcode;
510  }
511  }
512 }
513 
514 
515 METHODDEF(void)
516 quantize_ord_dither (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
518 /* General case, with ordered dithering */
519 {
520  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
521  register JSAMPROW input_ptr;
522  register JSAMPROW output_ptr;
523  JSAMPROW colorindex_ci;
524  int * dither; /* points to active row of dither matrix */
525  int row_index, col_index; /* current indexes into dither matrix */
526  int nc = cinfo->out_color_components;
527  int ci;
528  int row;
529  JDIMENSION col;
530  JDIMENSION width = cinfo->output_width;
531 
532  for (row = 0; row < num_rows; row++) {
533  /* Initialize output values to 0 so can process components separately */
534  FMEMZERO((void FAR *) output_buf[row],
535  (size_t) (width * SIZEOF(JSAMPLE)));
536  row_index = cquantize->row_index;
537  for (ci = 0; ci < nc; ci++) {
538  input_ptr = input_buf[row] + ci;
539  output_ptr = output_buf[row];
540  colorindex_ci = cquantize->colorindex[ci];
541  dither = cquantize->odither[ci][row_index];
542  col_index = 0;
543 
544  for (col = width; col > 0; col--) {
545  /* Form pixel value + dither, range-limit to 0..MAXJSAMPLE,
546  * select output value, accumulate into output code for this pixel.
547  * Range-limiting need not be done explicitly, as we have extended
548  * the colorindex table to produce the right answers for out-of-range
549  * inputs. The maximum dither is +- MAXJSAMPLE; this sets the
550  * required amount of padding.
551  */
552  *output_ptr += colorindex_ci[GETJSAMPLE(*input_ptr)+dither[col_index]];
553  input_ptr += nc;
554  output_ptr++;
555  col_index = (col_index + 1) & ODITHER_MASK;
556  }
557  }
558  /* Advance row index for next row */
559  row_index = (row_index + 1) & ODITHER_MASK;
560  cquantize->row_index = row_index;
561  }
562 }
563 
564 
565 METHODDEF(void)
566 quantize3_ord_dither (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
568 /* Fast path for out_color_components==3, with ordered dithering */
569 {
570  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
571  register int pixcode;
572  register JSAMPROW input_ptr;
573  register JSAMPROW output_ptr;
574  JSAMPROW colorindex0 = cquantize->colorindex[0];
575  JSAMPROW colorindex1 = cquantize->colorindex[1];
576  JSAMPROW colorindex2 = cquantize->colorindex[2];
577  int * dither0; /* points to active row of dither matrix */
578  int * dither1;
579  int * dither2;
580  int row_index, col_index; /* current indexes into dither matrix */
581  int row;
582  JDIMENSION col;
583  JDIMENSION width = cinfo->output_width;
584 
585  for (row = 0; row < num_rows; row++) {
586  row_index = cquantize->row_index;
587  input_ptr = input_buf[row];
588  output_ptr = output_buf[row];
589  dither0 = cquantize->odither[0][row_index];
590  dither1 = cquantize->odither[1][row_index];
591  dither2 = cquantize->odither[2][row_index];
592  col_index = 0;
593 
594  for (col = width; col > 0; col--) {
595  pixcode = GETJSAMPLE(colorindex0[GETJSAMPLE(*input_ptr++) +
596  dither0[col_index]]);
597  pixcode += GETJSAMPLE(colorindex1[GETJSAMPLE(*input_ptr++) +
598  dither1[col_index]]);
599  pixcode += GETJSAMPLE(colorindex2[GETJSAMPLE(*input_ptr++) +
600  dither2[col_index]]);
601  *output_ptr++ = (JSAMPLE) pixcode;
602  col_index = (col_index + 1) & ODITHER_MASK;
603  }
604  row_index = (row_index + 1) & ODITHER_MASK;
605  cquantize->row_index = row_index;
606  }
607 }
608 
609 
610 METHODDEF(void)
611 quantize_fs_dither (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
613 /* General case, with Floyd-Steinberg dithering */
614 {
615  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
616  register LOCFSERROR cur; /* current error or pixel value */
617  LOCFSERROR belowerr; /* error for pixel below cur */
618  LOCFSERROR bpreverr; /* error for below/prev col */
619  LOCFSERROR bnexterr; /* error for below/next col */
620  LOCFSERROR delta;
621  register FSERRPTR errorptr; /* => fserrors[] at column before current */
622  register JSAMPROW input_ptr;
623  register JSAMPROW output_ptr;
624  JSAMPROW colorindex_ci;
625  JSAMPROW colormap_ci;
626  int pixcode;
627  int nc = cinfo->out_color_components;
628  int dir; /* 1 for left-to-right, -1 for right-to-left */
629  int dirnc; /* dir * nc */
630  int ci;
631  int row;
632  JDIMENSION col;
633  JDIMENSION width = cinfo->output_width;
634  JSAMPLE *range_limit = cinfo->sample_range_limit;
636 
637  for (row = 0; row < num_rows; row++) {
638  /* Initialize output values to 0 so can process components separately */
639  FMEMZERO((void FAR *) output_buf[row],
640  (size_t) (width * SIZEOF(JSAMPLE)));
641  for (ci = 0; ci < nc; ci++) {
642  input_ptr = input_buf[row] + ci;
643  output_ptr = output_buf[row];
644  if (cquantize->on_odd_row) {
645  /* work right to left in this row */
646  input_ptr += (width-1) * nc; /* so point to rightmost pixel */
647  output_ptr += width-1;
648  dir = -1;
649  dirnc = -nc;
650  errorptr = cquantize->fserrors[ci] + (width+1); /* => entry after last column */
651  } else {
652  /* work left to right in this row */
653  dir = 1;
654  dirnc = nc;
655  errorptr = cquantize->fserrors[ci]; /* => entry before first column */
656  }
657  colorindex_ci = cquantize->colorindex[ci];
658  colormap_ci = cquantize->sv_colormap[ci];
659  /* Preset error values: no error propagated to first pixel from left */
660  cur = 0;
661  /* and no error propagated to row below yet */
662  belowerr = bpreverr = 0;
663 
664  for (col = width; col > 0; col--) {
665  /* cur holds the error propagated from the previous pixel on the
666  * current line. Add the error propagated from the previous line
667  * to form the complete error correction term for this pixel, and
668  * round the error term (which is expressed * 16) to an integer.
669  * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct
670  * for either sign of the error value.
671  * Note: errorptr points to *previous* column's array entry.
672  */
673  cur = RIGHT_SHIFT(cur + errorptr[dir] + 8, 4);
674  /* Form pixel value + error, and range-limit to 0..MAXJSAMPLE.
675  * The maximum error is +- MAXJSAMPLE; this sets the required size
676  * of the range_limit array.
677  */
678  cur += GETJSAMPLE(*input_ptr);
679  cur = GETJSAMPLE(range_limit[cur]);
680  /* Select output value, accumulate into output code for this pixel */
681  pixcode = GETJSAMPLE(colorindex_ci[cur]);
682  *output_ptr += (JSAMPLE) pixcode;
683  /* Compute actual representation error at this pixel */
684  /* Note: we can do this even though we don't have the final */
685  /* pixel code, because the colormap is orthogonal. */
686  cur -= GETJSAMPLE(colormap_ci[pixcode]);
687  /* Compute error fractions to be propagated to adjacent pixels.
688  * Add these into the running sums, and simultaneously shift the
689  * next-line error sums left by 1 column.
690  */
691  bnexterr = cur;
692  delta = cur * 2;
693  cur += delta; /* form error * 3 */
694  errorptr[0] = (FSERROR) (bpreverr + cur);
695  cur += delta; /* form error * 5 */
696  bpreverr = belowerr + cur;
697  belowerr = bnexterr;
698  cur += delta; /* form error * 7 */
699  /* At this point cur contains the 7/16 error value to be propagated
700  * to the next pixel on the current line, and all the errors for the
701  * next line have been shifted over. We are therefore ready to move on.
702  */
703  input_ptr += dirnc; /* advance input ptr to next column */
704  output_ptr += dir; /* advance output ptr to next column */
705  errorptr += dir; /* advance errorptr to current column */
706  }
707  /* Post-loop cleanup: we must unload the final error value into the
708  * final fserrors[] entry. Note we need not unload belowerr because
709  * it is for the dummy column before or after the actual array.
710  */
711  errorptr[0] = (FSERROR) bpreverr; /* unload prev err into array */
712  }
713  cquantize->on_odd_row = (cquantize->on_odd_row ? FALSE : TRUE);
714  }
715 }
716 
717 
718 /*
719  * Allocate workspace for Floyd-Steinberg errors.
720  */
721 
722 LOCAL(void)
723 alloc_fs_workspace (j_decompress_ptr cinfo)
724 {
725  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
726  size_t arraysize;
727  int i;
728 
729  arraysize = (size_t) ((cinfo->output_width + 2) * SIZEOF(FSERROR));
730  for (i = 0; i < cinfo->out_color_components; i++) {
731  cquantize->fserrors[i] = (FSERRPTR)
732  (*cinfo->mem->alloc_large)((j_common_ptr) cinfo, JPOOL_IMAGE, arraysize);
733  }
734 }
735 
736 
737 /*
738  * Initialize for one-pass color quantization.
739  */
740 
741 METHODDEF(void)
742 start_pass_1_quant (j_decompress_ptr cinfo, boolean is_pre_scan)
743 {
744  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
745  size_t arraysize;
746  int i;
747 
748  /* Install my colormap. */
749  cinfo->colormap = cquantize->sv_colormap;
750  cinfo->actual_number_of_colors = cquantize->sv_actual;
751 
752  /* Initialize for desired dithering mode. */
753  switch (cinfo->dither_mode) {
754  case JDITHER_NONE:
755  if (cinfo->out_color_components == 3)
756  cquantize->pub.color_quantize = color_quantize3;
757  else
758  cquantize->pub.color_quantize = color_quantize;
759  break;
760  case JDITHER_ORDERED:
761  if (cinfo->out_color_components == 3)
762  cquantize->pub.color_quantize = quantize3_ord_dither;
763  else
764  cquantize->pub.color_quantize = quantize_ord_dither;
765  cquantize->row_index = 0; /* initialize state for ordered dither */
766  /* If user changed to ordered dither from another mode,
767  * we must recreate the color index table with padding.
768  * This will cost extra space, but probably isn't very likely.
769  */
770  if (! cquantize->is_padded)
771  create_colorindex(cinfo);
772  /* Create ordered-dither tables if we didn't already. */
773  if (cquantize->odither[0] == NULL)
774  create_odither_tables(cinfo);
775  break;
776  case JDITHER_FS:
777  cquantize->pub.color_quantize = quantize_fs_dither;
778  cquantize->on_odd_row = FALSE; /* initialize state for F-S dither */
779  /* Allocate Floyd-Steinberg workspace if didn't already. */
780  if (cquantize->fserrors[0] == NULL)
781  alloc_fs_workspace(cinfo);
782  /* Initialize the propagated errors to zero. */
783  arraysize = (size_t) ((cinfo->output_width + 2) * SIZEOF(FSERROR));
784  for (i = 0; i < cinfo->out_color_components; i++)
785  FMEMZERO((void FAR *) cquantize->fserrors[i], arraysize);
786  break;
787  default:
788  ERREXIT(cinfo, JERR_NOT_COMPILED);
789  break;
790  }
791 }
792 
793 
794 /*
795  * Finish up at the end of the pass.
796  */
797 
798 METHODDEF(void)
799 finish_pass_1_quant (j_decompress_ptr cinfo)
800 {
801  /* no work in 1-pass case */
802 }
803 
804 
805 /*
806  * Switch to a new external colormap between output passes.
807  * Shouldn't get to this module!
808  */
809 
810 METHODDEF(void)
811 new_color_map_1_quant (j_decompress_ptr cinfo)
812 {
813  ERREXIT(cinfo, JERR_MODE_CHANGE);
814 }
815 
816 
817 /*
818  * Module initialization routine for 1-pass color quantization.
819  */
820 
821 GLOBAL(void)
822 jinit_1pass_quantizer (j_decompress_ptr cinfo)
823 {
824  my_cquantize_ptr cquantize;
825 
826  cquantize = (my_cquantize_ptr)
827  (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
828  SIZEOF(my_cquantizer));
829  cinfo->cquantize = (struct jpeg_color_quantizer *) cquantize;
830  cquantize->pub.start_pass = start_pass_1_quant;
831  cquantize->pub.finish_pass = finish_pass_1_quant;
832  cquantize->pub.new_color_map = new_color_map_1_quant;
833  cquantize->fserrors[0] = NULL; /* Flag FS workspace not allocated */
834  cquantize->odither[0] = NULL; /* Also flag odither arrays not allocated */
835 
836  /* Make sure my internal arrays won't overflow */
837  if (cinfo->out_color_components > MAX_Q_COMPS)
838  ERREXIT1(cinfo, JERR_QUANT_COMPONENTS, MAX_Q_COMPS);
839  /* Make sure colormap indexes can be represented by JSAMPLEs */
840  if (cinfo->desired_number_of_colors > (MAXJSAMPLE+1))
841  ERREXIT1(cinfo, JERR_QUANT_MANY_COLORS, MAXJSAMPLE+1);
842 
843  /* Create the colormap and color index table. */
844  create_colormap(cinfo);
845  create_colorindex(cinfo);
846 
847  /* Allocate Floyd-Steinberg workspace now if requested.
848  * We do this now since it is FAR storage and may affect the memory
849  * manager's space calculations. If the user changes to FS dither
850  * mode in a later pass, we will allocate the space then, and will
851  * possibly overrun the max_memory_to_use setting.
852  */
853  if (cinfo->dither_mode == JDITHER_FS)
854  alloc_fs_workspace(cinfo);
855 }
856 
857 #endif /* QUANT_1PASS_SUPPORTED */
GLint GLint GLsizei width
Definition: gl.h:1546
char JSAMPLE
Definition: jmorecfg.h:74
JSAMPLE FAR * JSAMPROW
Definition: jpeglib.h:75
#define ERREXIT(msg)
Definition: rdjpgcom.c:72
#define TRUE
Definition: types.h:120
struct jpeg_common_struct * j_common_ptr
Definition: jpeglib.h:284
#define GETJSAMPLE(value)
Definition: jmorecfg.h:78
JDIMENSION output_width
Definition: jpeglib.h:507
#define MAXJSAMPLE
Definition: jmorecfg.h:83
if(dx==0 &&dy==0)
Definition: linetemp.h:174
#define SHIFT_TEMPS
Definition: jpegint.h:301
#define SIZEOF(_ar)
Definition: calc.h:97
#define JPOOL_IMAGE
Definition: jpeglib.h:808
#define FALSE
Definition: types.h:117
J_COLOR_SPACE out_color_space
Definition: jpeglib.h:478
static PVOID ptr
Definition: dispmode.c:27
#define TRACEMS1(cinfo, lvl, code, p1)
Definition: jerror.h:268
switch(r->id)
Definition: btrfs.c:2980
unsigned int dir
Definition: maze.c:112
#define LOCAL(type)
Definition: jmorecfg.h:289
GLuint GLfloat * val
Definition: glext.h:7180
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 GLint GLint j
Definition: glfuncs.h:250
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
int JSAMPARRAY int int num_rows
Definition: jpegint.h:419
#define for
Definition: utility.h:88
GLuint GLuint num
Definition: glext.h:9618
J_DITHER_MODE dither_mode
Definition: jpeglib.h:493
struct jpeg_progress_mgr pub
Definition: cdjpeg.h:83
#define ERREXIT1(cinfo, code, p1)
Definition: jerror.h:212
static void output_value(const WCHAR *value_name, DWORD type, BYTE *data, DWORD data_size)
Definition: reg.c:603
JSAMPARRAY colormap
Definition: jpeglib.h:527
JSAMPROW * JSAMPARRAY
Definition: jpeglib.h:76
FxCollectionEntry * cur
#define GLOBAL(type)
Definition: jmorecfg.h:291
MYWORD blksize
Definition: tftpd.cpp:45
#define METHODDEF(type)
Definition: jmorecfg.h:287
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
static calc_node_t temp
Definition: rpn_ieee.c:38
#define RIGHT_SHIFT(x, shft)
Definition: jpegint.h:302
#define NULL
Definition: types.h:112
jpeg_component_info JCOEFPTR JSAMPARRAY output_buf
Definition: jdct.h:238
unsigned int JDIMENSION
Definition: jmorecfg.h:229
#define TRACEMS4(cinfo, lvl, code, p1, p2, p3, p4)
Definition: jerror.h:282
signed int INT32
#define FAR
Definition: zlib.h:34
unsigned char UINT8
int k
Definition: mpi.c:3369
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
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31
#define FMEMZERO(target, size)
Definition: jpegint.h:368
signed short INT16