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
25static int SortRGBAxis;
26
27typedef struct QuantizedColorType {
28    GifByteType RGB[3];
29    GifByteType NewColorIndex;
30    long Count;
31    struct QuantizedColorType *Pnext;
32} QuantizedColorType;
33
34typedef 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
41static int SubdivColorMap(NewColorMapType * NewColorSubdiv,
42                          unsigned int ColorMapSize,
43                          unsigned int *NewColorMapSize);
44static 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******************************************************************************/
58int
59GifQuantizeBuffer(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*******************************************************************************/
196static int
197SubdivColorMap(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
313static int
314SortCmpRtn(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