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        qsort(SortArray, NewColorSubdiv[Index].NumEntries,
238              sizeof(QuantizedColorType *), SortCmpRtn);
239
240        /* Relink the sorted list into one: */
241        for (j = 0; j < NewColorSubdiv[Index].NumEntries - 1; j++)
242            SortArray[j]->Pnext = SortArray[j + 1];
243        SortArray[NewColorSubdiv[Index].NumEntries - 1]->Pnext = NULL;
244        NewColorSubdiv[Index].QuantizedColors = QuantizedColor = SortArray[0];
245        free((char *)SortArray);
246
247        /* Now simply add the Counts until we have half of the Count: */
248        Sum = NewColorSubdiv[Index].Count / 2 - QuantizedColor->Count;
249        NumEntries = 1;
250        Count = QuantizedColor->Count;
251        while (QuantizedColor->Pnext != NULL &&
252	       (Sum -= QuantizedColor->Pnext->Count) >= 0 &&
253               QuantizedColor->Pnext->Pnext != NULL) {
254            QuantizedColor = QuantizedColor->Pnext;
255            NumEntries++;
256            Count += QuantizedColor->Count;
257        }
258        /* Save the values of the last color of the first half, and first
259         * of the second half so we can update the Bounding Boxes later.
260         * Also as the colors are quantized and the BBoxes are full 0..255,
261         * they need to be rescaled.
262         */
263        MaxColor = QuantizedColor->RGB[SortRGBAxis]; /* Max. of first half */
264	/* coverity[var_deref_op] */
265        MinColor = QuantizedColor->Pnext->RGB[SortRGBAxis]; /* of second */
266        MaxColor <<= (8 - BITS_PER_PRIM_COLOR);
267        MinColor <<= (8 - BITS_PER_PRIM_COLOR);
268
269        /* Partition right here: */
270        NewColorSubdiv[*NewColorMapSize].QuantizedColors =
271           QuantizedColor->Pnext;
272        QuantizedColor->Pnext = NULL;
273        NewColorSubdiv[*NewColorMapSize].Count = Count;
274        NewColorSubdiv[Index].Count -= Count;
275        NewColorSubdiv[*NewColorMapSize].NumEntries =
276           NewColorSubdiv[Index].NumEntries - NumEntries;
277        NewColorSubdiv[Index].NumEntries = NumEntries;
278        for (j = 0; j < 3; j++) {
279            NewColorSubdiv[*NewColorMapSize].RGBMin[j] =
280               NewColorSubdiv[Index].RGBMin[j];
281            NewColorSubdiv[*NewColorMapSize].RGBWidth[j] =
282               NewColorSubdiv[Index].RGBWidth[j];
283        }
284        NewColorSubdiv[*NewColorMapSize].RGBWidth[SortRGBAxis] =
285           NewColorSubdiv[*NewColorMapSize].RGBMin[SortRGBAxis] +
286           NewColorSubdiv[*NewColorMapSize].RGBWidth[SortRGBAxis] - MinColor;
287        NewColorSubdiv[*NewColorMapSize].RGBMin[SortRGBAxis] = MinColor;
288
289        NewColorSubdiv[Index].RGBWidth[SortRGBAxis] =
290           MaxColor - NewColorSubdiv[Index].RGBMin[SortRGBAxis];
291
292        (*NewColorMapSize)++;
293    }
294
295    return GIF_OK;
296}
297
298/****************************************************************************
299 Routine called by qsort to compare two entries.
300*****************************************************************************/
301static int
302SortCmpRtn(const void *Entry1,
303           const void *Entry2) {
304
305    return (*((QuantizedColorType **) Entry1))->RGB[SortRGBAxis] -
306       (*((QuantizedColorType **) Entry2))->RGB[SortRGBAxis];
307}
308
309/* end */
310