diff options
Diffstat (limited to 'Imaging/libImaging/Palette.c')
| -rw-r--r-- | Imaging/libImaging/Palette.c | 316 |
1 files changed, 316 insertions, 0 deletions
diff --git a/Imaging/libImaging/Palette.c b/Imaging/libImaging/Palette.c new file mode 100644 index 0000000..02e9e4f --- /dev/null +++ b/Imaging/libImaging/Palette.c @@ -0,0 +1,316 @@ +/* + * The Python Imaging Library + * $Id: Palette.c 2591 2005-12-08 21:25:29Z fredrik $ + * + * imaging palette object + * + * history: + * 1996-05-05 fl Added to library + * 1996-05-27 fl Added colour mapping stuff + * 1997-05-12 fl Support RGBA palettes + * 2005-02-09 fl Removed grayscale entries from web palette + * + * Copyright (c) Secret Labs AB 1997-2005. All rights reserved. + * Copyright (c) Fredrik Lundh 1995-1997. + * + * See the README file for information on usage and redistribution. + */ + + +#include "Imaging.h" + +#include <math.h> + + +ImagingPalette +ImagingPaletteNew(const char* mode) +{ + /* Create a palette object */ + + int i; + ImagingPalette palette; + + if (strcmp(mode, "RGB") && strcmp(mode, "RGBA")) + return (ImagingPalette) ImagingError_ModeError(); + + palette = calloc(1, sizeof(struct ImagingPaletteInstance)); + if (!palette) + return (ImagingPalette) ImagingError_MemoryError(); + + strcpy(palette->mode, mode); + + /* Initialize to ramp */ + for (i = 0; i < 256; i++) { + palette->palette[i*4+0] = + palette->palette[i*4+1] = + palette->palette[i*4+2] = (UINT8) i; + palette->palette[i*4+3] = 255; /* opaque */ + } + + return palette; +} + +ImagingPalette +ImagingPaletteNewBrowser(void) +{ + /* Create a standard "browser" palette object */ + + int i, r, g, b; + ImagingPalette palette; + + palette = ImagingPaletteNew("RGB"); + if (!palette) + return NULL; + + /* Blank out unused entries */ + /* FIXME: Add 10-level windows palette here? */ + + for (i = 0; i < 10; i++) { + palette->palette[i*4+0] = + palette->palette[i*4+1] = + palette->palette[i*4+2] = 0; + } + + /* Simple 6x6x6 colour cube */ + + for (b = 0; b < 256; b += 51) + for (g = 0; g < 256; g += 51) + for (r = 0; r < 256; r += 51) { + palette->palette[i*4+0] = r; + palette->palette[i*4+1] = g; + palette->palette[i*4+2] = b; + i++; + } + + /* Blank out unused entries */ + /* FIXME: add 30-level greyscale wedge here? */ + + for (; i < 256; i++) { + palette->palette[i*4+0] = + palette->palette[i*4+1] = + palette->palette[i*4+2] = 0; + } + + return palette; +} + +ImagingPalette +ImagingPaletteDuplicate(ImagingPalette palette) +{ + /* Duplicate palette descriptor */ + + ImagingPalette new_palette; + + if (!palette) + return NULL; + + new_palette = malloc(sizeof(struct ImagingPaletteInstance)); + if (!new_palette) + return (ImagingPalette) ImagingError_MemoryError(); + + memcpy(new_palette, palette, sizeof(struct ImagingPaletteInstance)); + + /* Don't share the cache */ + new_palette->cache = NULL; + + return new_palette; +} + +void +ImagingPaletteDelete(ImagingPalette palette) +{ + /* Destroy palette object */ + + if (palette) { + if (palette->cache) + free(palette->cache); + free(palette); + } +} + + +/* -------------------------------------------------------------------- */ +/* Colour mapping */ +/* -------------------------------------------------------------------- */ + +/* This code is used to map RGB triplets to palette indices, using + a palette index cache. */ + +/* + * This implementation is loosely based on the corresponding code in + * the IJG JPEG library by Thomas G. Lane. Original algorithms by + * Paul Heckbert and Spencer W. Thomas. + * + * The IJG JPEG library is copyright (C) 1991-1995, Thomas G. Lane. */ + +#define DIST(a, b, s) (a - b) * (a - b) * s + +/* Colour weights (no scaling, for now) */ +#define RSCALE 1 +#define GSCALE 1 +#define BSCALE 1 + +/* Calculated scaled distances */ +#define RDIST(a, b) DIST(a, b, RSCALE*RSCALE) +#define GDIST(a, b) DIST(a, b, GSCALE*GSCALE) +#define BDIST(a, b) DIST(a, b, BSCALE*BSCALE) + +/* Incremental steps */ +#define RSTEP (4 * RSCALE) +#define GSTEP (4 * GSCALE) +#define BSTEP (4 * BSCALE) + +#define BOX 8 + +#define BOXVOLUME BOX*BOX*BOX + +void +ImagingPaletteCacheUpdate(ImagingPalette palette, int r, int g, int b) +{ + int i, j; + unsigned int dmin[256], dmax; + int r0, g0, b0; + int r1, g1, b1; + int rc, gc, bc; + unsigned int d[BOXVOLUME]; + UINT8 c[BOXVOLUME]; + + /* Get box boundaries for the given (r,g,b)-triplet. Each box + covers eight cache slots (32 colour values, that is). */ + + r0 = r & 0xe0; r1 = r0 + 0x1f; rc = (r0 + r1) / 2; + g0 = g & 0xe0; g1 = g0 + 0x1f; gc = (g0 + g1) / 2; + b0 = b & 0xe0; b1 = b0 + 0x1f; bc = (b0 + b1) / 2; + + /* Step 1 -- Select relevant palette entries (after Heckbert) */ + + /* For each palette entry, calculate the min and max distances to + * any position in the box given by the colour we're looking for. */ + + dmax = (unsigned int) ~0; + + for (i = 0; i < 256; i++) { + + int r, g, b; + unsigned int tmin, tmax; + + /* Find min and max distances to any point in the box */ + r = palette->palette[i*4+0]; + tmin = (r < r0) ? RDIST(r, r1) : (r > r1) ? RDIST(r, r0) : 0; + tmax = (r <= rc) ? RDIST(r, r1) : RDIST(r, r0); + + g = palette->palette[i*4+1]; + tmin += (g < g0) ? GDIST(g, g1) : (g > g1) ? GDIST(g, g0) : 0; + tmax += (g <= gc) ? GDIST(g, g1) : GDIST(g, g0); + + b = palette->palette[i*4+2]; + tmin += (b < b0) ? BDIST(b, b1) : (b > b1) ? BDIST(b, b0) : 0; + tmax += (b <= bc) ? BDIST(b, b1) : BDIST(b, b0); + + dmin[i] = tmin; + if (tmax < dmax) + dmax = tmax; /* keep the smallest max distance only */ + + } + + /* Step 2 -- Incrementally update cache slot (after Thomas) */ + + /* Find the box containing the nearest palette entry, and update + * all slots in that box. We only check boxes for which the min + * distance is less than or equal the smallest max distance */ + + for (i = 0; i < BOXVOLUME; i++) + d[i] = (unsigned int) ~0; + + for (i = 0; i < 256; i++) + + if (dmin[i] <= dmax) { + + int rd, gd, bd; + int ri, gi, bi; + int rx, gx, bx; + + ri = (r0 - palette->palette[i*4+0]) * RSCALE; + gi = (g0 - palette->palette[i*4+1]) * GSCALE; + bi = (b0 - palette->palette[i*4+2]) * BSCALE; + + rd = ri*ri + gi*gi + bi*bi; + + ri = ri * (2 * RSTEP) + RSTEP * RSTEP; + gi = gi * (2 * GSTEP) + GSTEP * GSTEP; + bi = bi * (2 * BSTEP) + BSTEP * BSTEP; + + rx = ri; + for (r = j = 0; r < BOX; r++) { + gd = rd; gx = gi; + for (g = 0; g < BOX; g++) { + bd = gd; bx = bi; + for (b = 0; b < BOX; b++) { + if ((unsigned int) bd < d[j]) { + d[j] = bd; + c[j] = (UINT8) i; + } + bd += bx; + bx += 2 * BSTEP * BSTEP; + j++; + } + gd += gx; + gx += 2 * GSTEP * GSTEP; + } + rd += rx; + rx += 2 * RSTEP * RSTEP; + } + } + + /* Step 3 -- Update cache */ + + /* The c array now contains the closest match for each + * cache slot in the box. Update the cache. */ + + j = 0; + for (r = r0; r < r1; r+=4) + for (g = g0; g < g1; g+=4) + for (b = b0; b < b1; b+=4) + ImagingPaletteCache(palette, r, g, b) = c[j++]; +} + + +int +ImagingPaletteCachePrepare(ImagingPalette palette) +{ + /* Add a colour cache to a palette */ + + int i; + int entries = 64*64*64; + + if (palette->cache == NULL) { + + /* The cache is 512k. It might be a good idea to break it + up into a pointer array (e.g. an 8-bit image?) */ + + palette->cache = (INT16*) malloc(entries * sizeof(INT16)); + if (!palette->cache) { + ImagingError_MemoryError(); + return -1; + } + + /* Mark all entries as empty */ + for (i = 0; i < entries; i++) + palette->cache[i] = 0x100; + + } + + return 0; +} + + +void +ImagingPaletteCacheDelete(ImagingPalette palette) +{ + /* Release the colour cache, if any */ + + if (palette && palette->cache) { + free(palette->cache); + palette->cache = NULL; + } +} |