root/ext/gd/libgd/gd_topal.c

DEFINITIONS

1. METHODDEF
2. prescan_quantize
3. LOCAL
4. LOCAL
5. LOCAL
6. update_box
7. LOCAL
8. LOCAL
9. compute_color
10. LOCAL
11. LOCAL
12. LOCAL
13. LOCAL
14. METHODDEF
15. pass2_no_dither
16. METHODDEF
17. pass2_fs_dither
18. LOCAL
19. METHODDEF
20. METHODDEF
21. METHODDEF
22. METHODDEF
23. zeroHistogram
24. gdImageCreatePaletteFromTrueColor
25. gdImageTrueColorToPalette
26. GLOBAL

   1 /* TODO: oim and nim in the lower level functions;
   2   correct use of stub (sigh). */
   3 
   4 /* 2.0.12: a new adaptation from the same original, this time
   5         by Barend Gehrels. My attempt to incorporate alpha channel
   6         into the result worked poorly and degraded the quality of
   7         palette conversion even when the source contained no
   8         alpha channel data. This version does not attempt to produce
   9         an output file with transparency in some of the palette
  10         indexes, which, in practice, doesn't look so hot anyway. TBB */
  11 
  12 /*
  13  * gd_topal, adapted from jquant2.c
  14  *
  15  * Copyright (C) 1991-1996, Thomas G. Lane.
  16  * This file is part of the Independent JPEG Group's software.
  17  * For conditions of distribution and use, see the accompanying README file.
  18  *
  19  * This file contains 2-pass color quantization (color mapping) routines.
  20  * These routines provide selection of a custom color map for an image,
  21  * followed by mapping of the image to that color map, with optional
  22  * Floyd-Steinberg dithering.
  23  * It is also possible to use just the second pass to map to an arbitrary
  24  * externally-given color map.
  25  *
  26  * Note: ordered dithering is not supported, since there isn't any fast
  27  * way to compute intercolor distances; it's unclear that ordered dither's
  28  * fundamental assumptions even hold with an irregularly spaced color map.
  29  */
  30 
  31 #ifdef ORIGINAL_LIB_JPEG
  32 
  33 #define JPEG_INTERNALS
  34 
  35 #include "jinclude.h"
  36 #include "jpeglib.h"
  37 
  38 #else
  39 
  40 /*
  41  * THOMAS BOUTELL & BAREND GEHRELS, february 2003
  42  * adapted the code to work within gd rather than within libjpeg.
  43  * If it is not working, it's not Thomas G. Lane's fault.
  44  */
  45 
  46 /*
  47   SETTING THIS ONE CAUSES STRIPED IMAGE
  48   to be done: solve this
  49   #define ORIGINAL_LIB_JPEG_REVERSE_ODD_ROWS
  50  */
  51 
  52 #include <string.h>
  53 #include "gd.h"
  54 #include "gdhelpers.h"
  55 
  56 /* (Re)define some defines known by libjpeg */
  57 #define QUANT_2PASS_SUPPORTED
  58 
  59 #define RGB_RED         0
  60 #define RGB_GREEN       1
  61 #define RGB_BLUE        2
  62 
  63 #define JSAMPLE unsigned char
  64 #define MAXJSAMPLE (gdMaxColors-1)
  65 #define BITS_IN_JSAMPLE 8
  66 
  67 #define JSAMPROW int*
  68 #define JDIMENSION int
  69 
  70 #define METHODDEF(type) static type
  71 #define LOCAL(type)     static type
  72 
  73 
  74 /* We assume that right shift corresponds to signed division by 2 with
  75  * rounding towards minus infinity.  This is correct for typical "arithmetic
  76  * shift" instructions that shift in copies of the sign bit.  But some
  77  * C compilers implement >> with an unsigned shift.  For these machines you
  78  * must define RIGHT_SHIFT_IS_UNSIGNED.
  79  * RIGHT_SHIFT provides a proper signed right shift of an INT32 quantity.
  80  * It is only applied with constant shift counts.  SHIFT_TEMPS must be
  81  * included in the variables of any routine using RIGHT_SHIFT.
  82  */
  83 
  84 #ifdef RIGHT_SHIFT_IS_UNSIGNED
  85 #define SHIFT_TEMPS     INT32 shift_temp;
  86 #define RIGHT_SHIFT(x,shft)  \
  87         ((shift_temp = (x)) < 0 ? \
  88          (shift_temp >> (shft)) | ((~((INT32) 0)) << (32-(shft))) : \
  89          (shift_temp >> (shft)))
  90 #else
  91 #define SHIFT_TEMPS
  92 #define RIGHT_SHIFT(x,shft)     ((x) >> (shft))
  93 #endif
  94 
  95 
  96 #define range_limit(x) { if(x<0) x=0; if (x>255) x=255; }
  97 
  98 
  99 #ifndef INT16
 100 #define INT16  short
 101 #endif
 102 
 103 #ifndef UINT16
 104 #define UINT16 unsigned short
 105 #endif
 106 
 107 #ifndef INT32
 108 #define INT32 int
 109 #endif
 110 
 111 #ifndef FAR
 112 #define FAR
 113 #endif
 114 
 115 
 116 
 117 #ifndef boolean
 118 #define boolean int
 119 #endif
 120 
 121 #ifndef TRUE
 122 #define TRUE 1
 123 #endif
 124 
 125 #ifndef FALSE
 126 #define FALSE 0
 127 #endif
 128 
 129 
 130 #define input_buf (oim->tpixels)
 131 #define output_buf (nim->pixels)
 132 
 133 #endif
 134 
 135 #ifdef QUANT_2PASS_SUPPORTED
 136 
 137 
 138 /*
 139  * This module implements the well-known Heckbert paradigm for color
 140  * quantization.  Most of the ideas used here can be traced back to
 141  * Heckbert's seminal paper
 142  *   Heckbert, Paul.  "Color Image Quantization for Frame Buffer Display",
 143  *   Proc. SIGGRAPH '82, Computer Graphics v.16 #3 (July 1982), pp 297-304.
 144  *
 145  * In the first pass over the image, we accumulate a histogram showing the
 146  * usage count of each possible color.  To keep the histogram to a reasonable
 147  * size, we reduce the precision of the input; typical practice is to retain
 148  * 5 or 6 bits per color, so that 8 or 4 different input values are counted
 149  * in the same histogram cell.
 150  *
 151  * Next, the color-selection step begins with a box representing the whole
 152  * color space, and repeatedly splits the "largest" remaining box until we
 153  * have as many boxes as desired colors.  Then the mean color in each
 154  * remaining box becomes one of the possible output colors.
 155  *
 156  * The second pass over the image maps each input pixel to the closest output
 157  * color (optionally after applying a Floyd-Steinberg dithering correction).
 158  * This mapping is logically trivial, but making it go fast enough requires
 159  * considerable care.
 160  *
 161  * Heckbert-style quantizers vary a good deal in their policies for choosing
 162  * the "largest" box and deciding where to cut it.  The particular policies
 163  * used here have proved out well in experimental comparisons, but better ones
 164  * may yet be found.
 165  *
 166  * In earlier versions of the IJG code, this module quantized in YCbCr color
 167  * space, processing the raw upsampled data without a color conversion step.
 168  * This allowed the color conversion math to be done only once per colormap
 169  * entry, not once per pixel.  However, that optimization precluded other
 170  * useful optimizations (such as merging color conversion with upsampling)
 171  * and it also interfered with desired capabilities such as quantizing to an
 172  * externally-supplied colormap.  We have therefore abandoned that approach.
 173  * The present code works in the post-conversion color space, typically RGB.
 174  *
 175  * To improve the visual quality of the results, we actually work in scaled
 176  * RGB space, giving G distances more weight than R, and R in turn more than
 177  * B.  To do everything in integer math, we must use integer scale factors.
 178  * The 2/3/1 scale factors used here correspond loosely to the relative
 179  * weights of the colors in the NTSC grayscale equation.
 180  * If you want to use this code to quantize a non-RGB color space, you'll
 181  * probably need to change these scale factors.
 182  */
 183 
 184 #define R_SCALE 2               /* scale R distances by this much */
 185 #define G_SCALE 3               /* scale G distances by this much */
 186 #define B_SCALE 1               /* and B by this much */
 187 
 188 /* Relabel R/G/B as components 0/1/2, respecting the RGB ordering defined
 189  * in jmorecfg.h.  As the code stands, it will do the right thing for R,G,B
 190  * and B,G,R orders.  If you define some other weird order in jmorecfg.h,
 191  * you'll get compile errors until you extend this logic.  In that case
 192  * you'll probably want to tweak the histogram sizes too.
 193  */
 194 
 195 #if RGB_RED == 0
 196 #define C0_SCALE R_SCALE
 197 #endif
 198 #if RGB_BLUE == 0
 199 #define C0_SCALE B_SCALE
 200 #endif
 201 #if RGB_GREEN == 1
 202 #define C1_SCALE G_SCALE
 203 #endif
 204 #if RGB_RED == 2
 205 #define C2_SCALE R_SCALE
 206 #endif
 207 #if RGB_BLUE == 2
 208 #define C2_SCALE B_SCALE
 209 #endif
 210 
 211 
 212 /*
 213  * First we have the histogram data structure and routines for creating it.
 214  *
 215  * The number of bits of precision can be adjusted by changing these symbols.
 216  * We recommend keeping 6 bits for G and 5 each for R and B.
 217  * If you have plenty of memory and cycles, 6 bits all around gives marginally
 218  * better results; if you are short of memory, 5 bits all around will save
 219  * some space but degrade the results.
 220  * To maintain a fully accurate histogram, we'd need to allocate a "long"
 221  * (preferably unsigned long) for each cell.  In practice this is overkill;
 222  * we can get by with 16 bits per cell.  Few of the cell counts will overflow,
 223  * and clamping those that do overflow to the maximum value will give close-
 224  * enough results.  This reduces the recommended histogram size from 256Kb
 225  * to 128Kb, which is a useful savings on PC-class machines.
 226  * (In the second pass the histogram space is re-used for pixel mapping data;
 227  * in that capacity, each cell must be able to store zero to the number of
 228  * desired colors.  16 bits/cell is plenty for that too.)
 229  * Since the JPEG code is intended to run in small memory model on 80x86
 230  * machines, we can't just allocate the histogram in one chunk.  Instead
 231  * of a true 3-D array, we use a row of pointers to 2-D arrays.  Each
 232  * pointer corresponds to a C0 value (typically 2^5 = 32 pointers) and
 233  * each 2-D array has 2^6*2^5 = 2048 or 2^6*2^6 = 4096 entries.  Note that
 234  * on 80x86 machines, the pointer row is in near memory but the actual
 235  * arrays are in far memory (same arrangement as we use for image arrays).
 236  */
 237 
 238 #define MAXNUMCOLORS  (MAXJSAMPLE+1)    /* maximum size of colormap */
 239 
 240 /* These will do the right thing for either R,G,B or B,G,R color order,
 241  * but you may not like the results for other color orders.
 242  */
 243 #define HIST_C0_BITS  5         /* bits of precision in R/B histogram */
 244 #define HIST_C1_BITS  6         /* bits of precision in G histogram */
 245 #define HIST_C2_BITS  5         /* bits of precision in B/R histogram */
 246 
 247 /* Number of elements along histogram axes. */
 248 #define HIST_C0_ELEMS  (1<<HIST_C0_BITS)
 249 #define HIST_C1_ELEMS  (1<<HIST_C1_BITS)
 250 #define HIST_C2_ELEMS  (1<<HIST_C2_BITS)
 251 
 252 /* These are the amounts to shift an input value to get a histogram index. */
 253 #define C0_SHIFT  (BITS_IN_JSAMPLE-HIST_C0_BITS)
 254 #define C1_SHIFT  (BITS_IN_JSAMPLE-HIST_C1_BITS)
 255 #define C2_SHIFT  (BITS_IN_JSAMPLE-HIST_C2_BITS)
 256 
 257 
 258 typedef UINT16 histcell;        /* histogram cell; prefer an unsigned type */
 259 
 260 typedef histcell FAR *histptr;  /* for pointers to histogram cells */
 261 
 262 typedef histcell hist1d[HIST_C2_ELEMS]; /* typedefs for the array */
 263 typedef hist1d FAR *hist2d;     /* type for the 2nd-level pointers */
 264 typedef hist2d *hist3d;         /* type for top-level pointer */
 265 
 266 
 267 /* Declarations for Floyd-Steinberg dithering.
 268  *
 269  * Errors are accumulated into the array fserrors[], at a resolution of
 270  * 1/16th of a pixel count.  The error at a given pixel is propagated
 271  * to its not-yet-processed neighbors using the standard F-S fractions,
 272  *              ...     (here)  7/16
 273  *              3/16    5/16    1/16
 274  * We work left-to-right on even rows, right-to-left on odd rows.
 275  *
 276  * We can get away with a single array (holding one row's worth of errors)
 277  * by using it to store the current row's errors at pixel columns not yet
 278  * processed, but the next row's errors at columns already processed.  We
 279  * need only a few extra variables to hold the errors immediately around the
 280  * current column.  (If we are lucky, those variables are in registers, but
 281  * even if not, they're probably cheaper to access than array elements are.)
 282  *
 283  * The fserrors[] array has (#columns + 2) entries; the extra entry at
 284  * each end saves us from special-casing the first and last pixels.
 285  * Each entry is three values long, one value for each color component.
 286  *
 287  * Note: on a wide image, we might not have enough room in a PC's near data
 288  * segment to hold the error array; so it is allocated with alloc_large.
 289  */
 290 
 291 #if BITS_IN_JSAMPLE == 8
 292 typedef INT16 FSERROR;          /* 16 bits should be enough */
 293 typedef int LOCFSERROR;         /* use 'int' for calculation temps */
 294 #else
 295 typedef INT32 FSERROR;          /* may need more than 16 bits */
 296 typedef INT32 LOCFSERROR;       /* be sure calculation temps are big enough */
 297 #endif
 298 
 299 typedef FSERROR FAR *FSERRPTR;  /* pointer to error array (in FAR storage!) */
 300 
 301 
 302 /* Private subobject */
 303 
 304 typedef struct
 305 {
 306 #ifdef ORIGINAL_LIB_JPEG
 307   struct jpeg_color_quantizer pub;      /* public fields */
 308 
 309   /* Space for the eventually created colormap is stashed here */
 310   JSAMPARRAY sv_colormap;       /* colormap allocated at init time */
 311   int desired;                  /* desired # of colors = size of colormap */
 312   boolean needs_zeroed;         /* TRUE if next pass must zero histogram */
 313 #endif
 314 
 315   /* Variables for accumulating image statistics */
 316   hist3d histogram;             /* pointer to the histogram */
 317 
 318 
 319   /* Variables for Floyd-Steinberg dithering */
 320   FSERRPTR fserrors;            /* accumulated errors */
 321 
 322   boolean on_odd_row;           /* flag to remember which row we are on */
 323   int *error_limiter;           /* table for clamping the applied error */
 324 #ifndef ORIGINAL_LIB_JPEG
 325   int *error_limiter_storage;   /* gdMalloc'd storage for the above */
 326 #endif
 327 }
 328 my_cquantizer;
 329 
 330 typedef my_cquantizer *my_cquantize_ptr;
 331 
 332 
 333 /*
 334  * Prescan some rows of pixels.
 335  * In this module the prescan simply updates the histogram, which has been
 336  * initialized to zeroes by start_pass.
 337  * An output_buf parameter is required by the method signature, but no data
 338  * is actually output (in fact the buffer controller is probably passing a
 339  * NULL pointer).
 340  */
 341 
 342 METHODDEF (void)
 343 #ifndef ORIGINAL_LIB_JPEG
 344 prescan_quantize (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
 345 {
 346 #else
 347 prescan_quantize (j_decompress_ptr cinfo, JSAMPARRAY input_buf,
 348                   JSAMPARRAY output_buf, int num_rows)
 349 {
 350   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
 351 #endif
 352   register JSAMPROW ptr;
 353   register histptr histp;
 354   register hist3d histogram = cquantize->histogram;
 355   int row;
 356   JDIMENSION col;
 357 #ifdef ORIGINAL_LIB_JPEG
 358   JDIMENSION width = cinfo->output_width;
 359 #else
 360   int width = oim->sx;
 361   int num_rows = oim->sy;
 362 #endif
 363 
 364   for (row = 0; row < num_rows; row++)
 365     {
 366       ptr = input_buf[row];
 367       for (col = width; col > 0; col--)
 368         {
 369 #ifdef ORIGINAL_LIB_JPEG
 370           int r = GETJSAMPLE (ptr[0]) >> C0_SHIFT;
 371           int g = GETJSAMPLE (ptr[1]) >> C1_SHIFT;
 372           int b = GETJSAMPLE (ptr[2]) >> C2_SHIFT;
 373 #else
 374           int r = gdTrueColorGetRed (*ptr) >> C0_SHIFT;
 375           int g = gdTrueColorGetGreen (*ptr) >> C1_SHIFT;
 376           int b = gdTrueColorGetBlue (*ptr) >> C2_SHIFT;
 377           /* 2.0.12: Steven Brown: support a single totally transparent
 378              color in the original. */
 379           if ((oim->transparent >= 0) && (*ptr == oim->transparent))
 380             {
 381               ptr++;
 382               continue;
 383             }
 384 #endif
 385           /* get pixel value and index into the histogram */
 386           histp = &histogram[r][g][b];
 387           /* increment, check for overflow and undo increment if so. */
 388           if (++(*histp) == 0)
 389             (*histp)--;
 390 #ifdef ORIGINAL_LIB_JPEG
 391           ptr += 3;
 392 #else
 393           ptr++;
 394 #endif
 395         }
 396     }
 397 }
 398 
 399 
 400 /*
 401  * Next we have the really interesting routines: selection of a colormap
 402  * given the completed histogram.
 403  * These routines work with a list of "boxes", each representing a rectangular
 404  * subset of the input color space (to histogram precision).
 405  */
 406 
 407 typedef struct
 408 {
 409   /* The bounds of the box (inclusive); expressed as histogram indexes */
 410   int c0min, c0max;
 411   int c1min, c1max;
 412   int c2min, c2max;
 413   /* The volume (actually 2-norm) of the box */
 414   INT32 volume;
 415   /* The number of nonzero histogram cells within this box */
 416   long colorcount;
 417 }
 418 box;
 419 
 420 typedef box *boxptr;
 421 
 422 
 423 LOCAL (boxptr) find_biggest_color_pop (boxptr boxlist, int numboxes)
 424 /* Find the splittable box with the largest color population */
 425 /* Returns NULL if no splittable boxes remain */
 426 {
 427   register boxptr boxp;
 428   register int i;
 429   register long maxc = 0;
 430   boxptr which = NULL;
 431 
 432   for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++)
 433     {
 434       if (boxp->colorcount > maxc && boxp->volume > 0)
 435         {
 436           which = boxp;
 437           maxc = boxp->colorcount;
 438         }
 439     }
 440   return which;
 441 }
 442 
 443 
 444 LOCAL (boxptr) find_biggest_volume (boxptr boxlist, int numboxes)
 445 /* Find the splittable box with the largest (scaled) volume */
 446 /* Returns NULL if no splittable boxes remain */
 447 {
 448   register boxptr boxp;
 449   register int i;
 450   register INT32 maxv = 0;
 451   boxptr which = NULL;
 452 
 453   for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++)
 454     {
 455       if (boxp->volume > maxv)
 456         {
 457           which = boxp;
 458           maxv = boxp->volume;
 459         }
 460     }
 461   return which;
 462 }
 463 
 464 
 465 LOCAL (void)
 466 #ifndef ORIGINAL_LIB_JPEG
 467   update_box (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize, boxptr boxp)
 468 {
 469 #else
 470   update_box (j_decompress_ptr cinfo, boxptr boxp)
 471 /* Shrink the min/max bounds of a box to enclose only nonzero elements, */
 472 /* and recompute its volume and population */
 473 {
 474   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
 475 #endif
 476   hist3d histogram = cquantize->histogram;
 477   histptr histp;
 478   int c0, c1, c2;
 479   int c0min, c0max, c1min, c1max, c2min, c2max;
 480   INT32 dist0, dist1, dist2;
 481   long ccount;
 482 
 483   c0min = boxp->c0min;
 484   c0max = boxp->c0max;
 485   c1min = boxp->c1min;
 486   c1max = boxp->c1max;
 487   c2min = boxp->c2min;
 488   c2max = boxp->c2max;
 489 
 490   if (c0max > c0min)
 491     for (c0 = c0min; c0 <= c0max; c0++)
 492       for (c1 = c1min; c1 <= c1max; c1++)
 493         {
 494           histp = &histogram[c0][c1][c2min];
 495           for (c2 = c2min; c2 <= c2max; c2++)
 496             if (*histp++ != 0)
 497               {
 498                 boxp->c0min = c0min = c0;
 499                 goto have_c0min;
 500               }
 501         }
 502 have_c0min:
 503   if (c0max > c0min)
 504     for (c0 = c0max; c0 >= c0min; c0--)
 505       for (c1 = c1min; c1 <= c1max; c1++)
 506         {
 507           histp = &histogram[c0][c1][c2min];
 508           for (c2 = c2min; c2 <= c2max; c2++)
 509             if (*histp++ != 0)
 510               {
 511                 boxp->c0max = c0max = c0;
 512                 goto have_c0max;
 513               }
 514         }
 515 have_c0max:
 516   if (c1max > c1min)
 517     for (c1 = c1min; c1 <= c1max; c1++)
 518       for (c0 = c0min; c0 <= c0max; c0++)
 519         {
 520           histp = &histogram[c0][c1][c2min];
 521           for (c2 = c2min; c2 <= c2max; c2++)
 522             if (*histp++ != 0)
 523               {
 524                 boxp->c1min = c1min = c1;
 525                 goto have_c1min;
 526               }
 527         }
 528 have_c1min:
 529   if (c1max > c1min)
 530     for (c1 = c1max; c1 >= c1min; c1--)
 531       for (c0 = c0min; c0 <= c0max; c0++)
 532         {
 533           histp = &histogram[c0][c1][c2min];
 534           for (c2 = c2min; c2 <= c2max; c2++)
 535             if (*histp++ != 0)
 536               {
 537                 boxp->c1max = c1max = c1;
 538                 goto have_c1max;
 539               }
 540         }
 541 have_c1max:
 542   if (c2max > c2min)
 543     for (c2 = c2min; c2 <= c2max; c2++)
 544       for (c0 = c0min; c0 <= c0max; c0++)
 545         {
 546           histp = &histogram[c0][c1min][c2];
 547           for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)
 548             if (*histp != 0)
 549               {
 550                 boxp->c2min = c2min = c2;
 551                 goto have_c2min;
 552               }
 553         }
 554 have_c2min:
 555   if (c2max > c2min)
 556     for (c2 = c2max; c2 >= c2min; c2--)
 557       for (c0 = c0min; c0 <= c0max; c0++)
 558         {
 559           histp = &histogram[c0][c1min][c2];
 560           for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)
 561             if (*histp != 0)
 562               {
 563                 boxp->c2max = c2max = c2;
 564                 goto have_c2max;
 565               }
 566         }
 567 have_c2max:
 568 
 569   /* Update box volume.
 570    * We use 2-norm rather than real volume here; this biases the method
 571    * against making long narrow boxes, and it has the side benefit that
 572    * a box is splittable iff norm > 0.
 573    * Since the differences are expressed in histogram-cell units,
 574    * we have to shift back to JSAMPLE units to get consistent distances;
 575    * after which, we scale according to the selected distance scale factors.
 576    */
 577   dist0 = ((c0max - c0min) << C0_SHIFT) * C0_SCALE;
 578   dist1 = ((c1max - c1min) << C1_SHIFT) * C1_SCALE;
 579   dist2 = ((c2max - c2min) << C2_SHIFT) * C2_SCALE;
 580   boxp->volume = dist0 * dist0 + dist1 * dist1 + dist2 * dist2;
 581 
 582   /* Now scan remaining volume of box and compute population */
 583   ccount = 0;
 584   for (c0 = c0min; c0 <= c0max; c0++)
 585     for (c1 = c1min; c1 <= c1max; c1++)
 586       {
 587         histp = &histogram[c0][c1][c2min];
 588         for (c2 = c2min; c2 <= c2max; c2++, histp++)
 589           if (*histp != 0)
 590             {
 591               ccount++;
 592             }
 593       }
 594   boxp->colorcount = ccount;
 595 }
 596 
 597 
 598 LOCAL (int)
 599 #ifdef ORIGINAL_LIB_JPEG
 600 median_cut (j_decompress_ptr cinfo, boxptr boxlist, int numboxes,
 601             int desired_colors)
 602 #else
 603 median_cut (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize,
 604             boxptr boxlist, int numboxes, int desired_colors)
 605 #endif
 606 /* Repeatedly select and split the largest box until we have enough boxes */
 607 {
 608   int n, lb;
 609   int c0, c1, c2, cmax;
 610   register boxptr b1, b2;
 611 
 612   while (numboxes < desired_colors)
 613     {
 614       /* Select box to split.
 615        * Current algorithm: by population for first half, then by volume.
 616        */
 617       if (numboxes * 2 <= desired_colors)
 618         {
 619           b1 = find_biggest_color_pop (boxlist, numboxes);
 620         }
 621       else
 622         {
 623           b1 = find_biggest_volume (boxlist, numboxes);
 624         }
 625       if (b1 == NULL)           /* no splittable boxes left! */
 626         break;
 627       b2 = &boxlist[numboxes];  /* where new box will go */
 628       /* Copy the color bounds to the new box. */
 629       b2->c0max = b1->c0max;
 630       b2->c1max = b1->c1max;
 631       b2->c2max = b1->c2max;
 632       b2->c0min = b1->c0min;
 633       b2->c1min = b1->c1min;
 634       b2->c2min = b1->c2min;
 635       /* Choose which axis to split the box on.
 636        * Current algorithm: longest scaled axis.
 637        * See notes in update_box about scaling distances.
 638        */
 639       c0 = ((b1->c0max - b1->c0min) << C0_SHIFT) * C0_SCALE;
 640       c1 = ((b1->c1max - b1->c1min) << C1_SHIFT) * C1_SCALE;
 641       c2 = ((b1->c2max - b1->c2min) << C2_SHIFT) * C2_SCALE;
 642       /* We want to break any ties in favor of green, then red, blue last.
 643        * This code does the right thing for R,G,B or B,G,R color orders only.
 644        */
 645 #if RGB_RED == 0
 646       cmax = c1;
 647       n = 1;
 648       if (c0 > cmax)
 649         {
 650           cmax = c0;
 651           n = 0;
 652         }
 653       if (c2 > cmax)
 654         {
 655           n = 2;
 656         }
 657 #else
 658       cmax = c1;
 659       n = 1;
 660       if (c2 > cmax)
 661         {
 662           cmax = c2;
 663           n = 2;
 664         }
 665       if (c0 > cmax)
 666         {
 667           n = 0;
 668         }
 669 #endif
 670       /* Choose split point along selected axis, and update box bounds.
 671        * Current algorithm: split at halfway point.
 672        * (Since the box has been shrunk to minimum volume,
 673        * any split will produce two nonempty subboxes.)
 674        * Note that lb value is max for lower box, so must be < old max.
 675        */
 676       switch (n)
 677         {
 678         case 0:
 679           lb = (b1->c0max + b1->c0min) / 2;
 680           b1->c0max = lb;
 681           b2->c0min = lb + 1;
 682           break;
 683         case 1:
 684           lb = (b1->c1max + b1->c1min) / 2;
 685           b1->c1max = lb;
 686           b2->c1min = lb + 1;
 687           break;
 688         case 2:
 689           lb = (b1->c2max + b1->c2min) / 2;
 690           b1->c2max = lb;
 691           b2->c2min = lb + 1;
 692           break;
 693         }
 694       /* Update stats for boxes */
 695 #ifdef ORIGINAL_LIB_JPEG
 696       update_box (cinfo, b1);
 697       update_box (cinfo, b2);
 698 #else
 699       update_box (oim, nim, cquantize, b1);
 700       update_box (oim, nim, cquantize, b2);
 701 #endif
 702       numboxes++;
 703     }
 704   return numboxes;
 705 }
 706 
 707 
 708 LOCAL (void)
 709 #ifndef ORIGINAL_LIB_JPEG
 710   compute_color (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize,
 711                boxptr boxp, int icolor)
 712 {
 713 #else
 714   compute_color (j_decompress_ptr cinfo, boxptr boxp, int icolor)
 715 /* Compute representative color for a box, put it in colormap[icolor] */
 716 {
 717   /* Current algorithm: mean weighted by pixels (not colors) */
 718   /* Note it is important to get the rounding correct! */
 719   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
 720 #endif
 721   hist3d histogram = cquantize->histogram;
 722   histptr histp;
 723   int c0, c1, c2;
 724   int c0min, c0max, c1min, c1max, c2min, c2max;
 725   long count = 0; /* 2.0.28: = 0 */
 726   long total = 0;
 727   long c0total = 0;
 728   long c1total = 0;
 729   long c2total = 0;
 730 
 731   c0min = boxp->c0min;
 732   c0max = boxp->c0max;
 733   c1min = boxp->c1min;
 734   c1max = boxp->c1max;
 735   c2min = boxp->c2min;
 736   c2max = boxp->c2max;
 737 
 738   for (c0 = c0min; c0 <= c0max; c0++)
 739     for (c1 = c1min; c1 <= c1max; c1++)
 740       {
 741         histp = &histogram[c0][c1][c2min];
 742         for (c2 = c2min; c2 <= c2max; c2++)
 743           {
 744             if ((count = *histp++) != 0)
 745               {
 746                 total += count;
 747                 c0total +=
 748                   ((c0 << C0_SHIFT) + ((1 << C0_SHIFT) >> 1)) * count;
 749                 c1total +=
 750                   ((c1 << C1_SHIFT) + ((1 << C1_SHIFT) >> 1)) * count;
 751                 c2total +=
 752                   ((c2 << C2_SHIFT) + ((1 << C2_SHIFT) >> 1)) * count;
 753               }
 754           }
 755       }
 756 
 757 #ifdef ORIGINAL_LIB_JPEG
 758   cinfo->colormap[0][icolor] = (JSAMPLE) ((c0total + (total >> 1)) / total);
 759   cinfo->colormap[1][icolor] = (JSAMPLE) ((c1total + (total >> 1)) / total);
 760   cinfo->colormap[2][icolor] = (JSAMPLE) ((c2total + (total >> 1)) / total);
 761 #else
 762   /* 2.0.16: Paul den Dulk found an occasion where total can be 0 */
 763   if (count)
 764     {
 765       nim->red[icolor] = (int) ((c0total + (total >> 1)) / total);
 766       nim->green[icolor] = (int) ((c1total + (total >> 1)) / total);
 767       nim->blue[icolor] = (int) ((c2total + (total >> 1)) / total);
 768     }
 769   else
 770     {
 771       nim->red[icolor] = 255;
 772       nim->green[icolor] = 255;
 773       nim->blue[icolor] = 255;
 774     }
 775                 nim->open[icolor] = 0;
 776 #endif
 777 }
 778 
 779 
 780 LOCAL (void)
 781 #ifdef ORIGINAL_LIB_JPEG
 782 select_colors (j_decompress_ptr cinfo, int desired_colors)
 783 #else
 784 select_colors (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize, int desired_colors)
 785 #endif
 786 /* Master routine for color selection */
 787 {
 788   boxptr boxlist;
 789   int numboxes;
 790   int i;
 791 
 792   /* Allocate workspace for box list */
 793 #ifdef ORIGINAL_LIB_JPEG
 794   boxlist = (boxptr) (*cinfo->mem->alloc_small)
 795     ((j_common_ptr) cinfo, JPOOL_IMAGE, desired_colors * SIZEOF (box));
 796 #else
 797   boxlist = (boxptr) safe_emalloc(desired_colors, sizeof (box), 1);
 798 #endif
 799   /* Initialize one box containing whole space */
 800   numboxes = 1;
 801   boxlist[0].c0min = 0;
 802   boxlist[0].c0max = MAXJSAMPLE >> C0_SHIFT;
 803   boxlist[0].c1min = 0;
 804   boxlist[0].c1max = MAXJSAMPLE >> C1_SHIFT;
 805   boxlist[0].c2min = 0;
 806   boxlist[0].c2max = MAXJSAMPLE >> C2_SHIFT;
 807 #ifdef ORIGINAL_LIB_JPEG
 808   /* Shrink it to actually-used volume and set its statistics */
 809   update_box (cinfo, &boxlist[0]);
 810   /* Perform median-cut to produce final box list */
 811   numboxes = median_cut (cinfo, boxlist, numboxes, desired_colors);
 812   /* Compute the representative color for each box, fill colormap */
 813   for (i = 0; i < numboxes; i++)
 814     compute_color (cinfo, &boxlist[i], i);
 815   cinfo->actual_number_of_colors = numboxes;
 816   TRACEMS1 (cinfo, 1, JTRC_QUANT_SELECTED, numboxes);
 817 #else
 818   /* Shrink it to actually-used volume and set its statistics */
 819   update_box (oim, nim, cquantize, &boxlist[0]);
 820   /* Perform median-cut to produce final box list */
 821   numboxes = median_cut (oim, nim, cquantize, boxlist, numboxes, desired_colors);
 822   /* Compute the representative color for each box, fill colormap */
 823   for (i = 0; i < numboxes; i++)
 824     compute_color (oim, nim, cquantize, &boxlist[i], i);
 825   nim->colorsTotal = numboxes;
 826 
 827   /* If we had a pure transparency color, add it as the last palette entry.
 828    * Skip incrementing the color count so that the dither / matching phase
 829    * won't use it on pixels that shouldn't have been transparent.  We'll
 830    * increment it after all that finishes. */
 831   if (oim->transparent >= 0)
 832     {
 833       /* Save the transparent color. */
 834       nim->red[nim->colorsTotal] = gdTrueColorGetRed (oim->transparent);
 835       nim->green[nim->colorsTotal] = gdTrueColorGetGreen (oim->transparent);
 836       nim->blue[nim->colorsTotal] = gdTrueColorGetBlue (oim->transparent);
 837       nim->alpha[nim->colorsTotal] = gdAlphaTransparent;
 838       nim->open[nim->colorsTotal] = 0;
 839     }
 840 
 841   gdFree (boxlist);
 842 #endif
 843 }
 844 
 845 
 846 /*
 847  * These routines are concerned with the time-critical task of mapping input
 848  * colors to the nearest color in the selected colormap.
 849  *
 850  * We re-use the histogram space as an "inverse color map", essentially a
 851  * cache for the results of nearest-color searches.  All colors within a
 852  * histogram cell will be mapped to the same colormap entry, namely the one
 853  * closest to the cell's center.  This may not be quite the closest entry to
 854  * the actual input color, but it's almost as good.  A zero in the cache
 855  * indicates we haven't found the nearest color for that cell yet; the array
 856  * is cleared to zeroes before starting the mapping pass.  When we find the
 857  * nearest color for a cell, its colormap index plus one is recorded in the
 858  * cache for future use.  The pass2 scanning routines call fill_inverse_cmap
 859  * when they need to use an unfilled entry in the cache.
 860  *
 861  * Our method of efficiently finding nearest colors is based on the "locally
 862  * sorted search" idea described by Heckbert and on the incremental distance
 863  * calculation described by Spencer W. Thomas in chapter III.1 of Graphics
 864  * Gems II (James Arvo, ed.  Academic Press, 1991).  Thomas points out that
 865  * the distances from a given colormap entry to each cell of the histogram can
 866  * be computed quickly using an incremental method: the differences between
 867  * distances to adjacent cells themselves differ by a constant.  This allows a
 868  * fairly fast implementation of the "brute force" approach of computing the
 869  * distance from every colormap entry to every histogram cell.  Unfortunately,
 870  * it needs a work array to hold the best-distance-so-far for each histogram
 871  * cell (because the inner loop has to be over cells, not colormap entries).
 872  * The work array elements have to be INT32s, so the work array would need
 873  * 256Kb at our recommended precision.  This is not feasible in DOS machines.
 874  *
 875  * To get around these problems, we apply Thomas' method to compute the
 876  * nearest colors for only the cells within a small subbox of the histogram.
 877  * The work array need be only as big as the subbox, so the memory usage
 878  * problem is solved.  Furthermore, we need not fill subboxes that are never
 879  * referenced in pass2; many images use only part of the color gamut, so a
 880  * fair amount of work is saved.  An additional advantage of this
 881  * approach is that we can apply Heckbert's locality criterion to quickly
 882  * eliminate colormap entries that are far away from the subbox; typically
 883  * three-fourths of the colormap entries are rejected by Heckbert's criterion,
 884  * and we need not compute their distances to individual cells in the subbox.
 885  * The speed of this approach is heavily influenced by the subbox size: too
 886  * small means too much overhead, too big loses because Heckbert's criterion
 887  * can't eliminate as many colormap entries.  Empirically the best subbox
 888  * size seems to be about 1/512th of the histogram (1/8th in each direction).
 889  *
 890  * Thomas' article also describes a refined method which is asymptotically
 891  * faster than the brute-force method, but it is also far more complex and
 892  * cannot efficiently be applied to small subboxes.  It is therefore not
 893  * useful for programs intended to be portable to DOS machines.  On machines
 894  * with plenty of memory, filling the whole histogram in one shot with Thomas'
 895  * refined method might be faster than the present code --- but then again,
 896  * it might not be any faster, and it's certainly more complicated.
 897  */
 898 
 899 
 900 /* log2(histogram cells in update box) for each axis; this can be adjusted */
 901 #define BOX_C0_LOG  (HIST_C0_BITS-3)
 902 #define BOX_C1_LOG  (HIST_C1_BITS-3)
 903 #define BOX_C2_LOG  (HIST_C2_BITS-3)
 904 
 905 #define BOX_C0_ELEMS  (1<<BOX_C0_LOG)   /* # of hist cells in update box */
 906 #define BOX_C1_ELEMS  (1<<BOX_C1_LOG)
 907 #define BOX_C2_ELEMS  (1<<BOX_C2_LOG)
 908 
 909 #define BOX_C0_SHIFT  (C0_SHIFT + BOX_C0_LOG)
 910 #define BOX_C1_SHIFT  (C1_SHIFT + BOX_C1_LOG)
 911 #define BOX_C2_SHIFT  (C2_SHIFT + BOX_C2_LOG)
 912 
 913 
 914 /*
 915  * The next three routines implement inverse colormap filling.  They could
 916  * all be folded into one big routine, but splitting them up this way saves
 917  * some stack space (the mindist[] and bestdist[] arrays need not coexist)
 918  * and may allow some compilers to produce better code by registerizing more
 919  * inner-loop variables.
 920  */
 921 
 922 LOCAL (int)
 923 find_nearby_colors (
 924 #ifdef ORIGINAL_LIB_JPEG
 925                      j_decompress_ptr cinfo,
 926 #else
 927                      gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize,
 928 #endif
 929                      int minc0, int minc1, int minc2, JSAMPLE colorlist[])
 930 /* Locate the colormap entries close enough to an update box to be candidates
 931  * for the nearest entry to some cell(s) in the update box.  The update box
 932  * is specified by the center coordinates of its first cell.  The number of
 933  * candidate colormap entries is returned, and their colormap indexes are
 934  * placed in colorlist[].
 935  * This routine uses Heckbert's "locally sorted search" criterion to select
 936  * the colors that need further consideration.
 937  */
 938 {
 939 #ifdef ORIGINAL_LIB_JPEG
 940   int numcolors = cinfo->actual_number_of_colors;
 941 #else
 942   int numcolors = nim->colorsTotal;
 943 #endif
 944   int maxc0, maxc1, maxc2;
 945   int centerc0, centerc1, centerc2;
 946   int i, x, ncolors;
 947   INT32 minmaxdist, min_dist, max_dist, tdist;
 948   INT32 mindist[MAXNUMCOLORS];  /* min distance to colormap entry i */
 949 
 950   /* Compute true coordinates of update box's upper corner and center.
 951    * Actually we compute the coordinates of the center of the upper-corner
 952    * histogram cell, which are the upper bounds of the volume we care about.
 953    * Note that since ">>" rounds down, the "center" values may be closer to
 954    * min than to max; hence comparisons to them must be "<=", not "<".
 955    */
 956   maxc0 = minc0 + ((1 << BOX_C0_SHIFT) - (1 << C0_SHIFT));
 957   centerc0 = (minc0 + maxc0) >> 1;
 958   maxc1 = minc1 + ((1 << BOX_C1_SHIFT) - (1 << C1_SHIFT));
 959   centerc1 = (minc1 + maxc1) >> 1;
 960   maxc2 = minc2 + ((1 << BOX_C2_SHIFT) - (1 << C2_SHIFT));
 961   centerc2 = (minc2 + maxc2) >> 1;
 962 
 963   /* For each color in colormap, find:
 964    *  1. its minimum squared-distance to any point in the update box
 965    *     (zero if color is within update box);
 966    *  2. its maximum squared-distance to any point in the update box.
 967    * Both of these can be found by considering only the corners of the box.
 968    * We save the minimum distance for each color in mindist[];
 969    * only the smallest maximum distance is of interest.
 970    */
 971   minmaxdist = 0x7FFFFFFFL;
 972 
 973   for (i = 0; i < numcolors; i++)
 974     {
 975       /* We compute the squared-c0-distance term, then add in the other two. */
 976 #ifdef ORIGINAL_LIB_JPEG
 977       x = GETJSAMPLE (cinfo->colormap[0][i]);
 978 #else
 979       x = nim->red[i];
 980 #endif
 981       if (x < minc0)
 982         {
 983           tdist = (x - minc0) * C0_SCALE;
 984           min_dist = tdist * tdist;
 985           tdist = (x - maxc0) * C0_SCALE;
 986           max_dist = tdist * tdist;
 987         }
 988       else if (x > maxc0)
 989         {
 990           tdist = (x - maxc0) * C0_SCALE;
 991           min_dist = tdist * tdist;
 992           tdist = (x - minc0) * C0_SCALE;
 993           max_dist = tdist * tdist;
 994         }
 995       else
 996         {
 997           /* within cell range so no contribution to min_dist */
 998           min_dist = 0;
 999           if (x <= centerc0)
1000             {
1001               tdist = (x - maxc0) * C0_SCALE;
1002               max_dist = tdist * tdist;
1003             }
1004           else
1005             {
1006               tdist = (x - minc0) * C0_SCALE;
1007               max_dist = tdist * tdist;
1008             }
1009         }
1010 
1011 #ifdef ORIGINAL_LIB_JPEG
1012       x = GETJSAMPLE (cinfo->colormap[1][i]);
1013 #else
1014       x = nim->green[i];
1015 #endif
1016       if (x < minc1)
1017         {
1018           tdist = (x - minc1) * C1_SCALE;
1019           min_dist += tdist * tdist;
1020           tdist = (x - maxc1) * C1_SCALE;
1021           max_dist += tdist * tdist;
1022         }
1023       else if (x > maxc1)
1024         {
1025           tdist = (x - maxc1) * C1_SCALE;
1026           min_dist += tdist * tdist;
1027           tdist = (x - minc1) * C1_SCALE;
1028           max_dist += tdist * tdist;
1029         }
1030       else
1031         {
1032           /* within cell range so no contribution to min_dist */
1033           if (x <= centerc1)
1034             {
1035               tdist = (x - maxc1) * C1_SCALE;
1036               max_dist += tdist * tdist;
1037             }
1038           else
1039             {
1040               tdist = (x - minc1) * C1_SCALE;
1041               max_dist += tdist * tdist;
1042             }
1043         }
1044 
1045 #ifdef ORIGINAL_LIB_JPEG
1046       x = GETJSAMPLE (cinfo->colormap[2][i]);
1047 #else
1048       x = nim->blue[i];
1049 #endif
1050       if (x < minc2)
1051         {
1052           tdist = (x - minc2) * C2_SCALE;
1053           min_dist += tdist * tdist;
1054           tdist = (x - maxc2) * C2_SCALE;
1055           max_dist += tdist * tdist;
1056         }
1057       else if (x > maxc2)
1058         {
1059           tdist = (x - maxc2) * C2_SCALE;
1060           min_dist += tdist * tdist;
1061           tdist = (x - minc2) * C2_SCALE;
1062           max_dist += tdist * tdist;
1063         }
1064       else
1065         {
1066           /* within cell range so no contribution to min_dist */
1067           if (x <= centerc2)
1068             {
1069               tdist = (x - maxc2) * C2_SCALE;
1070               max_dist += tdist * tdist;
1071             }
1072           else
1073             {
1074               tdist = (x - minc2) * C2_SCALE;
1075               max_dist += tdist * tdist;
1076             }
1077         }
1078 
1079       mindist[i] = min_dist;    /* save away the results */
1080       if (max_dist < minmaxdist)
1081         minmaxdist = max_dist;
1082     }
1083 
1084   /* Now we know that no cell in the update box is more than minmaxdist
1085    * away from some colormap entry.  Therefore, only colors that are
1086    * within minmaxdist of some part of the box need be considered.
1087    */
1088   ncolors = 0;
1089   for (i = 0; i < numcolors; i++)
1090     {
1091       if (mindist[i] <= minmaxdist)
1092         colorlist[ncolors++] = (JSAMPLE) i;
1093     }
1094   return ncolors;
1095 }
1096 
1097 
1098 LOCAL (void) find_best_colors (
1099 #ifdef ORIGINAL_LIB_JPEG
1100                                 j_decompress_ptr cinfo,
1101 #else
1102                                 gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize,
1103 #endif
1104                                 int minc0, int minc1, int minc2,
1105                                 int numcolors, JSAMPLE colorlist[],
1106                                 JSAMPLE bestcolor[])
1107 /* Find the closest colormap entry for each cell in the update box,
1108  * given the list of candidate colors prepared by find_nearby_colors.
1109  * Return the indexes of the closest entries in the bestcolor[] array.
1110  * This routine uses Thomas' incremental distance calculation method to
1111  * find the distance from a colormap entry to successive cells in the box.
1112  */
1113 {
1114   int ic0, ic1, ic2;
1115   int i, icolor;
1116   register INT32 *bptr;         /* pointer into bestdist[] array */
1117   JSAMPLE *cptr;                /* pointer into bestcolor[] array */
1118   INT32 dist0, dist1;           /* initial distance values */
1119   register INT32 dist2;         /* current distance in inner loop */
1120   INT32 xx0, xx1;               /* distance increments */
1121   register INT32 xx2;
1122   INT32 inc0, inc1, inc2;       /* initial values for increments */
1123   /* This array holds the distance to the nearest-so-far color for each cell */
1124   INT32 bestdist[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS];
1125 
1126   /* Initialize best-distance for each cell of the update box */
1127   bptr = bestdist;
1128   for (i = BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS - 1; i >= 0; i--)
1129     *bptr++ = 0x7FFFFFFFL;
1130 
1131   /* For each color selected by find_nearby_colors,
1132    * compute its distance to the center of each cell in the box.
1133    * If that's less than best-so-far, update best distance and color number.
1134    */
1135 
1136   /* Nominal steps between cell centers ("x" in Thomas article) */
1137 #define STEP_C0  ((1 << C0_SHIFT) * C0_SCALE)
1138 #define STEP_C1  ((1 << C1_SHIFT) * C1_SCALE)
1139 #define STEP_C2  ((1 << C2_SHIFT) * C2_SCALE)
1140 
1141   for (i = 0; i < numcolors; i++)
1142     {
1143       int r, g, b;
1144 #ifdef ORIGINAL_LIB_JPEG
1145 
1146       icolor = GETJSAMPLE (colorlist[i]);
1147       r = GETJSAMPLE (cinfo->colormap[0][icolor]);
1148       g = GETJSAMPLE (cinfo->colormap[1][icolor]);
1149       b = GETJSAMPLE (cinfo->colormap[2][icolor]);
1150 #else
1151       icolor = colorlist[i];
1152       r = nim->red[icolor];
1153       g = nim->green[icolor];
1154       b = nim->blue[icolor];
1155 #endif
1156 
1157       /* Compute (square of) distance from minc0/c1/c2 to this color */
1158       inc0 = (minc0 - r) * C0_SCALE;
1159       dist0 = inc0 * inc0;
1160       inc1 = (minc1 - g) * C1_SCALE;
1161       dist0 += inc1 * inc1;
1162       inc2 = (minc2 - b) * C2_SCALE;
1163       dist0 += inc2 * inc2;
1164       /* Form the initial difference increments */
1165       inc0 = inc0 * (2 * STEP_C0) + STEP_C0 * STEP_C0;
1166       inc1 = inc1 * (2 * STEP_C1) + STEP_C1 * STEP_C1;
1167       inc2 = inc2 * (2 * STEP_C2) + STEP_C2 * STEP_C2;
1168       /* Now loop over all cells in box, updating distance per Thomas method */
1169       bptr = bestdist;
1170       cptr = bestcolor;
1171       xx0 = inc0;
1172       for (ic0 = BOX_C0_ELEMS - 1; ic0 >= 0; ic0--)
1173         {
1174           dist1 = dist0;
1175           xx1 = inc1;
1176           for (ic1 = BOX_C1_ELEMS - 1; ic1 >= 0; ic1--)
1177             {
1178               dist2 = dist1;
1179               xx2 = inc2;
1180               for (ic2 = BOX_C2_ELEMS - 1; ic2 >= 0; ic2--)
1181                 {
1182                   if (dist2 < *bptr)
1183                     {
1184                       *bptr = dist2;
1185                       *cptr = (JSAMPLE) icolor;
1186                     }
1187                   dist2 += xx2;
1188                   xx2 += 2 * STEP_C2 * STEP_C2;
1189                   bptr++;
1190                   cptr++;
1191                 }
1192               dist1 += xx1;
1193               xx1 += 2 * STEP_C1 * STEP_C1;
1194             }
1195           dist0 += xx0;
1196           xx0 += 2 * STEP_C0 * STEP_C0;
1197         }
1198     }
1199 }
1200 
1201 
1202 LOCAL (void)
1203 fill_inverse_cmap (
1204 #ifdef ORIGINAL_LIB_JPEG
1205                     j_decompress_ptr cinfo,
1206 #else
1207                     gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize,
1208 #endif
1209                     int c0, int c1, int c2)
1210 /* Fill the inverse-colormap entries in the update box that contains */
1211 /* histogram cell c0/c1/c2.  (Only that one cell MUST be filled, but */
1212 /* we can fill as many others as we wish.) */
1213 {
1214 #ifdef ORIGINAL_LIB_JPEG
1215   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1216 #endif
1217   hist3d histogram = cquantize->histogram;
1218   int minc0, minc1, minc2;      /* lower left corner of update box */
1219   int ic0, ic1, ic2;
1220   register JSAMPLE *cptr;       /* pointer into bestcolor[] array */
1221   register histptr cachep;      /* pointer into main cache array */
1222   /* This array lists the candidate colormap indexes. */
1223   JSAMPLE colorlist[MAXNUMCOLORS];
1224   int numcolors;                /* number of candidate colors */
1225   /* This array holds the actually closest colormap index for each cell. */
1226   JSAMPLE bestcolor[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS];
1227 
1228   /* Convert cell coordinates to update box ID */
1229   c0 >>= BOX_C0_LOG;
1230   c1 >>= BOX_C1_LOG;
1231   c2 >>= BOX_C2_LOG;
1232 
1233   /* Compute true coordinates of update box's origin corner.
1234    * Actually we compute the coordinates of the center of the corner
1235    * histogram cell, which are the lower bounds of the volume we care about.
1236    */
1237   minc0 = (c0 << BOX_C0_SHIFT) + ((1 << C0_SHIFT) >> 1);
1238   minc1 = (c1 << BOX_C1_SHIFT) + ((1 << C1_SHIFT) >> 1);
1239   minc2 = (c2 << BOX_C2_SHIFT) + ((1 << C2_SHIFT) >> 1);
1240 
1241   /* Determine which colormap entries are close enough to be candidates
1242    * for the nearest entry to some cell in the update box.
1243    */
1244 #ifdef ORIGINAL_LIB_JPEG
1245   numcolors = find_nearby_colors (cinfo, minc0, minc1, minc2, colorlist);
1246 
1247   /* Determine the actually nearest colors. */
1248   find_best_colors (cinfo, minc0, minc1, minc2, numcolors, colorlist,
1249                     bestcolor);
1250 #else
1251   numcolors =
1252     find_nearby_colors (oim, nim, cquantize, minc0, minc1, minc2, colorlist);
1253   find_best_colors (oim, nim, cquantize, minc0, minc1, minc2, numcolors,
1254                     colorlist, bestcolor);
1255 #endif
1256 
1257   /* Save the best color numbers (plus 1) in the main cache array */
1258   c0 <<= BOX_C0_LOG;            /* convert ID back to base cell indexes */
1259   c1 <<= BOX_C1_LOG;
1260   c2 <<= BOX_C2_LOG;
1261   cptr = bestcolor;
1262   for (ic0 = 0; ic0 < BOX_C0_ELEMS; ic0++)
1263     {
1264       for (ic1 = 0; ic1 < BOX_C1_ELEMS; ic1++)
1265         {
1266           cachep = &histogram[c0 + ic0][c1 + ic1][c2];
1267           for (ic2 = 0; ic2 < BOX_C2_ELEMS; ic2++)
1268             {
1269 #ifdef ORIGINAL_LIB_JPEG
1270               *cachep++ = (histcell) (GETJSAMPLE (*cptr++) + 1);
1271 #else
1272               *cachep++ = (histcell) ((*cptr++) + 1);
1273 #endif
1274             }
1275         }
1276     }
1277 }
1278 
1279 
1280 /*
1281  * Map some rows of pixels to the output colormapped representation.
1282  */
1283 
1284 METHODDEF (void)
1285 #ifndef ORIGINAL_LIB_JPEG
1286 pass2_no_dither (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
1287 {
1288   register int *inptr;
1289   register unsigned char *outptr;
1290   int width = oim->sx;
1291   int num_rows = oim->sy;
1292 #else
1293 pass2_no_dither (j_decompress_ptr cinfo,
1294                  JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows)
1295 /* This version performs no dithering */
1296 {
1297   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1298   register JSAMPROW inptr, outptr;
1299   JDIMENSION width = cinfo->output_width;
1300 #endif
1301   hist3d histogram = cquantize->histogram;
1302   register int c0, c1, c2;
1303   int row;
1304   JDIMENSION col;
1305   register histptr cachep;
1306 
1307 
1308   for (row = 0; row < num_rows; row++)
1309     {
1310       inptr = input_buf[row];
1311       outptr = output_buf[row];
1312       for (col = width; col > 0; col--)
1313         {
1314           /* get pixel value and index into the cache */
1315           int r, g, b;
1316 #ifdef ORIGINAL_LIB_JPEG
1317           r = GETJSAMPLE (*inptr++);
1318           g = GETJSAMPLE (*inptr++);
1319           b = GETJSAMPLE (*inptr++);
1320 #else
1321           r = gdTrueColorGetRed (*inptr);
1322           g = gdTrueColorGetGreen (*inptr);
1323           /*
1324              2.0.24: inptr must not be incremented until after
1325              transparency check, if any. Thanks to "Super Pikeman."
1326            */
1327           b = gdTrueColorGetBlue (*inptr);
1328 
1329           /* If the pixel is transparent, we assign it the palette index that
1330            * will later be added at the end of the palette as the transparent
1331            * index. */
1332           if ((oim->transparent >= 0) && (oim->transparent == *(inptr - 1)))
1333             {
1334               *outptr++ = nim->colorsTotal;
1335               inptr++;
1336               continue;
1337             }
1338           inptr++;
1339 #endif
1340           c0 = r >> C0_SHIFT;
1341           c1 = g >> C1_SHIFT;
1342           c2 = b >> C2_SHIFT;
1343           cachep = &histogram[c0][c1][c2];
1344           /* If we have not seen this color before, find nearest colormap entry */
1345           /* and update the cache */
1346           if (*cachep == 0)
1347 #ifdef ORIGINAL_LIB_JPEG
1348             fill_inverse_cmap (cinfo, c0, c1, c2);
1349 #else
1350             fill_inverse_cmap (oim, nim, cquantize, c0, c1, c2);
1351 #endif
1352           /* Now emit the colormap index for this cell */
1353 #ifdef ORIGINAL_LIB_JPEG
1354           *outptr++ = (JSAMPLE) (*cachep - 1);
1355 #else
1356           *outptr++ = (*cachep - 1);
1357 #endif
1358         }
1359     }
1360 }
1361 
1362 
1363 METHODDEF (void)
1364 #ifndef ORIGINAL_LIB_JPEG
1365 pass2_fs_dither (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
1366 {
1367 #else
1368 pass2_fs_dither (j_decompress_ptr cinfo,
1369                  JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows)
1370 /* This version performs Floyd-Steinberg dithering */
1371 {
1372   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1373   JSAMPROW inptr;               /* => current input pixel */
1374 #endif
1375   hist3d histogram = cquantize->histogram;
1376   register LOCFSERROR cur0, cur1, cur2; /* current error or pixel value */
1377   LOCFSERROR belowerr0, belowerr1, belowerr2;   /* error for pixel below cur */
1378   LOCFSERROR bpreverr0, bpreverr1, bpreverr2;   /* error for below/prev col */
1379   register FSERRPTR errorptr;   /* => fserrors[] at column before current */
1380   histptr cachep;
1381   int dir;                      /* +1 or -1 depending on direction */
1382   int dir3;                     /* 3*dir, for advancing inptr & errorptr */
1383   int row;
1384   JDIMENSION col;
1385 #ifdef ORIGINAL_LIB_JPEG
1386   JSAMPROW outptr;              /* => current output pixel */
1387   JDIMENSION width = cinfo->output_width;
1388   JSAMPLE *range_limit = cinfo->sample_range_limit;
1389   JSAMPROW colormap0 = cinfo->colormap[0];
1390   JSAMPROW colormap1 = cinfo->colormap[1];
1391   JSAMPROW colormap2 = cinfo->colormap[2];
1392 #else
1393   int *inptr;                   /* => current input pixel */
1394   unsigned char *outptr;        /* => current output pixel */
1395   int width = oim->sx;
1396   int num_rows = oim->sy;
1397   int *colormap0 = nim->red;
1398   int *colormap1 = nim->green;
1399   int *colormap2 = nim->blue;
1400 #endif
1401   int *error_limit = cquantize->error_limiter;
1402 
1403 
1404   SHIFT_TEMPS for (row = 0; row < num_rows; row++)
1405     {
1406       inptr = input_buf[row];
1407       outptr = output_buf[row];
1408       if (cquantize->on_odd_row)
1409         {
1410           /* work right to left in this row */
1411           inptr += (width - 1) * 3;     /* so point to rightmost pixel */
1412           outptr += width - 1;
1413           dir = -1;
1414           dir3 = -3;
1415           errorptr = cquantize->fserrors + (width + 1) * 3;     /* => entry after last column */
1416 #ifdef ORIGINAL_LIB_JPEG_REVERSE_ODD_ROWS
1417           cquantize->on_odd_row = FALSE;        /* flip for next time */
1418 #endif
1419         }
1420       else
1421         {
1422           /* work left to right in this row */
1423           dir = 1;
1424           dir3 = 3;
1425           errorptr = cquantize->fserrors;       /* => entry before first real column */
1426 #ifdef ORIGINAL_LIB_JPEG_REVERSE_ODD_ROWS
1427           cquantize->on_odd_row = TRUE; /* flip for next time */
1428 #endif
1429         }
1430       /* Preset error values: no error propagated to first pixel from left */
1431       cur0 = cur1 = cur2 = 0;
1432       /* and no error propagated to row below yet */
1433       belowerr0 = belowerr1 = belowerr2 = 0;
1434       bpreverr0 = bpreverr1 = bpreverr2 = 0;
1435 
1436       for (col = width; col > 0; col--)
1437         {
1438 
1439           /* If this pixel is transparent, we want to assign it to the special
1440            * transparency color index past the end of the palette rather than
1441            * go through matching / dithering. */
1442           if ((oim->transparent >= 0) && (*inptr == oim->transparent))
1443             {
1444               *outptr = nim->colorsTotal;
1445               errorptr[0] = 0;
1446               errorptr[1] = 0;
1447               errorptr[2] = 0;
1448               errorptr[3] = 0;
1449               inptr += dir;
1450               outptr += dir;
1451               errorptr += dir3;
1452               continue;
1453             }
1454           /* curN holds the error propagated from the previous pixel on the
1455            * current line.  Add the error propagated from the previous line
1456            * to form the complete error correction term for this pixel, and
1457            * round the error term (which is expressed * 16) to an integer.
1458            * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct
1459            * for either sign of the error value.
1460            * Note: errorptr points to *previous* column's array entry.
1461            */
1462           cur0 = RIGHT_SHIFT (cur0 + errorptr[dir3 + 0] + 8, 4);
1463           cur1 = RIGHT_SHIFT (cur1 + errorptr[dir3 + 1] + 8, 4);
1464           cur2 = RIGHT_SHIFT (cur2 + errorptr[dir3 + 2] + 8, 4);
1465           /* Limit the error using transfer function set by init_error_limit.
1466            * See comments with init_error_limit for rationale.
1467            */
1468           cur0 = error_limit[cur0];
1469           cur1 = error_limit[cur1];
1470           cur2 = error_limit[cur2];
1471           /* Form pixel value + error, and range-limit to 0..MAXJSAMPLE.
1472            * The maximum error is +- MAXJSAMPLE (or less with error limiting);
1473            * this sets the required size of the range_limit array.
1474            */
1475 #ifdef ORIGINAL_LIB_JPEG
1476           cur0 += GETJSAMPLE (inptr[0]);
1477           cur1 += GETJSAMPLE (inptr[1]);
1478           cur2 += GETJSAMPLE (inptr[2]);
1479           cur0 = GETJSAMPLE (range_limit[cur0]);
1480           cur1 = GETJSAMPLE (range_limit[cur1]);
1481           cur2 = GETJSAMPLE (range_limit[cur2]);
1482 #else
1483           cur0 += gdTrueColorGetRed (*inptr);
1484           cur1 += gdTrueColorGetGreen (*inptr);
1485           cur2 += gdTrueColorGetBlue (*inptr);
1486           range_limit (cur0);
1487           range_limit (cur1);
1488           range_limit (cur2);
1489 #endif
1490 
1491           /* Index into the cache with adjusted pixel value */
1492           cachep =
1493             &histogram[cur0 >> C0_SHIFT][cur1 >> C1_SHIFT][cur2 >> C2_SHIFT];
1494           /* If we have not seen this color before, find nearest colormap */
1495           /* entry and update the cache */
1496           if (*cachep == 0)
1497 #ifdef ORIGINAL_LIB_JPEG
1498             fill_inverse_cmap (cinfo, cur0 >> C0_SHIFT, cur1 >> C1_SHIFT,
1499                                cur2 >> C2_SHIFT);
1500 #else
1501             fill_inverse_cmap (oim, nim, cquantize, cur0 >> C0_SHIFT,
1502                                cur1 >> C1_SHIFT, cur2 >> C2_SHIFT);
1503 #endif
1504           /* Now emit the colormap index for this cell */
1505           {
1506             register int pixcode = *cachep - 1;
1507             *outptr = (JSAMPLE) pixcode;
1508             /* Compute representation error for this pixel */
1509 #define GETJSAMPLE
1510             cur0 -= GETJSAMPLE (colormap0[pixcode]);
1511             cur1 -= GETJSAMPLE (colormap1[pixcode]);
1512             cur2 -= GETJSAMPLE (colormap2[pixcode]);
1513 #undef GETJSAMPLE
1514           }
1515           /* Compute error fractions to be propagated to adjacent pixels.
1516            * Add these into the running sums, and simultaneously shift the
1517            * next-line error sums left by 1 column.
1518            */
1519           {
1520             register LOCFSERROR bnexterr, delta;
1521 
1522             bnexterr = cur0;    /* Process component 0 */
1523             delta = cur0 * 2;
1524             cur0 += delta;      /* form error * 3 */
1525             errorptr[0] = (FSERROR) (bpreverr0 + cur0);
1526             cur0 += delta;      /* form error * 5 */
1527             bpreverr0 = belowerr0 + cur0;
1528             belowerr0 = bnexterr;
1529             cur0 += delta;      /* form error * 7 */
1530             bnexterr = cur1;    /* Process component 1 */
1531             delta = cur1 * 2;
1532             cur1 += delta;      /* form error * 3 */
1533             errorptr[1] = (FSERROR) (bpreverr1 + cur1);
1534             cur1 += delta;      /* form error * 5 */
1535             bpreverr1 = belowerr1 + cur1;
1536             belowerr1 = bnexterr;
1537             cur1 += delta;      /* form error * 7 */
1538             bnexterr = cur2;    /* Process component 2 */
1539             delta = cur2 * 2;
1540             cur2 += delta;      /* form error * 3 */
1541             errorptr[2] = (FSERROR) (bpreverr2 + cur2);
1542             cur2 += delta;      /* form error * 5 */
1543             bpreverr2 = belowerr2 + cur2;
1544             belowerr2 = bnexterr;
1545             cur2 += delta;      /* form error * 7 */
1546           }
1547           /* At this point curN contains the 7/16 error value to be propagated
1548            * to the next pixel on the current line, and all the errors for the
1549            * next line have been shifted over.  We are therefore ready to move on.
1550            */
1551 #ifdef ORIGINAL_LIB_JPEG
1552           inptr += dir3;        /* Advance pixel pointers to next column */
1553 #else
1554           inptr += dir;         /* Advance pixel pointers to next column */
1555 #endif
1556           outptr += dir;
1557           errorptr += dir3;     /* advance errorptr to current column */
1558         }
1559       /* Post-loop cleanup: we must unload the final error values into the
1560        * final fserrors[] entry.  Note we need not unload belowerrN because
1561        * it is for the dummy column before or after the actual array.
1562        */
1563       errorptr[0] = (FSERROR) bpreverr0;        /* unload prev errs into array */
1564       errorptr[1] = (FSERROR) bpreverr1;
1565       errorptr[2] = (FSERROR) bpreverr2;
1566     }
1567 }
1568 
1569 
1570 /*
1571  * Initialize the error-limiting transfer function (lookup table).
1572  * The raw F-S error computation can potentially compute error values of up to
1573  * +- MAXJSAMPLE.  But we want the maximum correction applied to a pixel to be
1574  * much less, otherwise obviously wrong pixels will be created.  (Typical
1575  * effects include weird fringes at color-area boundaries, isolated bright
1576  * pixels in a dark area, etc.)  The standard advice for avoiding this problem
1577  * is to ensure that the "corners" of the color cube are allocated as output
1578  * colors; then repeated errors in the same direction cannot cause cascading
1579  * error buildup.  However, that only prevents the error from getting
1580  * completely out of hand; Aaron Giles reports that error limiting improves
1581  * the results even with corner colors allocated.
1582  * A simple clamping of the error values to about +- MAXJSAMPLE/8 works pretty
1583  * well, but the smoother transfer function used below is even better.  Thanks
1584  * to Aaron Giles for this idea.
1585  */
1586 
1587 LOCAL (void)
1588 #ifdef ORIGINAL_LIB_JPEG
1589 init_error_limit (j_decompress_ptr cinfo)
1590 #else
1591 init_error_limit (gdImagePtr oim, gdImagePtr nim, my_cquantize_ptr cquantize)
1592 #endif
1593 /* Allocate and fill in the error_limiter table */
1594 {
1595   int *table;
1596   int in, out;
1597 #ifdef ORIGINAL_LIB_JPEG
1598   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1599   table = (int *) (*cinfo->mem->alloc_small)
1600     ((j_common_ptr) cinfo, JPOOL_IMAGE, (MAXJSAMPLE * 2 + 1) * SIZEOF (int));
1601 #else
1602   cquantize->error_limiter_storage =
1603     (int *) safe_emalloc ((MAXJSAMPLE * 2 + 1), sizeof (int), 0);
1604   if (!cquantize->error_limiter_storage)
1605     {
1606       return;
1607     }
1608   table = cquantize->error_limiter_storage;
1609 #endif
1610 
1611   table += MAXJSAMPLE;          /* so can index -MAXJSAMPLE .. +MAXJSAMPLE */
1612   cquantize->error_limiter = table;
1613 
1614 #define STEPSIZE ((MAXJSAMPLE+1)/16)
1615   /* Map errors 1:1 up to +- MAXJSAMPLE/16 */
1616   out = 0;
1617   for (in = 0; in < STEPSIZE; in++, out++)
1618     {
1619       table[in] = out;
1620       table[-in] = -out;
1621     }
1622   /* Map errors 1:2 up to +- 3*MAXJSAMPLE/16 */
1623   for (; in < STEPSIZE * 3; in++, out += (in & 1) ? 0 : 1)
1624     {
1625       table[in] = out;
1626       table[-in] = -out;
1627     }
1628   /* Clamp the rest to final out value (which is (MAXJSAMPLE+1)/8) */
1629   for (; in <= MAXJSAMPLE; in++)
1630     {
1631       table[in] = out;
1632       table[-in] = -out;
1633     }
1634 #undef STEPSIZE
1635 }
1636 
1637 
1638 /*
1639  * Finish up at the end of each pass.
1640  */
1641 
1642 #ifdef ORIGINAL_LIB_JPEG
1643 METHODDEF (void)
1644 finish_pass1 (j_decompress_ptr cinfo)
1645 {
1646   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1647 
1648   /* Select the representative colors and fill in cinfo->colormap */
1649   cinfo->colormap = cquantize->sv_colormap;
1650   select_colors (cinfo, cquantize->desired);
1651   /* Force next pass to zero the color index table */
1652   cquantize->needs_zeroed = TRUE;
1653 }
1654 
1655 
1656 METHODDEF (void)
1657 finish_pass2 (j_decompress_ptr cinfo)
1658 {
1659   /* no work */
1660 }
1661 
1662 /*
1663  * Initialize for each processing pass.
1664  */
1665 
1666 METHODDEF (void)
1667 start_pass_2_quant (j_decompress_ptr cinfo, boolean is_pre_scan)
1668 {
1669   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1670   hist3d histogram = cquantize->histogram;
1671   int i;
1672 
1673   /* Only F-S dithering or no dithering is supported. */
1674   /* If user asks for ordered dither, give him F-S. */
1675   if (cinfo->dither_mode != JDITHER_NONE)
1676     cinfo->dither_mode = JDITHER_FS;
1677 
1678   if (is_pre_scan)
1679     {
1680       /* Set up method pointers */
1681       cquantize->pub.color_quantize = prescan_quantize;
1682       cquantize->pub.finish_pass = finish_pass1;
1683       cquantize->needs_zeroed = TRUE;   /* Always zero histogram */
1684     }
1685   else
1686     {
1687       /* Set up method pointers */
1688       if (cinfo->dither_mode == JDITHER_FS)
1689         cquantize->pub.color_quantize = pass2_fs_dither;
1690       else
1691         cquantize->pub.color_quantize = pass2_no_dither;
1692       cquantize->pub.finish_pass = finish_pass2;
1693 
1694       /* Make sure color count is acceptable */
1695       i = cinfo->actual_number_of_colors;
1696       if (i < 1)
1697         ERREXIT1 (cinfo, JERR_QUANT_FEW_COLORS, 1);
1698       if (i > MAXNUMCOLORS)
1699         ERREXIT1 (cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS);
1700 
1701       if (cinfo->dither_mode == JDITHER_FS)
1702         {
1703           size_t arraysize = (size_t) ((cinfo->output_width + 2) *
1704                                        (3 * SIZEOF (FSERROR)));
1705           /* Allocate Floyd-Steinberg workspace if we didn't already. */
1706           if (cquantize->fserrors == NULL)
1707             cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large)
1708               ((j_common_ptr) cinfo, JPOOL_IMAGE, arraysize);
1709           /* Initialize the propagated errors to zero. */
1710           jzero_far ((void FAR *) cquantize->fserrors, arraysize);
1711           /* Make the error-limit table if we didn't already. */
1712           if (cquantize->error_limiter == NULL)
1713             init_error_limit (cinfo);
1714           cquantize->on_odd_row = FALSE;
1715         }
1716 
1717     }
1718   /* Zero the histogram or inverse color map, if necessary */
1719   if (cquantize->needs_zeroed)
1720     {
1721       for (i = 0; i < HIST_C0_ELEMS; i++)
1722         {
1723           jzero_far ((void FAR *) histogram[i],
1724                      HIST_C1_ELEMS * HIST_C2_ELEMS * SIZEOF (histcell));
1725         }
1726       cquantize->needs_zeroed = FALSE;
1727     }
1728 }
1729 
1730 
1731 /*
1732  * Switch to a new external colormap between output passes.
1733  */
1734 
1735 METHODDEF (void)
1736 new_color_map_2_quant (j_decompress_ptr cinfo)
1737 {
1738   my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;
1739 
1740   /* Reset the inverse color map */
1741   cquantize->needs_zeroed = TRUE;
1742 }
1743 #else
1744 static void
1745 zeroHistogram (hist3d histogram)
1746 {
1747   int i;
1748   /* Zero the histogram or inverse color map */
1749   for (i = 0; i < HIST_C0_ELEMS; i++)
1750     {
1751       memset (histogram[i],
1752               0, HIST_C1_ELEMS * HIST_C2_ELEMS * sizeof (histcell));
1753     }
1754 }
1755 #endif
1756 
1757 static void gdImageTrueColorToPaletteBody (gdImagePtr oim, int dither, int colorsWanted, gdImagePtr *cimP);
1758 
1759 gdImagePtr gdImageCreatePaletteFromTrueColor (gdImagePtr im, int dither, int colorsWanted)
1760 {
1761         gdImagePtr nim;
1762         gdImageTrueColorToPaletteBody(im, dither, colorsWanted, &nim);
1763         return nim;
1764 }
1765 
1766 void gdImageTrueColorToPalette (gdImagePtr im, int dither, int colorsWanted)
1767 {
1768         gdImageTrueColorToPaletteBody(im, dither, colorsWanted, 0);
1769 }
1770 
1771 /*
1772  * Module initialization routine for 2-pass color quantization.
1773  */
1774 
1775 #ifdef ORIGINAL_LIB_JPEG
1776 GLOBAL (void)
1777 jinit_2pass_quantizer (j_decompress_ptr cinfo)
1778 #else
1779 static void gdImageTrueColorToPaletteBody (gdImagePtr oim, int dither, int colorsWanted, gdImagePtr *cimP)
1780 #endif
1781 {
1782   my_cquantize_ptr cquantize = NULL;
1783   int i;
1784 
1785 #ifndef ORIGINAL_LIB_JPEG
1786   /* Allocate the JPEG palette-storage */
1787   size_t arraysize;
1788   int maxColors = gdMaxColors;
1789   gdImagePtr nim;
1790   if (cimP) {
1791     nim = gdImageCreate(oim->sx, oim->sy);
1792     *cimP = nim;
1793     if (!nim) {
1794       return;
1795     }
1796   } else {
1797     nim = oim;
1798   }
1799   if (!oim->trueColor)
1800     {
1801       /* (Almost) nothing to do! */
1802       if (cimP) {
1803         gdImageCopy(nim, oim, 0, 0, 0, 0, oim->sx, oim->sy);
1804         *cimP = nim;
1805       }
1806       return;
1807     }
1808 
1809   /* If we have a transparent color (the alphaless mode of transparency), we
1810    * must reserve a palette entry for it at the end of the palette. */
1811   if (oim->transparent >= 0)
1812     {
1813       maxColors--;
1814     }
1815   if (colorsWanted > maxColors)
1816     {
1817       colorsWanted = maxColors;
1818     }
1819   if (!cimP) {
1820     nim->pixels = gdCalloc (sizeof (unsigned char *), oim->sy);
1821     if (!nim->pixels)
1822       {
1823         /* No can do */
1824         goto outOfMemory;
1825       }
1826     for (i = 0; (i < nim->sy); i++)
1827       {
1828         nim->pixels[i] = gdCalloc (sizeof (unsigned char *), oim->sx);
1829         if (!nim->pixels[i])
1830         {
1831           goto outOfMemory;
1832         }
1833       }
1834   }
1835 #endif
1836 
1837 #ifdef ORIGINAL_LIB_JPEG
1838   cquantize = (my_cquantize_ptr)
1839     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
1840                                 SIZEOF (my_cquantizer));
1841   cinfo->cquantize = (struct jpeg_color_quantizer *) cquantize;
1842   cquantize->pub.start_pass = start_pass_2_quant;
1843   cquantize->pub.new_color_map = new_color_map_2_quant;
1844   /* Make sure jdmaster didn't give me a case I can't handle */
1845   if (cinfo->out_color_components != 3)
1846     ERREXIT (cinfo, JERR_NOTIMPL);
1847 #else
1848   cquantize = (my_cquantize_ptr) gdCalloc (sizeof (my_cquantizer), 1);
1849   if (!cquantize)
1850     {
1851       /* No can do */
1852       goto outOfMemory;
1853     }
1854 #endif
1855   cquantize->fserrors = NULL;   /* flag optional arrays not allocated */
1856   cquantize->error_limiter = NULL;
1857 
1858 
1859   /* Allocate the histogram/inverse colormap storage */
1860 #ifdef ORIGINAL_LIB_JPEG
1861   cquantize->histogram = (hist3d) (*cinfo->mem->alloc_small)
1862     ((j_common_ptr) cinfo, JPOOL_IMAGE, HIST_C0_ELEMS * SIZEOF (hist2d));
1863   for (i = 0; i < HIST_C0_ELEMS; i++)
1864     {
1865       cquantize->histogram[i] = (hist2d) (*cinfo->mem->alloc_large)
1866         ((j_common_ptr) cinfo, JPOOL_IMAGE,
1867          HIST_C1_ELEMS * HIST_C2_ELEMS * SIZEOF (histcell));
1868     }
1869   cquantize->needs_zeroed = TRUE;       /* histogram is garbage now */
1870 #else
1871   cquantize->histogram = (hist3d) safe_emalloc (HIST_C0_ELEMS, sizeof (hist2d), 0);
1872   for (i = 0; i < HIST_C0_ELEMS; i++)
1873     {
1874       cquantize->histogram[i] =
1875         (hist2d) safe_emalloc (HIST_C1_ELEMS * HIST_C2_ELEMS, sizeof (histcell), 0);
1876       if (!cquantize->histogram[i])
1877         {
1878           goto outOfMemory;
1879         }
1880     }
1881 #endif
1882 
1883 #ifdef ORIGINAL_LIB_JPEG
1884   /* Allocate storage for the completed colormap, if required.
1885    * We do this now since it is FAR storage and may affect
1886    * the memory manager's space calculations.
1887    */
1888   if (cinfo->enable_2pass_quant)
1889     {
1890       /* Make sure color count is acceptable */
1891       int desired = cinfo->desired_number_of_colors;
1892       /* Lower bound on # of colors ... somewhat arbitrary as long as > 0 */
1893       if (desired < 8)
1894         ERREXIT1 (cinfo, JERR_QUANT_FEW_COLORS, 8);
1895       /* Make sure colormap indexes can be represented by JSAMPLEs */
1896       if (desired > MAXNUMCOLORS)
1897         ERREXIT1 (cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS);
1898       cquantize->sv_colormap = (*cinfo->mem->alloc_sarray)
1899         ((j_common_ptr) cinfo, JPOOL_IMAGE, (JDIMENSION) desired,
1900          (JDIMENSION) 3);
1901       cquantize->desired = desired;
1902     }
1903   else
1904     cquantize->sv_colormap = NULL;
1905 
1906   /* Only F-S dithering or no dithering is supported. */
1907   /* If user asks for ordered dither, give him F-S. */
1908   if (cinfo->dither_mode != JDITHER_NONE)
1909     cinfo->dither_mode = JDITHER_FS;
1910 
1911   /* Allocate Floyd-Steinberg workspace if necessary.
1912    * This isn't really needed until pass 2, but again it is FAR storage.
1913    * Although we will cope with a later change in dither_mode,
1914    * we do not promise to honor max_memory_to_use if dither_mode changes.
1915    */
1916   if (cinfo->dither_mode == JDITHER_FS)
1917     {
1918       cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large)
1919         ((j_common_ptr) cinfo, JPOOL_IMAGE,
1920          (size_t) ((cinfo->output_width + 2) * (3 * SIZEOF (FSERROR))));
1921       /* Might as well create the error-limiting table too. */
1922       init_error_limit (cinfo);
1923     }
1924 #else
1925 
1926   cquantize->fserrors = (FSERRPTR) safe_emalloc (3, sizeof (FSERROR), 0);
1927   init_error_limit (oim, nim, cquantize);
1928   arraysize = (size_t) ((nim->sx + 2) * (3 * sizeof (FSERROR)));
1929   /* Allocate Floyd-Steinberg workspace. */
1930   cquantize->fserrors = gdRealloc(cquantize->fserrors, arraysize);
1931   memset(cquantize->fserrors, 0, arraysize);
1932   if (!cquantize->fserrors)
1933     {
1934       goto outOfMemory;
1935     }
1936   cquantize->on_odd_row = FALSE;
1937 
1938   /* Do the work! */
1939   zeroHistogram (cquantize->histogram);
1940   prescan_quantize (oim, nim, cquantize);
1941   /* TBB 2.0.5: pass colorsWanted, not 256! */
1942   select_colors (oim, nim, cquantize, colorsWanted);
1943   zeroHistogram (cquantize->histogram);
1944   if (dither)
1945     {
1946       pass2_fs_dither (oim, nim, cquantize);
1947     }
1948   else
1949     {
1950       pass2_no_dither (oim, nim, cquantize);
1951     }
1952 #if 0                           /* 2.0.12; we no longer attempt full alpha in palettes */
1953   if (cquantize->transparentIsPresent)
1954     {
1955       int mt = -1;
1956       int mtIndex = -1;
1957       for (i = 0; (i < im->colorsTotal); i++)
1958         {
1959           if (im->alpha[i] > mt)
1960             {
1961               mtIndex = i;
1962               mt = im->alpha[i];
1963             }
1964         }
1965       for (i = 0; (i < im->colorsTotal); i++)
1966         {
1967           if (im->alpha[i] == mt)
1968             {
1969               im->alpha[i] = gdAlphaTransparent;
1970             }
1971         }
1972     }
1973   if (cquantize->opaqueIsPresent)
1974     {
1975       int mo = 128;
1976       int moIndex = -1;
1977       for (i = 0; (i < im->colorsTotal); i++)
1978         {
1979           if (im->alpha[i] < mo)
1980             {
1981               moIndex = i;
1982               mo = im->alpha[i];
1983             }
1984         }
1985       for (i = 0; (i < im->colorsTotal); i++)
1986         {
1987           if (im->alpha[i] == mo)
1988             {
1989               im->alpha[i] = gdAlphaOpaque;
1990             }
1991         }
1992     }
1993 #endif
1994 
1995   /* If we had a 'transparent' color, increment the color count so it's
1996    * officially in the palette and convert the transparent variable to point to
1997    * an index rather than a color (Its data already exists and transparent
1998    * pixels have already been mapped to it by this point, it is done late as to
1999    * avoid color matching / dithering with it). */
2000   if (oim->transparent >= 0)
2001     {
2002       nim->transparent = nim->colorsTotal;
2003       nim->colorsTotal++;
2004     }
2005 
2006   /* Success! Get rid of the truecolor image data. */
2007   if (!cimP) {
2008     oim->trueColor = 0;
2009     /* Junk the truecolor pixels */
2010     for (i = 0; i < oim->sy; i++)
2011       {
2012         gdFree (oim->tpixels[i]);
2013       }
2014     gdFree (oim->tpixels);
2015     oim->tpixels = 0;
2016   }
2017   goto success;
2018   /* Tediously free stuff. */
2019 outOfMemory:
2020   if (oim->trueColor)
2021     {
2022       if (!cimP) {
2023         /* On failure only */
2024         for (i = 0; i < nim->sy; i++)
2025         {
2026           if (nim->pixels[i])
2027             {
2028               gdFree (nim->pixels[i]);
2029             }
2030         }
2031         if (nim->pixels)
2032         {
2033           gdFree (nim->pixels);
2034         }
2035         nim->pixels = 0;
2036       } else {
2037         gdImageDestroy(nim);
2038         *cimP = 0;
2039       }
2040     }
2041 success:
2042   for (i = 0; i < HIST_C0_ELEMS; i++)
2043     {
2044       if (cquantize->histogram[i])
2045         {
2046           gdFree (cquantize->histogram[i]);
2047         }
2048     }
2049   if (cquantize->histogram)
2050     {
2051       gdFree (cquantize->histogram);
2052     }
2053   if (cquantize->fserrors)
2054     {
2055       gdFree (cquantize->fserrors);
2056     }
2057   if (cquantize->error_limiter_storage)
2058     {
2059       gdFree (cquantize->error_limiter_storage);
2060     }
2061   if (cquantize)
2062     {
2063       gdFree (cquantize);
2064     }
2065 
2066 #endif
2067 }
2068 
2069 
2070 #endif