"Fossies" - the Fresh Open Source Software Archive

Member "PDFlib-Lite-7.0.5p3/libs/jpeg/jquant1.c" (6 Jun 2012, 31395 Bytes) of package /linux/misc/old/PDFlib-Lite-7.0.5p3.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "jquant1.c" see the Fossies "Dox" file reference documentation.

    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   (void) cinfo;
  255   (void) ci;
  256 
  257   return (int) (((INT32) j * MAXJSAMPLE + maxj/2) / maxj);
  258 }
  259 
  260 
  261 LOCAL(int)
  262 largest_input_value (j_decompress_ptr cinfo, int ci, int j, int maxj)
  263 /* Return largest input value that should map to j'th output value */
  264 /* Must have largest(j=0) >= 0, and largest(j=maxj) >= MAXJSAMPLE */
  265 {
  266   (void) cinfo;
  267   (void) ci;
  268 
  269   /* Breakpoints are halfway between values returned by output_value */
  270   return (int) (((INT32) (2*j + 1) * MAXJSAMPLE + maxj) / (2*maxj));
  271 }
  272 
  273 
  274 /*
  275  * Create the colormap.
  276  */
  277 
  278 LOCAL(void)
  279 create_colormap (j_decompress_ptr cinfo)
  280 {
  281   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
  282   JSAMPARRAY colormap;      /* Created colormap */
  283   int total_colors;     /* Number of distinct output colors */
  284   int i,j,k, nci, blksize, blkdist, ptr, val;
  285 
  286   /* Select number of colors for each component */
  287   total_colors = select_ncolors(cinfo, cquantize->Ncolors);
  288 
  289   /* Report selected color counts */
  290   if (cinfo->out_color_components == 3)
  291     TRACEMS4(cinfo, 1, JTRC_QUANT_3_NCOLORS,
  292          total_colors, cquantize->Ncolors[0],
  293          cquantize->Ncolors[1], cquantize->Ncolors[2]);
  294   else
  295     TRACEMS1(cinfo, 1, JTRC_QUANT_NCOLORS, total_colors);
  296 
  297   /* Allocate and fill in the colormap. */
  298   /* The colors are ordered in the map in standard row-major order, */
  299   /* i.e. rightmost (highest-indexed) color changes most rapidly. */
  300 
  301   colormap = (*cinfo->mem->alloc_sarray)
  302     ((j_common_ptr) cinfo, JPOOL_IMAGE,
  303      (JDIMENSION) total_colors, (JDIMENSION) cinfo->out_color_components);
  304 
  305   /* blksize is number of adjacent repeated entries for a component */
  306   /* blkdist is distance between groups of identical entries for a component */
  307   blkdist = total_colors;
  308 
  309   for (i = 0; i < cinfo->out_color_components; i++) {
  310     /* fill in colormap entries for i'th color component */
  311     nci = cquantize->Ncolors[i]; /* # of distinct values for this color */
  312     blksize = blkdist / nci;
  313     for (j = 0; j < nci; j++) {
  314       /* Compute j'th output value (out of nci) for component */
  315       val = output_value(cinfo, i, j, nci-1);
  316       /* Fill in all colormap entries that have this value of this component */
  317       for (ptr = j * blksize; ptr < total_colors; ptr += blkdist) {
  318     /* fill in blksize entries beginning at ptr */
  319     for (k = 0; k < blksize; k++)
  320       colormap[i][ptr+k] = (JSAMPLE) val;
  321       }
  322     }
  323     blkdist = blksize;      /* blksize of this color is blkdist of next */
  324   }
  325 
  326   /* Save the colormap in private storage,
  327    * where it will survive color quantization mode changes.
  328    */
  329   cquantize->sv_colormap = colormap;
  330   cquantize->sv_actual = total_colors;
  331 }
  332 
  333 
  334 /*
  335  * Create the color index table.
  336  */
  337 
  338 LOCAL(void)
  339 create_colorindex (j_decompress_ptr cinfo)
  340 {
  341   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
  342   JSAMPROW indexptr;
  343   int i,j,k, nci, blksize, val, pad;
  344 
  345   /* For ordered dither, we pad the color index tables by MAXJSAMPLE in
  346    * each direction (input index values can be -MAXJSAMPLE .. 2*MAXJSAMPLE).
  347    * This is not necessary in the other dithering modes.  However, we
  348    * flag whether it was done in case user changes dithering mode.
  349    */
  350   if (cinfo->dither_mode == JDITHER_ORDERED) {
  351     pad = MAXJSAMPLE*2;
  352     cquantize->is_padded = TRUE;
  353   } else {
  354     pad = 0;
  355     cquantize->is_padded = FALSE;
  356   }
  357 
  358   cquantize->colorindex = (*cinfo->mem->alloc_sarray)
  359     ((j_common_ptr) cinfo, JPOOL_IMAGE,
  360      (JDIMENSION) (MAXJSAMPLE+1 + pad),
  361      (JDIMENSION) cinfo->out_color_components);
  362 
  363   /* blksize is number of adjacent repeated entries for a component */
  364   blksize = cquantize->sv_actual;
  365 
  366   for (i = 0; i < cinfo->out_color_components; i++) {
  367     /* fill in colorindex entries for i'th color component */
  368     nci = cquantize->Ncolors[i]; /* # of distinct values for this color */
  369     blksize = blksize / nci;
  370 
  371     /* adjust colorindex pointers to provide padding at negative indexes. */
  372     if (pad)
  373       cquantize->colorindex[i] += MAXJSAMPLE;
  374 
  375     /* in loop, val = index of current output value, */
  376     /* and k = largest j that maps to current val */
  377     indexptr = cquantize->colorindex[i];
  378     val = 0;
  379     k = largest_input_value(cinfo, i, 0, nci-1);
  380     for (j = 0; j <= MAXJSAMPLE; j++) {
  381       while (j > k)     /* advance val if past boundary */
  382     k = largest_input_value(cinfo, i, ++val, nci-1);
  383       /* premultiply so that no multiplication needed in main processing */
  384       indexptr[j] = (JSAMPLE) (val * blksize);
  385     }
  386     /* Pad at both ends if necessary */
  387     if (pad)
  388       for (j = 1; j <= MAXJSAMPLE; j++) {
  389     indexptr[-j] = indexptr[0];
  390     indexptr[MAXJSAMPLE+j] = indexptr[MAXJSAMPLE];
  391       }
  392   }
  393 }
  394 
  395 
  396 /*
  397  * Create an ordered-dither array for a component having ncolors
  398  * distinct output values.
  399  */
  400 
  401 LOCAL(ODITHER_MATRIX_PTR)
  402 make_odither_array (j_decompress_ptr cinfo, int ncolors)
  403 {
  404   ODITHER_MATRIX_PTR odither;
  405   int j,k;
  406   INT32 num,den;
  407 
  408   odither = (ODITHER_MATRIX_PTR)
  409     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
  410                 SIZEOF(ODITHER_MATRIX));
  411   /* The inter-value distance for this color is MAXJSAMPLE/(ncolors-1).
  412    * Hence the dither value for the matrix cell with fill order f
  413    * (f=0..N-1) should be (N-1-2*f)/(2*N) * MAXJSAMPLE/(ncolors-1).
  414    * On 16-bit-int machine, be careful to avoid overflow.
  415    */
  416   den = 2 * ODITHER_CELLS * ((INT32) (ncolors - 1));
  417   for (j = 0; j < ODITHER_SIZE; j++) {
  418     for (k = 0; k < ODITHER_SIZE; k++) {
  419       num = ((INT32) (ODITHER_CELLS-1 - 2*((int)base_dither_matrix[j][k])))
  420         * MAXJSAMPLE;
  421       /* Ensure round towards zero despite C's lack of consistency
  422        * about rounding negative values in integer division...
  423        */
  424       odither[j][k] = (int) (num<0 ? -((-num)/den) : num/den);
  425     }
  426   }
  427   return odither;
  428 }
  429 
  430 
  431 /*
  432  * Create the ordered-dither tables.
  433  * Components having the same number of representative colors may 
  434  * share a dither table.
  435  */
  436 
  437 LOCAL(void)
  438 create_odither_tables (j_decompress_ptr cinfo)
  439 {
  440   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
  441   ODITHER_MATRIX_PTR odither;
  442   int i, j, nci;
  443 
  444   for (i = 0; i < cinfo->out_color_components; i++) {
  445     nci = cquantize->Ncolors[i]; /* # of distinct values for this color */
  446     odither = NULL;     /* search for matching prior component */
  447     for (j = 0; j < i; j++) {
  448       if (nci == cquantize->Ncolors[j]) {
  449     odither = cquantize->odither[j];
  450     break;
  451       }
  452     }
  453     if (odither == NULL)    /* need a new table? */
  454       odither = make_odither_array(cinfo, nci);
  455     cquantize->odither[i] = odither;
  456   }
  457 }
  458 
  459 
  460 /*
  461  * Map some rows of pixels to the output colormapped representation.
  462  */
  463 
  464 METHODDEF(void)
  465 color_quantize (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
  466         JSAMPARRAY output_buf, int num_rows)
  467 /* General case, no dithering */
  468 {
  469   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
  470   JSAMPARRAY colorindex = cquantize->colorindex;
  471   register int pixcode, ci;
  472   register JSAMPROW ptrin, ptrout;
  473   int row;
  474   JDIMENSION col;
  475   JDIMENSION width = cinfo->output_width;
  476   register int nc = cinfo->out_color_components;
  477 
  478   for (row = 0; row < num_rows; row++) {
  479     ptrin = input_buf[row];
  480     ptrout = output_buf[row];
  481     for (col = width; col > 0; col--) {
  482       pixcode = 0;
  483       for (ci = 0; ci < nc; ci++) {
  484     pixcode += GETJSAMPLE(colorindex[ci][GETJSAMPLE(*ptrin++)]);
  485       }
  486       *ptrout++ = (JSAMPLE) pixcode;
  487     }
  488   }
  489 }
  490 
  491 
  492 METHODDEF(void)
  493 color_quantize3 (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
  494          JSAMPARRAY output_buf, int num_rows)
  495 /* Fast path for out_color_components==3, no dithering */
  496 {
  497   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
  498   register int pixcode;
  499   register JSAMPROW ptrin, ptrout;
  500   JSAMPROW colorindex0 = cquantize->colorindex[0];
  501   JSAMPROW colorindex1 = cquantize->colorindex[1];
  502   JSAMPROW colorindex2 = cquantize->colorindex[2];
  503   int row;
  504   JDIMENSION col;
  505   JDIMENSION width = cinfo->output_width;
  506 
  507   for (row = 0; row < num_rows; row++) {
  508     ptrin = input_buf[row];
  509     ptrout = output_buf[row];
  510     for (col = width; col > 0; col--) {
  511       pixcode  = GETJSAMPLE(colorindex0[GETJSAMPLE(*ptrin++)]);
  512       pixcode += GETJSAMPLE(colorindex1[GETJSAMPLE(*ptrin++)]);
  513       pixcode += GETJSAMPLE(colorindex2[GETJSAMPLE(*ptrin++)]);
  514       *ptrout++ = (JSAMPLE) pixcode;
  515     }
  516   }
  517 }
  518 
  519 
  520 METHODDEF(void)
  521 quantize_ord_dither (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
  522              JSAMPARRAY output_buf, int num_rows)
  523 /* General case, with ordered dithering */
  524 {
  525   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
  526   register JSAMPROW input_ptr;
  527   register JSAMPROW output_ptr;
  528   JSAMPROW colorindex_ci;
  529   int * dither;         /* points to active row of dither matrix */
  530   int row_index, col_index; /* current indexes into dither matrix */
  531   int nc = cinfo->out_color_components;
  532   int ci;
  533   int row;
  534   JDIMENSION col;
  535   JDIMENSION width = cinfo->output_width;
  536 
  537   for (row = 0; row < num_rows; row++) {
  538     /* Initialize output values to 0 so can process components separately */
  539     jzero_far((void FAR *) output_buf[row],
  540           (size_t) (width * SIZEOF(JSAMPLE)));
  541     row_index = cquantize->row_index;
  542     for (ci = 0; ci < nc; ci++) {
  543       input_ptr = input_buf[row] + ci;
  544       output_ptr = output_buf[row];
  545       colorindex_ci = cquantize->colorindex[ci];
  546       dither = cquantize->odither[ci][row_index];
  547       col_index = 0;
  548 
  549       for (col = width; col > 0; col--) {
  550     /* Form pixel value + dither, range-limit to 0..MAXJSAMPLE,
  551      * select output value, accumulate into output code for this pixel.
  552      * Range-limiting need not be done explicitly, as we have extended
  553      * the colorindex table to produce the right answers for out-of-range
  554      * inputs.  The maximum dither is +- MAXJSAMPLE; this sets the
  555      * required amount of padding.
  556      */
  557     *output_ptr += colorindex_ci[GETJSAMPLE(*input_ptr)+dither[col_index]];
  558     input_ptr += nc;
  559     output_ptr++;
  560     col_index = (col_index + 1) & ODITHER_MASK;
  561       }
  562     }
  563     /* Advance row index for next row */
  564     row_index = (row_index + 1) & ODITHER_MASK;
  565     cquantize->row_index = row_index;
  566   }
  567 }
  568 
  569 
  570 METHODDEF(void)
  571 quantize3_ord_dither (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
  572               JSAMPARRAY output_buf, int num_rows)
  573 /* Fast path for out_color_components==3, with ordered dithering */
  574 {
  575   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
  576   register int pixcode;
  577   register JSAMPROW input_ptr;
  578   register JSAMPROW output_ptr;
  579   JSAMPROW colorindex0 = cquantize->colorindex[0];
  580   JSAMPROW colorindex1 = cquantize->colorindex[1];
  581   JSAMPROW colorindex2 = cquantize->colorindex[2];
  582   int * dither0;        /* points to active row of dither matrix */
  583   int * dither1;
  584   int * dither2;
  585   int row_index, col_index; /* current indexes into dither matrix */
  586   int row;
  587   JDIMENSION col;
  588   JDIMENSION width = cinfo->output_width;
  589 
  590   for (row = 0; row < num_rows; row++) {
  591     row_index = cquantize->row_index;
  592     input_ptr = input_buf[row];
  593     output_ptr = output_buf[row];
  594     dither0 = cquantize->odither[0][row_index];
  595     dither1 = cquantize->odither[1][row_index];
  596     dither2 = cquantize->odither[2][row_index];
  597     col_index = 0;
  598 
  599     for (col = width; col > 0; col--) {
  600       pixcode  = GETJSAMPLE(colorindex0[GETJSAMPLE(*input_ptr++) +
  601                     dither0[col_index]]);
  602       pixcode += GETJSAMPLE(colorindex1[GETJSAMPLE(*input_ptr++) +
  603                     dither1[col_index]]);
  604       pixcode += GETJSAMPLE(colorindex2[GETJSAMPLE(*input_ptr++) +
  605                     dither2[col_index]]);
  606       *output_ptr++ = (JSAMPLE) pixcode;
  607       col_index = (col_index + 1) & ODITHER_MASK;
  608     }
  609     row_index = (row_index + 1) & ODITHER_MASK;
  610     cquantize->row_index = row_index;
  611   }
  612 }
  613 
  614 
  615 METHODDEF(void)
  616 quantize_fs_dither (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
  617             JSAMPARRAY output_buf, int num_rows)
  618 /* General case, with Floyd-Steinberg dithering */
  619 {
  620   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
  621   register LOCFSERROR cur;  /* current error or pixel value */
  622   LOCFSERROR belowerr;      /* error for pixel below cur */
  623   LOCFSERROR bpreverr;      /* error for below/prev col */
  624   LOCFSERROR bnexterr;      /* error for below/next col */
  625   LOCFSERROR delta;
  626   register FSERRPTR errorptr;   /* => fserrors[] at column before current */
  627   register JSAMPROW input_ptr;
  628   register JSAMPROW output_ptr;
  629   JSAMPROW colorindex_ci;
  630   JSAMPROW colormap_ci;
  631   int pixcode;
  632   int nc = cinfo->out_color_components;
  633   int dir;          /* 1 for left-to-right, -1 for right-to-left */
  634   int dirnc;            /* dir * nc */
  635   int ci;
  636   int row;
  637   JDIMENSION col;
  638   JDIMENSION width = cinfo->output_width;
  639   JSAMPLE *range_limit = cinfo->sample_range_limit;
  640   SHIFT_TEMPS
  641 
  642   for (row = 0; row < num_rows; row++) {
  643     /* Initialize output values to 0 so can process components separately */
  644     jzero_far((void FAR *) output_buf[row],
  645           (size_t) (width * SIZEOF(JSAMPLE)));
  646     for (ci = 0; ci < nc; ci++) {
  647       input_ptr = input_buf[row] + ci;
  648       output_ptr = output_buf[row];
  649       if (cquantize->on_odd_row) {
  650     /* work right to left in this row */
  651     input_ptr += (width-1) * nc; /* so point to rightmost pixel */
  652     output_ptr += width-1;
  653     dir = -1;
  654     dirnc = -nc;
  655     /* => entry after last column */
  656     errorptr = cquantize->fserrors[ci] + (width+1);
  657       } else {
  658     /* work left to right in this row */
  659     dir = 1;
  660     dirnc = nc;
  661     errorptr = cquantize->fserrors[ci]; /* => entry before first column */
  662       }
  663       colorindex_ci = cquantize->colorindex[ci];
  664       colormap_ci = cquantize->sv_colormap[ci];
  665       /* Preset error values: no error propagated to first pixel from left */
  666       cur = 0;
  667       /* and no error propagated to row below yet */
  668       belowerr = bpreverr = 0;
  669 
  670       for (col = width; col > 0; col--) {
  671     /* cur holds the error propagated from the previous pixel on the
  672      * current line.  Add the error propagated from the previous line
  673      * to form the complete error correction term for this pixel, and
  674      * round the error term (which is expressed * 16) to an integer.
  675      * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct
  676      * for either sign of the error value.
  677      * Note: errorptr points to *previous* column's array entry.
  678      */
  679     cur = RIGHT_SHIFT(cur + errorptr[dir] + 8, 4);
  680     /* Form pixel value + error, and range-limit to 0..MAXJSAMPLE.
  681      * The maximum error is +- MAXJSAMPLE; this sets the required size
  682      * of the range_limit array.
  683      */
  684     cur += GETJSAMPLE(*input_ptr);
  685     cur = GETJSAMPLE(range_limit[cur]);
  686     /* Select output value, accumulate into output code for this pixel */
  687     pixcode = GETJSAMPLE(colorindex_ci[cur]);
  688     *output_ptr += (JSAMPLE) pixcode;
  689     /* Compute actual representation error at this pixel */
  690     /* Note: we can do this even though we don't have the final */
  691     /* pixel code, because the colormap is orthogonal. */
  692     cur -= GETJSAMPLE(colormap_ci[pixcode]);
  693     /* Compute error fractions to be propagated to adjacent pixels.
  694      * Add these into the running sums, and simultaneously shift the
  695      * next-line error sums left by 1 column.
  696      */
  697     bnexterr = cur;
  698     delta = cur * 2;
  699     cur += delta;       /* form error * 3 */
  700     errorptr[0] = (FSERROR) (bpreverr + cur);
  701     cur += delta;       /* form error * 5 */
  702     bpreverr = belowerr + cur;
  703     belowerr = bnexterr;
  704     cur += delta;       /* form error * 7 */
  705     /* At this point cur contains the 7/16 error value to be propagated
  706      * to the next pixel on the current line, and all the errors for the
  707      * next line have been shifted over. We are therefore ready to move on.
  708      */
  709     input_ptr += dirnc; /* advance input ptr to next column */
  710     output_ptr += dir;  /* advance output ptr to next column */
  711     errorptr += dir;    /* advance errorptr to current column */
  712       }
  713       /* Post-loop cleanup: we must unload the final error value into the
  714        * final fserrors[] entry.  Note we need not unload belowerr because
  715        * it is for the dummy column before or after the actual array.
  716        */
  717       errorptr[0] = (FSERROR) bpreverr; /* unload prev err into array */
  718     }
  719     cquantize->on_odd_row = (cquantize->on_odd_row ? FALSE : TRUE);
  720   }
  721 }
  722 
  723 
  724 /*
  725  * Allocate workspace for Floyd-Steinberg errors.
  726  */
  727 
  728 LOCAL(void)
  729 alloc_fs_workspace (j_decompress_ptr cinfo)
  730 {
  731   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
  732   size_t arraysize;
  733   int i;
  734 
  735   arraysize = (size_t) ((cinfo->output_width + 2) * SIZEOF(FSERROR));
  736   for (i = 0; i < cinfo->out_color_components; i++) {
  737     cquantize->fserrors[i] = (FSERRPTR)
  738       (*cinfo->mem->alloc_large)((j_common_ptr) cinfo, JPOOL_IMAGE, arraysize);
  739   }
  740 }
  741 
  742 
  743 /*
  744  * Initialize for one-pass color quantization.
  745  */
  746 
  747 METHODDEF(void)
  748 start_pass_1_quant (j_decompress_ptr cinfo, boolean is_pre_scan)
  749 {
  750   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
  751   size_t arraysize;
  752   int i;
  753 
  754   (void) is_pre_scan;
  755 
  756   /* Install my colormap. */
  757   cinfo->colormap = cquantize->sv_colormap;
  758   cinfo->actual_number_of_colors = cquantize->sv_actual;
  759 
  760   /* Initialize for desired dithering mode. */
  761   switch (cinfo->dither_mode) {
  762   case JDITHER_NONE:
  763     if (cinfo->out_color_components == 3)
  764       cquantize->pub.color_quantize = color_quantize3;
  765     else
  766       cquantize->pub.color_quantize = color_quantize;
  767     break;
  768   case JDITHER_ORDERED:
  769     if (cinfo->out_color_components == 3)
  770       cquantize->pub.color_quantize = quantize3_ord_dither;
  771     else
  772       cquantize->pub.color_quantize = quantize_ord_dither;
  773     cquantize->row_index = 0;   /* initialize state for ordered dither */
  774     /* If user changed to ordered dither from another mode,
  775      * we must recreate the color index table with padding.
  776      * This will cost extra space, but probably isn't very likely.
  777      */
  778     if (! cquantize->is_padded)
  779       create_colorindex(cinfo);
  780     /* Create ordered-dither tables if we didn't already. */
  781     if (cquantize->odither[0] == NULL)
  782       create_odither_tables(cinfo);
  783     break;
  784   case JDITHER_FS:
  785     cquantize->pub.color_quantize = quantize_fs_dither;
  786     cquantize->on_odd_row = FALSE; /* initialize state for F-S dither */
  787     /* Allocate Floyd-Steinberg workspace if didn't already. */
  788     if (cquantize->fserrors[0] == NULL)
  789       alloc_fs_workspace(cinfo);
  790     /* Initialize the propagated errors to zero. */
  791     arraysize = (size_t) ((cinfo->output_width + 2) * SIZEOF(FSERROR));
  792     for (i = 0; i < cinfo->out_color_components; i++)
  793       jzero_far((void FAR *) cquantize->fserrors[i], arraysize);
  794     break;
  795   default:
  796     ERREXIT(cinfo, JERR_NOT_COMPILED);
  797     break;
  798   }
  799 }
  800 
  801 
  802 /*
  803  * Finish up at the end of the pass.
  804  */
  805 
  806 METHODDEF(void)
  807 finish_pass_1_quant (j_decompress_ptr cinfo)
  808 {
  809   (void) cinfo;
  810 
  811   /* no work in 1-pass case */
  812 }
  813 
  814 
  815 /*
  816  * Switch to a new external colormap between output passes.
  817  * Shouldn't get to this module!
  818  */
  819 
  820 METHODDEF(void)
  821 new_color_map_1_quant (j_decompress_ptr cinfo)
  822 {
  823   ERREXIT(cinfo, JERR_MODE_CHANGE);
  824 }
  825 
  826 
  827 /*
  828  * Module initialization routine for 1-pass color quantization.
  829  */
  830 
  831 GLOBAL(void)
  832 jinit_1pass_quantizer (j_decompress_ptr cinfo)
  833 {
  834   my_cquantize_ptr cquantize;
  835 
  836   cquantize = (my_cquantize_ptr)
  837     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
  838                 SIZEOF(my_cquantizer));
  839   cinfo->cquantize = (struct jpeg_color_quantizer *) cquantize;
  840   cquantize->pub.start_pass = start_pass_1_quant;
  841   cquantize->pub.finish_pass = finish_pass_1_quant;
  842   cquantize->pub.new_color_map = new_color_map_1_quant;
  843   cquantize->fserrors[0] = NULL; /* Flag FS workspace not allocated */
  844   cquantize->odither[0] = NULL; /* Also flag odither arrays not allocated */
  845 
  846   /* Make sure my internal arrays won't overflow */
  847   if (cinfo->out_color_components > MAX_Q_COMPS)
  848     ERREXIT1(cinfo, JERR_QUANT_COMPONENTS, MAX_Q_COMPS);
  849   /* Make sure colormap indexes can be represented by JSAMPLEs */
  850   if (cinfo->desired_number_of_colors > (MAXJSAMPLE+1))
  851     ERREXIT1(cinfo, JERR_QUANT_MANY_COLORS, MAXJSAMPLE+1);
  852 
  853   /* Create the colormap and color index table. */
  854   create_colormap(cinfo);
  855   create_colorindex(cinfo);
  856 
  857   /* Allocate Floyd-Steinberg workspace now if requested.
  858    * We do this now since it is FAR storage and may affect the memory
  859    * manager's space calculations.  If the user changes to FS dither
  860    * mode in a later pass, we will allocate the space then, and will
  861    * possibly overrun the max_memory_to_use setting.
  862    */
  863   if (cinfo->dither_mode == JDITHER_FS)
  864     alloc_fs_workspace(cinfo);
  865 }
  866 
  867 #endif /* QUANT_1PASS_SUPPORTED */