Back to index

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