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