1
2 #include "libimagequant.h"
3 #include "pam.h"
4 #include "viter.h"
5 #include "nearest.h"
6 #include <stdlib.h>
7 #include <string.h>
8
9 #ifdef _OPENMP
10 #include <omp.h>
11 #else
12 #define omp_get_max_threads() 1
13 #define omp_get_thread_num() 0
14 #endif
15
16 /*
17 * Voronoi iteration: new palette color is computed from weighted average of colors that map to that palette entry.
18 */
19 LIQ_PRIVATE void
viter_init(const colormap * map,const unsigned int max_threads,viter_state average_color[])20 viter_init (const colormap * map, const unsigned int max_threads,
21 viter_state average_color[])
22 {
23 memset (average_color, 0,
24 sizeof (average_color[0]) * (VITER_CACHE_LINE_GAP +
25 map->colors) * max_threads);
26 }
27
28 LIQ_PRIVATE void
viter_update_color(const f_pixel acolor,const float value,const colormap * map,unsigned int match,const unsigned int thread,viter_state average_color[])29 viter_update_color (const f_pixel acolor, const float value,
30 const colormap * map, unsigned int match, const unsigned int thread,
31 viter_state average_color[])
32 {
33 match += thread * (VITER_CACHE_LINE_GAP + map->colors);
34 average_color[match].a += acolor.a * value;
35 average_color[match].r += acolor.r * value;
36 average_color[match].g += acolor.g * value;
37 average_color[match].b += acolor.b * value;
38 average_color[match].total += value;
39 }
40
41 LIQ_PRIVATE void
viter_finalize(colormap * map,const unsigned int max_threads,const viter_state average_color[])42 viter_finalize (colormap * map, const unsigned int max_threads,
43 const viter_state average_color[])
44 {
45 for (unsigned int i = 0; i < map->colors; i++) {
46 double a = 0, r = 0, g = 0, b = 0, total = 0;
47
48 // Aggregate results from all threads
49 for (unsigned int t = 0; t < max_threads; t++) {
50 const unsigned int offset = (VITER_CACHE_LINE_GAP + map->colors) * t + i;
51
52 a += average_color[offset].a;
53 r += average_color[offset].r;
54 g += average_color[offset].g;
55 b += average_color[offset].b;
56 total += average_color[offset].total;
57 }
58
59 if (total && !map->palette[i].fixed) {
60 map->palette[i].acolor = (f_pixel) {
61 .a = a / total,.r = r / total,.g = g / total,.b = b / total,};
62 } else {
63 total = i / 1024.0;
64 }
65 map->palette[i].popularity = total;
66 }
67 }
68
69 LIQ_PRIVATE double
viter_do_iteration(histogram * hist,colormap * const map,const float min_opaque_val,viter_callback callback,const bool fast_palette)70 viter_do_iteration (histogram * hist, colormap * const map,
71 const float min_opaque_val, viter_callback callback,
72 const bool fast_palette)
73 {
74 viter_state *average_color;
75 const unsigned int max_threads = omp_get_max_threads ();
76 double total_diff = 0;
77
78 average_color =
79 g_alloca (sizeof (viter_state) * (VITER_CACHE_LINE_GAP +
80 map->colors) * max_threads);
81
82 viter_init (map, max_threads, average_color);
83 {
84 struct nearest_map *const n = nearest_init (map, fast_palette);
85 hist_item *const achv = hist->achv;
86 const int hist_size = hist->size;
87 int j;
88
89 #pragma omp parallel for if (hist_size > 3000) \
90 schedule(static) default(none) shared(average_color,callback) reduction(+:total_diff)
91 for (j = 0; j < hist_size; j++) {
92 float diff;
93 unsigned int match =
94 nearest_search (n, achv[j].acolor, achv[j].tmp.likely_colormap_index,
95 min_opaque_val, &diff);
96 achv[j].tmp.likely_colormap_index = match;
97 total_diff += diff * achv[j].perceptual_weight;
98
99 viter_update_color (achv[j].acolor, achv[j].perceptual_weight, map, match,
100 omp_get_thread_num (), average_color);
101
102 if (callback)
103 callback (&achv[j], diff);
104 }
105
106 nearest_free (n);
107 }
108 viter_finalize (map, max_threads, average_color);
109
110 return total_diff / hist->total_perceptual_weight;
111 }
112