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