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