19b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot/***************************************************************************** 29b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 39b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot quantize.c - quantize a high resolution image into lower one 49b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 59b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Based on: "Color Image Quantization for frame buffer Display", by 69b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Paul Heckbert SIGGRAPH 1982 page 297-307. 79b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 89b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot This doesn't really belong in the core library, was undocumented, 99b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot and was removed in 4.2. Then it turned out some client apps were 109b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot actually using it, so it was restored in 5.0. 119b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 129b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot******************************************************************************/ 139b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 149b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#include <stdlib.h> 159b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#include <stdio.h> 169b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#include "gif_lib.h" 179b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#include "gif_lib_private.h" 189b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 199b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#define ABS(x) ((x) > 0 ? (x) : (-(x))) 209b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 219b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#define COLOR_ARRAY_SIZE 32768 229b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#define BITS_PER_PRIM_COLOR 5 239b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#define MAX_PRIM_COLOR 0x1f 249b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 259b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfootstatic int SortRGBAxis; 269b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 279b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoottypedef struct QuantizedColorType { 289b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot GifByteType RGB[3]; 299b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot GifByteType NewColorIndex; 309b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot long Count; 319b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot struct QuantizedColorType *Pnext; 329b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot} QuantizedColorType; 339b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 349b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoottypedef struct NewColorMapType { 359b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot GifByteType RGBMin[3], RGBWidth[3]; 369b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot unsigned int NumEntries; /* # of QuantizedColorType in linked list below */ 379b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot unsigned long Count; /* Total number of pixels in all the entries */ 389b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot QuantizedColorType *QuantizedColors; 399b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot} NewColorMapType; 409b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 419b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfootstatic int SubdivColorMap(NewColorMapType * NewColorSubdiv, 429b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot unsigned int ColorMapSize, 439b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot unsigned int *NewColorMapSize); 449b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfootstatic int SortCmpRtn(const void *Entry1, const void *Entry2); 459b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 469b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot/****************************************************************************** 479b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Quantize high resolution image into lower one. Input image consists of a 489b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 2D array for each of the RGB colors with size Width by Height. There is no 499b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Color map for the input. Output is a quantized image with 2D array of 509b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot indexes into the output color map. 519b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Note input image can be 24 bits at the most (8 for red/green/blue) and 529b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot the output has 256 colors at the most (256 entries in the color map.). 539b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot ColorMapSize specifies size of color map up to 256 and will be updated to 549b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot real size before returning. 559b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Also non of the parameter are allocated by this routine. 569b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot This function returns GIF_OK if successful, GIF_ERROR otherwise. 579b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot******************************************************************************/ 589b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfootint 599b8f8602a74a943ddc356bb11c55b4998b2b386dKeith PlatfootGifQuantizeBuffer(unsigned int Width, 609b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot unsigned int Height, 619b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot int *ColorMapSize, 629b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot GifByteType * RedInput, 639b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot GifByteType * GreenInput, 649b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot GifByteType * BlueInput, 659b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot GifByteType * OutputBuffer, 669b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot GifColorType * OutputColorMap) { 679b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 689b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot unsigned int Index, NumOfEntries; 699b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot int i, j, MaxRGBError[3]; 709b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot unsigned int NewColorMapSize; 719b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot long Red, Green, Blue; 729b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorMapType NewColorSubdiv[256]; 739b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot QuantizedColorType *ColorArrayEntries, *QuantizedColor; 749b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 759b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot ColorArrayEntries = (QuantizedColorType *)malloc( 769b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot sizeof(QuantizedColorType) * COLOR_ARRAY_SIZE); 779b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot if (ColorArrayEntries == NULL) { 789b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot return GIF_ERROR; 799b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 809b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 819b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot for (i = 0; i < COLOR_ARRAY_SIZE; i++) { 829b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot ColorArrayEntries[i].RGB[0] = i >> (2 * BITS_PER_PRIM_COLOR); 839b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot ColorArrayEntries[i].RGB[1] = (i >> BITS_PER_PRIM_COLOR) & 849b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot MAX_PRIM_COLOR; 859b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot ColorArrayEntries[i].RGB[2] = i & MAX_PRIM_COLOR; 869b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot ColorArrayEntries[i].Count = 0; 879b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 889b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 899b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot /* Sample the colors and their distribution: */ 909b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot for (i = 0; i < (int)(Width * Height); i++) { 919b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Index = ((RedInput[i] >> (8 - BITS_PER_PRIM_COLOR)) << 929b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot (2 * BITS_PER_PRIM_COLOR)) + 939b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot ((GreenInput[i] >> (8 - BITS_PER_PRIM_COLOR)) << 949b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot BITS_PER_PRIM_COLOR) + 959b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot (BlueInput[i] >> (8 - BITS_PER_PRIM_COLOR)); 969b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot ColorArrayEntries[Index].Count++; 979b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 989b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 999b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot /* Put all the colors in the first entry of the color map, and call the 1009b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot * recursive subdivision process. */ 1019b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot for (i = 0; i < 256; i++) { 1029b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[i].QuantizedColors = NULL; 1039b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[i].Count = NewColorSubdiv[i].NumEntries = 0; 1049b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot for (j = 0; j < 3; j++) { 1059b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[i].RGBMin[j] = 0; 1069b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[i].RGBWidth[j] = 255; 1079b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 1089b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 1099b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 1109b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot /* Find the non empty entries in the color table and chain them: */ 1119b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot for (i = 0; i < COLOR_ARRAY_SIZE; i++) 1129b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot if (ColorArrayEntries[i].Count > 0) 1139b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot break; 1149b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot QuantizedColor = NewColorSubdiv[0].QuantizedColors = &ColorArrayEntries[i]; 1159b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NumOfEntries = 1; 1169b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot while (++i < COLOR_ARRAY_SIZE) 1179b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot if (ColorArrayEntries[i].Count > 0) { 1189b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot QuantizedColor->Pnext = &ColorArrayEntries[i]; 1199b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot QuantizedColor = &ColorArrayEntries[i]; 1209b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NumOfEntries++; 1219b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 1229b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot QuantizedColor->Pnext = NULL; 1239b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 1249b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[0].NumEntries = NumOfEntries; /* Different sampled colors */ 1259b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[0].Count = ((long)Width) * Height; /* Pixels */ 1269b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorMapSize = 1; 1279b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot if (SubdivColorMap(NewColorSubdiv, *ColorMapSize, &NewColorMapSize) != 1289b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot GIF_OK) { 1299b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot free((char *)ColorArrayEntries); 1309b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot return GIF_ERROR; 1319b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 1329b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot if (NewColorMapSize < *ColorMapSize) { 1339b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot /* And clear rest of color map: */ 1349b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot for (i = NewColorMapSize; i < *ColorMapSize; i++) 1359b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot OutputColorMap[i].Red = OutputColorMap[i].Green = 1369b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot OutputColorMap[i].Blue = 0; 1379b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 1389b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 1399b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot /* Average the colors in each entry to be the color to be used in the 1409b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot * output color map, and plug it into the output color map itself. */ 1419b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot for (i = 0; i < NewColorMapSize; i++) { 1429b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot if ((j = NewColorSubdiv[i].NumEntries) > 0) { 1439b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot QuantizedColor = NewColorSubdiv[i].QuantizedColors; 1449b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Red = Green = Blue = 0; 1459b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot while (QuantizedColor) { 1469b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot QuantizedColor->NewColorIndex = i; 1479b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Red += QuantizedColor->RGB[0]; 1489b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Green += QuantizedColor->RGB[1]; 1499b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Blue += QuantizedColor->RGB[2]; 1509b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot QuantizedColor = QuantizedColor->Pnext; 1519b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 1529b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot OutputColorMap[i].Red = (Red << (8 - BITS_PER_PRIM_COLOR)) / j; 1539b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot OutputColorMap[i].Green = (Green << (8 - BITS_PER_PRIM_COLOR)) / j; 1549b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot OutputColorMap[i].Blue = (Blue << (8 - BITS_PER_PRIM_COLOR)) / j; 1559b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 1569b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 1579b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 1589b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot /* Finally scan the input buffer again and put the mapped index in the 1599b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot * output buffer. */ 1609b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot MaxRGBError[0] = MaxRGBError[1] = MaxRGBError[2] = 0; 1619b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot for (i = 0; i < (int)(Width * Height); i++) { 1629b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Index = ((RedInput[i] >> (8 - BITS_PER_PRIM_COLOR)) << 1639b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot (2 * BITS_PER_PRIM_COLOR)) + 1649b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot ((GreenInput[i] >> (8 - BITS_PER_PRIM_COLOR)) << 1659b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot BITS_PER_PRIM_COLOR) + 1669b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot (BlueInput[i] >> (8 - BITS_PER_PRIM_COLOR)); 1679b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Index = ColorArrayEntries[Index].NewColorIndex; 1689b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot OutputBuffer[i] = Index; 1699b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot if (MaxRGBError[0] < ABS(OutputColorMap[Index].Red - RedInput[i])) 1709b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot MaxRGBError[0] = ABS(OutputColorMap[Index].Red - RedInput[i]); 1719b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot if (MaxRGBError[1] < ABS(OutputColorMap[Index].Green - GreenInput[i])) 1729b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot MaxRGBError[1] = ABS(OutputColorMap[Index].Green - GreenInput[i]); 1739b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot if (MaxRGBError[2] < ABS(OutputColorMap[Index].Blue - BlueInput[i])) 1749b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot MaxRGBError[2] = ABS(OutputColorMap[Index].Blue - BlueInput[i]); 1759b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 1769b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 1779b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#ifdef DEBUG 1789b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot fprintf(stderr, 1799b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot "Quantization L(0) errors: Red = %d, Green = %d, Blue = %d.\n", 1809b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot MaxRGBError[0], MaxRGBError[1], MaxRGBError[2]); 1819b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#endif /* DEBUG */ 1829b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 1839b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot free((char *)ColorArrayEntries); 1849b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 1859b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot *ColorMapSize = NewColorMapSize; 1869b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 1879b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot return GIF_OK; 1889b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot} 1899b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 1909b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot/****************************************************************************** 1919b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Routine to subdivide the RGB space recursively using median cut in each 1929b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot axes alternatingly until ColorMapSize different cubes exists. 1939b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot The biggest cube in one dimension is subdivide unless it has only one entry. 1949b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Returns GIF_ERROR if failed, otherwise GIF_OK. 1959b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot*******************************************************************************/ 1969b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfootstatic int 1979b8f8602a74a943ddc356bb11c55b4998b2b386dKeith PlatfootSubdivColorMap(NewColorMapType * NewColorSubdiv, 1989b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot unsigned int ColorMapSize, 1999b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot unsigned int *NewColorMapSize) { 2009b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 2019b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot int MaxSize; 2029b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot unsigned int i, j, Index = 0, NumEntries, MinColor, MaxColor; 2039b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot long Sum, Count; 2049b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot QuantizedColorType *QuantizedColor, **SortArray; 2059b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 2069b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot while (ColorMapSize > *NewColorMapSize) { 2079b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot /* Find candidate for subdivision: */ 2089b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot MaxSize = -1; 2099b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot for (i = 0; i < *NewColorMapSize; i++) { 2109b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot for (j = 0; j < 3; j++) { 2119b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot if ((((int)NewColorSubdiv[i].RGBWidth[j]) > MaxSize) && 2129b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot (NewColorSubdiv[i].NumEntries > 1)) { 2139b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot MaxSize = NewColorSubdiv[i].RGBWidth[j]; 2149b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Index = i; 2159b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot SortRGBAxis = j; 2169b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 2179b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 2189b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 2199b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 2209b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot if (MaxSize == -1) 2219b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot return GIF_OK; 2229b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 2239b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot /* Split the entry Index into two along the axis SortRGBAxis: */ 2249b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 2259b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot /* Sort all elements in that entry along the given axis and split at 2269b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot * the median. */ 2279b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot SortArray = (QuantizedColorType **)malloc( 2289b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot sizeof(QuantizedColorType *) * 2299b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[Index].NumEntries); 2309b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot if (SortArray == NULL) 2319b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot return GIF_ERROR; 2329b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot for (j = 0, QuantizedColor = NewColorSubdiv[Index].QuantizedColors; 2339b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot j < NewColorSubdiv[Index].NumEntries && QuantizedColor != NULL; 2349b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot j++, QuantizedColor = QuantizedColor->Pnext) 2359b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot SortArray[j] = QuantizedColor; 2369b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 2379b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot qsort(SortArray, NewColorSubdiv[Index].NumEntries, 2389b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot sizeof(QuantizedColorType *), SortCmpRtn); 2399b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 2409b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot /* Relink the sorted list into one: */ 2419b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot for (j = 0; j < NewColorSubdiv[Index].NumEntries - 1; j++) 2429b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot SortArray[j]->Pnext = SortArray[j + 1]; 2439b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot SortArray[NewColorSubdiv[Index].NumEntries - 1]->Pnext = NULL; 2449b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[Index].QuantizedColors = QuantizedColor = SortArray[0]; 2459b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot free((char *)SortArray); 2469b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 2479b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot /* Now simply add the Counts until we have half of the Count: */ 2489b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Sum = NewColorSubdiv[Index].Count / 2 - QuantizedColor->Count; 2499b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NumEntries = 1; 2509b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Count = QuantizedColor->Count; 2519b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot while (QuantizedColor->Pnext != NULL && 2529b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot (Sum -= QuantizedColor->Pnext->Count) >= 0 && 2539b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot QuantizedColor->Pnext->Pnext != NULL) { 2549b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot QuantizedColor = QuantizedColor->Pnext; 2559b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NumEntries++; 2569b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Count += QuantizedColor->Count; 2579b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 2589b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot /* Save the values of the last color of the first half, and first 2599b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot * of the second half so we can update the Bounding Boxes later. 2609b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot * Also as the colors are quantized and the BBoxes are full 0..255, 2619b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot * they need to be rescaled. 2629b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot */ 2639b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot MaxColor = QuantizedColor->RGB[SortRGBAxis]; /* Max. of first half */ 2649b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot /* coverity[var_deref_op] */ 2659b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot MinColor = QuantizedColor->Pnext->RGB[SortRGBAxis]; /* of second */ 2669b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot MaxColor <<= (8 - BITS_PER_PRIM_COLOR); 2679b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot MinColor <<= (8 - BITS_PER_PRIM_COLOR); 2689b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 2699b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot /* Partition right here: */ 2709b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[*NewColorMapSize].QuantizedColors = 2719b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot QuantizedColor->Pnext; 2729b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot QuantizedColor->Pnext = NULL; 2739b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[*NewColorMapSize].Count = Count; 2749b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[Index].Count -= Count; 2759b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[*NewColorMapSize].NumEntries = 2769b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[Index].NumEntries - NumEntries; 2779b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[Index].NumEntries = NumEntries; 2789b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot for (j = 0; j < 3; j++) { 2799b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[*NewColorMapSize].RGBMin[j] = 2809b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[Index].RGBMin[j]; 2819b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[*NewColorMapSize].RGBWidth[j] = 2829b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[Index].RGBWidth[j]; 2839b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 2849b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[*NewColorMapSize].RGBWidth[SortRGBAxis] = 2859b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[*NewColorMapSize].RGBMin[SortRGBAxis] + 2869b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[*NewColorMapSize].RGBWidth[SortRGBAxis] - MinColor; 2879b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[*NewColorMapSize].RGBMin[SortRGBAxis] = MinColor; 2889b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 2899b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NewColorSubdiv[Index].RGBWidth[SortRGBAxis] = 2909b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot MaxColor - NewColorSubdiv[Index].RGBMin[SortRGBAxis]; 2919b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 2929b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot (*NewColorMapSize)++; 2939b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 2949b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 2959b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot return GIF_OK; 2969b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot} 2979b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 2989b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot/**************************************************************************** 2999b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Routine called by qsort to compare two entries. 3009b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot*****************************************************************************/ 3019b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfootstatic int 3029b8f8602a74a943ddc356bb11c55b4998b2b386dKeith PlatfootSortCmpRtn(const void *Entry1, 3039b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot const void *Entry2) { 3049b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 3059b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot return (*((QuantizedColorType **) Entry1))->RGB[SortRGBAxis] - 3069b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot (*((QuantizedColorType **) Entry2))->RGB[SortRGBAxis]; 3079b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot} 3089b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 3099b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot/* end */ 310