Back to index

tetex-bin  3.0
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 #endif
00776 }
00777 
00778 
00779 LOCAL (void)
00780 #ifdef ORIGINAL_LIB_JPEG
00781 select_colors (j_decompress_ptr cinfo, int desired_colors)
00782 #else
00783 select_colors (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize, int desired_colors)
00784 #endif
00785 /* Master routine for color selection */
00786 {
00787   boxptr boxlist;
00788   int numboxes;
00789   int i;
00790 
00791   /* Allocate workspace for box list */
00792 #ifdef ORIGINAL_LIB_JPEG
00793   boxlist = (boxptr) (*cinfo->mem->alloc_small)
00794     ((j_common_ptr) cinfo, JPOOL_IMAGE, desired_colors * SIZEOF (box));
00795 #else
00796   /* This can't happen because we clamp desired_colors at gdMaxColors, 
00797     but anyway */
00798   if (overflow2(desired_colors, sizeof (box))) {
00799     return;
00800    }
00801   boxlist = (boxptr) gdMalloc (desired_colors * sizeof (box));
00802 #endif
00803   /* Initialize one box containing whole space */
00804   numboxes = 1;
00805   boxlist[0].c0min = 0;
00806   boxlist[0].c0max = MAXJSAMPLE >> C0_SHIFT;
00807   boxlist[0].c1min = 0;
00808   boxlist[0].c1max = MAXJSAMPLE >> C1_SHIFT;
00809   boxlist[0].c2min = 0;
00810   boxlist[0].c2max = MAXJSAMPLE >> C2_SHIFT;
00811 #ifdef ORIGINAL_LIB_JPEG
00812   /* Shrink it to actually-used volume and set its statistics */
00813   update_box (cinfo, &boxlist[0]);
00814   /* Perform median-cut to produce final box list */
00815   numboxes = median_cut (cinfo, boxlist, numboxes, desired_colors);
00816   /* Compute the representative color for each box, fill colormap */
00817   for (i = 0; i < numboxes; i++)
00818     compute_color (cinfo, &boxlist[i], i);
00819   cinfo->actual_number_of_colors = numboxes;
00820   TRACEMS1 (cinfo, 1, JTRC_QUANT_SELECTED, numboxes);
00821 #else
00822   /* Shrink it to actually-used volume and set its statistics */
00823   update_box (oim, nim, cquantize, &boxlist[0]);
00824   /* Perform median-cut to produce final box list */
00825   numboxes = median_cut (oim, nim, cquantize, boxlist, numboxes, desired_colors);
00826   /* Compute the representative color for each box, fill colormap */
00827   for (i = 0; i < numboxes; i++)
00828     compute_color (oim, nim, cquantize, &boxlist[i], i);
00829   nim->colorsTotal = numboxes;
00830 
00831   /* If we had a pure transparency color, add it as the last palette entry.
00832    * Skip incrementing the color count so that the dither / matching phase
00833    * won't use it on pixels that shouldn't have been transparent.  We'll
00834    * increment it after all that finishes. */
00835   if (oim->transparent >= 0)
00836     {
00837       /* Save the transparent color. */
00838       nim->red[nim->colorsTotal] = gdTrueColorGetRed (oim->transparent);
00839       nim->green[nim->colorsTotal] = gdTrueColorGetGreen (oim->transparent);
00840       nim->blue[nim->colorsTotal] = gdTrueColorGetBlue (oim->transparent);
00841       nim->alpha[nim->colorsTotal] = gdAlphaTransparent;
00842       nim->open[nim->colorsTotal] = 0;
00843     }
00844 
00845   gdFree (boxlist);
00846 #endif
00847 }
00848 
00849 
00850 /*
00851  * These routines are concerned with the time-critical task of mapping input
00852  * colors to the nearest color in the selected colormap.
00853  *
00854  * We re-use the histogram space as an "inverse color map", essentially a
00855  * cache for the results of nearest-color searches.  All colors within a
00856  * histogram cell will be mapped to the same colormap entry, namely the one
00857  * closest to the cell's center.  This may not be quite the closest entry to
00858  * the actual input color, but it's almost as good.  A zero in the cache
00859  * indicates we haven't found the nearest color for that cell yet; the array
00860  * is cleared to zeroes before starting the mapping pass.  When we find the
00861  * nearest color for a cell, its colormap index plus one is recorded in the
00862  * cache for future use.  The pass2 scanning routines call fill_inverse_cmap
00863  * when they need to use an unfilled entry in the cache.
00864  *
00865  * Our method of efficiently finding nearest colors is based on the "locally
00866  * sorted search" idea described by Heckbert and on the incremental distance
00867  * calculation described by Spencer W. Thomas in chapter III.1 of Graphics
00868  * Gems II (James Arvo, ed.  Academic Press, 1991).  Thomas points out that
00869  * the distances from a given colormap entry to each cell of the histogram can
00870  * be computed quickly using an incremental method: the differences between
00871  * distances to adjacent cells themselves differ by a constant.  This allows a
00872  * fairly fast implementation of the "brute force" approach of computing the
00873  * distance from every colormap entry to every histogram cell.  Unfortunately,
00874  * it needs a work array to hold the best-distance-so-far for each histogram
00875  * cell (because the inner loop has to be over cells, not colormap entries).
00876  * The work array elements have to be INT32s, so the work array would need
00877  * 256Kb at our recommended precision.  This is not feasible in DOS machines.
00878  *
00879  * To get around these problems, we apply Thomas' method to compute the
00880  * nearest colors for only the cells within a small subbox of the histogram.
00881  * The work array need be only as big as the subbox, so the memory usage
00882  * problem is solved.  Furthermore, we need not fill subboxes that are never
00883  * referenced in pass2; many images use only part of the color gamut, so a
00884  * fair amount of work is saved.  An additional advantage of this
00885  * approach is that we can apply Heckbert's locality criterion to quickly
00886  * eliminate colormap entries that are far away from the subbox; typically
00887  * three-fourths of the colormap entries are rejected by Heckbert's criterion,
00888  * and we need not compute their distances to individual cells in the subbox.
00889  * The speed of this approach is heavily influenced by the subbox size: too
00890  * small means too much overhead, too big loses because Heckbert's criterion
00891  * can't eliminate as many colormap entries.  Empirically the best subbox
00892  * size seems to be about 1/512th of the histogram (1/8th in each direction).
00893  *
00894  * Thomas' article also describes a refined method which is asymptotically
00895  * faster than the brute-force method, but it is also far more complex and
00896  * cannot efficiently be applied to small subboxes.  It is therefore not
00897  * useful for programs intended to be portable to DOS machines.  On machines
00898  * with plenty of memory, filling the whole histogram in one shot with Thomas'
00899  * refined method might be faster than the present code --- but then again,
00900  * it might not be any faster, and it's certainly more complicated.
00901  */
00902 
00903 
00904 /* log2(histogram cells in update box) for each axis; this can be adjusted */
00905 #define BOX_C0_LOG  (HIST_C0_BITS-3)
00906 #define BOX_C1_LOG  (HIST_C1_BITS-3)
00907 #define BOX_C2_LOG  (HIST_C2_BITS-3)
00908 
00909 #define BOX_C0_ELEMS  (1<<BOX_C0_LOG)     /* # of hist cells in update box */
00910 #define BOX_C1_ELEMS  (1<<BOX_C1_LOG)
00911 #define BOX_C2_ELEMS  (1<<BOX_C2_LOG)
00912 
00913 #define BOX_C0_SHIFT  (C0_SHIFT + BOX_C0_LOG)
00914 #define BOX_C1_SHIFT  (C1_SHIFT + BOX_C1_LOG)
00915 #define BOX_C2_SHIFT  (C2_SHIFT + BOX_C2_LOG)
00916 
00917 
00918 /*
00919  * The next three routines implement inverse colormap filling.  They could
00920  * all be folded into one big routine, but splitting them up this way saves
00921  * some stack space (the mindist[] and bestdist[] arrays need not coexist)
00922  * and may allow some compilers to produce better code by registerizing more
00923  * inner-loop variables.
00924  */
00925 
00926 LOCAL (int)
00927 find_nearby_colors (
00928 #ifdef ORIGINAL_LIB_JPEG
00929                    j_decompress_ptr cinfo,
00930 #else
00931                    gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize,
00932 #endif
00933                    int minc0, int minc1, int minc2, JSAMPLE colorlist[])
00934 /* Locate the colormap entries close enough to an update box to be candidates
00935  * for the nearest entry to some cell(s) in the update box.  The update box
00936  * is specified by the center coordinates of its first cell.  The number of
00937  * candidate colormap entries is returned, and their colormap indexes are
00938  * placed in colorlist[].
00939  * This routine uses Heckbert's "locally sorted search" criterion to select
00940  * the colors that need further consideration.
00941  */
00942 {
00943 #ifdef ORIGINAL_LIB_JPEG
00944   int numcolors = cinfo->actual_number_of_colors;
00945 #else
00946   int numcolors = nim->colorsTotal;
00947 #endif
00948   int maxc0, maxc1, maxc2;
00949   int centerc0, centerc1, centerc2;
00950   int i, x, ncolors;
00951   INT32 minmaxdist, min_dist, max_dist, tdist;
00952   INT32 mindist[MAXNUMCOLORS];     /* min distance to colormap entry i */
00953 
00954   /* Compute true coordinates of update box's upper corner and center.
00955    * Actually we compute the coordinates of the center of the upper-corner
00956    * histogram cell, which are the upper bounds of the volume we care about.
00957    * Note that since ">>" rounds down, the "center" values may be closer to
00958    * min than to max; hence comparisons to them must be "<=", not "<".
00959    */
00960   maxc0 = minc0 + ((1 << BOX_C0_SHIFT) - (1 << C0_SHIFT));
00961   centerc0 = (minc0 + maxc0) >> 1;
00962   maxc1 = minc1 + ((1 << BOX_C1_SHIFT) - (1 << C1_SHIFT));
00963   centerc1 = (minc1 + maxc1) >> 1;
00964   maxc2 = minc2 + ((1 << BOX_C2_SHIFT) - (1 << C2_SHIFT));
00965   centerc2 = (minc2 + maxc2) >> 1;
00966 
00967   /* For each color in colormap, find:
00968    *  1. its minimum squared-distance to any point in the update box
00969    *     (zero if color is within update box);
00970    *  2. its maximum squared-distance to any point in the update box.
00971    * Both of these can be found by considering only the corners of the box.
00972    * We save the minimum distance for each color in mindist[];
00973    * only the smallest maximum distance is of interest.
00974    */
00975   minmaxdist = 0x7FFFFFFFL;
00976 
00977   for (i = 0; i < numcolors; i++)
00978     {
00979       /* We compute the squared-c0-distance term, then add in the other two. */
00980 #ifdef ORIGINAL_LIB_JPEG
00981       x = GETJSAMPLE (cinfo->colormap[0][i]);
00982 #else
00983       x = nim->red[i];
00984 #endif
00985       if (x < minc0)
00986        {
00987          tdist = (x - minc0) * C0_SCALE;
00988          min_dist = tdist * tdist;
00989          tdist = (x - maxc0) * C0_SCALE;
00990          max_dist = tdist * tdist;
00991        }
00992       else if (x > maxc0)
00993        {
00994          tdist = (x - maxc0) * C0_SCALE;
00995          min_dist = tdist * tdist;
00996          tdist = (x - minc0) * C0_SCALE;
00997          max_dist = tdist * tdist;
00998        }
00999       else
01000        {
01001          /* within cell range so no contribution to min_dist */
01002          min_dist = 0;
01003          if (x <= centerc0)
01004            {
01005              tdist = (x - maxc0) * C0_SCALE;
01006              max_dist = tdist * tdist;
01007            }
01008          else
01009            {
01010              tdist = (x - minc0) * C0_SCALE;
01011              max_dist = tdist * tdist;
01012            }
01013        }
01014 
01015 #ifdef ORIGINAL_LIB_JPEG
01016       x = GETJSAMPLE (cinfo->colormap[1][i]);
01017 #else
01018       x = nim->green[i];
01019 #endif
01020       if (x < minc1)
01021        {
01022          tdist = (x - minc1) * C1_SCALE;
01023          min_dist += tdist * tdist;
01024          tdist = (x - maxc1) * C1_SCALE;
01025          max_dist += tdist * tdist;
01026        }
01027       else if (x > maxc1)
01028        {
01029          tdist = (x - maxc1) * C1_SCALE;
01030          min_dist += tdist * tdist;
01031          tdist = (x - minc1) * C1_SCALE;
01032          max_dist += tdist * tdist;
01033        }
01034       else
01035        {
01036          /* within cell range so no contribution to min_dist */
01037          if (x <= centerc1)
01038            {
01039              tdist = (x - maxc1) * C1_SCALE;
01040              max_dist += tdist * tdist;
01041            }
01042          else
01043            {
01044              tdist = (x - minc1) * C1_SCALE;
01045              max_dist += tdist * tdist;
01046            }
01047        }
01048 
01049 #ifdef ORIGINAL_LIB_JPEG
01050       x = GETJSAMPLE (cinfo->colormap[2][i]);
01051 #else
01052       x = nim->blue[i];
01053 #endif
01054       if (x < minc2)
01055        {
01056          tdist = (x - minc2) * C2_SCALE;
01057          min_dist += tdist * tdist;
01058          tdist = (x - maxc2) * C2_SCALE;
01059          max_dist += tdist * tdist;
01060        }
01061       else if (x > maxc2)
01062        {
01063          tdist = (x - maxc2) * C2_SCALE;
01064          min_dist += tdist * tdist;
01065          tdist = (x - minc2) * C2_SCALE;
01066          max_dist += tdist * tdist;
01067        }
01068       else
01069        {
01070          /* within cell range so no contribution to min_dist */
01071          if (x <= centerc2)
01072            {
01073              tdist = (x - maxc2) * C2_SCALE;
01074              max_dist += tdist * tdist;
01075            }
01076          else
01077            {
01078              tdist = (x - minc2) * C2_SCALE;
01079              max_dist += tdist * tdist;
01080            }
01081        }
01082 
01083       mindist[i] = min_dist;       /* save away the results */
01084       if (max_dist < minmaxdist)
01085        minmaxdist = max_dist;
01086     }
01087 
01088   /* Now we know that no cell in the update box is more than minmaxdist
01089    * away from some colormap entry.  Therefore, only colors that are
01090    * within minmaxdist of some part of the box need be considered.
01091    */
01092   ncolors = 0;
01093   for (i = 0; i < numcolors; i++)
01094     {
01095       if (mindist[i] <= minmaxdist)
01096        colorlist[ncolors++] = (JSAMPLE) i;
01097     }
01098   return ncolors;
01099 }
01100 
01101 
01102 LOCAL (void) find_best_colors (
01103 #ifdef ORIGINAL_LIB_JPEG
01104                             j_decompress_ptr cinfo,
01105 #else
01106                             gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize,
01107 #endif
01108                             int minc0, int minc1, int minc2,
01109                             int numcolors, JSAMPLE colorlist[],
01110                             JSAMPLE bestcolor[])
01111 /* Find the closest colormap entry for each cell in the update box,
01112  * given the list of candidate colors prepared by find_nearby_colors.
01113  * Return the indexes of the closest entries in the bestcolor[] array.
01114  * This routine uses Thomas' incremental distance calculation method to
01115  * find the distance from a colormap entry to successive cells in the box.
01116  */
01117 {
01118   int ic0, ic1, ic2;
01119   int i, icolor;
01120   register INT32 *bptr;            /* pointer into bestdist[] array */
01121   JSAMPLE *cptr;            /* pointer into bestcolor[] array */
01122   INT32 dist0, dist1;              /* initial distance values */
01123   register INT32 dist2;            /* current distance in inner loop */
01124   INT32 xx0, xx1;           /* distance increments */
01125   register INT32 xx2;
01126   INT32 inc0, inc1, inc2;   /* initial values for increments */
01127   /* This array holds the distance to the nearest-so-far color for each cell */
01128   INT32 bestdist[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS];
01129 
01130   /* Initialize best-distance for each cell of the update box */
01131   bptr = bestdist;
01132   for (i = BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS - 1; i >= 0; i--)
01133     *bptr++ = 0x7FFFFFFFL;
01134 
01135   /* For each color selected by find_nearby_colors,
01136    * compute its distance to the center of each cell in the box.
01137    * If that's less than best-so-far, update best distance and color number.
01138    */
01139 
01140   /* Nominal steps between cell centers ("x" in Thomas article) */
01141 #define STEP_C0  ((1 << C0_SHIFT) * C0_SCALE)
01142 #define STEP_C1  ((1 << C1_SHIFT) * C1_SCALE)
01143 #define STEP_C2  ((1 << C2_SHIFT) * C2_SCALE)
01144 
01145   for (i = 0; i < numcolors; i++)
01146     {
01147       int r, g, b;
01148 #ifdef ORIGINAL_LIB_JPEG
01149 
01150       icolor = GETJSAMPLE (colorlist[i]);
01151       r = GETJSAMPLE (cinfo->colormap[0][icolor]);
01152       g = GETJSAMPLE (cinfo->colormap[1][icolor]);
01153       b = GETJSAMPLE (cinfo->colormap[2][icolor]);
01154 #else
01155       icolor = colorlist[i];
01156       r = nim->red[icolor];
01157       g = nim->green[icolor];
01158       b = nim->blue[icolor];
01159 #endif
01160 
01161       /* Compute (square of) distance from minc0/c1/c2 to this color */
01162       inc0 = (minc0 - r) * C0_SCALE;
01163       dist0 = inc0 * inc0;
01164       inc1 = (minc1 - g) * C1_SCALE;
01165       dist0 += inc1 * inc1;
01166       inc2 = (minc2 - b) * C2_SCALE;
01167       dist0 += inc2 * inc2;
01168       /* Form the initial difference increments */
01169       inc0 = inc0 * (2 * STEP_C0) + STEP_C0 * STEP_C0;
01170       inc1 = inc1 * (2 * STEP_C1) + STEP_C1 * STEP_C1;
01171       inc2 = inc2 * (2 * STEP_C2) + STEP_C2 * STEP_C2;
01172       /* Now loop over all cells in box, updating distance per Thomas method */
01173       bptr = bestdist;
01174       cptr = bestcolor;
01175       xx0 = inc0;
01176       for (ic0 = BOX_C0_ELEMS - 1; ic0 >= 0; ic0--)
01177        {
01178          dist1 = dist0;
01179          xx1 = inc1;
01180          for (ic1 = BOX_C1_ELEMS - 1; ic1 >= 0; ic1--)
01181            {
01182              dist2 = dist1;
01183              xx2 = inc2;
01184              for (ic2 = BOX_C2_ELEMS - 1; ic2 >= 0; ic2--)
01185               {
01186                 if (dist2 < *bptr)
01187                   {
01188                     *bptr = dist2;
01189                     *cptr = (JSAMPLE) icolor;
01190                   }
01191                 dist2 += xx2;
01192                 xx2 += 2 * STEP_C2 * STEP_C2;
01193                 bptr++;
01194                 cptr++;
01195               }
01196              dist1 += xx1;
01197              xx1 += 2 * STEP_C1 * STEP_C1;
01198            }
01199          dist0 += xx0;
01200          xx0 += 2 * STEP_C0 * STEP_C0;
01201        }
01202     }
01203 }
01204 
01205 
01206 LOCAL (void)
01207 fill_inverse_cmap (
01208 #ifdef ORIGINAL_LIB_JPEG
01209                   j_decompress_ptr cinfo,
01210 #else
01211                   gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize,
01212 #endif
01213                   int c0, int c1, int c2)
01214 /* Fill the inverse-colormap entries in the update box that contains */
01215 /* histogram cell c0/c1/c2.  (Only that one cell MUST be filled, but */
01216 /* we can fill as many others as we wish.) */
01217 {
01218 #ifdef ORIGINAL_LIB_JPEG
01219   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
01220 #endif
01221   hist3d histogram = cquantize->histogram;
01222   int minc0, minc1, minc2;  /* lower left corner of update box */
01223   int ic0, ic1, ic2;
01224   register JSAMPLE *cptr;   /* pointer into bestcolor[] array */
01225   register histptr cachep;  /* pointer into main cache array */
01226   /* This array lists the candidate colormap indexes. */
01227   JSAMPLE colorlist[MAXNUMCOLORS];
01228   int numcolors;            /* number of candidate colors */
01229   /* This array holds the actually closest colormap index for each cell. */
01230   JSAMPLE bestcolor[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS];
01231 
01232   /* Convert cell coordinates to update box ID */
01233   c0 >>= BOX_C0_LOG;
01234   c1 >>= BOX_C1_LOG;
01235   c2 >>= BOX_C2_LOG;
01236 
01237   /* Compute true coordinates of update box's origin corner.
01238    * Actually we compute the coordinates of the center of the corner
01239    * histogram cell, which are the lower bounds of the volume we care about.
01240    */
01241   minc0 = (c0 << BOX_C0_SHIFT) + ((1 << C0_SHIFT) >> 1);
01242   minc1 = (c1 << BOX_C1_SHIFT) + ((1 << C1_SHIFT) >> 1);
01243   minc2 = (c2 << BOX_C2_SHIFT) + ((1 << C2_SHIFT) >> 1);
01244 
01245   /* Determine which colormap entries are close enough to be candidates
01246    * for the nearest entry to some cell in the update box.
01247    */
01248 #ifdef ORIGINAL_LIB_JPEG
01249   numcolors = find_nearby_colors (cinfo, minc0, minc1, minc2, colorlist);
01250 
01251   /* Determine the actually nearest colors. */
01252   find_best_colors (cinfo, minc0, minc1, minc2, numcolors, colorlist,
01253                   bestcolor);
01254 #else
01255   numcolors =
01256     find_nearby_colors (oim, nim, cquantize, minc0, minc1, minc2, colorlist);
01257   find_best_colors (oim, nim, cquantize, minc0, minc1, minc2, numcolors,
01258                   colorlist, bestcolor);
01259 #endif
01260 
01261   /* Save the best color numbers (plus 1) in the main cache array */
01262   c0 <<= BOX_C0_LOG;        /* convert ID back to base cell indexes */
01263   c1 <<= BOX_C1_LOG;
01264   c2 <<= BOX_C2_LOG;
01265   cptr = bestcolor;
01266   for (ic0 = 0; ic0 < BOX_C0_ELEMS; ic0++)
01267     {
01268       for (ic1 = 0; ic1 < BOX_C1_ELEMS; ic1++)
01269        {
01270          cachep = &histogram[c0 + ic0][c1 + ic1][c2];
01271          for (ic2 = 0; ic2 < BOX_C2_ELEMS; ic2++)
01272            {
01273 #ifdef ORIGINAL_LIB_JPEG
01274              *cachep++ = (histcell) (GETJSAMPLE (*cptr++) + 1);
01275 #else
01276              *cachep++ = (histcell) ((*cptr++) + 1);
01277 #endif
01278            }
01279        }
01280     }
01281 }
01282 
01283 
01284 /*
01285  * Map some rows of pixels to the output colormapped representation.
01286  */
01287 
01288 METHODDEF (void)
01289 #ifndef ORIGINAL_LIB_JPEG
01290 pass2_no_dither (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
01291 {
01292   register int *inptr;
01293   register unsigned char *outptr;
01294   int width = oim->sx;
01295   int num_rows = oim->sy;
01296 #else
01297 pass2_no_dither (j_decompress_ptr cinfo,
01298                JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows)
01299 /* This version performs no dithering */
01300 {
01301   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
01302   register JSAMPROW inptr, outptr;
01303   JDIMENSION width = cinfo->output_width;
01304 #endif
01305   hist3d histogram = cquantize->histogram;
01306   register int c0, c1, c2;
01307   int row;
01308   JDIMENSION col;
01309   register histptr cachep;
01310 
01311 
01312   for (row = 0; row < num_rows; row++)
01313     {
01314       inptr = input_buf[row];
01315       outptr = output_buf[row];
01316       for (col = width; col > 0; col--)
01317        {
01318          /* get pixel value and index into the cache */
01319          int r, g, b;
01320 #ifdef ORIGINAL_LIB_JPEG
01321          r = GETJSAMPLE (*inptr++);
01322          g = GETJSAMPLE (*inptr++);
01323          b = GETJSAMPLE (*inptr++);
01324 #else
01325          r = gdTrueColorGetRed (*inptr);
01326          g = gdTrueColorGetGreen (*inptr);
01327          /* 
01328             2.0.24: inptr must not be incremented until after
01329             transparency check, if any. Thanks to "Super Pikeman." 
01330           */
01331          b = gdTrueColorGetBlue (*inptr);
01332 
01333          /* If the pixel is transparent, we assign it the palette index that
01334           * will later be added at the end of the palette as the transparent
01335           * index. */
01336          if ((oim->transparent >= 0) && (oim->transparent == *inptr))
01337            {
01338              *outptr++ = nim->colorsTotal;
01339              inptr++;
01340              continue;
01341            }
01342          inptr++;
01343 #endif
01344          c0 = r >> C0_SHIFT;
01345          c1 = g >> C1_SHIFT;
01346          c2 = b >> C2_SHIFT;
01347          cachep = &histogram[c0][c1][c2];
01348          /* If we have not seen this color before, find nearest colormap entry */
01349          /* and update the cache */
01350          if (*cachep == 0)
01351 #ifdef ORIGINAL_LIB_JPEG
01352            fill_inverse_cmap (cinfo, c0, c1, c2);
01353 #else
01354            fill_inverse_cmap (oim, nim, cquantize, c0, c1, c2);
01355 #endif
01356          /* Now emit the colormap index for this cell */
01357 #ifdef ORIGINAL_LIB_JPEG
01358          *outptr++ = (JSAMPLE) (*cachep - 1);
01359 #else
01360          *outptr++ = (*cachep - 1);
01361 #endif
01362        }
01363     }
01364 }
01365 
01366 
01367 METHODDEF (void)
01368 #ifndef ORIGINAL_LIB_JPEG
01369 pass2_fs_dither (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
01370 {
01371 #else
01372 pass2_fs_dither (j_decompress_ptr cinfo,
01373                JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows)
01374 /* This version performs Floyd-Steinberg dithering */
01375 {
01376   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
01377   JSAMPROW inptr;           /* => current input pixel */
01378 #endif
01379   hist3d histogram = cquantize->histogram;
01380   register LOCFSERROR cur0, cur1, cur2;   /* current error or pixel value */
01381   LOCFSERROR belowerr0, belowerr1, belowerr2;    /* error for pixel below cur */
01382   LOCFSERROR bpreverr0, bpreverr1, bpreverr2;    /* error for below/prev col */
01383   register FSERRPTR errorptr;      /* => fserrors[] at column before current */
01384   histptr cachep;
01385   int dir;                  /* +1 or -1 depending on direction */
01386   int dir3;                 /* 3*dir, for advancing inptr & errorptr */
01387   int row;
01388   JDIMENSION col;
01389 #ifdef ORIGINAL_LIB_JPEG
01390   JSAMPROW outptr;          /* => current output pixel */
01391   JDIMENSION width = cinfo->output_width;
01392   JSAMPLE *range_limit = cinfo->sample_range_limit;
01393   JSAMPROW colormap0 = cinfo->colormap[0];
01394   JSAMPROW colormap1 = cinfo->colormap[1];
01395   JSAMPROW colormap2 = cinfo->colormap[2];
01396 #else
01397   int *inptr;               /* => current input pixel */
01398   unsigned char *outptr;    /* => current output pixel */
01399   int width = oim->sx;
01400   int num_rows = oim->sy;
01401   int *colormap0 = nim->red;
01402   int *colormap1 = nim->green;
01403   int *colormap2 = nim->blue;
01404 #endif
01405   int *error_limit = cquantize->error_limiter;
01406 
01407 
01408   SHIFT_TEMPS for (row = 0; row < num_rows; row++)
01409     {
01410       inptr = input_buf[row];
01411       outptr = output_buf[row];
01412       if (cquantize->on_odd_row)
01413        {
01414          /* work right to left in this row */
01415          inptr += (width - 1) * 3; /* so point to rightmost pixel */
01416          outptr += width - 1;
01417          dir = -1;
01418          dir3 = -3;
01419          errorptr = cquantize->fserrors + (width + 1) * 3;     /* => entry after last column */
01420 #ifdef ORIGINAL_LIB_JPEG_REVERSE_ODD_ROWS
01421          cquantize->on_odd_row = FALSE;   /* flip for next time */
01422 #endif
01423        }
01424       else
01425        {
01426          /* work left to right in this row */
01427          dir = 1;
01428          dir3 = 3;
01429          errorptr = cquantize->fserrors;  /* => entry before first real column */
01430 #ifdef ORIGINAL_LIB_JPEG_REVERSE_ODD_ROWS
01431          cquantize->on_odd_row = TRUE;    /* flip for next time */
01432 #endif
01433        }
01434       /* Preset error values: no error propagated to first pixel from left */
01435       cur0 = cur1 = cur2 = 0;
01436       /* and no error propagated to row below yet */
01437       belowerr0 = belowerr1 = belowerr2 = 0;
01438       bpreverr0 = bpreverr1 = bpreverr2 = 0;
01439 
01440       for (col = width; col > 0; col--)
01441        {
01442 
01443          /* If this pixel is transparent, we want to assign it to the special
01444           * transparency color index past the end of the palette rather than
01445           * go through matching / dithering. */
01446          if ((oim->transparent >= 0) && (*inptr == oim->transparent))
01447            {
01448              *outptr = nim->colorsTotal;
01449              errorptr[0] = 0;
01450              errorptr[1] = 0;
01451              errorptr[2] = 0;
01452              errorptr[3] = 0;
01453              inptr += dir;
01454              outptr += dir;
01455              errorptr += dir3;
01456              continue;
01457            }
01458          /* curN holds the error propagated from the previous pixel on the
01459           * current line.  Add the error propagated from the previous line
01460           * to form the complete error correction term for this pixel, and
01461           * round the error term (which is expressed * 16) to an integer.
01462           * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct
01463           * for either sign of the error value.
01464           * Note: errorptr points to *previous* column's array entry.
01465           */
01466          cur0 = RIGHT_SHIFT (cur0 + errorptr[dir3 + 0] + 8, 4);
01467          cur1 = RIGHT_SHIFT (cur1 + errorptr[dir3 + 1] + 8, 4);
01468          cur2 = RIGHT_SHIFT (cur2 + errorptr[dir3 + 2] + 8, 4);
01469          /* Limit the error using transfer function set by init_error_limit.
01470           * See comments with init_error_limit for rationale.
01471           */
01472          cur0 = error_limit[cur0];
01473          cur1 = error_limit[cur1];
01474          cur2 = error_limit[cur2];
01475          /* Form pixel value + error, and range-limit to 0..MAXJSAMPLE.
01476           * The maximum error is +- MAXJSAMPLE (or less with error limiting);
01477           * this sets the required size of the range_limit array.
01478           */
01479 #ifdef ORIGINAL_LIB_JPEG
01480          cur0 += GETJSAMPLE (inptr[0]);
01481          cur1 += GETJSAMPLE (inptr[1]);
01482          cur2 += GETJSAMPLE (inptr[2]);
01483          cur0 = GETJSAMPLE (range_limit[cur0]);
01484          cur1 = GETJSAMPLE (range_limit[cur1]);
01485          cur2 = GETJSAMPLE (range_limit[cur2]);
01486 #else
01487          cur0 += gdTrueColorGetRed (*inptr);
01488          cur1 += gdTrueColorGetGreen (*inptr);
01489          cur2 += gdTrueColorGetBlue (*inptr);
01490          range_limit (cur0);
01491          range_limit (cur1);
01492          range_limit (cur2);
01493 #endif
01494 
01495          /* Index into the cache with adjusted pixel value */
01496          cachep =
01497            &histogram[cur0 >> C0_SHIFT][cur1 >> C1_SHIFT][cur2 >> C2_SHIFT];
01498          /* If we have not seen this color before, find nearest colormap */
01499          /* entry and update the cache */
01500          if (*cachep == 0)
01501 #ifdef ORIGINAL_LIB_JPEG
01502            fill_inverse_cmap (cinfo, cur0 >> C0_SHIFT, cur1 >> C1_SHIFT,
01503                             cur2 >> C2_SHIFT);
01504 #else
01505            fill_inverse_cmap (oim, nim, cquantize, cur0 >> C0_SHIFT,
01506                             cur1 >> C1_SHIFT, cur2 >> C2_SHIFT);
01507 #endif
01508          /* Now emit the colormap index for this cell */
01509          {
01510            register int pixcode = *cachep - 1;
01511            *outptr = (JSAMPLE) pixcode;
01512            /* Compute representation error for this pixel */
01513 #define GETJSAMPLE
01514            cur0 -= GETJSAMPLE (colormap0[pixcode]);
01515            cur1 -= GETJSAMPLE (colormap1[pixcode]);
01516            cur2 -= GETJSAMPLE (colormap2[pixcode]);
01517 #undef GETJSAMPLE
01518          }
01519          /* Compute error fractions to be propagated to adjacent pixels.
01520           * Add these into the running sums, and simultaneously shift the
01521           * next-line error sums left by 1 column.
01522           */
01523          {
01524            register LOCFSERROR bnexterr, delta;
01525 
01526            bnexterr = cur0; /* Process component 0 */
01527            delta = cur0 * 2;
01528            cur0 += delta;   /* form error * 3 */
01529            errorptr[0] = (FSERROR) (bpreverr0 + cur0);
01530            cur0 += delta;   /* form error * 5 */
01531            bpreverr0 = belowerr0 + cur0;
01532            belowerr0 = bnexterr;
01533            cur0 += delta;   /* form error * 7 */
01534            bnexterr = cur1; /* Process component 1 */
01535            delta = cur1 * 2;
01536            cur1 += delta;   /* form error * 3 */
01537            errorptr[1] = (FSERROR) (bpreverr1 + cur1);
01538            cur1 += delta;   /* form error * 5 */
01539            bpreverr1 = belowerr1 + cur1;
01540            belowerr1 = bnexterr;
01541            cur1 += delta;   /* form error * 7 */
01542            bnexterr = cur2; /* Process component 2 */
01543            delta = cur2 * 2;
01544            cur2 += delta;   /* form error * 3 */
01545            errorptr[2] = (FSERROR) (bpreverr2 + cur2);
01546            cur2 += delta;   /* form error * 5 */
01547            bpreverr2 = belowerr2 + cur2;
01548            belowerr2 = bnexterr;
01549            cur2 += delta;   /* form error * 7 */
01550          }
01551          /* At this point curN contains the 7/16 error value to be propagated
01552           * to the next pixel on the current line, and all the errors for the
01553           * next line have been shifted over.  We are therefore ready to move on.
01554           */
01555 #ifdef ORIGINAL_LIB_JPEG
01556          inptr += dir3;     /* Advance pixel pointers to next column */
01557 #else
01558          inptr += dir;             /* Advance pixel pointers to next column */
01559 #endif
01560          outptr += dir;
01561          errorptr += dir3;  /* advance errorptr to current column */
01562        }
01563       /* Post-loop cleanup: we must unload the final error values into the
01564        * final fserrors[] entry.  Note we need not unload belowerrN because
01565        * it is for the dummy column before or after the actual array.
01566        */
01567       errorptr[0] = (FSERROR) bpreverr0;  /* unload prev errs into array */
01568       errorptr[1] = (FSERROR) bpreverr1;
01569       errorptr[2] = (FSERROR) bpreverr2;
01570     }
01571 }
01572 
01573 
01574 /*
01575  * Initialize the error-limiting transfer function (lookup table).
01576  * The raw F-S error computation can potentially compute error values of up to
01577  * +- MAXJSAMPLE.  But we want the maximum correction applied to a pixel to be
01578  * much less, otherwise obviously wrong pixels will be created.  (Typical
01579  * effects include weird fringes at color-area boundaries, isolated bright
01580  * pixels in a dark area, etc.)  The standard advice for avoiding this problem
01581  * is to ensure that the "corners" of the color cube are allocated as output
01582  * colors; then repeated errors in the same direction cannot cause cascading
01583  * error buildup.  However, that only prevents the error from getting
01584  * completely out of hand; Aaron Giles reports that error limiting improves
01585  * the results even with corner colors allocated.
01586  * A simple clamping of the error values to about +- MAXJSAMPLE/8 works pretty
01587  * well, but the smoother transfer function used below is even better.  Thanks
01588  * to Aaron Giles for this idea.
01589  */
01590 
01591 LOCAL (void)
01592 #ifdef ORIGINAL_LIB_JPEG
01593 init_error_limit (j_decompress_ptr cinfo)
01594 #else
01595 init_error_limit (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
01596 #endif
01597 /* Allocate and fill in the error_limiter table */
01598 {
01599   int *table;
01600   int in, out;
01601 #ifdef ORIGINAL_LIB_JPEG
01602   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
01603   table = (int *) (*cinfo->mem->alloc_small)
01604     ((j_common_ptr) cinfo, JPOOL_IMAGE, (MAXJSAMPLE * 2 + 1) * SIZEOF (int));
01605 #else
01606   cquantize->error_limiter_storage =
01607     (int *) gdMalloc ((MAXJSAMPLE * 2 + 1) * sizeof (int));
01608   if (!cquantize->error_limiter_storage)
01609     {
01610       return;
01611     }
01612   table = cquantize->error_limiter_storage;
01613 #endif
01614 
01615   table += MAXJSAMPLE;             /* so can index -MAXJSAMPLE .. +MAXJSAMPLE */
01616   cquantize->error_limiter = table;
01617 
01618 #define STEPSIZE ((MAXJSAMPLE+1)/16)
01619   /* Map errors 1:1 up to +- MAXJSAMPLE/16 */
01620   out = 0;
01621   for (in = 0; in < STEPSIZE; in++, out++)
01622     {
01623       table[in] = out;
01624       table[-in] = -out;
01625     }
01626   /* Map errors 1:2 up to +- 3*MAXJSAMPLE/16 */
01627   for (; in < STEPSIZE * 3; in++, out += (in & 1) ? 0 : 1)
01628     {
01629       table[in] = out;
01630       table[-in] = -out;
01631     }
01632   /* Clamp the rest to final out value (which is (MAXJSAMPLE+1)/8) */
01633   for (; in <= MAXJSAMPLE; in++)
01634     {
01635       table[in] = out;
01636       table[-in] = -out;
01637     }
01638 #undef STEPSIZE
01639 }
01640 
01641 
01642 /*
01643  * Finish up at the end of each pass.
01644  */
01645 
01646 #ifdef ORIGINAL_LIB_JPEG
01647 METHODDEF (void)
01648 finish_pass1 (j_decompress_ptr cinfo)
01649 {
01650   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
01651 
01652   /* Select the representative colors and fill in cinfo->colormap */
01653   cinfo->colormap = cquantize->sv_colormap;
01654   select_colors (cinfo, cquantize->desired);
01655   /* Force next pass to zero the color index table */
01656   cquantize->needs_zeroed = TRUE;
01657 }
01658 
01659 
01660 METHODDEF (void)
01661 finish_pass2 (j_decompress_ptr cinfo)
01662 {
01663   /* no work */
01664 }
01665 
01666 /*
01667  * Initialize for each processing pass.
01668  */
01669 
01670 METHODDEF (void)
01671 start_pass_2_quant (j_decompress_ptr cinfo, boolean is_pre_scan)
01672 {
01673   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
01674   hist3d histogram = cquantize->histogram;
01675   int i;
01676 
01677   /* Only F-S dithering or no dithering is supported. */
01678   /* If user asks for ordered dither, give him F-S. */
01679   if (cinfo->dither_mode != JDITHER_NONE)
01680     cinfo->dither_mode = JDITHER_FS;
01681 
01682   if (is_pre_scan)
01683     {
01684       /* Set up method pointers */
01685       cquantize->pub.color_quantize = prescan_quantize;
01686       cquantize->pub.finish_pass = finish_pass1;
01687       cquantize->needs_zeroed = TRUE;     /* Always zero histogram */
01688     }
01689   else
01690     {
01691       /* Set up method pointers */
01692       if (cinfo->dither_mode == JDITHER_FS)
01693        cquantize->pub.color_quantize = pass2_fs_dither;
01694       else
01695        cquantize->pub.color_quantize = pass2_no_dither;
01696       cquantize->pub.finish_pass = finish_pass2;
01697 
01698       /* Make sure color count is acceptable */
01699       i = cinfo->actual_number_of_colors;
01700       if (i < 1)
01701        ERREXIT1 (cinfo, JERR_QUANT_FEW_COLORS, 1);
01702       if (i > MAXNUMCOLORS)
01703        ERREXIT1 (cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS);
01704 
01705       if (cinfo->dither_mode == JDITHER_FS)
01706        {
01707          size_t arraysize = (size_t) ((cinfo->output_width + 2) *
01708                                    (3 * SIZEOF (FSERROR)));
01709          /* Allocate Floyd-Steinberg workspace if we didn't already. */
01710          if (cquantize->fserrors == NULL)
01711            cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large)
01712              ((j_common_ptr) cinfo, JPOOL_IMAGE, arraysize);
01713          /* Initialize the propagated errors to zero. */
01714          jzero_far ((void FAR *) cquantize->fserrors, arraysize);
01715          /* Make the error-limit table if we didn't already. */
01716          if (cquantize->error_limiter == NULL)
01717            init_error_limit (cinfo);
01718          cquantize->on_odd_row = FALSE;
01719        }
01720 
01721     }
01722   /* Zero the histogram or inverse color map, if necessary */
01723   if (cquantize->needs_zeroed)
01724     {
01725       for (i = 0; i < HIST_C0_ELEMS; i++)
01726        {
01727          jzero_far ((void FAR *) histogram[i],
01728                    HIST_C1_ELEMS * HIST_C2_ELEMS * SIZEOF (histcell));
01729        }
01730       cquantize->needs_zeroed = FALSE;
01731     }
01732 }
01733 
01734 
01735 /*
01736  * Switch to a new external colormap between output passes.
01737  */
01738 
01739 METHODDEF (void)
01740 new_color_map_2_quant (j_decompress_ptr cinfo)
01741 {
01742   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
01743 
01744   /* Reset the inverse color map */
01745   cquantize->needs_zeroed = TRUE;
01746 }
01747 #else
01748 static void
01749 zeroHistogram (hist3d histogram)
01750 {
01751   int i;
01752   /* Zero the histogram or inverse color map */
01753   for (i = 0; i < HIST_C0_ELEMS; i++)
01754     {
01755       memset (histogram[i],
01756              0, HIST_C1_ELEMS * HIST_C2_ELEMS * sizeof (histcell));
01757     }
01758 }
01759 #endif
01760 
01761 static void gdImageTrueColorToPaletteBody (gdImagePtr oim, int dither, int colorsWanted, gdImagePtr *cimP);
01762 
01763 BGD_DECLARE(gdImagePtr) gdImageCreatePaletteFromTrueColor (gdImagePtr im, int dither, int colorsWanted)
01764 {
01765        gdImagePtr nim;
01766        gdImageTrueColorToPaletteBody(im, dither, colorsWanted, &nim);
01767        return nim;
01768 }
01769 
01770 BGD_DECLARE(void) gdImageTrueColorToPalette (gdImagePtr im, int dither, int colorsWanted)
01771 {
01772        gdImageTrueColorToPaletteBody(im, dither, colorsWanted, 0);
01773 }
01774 
01775 /*
01776  * Module initialization routine for 2-pass color quantization.
01777  */
01778 
01779 #ifdef ORIGINAL_LIB_JPEG
01780 GLOBAL (void)
01781 jinit_2pass_quantizer (j_decompress_ptr cinfo)
01782 #else
01783 static void gdImageTrueColorToPaletteBody (gdImagePtr oim, int dither, int colorsWanted, gdImagePtr *cimP)
01784 #endif
01785 {
01786   my_cquantize_ptr cquantize = NULL;
01787   int i;
01788 
01789 #ifndef ORIGINAL_LIB_JPEG
01790   /* Allocate the JPEG palette-storage */
01791   size_t arraysize;
01792   int maxColors = gdMaxColors;
01793   gdImagePtr nim;
01794   if (cimP) {
01795     nim = gdImageCreate(oim->sx, oim->sy);
01796     *cimP = nim;
01797     if (!nim) {
01798       return;
01799     }
01800   } else {
01801     nim = oim;
01802   }     
01803   if (!oim->trueColor)
01804     {
01805       /* (Almost) nothing to do! */
01806       if (cimP) {
01807         gdImageCopy(nim, oim, 0, 0, 0, 0, oim->sx, oim->sy);
01808         *cimP = nim;
01809       }
01810       return;
01811     }
01812 
01813   /* If we have a transparent color (the alphaless mode of transparency), we
01814    * must reserve a palette entry for it at the end of the palette. */
01815   if (oim->transparent >= 0)
01816     {
01817       maxColors--;
01818     }
01819   if (colorsWanted > maxColors)
01820     {
01821       colorsWanted = maxColors;
01822     }
01823   if (!cimP) {
01824     nim->pixels = gdCalloc (sizeof (unsigned char *), oim->sy);
01825     if (!nim->pixels)
01826       {
01827         /* No can do */
01828         goto outOfMemory;
01829       }
01830     for (i = 0; (i < nim->sy); i++)
01831       {
01832         nim->pixels[i] = gdCalloc (sizeof (unsigned char *), oim->sx);
01833         if (!nim->pixels[i])
01834        {
01835          goto outOfMemory;
01836        }
01837       }
01838   }
01839 #endif
01840 
01841 #ifdef ORIGINAL_LIB_JPEG
01842   cquantize = (my_cquantize_ptr)
01843     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
01844                             SIZEOF (my_cquantizer));
01845   cinfo->cquantize = (struct jpeg_color_quantizer *) cquantize;
01846   cquantize->pub.start_pass = start_pass_2_quant;
01847   cquantize->pub.new_color_map = new_color_map_2_quant;
01848   /* Make sure jdmaster didn't give me a case I can't handle */
01849   if (cinfo->out_color_components != 3)
01850     ERREXIT (cinfo, JERR_NOTIMPL);
01851 #else
01852   cquantize = (my_cquantize_ptr) gdCalloc (sizeof (my_cquantizer), 1);
01853   if (!cquantize)
01854     {
01855       /* No can do */
01856       goto outOfMemory;
01857     }
01858 #endif
01859   cquantize->fserrors = NULL;      /* flag optional arrays not allocated */
01860   cquantize->error_limiter = NULL;
01861 
01862 
01863   /* Allocate the histogram/inverse colormap storage */
01864 #ifdef ORIGINAL_LIB_JPEG
01865   cquantize->histogram = (hist3d) (*cinfo->mem->alloc_small)
01866     ((j_common_ptr) cinfo, JPOOL_IMAGE, HIST_C0_ELEMS * SIZEOF (hist2d));
01867   for (i = 0; i < HIST_C0_ELEMS; i++)
01868     {
01869       cquantize->histogram[i] = (hist2d) (*cinfo->mem->alloc_large)
01870        ((j_common_ptr) cinfo, JPOOL_IMAGE,
01871         HIST_C1_ELEMS * HIST_C2_ELEMS * SIZEOF (histcell));
01872     }
01873   cquantize->needs_zeroed = TRUE;  /* histogram is garbage now */
01874 #else
01875   cquantize->histogram = (hist3d) gdMalloc (HIST_C0_ELEMS * sizeof (hist2d));
01876   for (i = 0; i < HIST_C0_ELEMS; i++)
01877     {
01878       cquantize->histogram[i] =
01879        (hist2d) gdMalloc (HIST_C1_ELEMS * HIST_C2_ELEMS * sizeof (histcell));
01880       if (!cquantize->histogram[i])
01881        {
01882          goto outOfMemory;
01883        }
01884     }
01885 #endif
01886 
01887 #ifdef ORIGINAL_LIB_JPEG
01888   /* Allocate storage for the completed colormap, if required.
01889    * We do this now since it is FAR storage and may affect
01890    * the memory manager's space calculations.
01891    */
01892   if (cinfo->enable_2pass_quant)
01893     {
01894       /* Make sure color count is acceptable */
01895       int desired = cinfo->desired_number_of_colors;
01896       /* Lower bound on # of colors ... somewhat arbitrary as long as > 0 */
01897       if (desired < 8)
01898        ERREXIT1 (cinfo, JERR_QUANT_FEW_COLORS, 8);
01899       /* Make sure colormap indexes can be represented by JSAMPLEs */
01900       if (desired > MAXNUMCOLORS)
01901        ERREXIT1 (cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS);
01902       cquantize->sv_colormap = (*cinfo->mem->alloc_sarray)
01903        ((j_common_ptr) cinfo, JPOOL_IMAGE, (JDIMENSION) desired,
01904         (JDIMENSION) 3);
01905       cquantize->desired = desired;
01906     }
01907   else
01908     cquantize->sv_colormap = NULL;
01909 
01910   /* Only F-S dithering or no dithering is supported. */
01911   /* If user asks for ordered dither, give him F-S. */
01912   if (cinfo->dither_mode != JDITHER_NONE)
01913     cinfo->dither_mode = JDITHER_FS;
01914 
01915   /* Allocate Floyd-Steinberg workspace if necessary.
01916    * This isn't really needed until pass 2, but again it is FAR storage.
01917    * Although we will cope with a later change in dither_mode,
01918    * we do not promise to honor max_memory_to_use if dither_mode changes.
01919    */
01920   if (cinfo->dither_mode == JDITHER_FS)
01921     {
01922       cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large)
01923        ((j_common_ptr) cinfo, JPOOL_IMAGE,
01924         (size_t) ((cinfo->output_width + 2) * (3 * SIZEOF (FSERROR))));
01925       /* Might as well create the error-limiting table too. */
01926       init_error_limit (cinfo);
01927     }
01928 #else
01929 
01930   cquantize->fserrors = (FSERRPTR) gdMalloc (3 * sizeof (FSERROR));
01931   init_error_limit (oim, nim, cquantize);
01932   arraysize = (size_t) ((nim->sx + 2) * (3 * sizeof (FSERROR)));
01933   /* Allocate Floyd-Steinberg workspace. */
01934   cquantize->fserrors = gdCalloc (arraysize, 1);
01935   if (!cquantize->fserrors)
01936     {
01937       goto outOfMemory;
01938     }
01939   cquantize->on_odd_row = FALSE;
01940 
01941   /* Do the work! */
01942   zeroHistogram (cquantize->histogram);
01943   prescan_quantize (oim, nim, cquantize);
01944   /* TBB 2.0.5: pass colorsWanted, not 256! */
01945   select_colors (oim, nim, cquantize, colorsWanted);
01946   zeroHistogram (cquantize->histogram);
01947   if (dither)
01948     {
01949       pass2_fs_dither (oim, nim, cquantize);
01950     }
01951   else
01952     {
01953       pass2_no_dither (oim, nim, cquantize);
01954     }
01955 #if 0                       /* 2.0.12; we no longer attempt full alpha in palettes */
01956   if (cquantize->transparentIsPresent)
01957     {
01958       int mt = -1;
01959       int mtIndex = -1;
01960       for (i = 0; (i < im->colorsTotal); i++)
01961        {
01962          if (im->alpha[i] > mt)
01963            {
01964              mtIndex = i;
01965              mt = im->alpha[i];
01966            }
01967        }
01968       for (i = 0; (i < im->colorsTotal); i++)
01969        {
01970          if (im->alpha[i] == mt)
01971            {
01972              im->alpha[i] = gdAlphaTransparent;
01973            }
01974        }
01975     }
01976   if (cquantize->opaqueIsPresent)
01977     {
01978       int mo = 128;
01979       int moIndex = -1;
01980       for (i = 0; (i < im->colorsTotal); i++)
01981        {
01982          if (im->alpha[i] < mo)
01983            {
01984              moIndex = i;
01985              mo = im->alpha[i];
01986            }
01987        }
01988       for (i = 0; (i < im->colorsTotal); i++)
01989        {
01990          if (im->alpha[i] == mo)
01991            {
01992              im->alpha[i] = gdAlphaOpaque;
01993            }
01994        }
01995     }
01996 #endif
01997 
01998   /* If we had a 'transparent' color, increment the color count so it's
01999    * officially in the palette and convert the transparent variable to point to
02000    * an index rather than a color (Its data already exists and transparent
02001    * pixels have already been mapped to it by this point, it is done late as to
02002    * avoid color matching / dithering with it). */
02003   if (oim->transparent >= 0)
02004     {
02005       nim->transparent = nim->colorsTotal;
02006       nim->colorsTotal++;
02007     }
02008 
02009   /* Success! Get rid of the truecolor image data. */
02010   if (!cimP) { 
02011     oim->trueColor = 0;
02012     /* Junk the truecolor pixels */
02013     for (i = 0; i < oim->sy; i++)
02014       {
02015         gdFree (oim->tpixels[i]);
02016       }
02017     gdFree (oim->tpixels);
02018     oim->tpixels = 0;
02019   }
02020   goto success;
02021   /* Tediously free stuff. */
02022 outOfMemory:
02023   if (oim->trueColor)
02024     {
02025       if (!cimP) {
02026         /* On failure only */
02027         for (i = 0; i < nim->sy; i++)
02028        {
02029          if (nim->pixels[i])
02030            {
02031              gdFree (nim->pixels[i]);
02032            }
02033        }
02034         if (nim->pixels)
02035        {
02036          gdFree (nim->pixels);
02037        }
02038         nim->pixels = 0;
02039       } else {
02040         gdImageDestroy(nim);
02041         *cimP = 0;
02042       }
02043     }
02044 success:
02045   for (i = 0; i < HIST_C0_ELEMS; i++)
02046     {
02047       if (cquantize->histogram[i])
02048        {
02049          gdFree (cquantize->histogram[i]);
02050        }
02051     }
02052   if (cquantize->histogram)
02053     {
02054       gdFree (cquantize->histogram);
02055     }
02056   if (cquantize->fserrors)
02057     {
02058       gdFree (cquantize->fserrors);
02059     }
02060   if (cquantize->error_limiter_storage)
02061     {
02062       gdFree (cquantize->error_limiter_storage);
02063     }
02064   if (cquantize)
02065     {
02066       gdFree (cquantize);
02067     }
02068 
02069 #endif
02070 }
02071 
02072 #endif