Coverage Report

Created: 2024-01-20 12:28

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