/src/giflib-code/quantize.c
Line | Count | Source (jump to first uncovered line) |
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 | | SPDX-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 | 23.9M | #define ABS(x) ((x) > 0 ? (x) : (-(x))) |
22 | | |
23 | 24.7M | #define COLOR_ARRAY_SIZE 32768 |
24 | 104M | #define BITS_PER_PRIM_COLOR 5 |
25 | 24.7M | #define MAX_PRIM_COLOR 0x1f |
26 | | |
27 | | static int SortRGBAxis; |
28 | | |
29 | | typedef struct QuantizedColorType { |
30 | | GifByteType RGB[3]; |
31 | | GifByteType NewColorIndex; |
32 | | long Count; |
33 | | struct QuantizedColorType *Pnext; |
34 | | } QuantizedColorType; |
35 | | |
36 | | typedef 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 | | |
43 | | static int SubdivColorMap(NewColorMapType * NewColorSubdiv, |
44 | | unsigned int ColorMapSize, |
45 | | unsigned int *NewColorMapSize); |
46 | | static 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 | | ******************************************************************************/ |
60 | | int |
61 | | GifQuantizeBuffer(unsigned int Width, |
62 | | unsigned int Height, |
63 | | int *ColorMapSize, |
64 | | GifByteType * RedInput, |
65 | | GifByteType * GreenInput, |
66 | | GifByteType * BlueInput, |
67 | | GifByteType * OutputBuffer, |
68 | 378 | GifColorType * OutputColorMap) { |
69 | | |
70 | 378 | unsigned int Index, NumOfEntries; |
71 | 378 | int i, j, MaxRGBError[3]; |
72 | 378 | unsigned int NewColorMapSize; |
73 | 378 | long Red, Green, Blue; |
74 | 378 | NewColorMapType NewColorSubdiv[256]; |
75 | 378 | QuantizedColorType *ColorArrayEntries, *QuantizedColor; |
76 | | |
77 | 378 | ColorArrayEntries = (QuantizedColorType *)malloc( |
78 | 378 | sizeof(QuantizedColorType) * COLOR_ARRAY_SIZE); |
79 | 378 | if (ColorArrayEntries == NULL) { |
80 | 0 | return GIF_ERROR; |
81 | 0 | } |
82 | | |
83 | 12.3M | for (i = 0; i < COLOR_ARRAY_SIZE; i++) { |
84 | 12.3M | ColorArrayEntries[i].RGB[0] = i >> (2 * BITS_PER_PRIM_COLOR); |
85 | 12.3M | ColorArrayEntries[i].RGB[1] = (i >> BITS_PER_PRIM_COLOR) & |
86 | 12.3M | MAX_PRIM_COLOR; |
87 | 12.3M | ColorArrayEntries[i].RGB[2] = i & MAX_PRIM_COLOR; |
88 | 12.3M | ColorArrayEntries[i].Count = 0; |
89 | 12.3M | } |
90 | | |
91 | | /* Sample the colors and their distribution: */ |
92 | 7.99M | for (i = 0; i < (int)(Width * Height); i++) { |
93 | 7.99M | Index = ((RedInput[i] >> (8 - BITS_PER_PRIM_COLOR)) << |
94 | 7.99M | (2 * BITS_PER_PRIM_COLOR)) + |
95 | 7.99M | ((GreenInput[i] >> (8 - BITS_PER_PRIM_COLOR)) << |
96 | 7.99M | BITS_PER_PRIM_COLOR) + |
97 | 7.99M | (BlueInput[i] >> (8 - BITS_PER_PRIM_COLOR)); |
98 | 7.99M | ColorArrayEntries[Index].Count++; |
99 | 7.99M | } |
100 | | |
101 | | /* Put all the colors in the first entry of the color map, and call the |
102 | | * recursive subdivision process. */ |
103 | 97.1k | for (i = 0; i < 256; i++) { |
104 | 96.7k | NewColorSubdiv[i].QuantizedColors = NULL; |
105 | 96.7k | NewColorSubdiv[i].Count = NewColorSubdiv[i].NumEntries = 0; |
106 | 387k | for (j = 0; j < 3; j++) { |
107 | 290k | NewColorSubdiv[i].RGBMin[j] = 0; |
108 | 290k | NewColorSubdiv[i].RGBWidth[j] = 255; |
109 | 290k | } |
110 | 96.7k | } |
111 | | |
112 | | /* Find the non empty entries in the color table and chain them: */ |
113 | 835k | for (i = 0; i < COLOR_ARRAY_SIZE; i++) |
114 | 835k | if (ColorArrayEntries[i].Count > 0) |
115 | 378 | break; |
116 | 378 | QuantizedColor = NewColorSubdiv[0].QuantizedColors = &ColorArrayEntries[i]; |
117 | 378 | NumOfEntries = 1; |
118 | 11.5M | while (++i < COLOR_ARRAY_SIZE) |
119 | 11.5M | if (ColorArrayEntries[i].Count > 0) { |
120 | 1.46M | QuantizedColor->Pnext = &ColorArrayEntries[i]; |
121 | 1.46M | QuantizedColor = &ColorArrayEntries[i]; |
122 | 1.46M | NumOfEntries++; |
123 | 1.46M | } |
124 | 378 | QuantizedColor->Pnext = NULL; |
125 | | |
126 | 378 | NewColorSubdiv[0].NumEntries = NumOfEntries; /* Different sampled colors */ |
127 | 378 | NewColorSubdiv[0].Count = ((long)Width) * Height; /* Pixels */ |
128 | 378 | NewColorMapSize = 1; |
129 | 378 | if (SubdivColorMap(NewColorSubdiv, *ColorMapSize, &NewColorMapSize) != |
130 | 378 | GIF_OK) { |
131 | 0 | free((char *)ColorArrayEntries); |
132 | 0 | return GIF_ERROR; |
133 | 0 | } |
134 | 378 | if (NewColorMapSize < *ColorMapSize) { |
135 | | /* And clear rest of color map: */ |
136 | 36.5k | for (i = NewColorMapSize; i < *ColorMapSize; i++) |
137 | 36.3k | OutputColorMap[i].Red = OutputColorMap[i].Green = |
138 | 36.3k | OutputColorMap[i].Blue = 0; |
139 | 191 | } |
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 | 60.8k | for (i = 0; i < NewColorMapSize; i++) { |
144 | 60.4k | if ((j = NewColorSubdiv[i].NumEntries) > 0) { |
145 | 60.4k | QuantizedColor = NewColorSubdiv[i].QuantizedColors; |
146 | 60.4k | Red = Green = Blue = 0; |
147 | 1.52M | while (QuantizedColor) { |
148 | 1.46M | QuantizedColor->NewColorIndex = i; |
149 | 1.46M | Red += QuantizedColor->RGB[0]; |
150 | 1.46M | Green += QuantizedColor->RGB[1]; |
151 | 1.46M | Blue += QuantizedColor->RGB[2]; |
152 | 1.46M | QuantizedColor = QuantizedColor->Pnext; |
153 | 1.46M | } |
154 | 60.4k | OutputColorMap[i].Red = (Red << (8 - BITS_PER_PRIM_COLOR)) / j; |
155 | 60.4k | OutputColorMap[i].Green = (Green << (8 - BITS_PER_PRIM_COLOR)) / j; |
156 | 60.4k | OutputColorMap[i].Blue = (Blue << (8 - BITS_PER_PRIM_COLOR)) / j; |
157 | 60.4k | } |
158 | 60.4k | } |
159 | | |
160 | | /* Finally scan the input buffer again and put the mapped index in the |
161 | | * output buffer. */ |
162 | 378 | MaxRGBError[0] = MaxRGBError[1] = MaxRGBError[2] = 0; |
163 | 7.99M | for (i = 0; i < (int)(Width * Height); i++) { |
164 | 7.99M | Index = ((RedInput[i] >> (8 - BITS_PER_PRIM_COLOR)) << |
165 | 7.99M | (2 * BITS_PER_PRIM_COLOR)) + |
166 | 7.99M | ((GreenInput[i] >> (8 - BITS_PER_PRIM_COLOR)) << |
167 | 7.99M | BITS_PER_PRIM_COLOR) + |
168 | 7.99M | (BlueInput[i] >> (8 - BITS_PER_PRIM_COLOR)); |
169 | 7.99M | Index = ColorArrayEntries[Index].NewColorIndex; |
170 | 7.99M | OutputBuffer[i] = Index; |
171 | 7.99M | if (MaxRGBError[0] < ABS(OutputColorMap[Index].Red - RedInput[i])) |
172 | 1.74k | MaxRGBError[0] = ABS(OutputColorMap[Index].Red - RedInput[i]); |
173 | 7.99M | if (MaxRGBError[1] < ABS(OutputColorMap[Index].Green - GreenInput[i])) |
174 | 1.72k | MaxRGBError[1] = ABS(OutputColorMap[Index].Green - GreenInput[i]); |
175 | 7.99M | if (MaxRGBError[2] < ABS(OutputColorMap[Index].Blue - BlueInput[i])) |
176 | 1.82k | MaxRGBError[2] = ABS(OutputColorMap[Index].Blue - BlueInput[i]); |
177 | 7.99M | } |
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 | 378 | free((char *)ColorArrayEntries); |
186 | | |
187 | 378 | *ColorMapSize = NewColorMapSize; |
188 | | |
189 | 378 | return GIF_OK; |
190 | 378 | } |
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 | | *******************************************************************************/ |
198 | | static int |
199 | | SubdivColorMap(NewColorMapType * NewColorSubdiv, |
200 | | unsigned int ColorMapSize, |
201 | 378 | unsigned int *NewColorMapSize) { |
202 | | |
203 | 378 | unsigned int i, j, Index = 0; |
204 | 378 | QuantizedColorType *QuantizedColor, **SortArray; |
205 | | |
206 | 60.4k | while (ColorMapSize > *NewColorMapSize) { |
207 | | /* Find candidate for subdivision: */ |
208 | 60.2k | long Sum, Count; |
209 | 60.2k | int MaxSize = -1; |
210 | 60.2k | unsigned int NumEntries, MinColor, MaxColor; |
211 | 6.95M | for (i = 0; i < *NewColorMapSize; i++) { |
212 | 27.5M | for (j = 0; j < 3; j++) { |
213 | 20.6M | if ((((int)NewColorSubdiv[i].RGBWidth[j]) > MaxSize) && |
214 | 20.6M | (NewColorSubdiv[i].NumEntries > 1)) { |
215 | 218k | MaxSize = NewColorSubdiv[i].RGBWidth[j]; |
216 | 218k | Index = i; |
217 | 218k | SortRGBAxis = j; |
218 | 218k | } |
219 | 20.6M | } |
220 | 6.89M | } |
221 | | |
222 | 60.2k | if (MaxSize == -1) |
223 | 191 | 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 | 60.0k | SortArray = (QuantizedColorType **)malloc( |
230 | 60.0k | sizeof(QuantizedColorType *) * |
231 | 60.0k | NewColorSubdiv[Index].NumEntries); |
232 | 60.0k | if (SortArray == NULL) |
233 | 0 | return GIF_ERROR; |
234 | 60.0k | for (j = 0, QuantizedColor = NewColorSubdiv[Index].QuantizedColors; |
235 | 24.6M | j < NewColorSubdiv[Index].NumEntries && QuantizedColor != NULL; |
236 | 24.6M | j++, QuantizedColor = QuantizedColor->Pnext) |
237 | 24.6M | 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 | 60.0k | qsort(SortArray, NewColorSubdiv[Index].NumEntries, |
251 | 60.0k | sizeof(QuantizedColorType *), SortCmpRtn); |
252 | | |
253 | | /* Relink the sorted list into one: */ |
254 | 24.6M | for (j = 0; j < NewColorSubdiv[Index].NumEntries - 1; j++) |
255 | 24.5M | SortArray[j]->Pnext = SortArray[j + 1]; |
256 | 60.0k | SortArray[NewColorSubdiv[Index].NumEntries - 1]->Pnext = NULL; |
257 | 60.0k | NewColorSubdiv[Index].QuantizedColors = QuantizedColor = SortArray[0]; |
258 | 60.0k | free((char *)SortArray); |
259 | | |
260 | | /* Now simply add the Counts until we have half of the Count: */ |
261 | 60.0k | Sum = NewColorSubdiv[Index].Count / 2 - QuantizedColor->Count; |
262 | 60.0k | NumEntries = 1; |
263 | 60.0k | Count = QuantizedColor->Count; |
264 | 5.30M | while (QuantizedColor->Pnext != NULL && |
265 | 5.30M | (Sum -= QuantizedColor->Pnext->Count) >= 0 && |
266 | 5.30M | QuantizedColor->Pnext->Pnext != NULL) { |
267 | 5.24M | QuantizedColor = QuantizedColor->Pnext; |
268 | 5.24M | NumEntries++; |
269 | 5.24M | Count += QuantizedColor->Count; |
270 | 5.24M | } |
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 | 60.0k | MaxColor = QuantizedColor->RGB[SortRGBAxis]; /* Max. of first half */ |
277 | | /* coverity[var_deref_op] */ |
278 | 60.0k | MinColor = QuantizedColor->Pnext->RGB[SortRGBAxis]; /* of second */ |
279 | 60.0k | MaxColor <<= (8 - BITS_PER_PRIM_COLOR); |
280 | 60.0k | MinColor <<= (8 - BITS_PER_PRIM_COLOR); |
281 | | |
282 | | /* Partition right here: */ |
283 | 60.0k | NewColorSubdiv[*NewColorMapSize].QuantizedColors = |
284 | 60.0k | QuantizedColor->Pnext; |
285 | 60.0k | QuantizedColor->Pnext = NULL; |
286 | 60.0k | NewColorSubdiv[*NewColorMapSize].Count = Count; |
287 | 60.0k | NewColorSubdiv[Index].Count -= Count; |
288 | 60.0k | NewColorSubdiv[*NewColorMapSize].NumEntries = |
289 | 60.0k | NewColorSubdiv[Index].NumEntries - NumEntries; |
290 | 60.0k | NewColorSubdiv[Index].NumEntries = NumEntries; |
291 | 240k | for (j = 0; j < 3; j++) { |
292 | 180k | NewColorSubdiv[*NewColorMapSize].RGBMin[j] = |
293 | 180k | NewColorSubdiv[Index].RGBMin[j]; |
294 | 180k | NewColorSubdiv[*NewColorMapSize].RGBWidth[j] = |
295 | 180k | NewColorSubdiv[Index].RGBWidth[j]; |
296 | 180k | } |
297 | 60.0k | NewColorSubdiv[*NewColorMapSize].RGBWidth[SortRGBAxis] = |
298 | 60.0k | NewColorSubdiv[*NewColorMapSize].RGBMin[SortRGBAxis] + |
299 | 60.0k | NewColorSubdiv[*NewColorMapSize].RGBWidth[SortRGBAxis] - MinColor; |
300 | 60.0k | NewColorSubdiv[*NewColorMapSize].RGBMin[SortRGBAxis] = MinColor; |
301 | | |
302 | 60.0k | NewColorSubdiv[Index].RGBWidth[SortRGBAxis] = |
303 | 60.0k | MaxColor - NewColorSubdiv[Index].RGBMin[SortRGBAxis]; |
304 | | |
305 | 60.0k | (*NewColorMapSize)++; |
306 | 60.0k | } |
307 | | |
308 | 187 | return GIF_OK; |
309 | 378 | } |
310 | | |
311 | | /**************************************************************************** |
312 | | Routine called by qsort to compare two entries. |
313 | | *****************************************************************************/ |
314 | | |
315 | | static int |
316 | | SortCmpRtn(const void *Entry1, |
317 | 161M | const void *Entry2) { |
318 | 161M | QuantizedColorType *entry1 = (*((QuantizedColorType **) Entry1)); |
319 | 161M | QuantizedColorType *entry2 = (*((QuantizedColorType **) Entry2)); |
320 | | |
321 | | /* sort on all axes of the color space! */ |
322 | 161M | int hash1 = entry1->RGB[SortRGBAxis] * 256 * 256 |
323 | 161M | + entry1->RGB[(SortRGBAxis+1) % 3] * 256 |
324 | 161M | + entry1->RGB[(SortRGBAxis+2) % 3]; |
325 | 161M | int hash2 = entry2->RGB[SortRGBAxis] * 256 * 256 |
326 | 161M | + entry2->RGB[(SortRGBAxis+1) % 3] * 256 |
327 | 161M | + entry2->RGB[(SortRGBAxis+2) % 3]; |
328 | | |
329 | 161M | return hash1 - hash2; |
330 | 161M | } |
331 | | |
332 | | /* end */ |