Coverage Report

Created: 2023-03-26 07:33

/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 */