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