Annotation of embedaddon/php/ext/gd/libgd/gd_topal.c, revision 1.1
1.1 ! misho 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
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to gd_topal.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / ext / gd / libgd