← Back to branch summary

~ubuntu-branches/debian/stretch/pngquant/stretch

« back to all changes in this revision

Viewing changes to lib/nearest.c

  • Committer: Package Import Robot
  • Author(s): Andreas Tille
  • Date: 2014-10-07 09:19:38 UTC
  • mfrom: (1.1.3)
  • Revision ID: package-import@ubuntu.com-20141007091938-jmu20wvmi6hd2nb3
Tags: 2.3.0-1
* New upstream version
* cme fix dpkg-control
* d/copyright: Fix some DEP5 names
* d/rules: cope with hand-written configure script

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/nearest.c
5
5
#include "mempool.h"
6
6
#include <stdlib.h>
7
7
 
8
 
struct color_entry {
9
 
    f_pixel color;
10
 
    unsigned int index;
11
 
};
12
 
 
13
8
struct sorttmp {
14
9
    float radius;
15
10
    unsigned int index;
20
15
    f_pixel vantage_point;
21
16
    float radius;
22
17
    unsigned int num_candidates;
23
 
    struct color_entry *candidates;
 
18
    f_pixel *candidates_color;
 
19
    unsigned short *candidates_index;
24
20
};
25
21
 
26
22
struct nearest_map {
27
 
    struct head *heads;
28
23
    const colormap *map;
29
24
    float nearest_other_color_dist[256];
30
25
    mempool mempool;
 
26
    struct head heads[];
31
27
};
32
28
 
33
 
static int find_slow(const f_pixel px, const colormap *map)
 
29
static unsigned int find_slow(const f_pixel px, const colormap *map)
34
30
{
35
 
    int best=0;
 
31
    unsigned int best=0;
36
32
    float bestdiff = colordifference(px, map->palette[0].acolor);
37
33
 
38
34
    for(unsigned int i=1; i < map->colors; i++) {
83
79
    num_candidates = MIN(colorsused, num_candidates);
84
80
 
85
81
    struct head h = {
86
 
        .candidates = mempool_alloc(m, num_candidates * sizeof(h.candidates[0]), 0),
 
82
        .candidates_color = mempool_alloc(m, num_candidates * sizeof(h.candidates_color[0]), 0),
 
83
        .candidates_index = mempool_alloc(m, num_candidates * sizeof(h.candidates_index[0]), 0),
87
84
        .vantage_point = px,
88
85
        .num_candidates = num_candidates,
89
86
    };
90
87
    for(unsigned int i=0; i < num_candidates; i++) {
91
 
        h.candidates[i] = (struct color_entry) {
92
 
            .color = map->palette[colors[i].index].acolor,
93
 
            .index = colors[i].index,
94
 
        };
 
88
        h.candidates_color[i] = map->palette[colors[i].index].acolor;
 
89
        h.candidates_index[i] = colors[i].index;
95
90
    }
96
91
    // if all colors within this radius are included in candidates, then there cannot be any other better match
97
92
    // farther away from the vantage point than half of the radius. Due to alpha channel must assume pessimistic radius.
98
 
    h.radius = min_colordifference(px, h.candidates[num_candidates-1].color)/4.0f; // /4 = half of radius, but radius is squared
 
93
    h.radius = min_colordifference(px, h.candidates_color[num_candidates-1])/4.0f; // /4 = half of radius, but radius is squared
99
94
 
100
95
    for(unsigned int i=0; i < num_candidates; i++) {
101
96
        // divide again as that's matching certain subset within radius-limited subset
127
122
LIQ_PRIVATE struct nearest_map *nearest_init(const colormap *map, bool fast)
128
123
{
129
124
    colormap *subset_palette = get_subset_palette(map);
 
125
    const unsigned int num_vantage_points = map->colors > 16 ? MIN(map->colors/4, subset_palette->colors) : 0;
 
126
    const unsigned long heads_size = sizeof(struct head) * (num_vantage_points+1); // +1 is fallback head
130
127
 
131
 
    const unsigned long mempool_size = sizeof(struct color_entry) * subset_palette->colors * map->colors/5 + (1<<14);
 
128
    const unsigned long mempool_size = (sizeof(f_pixel) + sizeof(unsigned int)) * subset_palette->colors * map->colors/5 + (1<<14);
132
129
    mempool m = NULL;
133
 
    struct nearest_map *centroids = mempool_create(&m, sizeof(*centroids), mempool_size, map->malloc, map->free);
 
130
    struct nearest_map *centroids = mempool_create(&m, sizeof(*centroids) + heads_size /* heads array is appended to it */, mempool_size, map->malloc, map->free);
134
131
    centroids->mempool = m;
135
132
 
136
133
    for(unsigned int i=0; i < map->colors; i++) {
144
141
    assert(map->colors > 0);
145
142
    bool skip_index[map->colors]; for(unsigned int j=0; j < map->colors; j++) skip_index[j]=false;
146
143
 
147
 
 
148
 
    const unsigned int num_vantage_points = map->colors > 16 ? MIN(map->colors/4, subset_palette->colors) : 0;
149
 
    centroids->heads = mempool_alloc(&centroids->mempool, sizeof(centroids->heads[0])*(num_vantage_points+1), mempool_size); // +1 is fallback head
150
 
 
151
144
    // floats and colordifference calculations are not perfect
152
145
    const float error_margin = fast ? 0 : 8.f/256.f/256.f;
153
146
    unsigned int h=0;
216
209
        if (vantage_point_dist <= heads[i].radius) {
217
210
            assert(heads[i].num_candidates);
218
211
            unsigned int ind=0;
219
 
            float dist = colordifference(px, heads[i].candidates[0].color);
 
212
            float dist = colordifference(px, heads[i].candidates_color[0]);
220
213
 
221
214
            /* penalty for making holes in IE */
222
 
            if (iebug && heads[i].candidates[0].color.a < 1) {
 
215
            if (iebug && heads[i].candidates_color[0].a < 1) {
223
216
                dist += 1.f/1024.f;
224
217
            }
225
218
 
226
219
            for(unsigned int j=1; j < heads[i].num_candidates; j++) {
227
 
                float newdist = colordifference(px, heads[i].candidates[j].color);
 
220
                float newdist = colordifference(px, heads[i].candidates_color[j]);
228
221
 
229
222
                /* penalty for making holes in IE */
230
 
                if (iebug && heads[i].candidates[j].color.a < 1) {
 
223
                if (iebug && heads[i].candidates_color[j].a < 1) {
231
224
                    newdist += 1.f/1024.f;
232
225
                }
233
226
 
237
230
                }
238
231
            }
239
232
            if (diff) *diff = dist;
240
 
            return heads[i].candidates[ind].index;
 
233
            return heads[i].candidates_index[ind];
241
234
        }
242
235
    }
243
236
}