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