Pillow

1
/*
2
 * The Python Imaging Library
3
 * $Id$
4
 *
5
 * imaging palette object
6
 *
7
 * history:
8
 * 1996-05-05 fl   Added to library
9
 * 1996-05-27 fl   Added colour mapping stuff
10
 * 1997-05-12 fl   Support RGBA palettes
11
 * 2005-02-09 fl   Removed grayscale entries from web palette
12
 *
13
 * Copyright (c) Secret Labs AB 1997-2005.  All rights reserved.
14
 * Copyright (c) Fredrik Lundh 1995-1997.
15
 *
16
 * See the README file for information on usage and redistribution.
17
 */
18

19
#include "Imaging.h"
20

21
#include <math.h>
22

23
ImagingPalette
24
ImagingPaletteNew(const char *mode) {
25
    /* Create a palette object */
26

27
    int i;
28
    ImagingPalette palette;
29

30
    if (strcmp(mode, "RGB") && strcmp(mode, "RGBA")) {
31
        return (ImagingPalette)ImagingError_ModeError();
32
    }
33

34
    palette = calloc(1, sizeof(struct ImagingPaletteInstance));
35
    if (!palette) {
36
        return (ImagingPalette)ImagingError_MemoryError();
37
    }
38

39
    strncpy(palette->mode, mode, IMAGING_MODE_LENGTH - 1);
40
    palette->mode[IMAGING_MODE_LENGTH - 1] = 0;
41

42
    palette->size = 0;
43
    for (i = 0; i < 256; i++) {
44
        palette->palette[i * 4 + 3] = 255; /* opaque */
45
    }
46

47
    return palette;
48
}
49

50
ImagingPalette
51
ImagingPaletteNewBrowser(void) {
52
    /* Create a standard "browser" palette object */
53

54
    int i, r, g, b;
55
    ImagingPalette palette;
56

57
    palette = ImagingPaletteNew("RGB");
58
    if (!palette) {
59
        return NULL;
60
    }
61

62
    /* FIXME: Add 10-level windows palette here? */
63

64
    /* Simple 6x6x6 colour cube */
65
    i = 10;
66
    for (b = 0; b < 256; b += 51) {
67
        for (g = 0; g < 256; g += 51) {
68
            for (r = 0; r < 256; r += 51) {
69
                palette->palette[i * 4 + 0] = r;
70
                palette->palette[i * 4 + 1] = g;
71
                palette->palette[i * 4 + 2] = b;
72
                i++;
73
            }
74
        }
75
    }
76
    palette->size = i;
77

78
    /* FIXME: add 30-level grayscale wedge here? */
79

80
    return palette;
81
}
82

83
ImagingPalette
84
ImagingPaletteDuplicate(ImagingPalette palette) {
85
    /* Duplicate palette descriptor */
86

87
    ImagingPalette new_palette;
88

89
    if (!palette) {
90
        return NULL;
91
    }
92
    /* malloc check ok, small constant allocation */
93
    new_palette = malloc(sizeof(struct ImagingPaletteInstance));
94
    if (!new_palette) {
95
        return (ImagingPalette)ImagingError_MemoryError();
96
    }
97

98
    memcpy(new_palette, palette, sizeof(struct ImagingPaletteInstance));
99

100
    /* Don't share the cache */
101
    new_palette->cache = NULL;
102

103
    return new_palette;
104
}
105

106
void
107
ImagingPaletteDelete(ImagingPalette palette) {
108
    /* Destroy palette object */
109

110
    if (palette) {
111
        if (palette->cache) {
112
            free(palette->cache);
113
        }
114
        free(palette);
115
    }
116
}
117

118
/* -------------------------------------------------------------------- */
119
/* Colour mapping                                                       */
120
/* -------------------------------------------------------------------- */
121

122
/* This code is used to map RGB triplets to palette indices, using
123
   a palette index cache. */
124

125
/*
126
 * This implementation is loosely based on the corresponding code in
127
 * the IJG JPEG library by Thomas G. Lane.  Original algorithms by
128
 * Paul Heckbert and Spencer W. Thomas.
129
 *
130
 * The IJG JPEG library is copyright (C) 1991-1995, Thomas G. Lane.  */
131

132
#define DIST(a, b, s) (a - b) * (a - b) * s
133

134
/* Colour weights (no scaling, for now) */
135
#define RSCALE 1
136
#define GSCALE 1
137
#define BSCALE 1
138

139
/* Calculated scaled distances */
140
#define RDIST(a, b) DIST(a, b, RSCALE *RSCALE)
141
#define GDIST(a, b) DIST(a, b, GSCALE *GSCALE)
142
#define BDIST(a, b) DIST(a, b, BSCALE *BSCALE)
143

144
/* Incremental steps */
145
#define RSTEP (4 * RSCALE)
146
#define GSTEP (4 * GSCALE)
147
#define BSTEP (4 * BSCALE)
148

149
#define BOX 8
150

151
#define BOXVOLUME BOX *BOX *BOX
152

153
void
154
ImagingPaletteCacheUpdate(ImagingPalette palette, int r, int g, int b) {
155
    int i, j;
156
    unsigned int dmin[256], dmax;
157
    int r0, g0, b0;
158
    int r1, g1, b1;
159
    int rc, gc, bc;
160
    unsigned int d[BOXVOLUME];
161
    UINT8 c[BOXVOLUME];
162

163
    /* Get box boundaries for the given (r,g,b)-triplet.  Each box
164
       covers eight cache slots (32 colour values, that is). */
165

166
    r0 = r & 0xe0;
167
    r1 = r0 + 0x1f;
168
    rc = (r0 + r1) / 2;
169
    g0 = g & 0xe0;
170
    g1 = g0 + 0x1f;
171
    gc = (g0 + g1) / 2;
172
    b0 = b & 0xe0;
173
    b1 = b0 + 0x1f;
174
    bc = (b0 + b1) / 2;
175

176
    /* Step 1 -- Select relevant palette entries (after Heckbert) */
177

178
    /* For each palette entry, calculate the min and max distances to
179
     * any position in the box given by the colour we're looking for. */
180

181
    dmax = (unsigned int)~0;
182

183
    for (i = 0; i < palette->size; i++) {
184
        int r, g, b;
185
        unsigned int tmin, tmax;
186

187
        /* Find min and max distances to any point in the box */
188
        r = palette->palette[i * 4 + 0];
189
        tmin = (r < r0) ? RDIST(r, r0) : (r > r1) ? RDIST(r, r1) : 0;
190
        tmax = (r <= rc) ? RDIST(r, r1) : RDIST(r, r0);
191

192
        g = palette->palette[i * 4 + 1];
193
        tmin += (g < g0) ? GDIST(g, g0) : (g > g1) ? GDIST(g, g1) : 0;
194
        tmax += (g <= gc) ? GDIST(g, g1) : GDIST(g, g0);
195

196
        b = palette->palette[i * 4 + 2];
197
        tmin += (b < b0) ? BDIST(b, b0) : (b > b1) ? BDIST(b, b1) : 0;
198
        tmax += (b <= bc) ? BDIST(b, b1) : BDIST(b, b0);
199

200
        dmin[i] = tmin;
201
        if (tmax < dmax) {
202
            dmax = tmax; /* keep the smallest max distance only */
203
        }
204
    }
205

206
    /* Step 2 -- Incrementally update cache slot (after Thomas) */
207

208
    /* Find the box containing the nearest palette entry, and update
209
     * all slots in that box.  We only check boxes for which the min
210
     * distance is less than or equal the smallest max distance */
211

212
    for (i = 0; i < BOXVOLUME; i++) {
213
        d[i] = (unsigned int)~0;
214
    }
215

216
    for (i = 0; i < palette->size; i++) {
217
        if (dmin[i] <= dmax) {
218
            int rd, gd, bd;
219
            int ri, gi, bi;
220
            int rx, gx, bx;
221

222
            ri = (r0 - palette->palette[i * 4 + 0]) * RSCALE;
223
            gi = (g0 - palette->palette[i * 4 + 1]) * GSCALE;
224
            bi = (b0 - palette->palette[i * 4 + 2]) * BSCALE;
225

226
            rd = ri * ri + gi * gi + bi * bi;
227

228
            ri = ri * (2 * RSTEP) + RSTEP * RSTEP;
229
            gi = gi * (2 * GSTEP) + GSTEP * GSTEP;
230
            bi = bi * (2 * BSTEP) + BSTEP * BSTEP;
231

232
            rx = ri;
233
            for (r = j = 0; r < BOX; r++) {
234
                gd = rd;
235
                gx = gi;
236
                for (g = 0; g < BOX; g++) {
237
                    bd = gd;
238
                    bx = bi;
239
                    for (b = 0; b < BOX; b++) {
240
                        if ((unsigned int)bd < d[j]) {
241
                            d[j] = bd;
242
                            c[j] = (UINT8)i;
243
                        }
244
                        bd += bx;
245
                        bx += 2 * BSTEP * BSTEP;
246
                        j++;
247
                    }
248
                    gd += gx;
249
                    gx += 2 * GSTEP * GSTEP;
250
                }
251
                rd += rx;
252
                rx += 2 * RSTEP * RSTEP;
253
            }
254
        }
255
    }
256

257
    /* Step 3 -- Update cache */
258

259
    /* The c array now contains the closest match for each
260
     * cache slot in the box.  Update the cache. */
261

262
    j = 0;
263
    for (r = r0; r < r1; r += 4) {
264
        for (g = g0; g < g1; g += 4) {
265
            for (b = b0; b < b1; b += 4) {
266
                ImagingPaletteCache(palette, r, g, b) = c[j++];
267
            }
268
        }
269
    }
270
}
271

272
int
273
ImagingPaletteCachePrepare(ImagingPalette palette) {
274
    /* Add a colour cache to a palette */
275

276
    int i;
277
    int entries = 64 * 64 * 64;
278

279
    if (palette->cache == NULL) {
280
        /* The cache is 512k.  It might be a good idea to break it
281
           up into a pointer array (e.g. an 8-bit image?) */
282

283
        /* malloc check ok, small constant allocation */
284
        palette->cache = (INT16 *)malloc(entries * sizeof(INT16));
285
        if (!palette->cache) {
286
            (void)ImagingError_MemoryError();
287
            return -1;
288
        }
289

290
        /* Mark all entries as empty */
291
        for (i = 0; i < entries; i++) {
292
            palette->cache[i] = 0x100;
293
        }
294
    }
295

296
    return 0;
297
}
298

299
void
300
ImagingPaletteCacheDelete(ImagingPalette palette) {
301
    /* Release the colour cache, if any */
302

303
    if (palette && palette->cache) {
304
        free(palette->cache);
305
        palette->cache = NULL;
306
    }
307
}
308