1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/libjpeg/jquant1.c	Thu Sep 08 06:28:38 2011 +0300
     1.3 @@ -0,0 +1,856 @@
     1.4 +/*
     1.5 + * jquant1.c
     1.6 + *
     1.7 + * Copyright (C) 1991-1996, Thomas G. Lane.
     1.8 + * This file is part of the Independent JPEG Group's software.
     1.9 + * For conditions of distribution and use, see the accompanying README file.
    1.10 + *
    1.11 + * This file contains 1-pass color quantization (color mapping) routines.
    1.12 + * These routines provide mapping to a fixed color map using equally spaced
    1.13 + * color values.  Optional Floyd-Steinberg or ordered dithering is available.
    1.14 + */
    1.15 +
    1.16 +#define JPEG_INTERNALS
    1.17 +#include "jinclude.h"
    1.18 +#include "jpeglib.h"
    1.19 +
    1.20 +#ifdef QUANT_1PASS_SUPPORTED
    1.21 +
    1.22 +
    1.23 +/*
    1.24 + * The main purpose of 1-pass quantization is to provide a fast, if not very
    1.25 + * high quality, colormapped output capability.  A 2-pass quantizer usually
    1.26 + * gives better visual quality; however, for quantized grayscale output this
    1.27 + * quantizer is perfectly adequate.  Dithering is highly recommended with this
    1.28 + * quantizer, though you can turn it off if you really want to.
    1.29 + *
    1.30 + * In 1-pass quantization the colormap must be chosen in advance of seeing the
    1.31 + * image.  We use a map consisting of all combinations of Ncolors[i] color
    1.32 + * values for the i'th component.  The Ncolors[] values are chosen so that
    1.33 + * their product, the total number of colors, is no more than that requested.
    1.34 + * (In most cases, the product will be somewhat less.)
    1.35 + *
    1.36 + * Since the colormap is orthogonal, the representative value for each color
    1.37 + * component can be determined without considering the other components;
    1.38 + * then these indexes can be combined into a colormap index by a standard
    1.39 + * N-dimensional-array-subscript calculation.  Most of the arithmetic involved
    1.40 + * can be precalculated and stored in the lookup table colorindex[].
    1.41 + * colorindex[i][j] maps pixel value j in component i to the nearest
    1.42 + * representative value (grid plane) for that component; this index is
    1.43 + * multiplied by the array stride for component i, so that the
    1.44 + * index of the colormap entry closest to a given pixel value is just
    1.45 + *    sum( colorindex[component-number][pixel-component-value] )
    1.46 + * Aside from being fast, this scheme allows for variable spacing between
    1.47 + * representative values with no additional lookup cost.
    1.48 + *
    1.49 + * If gamma correction has been applied in color conversion, it might be wise
    1.50 + * to adjust the color grid spacing so that the representative colors are
    1.51 + * equidistant in linear space.  At this writing, gamma correction is not
    1.52 + * implemented by jdcolor, so nothing is done here.
    1.53 + */
    1.54 +
    1.55 +
    1.56 +/* Declarations for ordered dithering.
    1.57 + *
    1.58 + * We use a standard 16x16 ordered dither array.  The basic concept of ordered
    1.59 + * dithering is described in many references, for instance Dale Schumacher's
    1.60 + * chapter II.2 of Graphics Gems II (James Arvo, ed. Academic Press, 1991).
    1.61 + * In place of Schumacher's comparisons against a "threshold" value, we add a
    1.62 + * "dither" value to the input pixel and then round the result to the nearest
    1.63 + * output value.  The dither value is equivalent to (0.5 - threshold) times
    1.64 + * the distance between output values.  For ordered dithering, we assume that
    1.65 + * the output colors are equally spaced; if not, results will probably be
    1.66 + * worse, since the dither may be too much or too little at a given point.
    1.67 + *
    1.68 + * The normal calculation would be to form pixel value + dither, range-limit
    1.69 + * this to 0..MAXJSAMPLE, and then index into the colorindex table as usual.
    1.70 + * We can skip the separate range-limiting step by extending the colorindex
    1.71 + * table in both directions.
    1.72 + */
    1.73 +
    1.74 +#define ODITHER_SIZE  16	/* dimension of dither matrix */
    1.75 +/* NB: if ODITHER_SIZE is not a power of 2, ODITHER_MASK uses will break */
    1.76 +#define ODITHER_CELLS (ODITHER_SIZE*ODITHER_SIZE)	/* # cells in matrix */
    1.77 +#define ODITHER_MASK  (ODITHER_SIZE-1) /* mask for wrapping around counters */
    1.78 +
    1.79 +typedef int ODITHER_MATRIX[ODITHER_SIZE][ODITHER_SIZE];
    1.80 +typedef int (*ODITHER_MATRIX_PTR)[ODITHER_SIZE];
    1.81 +
    1.82 +static const UINT8 base_dither_matrix[ODITHER_SIZE][ODITHER_SIZE] = {
    1.83 +  /* Bayer's order-4 dither array.  Generated by the code given in
    1.84 +   * Stephen Hawley's article "Ordered Dithering" in Graphics Gems I.
    1.85 +   * The values in this array must range from 0 to ODITHER_CELLS-1.
    1.86 +   */
    1.87 +  {   0,192, 48,240, 12,204, 60,252,  3,195, 51,243, 15,207, 63,255 },
    1.88 +  { 128, 64,176,112,140, 76,188,124,131, 67,179,115,143, 79,191,127 },
    1.89 +  {  32,224, 16,208, 44,236, 28,220, 35,227, 19,211, 47,239, 31,223 },
    1.90 +  { 160, 96,144, 80,172,108,156, 92,163, 99,147, 83,175,111,159, 95 },
    1.91 +  {   8,200, 56,248,  4,196, 52,244, 11,203, 59,251,  7,199, 55,247 },
    1.92 +  { 136, 72,184,120,132, 68,180,116,139, 75,187,123,135, 71,183,119 },
    1.93 +  {  40,232, 24,216, 36,228, 20,212, 43,235, 27,219, 39,231, 23,215 },
    1.94 +  { 168,104,152, 88,164,100,148, 84,171,107,155, 91,167,103,151, 87 },
    1.95 +  {   2,194, 50,242, 14,206, 62,254,  1,193, 49,241, 13,205, 61,253 },
    1.96 +  { 130, 66,178,114,142, 78,190,126,129, 65,177,113,141, 77,189,125 },
    1.97 +  {  34,226, 18,210, 46,238, 30,222, 33,225, 17,209, 45,237, 29,221 },
    1.98 +  { 162, 98,146, 82,174,110,158, 94,161, 97,145, 81,173,109,157, 93 },
    1.99 +  {  10,202, 58,250,  6,198, 54,246,  9,201, 57,249,  5,197, 53,245 },
   1.100 +  { 138, 74,186,122,134, 70,182,118,137, 73,185,121,133, 69,181,117 },
   1.101 +  {  42,234, 26,218, 38,230, 22,214, 41,233, 25,217, 37,229, 21,213 },
   1.102 +  { 170,106,154, 90,166,102,150, 86,169,105,153, 89,165,101,149, 85 }
   1.103 +};
   1.104 +
   1.105 +
   1.106 +/* Declarations for Floyd-Steinberg dithering.
   1.107 + *
   1.108 + * Errors are accumulated into the array fserrors[], at a resolution of
   1.109 + * 1/16th of a pixel count.  The error at a given pixel is propagated
   1.110 + * to its not-yet-processed neighbors using the standard F-S fractions,
   1.111 + *		...	(here)	7/16
   1.112 + *		3/16	5/16	1/16
   1.113 + * We work left-to-right on even rows, right-to-left on odd rows.
   1.114 + *
   1.115 + * We can get away with a single array (holding one row's worth of errors)
   1.116 + * by using it to store the current row's errors at pixel columns not yet
   1.117 + * processed, but the next row's errors at columns already processed.  We
   1.118 + * need only a few extra variables to hold the errors immediately around the
   1.119 + * current column.  (If we are lucky, those variables are in registers, but
   1.120 + * even if not, they're probably cheaper to access than array elements are.)
   1.121 + *
   1.122 + * The fserrors[] array is indexed [component#][position].
   1.123 + * We provide (#columns + 2) entries per component; the extra entry at each
   1.124 + * end saves us from special-casing the first and last pixels.
   1.125 + *
   1.126 + * Note: on a wide image, we might not have enough room in a PC's near data
   1.127 + * segment to hold the error array; so it is allocated with alloc_large.
   1.128 + */
   1.129 +
   1.130 +#if BITS_IN_JSAMPLE == 8
   1.131 +typedef INT16 FSERROR;		/* 16 bits should be enough */
   1.132 +typedef int LOCFSERROR;		/* use 'int' for calculation temps */
   1.133 +#else
   1.134 +typedef INT32 FSERROR;		/* may need more than 16 bits */
   1.135 +typedef INT32 LOCFSERROR;	/* be sure calculation temps are big enough */
   1.136 +#endif
   1.137 +
   1.138 +typedef FSERROR FAR *FSERRPTR;	/* pointer to error array (in FAR storage!) */
   1.139 +
   1.140 +
   1.141 +/* Private subobject */
   1.142 +
   1.143 +#define MAX_Q_COMPS 4		/* max components I can handle */
   1.144 +
   1.145 +typedef struct {
   1.146 +  struct jpeg_color_quantizer pub; /* public fields */
   1.147 +
   1.148 +  /* Initially allocated colormap is saved here */
   1.149 +  JSAMPARRAY sv_colormap;	/* The color map as a 2-D pixel array */
   1.150 +  int sv_actual;		/* number of entries in use */
   1.151 +
   1.152 +  JSAMPARRAY colorindex;	/* Precomputed mapping for speed */
   1.153 +  /* colorindex[i][j] = index of color closest to pixel value j in component i,
   1.154 +   * premultiplied as described above.  Since colormap indexes must fit into
   1.155 +   * JSAMPLEs, the entries of this array will too.
   1.156 +   */
   1.157 +  boolean is_padded;		/* is the colorindex padded for odither? */
   1.158 +
   1.159 +  int Ncolors[MAX_Q_COMPS];	/* # of values alloced to each component */
   1.160 +
   1.161 +  /* Variables for ordered dithering */
   1.162 +  int row_index;		/* cur row's vertical index in dither matrix */
   1.163 +  ODITHER_MATRIX_PTR odither[MAX_Q_COMPS]; /* one dither array per component */
   1.164 +
   1.165 +  /* Variables for Floyd-Steinberg dithering */
   1.166 +  FSERRPTR fserrors[MAX_Q_COMPS]; /* accumulated errors */
   1.167 +  boolean on_odd_row;		/* flag to remember which row we are on */
   1.168 +} my_cquantizer;
   1.169 +
   1.170 +typedef my_cquantizer * my_cquantize_ptr;
   1.171 +
   1.172 +
   1.173 +/*
   1.174 + * Policy-making subroutines for create_colormap and create_colorindex.
   1.175 + * These routines determine the colormap to be used.  The rest of the module
   1.176 + * only assumes that the colormap is orthogonal.
   1.177 + *
   1.178 + *  * select_ncolors decides how to divvy up the available colors
   1.179 + *    among the components.
   1.180 + *  * output_value defines the set of representative values for a component.
   1.181 + *  * largest_input_value defines the mapping from input values to
   1.182 + *    representative values for a component.
   1.183 + * Note that the latter two routines may impose different policies for
   1.184 + * different components, though this is not currently done.
   1.185 + */
   1.186 +
   1.187 +
   1.188 +LOCAL(int)
   1.189 +select_ncolors (j_decompress_ptr cinfo, int Ncolors[])
   1.190 +/* Determine allocation of desired colors to components, */
   1.191 +/* and fill in Ncolors[] array to indicate choice. */
   1.192 +/* Return value is total number of colors (product of Ncolors[] values). */
   1.193 +{
   1.194 +  int nc = cinfo->out_color_components; /* number of color components */
   1.195 +  int max_colors = cinfo->desired_number_of_colors;
   1.196 +  int total_colors, iroot, i, j;
   1.197 +  boolean changed;
   1.198 +  long temp;
   1.199 +  static const int RGB_order[3] = { RGB_GREEN, RGB_RED, RGB_BLUE };
   1.200 +
   1.201 +  /* We can allocate at least the nc'th root of max_colors per component. */
   1.202 +  /* Compute floor(nc'th root of max_colors). */
   1.203 +  iroot = 1;
   1.204 +  do {
   1.205 +    iroot++;
   1.206 +    temp = iroot;		/* set temp = iroot ** nc */
   1.207 +    for (i = 1; i < nc; i++)
   1.208 +      temp *= iroot;
   1.209 +  } while (temp <= (long) max_colors); /* repeat till iroot exceeds root */
   1.210 +  iroot--;			/* now iroot = floor(root) */
   1.211 +
   1.212 +  /* Must have at least 2 color values per component */
   1.213 +  if (iroot < 2)
   1.214 +    ERREXIT1(cinfo, JERR_QUANT_FEW_COLORS, (int) temp);
   1.215 +
   1.216 +  /* Initialize to iroot color values for each component */
   1.217 +  total_colors = 1;
   1.218 +  for (i = 0; i < nc; i++) {
   1.219 +    Ncolors[i] = iroot;
   1.220 +    total_colors *= iroot;
   1.221 +  }
   1.222 +  /* We may be able to increment the count for one or more components without
   1.223 +   * exceeding max_colors, though we know not all can be incremented.
   1.224 +   * Sometimes, the first component can be incremented more than once!
   1.225 +   * (Example: for 16 colors, we start at 2*2*2, go to 3*2*2, then 4*2*2.)
   1.226 +   * In RGB colorspace, try to increment G first, then R, then B.
   1.227 +   */
   1.228 +  do {
   1.229 +    changed = FALSE;
   1.230 +    for (i = 0; i < nc; i++) {
   1.231 +      j = (cinfo->out_color_space == JCS_RGB ? RGB_order[i] : i);
   1.232 +      /* calculate new total_colors if Ncolors[j] is incremented */
   1.233 +      temp = total_colors / Ncolors[j];
   1.234 +      temp *= Ncolors[j]+1;	/* done in long arith to avoid oflo */
   1.235 +      if (temp > (long) max_colors)
   1.236 +	break;			/* won't fit, done with this pass */
   1.237 +      Ncolors[j]++;		/* OK, apply the increment */
   1.238 +      total_colors = (int) temp;
   1.239 +      changed = TRUE;
   1.240 +    }
   1.241 +  } while (changed);
   1.242 +
   1.243 +  return total_colors;
   1.244 +}
   1.245 +
   1.246 +
   1.247 +LOCAL(int)
   1.248 +output_value (j_decompress_ptr cinfo, int ci, int j, int maxj)
   1.249 +/* Return j'th output value, where j will range from 0 to maxj */
   1.250 +/* The output values must fall in 0..MAXJSAMPLE in increasing order */
   1.251 +{
   1.252 +  /* We always provide values 0 and MAXJSAMPLE for each component;
   1.253 +   * any additional values are equally spaced between these limits.
   1.254 +   * (Forcing the upper and lower values to the limits ensures that
   1.255 +   * dithering can't produce a color outside the selected gamut.)
   1.256 +   */
   1.257 +  return (int) (((INT32) j * MAXJSAMPLE + maxj/2) / maxj);
   1.258 +}
   1.259 +
   1.260 +
   1.261 +LOCAL(int)
   1.262 +largest_input_value (j_decompress_ptr cinfo, int ci, int j, int maxj)
   1.263 +/* Return largest input value that should map to j'th output value */
   1.264 +/* Must have largest(j=0) >= 0, and largest(j=maxj) >= MAXJSAMPLE */
   1.265 +{
   1.266 +  /* Breakpoints are halfway between values returned by output_value */
   1.267 +  return (int) (((INT32) (2*j + 1) * MAXJSAMPLE + maxj) / (2*maxj));
   1.268 +}
   1.269 +
   1.270 +
   1.271 +/*
   1.272 + * Create the colormap.
   1.273 + */
   1.274 +
   1.275 +LOCAL(void)
   1.276 +create_colormap (j_decompress_ptr cinfo)
   1.277 +{
   1.278 +  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
   1.279 +  JSAMPARRAY colormap;		/* Created colormap */
   1.280 +  int total_colors;		/* Number of distinct output colors */
   1.281 +  int i,j,k, nci, blksize, blkdist, ptr, val;
   1.282 +
   1.283 +  /* Select number of colors for each component */
   1.284 +  total_colors = select_ncolors(cinfo, cquantize->Ncolors);
   1.285 +
   1.286 +  /* Report selected color counts */
   1.287 +  if (cinfo->out_color_components == 3)
   1.288 +    TRACEMS4(cinfo, 1, JTRC_QUANT_3_NCOLORS,
   1.289 +	     total_colors, cquantize->Ncolors[0],
   1.290 +	     cquantize->Ncolors[1], cquantize->Ncolors[2]);
   1.291 +  else
   1.292 +    TRACEMS1(cinfo, 1, JTRC_QUANT_NCOLORS, total_colors);
   1.293 +
   1.294 +  /* Allocate and fill in the colormap. */
   1.295 +  /* The colors are ordered in the map in standard row-major order, */
   1.296 +  /* i.e. rightmost (highest-indexed) color changes most rapidly. */
   1.297 +
   1.298 +  colormap = (*cinfo->mem->alloc_sarray)
   1.299 +    ((j_common_ptr) cinfo, JPOOL_IMAGE,
   1.300 +     (JDIMENSION) total_colors, (JDIMENSION) cinfo->out_color_components);
   1.301 +
   1.302 +  /* blksize is number of adjacent repeated entries for a component */
   1.303 +  /* blkdist is distance between groups of identical entries for a component */
   1.304 +  blkdist = total_colors;
   1.305 +
   1.306 +  for (i = 0; i < cinfo->out_color_components; i++) {
   1.307 +    /* fill in colormap entries for i'th color component */
   1.308 +    nci = cquantize->Ncolors[i]; /* # of distinct values for this color */
   1.309 +    blksize = blkdist / nci;
   1.310 +    for (j = 0; j < nci; j++) {
   1.311 +      /* Compute j'th output value (out of nci) for component */
   1.312 +      val = output_value(cinfo, i, j, nci-1);
   1.313 +      /* Fill in all colormap entries that have this value of this component */
   1.314 +      for (ptr = j * blksize; ptr < total_colors; ptr += blkdist) {
   1.315 +	/* fill in blksize entries beginning at ptr */
   1.316 +	for (k = 0; k < blksize; k++)
   1.317 +	  colormap[i][ptr+k] = (JSAMPLE) val;
   1.318 +      }
   1.319 +    }
   1.320 +    blkdist = blksize;		/* blksize of this color is blkdist of next */
   1.321 +  }
   1.322 +
   1.323 +  /* Save the colormap in private storage,
   1.324 +   * where it will survive color quantization mode changes.
   1.325 +   */
   1.326 +  cquantize->sv_colormap = colormap;
   1.327 +  cquantize->sv_actual = total_colors;
   1.328 +}
   1.329 +
   1.330 +
   1.331 +/*
   1.332 + * Create the color index table.
   1.333 + */
   1.334 +
   1.335 +LOCAL(void)
   1.336 +create_colorindex (j_decompress_ptr cinfo)
   1.337 +{
   1.338 +  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
   1.339 +  JSAMPROW indexptr;
   1.340 +  int i,j,k, nci, blksize, val, pad;
   1.341 +
   1.342 +  /* For ordered dither, we pad the color index tables by MAXJSAMPLE in
   1.343 +   * each direction (input index values can be -MAXJSAMPLE .. 2*MAXJSAMPLE).
   1.344 +   * This is not necessary in the other dithering modes.  However, we
   1.345 +   * flag whether it was done in case user changes dithering mode.
   1.346 +   */
   1.347 +  if (cinfo->dither_mode == JDITHER_ORDERED) {
   1.348 +    pad = MAXJSAMPLE*2;
   1.349 +    cquantize->is_padded = TRUE;
   1.350 +  } else {
   1.351 +    pad = 0;
   1.352 +    cquantize->is_padded = FALSE;
   1.353 +  }
   1.354 +
   1.355 +  cquantize->colorindex = (*cinfo->mem->alloc_sarray)
   1.356 +    ((j_common_ptr) cinfo, JPOOL_IMAGE,
   1.357 +     (JDIMENSION) (MAXJSAMPLE+1 + pad),
   1.358 +     (JDIMENSION) cinfo->out_color_components);
   1.359 +
   1.360 +  /* blksize is number of adjacent repeated entries for a component */
   1.361 +  blksize = cquantize->sv_actual;
   1.362 +
   1.363 +  for (i = 0; i < cinfo->out_color_components; i++) {
   1.364 +    /* fill in colorindex entries for i'th color component */
   1.365 +    nci = cquantize->Ncolors[i]; /* # of distinct values for this color */
   1.366 +    blksize = blksize / nci;
   1.367 +
   1.368 +    /* adjust colorindex pointers to provide padding at negative indexes. */
   1.369 +    if (pad)
   1.370 +      cquantize->colorindex[i] += MAXJSAMPLE;
   1.371 +
   1.372 +    /* in loop, val = index of current output value, */
   1.373 +    /* and k = largest j that maps to current val */
   1.374 +    indexptr = cquantize->colorindex[i];
   1.375 +    val = 0;
   1.376 +    k = largest_input_value(cinfo, i, 0, nci-1);
   1.377 +    for (j = 0; j <= MAXJSAMPLE; j++) {
   1.378 +      while (j > k)		/* advance val if past boundary */
   1.379 +	k = largest_input_value(cinfo, i, ++val, nci-1);
   1.380 +      /* premultiply so that no multiplication needed in main processing */
   1.381 +      indexptr[j] = (JSAMPLE) (val * blksize);
   1.382 +    }
   1.383 +    /* Pad at both ends if necessary */
   1.384 +    if (pad)
   1.385 +      for (j = 1; j <= MAXJSAMPLE; j++) {
   1.386 +	indexptr[-j] = indexptr[0];
   1.387 +	indexptr[MAXJSAMPLE+j] = indexptr[MAXJSAMPLE];
   1.388 +      }
   1.389 +  }
   1.390 +}
   1.391 +
   1.392 +
   1.393 +/*
   1.394 + * Create an ordered-dither array for a component having ncolors
   1.395 + * distinct output values.
   1.396 + */
   1.397 +
   1.398 +LOCAL(ODITHER_MATRIX_PTR)
   1.399 +make_odither_array (j_decompress_ptr cinfo, int ncolors)
   1.400 +{
   1.401 +  ODITHER_MATRIX_PTR odither;
   1.402 +  int j,k;
   1.403 +  INT32 num,den;
   1.404 +
   1.405 +  odither = (ODITHER_MATRIX_PTR)
   1.406 +    (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
   1.407 +				SIZEOF(ODITHER_MATRIX));
   1.408 +  /* The inter-value distance for this color is MAXJSAMPLE/(ncolors-1).
   1.409 +   * Hence the dither value for the matrix cell with fill order f
   1.410 +   * (f=0..N-1) should be (N-1-2*f)/(2*N) * MAXJSAMPLE/(ncolors-1).
   1.411 +   * On 16-bit-int machine, be careful to avoid overflow.
   1.412 +   */
   1.413 +  den = 2 * ODITHER_CELLS * ((INT32) (ncolors - 1));
   1.414 +  for (j = 0; j < ODITHER_SIZE; j++) {
   1.415 +    for (k = 0; k < ODITHER_SIZE; k++) {
   1.416 +      num = ((INT32) (ODITHER_CELLS-1 - 2*((int)base_dither_matrix[j][k])))
   1.417 +	    * MAXJSAMPLE;
   1.418 +      /* Ensure round towards zero despite C's lack of consistency
   1.419 +       * about rounding negative values in integer division...
   1.420 +       */
   1.421 +      odither[j][k] = (int) (num<0 ? -((-num)/den) : num/den);
   1.422 +    }
   1.423 +  }
   1.424 +  return odither;
   1.425 +}
   1.426 +
   1.427 +
   1.428 +/*
   1.429 + * Create the ordered-dither tables.
   1.430 + * Components having the same number of representative colors may 
   1.431 + * share a dither table.
   1.432 + */
   1.433 +
   1.434 +LOCAL(void)
   1.435 +create_odither_tables (j_decompress_ptr cinfo)
   1.436 +{
   1.437 +  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
   1.438 +  ODITHER_MATRIX_PTR odither;
   1.439 +  int i, j, nci;
   1.440 +
   1.441 +  for (i = 0; i < cinfo->out_color_components; i++) {
   1.442 +    nci = cquantize->Ncolors[i]; /* # of distinct values for this color */
   1.443 +    odither = NULL;		/* search for matching prior component */
   1.444 +    for (j = 0; j < i; j++) {
   1.445 +      if (nci == cquantize->Ncolors[j]) {
   1.446 +	odither = cquantize->odither[j];
   1.447 +	break;
   1.448 +      }
   1.449 +    }
   1.450 +    if (odither == NULL)	/* need a new table? */
   1.451 +      odither = make_odither_array(cinfo, nci);
   1.452 +    cquantize->odither[i] = odither;
   1.453 +  }
   1.454 +}
   1.455 +
   1.456 +
   1.457 +/*
   1.458 + * Map some rows of pixels to the output colormapped representation.
   1.459 + */
   1.460 +
   1.461 +METHODDEF(void)
   1.462 +color_quantize (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
   1.463 +		JSAMPARRAY output_buf, int num_rows)
   1.464 +/* General case, no dithering */
   1.465 +{
   1.466 +  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
   1.467 +  JSAMPARRAY colorindex = cquantize->colorindex;
   1.468 +  register int pixcode, ci;
   1.469 +  register JSAMPROW ptrin, ptrout;
   1.470 +  int row;
   1.471 +  JDIMENSION col;
   1.472 +  JDIMENSION width = cinfo->output_width;
   1.473 +  register int nc = cinfo->out_color_components;
   1.474 +
   1.475 +  for (row = 0; row < num_rows; row++) {
   1.476 +    ptrin = input_buf[row];
   1.477 +    ptrout = output_buf[row];
   1.478 +    for (col = width; col > 0; col--) {
   1.479 +      pixcode = 0;
   1.480 +      for (ci = 0; ci < nc; ci++) {
   1.481 +	pixcode += GETJSAMPLE(colorindex[ci][GETJSAMPLE(*ptrin++)]);
   1.482 +      }
   1.483 +      *ptrout++ = (JSAMPLE) pixcode;
   1.484 +    }
   1.485 +  }
   1.486 +}
   1.487 +
   1.488 +
   1.489 +METHODDEF(void)
   1.490 +color_quantize3 (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
   1.491 +		 JSAMPARRAY output_buf, int num_rows)
   1.492 +/* Fast path for out_color_components==3, no dithering */
   1.493 +{
   1.494 +  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
   1.495 +  register int pixcode;
   1.496 +  register JSAMPROW ptrin, ptrout;
   1.497 +  JSAMPROW colorindex0 = cquantize->colorindex[0];
   1.498 +  JSAMPROW colorindex1 = cquantize->colorindex[1];
   1.499 +  JSAMPROW colorindex2 = cquantize->colorindex[2];
   1.500 +  int row;
   1.501 +  JDIMENSION col;
   1.502 +  JDIMENSION width = cinfo->output_width;
   1.503 +
   1.504 +  for (row = 0; row < num_rows; row++) {
   1.505 +    ptrin = input_buf[row];
   1.506 +    ptrout = output_buf[row];
   1.507 +    for (col = width; col > 0; col--) {
   1.508 +      pixcode  = GETJSAMPLE(colorindex0[GETJSAMPLE(*ptrin++)]);
   1.509 +      pixcode += GETJSAMPLE(colorindex1[GETJSAMPLE(*ptrin++)]);
   1.510 +      pixcode += GETJSAMPLE(colorindex2[GETJSAMPLE(*ptrin++)]);
   1.511 +      *ptrout++ = (JSAMPLE) pixcode;
   1.512 +    }
   1.513 +  }
   1.514 +}
   1.515 +
   1.516 +
   1.517 +METHODDEF(void)
   1.518 +quantize_ord_dither (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
   1.519 +		     JSAMPARRAY output_buf, int num_rows)
   1.520 +/* General case, with ordered dithering */
   1.521 +{
   1.522 +  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
   1.523 +  register JSAMPROW input_ptr;
   1.524 +  register JSAMPROW output_ptr;
   1.525 +  JSAMPROW colorindex_ci;
   1.526 +  int * dither;			/* points to active row of dither matrix */
   1.527 +  int row_index, col_index;	/* current indexes into dither matrix */
   1.528 +  int nc = cinfo->out_color_components;
   1.529 +  int ci;
   1.530 +  int row;
   1.531 +  JDIMENSION col;
   1.532 +  JDIMENSION width = cinfo->output_width;
   1.533 +
   1.534 +  for (row = 0; row < num_rows; row++) {
   1.535 +    /* Initialize output values to 0 so can process components separately */
   1.536 +    jzero_far((void FAR *) output_buf[row],
   1.537 +	      (size_t) (width * SIZEOF(JSAMPLE)));
   1.538 +    row_index = cquantize->row_index;
   1.539 +    for (ci = 0; ci < nc; ci++) {
   1.540 +      input_ptr = input_buf[row] + ci;
   1.541 +      output_ptr = output_buf[row];
   1.542 +      colorindex_ci = cquantize->colorindex[ci];
   1.543 +      dither = cquantize->odither[ci][row_index];
   1.544 +      col_index = 0;
   1.545 +
   1.546 +      for (col = width; col > 0; col--) {
   1.547 +	/* Form pixel value + dither, range-limit to 0..MAXJSAMPLE,
   1.548 +	 * select output value, accumulate into output code for this pixel.
   1.549 +	 * Range-limiting need not be done explicitly, as we have extended
   1.550 +	 * the colorindex table to produce the right answers for out-of-range
   1.551 +	 * inputs.  The maximum dither is +- MAXJSAMPLE; this sets the
   1.552 +	 * required amount of padding.
   1.553 +	 */
   1.554 +	*output_ptr += colorindex_ci[GETJSAMPLE(*input_ptr)+dither[col_index]];
   1.555 +	input_ptr += nc;
   1.556 +	output_ptr++;
   1.557 +	col_index = (col_index + 1) & ODITHER_MASK;
   1.558 +      }
   1.559 +    }
   1.560 +    /* Advance row index for next row */
   1.561 +    row_index = (row_index + 1) & ODITHER_MASK;
   1.562 +    cquantize->row_index = row_index;
   1.563 +  }
   1.564 +}
   1.565 +
   1.566 +
   1.567 +METHODDEF(void)
   1.568 +quantize3_ord_dither (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
   1.569 +		      JSAMPARRAY output_buf, int num_rows)
   1.570 +/* Fast path for out_color_components==3, with ordered dithering */
   1.571 +{
   1.572 +  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
   1.573 +  register int pixcode;
   1.574 +  register JSAMPROW input_ptr;
   1.575 +  register JSAMPROW output_ptr;
   1.576 +  JSAMPROW colorindex0 = cquantize->colorindex[0];
   1.577 +  JSAMPROW colorindex1 = cquantize->colorindex[1];
   1.578 +  JSAMPROW colorindex2 = cquantize->colorindex[2];
   1.579 +  int * dither0;		/* points to active row of dither matrix */
   1.580 +  int * dither1;
   1.581 +  int * dither2;
   1.582 +  int row_index, col_index;	/* current indexes into dither matrix */
   1.583 +  int row;
   1.584 +  JDIMENSION col;
   1.585 +  JDIMENSION width = cinfo->output_width;
   1.586 +
   1.587 +  for (row = 0; row < num_rows; row++) {
   1.588 +    row_index = cquantize->row_index;
   1.589 +    input_ptr = input_buf[row];
   1.590 +    output_ptr = output_buf[row];
   1.591 +    dither0 = cquantize->odither[0][row_index];
   1.592 +    dither1 = cquantize->odither[1][row_index];
   1.593 +    dither2 = cquantize->odither[2][row_index];
   1.594 +    col_index = 0;
   1.595 +
   1.596 +    for (col = width; col > 0; col--) {
   1.597 +      pixcode  = GETJSAMPLE(colorindex0[GETJSAMPLE(*input_ptr++) +
   1.598 +					dither0[col_index]]);
   1.599 +      pixcode += GETJSAMPLE(colorindex1[GETJSAMPLE(*input_ptr++) +
   1.600 +					dither1[col_index]]);
   1.601 +      pixcode += GETJSAMPLE(colorindex2[GETJSAMPLE(*input_ptr++) +
   1.602 +					dither2[col_index]]);
   1.603 +      *output_ptr++ = (JSAMPLE) pixcode;
   1.604 +      col_index = (col_index + 1) & ODITHER_MASK;
   1.605 +    }
   1.606 +    row_index = (row_index + 1) & ODITHER_MASK;
   1.607 +    cquantize->row_index = row_index;
   1.608 +  }
   1.609 +}
   1.610 +
   1.611 +
   1.612 +METHODDEF(void)
   1.613 +quantize_fs_dither (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
   1.614 +		    JSAMPARRAY output_buf, int num_rows)
   1.615 +/* General case, with Floyd-Steinberg dithering */
   1.616 +{
   1.617 +  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
   1.618 +  register LOCFSERROR cur;	/* current error or pixel value */
   1.619 +  LOCFSERROR belowerr;		/* error for pixel below cur */
   1.620 +  LOCFSERROR bpreverr;		/* error for below/prev col */
   1.621 +  LOCFSERROR bnexterr;		/* error for below/next col */
   1.622 +  LOCFSERROR delta;
   1.623 +  register FSERRPTR errorptr;	/* => fserrors[] at column before current */
   1.624 +  register JSAMPROW input_ptr;
   1.625 +  register JSAMPROW output_ptr;
   1.626 +  JSAMPROW colorindex_ci;
   1.627 +  JSAMPROW colormap_ci;
   1.628 +  int pixcode;
   1.629 +  int nc = cinfo->out_color_components;
   1.630 +  int dir;			/* 1 for left-to-right, -1 for right-to-left */
   1.631 +  int dirnc;			/* dir * nc */
   1.632 +  int ci;
   1.633 +  int row;
   1.634 +  JDIMENSION col;
   1.635 +  JDIMENSION width = cinfo->output_width;
   1.636 +  JSAMPLE *range_limit = cinfo->sample_range_limit;
   1.637 +  SHIFT_TEMPS
   1.638 +
   1.639 +  for (row = 0; row < num_rows; row++) {
   1.640 +    /* Initialize output values to 0 so can process components separately */
   1.641 +    jzero_far((void FAR *) output_buf[row],
   1.642 +	      (size_t) (width * SIZEOF(JSAMPLE)));
   1.643 +    for (ci = 0; ci < nc; ci++) {
   1.644 +      input_ptr = input_buf[row] + ci;
   1.645 +      output_ptr = output_buf[row];
   1.646 +      if (cquantize->on_odd_row) {
   1.647 +	/* work right to left in this row */
   1.648 +	input_ptr += (width-1) * nc; /* so point to rightmost pixel */
   1.649 +	output_ptr += width-1;
   1.650 +	dir = -1;
   1.651 +	dirnc = -nc;
   1.652 +	errorptr = cquantize->fserrors[ci] + (width+1); /* => entry after last column */
   1.653 +      } else {
   1.654 +	/* work left to right in this row */
   1.655 +	dir = 1;
   1.656 +	dirnc = nc;
   1.657 +	errorptr = cquantize->fserrors[ci]; /* => entry before first column */
   1.658 +      }
   1.659 +      colorindex_ci = cquantize->colorindex[ci];
   1.660 +      colormap_ci = cquantize->sv_colormap[ci];
   1.661 +      /* Preset error values: no error propagated to first pixel from left */
   1.662 +      cur = 0;
   1.663 +      /* and no error propagated to row below yet */
   1.664 +      belowerr = bpreverr = 0;
   1.665 +
   1.666 +      for (col = width; col > 0; col--) {
   1.667 +	/* cur holds the error propagated from the previous pixel on the
   1.668 +	 * current line.  Add the error propagated from the previous line
   1.669 +	 * to form the complete error correction term for this pixel, and
   1.670 +	 * round the error term (which is expressed * 16) to an integer.
   1.671 +	 * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct
   1.672 +	 * for either sign of the error value.
   1.673 +	 * Note: errorptr points to *previous* column's array entry.
   1.674 +	 */
   1.675 +	cur = RIGHT_SHIFT(cur + errorptr[dir] + 8, 4);
   1.676 +	/* Form pixel value + error, and range-limit to 0..MAXJSAMPLE.
   1.677 +	 * The maximum error is +- MAXJSAMPLE; this sets the required size
   1.678 +	 * of the range_limit array.
   1.679 +	 */
   1.680 +	cur += GETJSAMPLE(*input_ptr);
   1.681 +	cur = GETJSAMPLE(range_limit[cur]);
   1.682 +	/* Select output value, accumulate into output code for this pixel */
   1.683 +	pixcode = GETJSAMPLE(colorindex_ci[cur]);
   1.684 +	*output_ptr += (JSAMPLE) pixcode;
   1.685 +	/* Compute actual representation error at this pixel */
   1.686 +	/* Note: we can do this even though we don't have the final */
   1.687 +	/* pixel code, because the colormap is orthogonal. */
   1.688 +	cur -= GETJSAMPLE(colormap_ci[pixcode]);
   1.689 +	/* Compute error fractions to be propagated to adjacent pixels.
   1.690 +	 * Add these into the running sums, and simultaneously shift the
   1.691 +	 * next-line error sums left by 1 column.
   1.692 +	 */
   1.693 +	bnexterr = cur;
   1.694 +	delta = cur * 2;
   1.695 +	cur += delta;		/* form error * 3 */
   1.696 +	errorptr[0] = (FSERROR) (bpreverr + cur);
   1.697 +	cur += delta;		/* form error * 5 */
   1.698 +	bpreverr = belowerr + cur;
   1.699 +	belowerr = bnexterr;
   1.700 +	cur += delta;		/* form error * 7 */
   1.701 +	/* At this point cur contains the 7/16 error value to be propagated
   1.702 +	 * to the next pixel on the current line, and all the errors for the
   1.703 +	 * next line have been shifted over. We are therefore ready to move on.
   1.704 +	 */
   1.705 +	input_ptr += dirnc;	/* advance input ptr to next column */
   1.706 +	output_ptr += dir;	/* advance output ptr to next column */
   1.707 +	errorptr += dir;	/* advance errorptr to current column */
   1.708 +      }
   1.709 +      /* Post-loop cleanup: we must unload the final error value into the
   1.710 +       * final fserrors[] entry.  Note we need not unload belowerr because
   1.711 +       * it is for the dummy column before or after the actual array.
   1.712 +       */
   1.713 +      errorptr[0] = (FSERROR) bpreverr; /* unload prev err into array */
   1.714 +    }
   1.715 +    cquantize->on_odd_row = (cquantize->on_odd_row ? FALSE : TRUE);
   1.716 +  }
   1.717 +}
   1.718 +
   1.719 +
   1.720 +/*
   1.721 + * Allocate workspace for Floyd-Steinberg errors.
   1.722 + */
   1.723 +
   1.724 +LOCAL(void)
   1.725 +alloc_fs_workspace (j_decompress_ptr cinfo)
   1.726 +{
   1.727 +  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
   1.728 +  size_t arraysize;
   1.729 +  int i;
   1.730 +
   1.731 +  arraysize = (size_t) ((cinfo->output_width + 2) * SIZEOF(FSERROR));
   1.732 +  for (i = 0; i < cinfo->out_color_components; i++) {
   1.733 +    cquantize->fserrors[i] = (FSERRPTR)
   1.734 +      (*cinfo->mem->alloc_large)((j_common_ptr) cinfo, JPOOL_IMAGE, arraysize);
   1.735 +  }
   1.736 +}
   1.737 +
   1.738 +
   1.739 +/*
   1.740 + * Initialize for one-pass color quantization.
   1.741 + */
   1.742 +
   1.743 +METHODDEF(void)
   1.744 +start_pass_1_quant (j_decompress_ptr cinfo, boolean is_pre_scan)
   1.745 +{
   1.746 +  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
   1.747 +  size_t arraysize;
   1.748 +  int i;
   1.749 +
   1.750 +  /* Install my colormap. */
   1.751 +  cinfo->colormap = cquantize->sv_colormap;
   1.752 +  cinfo->actual_number_of_colors = cquantize->sv_actual;
   1.753 +
   1.754 +  /* Initialize for desired dithering mode. */
   1.755 +  switch (cinfo->dither_mode) {
   1.756 +  case JDITHER_NONE:
   1.757 +    if (cinfo->out_color_components == 3)
   1.758 +      cquantize->pub.color_quantize = color_quantize3;
   1.759 +    else
   1.760 +      cquantize->pub.color_quantize = color_quantize;
   1.761 +    break;
   1.762 +  case JDITHER_ORDERED:
   1.763 +    if (cinfo->out_color_components == 3)
   1.764 +      cquantize->pub.color_quantize = quantize3_ord_dither;
   1.765 +    else
   1.766 +      cquantize->pub.color_quantize = quantize_ord_dither;
   1.767 +    cquantize->row_index = 0;	/* initialize state for ordered dither */
   1.768 +    /* If user changed to ordered dither from another mode,
   1.769 +     * we must recreate the color index table with padding.
   1.770 +     * This will cost extra space, but probably isn't very likely.
   1.771 +     */
   1.772 +    if (! cquantize->is_padded)
   1.773 +      create_colorindex(cinfo);
   1.774 +    /* Create ordered-dither tables if we didn't already. */
   1.775 +    if (cquantize->odither[0] == NULL)
   1.776 +      create_odither_tables(cinfo);
   1.777 +    break;
   1.778 +  case JDITHER_FS:
   1.779 +    cquantize->pub.color_quantize = quantize_fs_dither;
   1.780 +    cquantize->on_odd_row = FALSE; /* initialize state for F-S dither */
   1.781 +    /* Allocate Floyd-Steinberg workspace if didn't already. */
   1.782 +    if (cquantize->fserrors[0] == NULL)
   1.783 +      alloc_fs_workspace(cinfo);
   1.784 +    /* Initialize the propagated errors to zero. */
   1.785 +    arraysize = (size_t) ((cinfo->output_width + 2) * SIZEOF(FSERROR));
   1.786 +    for (i = 0; i < cinfo->out_color_components; i++)
   1.787 +      jzero_far((void FAR *) cquantize->fserrors[i], arraysize);
   1.788 +    break;
   1.789 +  default:
   1.790 +    ERREXIT(cinfo, JERR_NOT_COMPILED);
   1.791 +    break;
   1.792 +  }
   1.793 +}
   1.794 +
   1.795 +
   1.796 +/*
   1.797 + * Finish up at the end of the pass.
   1.798 + */
   1.799 +
   1.800 +METHODDEF(void)
   1.801 +finish_pass_1_quant (j_decompress_ptr cinfo)
   1.802 +{
   1.803 +  /* no work in 1-pass case */
   1.804 +}
   1.805 +
   1.806 +
   1.807 +/*
   1.808 + * Switch to a new external colormap between output passes.
   1.809 + * Shouldn't get to this module!
   1.810 + */
   1.811 +
   1.812 +METHODDEF(void)
   1.813 +new_color_map_1_quant (j_decompress_ptr cinfo)
   1.814 +{
   1.815 +  ERREXIT(cinfo, JERR_MODE_CHANGE);
   1.816 +}
   1.817 +
   1.818 +
   1.819 +/*
   1.820 + * Module initialization routine for 1-pass color quantization.
   1.821 + */
   1.822 +
   1.823 +GLOBAL(void)
   1.824 +jinit_1pass_quantizer (j_decompress_ptr cinfo)
   1.825 +{
   1.826 +  my_cquantize_ptr cquantize;
   1.827 +
   1.828 +  cquantize = (my_cquantize_ptr)
   1.829 +    (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
   1.830 +				SIZEOF(my_cquantizer));
   1.831 +  cinfo->cquantize = (struct jpeg_color_quantizer *) cquantize;
   1.832 +  cquantize->pub.start_pass = start_pass_1_quant;
   1.833 +  cquantize->pub.finish_pass = finish_pass_1_quant;
   1.834 +  cquantize->pub.new_color_map = new_color_map_1_quant;
   1.835 +  cquantize->fserrors[0] = NULL; /* Flag FS workspace not allocated */
   1.836 +  cquantize->odither[0] = NULL;	/* Also flag odither arrays not allocated */
   1.837 +
   1.838 +  /* Make sure my internal arrays won't overflow */
   1.839 +  if (cinfo->out_color_components > MAX_Q_COMPS)
   1.840 +    ERREXIT1(cinfo, JERR_QUANT_COMPONENTS, MAX_Q_COMPS);
   1.841 +  /* Make sure colormap indexes can be represented by JSAMPLEs */
   1.842 +  if (cinfo->desired_number_of_colors > (MAXJSAMPLE+1))
   1.843 +    ERREXIT1(cinfo, JERR_QUANT_MANY_COLORS, MAXJSAMPLE+1);
   1.844 +
   1.845 +  /* Create the colormap and color index table. */
   1.846 +  create_colormap(cinfo);
   1.847 +  create_colorindex(cinfo);
   1.848 +
   1.849 +  /* Allocate Floyd-Steinberg workspace now if requested.
   1.850 +   * We do this now since it is FAR storage and may affect the memory
   1.851 +   * manager's space calculations.  If the user changes to FS dither
   1.852 +   * mode in a later pass, we will allocate the space then, and will
   1.853 +   * possibly overrun the max_memory_to_use setting.
   1.854 +   */
   1.855 +  if (cinfo->dither_mode == JDITHER_FS)
   1.856 +    alloc_fs_workspace(cinfo);
   1.857 +}
   1.858 +
   1.859 +#endif /* QUANT_1PASS_SUPPORTED */