1 /* pam.h - pam (portable alpha map) utility library
2 **
3 ** Colormap routines.
4 **
5 ** Copyright (C) 1989, 1991 by Jef Poskanzer.
6 ** Copyright (C) 1997 by Greg Roelofs.
7 **
8 ** Permission to use, copy, modify, and distribute this software and its
9 ** documentation for any purpose and without fee is hereby granted, provided
10 ** that the above copyright notice appear in all copies and that both that
11 ** copyright notice and this permission notice appear in supporting
12 ** documentation. This software is provided "as is" without express or
13 ** implied warranty.
14 */
15
16 #ifndef PAM_H
17 #define PAM_H
18
19 #include <math.h>
20 #include <assert.h>
21 #include <stdlib.h>
22 #include <stdbool.h>
23
24 #ifndef MAX
25 # define MAX(a,b) ((a) > (b)? (a) : (b))
26 # define MIN(a,b) ((a) < (b)? (a) : (b))
27 #endif
28
29 #define MAX_DIFF 1e20
30
31 #ifndef USE_SSE
32 # if defined(__SSE__) && (defined(WIN32) || defined(__WIN32__))
33 # define USE_SSE 1
34 # else
35 # define USE_SSE 0
36 # endif
37 #endif
38
39 #if USE_SSE
40 # include <xmmintrin.h>
41 # ifdef _MSC_VER
42 # include <intrin.h>
43 # define SSE_ALIGN
44 # else
45 # define SSE_ALIGN __attribute__ ((aligned (16)))
46 # if defined(__i386__) && defined(__PIC__)
47 # define cpuid(func,ax,bx,cx,dx)\
48 __asm__ __volatile__ ( \
49 "push %%ebx\n" \
50 "cpuid\n" \
51 "mov %%ebx, %1\n" \
52 "pop %%ebx\n" \
53 : "=a" (ax), "=r" (bx), "=c" (cx), "=d" (dx) \
54 : "a" (func));
55 # else
56 # define cpuid(func,ax,bx,cx,dx)\
57 __asm__ __volatile__ ("cpuid":\
58 "=a" (ax), "=b" (bx), "=c" (cx), "=d" (dx) : "a" (func));
59 # endif
60 #endif
61 #else
62 # define SSE_ALIGN
63 #endif
64
65 #if defined(__GNUC__) || defined (__llvm__)
66 #define ALWAYS_INLINE __attribute__((always_inline)) inline
67 #define NEVER_INLINE __attribute__ ((noinline))
68 #elif defined(_MSC_VER)
69 #define inline __inline
70 #define restrict __restrict
71 #define ALWAYS_INLINE __forceinline
72 #define NEVER_INLINE __declspec(noinline)
73 #else
74 #define ALWAYS_INLINE inline
75 #define NEVER_INLINE
76 #endif
77
78 /* from pam.h */
79
80 typedef struct {
81 unsigned char r, g, b, a;
82 } rgba_pixel;
83
84 typedef struct {
85 float a, r, g, b;
86 } SSE_ALIGN f_pixel;
87
88 static const double internal_gamma = 0.5499;
89
90 LIQ_PRIVATE void to_f_set_gamma(float gamma_lut[], const double gamma);
91
92 /**
93 Converts 8-bit color to internal gamma and premultiplied alpha.
94 (premultiplied color space is much better for blending of semitransparent colors)
95 */
96 ALWAYS_INLINE static f_pixel to_f(const float gamma_lut[], const rgba_pixel px);
to_f(const float gamma_lut[],const rgba_pixel px)97 inline static f_pixel to_f(const float gamma_lut[], const rgba_pixel px)
98 {
99 float a = px.a/255.f;
100
101 return (f_pixel) {
102 .a = a,
103 .r = gamma_lut[px.r]*a,
104 .g = gamma_lut[px.g]*a,
105 .b = gamma_lut[px.b]*a,
106 };
107 }
108
to_rgb(const float gamma,const f_pixel px)109 inline static rgba_pixel to_rgb(const float gamma, const f_pixel px)
110 {
111 float r, g, b, a;
112
113 if (px.a < 1.f/256.f) {
114 return (rgba_pixel){0,0,0,0};
115 }
116
117 r = px.r / px.a,
118 g = px.g / px.a,
119 b = px.b / px.a,
120 a = px.a;
121
122 r = powf(r, gamma/internal_gamma);
123 g = powf(g, gamma/internal_gamma);
124 b = powf(b, gamma/internal_gamma);
125
126 // 256, because numbers are in range 1..255.9999… rounded down
127 r *= 256.f;
128 g *= 256.f;
129 b *= 256.f;
130 a *= 256.f;
131
132 return (rgba_pixel){
133 .r = r>=255.f ? 255 : r,
134 .g = g>=255.f ? 255 : g,
135 .b = b>=255.f ? 255 : b,
136 .a = a>=255.f ? 255 : a,
137 };
138 }
139
140 ALWAYS_INLINE static double colordifference_ch(const double x, const double y, const double alphas);
colordifference_ch(const double x,const double y,const double alphas)141 inline static double colordifference_ch(const double x, const double y, const double alphas)
142 {
143 // maximum of channel blended on white, and blended on black
144 // premultiplied alpha and backgrounds 0/1 shorten the formula
145 const double black = x-y, white = black+alphas;
146 return black*black + white*white;
147 }
148
149 ALWAYS_INLINE static float colordifference_stdc(const f_pixel px, const f_pixel py);
colordifference_stdc(const f_pixel px,const f_pixel py)150 inline static float colordifference_stdc(const f_pixel px, const f_pixel py)
151 {
152 // px_b.rgb = px.rgb + 0*(1-px.a) // blend px on black
153 // px_b.a = px.a + 1*(1-px.a)
154 // px_w.rgb = px.rgb + 1*(1-px.a) // blend px on white
155 // px_w.a = px.a + 1*(1-px.a)
156
157 // px_b.rgb = px.rgb // difference same as in opaque RGB
158 // px_b.a = 1
159 // px_w.rgb = px.rgb - px.a // difference simplifies to formula below
160 // px_w.a = 1
161
162 // (px.rgb - px.a) - (py.rgb - py.a)
163 // (px.rgb - py.rgb) + (py.a - px.a)
164
165 const double alphas = py.a-px.a;
166 return colordifference_ch(px.r, py.r, alphas) +
167 colordifference_ch(px.g, py.g, alphas) +
168 colordifference_ch(px.b, py.b, alphas);
169 }
170
171 ALWAYS_INLINE static double min_colordifference_ch(const double x, const double y, const double alphas);
min_colordifference_ch(const double x,const double y,const double alphas)172 inline static double min_colordifference_ch(const double x, const double y, const double alphas)
173 {
174 const double black = x-y, white = black+alphas;
175 return MIN(black*black , white*white) * 2.f;
176 }
177
178 /* least possible difference between colors (difference varies depending on background they're blended on) */
179 ALWAYS_INLINE static float min_colordifference(const f_pixel px, const f_pixel py);
min_colordifference(const f_pixel px,const f_pixel py)180 inline static float min_colordifference(const f_pixel px, const f_pixel py)
181 {
182 const double alphas = py.a-px.a;
183 return min_colordifference_ch(px.r, py.r, alphas) +
184 min_colordifference_ch(px.g, py.g, alphas) +
185 min_colordifference_ch(px.b, py.b, alphas);
186 }
187
188 ALWAYS_INLINE static float colordifference(f_pixel px, f_pixel py);
colordifference(f_pixel px,f_pixel py)189 inline static float colordifference(f_pixel px, f_pixel py)
190 {
191 #if USE_SSE
192 __m128 alphas, onblack, onwhite;
193 const __m128 vpx = _mm_load_ps((const float*)&px);
194 const __m128 vpy = _mm_load_ps((const float*)&py);
195 float res;
196
197 // y.a - x.a
198 alphas = _mm_sub_ss(vpy, vpx);
199 alphas = _mm_shuffle_ps(alphas,alphas,0); // copy first to all four
200
201 onblack = _mm_sub_ps(vpx, vpy); // x - y
202 onwhite = _mm_add_ps(onblack, alphas); // x - y + (y.a - x.a)
203
204 onblack = _mm_mul_ps(onblack, onblack);
205 onwhite = _mm_mul_ps(onwhite, onwhite);
206
207 {
208 const __m128 max = _mm_add_ps(onwhite, onblack);
209
210 // add rgb, not a
211 const __m128 maxhl = _mm_movehl_ps(max, max);
212 const __m128 tmp = _mm_add_ps(max, maxhl);
213 const __m128 sum = _mm_add_ss(maxhl, _mm_shuffle_ps(tmp, tmp, 1));
214
215 res = _mm_cvtss_f32(sum);
216 }
217 assert(fabs(res - colordifference_stdc(px,py)) < 0.001);
218 return res;
219 #else
220 return colordifference_stdc(px,py);
221 #endif
222 }
223
224 /* from pamcmap.h */
225 union rgba_as_int {
226 rgba_pixel rgba;
227 unsigned int l;
228 };
229
230 typedef struct {
231 f_pixel acolor;
232 float adjusted_weight, // perceptual weight changed to tweak how mediancut selects colors
233 perceptual_weight; // number of pixels weighted by importance of different areas of the picture
234
235 float color_weight; // these two change every time histogram subset is sorted
236 union {
237 unsigned int sort_value;
238 unsigned char likely_colormap_index;
239 } tmp;
240 } hist_item;
241
242 typedef struct {
243 hist_item *achv;
244 void (*free)(void*);
245 double total_perceptual_weight;
246 unsigned int size;
247 unsigned int ignorebits;
248 } histogram;
249
250 typedef struct {
251 f_pixel acolor;
252 float popularity;
253 bool fixed; // if true it's user-supplied and must not be changed (e.g in voronoi iteration)
254 } colormap_item;
255
256 typedef struct colormap {
257 unsigned int colors;
258 void* (*malloc)(size_t);
259 void (*free)(void*);
260 struct colormap *subset_palette;
261 colormap_item palette[];
262 } colormap;
263
264 struct acolorhist_arr_item {
265 union rgba_as_int color;
266 float perceptual_weight;
267 };
268
269 struct acolorhist_arr_head {
270 unsigned int used, capacity;
271 struct {
272 union rgba_as_int color;
273 float perceptual_weight;
274 } inline1, inline2;
275 struct acolorhist_arr_item *other_items;
276 };
277
278 struct acolorhash_table {
279 struct mempool *mempool;
280 unsigned int ignorebits, maxcolors, colors, cols, rows;
281 unsigned int hash_size;
282 unsigned int freestackp;
283 struct acolorhist_arr_item *freestack[512];
284 struct acolorhist_arr_head buckets[];
285 };
286
287 LIQ_PRIVATE void pam_freeacolorhash(struct acolorhash_table *acht);
288 LIQ_PRIVATE struct acolorhash_table *pam_allocacolorhash(unsigned int maxcolors, unsigned int surface, unsigned int ignorebits, void* (*malloc)(size_t), void (*free)(void*));
289 LIQ_PRIVATE histogram *pam_acolorhashtoacolorhist(const struct acolorhash_table *acht, const double gamma, void* (*malloc)(size_t), void (*free)(void*));
290 LIQ_PRIVATE bool pam_computeacolorhash(struct acolorhash_table *acht, const rgba_pixel *const pixels[], unsigned int cols, unsigned int rows, const unsigned char *importance_map);
291
292 LIQ_PRIVATE void pam_freeacolorhist(histogram *h);
293
294 LIQ_PRIVATE colormap *pam_colormap(unsigned int colors, void* (*malloc)(size_t), void (*free)(void*));
295 LIQ_PRIVATE colormap *pam_duplicate_colormap(colormap *map);
296 LIQ_PRIVATE void pam_freecolormap(colormap *c);
297
298 #endif
299