1 /* pam.c - pam (portable alpha map) utility library
2 **
3 ** Copyright (C) 1989, 1991 by Jef Poskanzer.
4 ** Copyright (C) 1997, 2000, 2002 by Greg Roelofs; based on an idea by
5 ** Stefan Schneider.
6 ** © 2009-2013 by Kornel Lesinski.
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 #include <stdlib.h>
17 #include <string.h>
18
19 #include "libimagequant.h"
20 #include "pam.h"
21 #include "mempool.h"
22
23 /* *INDENT-OFF* */
24 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)25 pam_computeacolorhash (struct acolorhash_table *acht,
26 const rgba_pixel * const pixels[], unsigned int cols, unsigned int rows,
27 const unsigned char *importance_map)
28 /* *INDENT-ON* */
29 {
30 const unsigned int maxacolors = acht->maxcolors, ignorebits =
31 acht->ignorebits;
32 const unsigned int channel_mask = 255U >> ignorebits << ignorebits;
33 const unsigned int channel_hmask = (255U >> ignorebits) ^ 0xFFU;
34 const unsigned int posterize_mask =
35 channel_mask << 24 | channel_mask << 16 | channel_mask << 8 |
36 channel_mask;
37 const unsigned int posterize_high_mask =
38 channel_hmask << 24 | channel_hmask << 16 | channel_hmask << 8 |
39 channel_hmask;
40 struct acolorhist_arr_head *const buckets = acht->buckets;
41
42 unsigned int colors = acht->colors;
43 const unsigned int hash_size = acht->hash_size;
44
45 const unsigned int stacksize =
46 sizeof (acht->freestack) / sizeof (acht->freestack[0]);
47 struct acolorhist_arr_item **freestack = acht->freestack;
48 unsigned int freestackp = acht->freestackp;
49
50 /* Go through the entire image, building a hash table of colors. */
51 for (unsigned int row = 0; row < rows; ++row) {
52
53 float boost = 1.0;
54 for (unsigned int col = 0; col < cols; ++col) {
55 union rgba_as_int px = { pixels[row][col] };
56 unsigned int hash;
57 struct acolorhist_arr_head *achl;
58
59 if (importance_map) {
60 boost = 0.5f + (double) *importance_map++ / 255.f;
61 }
62 // RGBA color is casted to long for easier hasing/comparisons
63 if (!px.rgba.a) {
64 // "dirty alpha" has different RGBA values that end up being the same fully transparent color
65 px.l = 0;
66 hash = 0;
67 } else {
68 // mask posterizes all 4 channels in one go
69 px.l =
70 (px.l & posterize_mask) | ((px.l & posterize_high_mask) >> (8 -
71 ignorebits));
72 // fancier hashing algorithms didn't improve much
73 hash = px.l % hash_size;
74 }
75
76 /* head of the hash function stores first 2 colors inline (achl->used = 1..2),
77 to reduce number of allocations of achl->other_items.
78 */
79 achl = &buckets[hash];
80 if (achl->inline1.color.l == px.l && achl->used) {
81 achl->inline1.perceptual_weight += boost;
82 continue;
83 }
84 if (achl->used) {
85 if (achl->used > 1) {
86 struct acolorhist_arr_item *other_items;
87 unsigned int i = 0;
88 struct acolorhist_arr_item *new_items;
89 unsigned int capacity;
90
91 if (achl->inline2.color.l == px.l) {
92 achl->inline2.perceptual_weight += boost;
93 continue;
94 }
95 // other items are stored as an array (which gets reallocated if needed)
96 other_items = achl->other_items;
97 for (i = 0; i < achl->used - 2; i++) {
98 if (other_items[i].color.l == px.l) {
99 other_items[i].perceptual_weight += boost;
100 goto continue_outer_loop;
101 }
102 }
103
104 // the array was allocated with spare items
105 if (i < achl->capacity) {
106 other_items[i] = (struct acolorhist_arr_item) {
107 .color = px,.perceptual_weight = boost,};
108 achl->used++;
109 ++colors;
110 continue;
111 }
112
113 if (++colors > maxacolors) {
114 acht->colors = colors;
115 acht->freestackp = freestackp;
116 return false;
117 }
118
119 if (!other_items) { // there was no array previously, alloc "small" array
120 capacity = 8;
121 if (freestackp <= 0) {
122 // estimate how many colors are going to be + headroom
123 const int mempool_size =
124 ((acht->rows + rows - row) * 2 * colors / (acht->rows + row +
125 1) + 1024) * sizeof (struct acolorhist_arr_item);
126 new_items =
127 mempool_alloc (&acht->mempool,
128 sizeof (struct acolorhist_arr_item) * capacity, mempool_size);
129 } else {
130 // freestack stores previously freed (reallocated) arrays that can be reused
131 // (all pesimistically assumed to be capacity = 8)
132 new_items = freestack[--freestackp];
133 }
134 } else {
135 // simply reallocs and copies array to larger capacity
136 capacity = achl->capacity * 2 + 16;
137 if (freestackp < stacksize - 1) {
138 freestack[freestackp++] = other_items;
139 }
140
141 {
142 const int mempool_size =
143 ((acht->rows + rows - row) * 2 * colors / (acht->rows + row +
144 1) + 32 * capacity) * sizeof (struct acolorhist_arr_item);
145 new_items =
146 mempool_alloc (&acht->mempool,
147 sizeof (struct acolorhist_arr_item) * capacity, mempool_size);
148 }
149 if (!new_items)
150 return false;
151 memcpy (new_items, other_items,
152 sizeof (other_items[0]) * achl->capacity);
153 }
154
155 achl->other_items = new_items;
156 achl->capacity = capacity;
157 new_items[i] = (struct acolorhist_arr_item) {
158 .color = px,.perceptual_weight = boost,};
159 achl->used++;
160 } else {
161 // these are elses for first checks whether first and second inline-stored colors are used
162 achl->inline2.color.l = px.l;
163 achl->inline2.perceptual_weight = boost;
164 achl->used = 2;
165 ++colors;
166 }
167 } else {
168 achl->inline1.color.l = px.l;
169 achl->inline1.perceptual_weight = boost;
170 achl->used = 1;
171 ++colors;
172 }
173
174 continue_outer_loop:;
175 }
176
177 }
178 acht->colors = colors;
179 acht->cols = cols;
180 acht->rows += rows;
181 acht->freestackp = freestackp;
182 return true;
183 }
184
185 LIQ_PRIVATE struct acolorhash_table *
pam_allocacolorhash(unsigned int maxcolors,unsigned int surface,unsigned int ignorebits,void * (* malloc)(size_t),void (* free)(void *))186 pam_allocacolorhash (unsigned int maxcolors, unsigned int surface,
187 unsigned int ignorebits, void *(*malloc) (size_t), void (*free) (void *))
188 {
189 const unsigned int estimated_colors =
190 MIN (maxcolors, surface / (ignorebits + (surface > 512 * 512 ? 5 : 4)));
191 const unsigned int hash_size =
192 estimated_colors < 66000 ? 6673 : (estimated_colors <
193 200000 ? 12011 : 24019);
194
195 mempool m = NULL;
196 const unsigned int buckets_size =
197 hash_size * sizeof (struct acolorhist_arr_head);
198 const unsigned int mempool_size =
199 sizeof (struct acolorhash_table) + buckets_size +
200 estimated_colors * sizeof (struct acolorhist_arr_item);
201 struct acolorhash_table *t =
202 mempool_create (&m, sizeof (*t) + buckets_size, mempool_size, malloc,
203 free);
204 if (!t)
205 return NULL;
206 *t = (struct acolorhash_table) {
207 .mempool = m,.hash_size = hash_size,.maxcolors = maxcolors,.ignorebits =
208 ignorebits,};
209 memset (t->buckets, 0, hash_size * sizeof (struct acolorhist_arr_head));
210 return t;
211 }
212
213 #define PAM_ADD_TO_HIST(entry) { \
214 hist->achv[j].acolor = to_f(gamma_lut, entry.color.rgba); \
215 total_weight += hist->achv[j].adjusted_weight = hist->achv[j].perceptual_weight = MIN(entry.perceptual_weight, max_perceptual_weight); \
216 ++j; \
217 }
218
219 LIQ_PRIVATE histogram *
pam_acolorhashtoacolorhist(const struct acolorhash_table * acht,const double gamma,void * (* malloc)(size_t),void (* free)(void *))220 pam_acolorhashtoacolorhist (const struct acolorhash_table * acht,
221 const double gamma, void *(*malloc) (size_t), void (*free) (void *))
222 {
223 histogram *hist = malloc (sizeof (hist[0]));
224 float gamma_lut[256];
225 float max_perceptual_weight;
226 double total_weight;
227 unsigned int i, j, k;
228
229 if (!hist || !acht)
230 return NULL;
231 *hist = (histogram) {
232 .achv = malloc (acht->colors * sizeof (hist->achv[0])),.size =
233 acht->colors,.free = free,.ignorebits = acht->ignorebits,};
234 if (!hist->achv)
235 return NULL;
236
237 to_f_set_gamma (gamma_lut, gamma);
238
239 /* Limit perceptual weight to 1/10th of the image surface area to prevent
240 a single color from dominating all others. */
241 max_perceptual_weight = 0.1f * acht->cols * acht->rows;
242 total_weight = 0;
243
244 for (j = 0, i = 0; i < acht->hash_size; ++i) {
245 const struct acolorhist_arr_head *const achl = &acht->buckets[i];
246 if (achl->used) {
247 PAM_ADD_TO_HIST (achl->inline1);
248
249 if (achl->used > 1) {
250 PAM_ADD_TO_HIST (achl->inline2);
251
252 for (k = 0; k < achl->used - 2; k++) {
253 PAM_ADD_TO_HIST (achl->other_items[k]);
254 }
255 }
256 }
257 }
258
259 hist->total_perceptual_weight = total_weight;
260 return hist;
261 }
262
263
264 LIQ_PRIVATE void
pam_freeacolorhash(struct acolorhash_table * acht)265 pam_freeacolorhash (struct acolorhash_table *acht)
266 {
267 mempool_destroy (acht->mempool);
268 }
269
270 LIQ_PRIVATE void
pam_freeacolorhist(histogram * hist)271 pam_freeacolorhist (histogram * hist)
272 {
273 hist->free (hist->achv);
274 hist->free (hist);
275 }
276
277 LIQ_PRIVATE colormap *
pam_colormap(unsigned int colors,void * (* malloc)(size_t),void (* free)(void *))278 pam_colormap (unsigned int colors, void *(*malloc) (size_t),
279 void (*free) (void *))
280 {
281 const size_t colors_size = colors * sizeof (colormap_item);
282 colormap *map;
283
284 assert (colors > 0 && colors < 65536);
285
286 map = malloc (sizeof (colormap) + colors_size);
287 if (!map)
288 return NULL;
289 *map = (colormap) {
290 .malloc = malloc,.free = free,.subset_palette = NULL,.colors = colors,};
291 memset (map->palette, 0, colors_size);
292 return map;
293 }
294
295 LIQ_PRIVATE colormap *
pam_duplicate_colormap(colormap * map)296 pam_duplicate_colormap (colormap * map)
297 {
298 colormap *dupe = pam_colormap (map->colors, map->malloc, map->free);
299 for (unsigned int i = 0; i < map->colors; i++) {
300 dupe->palette[i] = map->palette[i];
301 }
302 if (map->subset_palette) {
303 dupe->subset_palette = pam_duplicate_colormap (map->subset_palette);
304 }
305 return dupe;
306 }
307
308 LIQ_PRIVATE void
pam_freecolormap(colormap * c)309 pam_freecolormap (colormap * c)
310 {
311 if (c->subset_palette)
312 pam_freecolormap (c->subset_palette);
313 c->free (c);
314 }
315
316 LIQ_PRIVATE void
to_f_set_gamma(float gamma_lut[],const double gamma)317 to_f_set_gamma (float gamma_lut[], const double gamma)
318 {
319 for (int i = 0; i < 256; i++) {
320 gamma_lut[i] = pow ((double) i / 255.0, internal_gamma / gamma);
321 }
322 }
323