1 /* kcolor.h - Color-oriented function declarations for gifsicle.
2 Copyright (C) 2013-2021 Eddie Kohler, ekohler@gmail.com
3 This file is part of gifsicle.
4
5 Gifsicle is free software. It is distributed under the GNU Public License,
6 version 2; you can copy, distribute, or alter it at will, as long
7 as this notice is kept intact and this source code is made available. There
8 is no warranty, express or implied. */
9
10 #ifndef GIFSICLE_KCOLOR_H
11 #define GIFSICLE_KCOLOR_H
12 #include <lcdfgif/gif.h>
13 #include <assert.h>
14
15 /* kcolor: a 3D vector, each component has 15 bits of precision */
16 /* 15 bits means KC_MAX * KC_MAX always fits within a signed 32-bit
17 integer, and a 3-D squared distance always fits within an unsigned 32-bit
18 integer. */
19 #define KC_MAX 0x7FFF
20 #define KC_WHOLE 0x8000
21 #define KC_HALF 0x4000
22 #define KC_QUARTER 0x2000
23 #define KC_BITS 15
24 typedef struct kcolor {
25 int16_t a[3];
26 } kcolor;
27
28 #undef min
29 #undef max
30 #define min(a, b) ((a) < (b) ? (a) : (b))
31 #define max(a, b) ((a) > (b) ? (a) : (b))
32
33 #define KC_CLAMPV(v) (max(0, min((v), KC_MAX)))
34
35 typedef union kacolor {
36 kcolor k;
37 int16_t a[4];
38 #if HAVE_INT64_T
39 int64_t q; /* to get better alignment */
40 #endif
41 } kacolor;
42
43
44 /* gamma_tables[0]: array of 256 gamma-conversion values
45 gamma_tables[1]: array of 256 reverse gamma-conversion values */
46 extern uint16_t* gamma_tables[2];
47
48
49 /* set `*kc` to the gamma transformation of `a0/a1/a2` [RGB] */
kc_set8g(kcolor * kc,int a0,int a1,int a2)50 static inline void kc_set8g(kcolor* kc, int a0, int a1, int a2) {
51 kc->a[0] = gamma_tables[0][a0];
52 kc->a[1] = gamma_tables[0][a1];
53 kc->a[2] = gamma_tables[0][a2];
54 }
55
56 /* return the gamma transformation of `a0/a1/a2` [RGB] */
kc_make8g(int a0,int a1,int a2)57 static inline kcolor kc_make8g(int a0, int a1, int a2) {
58 kcolor kc;
59 kc_set8g(&kc, a0, a1, a2);
60 return kc;
61 }
62
63 /* return the gamma transformation of `*gfc` */
kc_makegfcg(const Gif_Color * gfc)64 static inline kcolor kc_makegfcg(const Gif_Color* gfc) {
65 return kc_make8g(gfc->gfc_red, gfc->gfc_green, gfc->gfc_blue);
66 }
67
68 /* return the uncorrected representation of `a0/a1/a2` [RGB] */
kc_make8ng(int a0,int a1,int a2)69 static inline kcolor kc_make8ng(int a0, int a1, int a2) {
70 kcolor kc;
71 kc.a[0] = (a0 << 7) + (a0 >> 1);
72 kc.a[1] = (a1 << 7) + (a1 >> 1);
73 kc.a[2] = (a2 << 7) + (a2 >> 1);
74 return kc;
75 }
76
77 /* return the kcolor representation of `*gfc` (no gamma transformation) */
kc_makegfcng(const Gif_Color * gfc)78 static inline kcolor kc_makegfcng(const Gif_Color* gfc) {
79 return kc_make8ng(gfc->gfc_red, gfc->gfc_green, gfc->gfc_blue);
80 }
81
82 /* return transparency */
kac_transparent()83 static inline kacolor kac_transparent() {
84 kacolor x;
85 x.a[0] = x.a[1] = x.a[2] = x.a[3] = 0;
86 return x;
87 }
88
89 /* return a hex color string definition for `x` */
90 const char* kc_debug_str(kcolor x);
91
92 /* set `*x` to the reverse gamma transformation of `*x` */
93 void kc_revgamma_transform(kcolor* x);
94
95 /* return the reverse gramma transformation of `*x` as a Gif_Color */
kc_togfcg(const kcolor * x)96 static inline Gif_Color kc_togfcg(const kcolor* x) {
97 kcolor xx = *x;
98 Gif_Color gfc;
99 kc_revgamma_transform(&xx);
100 gfc.gfc_red = (uint8_t) (xx.a[0] >> 7);
101 gfc.gfc_green = (uint8_t) (xx.a[1] >> 7);
102 gfc.gfc_blue = (uint8_t) (xx.a[2] >> 7);
103 gfc.haspixel = 0;
104 return gfc;
105 }
106
107
108 /* return the squared Euclidean distance between `*x` and `*y` */
kc_distance(const kcolor * x,const kcolor * y)109 static inline uint32_t kc_distance(const kcolor* x, const kcolor* y) {
110 /* It’s OK to use unsigned multiplication for this: the low 32 bits
111 are the same either way. Unsigned avoids undefined behavior. */
112 uint32_t d0 = x->a[0] - y->a[0];
113 uint32_t d1 = x->a[1] - y->a[1];
114 uint32_t d2 = x->a[2] - y->a[2];
115 return d0 * d0 + d1 * d1 + d2 * d2;
116 }
117
118 /* return the luminance value for `*x`; result is between 0 and KC_MAX */
kc_luminance(const kcolor * x)119 static inline int kc_luminance(const kcolor* x) {
120 return (55 * x->a[0] + 183 * x->a[1] + 19 * x->a[2]) >> 8;
121 }
122
123 /* set `*x` to the grayscale version of `*x`, transformed by luminance */
kc_luminance_transform(kcolor * x)124 static inline void kc_luminance_transform(kcolor* x) {
125 /* For grayscale colormaps, use distance in luminance space instead of
126 distance in RGB space. The weights for the R,G,B components in
127 luminance space are 0.2126,0.7152,0.0722. (That's ITU primaries, which
128 are compatible with sRGB; NTSC recommended our previous values,
129 0.299,0.587,0.114.) Using the proportional factors 55,183,19 we get a
130 scaled gray value between 0 and 255 * 257; dividing by 256 gives us
131 what we want. Thanks to Christian Kumpf, <kumpf@igd.fhg.de>, for
132 providing a patch.*/
133 x->a[0] = x->a[1] = x->a[2] = kc_luminance(x);
134 }
135
136
137 /* wkcolor: like kcolor, but components are 32 bits instead of 16 */
138
139 typedef struct wkcolor {
140 int32_t a[3];
141 } wkcolor;
142
wkc_clear(wkcolor * x)143 static inline void wkc_clear(wkcolor* x) {
144 x->a[0] = x->a[1] = x->a[2] = 0;
145 }
146
147
148 /* kd3_tree: kd-tree for 3 dimensions, indexing kcolors */
149
150 typedef struct kd3_tree kd3_tree;
151 typedef struct kd3_treepos kd3_treepos;
152
153 struct kd3_tree {
154 kd3_treepos* tree;
155 int ntree;
156 int disabled;
157 kcolor* ks;
158 int nitems;
159 int items_cap;
160 int maxdepth;
161 void (*transform)(kcolor*);
162 unsigned* xradius;
163 };
164
165 /* initialize `kd3` with the given color `transform` (may be NULL) */
166 void kd3_init(kd3_tree* kd3, void (*transform)(kcolor*));
167
168 /* free `kd3` */
169 void kd3_cleanup(kd3_tree* kd3);
170
171 /* add the transformed color `k` to `*kd3` (do not apply `kd3->transform`). */
172 void kd3_add_transformed(kd3_tree* kd3, const kcolor* k);
173
174 /* given 8-bit color `a0/a1/a2` (RGB), gamma-transform it, transform it
175 by `kd3->transform` if necessary, and add it to `*kd3` */
176 void kd3_add8g(kd3_tree* kd3, int a0, int a1, int a2);
177
178 /* set `kd3->xradius`. given color `i`, `kd3->xradius[i]` is the square of the
179 color's uniquely owned neighborhood.
180 If `kc_distance(&kd3->ks[i], &k) < kd3->xradius[i]`, then
181 `kd3_closest_transformed(kd3, &k) == i`. */
182 void kd3_build_xradius(kd3_tree* kd3);
183
184 /* build the actual kd-tree for `kd3`. must be called before kd3_closest. */
185 void kd3_build(kd3_tree* kd3);
186
187 /* kd3_init + kd3_add8g for all colors in `gfcm` + kd3_build */
188 void kd3_init_build(kd3_tree* kd3, void (*transform)(kcolor*),
189 const Gif_Colormap* gfcm);
190
191 /* return the index of the color in `*kd3` closest to `k`.
192 if `dist!=NULL`, store the distance from `k` to that index in `*dist`. */
193 int kd3_closest_transformed(kd3_tree* kd3, const kcolor* k,
194 unsigned* dist);
195
196 /* given 8-bit color `a0/a1/a2` (RGB), gamma-transform it, transform it by
197 `kd3->transform` if necessary, and return the index of the color in
198 `*kd3` closest to it. */
199 int kd3_closest8g(kd3_tree* kd3, int a0, int a1, int a2);
200
201 /* disable color index `i` in `*kd3`: it will never be returned by
202 `kd3_closest*` */
kd3_disable(kd3_tree * kd3,int i)203 static inline void kd3_disable(kd3_tree* kd3, int i) {
204 assert((unsigned) i < (unsigned) kd3->nitems);
205 assert(kd3->disabled < 0 || kd3->disabled == i);
206 kd3->disabled = i;
207 }
208
209 /* enable all color indexes in `*kd3` */
kd3_enable_all(kd3_tree * kd3)210 static inline void kd3_enable_all(kd3_tree* kd3) {
211 kd3->disabled = -1;
212 }
213
214
215 typedef uint32_t kchist_count_t;
216 typedef struct kchistitem {
217 kacolor ka;
218 kchist_count_t count;
219 } kchistitem;
220
221 typedef struct kchist {
222 kchistitem* h;
223 int n;
224 int capacity;
225 } kchist;
226
227 void kchist_init(kchist* kch);
228 void kchist_cleanup(kchist* kch);
229 void kchist_make(kchist* kch, Gif_Stream* gfs, uint32_t* ntransp);
230 kchistitem* kchist_add(kchist* kch, kcolor color, kchist_count_t count);
231 void kchist_compress(kchist* kch);
232
233
234 typedef struct {
235 kchist* kch;
236 int* closest;
237 uint32_t* min_dist;
238 uint32_t* min_dither_dist;
239 int* chosen;
240 int nchosen;
241 } kcdiversity;
242
243 void kcdiversity_init(kcdiversity* div, kchist* kch, int dodither);
244 void kcdiversity_cleanup(kcdiversity* div);
245 int kcdiversity_find_popular(kcdiversity* div);
246 int kcdiversity_find_diverse(kcdiversity* div, double ditherweight);
247 int kcdiversity_choose(kcdiversity* div, int chosen, int dodither);
248
249
250 Gif_Colormap* colormap_blend_diversity(kchist* kch, Gt_OutputData* od);
251 Gif_Colormap* colormap_flat_diversity(kchist* kch, Gt_OutputData* od);
252 Gif_Colormap* colormap_median_cut(kchist* kch, Gt_OutputData* od);
253
254
255 #if HAVE_SIMD && HAVE_VECTOR_SIZE_VECTOR_TYPES
256 typedef float float4 __attribute__((vector_size (sizeof(float) * 4)));
257 typedef int int4 __attribute__((vector_size (sizeof(int) * 4)));
258 #elif HAVE_SIMD && HAVE_EXT_VECTOR_TYPE_VECTOR_TYPES
259 typedef float float4 __attribute__((ext_vector_type (4)));
260 #else
261 typedef float float4[4];
262 #endif
263
264 typedef union scale_color {
265 float4 a;
266 } scale_color;
267
sc_clear(scale_color * x)268 static inline void sc_clear(scale_color* x) {
269 x->a[0] = x->a[1] = x->a[2] = x->a[3] = 0;
270 }
271
sc_makekc(const kcolor * k)272 static inline scale_color sc_makekc(const kcolor* k) {
273 scale_color sc;
274 sc.a[0] = k->a[0];
275 sc.a[1] = k->a[1];
276 sc.a[2] = k->a[2];
277 sc.a[3] = KC_MAX;
278 return sc;
279 }
280
sc_make(float a0,float a1,float a2,float a3)281 static inline scale_color sc_make(float a0, float a1, float a2, float a3) {
282 scale_color sc;
283 sc.a[0] = a0;
284 sc.a[1] = a1;
285 sc.a[2] = a2;
286 sc.a[3] = a3;
287 return sc;
288 }
289
290 #if HAVE_SIMD
291 # define SCVEC_ADDV(sc, sc2) (sc).a += (sc2).a
292 # define SCVEC_MULV(sc, sc2) (sc).a *= (sc2).a
293 # define SCVEC_MULF(sc, f) (sc).a *= (f)
294 # define SCVEC_DIVF(sc, f) (sc).a /= (f)
295 # define SCVEC_ADDVxF(sc, sc2, f) (sc).a += (sc2).a * (f)
296 # if HAVE___BUILTIN_SHUFFLEVECTOR
297 # define SCVEC_ROT3(out, sc) do { (out).a = __builtin_shufflevector((sc).a, (sc).a, 1, 2, 0, 3); } while (0)
298 # else
299 # define SCVEC_ROT3(out, sc) do { int4 shufmask__ = {1, 2, 0, 3}; (out).a = __builtin_shuffle((sc).a, shufmask__); } while (0)
300 # endif
301 #else
302 # define SCVEC_FOREACH(t) do { int k__; for (k__ = 0; k__ != 4; ++k__) { t; } } while (0)
303 # define SCVEC_ADDV(sc, sc2) SCVEC_FOREACH((sc).a[k__] += (sc2).a[k__])
304 # define SCVEC_MULV(sc, sc2) SCVEC_FOREACH((sc).a[k__] *= (sc2).a[k__])
305 # define SCVEC_MULF(sc, f) SCVEC_FOREACH((sc).a[k__] *= (f))
306 # define SCVEC_DIVF(sc, f) SCVEC_FOREACH((sc).a[k__] /= (f))
307 # define SCVEC_ADDVxF(sc, sc2, f) SCVEC_FOREACH((sc).a[k__] += (sc2).a[k__] * (f))
308 # define SCVEC_ROT3(out, sc) do { float __a0 = (sc).a[0]; (out).a[0] = (sc).a[1]; (out).a[1] = (sc).a[2]; (out).a[2] = __a0; (out).a[3] = (sc).a[3]; } while (0)
309 #endif
310
311 #endif
312