Line data Source code
1 : /*
2 : * SPDX-License-Identifier: GPL-3.0-or-later
3 : *
4 : * This file is part of colopresso
5 : *
6 : * Copyright (C) 2025 COLOPL, Inc.
7 : *
8 : * Author: Go Kudo <g-kudo@colopl.co.jp>
9 : * Developed with AI (LLM) code assistance. See `NOTICE` for details.
10 : */
11 :
12 : #include <limits.h>
13 : #include <math.h>
14 : #include <stdio.h>
15 : #include <stdlib.h>
16 : #include <string.h>
17 :
18 : #include <png.h>
19 :
20 : #include "internal/log.h"
21 : #include "internal/pngx_common.h"
22 :
23 : typedef struct {
24 : uint32_t color;
25 : uint32_t count;
26 : uint32_t mapped_color;
27 : uint8_t detail_bits_rgb;
28 : uint8_t detail_bits_alpha;
29 : bool locked;
30 : } pngx_color_entry_t;
31 :
32 : typedef struct {
33 : pngx_color_entry_t *entries;
34 : size_t count;
35 : size_t unlocked_count;
36 : } pngx_color_histogram_t;
37 :
38 : typedef struct {
39 : uint32_t color;
40 : uint16_t weight;
41 : uint8_t rgb_bits;
42 : uint8_t alpha_bits;
43 : } pngx_histogram_sample_t;
44 :
45 : typedef struct {
46 : size_t start;
47 : size_t end;
48 : uint8_t min_r;
49 : uint8_t min_g;
50 : uint8_t min_b;
51 : uint8_t min_a;
52 : uint8_t max_r;
53 : uint8_t max_g;
54 : uint8_t max_b;
55 : uint8_t max_a;
56 : uint64_t total_weight;
57 : } pngx_color_box_t;
58 :
59 : typedef struct {
60 : uint32_t color;
61 : uint32_t mapped_color;
62 : } pngx_color_map_entry_t;
63 :
64 : typedef struct {
65 : uint32_t color;
66 : uint32_t count;
67 : } pngx_color_freq_t;
68 :
69 : typedef struct {
70 : size_t index;
71 : uint32_t count;
72 : uint32_t color;
73 : } pngx_freq_rank_t;
74 :
75 290060 : static int compare_entries_r(const void *lhs, const void *rhs) {
76 290060 : const pngx_color_entry_t *a = (const pngx_color_entry_t *)lhs, *b = (const pngx_color_entry_t *)rhs;
77 290060 : uint8_t av = (uint8_t)(a->color & 0xff), bv = (uint8_t)(b->color & 0xff);
78 :
79 290060 : return (av < bv) ? -1 : ((av > bv) ? 1 : 0);
80 : }
81 :
82 213350 : static int compare_entries_g(const void *lhs, const void *rhs) {
83 213350 : const pngx_color_entry_t *a = (const pngx_color_entry_t *)lhs, *b = (const pngx_color_entry_t *)rhs;
84 213350 : uint8_t av = (uint8_t)((a->color >> 8) & 0xff), bv = (uint8_t)((b->color >> 8) & 0xff);
85 :
86 213350 : return (av < bv) ? -1 : ((av > bv) ? 1 : 0);
87 : }
88 :
89 103592 : static int compare_entries_b(const void *lhs, const void *rhs) {
90 103592 : const pngx_color_entry_t *a = (const pngx_color_entry_t *)lhs, *b = (const pngx_color_entry_t *)rhs;
91 103592 : uint8_t av = (uint8_t)((a->color >> 16) & 0xff), bv = (uint8_t)((b->color >> 16) & 0xff);
92 :
93 103592 : return (av < bv) ? -1 : ((av > bv) ? 1 : 0);
94 : }
95 :
96 144554 : static int compare_entries_a(const void *lhs, const void *rhs) {
97 144554 : const pngx_color_entry_t *a = (const pngx_color_entry_t *)lhs, *b = (const pngx_color_entry_t *)rhs;
98 144554 : uint8_t av = (uint8_t)((a->color >> 24) & 0xff), bv = (uint8_t)((b->color >> 24) & 0xff);
99 :
100 144554 : return (av < bv) ? -1 : ((av > bv) ? 1 : 0);
101 : }
102 :
103 18 : static inline uint32_t compute_grid_capacity(uint8_t bits_rgb, uint8_t bits_alpha) {
104 : uint64_t capacity;
105 18 : uint32_t rgb_levels = 1, alpha_levels = 1;
106 :
107 18 : bits_rgb = clamp_reduced_bits(bits_rgb);
108 18 : bits_alpha = clamp_reduced_bits(bits_alpha);
109 :
110 18 : if (bits_rgb < 8) {
111 14 : rgb_levels = (uint32_t)1 << bits_rgb;
112 14 : rgb_levels = rgb_levels * rgb_levels * rgb_levels;
113 : } else {
114 4 : rgb_levels = UINT32_MAX;
115 : }
116 :
117 18 : if (bits_alpha < 8) {
118 18 : alpha_levels = (uint32_t)1 << bits_alpha;
119 : } else {
120 0 : alpha_levels = UINT32_MAX;
121 : }
122 :
123 18 : if (rgb_levels == UINT32_MAX || alpha_levels == UINT32_MAX) {
124 4 : return (uint32_t)COLOPRESSO_PNGX_REDUCED_COLORS_MAX;
125 : }
126 :
127 14 : capacity = (uint64_t)rgb_levels * (uint64_t)alpha_levels;
128 14 : if (capacity > (uint64_t)COLOPRESSO_PNGX_REDUCED_COLORS_MAX) {
129 8 : capacity = (uint64_t)COLOPRESSO_PNGX_REDUCED_COLORS_MAX;
130 : }
131 :
132 14 : return (uint32_t)capacity;
133 : }
134 :
135 9238467 : static inline uint32_t pack_rgba_u32(uint8_t r, uint8_t g, uint8_t b, uint8_t a) { return ((uint32_t)a << 24) | ((uint32_t)b << 16) | ((uint32_t)g << 8) | (uint32_t)r; }
136 :
137 4565 : static uint32_t box_representative_color(const pngx_color_entry_t *entries, const pngx_color_box_t *box) {
138 : size_t i;
139 4565 : uint64_t sum_r = 0, sum_g = 0, sum_b = 0, sum_a = 0, total = 0, weight;
140 : uint32_t c;
141 :
142 4565 : if (!entries || !box) {
143 0 : return 0;
144 : }
145 21498 : for (i = box->start; i < box->end; ++i) {
146 16933 : c = entries[i].color;
147 16933 : weight = (uint64_t)entries[i].count;
148 16933 : sum_r += (uint64_t)(c & 0xff) * weight;
149 16933 : sum_g += (uint64_t)((c >> 8) & 0xff) * weight;
150 16933 : sum_b += (uint64_t)((c >> 16) & 0xff) * weight;
151 16933 : sum_a += (uint64_t)((c >> 24) & 0xff) * weight;
152 16933 : total += weight;
153 : }
154 :
155 4565 : if (total == 0) {
156 0 : return entries[box->start].color;
157 : }
158 :
159 4565 : sum_r = (sum_r + (total / 2)) / total;
160 4565 : sum_g = (sum_g + (total / 2)) / total;
161 4565 : sum_b = (sum_b + (total / 2)) / total;
162 4565 : sum_a = (sum_a + (total / 2)) / total;
163 :
164 4565 : return pack_rgba_u32((uint8_t)sum_r, (uint8_t)sum_g, (uint8_t)sum_b, (uint8_t)sum_a);
165 : }
166 :
167 381372496 : static inline uint8_t color_component(uint32_t color, uint8_t channel) { return (uint8_t)((color >> (channel * 8)) & 0xff); }
168 :
169 47671562 : static inline uint32_t color_distance_sq_u32(uint32_t lhs, uint32_t rhs) {
170 47671562 : int32_t dr = (int32_t)color_component(lhs, 0) - (int32_t)color_component(rhs, 0), dg = (int32_t)color_component(lhs, 1) - (int32_t)color_component(rhs, 1),
171 47671562 : db = (int32_t)color_component(lhs, 2) - (int32_t)color_component(rhs, 2), da = (int32_t)color_component(lhs, 3) - (int32_t)color_component(rhs, 3);
172 :
173 47671562 : return (uint32_t)(dr * dr + dg * dg + db * db + da * da);
174 : }
175 :
176 1037047 : static inline void unpack_rgba_u32(uint32_t color, uint8_t *r, uint8_t *g, uint8_t *b, uint8_t *a) {
177 1037047 : if (r) {
178 1037047 : *r = (uint8_t)(color & 0xff);
179 : }
180 :
181 1037047 : if (g) {
182 1037047 : *g = (uint8_t)((color >> 8) & 0xff);
183 : }
184 :
185 1037047 : if (b) {
186 1037047 : *b = (uint8_t)((color >> 16) & 0xff);
187 : }
188 :
189 1037047 : if (a) {
190 1037047 : *a = (uint8_t)((color >> 24) & 0xff);
191 : }
192 1037047 : }
193 :
194 2424832 : static inline float importance_dither_scale(uint8_t importance_value) {
195 : float normalized, scale;
196 :
197 2424832 : normalized = (float)importance_value / PNGX_REDUCED_IMPORTANCE_SCALE_DENOM;
198 2424832 : scale = PNGX_REDUCED_IMPORTANCE_SCALE_MIN + (1.0f - normalized) * PNGX_REDUCED_IMPORTANCE_SCALE_RANGE;
199 :
200 2424832 : return scale < 0.0f ? 0.0f : (scale > 1.0f ? 1.0f : scale);
201 : }
202 :
203 8 : static inline void color_histogram_reset(pngx_color_histogram_t *hist) {
204 8 : if (!hist) {
205 0 : return;
206 : }
207 :
208 8 : free(hist->entries);
209 8 : hist->entries = NULL;
210 8 : hist->count = 0;
211 8 : hist->unlocked_count = 0;
212 : }
213 :
214 16937 : static inline bool is_protected_color(uint32_t color, const uint32_t *protected_colors, size_t protected_count) {
215 : size_t i;
216 :
217 16937 : if (!protected_colors || protected_count == 0) {
218 16933 : return false;
219 : }
220 :
221 10 : for (i = 0; i < protected_count; ++i) {
222 10 : if (protected_colors[i] == color) {
223 4 : return true;
224 : }
225 : }
226 :
227 0 : return false;
228 : }
229 :
230 2491400 : static inline uint16_t histogram_importance_weight(const pngx_quant_support_t *support, size_t pixel_index) {
231 : const uint8_t *map;
232 : uint16_t weight;
233 : uint8_t importance;
234 :
235 2491400 : if (!support || !support->importance_map || pixel_index >= support->importance_map_len) {
236 66568 : return 1;
237 : }
238 :
239 2424832 : map = support->importance_map;
240 2424832 : importance = map[pixel_index];
241 :
242 2424832 : weight = 1 + (uint16_t)(importance >> PNGX_REDUCED_IMPORTANCE_WEIGHT_SHIFT);
243 2424832 : if (importance > PNGX_REDUCED_IMPORTANCE_WEIGHT_THRESHOLD_STRONG) {
244 23900 : weight += PNGX_REDUCED_IMPORTANCE_WEIGHT_BONUS_STRONG;
245 2400932 : } else if (importance > PNGX_REDUCED_IMPORTANCE_WEIGHT_THRESHOLD_HIGH) {
246 545339 : weight += PNGX_REDUCED_IMPORTANCE_WEIGHT_BONUS_HIGH;
247 1855593 : } else if (importance > PNGX_REDUCED_IMPORTANCE_WEIGHT_THRESHOLD_MEDIUM) {
248 1190152 : weight += PNGX_REDUCED_IMPORTANCE_WEIGHT_BONUS_MEDIUM;
249 : }
250 :
251 2424832 : if (weight > PNGX_REDUCED_IMPORTANCE_WEIGHT_CAP) {
252 0 : weight = PNGX_REDUCED_IMPORTANCE_WEIGHT_CAP;
253 : }
254 :
255 2424832 : return weight;
256 : }
257 :
258 39340728 : static inline int compare_histogram_sample(const void *lhs, const void *rhs) {
259 39340728 : const pngx_histogram_sample_t *a = (const pngx_histogram_sample_t *)lhs, *b = (const pngx_histogram_sample_t *)rhs;
260 :
261 39340728 : return a->color < b->color ? -1 : (a->color > b->color ? 1 : 0);
262 : }
263 :
264 9123 : static inline void color_box_refresh(const pngx_color_entry_t *entries, pngx_color_box_t *box) {
265 : size_t i;
266 : uint32_t c;
267 : uint8_t r, g, b, a;
268 :
269 9123 : if (!entries || !box || box->end <= box->start) {
270 0 : return;
271 : }
272 :
273 9123 : box->min_r = 255;
274 9123 : box->min_g = 255;
275 9123 : box->min_b = 255;
276 9123 : box->min_a = 255;
277 9123 : box->max_r = 0;
278 9123 : box->max_g = 0;
279 9123 : box->max_b = 0;
280 9123 : box->max_a = 0;
281 9123 : box->total_weight = 0;
282 167036 : for (i = box->start; i < box->end; ++i) {
283 157913 : c = entries[i].color;
284 157913 : r = (uint8_t)(c & 0xff);
285 157913 : g = (uint8_t)((c >> 8) & 0xff);
286 157913 : b = (uint8_t)((c >> 16) & 0xff);
287 157913 : a = (uint8_t)((c >> 24) & 0xff);
288 157913 : if (r < box->min_r) {
289 15732 : box->min_r = r;
290 : }
291 157913 : if (r > box->max_r) {
292 16254 : box->max_r = r;
293 : }
294 157913 : if (g < box->min_g) {
295 10480 : box->min_g = g;
296 : }
297 157913 : if (g > box->max_g) {
298 14455 : box->max_g = g;
299 : }
300 157913 : if (b < box->min_b) {
301 10909 : box->min_b = b;
302 : }
303 157913 : if (b > box->max_b) {
304 18039 : box->max_b = b;
305 : }
306 157913 : if (a < box->min_a) {
307 8445 : box->min_a = a;
308 : }
309 157913 : if (a > box->max_a) {
310 12590 : box->max_a = a;
311 : }
312 157913 : box->total_weight += (uint64_t)entries[i].count;
313 : }
314 : }
315 :
316 55863128 : static inline int compare_u32(const void *lhs, const void *rhs) {
317 55863128 : uint32_t a = *(const uint32_t *)lhs, b = *(const uint32_t *)rhs;
318 :
319 55863128 : if (a < b) {
320 14669942 : return -1;
321 : }
322 :
323 41193186 : if (a > b) {
324 24983195 : return 1;
325 : }
326 :
327 16209991 : return 0;
328 : }
329 :
330 3202653 : static inline bool color_box_splittable(const pngx_color_box_t *box) { return box && box->end > box->start + 1; }
331 :
332 952896 : static inline uint8_t color_box_max_span(const pngx_color_box_t *box) {
333 952896 : uint8_t span_r = box->max_r - box->min_r, span_g = box->max_g - box->min_g, span_b = box->max_b - box->min_b, span_a = box->max_a - box->min_a, span = span_r;
334 :
335 952896 : return span_g > span ? span_g : (span_b > span ? span_b : (span_a > span ? span_a : span));
336 : }
337 :
338 952896 : static inline float color_box_detail_bias(const pngx_color_entry_t *entries, const pngx_color_box_t *box, uint8_t base_bits_rgb, uint8_t base_bits_alpha) {
339 : const pngx_color_entry_t *entry;
340 952896 : uint64_t weight = 0, w, accum_x2 = 0;
341 : uint32_t delta_rgb, delta_alpha, score_x2;
342 : size_t idx;
343 :
344 952896 : if (!entries || !box || box->end <= box->start) {
345 0 : return 0.0f;
346 : }
347 :
348 11931878 : for (idx = box->start; idx < box->end; ++idx) {
349 10978982 : entry = &entries[idx];
350 10978982 : w = entry->count ? entry->count : 1;
351 10978982 : delta_rgb = (entry->detail_bits_rgb > base_bits_rgb) ? (uint32_t)(entry->detail_bits_rgb - base_bits_rgb) : 0;
352 10978982 : delta_alpha = (entry->detail_bits_alpha > base_bits_alpha) ? (uint32_t)(entry->detail_bits_alpha - base_bits_alpha) : 0;
353 10978982 : score_x2 = (delta_rgb << 1) + delta_alpha;
354 :
355 10978982 : if (score_x2 > 0) {
356 5078465 : accum_x2 += (uint64_t)score_x2 * w;
357 : }
358 10978982 : weight += w;
359 : }
360 :
361 952896 : if (weight == 0) {
362 0 : return 0.0f;
363 : }
364 :
365 952896 : return (float)accum_x2 / (float)(weight * 2);
366 : }
367 :
368 4558 : static inline int select_box_to_split(const pngx_color_box_t *boxes, size_t box_count, const pngx_color_entry_t *entries, uint8_t base_bits_rgb, uint8_t base_bits_alpha) {
369 : size_t i;
370 4558 : float best_priority = -1.0f, detail_bias, span_score, weight_score, priority;
371 4558 : int best_index = -1;
372 :
373 4558 : if (!boxes || box_count == 0) {
374 0 : return -1;
375 : }
376 :
377 3202653 : for (i = 0; i < box_count; ++i) {
378 3198095 : if (!color_box_splittable(&boxes[i])) {
379 2245199 : continue;
380 : }
381 :
382 952896 : detail_bias = color_box_detail_bias(entries, &boxes[i], base_bits_rgb, base_bits_alpha);
383 952896 : span_score = (float)color_box_max_span(&boxes[i]) / 255.0f;
384 952896 : weight_score = (boxes[i].total_weight > 0) ? logf((float)boxes[i].total_weight + 1.0f) : 0.0f;
385 952896 : priority = (span_score * PNGX_REDUCED_PRIORITY_SPAN_WEIGHT) + (detail_bias * PNGX_REDUCED_PRIORITY_DETAIL_WEIGHT) + (weight_score * PNGX_REDUCED_PRIORITY_MASS_WEIGHT);
386 :
387 952896 : if (priority > best_priority) {
388 25538 : best_priority = priority;
389 25538 : best_index = (int)i;
390 : }
391 : }
392 :
393 4558 : return best_index;
394 : }
395 :
396 4558 : static inline size_t box_find_split_index(const pngx_color_entry_t *entries, const pngx_color_box_t *box) {
397 4558 : uint64_t half, accum = 0;
398 : size_t idx;
399 :
400 4558 : if (!entries || !box || box->end <= box->start) {
401 0 : return box ? box->start : 0;
402 : }
403 :
404 4558 : half = box->total_weight / 2;
405 4558 : if (half == 0) {
406 0 : half = 1;
407 : }
408 :
409 67505 : for (idx = box->start; idx < box->end; ++idx) {
410 67505 : accum += (uint64_t)entries[idx].count;
411 67505 : if (accum >= half) {
412 4558 : return idx;
413 : }
414 : }
415 :
416 0 : return box->start + ((box->end - box->start) / 2);
417 : }
418 :
419 4558 : static inline void sort_entries_by_axis(pngx_color_entry_t *entries, size_t count, int axis) {
420 4558 : if (!entries || count == 0) {
421 0 : return;
422 : }
423 :
424 4558 : switch (axis) {
425 1294 : case 0:
426 1294 : qsort(entries, count, sizeof(pngx_color_entry_t), compare_entries_r);
427 1294 : break;
428 1213 : case 1:
429 1213 : qsort(entries, count, sizeof(pngx_color_entry_t), compare_entries_g);
430 1213 : break;
431 1220 : case 2:
432 1220 : qsort(entries, count, sizeof(pngx_color_entry_t), compare_entries_b);
433 1220 : break;
434 831 : case 3:
435 831 : qsort(entries, count, sizeof(pngx_color_entry_t), compare_entries_a);
436 831 : break;
437 0 : default:
438 0 : qsort(entries, count, sizeof(pngx_color_entry_t), compare_entries_r);
439 0 : break;
440 : }
441 : }
442 :
443 4558 : static inline bool split_color_box(pngx_color_entry_t *entries, pngx_color_box_t *box, pngx_color_box_t *new_box) {
444 : size_t split_index;
445 : int axis;
446 :
447 4558 : if (!entries || !box || !new_box || !color_box_splittable(box)) {
448 0 : return false;
449 : }
450 :
451 4558 : axis = 0;
452 4558 : if ((box->max_g - box->min_g) > (box->max_r - box->min_r)) {
453 1500 : axis = 1;
454 : }
455 4558 : if ((box->max_b - box->min_b) > (box->max_g - box->min_g) && (box->max_b - box->min_b) >= (box->max_r - box->min_r)) {
456 1278 : axis = 2;
457 : }
458 4558 : if ((box->max_a - box->min_a) > (box->max_b - box->min_b) && (box->max_a - box->min_a) >= (box->max_g - box->min_g) && (box->max_a - box->min_a) >= (box->max_r - box->min_r)) {
459 831 : axis = 3;
460 : }
461 :
462 4558 : sort_entries_by_axis(entries + box->start, box->end - box->start, axis);
463 :
464 4558 : split_index = box_find_split_index(entries, box);
465 4558 : if (split_index <= box->start) {
466 977 : split_index = box->start + 1;
467 : }
468 4558 : if (split_index >= box->end) {
469 0 : split_index = box->end - 1;
470 : }
471 :
472 4558 : new_box->start = split_index;
473 4558 : new_box->end = box->end;
474 4558 : box->end = split_index;
475 :
476 4558 : color_box_refresh(entries, box);
477 4558 : color_box_refresh(entries, new_box);
478 :
479 4558 : return true;
480 : }
481 :
482 152503 : static inline int compare_color_map_by_color(const void *lhs, const void *rhs) {
483 152503 : const pngx_color_map_entry_t *a = (const pngx_color_map_entry_t *)lhs, *b = (const pngx_color_map_entry_t *)rhs;
484 :
485 152503 : return a->color < b->color ? -1 : (a->color > b->color ? 1 : 0);
486 : }
487 :
488 145518 : static inline int compare_color_map_by_mapped(const void *lhs, const void *rhs) {
489 145518 : const pngx_color_map_entry_t *a = (const pngx_color_map_entry_t *)lhs, *b = (const pngx_color_map_entry_t *)rhs;
490 :
491 145518 : return a->mapped_color < b->mapped_color ? -1 : (a->mapped_color > b->mapped_color ? 1 : 0);
492 : }
493 :
494 2462854 : static inline const pngx_color_map_entry_t *find_color_mapping(const pngx_color_map_entry_t *map, size_t count, uint32_t color) {
495 2462854 : size_t left = 0, right = (count > 0) ? count - 1 : 0, mid;
496 :
497 2462854 : if (!map || count == 0) {
498 0 : return NULL;
499 : }
500 :
501 30603647 : while (left <= right) {
502 29094766 : mid = left + ((right - left) / 2);
503 :
504 29094766 : if (map[mid].color == color) {
505 878632 : return &map[mid];
506 : }
507 :
508 28216134 : if (map[mid].color < color) {
509 12347562 : left = mid + 1;
510 : } else {
511 15868572 : if (mid == 0) {
512 75341 : break;
513 : }
514 15793231 : right = mid - 1;
515 : }
516 : }
517 :
518 1584222 : return NULL;
519 : }
520 :
521 7 : static inline void refine_reduced_palette(pngx_color_entry_t *entries, size_t unlocked_count, const uint32_t *seed_palette, const uint8_t *palette_bits_rgb, const uint8_t *palette_bits_alpha,
522 : size_t palette_count) {
523 7 : const size_t max_iter = 3;
524 : size_t iter, best_index, candidate, i, p;
525 : uint64_t *sum_r, *sum_g, *sum_b, *sum_a, *sum_w, w;
526 : uint32_t *palette, color, best_dist, weight, dist, new_color;
527 : uint8_t r, g, b, a, snap_bits_rgb, snap_bits_alpha, cr, cg, cb, ca;
528 : bool palette_changed;
529 :
530 7 : if (!entries || unlocked_count == 0 || !seed_palette || palette_count == 0 || palette_count > 4096) {
531 0 : return;
532 : }
533 :
534 7 : palette = (uint32_t *)malloc(sizeof(uint32_t) * palette_count);
535 7 : if (!palette) {
536 0 : return;
537 : }
538 :
539 7 : memcpy(palette, seed_palette, sizeof(uint32_t) * palette_count);
540 :
541 7 : sum_r = (uint64_t *)malloc(sizeof(uint64_t) * palette_count);
542 7 : sum_g = (uint64_t *)malloc(sizeof(uint64_t) * palette_count);
543 7 : sum_b = (uint64_t *)malloc(sizeof(uint64_t) * palette_count);
544 7 : sum_a = (uint64_t *)malloc(sizeof(uint64_t) * palette_count);
545 7 : sum_w = (uint64_t *)malloc(sizeof(uint64_t) * palette_count);
546 :
547 7 : if (!sum_r || !sum_g || !sum_b || !sum_a || !sum_w) {
548 0 : free(sum_r);
549 0 : free(sum_g);
550 0 : free(sum_b);
551 0 : free(sum_a);
552 0 : free(sum_w);
553 0 : free(palette);
554 :
555 0 : return;
556 : }
557 :
558 21 : for (iter = 0; iter < max_iter; ++iter) {
559 17 : palette_changed = false;
560 :
561 17 : memset(sum_r, 0, sizeof(uint64_t) * palette_count);
562 17 : memset(sum_g, 0, sizeof(uint64_t) * palette_count);
563 17 : memset(sum_b, 0, sizeof(uint64_t) * palette_count);
564 17 : memset(sum_a, 0, sizeof(uint64_t) * palette_count);
565 17 : memset(sum_w, 0, sizeof(uint64_t) * palette_count);
566 :
567 47374 : for (i = 0; i < unlocked_count; ++i) {
568 47357 : color = entries[i].color;
569 47357 : best_dist = UINT32_MAX;
570 47357 : best_index = 0;
571 47357 : candidate = 0;
572 47357 : weight = entries[i].count ? entries[i].count : 1;
573 :
574 33876129 : for (candidate = 0; candidate < palette_count; ++candidate) {
575 33828772 : dist = color_distance_sq_u32(color, palette[candidate]);
576 33828772 : if (dist < best_dist) {
577 337174 : best_dist = dist;
578 337174 : best_index = candidate;
579 : }
580 : }
581 :
582 47357 : unpack_rgba_u32(color, &cr, &cg, &cb, &ca);
583 :
584 47357 : sum_r[best_index] += (uint64_t)cr * (uint64_t)weight;
585 47357 : sum_g[best_index] += (uint64_t)cg * (uint64_t)weight;
586 47357 : sum_b[best_index] += (uint64_t)cb * (uint64_t)weight;
587 47357 : sum_a[best_index] += (uint64_t)ca * (uint64_t)weight;
588 47357 : sum_w[best_index] += (uint64_t)weight;
589 : }
590 :
591 10974 : for (p = 0; p < palette_count; ++p) {
592 10957 : w = sum_w[p];
593 10957 : if (w == 0) {
594 78 : continue;
595 : }
596 10879 : r = (uint8_t)((sum_r[p] + (w / 2)) / w);
597 10879 : g = (uint8_t)((sum_g[p] + (w / 2)) / w);
598 10879 : b = (uint8_t)((sum_b[p] + (w / 2)) / w);
599 10879 : a = (uint8_t)((sum_a[p] + (w / 2)) / w);
600 10879 : snap_bits_rgb = palette_bits_rgb ? palette_bits_rgb[p] : COLOPRESSO_PNGX_REDUCED_BITS_MAX;
601 10879 : snap_bits_alpha = palette_bits_alpha ? palette_bits_alpha[p] : COLOPRESSO_PNGX_REDUCED_BITS_MAX;
602 10879 : snap_rgba_to_bits(&r, &g, &b, &a, snap_bits_rgb, snap_bits_alpha);
603 10879 : new_color = pack_rgba_u32(r, g, b, a);
604 10879 : if (new_color != palette[p]) {
605 831 : palette[p] = new_color;
606 831 : palette_changed = true;
607 : }
608 : }
609 :
610 17 : if (!palette_changed) {
611 3 : break;
612 : }
613 : }
614 :
615 16940 : for (i = 0; i < unlocked_count; ++i) {
616 16933 : color = entries[i].color;
617 16933 : best_dist = UINT32_MAX;
618 16933 : best_index = 0;
619 :
620 13258047 : for (candidate = 0; candidate < palette_count; ++candidate) {
621 13241114 : dist = color_distance_sq_u32(color, palette[candidate]);
622 13241114 : if (dist < best_dist) {
623 124418 : best_dist = dist;
624 124418 : best_index = candidate;
625 : }
626 : }
627 :
628 16933 : entries[i].mapped_color = palette[best_index];
629 : }
630 :
631 7 : free(sum_r);
632 7 : free(sum_g);
633 7 : free(sum_b);
634 7 : free(sum_a);
635 7 : free(sum_w);
636 :
637 7 : free(palette);
638 : }
639 :
640 8 : static inline bool build_color_histogram(const pngx_rgba_image_t *image, const pngx_options_t *opts, const pngx_quant_support_t *support, pngx_color_histogram_t *hist) {
641 8 : const cpres_rgba_color_t *protected_colors = (opts && opts->protected_colors_count > 0) ? opts->protected_colors : NULL;
642 8 : pngx_histogram_sample_t *samples = NULL;
643 : pngx_color_entry_t tmp;
644 8 : size_t pixel_count, i, unique_count, base, run, write, protected_count = (protected_colors && opts->protected_colors_count > 0) ? (size_t)opts->protected_colors_count : 0;
645 : uint64_t weight_sum;
646 : uint32_t protected_table[256], color;
647 8 : uint8_t bits_rgb = 8, bits_alpha = 8, r, g, b, a, sample_bits_rgb, sample_bits_alpha, hint, hint_rgb, hint_alpha, max_bits_rgb, max_bits_alpha;
648 8 : bool quantize_rgb = false, quantize_alpha = false;
649 :
650 8 : if (!image || !image->rgba || !hist || image->pixel_count == 0) {
651 0 : return false;
652 : }
653 :
654 8 : if (opts) {
655 8 : bits_rgb = clamp_reduced_bits(opts->lossy_reduced_bits_rgb);
656 8 : bits_alpha = clamp_reduced_bits(opts->lossy_reduced_alpha_bits);
657 : }
658 :
659 8 : quantize_rgb = bits_rgb < 8;
660 8 : quantize_alpha = bits_alpha < 8;
661 :
662 8 : if (protected_count > 256) {
663 0 : protected_count = 256;
664 : }
665 :
666 12 : for (i = 0; i < protected_count; ++i) {
667 4 : r = protected_colors[i].r;
668 4 : g = protected_colors[i].g;
669 4 : b = protected_colors[i].b;
670 4 : a = protected_colors[i].a;
671 4 : if (quantize_rgb) {
672 4 : r = quantize_bits(r, bits_rgb);
673 4 : g = quantize_bits(g, bits_rgb);
674 4 : b = quantize_bits(b, bits_rgb);
675 : }
676 4 : if (quantize_alpha) {
677 4 : a = quantize_bits(a, bits_alpha);
678 : }
679 4 : protected_table[i] = pack_rgba_u32(r, g, b, a);
680 : }
681 :
682 8 : pixel_count = image->pixel_count;
683 :
684 8 : samples = (pngx_histogram_sample_t *)malloc(pixel_count * sizeof(pngx_histogram_sample_t));
685 8 : if (!samples) {
686 0 : return false;
687 : }
688 :
689 2491408 : for (i = 0; i < pixel_count; ++i) {
690 2491400 : base = i * 4;
691 2491400 : r = image->rgba[base + 0];
692 2491400 : g = image->rgba[base + 1];
693 2491400 : b = image->rgba[base + 2];
694 2491400 : a = image->rgba[base + 3];
695 2491400 : sample_bits_rgb = bits_rgb;
696 2491400 : sample_bits_alpha = bits_alpha;
697 :
698 2491400 : if (support && support->bit_hint_map && i < support->bit_hint_len) {
699 2491400 : hint = support->bit_hint_map[i];
700 2491400 : hint_rgb = hint >> 4;
701 2491400 : hint_alpha = hint & 0x0fu;
702 :
703 2491400 : if (hint_rgb >= COLOPRESSO_PNGX_REDUCED_BITS_MIN) {
704 2491400 : sample_bits_rgb = clamp_reduced_bits(hint_rgb);
705 : }
706 :
707 2491400 : if (hint_alpha >= COLOPRESSO_PNGX_REDUCED_BITS_MIN) {
708 2491400 : sample_bits_alpha = clamp_reduced_bits(hint_alpha);
709 : }
710 : }
711 :
712 2491400 : if (quantize_rgb) {
713 2424840 : r = quantize_bits(r, bits_rgb);
714 2424840 : g = quantize_bits(g, bits_rgb);
715 2424840 : b = quantize_bits(b, bits_rgb);
716 : }
717 :
718 2491400 : if (quantize_alpha) {
719 2491400 : a = quantize_bits(a, bits_alpha);
720 : }
721 :
722 2491400 : samples[i].color = pack_rgba_u32(r, g, b, a);
723 2491400 : samples[i].weight = histogram_importance_weight(support, i);
724 2491400 : samples[i].rgb_bits = sample_bits_rgb;
725 2491400 : samples[i].alpha_bits = sample_bits_alpha;
726 : }
727 :
728 8 : qsort(samples, pixel_count, sizeof(pngx_histogram_sample_t), compare_histogram_sample);
729 :
730 8 : unique_count = 0;
731 :
732 16945 : for (i = 0; i < pixel_count;) {
733 16937 : color = samples[i].color;
734 16937 : run = 1;
735 :
736 2491400 : while (i + run < pixel_count && samples[i + run].color == color) {
737 2474463 : ++run;
738 : }
739 :
740 16937 : ++unique_count;
741 16937 : i += run;
742 : }
743 :
744 8 : hist->entries = (pngx_color_entry_t *)malloc(unique_count * sizeof(pngx_color_entry_t));
745 8 : if (!hist->entries) {
746 0 : free(samples);
747 0 : return false;
748 : }
749 8 : hist->count = unique_count;
750 8 : hist->unlocked_count = 0;
751 :
752 16945 : for (i = 0, unique_count = 0; i < pixel_count;) {
753 16937 : color = samples[i].color;
754 16937 : run = 1;
755 16937 : weight_sum = samples[i].weight;
756 16937 : max_bits_rgb = samples[i].rgb_bits;
757 16937 : max_bits_alpha = samples[i].alpha_bits;
758 :
759 2491400 : while (i + run < pixel_count && samples[i + run].color == color) {
760 2474463 : weight_sum += samples[i + run].weight;
761 :
762 2474463 : if (samples[i + run].rgb_bits > max_bits_rgb) {
763 770 : max_bits_rgb = samples[i + run].rgb_bits;
764 : }
765 :
766 2474463 : if (samples[i + run].alpha_bits > max_bits_alpha) {
767 540 : max_bits_alpha = samples[i + run].alpha_bits;
768 : }
769 :
770 2474463 : ++run;
771 : }
772 :
773 16937 : hist->entries[unique_count].color = color;
774 16937 : hist->entries[unique_count].count = (uint32_t)((weight_sum > UINT32_MAX) ? UINT32_MAX : weight_sum);
775 16937 : hist->entries[unique_count].mapped_color = color;
776 16937 : hist->entries[unique_count].locked = is_protected_color(color, protected_table, protected_count);
777 16937 : hist->entries[unique_count].detail_bits_rgb = clamp_reduced_bits(max_bits_rgb);
778 16937 : hist->entries[unique_count].detail_bits_alpha = clamp_reduced_bits(max_bits_alpha);
779 16937 : ++unique_count;
780 16937 : i += run;
781 : }
782 :
783 8 : free(samples);
784 :
785 8 : if (unique_count == 0) {
786 0 : return true;
787 : }
788 :
789 8 : write = 0;
790 :
791 16945 : for (i = 0; i < unique_count; ++i) {
792 16937 : if (!hist->entries[i].locked) {
793 16933 : if (write != i) {
794 0 : tmp = hist->entries[write];
795 0 : hist->entries[write] = hist->entries[i];
796 0 : hist->entries[i] = tmp;
797 : }
798 16933 : ++write;
799 : }
800 : }
801 8 : hist->unlocked_count = write;
802 :
803 8 : return true;
804 : }
805 :
806 7 : static inline bool apply_reduced_rgba32_quantization(pngx_color_histogram_t *hist, pngx_rgba_image_t *image, uint32_t target_colors, uint8_t bits_rgb, uint8_t bits_alpha, uint32_t *applied_colors) {
807 : const pngx_color_map_entry_t *mapping;
808 7 : pngx_color_box_t *boxes = NULL, new_box;
809 7 : pngx_color_map_entry_t *map = NULL;
810 7 : uint32_t *palette_seed = NULL, actual_colors = 0, mapped, original;
811 7 : uint8_t *palette_bits_rgb = NULL, *palette_bits_alpha = NULL, r, g, b, a, *px;
812 7 : size_t box_count = 0, map_count, i, idx;
813 : int split_index;
814 :
815 7 : if (!hist || !image || target_colors == 0) {
816 0 : if (applied_colors) {
817 0 : *applied_colors = (uint32_t)(hist ? hist->count : 0);
818 : }
819 :
820 0 : return true;
821 : }
822 :
823 7 : if (hist->unlocked_count == 0) {
824 0 : if (applied_colors) {
825 0 : *applied_colors = (uint32_t)hist->count;
826 : }
827 :
828 0 : return true;
829 : }
830 :
831 7 : if (target_colors > (uint32_t)hist->unlocked_count) {
832 0 : target_colors = (uint32_t)hist->unlocked_count;
833 : }
834 :
835 7 : if (target_colors == 0) {
836 0 : target_colors = 1;
837 : }
838 :
839 7 : boxes = (pngx_color_box_t *)calloc(target_colors, sizeof(pngx_color_box_t));
840 7 : if (!boxes) {
841 0 : return false;
842 : }
843 :
844 7 : boxes[0].start = 0;
845 7 : boxes[0].end = hist->unlocked_count;
846 7 : color_box_refresh(hist->entries, &boxes[0]);
847 7 : box_count = (boxes[0].end > boxes[0].start) ? 1 : 0;
848 :
849 4565 : while (box_count < target_colors) {
850 4558 : split_index = select_box_to_split(boxes, box_count, hist->entries, bits_rgb, bits_alpha);
851 4558 : if (split_index < 0) {
852 0 : break;
853 : }
854 :
855 4558 : if (!split_color_box(hist->entries, &boxes[split_index], &new_box)) {
856 0 : break;
857 : }
858 :
859 4558 : boxes[box_count++] = new_box;
860 : }
861 :
862 7 : if (box_count == 0) {
863 0 : free(boxes);
864 :
865 0 : if (applied_colors) {
866 0 : *applied_colors = (uint32_t)hist->count;
867 : }
868 :
869 0 : return true;
870 : }
871 :
872 7 : palette_seed = (uint32_t *)malloc(sizeof(uint32_t) * box_count);
873 7 : palette_bits_rgb = (uint8_t *)calloc(box_count, sizeof(uint8_t));
874 7 : palette_bits_alpha = (uint8_t *)calloc(box_count, sizeof(uint8_t));
875 7 : if (!palette_seed || !palette_bits_rgb || !palette_bits_alpha) {
876 0 : free(palette_seed);
877 0 : free(palette_bits_rgb);
878 0 : free(palette_bits_alpha);
879 0 : free(boxes);
880 :
881 0 : return false;
882 : }
883 :
884 4572 : for (i = 0; i < box_count; ++i) {
885 4565 : mapped = box_representative_color(hist->entries, &boxes[i]);
886 4565 : unpack_rgba_u32(mapped, &r, &g, &b, &a);
887 4565 : snap_rgba_to_bits(&r, &g, &b, &a, bits_rgb, bits_alpha);
888 4565 : mapped = pack_rgba_u32(r, g, b, a);
889 4565 : palette_seed[i] = mapped;
890 4565 : palette_bits_rgb[i] = bits_rgb;
891 4565 : palette_bits_alpha[i] = bits_alpha;
892 :
893 21498 : for (idx = boxes[i].start; idx < boxes[i].end; ++idx) {
894 16933 : hist->entries[idx].mapped_color = mapped;
895 : }
896 : }
897 :
898 7 : if (box_count > 0 && box_count <= 4096) {
899 7 : refine_reduced_palette(hist->entries, hist->unlocked_count, palette_seed, palette_bits_rgb, palette_bits_alpha, box_count);
900 : }
901 :
902 7 : for (i = hist->unlocked_count; i < hist->count; ++i) {
903 0 : hist->entries[i].mapped_color = hist->entries[i].color;
904 : }
905 :
906 7 : map_count = hist->count;
907 7 : if (map_count == 0) {
908 0 : free(palette_seed);
909 0 : free(palette_bits_rgb);
910 0 : free(palette_bits_alpha);
911 0 : free(boxes);
912 :
913 0 : if (applied_colors) {
914 0 : *applied_colors = 0;
915 : }
916 :
917 0 : return true;
918 : }
919 :
920 7 : map = (pngx_color_map_entry_t *)malloc(map_count * sizeof(pngx_color_map_entry_t));
921 7 : if (!map) {
922 0 : free(palette_seed);
923 0 : free(palette_bits_rgb);
924 0 : free(palette_bits_alpha);
925 0 : free(boxes);
926 0 : return false;
927 : }
928 :
929 16940 : for (i = 0; i < map_count; ++i) {
930 16933 : map[i].color = hist->entries[i].color;
931 16933 : map[i].mapped_color = hist->entries[i].mapped_color;
932 : }
933 :
934 7 : qsort(map, map_count, sizeof(*map), compare_color_map_by_color);
935 :
936 2491403 : for (i = 0; i < image->pixel_count; ++i) {
937 2491396 : px = &image->rgba[i * PNGX_RGBA_CHANNELS];
938 2491396 : if (px[3] <= PNGX_REDUCED_ALPHA_NEAR_TRANSPARENT) {
939 28542 : continue;
940 : }
941 2462854 : original = pack_rgba_u32(px[0], px[1], px[2], px[3]);
942 2462854 : mapping = find_color_mapping(map, map_count, original);
943 :
944 2462854 : if (!mapping) {
945 1584222 : continue;
946 : }
947 :
948 878632 : unpack_rgba_u32(mapping->mapped_color, &px[0], &px[1], &px[2], &px[3]);
949 : }
950 :
951 7 : qsort(map, map_count, sizeof(*map), compare_color_map_by_mapped);
952 16940 : for (i = 0; i < map_count; ++i) {
953 16933 : if (i == 0 || map[i].mapped_color != map[i - 1].mapped_color) {
954 4537 : ++actual_colors;
955 : }
956 : }
957 :
958 7 : if (applied_colors) {
959 7 : *applied_colors = actual_colors;
960 : }
961 :
962 7 : free(map);
963 7 : free(palette_seed);
964 7 : free(palette_bits_rgb);
965 7 : free(palette_bits_alpha);
966 7 : free(boxes);
967 :
968 7 : return true;
969 : }
970 :
971 17 : static inline bool pack_sorted_rgba(const uint8_t *rgba, size_t pixel_count, uint32_t **out_sorted) {
972 : uint32_t *packed;
973 : size_t base, i;
974 :
975 17 : if (!rgba || pixel_count == 0 || !out_sorted) {
976 0 : return false;
977 : }
978 :
979 17 : if (pixel_count > SIZE_MAX / sizeof(uint32_t)) {
980 0 : return false;
981 : }
982 :
983 17 : packed = (uint32_t *)malloc(sizeof(uint32_t) * pixel_count);
984 17 : if (!packed) {
985 0 : return false;
986 : }
987 :
988 3673369 : for (i = 0; i < pixel_count; ++i) {
989 3673352 : base = i * 4;
990 3673352 : packed[i] = pack_rgba_u32(rgba[base + 0], rgba[base + 1], rgba[base + 2], rgba[base + 3]);
991 : }
992 :
993 17 : qsort(packed, pixel_count, sizeof(uint32_t), compare_u32);
994 17 : *out_sorted = packed;
995 :
996 17 : return true;
997 : }
998 :
999 13 : static inline size_t count_unique_rgba(const uint8_t *rgba, size_t pixel_count) {
1000 : uint32_t *packed;
1001 13 : size_t i, unique = 0;
1002 :
1003 13 : if (!rgba || pixel_count == 0) {
1004 0 : return 0;
1005 : }
1006 :
1007 13 : if (!pack_sorted_rgba(rgba, pixel_count, &packed)) {
1008 0 : return 0;
1009 : }
1010 :
1011 3082517 : for (i = 0; i < pixel_count; ++i) {
1012 3082504 : if (i == 0 || packed[i] != packed[i - 1]) {
1013 74495 : ++unique;
1014 : }
1015 : }
1016 :
1017 13 : free(packed);
1018 :
1019 13 : return unique;
1020 : }
1021 :
1022 4 : static inline bool build_color_frequency(const uint8_t *rgba, size_t pixel_count, pngx_color_freq_t **out_freq, size_t *out_count) {
1023 : pngx_color_freq_t *freq, *shrunk;
1024 : uint32_t *packed;
1025 : size_t i, unique;
1026 :
1027 4 : if (!out_freq || !out_count) {
1028 0 : return false;
1029 : }
1030 :
1031 4 : if (!pack_sorted_rgba(rgba, pixel_count, &packed)) {
1032 0 : return false;
1033 : }
1034 :
1035 4 : freq = (pngx_color_freq_t *)malloc(sizeof(pngx_color_freq_t) * pixel_count);
1036 4 : if (!freq) {
1037 0 : free(packed);
1038 0 : return false;
1039 : }
1040 :
1041 4 : unique = 0;
1042 590852 : for (i = 0; i < pixel_count; ++i) {
1043 590848 : if (i == 0 || packed[i] != packed[i - 1]) {
1044 4373 : freq[unique].color = packed[i];
1045 4373 : freq[unique].count = 1;
1046 4373 : ++unique;
1047 : } else {
1048 586475 : ++freq[unique - 1].count;
1049 : }
1050 : }
1051 :
1052 4 : free(packed);
1053 :
1054 4 : if (unique == 0) {
1055 0 : free(freq);
1056 0 : *out_freq = NULL;
1057 0 : *out_count = 0;
1058 0 : return true;
1059 : }
1060 :
1061 4 : shrunk = (pngx_color_freq_t *)realloc(freq, sizeof(pngx_color_freq_t) * unique);
1062 4 : if (!shrunk) {
1063 0 : free(freq);
1064 0 : return false;
1065 : }
1066 4 : freq = shrunk;
1067 :
1068 4 : *out_freq = freq;
1069 4 : *out_count = unique;
1070 :
1071 4 : return true;
1072 : }
1073 :
1074 590848 : static inline bool find_freq_index(const pngx_color_freq_t *freq, size_t freq_count, uint32_t color, size_t *index_out) {
1075 590848 : size_t left = 0, right = freq_count, mid;
1076 :
1077 590848 : if (!freq || freq_count == 0) {
1078 0 : return false;
1079 : }
1080 :
1081 5599644 : while (left < right) {
1082 5599644 : mid = left + (right - left) / 2;
1083 5599644 : if (freq[mid].color == color) {
1084 590848 : if (index_out) {
1085 590848 : *index_out = mid;
1086 : }
1087 :
1088 590848 : return true;
1089 : }
1090 :
1091 5008796 : if (freq[mid].color < color) {
1092 2165167 : left = mid + 1;
1093 : } else {
1094 2843629 : right = mid;
1095 : }
1096 : }
1097 :
1098 0 : return false;
1099 : }
1100 :
1101 39229 : static inline int compare_freq_rank_desc(const void *lhs, const void *rhs) {
1102 39229 : const pngx_freq_rank_t *a = (const pngx_freq_rank_t *)lhs, *b = (const pngx_freq_rank_t *)rhs;
1103 :
1104 39229 : return a->count != b->count ? (b->count - a->count) : (a->color != b->color ? (a->color - b->color) : 0);
1105 : }
1106 :
1107 4 : static inline bool enforce_manual_reduced_limit(pngx_rgba_image_t *image, uint32_t manual_limit, uint8_t bits_rgb, uint8_t bits_alpha, uint32_t *applied_colors) {
1108 4 : pngx_color_freq_t *freq = NULL;
1109 4 : pngx_freq_rank_t *rank = NULL;
1110 4 : uint32_t *mapped = NULL, source, best_color, best_dist, candidate_color, distance, original;
1111 4 : size_t *keep_indices = NULL, freq_count = 0, keep_count, current_unique, unique_after, pixel_index, idx, best_keep, keep_idx, candidate_index, base, freq_index, i;
1112 4 : bool success = false;
1113 :
1114 4 : if (!image || !image->rgba || image->pixel_count == 0 || manual_limit == 0) {
1115 0 : if (applied_colors && image && image->rgba) {
1116 0 : current_unique = count_unique_rgba(image->rgba, image->pixel_count);
1117 :
1118 0 : if (current_unique > UINT32_MAX) {
1119 0 : current_unique = UINT32_MAX;
1120 : }
1121 :
1122 0 : *applied_colors = (uint32_t)current_unique;
1123 : }
1124 :
1125 0 : return true;
1126 : }
1127 :
1128 4 : snap_rgba_image_to_bits(image->rgba, image->pixel_count, bits_rgb, bits_alpha);
1129 :
1130 4 : if (!build_color_frequency(image->rgba, image->pixel_count, &freq, &freq_count)) {
1131 0 : goto bailout;
1132 : }
1133 :
1134 4 : if (freq_count == 0) {
1135 0 : if (applied_colors) {
1136 0 : *applied_colors = 0;
1137 : }
1138 :
1139 0 : success = true;
1140 :
1141 0 : goto bailout;
1142 : }
1143 :
1144 4 : if (freq_count <= (size_t)manual_limit) {
1145 0 : if (applied_colors) {
1146 0 : *applied_colors = (uint32_t)freq_count;
1147 : }
1148 :
1149 0 : success = true;
1150 :
1151 0 : goto bailout;
1152 : }
1153 :
1154 4 : keep_count = (size_t)manual_limit;
1155 4 : if (keep_count > freq_count) {
1156 0 : keep_count = freq_count;
1157 : }
1158 :
1159 4 : rank = (pngx_freq_rank_t *)malloc(sizeof(pngx_freq_rank_t) * freq_count);
1160 4 : mapped = (uint32_t *)malloc(sizeof(uint32_t) * freq_count);
1161 4 : keep_indices = (size_t *)malloc(sizeof(size_t) * keep_count);
1162 4 : if (!rank || !mapped || !keep_indices) {
1163 0 : goto bailout;
1164 : }
1165 :
1166 4377 : for (i = 0; i < freq_count; ++i) {
1167 4373 : rank[i].index = i;
1168 4373 : rank[i].count = freq[i].count;
1169 4373 : rank[i].color = freq[i].color;
1170 4373 : mapped[i] = freq[i].color;
1171 : }
1172 :
1173 4 : qsort(rank, freq_count, sizeof(pngx_freq_rank_t), compare_freq_rank_desc);
1174 :
1175 2700 : for (i = 0; i < keep_count; ++i) {
1176 2696 : keep_indices[i] = rank[i].index;
1177 : }
1178 :
1179 1681 : for (i = keep_count; i < freq_count; ++i) {
1180 1677 : idx = rank[i].index;
1181 1677 : source = freq[idx].color;
1182 1677 : best_keep = keep_indices[0];
1183 1677 : best_color = freq[best_keep].color;
1184 1677 : best_dist = color_distance_sq_u32(source, best_color);
1185 :
1186 601676 : for (keep_idx = 1; keep_idx < keep_count; ++keep_idx) {
1187 599999 : candidate_index = keep_indices[keep_idx];
1188 599999 : candidate_color = freq[candidate_index].color;
1189 599999 : distance = color_distance_sq_u32(source, candidate_color);
1190 :
1191 599999 : if (distance < best_dist) {
1192 10249 : best_dist = distance;
1193 10249 : best_color = candidate_color;
1194 : }
1195 : }
1196 :
1197 1677 : mapped[idx] = best_color;
1198 : }
1199 :
1200 590852 : for (pixel_index = 0; pixel_index < image->pixel_count; ++pixel_index) {
1201 590848 : base = pixel_index * 4;
1202 590848 : original = pack_rgba_u32(image->rgba[base + 0], image->rgba[base + 1], image->rgba[base + 2], image->rgba[base + 3]);
1203 :
1204 590848 : if (!find_freq_index(freq, freq_count, original, &freq_index)) {
1205 0 : continue;
1206 : }
1207 :
1208 590848 : if (mapped[freq_index] == original) {
1209 484355 : continue;
1210 : }
1211 :
1212 106493 : unpack_rgba_u32(mapped[freq_index], &image->rgba[base + 0], &image->rgba[base + 1], &image->rgba[base + 2], &image->rgba[base + 3]);
1213 : }
1214 :
1215 4 : snap_rgba_image_to_bits(image->rgba, image->pixel_count, bits_rgb, bits_alpha);
1216 :
1217 4 : unique_after = count_unique_rgba(image->rgba, image->pixel_count);
1218 4 : if (applied_colors) {
1219 4 : if (unique_after > UINT32_MAX) {
1220 0 : unique_after = UINT32_MAX;
1221 : }
1222 4 : *applied_colors = (uint32_t)unique_after;
1223 : }
1224 :
1225 4 : cpres_log(CPRES_LOG_LEVEL_DEBUG, "PNGX: Reduced RGBA32 manual target enforcement trimmed %zu -> %zu colors", freq_count, unique_after);
1226 :
1227 4 : success = true;
1228 :
1229 4 : bailout:
1230 4 : free(freq);
1231 4 : free(rank);
1232 4 : free(mapped);
1233 4 : free(keep_indices);
1234 :
1235 4 : return success;
1236 : }
1237 :
1238 4983312 : static inline uint8_t resolve_pixel_bits(uint8_t importance, uint8_t base_bits, uint8_t boost_bits) {
1239 4983312 : uint8_t resolved = base_bits, mid_bits;
1240 :
1241 4983312 : if (boost_bits <= base_bits) {
1242 133648 : return base_bits;
1243 : }
1244 :
1245 4849664 : if (importance >= PNGX_REDUCED_IMPORTANCE_LEVEL_FULL) {
1246 30540 : resolved = boost_bits;
1247 4819124 : } else if (importance >= PNGX_REDUCED_IMPORTANCE_LEVEL_HIGH) {
1248 311036 : mid_bits = (uint8_t)((base_bits + boost_bits + 1) / 2);
1249 311036 : resolved = mid_bits;
1250 4508088 : } else if (importance >= PNGX_REDUCED_IMPORTANCE_LEVEL_MEDIUM) {
1251 1374458 : mid_bits = (uint8_t)((base_bits * 2 + boost_bits + 2) / 3);
1252 1374458 : resolved = mid_bits;
1253 3133630 : } else if (importance >= PNGX_REDUCED_IMPORTANCE_LEVEL_LOW) {
1254 1456982 : resolved = (uint8_t)((base_bits * 3 + boost_bits + 3) / 4);
1255 : }
1256 :
1257 4849664 : if (resolved > boost_bits) {
1258 0 : resolved = boost_bits;
1259 : }
1260 4849664 : if (resolved < base_bits) {
1261 0 : resolved = base_bits;
1262 : }
1263 :
1264 4849664 : return resolved;
1265 : }
1266 :
1267 5 : static inline void reduce_rgba_custom_bitdepth_simple(uint8_t *rgba, size_t pixel_count, uint8_t bits_rgb, uint8_t bits_alpha, const uint8_t *importance_map, size_t importance_map_len,
1268 : uint8_t boost_bits_rgb, uint8_t boost_bits_alpha, uint8_t *bit_hint_map, size_t bit_hint_len) {
1269 : size_t i, base;
1270 : uint8_t importance, pixel_bits_rgb, pixel_bits_alpha;
1271 :
1272 5 : if (!rgba || pixel_count == 0) {
1273 0 : return;
1274 : }
1275 :
1276 5 : bits_rgb = clamp_reduced_bits(bits_rgb);
1277 5 : bits_alpha = clamp_reduced_bits(bits_alpha);
1278 5 : boost_bits_rgb = clamp_reduced_bits(boost_bits_rgb);
1279 5 : boost_bits_alpha = clamp_reduced_bits(boost_bits_alpha);
1280 :
1281 66829 : for (i = 0; i < pixel_count; ++i) {
1282 66824 : base = i * PNGX_RGBA_CHANNELS;
1283 66824 : importance = (importance_map && i < importance_map_len) ? importance_map[i] : 0;
1284 66824 : pixel_bits_rgb = resolve_pixel_bits(importance, bits_rgb, boost_bits_rgb);
1285 66824 : pixel_bits_alpha = resolve_pixel_bits(importance, bits_alpha, boost_bits_alpha);
1286 :
1287 66824 : if (bit_hint_map && i < bit_hint_len) {
1288 66824 : bit_hint_map[i] = (uint8_t)((pixel_bits_rgb << 4) | (pixel_bits_alpha & 0x0fu));
1289 : }
1290 :
1291 66824 : if (rgba[base + 3] > PNGX_REDUCED_ALPHA_NEAR_TRANSPARENT) {
1292 66760 : if (pixel_bits_rgb < PNGX_FULL_CHANNEL_BITS) {
1293 200 : rgba[base + 0] = quantize_bits(rgba[base + 0], pixel_bits_rgb);
1294 200 : rgba[base + 1] = quantize_bits(rgba[base + 1], pixel_bits_rgb);
1295 200 : rgba[base + 2] = quantize_bits(rgba[base + 2], pixel_bits_rgb);
1296 : }
1297 : }
1298 66824 : if (pixel_bits_alpha < PNGX_FULL_CHANNEL_BITS) {
1299 66824 : rgba[base + 3] = quantize_bits(rgba[base + 3], pixel_bits_alpha);
1300 : }
1301 : }
1302 : }
1303 :
1304 2424832 : static inline void process_custom_bitdepth_pixel(uint8_t *rgba, png_uint_32 width, png_uint_32 height, uint32_t x, uint32_t y, uint8_t base_bits_rgb, uint8_t base_bits_alpha, uint8_t boost_bits_rgb,
1305 : uint8_t boost_bits_alpha, float base_dither, const uint8_t *importance_map, size_t pixel_count, float *err_curr, float *err_next, bool left_to_right,
1306 : uint8_t *bit_hint_map, size_t bit_hint_len) {
1307 2424832 : size_t pixel_index = (size_t)y * (size_t)width + (size_t)x, rgba_index = pixel_index * PNGX_RGBA_CHANNELS, err_index = (size_t)x * PNGX_RGBA_CHANNELS;
1308 2424832 : uint8_t importance = 0, pixel_bits_rgb, pixel_bits_alpha, channel, bits, quantized;
1309 2424832 : float dither = base_dither, value, error, alpha_factor, dither_ch;
1310 :
1311 2424832 : if (importance_map && pixel_index < pixel_count) {
1312 2424832 : importance = importance_map[pixel_index];
1313 2424832 : dither *= importance_dither_scale(importance);
1314 : }
1315 2424832 : alpha_factor = (float)rgba[rgba_index + 3] / 255.0f;
1316 :
1317 2424832 : pixel_bits_rgb = resolve_pixel_bits(importance, base_bits_rgb, boost_bits_rgb);
1318 2424832 : pixel_bits_alpha = resolve_pixel_bits(importance, base_bits_alpha, boost_bits_alpha);
1319 2424832 : if (bit_hint_map && pixel_index < bit_hint_len) {
1320 2424832 : bit_hint_map[pixel_index] = (uint8_t)((pixel_bits_rgb << 4) | (pixel_bits_alpha & 0x0fu));
1321 : }
1322 :
1323 12124160 : for (channel = 0; channel < PNGX_RGBA_CHANNELS; ++channel) {
1324 9699328 : if (channel != 3 && rgba[rgba_index + 3] <= PNGX_REDUCED_ALPHA_NEAR_TRANSPARENT) {
1325 82944 : bits = PNGX_FULL_CHANNEL_BITS;
1326 : } else {
1327 9616384 : bits = (channel == 3) ? pixel_bits_alpha : pixel_bits_rgb;
1328 : }
1329 :
1330 9699328 : if (bits >= PNGX_FULL_CHANNEL_BITS) {
1331 82944 : err_curr[err_index + channel] = 0.0f;
1332 82944 : continue;
1333 : }
1334 :
1335 9616384 : value = (float)rgba[rgba_index + channel] + err_curr[err_index + channel];
1336 9616384 : quantized = quantize_channel_value(value, bits);
1337 9616384 : error = (value - (float)quantized);
1338 :
1339 9616384 : if (channel == 3) {
1340 2424832 : dither_ch = 0.0f;
1341 : } else {
1342 7191552 : dither_ch = dither * alpha_factor;
1343 7191552 : if (alpha_factor < PNGX_REDUCED_ALPHA_MIN_DITHER_FACTOR) {
1344 18432 : dither_ch = 0.0f;
1345 : }
1346 : }
1347 :
1348 9616384 : error *= dither_ch;
1349 :
1350 9616384 : rgba[rgba_index + channel] = quantized;
1351 9616384 : err_curr[err_index + channel] = 0.0f;
1352 :
1353 9616384 : if (dither_ch <= 0.0f || error == 0.0f) {
1354 2573894 : continue;
1355 : }
1356 :
1357 7042490 : if (left_to_right) {
1358 3520033 : if (x + 1 < width) {
1359 3515946 : err_curr[err_index + PNGX_RGBA_CHANNELS + channel] += error * (7.0f / 16.0f);
1360 : }
1361 3520033 : if (y + 1 < height) {
1362 3520033 : if (x > 0) {
1363 3515928 : err_next[err_index - PNGX_RGBA_CHANNELS + channel] += error * (3.0f / 16.0f);
1364 : }
1365 3520033 : err_next[err_index + channel] += error * (5.0f / 16.0f);
1366 3520033 : if (x + 1 < width) {
1367 3515946 : err_next[err_index + PNGX_RGBA_CHANNELS + channel] += error * (1.0f / 16.0f);
1368 : }
1369 : }
1370 : } else {
1371 3522457 : if (x > 0) {
1372 3518333 : err_curr[err_index - PNGX_RGBA_CHANNELS + channel] += error * (7.0f / 16.0f);
1373 : }
1374 3522457 : if (y + 1 < height) {
1375 3514481 : if (x + 1 < width) {
1376 3510412 : err_next[err_index + PNGX_RGBA_CHANNELS + channel] += error * (3.0f / 16.0f);
1377 : }
1378 3514481 : err_next[err_index + channel] += error * (5.0f / 16.0f);
1379 3514481 : if (x > 0) {
1380 3510369 : err_next[err_index - PNGX_RGBA_CHANNELS + channel] += error * (1.0f / 16.0f);
1381 : }
1382 : }
1383 : }
1384 : }
1385 2424832 : }
1386 :
1387 4 : static inline bool reduce_rgba_custom_bitdepth_dither(uint8_t *rgba, png_uint_32 width, png_uint_32 height, uint8_t bits_rgb, uint8_t bits_alpha, uint8_t boost_bits_rgb, uint8_t boost_bits_alpha,
1388 : float dither_level, const uint8_t *importance_map, size_t pixel_count, uint8_t *bit_hint_map, size_t bit_hint_len) {
1389 : uint32_t x, y;
1390 : size_t row_stride;
1391 : float *err_curr, *err_next, *tmp;
1392 : bool left_to_right;
1393 :
1394 4 : bits_rgb = clamp_reduced_bits(bits_rgb);
1395 4 : bits_alpha = clamp_reduced_bits(bits_alpha);
1396 4 : boost_bits_rgb = clamp_reduced_bits(boost_bits_rgb);
1397 4 : boost_bits_alpha = clamp_reduced_bits(boost_bits_alpha);
1398 4 : if ((!rgba) || width == 0 || height == 0 || (bits_rgb >= PNGX_FULL_CHANNEL_BITS && bits_alpha >= PNGX_FULL_CHANNEL_BITS)) {
1399 0 : return true;
1400 : }
1401 :
1402 4 : row_stride = (size_t)width * PNGX_RGBA_CHANNELS;
1403 4 : err_curr = (float *)calloc(row_stride, sizeof(float));
1404 4 : err_next = (float *)calloc(row_stride, sizeof(float));
1405 4 : if (!err_curr || !err_next) {
1406 0 : free(err_curr);
1407 0 : free(err_next);
1408 0 : cpres_log(CPRES_LOG_LEVEL_ERROR, "PNGX: Reduced RGBA32 dither allocation failed");
1409 :
1410 0 : return false;
1411 : }
1412 :
1413 2820 : for (y = 0; y < height; ++y) {
1414 2816 : left_to_right = ((y & 1) == 0);
1415 2816 : memset(err_next, 0, row_stride * sizeof(float));
1416 2816 : if (left_to_right) {
1417 1213824 : for (x = 0; x < width; ++x) {
1418 1212416 : process_custom_bitdepth_pixel(rgba, width, height, x, y, bits_rgb, bits_alpha, boost_bits_rgb, boost_bits_alpha, dither_level, importance_map, pixel_count, err_curr, err_next, true,
1419 : bit_hint_map, bit_hint_len);
1420 : }
1421 : } else {
1422 1408 : x = width;
1423 1213824 : while (x-- > 0) {
1424 1212416 : process_custom_bitdepth_pixel(rgba, width, height, x, y, bits_rgb, bits_alpha, boost_bits_rgb, boost_bits_alpha, dither_level, importance_map, pixel_count, err_curr, err_next, false,
1425 : bit_hint_map, bit_hint_len);
1426 : }
1427 : }
1428 :
1429 2816 : tmp = err_curr;
1430 2816 : err_curr = err_next;
1431 2816 : err_next = tmp;
1432 : }
1433 :
1434 4 : free(err_curr);
1435 4 : free(err_next);
1436 :
1437 4 : return true;
1438 : }
1439 :
1440 9 : static inline bool reduce_rgba_custom_bitdepth(uint8_t *rgba, png_uint_32 width, png_uint_32 height, uint8_t bits_rgb, uint8_t bits_alpha, float dither_level, const uint8_t *importance_map,
1441 : size_t importance_map_len, pngx_quant_support_t *support) {
1442 9 : uint8_t boost_bits_rgb, boost_bits_alpha, *bit_hint_map = NULL;
1443 9 : size_t bit_hint_len = 0, pixel_count, hint_len;
1444 : bool need_rgb, need_alpha;
1445 :
1446 9 : if (!rgba || width == 0 || height == 0) {
1447 0 : return true;
1448 : }
1449 :
1450 9 : bits_rgb = clamp_reduced_bits(bits_rgb);
1451 9 : bits_alpha = clamp_reduced_bits(bits_alpha);
1452 9 : need_rgb = bits_rgb < PNGX_FULL_CHANNEL_BITS;
1453 9 : need_alpha = bits_alpha < PNGX_FULL_CHANNEL_BITS;
1454 9 : if (!need_rgb && !need_alpha) {
1455 0 : return true;
1456 : }
1457 :
1458 9 : pixel_count = (size_t)width * (size_t)height;
1459 9 : if (!importance_map || importance_map_len < pixel_count) {
1460 5 : importance_map = NULL;
1461 : }
1462 :
1463 9 : boost_bits_rgb = (importance_map && bits_rgb < PNGX_FULL_CHANNEL_BITS) ? clamp_reduced_bits((uint8_t)(bits_rgb + 3)) : bits_rgb;
1464 9 : boost_bits_alpha = (importance_map && bits_alpha < PNGX_FULL_CHANNEL_BITS) ? clamp_reduced_bits((uint8_t)(bits_alpha + 2)) : bits_alpha;
1465 :
1466 9 : if (support) {
1467 9 : free(support->bit_hint_map);
1468 9 : support->bit_hint_map = NULL;
1469 9 : support->bit_hint_len = 0;
1470 9 : if (pixel_count > 0) {
1471 9 : support->bit_hint_map = (uint8_t *)malloc(pixel_count);
1472 9 : if (support->bit_hint_map) {
1473 9 : support->bit_hint_len = pixel_count;
1474 9 : bit_hint_map = support->bit_hint_map;
1475 9 : bit_hint_len = support->bit_hint_len;
1476 : }
1477 : }
1478 : }
1479 :
1480 9 : if (dither_level > 0.0f) {
1481 4 : if (!reduce_rgba_custom_bitdepth_dither(rgba, width, height, bits_rgb, bits_alpha, boost_bits_rgb, boost_bits_alpha, dither_level, importance_map, pixel_count, bit_hint_map, bit_hint_len)) {
1482 0 : return false;
1483 : }
1484 : } else {
1485 5 : hint_len = importance_map ? pixel_count : 0;
1486 5 : reduce_rgba_custom_bitdepth_simple(rgba, pixel_count, bits_rgb, bits_alpha, importance_map, hint_len, boost_bits_rgb, boost_bits_alpha, bit_hint_map, bit_hint_len);
1487 : }
1488 :
1489 9 : return true;
1490 : }
1491 :
1492 9 : static inline uint32_t collect_alpha_levels(const pngx_rgba_image_t *image, float *non_opaque_ratio) {
1493 9 : uint32_t unique = 0, non_opaque = 0;
1494 : uint8_t alpha;
1495 : size_t i;
1496 9 : bool level_used[256] = {false};
1497 :
1498 9 : if (!image || !image->rgba || image->pixel_count == 0) {
1499 0 : if (non_opaque_ratio) {
1500 0 : *non_opaque_ratio = 0.0f;
1501 : }
1502 :
1503 0 : return 0;
1504 : }
1505 :
1506 2491665 : for (i = 0; i < image->pixel_count; ++i) {
1507 2491656 : alpha = image->rgba[i * 4 + 3];
1508 2491656 : if (!level_used[alpha]) {
1509 932 : level_used[alpha] = true;
1510 932 : ++unique;
1511 : }
1512 :
1513 2491656 : if (alpha < 255) {
1514 2420117 : ++non_opaque;
1515 : }
1516 : }
1517 :
1518 9 : if (non_opaque_ratio) {
1519 9 : *non_opaque_ratio = (image->pixel_count > 0) ? ((float)non_opaque / (float)image->pixel_count) : 0.0f;
1520 : }
1521 :
1522 9 : return unique;
1523 : }
1524 :
1525 9 : static inline uint8_t bits_for_level_count(uint32_t levels) {
1526 9 : uint32_t capacity = 1;
1527 9 : uint8_t bits = 1;
1528 :
1529 9 : if (levels == 0) {
1530 0 : return 1;
1531 : }
1532 :
1533 41 : while (capacity < levels && bits < COLOPRESSO_PNGX_REDUCED_BITS_MAX) {
1534 32 : ++bits;
1535 32 : capacity <<= 1;
1536 : }
1537 :
1538 9 : return clamp_reduced_bits(bits);
1539 : }
1540 :
1541 9 : static inline void tune_reduced_bitdepth(const pngx_rgba_image_t *image, const pngx_image_stats_t *stats, uint8_t *bits_rgb, uint8_t *bits_alpha) {
1542 : uint32_t alpha_levels;
1543 : uint8_t tuned_rgb, tuned_alpha, level_bits, next_alpha;
1544 : float gradient, saturation, vibrant, opaque, translucent, non_opaque_ratio;
1545 :
1546 9 : if (!bits_rgb || !bits_alpha) {
1547 0 : return;
1548 : }
1549 :
1550 9 : tuned_rgb = clamp_reduced_bits(*bits_rgb);
1551 9 : tuned_alpha = clamp_reduced_bits(*bits_alpha);
1552 9 : gradient = stats ? stats->gradient_mean : PNGX_REDUCED_TUNE_DEFAULT_GRADIENT;
1553 9 : saturation = stats ? stats->saturation_mean : PNGX_REDUCED_TUNE_DEFAULT_SATURATION;
1554 9 : vibrant = stats ? stats->vibrant_ratio : PNGX_REDUCED_TUNE_DEFAULT_VIBRANT;
1555 9 : opaque = stats ? stats->opaque_ratio : PNGX_REDUCED_TUNE_DEFAULT_OPAQUE;
1556 9 : translucent = stats ? stats->translucent_ratio : PNGX_REDUCED_TUNE_DEFAULT_TRANSLUCENT;
1557 :
1558 9 : if (gradient < PNGX_REDUCED_TUNE_FLAT_GRADIENT_THRESHOLD && saturation < PNGX_REDUCED_TUNE_FLAT_SATURATION_THRESHOLD && vibrant < PNGX_REDUCED_TUNE_FLAT_VIBRANT_THRESHOLD && tuned_rgb > 3) {
1559 0 : --tuned_rgb;
1560 0 : if (gradient < PNGX_REDUCED_TUNE_VERY_FLAT_GRADIENT && saturation < PNGX_REDUCED_TUNE_VERY_FLAT_SATURATION && tuned_rgb > 3) {
1561 0 : --tuned_rgb;
1562 : }
1563 0 : if (tuned_rgb < 3) {
1564 0 : tuned_rgb = 3;
1565 : }
1566 : }
1567 :
1568 9 : non_opaque_ratio = 0.0f;
1569 9 : alpha_levels = collect_alpha_levels(image, &non_opaque_ratio);
1570 9 : if (alpha_levels > 0) {
1571 9 : level_bits = bits_for_level_count(alpha_levels);
1572 9 : if (alpha_levels <= PNGX_REDUCED_ALPHA_LEVEL_LIMIT_FEW && non_opaque_ratio < PNGX_REDUCED_ALPHA_RATIO_FEW && tuned_alpha > level_bits) {
1573 3 : tuned_alpha = (level_bits < 2) ? 2 : level_bits;
1574 6 : } else if (alpha_levels <= PNGX_REDUCED_ALPHA_NEAR_TRANSPARENT && non_opaque_ratio < PNGX_REDUCED_ALPHA_RATIO_LOW && tuned_alpha > (uint8_t)(level_bits + 1)) {
1575 0 : tuned_alpha = (uint8_t)(level_bits + 1);
1576 6 : } else if (alpha_levels <= 16 && non_opaque_ratio < PNGX_REDUCED_ALPHA_RATIO_MINIMAL && tuned_alpha > (uint8_t)(level_bits + 2)) {
1577 0 : tuned_alpha = (uint8_t)(level_bits + 2);
1578 : }
1579 :
1580 9 : if (opaque > PNGX_REDUCED_ALPHA_OPAQUE_LIMIT && level_bits <= 2 && tuned_alpha > 2) {
1581 0 : tuned_alpha = 2;
1582 9 : } else if (translucent < PNGX_REDUCED_ALPHA_TRANSLUCENT_LIMIT && tuned_alpha > level_bits) {
1583 3 : next_alpha = (uint8_t)(tuned_alpha - 1);
1584 3 : if (next_alpha < level_bits) {
1585 0 : next_alpha = level_bits;
1586 : }
1587 3 : tuned_alpha = next_alpha;
1588 : }
1589 : }
1590 :
1591 9 : if (tuned_alpha < COLOPRESSO_PNGX_REDUCED_BITS_MIN) {
1592 0 : tuned_alpha = COLOPRESSO_PNGX_REDUCED_BITS_MIN;
1593 : }
1594 :
1595 9 : *bits_rgb = tuned_rgb;
1596 9 : *bits_alpha = tuned_alpha;
1597 : }
1598 :
1599 9 : static inline bool apply_reduced_rgba32_prepass(pngx_rgba_image_t *image, const pngx_options_t *opts, pngx_quant_support_t *support, pngx_image_stats_t *stats) {
1600 9 : const uint8_t *importance = NULL;
1601 9 : uint8_t bits_rgb = COLOPRESSO_PNGX_DEFAULT_REDUCED_BITS_RGB, bits_alpha = COLOPRESSO_PNGX_DEFAULT_REDUCED_ALPHA_BITS;
1602 9 : size_t importance_len = 0;
1603 9 : float dither = 0.0f;
1604 :
1605 9 : if (!image || !image->rgba || image->pixel_count == 0) {
1606 0 : return true;
1607 : }
1608 :
1609 9 : if (opts) {
1610 9 : bits_rgb = clamp_reduced_bits(opts->lossy_reduced_bits_rgb);
1611 9 : bits_alpha = clamp_reduced_bits(opts->lossy_reduced_alpha_bits);
1612 9 : if (opts->lossy_dither_auto) {
1613 1 : dither = resolve_quant_dither(opts, stats);
1614 : } else {
1615 8 : dither = clamp_float(opts->lossy_dither_level, 0.0f, 1.0f);
1616 : }
1617 9 : if (support && support->importance_map && support->importance_map_len >= image->pixel_count) {
1618 4 : importance = support->importance_map;
1619 4 : importance_len = support->importance_map_len;
1620 : }
1621 : }
1622 :
1623 9 : return reduce_rgba_custom_bitdepth(image->rgba, image->width, image->height, bits_rgb, bits_alpha, dither, importance, importance_len, support);
1624 : }
1625 :
1626 552 : static inline void head_heap_sift_up(uint64_t *heap, size_t index) {
1627 : uint64_t parent_value;
1628 : size_t parent;
1629 :
1630 868 : while (index > 0) {
1631 843 : parent = (index - 1) / 2;
1632 843 : parent_value = heap[parent];
1633 :
1634 843 : if (parent_value <= heap[index]) {
1635 527 : break;
1636 : }
1637 :
1638 316 : heap[parent] = heap[index];
1639 316 : heap[index] = parent_value;
1640 316 : index = parent;
1641 : }
1642 552 : }
1643 :
1644 1528 : static inline void head_heap_sift_down(uint64_t *heap, size_t size, size_t index) {
1645 : uint64_t tmp;
1646 : size_t left, right, smallest;
1647 :
1648 : while (true) {
1649 7556 : left = index * 2 + 1;
1650 7556 : right = left + 1;
1651 7556 : smallest = index;
1652 :
1653 7556 : if (left < size && heap[left] < heap[smallest]) {
1654 5567 : smallest = left;
1655 : }
1656 :
1657 7556 : if (right < size && heap[right] < heap[smallest]) {
1658 2877 : smallest = right;
1659 : }
1660 :
1661 7556 : if (smallest == index) {
1662 1528 : break;
1663 : }
1664 :
1665 6028 : tmp = heap[index];
1666 6028 : heap[index] = heap[smallest];
1667 6028 : heap[smallest] = tmp;
1668 6028 : index = smallest;
1669 : }
1670 1528 : }
1671 :
1672 12 : static inline float histogram_head_dominance(const pngx_color_histogram_t *hist, size_t head_limit) {
1673 12 : uint64_t heap[PNGX_REDUCED_HEAD_DOMINANCE_LIMIT], weight, total_weight = 0, head_sum = 0;
1674 12 : size_t heap_size = 0, capacity, i;
1675 :
1676 12 : if (!hist || hist->count == 0 || head_limit == 0) {
1677 0 : return 0.0f;
1678 : }
1679 :
1680 12 : capacity = head_limit;
1681 12 : if (capacity > PNGX_REDUCED_HEAD_DOMINANCE_LIMIT) {
1682 0 : capacity = PNGX_REDUCED_HEAD_DOMINANCE_LIMIT;
1683 : }
1684 :
1685 28800 : for (i = 0; i < hist->count; ++i) {
1686 28788 : weight = hist->entries[i].count ? hist->entries[i].count : 1;
1687 28788 : total_weight += weight;
1688 :
1689 28788 : if (capacity == 0) {
1690 0 : continue;
1691 : }
1692 :
1693 28788 : if (heap_size < capacity) {
1694 552 : heap[heap_size] = weight;
1695 552 : ++heap_size;
1696 552 : head_heap_sift_up(heap, heap_size - 1);
1697 28236 : } else if (weight > heap[0]) {
1698 1528 : heap[0] = weight;
1699 1528 : head_heap_sift_down(heap, heap_size, 0);
1700 : }
1701 : }
1702 :
1703 12 : if (total_weight == 0 || heap_size == 0) {
1704 0 : return 0.0f;
1705 : }
1706 :
1707 564 : for (i = 0; i < heap_size; ++i) {
1708 552 : head_sum += heap[i];
1709 : }
1710 :
1711 12 : return (float)head_sum / (float)total_weight;
1712 : }
1713 :
1714 12 : static inline float histogram_low_weight_ratio(const pngx_color_histogram_t *hist, uint32_t weight_threshold) {
1715 : const pngx_color_entry_t *entry;
1716 12 : uint64_t total_weight = 0, low_weight = 0, weight;
1717 : size_t i;
1718 :
1719 12 : if (!hist || hist->count == 0 || weight_threshold == 0) {
1720 0 : return 0.0f;
1721 : }
1722 :
1723 28800 : for (i = 0; i < hist->count; ++i) {
1724 28788 : entry = &hist->entries[i];
1725 28788 : weight = entry->count ? entry->count : 1;
1726 28788 : total_weight += weight;
1727 28788 : if (entry->count <= weight_threshold) {
1728 17648 : low_weight += weight;
1729 : }
1730 : }
1731 :
1732 12 : if (total_weight == 0) {
1733 0 : return 0.0f;
1734 : }
1735 :
1736 12 : return (float)low_weight / (float)total_weight;
1737 : }
1738 :
1739 12 : static inline float histogram_detail_pressure(const pngx_color_histogram_t *hist, uint8_t base_bits_rgb, uint8_t base_bits_alpha) {
1740 : const pngx_color_entry_t *entry;
1741 12 : uint64_t total_weight = 0, detail_weight = 0, weight;
1742 : size_t i;
1743 :
1744 12 : if (!hist || hist->count == 0) {
1745 0 : return 0.0f;
1746 : }
1747 :
1748 28800 : for (i = 0; i < hist->count; ++i) {
1749 28788 : entry = &hist->entries[i];
1750 28788 : weight = entry->count ? entry->count : 1;
1751 28788 : total_weight += weight;
1752 28788 : if (entry->detail_bits_rgb > base_bits_rgb || entry->detail_bits_alpha > base_bits_alpha) {
1753 13338 : detail_weight += weight;
1754 : }
1755 : }
1756 :
1757 12 : if (total_weight == 0) {
1758 0 : return 0.0f;
1759 : }
1760 :
1761 12 : return (float)detail_weight / (float)total_weight;
1762 : }
1763 :
1764 12 : static inline float stats_flatness_factor(const pngx_image_stats_t *stats) {
1765 12 : float gradient = stats ? stats->gradient_mean : PNGX_REDUCED_STATS_FLAT_DEFAULT_GRADIENT, saturation = stats ? stats->saturation_mean : PNGX_REDUCED_STATS_FLAT_DEFAULT_SATURATION,
1766 12 : vibrant = stats ? stats->vibrant_ratio : PNGX_REDUCED_STATS_FLAT_DEFAULT_VIBRANT;
1767 12 : float gradient_term = clamp_float((PNGX_REDUCED_STATS_FLAT_GRADIENT_REF - gradient) / PNGX_REDUCED_STATS_FLAT_GRADIENT_REF, 0.0f, 1.0f),
1768 12 : saturation_term = clamp_float((PNGX_REDUCED_STATS_FLAT_SATURATION_REF - saturation) / PNGX_REDUCED_STATS_FLAT_SATURATION_REF, 0.0f, 1.0f),
1769 12 : vibrant_term = clamp_float((PNGX_REDUCED_VIBRANT_RATIO_LOW - vibrant) / PNGX_REDUCED_VIBRANT_RATIO_LOW, 0.0f, 1.0f);
1770 :
1771 12 : return (gradient_term * PNGX_REDUCED_STATS_FLAT_GRADIENT_WEIGHT) + (saturation_term * PNGX_REDUCED_STATS_FLAT_SATURATION_WEIGHT) + (vibrant_term * PNGX_REDUCED_STATS_FLAT_VIBRANT_WEIGHT);
1772 : }
1773 :
1774 12 : static inline float stats_alpha_simplicity(const pngx_image_stats_t *stats) {
1775 12 : float opaque = stats ? stats->opaque_ratio : PNGX_REDUCED_ALPHA_SIMPLE_DEFAULT_OPAQUE;
1776 12 : float translucent = stats ? stats->translucent_ratio : PNGX_REDUCED_ALPHA_SIMPLE_DEFAULT_TRANSLUCENT;
1777 12 : float opaque_term = clamp_float((opaque - PNGX_REDUCED_ALPHA_SIMPLE_OPAQUE_REF) / PNGX_REDUCED_ALPHA_SIMPLE_OPAQUE_RANGE, 0.0f, 1.0f);
1778 12 : float translucent_term = clamp_float((PNGX_REDUCED_ALPHA_SIMPLE_TRANSLUCENT_REF - translucent) / PNGX_REDUCED_ALPHA_SIMPLE_TRANSLUCENT_RANGE, 0.0f, 1.0f);
1779 :
1780 12 : return (opaque_term * PNGX_REDUCED_ALPHA_SIMPLE_OPAQUE_WEIGHT) + (translucent_term * PNGX_REDUCED_ALPHA_SIMPLE_TRANSLUCENT_WEIGHT);
1781 : }
1782 :
1783 9 : static inline uint32_t resolve_reduced_passthrough_threshold(uint32_t grid_cap, const pngx_image_stats_t *stats) {
1784 : uint32_t threshold;
1785 9 : float gradient = stats ? stats->gradient_mean : PNGX_REDUCED_PASSTHROUGH_DEFAULT_GRADIENT, saturation = stats ? stats->saturation_mean : PNGX_REDUCED_PASSTHROUGH_DEFAULT_SATURATION,
1786 9 : vibrant = stats ? stats->vibrant_ratio : PNGX_REDUCED_PASSTHROUGH_DEFAULT_VIBRANT;
1787 9 : float ratio =
1788 : PNGX_REDUCED_PASSTHROUGH_RATIO_BASE +
1789 9 : clamp_float((gradient * PNGX_REDUCED_PASSTHROUGH_GRADIENT_WEIGHT) + (saturation * PNGX_REDUCED_PASSTHROUGH_SATURATION_WEIGHT) + (vibrant * PNGX_REDUCED_PASSTHROUGH_VIBRANT_WEIGHT), 0.0f, 1.0f) *
1790 : PNGX_REDUCED_PASSTHROUGH_RATIO_GAIN;
1791 :
1792 9 : if (ratio > PNGX_REDUCED_PASSTHROUGH_RATIO_CAP) {
1793 0 : ratio = PNGX_REDUCED_PASSTHROUGH_RATIO_CAP;
1794 : }
1795 :
1796 9 : threshold = (uint32_t)((float)grid_cap * ratio + PNGX_REDUCED_ROUNDING_OFFSET);
1797 9 : if (threshold < PNGX_REDUCED_RGBA32_PASSTHROUGH_MIN_COLORS) {
1798 1 : threshold = PNGX_REDUCED_RGBA32_PASSTHROUGH_MIN_COLORS;
1799 : }
1800 9 : if (threshold > grid_cap) {
1801 1 : threshold = grid_cap;
1802 : }
1803 :
1804 9 : return threshold;
1805 : }
1806 :
1807 6 : static inline uint32_t compute_auto_trim_limit(const pngx_color_histogram_t *hist, size_t pixel_count, uint32_t actual_colors, uint8_t bits_rgb, uint8_t bits_alpha, const pngx_image_stats_t *stats) {
1808 : uint32_t low_weight_threshold, limit;
1809 6 : float low_weight_ratio, detail_pressure, head_dominance, flatness, alpha_simple, density_f, trim = 0.0f;
1810 : double density;
1811 :
1812 6 : if (!hist || hist->count == 0 || pixel_count == 0 || actual_colors <= (uint32_t)(COLOPRESSO_PNGX_REDUCED_COLORS_MIN + PNGX_REDUCED_TRIM_MIN_COLOR_MARGIN)) {
1813 2 : return 0;
1814 : }
1815 :
1816 4 : density = (double)hist->count / (double)pixel_count;
1817 4 : density_f = (float)density;
1818 4 : low_weight_threshold = (uint32_t)(pixel_count / PNGX_REDUCED_LOW_WEIGHT_DIVISOR);
1819 4 : if (low_weight_threshold < PNGX_REDUCED_LOW_WEIGHT_MIN) {
1820 1 : low_weight_threshold = PNGX_REDUCED_LOW_WEIGHT_MIN;
1821 3 : } else if (low_weight_threshold > PNGX_REDUCED_LOW_WEIGHT_MAX) {
1822 0 : low_weight_threshold = PNGX_REDUCED_LOW_WEIGHT_MAX;
1823 : }
1824 :
1825 4 : low_weight_ratio = histogram_low_weight_ratio(hist, low_weight_threshold);
1826 4 : detail_pressure = histogram_detail_pressure(hist, bits_rgb, bits_alpha);
1827 4 : head_dominance = histogram_head_dominance(hist, PNGX_REDUCED_HEAD_DOMINANCE_LIMIT);
1828 4 : flatness = stats_flatness_factor(stats);
1829 4 : alpha_simple = stats_alpha_simplicity(stats);
1830 :
1831 4 : if (head_dominance > PNGX_REDUCED_TRIM_HEAD_DOMINANCE_THRESHOLD && detail_pressure < PNGX_REDUCED_TRIM_DETAIL_PRESSURE_HEAD_LIMIT) {
1832 : float head_term =
1833 0 : clamp_float((head_dominance - PNGX_REDUCED_TRIM_HEAD_DOMINANCE_THRESHOLD) * (PNGX_REDUCED_TRIM_HEAD_WEIGHT + flatness * PNGX_REDUCED_TRIM_FLATNESS_WEIGHT), 0.0f, PNGX_REDUCED_TRIM_HEAD_CLAMP);
1834 0 : trim += head_term;
1835 : }
1836 :
1837 4 : if (low_weight_ratio > PNGX_REDUCED_TRIM_TAIL_RATIO_THRESHOLD && detail_pressure < PNGX_REDUCED_TRIM_DETAIL_PRESSURE_TAIL_LIMIT) {
1838 2 : float tail_term = (low_weight_ratio - PNGX_REDUCED_TRIM_TAIL_RATIO_THRESHOLD) * (PNGX_REDUCED_TRIM_TAIL_BASE_WEIGHT + PNGX_REDUCED_TRIM_TAIL_DETAIL_WEIGHT * (1.0f - detail_pressure));
1839 2 : trim += clamp_float(tail_term, 0.0f, PNGX_REDUCED_TRIM_TAIL_CLAMP);
1840 : }
1841 :
1842 4 : if (density_f < PNGX_REDUCED_TRIM_DENSITY_THRESHOLD) {
1843 3 : trim += clamp_float((PNGX_REDUCED_TRIM_DENSITY_THRESHOLD - density_f) * PNGX_REDUCED_TRIM_DENSITY_SCALE, 0.0f, PNGX_REDUCED_TRIM_DENSITY_CLAMP);
1844 : }
1845 :
1846 4 : if (alpha_simple > PNGX_REDUCED_TRIM_ALPHA_SIMPLE_THRESHOLD && detail_pressure < PNGX_REDUCED_TRIM_DETAIL_PRESSURE_HEAD_LIMIT) {
1847 2 : trim += clamp_float(alpha_simple * PNGX_REDUCED_TRIM_ALPHA_SIMPLE_SCALE, 0.0f, PNGX_REDUCED_TRIM_ALPHA_SIMPLE_CLAMP);
1848 : }
1849 :
1850 4 : if (flatness > PNGX_REDUCED_TRIM_FLATNESS_THRESHOLD && detail_pressure < PNGX_REDUCED_TRIM_DETAIL_PRESSURE_FLAT_LIMIT) {
1851 2 : trim += clamp_float((flatness - PNGX_REDUCED_TRIM_FLATNESS_THRESHOLD) * PNGX_REDUCED_TRIM_FLATNESS_SCALE, 0.0f, PNGX_REDUCED_TRIM_FLATNESS_CLAMP);
1852 : }
1853 :
1854 4 : trim = clamp_float(trim, 0.0f, PNGX_REDUCED_TRIM_TOTAL_CLAMP);
1855 4 : if (trim < PNGX_REDUCED_TRIM_MIN_TRIGGER) {
1856 0 : return 0;
1857 : }
1858 :
1859 4 : limit = (uint32_t)((float)actual_colors * (1.0f - trim) + PNGX_REDUCED_ROUNDING_OFFSET);
1860 4 : if (limit < (uint32_t)COLOPRESSO_PNGX_REDUCED_COLORS_MIN) {
1861 0 : limit = (uint32_t)COLOPRESSO_PNGX_REDUCED_COLORS_MIN;
1862 : }
1863 :
1864 4 : if (actual_colors <= limit || (actual_colors - limit) < PNGX_REDUCED_TRIM_MIN_COLOR_DIFF) {
1865 2 : return 0;
1866 : }
1867 :
1868 2 : return limit;
1869 : }
1870 :
1871 8 : static inline uint32_t resolve_reduced_rgba32_target(const pngx_color_histogram_t *hist, size_t pixel_count, int32_t hint, uint8_t bits_rgb, uint8_t bits_alpha, const pngx_image_stats_t *stats) {
1872 8 : uint64_t rgb_cap = 0, alpha_cap = 0;
1873 8 : uint32_t target, grid_cap = COLOPRESSO_PNGX_REDUCED_COLORS_MAX, low_weight_threshold;
1874 8 : size_t unique_colors = hist ? hist->count : 0, unlocked = hist ? hist->unlocked_count : 0;
1875 : double base, density;
1876 8 : float low_weight_ratio = 0.0f, detail_pressure = 0.0f, reduction_scale, boost_scale, flatness_score = 0.0f, alpha_simple = 0.0f, head_dominance = 0.0f, tail_cut, dominance_cut, gentle_cut,
1877 : applied_cut, tail_gain, dominance_gain, relief, gradient_relief, softness_relief, detail_relief, combined_cut, density_gap, flatness_reduction, alpha_reduction, span_ratio;
1878 :
1879 8 : if (unique_colors == 0) {
1880 0 : return 0;
1881 : }
1882 :
1883 8 : density = (pixel_count > 0) ? ((double)unique_colors / (double)pixel_count) : 0.0;
1884 :
1885 8 : bits_rgb = clamp_reduced_bits(bits_rgb);
1886 8 : bits_alpha = clamp_reduced_bits(bits_alpha);
1887 8 : if (bits_rgb < 8) {
1888 6 : rgb_cap = (uint64_t)1 << (bits_rgb * 3);
1889 : }
1890 8 : if (bits_alpha < 8) {
1891 8 : alpha_cap = (uint64_t)1 << bits_alpha;
1892 : }
1893 8 : if (rgb_cap == 0) {
1894 2 : rgb_cap = COLOPRESSO_PNGX_REDUCED_COLORS_MAX;
1895 : }
1896 8 : if (alpha_cap == 0) {
1897 0 : alpha_cap = 1;
1898 : }
1899 8 : if (rgb_cap > (uint64_t)COLOPRESSO_PNGX_REDUCED_COLORS_MAX) {
1900 0 : rgb_cap = COLOPRESSO_PNGX_REDUCED_COLORS_MAX;
1901 : }
1902 8 : if (alpha_cap > (uint64_t)COLOPRESSO_PNGX_REDUCED_COLORS_MAX) {
1903 0 : alpha_cap = COLOPRESSO_PNGX_REDUCED_COLORS_MAX;
1904 : }
1905 8 : if (rgb_cap * alpha_cap < (uint64_t)COLOPRESSO_PNGX_REDUCED_COLORS_MAX) {
1906 2 : grid_cap = (uint32_t)(rgb_cap * alpha_cap);
1907 : }
1908 :
1909 8 : if (hint > 0) {
1910 2 : target = (uint32_t)hint;
1911 2 : if (target < COLOPRESSO_PNGX_REDUCED_COLORS_MIN) {
1912 0 : target = COLOPRESSO_PNGX_REDUCED_COLORS_MIN;
1913 : }
1914 2 : if (target > COLOPRESSO_PNGX_REDUCED_COLORS_MAX) {
1915 0 : target = COLOPRESSO_PNGX_REDUCED_COLORS_MAX;
1916 : }
1917 : } else {
1918 6 : target = (uint32_t)unique_colors;
1919 6 : if (unique_colors > PNGX_REDUCED_TARGET_UNIQUE_COLOR_THRESHOLD) {
1920 3 : base = sqrt((double)unique_colors) * PNGX_REDUCED_TARGET_UNIQUE_BASE_SCALE;
1921 3 : if (density < PNGX_REDUCED_TARGET_DENSITY_LOW_THRESHOLD) {
1922 3 : base *= PNGX_REDUCED_TARGET_DENSITY_LOW_SCALE;
1923 0 : } else if (density > PNGX_REDUCED_TARGET_DENSITY_HIGH_THRESHOLD) {
1924 0 : base *= PNGX_REDUCED_TARGET_DENSITY_HIGH_SCALE;
1925 : }
1926 :
1927 3 : if (base < PNGX_REDUCED_TARGET_BASE_MIN) {
1928 1 : base = PNGX_REDUCED_TARGET_BASE_MIN;
1929 : }
1930 :
1931 3 : if (base > (double)COLOPRESSO_PNGX_REDUCED_COLORS_MAX) {
1932 0 : base = (double)COLOPRESSO_PNGX_REDUCED_COLORS_MAX;
1933 : }
1934 :
1935 3 : target = (uint32_t)(base + PNGX_REDUCED_ROUNDING_OFFSET);
1936 : }
1937 : }
1938 :
1939 8 : if (pixel_count > 0 && hist) {
1940 8 : low_weight_threshold = (uint32_t)(pixel_count / PNGX_REDUCED_LOW_WEIGHT_DIVISOR);
1941 8 : if (low_weight_threshold < PNGX_REDUCED_LOW_WEIGHT_MIN) {
1942 3 : low_weight_threshold = PNGX_REDUCED_LOW_WEIGHT_MIN;
1943 5 : } else if (low_weight_threshold > PNGX_REDUCED_LOW_WEIGHT_MAX) {
1944 0 : low_weight_threshold = PNGX_REDUCED_LOW_WEIGHT_MAX;
1945 : }
1946 :
1947 8 : low_weight_ratio = histogram_low_weight_ratio(hist, low_weight_threshold);
1948 8 : detail_pressure = histogram_detail_pressure(hist, bits_rgb, bits_alpha);
1949 8 : head_dominance = histogram_head_dominance(hist, PNGX_REDUCED_TARGET_HEAD_DOMINANCE_BUCKETS);
1950 :
1951 8 : if (low_weight_ratio > PNGX_REDUCED_TARGET_LOW_WEIGHT_REDUCTION_START) {
1952 8 : reduction_scale = 1.0f - clamp_float((low_weight_ratio - PNGX_REDUCED_TARGET_LOW_WEIGHT_REDUCTION_START) *
1953 4 : (PNGX_REDUCED_TARGET_LOW_WEIGHT_REDUCTION_BASE + (PNGX_REDUCED_TARGET_LOW_WEIGHT_REDUCTION_DETAIL * (1.0f - detail_pressure))),
1954 : 0.0f, PNGX_REDUCED_TARGET_LOW_WEIGHT_REDUCTION_CLAMP);
1955 4 : target = (uint32_t)((float)target * reduction_scale + PNGX_REDUCED_ROUNDING_OFFSET);
1956 : }
1957 :
1958 8 : if (low_weight_ratio > PNGX_REDUCED_TARGET_TAIL_RATIO_THRESHOLD && detail_pressure < PNGX_REDUCED_TARGET_DETAIL_PRESSURE_TAIL_LIMIT) {
1959 3 : tail_cut = clamp_float((low_weight_ratio - PNGX_REDUCED_TARGET_TAIL_RATIO_THRESHOLD) * (PNGX_REDUCED_TARGET_TAIL_WIDTH_BASE - detail_pressure) * PNGX_REDUCED_TARGET_TAIL_WIDTH_SCALE, 0.0f,
1960 : PNGX_REDUCED_TARGET_TAIL_CUT_CLAMP);
1961 3 : target = (uint32_t)((float)target * (1.0f - tail_cut) + PNGX_REDUCED_ROUNDING_OFFSET);
1962 : }
1963 :
1964 8 : if (detail_pressure > PNGX_REDUCED_TARGET_DETAIL_PRESSURE_BOOST) {
1965 4 : boost_scale = 1.0f + clamp_float((detail_pressure - PNGX_REDUCED_TARGET_DETAIL_PRESSURE_BOOST) * PNGX_REDUCED_TARGET_DETAIL_BOOST_SCALE, 0.0f, PNGX_REDUCED_TARGET_DETAIL_BOOST_CLAMP);
1966 4 : target = (uint32_t)((float)target * boost_scale + PNGX_REDUCED_ROUNDING_OFFSET);
1967 : }
1968 :
1969 8 : if (head_dominance > PNGX_REDUCED_TARGET_HEAD_DOMINANCE_THRESHOLD && detail_pressure < PNGX_REDUCED_TARGET_DETAIL_PRESSURE_HEAD_LIMIT) {
1970 2 : gradient_relief =
1971 2 : stats ? clamp_float((PNGX_REDUCED_TARGET_GRADIENT_RELIEF_REF - stats->gradient_mean) / PNGX_REDUCED_TARGET_GRADIENT_RELIEF_REF, 0.0f, 1.0f) : PNGX_REDUCED_TARGET_GRADIENT_RELIEF_DEFAULT;
1972 2 : dominance_cut = clamp_float((head_dominance - PNGX_REDUCED_TARGET_HEAD_DOMINANCE_THRESHOLD) * (PNGX_REDUCED_TARGET_HEAD_CUT_BASE + PNGX_REDUCED_TARGET_HEAD_CUT_RELIEF * gradient_relief), 0.0f,
1973 : PNGX_REDUCED_TARGET_HEAD_CUT_CLAMP);
1974 2 : target = (uint32_t)((float)target * (1.0f - dominance_cut) + PNGX_REDUCED_ROUNDING_OFFSET);
1975 : }
1976 :
1977 8 : if (head_dominance > PNGX_REDUCED_TARGET_HEAD_DOMINANCE_STRONG && low_weight_ratio > PNGX_REDUCED_TARGET_LOW_WEIGHT_RATIO_STRONG &&
1978 : detail_pressure < PNGX_REDUCED_TARGET_DETAIL_PRESSURE_STRONG_LIMIT) {
1979 2 : gradient_relief = stats ? clamp_float((PNGX_REDUCED_TARGET_GRADIENT_RELIEF_SECONDARY_REF - stats->gradient_mean) / PNGX_REDUCED_TARGET_GRADIENT_RELIEF_SECONDARY_REF, 0.0f, 1.0f)
1980 2 : : PNGX_REDUCED_TARGET_GRADIENT_RELIEF_SECONDARY_DEFAULT;
1981 2 : softness_relief = stats ? clamp_float((PNGX_REDUCED_TARGET_SATURATION_RELIEF_REF - stats->saturation_mean) / PNGX_REDUCED_TARGET_SATURATION_RELIEF_REF, 0.0f, 1.0f)
1982 2 : : PNGX_REDUCED_TARGET_SATURATION_RELIEF_DEFAULT;
1983 2 : relief = clamp_float((gradient_relief * PNGX_REDUCED_TARGET_RELIEF_GRADIENT_WEIGHT + softness_relief * PNGX_REDUCED_TARGET_RELIEF_SATURATION_WEIGHT) * PNGX_REDUCED_TARGET_RELIEF_SCALE, 0.0f,
1984 : PNGX_REDUCED_TARGET_RELIEF_CLAMP);
1985 2 : dominance_gain = clamp_float((head_dominance - PNGX_REDUCED_TARGET_HEAD_DOMINANCE_STRONG) * PNGX_REDUCED_TARGET_DOMINANCE_GAIN_SCALE, 0.0f, PNGX_REDUCED_TARGET_DOMINANCE_GAIN_CLAMP);
1986 2 : tail_gain = clamp_float((low_weight_ratio - PNGX_REDUCED_TARGET_LOW_WEIGHT_RATIO_STRONG) *
1987 2 : (PNGX_REDUCED_TARGET_TAIL_GAIN_BASE + PNGX_REDUCED_TARGET_TAIL_GAIN_RELIEF * (gradient_relief + softness_relief)),
1988 : 0.0f, PNGX_REDUCED_TARGET_TAIL_GAIN_CLAMP);
1989 2 : detail_relief = clamp_float((PNGX_REDUCED_TARGET_DETAIL_RELIEF_BASE - detail_pressure) * PNGX_REDUCED_TARGET_DETAIL_RELIEF_SCALE, 0.0f, PNGX_REDUCED_TARGET_DETAIL_RELIEF_CLAMP);
1990 2 : combined_cut = clamp_float((dominance_gain + tail_gain) * (PNGX_REDUCED_TARGET_COMBINED_CUT_BASE + relief + detail_relief), 0.0f, PNGX_REDUCED_TARGET_COMBINED_CUT_CLAMP);
1991 2 : target = (uint32_t)((float)target * (1.0f - combined_cut) + PNGX_REDUCED_ROUNDING_OFFSET);
1992 : }
1993 :
1994 8 : if (density < PNGX_REDUCED_TARGET_DENSITY_THRESHOLD && detail_pressure < PNGX_REDUCED_TARGET_DETAIL_PRESSURE_DENSITY_LIMIT) {
1995 1 : density_gap = clamp_float((PNGX_REDUCED_TARGET_DENSITY_THRESHOLD - (float)density) * PNGX_REDUCED_TARGET_DENSITY_GAP_SCALE, 0.0f, PNGX_REDUCED_TARGET_DENSITY_GAP_CLAMP);
1996 1 : target = (uint32_t)((float)target * (1.0f - density_gap) + PNGX_REDUCED_ROUNDING_OFFSET);
1997 : }
1998 : }
1999 :
2000 8 : if (stats) {
2001 8 : flatness_score = stats_flatness_factor(stats);
2002 8 : if (flatness_score > PNGX_REDUCED_TARGET_FLATNESS_THRESHOLD && detail_pressure < PNGX_REDUCED_TARGET_DETAIL_PRESSURE_FLAT_LIMIT) {
2003 4 : flatness_reduction = clamp_float(flatness_score * PNGX_REDUCED_TARGET_FLATNESS_SCALE, 0.0f, PNGX_REDUCED_TARGET_FLATNESS_CLAMP);
2004 4 : target = (uint32_t)((float)target * (1.0f - flatness_reduction) + PNGX_REDUCED_ROUNDING_OFFSET);
2005 : }
2006 :
2007 8 : alpha_simple = stats_alpha_simplicity(stats);
2008 8 : if (alpha_simple > PNGX_REDUCED_TARGET_ALPHA_SIMPLE_THRESHOLD && detail_pressure < PNGX_REDUCED_TARGET_DETAIL_PRESSURE_ALPHA_LIMIT) {
2009 3 : alpha_reduction = clamp_float(alpha_simple * PNGX_REDUCED_TARGET_ALPHA_SIMPLE_SCALE, 0.0f, PNGX_REDUCED_TARGET_ALPHA_SIMPLE_CLAMP);
2010 3 : target = (uint32_t)((float)target * (1.0f - alpha_reduction) + PNGX_REDUCED_ROUNDING_OFFSET);
2011 : }
2012 : }
2013 :
2014 8 : if (hint <= 0 && unique_colors > PNGX_REDUCED_TARGET_GENTLE_MIN_COLORS && unique_colors <= PNGX_REDUCED_TARGET_GENTLE_MAX_COLORS &&
2015 : detail_pressure < PNGX_REDUCED_TARGET_DETAIL_PRESSURE_GENTLE_LIMIT) {
2016 1 : span_ratio = ((float)unique_colors - (float)PNGX_REDUCED_TARGET_GENTLE_MIN_COLORS) / PNGX_REDUCED_TARGET_GENTLE_COLOR_RANGE;
2017 1 : if (span_ratio < 0.0f) {
2018 0 : span_ratio = 0.0f;
2019 1 : } else if (span_ratio > 1.0f) {
2020 0 : span_ratio = 1.0f;
2021 : }
2022 :
2023 1 : gentle_cut = clamp_float((1.0f - detail_pressure) * PNGX_REDUCED_TARGET_GENTLE_SCALE, 0.0f, PNGX_REDUCED_TARGET_GENTLE_CLAMP);
2024 1 : applied_cut = span_ratio * gentle_cut;
2025 1 : target = (uint32_t)((float)target * (1.0f - applied_cut) + PNGX_REDUCED_ROUNDING_OFFSET);
2026 : }
2027 :
2028 8 : if (target > unique_colors) {
2029 0 : target = (uint32_t)unique_colors;
2030 : }
2031 :
2032 8 : if (target < (uint32_t)COLOPRESSO_PNGX_REDUCED_COLORS_MIN) {
2033 1 : target = COLOPRESSO_PNGX_REDUCED_COLORS_MIN;
2034 : }
2035 :
2036 8 : if (target > grid_cap) {
2037 0 : target = grid_cap;
2038 : }
2039 :
2040 8 : if (unlocked > 0 && target > (uint32_t)unlocked) {
2041 0 : target = (uint32_t)unlocked;
2042 : }
2043 :
2044 8 : if (unlocked == 0) {
2045 1 : target = (uint32_t)unique_colors;
2046 : }
2047 :
2048 8 : return target;
2049 : }
2050 :
2051 9 : bool pngx_quantize_reduced_rgba32(const uint8_t *png_data, size_t png_size, const pngx_options_t *opts, uint32_t *resolved_target, uint32_t *applied_colors, uint8_t **out_data, size_t *out_size) {
2052 : pngx_rgba_image_t image;
2053 : pngx_color_histogram_t histogram;
2054 9 : pngx_quant_support_t support = {0};
2055 : pngx_image_stats_t stats;
2056 : pngx_options_t tuned_opts;
2057 9 : uint32_t target = 0, actual = 0, manual_limit = 0, auto_trim_limit = 0, grid_cap;
2058 : uint8_t bits_rgb, bits_alpha;
2059 : size_t grid_unique, passthrough_threshold;
2060 9 : bool wrote, manual_target = false, success, auto_target, grid_passthrough, auto_trim_applied = false;
2061 :
2062 9 : if (!png_data || png_size == 0 || !opts || !out_data || !out_size) {
2063 0 : return false;
2064 : }
2065 :
2066 9 : if (!load_rgba_image(png_data, png_size, &image)) {
2067 0 : return false;
2068 : }
2069 :
2070 9 : histogram.entries = NULL;
2071 9 : histogram.count = 0;
2072 9 : histogram.unlocked_count = 0;
2073 9 : tuned_opts = *opts;
2074 :
2075 9 : image_stats_reset(&stats);
2076 :
2077 9 : if (!prepare_quant_support(&image, &tuned_opts, &support, &stats)) {
2078 0 : rgba_image_reset(&image);
2079 0 : return false;
2080 : }
2081 :
2082 9 : tune_reduced_bitdepth(&image, &stats, &tuned_opts.lossy_reduced_bits_rgb, &tuned_opts.lossy_reduced_alpha_bits);
2083 9 : if (!apply_reduced_rgba32_prepass(&image, &tuned_opts, &support, &stats)) {
2084 0 : color_histogram_reset(&histogram);
2085 0 : quant_support_reset(&support);
2086 0 : rgba_image_reset(&image);
2087 :
2088 0 : return false;
2089 : }
2090 :
2091 9 : bits_rgb = clamp_reduced_bits(tuned_opts.lossy_reduced_bits_rgb);
2092 9 : bits_alpha = clamp_reduced_bits(tuned_opts.lossy_reduced_alpha_bits);
2093 9 : grid_cap = compute_grid_capacity(bits_rgb, bits_alpha);
2094 9 : if (grid_cap == 0) {
2095 0 : grid_cap = COLOPRESSO_PNGX_REDUCED_COLORS_MAX;
2096 : }
2097 9 : if (opts->lossy_reduced_colors >= (int32_t)COLOPRESSO_PNGX_REDUCED_COLORS_MIN) {
2098 2 : manual_target = true;
2099 2 : manual_limit = (uint32_t)opts->lossy_reduced_colors;
2100 2 : if (manual_limit > grid_cap) {
2101 0 : manual_limit = grid_cap;
2102 : }
2103 : }
2104 :
2105 9 : grid_unique = count_unique_rgba(image.rgba, image.pixel_count);
2106 9 : grid_cap = compute_grid_capacity(bits_rgb, bits_alpha);
2107 9 : auto_target = (opts->lossy_reduced_colors <= 0);
2108 9 : grid_passthrough = false;
2109 :
2110 9 : if (grid_cap == 0) {
2111 0 : grid_cap = COLOPRESSO_PNGX_REDUCED_COLORS_MAX;
2112 : }
2113 :
2114 9 : passthrough_threshold = resolve_reduced_passthrough_threshold(grid_cap, &stats);
2115 :
2116 9 : if (grid_unique > (size_t)grid_cap) {
2117 0 : grid_unique = (size_t)grid_cap;
2118 : }
2119 :
2120 9 : if (auto_target && grid_unique >= passthrough_threshold) {
2121 1 : grid_passthrough = true;
2122 : }
2123 :
2124 9 : if (grid_passthrough) {
2125 1 : wrote = false;
2126 1 : snap_rgba_image_to_bits(image.rgba, image.pixel_count, bits_rgb, bits_alpha);
2127 :
2128 1 : if (resolved_target) {
2129 1 : *resolved_target = (uint32_t)grid_unique;
2130 : }
2131 :
2132 1 : if (applied_colors) {
2133 1 : *applied_colors = (uint32_t)grid_unique;
2134 : }
2135 :
2136 1 : wrote = create_rgba_png(image.rgba, image.pixel_count, image.width, image.height, out_data, out_size);
2137 1 : if (wrote) {
2138 1 : cpres_log(CPRES_LOG_LEVEL_DEBUG, "PNGX: Reduced RGBA32 grid passthrough kept %zu colors (capacity=%u)", grid_unique, grid_cap);
2139 : }
2140 :
2141 1 : quant_support_reset(&support);
2142 1 : rgba_image_reset(&image);
2143 :
2144 1 : return wrote;
2145 : }
2146 :
2147 8 : if (!build_color_histogram(&image, &tuned_opts, &support, &histogram)) {
2148 0 : quant_support_reset(&support);
2149 0 : rgba_image_reset(&image);
2150 :
2151 0 : return false;
2152 : }
2153 :
2154 8 : target = resolve_reduced_rgba32_target(&histogram, image.pixel_count, opts->lossy_reduced_colors, bits_rgb, bits_alpha, &stats);
2155 8 : if (histogram.unlocked_count == 0 || target == 0) {
2156 1 : actual = (uint32_t)histogram.count;
2157 1 : snap_rgba_image_to_bits(image.rgba, image.pixel_count, bits_rgb, bits_alpha);
2158 : } else {
2159 7 : if (!apply_reduced_rgba32_quantization(&histogram, &image, target, bits_rgb, bits_alpha, &actual)) {
2160 0 : color_histogram_reset(&histogram);
2161 0 : quant_support_reset(&support);
2162 0 : rgba_image_reset(&image);
2163 :
2164 0 : return false;
2165 : }
2166 : }
2167 :
2168 8 : if (!manual_target) {
2169 6 : auto_trim_limit = compute_auto_trim_limit(&histogram, image.pixel_count, actual, bits_rgb, bits_alpha, &stats);
2170 6 : if (auto_trim_limit > 0 && auto_trim_limit < actual) {
2171 4 : if (enforce_manual_reduced_limit(&image, auto_trim_limit, bits_rgb, bits_alpha, &actual)) {
2172 2 : auto_trim_applied = true;
2173 2 : cpres_log(CPRES_LOG_LEVEL_DEBUG, "PNGX: Reduced RGBA32 auto trim applied %u -> %u colors", target, auto_trim_limit);
2174 : } else {
2175 0 : cpres_log(CPRES_LOG_LEVEL_WARNING, "PNGX: Reduced RGBA32 auto trim request failed (limit=%u)", auto_trim_limit);
2176 0 : auto_trim_limit = 0;
2177 : }
2178 : } else {
2179 4 : auto_trim_limit = 0;
2180 : }
2181 : }
2182 :
2183 8 : if (manual_target) {
2184 2 : if (!enforce_manual_reduced_limit(&image, manual_limit, bits_rgb, bits_alpha, &actual)) {
2185 0 : color_histogram_reset(&histogram);
2186 0 : quant_support_reset(&support);
2187 0 : rgba_image_reset(&image);
2188 :
2189 0 : return false;
2190 : }
2191 : }
2192 :
2193 8 : success = create_rgba_png(image.rgba, image.pixel_count, image.width, image.height, out_data, out_size);
2194 :
2195 8 : if (resolved_target) {
2196 8 : if (manual_target) {
2197 2 : *resolved_target = manual_limit;
2198 6 : } else if (auto_trim_applied && auto_trim_limit > 0) {
2199 2 : *resolved_target = auto_trim_limit;
2200 4 : } else if (histogram.unlocked_count == 0 || target == 0) {
2201 1 : *resolved_target = (uint32_t)histogram.count;
2202 : } else {
2203 3 : *resolved_target = target;
2204 : }
2205 : }
2206 :
2207 8 : if (applied_colors) {
2208 8 : *applied_colors = actual;
2209 : }
2210 :
2211 8 : color_histogram_reset(&histogram);
2212 8 : quant_support_reset(&support);
2213 8 : rgba_image_reset(&image);
2214 :
2215 8 : return success;
2216 : }
|
