1  /********************************************************************** <BR>


2  This file is part of Crack dot Com's free source code release of


3  Golgotha. <a href="http://www.crack.com/golgotha_release"> <BR> for


4  information about compiling & licensing issues visit this URL</a>


5  <PRE> If that doesn't help, contact Jonathan Clark at


6  golgotha_source@usa.net (Subject should have "GOLG" in it)


7  ***********************************************************************/


8 


9  /*


10  * jquant1.c


11  *


12  * Copyright (C) 19911996, Thomas G. Lane.


13  * This file is part of the Independent JPEG Group's software.


14  * For conditions of distribution and use, see the accompanying README file.


15  *


16  * This file contains 1pass color quantization (color mapping) routines.


17  * These routines provide mapping to a fixed color map using equally spaced


18  * color values. Optional FloydSteinberg or ordered dithering is available.


19  */


20 


21  #define JPEG_INTERNALS


22  #include "loaders/jpg/jinclude.h"


23  #include "loaders/jpg/jpeglib.h"


24 


25  #ifdef QUANT_1PASS_SUPPORTED


26 


27 


28  /*


29  * The main purpose of 1pass quantization is to provide a fast, if not very


30  * high quality, colormapped output capability. A 2pass quantizer usually


31  * gives better visual quality; however, for quantized grayscale output this


32  * quantizer is perfectly adequate. Dithering is highly recommended with this


33  * quantizer, though you can turn it off if you really want to.


34  *


35  * In 1pass quantization the colormap must be chosen in advance of seeing the


36  * image. We use a map consisting of all combinations of Ncolors[i] color


37  * values for the i'th component. The Ncolors[] values are chosen so that


38  * their product, the total number of colors, is no more than that requested.


39  * (In most cases, the product will be somewhat less.)


40  *


41  * Since the colormap is orthogonal, the representative value for each color


42  * component can be determined without considering the other components;


43  * then these indexes can be combined into a colormap index by a standard


44  * Ndimensionalarraysubscript calculation. Most of the arithmetic involved


45  * can be precalculated and stored in the lookup table colorindex[].


46  * colorindex[i][j] maps pixel value j in component i to the nearest


47  * representative value (grid plane) for that component; this index is


48  * multiplied by the array stride for component i, so that the


49  * index of the colormap entry closest to a given pixel value is just


50  * sum( colorindex[componentnumber][pixelcomponentvalue] )


51  * Aside from being fast, this scheme allows for variable spacing between


52  * representative values with no additional lookup cost.


53  *


54  * If gamma correction has been applied in color conversion, it might be wise


55  * to adjust the color grid spacing so that the representative colors are


56  * equidistant in linear space. At this writing, gamma correction is not


57  * implemented by jdcolor, so nothing is done here.


58  */


59 


60 


61  /* Declarations for ordered dithering.


62  *


63  * We use a standard 16x16 ordered dither array. The basic concept of ordered


64  * dithering is described in many references, for instance Dale Schumacher's


65  * chapter II.2 of Graphics Gems II (James Arvo, ed. Academic Press, 1991).


66  * In place of Schumacher's comparisons against a "threshold" value, we add a


67  * "dither" value to the input pixel and then round the result to the nearest


68  * output value. The dither value is equivalent to (0.5  threshold) times


69  * the distance between output values. For ordered dithering, we assume that


70  * the output colors are equally spaced; if not, results will probably be


71  * worse, since the dither may be too much or too little at a given point.


72  *


73  * The normal calculation would be to form pixel value + dither, rangelimit


74  * this to 0..MAXJSAMPLE, and then index into the colorindex table as usual.


75  * We can skip the separate rangelimiting step by extending the colorindex


76  * table in both directions.


77  */


78 


79  #define ODITHER_SIZE 16 /* dimension of dither matrix */


80  /* NB: if ODITHER_SIZE is not a power of 2, ODITHER_MASK uses will break */


81  #define ODITHER_CELLS (ODITHER_SIZE*ODITHER_SIZE) /* # cells in matrix */


82  #define ODITHER_MASK (ODITHER_SIZE1) /* mask for wrapping around counters */


83 


84  typedef int ODITHER_MATRIX[ODITHER_SIZE][ODITHER_SIZE];


85  typedef int (*ODITHER_MATRIX_PTR)[ODITHER_SIZE];


86 


87  static const UINT8 base_dither_matrix[ODITHER_SIZE][ODITHER_SIZE] = {


88  /* Bayer's order4 dither array. Generated by the code given in


89  * Stephen Hawley's article "Ordered Dithering" in Graphics Gems I.


90  * The values in this array must range from 0 to ODITHER_CELLS1.


91  */


92  { 0,192, 48,240, 12,204, 60,252, 3,195, 51,243, 15,207, 63,255 },


93  { 128, 64,176,112,140, 76,188,124,131, 67,179,115,143, 79,191,127 },


94  { 32,224, 16,208, 44,236, 28,220, 35,227, 19,211, 47,239, 31,223 },


95  { 160, 96,144, 80,172,108,156, 92,163, 99,147, 83,175,111,159, 95 },


96  { 8,200, 56,248, 4,196, 52,244, 11,203, 59,251, 7,199, 55,247 },


97  { 136, 72,184,120,132, 68,180,116,139, 75,187,123,135, 71,183,119 },


98  { 40,232, 24,216, 36,228, 20,212, 43,235, 27,219, 39,231, 23,215 },


99  { 168,104,152, 88,164,100,148, 84,171,107,155, 91,167,103,151, 87 },


100  { 2,194, 50,242, 14,206, 62,254, 1,193, 49,241, 13,205, 61,253 },


101  { 130, 66,178,114,142, 78,190,126,129, 65,177,113,141, 77,189,125 },


102  { 34,226, 18,210, 46,238, 30,222, 33,225, 17,209, 45,237, 29,221 },


103  { 162, 98,146, 82,174,110,158, 94,161, 97,145, 81,173,109,157, 93 },


104  { 10,202, 58,250, 6,198, 54,246, 9,201, 57,249, 5,197, 53,245 },


105  { 138, 74,186,122,134, 70,182,118,137, 73,185,121,133, 69,181,117 },


106  { 42,234, 26,218, 38,230, 22,214, 41,233, 25,217, 37,229, 21,213 },


107  { 170,106,154, 90,166,102,150, 86,169,105,153, 89,165,101,149, 85 }


108  };


109 


110 


111  /* Declarations for FloydSteinberg dithering.


112  *


113  * Errors are accumulated into the array fserrors[], at a resolution of


114  * 1/16th of a pixel count. The error at a given pixel is propagated


115  * to its notyetprocessed neighbors using the standard FS fractions,


116  * ... (here) 7/16


117  * 3/16 5/16 1/16


118  * We work lefttoright on even rows, righttoleft on odd rows.


119  *


120  * We can get away with a single array (holding one row's worth of errors)


121  * by using it to store the current row's errors at pixel columns not yet


122  * processed, but the next row's errors at columns already processed. We


123  * need only a few extra variables to hold the errors immediately around the


124  * current column. (If we are lucky, those variables are in registers, but


125  * even if not, they're probably cheaper to access than array elements are.)


126  *


127  * The fserrors[] array is indexed [component#][position].


128  * We provide (#columns + 2) entries per component; the extra entry at each


129  * end saves us from specialcasing the first and last pixels.


130  *


131  * Note: on a wide image, we might not have enough room in a PC's near data


132  * segment to hold the error array; so it is allocated with alloc_large.


133  */


134 


135  #if BITS_IN_JSAMPLE == 8


136  typedef INT16 FSERROR; /* 16 bits should be enough */


137  typedef int LOCFSERROR; /* use 'int' for calculation temps */


138  #else


139  typedef INT32 FSERROR; /* may need more than 16 bits */


140  typedef INT32 LOCFSERROR; /* be sure calculation temps are big enough */


141  #endif


142 


143  typedef FSERROR FAR *FSERRPTR; /* pointer to error array (in FAR storage!) */


144 


145 


146  /* Private subobject */


147 


148  #define MAX_Q_COMPS 4 /* max components I can handle */


149 


150  typedef struct {


151  struct jpeg_color_quantizer pub; /* public fields */


152 


153  /* Initially allocated colormap is saved here */


154  JSAMPARRAY sv_colormap; /* The color map as a 2D pixel array */


155  int sv_actual; /* number of entries in use */


156 


157  JSAMPARRAY colorindex; /* Precomputed mapping for speed */


158  /* colorindex[i][j] = index of color closest to pixel value j in component i,


159  * premultiplied as described above. Since colormap indexes must fit into


160  * JSAMPLEs, the entries of this array will too.


161  */


162  boolean is_padded; /* is the colorindex padded for odither? */


163 


164  int Ncolors[MAX_Q_COMPS]; /* # of values alloced to each component */


165 


166  /* Variables for ordered dithering */


167  int row_index; /* cur row's vertical index in dither matrix */


168  ODITHER_MATRIX_PTR odither[MAX_Q_COMPS]; /* one dither array per component */


169 


170  /* Variables for FloydSteinberg dithering */


171  FSERRPTR fserrors[MAX_Q_COMPS]; /* accumulated errors */


172  boolean on_odd_row; /* flag to remember which row we are on */


173  } my_cquantizer;


174 


175  typedef my_cquantizer * my_cquantize_ptr;


176 


177 


178  /*


179  * Policymaking subroutines for create_colormap and create_colorindex.


180  * These routines determine the colormap to be used. The rest of the module


181  * only assumes that the colormap is orthogonal.


182  *


183  * * select_ncolors decides how to divvy up the available colors


184  * among the components.


185  * * output_value defines the set of representative values for a component.


186  * * largest_input_value defines the mapping from input values to


187  * representative values for a component.


188  * Note that the latter two routines may impose different policies for


189  * different components, though this is not currently done.


190  */


191 


192 


193  LOCAL(int)


194  select_ncolors (j_decompress_ptr cinfo, int Ncolors[])


195  /* Determine allocation of desired colors to components, */


196  /* and fill in Ncolors[] array to indicate choice. */


197  /* Return value is total number of colors (product of Ncolors[] values). */


198  {


199  int nc = cinfo>out_color_components; /* number of color components */


200  int max_colors = cinfo>desired_number_of_colors;


201  int total_colors, iroot, i, j;


202  boolean changed;


203  long temp;


204  static const int RGB_order[3] = { RGB_GREEN, RGB_RED, RGB_BLUE };


205 


206  /* We can allocate at least the nc'th root of max_colors per component. */


207  /* Compute floor(nc'th root of max_colors). */


208  iroot = 1;


209  do {


210  iroot++;


211  temp = iroot; /* set temp = iroot ** nc */


212  for (i = 1; i < nc; i++)


213  temp *= iroot;


214  } while (temp <= (long) max_colors); /* repeat till iroot exceeds root */


215  iroot; /* now iroot = floor(root) */


216 


217  /* Must have at least 2 color values per component */


218  if (iroot < 2)


219  ERREXIT1(cinfo, JERR_QUANT_FEW_COLORS, (int) temp);


220 


221  /* Initialize to iroot color values for each component */


222  total_colors = 1;


223  for (i = 0; i < nc; i++) {


224  Ncolors[i] = iroot;


225  total_colors *= iroot;


226  }


227  /* We may be able to increment the count for one or more components without


228  * exceeding max_colors, though we know not all can be incremented.


229  * Sometimes, the first component can be incremented more than once!


230  * (Example: for 16 colors, we start at 2*2*2, go to 3*2*2, then 4*2*2.)


231  * In RGB colorspace, try to increment G first, then R, then B.


232  */


233  do {


234  changed = FALSE;


235  for (i = 0; i < nc; i++) {


236  j = (cinfo>out_color_space == JCS_RGB ? RGB_order[i] : i);


237  /* calculate new total_colors if Ncolors[j] is incremented */


238  temp = total_colors / Ncolors[j];


239  temp *= Ncolors[j]+1; /* done in long arith to avoid oflo */


240  if (temp > (long) max_colors)


241  break; /* won't fit, done with this pass */


242  Ncolors[j]++; /* OK, apply the increment */


243  total_colors = (int) temp;


244  changed = TRUE;


245  }


246  } while (changed);


247 


248  return total_colors;


249  }


250 


251 


252  LOCAL(int)


253  output_value (j_decompress_ptr cinfo, int ci, int j, int maxj)


254  /* Return j'th output value, where j will range from 0 to maxj */


255  /* The output values must fall in 0..MAXJSAMPLE in increasing order */


256  {


257  /* We always provide values 0 and MAXJSAMPLE for each component;


258  * any additional values are equally spaced between these limits.


259  * (Forcing the upper and lower values to the limits ensures that


260  * dithering can't produce a color outside the selected gamut.)


261  */


262  return (int) (((INT32) j * MAXJSAMPLE + maxj/2) / maxj);


263  }


264 


265 


266  LOCAL(int)


267  largest_input_value (j_decompress_ptr cinfo, int ci, int j, int maxj)


268  /* Return largest input value that should map to j'th output value */


269  /* Must have largest(j=0) >= 0, and largest(j=maxj) >= MAXJSAMPLE */


270  {


271  /* Breakpoints are halfway between values returned by output_value */


272  return (int) (((INT32) (2*j + 1) * MAXJSAMPLE + maxj) / (2*maxj));


273  }


274 


275 


276  /*


277  * Create the colormap.


278  */


279 


280  LOCAL(void)


281  create_colormap (j_decompress_ptr cinfo)


282  {


283  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo>cquantize;


284  JSAMPARRAY colormap; /* Created colormap */


285  int total_colors; /* Number of distinct output colors */


286  int i,j,k, nci, blksize, blkdist, ptr, val;


287 


288  /* Select number of colors for each component */


289  total_colors = select_ncolors(cinfo, cquantize>Ncolors);


290 


291  /* Report selected color counts */


292  if (cinfo>out_color_components == 3)


293  TRACEMS4(cinfo, 1, JTRC_QUANT_3_NCOLORS,


294  total_colors, cquantize>Ncolors[0],


295  cquantize>Ncolors[1], cquantize>Ncolors[2]);


296  else


297  TRACEMS1(cinfo, 1, JTRC_QUANT_NCOLORS, total_colors);


298 


299  /* Allocate and fill in the colormap. */


300  /* The colors are ordered in the map in standard rowmajor order, */


301  /* i.e. rightmost (highestindexed) color changes most rapidly. */


302 


303  colormap = (*cinfo>mem>alloc_sarray)


304  ((j_common_ptr) cinfo, JPOOL_IMAGE,


305  (JDIMENSION) total_colors, (JDIMENSION) cinfo>out_color_components);


306 


307  /* blksize is number of adjacent repeated entries for a component */


308  /* blkdist is distance between groups of identical entries for a component */


309  blkdist = total_colors;


310 


311  for (i = 0; i < cinfo>out_color_components; i++) {


312  /* fill in colormap entries for i'th color component */


313  nci = cquantize>Ncolors[i]; /* # of distinct values for this color */


314  blksize = blkdist / nci;


315  for (j = 0; j < nci; j++) {


316  /* Compute j'th output value (out of nci) for component */


317  val = output_value(cinfo, i, j, nci1);


318  /* Fill in all colormap entries that have this value of this component */


319  for (ptr = j * blksize; ptr < total_colors; ptr += blkdist) {


320  /* fill in blksize entries beginning at ptr */


321  for (k = 0; k < blksize; k++)


322  colormap[i][ptr+k] = (JSAMPLE) val;


323  }


324  }


325  blkdist = blksize; /* blksize of this color is blkdist of next */


326  }


327 


328  /* Save the colormap in private storage,


329  * where it will survive color quantization mode changes.


330  */


331  cquantize>sv_colormap = colormap;


332  cquantize>sv_actual = total_colors;


333  }


334 


335 


336  /*


337  * Create the color index table.


338  */


339 


340  LOCAL(void)


341  create_colorindex (j_decompress_ptr cinfo)


342  {


343  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo>cquantize;


344  JSAMPROW indexptr;


345  int i,j,k, nci, blksize, val, pad;


346 


347  /* For ordered dither, we pad the color index tables by MAXJSAMPLE in


348  * each direction (input index values can be MAXJSAMPLE .. 2*MAXJSAMPLE).


349  * This is not necessary in the other dithering modes. However, we


350  * flag whether it was done in case user changes dithering mode.


351  */


352  if (cinfo>dither_mode == JDITHER_ORDERED) {


353  pad = MAXJSAMPLE*2;


354  cquantize>is_padded = TRUE;


355  } else {


356  pad = 0;


357  cquantize>is_padded = FALSE;


358  }


359 


360  cquantize>colorindex = (*cinfo>mem>alloc_sarray)


361  ((j_common_ptr) cinfo, JPOOL_IMAGE,


362  (JDIMENSION) (MAXJSAMPLE+1 + pad),


363  (JDIMENSION) cinfo>out_color_components);


364 


365  /* blksize is number of adjacent repeated entries for a component */


366  blksize = cquantize>sv_actual;


367 


368  for (i = 0; i < cinfo>out_color_components; i++) {


369  /* fill in colorindex entries for i'th color component */


370  nci = cquantize>Ncolors[i]; /* # of distinct values for this color */


371  blksize = blksize / nci;


372 


373  /* adjust colorindex pointers to provide padding at negative indexes. */


374  if (pad)


375  cquantize>colorindex[i] += MAXJSAMPLE;


376 


377  /* in loop, val = index of current output value, */


378  /* and k = largest j that maps to current val */


379  indexptr = cquantize>colorindex[i];


380  val = 0;


381  k = largest_input_value(cinfo, i, 0, nci1);


382  for (j = 0; j <= MAXJSAMPLE; j++) {


383  while (j > k) /* advance val if past boundary */


384  k = largest_input_value(cinfo, i, ++val, nci1);


385  /* premultiply so that no multiplication needed in main processing */


386  indexptr[j] = (JSAMPLE) (val * blksize);


387  }


388  /* Pad at both ends if necessary */


389  if (pad)


390  for (j = 1; j <= MAXJSAMPLE; j++) {


391  indexptr[j] = indexptr[0];


392  indexptr[MAXJSAMPLE+j] = indexptr[MAXJSAMPLE];


393  }


394  }


395  }


396 


397 


398  /*


399  * Create an ordereddither array for a component having ncolors


400  * distinct output values.


401  */


402 


403  LOCAL(ODITHER_MATRIX_PTR)


404  make_odither_array (j_decompress_ptr cinfo, int ncolors)


405  {


406  ODITHER_MATRIX_PTR odither;


407  int j,k;


408  INT32 num,den;


409 


410  odither = (ODITHER_MATRIX_PTR)


411  (*cinfo>mem>alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,


412  SIZEOF(ODITHER_MATRIX));


413  /* The intervalue distance for this color is MAXJSAMPLE/(ncolors1).


414  * Hence the dither value for the matrix cell with fill order f


415  * (f=0..N1) should be (N12*f)/(2*N) * MAXJSAMPLE/(ncolors1).


416  * On 16bitint machine, be careful to avoid overflow.


417  */


418  den = 2 * ODITHER_CELLS * ((INT32) (ncolors  1));


419  for (j = 0; j < ODITHER_SIZE; j++) {


420  for (k = 0; k < ODITHER_SIZE; k++) {


421  num = ((INT32) (ODITHER_CELLS1  2*((int)base_dither_matrix[j][k])))


422  * MAXJSAMPLE;


423  /* Ensure round towards zero despite C's lack of consistency


424  * about rounding negative values in integer division...


425  */


426  odither[j][k] = (int) (num<0 ? ((num)/den) : num/den);


427  }


428  }


429  return odither;


430  }


431 


432 


433  /*


434  * Create the ordereddither tables.


435  * Components having the same number of representative colors may


436  * share a dither table.


437  */


438 


439  LOCAL(void)


440  create_odither_tables (j_decompress_ptr cinfo)


441  {


442  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo>cquantize;


443  ODITHER_MATRIX_PTR odither;


444  int i, j, nci;


445 


446  for (i = 0; i < cinfo>out_color_components; i++) {


447  nci = cquantize>Ncolors[i]; /* # of distinct values for this color */


448  odither = NULL; /* search for matching prior component */


449  for (j = 0; j < i; j++) {


450  if (nci == cquantize>Ncolors[j]) {


451  odither = cquantize>odither[j];


452  break;


453  }


454  }


455  if (odither == NULL) /* need a new table? */


456  odither = make_odither_array(cinfo, nci);


457  cquantize>odither[i] = odither;


458  }


459  }


460 


461 


462  /*


463  * Map some rows of pixels to the output colormapped representation.


464  */


465 


466  METHODDEF(void)


467  color_quantize (j_decompress_ptr cinfo, JSAMPARRAY input_buf,


468  JSAMPARRAY output_buf, int num_rows)


469  /* General case, no dithering */


470  {


471  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo>cquantize;


472  JSAMPARRAY colorindex = cquantize>colorindex;


473  register int pixcode, ci;


474  register JSAMPROW ptrin, ptrout;


475  int row;


476  JDIMENSION col;


477  JDIMENSION width = cinfo>output_width;


478  register int nc = cinfo>out_color_components;


479 


480  for (row = 0; row < num_rows; row++) {


481  ptrin = input_buf[row];


482  ptrout = output_buf[row];


483  for (col = width; col > 0; col) {


484  pixcode = 0;


485  for (ci = 0; ci < nc; ci++) {


486  pixcode += GETJSAMPLE(colorindex[ci][GETJSAMPLE(*ptrin++)]);


487  }


488  *ptrout++ = (JSAMPLE) pixcode;


489  }


490  }


491  }


492 


493 


494  METHODDEF(void)


495  color_quantize3 (j_decompress_ptr cinfo, JSAMPARRAY input_buf,


496  JSAMPARRAY output_buf, int num_rows)


497  /* Fast path for out_color_components==3, no dithering */


498  {


499  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo>cquantize;


500  register int pixcode;


501  register JSAMPROW ptrin, ptrout;


502  JSAMPROW colorindex0 = cquantize>colorindex[0];


503  JSAMPROW colorindex1 = cquantize>colorindex[1];


504  JSAMPROW colorindex2 = cquantize>colorindex[2];


505  int row;


506  JDIMENSION col;


507  JDIMENSION width = cinfo>output_width;


508 


509  for (row = 0; row < num_rows; row++) {


510  ptrin = input_buf[row];


511  ptrout = output_buf[row];


512  for (col = width; col > 0; col) {


513  pixcode = GETJSAMPLE(colorindex0[GETJSAMPLE(*ptrin++)]);


514  pixcode += GETJSAMPLE(colorindex1[GETJSAMPLE(*ptrin++)]);


515  pixcode += GETJSAMPLE(colorindex2[GETJSAMPLE(*ptrin++)]);


516  *ptrout++ = (JSAMPLE) pixcode;


517  }


518  }


519  }


520 


521 


522  METHODDEF(void)


523  quantize_ord_dither (j_decompress_ptr cinfo, JSAMPARRAY input_buf,


524  JSAMPARRAY output_buf, int num_rows)


525  /* General case, with ordered dithering */


526  {


527  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo>cquantize;


528  register JSAMPROW input_ptr;


529  register JSAMPROW output_ptr;


530  JSAMPROW colorindex_ci;


531  int * dither; /* points to active row of dither matrix */


532  int row_index, col_index; /* current indexes into dither matrix */


533  int nc = cinfo>out_color_components;


534  int ci;


535  int row;


536  JDIMENSION col;


537  JDIMENSION width = cinfo>output_width;


538 


539  for (row = 0; row < num_rows; row++) {


540  /* Initialize output values to 0 so can process components separately */


541  jzero_far((void FAR *) output_buf[row],


542  (size_t) (width * SIZEOF(JSAMPLE)));


543  row_index = cquantize>row_index;


544  for (ci = 0; ci < nc; ci++) {


545  input_ptr = input_buf[row] + ci;


546  output_ptr = output_buf[row];


547  colorindex_ci = cquantize>colorindex[ci];


548  dither = cquantize>odither[ci][row_index];


549  col_index = 0;


550 


551  for (col = width; col > 0; col) {


552  /* Form pixel value + dither, rangelimit to 0..MAXJSAMPLE,


553  * select output value, accumulate into output code for this pixel.


554  * Rangelimiting need not be done explicitly, as we have extended


555  * the colorindex table to produce the right answers for outofrange


556  * inputs. The maximum dither is + MAXJSAMPLE; this sets the


557  * required amount of padding.


558  */


559  *output_ptr += colorindex_ci[GETJSAMPLE(*input_ptr)+dither[col_index]];


560  input_ptr += nc;


561  output_ptr++;


562  col_index = (col_index + 1) & ODITHER_MASK;


563  }


564  }


565  /* Advance row index for next row */


566  row_index = (row_index + 1) & ODITHER_MASK;


567  cquantize>row_index = row_index;


568  }


569  }


570 


571 


572  METHODDEF(void)


573  quantize3_ord_dither (j_decompress_ptr cinfo, JSAMPARRAY input_buf,


574  JSAMPARRAY output_buf, int num_rows)


575  /* Fast path for out_color_components==3, with ordered dithering */


576  {


577  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo>cquantize;


578  register int pixcode;


579  register JSAMPROW input_ptr;


580  register JSAMPROW output_ptr;


581  JSAMPROW colorindex0 = cquantize>colorindex[0];


582  JSAMPROW colorindex1 = cquantize>colorindex[1];


583  JSAMPROW colorindex2 = cquantize>colorindex[2];


584  int * dither0; /* points to active row of dither matrix */


585  int * dither1;


586  int * dither2;


587  int row_index, col_index; /* current indexes into dither matrix */


588  int row;


589  JDIMENSION col;


590  JDIMENSION width = cinfo>output_width;


591 


592  for (row = 0; row < num_rows; row++) {


593  row_index = cquantize>row_index;


594  input_ptr = input_buf[row];


595  output_ptr = output_buf[row];


596  dither0 = cquantize>odither[0][row_index];


597  dither1 = cquantize>odither[1][row_index];


598  dither2 = cquantize>odither[2][row_index];


599  col_index = 0;


600 


601  for (col = width; col > 0; col) {


602  pixcode = GETJSAMPLE(colorindex0[GETJSAMPLE(*input_ptr++) +


603  dither0[col_index]]);


604  pixcode += GETJSAMPLE(colorindex1[GETJSAMPLE(*input_ptr++) +


605  dither1[col_index]]);


606  pixcode += GETJSAMPLE(colorindex2[GETJSAMPLE(*input_ptr++) +


607  dither2[col_index]]);


608  *output_ptr++ = (JSAMPLE) pixcode;


609  col_index = (col_index + 1) & ODITHER_MASK;


610  }


611  row_index = (row_index + 1) & ODITHER_MASK;


612  cquantize>row_index = row_index;


613  }


614  }


615 


616 


617  METHODDEF(void)


618  quantize_fs_dither (j_decompress_ptr cinfo, JSAMPARRAY input_buf,


619  JSAMPARRAY output_buf, int num_rows)


620  /* General case, with FloydSteinberg dithering */


621  {


622  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo>cquantize;


623  register LOCFSERROR cur; /* current error or pixel value */


624  LOCFSERROR belowerr; /* error for pixel below cur */


625  LOCFSERROR bpreverr; /* error for below/prev col */


626  LOCFSERROR bnexterr; /* error for below/next col */


627  LOCFSERROR delta;


628  register FSERRPTR errorptr; /* => fserrors[] at column before current */


629  register JSAMPROW input_ptr;


630  register JSAMPROW output_ptr;


631  JSAMPROW colorindex_ci;


632  JSAMPROW colormap_ci;


633  int pixcode;


634  int nc = cinfo>out_color_components;


635  int dir; /* 1 for lefttoright, 1 for righttoleft */


636  int dirnc; /* dir * nc */


637  int ci;


638  int row;


639  JDIMENSION col;


640  JDIMENSION width = cinfo>output_width;


641  JSAMPLE *range_limit = cinfo>sample_range_limit;


642  SHIFT_TEMPS


643 


644  for (row = 0; row < num_rows; row++) {


645  /* Initialize output values to 0 so can process components separately */


646  jzero_far((void FAR *) output_buf[row],


647  (size_t) (width * SIZEOF(JSAMPLE)));


648  for (ci = 0; ci < nc; ci++) {


649  input_ptr = input_buf[row] + ci;


650  output_ptr = output_buf[row];


651  if (cquantize>on_odd_row) {


652  /* work right to left in this row */


653  input_ptr += (width1) * nc; /* so point to rightmost pixel */


654  output_ptr += width1;


655  dir = 1;


656  dirnc = nc;


657  errorptr = cquantize>fserrors[ci] + (width+1); /* => entry after last column */


658  } else {


659  /* work left to right in this row */


660  dir = 1;


661  dirnc = nc;


662  errorptr = cquantize>fserrors[ci]; /* => entry before first column */


663  }


664  colorindex_ci = cquantize>colorindex[ci];


665  colormap_ci = cquantize>sv_colormap[ci];


666  /* Preset error values: no error propagated to first pixel from left */


667  cur = 0;


668  /* and no error propagated to row below yet */


669  belowerr = bpreverr = 0;


670 


671  for (col = width; col > 0; col) {


672  /* cur holds the error propagated from the previous pixel on the


673  * current line. Add the error propagated from the previous line


674  * to form the complete error correction term for this pixel, and


675  * round the error term (which is expressed * 16) to an integer.


676  * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct


677  * for either sign of the error value.


678  * Note: errorptr points to *previous* column's array entry.


679  */


680  cur = RIGHT_SHIFT(cur + errorptr[dir] + 8, 4);


681  /* Form pixel value + error, and rangelimit to 0..MAXJSAMPLE.


682  * The maximum error is + MAXJSAMPLE; this sets the required size


683  * of the range_limit array.


684  */


685  cur += GETJSAMPLE(*input_ptr);


686  cur = GETJSAMPLE(range_limit[cur]);


687  /* Select output value, accumulate into output code for this pixel */


688  pixcode = GETJSAMPLE(colorindex_ci[cur]);


689  *output_ptr += (JSAMPLE) pixcode;


690  /* Compute actual representation error at this pixel */


691  /* Note: we can do this even though we don't have the final */


692  /* pixel code, because the colormap is orthogonal. */


693  cur = GETJSAMPLE(colormap_ci[pixcode]);


694  /* Compute error fractions to be propagated to adjacent pixels.


695  * Add these into the running sums, and simultaneously shift the


696  * nextline error sums left by 1 column.


697  */


698  bnexterr = cur;


699  delta = cur * 2;


700  cur += delta; /* form error * 3 */


701  errorptr[0] = (FSERROR) (bpreverr + cur);


702  cur += delta; /* form error * 5 */


703  bpreverr = belowerr + cur;


704  belowerr = bnexterr;


705  cur += delta; /* form error * 7 */


706  /* At this point cur contains the 7/16 error value to be propagated


707  * to the next pixel on the current line, and all the errors for the


708  * next line have been shifted over. We are therefore ready to move on.


709  */


710  input_ptr += dirnc; /* advance input ptr to next column */


711  output_ptr += dir; /* advance output ptr to next column */


712  errorptr += dir; /* advance errorptr to current column */


713  }


714  /* Postloop cleanup: we must unload the final error value into the


715  * final fserrors[] entry. Note we need not unload belowerr because


716  * it is for the dummy column before or after the actual array.


717  */


718  errorptr[0] = (FSERROR) bpreverr; /* unload prev err into array */


719  }


720  cquantize>on_odd_row = (cquantize>on_odd_row ? FALSE : TRUE);


721  }


722  }


723 


724 


725  /*


726  * Allocate workspace for FloydSteinberg errors.


727  */


728 


729  LOCAL(void)


730  alloc_fs_workspace (j_decompress_ptr cinfo)


731  {


732  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo>cquantize;


733  size_t arraysize;


734  int i;


735 


736  arraysize = (size_t) ((cinfo>output_width + 2) * SIZEOF(FSERROR));


737  for (i = 0; i < cinfo>out_color_components; i++) {


738  cquantize>fserrors[i] = (FSERRPTR)


739  (*cinfo>mem>alloc_large)((j_common_ptr) cinfo, JPOOL_IMAGE, arraysize);


740  }


741  }


742 


743 


744  /*


745  * Initialize for onepass color quantization.


746  */


747 


748  METHODDEF(void)


749  start_pass_1_quant (j_decompress_ptr cinfo, boolean is_pre_scan)


750  {


751  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo>cquantize;


752  size_t arraysize;


753  int i;


754 


755  /* Install my colormap. */


756  cinfo>colormap = cquantize>sv_colormap;


757  cinfo>actual_number_of_colors = cquantize>sv_actual;


758 


759  /* Initialize for desired dithering mode. */


760  switch (cinfo>dither_mode) {


761  case JDITHER_NONE:


762  if (cinfo>out_color_components == 3)


763  cquantize>pub.color_quantize = color_quantize3;


764  else


765  cquantize>pub.color_quantize = color_quantize;


766  break;


767  case JDITHER_ORDERED:


768  if (cinfo>out_color_components == 3)


769  cquantize>pub.color_quantize = quantize3_ord_dither;


770  else


771  cquantize>pub.color_quantize = quantize_ord_dither;


772  cquantize>row_index = 0; /* initialize state for ordered dither */


773  /* If user changed to ordered dither from another mode,


774  * we must recreate the color index table with padding.


775  * This will cost extra space, but probably isn't very likely.


776  */


777  if (! cquantize>is_padded)


778  create_colorindex(cinfo);


779  /* Create ordereddither tables if we didn't already. */


780  if (cquantize>odither[0] == NULL)


781  create_odither_tables(cinfo);


782  break;


783  case JDITHER_FS:


784  cquantize>pub.color_quantize = quantize_fs_dither;


785  cquantize>on_odd_row = FALSE; /* initialize state for FS dither */


786  /* Allocate FloydSteinberg workspace if didn't already. */


787  if (cquantize>fserrors[0] == NULL)


788  alloc_fs_workspace(cinfo);


789  /* Initialize the propagated errors to zero. */


790  arraysize = (size_t) ((cinfo>output_width + 2) * SIZEOF(FSERROR));


791  for (i = 0; i < cinfo>out_color_components; i++)


792  jzero_far((void FAR *) cquantize>fserrors[i], arraysize);


793  break;


794  default:


795  ERREXIT(cinfo, JERR_NOT_COMPILED);


796  break;


797  }


798  }


799 


800 


801  /*


802  * Finish up at the end of the pass.


803  */


804 


805  METHODDEF(void)


806  finish_pass_1_quant (j_decompress_ptr cinfo)


807  {


808  /* no work in 1pass case */


809  }


810 


811 


812  /*


813  * Switch to a new external colormap between output passes.


814  * Shouldn't get to this module!


815  */


816 


817  METHODDEF(void)


818  new_color_map_1_quant (j_decompress_ptr cinfo)


819  {


820  ERREXIT(cinfo, JERR_MODE_CHANGE);


821  }


822 


823 


824  /*


825  * Module initialization routine for 1pass color quantization.


826  */


827 


828  GLOBAL(void)


829  jinit_1pass_quantizer (j_decompress_ptr cinfo)


830  {


831  my_cquantize_ptr cquantize;


832 


833  cquantize = (my_cquantize_ptr)


834  (*cinfo>mem>alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,


835  SIZEOF(my_cquantizer));


836  cinfo>cquantize = (struct jpeg_color_quantizer *) cquantize;


837  cquantize>pub.start_pass = start_pass_1_quant;


838  cquantize>pub.finish_pass = finish_pass_1_quant;


839  cquantize>pub.new_color_map = new_color_map_1_quant;


840  cquantize>fserrors[0] = NULL; /* Flag FS workspace not allocated */


841  cquantize>odither[0] = NULL; /* Also flag odither arrays not allocated */


842 


843  /* Make sure my internal arrays won't overflow */


844  if (cinfo>out_color_components > MAX_Q_COMPS)


845  ERREXIT1(cinfo, JERR_QUANT_COMPONENTS, MAX_Q_COMPS);


846  /* Make sure colormap indexes can be represented by JSAMPLEs */


847  if (cinfo>desired_number_of_colors > (MAXJSAMPLE+1))


848  ERREXIT1(cinfo, JERR_QUANT_MANY_COLORS, MAXJSAMPLE+1);


849 


850  /* Create the colormap and color index table. */


851  create_colormap(cinfo);


852  create_colorindex(cinfo);


853 


854  /* Allocate FloydSteinberg workspace now if requested.


855  * We do this now since it is FAR storage and may affect the memory


856  * manager's space calculations. If the user changes to FS dither


857  * mode in a later pass, we will allocate the space then, and will


858  * possibly overrun the max_memory_to_use setting.


859  */


860  if (cinfo>dither_mode == JDITHER_FS)


861  alloc_fs_workspace(cinfo);


862  }


863 


864  #endif /* QUANT_1PASS_SUPPORTED */

