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