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