vrshoot
diff libs/libjpeg/jquant2.c @ 0:b2f14e535253
initial commit
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Sat, 01 Feb 2014 19:58:19 +0200 |
| parents | |
| children |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/libs/libjpeg/jquant2.c Sat Feb 01 19:58:19 2014 +0200 1.3 @@ -0,0 +1,1310 @@ 1.4 +/* 1.5 + * jquant2.c 1.6 + * 1.7 + * Copyright (C) 1991-1996, Thomas G. Lane. 1.8 + * This file is part of the Independent JPEG Group's software. 1.9 + * For conditions of distribution and use, see the accompanying README file. 1.10 + * 1.11 + * This file contains 2-pass color quantization (color mapping) routines. 1.12 + * These routines provide selection of a custom color map for an image, 1.13 + * followed by mapping of the image to that color map, with optional 1.14 + * Floyd-Steinberg dithering. 1.15 + * It is also possible to use just the second pass to map to an arbitrary 1.16 + * externally-given color map. 1.17 + * 1.18 + * Note: ordered dithering is not supported, since there isn't any fast 1.19 + * way to compute intercolor distances; it's unclear that ordered dither's 1.20 + * fundamental assumptions even hold with an irregularly spaced color map. 1.21 + */ 1.22 + 1.23 +#define JPEG_INTERNALS 1.24 +#include "jinclude.h" 1.25 +#include "jpeglib.h" 1.26 + 1.27 +#ifdef QUANT_2PASS_SUPPORTED 1.28 + 1.29 + 1.30 +/* 1.31 + * This module implements the well-known Heckbert paradigm for color 1.32 + * quantization. Most of the ideas used here can be traced back to 1.33 + * Heckbert's seminal paper 1.34 + * Heckbert, Paul. "Color Image Quantization for Frame Buffer Display", 1.35 + * Proc. SIGGRAPH '82, Computer Graphics v.16 #3 (July 1982), pp 297-304. 1.36 + * 1.37 + * In the first pass over the image, we accumulate a histogram showing the 1.38 + * usage count of each possible color. To keep the histogram to a reasonable 1.39 + * size, we reduce the precision of the input; typical practice is to retain 1.40 + * 5 or 6 bits per color, so that 8 or 4 different input values are counted 1.41 + * in the same histogram cell. 1.42 + * 1.43 + * Next, the color-selection step begins with a box representing the whole 1.44 + * color space, and repeatedly splits the "largest" remaining box until we 1.45 + * have as many boxes as desired colors. Then the mean color in each 1.46 + * remaining box becomes one of the possible output colors. 1.47 + * 1.48 + * The second pass over the image maps each input pixel to the closest output 1.49 + * color (optionally after applying a Floyd-Steinberg dithering correction). 1.50 + * This mapping is logically trivial, but making it go fast enough requires 1.51 + * considerable care. 1.52 + * 1.53 + * Heckbert-style quantizers vary a good deal in their policies for choosing 1.54 + * the "largest" box and deciding where to cut it. The particular policies 1.55 + * used here have proved out well in experimental comparisons, but better ones 1.56 + * may yet be found. 1.57 + * 1.58 + * In earlier versions of the IJG code, this module quantized in YCbCr color 1.59 + * space, processing the raw upsampled data without a color conversion step. 1.60 + * This allowed the color conversion math to be done only once per colormap 1.61 + * entry, not once per pixel. However, that optimization precluded other 1.62 + * useful optimizations (such as merging color conversion with upsampling) 1.63 + * and it also interfered with desired capabilities such as quantizing to an 1.64 + * externally-supplied colormap. We have therefore abandoned that approach. 1.65 + * The present code works in the post-conversion color space, typically RGB. 1.66 + * 1.67 + * To improve the visual quality of the results, we actually work in scaled 1.68 + * RGB space, giving G distances more weight than R, and R in turn more than 1.69 + * B. To do everything in integer math, we must use integer scale factors. 1.70 + * The 2/3/1 scale factors used here correspond loosely to the relative 1.71 + * weights of the colors in the NTSC grayscale equation. 1.72 + * If you want to use this code to quantize a non-RGB color space, you'll 1.73 + * probably need to change these scale factors. 1.74 + */ 1.75 + 1.76 +#define R_SCALE 2 /* scale R distances by this much */ 1.77 +#define G_SCALE 3 /* scale G distances by this much */ 1.78 +#define B_SCALE 1 /* and B by this much */ 1.79 + 1.80 +/* Relabel R/G/B as components 0/1/2, respecting the RGB ordering defined 1.81 + * in jmorecfg.h. As the code stands, it will do the right thing for R,G,B 1.82 + * and B,G,R orders. If you define some other weird order in jmorecfg.h, 1.83 + * you'll get compile errors until you extend this logic. In that case 1.84 + * you'll probably want to tweak the histogram sizes too. 1.85 + */ 1.86 + 1.87 +#if RGB_RED == 0 1.88 +#define C0_SCALE R_SCALE 1.89 +#endif 1.90 +#if RGB_BLUE == 0 1.91 +#define C0_SCALE B_SCALE 1.92 +#endif 1.93 +#if RGB_GREEN == 1 1.94 +#define C1_SCALE G_SCALE 1.95 +#endif 1.96 +#if RGB_RED == 2 1.97 +#define C2_SCALE R_SCALE 1.98 +#endif 1.99 +#if RGB_BLUE == 2 1.100 +#define C2_SCALE B_SCALE 1.101 +#endif 1.102 + 1.103 + 1.104 +/* 1.105 + * First we have the histogram data structure and routines for creating it. 1.106 + * 1.107 + * The number of bits of precision can be adjusted by changing these symbols. 1.108 + * We recommend keeping 6 bits for G and 5 each for R and B. 1.109 + * If you have plenty of memory and cycles, 6 bits all around gives marginally 1.110 + * better results; if you are short of memory, 5 bits all around will save 1.111 + * some space but degrade the results. 1.112 + * To maintain a fully accurate histogram, we'd need to allocate a "long" 1.113 + * (preferably unsigned long) for each cell. In practice this is overkill; 1.114 + * we can get by with 16 bits per cell. Few of the cell counts will overflow, 1.115 + * and clamping those that do overflow to the maximum value will give close- 1.116 + * enough results. This reduces the recommended histogram size from 256Kb 1.117 + * to 128Kb, which is a useful savings on PC-class machines. 1.118 + * (In the second pass the histogram space is re-used for pixel mapping data; 1.119 + * in that capacity, each cell must be able to store zero to the number of 1.120 + * desired colors. 16 bits/cell is plenty for that too.) 1.121 + * Since the JPEG code is intended to run in small memory model on 80x86 1.122 + * machines, we can't just allocate the histogram in one chunk. Instead 1.123 + * of a true 3-D array, we use a row of pointers to 2-D arrays. Each 1.124 + * pointer corresponds to a C0 value (typically 2^5 = 32 pointers) and 1.125 + * each 2-D array has 2^6*2^5 = 2048 or 2^6*2^6 = 4096 entries. Note that 1.126 + * on 80x86 machines, the pointer row is in near memory but the actual 1.127 + * arrays are in far memory (same arrangement as we use for image arrays). 1.128 + */ 1.129 + 1.130 +#define MAXNUMCOLORS (MAXJSAMPLE+1) /* maximum size of colormap */ 1.131 + 1.132 +/* These will do the right thing for either R,G,B or B,G,R color order, 1.133 + * but you may not like the results for other color orders. 1.134 + */ 1.135 +#define HIST_C0_BITS 5 /* bits of precision in R/B histogram */ 1.136 +#define HIST_C1_BITS 6 /* bits of precision in G histogram */ 1.137 +#define HIST_C2_BITS 5 /* bits of precision in B/R histogram */ 1.138 + 1.139 +/* Number of elements along histogram axes. */ 1.140 +#define HIST_C0_ELEMS (1<<HIST_C0_BITS) 1.141 +#define HIST_C1_ELEMS (1<<HIST_C1_BITS) 1.142 +#define HIST_C2_ELEMS (1<<HIST_C2_BITS) 1.143 + 1.144 +/* These are the amounts to shift an input value to get a histogram index. */ 1.145 +#define C0_SHIFT (BITS_IN_JSAMPLE-HIST_C0_BITS) 1.146 +#define C1_SHIFT (BITS_IN_JSAMPLE-HIST_C1_BITS) 1.147 +#define C2_SHIFT (BITS_IN_JSAMPLE-HIST_C2_BITS) 1.148 + 1.149 + 1.150 +typedef UINT16 histcell; /* histogram cell; prefer an unsigned type */ 1.151 + 1.152 +typedef histcell FAR * histptr; /* for pointers to histogram cells */ 1.153 + 1.154 +typedef histcell hist1d[HIST_C2_ELEMS]; /* typedefs for the array */ 1.155 +typedef hist1d FAR * hist2d; /* type for the 2nd-level pointers */ 1.156 +typedef hist2d * hist3d; /* type for top-level pointer */ 1.157 + 1.158 + 1.159 +/* Declarations for Floyd-Steinberg dithering. 1.160 + * 1.161 + * Errors are accumulated into the array fserrors[], at a resolution of 1.162 + * 1/16th of a pixel count. The error at a given pixel is propagated 1.163 + * to its not-yet-processed neighbors using the standard F-S fractions, 1.164 + * ... (here) 7/16 1.165 + * 3/16 5/16 1/16 1.166 + * We work left-to-right on even rows, right-to-left on odd rows. 1.167 + * 1.168 + * We can get away with a single array (holding one row's worth of errors) 1.169 + * by using it to store the current row's errors at pixel columns not yet 1.170 + * processed, but the next row's errors at columns already processed. We 1.171 + * need only a few extra variables to hold the errors immediately around the 1.172 + * current column. (If we are lucky, those variables are in registers, but 1.173 + * even if not, they're probably cheaper to access than array elements are.) 1.174 + * 1.175 + * The fserrors[] array has (#columns + 2) entries; the extra entry at 1.176 + * each end saves us from special-casing the first and last pixels. 1.177 + * Each entry is three values long, one value for each color component. 1.178 + * 1.179 + * Note: on a wide image, we might not have enough room in a PC's near data 1.180 + * segment to hold the error array; so it is allocated with alloc_large. 1.181 + */ 1.182 + 1.183 +#if BITS_IN_JSAMPLE == 8 1.184 +typedef INT16 FSERROR; /* 16 bits should be enough */ 1.185 +typedef int LOCFSERROR; /* use 'int' for calculation temps */ 1.186 +#else 1.187 +typedef INT32 FSERROR; /* may need more than 16 bits */ 1.188 +typedef INT32 LOCFSERROR; /* be sure calculation temps are big enough */ 1.189 +#endif 1.190 + 1.191 +typedef FSERROR FAR *FSERRPTR; /* pointer to error array (in FAR storage!) */ 1.192 + 1.193 + 1.194 +/* Private subobject */ 1.195 + 1.196 +typedef struct { 1.197 + struct jpeg_color_quantizer pub; /* public fields */ 1.198 + 1.199 + /* Space for the eventually created colormap is stashed here */ 1.200 + JSAMPARRAY sv_colormap; /* colormap allocated at init time */ 1.201 + int desired; /* desired # of colors = size of colormap */ 1.202 + 1.203 + /* Variables for accumulating image statistics */ 1.204 + hist3d histogram; /* pointer to the histogram */ 1.205 + 1.206 + boolean needs_zeroed; /* TRUE if next pass must zero histogram */ 1.207 + 1.208 + /* Variables for Floyd-Steinberg dithering */ 1.209 + FSERRPTR fserrors; /* accumulated errors */ 1.210 + boolean on_odd_row; /* flag to remember which row we are on */ 1.211 + int * error_limiter; /* table for clamping the applied error */ 1.212 +} my_cquantizer; 1.213 + 1.214 +typedef my_cquantizer * my_cquantize_ptr; 1.215 + 1.216 + 1.217 +/* 1.218 + * Prescan some rows of pixels. 1.219 + * In this module the prescan simply updates the histogram, which has been 1.220 + * initialized to zeroes by start_pass. 1.221 + * An output_buf parameter is required by the method signature, but no data 1.222 + * is actually output (in fact the buffer controller is probably passing a 1.223 + * NULL pointer). 1.224 + */ 1.225 + 1.226 +METHODDEF(void) 1.227 +prescan_quantize (j_decompress_ptr cinfo, JSAMPARRAY input_buf, 1.228 + JSAMPARRAY output_buf, int num_rows) 1.229 +{ 1.230 + my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 1.231 + register JSAMPROW ptr; 1.232 + register histptr histp; 1.233 + register hist3d histogram = cquantize->histogram; 1.234 + int row; 1.235 + JDIMENSION col; 1.236 + JDIMENSION width = cinfo->output_width; 1.237 + 1.238 + for (row = 0; row < num_rows; row++) { 1.239 + ptr = input_buf[row]; 1.240 + for (col = width; col > 0; col--) { 1.241 + /* get pixel value and index into the histogram */ 1.242 + histp = & histogram[GETJSAMPLE(ptr[0]) >> C0_SHIFT] 1.243 + [GETJSAMPLE(ptr[1]) >> C1_SHIFT] 1.244 + [GETJSAMPLE(ptr[2]) >> C2_SHIFT]; 1.245 + /* increment, check for overflow and undo increment if so. */ 1.246 + if (++(*histp) <= 0) 1.247 + (*histp)--; 1.248 + ptr += 3; 1.249 + } 1.250 + } 1.251 +} 1.252 + 1.253 + 1.254 +/* 1.255 + * Next we have the really interesting routines: selection of a colormap 1.256 + * given the completed histogram. 1.257 + * These routines work with a list of "boxes", each representing a rectangular 1.258 + * subset of the input color space (to histogram precision). 1.259 + */ 1.260 + 1.261 +typedef struct { 1.262 + /* The bounds of the box (inclusive); expressed as histogram indexes */ 1.263 + int c0min, c0max; 1.264 + int c1min, c1max; 1.265 + int c2min, c2max; 1.266 + /* The volume (actually 2-norm) of the box */ 1.267 + INT32 volume; 1.268 + /* The number of nonzero histogram cells within this box */ 1.269 + long colorcount; 1.270 +} box; 1.271 + 1.272 +typedef box * boxptr; 1.273 + 1.274 + 1.275 +LOCAL(boxptr) 1.276 +find_biggest_color_pop (boxptr boxlist, int numboxes) 1.277 +/* Find the splittable box with the largest color population */ 1.278 +/* Returns NULL if no splittable boxes remain */ 1.279 +{ 1.280 + register boxptr boxp; 1.281 + register int i; 1.282 + register long maxc = 0; 1.283 + boxptr which = NULL; 1.284 + 1.285 + for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) { 1.286 + if (boxp->colorcount > maxc && boxp->volume > 0) { 1.287 + which = boxp; 1.288 + maxc = boxp->colorcount; 1.289 + } 1.290 + } 1.291 + return which; 1.292 +} 1.293 + 1.294 + 1.295 +LOCAL(boxptr) 1.296 +find_biggest_volume (boxptr boxlist, int numboxes) 1.297 +/* Find the splittable box with the largest (scaled) volume */ 1.298 +/* Returns NULL if no splittable boxes remain */ 1.299 +{ 1.300 + register boxptr boxp; 1.301 + register int i; 1.302 + register INT32 maxv = 0; 1.303 + boxptr which = NULL; 1.304 + 1.305 + for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) { 1.306 + if (boxp->volume > maxv) { 1.307 + which = boxp; 1.308 + maxv = boxp->volume; 1.309 + } 1.310 + } 1.311 + return which; 1.312 +} 1.313 + 1.314 + 1.315 +LOCAL(void) 1.316 +update_box (j_decompress_ptr cinfo, boxptr boxp) 1.317 +/* Shrink the min/max bounds of a box to enclose only nonzero elements, */ 1.318 +/* and recompute its volume and population */ 1.319 +{ 1.320 + my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 1.321 + hist3d histogram = cquantize->histogram; 1.322 + histptr histp; 1.323 + int c0,c1,c2; 1.324 + int c0min,c0max,c1min,c1max,c2min,c2max; 1.325 + INT32 dist0,dist1,dist2; 1.326 + long ccount; 1.327 + 1.328 + c0min = boxp->c0min; c0max = boxp->c0max; 1.329 + c1min = boxp->c1min; c1max = boxp->c1max; 1.330 + c2min = boxp->c2min; c2max = boxp->c2max; 1.331 + 1.332 + if (c0max > c0min) 1.333 + for (c0 = c0min; c0 <= c0max; c0++) 1.334 + for (c1 = c1min; c1 <= c1max; c1++) { 1.335 + histp = & histogram[c0][c1][c2min]; 1.336 + for (c2 = c2min; c2 <= c2max; c2++) 1.337 + if (*histp++ != 0) { 1.338 + boxp->c0min = c0min = c0; 1.339 + goto have_c0min; 1.340 + } 1.341 + } 1.342 + have_c0min: 1.343 + if (c0max > c0min) 1.344 + for (c0 = c0max; c0 >= c0min; c0--) 1.345 + for (c1 = c1min; c1 <= c1max; c1++) { 1.346 + histp = & histogram[c0][c1][c2min]; 1.347 + for (c2 = c2min; c2 <= c2max; c2++) 1.348 + if (*histp++ != 0) { 1.349 + boxp->c0max = c0max = c0; 1.350 + goto have_c0max; 1.351 + } 1.352 + } 1.353 + have_c0max: 1.354 + if (c1max > c1min) 1.355 + for (c1 = c1min; c1 <= c1max; c1++) 1.356 + for (c0 = c0min; c0 <= c0max; c0++) { 1.357 + histp = & histogram[c0][c1][c2min]; 1.358 + for (c2 = c2min; c2 <= c2max; c2++) 1.359 + if (*histp++ != 0) { 1.360 + boxp->c1min = c1min = c1; 1.361 + goto have_c1min; 1.362 + } 1.363 + } 1.364 + have_c1min: 1.365 + if (c1max > c1min) 1.366 + for (c1 = c1max; c1 >= c1min; c1--) 1.367 + for (c0 = c0min; c0 <= c0max; c0++) { 1.368 + histp = & histogram[c0][c1][c2min]; 1.369 + for (c2 = c2min; c2 <= c2max; c2++) 1.370 + if (*histp++ != 0) { 1.371 + boxp->c1max = c1max = c1; 1.372 + goto have_c1max; 1.373 + } 1.374 + } 1.375 + have_c1max: 1.376 + if (c2max > c2min) 1.377 + for (c2 = c2min; c2 <= c2max; c2++) 1.378 + for (c0 = c0min; c0 <= c0max; c0++) { 1.379 + histp = & histogram[c0][c1min][c2]; 1.380 + for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS) 1.381 + if (*histp != 0) { 1.382 + boxp->c2min = c2min = c2; 1.383 + goto have_c2min; 1.384 + } 1.385 + } 1.386 + have_c2min: 1.387 + if (c2max > c2min) 1.388 + for (c2 = c2max; c2 >= c2min; c2--) 1.389 + for (c0 = c0min; c0 <= c0max; c0++) { 1.390 + histp = & histogram[c0][c1min][c2]; 1.391 + for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS) 1.392 + if (*histp != 0) { 1.393 + boxp->c2max = c2max = c2; 1.394 + goto have_c2max; 1.395 + } 1.396 + } 1.397 + have_c2max: 1.398 + 1.399 + /* Update box volume. 1.400 + * We use 2-norm rather than real volume here; this biases the method 1.401 + * against making long narrow boxes, and it has the side benefit that 1.402 + * a box is splittable iff norm > 0. 1.403 + * Since the differences are expressed in histogram-cell units, 1.404 + * we have to shift back to JSAMPLE units to get consistent distances; 1.405 + * after which, we scale according to the selected distance scale factors. 1.406 + */ 1.407 + dist0 = ((c0max - c0min) << C0_SHIFT) * C0_SCALE; 1.408 + dist1 = ((c1max - c1min) << C1_SHIFT) * C1_SCALE; 1.409 + dist2 = ((c2max - c2min) << C2_SHIFT) * C2_SCALE; 1.410 + boxp->volume = dist0*dist0 + dist1*dist1 + dist2*dist2; 1.411 + 1.412 + /* Now scan remaining volume of box and compute population */ 1.413 + ccount = 0; 1.414 + for (c0 = c0min; c0 <= c0max; c0++) 1.415 + for (c1 = c1min; c1 <= c1max; c1++) { 1.416 + histp = & histogram[c0][c1][c2min]; 1.417 + for (c2 = c2min; c2 <= c2max; c2++, histp++) 1.418 + if (*histp != 0) { 1.419 + ccount++; 1.420 + } 1.421 + } 1.422 + boxp->colorcount = ccount; 1.423 +} 1.424 + 1.425 + 1.426 +LOCAL(int) 1.427 +median_cut (j_decompress_ptr cinfo, boxptr boxlist, int numboxes, 1.428 + int desired_colors) 1.429 +/* Repeatedly select and split the largest box until we have enough boxes */ 1.430 +{ 1.431 + int n,lb; 1.432 + int c0,c1,c2,cmax; 1.433 + register boxptr b1,b2; 1.434 + 1.435 + while (numboxes < desired_colors) { 1.436 + /* Select box to split. 1.437 + * Current algorithm: by population for first half, then by volume. 1.438 + */ 1.439 + if (numboxes*2 <= desired_colors) { 1.440 + b1 = find_biggest_color_pop(boxlist, numboxes); 1.441 + } else { 1.442 + b1 = find_biggest_volume(boxlist, numboxes); 1.443 + } 1.444 + if (b1 == NULL) /* no splittable boxes left! */ 1.445 + break; 1.446 + b2 = &boxlist[numboxes]; /* where new box will go */ 1.447 + /* Copy the color bounds to the new box. */ 1.448 + b2->c0max = b1->c0max; b2->c1max = b1->c1max; b2->c2max = b1->c2max; 1.449 + b2->c0min = b1->c0min; b2->c1min = b1->c1min; b2->c2min = b1->c2min; 1.450 + /* Choose which axis to split the box on. 1.451 + * Current algorithm: longest scaled axis. 1.452 + * See notes in update_box about scaling distances. 1.453 + */ 1.454 + c0 = ((b1->c0max - b1->c0min) << C0_SHIFT) * C0_SCALE; 1.455 + c1 = ((b1->c1max - b1->c1min) << C1_SHIFT) * C1_SCALE; 1.456 + c2 = ((b1->c2max - b1->c2min) << C2_SHIFT) * C2_SCALE; 1.457 + /* We want to break any ties in favor of green, then red, blue last. 1.458 + * This code does the right thing for R,G,B or B,G,R color orders only. 1.459 + */ 1.460 +#if RGB_RED == 0 1.461 + cmax = c1; n = 1; 1.462 + if (c0 > cmax) { cmax = c0; n = 0; } 1.463 + if (c2 > cmax) { n = 2; } 1.464 +#else 1.465 + cmax = c1; n = 1; 1.466 + if (c2 > cmax) { cmax = c2; n = 2; } 1.467 + if (c0 > cmax) { n = 0; } 1.468 +#endif 1.469 + /* Choose split point along selected axis, and update box bounds. 1.470 + * Current algorithm: split at halfway point. 1.471 + * (Since the box has been shrunk to minimum volume, 1.472 + * any split will produce two nonempty subboxes.) 1.473 + * Note that lb value is max for lower box, so must be < old max. 1.474 + */ 1.475 + switch (n) { 1.476 + case 0: 1.477 + lb = (b1->c0max + b1->c0min) / 2; 1.478 + b1->c0max = lb; 1.479 + b2->c0min = lb+1; 1.480 + break; 1.481 + case 1: 1.482 + lb = (b1->c1max + b1->c1min) / 2; 1.483 + b1->c1max = lb; 1.484 + b2->c1min = lb+1; 1.485 + break; 1.486 + case 2: 1.487 + lb = (b1->c2max + b1->c2min) / 2; 1.488 + b1->c2max = lb; 1.489 + b2->c2min = lb+1; 1.490 + break; 1.491 + } 1.492 + /* Update stats for boxes */ 1.493 + update_box(cinfo, b1); 1.494 + update_box(cinfo, b2); 1.495 + numboxes++; 1.496 + } 1.497 + return numboxes; 1.498 +} 1.499 + 1.500 + 1.501 +LOCAL(void) 1.502 +compute_color (j_decompress_ptr cinfo, boxptr boxp, int icolor) 1.503 +/* Compute representative color for a box, put it in colormap[icolor] */ 1.504 +{ 1.505 + /* Current algorithm: mean weighted by pixels (not colors) */ 1.506 + /* Note it is important to get the rounding correct! */ 1.507 + my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 1.508 + hist3d histogram = cquantize->histogram; 1.509 + histptr histp; 1.510 + int c0,c1,c2; 1.511 + int c0min,c0max,c1min,c1max,c2min,c2max; 1.512 + long count; 1.513 + long total = 0; 1.514 + long c0total = 0; 1.515 + long c1total = 0; 1.516 + long c2total = 0; 1.517 + 1.518 + c0min = boxp->c0min; c0max = boxp->c0max; 1.519 + c1min = boxp->c1min; c1max = boxp->c1max; 1.520 + c2min = boxp->c2min; c2max = boxp->c2max; 1.521 + 1.522 + for (c0 = c0min; c0 <= c0max; c0++) 1.523 + for (c1 = c1min; c1 <= c1max; c1++) { 1.524 + histp = & histogram[c0][c1][c2min]; 1.525 + for (c2 = c2min; c2 <= c2max; c2++) { 1.526 + if ((count = *histp++) != 0) { 1.527 + total += count; 1.528 + c0total += ((c0 << C0_SHIFT) + ((1<<C0_SHIFT)>>1)) * count; 1.529 + c1total += ((c1 << C1_SHIFT) + ((1<<C1_SHIFT)>>1)) * count; 1.530 + c2total += ((c2 << C2_SHIFT) + ((1<<C2_SHIFT)>>1)) * count; 1.531 + } 1.532 + } 1.533 + } 1.534 + 1.535 + cinfo->colormap[0][icolor] = (JSAMPLE) ((c0total + (total>>1)) / total); 1.536 + cinfo->colormap[1][icolor] = (JSAMPLE) ((c1total + (total>>1)) / total); 1.537 + cinfo->colormap[2][icolor] = (JSAMPLE) ((c2total + (total>>1)) / total); 1.538 +} 1.539 + 1.540 + 1.541 +LOCAL(void) 1.542 +select_colors (j_decompress_ptr cinfo, int desired_colors) 1.543 +/* Master routine for color selection */ 1.544 +{ 1.545 + boxptr boxlist; 1.546 + int numboxes; 1.547 + int i; 1.548 + 1.549 + /* Allocate workspace for box list */ 1.550 + boxlist = (boxptr) (*cinfo->mem->alloc_small) 1.551 + ((j_common_ptr) cinfo, JPOOL_IMAGE, desired_colors * SIZEOF(box)); 1.552 + /* Initialize one box containing whole space */ 1.553 + numboxes = 1; 1.554 + boxlist[0].c0min = 0; 1.555 + boxlist[0].c0max = MAXJSAMPLE >> C0_SHIFT; 1.556 + boxlist[0].c1min = 0; 1.557 + boxlist[0].c1max = MAXJSAMPLE >> C1_SHIFT; 1.558 + boxlist[0].c2min = 0; 1.559 + boxlist[0].c2max = MAXJSAMPLE >> C2_SHIFT; 1.560 + /* Shrink it to actually-used volume and set its statistics */ 1.561 + update_box(cinfo, & boxlist[0]); 1.562 + /* Perform median-cut to produce final box list */ 1.563 + numboxes = median_cut(cinfo, boxlist, numboxes, desired_colors); 1.564 + /* Compute the representative color for each box, fill colormap */ 1.565 + for (i = 0; i < numboxes; i++) 1.566 + compute_color(cinfo, & boxlist[i], i); 1.567 + cinfo->actual_number_of_colors = numboxes; 1.568 + TRACEMS1(cinfo, 1, JTRC_QUANT_SELECTED, numboxes); 1.569 +} 1.570 + 1.571 + 1.572 +/* 1.573 + * These routines are concerned with the time-critical task of mapping input 1.574 + * colors to the nearest color in the selected colormap. 1.575 + * 1.576 + * We re-use the histogram space as an "inverse color map", essentially a 1.577 + * cache for the results of nearest-color searches. All colors within a 1.578 + * histogram cell will be mapped to the same colormap entry, namely the one 1.579 + * closest to the cell's center. This may not be quite the closest entry to 1.580 + * the actual input color, but it's almost as good. A zero in the cache 1.581 + * indicates we haven't found the nearest color for that cell yet; the array 1.582 + * is cleared to zeroes before starting the mapping pass. When we find the 1.583 + * nearest color for a cell, its colormap index plus one is recorded in the 1.584 + * cache for future use. The pass2 scanning routines call fill_inverse_cmap 1.585 + * when they need to use an unfilled entry in the cache. 1.586 + * 1.587 + * Our method of efficiently finding nearest colors is based on the "locally 1.588 + * sorted search" idea described by Heckbert and on the incremental distance 1.589 + * calculation described by Spencer W. Thomas in chapter III.1 of Graphics 1.590 + * Gems II (James Arvo, ed. Academic Press, 1991). Thomas points out that 1.591 + * the distances from a given colormap entry to each cell of the histogram can 1.592 + * be computed quickly using an incremental method: the differences between 1.593 + * distances to adjacent cells themselves differ by a constant. This allows a 1.594 + * fairly fast implementation of the "brute force" approach of computing the 1.595 + * distance from every colormap entry to every histogram cell. Unfortunately, 1.596 + * it needs a work array to hold the best-distance-so-far for each histogram 1.597 + * cell (because the inner loop has to be over cells, not colormap entries). 1.598 + * The work array elements have to be INT32s, so the work array would need 1.599 + * 256Kb at our recommended precision. This is not feasible in DOS machines. 1.600 + * 1.601 + * To get around these problems, we apply Thomas' method to compute the 1.602 + * nearest colors for only the cells within a small subbox of the histogram. 1.603 + * The work array need be only as big as the subbox, so the memory usage 1.604 + * problem is solved. Furthermore, we need not fill subboxes that are never 1.605 + * referenced in pass2; many images use only part of the color gamut, so a 1.606 + * fair amount of work is saved. An additional advantage of this 1.607 + * approach is that we can apply Heckbert's locality criterion to quickly 1.608 + * eliminate colormap entries that are far away from the subbox; typically 1.609 + * three-fourths of the colormap entries are rejected by Heckbert's criterion, 1.610 + * and we need not compute their distances to individual cells in the subbox. 1.611 + * The speed of this approach is heavily influenced by the subbox size: too 1.612 + * small means too much overhead, too big loses because Heckbert's criterion 1.613 + * can't eliminate as many colormap entries. Empirically the best subbox 1.614 + * size seems to be about 1/512th of the histogram (1/8th in each direction). 1.615 + * 1.616 + * Thomas' article also describes a refined method which is asymptotically 1.617 + * faster than the brute-force method, but it is also far more complex and 1.618 + * cannot efficiently be applied to small subboxes. It is therefore not 1.619 + * useful for programs intended to be portable to DOS machines. On machines 1.620 + * with plenty of memory, filling the whole histogram in one shot with Thomas' 1.621 + * refined method might be faster than the present code --- but then again, 1.622 + * it might not be any faster, and it's certainly more complicated. 1.623 + */ 1.624 + 1.625 + 1.626 +/* log2(histogram cells in update box) for each axis; this can be adjusted */ 1.627 +#define BOX_C0_LOG (HIST_C0_BITS-3) 1.628 +#define BOX_C1_LOG (HIST_C1_BITS-3) 1.629 +#define BOX_C2_LOG (HIST_C2_BITS-3) 1.630 + 1.631 +#define BOX_C0_ELEMS (1<<BOX_C0_LOG) /* # of hist cells in update box */ 1.632 +#define BOX_C1_ELEMS (1<<BOX_C1_LOG) 1.633 +#define BOX_C2_ELEMS (1<<BOX_C2_LOG) 1.634 + 1.635 +#define BOX_C0_SHIFT (C0_SHIFT + BOX_C0_LOG) 1.636 +#define BOX_C1_SHIFT (C1_SHIFT + BOX_C1_LOG) 1.637 +#define BOX_C2_SHIFT (C2_SHIFT + BOX_C2_LOG) 1.638 + 1.639 + 1.640 +/* 1.641 + * The next three routines implement inverse colormap filling. They could 1.642 + * all be folded into one big routine, but splitting them up this way saves 1.643 + * some stack space (the mindist[] and bestdist[] arrays need not coexist) 1.644 + * and may allow some compilers to produce better code by registerizing more 1.645 + * inner-loop variables. 1.646 + */ 1.647 + 1.648 +LOCAL(int) 1.649 +find_nearby_colors (j_decompress_ptr cinfo, int minc0, int minc1, int minc2, 1.650 + JSAMPLE colorlist[]) 1.651 +/* Locate the colormap entries close enough to an update box to be candidates 1.652 + * for the nearest entry to some cell(s) in the update box. The update box 1.653 + * is specified by the center coordinates of its first cell. The number of 1.654 + * candidate colormap entries is returned, and their colormap indexes are 1.655 + * placed in colorlist[]. 1.656 + * This routine uses Heckbert's "locally sorted search" criterion to select 1.657 + * the colors that need further consideration. 1.658 + */ 1.659 +{ 1.660 + int numcolors = cinfo->actual_number_of_colors; 1.661 + int maxc0, maxc1, maxc2; 1.662 + int centerc0, centerc1, centerc2; 1.663 + int i, x, ncolors; 1.664 + INT32 minmaxdist, min_dist, max_dist, tdist; 1.665 + INT32 mindist[MAXNUMCOLORS]; /* min distance to colormap entry i */ 1.666 + 1.667 + /* Compute true coordinates of update box's upper corner and center. 1.668 + * Actually we compute the coordinates of the center of the upper-corner 1.669 + * histogram cell, which are the upper bounds of the volume we care about. 1.670 + * Note that since ">>" rounds down, the "center" values may be closer to 1.671 + * min than to max; hence comparisons to them must be "<=", not "<". 1.672 + */ 1.673 + maxc0 = minc0 + ((1 << BOX_C0_SHIFT) - (1 << C0_SHIFT)); 1.674 + centerc0 = (minc0 + maxc0) >> 1; 1.675 + maxc1 = minc1 + ((1 << BOX_C1_SHIFT) - (1 << C1_SHIFT)); 1.676 + centerc1 = (minc1 + maxc1) >> 1; 1.677 + maxc2 = minc2 + ((1 << BOX_C2_SHIFT) - (1 << C2_SHIFT)); 1.678 + centerc2 = (minc2 + maxc2) >> 1; 1.679 + 1.680 + /* For each color in colormap, find: 1.681 + * 1. its minimum squared-distance to any point in the update box 1.682 + * (zero if color is within update box); 1.683 + * 2. its maximum squared-distance to any point in the update box. 1.684 + * Both of these can be found by considering only the corners of the box. 1.685 + * We save the minimum distance for each color in mindist[]; 1.686 + * only the smallest maximum distance is of interest. 1.687 + */ 1.688 + minmaxdist = 0x7FFFFFFFL; 1.689 + 1.690 + for (i = 0; i < numcolors; i++) { 1.691 + /* We compute the squared-c0-distance term, then add in the other two. */ 1.692 + x = GETJSAMPLE(cinfo->colormap[0][i]); 1.693 + if (x < minc0) { 1.694 + tdist = (x - minc0) * C0_SCALE; 1.695 + min_dist = tdist*tdist; 1.696 + tdist = (x - maxc0) * C0_SCALE; 1.697 + max_dist = tdist*tdist; 1.698 + } else if (x > maxc0) { 1.699 + tdist = (x - maxc0) * C0_SCALE; 1.700 + min_dist = tdist*tdist; 1.701 + tdist = (x - minc0) * C0_SCALE; 1.702 + max_dist = tdist*tdist; 1.703 + } else { 1.704 + /* within cell range so no contribution to min_dist */ 1.705 + min_dist = 0; 1.706 + if (x <= centerc0) { 1.707 + tdist = (x - maxc0) * C0_SCALE; 1.708 + max_dist = tdist*tdist; 1.709 + } else { 1.710 + tdist = (x - minc0) * C0_SCALE; 1.711 + max_dist = tdist*tdist; 1.712 + } 1.713 + } 1.714 + 1.715 + x = GETJSAMPLE(cinfo->colormap[1][i]); 1.716 + if (x < minc1) { 1.717 + tdist = (x - minc1) * C1_SCALE; 1.718 + min_dist += tdist*tdist; 1.719 + tdist = (x - maxc1) * C1_SCALE; 1.720 + max_dist += tdist*tdist; 1.721 + } else if (x > maxc1) { 1.722 + tdist = (x - maxc1) * C1_SCALE; 1.723 + min_dist += tdist*tdist; 1.724 + tdist = (x - minc1) * C1_SCALE; 1.725 + max_dist += tdist*tdist; 1.726 + } else { 1.727 + /* within cell range so no contribution to min_dist */ 1.728 + if (x <= centerc1) { 1.729 + tdist = (x - maxc1) * C1_SCALE; 1.730 + max_dist += tdist*tdist; 1.731 + } else { 1.732 + tdist = (x - minc1) * C1_SCALE; 1.733 + max_dist += tdist*tdist; 1.734 + } 1.735 + } 1.736 + 1.737 + x = GETJSAMPLE(cinfo->colormap[2][i]); 1.738 + if (x < minc2) { 1.739 + tdist = (x - minc2) * C2_SCALE; 1.740 + min_dist += tdist*tdist; 1.741 + tdist = (x - maxc2) * C2_SCALE; 1.742 + max_dist += tdist*tdist; 1.743 + } else if (x > maxc2) { 1.744 + tdist = (x - maxc2) * C2_SCALE; 1.745 + min_dist += tdist*tdist; 1.746 + tdist = (x - minc2) * C2_SCALE; 1.747 + max_dist += tdist*tdist; 1.748 + } else { 1.749 + /* within cell range so no contribution to min_dist */ 1.750 + if (x <= centerc2) { 1.751 + tdist = (x - maxc2) * C2_SCALE; 1.752 + max_dist += tdist*tdist; 1.753 + } else { 1.754 + tdist = (x - minc2) * C2_SCALE; 1.755 + max_dist += tdist*tdist; 1.756 + } 1.757 + } 1.758 + 1.759 + mindist[i] = min_dist; /* save away the results */ 1.760 + if (max_dist < minmaxdist) 1.761 + minmaxdist = max_dist; 1.762 + } 1.763 + 1.764 + /* Now we know that no cell in the update box is more than minmaxdist 1.765 + * away from some colormap entry. Therefore, only colors that are 1.766 + * within minmaxdist of some part of the box need be considered. 1.767 + */ 1.768 + ncolors = 0; 1.769 + for (i = 0; i < numcolors; i++) { 1.770 + if (mindist[i] <= minmaxdist) 1.771 + colorlist[ncolors++] = (JSAMPLE) i; 1.772 + } 1.773 + return ncolors; 1.774 +} 1.775 + 1.776 + 1.777 +LOCAL(void) 1.778 +find_best_colors (j_decompress_ptr cinfo, int minc0, int minc1, int minc2, 1.779 + int numcolors, JSAMPLE colorlist[], JSAMPLE bestcolor[]) 1.780 +/* Find the closest colormap entry for each cell in the update box, 1.781 + * given the list of candidate colors prepared by find_nearby_colors. 1.782 + * Return the indexes of the closest entries in the bestcolor[] array. 1.783 + * This routine uses Thomas' incremental distance calculation method to 1.784 + * find the distance from a colormap entry to successive cells in the box. 1.785 + */ 1.786 +{ 1.787 + int ic0, ic1, ic2; 1.788 + int i, icolor; 1.789 + register INT32 * bptr; /* pointer into bestdist[] array */ 1.790 + JSAMPLE * cptr; /* pointer into bestcolor[] array */ 1.791 + INT32 dist0, dist1; /* initial distance values */ 1.792 + register INT32 dist2; /* current distance in inner loop */ 1.793 + INT32 xx0, xx1; /* distance increments */ 1.794 + register INT32 xx2; 1.795 + INT32 inc0, inc1, inc2; /* initial values for increments */ 1.796 + /* This array holds the distance to the nearest-so-far color for each cell */ 1.797 + INT32 bestdist[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS]; 1.798 + 1.799 + /* Initialize best-distance for each cell of the update box */ 1.800 + bptr = bestdist; 1.801 + for (i = BOX_C0_ELEMS*BOX_C1_ELEMS*BOX_C2_ELEMS-1; i >= 0; i--) 1.802 + *bptr++ = 0x7FFFFFFFL; 1.803 + 1.804 + /* For each color selected by find_nearby_colors, 1.805 + * compute its distance to the center of each cell in the box. 1.806 + * If that's less than best-so-far, update best distance and color number. 1.807 + */ 1.808 + 1.809 + /* Nominal steps between cell centers ("x" in Thomas article) */ 1.810 +#define STEP_C0 ((1 << C0_SHIFT) * C0_SCALE) 1.811 +#define STEP_C1 ((1 << C1_SHIFT) * C1_SCALE) 1.812 +#define STEP_C2 ((1 << C2_SHIFT) * C2_SCALE) 1.813 + 1.814 + for (i = 0; i < numcolors; i++) { 1.815 + icolor = GETJSAMPLE(colorlist[i]); 1.816 + /* Compute (square of) distance from minc0/c1/c2 to this color */ 1.817 + inc0 = (minc0 - GETJSAMPLE(cinfo->colormap[0][icolor])) * C0_SCALE; 1.818 + dist0 = inc0*inc0; 1.819 + inc1 = (minc1 - GETJSAMPLE(cinfo->colormap[1][icolor])) * C1_SCALE; 1.820 + dist0 += inc1*inc1; 1.821 + inc2 = (minc2 - GETJSAMPLE(cinfo->colormap[2][icolor])) * C2_SCALE; 1.822 + dist0 += inc2*inc2; 1.823 + /* Form the initial difference increments */ 1.824 + inc0 = inc0 * (2 * STEP_C0) + STEP_C0 * STEP_C0; 1.825 + inc1 = inc1 * (2 * STEP_C1) + STEP_C1 * STEP_C1; 1.826 + inc2 = inc2 * (2 * STEP_C2) + STEP_C2 * STEP_C2; 1.827 + /* Now loop over all cells in box, updating distance per Thomas method */ 1.828 + bptr = bestdist; 1.829 + cptr = bestcolor; 1.830 + xx0 = inc0; 1.831 + for (ic0 = BOX_C0_ELEMS-1; ic0 >= 0; ic0--) { 1.832 + dist1 = dist0; 1.833 + xx1 = inc1; 1.834 + for (ic1 = BOX_C1_ELEMS-1; ic1 >= 0; ic1--) { 1.835 + dist2 = dist1; 1.836 + xx2 = inc2; 1.837 + for (ic2 = BOX_C2_ELEMS-1; ic2 >= 0; ic2--) { 1.838 + if (dist2 < *bptr) { 1.839 + *bptr = dist2; 1.840 + *cptr = (JSAMPLE) icolor; 1.841 + } 1.842 + dist2 += xx2; 1.843 + xx2 += 2 * STEP_C2 * STEP_C2; 1.844 + bptr++; 1.845 + cptr++; 1.846 + } 1.847 + dist1 += xx1; 1.848 + xx1 += 2 * STEP_C1 * STEP_C1; 1.849 + } 1.850 + dist0 += xx0; 1.851 + xx0 += 2 * STEP_C0 * STEP_C0; 1.852 + } 1.853 + } 1.854 +} 1.855 + 1.856 + 1.857 +LOCAL(void) 1.858 +fill_inverse_cmap (j_decompress_ptr cinfo, int c0, int c1, int c2) 1.859 +/* Fill the inverse-colormap entries in the update box that contains */ 1.860 +/* histogram cell c0/c1/c2. (Only that one cell MUST be filled, but */ 1.861 +/* we can fill as many others as we wish.) */ 1.862 +{ 1.863 + my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 1.864 + hist3d histogram = cquantize->histogram; 1.865 + int minc0, minc1, minc2; /* lower left corner of update box */ 1.866 + int ic0, ic1, ic2; 1.867 + register JSAMPLE * cptr; /* pointer into bestcolor[] array */ 1.868 + register histptr cachep; /* pointer into main cache array */ 1.869 + /* This array lists the candidate colormap indexes. */ 1.870 + JSAMPLE colorlist[MAXNUMCOLORS]; 1.871 + int numcolors; /* number of candidate colors */ 1.872 + /* This array holds the actually closest colormap index for each cell. */ 1.873 + JSAMPLE bestcolor[BOX_C0_ELEMS * BOX_C1_ELEMS * BOX_C2_ELEMS]; 1.874 + 1.875 + /* Convert cell coordinates to update box ID */ 1.876 + c0 >>= BOX_C0_LOG; 1.877 + c1 >>= BOX_C1_LOG; 1.878 + c2 >>= BOX_C2_LOG; 1.879 + 1.880 + /* Compute true coordinates of update box's origin corner. 1.881 + * Actually we compute the coordinates of the center of the corner 1.882 + * histogram cell, which are the lower bounds of the volume we care about. 1.883 + */ 1.884 + minc0 = (c0 << BOX_C0_SHIFT) + ((1 << C0_SHIFT) >> 1); 1.885 + minc1 = (c1 << BOX_C1_SHIFT) + ((1 << C1_SHIFT) >> 1); 1.886 + minc2 = (c2 << BOX_C2_SHIFT) + ((1 << C2_SHIFT) >> 1); 1.887 + 1.888 + /* Determine which colormap entries are close enough to be candidates 1.889 + * for the nearest entry to some cell in the update box. 1.890 + */ 1.891 + numcolors = find_nearby_colors(cinfo, minc0, minc1, minc2, colorlist); 1.892 + 1.893 + /* Determine the actually nearest colors. */ 1.894 + find_best_colors(cinfo, minc0, minc1, minc2, numcolors, colorlist, 1.895 + bestcolor); 1.896 + 1.897 + /* Save the best color numbers (plus 1) in the main cache array */ 1.898 + c0 <<= BOX_C0_LOG; /* convert ID back to base cell indexes */ 1.899 + c1 <<= BOX_C1_LOG; 1.900 + c2 <<= BOX_C2_LOG; 1.901 + cptr = bestcolor; 1.902 + for (ic0 = 0; ic0 < BOX_C0_ELEMS; ic0++) { 1.903 + for (ic1 = 0; ic1 < BOX_C1_ELEMS; ic1++) { 1.904 + cachep = & histogram[c0+ic0][c1+ic1][c2]; 1.905 + for (ic2 = 0; ic2 < BOX_C2_ELEMS; ic2++) { 1.906 + *cachep++ = (histcell) (GETJSAMPLE(*cptr++) + 1); 1.907 + } 1.908 + } 1.909 + } 1.910 +} 1.911 + 1.912 + 1.913 +/* 1.914 + * Map some rows of pixels to the output colormapped representation. 1.915 + */ 1.916 + 1.917 +METHODDEF(void) 1.918 +pass2_no_dither (j_decompress_ptr cinfo, 1.919 + JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows) 1.920 +/* This version performs no dithering */ 1.921 +{ 1.922 + my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 1.923 + hist3d histogram = cquantize->histogram; 1.924 + register JSAMPROW inptr, outptr; 1.925 + register histptr cachep; 1.926 + register int c0, c1, c2; 1.927 + int row; 1.928 + JDIMENSION col; 1.929 + JDIMENSION width = cinfo->output_width; 1.930 + 1.931 + for (row = 0; row < num_rows; row++) { 1.932 + inptr = input_buf[row]; 1.933 + outptr = output_buf[row]; 1.934 + for (col = width; col > 0; col--) { 1.935 + /* get pixel value and index into the cache */ 1.936 + c0 = GETJSAMPLE(*inptr++) >> C0_SHIFT; 1.937 + c1 = GETJSAMPLE(*inptr++) >> C1_SHIFT; 1.938 + c2 = GETJSAMPLE(*inptr++) >> C2_SHIFT; 1.939 + cachep = & histogram[c0][c1][c2]; 1.940 + /* If we have not seen this color before, find nearest colormap entry */ 1.941 + /* and update the cache */ 1.942 + if (*cachep == 0) 1.943 + fill_inverse_cmap(cinfo, c0,c1,c2); 1.944 + /* Now emit the colormap index for this cell */ 1.945 + *outptr++ = (JSAMPLE) (*cachep - 1); 1.946 + } 1.947 + } 1.948 +} 1.949 + 1.950 + 1.951 +METHODDEF(void) 1.952 +pass2_fs_dither (j_decompress_ptr cinfo, 1.953 + JSAMPARRAY input_buf, JSAMPARRAY output_buf, int num_rows) 1.954 +/* This version performs Floyd-Steinberg dithering */ 1.955 +{ 1.956 + my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 1.957 + hist3d histogram = cquantize->histogram; 1.958 + register LOCFSERROR cur0, cur1, cur2; /* current error or pixel value */ 1.959 + LOCFSERROR belowerr0, belowerr1, belowerr2; /* error for pixel below cur */ 1.960 + LOCFSERROR bpreverr0, bpreverr1, bpreverr2; /* error for below/prev col */ 1.961 + register FSERRPTR errorptr; /* => fserrors[] at column before current */ 1.962 + JSAMPROW inptr; /* => current input pixel */ 1.963 + JSAMPROW outptr; /* => current output pixel */ 1.964 + histptr cachep; 1.965 + int dir; /* +1 or -1 depending on direction */ 1.966 + int dir3; /* 3*dir, for advancing inptr & errorptr */ 1.967 + int row; 1.968 + JDIMENSION col; 1.969 + JDIMENSION width = cinfo->output_width; 1.970 + JSAMPLE *range_limit = cinfo->sample_range_limit; 1.971 + int *error_limit = cquantize->error_limiter; 1.972 + JSAMPROW colormap0 = cinfo->colormap[0]; 1.973 + JSAMPROW colormap1 = cinfo->colormap[1]; 1.974 + JSAMPROW colormap2 = cinfo->colormap[2]; 1.975 + SHIFT_TEMPS 1.976 + 1.977 + for (row = 0; row < num_rows; row++) { 1.978 + inptr = input_buf[row]; 1.979 + outptr = output_buf[row]; 1.980 + if (cquantize->on_odd_row) { 1.981 + /* work right to left in this row */ 1.982 + inptr += (width-1) * 3; /* so point to rightmost pixel */ 1.983 + outptr += width-1; 1.984 + dir = -1; 1.985 + dir3 = -3; 1.986 + errorptr = cquantize->fserrors + (width+1)*3; /* => entry after last column */ 1.987 + cquantize->on_odd_row = FALSE; /* flip for next time */ 1.988 + } else { 1.989 + /* work left to right in this row */ 1.990 + dir = 1; 1.991 + dir3 = 3; 1.992 + errorptr = cquantize->fserrors; /* => entry before first real column */ 1.993 + cquantize->on_odd_row = TRUE; /* flip for next time */ 1.994 + } 1.995 + /* Preset error values: no error propagated to first pixel from left */ 1.996 + cur0 = cur1 = cur2 = 0; 1.997 + /* and no error propagated to row below yet */ 1.998 + belowerr0 = belowerr1 = belowerr2 = 0; 1.999 + bpreverr0 = bpreverr1 = bpreverr2 = 0; 1.1000 + 1.1001 + for (col = width; col > 0; col--) { 1.1002 + /* curN holds the error propagated from the previous pixel on the 1.1003 + * current line. Add the error propagated from the previous line 1.1004 + * to form the complete error correction term for this pixel, and 1.1005 + * round the error term (which is expressed * 16) to an integer. 1.1006 + * RIGHT_SHIFT rounds towards minus infinity, so adding 8 is correct 1.1007 + * for either sign of the error value. 1.1008 + * Note: errorptr points to *previous* column's array entry. 1.1009 + */ 1.1010 + cur0 = RIGHT_SHIFT(cur0 + errorptr[dir3+0] + 8, 4); 1.1011 + cur1 = RIGHT_SHIFT(cur1 + errorptr[dir3+1] + 8, 4); 1.1012 + cur2 = RIGHT_SHIFT(cur2 + errorptr[dir3+2] + 8, 4); 1.1013 + /* Limit the error using transfer function set by init_error_limit. 1.1014 + * See comments with init_error_limit for rationale. 1.1015 + */ 1.1016 + cur0 = error_limit[cur0]; 1.1017 + cur1 = error_limit[cur1]; 1.1018 + cur2 = error_limit[cur2]; 1.1019 + /* Form pixel value + error, and range-limit to 0..MAXJSAMPLE. 1.1020 + * The maximum error is +- MAXJSAMPLE (or less with error limiting); 1.1021 + * this sets the required size of the range_limit array. 1.1022 + */ 1.1023 + cur0 += GETJSAMPLE(inptr[0]); 1.1024 + cur1 += GETJSAMPLE(inptr[1]); 1.1025 + cur2 += GETJSAMPLE(inptr[2]); 1.1026 + cur0 = GETJSAMPLE(range_limit[cur0]); 1.1027 + cur1 = GETJSAMPLE(range_limit[cur1]); 1.1028 + cur2 = GETJSAMPLE(range_limit[cur2]); 1.1029 + /* Index into the cache with adjusted pixel value */ 1.1030 + cachep = & histogram[cur0>>C0_SHIFT][cur1>>C1_SHIFT][cur2>>C2_SHIFT]; 1.1031 + /* If we have not seen this color before, find nearest colormap */ 1.1032 + /* entry and update the cache */ 1.1033 + if (*cachep == 0) 1.1034 + fill_inverse_cmap(cinfo, cur0>>C0_SHIFT,cur1>>C1_SHIFT,cur2>>C2_SHIFT); 1.1035 + /* Now emit the colormap index for this cell */ 1.1036 + { register int pixcode = *cachep - 1; 1.1037 + *outptr = (JSAMPLE) pixcode; 1.1038 + /* Compute representation error for this pixel */ 1.1039 + cur0 -= GETJSAMPLE(colormap0[pixcode]); 1.1040 + cur1 -= GETJSAMPLE(colormap1[pixcode]); 1.1041 + cur2 -= GETJSAMPLE(colormap2[pixcode]); 1.1042 + } 1.1043 + /* Compute error fractions to be propagated to adjacent pixels. 1.1044 + * Add these into the running sums, and simultaneously shift the 1.1045 + * next-line error sums left by 1 column. 1.1046 + */ 1.1047 + { register LOCFSERROR bnexterr, delta; 1.1048 + 1.1049 + bnexterr = cur0; /* Process component 0 */ 1.1050 + delta = cur0 * 2; 1.1051 + cur0 += delta; /* form error * 3 */ 1.1052 + errorptr[0] = (FSERROR) (bpreverr0 + cur0); 1.1053 + cur0 += delta; /* form error * 5 */ 1.1054 + bpreverr0 = belowerr0 + cur0; 1.1055 + belowerr0 = bnexterr; 1.1056 + cur0 += delta; /* form error * 7 */ 1.1057 + bnexterr = cur1; /* Process component 1 */ 1.1058 + delta = cur1 * 2; 1.1059 + cur1 += delta; /* form error * 3 */ 1.1060 + errorptr[1] = (FSERROR) (bpreverr1 + cur1); 1.1061 + cur1 += delta; /* form error * 5 */ 1.1062 + bpreverr1 = belowerr1 + cur1; 1.1063 + belowerr1 = bnexterr; 1.1064 + cur1 += delta; /* form error * 7 */ 1.1065 + bnexterr = cur2; /* Process component 2 */ 1.1066 + delta = cur2 * 2; 1.1067 + cur2 += delta; /* form error * 3 */ 1.1068 + errorptr[2] = (FSERROR) (bpreverr2 + cur2); 1.1069 + cur2 += delta; /* form error * 5 */ 1.1070 + bpreverr2 = belowerr2 + cur2; 1.1071 + belowerr2 = bnexterr; 1.1072 + cur2 += delta; /* form error * 7 */ 1.1073 + } 1.1074 + /* At this point curN contains the 7/16 error value to be propagated 1.1075 + * to the next pixel on the current line, and all the errors for the 1.1076 + * next line have been shifted over. We are therefore ready to move on. 1.1077 + */ 1.1078 + inptr += dir3; /* Advance pixel pointers to next column */ 1.1079 + outptr += dir; 1.1080 + errorptr += dir3; /* advance errorptr to current column */ 1.1081 + } 1.1082 + /* Post-loop cleanup: we must unload the final error values into the 1.1083 + * final fserrors[] entry. Note we need not unload belowerrN because 1.1084 + * it is for the dummy column before or after the actual array. 1.1085 + */ 1.1086 + errorptr[0] = (FSERROR) bpreverr0; /* unload prev errs into array */ 1.1087 + errorptr[1] = (FSERROR) bpreverr1; 1.1088 + errorptr[2] = (FSERROR) bpreverr2; 1.1089 + } 1.1090 +} 1.1091 + 1.1092 + 1.1093 +/* 1.1094 + * Initialize the error-limiting transfer function (lookup table). 1.1095 + * The raw F-S error computation can potentially compute error values of up to 1.1096 + * +- MAXJSAMPLE. But we want the maximum correction applied to a pixel to be 1.1097 + * much less, otherwise obviously wrong pixels will be created. (Typical 1.1098 + * effects include weird fringes at color-area boundaries, isolated bright 1.1099 + * pixels in a dark area, etc.) The standard advice for avoiding this problem 1.1100 + * is to ensure that the "corners" of the color cube are allocated as output 1.1101 + * colors; then repeated errors in the same direction cannot cause cascading 1.1102 + * error buildup. However, that only prevents the error from getting 1.1103 + * completely out of hand; Aaron Giles reports that error limiting improves 1.1104 + * the results even with corner colors allocated. 1.1105 + * A simple clamping of the error values to about +- MAXJSAMPLE/8 works pretty 1.1106 + * well, but the smoother transfer function used below is even better. Thanks 1.1107 + * to Aaron Giles for this idea. 1.1108 + */ 1.1109 + 1.1110 +LOCAL(void) 1.1111 +init_error_limit (j_decompress_ptr cinfo) 1.1112 +/* Allocate and fill in the error_limiter table */ 1.1113 +{ 1.1114 + my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 1.1115 + int * table; 1.1116 + int in, out; 1.1117 + 1.1118 + table = (int *) (*cinfo->mem->alloc_small) 1.1119 + ((j_common_ptr) cinfo, JPOOL_IMAGE, (MAXJSAMPLE*2+1) * SIZEOF(int)); 1.1120 + table += MAXJSAMPLE; /* so can index -MAXJSAMPLE .. +MAXJSAMPLE */ 1.1121 + cquantize->error_limiter = table; 1.1122 + 1.1123 +#define STEPSIZE ((MAXJSAMPLE+1)/16) 1.1124 + /* Map errors 1:1 up to +- MAXJSAMPLE/16 */ 1.1125 + out = 0; 1.1126 + for (in = 0; in < STEPSIZE; in++, out++) { 1.1127 + table[in] = out; table[-in] = -out; 1.1128 + } 1.1129 + /* Map errors 1:2 up to +- 3*MAXJSAMPLE/16 */ 1.1130 + for (; in < STEPSIZE*3; in++, out += (in&1) ? 0 : 1) { 1.1131 + table[in] = out; table[-in] = -out; 1.1132 + } 1.1133 + /* Clamp the rest to final out value (which is (MAXJSAMPLE+1)/8) */ 1.1134 + for (; in <= MAXJSAMPLE; in++) { 1.1135 + table[in] = out; table[-in] = -out; 1.1136 + } 1.1137 +#undef STEPSIZE 1.1138 +} 1.1139 + 1.1140 + 1.1141 +/* 1.1142 + * Finish up at the end of each pass. 1.1143 + */ 1.1144 + 1.1145 +METHODDEF(void) 1.1146 +finish_pass1 (j_decompress_ptr cinfo) 1.1147 +{ 1.1148 + my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 1.1149 + 1.1150 + /* Select the representative colors and fill in cinfo->colormap */ 1.1151 + cinfo->colormap = cquantize->sv_colormap; 1.1152 + select_colors(cinfo, cquantize->desired); 1.1153 + /* Force next pass to zero the color index table */ 1.1154 + cquantize->needs_zeroed = TRUE; 1.1155 +} 1.1156 + 1.1157 + 1.1158 +METHODDEF(void) 1.1159 +finish_pass2 (j_decompress_ptr cinfo) 1.1160 +{ 1.1161 + /* no work */ 1.1162 +} 1.1163 + 1.1164 + 1.1165 +/* 1.1166 + * Initialize for each processing pass. 1.1167 + */ 1.1168 + 1.1169 +METHODDEF(void) 1.1170 +start_pass_2_quant (j_decompress_ptr cinfo, boolean is_pre_scan) 1.1171 +{ 1.1172 + my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 1.1173 + hist3d histogram = cquantize->histogram; 1.1174 + int i; 1.1175 + 1.1176 + /* Only F-S dithering or no dithering is supported. */ 1.1177 + /* If user asks for ordered dither, give him F-S. */ 1.1178 + if (cinfo->dither_mode != JDITHER_NONE) 1.1179 + cinfo->dither_mode = JDITHER_FS; 1.1180 + 1.1181 + if (is_pre_scan) { 1.1182 + /* Set up method pointers */ 1.1183 + cquantize->pub.color_quantize = prescan_quantize; 1.1184 + cquantize->pub.finish_pass = finish_pass1; 1.1185 + cquantize->needs_zeroed = TRUE; /* Always zero histogram */ 1.1186 + } else { 1.1187 + /* Set up method pointers */ 1.1188 + if (cinfo->dither_mode == JDITHER_FS) 1.1189 + cquantize->pub.color_quantize = pass2_fs_dither; 1.1190 + else 1.1191 + cquantize->pub.color_quantize = pass2_no_dither; 1.1192 + cquantize->pub.finish_pass = finish_pass2; 1.1193 + 1.1194 + /* Make sure color count is acceptable */ 1.1195 + i = cinfo->actual_number_of_colors; 1.1196 + if (i < 1) 1.1197 + ERREXIT1(cinfo, JERR_QUANT_FEW_COLORS, 1); 1.1198 + if (i > MAXNUMCOLORS) 1.1199 + ERREXIT1(cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS); 1.1200 + 1.1201 + if (cinfo->dither_mode == JDITHER_FS) { 1.1202 + size_t arraysize = (size_t) ((cinfo->output_width + 2) * 1.1203 + (3 * SIZEOF(FSERROR))); 1.1204 + /* Allocate Floyd-Steinberg workspace if we didn't already. */ 1.1205 + if (cquantize->fserrors == NULL) 1.1206 + cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large) 1.1207 + ((j_common_ptr) cinfo, JPOOL_IMAGE, arraysize); 1.1208 + /* Initialize the propagated errors to zero. */ 1.1209 + jzero_far((void FAR *) cquantize->fserrors, arraysize); 1.1210 + /* Make the error-limit table if we didn't already. */ 1.1211 + if (cquantize->error_limiter == NULL) 1.1212 + init_error_limit(cinfo); 1.1213 + cquantize->on_odd_row = FALSE; 1.1214 + } 1.1215 + 1.1216 + } 1.1217 + /* Zero the histogram or inverse color map, if necessary */ 1.1218 + if (cquantize->needs_zeroed) { 1.1219 + for (i = 0; i < HIST_C0_ELEMS; i++) { 1.1220 + jzero_far((void FAR *) histogram[i], 1.1221 + HIST_C1_ELEMS*HIST_C2_ELEMS * SIZEOF(histcell)); 1.1222 + } 1.1223 + cquantize->needs_zeroed = FALSE; 1.1224 + } 1.1225 +} 1.1226 + 1.1227 + 1.1228 +/* 1.1229 + * Switch to a new external colormap between output passes. 1.1230 + */ 1.1231 + 1.1232 +METHODDEF(void) 1.1233 +new_color_map_2_quant (j_decompress_ptr cinfo) 1.1234 +{ 1.1235 + my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize; 1.1236 + 1.1237 + /* Reset the inverse color map */ 1.1238 + cquantize->needs_zeroed = TRUE; 1.1239 +} 1.1240 + 1.1241 + 1.1242 +/* 1.1243 + * Module initialization routine for 2-pass color quantization. 1.1244 + */ 1.1245 + 1.1246 +GLOBAL(void) 1.1247 +jinit_2pass_quantizer (j_decompress_ptr cinfo) 1.1248 +{ 1.1249 + my_cquantize_ptr cquantize; 1.1250 + int i; 1.1251 + 1.1252 + cquantize = (my_cquantize_ptr) 1.1253 + (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 1.1254 + SIZEOF(my_cquantizer)); 1.1255 + cinfo->cquantize = (struct jpeg_color_quantizer *) cquantize; 1.1256 + cquantize->pub.start_pass = start_pass_2_quant; 1.1257 + cquantize->pub.new_color_map = new_color_map_2_quant; 1.1258 + cquantize->fserrors = NULL; /* flag optional arrays not allocated */ 1.1259 + cquantize->error_limiter = NULL; 1.1260 + 1.1261 + /* Make sure jdmaster didn't give me a case I can't handle */ 1.1262 + if (cinfo->out_color_components != 3) 1.1263 + ERREXIT(cinfo, JERR_NOTIMPL); 1.1264 + 1.1265 + /* Allocate the histogram/inverse colormap storage */ 1.1266 + cquantize->histogram = (hist3d) (*cinfo->mem->alloc_small) 1.1267 + ((j_common_ptr) cinfo, JPOOL_IMAGE, HIST_C0_ELEMS * SIZEOF(hist2d)); 1.1268 + for (i = 0; i < HIST_C0_ELEMS; i++) { 1.1269 + cquantize->histogram[i] = (hist2d) (*cinfo->mem->alloc_large) 1.1270 + ((j_common_ptr) cinfo, JPOOL_IMAGE, 1.1271 + HIST_C1_ELEMS*HIST_C2_ELEMS * SIZEOF(histcell)); 1.1272 + } 1.1273 + cquantize->needs_zeroed = TRUE; /* histogram is garbage now */ 1.1274 + 1.1275 + /* Allocate storage for the completed colormap, if required. 1.1276 + * We do this now since it is FAR storage and may affect 1.1277 + * the memory manager's space calculations. 1.1278 + */ 1.1279 + if (cinfo->enable_2pass_quant) { 1.1280 + /* Make sure color count is acceptable */ 1.1281 + int desired = cinfo->desired_number_of_colors; 1.1282 + /* Lower bound on # of colors ... somewhat arbitrary as long as > 0 */ 1.1283 + if (desired < 8) 1.1284 + ERREXIT1(cinfo, JERR_QUANT_FEW_COLORS, 8); 1.1285 + /* Make sure colormap indexes can be represented by JSAMPLEs */ 1.1286 + if (desired > MAXNUMCOLORS) 1.1287 + ERREXIT1(cinfo, JERR_QUANT_MANY_COLORS, MAXNUMCOLORS); 1.1288 + cquantize->sv_colormap = (*cinfo->mem->alloc_sarray) 1.1289 + ((j_common_ptr) cinfo,JPOOL_IMAGE, (JDIMENSION) desired, (JDIMENSION) 3); 1.1290 + cquantize->desired = desired; 1.1291 + } else 1.1292 + cquantize->sv_colormap = NULL; 1.1293 + 1.1294 + /* Only F-S dithering or no dithering is supported. */ 1.1295 + /* If user asks for ordered dither, give him F-S. */ 1.1296 + if (cinfo->dither_mode != JDITHER_NONE) 1.1297 + cinfo->dither_mode = JDITHER_FS; 1.1298 + 1.1299 + /* Allocate Floyd-Steinberg workspace if necessary. 1.1300 + * This isn't really needed until pass 2, but again it is FAR storage. 1.1301 + * Although we will cope with a later change in dither_mode, 1.1302 + * we do not promise to honor max_memory_to_use if dither_mode changes. 1.1303 + */ 1.1304 + if (cinfo->dither_mode == JDITHER_FS) { 1.1305 + cquantize->fserrors = (FSERRPTR) (*cinfo->mem->alloc_large) 1.1306 + ((j_common_ptr) cinfo, JPOOL_IMAGE, 1.1307 + (size_t) ((cinfo->output_width + 2) * (3 * SIZEOF(FSERROR)))); 1.1308 + /* Might as well create the error-limiting table too. */ 1.1309 + init_error_limit(cinfo); 1.1310 + } 1.1311 +} 1.1312 + 1.1313 +#endif /* QUANT_2PASS_SUPPORTED */