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