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