1e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett/***************************************************************************** 2e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 3e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett quantize.c - quantize a high resolution image into lower one 4e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 5e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Based on: "Color Image Quantization for frame buffer Display", by 6e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Paul Heckbert SIGGRAPH 1982 page 297-307. 7e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 8e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett This doesn't really belong in the core library, was undocumented, 9e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett and was removed in 4.2. Then it turned out some client apps were 10e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett actually using it, so it was restored in 5.0. 11e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 12e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett******************************************************************************/ 13e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 14e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett#include <stdlib.h> 15e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett#include <stdio.h> 16e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett#include "gif_lib.h" 17e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett#include "gif_lib_private.h" 18e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 19e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett#define ABS(x) ((x) > 0 ? (x) : (-(x))) 20e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 21e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett#define COLOR_ARRAY_SIZE 32768 22e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett#define BITS_PER_PRIM_COLOR 5 23e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett#define MAX_PRIM_COLOR 0x1f 24e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 25e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarettstatic int SortRGBAxis; 26e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 27e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Saretttypedef struct QuantizedColorType { 28e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett GifByteType RGB[3]; 29e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett GifByteType NewColorIndex; 30e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett long Count; 31e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett struct QuantizedColorType *Pnext; 32e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett} QuantizedColorType; 33e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 34e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Saretttypedef struct NewColorMapType { 35e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett GifByteType RGBMin[3], RGBWidth[3]; 36e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett unsigned int NumEntries; /* # of QuantizedColorType in linked list below */ 37e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett unsigned long Count; /* Total number of pixels in all the entries */ 38e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett QuantizedColorType *QuantizedColors; 39e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett} NewColorMapType; 40e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 41e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarettstatic int SubdivColorMap(NewColorMapType * NewColorSubdiv, 42e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett unsigned int ColorMapSize, 43e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett unsigned int *NewColorMapSize); 44e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarettstatic int SortCmpRtn(const void *Entry1, const void *Entry2); 45e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 46e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett/****************************************************************************** 47e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Quantize high resolution image into lower one. Input image consists of a 48e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 2D array for each of the RGB colors with size Width by Height. There is no 49e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Color map for the input. Output is a quantized image with 2D array of 50e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett indexes into the output color map. 51e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Note input image can be 24 bits at the most (8 for red/green/blue) and 52e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett the output has 256 colors at the most (256 entries in the color map.). 53e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett ColorMapSize specifies size of color map up to 256 and will be updated to 54e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett real size before returning. 55e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Also non of the parameter are allocated by this routine. 56e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett This function returns GIF_OK if successful, GIF_ERROR otherwise. 57e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett******************************************************************************/ 58e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarettint 59e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt SarettGifQuantizeBuffer(unsigned int Width, 60e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett unsigned int Height, 61e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett int *ColorMapSize, 62e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett GifByteType * RedInput, 63e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett GifByteType * GreenInput, 64e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett GifByteType * BlueInput, 65e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett GifByteType * OutputBuffer, 66e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett GifColorType * OutputColorMap) { 67e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 68e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett unsigned int Index, NumOfEntries; 69e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett int i, j, MaxRGBError[3]; 70e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett unsigned int NewColorMapSize; 71e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett long Red, Green, Blue; 72e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorMapType NewColorSubdiv[256]; 73e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett QuantizedColorType *ColorArrayEntries, *QuantizedColor; 74e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 75e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett ColorArrayEntries = (QuantizedColorType *)malloc( 76e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett sizeof(QuantizedColorType) * COLOR_ARRAY_SIZE); 77e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett if (ColorArrayEntries == NULL) { 78e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett return GIF_ERROR; 79e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 80e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 81e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett for (i = 0; i < COLOR_ARRAY_SIZE; i++) { 82e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett ColorArrayEntries[i].RGB[0] = i >> (2 * BITS_PER_PRIM_COLOR); 83e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett ColorArrayEntries[i].RGB[1] = (i >> BITS_PER_PRIM_COLOR) & 84e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett MAX_PRIM_COLOR; 85e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett ColorArrayEntries[i].RGB[2] = i & MAX_PRIM_COLOR; 86e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett ColorArrayEntries[i].Count = 0; 87e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 88e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 89e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett /* Sample the colors and their distribution: */ 90e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett for (i = 0; i < (int)(Width * Height); i++) { 91e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Index = ((RedInput[i] >> (8 - BITS_PER_PRIM_COLOR)) << 92e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett (2 * BITS_PER_PRIM_COLOR)) + 93e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett ((GreenInput[i] >> (8 - BITS_PER_PRIM_COLOR)) << 94e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett BITS_PER_PRIM_COLOR) + 95e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett (BlueInput[i] >> (8 - BITS_PER_PRIM_COLOR)); 96e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett ColorArrayEntries[Index].Count++; 97e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 98e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 99e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett /* Put all the colors in the first entry of the color map, and call the 100e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett * recursive subdivision process. */ 101e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett for (i = 0; i < 256; i++) { 102e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[i].QuantizedColors = NULL; 103e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[i].Count = NewColorSubdiv[i].NumEntries = 0; 104e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett for (j = 0; j < 3; j++) { 105e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[i].RGBMin[j] = 0; 106e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[i].RGBWidth[j] = 255; 107e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 108e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 109e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 110e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett /* Find the non empty entries in the color table and chain them: */ 111e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett for (i = 0; i < COLOR_ARRAY_SIZE; i++) 112e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett if (ColorArrayEntries[i].Count > 0) 113e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett break; 114e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett QuantizedColor = NewColorSubdiv[0].QuantizedColors = &ColorArrayEntries[i]; 115e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NumOfEntries = 1; 116e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett while (++i < COLOR_ARRAY_SIZE) 117e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett if (ColorArrayEntries[i].Count > 0) { 118e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett QuantizedColor->Pnext = &ColorArrayEntries[i]; 119e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett QuantizedColor = &ColorArrayEntries[i]; 120e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NumOfEntries++; 121e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 122e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett QuantizedColor->Pnext = NULL; 123e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 124e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[0].NumEntries = NumOfEntries; /* Different sampled colors */ 125e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[0].Count = ((long)Width) * Height; /* Pixels */ 126e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorMapSize = 1; 127e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett if (SubdivColorMap(NewColorSubdiv, *ColorMapSize, &NewColorMapSize) != 128e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett GIF_OK) { 129e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett free((char *)ColorArrayEntries); 130e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett return GIF_ERROR; 131e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 132e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett if (NewColorMapSize < *ColorMapSize) { 133e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett /* And clear rest of color map: */ 134e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett for (i = NewColorMapSize; i < *ColorMapSize; i++) 135e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett OutputColorMap[i].Red = OutputColorMap[i].Green = 136e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett OutputColorMap[i].Blue = 0; 137e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 138e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 139e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett /* Average the colors in each entry to be the color to be used in the 140e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett * output color map, and plug it into the output color map itself. */ 141e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett for (i = 0; i < NewColorMapSize; i++) { 142e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett if ((j = NewColorSubdiv[i].NumEntries) > 0) { 143e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett QuantizedColor = NewColorSubdiv[i].QuantizedColors; 144e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Red = Green = Blue = 0; 145e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett while (QuantizedColor) { 146e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett QuantizedColor->NewColorIndex = i; 147e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Red += QuantizedColor->RGB[0]; 148e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Green += QuantizedColor->RGB[1]; 149e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Blue += QuantizedColor->RGB[2]; 150e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett QuantizedColor = QuantizedColor->Pnext; 151e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 152e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett OutputColorMap[i].Red = (Red << (8 - BITS_PER_PRIM_COLOR)) / j; 153e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett OutputColorMap[i].Green = (Green << (8 - BITS_PER_PRIM_COLOR)) / j; 154e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett OutputColorMap[i].Blue = (Blue << (8 - BITS_PER_PRIM_COLOR)) / j; 155e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 156e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 157e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 158e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett /* Finally scan the input buffer again and put the mapped index in the 159e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett * output buffer. */ 160e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett MaxRGBError[0] = MaxRGBError[1] = MaxRGBError[2] = 0; 161e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett for (i = 0; i < (int)(Width * Height); i++) { 162e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Index = ((RedInput[i] >> (8 - BITS_PER_PRIM_COLOR)) << 163e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett (2 * BITS_PER_PRIM_COLOR)) + 164e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett ((GreenInput[i] >> (8 - BITS_PER_PRIM_COLOR)) << 165e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett BITS_PER_PRIM_COLOR) + 166e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett (BlueInput[i] >> (8 - BITS_PER_PRIM_COLOR)); 167e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Index = ColorArrayEntries[Index].NewColorIndex; 168e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett OutputBuffer[i] = Index; 169e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett if (MaxRGBError[0] < ABS(OutputColorMap[Index].Red - RedInput[i])) 170e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett MaxRGBError[0] = ABS(OutputColorMap[Index].Red - RedInput[i]); 171e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett if (MaxRGBError[1] < ABS(OutputColorMap[Index].Green - GreenInput[i])) 172e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett MaxRGBError[1] = ABS(OutputColorMap[Index].Green - GreenInput[i]); 173e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett if (MaxRGBError[2] < ABS(OutputColorMap[Index].Blue - BlueInput[i])) 174e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett MaxRGBError[2] = ABS(OutputColorMap[Index].Blue - BlueInput[i]); 175e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 176e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 177e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett#ifdef DEBUG 178e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett fprintf(stderr, 179e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett "Quantization L(0) errors: Red = %d, Green = %d, Blue = %d.\n", 180e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett MaxRGBError[0], MaxRGBError[1], MaxRGBError[2]); 181e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett#endif /* DEBUG */ 182e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 183e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett free((char *)ColorArrayEntries); 184e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 185e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett *ColorMapSize = NewColorMapSize; 186e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 187e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett return GIF_OK; 188e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett} 189e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 190e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett/****************************************************************************** 191e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Routine to subdivide the RGB space recursively using median cut in each 192e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett axes alternatingly until ColorMapSize different cubes exists. 193e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett The biggest cube in one dimension is subdivide unless it has only one entry. 194e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Returns GIF_ERROR if failed, otherwise GIF_OK. 195e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett*******************************************************************************/ 196e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarettstatic int 197e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt SarettSubdivColorMap(NewColorMapType * NewColorSubdiv, 198e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett unsigned int ColorMapSize, 199e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett unsigned int *NewColorMapSize) { 200e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 201e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett int MaxSize; 202e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett unsigned int i, j, Index = 0, NumEntries, MinColor, MaxColor; 203e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett long Sum, Count; 204e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett QuantizedColorType *QuantizedColor, **SortArray; 205e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 206e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett while (ColorMapSize > *NewColorMapSize) { 207e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett /* Find candidate for subdivision: */ 208e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett MaxSize = -1; 209e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett for (i = 0; i < *NewColorMapSize; i++) { 210e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett for (j = 0; j < 3; j++) { 211e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett if ((((int)NewColorSubdiv[i].RGBWidth[j]) > MaxSize) && 212e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett (NewColorSubdiv[i].NumEntries > 1)) { 213e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett MaxSize = NewColorSubdiv[i].RGBWidth[j]; 214e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Index = i; 215e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett SortRGBAxis = j; 216e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 217e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 218e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 219e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 220e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett if (MaxSize == -1) 221e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett return GIF_OK; 222e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 223e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett /* Split the entry Index into two along the axis SortRGBAxis: */ 224e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 225e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett /* Sort all elements in that entry along the given axis and split at 226e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett * the median. */ 227e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett SortArray = (QuantizedColorType **)malloc( 228e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett sizeof(QuantizedColorType *) * 229e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[Index].NumEntries); 230e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett if (SortArray == NULL) 231e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett return GIF_ERROR; 232e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett for (j = 0, QuantizedColor = NewColorSubdiv[Index].QuantizedColors; 233e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett j < NewColorSubdiv[Index].NumEntries && QuantizedColor != NULL; 234e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett j++, QuantizedColor = QuantizedColor->Pnext) 235e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett SortArray[j] = QuantizedColor; 236e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 237e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett /* 238e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett * Because qsort isn't stable, this can produce differing 239e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett * results for the order of tuples depending on platform 240e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett * details of how qsort() is implemented. 241e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett * 242e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett * We mitigate this problem by sorting on all three axes rather 243e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett * than only the one specied by SortRGBAxis; that way the instability 244e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett * can only become an issue if there are multiple color indices 245e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett * referring to identical RGB tuples. Older versions of this 246e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett * sorted on only the one axis. 247e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett */ 248e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett qsort(SortArray, NewColorSubdiv[Index].NumEntries, 249e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett sizeof(QuantizedColorType *), SortCmpRtn); 250e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 251e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett /* Relink the sorted list into one: */ 252e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett for (j = 0; j < NewColorSubdiv[Index].NumEntries - 1; j++) 253e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett SortArray[j]->Pnext = SortArray[j + 1]; 254e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett SortArray[NewColorSubdiv[Index].NumEntries - 1]->Pnext = NULL; 255e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[Index].QuantizedColors = QuantizedColor = SortArray[0]; 256e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett free((char *)SortArray); 257e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 258e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett /* Now simply add the Counts until we have half of the Count: */ 259e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Sum = NewColorSubdiv[Index].Count / 2 - QuantizedColor->Count; 260e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NumEntries = 1; 261e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Count = QuantizedColor->Count; 262e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett while (QuantizedColor->Pnext != NULL && 263e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett (Sum -= QuantizedColor->Pnext->Count) >= 0 && 264e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett QuantizedColor->Pnext->Pnext != NULL) { 265e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett QuantizedColor = QuantizedColor->Pnext; 266e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NumEntries++; 267e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Count += QuantizedColor->Count; 268e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 269e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett /* Save the values of the last color of the first half, and first 270e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett * of the second half so we can update the Bounding Boxes later. 271e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett * Also as the colors are quantized and the BBoxes are full 0..255, 272e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett * they need to be rescaled. 273e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett */ 274e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett MaxColor = QuantizedColor->RGB[SortRGBAxis]; /* Max. of first half */ 275e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett /* coverity[var_deref_op] */ 276e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett MinColor = QuantizedColor->Pnext->RGB[SortRGBAxis]; /* of second */ 277e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett MaxColor <<= (8 - BITS_PER_PRIM_COLOR); 278e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett MinColor <<= (8 - BITS_PER_PRIM_COLOR); 279e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 280e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett /* Partition right here: */ 281e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[*NewColorMapSize].QuantizedColors = 282e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett QuantizedColor->Pnext; 283e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett QuantizedColor->Pnext = NULL; 284e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[*NewColorMapSize].Count = Count; 285e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[Index].Count -= Count; 286e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[*NewColorMapSize].NumEntries = 287e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[Index].NumEntries - NumEntries; 288e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[Index].NumEntries = NumEntries; 289e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett for (j = 0; j < 3; j++) { 290e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[*NewColorMapSize].RGBMin[j] = 291e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[Index].RGBMin[j]; 292e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[*NewColorMapSize].RGBWidth[j] = 293e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[Index].RGBWidth[j]; 294e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 295e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[*NewColorMapSize].RGBWidth[SortRGBAxis] = 296e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[*NewColorMapSize].RGBMin[SortRGBAxis] + 297e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[*NewColorMapSize].RGBWidth[SortRGBAxis] - MinColor; 298e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[*NewColorMapSize].RGBMin[SortRGBAxis] = MinColor; 299e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 300e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett NewColorSubdiv[Index].RGBWidth[SortRGBAxis] = 301e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett MaxColor - NewColorSubdiv[Index].RGBMin[SortRGBAxis]; 302e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 303e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett (*NewColorMapSize)++; 304e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett } 305e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 306e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett return GIF_OK; 307e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett} 308e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 309e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett/**************************************************************************** 310e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett Routine called by qsort to compare two entries. 311e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett*****************************************************************************/ 312e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 313e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarettstatic int 314e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt SarettSortCmpRtn(const void *Entry1, 315e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett const void *Entry2) { 316e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett QuantizedColorType *entry1 = (*((QuantizedColorType **) Entry1)); 317e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett QuantizedColorType *entry2 = (*((QuantizedColorType **) Entry2)); 318e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 319e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett /* sort on all axes of the color space! */ 320e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett int hash1 = entry1->RGB[SortRGBAxis] * 256 * 256 321e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett + entry1->RGB[(SortRGBAxis+1) % 3] * 256 322e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett + entry1->RGB[(SortRGBAxis+2) % 3]; 323e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett int hash2 = entry2->RGB[SortRGBAxis] * 256 * 256 324e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett + entry2->RGB[(SortRGBAxis+1) % 3] * 256 325e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett + entry2->RGB[(SortRGBAxis+2) % 3]; 326e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 327e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett return hash1 - hash2; 328e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett} 329e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett 330e189ac98c1d4e339fd0327aae046f908e22fa1bcMatt Sarett/* end */ 331