Back to index

plt-scheme  4.2.1
gd_topal.c
Go to the documentation of this file.
00001 /* 2.0.12: a new adaptation from the same original, this time
00002        by Barend Gehrels. My attempt to incorporate alpha channel
00003        into the result worked poorly and degraded the quality of
00004        palette conversion even when the source contained no
00005        alpha channel data. This version does not attempt to produce
00006        an output file with transparency in some of the palette
00007        indexes, which, in practice, doesn't look so hot anyway. TBB */
00008 
00009 /*
00010  * gd_topal, adapted from jquant2.c
00011  *
00012  * Copyright (C) 1991-1996, Thomas G. Lane.
00013  * This file is part of the Independent JPEG Group's software.
00014  * For conditions of distribution and use, see the accompanying README file.
00015  *
00016  * This file contains 2-pass color quantization (color mapping) routines.
00017  * These routines provide selection of a custom color map for an image,
00018  * followed by mapping of the image to that color map, with optional
00019  * Floyd-Steinberg dithering.
00020  * It is also possible to use just the second pass to map to an arbitrary
00021  * externally-given color map.
00022  *
00023  * Note: ordered dithering is not supported, since there isn't any fast
00024  * way to compute intercolor distances; it's unclear that ordered dither's
00025  * fundamental assumptions even hold with an irregularly spaced color map.
00026  */
00027 
00028 #ifdef ORIGINAL_LIB_JPEG
00029 
00030 #define JPEG_INTERNALS
00031 
00032 #include "jinclude.h"
00033 #include "jpeglib.h"
00034 
00035 #else
00036 
00037 /*
00038  * THOMAS BOUTELL & BAREND GEHRELS, february 2003
00039  * adapted the code to work within gd rather than within libjpeg.
00040  * If it is not working, it's not Thomas G. Lane's fault.
00041  */
00042 
00043 /* 
00044   SETTING THIS ONE CAUSES STRIPED IMAGE
00045   to be done: solve this
00046   #define ORIGINAL_LIB_JPEG_REVERSE_ODD_ROWS
00047  */
00048 
00049 #include <string.h>
00050 #include "gd.h"
00051 #include "gdhelpers.h"
00052 
00053 /* (Re)define some defines known by libjpeg */
00054 #define QUANT_2PASS_SUPPORTED
00055 
00056 #define RGB_RED             0
00057 #define RGB_GREEN    1
00058 #define RGB_BLUE     2
00059 
00060 #define JSAMPLE unsigned char
00061 #define MAXJSAMPLE (gdMaxColors-1)
00062 #define BITS_IN_JSAMPLE 8
00063 
00064 #define JSAMPROW int*
00065 #define JDIMENSION int
00066 
00067 #define METHODDEF(type) static type
00068 #define LOCAL(type)  static type
00069 
00070 
00071 /* We assume that right shift corresponds to signed division by 2 with
00072  * rounding towards minus infinity.  This is correct for typical "arithmetic
00073  * shift" instructions that shift in copies of the sign bit.  But some
00074  * C compilers implement >> with an unsigned shift.  For these machines you
00075  * must define RIGHT_SHIFT_IS_UNSIGNED.
00076  * RIGHT_SHIFT provides a proper signed right shift of an INT32 quantity.
00077  * It is only applied with constant shift counts.  SHIFT_TEMPS must be
00078  * included in the variables of any routine using RIGHT_SHIFT.
00079  */
00080 
00081 #ifdef RIGHT_SHIFT_IS_UNSIGNED
00082 #define SHIFT_TEMPS  INT32 shift_temp;
00083 #define RIGHT_SHIFT(x,shft)  \
00084        ((shift_temp = (x)) < 0 ? \
00085         (shift_temp >> (shft)) | ((~((INT32) 0)) << (32-(shft))) : \
00086         (shift_temp >> (shft)))
00087 #else
00088 #define SHIFT_TEMPS
00089 #define RIGHT_SHIFT(x,shft) ((x) >> (shft))
00090 #endif
00091 
00092 
00093 #define range_limit(x) { if(x<0) x=0; if (x>255) x=255; }
00094 
00095 
00096 #ifndef INT16
00097 #define INT16  short
00098 #endif
00099 
00100 #ifndef UINT16
00101 #define UINT16 unsigned short
00102 #endif
00103 
00104 #ifndef INT32
00105 #define INT32 int
00106 #endif
00107 
00108 #ifndef FAR
00109 #define FAR
00110 #endif
00111 
00112 
00113 
00114 #ifndef boolean
00115 #define boolean int
00116 #endif
00117 
00118 #ifndef TRUE
00119 #define TRUE 1
00120 #endif
00121 
00122 #ifndef FALSE
00123 #define FALSE 0
00124 #endif
00125 
00126 
00127 #define input_buf (im->tpixels)
00128 #define output_buf (im->pixels)
00129 
00130 #endif
00131 
00132 #ifdef QUANT_2PASS_SUPPORTED
00133 
00134 
00135 /*
00136  * This module implements the well-known Heckbert paradigm for color
00137  * quantization.  Most of the ideas used here can be traced back to
00138  * Heckbert's seminal paper
00139  *   Heckbert, Paul.  "Color Image Quantization for Frame Buffer Display",
00140  *   Proc. SIGGRAPH '82, Computer Graphics v.16 #3 (July 1982), pp 297-304.
00141  *
00142  * In the first pass over the image, we accumulate a histogram showing the
00143  * usage count of each possible color.  To keep the histogram to a reasonable
00144  * size, we reduce the precision of the input; typical practice is to retain
00145  * 5 or 6 bits per color, so that 8 or 4 different input values are counted
00146  * in the same histogram cell.
00147  *
00148  * Next, the color-selection step begins with a box representing the whole
00149  * color space, and repeatedly splits the "largest" remaining box until we
00150  * have as many boxes as desired colors.  Then the mean color in each
00151  * remaining box becomes one of the possible output colors.
00152  * 
00153  * The second pass over the image maps each input pixel to the closest output
00154  * color (optionally after applying a Floyd-Steinberg dithering correction).
00155  * This mapping is logically trivial, but making it go fast enough requires
00156  * considerable care.
00157  *
00158  * Heckbert-style quantizers vary a good deal in their policies for choosing
00159  * the "largest" box and deciding where to cut it.  The particular policies
00160  * used here have proved out well in experimental comparisons, but better ones
00161  * may yet be found.
00162  *
00163  * In earlier versions of the IJG code, this module quantized in YCbCr color
00164  * space, processing the raw upsampled data without a color conversion step.
00165  * This allowed the color conversion math to be done only once per colormap
00166  * entry, not once per pixel.  However, that optimization precluded other
00167  * useful optimizations (such as merging color conversion with upsampling)
00168  * and it also interfered with desired capabilities such as quantizing to an
00169  * externally-supplied colormap.  We have therefore abandoned that approach.
00170  * The present code works in the post-conversion color space, typically RGB.
00171  *
00172  * To improve the visual quality of the results, we actually work in scaled
00173  * RGB space, giving G distances more weight than R, and R in turn more than
00174  * B.  To do everything in integer math, we must use integer scale factors.
00175  * The 2/3/1 scale factors used here correspond loosely to the relative
00176  * weights of the colors in the NTSC grayscale equation.
00177  * If you want to use this code to quantize a non-RGB color space, you'll
00178  * probably need to change these scale factors.
00179  */
00180 
00181 #define R_SCALE 2           /* scale R distances by this much */
00182 #define G_SCALE 3           /* scale G distances by this much */
00183 #define B_SCALE 1           /* and B by this much */
00184 
00185 /* Relabel R/G/B as components 0/1/2, respecting the RGB ordering defined
00186  * in jmorecfg.h.  As the code stands, it will do the right thing for R,G,B
00187  * and B,G,R orders.  If you define some other weird order in jmorecfg.h,
00188  * you'll get compile errors until you extend this logic.  In that case
00189  * you'll probably want to tweak the histogram sizes too.
00190  */
00191 
00192 #if RGB_RED == 0
00193 #define C0_SCALE R_SCALE
00194 #endif
00195 #if RGB_BLUE == 0
00196 #define C0_SCALE B_SCALE
00197 #endif
00198 #if RGB_GREEN == 1
00199 #define C1_SCALE G_SCALE
00200 #endif
00201 #if RGB_RED == 2
00202 #define C2_SCALE R_SCALE
00203 #endif
00204 #if RGB_BLUE == 2
00205 #define C2_SCALE B_SCALE
00206 #endif
00207 
00208 
00209 /*
00210  * First we have the histogram data structure and routines for creating it.
00211  *
00212  * The number of bits of precision can be adjusted by changing these symbols.
00213  * We recommend keeping 6 bits for G and 5 each for R and B.
00214  * If you have plenty of memory and cycles, 6 bits all around gives marginally
00215  * better results; if you are short of memory, 5 bits all around will save
00216  * some space but degrade the results.
00217  * To maintain a fully accurate histogram, we'd need to allocate a "long"
00218  * (preferably unsigned long) for each cell.  In practice this is overkill;
00219  * we can get by with 16 bits per cell.  Few of the cell counts will overflow,
00220  * and clamping those that do overflow to the maximum value will give close-
00221  * enough results.  This reduces the recommended histogram size from 256Kb
00222  * to 128Kb, which is a useful savings on PC-class machines.
00223  * (In the second pass the histogram space is re-used for pixel mapping data;
00224  * in that capacity, each cell must be able to store zero to the number of
00225  * desired colors.  16 bits/cell is plenty for that too.)
00226  * Since the JPEG code is intended to run in small memory model on 80x86
00227  * machines, we can't just allocate the histogram in one chunk.  Instead
00228  * of a true 3-D array, we use a row of pointers to 2-D arrays.  Each
00229  * pointer corresponds to a C0 value (typically 2^5 = 32 pointers) and
00230  * each 2-D array has 2^6*2^5 = 2048 or 2^6*2^6 = 4096 entries.  Note that
00231  * on 80x86 machines, the pointer row is in near memory but the actual
00232  * arrays are in far memory (same arrangement as we use for image arrays).
00233  */
00234 
00235 #define MAXNUMCOLORS  (MAXJSAMPLE+1)      /* maximum size of colormap */
00236 
00237 /* These will do the right thing for either R,G,B or B,G,R color order,
00238  * but you may not like the results for other color orders.
00239  */
00240 #define HIST_C0_BITS  5            /* bits of precision in R/B histogram */
00241 #define HIST_C1_BITS  6            /* bits of precision in G histogram */
00242 #define HIST_C2_BITS  5            /* bits of precision in B/R histogram */
00243 
00244 /* Number of elements along histogram axes. */
00245 #define HIST_C0_ELEMS  (1<<HIST_C0_BITS)
00246 #define HIST_C1_ELEMS  (1<<HIST_C1_BITS)
00247 #define HIST_C2_ELEMS  (1<<HIST_C2_BITS)
00248 
00249 /* These are the amounts to shift an input value to get a histogram index. */
00250 #define C0_SHIFT  (BITS_IN_JSAMPLE-HIST_C0_BITS)
00251 #define C1_SHIFT  (BITS_IN_JSAMPLE-HIST_C1_BITS)
00252 #define C2_SHIFT  (BITS_IN_JSAMPLE-HIST_C2_BITS)
00253 
00254 
00255 typedef UINT16 histcell;    /* histogram cell; prefer an unsigned type */
00256 
00257 typedef histcell FAR *histptr;     /* for pointers to histogram cells */
00258 
00259 typedef histcell hist1d[HIST_C2_ELEMS];   /* typedefs for the array */
00260 typedef hist1d FAR *hist2d; /* type for the 2nd-level pointers */
00261 typedef hist2d *hist3d;            /* type for top-level pointer */
00262 
00263 
00264 /* Declarations for Floyd-Steinberg dithering.
00265  *
00266  * Errors are accumulated into the array fserrors[], at a resolution of
00267  * 1/16th of a pixel count.  The error at a given pixel is propagated
00268  * to its not-yet-processed neighbors using the standard F-S fractions,
00269  *            ...    (here) 7/16
00270  *            3/16   5/16   1/16
00271  * We work left-to-right on even rows, right-to-left on odd rows.
00272  *
00273  * We can get away with a single array (holding one row's worth of errors)
00274  * by using it to store the current row's errors at pixel columns not yet
00275  * processed, but the next row's errors at columns already processed.  We
00276  * need only a few extra variables to hold the errors immediately around the
00277  * current column.  (If we are lucky, those variables are in registers, but
00278  * even if not, they're probably cheaper to access than array elements are.)
00279  *
00280  * The fserrors[] array has (#columns + 2) entries; the extra entry at
00281  * each end saves us from special-casing the first and last pixels.
00282  * Each entry is three values long, one value for each color component.
00283  *
00284  * Note: on a wide image, we might not have enough room in a PC's near data
00285  * segment to hold the error array; so it is allocated with alloc_large.
00286  */
00287 
00288 #if BITS_IN_JSAMPLE == 8
00289 typedef INT16 FSERROR;             /* 16 bits should be enough */
00290 typedef int LOCFSERROR;            /* use 'int' for calculation temps */
00291 #else
00292 typedef INT32 FSERROR;             /* may need more than 16 bits */
00293 typedef INT32 LOCFSERROR;   /* be sure calculation temps are big enough */
00294 #endif
00295 
00296 typedef FSERROR FAR *FSERRPTR;     /* pointer to error array (in FAR storage!) */
00297 
00298 
00299 /* Private subobject */
00300 
00301 typedef struct
00302 {
00303 #ifdef ORIGINAL_LIB_JPEG
00304   struct jpeg_color_quantizer pub; /* public fields */
00305 
00306   /* Space for the eventually created colormap is stashed here */
00307   JSAMPARRAY sv_colormap;   /* colormap allocated at init time */
00308   int desired;                     /* desired # of colors = size of colormap */
00309   boolean needs_zeroed;            /* TRUE if next pass must zero histogram */
00310 #endif
00311 
00312   /* Variables for accumulating image statistics */
00313   hist3d histogram;         /* pointer to the histogram */
00314 
00315 
00316   /* Variables for Floyd-Steinberg dithering */
00317   FSERRPTR fserrors;        /* accumulated errors */
00318 
00319   boolean on_odd_row;              /* flag to remember which row we are on */
00320   int *error_limiter;              /* table for clamping the applied error */
00321 #ifndef ORIGINAL_LIB_JPEG
00322   int *error_limiter_storage;      /* gdMalloc'd storage for the above */
00323 #endif
00324 }
00325 my_cquantizer;
00326 
00327 typedef my_cquantizer *my_cquantize_ptr;
00328 
00329 
00330 /*
00331  * Prescan some rows of pixels.
00332  * In this module the prescan simply updates the histogram, which has been
00333  * initialized to zeroes by start_pass.
00334  * An output_buf parameter is required by the method signature, but no data
00335  * is actually output (in fact the buffer controller is probably passing a
00336  * NULL pointer).
00337  */
00338 
00339 METHODDEF (void)
00340 #ifndef ORIGINAL_LIB_JPEG
00341 prescan_quantize (gdImagePtr im, my_cquantize_ptr cquantize)
00342 {
00343 #else
00344 prescan_quantize (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
00345                 JSAMPARRAY output_buf, int num_rows)
00346 {
00347   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
00348 #endif
00349   register JSAMPROW ptr;
00350   register histptr histp;
00351   register hist3d histogram = cquantize->histogram;
00352   int row;
00353   JDIMENSION col;
00354 #ifdef ORIGINAL_LIB_JPEG
00355   JDIMENSION width = cinfo->output_width;
00356 #else
00357   int width = im->sx;
00358   int num_rows = im->sy;
00359 #endif
00360 
00361   for (row = 0; row < num_rows; row++)
00362     {
00363       ptr = input_buf[row];
00364       for (col = width; col > 0; col--)
00365        {
00366 #ifdef ORIGINAL_LIB_JPEG
00367          int r = GETJSAMPLE (ptr[0]) >> C0_SHIFT;
00368          int g = GETJSAMPLE (ptr[1]) >> C1_SHIFT;
00369          int b = GETJSAMPLE (ptr[2]) >> C2_SHIFT;
00370 #else
00371          int r = gdTrueColorGetRed (*ptr) >> C0_SHIFT;
00372          int g = gdTrueColorGetGreen (*ptr) >> C1_SHIFT;
00373          int b = gdTrueColorGetBlue (*ptr) >> C2_SHIFT;
00374          /* 2.0.12: Steven Brown: support a single totally transparent
00375             color in the original. */
00376          if ((im->transparent >= 0) && (*ptr == im->transparent))
00377            {
00378              ptr++;
00379              continue;
00380            }
00381 #endif
00382          /* get pixel value and index into the histogram */
00383          histp = &histogram[r][g][b];
00384          /* increment, check for overflow and undo increment if so. */
00385          if (++(*histp) == 0)
00386            (*histp)--;
00387 #ifdef ORIGINAL_LIB_JPEG
00388          ptr += 3;
00389 #else
00390          ptr++;
00391 #endif
00392        }
00393     }
00394 }
00395 
00396 
00397 /*
00398  * Next we have the really interesting routines: selection of a colormap
00399  * given the completed histogram.
00400  * These routines work with a list of "boxes", each representing a rectangular
00401  * subset of the input color space (to histogram precision).
00402  */
00403 
00404 typedef struct
00405 {
00406   /* The bounds of the box (inclusive); expressed as histogram indexes */
00407   int c0min, c0max;
00408   int c1min, c1max;
00409   int c2min, c2max;
00410   /* The volume (actually 2-norm) of the box */
00411   INT32 volume;
00412   /* The number of nonzero histogram cells within this box */
00413   long colorcount;
00414 }
00415 box;
00416 
00417 typedef box *boxptr;
00418 
00419 
00420 LOCAL (boxptr) find_biggest_color_pop (boxptr boxlist, int numboxes)
00421 /* Find the splittable box with the largest color population */
00422 /* Returns NULL if no splittable boxes remain */
00423 {
00424   register boxptr boxp;
00425   register int i;
00426   register long maxc = 0;
00427   boxptr which = NULL;
00428 
00429   for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++)
00430     {
00431       if (boxp->colorcount > maxc && boxp->volume > 0)
00432        {
00433          which = boxp;
00434          maxc = boxp->colorcount;
00435        }
00436     }
00437   return which;
00438 }
00439 
00440 
00441 LOCAL (boxptr) find_biggest_volume (boxptr boxlist, int numboxes)
00442 /* Find the splittable box with the largest (scaled) volume */
00443 /* Returns NULL if no splittable boxes remain */
00444 {
00445   register boxptr boxp;
00446   register int i;
00447   register INT32 maxv = 0;
00448   boxptr which = NULL;
00449 
00450   for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++)
00451     {
00452       if (boxp->volume > maxv)
00453        {
00454          which = boxp;
00455          maxv = boxp->volume;
00456        }
00457     }
00458   return which;
00459 }
00460 
00461 
00462 LOCAL (void)
00463 #ifndef ORIGINAL_LIB_JPEG
00464   update_box (gdImagePtr im, my_cquantize_ptr cquantize, boxptr boxp)
00465 {
00466 #else
00467   update_box (j_decompress_ptr cinfo, boxptr boxp)
00468 /* Shrink the min/max bounds of a box to enclose only nonzero elements, */
00469 /* and recompute its volume and population */
00470 {
00471   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
00472 #endif
00473   hist3d histogram = cquantize->histogram;
00474   histptr histp;
00475   int c0, c1, c2;
00476   int c0min, c0max, c1min, c1max, c2min, c2max;
00477   INT32 dist0, dist1, dist2;
00478   long ccount;
00479 
00480   c0min = boxp->c0min;
00481   c0max = boxp->c0max;
00482   c1min = boxp->c1min;
00483   c1max = boxp->c1max;
00484   c2min = boxp->c2min;
00485   c2max = boxp->c2max;
00486 
00487   if (c0max > c0min)
00488     for (c0 = c0min; c0 <= c0max; c0++)
00489       for (c1 = c1min; c1 <= c1max; c1++)
00490        {
00491          histp = &histogram[c0][c1][c2min];
00492          for (c2 = c2min; c2 <= c2max; c2++)
00493            if (*histp++ != 0)
00494              {
00495               boxp->c0min = c0min = c0;
00496               goto have_c0min;
00497              }
00498        }
00499 have_c0min:
00500   if (c0max > c0min)
00501     for (c0 = c0max; c0 >= c0min; c0--)
00502       for (c1 = c1min; c1 <= c1max; c1++)
00503        {
00504          histp = &histogram[c0][c1][c2min];
00505          for (c2 = c2min; c2 <= c2max; c2++)
00506            if (*histp++ != 0)
00507              {
00508               boxp->c0max = c0max = c0;
00509               goto have_c0max;
00510              }
00511        }
00512 have_c0max:
00513   if (c1max > c1min)
00514     for (c1 = c1min; c1 <= c1max; c1++)
00515       for (c0 = c0min; c0 <= c0max; c0++)
00516        {
00517          histp = &histogram[c0][c1][c2min];
00518          for (c2 = c2min; c2 <= c2max; c2++)
00519            if (*histp++ != 0)
00520              {
00521               boxp->c1min = c1min = c1;
00522               goto have_c1min;
00523              }
00524        }
00525 have_c1min:
00526   if (c1max > c1min)
00527     for (c1 = c1max; c1 >= c1min; c1--)
00528       for (c0 = c0min; c0 <= c0max; c0++)
00529        {
00530          histp = &histogram[c0][c1][c2min];
00531          for (c2 = c2min; c2 <= c2max; c2++)
00532            if (*histp++ != 0)
00533              {
00534               boxp->c1max = c1max = c1;
00535               goto have_c1max;
00536              }
00537        }
00538 have_c1max:
00539   if (c2max > c2min)
00540     for (c2 = c2min; c2 <= c2max; c2++)
00541       for (c0 = c0min; c0 <= c0max; c0++)
00542        {
00543          histp = &histogram[c0][c1min][c2];
00544          for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)
00545            if (*histp != 0)
00546              {
00547               boxp->c2min = c2min = c2;
00548               goto have_c2min;
00549              }
00550        }
00551 have_c2min:
00552   if (c2max > c2min)
00553     for (c2 = c2max; c2 >= c2min; c2--)
00554       for (c0 = c0min; c0 <= c0max; c0++)
00555        {
00556          histp = &histogram[c0][c1min][c2];
00557          for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)
00558            if (*histp != 0)
00559              {
00560               boxp->c2max = c2max = c2;
00561               goto have_c2max;
00562              }
00563        }
00564 have_c2max:
00565 
00566   /* Update box volume.
00567    * We use 2-norm rather than real volume here; this biases the method
00568    * against making long narrow boxes, and it has the side benefit that
00569    * a box is splittable iff norm > 0.
00570    * Since the differences are expressed in histogram-cell units,
00571    * we have to shift back to JSAMPLE units to get consistent distances;
00572    * after which, we scale according to the selected distance scale factors.
00573    */
00574   dist0 = ((c0max - c0min) << C0_SHIFT) * C0_SCALE;
00575   dist1 = ((c1max - c1min) << C1_SHIFT) * C1_SCALE;
00576   dist2 = ((c2max - c2min) << C2_SHIFT) * C2_SCALE;
00577   boxp->volume = dist0 * dist0 + dist1 * dist1 + dist2 * dist2;
00578 
00579   /* Now scan remaining volume of box and compute population */
00580   ccount = 0;
00581   for (c0 = c0min; c0 <= c0max; c0++)
00582     for (c1 = c1min; c1 <= c1max; c1++)
00583       {
00584        histp = &histogram[c0][c1][c2min];
00585        for (c2 = c2min; c2 <= c2max; c2++, histp++)
00586          if (*histp != 0)
00587            {
00588              ccount++;
00589            }
00590       }
00591   boxp->colorcount = ccount;
00592 }
00593 
00594 
00595 LOCAL (int)
00596 #ifdef ORIGINAL_LIB_JPEG
00597 median_cut (j_decompress_ptr cinfo, boxptr boxlist, int numboxes,
00598            int desired_colors)
00599 #else
00600 median_cut (gdImagePtr im, my_cquantize_ptr cquantize,
00601            boxptr boxlist, int numboxes, int desired_colors)
00602 #endif
00603 /* Repeatedly select and split the largest box until we have enough boxes */
00604 {
00605   int n, lb;
00606   int c0, c1, c2, cmax;
00607   register boxptr b1, b2;
00608 
00609   while (numboxes < desired_colors)
00610     {
00611       /* Select box to split.
00612        * Current algorithm: by population for first half, then by volume.
00613        */
00614       if (numboxes * 2 <= desired_colors)
00615        {
00616          b1 = find_biggest_color_pop (boxlist, numboxes);
00617        }
00618       else
00619        {
00620          b1 = find_biggest_volume (boxlist, numboxes);
00621        }
00622       if (b1 == NULL)              /* no splittable boxes left! */
00623        break;
00624       b2 = &boxlist[numboxes];     /* where new box will go */
00625       /* Copy the color bounds to the new box. */
00626       b2->c0max = b1->c0max;
00627       b2->c1max = b1->c1max;
00628       b2->c2max = b1->c2max;
00629       b2->c0min = b1->c0min;
00630       b2->c1min = b1->c1min;
00631       b2->c2min = b1->c2min;
00632       /* Choose which axis to split the box on.
00633        * Current algorithm: longest scaled axis.
00634        * See notes in update_box about scaling distances.
00635        */
00636       c0 = ((b1->c0max - b1->c0min) << C0_SHIFT) * C0_SCALE;
00637       c1 = ((b1->c1max - b1->c1min) << C1_SHIFT) * C1_SCALE;
00638       c2 = ((b1->c2max - b1->c2min) << C2_SHIFT) * C2_SCALE;
00639       /* We want to break any ties in favor of green, then red, blue last.
00640        * This code does the right thing for R,G,B or B,G,R color orders only.
00641        */
00642 #if RGB_RED == 0
00643       cmax = c1;
00644       n = 1;
00645       if (c0 > cmax)
00646        {
00647          cmax = c0;
00648          n = 0;
00649        }
00650       if (c2 > cmax)
00651        {
00652          n = 2;
00653        }
00654 #else
00655       cmax = c1;
00656       n = 1;
00657       if (c2 > cmax)
00658        {
00659          cmax = c2;
00660          n = 2;
00661        }
00662       if (c0 > cmax)
00663        {
00664          n = 0;
00665        }
00666 #endif
00667       /* Choose split point along selected axis, and update box bounds.
00668        * Current algorithm: split at halfway point.
00669        * (Since the box has been shrunk to minimum volume,
00670        * any split will produce two nonempty subboxes.)
00671        * Note that lb value is max for lower box, so must be < old max.
00672        */
00673       switch (n)
00674        {
00675        case 0:
00676          lb = (b1->c0max + b1->c0min) / 2;
00677          b1->c0max = lb;
00678          b2->c0min = lb + 1;
00679          break;
00680        case 1:
00681          lb = (b1->c1max + b1->c1min) / 2;
00682          b1->c1max = lb;
00683          b2->c1min = lb + 1;
00684          break;
00685        case 2:
00686          lb = (b1->c2max + b1->c2min) / 2;
00687          b1->c2max = lb;
00688          b2->c2min = lb + 1;
00689          break;
00690        }
00691       /* Update stats for boxes */
00692 #ifdef ORIGINAL_LIB_JPEG
00693       update_box (cinfo, b1);
00694       update_box (cinfo, b2);
00695 #else
00696       update_box (im, cquantize, b1);
00697       update_box (im, cquantize, b2);
00698 #endif
00699       numboxes++;
00700     }
00701   return numboxes;
00702 }
00703 
00704 
00705 LOCAL (void)
00706 #ifndef ORIGINAL_LIB_JPEG
00707   compute_color (gdImagePtr im, my_cquantize_ptr cquantize,
00708               boxptr boxp, int icolor)
00709 {
00710 #else
00711   compute_color (j_decompress_ptr cinfo, boxptr boxp, int icolor)
00712 /* Compute representative color for a box, put it in colormap[icolor] */
00713 {
00714   /* Current algorithm: mean weighted by pixels (not colors) */
00715   /* Note it is important to get the rounding correct! */
00716   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
00717 #endif
00718   hist3d histogram = cquantize->histogram;
00719   histptr histp;
00720   int c0, c1, c2;
00721   int c0min, c0max, c1min, c1max, c2min, c2max;
00722   long count;
00723   long total = 0;
00724   long c0total = 0;
00725   long c1total = 0;
00726   long c2total = 0;
00727 
00728   c0min = boxp->c0min;
00729   c0max = boxp->c0max;
00730   c1min = boxp->c1min;
00731   c1max = boxp->c1max;
00732   c2min = boxp->c2min;
00733   c2max = boxp->c2max;
00734 
00735   for (c0 = c0min; c0 <= c0max; c0++)
00736     for (c1 = c1min; c1 <= c1max; c1++)
00737       {
00738        histp = &histogram[c0][c1][c2min];
00739        for (c2 = c2min; c2 <= c2max; c2++)
00740          {
00741            if ((count = *histp++) != 0)
00742              {
00743               total += count;
00744               c0total +=
00745                 ((c0 << C0_SHIFT) + ((1 << C0_SHIFT) >> 1)) * count;
00746               c1total +=
00747                 ((c1 << C1_SHIFT) + ((1 << C1_SHIFT) >> 1)) * count;
00748               c2total +=
00749                 ((c2 << C2_SHIFT) + ((1 << C2_SHIFT) >> 1)) * count;
00750              }
00751          }
00752       }
00753 
00754 #ifdef ORIGINAL_LIB_JPEG
00755   cinfo->colormap[0][icolor] = (JSAMPLE) ((c0total + (total >> 1)) / total);
00756   cinfo->colormap[1][icolor] = (JSAMPLE) ((c1total + (total >> 1)) / total);
00757   cinfo->colormap[2][icolor] = (JSAMPLE) ((c2total + (total >> 1)) / total);
00758 #else
00759   im->red[icolor] = (int) ((c0total + (total >> 1)) / total);
00760   im->green[icolor] = (int) ((c1total + (total >> 1)) / total);
00761   im->blue[icolor] = (int) ((c2total + (total >> 1)) / total);
00762 #endif
00763 }
00764 
00765 
00766 LOCAL (void)
00767 #ifdef ORIGINAL_LIB_JPEG
00768 select_colors (j_decompress_ptr cinfo, int desired_colors)
00769 #else
00770 select_colors (gdImagePtr im, my_cquantize_ptr cquantize, int desired_colors)
00771 #endif
00772 /* Master routine for color selection */
00773 {
00774   boxptr boxlist;
00775   int numboxes;
00776   int i;
00777 
00778   /* Allocate workspace for box list */
00779 #ifdef ORIGINAL_LIB_JPEG
00780   boxlist = (boxptr) (*cinfo->mem->alloc_small)
00781     ((j_common_ptr) cinfo, JPOOL_IMAGE, desired_colors * SIZEOF (box));
00782 #else
00783   boxlist = (boxptr) gdMalloc (desired_colors * sizeof (box));
00784 #endif
00785   /* Initialize one box containing whole space */
00786   numboxes = 1;
00787   boxlist[0].c0min = 0;
00788   boxlist[0].c0max = MAXJSAMPLE >> C0_SHIFT;
00789   boxlist[0].c1min = 0;
00790   boxlist[0].c1max = MAXJSAMPLE >> C1_SHIFT;
00791   boxlist[0].c2min = 0;
00792   boxlist[0].c2max = MAXJSAMPLE >> C2_SHIFT;
00793 #ifdef ORIGINAL_LIB_JPEG
00794   /* Shrink it to actually-used volume and set its statistics */
00795   update_box (cinfo, &boxlist[0]);
00796   /* Perform median-cut to produce final box list */
00797   numboxes = median_cut (cinfo, boxlist, numboxes, desired_colors);
00798   /* Compute the representative color for each box, fill colormap */
00799   for (i = 0; i < numboxes; i++)
00800     compute_color (cinfo, &boxlist[i], i);
00801   cinfo->actual_number_of_colors = numboxes;
00802   TRACEMS1 (cinfo, 1, JTRC_QUANT_SELECTED, numboxes);
00803 #else
00804   /* Shrink it to actually-used volume and set its statistics */
00805   update_box (im, cquantize, &boxlist[0]);
00806   /* Perform median-cut to produce final box list */
00807   numboxes = median_cut (im, cquantize, boxlist, numboxes, desired_colors);
00808   /* Compute the representative color for each box, fill colormap */
00809   for (i = 0; i < numboxes; i++)
00810     compute_color (im, cquantize, &boxlist[i], i);
00811   im->colorsTotal = numboxes;
00812 
00813   /* If we had a pure transparency color, add it as the last palette entry.
00814    * Skip incrementing the color count so that the dither / matching phase
00815    * won't use it on pixels that shouldn't have been transparent.  We'll
00816    * increment it after all that finishes. */
00817   if (im->transparent >= 0)
00818     {
00819       /* Save the transparent color. */
00820       im->red[im->colorsTotal] = gdTrueColorGetRed (im->transparent);
00821       im->green[im->colorsTotal] = gdTrueColorGetGreen (im->transparent);
00822       im->blue[im->colorsTotal] = gdTrueColorGetBlue (im->transparent);
00823       im->alpha[im->colorsTotal] = gdAlphaTransparent;
00824       im->open[im->colorsTotal] = 0;
00825     }
00826 
00827   gdFree (boxlist);
00828 #endif
00829 }
00830 
00831 
00832 /*
00833  * These routines are concerned with the time-critical task of mapping input
00834  * colors to the nearest color in the selected colormap.
00835  *
00836  * We re-use the histogram space as an "inverse color map", essentially a
00837  * cache for the results of nearest-color searches.  All colors within a
00838  * histogram cell will be mapped to the same colormap entry, namely the one
00839  * closest to the cell's center.  This may not be quite the closest entry to
00840  * the actual input color, but it's almost as good.  A zero in the cache
00841  * indicates we haven't found the nearest color for that cell yet; the array
00842  * is cleared to zeroes before starting the mapping pass.  When we find the
00843  * nearest color for a cell, its colormap index plus one is recorded in the
00844  * cache for future use.  The pass2 scanning routines call fill_inverse_cmap
00845  * when they need to use an unfilled entry in the cache.
00846  *
00847  * Our method of efficiently finding nearest colors is based on the "locally
00848  * sorted search" idea described by Heckbert and on the incremental distance
00849  * calculation described by Spencer W. Thomas in chapter III.1 of Graphics
00850  * Gems II (James Arvo, ed.  Academic Press, 1991).  Thomas points out that
00851  * the distances from a given colormap entry to each cell of the histogram can
00852  * be computed quickly using an incremental method: the differences between
00853  * distances to adjacent cells themselves differ by a constant.  This allows a
00854  * fairly fast implementation of the "brute force" approach of computing the
00855  * distance from every colormap entry to every histogram cell.  Unfortunately,
00856  * it needs a work array to hold the best-distance-so-far for each histogram
00857  * cell (because the inner loop has to be over cells, not colormap entries).
00858  * The work array elements have to be INT32s, so the work array would need
00859  * 256Kb at our recommended precision.  This is not feasible in DOS machines.
00860  *
00861  * To get around these problems, we apply Thomas' method to compute the
00862  * nearest colors for only the cells within a small subbox of the histogram.
00863  * The work array need be only as big as the subbox, so the memory usage
00864  * problem is solved.  Furthermore, we need not fill subboxes that are never
00865  * referenced in pass2; many images use only part of the color gamut, so a
00866  * fair amount of work is saved.  An additional advantage of this
00867  * approach is that we can apply Heckbert's locality criterion to quickly
00868  * eliminate colormap entries that are far away from the subbox; typically
00869  * three-fourths of the colormap entries are rejected by Heckbert's criterion,
00870  * and we need not compute their distances to individual cells in the subbox.
00871  * The speed of this approach is heavily influenced by the subbox size: too
00872  * small means too much overhead, too big loses because Heckbert's criterion
00873  * can't eliminate as many colormap entries.  Empirically the best subbox
00874  * size seems to be about 1/512th of the histogram (1/8th in each direction).
00875  *
00876  * Thomas' article also describes a refined method which is asymptotically
00877  * faster than the brute-force method, but it is also far more complex and
00878  * cannot efficiently be applied to small subboxes.  It is therefore not
00879  * useful for programs intended to be portable to DOS machines.  On machines
00880  * with plenty of memory, filling the whole histogram in one shot with Thomas'
00881  * refined method might be faster than the present code --- but then again,
00882  * it might not be any faster, and it's certainly more complicated.
00883  */
00884 
00885 
00886 /* log2(histogram cells in update box) for each axis; this can be adjusted */
00887 #define BOX_C0_LOG  (HIST_C0_BITS-3)
00888 #define BOX_C1_LOG  (HIST_C1_BITS-3)
00889 #define BOX_C2_LOG  (HIST_C2_BITS-3)
00890 
00891 #define BOX_C0_ELEMS  (1<<BOX_C0_LOG)     /* # of hist cells in update box */
00892 #define BOX_C1_ELEMS  (1<<BOX_C1_LOG)
00893 #define BOX_C2_ELEMS  (1<<BOX_C2_LOG)
00894 
00895 #define BOX_C0_SHIFT  (C0_SHIFT + BOX_C0_LOG)
00896 #define BOX_C1_SHIFT  (C1_SHIFT + BOX_C1_LOG)
00897 #define BOX_C2_SHIFT  (C2_SHIFT + BOX_C2_LOG)
00898 
00899 
00900 /*
00901  * The next three routines implement inverse colormap filling.  They could
00902  * all be folded into one big routine, but splitting them up this way saves
00903  * some stack space (the mindist[] and bestdist[] arrays need not coexist)
00904  * and may allow some compilers to produce better code by registerizing more
00905  * inner-loop variables.
00906  */
00907 
00908 LOCAL (int)
00909 find_nearby_colors (
00910 #ifdef ORIGINAL_LIB_JPEG
00911                    j_decompress_ptr cinfo,
00912 #else
00913                    gdImagePtr im, my_cquantize_ptr cquantize,
00914 #endif
00915                    int minc0, int minc1, int minc2, JSAMPLE colorlist[])
00916 /* Locate the colormap entries close enough to an update box to be candidates
00917  * for the nearest entry to some cell(s) in the update box.  The update box
00918  * is specified by the center coordinates of its first cell.  The number of
00919  * candidate colormap entries is returned, and their colormap indexes are
00920  * placed in colorlist[].
00921  * This routine uses Heckbert's "locally sorted search" criterion to select
00922  * the colors that need further consideration.
00923  */
00924 {
00925 #ifdef ORIGINAL_LIB_JPEG
00926   int numcolors = cinfo->actual_number_of_colors;
00927 #else
00928   int numcolors = im->colorsTotal;
00929 #endif
00930   int maxc0, maxc1, maxc2;
00931   int centerc0, centerc1, centerc2;
00932   int i, x, ncolors;
00933   INT32 minmaxdist, min_dist, max_dist, tdist;
00934   INT32 mindist[MAXNUMCOLORS];     /* min distance to colormap entry i */
00935 
00936   /* Compute true coordinates of update box's upper corner and center.
00937    * Actually we compute the coordinates of the center of the upper-corner
00938    * histogram cell, which are the upper bounds of the volume we care about.
00939    * Note that since ">>" rounds down, the "center" values may be closer to
00940    * min than to max; hence comparisons to them must be "<=", not "<".
00941    */
00942   maxc0 = minc0 + ((1 << BOX_C0_SHIFT) - (1 << C0_SHIFT));
00943   centerc0 = (minc0 + maxc0) >> 1;
00944   maxc1 = minc1 + ((1 << BOX_C1_SHIFT) - (1 << C1_SHIFT));
00945   centerc1 = (minc1 + maxc1) >> 1;
00946   maxc2 = minc2 + ((1 << BOX_C2_SHIFT) - (1 << C2_SHIFT));
00947   centerc2 = (minc2 + maxc2) >> 1;
00948 
00949   /* For each color in colormap, find:
00950    *  1. its minimum squared-distance to any point in the update box
00951    *     (zero if color is within update box);
00952    *  2. its maximum squared-distance to any point in the update box.
00953    * Both of these can be found by considering only the corners of the box.
00954    * We save the minimum distance for each color in mindist[];
00955    * only the smallest maximum distance is of interest.
00956    */
00957   minmaxdist = 0x7FFFFFFFL;
00958 
00959   for (i = 0; i < numcolors; i++)
00960     {
00961       /* We compute the squared-c0-distance term, then add in the other two. */
00962 #ifdef ORIGINAL_LIB_JPEG
00963       x = GETJSAMPLE (cinfo->colormap[0][i]);
00964 #else
00965       x = im->red[i];
00966 #endif
00967       if (x < minc0)
00968        {
00969          tdist = (x - minc0) * C0_SCALE;
00970          min_dist = tdist * tdist;
00971          tdist = (x - maxc0) * C0_SCALE;
00972          max_dist = tdist * tdist;
00973        }
00974       else if (x > maxc0)
00975        {
00976          tdist = (x - maxc0) * C0_SCALE;
00977          min_dist = tdist * tdist;
00978          tdist = (x - minc0) * C0_SCALE;
00979          max_dist = tdist * tdist;
00980        }
00981       else
00982        {
00983          /* within cell range so no contribution to min_dist */
00984          min_dist = 0;
00985          if (x <= centerc0)
00986            {
00987              tdist = (x - maxc0) * C0_SCALE;
00988              max_dist = tdist * tdist;
00989            }
00990          else
00991            {
00992              tdist = (x - minc0) * C0_SCALE;
00993              max_dist = tdist * tdist;
00994            }
00995        }
00996 
00997 #ifdef ORIGINAL_LIB_JPEG
00998       x = GETJSAMPLE (cinfo->colormap[1][i]);
00999 #else
01000       x = im->green[i];
01001 #endif
01002       if (x < minc1)
01003        {
01004          tdist = (x - minc1) * C1_SCALE;
01005          min_dist += tdist * tdist;
01006          tdist = (x - maxc1) * C1_SCALE;
01007          max_dist += tdist * tdist;
01008        }
01009       else if (x > maxc1)
01010        {
01011          tdist = (x - maxc1) * C1_SCALE;
01012          min_dist += tdist * tdist;
01013          tdist = (x - minc1) * C1_SCALE;
01014          max_dist += tdist * tdist;
01015        }
01016       else
01017        {
01018          /* within cell range so no contribution to min_dist */
01019          if (x <= centerc1)
01020            {
01021              tdist = (x - maxc1) * C1_SCALE;
01022              max_dist += tdist * tdist;
01023            }
01024          else
01025            {
01026              tdist = (x - minc1) * C1_SCALE;
01027              max_dist += tdist * tdist;
01028            }
01029        }
01030 
01031 #ifdef ORIGINAL_LIB_JPEG
01032       x = GETJSAMPLE (cinfo->colormap[2][i]);
01033 #else
01034       x = im->blue[i];
01035 #endif
01036       if (x < minc2)
01037        {
01038          tdist = (x - minc2) * C2_SCALE;
01039          min_dist += tdist * tdist;
01040          tdist = (x - maxc2) * C2_SCALE;
01041          max_dist += tdist * tdist;
01042        }
01043       else if (x > maxc2)
01044        {
01045          tdist = (x - maxc2) * C2_SCALE;
01046          min_dist += tdist * tdist;
01047          tdist = (x - minc2) * C2_SCALE;
01048          max_dist += tdist * tdist;
01049        }
01050       else
01051        {
01052          /* within cell range so no contribution to min_dist */
01053          if (x <= centerc2)
01054            {
01055              tdist = (x - maxc2) * C2_SCALE;
01056              max_dist += tdist * tdist;
01057            }
01058          else
01059            {
01060              tdist = (x - minc2) * C2_SCALE;
01061              max_dist += tdist * tdist;
01062            }
01063        }
01064 
01065       mindist[i] = min_dist;       /* save away the results */
01066       if (max_dist < minmaxdist)
01067        minmaxdist = max_dist;
01068     }
01069 
01070   /* Now we know that no cell in the update box is more than minmaxdist
01071    * away from some colormap entry.  Therefore, only colors that are
01072    * within minmaxdist of some part of the box need be considered.
01073    */
01074   ncolors = 0;
01075   for (i = 0; i < numcolors; i++)
01076     {
01077       if (mindist[i] <= minmaxdist)
01078        colorlist[ncolors++] = (JSAMPLE) i;
01079     }
01080   return ncolors;
01081 }
01082 
01083 
01084 LOCAL (void) find_best_colors (
01085 #ifdef ORIGINAL_LIB_JPEG
01086                             j_decompress_ptr cinfo,
01087 #else
01088                             gdImagePtr im, my_cquantize_ptr cquantize,
01089 #endif
01090                             int minc0, int minc1, int minc2,
01091                             int numcolors, JSAMPLE colorlist[],
01092                             JSAMPLE bestcolor[])
01093 /* Find the closest colormap entry for each cell in the update box,
01094  * given the list of candidate colors prepared by find_nearby_colors.
01095  * Return the indexes of the closest entries in the bestcolor[] array.
01096  * This routine uses Thomas' incremental distance calculation method to
01097  * find the distance from a colormap entry to successive cells in the box.
01098  */
01099 {
01100   int ic0, ic1, ic2;
01101   int i, icolor;
01102   register INT32 *bptr;            /* pointer into bestdist[] array */
01103   JSAMPLE *cptr;            /* pointer into bestcolor[] array */
01104   INT32 dist0, dist1;              /* initial distance values */
01105   register INT32 dist2;            /* current distance in inner loop */
01106   INT32 xx0, xx1;           /* distance increments */
01107   register INT32 xx2;
01108   INT32 inc0, inc1, inc2;   /* initial values for increments */
01109   /* This array holds the distance to the nearest-so-far color for each cell */
01110   INT32 bestdist[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS];
01111 
01112   /* Initialize best-distance for each cell of the update box */
01113   bptr = bestdist;
01114   for (i = BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS - 1; i >= 0; i--)
01115     *bptr++ = 0x7FFFFFFFL;
01116 
01117   /* For each color selected by find_nearby_colors,
01118    * compute its distance to the center of each cell in the box.
01119    * If that's less than best-so-far, update best distance and color number.
01120    */
01121 
01122   /* Nominal steps between cell centers ("x" in Thomas article) */
01123 #define STEP_C0  ((1 << C0_SHIFT) * C0_SCALE)
01124 #define STEP_C1  ((1 << C1_SHIFT) * C1_SCALE)
01125 #define STEP_C2  ((1 << C2_SHIFT) * C2_SCALE)
01126 
01127   for (i = 0; i < numcolors; i++)
01128     {
01129       int r, g, b;
01130 #ifdef ORIGINAL_LIB_JPEG
01131 
01132       icolor = GETJSAMPLE (colorlist[i]);
01133       r = GETJSAMPLE (cinfo->colormap[0][icolor]);
01134       g = GETJSAMPLE (cinfo->colormap[1][icolor]);
01135       b = GETJSAMPLE (cinfo->colormap[2][icolor]);
01136 #else
01137       icolor = colorlist[i];
01138       r = im->red[icolor];
01139       g = im->green[icolor];
01140       b = im->blue[icolor];
01141 #endif
01142 
01143       /* Compute (square of) distance from minc0/c1/c2 to this color */
01144       inc0 = (minc0 - r) * C0_SCALE;
01145       dist0 = inc0 * inc0;
01146       inc1 = (minc1 - g) * C1_SCALE;
01147       dist0 += inc1 * inc1;
01148       inc2 = (minc2 - b) * C2_SCALE;
01149       dist0 += inc2 * inc2;
01150       /* Form the initial difference increments */
01151       inc0 = inc0 * (2 * STEP_C0) + STEP_C0 * STEP_C0;
01152       inc1 = inc1 * (2 * STEP_C1) + STEP_C1 * STEP_C1;
01153       inc2 = inc2 * (2 * STEP_C2) + STEP_C2 * STEP_C2;
01154       /* Now loop over all cells in box, updating distance per Thomas method */
01155       bptr = bestdist;
01156       cptr = bestcolor;
01157       xx0 = inc0;
01158       for (ic0 = BOX_C0_ELEMS - 1; ic0 >= 0; ic0--)
01159        {
01160          dist1 = dist0;
01161          xx1 = inc1;
01162          for (ic1 = BOX_C1_ELEMS - 1; ic1 >= 0; ic1--)
01163            {
01164              dist2 = dist1;
01165              xx2 = inc2;
01166              for (ic2 = BOX_C2_ELEMS - 1; ic2 >= 0; ic2--)
01167               {
01168                 if (dist2 < *bptr)
01169                   {
01170                     *bptr = dist2;
01171                     *cptr = (JSAMPLE) icolor;
01172                   }
01173                 dist2 += xx2;
01174                 xx2 += 2 * STEP_C2 * STEP_C2;
01175                 bptr++;
01176                 cptr++;
01177               }
01178              dist1 += xx1;
01179              xx1 += 2 * STEP_C1 * STEP_C1;
01180            }
01181          dist0 += xx0;
01182          xx0 += 2 * STEP_C0 * STEP_C0;
01183        }
01184     }
01185 }
01186 
01187 
01188 LOCAL (void)
01189 fill_inverse_cmap (
01190 #ifdef ORIGINAL_LIB_JPEG
01191                   j_decompress_ptr cinfo,
01192 #else
01193                   gdImagePtr im, my_cquantize_ptr cquantize,
01194 #endif
01195                   int c0, int c1, int c2)
01196 /* Fill the inverse-colormap entries in the update box that contains */
01197 /* histogram cell c0/c1/c2.  (Only that one cell MUST be filled, but */
01198 /* we can fill as many others as we wish.) */
01199 {
01200 #ifdef ORIGINAL_LIB_JPEG
01201   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
01202 #endif
01203   hist3d histogram = cquantize->histogram;
01204   int minc0, minc1, minc2;  /* lower left corner of update box */
01205   int ic0, ic1, ic2;
01206   register JSAMPLE *cptr;   /* pointer into bestcolor[] array */
01207   register histptr cachep;  /* pointer into main cache array */
01208   /* This array lists the candidate colormap indexes. */
01209   JSAMPLE colorlist[MAXNUMCOLORS];
01210   int numcolors;            /* number of candidate colors */
01211   /* This array holds the actually closest colormap index for each cell. */
01212   JSAMPLE bestcolor[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS];
01213 
01214   /* Convert cell coordinates to update box ID */
01215   c0 >>= BOX_C0_LOG;
01216   c1 >>= BOX_C1_LOG;
01217   c2 >>= BOX_C2_LOG;
01218 
01219   /* Compute true coordinates of update box's origin corner.
01220    * Actually we compute the coordinates of the center of the corner
01221    * histogram cell, which are the lower bounds of the volume we care about.
01222    */
01223   minc0 = (c0 << BOX_C0_SHIFT) + ((1 << C0_SHIFT) >> 1);
01224   minc1 = (c1 << BOX_C1_SHIFT) + ((1 << C1_SHIFT) >> 1);
01225   minc2 = (c2 << BOX_C2_SHIFT) + ((1 << C2_SHIFT) >> 1);
01226 
01227   /* Determine which colormap entries are close enough to be candidates
01228    * for the nearest entry to some cell in the update box.
01229    */
01230 #ifdef ORIGINAL_LIB_JPEG
01231   numcolors = find_nearby_colors (cinfo, minc0, minc1, minc2, colorlist);
01232 
01233   /* Determine the actually nearest colors. */
01234   find_best_colors (cinfo, minc0, minc1, minc2, numcolors, colorlist,
01235                   bestcolor);
01236 #else
01237   numcolors =
01238     find_nearby_colors (im, cquantize, minc0, minc1, minc2, colorlist);
01239   find_best_colors (im, cquantize, minc0, minc1, minc2, numcolors,
01240                   colorlist, bestcolor);
01241 #endif
01242 
01243   /* Save the best color numbers (plus 1) in the main cache array */
01244   c0 <<= BOX_C0_LOG;        /* convert ID back to base cell indexes */
01245   c1 <<= BOX_C1_LOG;
01246   c2 <<= BOX_C2_LOG;
01247   cptr = bestcolor;
01248   for (ic0 = 0; ic0 < BOX_C0_ELEMS; ic0++)
01249     {
01250       for (ic1 = 0; ic1 < BOX_C1_ELEMS; ic1++)
01251        {
01252          cachep = &histogram[c0 + ic0][c1 + ic1][c2];
01253          for (ic2 = 0; ic2 < BOX_C2_ELEMS; ic2++)
01254            {
01255 #ifdef ORIGINAL_LIB_JPEG
01256              *cachep++ = (histcell) (GETJSAMPLE (*cptr++) + 1);
01257 #else
01258              *cachep++ = (histcell) ((*cptr++) + 1);
01259 #endif
01260            }
01261        }
01262     }
01263 }
01264 
01265 
01266 /*
01267  * Map some rows of pixels to the output colormapped representation.
01268  */
01269 
01270 METHODDEF (void)
01271 #ifndef ORIGINAL_LIB_JPEG
01272 pass2_no_dither (gdImagePtr im, my_cquantize_ptr cquantize)
01273 {
01274   register int *inptr;
01275   register unsigned char *outptr;
01276   int width = im->sx;
01277   int num_rows = im->sy;
01278 #else
01279 pass2_no_dither (j_decompress_ptr cinfo,
01280                JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows)
01281 /* This version performs no dithering */
01282 {
01283   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
01284   register JSAMPROW inptr, outptr;
01285   JDIMENSION width = cinfo->output_width;
01286 #endif
01287   hist3d histogram = cquantize->histogram;
01288   register int c0, c1, c2;
01289   int row;
01290   JDIMENSION col;
01291   register histptr cachep;
01292 
01293 
01294   for (row = 0; row < num_rows; row++)
01295     {
01296       inptr = input_buf[row];
01297       outptr = output_buf[row];
01298       for (col = width; col > 0; col--)
01299        {
01300          /* get pixel value and index into the cache */
01301          int r, g, b;
01302 #ifdef ORIGINAL_LIB_JPEG
01303          r = GETJSAMPLE (*inptr++);
01304          g = GETJSAMPLE (*inptr++);
01305          b = GETJSAMPLE (*inptr++);
01306 #else
01307          r = gdTrueColorGetRed (*inptr);
01308          g = gdTrueColorGetGreen (*inptr);
01309          b = gdTrueColorGetBlue (*inptr++);
01310 
01311          /* If the pixel is transparent, we assign it the palette index that
01312           * will later be added at the end of the palette as the transparent
01313           * index. */
01314          if ((im->transparent >= 0) && (im->transparent == *inptr))
01315            {
01316              *outptr++ = im->colorsTotal;
01317              continue;
01318            }
01319 #endif
01320          c0 = r >> C0_SHIFT;
01321          c1 = g >> C1_SHIFT;
01322          c2 = b >> C2_SHIFT;
01323          cachep = &histogram[c0][c1][c2];
01324          /* If we have not seen this color before, find nearest colormap entry */
01325          /* and update the cache */
01326          if (*cachep == 0)
01327 #ifdef ORIGINAL_LIB_JPEG
01328            fill_inverse_cmap (cinfo, c0, c1, c2);
01329 #else
01330            fill_inverse_cmap (im, cquantize, c0, c1, c2);
01331 #endif
01332          /* Now emit the colormap index for this cell */
01333 #ifdef ORIGINAL_LIB_JPEG
01334          *outptr++ = (JSAMPLE) (*cachep - 1);
01335 #else
01336          *outptr++ = (*cachep - 1);
01337 #endif
01338        }
01339     }
01340 }
01341 
01342 
01343 METHODDEF (void)
01344 #ifndef ORIGINAL_LIB_JPEG
01345 pass2_fs_dither (gdImagePtr im, my_cquantize_ptr cquantize)
01346 {
01347 #else
01348 pass2_fs_dither (j_decompress_ptr cinfo,
01349                JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows)
01350 /* This version performs Floyd-Steinberg dithering */
01351 {
01352   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
01353   JSAMPROW inptr;           /* => current input pixel */
01354 #endif
01355   hist3d histogram = cquantize->histogram;
01356   register LOCFSERROR cur0, cur1, cur2;   /* current error or pixel value */
01357   LOCFSERROR belowerr0, belowerr1, belowerr2;    /* error for pixel below cur */
01358   LOCFSERROR bpreverr0, bpreverr1, bpreverr2;    /* error for below/prev col */
01359   register FSERRPTR errorptr;      /* => fserrors[] at column before current */
01360   histptr cachep;
01361   int dir;                  /* +1 or -1 depending on direction */
01362   int dir3;                 /* 3*dir, for advancing inptr & errorptr */
01363   int row;
01364   JDIMENSION col;
01365 #ifdef ORIGINAL_LIB_JPEG
01366   JSAMPROW outptr;          /* => current output pixel */
01367   JDIMENSION width = cinfo->output_width;
01368   JSAMPLE *range_limit = cinfo->sample_range_limit;
01369   JSAMPROW colormap0 = cinfo->colormap[0];
01370   JSAMPROW colormap1 = cinfo->colormap[1];
01371   JSAMPROW colormap2 = cinfo->colormap[2];
01372 #else
01373   int *inptr;               /* => current input pixel */
01374   unsigned char *outptr;    /* => current output pixel */
01375   int width = im->sx;
01376   int num_rows = im->sy;
01377   int *colormap0 = im->red;
01378   int *colormap1 = im->green;
01379   int *colormap2 = im->blue;
01380 #endif
01381   int *error_limit = cquantize->error_limiter;
01382 
01383 
01384   SHIFT_TEMPS for (row = 0; row < num_rows; row++)
01385     {
01386       inptr = input_buf[row];
01387       outptr = output_buf[row];
01388       if (cquantize->on_odd_row)
01389        {
01390          /* work right to left in this row */
01391          inptr += (width - 1) * 3; /* so point to rightmost pixel */
01392          outptr += width - 1;
01393          dir = -1;
01394          dir3 = -3;
01395          errorptr = cquantize->fserrors + (width + 1) * 3;     /* => entry after last column */
01396 #ifdef ORIGINAL_LIB_JPEG_REVERSE_ODD_ROWS
01397          cquantize->on_odd_row = FALSE;   /* flip for next time */
01398 #endif
01399        }
01400       else
01401        {
01402          /* work left to right in this row */
01403          dir = 1;
01404          dir3 = 3;
01405          errorptr = cquantize->fserrors;  /* => entry before first real column */
01406 #ifdef ORIGINAL_LIB_JPEG_REVERSE_ODD_ROWS
01407          cquantize->on_odd_row = TRUE;    /* flip for next time */
01408 #endif
01409        }
01410       /* Preset error values: no error propagated to first pixel from left */
01411       cur0 = cur1 = cur2 = 0;
01412       /* and no error propagated to row below yet */
01413       belowerr0 = belowerr1 = belowerr2 = 0;
01414       bpreverr0 = bpreverr1 = bpreverr2 = 0;
01415 
01416       for (col = width; col > 0; col--)
01417        {
01418 
01419          /* If this pixel is transparent, we want to assign it to the special
01420           * transparency color index past the end of the palette rather than
01421           * go through matching / dithering. */
01422          if ((im->transparent >= 0) && (*inptr == im->transparent))
01423            {
01424              *outptr = im->colorsTotal;
01425              errorptr[0] = 0;
01426              errorptr[1] = 0;
01427              errorptr[2] = 0;
01428              errorptr[3] = 0;
01429              inptr += dir;
01430              outptr += dir;
01431              errorptr += dir3;
01432              continue;
01433            }
01434          /* curN holds the error propagated from the previous pixel on the
01435           * current line.  Add the error propagated from the previous line
01436           * to form the complete error correction term for this pixel, and
01437           * round the error term (which is expressed * 16) to an integer.
01438           * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct
01439           * for either sign of the error value.
01440           * Note: errorptr points to *previous* column's array entry.
01441           */
01442          cur0 = RIGHT_SHIFT (cur0 + errorptr[dir3 + 0] + 8, 4);
01443          cur1 = RIGHT_SHIFT (cur1 + errorptr[dir3 + 1] + 8, 4);
01444          cur2 = RIGHT_SHIFT (cur2 + errorptr[dir3 + 2] + 8, 4);
01445          /* Limit the error using transfer function set by init_error_limit.
01446           * See comments with init_error_limit for rationale.
01447           */
01448          cur0 = error_limit[cur0];
01449          cur1 = error_limit[cur1];
01450          cur2 = error_limit[cur2];
01451          /* Form pixel value + error, and range-limit to 0..MAXJSAMPLE.
01452           * The maximum error is +- MAXJSAMPLE (or less with error limiting);
01453           * this sets the required size of the range_limit array.
01454           */
01455 #ifdef ORIGINAL_LIB_JPEG
01456          cur0 += GETJSAMPLE (inptr[0]);
01457          cur1 += GETJSAMPLE (inptr[1]);
01458          cur2 += GETJSAMPLE (inptr[2]);
01459          cur0 = GETJSAMPLE (range_limit[cur0]);
01460          cur1 = GETJSAMPLE (range_limit[cur1]);
01461          cur2 = GETJSAMPLE (range_limit[cur2]);
01462 #else
01463          cur0 += gdTrueColorGetRed (*inptr);
01464          cur1 += gdTrueColorGetGreen (*inptr);
01465          cur2 += gdTrueColorGetBlue (*inptr);
01466          range_limit (cur0);
01467          range_limit (cur1);
01468          range_limit (cur2);
01469 #endif
01470 
01471          /* Index into the cache with adjusted pixel value */
01472          cachep =
01473            &histogram[cur0 >> C0_SHIFT][cur1 >> C1_SHIFT][cur2 >> C2_SHIFT];
01474          /* If we have not seen this color before, find nearest colormap */
01475          /* entry and update the cache */
01476          if (*cachep == 0)
01477 #ifdef ORIGINAL_LIB_JPEG
01478            fill_inverse_cmap (cinfo, cur0 >> C0_SHIFT, cur1 >> C1_SHIFT,
01479                             cur2 >> C2_SHIFT);
01480 #else
01481            fill_inverse_cmap (im, cquantize, cur0 >> C0_SHIFT,
01482                             cur1 >> C1_SHIFT, cur2 >> C2_SHIFT);
01483 #endif
01484          /* Now emit the colormap index for this cell */
01485          {
01486            register int pixcode = *cachep - 1;
01487            *outptr = (JSAMPLE) pixcode;
01488            /* Compute representation error for this pixel */
01489 #define GETJSAMPLE
01490            cur0 -= GETJSAMPLE (colormap0[pixcode]);
01491            cur1 -= GETJSAMPLE (colormap1[pixcode]);
01492            cur2 -= GETJSAMPLE (colormap2[pixcode]);
01493 #undef GETJSAMPLE
01494          }
01495          /* Compute error fractions to be propagated to adjacent pixels.
01496           * Add these into the running sums, and simultaneously shift the
01497           * next-line error sums left by 1 column.
01498           */
01499          {
01500            register LOCFSERROR bnexterr, delta;
01501 
01502            bnexterr = cur0; /* Process component 0 */
01503            delta = cur0 * 2;
01504            cur0 += delta;   /* form error * 3 */
01505            errorptr[0] = (FSERROR) (bpreverr0 + cur0);
01506            cur0 += delta;   /* form error * 5 */
01507            bpreverr0 = belowerr0 + cur0;
01508            belowerr0 = bnexterr;
01509            cur0 += delta;   /* form error * 7 */
01510            bnexterr = cur1; /* Process component 1 */
01511            delta = cur1 * 2;
01512            cur1 += delta;   /* form error * 3 */
01513            errorptr[1] = (FSERROR) (bpreverr1 + cur1);
01514            cur1 += delta;   /* form error * 5 */
01515            bpreverr1 = belowerr1 + cur1;
01516            belowerr1 = bnexterr;
01517            cur1 += delta;   /* form error * 7 */
01518            bnexterr = cur2; /* Process component 2 */
01519            delta = cur2 * 2;
01520            cur2 += delta;   /* form error * 3 */
01521            errorptr[2] = (FSERROR) (bpreverr2 + cur2);
01522            cur2 += delta;   /* form error * 5 */
01523            bpreverr2 = belowerr2 + cur2;
01524            belowerr2 = bnexterr;
01525            cur2 += delta;   /* form error * 7 */
01526          }
01527          /* At this point curN contains the 7/16 error value to be propagated
01528           * to the next pixel on the current line, and all the errors for the
01529           * next line have been shifted over.  We are therefore ready to move on.
01530           */
01531 #ifdef ORIGINAL_LIB_JPEG
01532          inptr += dir3;     /* Advance pixel pointers to next column */
01533 #else
01534          inptr += dir;             /* Advance pixel pointers to next column */
01535 #endif
01536          outptr += dir;
01537          errorptr += dir3;  /* advance errorptr to current column */
01538        }
01539       /* Post-loop cleanup: we must unload the final error values into the
01540        * final fserrors[] entry.  Note we need not unload belowerrN because
01541        * it is for the dummy column before or after the actual array.
01542        */
01543       errorptr[0] = (FSERROR) bpreverr0;  /* unload prev errs into array */
01544       errorptr[1] = (FSERROR) bpreverr1;
01545       errorptr[2] = (FSERROR) bpreverr2;
01546     }
01547 }
01548 
01549 
01550 /*
01551  * Initialize the error-limiting transfer function (lookup table).
01552  * The raw F-S error computation can potentially compute error values of up to
01553  * +- MAXJSAMPLE.  But we want the maximum correction applied to a pixel to be
01554  * much less, otherwise obviously wrong pixels will be created.  (Typical
01555  * effects include weird fringes at color-area boundaries, isolated bright
01556  * pixels in a dark area, etc.)  The standard advice for avoiding this problem
01557  * is to ensure that the "corners" of the color cube are allocated as output
01558  * colors; then repeated errors in the same direction cannot cause cascading
01559  * error buildup.  However, that only prevents the error from getting
01560  * completely out of hand; Aaron Giles reports that error limiting improves
01561  * the results even with corner colors allocated.
01562  * A simple clamping of the error values to about +- MAXJSAMPLE/8 works pretty
01563  * well, but the smoother transfer function used below is even better.  Thanks
01564  * to Aaron Giles for this idea.
01565  */
01566 
01567 LOCAL (void)
01568 #ifdef ORIGINAL_LIB_JPEG
01569 init_error_limit (j_decompress_ptr cinfo)
01570 #else
01571 init_error_limit (gdImagePtr im, my_cquantize_ptr cquantize)
01572 #endif
01573 /* Allocate and fill in the error_limiter table */
01574 {
01575   int *table;
01576   int in, out;
01577 #ifdef ORIGINAL_LIB_JPEG
01578   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
01579   table = (int *) (*cinfo->mem->alloc_small)
01580     ((j_common_ptr) cinfo, JPOOL_IMAGE, (MAXJSAMPLE * 2 + 1) * SIZEOF (int));
01581 #else
01582   cquantize->error_limiter_storage =
01583     (int *) gdMalloc ((MAXJSAMPLE * 2 + 1) * sizeof (int));
01584   if (!cquantize->error_limiter_storage)
01585     {
01586       return;
01587     }
01588   table = cquantize->error_limiter_storage;
01589 #endif
01590 
01591   table += MAXJSAMPLE;             /* so can index -MAXJSAMPLE .. +MAXJSAMPLE */
01592   cquantize->error_limiter = table;
01593 
01594 #define STEPSIZE ((MAXJSAMPLE+1)/16)
01595   /* Map errors 1:1 up to +- MAXJSAMPLE/16 */
01596   out = 0;
01597   for (in = 0; in < STEPSIZE; in++, out++)
01598     {
01599       table[in] = out;
01600       table[-in] = -out;
01601     }
01602   /* Map errors 1:2 up to +- 3*MAXJSAMPLE/16 */
01603   for (; in < STEPSIZE * 3; in++, out += (in & 1) ? 0 : 1)
01604     {
01605       table[in] = out;
01606       table[-in] = -out;
01607     }
01608   /* Clamp the rest to final out value (which is (MAXJSAMPLE+1)/8) */
01609   for (; in <= MAXJSAMPLE; in++)
01610     {
01611       table[in] = out;
01612       table[-in] = -out;
01613     }
01614 #undef STEPSIZE
01615 }
01616 
01617 
01618 /*
01619  * Finish up at the end of each pass.
01620  */
01621 
01622 #ifdef ORIGINAL_LIB_JPEG
01623 METHODDEF (void)
01624 finish_pass1 (j_decompress_ptr cinfo)
01625 {
01626   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
01627 
01628   /* Select the representative colors and fill in cinfo->colormap */
01629   cinfo->colormap = cquantize->sv_colormap;
01630   select_colors (cinfo, cquantize->desired);
01631   /* Force next pass to zero the color index table */
01632   cquantize->needs_zeroed = TRUE;
01633 }
01634 
01635 
01636 METHODDEF (void)
01637 finish_pass2 (j_decompress_ptr cinfo)
01638 {
01639   /* no work */
01640 }
01641 
01642 /*
01643  * Initialize for each processing pass.
01644  */
01645 
01646 METHODDEF (void)
01647 start_pass_2_quant (j_decompress_ptr cinfo, boolean is_pre_scan)
01648 {
01649   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
01650   hist3d histogram = cquantize->histogram;
01651   int i;
01652 
01653   /* Only F-S dithering or no dithering is supported. */
01654   /* If user asks for ordered dither, give him F-S. */
01655   if (cinfo->dither_mode != JDITHER_NONE)
01656     cinfo->dither_mode = JDITHER_FS;
01657 
01658   if (is_pre_scan)
01659     {
01660       /* Set up method pointers */
01661       cquantize->pub.color_quantize = prescan_quantize;
01662       cquantize->pub.finish_pass = finish_pass1;
01663       cquantize->needs_zeroed = TRUE;     /* Always zero histogram */
01664     }
01665   else
01666     {
01667       /* Set up method pointers */
01668       if (cinfo->dither_mode == JDITHER_FS)
01669        cquantize->pub.color_quantize = pass2_fs_dither;
01670       else
01671        cquantize->pub.color_quantize = pass2_no_dither;
01672       cquantize->pub.finish_pass = finish_pass2;
01673 
01674       /* Make sure color count is acceptable */
01675       i = cinfo->actual_number_of_colors;
01676       if (i < 1)
01677        ERREXIT1 (cinfo, JERR_QUANT_FEW_COLORS, 1);
01678       if (i > MAXNUMCOLORS)
01679        ERREXIT1 (cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS);
01680 
01681       if (cinfo->dither_mode == JDITHER_FS)
01682        {
01683          size_t arraysize = (size_t) ((cinfo->output_width + 2) *
01684                                    (3 * SIZEOF (FSERROR)));
01685          /* Allocate Floyd-Steinberg workspace if we didn't already. */
01686          if (cquantize->fserrors == NULL)
01687            cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large)
01688              ((j_common_ptr) cinfo, JPOOL_IMAGE, arraysize);
01689          /* Initialize the propagated errors to zero. */
01690          jzero_far ((void FAR *) cquantize->fserrors, arraysize);
01691          /* Make the error-limit table if we didn't already. */
01692          if (cquantize->error_limiter == NULL)
01693            init_error_limit (cinfo);
01694          cquantize->on_odd_row = FALSE;
01695        }
01696 
01697     }
01698   /* Zero the histogram or inverse color map, if necessary */
01699   if (cquantize->needs_zeroed)
01700     {
01701       for (i = 0; i < HIST_C0_ELEMS; i++)
01702        {
01703          jzero_far ((void FAR *) histogram[i],
01704                    HIST_C1_ELEMS * HIST_C2_ELEMS * SIZEOF (histcell));
01705        }
01706       cquantize->needs_zeroed = FALSE;
01707     }
01708 }
01709 
01710 
01711 /*
01712  * Switch to a new external colormap between output passes.
01713  */
01714 
01715 METHODDEF (void)
01716 new_color_map_2_quant (j_decompress_ptr cinfo)
01717 {
01718   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
01719 
01720   /* Reset the inverse color map */
01721   cquantize->needs_zeroed = TRUE;
01722 }
01723 #else
01724 static void
01725 zeroHistogram (hist3d histogram)
01726 {
01727   int i;
01728   /* Zero the histogram or inverse color map */
01729   for (i = 0; i < HIST_C0_ELEMS; i++)
01730     {
01731       memset (histogram[i],
01732              0, HIST_C1_ELEMS * HIST_C2_ELEMS * sizeof (histcell));
01733     }
01734 }
01735 #endif
01736 
01737 /*
01738  * Module initialization routine for 2-pass color quantization.
01739  */
01740 
01741 #ifdef ORIGINAL_LIB_JPEG
01742 GLOBAL (void)
01743 jinit_2pass_quantizer (j_decompress_ptr cinfo)
01744 #else
01745 void
01746 gdImageTrueColorToPalette (gdImagePtr im, int dither, int colorsWanted)
01747 #endif
01748 {
01749   my_cquantize_ptr cquantize = NULL;
01750   int i;
01751 
01752 #ifndef ORIGINAL_LIB_JPEG
01753   /* Allocate the JPEG palette-storage */
01754   size_t arraysize;
01755   int maxColors = gdMaxColors;
01756   if (!im->trueColor)
01757     {
01758       /* Nothing to do! */
01759       return;
01760     }
01761 
01762   /* If we have a transparent color (the alphaless mode of transparency), we
01763    * must reserve a palette entry for it at the end of the palette. */
01764   if (im->transparent >= 0)
01765     {
01766       maxColors--;
01767     }
01768   if (colorsWanted > maxColors)
01769     {
01770       colorsWanted = maxColors;
01771     }
01772   im->pixels = gdCalloc (sizeof (unsigned char *), im->sy);
01773   if (!im->pixels)
01774     {
01775       /* No can do */
01776       goto outOfMemory;
01777     }
01778   for (i = 0; (i < im->sy); i++)
01779     {
01780       im->pixels[i] = gdCalloc (sizeof (unsigned char *), im->sx);
01781       if (!im->pixels[i])
01782        {
01783          goto outOfMemory;
01784        }
01785     }
01786 #endif
01787 
01788 #ifdef ORIGINAL_LIB_JPEG
01789   cquantize = (my_cquantize_ptr)
01790     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
01791                             SIZEOF (my_cquantizer));
01792   cinfo->cquantize = (struct jpeg_color_quantizer *) cquantize;
01793   cquantize->pub.start_pass = start_pass_2_quant;
01794   cquantize->pub.new_color_map = new_color_map_2_quant;
01795   /* Make sure jdmaster didn't give me a case I can't handle */
01796   if (cinfo->out_color_components != 3)
01797     ERREXIT (cinfo, JERR_NOTIMPL);
01798 #else
01799   cquantize = (my_cquantize_ptr) gdCalloc (sizeof (my_cquantizer), 1);
01800   if (!cquantize)
01801     {
01802       /* No can do */
01803       goto outOfMemory;
01804     }
01805 #endif
01806   cquantize->fserrors = NULL;      /* flag optional arrays not allocated */
01807   cquantize->error_limiter = NULL;
01808 
01809 
01810   /* Allocate the histogram/inverse colormap storage */
01811 #ifdef ORIGINAL_LIB_JPEG
01812   cquantize->histogram = (hist3d) (*cinfo->mem->alloc_small)
01813     ((j_common_ptr) cinfo, JPOOL_IMAGE, HIST_C0_ELEMS * SIZEOF (hist2d));
01814   for (i = 0; i < HIST_C0_ELEMS; i++)
01815     {
01816       cquantize->histogram[i] = (hist2d) (*cinfo->mem->alloc_large)
01817        ((j_common_ptr) cinfo, JPOOL_IMAGE,
01818         HIST_C1_ELEMS * HIST_C2_ELEMS * SIZEOF (histcell));
01819     }
01820   cquantize->needs_zeroed = TRUE;  /* histogram is garbage now */
01821 #else
01822   cquantize->histogram = (hist3d) gdMalloc (HIST_C0_ELEMS * sizeof (hist2d));
01823   for (i = 0; i < HIST_C0_ELEMS; i++)
01824     {
01825       cquantize->histogram[i] =
01826        (hist2d) gdMalloc (HIST_C1_ELEMS * HIST_C2_ELEMS * sizeof (histcell));
01827       if (!cquantize->histogram[i])
01828        {
01829          goto outOfMemory;
01830        }
01831     }
01832 #endif
01833 
01834 #ifdef ORIGINAL_LIB_JPEG
01835   /* Allocate storage for the completed colormap, if required.
01836    * We do this now since it is FAR storage and may affect
01837    * the memory manager's space calculations.
01838    */
01839   if (cinfo->enable_2pass_quant)
01840     {
01841       /* Make sure color count is acceptable */
01842       int desired = cinfo->desired_number_of_colors;
01843       /* Lower bound on # of colors ... somewhat arbitrary as long as > 0 */
01844       if (desired < 8)
01845        ERREXIT1 (cinfo, JERR_QUANT_FEW_COLORS, 8);
01846       /* Make sure colormap indexes can be represented by JSAMPLEs */
01847       if (desired > MAXNUMCOLORS)
01848        ERREXIT1 (cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS);
01849       cquantize->sv_colormap = (*cinfo->mem->alloc_sarray)
01850        ((j_common_ptr) cinfo, JPOOL_IMAGE, (JDIMENSION) desired,
01851         (JDIMENSION) 3);
01852       cquantize->desired = desired;
01853     }
01854   else
01855     cquantize->sv_colormap = NULL;
01856 
01857   /* Only F-S dithering or no dithering is supported. */
01858   /* If user asks for ordered dither, give him F-S. */
01859   if (cinfo->dither_mode != JDITHER_NONE)
01860     cinfo->dither_mode = JDITHER_FS;
01861 
01862   /* Allocate Floyd-Steinberg workspace if necessary.
01863    * This isn't really needed until pass 2, but again it is FAR storage.
01864    * Although we will cope with a later change in dither_mode,
01865    * we do not promise to honor max_memory_to_use if dither_mode changes.
01866    */
01867   if (cinfo->dither_mode == JDITHER_FS)
01868     {
01869       cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large)
01870        ((j_common_ptr) cinfo, JPOOL_IMAGE,
01871         (size_t) ((cinfo->output_width + 2) * (3 * SIZEOF (FSERROR))));
01872       /* Might as well create the error-limiting table too. */
01873       init_error_limit (cinfo);
01874     }
01875 #else
01876 
01877   cquantize->fserrors = (FSERRPTR) gdMalloc (3 * sizeof (FSERROR));
01878   init_error_limit (im, cquantize);
01879   arraysize = (size_t) ((im->sx + 2) * (3 * sizeof (FSERROR)));
01880   /* Allocate Floyd-Steinberg workspace. */
01881   cquantize->fserrors = gdCalloc (arraysize, 1);
01882   if (!cquantize->fserrors)
01883     {
01884       goto outOfMemory;
01885     }
01886   cquantize->on_odd_row = FALSE;
01887 
01888   /* Do the work! */
01889   zeroHistogram (cquantize->histogram);
01890   prescan_quantize (im, cquantize);
01891   /* TBB 2.0.5: pass colorsWanted, not 256! */
01892   select_colors (im, cquantize, colorsWanted);
01893   zeroHistogram (cquantize->histogram);
01894   if (dither)
01895     {
01896       pass2_fs_dither (im, cquantize);
01897     }
01898   else
01899     {
01900       pass2_no_dither (im, cquantize);
01901     }
01902 #if 0                       /* 2.0.12; we no longer attempt full alpha in palettes */
01903   if (cquantize->transparentIsPresent)
01904     {
01905       int mt = -1;
01906       int mtIndex = -1;
01907       for (i = 0; (i < im->colorsTotal); i++)
01908        {
01909          if (im->alpha[i] > mt)
01910            {
01911              mtIndex = i;
01912              mt = im->alpha[i];
01913            }
01914        }
01915       for (i = 0; (i < im->colorsTotal); i++)
01916        {
01917          if (im->alpha[i] == mt)
01918            {
01919              im->alpha[i] = gdAlphaTransparent;
01920            }
01921        }
01922     }
01923   if (cquantize->opaqueIsPresent)
01924     {
01925       int mo = 128;
01926       int moIndex = -1;
01927       for (i = 0; (i < im->colorsTotal); i++)
01928        {
01929          if (im->alpha[i] < mo)
01930            {
01931              moIndex = i;
01932              mo = im->alpha[i];
01933            }
01934        }
01935       for (i = 0; (i < im->colorsTotal); i++)
01936        {
01937          if (im->alpha[i] == mo)
01938            {
01939              im->alpha[i] = gdAlphaOpaque;
01940            }
01941        }
01942     }
01943 #endif
01944 
01945   /* If we had a 'transparent' color, increment the color count so it's
01946    * officially in the palette and convert the transparent variable to point to
01947    * an index rather than a color (Its data already exists and transparent
01948    * pixels have already been mapped to it by this point, it is done late as to
01949    * avoid color matching / dithering with it). */
01950   if (im->transparent >= 0)
01951     {
01952       im->transparent = im->colorsTotal;
01953       im->colorsTotal++;
01954     }
01955 
01956   /* Success! Get rid of the truecolor image data. */
01957   im->trueColor = 0;
01958   /* Junk the truecolor pixels */
01959   for (i = 0; i < im->sy; i++)
01960     {
01961       gdFree (im->tpixels[i]);
01962     }
01963   gdFree (im->tpixels);
01964   im->tpixels = 0;
01965   /* Tediously free stuff. */
01966 outOfMemory:
01967   if (im->trueColor)
01968     {
01969       /* On failure only */
01970       for (i = 0; i < im->sy; i++)
01971        {
01972          if (im->pixels[i])
01973            {
01974              gdFree (im->pixels[i]);
01975            }
01976        }
01977       if (im->pixels)
01978        {
01979          gdFree (im->pixels);
01980        }
01981       im->pixels = 0;
01982     }
01983   for (i = 0; i < HIST_C0_ELEMS; i++)
01984     {
01985       if (cquantize->histogram[i])
01986        {
01987          gdFree (cquantize->histogram[i]);
01988        }
01989     }
01990   if (cquantize->histogram)
01991     {
01992       gdFree (cquantize->histogram);
01993     }
01994   if (cquantize->fserrors)
01995     {
01996       gdFree (cquantize->fserrors);
01997     }
01998   if (cquantize->error_limiter_storage)
01999     {
02000       gdFree (cquantize->error_limiter_storage);
02001     }
02002   if (cquantize)
02003     {
02004       gdFree (cquantize);
02005     }
02006 
02007 #endif
02008 }
02009 
02010 #endif