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