← Back to branch summary

~ubuntu-branches/debian/squeeze/python-imaging/squeeze

« back to all changes in this revision

Viewing changes to libImaging/GetBBox.c

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Klose
  • Date: 2006-08-28 23:14:10 UTC
  • mfrom: (2.1.5 edgy)
  • Revision ID: james.westby@ubuntu.com-20060828231410-lca9enmne3ecmkup
Tags: 1.1.5-11
http://bugs.debian.org/382190
http://bugs.debian.org/378596
* python-imaging-sane: Depend on python-numarray. Closes: #382190.
* Add dependencies on ${shlibs:Depends}, lost in -6. Closes: #378596.

Show diffs side-by-side

added added

removed removed

Lines of Context:
libImaging/GetBBox.c
1
1
/* 
2
2
 * The Python Imaging Library
3
 
 * $Id: //modules/pil/libImaging/GetBBox.c#4 $
 
3
 * $Id: GetBBox.c 2298 2005-02-17 21:17:29Z fredrik $
4
4
 *
5
 
 * get bounding box for image
 
5
 * helpers to bounding boxes, min/max values, number of colors, etc.
6
6
 *
7
7
 * history:
8
8
 * 1996-07-22 fl   Created
9
9
 * 1996-12-30 fl   Added projection stuff
10
10
 * 1998-07-12 fl   Added extrema stuff
 
11
 * 2004-09-17 fl   Added colors stuff
11
12
 *
12
 
 * Copyright (c) 1997-2003 by Secret Labs AB.
13
 
 * Copyright (c) 1996-2003 by Fredrik Lundh.
 
13
 * Copyright (c) 1997-2004 by Secret Labs AB.
 
14
 * Copyright (c) 1996-2004 by Fredrik Lundh.
14
15
 *
15
16
 * See the README file for details on usage and redistribution.
16
17
 */
104
105
}
105
106
 
106
107
 
107
 
 
108
108
int
109
109
ImagingGetExtrema(Imaging im, void *extrema)
110
110
{
186
186
    }
187
187
    return 1; /* ok */
188
188
}
 
189
 
 
190
 
 
191
/* static ImagingColorItem* getcolors8(Imaging im, int maxcolors, int* size);*/
 
192
static ImagingColorItem* getcolors32(Imaging im, int maxcolors, int* size);
 
193
 
 
194
ImagingColorItem*
 
195
ImagingGetColors(Imaging im, int maxcolors, int* size)
 
196
{
 
197
    /* FIXME: add support for 8-bit images */
 
198
    return getcolors32(im, maxcolors, size);
 
199
}
 
200
 
 
201
static ImagingColorItem*
 
202
getcolors32(Imaging im, int maxcolors, int* size)
 
203
{
 
204
    unsigned int h;
 
205
    unsigned int i, incr;
 
206
    int colors;
 
207
    INT32 pixel_mask;
 
208
    int x, y;
 
209
    ImagingColorItem* table;
 
210
    ImagingColorItem* v;
 
211
 
 
212
    unsigned int code_size;
 
213
    unsigned int code_poly;
 
214
    unsigned int code_mask;
 
215
 
 
216
    /* note: the hash algorithm used here is based on the dictionary
 
217
       code in Python 2.1.3; the exact implementation is borrowed from
 
218
       Python's Unicode property database (written by yours truly) /F */
 
219
 
 
220
    static int SIZES[] = {
 
221
        4,3, 8,3, 16,3, 32,5, 64,3, 128,3, 256,29, 512,17, 1024,9, 2048,5,
 
222
        4096,83, 8192,27, 16384,43, 32768,3, 65536,45, 131072,9, 262144,39,
 
223
        524288,39, 1048576,9, 2097152,5, 4194304,3, 8388608,33, 16777216,27,
 
224
        33554432,9, 67108864,71, 134217728,39, 268435456,9, 536870912,5,
 
225
        1073741824,83, 0
 
226
    };
 
227
    
 
228
    code_size = code_poly = code_mask = 0;
 
229
 
 
230
    for (i = 0; SIZES[i]; i += 2) {
 
231
        if (SIZES[i] > maxcolors) {
 
232
            code_size = SIZES[i];
 
233
            code_poly = SIZES[i+1];
 
234
            code_mask = code_size - 1;
 
235
            break;
 
236
        }
 
237
    }
 
238
 
 
239
    /* printf("code_size=%d\n", code_size); */
 
240
    /* printf("code_poly=%d\n", code_poly); */
 
241
 
 
242
    if (!code_size) {
 
243
        ImagingError_MemoryError(); /* just give up */
 
244
        return NULL;
 
245
    }
 
246
 
 
247
    if (!im->image32) {
 
248
        ImagingError_ModeError();
 
249
        return NULL;
 
250
    }
 
251
 
 
252
    table = calloc(code_size + 1, sizeof(ImagingColorItem));
 
253
    if (!table) {
 
254
        ImagingError_MemoryError();
 
255
        return NULL;
 
256
    }
 
257
 
 
258
    pixel_mask = 0xffffffff;
 
259
    if (im->bands == 3)
 
260
        ((UINT8*) &pixel_mask)[3] = 0;
 
261
 
 
262
    colors = 0;
 
263
 
 
264
    for (y = 0; y < im->ysize; y++) {
 
265
        INT32* p = im->image32[y];
 
266
        for (x = 0; x < im->xsize; x++) {
 
267
            INT32 pixel = p[x] & pixel_mask;
 
268
            h = (pixel); /* null hashing */
 
269
            i = (~h) & code_mask;
 
270
            v = &table[i];
 
271
            if (!v->count) {
 
272
                /* add to table */
 
273
                if (colors++ == maxcolors)
 
274
                    goto overflow;
 
275
                v->x = x; v->y = y;
 
276
                v->pixel = pixel;
 
277
                v->count = 1;
 
278
                continue;
 
279
            } else if (v->pixel == pixel) {
 
280
                v->count++;
 
281
                continue;
 
282
            }
 
283
            incr = (h ^ (h >> 3)) & code_mask;
 
284
            if (!incr)
 
285
                incr = code_mask;
 
286
            for (;;) {
 
287
                i = (i + incr) & code_mask;
 
288
                v = &table[i];
 
289
                if (!v->count) {
 
290
                    /* add to table */
 
291
                    if (colors++ == maxcolors)
 
292
                        goto overflow;
 
293
                    v->x = x; v->y = y;
 
294
                    v->pixel = pixel;
 
295
                    v->count = 1;
 
296
                    break;
 
297
                } else if (v->pixel == pixel) {
 
298
                    v->count++;
 
299
                    break;
 
300
                }
 
301
                incr = incr << 1;
 
302
                if (incr > code_mask)
 
303
                    incr = incr ^ code_poly;
 
304
            }
 
305
        }
 
306
    }
 
307
 
 
308
overflow:
 
309
 
 
310
    /* pack the table */
 
311
    for (x = y = 0; x < (int) code_size; x++)
 
312
        if (table[x].count) {
 
313
            if (x != y)
 
314
                table[y] = table[x];
 
315
            y++;
 
316
        }
 
317
    table[y].count = 0; /* mark end of table */
 
318
 
 
319
    *size = colors;
 
320
 
 
321
    return table;
 
322
}