gimpimage-convert.c 131 KB
Newer Older
Elliot Lee's avatar
Elliot Lee committed
1
2
/* The GIMP -- an image manipulation program
 * Copyright (C) 1995 Spencer Kimball and Peter Mattis
3
 * Copyright (C) 1997-2004 Adam D. Moss <adam@gimp.org>
Elliot Lee's avatar
Elliot Lee committed
4
5
6
7
8
9
10
11
12
13
14
15
16
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
17
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
Elliot Lee's avatar
Elliot Lee committed
18
19
20
 */

/*
21
22
23
24
 * 2004-12-12 - Use a slower but much nicer technique for finding the
 *  two best colours to dither between when using fixed/positional
 *  dither methods.  Makes positional dither much less lame.  [adam@gimp.org]
 *
25
26
27
28
29
30
31
32
33
34
 * 2002-02-10 - Quantizer version 3.0 (the rest of the commit started
 *  a year ago -- whoops).  Divide colours within CIE L*a*b* space using
 *  CPercep module (cpercep.[ch]), colour-match and dither likewise,
 *  change the underlying box selection criteria and division point
 *  logic, bump luminance precision upwards, etc.etc.  Generally
 *  chooses a much richer colour set, especially for low numbers of
 *  colours.  n.b.: Less luminance-sloppy in straight remapping which is
 *  good for colour but a bit worse for high-frequency detail (that's
 *  partly what fs-dithering is for -- use it).  [adam@gimp.org]
 *
35
36
37
38
39
40
41
42
 * 2001-03-25 - Define accessor function/macro for histogram reads and
 *  writes.  This slows us down a little because we avoid some of the
 *  dirty tricks we used when we knew that the histogram was a straight
 *  3d array, so I've recovered some of the speed loss by implementing
 *  a 5d accessor function with good locality of reference.  This change
 *  is the first step towards quantizing in a more interesting colourspace
 *  than frumpy old RGB.  [Adam]
 *
43
44
 * 2000/01/30 - Use palette_selector instead of option_menu for custom
 *  palette. Use libgimp callback functions.  [Sven]
45
 *
46
47
 * 99/09/01 - Created a low-bleed FS-dither option.  [Adam]
 *
48
49
50
51
52
 * 99/08/29 - Deterministic colour dithering to arbitrary palettes.
 *  Ideal for animations that are going to be delta-optimized or simply
 *  don't want to look 'busy' in static areas.  Also a bunch of bugfixes
 *  and tweaks.  [Adam]
 *
53
54
55
56
 * 99/08/28 - Deterministic alpha dithering over layers, reduced bleeding
 *  of transparent values into opaque values, added optional stage to
 *  remove duplicate or unused colour entries from final colourmap. [Adam]
 *
57
58
59
60
61
62
63
64
65
 * 99/02/24 - Many revisions to the box-cut quantizer used in RGB->INDEXED
 *  conversion.  Box to be cut is chosen on the basis of posessing an axis
 *  with the largest sum of weighted perceptible error, rather than based on
 *  volume or population.  The box is split along this axis rather than its
 *  longest axis, at the point of error mean rather than simply at its centre.
 *  Error-limiting in the F-S dither has been disabled - it may become optional
 *  again later.  If you're convinced that you have an image where the old
 *  dither looks better, let me know.  [Adam]
 *
66
67
 * 99/01/10 - Hourglass... [Adam]
 *
68
 * 98/07/25 - Convert-to-indexed now remembers the last invocation's
69
 *  settings.  Also, GRAY->INDEXED is more flexible.  [Adam]
70
 *
71
72
73
74
75
76
 * 98/07/05 - Sucked the warning about quantizing to too many colours into
 *  a text widget embedded in the dialog, improved intelligence of dialog
 *  to default 'custom palette' selection to 'Web' if available, and
 *  in this case not bother to present the native WWW-palette radio
 *  button.  [Adam]
 *
77
 * 98/04/13 - avoid a division by zero when converting an empty gray-scale
78
 *  image (who would like to do such a thing anyway??)  [Sven ]
79
 *
80
 * 98/03/23 - fixed a longstanding fencepost - hopefully the *right*
81
 *  way, *again*.  [Adam]
82
 *
83
84
85
 * 97/11/14 - added a proper pdb interface and support for dithering
 *  to custom palettes (based on a patch by Eric Hernes) [Yosh]
 *
86
87
88
89
90
91
92
 * 97/11/04 - fixed the accidental use of the colour-counting case
 *  when palette_type is WEB or MONO. [Adam]
 *
 * 97/10/25 - colour-counting implemented (could use some hashing, but
 *  performance actually seems okay) - now RGB->INDEXED conversion isn't
 *  destructive if it doesn't have to be. [Adam]
 *
Elliot Lee's avatar
Elliot Lee committed
93
94
95
96
97
98
99
100
 * 97/10/14 - fixed divide-by-zero when converting a completely transparent
 *  RGB image to indexed. [Adam]
 *
 * 97/07/01 - started todo/revision log.  Put code back in to
 *  eliminate full-alpha pixels from RGB histogram.
 *  [Adam D. Moss - adam@gimp.org]
 */

101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
  /* TODO for Convert:
   *
   * . Tweak, tweak, tweak.  Old RGB code was tuned muchly.
   *
   * . Re-enable Heckbert locality for matching, benchmark it
   *
   * . Try faster fixed-point sRGB<->L*a*b* pixel conversion (see cpercep.c)
   *
   * . Use palette of another open INDEXED image?
   *
   * . Do error-splitting trick for GREY->INDEXED (hardly worth it)
   */

  /* CODE READABILITY BUGS:
   *
   * . Most uses of variants of the R,G,B variable naming convention
   *   are referring to L*a*b* co-ordinates, not RGB co-ordinates!
   *
   * . Each said variable is usually one of the following, but it is
   *   rarely clear which one:
   *     - (assumed sRGB) raw non-linear 8-bit RGB co-ordinates
   *     - 'full'-precision (unshifted) 8-bit L*a*b* co-ordinates
   *     - box-space (reduced-precision shifted L*a*b*) co-ordinates
   */

126
#include "config.h"
Elliot Lee's avatar
Elliot Lee committed
127
128

#include <stdlib.h>
129
#include <stdio.h>
Elliot Lee's avatar
Elliot Lee committed
130
#include <string.h>
131

132
#include <glib-object.h>
Sven Neumann's avatar
Sven Neumann committed
133

134
#include "libgimpcolor/gimpcolor.h"
135
#include "libgimpmath/gimpmath.h"
136

Michael Natterer's avatar
Michael Natterer committed
137
#include "core-types.h"
Sven Neumann's avatar
Sven Neumann committed
138

Michael Natterer's avatar
Michael Natterer committed
139
140
141
#include "base/pixel-region.h"
#include "base/tile-manager.h"

142
#include "gimp.h"
143
#include "gimpdrawable.h"
144
#include "gimpdrawable-convert.h"
145
#include "gimpimage.h"
146
#include "gimpimage-colormap.h"
147
#include "gimpimage-undo.h"
148
#include "gimpimage-undo-push.h"
149
#include "gimplist.h"
150
#include "gimplayer.h"
151
#include "gimplayer-floating-sel.h"
152
#include "gimppalette.h"
153
#include "gimpprogress.h"
Michael Natterer's avatar
Michael Natterer committed
154

155
156
157
158
#include "cpercep.h"
#include "gimpimage-convert-fsdither.h"
#include "gimpimage-convert-data.h"
#include "gimpimage-convert.h"
159

160
#include "gimp-intl.h"
161

162

163
164
165
166
#ifndef DM_RANGE
# define DM_RANGE 63
#endif

167
168
/* basic memory/quality tradeoff */
#define PRECISION_R 8
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#define PRECISION_G 6
#define PRECISION_B 6

#define HIST_R_ELEMS (1<<PRECISION_R)
#define HIST_G_ELEMS (1<<PRECISION_G)
#define HIST_B_ELEMS (1<<PRECISION_B)

#define MR (HIST_G_ELEMS*HIST_B_ELEMS)
#define MG HIST_B_ELEMS

#define BITS_IN_SAMPLE 8

#define R_SHIFT  (BITS_IN_SAMPLE-PRECISION_R)
#define G_SHIFT  (BITS_IN_SAMPLE-PRECISION_G)
#define B_SHIFT  (BITS_IN_SAMPLE-PRECISION_B)

185
186
187
188
189
190
191
/* we've stretched our non-cubic L*a*b* volume to touch the
   faces of the logical cube we've allocated for it, so re-scale
   again in inverse proportion to get back to linear proportions.
*/
#define R_SCALE 13              /*  scale R (L*) distances by this much  */
#define G_SCALE 24              /*  scale G (a*) distances by this much  */
#define B_SCALE 26              /*  and B (b*) by this much              */
192
193


Elliot Lee's avatar
Elliot Lee committed
194
195
196
typedef struct _Color Color;
typedef struct _QuantizeObj QuantizeObj;
typedef void (* Pass1_Func) (QuantizeObj *);
197
typedef void (* Pass2i_Func) (QuantizeObj *);
198
typedef void (* Pass2_Func) (QuantizeObj *, GimpLayer *, TileManager *);
Elliot Lee's avatar
Elliot Lee committed
199
200
typedef void (* Cleanup_Func) (QuantizeObj *);
typedef unsigned long ColorFreq;
Manish Singh's avatar
Manish Singh committed
201
typedef ColorFreq *CFHistogram;
Elliot Lee's avatar
Elliot Lee committed
202

203
typedef enum {AXIS_UNDEF, AXIS_RED, AXIS_BLUE, AXIS_GREEN} axisType;
204

205
typedef double etype;
206
207


208
209
210
211
212
213
214
215
216
217
218
219
/*
  We provide two different histogram access interfaces.  HIST_LIN()
  accesses the histogram in histogram-native space, taking absolute
  histogram co-ordinates.  HIST_RGB() accesses the histogram in RGB
  space.  This latter takes unsigned 8-bit co-ordinates, internally
  converts those co-ordinates to histogram-native space and returns
  the access pointer to the corresponding histogram cell.

  Using these two interfaces we can import RGB data into a more
  interesting space and efficiently work in the latter space until
  it is time to output the quantized values in RGB again.  For
  this final conversion we implement the function lin_to_rgb().
220

221
222
223
224
225
  We effectively pull our three-dimensional space into five dimensions
  such that the most-entropic bits lay in the lowest bits of the resulting
  array index.  This gives significantly better locality of reference
  and hence a small speedup despite the extra work involved in calculating
  the index.
226

227
228
229
230
231
232
233
  Why not six dimensions?  The expansion of dimensionality is good for random
  access such as histogram population and the query pattern typical of
  dithering but we have some code which iterates in a scanning manner, for
  which the expansion is suboptimal.  The compromise is to leave the B
  dimension unmolested in the lower-order bits of the index, since this is
  the dimension most commonly iterated through in the inner loop of the
  scans.
234

235
  --adam
236

237
  RhGhRlGlB
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
*/
#define VOL_GBITS  (PRECISION_G)
#define VOL_BBITS  (PRECISION_B)
#define VOL_RBITS  (PRECISION_R)
#define VOL_GBITSh (VOL_GBITS - 3)
#define VOL_GBITSl (VOL_GBITS - VOL_GBITSh)
#define VOL_BBITSh (VOL_BBITS - 4)
#define VOL_BBITSl (VOL_BBITS - VOL_BBITSh)
#define VOL_RBITSh (VOL_RBITS - 3)
#define VOL_RBITSl (VOL_RBITS - VOL_RBITSh)
#define VOL_GMASKh (((1<<VOL_GBITSh)-1) << VOL_GBITSl)
#define VOL_GMASKl ((1<<VOL_GBITSl)-1)
#define VOL_BMASKh (((1<<VOL_BBITSh)-1) << VOL_BBITSl)
#define VOL_BMASKl ((1<<VOL_BBITSl)-1)
#define VOL_RMASKh (((1<<VOL_RBITSh)-1) << VOL_RBITSl)
#define VOL_RMASKl ((1<<VOL_RBITSl)-1)
/* The 5d compromise thing. */
#define REF_FUNC(r,g,b) \
( \
 (((r) & VOL_RMASKh) << (VOL_BBITS + VOL_GBITS)) | \
 (((r) & VOL_RMASKl) << (VOL_GBITSl + VOL_BBITS)) | \
 (((g) & VOL_GMASKh) << (VOL_RBITSl + VOL_BBITS)) | \
 (((g) & VOL_GMASKl) << (VOL_BBITS)) | \
 (b) \
)
/* The full-on 6d thing. */
/*
#define REF_FUNC(r,g,b) \
( \
 (((r) & VOL_RMASKh) << (VOL_BBITS + VOL_GBITS)) | \
 (((r) & VOL_RMASKl) << (VOL_GBITSl + VOL_BBITSl)) | \
 (((g) & VOL_GMASKh) << (VOL_RBITSl + VOL_BBITS)) | \
 (((g) & VOL_GMASKl) << (VOL_BBITSl)) | \
 (((b) & VOL_BMASKh) << (VOL_RBITSl + VOL_GBITSl)) | \
 ((b) & VOL_BMASKl) \
)
*/
/* The boring old 3d thing. */
/*
#define REF_FUNC(r,g,b) (((r)<<(PRECISION_G+PRECISION_B)) | ((g)<<(PRECISION_B)) | (b))
*/

/* You even get to choose whether you want the accessor function
   implemented as a macro or an inline function.  Don't say I never
   give you anything. */
/*
284
#define HIST_LIN(hist_ptr,r,g,b) (&(hist_ptr)[REF_FUNC((r),(g),(b))])
285
*/
286
static inline
287
ColorFreq* HIST_LIN(ColorFreq *hist_ptr,
288
                    const int r, const int g, const int b)
289
290
{
  return (&(hist_ptr)[
291
                      REF_FUNC(r,g,b)
292
293
294
295
  ]);
}


296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
#define LOWA (-86.181F)
#define LOWB (-107.858F)
#define HIGHA (98.237F)
#define HIGHB (94.480F)

#if 1
#define LRAT (2.55F)
#define ARAT (255.0F / (HIGHA - LOWA))
#define BRAT (255.0F / (HIGHB - LOWB))
#else
#define LRAT (1.0F)
#define ARAT (1.0F)
#define BRAT (1.0F)
#endif

static inline
void rgb_to_unshifted_lin(const unsigned char r,
313
314
315
                          const unsigned char g,
                          const unsigned char b,
                          int *hr, int *hg, int *hb)
316
317
318
319
{
  double sL, sa, sb;
  int or, og, ob;

Adam D. Moss's avatar
Adam D. Moss committed
320
  cpercep_rgb_to_space(r,g,b, &sL, &sa, &sb);
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341

  /* fprintf(stderr, " %d-%d-%d -> %0.3f,%0.3f,%0.3f ", r, g, b, sL, sa, sb);*/

  or = RINT(sL * LRAT);
  og = RINT((sa - LOWA) * ARAT);
  ob = RINT((sb - LOWB) * BRAT);

  /*  fprintf(stderr, " %d-%d-%d ", or, og, ob); */

#if 0
  if (or < 0 || or > 255)
    fprintf(stderr, " \007R%d ", or);
  if (og < 0 || og > 255)
    fprintf(stderr, " \007G%d ", og);
  if (ob < 0 || ob > 255)
    fprintf(stderr, " \007B%d ", ob);
#endif

  *hr = CLAMP(or, 0, 255);
  *hg = CLAMP(og, 0, 255);
  *hb = CLAMP(ob, 0, 255);
342

343
344
345
346
347
348
  /*  fprintf(stderr, " %d:%d:%d ", *hr, *hg, *hb); */
}


static inline
void rgb_to_lin(const unsigned char r,
349
350
351
                const unsigned char g,
                const unsigned char b,
                int *hr, int *hg, int *hb)
352
353
354
355
356
357
358
359
360
361
362
363
364
{
  int or, og, ob;

  /*
  double sL, sa, sb;
  {
    double low_l = 999.0, low_a = 999.9, low_b = 999.0;
    double high_l = -999.0, high_a = -999.0, high_b = -999.0;

    int r,g,b;

    for (r=0; r<256; r++)
      for (g=0; g<256; g++)
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
        for (b=0; b<256; b++)
          {
            cpercep_rgb_to_space(r,g,b, &sL, &sa, &sb);

            if (sL > high_l)
              high_l = sL;
            if (sL < low_l)
              low_l = sL;
            if (sa > high_a)
              high_a = sa;
            if (sa < low_a)
              low_a = sa;
            if (sb > high_b)
              high_b = sb;
            if (sb < low_b)
              low_b = sb;
          }
382

383
    fprintf(stderr, " [L: %0.3f -> %0.3f / a: %0.3f -> %0.3f / b: %0.3f -> %0.3f]\t", low_l, high_l, low_a, high_a, low_b, high_b);
384

385
386
387
388
389
    exit(-1);
  }
  */

  rgb_to_unshifted_lin (r,g,b,
390
                        &or, &og, &ob);
391
392
393

#if 0
#define RSDF(r) ((r) >= ((HIST_R_ELEMS-1) << R_SHIFT) ? HIST_R_ELEMS-1 : \
394
                 ((r) + ((1<<R_SHIFT)>>1) ) >> R_SHIFT)
395
#define GSDF(g) ((g) >= ((HIST_G_ELEMS-1) << G_SHIFT) ? HIST_G_ELEMS-1 : \
396
                 ((g) + ((1<<G_SHIFT)>>1) ) >> G_SHIFT)
397
#define BSDF(b) ((b) >= ((HIST_B_ELEMS-1) << B_SHIFT) ? HIST_B_ELEMS-1 : \
398
                 ((b) + ((1<<B_SHIFT)>>1) ) >> B_SHIFT)
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
#else
#define RSDF(r) ((r) >> R_SHIFT)
#define GSDF(g) ((g) >> G_SHIFT)
#define BSDF(b) ((b) >> B_SHIFT)
#endif

  or = RSDF(or);
  og = GSDF(og);
  ob = BSDF(ob);

  *hr = or;
  *hg = og;
  *hb = ob;
}


static inline
ColorFreq* HIST_RGB(ColorFreq *hist_ptr,
417
                    const int r, const int g, const int b)
418
419
420
421
{
  int hr, hg, hb;

  rgb_to_lin(r, g, b,
422
             &hr, &hg, &hb);
423
424
425
426
427
428
429

  return (HIST_LIN(hist_ptr,hr,hg,hb));
}


static inline
void lin_to_rgb(const double hr, const double hg, const double hb,
430
431
432
                unsigned char *r,
                unsigned char *g,
                unsigned char *b)
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
{
  double sr,sg,sb;
  double ir,ig,ib;

  /*  fprintf(stderr, "%d.%d.%d ", hr,hg,hb); */

#if 0
  ir = (hr * ((double) (1 << R_SHIFT))) + (((double)(1<<R_SHIFT))*0.5);
  ig = (hg * ((double) (1 << G_SHIFT))) + (((double)(1<<G_SHIFT))*0.5);
  ib = (hb * ((double) (1 << B_SHIFT))) + (((double)(1<<B_SHIFT))*0.5);
#else
  /* w/ artificial widening of dynamic range */
  ir = ((double)(hr)) * 255.0F / (double)(HIST_R_ELEMS-1);
  ig = ((double)(hg)) * 255.0F / (double)(HIST_G_ELEMS-1);
  ib = ((double)(hb)) * 255.0F / (double)(HIST_B_ELEMS-1);
#endif

  ir = ir / LRAT;
  ig = (ig / ARAT) + LOWA;
  ib = (ib / BRAT) + LOWB;

  /*  fprintf(stderr, "%0.1f,%0.1f,%0.1f ", ir,ig,ib); */

Adam D. Moss's avatar
Adam D. Moss committed
456
  cpercep_space_to_rgb(ir, ig, ib,
457
                       &sr, &sg, &sb);
458
459
460
461
462
463
464
465
466
467

  *r = RINT(CLAMP(sr, 0.0F, 255.0F));
  *g = RINT(CLAMP(sg, 0.0F, 255.0F));
  *b = RINT(CLAMP(sb, 0.0F, 255.0F));

  /*  fprintf(stderr, "%d,%d,%d ", *r, *g, *b); */
}



Elliot Lee's avatar
Elliot Lee committed
468
469
470
471
472
473
474
475
476
struct _Color
{
  int red;
  int green;
  int blue;
};

struct _QuantizeObj
{
477
  Pass1_Func first_pass;            /* first pass over image data creates colormap  */
478
  Pass2i_Func second_pass_init;     /* Initialize data which persists over invocations */
479
  Pass2_Func second_pass;           /* second pass maps from image data to colormap */
480
481
482
483
  Cleanup_Func delete_func;         /* function to clean up data associated with private */

  int desired_number_of_colors;     /* Number of colors we will allow    */
  int actual_number_of_colors;      /* Number of colors actually needed  */
484
  Color cmap[256];                  /* colormap created by quantization  */
485
  Color clin[256];                  /* .. converted back to linear space */
Manish Singh's avatar
Manish Singh committed
486
487
  gulong index_used_count[256];     /* how many times an index was used */
  CFHistogram histogram;            /* holds the histogram               */
488

489
490
  gboolean want_alpha_dither;
  int      error_freedom;           /* 0=much bleed, 1=controlled bleed */
491

492
493
494
  GimpProgress *progress;
  gint          nth_layer;
  gint          n_layers;
Elliot Lee's avatar
Elliot Lee committed
495
496
497
498
499
500
};

typedef struct
{
  /*  The bounds of the box (inclusive); expressed as histogram indexes  */
  int   Rmin, Rmax;
501
  int   Rhalferror;
Elliot Lee's avatar
Elliot Lee committed
502
  int   Gmin, Gmax;
503
  int   Ghalferror;
Elliot Lee's avatar
Elliot Lee committed
504
  int   Bmin, Bmax;
505
  int   Bhalferror;
Elliot Lee's avatar
Elliot Lee committed
506
507
508
509
510
511

  /*  The volume (actually 2-norm) of the box  */
  int   volume;

  /*  The number of nonzero histogram cells within this box  */
  long  colorcount;
512
513
514
515
516
517
518
519

  /* The sum of the weighted error within this box */
  guint64 error;
  /* The sum of the unweighted error within this box */
  guint64 rerror;
  guint64 gerror;
  guint64 berror;

Elliot Lee's avatar
Elliot Lee committed
520
521
522
523
524
525
526
527
} box, *boxptr;

typedef struct
{
  long ncolors;
  long dither;
} Options;

528

529

530
531
532
533
534
535
536
537
538
539
540
541
static void zero_histogram_gray     (CFHistogram   histogram);
static void zero_histogram_rgb      (CFHistogram   histogram);
static void generate_histogram_gray (CFHistogram   hostogram,
                                     GimpLayer    *layer,
                                     gboolean      alpha_dither);
static void generate_histogram_rgb  (CFHistogram   histogram,
                                     GimpLayer    *layer,
                                     gint          col_limit,
                                     gboolean      alpha_dither,
                                     GimpProgress *progress,
                                     gint          nth_layer,
                                     gint          n_layers);
Elliot Lee's avatar
Elliot Lee committed
542

543
544
545
546
547
548
549
550
551
552
553
static QuantizeObj * initialize_median_cut (GimpImageBaseType      old_type,
                                            gint                   num_cols,
                                            GimpConvertDitherType  dither_type,
                                            GimpConvertPaletteType palette_type,
                                            gboolean               alpha_dither,
                                            GimpProgress          *progress);

static void          compute_color_lin8    (QuantizeObj           *quantobj,
                                            CFHistogram            histogram,
                                            boxptr                 boxp,
                                            const int              icolor);
554

555

556
557
558
static guchar    found_cols[MAXNUMCOLORS][3];
static gint      num_found_cols;
static gboolean  needs_quantize;
559

560
static GimpPalette *theCustomPalette = NULL;
561

562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583

/**********************************************************/
typedef struct
{
  signed long used_count;
  unsigned char initial_index;
} palentryStruct;

static int
mapping_compare (const void *a, const void *b)
{
  palentryStruct *m1 = (palentryStruct*)a;
  palentryStruct *m2 = (palentryStruct*)b;

  return (m2->used_count - m1->used_count);
}

/* FWIW, the make_remap_table() and mapping_compare() function source
   and palentryStruct may be re-used under the XFree86-style license.
   <adam@gimp.org> */
static void
make_remap_table (const unsigned char  old_palette[],
584
585
586
587
                  unsigned char        new_palette[],
                  const unsigned long  index_used_count[],
                  unsigned char        remap_table[],
                  int*                 num_entries)
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
{
  int i,j,k;
  unsigned char temppal[256 * 3];
  unsigned long tempuse[256];
  unsigned long transmap[256];
  palentryStruct *palentries;
  int used = 0;

  memset(temppal, 0, 256 * 3);
  memset(tempuse, 0, 256 * sizeof(unsigned long));
  memset(transmap, 255, 256 * sizeof(unsigned long));

  /* First pass - only collect entries which are marked as
     being used at all in index_used_count. */
  for (i = 0; i < *num_entries; i++)
    {
      if (index_used_count[i])
605
606
607
608
        {
          temppal[used*3 + 0] = old_palette[i*3 + 0];
          temppal[used*3 + 1] = old_palette[i*3 + 1];
          temppal[used*3 + 2] = old_palette[i*3 + 2];
609

610
611
          tempuse[used] = index_used_count[i];
          transmap[i] = used;
612

613
614
          used++;
        }
615
616
617
618
619
620
    }

  /* Second pass - remove duplicates. (O(n^3), could do better!) */
  for (i = 0; i < used; i++)
    {
      for (j = 0; j < i; j++)
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
        {
          if ((temppal[i*3 + 1] == temppal[j*3 + 1]) &&
              (temppal[i*3 + 0] == temppal[j*3 + 0]) &&
              (temppal[i*3 + 2] == temppal[j*3 + 2]) &&
              tempuse[j] &&
              tempuse[i])
            {
              /* Move the 'used' tally from one to the other. */
              tempuse[i] += tempuse[j];
              /* zero one of them, deactivating its entry. */
              tempuse[j] = 0;

              /* change all mappings from this dead index
                 to the live one. */
              for (k = 0; k < *num_entries; k++)
                {
                  if (index_used_count[k] && (transmap[k] == j))
                    transmap[k] = i;
                }
            }
        }
642
643
644
645
646
647
648
649
650
651
652
    }

  /* Third pass - rank all used indicies to the beginning of the
     palette. */
  palentries = g_malloc(used * sizeof(palentryStruct));
  for (i = 0; i < used; i++)
    {
      palentries[i].initial_index = i;
      palentries[i].used_count    = tempuse[i];
    }
  qsort(palentries, used, sizeof(palentryStruct),
653
        &mapping_compare);
654
655
656
  for (i = 0; i < *num_entries; i++)
    {
      if (index_used_count[i])
657
658
659
660
661
662
663
664
665
666
667
        {
          for (j = 0; j < used; j++)
            {
              if ((transmap[i] == palentries[j].initial_index)
                  && (palentries[j].used_count))
                {
                  remap_table[i] = j;
                  break;
                }
            }
        }
668
669
670
671
    }
  for (i = 0; i < *num_entries; i++)
    {
      if (index_used_count[i])
672
673
674
675
676
        {
          new_palette[remap_table[i]*3 + 0] = old_palette[i*3 + 0];
          new_palette[remap_table[i]*3 + 1] = old_palette[i*3 + 1];
          new_palette[remap_table[i]*3 + 2] = old_palette[i*3 + 2];
        }
677
    }
678

679
  *num_entries = 0;
680

681
682
683
  for (j = 0; j < used; j++)
    {
      if (palentries[j].used_count)
684
685
686
        {
          (*num_entries)++;
        }
687
    }
688

689
690
691
692
  g_free (palentries);
}

static void
693
694
695
remap_indexed_layer (GimpLayer    *layer,
                     const guchar *remap_table,
                     gint          num_entries)
696
{
697
698
699
700
701
702
  PixelRegion   srcPR, destPR;
  gpointer      pr;
  gboolean      has_alpha;
  gint          pixels;
  const guchar *src;
  guchar       *dest;
703
704
705
706
707

  has_alpha = gimp_drawable_has_alpha (GIMP_DRAWABLE (layer));

  pixel_region_init (&srcPR, GIMP_DRAWABLE (layer)->tiles,
                     0, 0,
708
                     GIMP_ITEM (layer)->width,
709
                     GIMP_ITEM (layer)->height,
710
                     FALSE);
711
712
  pixel_region_init (&destPR, GIMP_DRAWABLE (layer)->tiles,
                     0, 0,
713
                     GIMP_ITEM (layer)->width,
714
                     GIMP_ITEM (layer)->height,
715
                     TRUE);
716

717
  if (has_alpha)
718
    {
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
      for (pr = pixel_regions_register (2, &srcPR, &destPR);
           pr != NULL;
           pr = pixel_regions_process (pr))
        {
          src = srcPR.data;
          dest = destPR.data;
          pixels = srcPR.h * srcPR.w;

          while (pixels--)
            {
              if (src[ALPHA_I_PIX])
                dest[INDEXED_PIX] = remap_table[src[INDEXED_PIX]];
            }

          src += srcPR.bytes;
          dest += destPR.bytes;
        }
    }
  else
    {
      for (pr = pixel_regions_register (2, &srcPR, &destPR);
           pr != NULL;
           pr = pixel_regions_process (pr))
        {
          src = srcPR.data;
          dest = destPR.data;
          pixels = srcPR.h * srcPR.w;

          while (pixels--)
            dest[INDEXED_PIX] = remap_table[src[INDEXED_PIX]];

          src += srcPR.bytes;
          dest += destPR.bytes;
        }
753
754
755
    }
}

756
static int
757
758
759
760
761
color_quicksort (const void *c1,
                 const void *c2)
{
  Color *color1 = (Color *)c1;
  Color *color2 = (Color *)c2;
762
763
764
765

  double v1 = GIMP_RGB_INTENSITY (color1->red, color1->green, color1->blue);
  double v2 = GIMP_RGB_INTENSITY (color2->red, color2->green, color2->blue);

766
767
768
769
770
771
772
  if (v1 < v2)
    return -1;
  else if (v1 > v2)
    return 1;
  else
    return 0;
}
773

774
void
775
gimp_image_convert (GimpImage              *gimage,
776
777
778
779
780
781
782
783
784
785
                    GimpImageBaseType       new_type,
                    /* The following three params used only for
                     * new_type == GIMP_INDEXED
                     */
                    gint                    num_cols,
                    GimpConvertDitherType   dither,
                    gboolean                alpha_dither,
                    gboolean                remove_dups,
                    GimpConvertPaletteType  palette_type,
                    GimpPalette            *custom_palette,
786
                    GimpProgress           *progress)
Elliot Lee's avatar
Elliot Lee committed
787
{
788
  QuantizeObj       *quantobj = NULL;
789
790
791
792
  GimpLayer         *layer;
  GimpImageBaseType  old_type;
  GList             *list;
  GimpImageType      new_layer_type;
793
794
  TileManager       *new_tiles;
  const gchar       *undo_desc = NULL;
795
  gint               nth_layer, n_layers;
Elliot Lee's avatar
Elliot Lee committed
796

797
  g_return_if_fail (GIMP_IS_IMAGE (gimage));
798
  g_return_if_fail (new_type != gimp_image_base_type (gimage));
799
  g_return_if_fail (progress == NULL || GIMP_IS_PROGRESS (progress));
800

801
802
  theCustomPalette = custom_palette;

803
  gimp_set_busy (gimage->gimp);
804

805
806
  n_layers = g_list_length (GIMP_LIST (gimage->layers)->list);

807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
  switch (new_type)
    {
    case GIMP_RGB:
      undo_desc = _("Convert Image to RGB");
      break;

    case GIMP_GRAY:
      undo_desc = _("Convert Image to Grayscale");
      break;

    case GIMP_INDEXED:
      undo_desc = _("Convert Image to Indexed");
      break;
    }

822
823
  g_object_freeze_notify (G_OBJECT (gimage));

824
  gimp_image_undo_group_start (gimage, GIMP_UNDO_GROUP_IMAGE_CONVERT,
825
                               undo_desc);
Elliot Lee's avatar
Elliot Lee committed
826

827
828
829
  if (gimp_image_floating_sel (gimage))
    floating_sel_relax (gimp_image_floating_sel (gimage), TRUE);

830
  /*  Push the image type to the stack  */
831
  gimp_image_undo_push_image_type (gimage, NULL);
Elliot Lee's avatar
Elliot Lee committed
832
833
834

  /*  Set the new base type  */
  old_type = gimage->base_type;
835
836

  g_object_set (gimage, "base-type", new_type, NULL);
Elliot Lee's avatar
Elliot Lee committed
837

838
  /* initialize the colour conversion routines */
839
  cpercep_init_conversions ();
840

Elliot Lee's avatar
Elliot Lee committed
841
  /*  Convert to indexed?  Build histogram if necessary.  */
842
  if (new_type == GIMP_INDEXED)
Elliot Lee's avatar
Elliot Lee committed
843
    {
844
      gint i;
Elliot Lee's avatar
Elliot Lee committed
845

846
847
      /* fprintf(stderr, " TO INDEXED(%d) ", num_cols); */

848
      /* don't dither if the input is grayscale and we are simply
849
850
851
852
       * mapping every color
       */
      if (old_type     == GIMP_GRAY &&
          num_cols     == 256       &&
853
854
855
856
          palette_type == GIMP_MAKE_PALETTE)
        {
          dither = GIMP_NO_DITHER;
        }
Elliot Lee's avatar
Elliot Lee committed
857

858
      quantobj = initialize_median_cut (old_type, num_cols, dither,
859
860
                                        palette_type, alpha_dither,
                                        progress);
Elliot Lee's avatar
Elliot Lee committed
861

862
      if (palette_type == GIMP_MAKE_PALETTE)
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
        {
          if (old_type == GIMP_GRAY)
            zero_histogram_gray (quantobj->histogram);
          else
            zero_histogram_rgb (quantobj->histogram);

          /* To begin, assume that there are fewer colours in
           *  the image than the user actually asked for.  In that
           *  case, we don't need to quantize or colour-dither.
           */
          needs_quantize = FALSE;
          num_found_cols = 0;

          /*  Build the histogram  */
          for (list = GIMP_LIST (gimage->layers)->list, nth_layer = 0;
               list;
               list = g_list_next (list), nth_layer++)
            {
              layer = (GimpLayer *) list->data;

              if (old_type == GIMP_GRAY)
                generate_histogram_gray (quantobj->histogram,
885
                                         layer, alpha_dither);
886
887
              else
                generate_histogram_rgb (quantobj->histogram,
888
                                        layer, num_cols, alpha_dither,
889
                                        progress, nth_layer, n_layers);
890
891
892
893
894
895
896
              /*
               * Note: generate_histogram_rgb may set needs_quantize if
               *  the image contains more colours than the limit specified
               *  by the user.
               */
            }
        }
Elliot Lee's avatar
Elliot Lee committed
897

898
899
900
901
      if (progress)
        gimp_progress_set_text (progress,
                                _("Converting to indexed (stage 2)..."));

902
903
904
      if (old_type == GIMP_RGB &&
          ! needs_quantize     &&
          palette_type == GIMP_MAKE_PALETTE)
905
906
907
908
909
910
911
912
913
914
        {
          /* If this is an RGB image, and the user wanted a custom-built
           *  generated palette, and this image has no more colours than
           *  the user asked for, we don't need the first pass (quantization).
           *
           * There's also no point in dithering, since there's no error to
           *  spread.  So we destroy the old quantobj and make a new one
           *  with the remapping function set to a special LUT-based
           *  no-dither remapper.
           */
915

916
917
918
          quantobj->delete_func (quantobj);
          quantobj = initialize_median_cut (old_type, num_cols,
                                            GIMP_NODESTRUCT_DITHER,
919
                                            palette_type,
920
                                            alpha_dither,
921
                                            progress);
922
923
924
925
926
927
928
929
930
931
          /* We can skip the first pass (palette creation) */

          quantobj->actual_number_of_colors = num_found_cols;
          for (i = 0; i < num_found_cols; i++)
            {
              quantobj->cmap[i].red = found_cols[i][0];
              quantobj->cmap[i].green = found_cols[i][1];
              quantobj->cmap[i].blue = found_cols[i][2];
            }
        }
Elliot Lee's avatar
Elliot Lee committed
932
      else
933
934
935
        {
          (* quantobj->first_pass) (quantobj);
        }
936

937
      if (palette_type == GIMP_MAKE_PALETTE)
938
939
        qsort (quantobj->cmap,
               quantobj->actual_number_of_colors, sizeof (Color),
940
               color_quicksort);
941
    }
Elliot Lee's avatar
Elliot Lee committed
942

943
944
945
946
  if (progress)
    gimp_progress_set_text (progress,
                            _("Converting to indexed (stage 3)..."));

947
948
949
  /* Initialise data which must persist across indexed layer iterations */
  switch (new_type)
    {
950
    case GIMP_INDEXED:
951
      if (quantobj->second_pass_init)
952
        (* quantobj->second_pass_init) (quantobj);
953
954
955
      break;
    default:
      break;
Elliot Lee's avatar
Elliot Lee committed
956
957
958
    }

  /*  Convert all layers  */
959
960
961
962
  if (quantobj)
    quantobj->n_layers = n_layers;

  for (list = GIMP_LIST (gimage->layers)->list, nth_layer = 0;
963
       list;
964
       list = g_list_next (list), nth_layer++)
Elliot Lee's avatar
Elliot Lee committed
965
    {
966
      layer = list->data;
Elliot Lee's avatar
Elliot Lee committed
967

968
969
      new_layer_type = GIMP_IMAGE_TYPE_FROM_BASE_TYPE (new_type);

970
      if (gimp_drawable_has_alpha (GIMP_DRAWABLE (layer)))
971
        new_layer_type = GIMP_IMAGE_TYPE_WITH_ALPHA (new_layer_type);
972

973
      new_tiles = tile_manager_new (GIMP_ITEM (layer)->width,
974
975
                                    GIMP_ITEM (layer)->height,
                                    GIMP_IMAGE_TYPE_BYTES (new_layer_type));
Elliot Lee's avatar
Elliot Lee committed
976
977

      switch (new_type)
978
979
980
981
982
983
984
985
986
987
988
989
        {
        case GIMP_RGB:
          gimp_drawable_convert_rgb (GIMP_DRAWABLE (layer),
                                     new_tiles,
                                     old_type);
          break;
        case GIMP_GRAY:
          gimp_drawable_convert_grayscale (GIMP_DRAWABLE (layer),
                                           new_tiles,
                                           old_type);
          break;
        case GIMP_INDEXED:
990
          quantobj->nth_layer = nth_layer;
991
992
993
994
995
996
997
          (* quantobj->second_pass) (quantobj,
                                     layer,
                                     new_tiles);
          break;
        default:
          break;
        }
Elliot Lee's avatar
Elliot Lee committed
998

999
1000
1001
1002
      gimp_drawable_set_tiles_full (GIMP_DRAWABLE (layer), TRUE, NULL,
                                    new_tiles, new_layer_type,
                                    GIMP_ITEM (layer)->offset_x,
                                    GIMP_ITEM (layer)->offset_y);
1003
      tile_manager_unref (new_tiles);
Elliot Lee's avatar
Elliot Lee committed
1004
1005
    }

1006
  switch (new_type)
1007
    {
1008
1009
    case GIMP_RGB:
    case GIMP_GRAY:
1010
1011
      if (old_type == GIMP_INDEXED)
        gimp_image_set_colormap (gimage, NULL, 0, TRUE);
1012
1013
1014
      break;

    case GIMP_INDEXED:
1015
1016
      gimp_image_undo_push_image_colormap (gimage, NULL);

1017
      gimage->cmap = g_new0 (guchar, GIMP_IMAGE_COLORMAP_SIZE);
1018

1019
1020
      if (remove_dups && ((palette_type == GIMP_WEB_PALETTE) ||
                          (palette_type == GIMP_CUSTOM_PALETTE)))
1021
1022
        {
          gint   i, j;
1023
1024
1025
          guchar old_palette[256 * 3];
          guchar new_palette[256 * 3];
          guchar remap_table[256];
1026
          gint   num_entries;
1027

1028
1029
1030
1031
1032
1033
1034
1035
          for (i = 0, j = 0; i < quantobj->actual_number_of_colors; i++)
            {
              old_palette[j++] = quantobj->cmap[i].red;
              old_palette[j++] = quantobj->cmap[i].green;
              old_palette[j++] = quantobj->cmap[i].blue;
            }

          num_entries = quantobj->actual_number_of_colors;
1036
1037

#if 1
1038
1039
1040
          /* Generate a remapping table */
          make_remap_table (old_palette, new_palette,
                            quantobj->index_used_count,
1041
                            remap_table, &num_entries);
1042

1043
1044
1045
1046
1047
1048
1049
1050
1051
          /*  Convert all layers  */
          for (list = GIMP_LIST (gimage->layers)->list;
               list;
               list = g_list_next (list))
            {
              layer = (GimpLayer *) list->data;

              remap_indexed_layer (layer, remap_table, num_entries);
            }
1052
#else
1053
          memcpy (new_palette, old_palette, 256 * 3);
1054
1055
#endif

1056
1057
1058
1059
1060
1061
          for (i = 0, j = 0; i < num_entries; i++)
            {
              gimage->cmap[j] = new_palette[j]; j++;
              gimage->cmap[j] = new_palette[j]; j++;
              gimage->cmap[j] = new_palette[j]; j++;
            }
1062

1063
1064
          gimage->num_cols = num_entries;
        }
1065
      else
1066
1067
        {
          gint i,j;
1068

1069
1070
1071
1072
1073
1074
          for (i = 0, j = 0; i < quantobj->actual_number_of_colors; i++)
            {
              gimage->cmap[j++] = quantobj->cmap[i].red;
              gimage->cmap[j++] = quantobj->cmap[i].green;
              gimage->cmap[j++] = quantobj->cmap[i].blue;
            }
1075

1076
1077
          gimage->num_cols = quantobj->actual_number_of_colors;
        }
1078
1079

      gimp_image_colormap_changed (gimage, -1);
1080
      break;
1081
1082
    }

scott's avatar
scott committed
1083
  /*  Delete the quantizer object, if there is one */
1084
  if (quantobj)
scott's avatar
scott committed
1085
1086
    quantobj->delete_func (quantobj);

1087
1088
1089
  if (gimp_image_floating_sel (gimage))
    floating_sel_rigor (gimp_image_floating_sel (gimage), TRUE);

1090
  gimp_image_undo_group_end (gimage);
Elliot Lee's avatar
Elliot Lee committed
1091

1092
  gimp_image_invalidate_layer_previews (gimage);
1093
  gimp_image_mode_changed (gimage);
1094
  g_object_thaw_notify (G_OBJECT (gimage));
1095

1096
  gimp_unset_busy (gimage->gimp);
Elliot Lee's avatar
Elliot Lee committed
1097
1098
}

1099

Elliot Lee's avatar
Elliot Lee committed
1100
1101
1102
1103
1104
/*
 *  Indexed color conversion machinery
 */

static void
Manish Singh's avatar
Manish Singh committed
1105
zero_histogram_gray (CFHistogram histogram)
Elliot Lee's avatar
Elliot Lee committed
1106
1107
1108
1109
1110
1111
1112
1113
1114
{
  int i;

  for (i = 0; i < 256; i++)
    histogram[i] = 0;
}


static void
Manish Singh's avatar
Manish Singh committed
1115
zero_histogram_rgb (CFHistogram histogram)
Elliot Lee's avatar
Elliot Lee committed
1116
{
1117
1118
  memset (histogram, 0,
          HIST_R_ELEMS * HIST_G_ELEMS * HIST_B_ELEMS * sizeof(ColorFreq));
Elliot Lee's avatar
Elliot Lee committed
1119
1120
1121
1122
}


static void
Manish Singh's avatar
Manish Singh committed
1123
generate_histogram_gray (CFHistogram  histogram,
1124
1125
                         GimpLayer   *layer,
                         gboolean     alpha_dither)
Elliot Lee's avatar
Elliot Lee committed
1126
{
1127
1128
1129
1130
1131
  PixelRegion   srcPR;
  const guchar *data;
  gint          size;
  gpointer      pr;
  gboolean      has_alpha;
Elliot Lee's avatar
Elliot Lee committed
1132

1133
  has_alpha = gimp_drawable_has_alpha (GIMP_DRAWABLE (layer));
Elliot Lee's avatar
Elliot Lee committed
1134

1135
1136
  pixel_region_init (&srcPR, GIMP_DRAWABLE (layer)->tiles,
                     0, 0,
1137
1138
                     GIMP_ITEM (layer)->width,
                     GIMP_ITEM (layer)->height,
1139
1140
                     FALSE);

Elliot Lee's avatar
Elliot Lee committed
1141
1142
1143
1144
1145
1146
1147
  for (pr = pixel_regions_register (1, &srcPR);
       pr != NULL;
       pr = pixel_regions_process (pr))
    {
      data = srcPR.data;
      size = srcPR.w * srcPR.h;
      while (size--)
1148
1149
1150
1151
        {
          histogram[*data]++;
          data += srcPR.bytes;
        }
Elliot Lee's avatar
Elliot Lee committed
1152
1153
1154
1155
1156
    }
}


static void
1157
generate_histogram_rgb (CFHistogram   histogram,
1158
1159
1160
                        GimpLayer    *layer,
                        gint          col_limit,
                        gboolean      alpha_dither,
1161
1162
1163
                        GimpProgress *progress,
                        gint          nth_layer,
                        gint          n_layers)
Elliot Lee's avatar
Elliot Lee committed
1164
{
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
  PixelRegion   srcPR;
  const guchar *data;
  gint          size;
  gpointer      pr;
  ColorFreq    *colfreq;
  gboolean      has_alpha;
  gint          nfc_iter;
  gint          row, col, coledge;
  gint          offsetx, offsety;
  glong         total_size = 0, layer_size;
Elliot Lee's avatar
Elliot Lee committed
1175

1176
  has_alpha = gimp_drawable_has_alpha (GIMP_DRAWABLE (layer));
Elliot Lee's avatar
Elliot Lee committed
1177

1178
  gimp_item_offsets (GIMP_ITEM (layer), &offsetx, &offsety);
1179

1180
/*  g_print ("col_limit = %d, nfc = %d\n", col_limit, num_found_cols);*/
Elliot Lee's avatar
Elliot Lee committed
1181

1182
1183
  pixel_region_init (&srcPR, GIMP_DRAWABLE (layer)->tiles,
                     0, 0,
1184
1185
1186
                     GIMP_ITEM (layer)->width,
                     GIMP_ITEM (layer)->height,
                     FALSE);
1187

1188
1189
  layer_size = GIMP_ITEM (layer)->width * GIMP_ITEM (layer)->height;

1190
1191
  if (progress)
    gimp_progress_set_value (progress, 0.0);
1192

Elliot Lee's avatar
Elliot Lee committed
1193
1194
1195
1196
1197
1198
1199
  for (pr = pixel_regions_register (1, &srcPR);
       pr != NULL;
       pr = pixel_regions_process (pr))
    {
      data = srcPR.data;
      size = srcPR.w * srcPR.h;

1200
1201
      total_size += size;

1202
      /* g_printerr (" [%d,%d - %d,%d]", srcPR.x, srcPR.y, offsetx, offsety); */
1203

Elliot Lee's avatar
Elliot Lee committed
1204
      if (needs_quantize)
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
        {
          if (alpha_dither)
            {
              /* if alpha-dithering,
                 we need to be deterministic w.r.t. offsets */

              col = srcPR.x + offsetx;
              coledge = col + srcPR.w;
              row = srcPR.y + offsety;

              while (size--)
                {
                  if (
                      (
                       has_alpha && (
                                     (data[ALPHA_PIX] << 6) >
                                     (255 * DM[col&DM_WIDTHMASK][row&DM_HEIGHTMASK])
                                     )
                       )
                      || (!has_alpha))
                    {
                      colfreq = HIST_RGB (histogram,
1227
1228
1229
                                          data[RED_PIX],
                                          data[GREEN_PIX],
                                          data[BLUE_PIX]);
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
                      (*colfreq)++;
                    }

                  col++;
                  if (col == coledge)
                    {
                      col = srcPR.x + offsetx;
                      row++;
                    }

                  data += srcPR.bytes;
                }
            }
          else
            {
              while (size--)
                {
                  if (
                      (
                       has_alpha && (
                                     (data[ALPHA_PIX] > 127)
                                     )
                       )
                      || (!has_alpha))
                    {
                      colfreq = HIST_RGB (histogram,
1256
1257
1258
                                          data[RED_PIX],
                                          data[GREEN_PIX],
                                          data[BLUE_PIX]);
1259
1260
1261
1262
1263
1264
                      (*colfreq)++;
                    }
                  data += srcPR.bytes;
                }
            }
        }
Elliot Lee's avatar
Elliot Lee committed
1265
      else
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
        {
          /* if alpha-dithering, we need to be deterministic w.r.t. offsets */
          col = srcPR.x + offsetx;
          coledge = col + srcPR.w;
          row = srcPR.y + offsety;

          while (size--)
            {
              if ((has_alpha && (alpha_dither ?
                                 ((data[ALPHA_PIX] << 6) > (255 * DM[col&DM_WIDTHMASK][row&DM_HEIGHTMASK])) :
                                 (data[ALPHA_PIX] > 127))) || (!has_alpha))
                {
                  colfreq = HIST_RGB (histogram,
1279
1280
1281
                                      data[RED_PIX],
                                      data[GREEN_PIX],
                                      data[BLUE_PIX]);
1282
1283
1284
1285
1286
1287
1288
1289