1 diff -ur a/quantize.c b/quantize.c
2 --- a/quantize.c 2019-02-11 07:43:57.000000000 -0700
3 +++ b/quantize.c 2019-02-27 17:20:06.369498072 -0700
4 # SortRGBAxis is static and not locked, qsort recoded
5 # GAErrorToken is also static and not locked, not fixed
8 ******************************************************************************/
15 #include "gif_lib_private.h"
18 #define BITS_PER_PRIM_COLOR 5
19 #define MAX_PRIM_COLOR 0x1f
21 -static int SortRGBAxis;
23 typedef struct QuantizedColorType {
25 GifByteType NewColorIndex;
27 struct QuantizedColorType *Pnext;
30 +static int QCmpr(QuantizedColorType *a, QuantizedColorType *b, int i)
32 + int i0 = i, i1 = i+1, i2 = i+2;
33 + if( i1 >= 3 ) i1 -= 3;
34 + if( i2 >= 3 ) i2 -= 3;
35 + /* sort on all axes of the color space! */
36 + int hash_a = (a->RGB[i0] << 16) | (a->RGB[i1] << 8) | (a->RGB[i2] << 0);
37 + int hash_b = (b->RGB[i0] << 16) | (b->RGB[i1] << 8) | (b->RGB[i2] << 0);
38 + return hash_a - hash_b;
41 +static int QSplit(QuantizedColorType **q, int l, int r, int i)
44 + QuantizedColorType *t;
46 + while( QCmpr(q[r],q[l], i) >= 0 ) if( ++l == r ) return r;
47 + t = q[l]; q[l] = q[r]; q[r] = t; m = l; l = r; r = m;
48 + while( QCmpr(q[l],q[r], i) >= 0 ) if( r == --l ) return r;
49 + t = q[l]; q[l] = q[r]; q[r] = t; m = l; l = r; r = m;
53 +static void QSort(QuantizedColorType **q, int ll, int rr, int i)
56 + int l = ll+1; if( l == rr ) return;
57 + int r = rr-1; if( l == r ) return;
58 + int m = QSplit(q, l, r, i);
64 typedef struct NewColorMapType {
65 GifByteType RGBMin[3], RGBWidth[3];
66 unsigned int NumEntries; /* # of QuantizedColorType in linked list below */
68 static int SubdivColorMap(NewColorMapType * NewColorSubdiv,
69 unsigned int ColorMapSize,
70 unsigned int *NewColorMapSize);
71 -static int SortCmpRtn(const void *Entry1, const void *Entry2);
73 /******************************************************************************
74 Quantize high resolution image into lower one. Input image consists of a
76 unsigned int ColorMapSize,
77 unsigned int *NewColorMapSize) {
79 + int SortRGBAxis = 0;
80 unsigned int i, j, Index = 0;
81 QuantizedColorType *QuantizedColor, **SortArray;
84 j++, QuantizedColor = QuantizedColor->Pnext)
85 SortArray[j] = QuantizedColor;
88 - * Because qsort isn't stable, this can produce differing
89 - * results for the order of tuples depending on platform
90 - * details of how qsort() is implemented.
92 - * We mitigate this problem by sorting on all three axes rather
93 - * than only the one specied by SortRGBAxis; that way the instability
94 - * can only become an issue if there are multiple color indices
95 - * referring to identical RGB tuples. Older versions of this
96 - * sorted on only the one axis.
98 - qsort(SortArray, NewColorSubdiv[Index].NumEntries,
99 - sizeof(QuantizedColorType *), SortCmpRtn);
100 + QSort(SortArray, -1, NewColorSubdiv[Index].NumEntries, SortRGBAxis);
102 /* Relink the sorted list into one: */
103 for (j = 0; j < NewColorSubdiv[Index].NumEntries - 1; j++)
105 Routine called by qsort to compare two entries.
106 *****************************************************************************/
109 -SortCmpRtn(const void *Entry1,
110 - const void *Entry2) {
111 - QuantizedColorType *entry1 = (*((QuantizedColorType **) Entry1));
112 - QuantizedColorType *entry2 = (*((QuantizedColorType **) Entry2));
114 - /* sort on all axes of the color space! */
115 - int hash1 = entry1->RGB[SortRGBAxis] * 256 * 256
116 - + entry1->RGB[(SortRGBAxis+1) % 3] * 256
117 - + entry1->RGB[(SortRGBAxis+2) % 3];
118 - int hash2 = entry2->RGB[SortRGBAxis] * 256 * 256
119 - + entry2->RGB[(SortRGBAxis+1) % 3] * 256
120 - + entry2->RGB[(SortRGBAxis+2) % 3];
122 - return hash1 - hash2;