1/* 2 * reserved comment block 3 * DO NOT REMOVE OR ALTER! 4 */ 5/* 6 * jquant2.c 7 * 8 * Copyright (C) 1991-1996, Thomas G. Lane. 9 * This file is part of the Independent JPEG Group's software. 10 * For conditions of distribution and use, see the accompanying README file. 11 * 12 * This file contains 2-pass color quantization (color mapping) routines. 13 * These routines provide selection of a custom color map for an image, 14 * followed by mapping of the image to that color map, with optional 15 * Floyd-Steinberg dithering. 16 * It is also possible to use just the second pass to map to an arbitrary 17 * externally-given color map. 18 * 19 * Note: ordered dithering is not supported, since there isn't any fast 20 * way to compute intercolor distances; it's unclear that ordered dither's 21 * fundamental assumptions even hold with an irregularly spaced color map. 22 */ 23 24#define JPEG_INTERNALS 25#include "jinclude.h" 26#include "jpeglib.h" 27 28#ifdef QUANT_2PASS_SUPPORTED 29 30 31/* 32 * This module implements the well-known Heckbert paradigm for color 33 * quantization. Most of the ideas used here can be traced back to 34 * Heckbert's seminal paper 35 * Heckbert, Paul. "Color Image Quantization for Frame Buffer Display", 36 * Proc. SIGGRAPH '82, Computer Graphics v.16 #3 (July 1982), pp 297-304. 37 * 38 * In the first pass over the image, we accumulate a histogram showing the 39 * usage count of each possible color. To keep the histogram to a reasonable 40 * size, we reduce the precision of the input; typical practice is to retain 41 * 5 or 6 bits per color, so that 8 or 4 different input values are counted 42 * in the same histogram cell. 43 * 44 * Next, the color-selection step begins with a box representing the whole 45 * color space, and repeatedly splits the "largest" remaining box until we 46 * have as many boxes as desired colors. Then the mean color in each 47 * remaining box becomes one of the possible output colors. 48 * 49 * The second pass over the image maps each input pixel to the closest output 50 * color (optionally after applying a Floyd-Steinberg dithering correction). 51 * This mapping is logically trivial, but making it go fast enough requires 52 * considerable care. 53 * 54 * Heckbert-style quantizers vary a good deal in their policies for choosing 55 * the "largest" box and deciding where to cut it. The particular policies 56 * used here have proved out well in experimental comparisons, but better ones 57 * may yet be found. 58 * 59 * In earlier versions of the IJG code, this module quantized in YCbCr color 60 * space, processing the raw upsampled data without a color conversion step. 61 * This allowed the color conversion math to be done only once per colormap 62 * entry, not once per pixel. However, that optimization precluded other 63 * useful optimizations (such as merging color conversion with upsampling) 64 * and it also interfered with desired capabilities such as quantizing to an 65 * externally-supplied colormap. We have therefore abandoned that approach. 66 * The present code works in the post-conversion color space, typically RGB. 67 * 68 * To improve the visual quality of the results, we actually work in scaled 69 * RGB space, giving G distances more weight than R, and R in turn more than 70 * B. To do everything in integer math, we must use integer scale factors. 71 * The 2/3/1 scale factors used here correspond loosely to the relative 72 * weights of the colors in the NTSC grayscale equation. 73 * If you want to use this code to quantize a non-RGB color space, you'll 74 * probably need to change these scale factors. 75 */ 76 77#define R_SCALE 2 /* scale R distances by this much */ 78#define G_SCALE 3 /* scale G distances by this much */ 79#define B_SCALE 1 /* and B by this much */ 80 81/* Relabel R/G/B as components 0/1/2, respecting the RGB ordering defined 82 * in jmorecfg.h. As the code stands, it will do the right thing for R,G,B 83 * and B,G,R orders. If you define some other weird order in jmorecfg.h, 84 * you'll get compile errors until you extend this logic. In that case 85 * you'll probably want to tweak the histogram sizes too. 86 */ 87 88#if RGB_RED == 0 89#define C0_SCALE R_SCALE 90#endif 91#if RGB_BLUE == 0 92#define C0_SCALE B_SCALE 93#endif 94#if RGB_GREEN == 1 95#define C1_SCALE G_SCALE 96#endif 97#if RGB_RED == 2 98#define C2_SCALE R_SCALE 99#endif 100#if RGB_BLUE == 2 101#define C2_SCALE B_SCALE 102#endif 103 104 105/* 106 * First we have the histogram data structure and routines for creating it. 107 * 108 * The number of bits of precision can be adjusted by changing these symbols. 109 * We recommend keeping 6 bits for G and 5 each for R and B. 110 * If you have plenty of memory and cycles, 6 bits all around gives marginally 111 * better results; if you are short of memory, 5 bits all around will save 112 * some space but degrade the results. 113 * To maintain a fully accurate histogram, we'd need to allocate a "long" 114 * (preferably unsigned long) for each cell. In practice this is overkill; 115 * we can get by with 16 bits per cell. Few of the cell counts will overflow, 116 * and clamping those that do overflow to the maximum value will give close- 117 * enough results. This reduces the recommended histogram size from 256Kb 118 * to 128Kb, which is a useful savings on PC-class machines. 119 * (In the second pass the histogram space is re-used for pixel mapping data; 120 * in that capacity, each cell must be able to store zero to the number of 121 * desired colors. 16 bits/cell is plenty for that too.) 122 * Since the JPEG code is intended to run in small memory model on 80x86 123 * machines, we can't just allocate the histogram in one chunk. Instead 124 * of a true 3-D array, we use a row of pointers to 2-D arrays. Each 125 * pointer corresponds to a C0 value (typically 2^5 = 32 pointers) and 126 * each 2-D array has 2^6*2^5 = 2048 or 2^6*2^6 = 4096 entries. Note that 127 * on 80x86 machines, the pointer row is in near memory but the actual 128 * arrays are in far memory (same arrangement as we use for image arrays). 129 */ 130 131#define MAXNUMCOLORS (MAXJSAMPLE+1) /* maximum size of colormap */ 132 133/* These will do the right thing for either R,G,B or B,G,R color order, 134 * but you may not like the results for other color orders. 135 */ 136#define HIST_C0_BITS 5 /* bits of precision in R/B histogram */ 137#define HIST_C1_BITS 6 /* bits of precision in G histogram */ 138#define HIST_C2_BITS 5 /* bits of precision in B/R histogram */ 139 140/* Number of elements along histogram axes. */ 141#define HIST_C0_ELEMS (1<<HIST_C0_BITS) 142#define HIST_C1_ELEMS (1<<HIST_C1_BITS) 143#define HIST_C2_ELEMS (1<<HIST_C2_BITS) 144 145/* These are the amounts to shift an input value to get a histogram index. */ 146#define C0_SHIFT (BITS_IN_JSAMPLE-HIST_C0_BITS) 147#define C1_SHIFT (BITS_IN_JSAMPLE-HIST_C1_BITS) 148#define C2_SHIFT (BITS_IN_JSAMPLE-HIST_C2_BITS) 149 150 151typedef UINT16 histcell; /* histogram cell; prefer an unsigned type */ 152 153typedef histcell FAR * histptr; /* for pointers to histogram cells */ 154 155typedef histcell hist1d[HIST_C2_ELEMS]; /* typedefs for the array */ 156typedef hist1d FAR * hist2d; /* type for the 2nd-level pointers */ 157typedef hist2d * hist3d; /* type for top-level pointer */ 158 159 160/* Declarations for Floyd-Steinberg dithering. 161 * 162 * Errors are accumulated into the array fserrors[], at a resolution of 163 * 1/16th of a pixel count. The error at a given pixel is propagated 164 * to its not-yet-processed neighbors using the standard F-S fractions, 165 * ... (here) 7/16 166 * 3/16 5/16 1/16 167 * We work left-to-right on even rows, right-to-left on odd rows. 168 * 169 * We can get away with a single array (holding one row's worth of errors) 170 * by using it to store the current row's errors at pixel columns not yet 171 * processed, but the next row's errors at columns already processed. We 172 * need only a few extra variables to hold the errors immediately around the 173 * current column. (If we are lucky, those variables are in registers, but 174 * even if not, they're probably cheaper to access than array elements are.) 175 * 176 * The fserrors[] array has (#columns + 2) entries; the extra entry at 177 * each end saves us from special-casing the first and last pixels. 178 * Each entry is three values long, one value for each color component. 179 * 180 * Note: on a wide image, we might not have enough room in a PC's near data 181 * segment to hold the error array; so it is allocated with alloc_large. 182 */ 183 184#if BITS_IN_JSAMPLE == 8 185typedef INT16 FSERROR; /* 16 bits should be enough */ 186typedef int LOCFSERROR; /* use 'int' for calculation temps */ 187#else 188typedef INT32 FSERROR; /* may need more than 16 bits */ 189typedef INT32 LOCFSERROR; /* be sure calculation temps are big enough */ 190#endif 191 192typedef FSERROR FAR *FSERRPTR; /* pointer to error array (in FAR storage!) */ 193 194 195/* Private subobject */ 196 197typedef struct { 198 struct jpeg_color_quantizer pub; /* public fields */ 199 200 /* Space for the eventually created colormap is stashed here */ 201 JSAMPARRAY sv_colormap; /* colormap allocated at init time */ 202 int desired; /* desired # of colors = size of colormap */ 203 204 /* Variables for accumulating image statistics */ 205 hist3d histogram; /* pointer to the histogram */ 206 207 boolean needs_zeroed; /* TRUE if next pass must zero histogram */ 208 209 /* Variables for Floyd-Steinberg dithering */ 210 FSERRPTR fserrors; /* accumulated errors */ 211 boolean on_odd_row; /* flag to remember which row we are on */ 212 int * error_limiter; /* table for clamping the applied error */ 213} my_cquantizer; 214 215typedef my_cquantizer * my_cquantize_ptr; 216 217 218/* 219 * Prescan some rows of pixels. 220 * In this module the prescan simply updates the histogram, which has been 221 * initialized to zeroes by start_pass. 222 * An output_buf parameter is required by the method signature, but no data 223 * is actually output (in fact the buffer controller is probably passing a 224 * NULL pointer). 225 */ 226 227METHODDEF(void) 228prescan_quantize (j_decompress_ptr cinfo, JSAMPARRAY input_buf, 229 JSAMPARRAY output_buf, int num_rows) 230{ 231 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 232 register JSAMPROW ptr; 233 register histptr histp; 234 register hist3d histogram = cquantize->histogram; 235 int row; 236 JDIMENSION col; 237 JDIMENSION width = cinfo->output_width; 238 239 for (row = 0; row < num_rows; row++) { 240 ptr = input_buf[row]; 241 for (col = width; col > 0; col--) { 242 /* get pixel value and index into the histogram */ 243 histp = & histogram[GETJSAMPLE(ptr[0]) >> C0_SHIFT] 244 [GETJSAMPLE(ptr[1]) >> C1_SHIFT] 245 [GETJSAMPLE(ptr[2]) >> C2_SHIFT]; 246 /* increment, check for overflow and undo increment if so. */ 247 if (++(*histp) <= 0) 248 (*histp)--; 249 ptr += 3; 250 } 251 } 252} 253 254 255/* 256 * Next we have the really interesting routines: selection of a colormap 257 * given the completed histogram. 258 * These routines work with a list of "boxes", each representing a rectangular 259 * subset of the input color space (to histogram precision). 260 */ 261 262typedef struct { 263 /* The bounds of the box (inclusive); expressed as histogram indexes */ 264 int c0min, c0max; 265 int c1min, c1max; 266 int c2min, c2max; 267 /* The volume (actually 2-norm) of the box */ 268 INT32 volume; 269 /* The number of nonzero histogram cells within this box */ 270 long colorcount; 271} box; 272 273typedef box * boxptr; 274 275 276LOCAL(boxptr) 277find_biggest_color_pop (boxptr boxlist, int numboxes) 278/* Find the splittable box with the largest color population */ 279/* Returns NULL if no splittable boxes remain */ 280{ 281 register boxptr boxp; 282 register int i; 283 register long maxc = 0; 284 boxptr which = NULL; 285 286 for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) { 287 if (boxp->colorcount > maxc && boxp->volume > 0) { 288 which = boxp; 289 maxc = boxp->colorcount; 290 } 291 } 292 return which; 293} 294 295 296LOCAL(boxptr) 297find_biggest_volume (boxptr boxlist, int numboxes) 298/* Find the splittable box with the largest (scaled) volume */ 299/* Returns NULL if no splittable boxes remain */ 300{ 301 register boxptr boxp; 302 register int i; 303 register INT32 maxv = 0; 304 boxptr which = NULL; 305 306 for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) { 307 if (boxp->volume > maxv) { 308 which = boxp; 309 maxv = boxp->volume; 310 } 311 } 312 return which; 313} 314 315 316LOCAL(void) 317update_box (j_decompress_ptr cinfo, boxptr boxp) 318/* Shrink the min/max bounds of a box to enclose only nonzero elements, */ 319/* and recompute its volume and population */ 320{ 321 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 322 hist3d histogram = cquantize->histogram; 323 histptr histp; 324 int c0,c1,c2; 325 int c0min,c0max,c1min,c1max,c2min,c2max; 326 INT32 dist0,dist1,dist2; 327 long ccount; 328 329 c0min = boxp->c0min; c0max = boxp->c0max; 330 c1min = boxp->c1min; c1max = boxp->c1max; 331 c2min = boxp->c2min; c2max = boxp->c2max; 332 333 if (c0max > c0min) 334 for (c0 = c0min; c0 <= c0max; c0++) 335 for (c1 = c1min; c1 <= c1max; c1++) { 336 histp = & histogram[c0][c1][c2min]; 337 for (c2 = c2min; c2 <= c2max; c2++) 338 if (*histp++ != 0) { 339 boxp->c0min = c0min = c0; 340 goto have_c0min; 341 } 342 } 343 have_c0min: 344 if (c0max > c0min) 345 for (c0 = c0max; c0 >= c0min; c0--) 346 for (c1 = c1min; c1 <= c1max; c1++) { 347 histp = & histogram[c0][c1][c2min]; 348 for (c2 = c2min; c2 <= c2max; c2++) 349 if (*histp++ != 0) { 350 boxp->c0max = c0max = c0; 351 goto have_c0max; 352 } 353 } 354 have_c0max: 355 if (c1max > c1min) 356 for (c1 = c1min; c1 <= c1max; c1++) 357 for (c0 = c0min; c0 <= c0max; c0++) { 358 histp = & histogram[c0][c1][c2min]; 359 for (c2 = c2min; c2 <= c2max; c2++) 360 if (*histp++ != 0) { 361 boxp->c1min = c1min = c1; 362 goto have_c1min; 363 } 364 } 365 have_c1min: 366 if (c1max > c1min) 367 for (c1 = c1max; c1 >= c1min; c1--) 368 for (c0 = c0min; c0 <= c0max; c0++) { 369 histp = & histogram[c0][c1][c2min]; 370 for (c2 = c2min; c2 <= c2max; c2++) 371 if (*histp++ != 0) { 372 boxp->c1max = c1max = c1; 373 goto have_c1max; 374 } 375 } 376 have_c1max: 377 if (c2max > c2min) 378 for (c2 = c2min; c2 <= c2max; c2++) 379 for (c0 = c0min; c0 <= c0max; c0++) { 380 histp = & histogram[c0][c1min][c2]; 381 for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS) 382 if (*histp != 0) { 383 boxp->c2min = c2min = c2; 384 goto have_c2min; 385 } 386 } 387 have_c2min: 388 if (c2max > c2min) 389 for (c2 = c2max; c2 >= c2min; c2--) 390 for (c0 = c0min; c0 <= c0max; c0++) { 391 histp = & histogram[c0][c1min][c2]; 392 for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS) 393 if (*histp != 0) { 394 boxp->c2max = c2max = c2; 395 goto have_c2max; 396 } 397 } 398 have_c2max: 399 400 /* Update box volume. 401 * We use 2-norm rather than real volume here; this biases the method 402 * against making long narrow boxes, and it has the side benefit that 403 * a box is splittable iff norm > 0. 404 * Since the differences are expressed in histogram-cell units, 405 * we have to shift back to JSAMPLE units to get consistent distances; 406 * after which, we scale according to the selected distance scale factors. 407 */ 408 dist0 = ((c0max - c0min) << C0_SHIFT) * C0_SCALE; 409 dist1 = ((c1max - c1min) << C1_SHIFT) * C1_SCALE; 410 dist2 = ((c2max - c2min) << C2_SHIFT) * C2_SCALE; 411 boxp->volume = dist0*dist0 + dist1*dist1 + dist2*dist2; 412 413 /* Now scan remaining volume of box and compute population */ 414 ccount = 0; 415 for (c0 = c0min; c0 <= c0max; c0++) 416 for (c1 = c1min; c1 <= c1max; c1++) { 417 histp = & histogram[c0][c1][c2min]; 418 for (c2 = c2min; c2 <= c2max; c2++, histp++) 419 if (*histp != 0) { 420 ccount++; 421 } 422 } 423 boxp->colorcount = ccount; 424} 425 426 427LOCAL(int) 428median_cut (j_decompress_ptr cinfo, boxptr boxlist, int numboxes, 429 int desired_colors) 430/* Repeatedly select and split the largest box until we have enough boxes */ 431{ 432 int n,lb; 433 int c0,c1,c2,cmax; 434 register boxptr b1,b2; 435 436 while (numboxes < desired_colors) { 437 /* Select box to split. 438 * Current algorithm: by population for first half, then by volume. 439 */ 440 if (numboxes*2 <= desired_colors) { 441 b1 = find_biggest_color_pop(boxlist, numboxes); 442 } else { 443 b1 = find_biggest_volume(boxlist, numboxes); 444 } 445 if (b1 == NULL) /* no splittable boxes left! */ 446 break; 447 b2 = &boxlist[numboxes]; /* where new box will go */ 448 /* Copy the color bounds to the new box. */ 449 b2->c0max = b1->c0max; b2->c1max = b1->c1max; b2->c2max = b1->c2max; 450 b2->c0min = b1->c0min; b2->c1min = b1->c1min; b2->c2min = b1->c2min; 451 /* Choose which axis to split the box on. 452 * Current algorithm: longest scaled axis. 453 * See notes in update_box about scaling distances. 454 */ 455 c0 = ((b1->c0max - b1->c0min) << C0_SHIFT) * C0_SCALE; 456 c1 = ((b1->c1max - b1->c1min) << C1_SHIFT) * C1_SCALE; 457 c2 = ((b1->c2max - b1->c2min) << C2_SHIFT) * C2_SCALE; 458 /* We want to break any ties in favor of green, then red, blue last. 459 * This code does the right thing for R,G,B or B,G,R color orders only. 460 */ 461#if RGB_RED == 0 462 cmax = c1; n = 1; 463 if (c0 > cmax) { cmax = c0; n = 0; } 464 if (c2 > cmax) { n = 2; } 465#else 466 cmax = c1; n = 1; 467 if (c2 > cmax) { cmax = c2; n = 2; } 468 if (c0 > cmax) { n = 0; } 469#endif 470 /* Choose split point along selected axis, and update box bounds. 471 * Current algorithm: split at halfway point. 472 * (Since the box has been shrunk to minimum volume, 473 * any split will produce two nonempty subboxes.) 474 * Note that lb value is max for lower box, so must be < old max. 475 */ 476 switch (n) { 477 case 0: 478 lb = (b1->c0max + b1->c0min) / 2; 479 b1->c0max = lb; 480 b2->c0min = lb+1; 481 break; 482 case 1: 483 lb = (b1->c1max + b1->c1min) / 2; 484 b1->c1max = lb; 485 b2->c1min = lb+1; 486 break; 487 case 2: 488 lb = (b1->c2max + b1->c2min) / 2; 489 b1->c2max = lb; 490 b2->c2min = lb+1; 491 break; 492 } 493 /* Update stats for boxes */ 494 update_box(cinfo, b1); 495 update_box(cinfo, b2); 496 numboxes++; 497 } 498 return numboxes; 499} 500 501 502LOCAL(void) 503compute_color (j_decompress_ptr cinfo, boxptr boxp, int icolor) 504/* Compute representative color for a box, put it in colormap[icolor] */ 505{ 506 /* Current algorithm: mean weighted by pixels (not colors) */ 507 /* Note it is important to get the rounding correct! */ 508 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 509 hist3d histogram = cquantize->histogram; 510 histptr histp; 511 int c0,c1,c2; 512 int c0min,c0max,c1min,c1max,c2min,c2max; 513 long count; 514 long total = 0; 515 long c0total = 0; 516 long c1total = 0; 517 long c2total = 0; 518 519 c0min = boxp->c0min; c0max = boxp->c0max; 520 c1min = boxp->c1min; c1max = boxp->c1max; 521 c2min = boxp->c2min; c2max = boxp->c2max; 522 523 for (c0 = c0min; c0 <= c0max; c0++) 524 for (c1 = c1min; c1 <= c1max; c1++) { 525 histp = & histogram[c0][c1][c2min]; 526 for (c2 = c2min; c2 <= c2max; c2++) { 527 if ((count = *histp++) != 0) { 528 total += count; 529 c0total += ((c0 << C0_SHIFT) + ((1<<C0_SHIFT)>>1)) * count; 530 c1total += ((c1 << C1_SHIFT) + ((1<<C1_SHIFT)>>1)) * count; 531 c2total += ((c2 << C2_SHIFT) + ((1<<C2_SHIFT)>>1)) * count; 532 } 533 } 534 } 535 536 cinfo->colormap[0][icolor] = (JSAMPLE) ((c0total + (total>>1)) / total); 537 cinfo->colormap[1][icolor] = (JSAMPLE) ((c1total + (total>>1)) / total); 538 cinfo->colormap[2][icolor] = (JSAMPLE) ((c2total + (total>>1)) / total); 539} 540 541 542LOCAL(void) 543select_colors (j_decompress_ptr cinfo, int desired_colors) 544/* Master routine for color selection */ 545{ 546 boxptr boxlist; 547 int numboxes; 548 int i; 549 550 /* Allocate workspace for box list */ 551 boxlist = (boxptr) (*cinfo->mem->alloc_small) 552 ((j_common_ptr) cinfo, JPOOL_IMAGE, desired_colors * SIZEOF(box)); 553 /* Initialize one box containing whole space */ 554 numboxes = 1; 555 boxlist[0].c0min = 0; 556 boxlist[0].c0max = MAXJSAMPLE >> C0_SHIFT; 557 boxlist[0].c1min = 0; 558 boxlist[0].c1max = MAXJSAMPLE >> C1_SHIFT; 559 boxlist[0].c2min = 0; 560 boxlist[0].c2max = MAXJSAMPLE >> C2_SHIFT; 561 /* Shrink it to actually-used volume and set its statistics */ 562 update_box(cinfo, & boxlist[0]); 563 /* Perform median-cut to produce final box list */ 564 numboxes = median_cut(cinfo, boxlist, numboxes, desired_colors); 565 /* Compute the representative color for each box, fill colormap */ 566 for (i = 0; i < numboxes; i++) 567 compute_color(cinfo, & boxlist[i], i); 568 cinfo->actual_number_of_colors = numboxes; 569 TRACEMS1(cinfo, 1, JTRC_QUANT_SELECTED, numboxes); 570} 571 572 573/* 574 * These routines are concerned with the time-critical task of mapping input 575 * colors to the nearest color in the selected colormap. 576 * 577 * We re-use the histogram space as an "inverse color map", essentially a 578 * cache for the results of nearest-color searches. All colors within a 579 * histogram cell will be mapped to the same colormap entry, namely the one 580 * closest to the cell's center. This may not be quite the closest entry to 581 * the actual input color, but it's almost as good. A zero in the cache 582 * indicates we haven't found the nearest color for that cell yet; the array 583 * is cleared to zeroes before starting the mapping pass. When we find the 584 * nearest color for a cell, its colormap index plus one is recorded in the 585 * cache for future use. The pass2 scanning routines call fill_inverse_cmap 586 * when they need to use an unfilled entry in the cache. 587 * 588 * Our method of efficiently finding nearest colors is based on the "locally 589 * sorted search" idea described by Heckbert and on the incremental distance 590 * calculation described by Spencer W. Thomas in chapter III.1 of Graphics 591 * Gems II (James Arvo, ed. Academic Press, 1991). Thomas points out that 592 * the distances from a given colormap entry to each cell of the histogram can 593 * be computed quickly using an incremental method: the differences between 594 * distances to adjacent cells themselves differ by a constant. This allows a 595 * fairly fast implementation of the "brute force" approach of computing the 596 * distance from every colormap entry to every histogram cell. Unfortunately, 597 * it needs a work array to hold the best-distance-so-far for each histogram 598 * cell (because the inner loop has to be over cells, not colormap entries). 599 * The work array elements have to be INT32s, so the work array would need 600 * 256Kb at our recommended precision. This is not feasible in DOS machines. 601 * 602 * To get around these problems, we apply Thomas' method to compute the 603 * nearest colors for only the cells within a small subbox of the histogram. 604 * The work array need be only as big as the subbox, so the memory usage 605 * problem is solved. Furthermore, we need not fill subboxes that are never 606 * referenced in pass2; many images use only part of the color gamut, so a 607 * fair amount of work is saved. An additional advantage of this 608 * approach is that we can apply Heckbert's locality criterion to quickly 609 * eliminate colormap entries that are far away from the subbox; typically 610 * three-fourths of the colormap entries are rejected by Heckbert's criterion, 611 * and we need not compute their distances to individual cells in the subbox. 612 * The speed of this approach is heavily influenced by the subbox size: too 613 * small means too much overhead, too big loses because Heckbert's criterion 614 * can't eliminate as many colormap entries. Empirically the best subbox 615 * size seems to be about 1/512th of the histogram (1/8th in each direction). 616 * 617 * Thomas' article also describes a refined method which is asymptotically 618 * faster than the brute-force method, but it is also far more complex and 619 * cannot efficiently be applied to small subboxes. It is therefore not 620 * useful for programs intended to be portable to DOS machines. On machines 621 * with plenty of memory, filling the whole histogram in one shot with Thomas' 622 * refined method might be faster than the present code --- but then again, 623 * it might not be any faster, and it's certainly more complicated. 624 */ 625 626 627/* log2(histogram cells in update box) for each axis; this can be adjusted */ 628#define BOX_C0_LOG (HIST_C0_BITS-3) 629#define BOX_C1_LOG (HIST_C1_BITS-3) 630#define BOX_C2_LOG (HIST_C2_BITS-3) 631 632#define BOX_C0_ELEMS (1<<BOX_C0_LOG) /* # of hist cells in update box */ 633#define BOX_C1_ELEMS (1<<BOX_C1_LOG) 634#define BOX_C2_ELEMS (1<<BOX_C2_LOG) 635 636#define BOX_C0_SHIFT (C0_SHIFT + BOX_C0_LOG) 637#define BOX_C1_SHIFT (C1_SHIFT + BOX_C1_LOG) 638#define BOX_C2_SHIFT (C2_SHIFT + BOX_C2_LOG) 639 640 641/* 642 * The next three routines implement inverse colormap filling. They could 643 * all be folded into one big routine, but splitting them up this way saves 644 * some stack space (the mindist[] and bestdist[] arrays need not coexist) 645 * and may allow some compilers to produce better code by registerizing more 646 * inner-loop variables. 647 */ 648 649LOCAL(int) 650find_nearby_colors (j_decompress_ptr cinfo, int minc0, int minc1, int minc2, 651 JSAMPLE colorlist[]) 652/* Locate the colormap entries close enough to an update box to be candidates 653 * for the nearest entry to some cell(s) in the update box. The update box 654 * is specified by the center coordinates of its first cell. The number of 655 * candidate colormap entries is returned, and their colormap indexes are 656 * placed in colorlist[]. 657 * This routine uses Heckbert's "locally sorted search" criterion to select 658 * the colors that need further consideration. 659 */ 660{ 661 int numcolors = cinfo->actual_number_of_colors; 662 int maxc0, maxc1, maxc2; 663 int centerc0, centerc1, centerc2; 664 int i, x, ncolors; 665 INT32 minmaxdist, min_dist, max_dist, tdist; 666 INT32 mindist[MAXNUMCOLORS]; /* min distance to colormap entry i */ 667 668 /* Compute true coordinates of update box's upper corner and center. 669 * Actually we compute the coordinates of the center of the upper-corner 670 * histogram cell, which are the upper bounds of the volume we care about. 671 * Note that since ">>" rounds down, the "center" values may be closer to 672 * min than to max; hence comparisons to them must be "<=", not "<". 673 */ 674 maxc0 = minc0 + ((1 << BOX_C0_SHIFT) - (1 << C0_SHIFT)); 675 centerc0 = (minc0 + maxc0) >> 1; 676 maxc1 = minc1 + ((1 << BOX_C1_SHIFT) - (1 << C1_SHIFT)); 677 centerc1 = (minc1 + maxc1) >> 1; 678 maxc2 = minc2 + ((1 << BOX_C2_SHIFT) - (1 << C2_SHIFT)); 679 centerc2 = (minc2 + maxc2) >> 1; 680 681 /* For each color in colormap, find: 682 * 1. its minimum squared-distance to any point in the update box 683 * (zero if color is within update box); 684 * 2. its maximum squared-distance to any point in the update box. 685 * Both of these can be found by considering only the corners of the box. 686 * We save the minimum distance for each color in mindist[]; 687 * only the smallest maximum distance is of interest. 688 */ 689 minmaxdist = 0x7FFFFFFFL; 690 691 for (i = 0; i < numcolors; i++) { 692 /* We compute the squared-c0-distance term, then add in the other two. */ 693 x = GETJSAMPLE(cinfo->colormap[0][i]); 694 if (x < minc0) { 695 tdist = (x - minc0) * C0_SCALE; 696 min_dist = tdist*tdist; 697 tdist = (x - maxc0) * C0_SCALE; 698 max_dist = tdist*tdist; 699 } else if (x > maxc0) { 700 tdist = (x - maxc0) * C0_SCALE; 701 min_dist = tdist*tdist; 702 tdist = (x - minc0) * C0_SCALE; 703 max_dist = tdist*tdist; 704 } else { 705 /* within cell range so no contribution to min_dist */ 706 min_dist = 0; 707 if (x <= centerc0) { 708 tdist = (x - maxc0) * C0_SCALE; 709 max_dist = tdist*tdist; 710 } else { 711 tdist = (x - minc0) * C0_SCALE; 712 max_dist = tdist*tdist; 713 } 714 } 715 716 x = GETJSAMPLE(cinfo->colormap[1][i]); 717 if (x < minc1) { 718 tdist = (x - minc1) * C1_SCALE; 719 min_dist += tdist*tdist; 720 tdist = (x - maxc1) * C1_SCALE; 721 max_dist += tdist*tdist; 722 } else if (x > maxc1) { 723 tdist = (x - maxc1) * C1_SCALE; 724 min_dist += tdist*tdist; 725 tdist = (x - minc1) * C1_SCALE; 726 max_dist += tdist*tdist; 727 } else { 728 /* within cell range so no contribution to min_dist */ 729 if (x <= centerc1) { 730 tdist = (x - maxc1) * C1_SCALE; 731 max_dist += tdist*tdist; 732 } else { 733 tdist = (x - minc1) * C1_SCALE; 734 max_dist += tdist*tdist; 735 } 736 } 737 738 x = GETJSAMPLE(cinfo->colormap[2][i]); 739 if (x < minc2) { 740 tdist = (x - minc2) * C2_SCALE; 741 min_dist += tdist*tdist; 742 tdist = (x - maxc2) * C2_SCALE; 743 max_dist += tdist*tdist; 744 } else if (x > maxc2) { 745 tdist = (x - maxc2) * C2_SCALE; 746 min_dist += tdist*tdist; 747 tdist = (x - minc2) * C2_SCALE; 748 max_dist += tdist*tdist; 749 } else { 750 /* within cell range so no contribution to min_dist */ 751 if (x <= centerc2) { 752 tdist = (x - maxc2) * C2_SCALE; 753 max_dist += tdist*tdist; 754 } else { 755 tdist = (x - minc2) * C2_SCALE; 756 max_dist += tdist*tdist; 757 } 758 } 759 760 mindist[i] = min_dist; /* save away the results */ 761 if (max_dist < minmaxdist) 762 minmaxdist = max_dist; 763 } 764 765 /* Now we know that no cell in the update box is more than minmaxdist 766 * away from some colormap entry. Therefore, only colors that are 767 * within minmaxdist of some part of the box need be considered. 768 */ 769 ncolors = 0; 770 for (i = 0; i < numcolors; i++) { 771 if (mindist[i] <= minmaxdist) 772 colorlist[ncolors++] = (JSAMPLE) i; 773 } 774 return ncolors; 775} 776 777 778LOCAL(void) 779find_best_colors (j_decompress_ptr cinfo, int minc0, int minc1, int minc2, 780 int numcolors, JSAMPLE colorlist[], JSAMPLE bestcolor[]) 781/* Find the closest colormap entry for each cell in the update box, 782 * given the list of candidate colors prepared by find_nearby_colors. 783 * Return the indexes of the closest entries in the bestcolor[] array. 784 * This routine uses Thomas' incremental distance calculation method to 785 * find the distance from a colormap entry to successive cells in the box. 786 */ 787{ 788 int ic0, ic1, ic2; 789 int i, icolor; 790 register INT32 * bptr; /* pointer into bestdist[] array */ 791 JSAMPLE * cptr; /* pointer into bestcolor[] array */ 792 INT32 dist0, dist1; /* initial distance values */ 793 register INT32 dist2; /* current distance in inner loop */ 794 INT32 xx0, xx1; /* distance increments */ 795 register INT32 xx2; 796 INT32 inc0, inc1, inc2; /* initial values for increments */ 797 /* This array holds the distance to the nearest-so-far color for each cell */ 798 INT32 bestdist[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS]; 799 800 /* Initialize best-distance for each cell of the update box */ 801 bptr = bestdist; 802 for (i = BOX_C0_ELEMS*BOX_C1_ELEMS*BOX_C2_ELEMS-1; i >= 0; i--) 803 *bptr++ = 0x7FFFFFFFL; 804 805 /* For each color selected by find_nearby_colors, 806 * compute its distance to the center of each cell in the box. 807 * If that's less than best-so-far, update best distance and color number. 808 */ 809 810 /* Nominal steps between cell centers ("x" in Thomas article) */ 811#define STEP_C0 ((1 << C0_SHIFT) * C0_SCALE) 812#define STEP_C1 ((1 << C1_SHIFT) * C1_SCALE) 813#define STEP_C2 ((1 << C2_SHIFT) * C2_SCALE) 814 815 for (i = 0; i < numcolors; i++) { 816 icolor = GETJSAMPLE(colorlist[i]); 817 /* Compute (square of) distance from minc0/c1/c2 to this color */ 818 inc0 = (minc0 - GETJSAMPLE(cinfo->colormap[0][icolor])) * C0_SCALE; 819 dist0 = inc0*inc0; 820 inc1 = (minc1 - GETJSAMPLE(cinfo->colormap[1][icolor])) * C1_SCALE; 821 dist0 += inc1*inc1; 822 inc2 = (minc2 - GETJSAMPLE(cinfo->colormap[2][icolor])) * C2_SCALE; 823 dist0 += inc2*inc2; 824 /* Form the initial difference increments */ 825 inc0 = inc0 * (2 * STEP_C0) + STEP_C0 * STEP_C0; 826 inc1 = inc1 * (2 * STEP_C1) + STEP_C1 * STEP_C1; 827 inc2 = inc2 * (2 * STEP_C2) + STEP_C2 * STEP_C2; 828 /* Now loop over all cells in box, updating distance per Thomas method */ 829 bptr = bestdist; 830 cptr = bestcolor; 831 xx0 = inc0; 832 for (ic0 = BOX_C0_ELEMS-1; ic0 >= 0; ic0--) { 833 dist1 = dist0; 834 xx1 = inc1; 835 for (ic1 = BOX_C1_ELEMS-1; ic1 >= 0; ic1--) { 836 dist2 = dist1; 837 xx2 = inc2; 838 for (ic2 = BOX_C2_ELEMS-1; ic2 >= 0; ic2--) { 839 if (dist2 < *bptr) { 840 *bptr = dist2; 841 *cptr = (JSAMPLE) icolor; 842 } 843 dist2 += xx2; 844 xx2 += 2 * STEP_C2 * STEP_C2; 845 bptr++; 846 cptr++; 847 } 848 dist1 += xx1; 849 xx1 += 2 * STEP_C1 * STEP_C1; 850 } 851 dist0 += xx0; 852 xx0 += 2 * STEP_C0 * STEP_C0; 853 } 854 } 855} 856 857 858LOCAL(void) 859fill_inverse_cmap (j_decompress_ptr cinfo, int c0, int c1, int c2) 860/* Fill the inverse-colormap entries in the update box that contains */ 861/* histogram cell c0/c1/c2. (Only that one cell MUST be filled, but */ 862/* we can fill as many others as we wish.) */ 863{ 864 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 865 hist3d histogram = cquantize->histogram; 866 int minc0, minc1, minc2; /* lower left corner of update box */ 867 int ic0, ic1, ic2; 868 register JSAMPLE * cptr; /* pointer into bestcolor[] array */ 869 register histptr cachep; /* pointer into main cache array */ 870 /* This array lists the candidate colormap indexes. */ 871 JSAMPLE colorlist[MAXNUMCOLORS]; 872 int numcolors; /* number of candidate colors */ 873 /* This array holds the actually closest colormap index for each cell. */ 874 JSAMPLE bestcolor[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS]; 875 876 /* Convert cell coordinates to update box ID */ 877 c0 >>= BOX_C0_LOG; 878 c1 >>= BOX_C1_LOG; 879 c2 >>= BOX_C2_LOG; 880 881 /* Compute true coordinates of update box's origin corner. 882 * Actually we compute the coordinates of the center of the corner 883 * histogram cell, which are the lower bounds of the volume we care about. 884 */ 885 minc0 = (c0 << BOX_C0_SHIFT) + ((1 << C0_SHIFT) >> 1); 886 minc1 = (c1 << BOX_C1_SHIFT) + ((1 << C1_SHIFT) >> 1); 887 minc2 = (c2 << BOX_C2_SHIFT) + ((1 << C2_SHIFT) >> 1); 888 889 /* Determine which colormap entries are close enough to be candidates 890 * for the nearest entry to some cell in the update box. 891 */ 892 numcolors = find_nearby_colors(cinfo, minc0, minc1, minc2, colorlist); 893 894 /* Determine the actually nearest colors. */ 895 find_best_colors(cinfo, minc0, minc1, minc2, numcolors, colorlist, 896 bestcolor); 897 898 /* Save the best color numbers (plus 1) in the main cache array */ 899 c0 <<= BOX_C0_LOG; /* convert ID back to base cell indexes */ 900 c1 <<= BOX_C1_LOG; 901 c2 <<= BOX_C2_LOG; 902 cptr = bestcolor; 903 for (ic0 = 0; ic0 < BOX_C0_ELEMS; ic0++) { 904 for (ic1 = 0; ic1 < BOX_C1_ELEMS; ic1++) { 905 cachep = & histogram[c0+ic0][c1+ic1][c2]; 906 for (ic2 = 0; ic2 < BOX_C2_ELEMS; ic2++) { 907 *cachep++ = (histcell) (GETJSAMPLE(*cptr++) + 1); 908 } 909 } 910 } 911} 912 913 914/* 915 * Map some rows of pixels to the output colormapped representation. 916 */ 917 918METHODDEF(void) 919pass2_no_dither (j_decompress_ptr cinfo, 920 JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows) 921/* This version performs no dithering */ 922{ 923 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 924 hist3d histogram = cquantize->histogram; 925 register JSAMPROW inptr, outptr; 926 register histptr cachep; 927 register int c0, c1, c2; 928 int row; 929 JDIMENSION col; 930 JDIMENSION width = cinfo->output_width; 931 932 for (row = 0; row < num_rows; row++) { 933 inptr = input_buf[row]; 934 outptr = output_buf[row]; 935 for (col = width; col > 0; col--) { 936 /* get pixel value and index into the cache */ 937 c0 = GETJSAMPLE(*inptr++) >> C0_SHIFT; 938 c1 = GETJSAMPLE(*inptr++) >> C1_SHIFT; 939 c2 = GETJSAMPLE(*inptr++) >> C2_SHIFT; 940 cachep = & histogram[c0][c1][c2]; 941 /* If we have not seen this color before, find nearest colormap entry */ 942 /* and update the cache */ 943 if (*cachep == 0) 944 fill_inverse_cmap(cinfo, c0,c1,c2); 945 /* Now emit the colormap index for this cell */ 946 *outptr++ = (JSAMPLE) (*cachep - 1); 947 } 948 } 949} 950 951 952METHODDEF(void) 953pass2_fs_dither (j_decompress_ptr cinfo, 954 JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows) 955/* This version performs Floyd-Steinberg dithering */ 956{ 957 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 958 hist3d histogram = cquantize->histogram; 959 register LOCFSERROR cur0, cur1, cur2; /* current error or pixel value */ 960 LOCFSERROR belowerr0, belowerr1, belowerr2; /* error for pixel below cur */ 961 LOCFSERROR bpreverr0, bpreverr1, bpreverr2; /* error for below/prev col */ 962 register FSERRPTR errorptr; /* => fserrors[] at column before current */ 963 JSAMPROW inptr; /* => current input pixel */ 964 JSAMPROW outptr; /* => current output pixel */ 965 histptr cachep; 966 int dir; /* +1 or -1 depending on direction */ 967 int dir3; /* 3*dir, for advancing inptr & errorptr */ 968 int row; 969 JDIMENSION col; 970 JDIMENSION width = cinfo->output_width; 971 JSAMPLE *range_limit = cinfo->sample_range_limit; 972 int *error_limit = cquantize->error_limiter; 973 JSAMPROW colormap0 = cinfo->colormap[0]; 974 JSAMPROW colormap1 = cinfo->colormap[1]; 975 JSAMPROW colormap2 = cinfo->colormap[2]; 976 SHIFT_TEMPS 977 978 for (row = 0; row < num_rows; row++) { 979 inptr = input_buf[row]; 980 outptr = output_buf[row]; 981 if (cquantize->on_odd_row) { 982 /* work right to left in this row */ 983 inptr += (width-1) * 3; /* so point to rightmost pixel */ 984 outptr += width-1; 985 dir = -1; 986 dir3 = -3; 987 errorptr = cquantize->fserrors + (width+1)*3; /* => entry after last column */ 988 cquantize->on_odd_row = FALSE; /* flip for next time */ 989 } else { 990 /* work left to right in this row */ 991 dir = 1; 992 dir3 = 3; 993 errorptr = cquantize->fserrors; /* => entry before first real column */ 994 cquantize->on_odd_row = TRUE; /* flip for next time */ 995 } 996 /* Preset error values: no error propagated to first pixel from left */ 997 cur0 = cur1 = cur2 = 0; 998 /* and no error propagated to row below yet */ 999 belowerr0 = belowerr1 = belowerr2 = 0; 1000 bpreverr0 = bpreverr1 = bpreverr2 = 0; 1001 1002 for (col = width; col > 0; col--) { 1003 /* curN holds the error propagated from the previous pixel on the 1004 * current line. Add the error propagated from the previous line 1005 * to form the complete error correction term for this pixel, and 1006 * round the error term (which is expressed * 16) to an integer. 1007 * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct 1008 * for either sign of the error value. 1009 * Note: errorptr points to *previous* column's array entry. 1010 */ 1011 cur0 = RIGHT_SHIFT(cur0 + errorptr[dir3+0] + 8, 4); 1012 cur1 = RIGHT_SHIFT(cur1 + errorptr[dir3+1] + 8, 4); 1013 cur2 = RIGHT_SHIFT(cur2 + errorptr[dir3+2] + 8, 4); 1014 /* Limit the error using transfer function set by init_error_limit. 1015 * See comments with init_error_limit for rationale. 1016 */ 1017 cur0 = error_limit[cur0]; 1018 cur1 = error_limit[cur1]; 1019 cur2 = error_limit[cur2]; 1020 /* Form pixel value + error, and range-limit to 0..MAXJSAMPLE. 1021 * The maximum error is +- MAXJSAMPLE (or less with error limiting); 1022 * this sets the required size of the range_limit array. 1023 */ 1024 cur0 += GETJSAMPLE(inptr[0]); 1025 cur1 += GETJSAMPLE(inptr[1]); 1026 cur2 += GETJSAMPLE(inptr[2]); 1027 cur0 = GETJSAMPLE(range_limit[cur0]); 1028 cur1 = GETJSAMPLE(range_limit[cur1]); 1029 cur2 = GETJSAMPLE(range_limit[cur2]); 1030 /* Index into the cache with adjusted pixel value */ 1031 cachep = & histogram[cur0>>C0_SHIFT][cur1>>C1_SHIFT][cur2>>C2_SHIFT]; 1032 /* If we have not seen this color before, find nearest colormap */ 1033 /* entry and update the cache */ 1034 if (*cachep == 0) 1035 fill_inverse_cmap(cinfo, cur0>>C0_SHIFT,cur1>>C1_SHIFT,cur2>>C2_SHIFT); 1036 /* Now emit the colormap index for this cell */ 1037 { register int pixcode = *cachep - 1; 1038 *outptr = (JSAMPLE) pixcode; 1039 /* Compute representation error for this pixel */ 1040 cur0 -= GETJSAMPLE(colormap0[pixcode]); 1041 cur1 -= GETJSAMPLE(colormap1[pixcode]); 1042 cur2 -= GETJSAMPLE(colormap2[pixcode]); 1043 } 1044 /* Compute error fractions to be propagated to adjacent pixels. 1045 * Add these into the running sums, and simultaneously shift the 1046 * next-line error sums left by 1 column. 1047 */ 1048 { register LOCFSERROR bnexterr, delta; 1049 1050 bnexterr = cur0; /* Process component 0 */ 1051 delta = cur0 * 2; 1052 cur0 += delta; /* form error * 3 */ 1053 errorptr[0] = (FSERROR) (bpreverr0 + cur0); 1054 cur0 += delta; /* form error * 5 */ 1055 bpreverr0 = belowerr0 + cur0; 1056 belowerr0 = bnexterr; 1057 cur0 += delta; /* form error * 7 */ 1058 bnexterr = cur1; /* Process component 1 */ 1059 delta = cur1 * 2; 1060 cur1 += delta; /* form error * 3 */ 1061 errorptr[1] = (FSERROR) (bpreverr1 + cur1); 1062 cur1 += delta; /* form error * 5 */ 1063 bpreverr1 = belowerr1 + cur1; 1064 belowerr1 = bnexterr; 1065 cur1 += delta; /* form error * 7 */ 1066 bnexterr = cur2; /* Process component 2 */ 1067 delta = cur2 * 2; 1068 cur2 += delta; /* form error * 3 */ 1069 errorptr[2] = (FSERROR) (bpreverr2 + cur2); 1070 cur2 += delta; /* form error * 5 */ 1071 bpreverr2 = belowerr2 + cur2; 1072 belowerr2 = bnexterr; 1073 cur2 += delta; /* form error * 7 */ 1074 } 1075 /* At this point curN contains the 7/16 error value to be propagated 1076 * to the next pixel on the current line, and all the errors for the 1077 * next line have been shifted over. We are therefore ready to move on. 1078 */ 1079 inptr += dir3; /* Advance pixel pointers to next column */ 1080 outptr += dir; 1081 errorptr += dir3; /* advance errorptr to current column */ 1082 } 1083 /* Post-loop cleanup: we must unload the final error values into the 1084 * final fserrors[] entry. Note we need not unload belowerrN because 1085 * it is for the dummy column before or after the actual array. 1086 */ 1087 errorptr[0] = (FSERROR) bpreverr0; /* unload prev errs into array */ 1088 errorptr[1] = (FSERROR) bpreverr1; 1089 errorptr[2] = (FSERROR) bpreverr2; 1090 } 1091} 1092 1093 1094/* 1095 * Initialize the error-limiting transfer function (lookup table). 1096 * The raw F-S error computation can potentially compute error values of up to 1097 * +- MAXJSAMPLE. But we want the maximum correction applied to a pixel to be 1098 * much less, otherwise obviously wrong pixels will be created. (Typical 1099 * effects include weird fringes at color-area boundaries, isolated bright 1100 * pixels in a dark area, etc.) The standard advice for avoiding this problem 1101 * is to ensure that the "corners" of the color cube are allocated as output 1102 * colors; then repeated errors in the same direction cannot cause cascading 1103 * error buildup. However, that only prevents the error from getting 1104 * completely out of hand; Aaron Giles reports that error limiting improves 1105 * the results even with corner colors allocated. 1106 * A simple clamping of the error values to about +- MAXJSAMPLE/8 works pretty 1107 * well, but the smoother transfer function used below is even better. Thanks 1108 * to Aaron Giles for this idea. 1109 */ 1110 1111LOCAL(void) 1112init_error_limit (j_decompress_ptr cinfo) 1113/* Allocate and fill in the error_limiter table */ 1114{ 1115 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 1116 int * table; 1117 int in, out; 1118 1119 table = (int *) (*cinfo->mem->alloc_small) 1120 ((j_common_ptr) cinfo, JPOOL_IMAGE, (MAXJSAMPLE*2+1) * SIZEOF(int)); 1121 table += MAXJSAMPLE; /* so can index -MAXJSAMPLE .. +MAXJSAMPLE */ 1122 cquantize->error_limiter = table; 1123 1124#define STEPSIZE ((MAXJSAMPLE+1)/16) 1125 /* Map errors 1:1 up to +- MAXJSAMPLE/16 */ 1126 out = 0; 1127 for (in = 0; in < STEPSIZE; in++, out++) { 1128 table[in] = out; table[-in] = -out; 1129 } 1130 /* Map errors 1:2 up to +- 3*MAXJSAMPLE/16 */ 1131 for (; in < STEPSIZE*3; in++, out += (in&1) ? 0 : 1) { 1132 table[in] = out; table[-in] = -out; 1133 } 1134 /* Clamp the rest to final out value (which is (MAXJSAMPLE+1)/8) */ 1135 for (; in <= MAXJSAMPLE; in++) { 1136 table[in] = out; table[-in] = -out; 1137 } 1138#undef STEPSIZE 1139} 1140 1141 1142/* 1143 * Finish up at the end of each pass. 1144 */ 1145 1146METHODDEF(void) 1147finish_pass1 (j_decompress_ptr cinfo) 1148{ 1149 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 1150 1151 /* Select the representative colors and fill in cinfo->colormap */ 1152 cinfo->colormap = cquantize->sv_colormap; 1153 select_colors(cinfo, cquantize->desired); 1154 /* Force next pass to zero the color index table */ 1155 cquantize->needs_zeroed = TRUE; 1156} 1157 1158 1159METHODDEF(void) 1160finish_pass2 (j_decompress_ptr cinfo) 1161{ 1162 /* no work */ 1163} 1164 1165 1166/* 1167 * Initialize for each processing pass. 1168 */ 1169 1170METHODDEF(void) 1171start_pass_2_quant (j_decompress_ptr cinfo, boolean is_pre_scan) 1172{ 1173 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 1174 hist3d histogram = cquantize->histogram; 1175 int i; 1176 1177 /* Only F-S dithering or no dithering is supported. */ 1178 /* If user asks for ordered dither, give him F-S. */ 1179 if (cinfo->dither_mode != JDITHER_NONE) 1180 cinfo->dither_mode = JDITHER_FS; 1181 1182 if (is_pre_scan) { 1183 /* Set up method pointers */ 1184 cquantize->pub.color_quantize = prescan_quantize; 1185 cquantize->pub.finish_pass = finish_pass1; 1186 cquantize->needs_zeroed = TRUE; /* Always zero histogram */ 1187 } else { 1188 /* Set up method pointers */ 1189 if (cinfo->dither_mode == JDITHER_FS) 1190 cquantize->pub.color_quantize = pass2_fs_dither; 1191 else 1192 cquantize->pub.color_quantize = pass2_no_dither; 1193 cquantize->pub.finish_pass = finish_pass2; 1194 1195 /* Make sure color count is acceptable */ 1196 i = cinfo->actual_number_of_colors; 1197 if (i < 1) 1198 ERREXIT1(cinfo, JERR_QUANT_FEW_COLORS, 1); 1199 if (i > MAXNUMCOLORS) 1200 ERREXIT1(cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS); 1201 1202 if (cinfo->dither_mode == JDITHER_FS) { 1203 size_t arraysize = (size_t) ((cinfo->output_width + 2) * 1204 (3 * SIZEOF(FSERROR))); 1205 /* Allocate Floyd-Steinberg workspace if we didn't already. */ 1206 if (cquantize->fserrors == NULL) 1207 cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large) 1208 ((j_common_ptr) cinfo, JPOOL_IMAGE, arraysize); 1209 /* Initialize the propagated errors to zero. */ 1210 jzero_far((void FAR *) cquantize->fserrors, arraysize); 1211 /* Make the error-limit table if we didn't already. */ 1212 if (cquantize->error_limiter == NULL) 1213 init_error_limit(cinfo); 1214 cquantize->on_odd_row = FALSE; 1215 } 1216 1217 } 1218 /* Zero the histogram or inverse color map, if necessary */ 1219 if (cquantize->needs_zeroed) { 1220 for (i = 0; i < HIST_C0_ELEMS; i++) { 1221 jzero_far((void FAR *) histogram[i], 1222 HIST_C1_ELEMS*HIST_C2_ELEMS * SIZEOF(histcell)); 1223 } 1224 cquantize->needs_zeroed = FALSE; 1225 } 1226} 1227 1228 1229/* 1230 * Switch to a new external colormap between output passes. 1231 */ 1232 1233METHODDEF(void) 1234new_color_map_2_quant (j_decompress_ptr cinfo) 1235{ 1236 my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 1237 1238 /* Reset the inverse color map */ 1239 cquantize->needs_zeroed = TRUE; 1240} 1241 1242 1243/* 1244 * Module initialization routine for 2-pass color quantization. 1245 */ 1246 1247GLOBAL(void) 1248jinit_2pass_quantizer (j_decompress_ptr cinfo) 1249{ 1250 my_cquantize_ptr cquantize; 1251 int i; 1252 1253 cquantize = (my_cquantize_ptr) 1254 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 1255 SIZEOF(my_cquantizer)); 1256 cinfo->cquantize = (struct jpeg_color_quantizer *) cquantize; 1257 cquantize->pub.start_pass = start_pass_2_quant; 1258 cquantize->pub.new_color_map = new_color_map_2_quant; 1259 cquantize->fserrors = NULL; /* flag optional arrays not allocated */ 1260 cquantize->error_limiter = NULL; 1261 1262 /* Make sure jdmaster didn't give me a case I can't handle */ 1263 if (cinfo->out_color_components != 3) 1264 ERREXIT(cinfo, JERR_NOTIMPL); 1265 1266 /* Allocate the histogram/inverse colormap storage */ 1267 cquantize->histogram = (hist3d) (*cinfo->mem->alloc_small) 1268 ((j_common_ptr) cinfo, JPOOL_IMAGE, HIST_C0_ELEMS * SIZEOF(hist2d)); 1269 for (i = 0; i < HIST_C0_ELEMS; i++) { 1270 cquantize->histogram[i] = (hist2d) (*cinfo->mem->alloc_large) 1271 ((j_common_ptr) cinfo, JPOOL_IMAGE, 1272 HIST_C1_ELEMS*HIST_C2_ELEMS * SIZEOF(histcell)); 1273 } 1274 cquantize->needs_zeroed = TRUE; /* histogram is garbage now */ 1275 1276 /* Allocate storage for the completed colormap, if required. 1277 * We do this now since it is FAR storage and may affect 1278 * the memory manager's space calculations. 1279 */ 1280 if (cinfo->enable_2pass_quant) { 1281 /* Make sure color count is acceptable */ 1282 int desired = cinfo->desired_number_of_colors; 1283 /* Lower bound on # of colors ... somewhat arbitrary as long as > 0 */ 1284 if (desired < 8) 1285 ERREXIT1(cinfo, JERR_QUANT_FEW_COLORS, 8); 1286 /* Make sure colormap indexes can be represented by JSAMPLEs */ 1287 if (desired > MAXNUMCOLORS) 1288 ERREXIT1(cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS); 1289 cquantize->sv_colormap = (*cinfo->mem->alloc_sarray) 1290 ((j_common_ptr) cinfo,JPOOL_IMAGE, (JDIMENSION) desired, (JDIMENSION) 3); 1291 cquantize->desired = desired; 1292 } else 1293 cquantize->sv_colormap = NULL; 1294 1295 /* Only F-S dithering or no dithering is supported. */ 1296 /* If user asks for ordered dither, give him F-S. */ 1297 if (cinfo->dither_mode != JDITHER_NONE) 1298 cinfo->dither_mode = JDITHER_FS; 1299 1300 /* Allocate Floyd-Steinberg workspace if necessary. 1301 * This isn't really needed until pass 2, but again it is FAR storage. 1302 * Although we will cope with a later change in dither_mode, 1303 * we do not promise to honor max_memory_to_use if dither_mode changes. 1304 */ 1305 if (cinfo->dither_mode == JDITHER_FS) { 1306 cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large) 1307 ((j_common_ptr) cinfo, JPOOL_IMAGE, 1308 (size_t) ((cinfo->output_width + 2) * (3 * SIZEOF(FSERROR)))); 1309 /* Might as well create the error-limiting table too. */ 1310 init_error_limit(cinfo); 1311 } 1312} 1313 1314#endif /* QUANT_2PASS_SUPPORTED */ 1315