Pillow

1
/*
2
 * The Python Imaging Library
3
 * $Id$
4
 *
5
 * helpers to bounding boxes, min/max values, number of colors, etc.
6
 *
7
 * history:
8
 * 1996-07-22 fl   Created
9
 * 1996-12-30 fl   Added projection stuff
10
 * 1998-07-12 fl   Added extrema stuff
11
 * 2004-09-17 fl   Added colors stuff
12
 *
13
 * Copyright (c) 1997-2004 by Secret Labs AB.
14
 * Copyright (c) 1996-2004 by Fredrik Lundh.
15
 *
16
 * See the README file for details on usage and redistribution.
17
 */
18

19
#include "Imaging.h"
20

21
int
22
ImagingGetBBox(Imaging im, int bbox[4], int alpha_only) {
23
    /* Get the bounding box for any non-zero data in the image.*/
24

25
    int x, y;
26
    int has_data;
27

28
    /* Initialize bounding box to max values */
29
    bbox[0] = im->xsize;
30
    bbox[1] = -1;
31
    bbox[2] = bbox[3] = 0;
32

33
#define GETBBOX(image, mask)              \
34
    for (y = 0; y < im->ysize; y++) {     \
35
        has_data = 0;                     \
36
        for (x = 0; x < im->xsize; x++) { \
37
            if (im->image[y][x] & mask) { \
38
                has_data = 1;             \
39
                if (x < bbox[0]) {        \
40
                    bbox[0] = x;          \
41
                }                         \
42
                if (x >= bbox[2]) {       \
43
                    bbox[2] = x + 1;      \
44
                }                         \
45
            }                             \
46
        }                                 \
47
        if (has_data) {                   \
48
            if (bbox[1] < 0) {            \
49
                bbox[1] = y;              \
50
            }                             \
51
            bbox[3] = y + 1;              \
52
        }                                 \
53
    }
54

55
    if (im->image8) {
56
        GETBBOX(image8, 0xff);
57
    } else {
58
        INT32 mask = 0xffffffff;
59
        if (im->bands == 3) {
60
            ((UINT8 *)&mask)[3] = 0;
61
        } else if (alpha_only &&
62
                   (strcmp(im->mode, "RGBa") == 0 || strcmp(im->mode, "RGBA") == 0 ||
63
                    strcmp(im->mode, "La") == 0 || strcmp(im->mode, "LA") == 0 ||
64
                    strcmp(im->mode, "PA") == 0)) {
65
#ifdef WORDS_BIGENDIAN
66
            mask = 0x000000ff;
67
#else
68
            mask = 0xff000000;
69
#endif
70
        }
71
        GETBBOX(image32, mask);
72
    }
73

74
    /* Check that we got a box */
75
    if (bbox[1] < 0) {
76
        return 0; /* no data */
77
    }
78

79
    return 1; /* ok */
80
}
81

82
int
83
ImagingGetProjection(Imaging im, UINT8 *xproj, UINT8 *yproj) {
84
    /* Get projection arrays for non-zero data in the image.*/
85

86
    int x, y;
87
    int has_data;
88

89
    /* Initialize projection arrays */
90
    memset(xproj, 0, im->xsize);
91
    memset(yproj, 0, im->ysize);
92

93
#define GETPROJ(image, mask)              \
94
    for (y = 0; y < im->ysize; y++) {     \
95
        has_data = 0;                     \
96
        for (x = 0; x < im->xsize; x++) { \
97
            if (im->image[y][x] & mask) { \
98
                has_data = 1;             \
99
                xproj[x] = 1;             \
100
            }                             \
101
        }                                 \
102
        if (has_data) {                   \
103
            yproj[y] = 1;                 \
104
        }                                 \
105
    }
106

107
    if (im->image8) {
108
        GETPROJ(image8, 0xff);
109
    } else {
110
        INT32 mask = 0xffffffff;
111
        if (im->bands == 3) {
112
            ((UINT8 *)&mask)[3] = 0;
113
        }
114
        GETPROJ(image32, mask);
115
    }
116

117
    return 1; /* ok */
118
}
119

120
int
121
ImagingGetExtrema(Imaging im, void *extrema) {
122
    int x, y;
123
    INT32 imin, imax;
124
    FLOAT32 fmin, fmax;
125

126
    if (im->bands != 1) {
127
        (void)ImagingError_ModeError();
128
        return -1; /* mismatch */
129
    }
130

131
    if (!im->xsize || !im->ysize) {
132
        return 0; /* zero size */
133
    }
134

135
    switch (im->type) {
136
        case IMAGING_TYPE_UINT8:
137
            imin = imax = im->image8[0][0];
138
            for (y = 0; y < im->ysize; y++) {
139
                UINT8 *in = im->image8[y];
140
                for (x = 0; x < im->xsize; x++) {
141
                    if (imin > in[x]) {
142
                        imin = in[x];
143
                    } else if (imax < in[x]) {
144
                        imax = in[x];
145
                    }
146
                }
147
            }
148
            ((UINT8 *)extrema)[0] = (UINT8)imin;
149
            ((UINT8 *)extrema)[1] = (UINT8)imax;
150
            break;
151
        case IMAGING_TYPE_INT32:
152
            imin = imax = im->image32[0][0];
153
            for (y = 0; y < im->ysize; y++) {
154
                INT32 *in = im->image32[y];
155
                for (x = 0; x < im->xsize; x++) {
156
                    if (imin > in[x]) {
157
                        imin = in[x];
158
                    } else if (imax < in[x]) {
159
                        imax = in[x];
160
                    }
161
                }
162
            }
163
            memcpy(extrema, &imin, sizeof(imin));
164
            memcpy(((char *)extrema) + sizeof(imin), &imax, sizeof(imax));
165
            break;
166
        case IMAGING_TYPE_FLOAT32:
167
            fmin = fmax = ((FLOAT32 *)im->image32[0])[0];
168
            for (y = 0; y < im->ysize; y++) {
169
                FLOAT32 *in = (FLOAT32 *)im->image32[y];
170
                for (x = 0; x < im->xsize; x++) {
171
                    if (fmin > in[x]) {
172
                        fmin = in[x];
173
                    } else if (fmax < in[x]) {
174
                        fmax = in[x];
175
                    }
176
                }
177
            }
178
            memcpy(extrema, &fmin, sizeof(fmin));
179
            memcpy(((char *)extrema) + sizeof(fmin), &fmax, sizeof(fmax));
180
            break;
181
        case IMAGING_TYPE_SPECIAL:
182
            if (strcmp(im->mode, "I;16") == 0) {
183
                UINT16 v;
184
                UINT8 *pixel = *im->image8;
185
#ifdef WORDS_BIGENDIAN
186
                v = pixel[0] + (pixel[1] << 8);
187
#else
188
                memcpy(&v, pixel, sizeof(v));
189
#endif
190
                imin = imax = v;
191
                for (y = 0; y < im->ysize; y++) {
192
                    for (x = 0; x < im->xsize; x++) {
193
                        pixel = (UINT8 *)im->image[y] + x * sizeof(v);
194
#ifdef WORDS_BIGENDIAN
195
                        v = pixel[0] + (pixel[1] << 8);
196
#else
197
                        memcpy(&v, pixel, sizeof(v));
198
#endif
199
                        if (imin > v) {
200
                            imin = v;
201
                        } else if (imax < v) {
202
                            imax = v;
203
                        }
204
                    }
205
                }
206
                v = (UINT16)imin;
207
                memcpy(extrema, &v, sizeof(v));
208
                v = (UINT16)imax;
209
                memcpy(((char *)extrema) + sizeof(v), &v, sizeof(v));
210
                break;
211
            }
212
            /* FALL THROUGH */
213
        default:
214
            (void)ImagingError_ModeError();
215
            return -1;
216
    }
217
    return 1; /* ok */
218
}
219

220
/* static ImagingColorItem* getcolors8(Imaging im, int maxcolors, int* size);*/
221
static ImagingColorItem *
222
getcolors32(Imaging im, int maxcolors, int *size);
223

224
ImagingColorItem *
225
ImagingGetColors(Imaging im, int maxcolors, int *size) {
226
    /* FIXME: add support for 8-bit images */
227
    return getcolors32(im, maxcolors, size);
228
}
229

230
static ImagingColorItem *
231
getcolors32(Imaging im, int maxcolors, int *size) {
232
    unsigned int h;
233
    unsigned int i, incr;
234
    int colors;
235
    INT32 pixel_mask;
236
    int x, y;
237
    ImagingColorItem *table;
238
    ImagingColorItem *v;
239

240
    unsigned int code_size;
241
    unsigned int code_poly;
242
    unsigned int code_mask;
243

244
    /* note: the hash algorithm used here is based on the dictionary
245
       code in Python 2.1.3; the exact implementation is borrowed from
246
       Python's Unicode property database (written by yours truly) /F */
247

248
    static int SIZES[] = {4,          3,  8,         3,  16,        3,  32,        5,
249
                          64,         3,  128,       3,  256,       29, 512,       17,
250
                          1024,       9,  2048,      5,  4096,      83, 8192,      27,
251
                          16384,      43, 32768,     3,  65536,     45, 131072,    9,
252
                          262144,     39, 524288,    39, 1048576,   9,  2097152,   5,
253
                          4194304,    3,  8388608,   33, 16777216,  27, 33554432,  9,
254
                          67108864,   71, 134217728, 39, 268435456, 9,  536870912, 5,
255
                          1073741824, 83, 0};
256

257
    code_size = code_poly = code_mask = 0;
258

259
    for (i = 0; SIZES[i]; i += 2) {
260
        if (SIZES[i] > maxcolors) {
261
            code_size = SIZES[i];
262
            code_poly = SIZES[i + 1];
263
            code_mask = code_size - 1;
264
            break;
265
        }
266
    }
267

268
    /* printf("code_size=%d\n", code_size); */
269
    /* printf("code_poly=%d\n", code_poly); */
270

271
    if (!code_size) {
272
        return ImagingError_MemoryError(); /* just give up */
273
    }
274

275
    if (!im->image32) {
276
        return ImagingError_ModeError();
277
    }
278

279
    table = calloc(code_size + 1, sizeof(ImagingColorItem));
280
    if (!table) {
281
        return ImagingError_MemoryError();
282
    }
283

284
    pixel_mask = 0xffffffff;
285
    if (im->bands == 3) {
286
        ((UINT8 *)&pixel_mask)[3] = 0;
287
    }
288

289
    colors = 0;
290

291
    for (y = 0; y < im->ysize; y++) {
292
        INT32 *p = im->image32[y];
293
        for (x = 0; x < im->xsize; x++) {
294
            INT32 pixel = p[x] & pixel_mask;
295
            h = (pixel); /* null hashing */
296
            i = (~h) & code_mask;
297
            v = &table[i];
298
            if (!v->count) {
299
                /* add to table */
300
                if (colors++ == maxcolors) {
301
                    goto overflow;
302
                }
303
                v->x = x;
304
                v->y = y;
305
                v->pixel = pixel;
306
                v->count = 1;
307
                continue;
308
            } else if (v->pixel == pixel) {
309
                v->count++;
310
                continue;
311
            }
312
            incr = (h ^ (h >> 3)) & code_mask;
313
            if (!incr) {
314
                incr = code_mask;
315
            }
316
            for (;;) {
317
                i = (i + incr) & code_mask;
318
                v = &table[i];
319
                if (!v->count) {
320
                    /* add to table */
321
                    if (colors++ == maxcolors) {
322
                        goto overflow;
323
                    }
324
                    v->x = x;
325
                    v->y = y;
326
                    v->pixel = pixel;
327
                    v->count = 1;
328
                    break;
329
                } else if (v->pixel == pixel) {
330
                    v->count++;
331
                    break;
332
                }
333
                incr = incr << 1;
334
                if (incr > code_mask) {
335
                    incr = incr ^ code_poly;
336
                }
337
            }
338
        }
339
    }
340

341
overflow:
342

343
    /* pack the table */
344
    for (x = y = 0; x < (int)code_size; x++)
345
        if (table[x].count) {
346
            if (x != y) {
347
                table[y] = table[x];
348
            }
349
            y++;
350
        }
351
    table[y].count = 0; /* mark end of table */
352

353
    *size = colors;
354

355
    return table;
356
}
357