/[pcsx2_0.9.7]/trunk/3rdparty/wxWidgets/src/common/quantize.cpp
ViewVC logotype

Contents of /trunk/3rdparty/wxWidgets/src/common/quantize.cpp

Parent Directory Parent Directory | Revision Log Revision Log


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

  ViewVC Help
Powered by ViewVC 1.1.22