FFmpeg coverage

Directory: ../../../ffmpeg/
File: src/libavfilter/vf_latticepal.c
Date: 2026-09-14 03:06:03
Exec Total Coverage
Lines: 555 710 78.2%
Functions: 16 19 84.2%
Branches: 334 512 65.2%
Line Branch Exec Source
1 /*
2 * Copyright (c) 2026 Michael Niedermayer <michael-ffmpeg@niedermayer.cc>
3 *
4 * This file is part of FFmpeg.
5 *
6 * FFmpeg is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
10 *
11 * FFmpeg is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with FFmpeg; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
21 /**
22 * @file
23 * Convert packed RGB/BGR to PAL8 with a per-frame palette whose colors sit
24 * on a face-centered cubic (FCC) lattice.
25 *
26 * The FCC lattice is realized as the D3 checkerboard lattice: the points
27 * (i,j,k) with an even coordinate sum, scaled so that the density option is
28 * the number of lattice steps spanning one color axis (0..255). Only the
29 * lattice points actually used by a frame enter its palette; if a frame
30 * uses more than 256 of them, the used colors are reduced by iteratively
31 * dropping the color whose removal has the least impact and mapping its
32 * pixels to the nearest remaining color.
33 */
34
35 #include <math.h>
36 #include "libavutil/lfg.h"
37 #include "libavutil/mem.h"
38 #include "libavutil/opt.h"
39 #include "libavutil/pixdesc.h"
40 #include "avfilter.h"
41 #include "filters.h"
42 #include "formats.h"
43 #include "video.h"
44
45 #define MAX_DENSITY 255
46 #define MAX_DENSITY_ALPHA 64
47
48 enum dithering_mode {
49 DITHERING_NONE,
50 DITHERING_BAYER,
51 DITHERING_BLUE_NOISE,
52 DITHERING_FLOYD_STEINBERG,
53 NB_DITHERING
54 };
55
56 enum refine_mode {
57 REFINE_NONE,
58 REFINE_FULL,
59 REFINE_RESIDUAL,
60 REFINE_BATCHED,
61 NB_REFINE
62 };
63
64 /* void-and-cluster blue noise mask parameters */
65 #define VC_SHIFT 6
66 #define VC_SIZE (1 << VC_SHIFT)
67 #define VC_AREA (VC_SIZE * VC_SIZE)
68 #define VC_MASK (VC_SIZE - 1)
69 #define VC_SIGMA 1.5f
70 #define VC_RADIUS 7
71 #define VC_KSIZE (2 * VC_RADIUS + 1)
72
73 typedef struct PalEntry {
74 int pos; ///< lattice cell position, ((i * dim + j) * dim + k) [* dim + l]
75 uint8_t ci[4]; ///< lattice indices of the color
76 uint8_t alive; ///< still part of the palette while reducing
77 int nn; ///< nearest live color while reducing, then palette slot
78 int d2; ///< squared RGB(A) distance to nn
79 int64_t count; ///< pixels quantizing to this color, incl. absorbed ones
80 } PalEntry;
81
82 typedef struct LatticePalContext {
83 const AVClass *class;
84 int density; ///< lattice steps per color axis
85 int dither;
86 int max_colors; ///< palette entries to use at most
87 int alpha; ///< quantize the alpha channel too (D4 lattice)
88 int refine; ///< rediffuse the error of dropped colors
89
90 int ro, go, bo, ao; ///< byte offsets of R, G, B, A in an input pixel, ao < 0: opaque
91 int nc; ///< quantized components, 3 or 4
92 int pixstep; ///< bytes per input pixel
93 float scale; ///< density / 255
94 uint8_t idx2val[MAX_DENSITY + 1]; ///< lattice index -> 8-bit component value
95 int ordered_dither[4][8 * 8]; ///< per-channel bayer offsets spanning one lattice period
96 int *blue_dither[4]; ///< per-channel blue noise offsets spanning one lattice period
97 int32_t *err[2]; ///< Floyd-Steinberg error rows, nc ints per pixel
98
99 int dim; ///< density + 1, lattice cells per axis
100 int min_gap; ///< smallest idx2val increment
101 int32_t *cell; ///< dim^nc table: lattice cell -> list index + 1, 0 if unused
102 uint32_t *pixpos; ///< per-pixel cell position of the quantized color
103 PalEntry *list; ///< colors used by the current frame
104 int nb_used;
105 int nb_alloc;
106 int *alive_arr; ///< compact list of live color indices while reducing
107 int *alive_pos; ///< position of each live color in alive_arr
108 int nb_alive; ///< entries in alive_arr, 0 outside reduction/remap
109 int alive_alloc;
110 uint32_t prev_pal[AVPALETTE_COUNT]; ///< previous frame's palette, for stable slot assignment
111 int *touched; ///< cells filled on demand by the refinement pass
112 int nb_touched;
113 int touched_alloc;
114 } LatticePalContext;
115
116 #define OFFSET(x) offsetof(LatticePalContext, x)
117 #define FLAGS AV_OPT_FLAG_FILTERING_PARAM|AV_OPT_FLAG_VIDEO_PARAM
118 static const AVOption latticepal_options[] = {
119 { "density", "set the number of lattice steps spanning one color axis", OFFSET(density), AV_OPT_TYPE_INT, {.i64=20}, 1, MAX_DENSITY, FLAGS },
120 { "max_colors", "set the maximum number of palette entries to use", OFFSET(max_colors), AV_OPT_TYPE_INT, {.i64=256}, 2, 256, FLAGS },
121 { "alpha", "quantize the alpha channel too, on a 4 dimensional lattice", OFFSET(alpha), AV_OPT_TYPE_BOOL, {.i64=0}, 0, 1, FLAGS },
122 { "refine", "rediffuse the error of dropped colors against the final palette", OFFSET(refine), AV_OPT_TYPE_INT, {.i64=REFINE_NONE}, 0, NB_REFINE-1, FLAGS, .unit = "refine_mode" },
123 { "none", "no refinement", 0, AV_OPT_TYPE_CONST, {.i64=REFINE_NONE}, INT_MIN, INT_MAX, FLAGS, .unit = "refine_mode" },
124 { "full", "rediffuse the whole frame against the final palette", 0, AV_OPT_TYPE_CONST, {.i64=REFINE_FULL}, INT_MIN, INT_MAX, FLAGS, .unit = "refine_mode" },
125 { "residual", "diffuse only the residual of the dropped colors", 0, AV_OPT_TYPE_CONST, {.i64=REFINE_RESIDUAL}, INT_MIN, INT_MAX, FLAGS, .unit = "refine_mode" },
126 { "batched", "interleave removal and rediffusion in geometric batches", 0, AV_OPT_TYPE_CONST, {.i64=REFINE_BATCHED}, INT_MIN, INT_MAX, FLAGS, .unit = "refine_mode" },
127 { "dither", "select dithering mode", OFFSET(dither), AV_OPT_TYPE_INT, {.i64=DITHERING_FLOYD_STEINBERG}, 0, NB_DITHERING-1, FLAGS, .unit = "dithering_mode" },
128 { "none", "no dithering", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_NONE}, INT_MIN, INT_MAX, FLAGS, .unit = "dithering_mode" },
129 { "bayer", "ordered 8x8 bayer dithering", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_BAYER}, INT_MIN, INT_MAX, FLAGS, .unit = "dithering_mode" },
130 { "blue_noise", "void-and-cluster blue noise dithering", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_BLUE_NOISE}, INT_MIN, INT_MAX, FLAGS, .unit = "dithering_mode" },
131 { "floyd_steinberg", "Floyd-Steinberg error diffusion", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_FLOYD_STEINBERG}, INT_MIN, INT_MAX, FLAGS, .unit = "dithering_mode" },
132 { NULL }
133 };
134
135 AVFILTER_DEFINE_CLASS(latticepal);
136
137 6 static int query_formats(const AVFilterContext *ctx,
138 AVFilterFormatsConfig **cfg_in,
139 AVFilterFormatsConfig **cfg_out)
140 {
141 static const enum AVPixelFormat in_fmts[] = {
142 AV_PIX_FMT_RGB24, AV_PIX_FMT_BGR24,
143 AV_PIX_FMT_RGBA, AV_PIX_FMT_BGRA,
144 AV_PIX_FMT_ARGB, AV_PIX_FMT_ABGR,
145 AV_PIX_FMT_RGB0, AV_PIX_FMT_BGR0,
146 AV_PIX_FMT_0RGB, AV_PIX_FMT_0BGR,
147 AV_PIX_FMT_NONE
148 };
149 static const enum AVPixelFormat out_fmts[] = { AV_PIX_FMT_PAL8, AV_PIX_FMT_NONE };
150 int ret;
151
152
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
 6 if ((ret = ff_formats_ref(ff_make_pixel_format_list(in_fmts), &cfg_in[0]->formats)) < 0)
153 ✗ return ret;
154
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
 6 if ((ret = ff_formats_ref(ff_make_pixel_format_list(out_fmts), &cfg_out[0]->formats)) < 0)
155 ✗ return ret;
156 6 return 0;
157 }
158
159 /* Classic swscale ordered dither matrix (libswscale/output.c), 73 levels. */
160 static const uint8_t dither_8x8_73[8][8] = {
161 { 0, 55, 14, 68, 3, 58, 17, 72, },
162 { 37, 18, 50, 32, 40, 22, 54, 35, },
163 { 9, 64, 5, 59, 13, 67, 8, 63, },
164 { 46, 27, 41, 23, 49, 31, 44, 26, },
165 { 2, 57, 16, 71, 1, 56, 15, 70, },
166 { 39, 21, 52, 34, 38, 19, 51, 33, },
167 { 11, 66, 7, 62, 10, 65, 6, 60, },
168 { 48, 30, 43, 25, 47, 29, 42, 24, },
169 };
170
171 /**
172 * Add (sign > 0) or remove (sign < 0) the Gaussian energy contribution of a
173 * minority pixel at position pos on the VC_SIZE x VC_SIZE torus.
174 */
175 ✗ static void vc_splat(float *energy, const float *kern, int pos, float sign)
176 {
177 ✗ const int px = pos & VC_MASK, py = pos >> VC_SHIFT;
178
179 ✗ for (int dy = -VC_RADIUS; dy <= VC_RADIUS; dy++) {
180 ✗ const int y = (py + dy) & VC_MASK;
181 ✗ const float *krow = &kern[(dy + VC_RADIUS) * VC_KSIZE + VC_RADIUS];
182 ✗ float *erow = &energy[y << VC_SHIFT];
183
184 ✗ for (int dx = -VC_RADIUS; dx <= VC_RADIUS; dx++)
185 ✗ erow[(px + dx) & VC_MASK] += sign * krow[dx];
186 }
187 ✗ }
188
189 /**
190 * Position of the extreme energy value among the cells whose bit equals
191 * want_set: the tightest cluster (find_max, among minority pixels) or the
192 * largest void (!find_max, among majority pixels).
193 */
194 ✗ static int vc_extreme(const float *energy, const uint8_t *bits, int want_set, int find_max)
195 {
196 ✗ int best = -1;
197 ✗ float beste = 0.f;
198
199 ✗ for (int i = 0; i < VC_AREA; i++) {
200 ✗ if (bits[i] != want_set)
201 ✗ continue;
202 ✗ if (best < 0 || (find_max ? energy[i] > beste : energy[i] < beste)) {
203 ✗ best = i;
204 ✗ beste = energy[i];
205 }
206 }
207 ✗ return best;
208 }
209
210 /**
211 * Generate a void-and-cluster blue noise rank matrix (Ulichney 1993):
212 * every cell gets a unique rank in [0, VC_AREA).
213 *
214 * On a torus the filtered field of the zero pattern is the constant kernel
215 * sum minus the field of the one pattern, so the tightest cluster of zeros
216 * coincides with the largest void of ones and the ranking above 50% fill
217 * needs no separate phase.
218 */
219 ✗ static void vc_generate(uint16_t *rank, uint8_t *bits, float *energy,
220 float *e1, const float *kern, AVLFG *lfg)
221 {
222 ✗ const int n1 = VC_AREA / 10;
223 uint8_t b1[VC_AREA];
224 int placed, pos;
225
226 ✗ memset(bits, 0, VC_AREA * sizeof(*bits));
227 ✗ memset(energy, 0, VC_AREA * sizeof(*energy));
228
229 /* initial random minority pattern */
230 ✗ for (placed = 0; placed < n1;) {
231 ✗ pos = av_lfg_get(lfg) & (VC_AREA - 1);
232 ✗ if (!bits[pos]) {
233 ✗ bits[pos] = 1;
234 ✗ vc_splat(energy, kern, pos, 1.f);
235 ✗ placed++;
236 }
237 }
238
239 /* relax: move the tightest cluster into the largest void until stable */
240 ✗ for (int i = 0; i < VC_AREA * 8; i++) {
241 ✗ pos = vc_extreme(energy, bits, 1, 1);
242 ✗ bits[pos] = 0;
243 ✗ vc_splat(energy, kern, pos, -1.f);
244 ✗ const int vp = vc_extreme(energy, bits, 0, 0);
245 ✗ bits[vp] = 1;
246 ✗ vc_splat(energy, kern, vp, 1.f);
247 ✗ if (vp == pos)
248 ✗ break;
249 }
250
251 /* phase 1: rank the initial pattern by removing tightest clusters */
252 ✗ memcpy(b1, bits, sizeof(b1));
253 ✗ memcpy(e1, energy, VC_AREA * sizeof(*e1));
254 ✗ for (int r = n1 - 1; r >= 0; r--) {
255 ✗ pos = vc_extreme(e1, b1, 1, 1);
256 ✗ b1[pos] = 0;
257 ✗ vc_splat(e1, kern, pos, -1.f);
258 ✗ rank[pos] = r;
259 }
260
261 /* phase 2+3: fill the largest void until all cells are ranked */
262 ✗ for (int r = n1; r < VC_AREA; r++) {
263 ✗ pos = vc_extreme(energy, bits, 0, 0);
264 ✗ bits[pos] = 1;
265 ✗ vc_splat(energy, kern, pos, 1.f);
266 ✗ rank[pos] = r;
267 }
268 ✗ }
269
270 /**
271 * Quantize a color to the nearest point of the scaled D3 (FCC) or D4
272 * lattice.
273 *
274 * Conway & Sloane: round every coordinate to the nearest integer; if the
275 * coordinate sum is odd, re-round the coordinate with the largest rounding
276 * error in the other direction. This works for any checkerboard lattice Dn.
277 *
278 * @param in the nc input components
279 * @param f receives the nc lattice indices
280 */
281 13989888 static av_always_inline void quant_dn(const LatticePalContext *s, const int *in, int f[4])
282 {
283 13989888 const int N = s->density;
284 13989888 const int nc = s->nc;
285 13989888 int sum = 0;
286 float d[4];
287
288
2/2
✓ Branch 0 taken 41969664 times.
✓ Branch 1 taken 13989888 times.
 55959552 for (int i = 0; i < nc; i++) {
289 41969664 const float u = av_clipf(in[i] * s->scale, 0.f, N);
290 41969664 f[i] = lrintf(u);
291 41969664 d[i] = u - f[i];
292 41969664 sum += f[i];
293 }
294
295
2/2
✓ Branch 0 taken 6985274 times.
✓ Branch 1 taken 7004614 times.
 13989888 if (sum & 1) {
296 6985274 int k = 0, dir;
297
2/2
✓ Branch 0 taken 13970548 times.
✓ Branch 1 taken 6985274 times.
 20955822 for (int i = 1; i < nc; i++)
298
2/2
✓ Branch 0 taken 5751663 times.
✓ Branch 1 taken 8218885 times.
 13970548 if (fabsf(d[i]) > fabsf(d[k]))
299 5751663 k = i;
300
2/2
✓ Branch 0 taken 3495776 times.
✓ Branch 1 taken 3489498 times.
 6985274 dir = d[k] >= 0.f ? 1 : -1;
301
3/4
✓ Branch 0 taken 6985274 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 820 times.
✓ Branch 3 taken 6984454 times.
 6985274 if (f[k] + dir < 0 || f[k] + dir > N)
302 820 dir = -dir;
303 6985274 f[k] += dir;
304 }
305 13989888 }
306
307 /**
308 * Account one pixel using the lattice color with indices f, registering the
309 * color in the cell table and the used color list on first use.
310 *
311 * @return the lattice cell position, or AVERROR(ENOMEM)
312 */
313 3649536 static av_always_inline int color_inc(LatticePalContext *s, const int f[4])
314 {
315 3649536 int pos = f[0];
316 int idx;
317
318
2/2
✓ Branch 0 taken 7299072 times.
✓ Branch 1 taken 3649536 times.
 10948608 for (int i = 1; i < s->nc; i++)
319 7299072 pos = pos * s->dim + f[i];
320 3649536 idx = s->cell[pos];
321
322
2/2
✓ Branch 0 taken 519270 times.
✓ Branch 1 taken 3130266 times.
 3649536 if (!idx) {
323 PalEntry *e;
324
325
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 519234 times.
 519270 if (s->nb_used == s->nb_alloc) {
326 36 const int na = FFMAX(s->nb_alloc * 2, 512);
327 36 PalEntry *nl = av_realloc_array(s->list, na, sizeof(*nl));
328
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 36 times.
 36 if (!nl)
329 ✗ return AVERROR(ENOMEM);
330 36 s->list = nl;
331 36 s->nb_alloc = na;
332 }
333 519270 e = &s->list[s->nb_used];
334 519270 e->pos = pos;
335 519270 e->ci[0] = f[0];
336 519270 e->ci[1] = f[1];
337 519270 e->ci[2] = f[2];
338
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 519270 times.
 519270 e->ci[3] = s->nc == 4 ? f[3] : 0;
339 519270 e->alive = 1;
340 519270 e->count = 0;
341 519270 s->cell[pos] = idx = ++s->nb_used;
342 }
343 3649536 s->list[idx - 1].count++;
344 3649536 return pos;
345 }
346
347 /**
348 * Find the nearest live color of the used color list, excluding self
349 * (pass -1 to match any live color).
350 *
351 * While many colors are alive, search outward in Chebyshev shells of the
352 * lattice index space; the component value difference of a cell r shells
353 * away is at least r * min_gap, which bounds the search once a candidate
354 * is known. When only few colors are left the lattice around them is
355 * sparse and shells get expensive, so scan the compact live list instead.
356 * (For 3 components ci[3] is 0 everywhere, contributing nothing.)
357 *
358 * @return list index of the nearest live color, its distance in *out_d2
359 */
360 1756701 static int nearest_alive(LatticePalContext *s, const uint8_t ci[4], int self, int *out_d2)
361 {
362 1756701 PalEntry *list = s->list;
363 1756701 const uint8_t *val = s->idx2val;
364 1756701 const int dim = s->dim;
365 1756701 const int i0 = ci[0], i1 = ci[1], i2 = ci[2], i3 = ci[3];
366 1756701 const int v0 = val[i0], v1 = val[i1], v2 = val[i2], v3 = val[i3];
367 1756701 int best = -1, bestd = INT_MAX;
368
369
3/4
✓ Branch 0 taken 1756701 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 583825 times.
✓ Branch 3 taken 1172876 times.
 1756701 if (s->nb_alive > 0 && s->nb_alive <= 1024) {
370
2/2
✓ Branch 0 taken 181035657 times.
✓ Branch 1 taken 583825 times.
 181619482 for (int k = 0; k < s->nb_alive; k++) {
371 181035657 const int j = s->alive_arr[k];
372 181035657 const PalEntry *o = &list[j];
373 int d2, dv;
374
375
2/2
✓ Branch 0 taken 51033 times.
✓ Branch 1 taken 180984624 times.
 181035657 if (j == self)
376 51033 continue;
377 180984624 dv = val[o->ci[0]] - v0; d2 = dv * dv;
378 180984624 dv = val[o->ci[1]] - v1; d2 += dv * dv;
379 180984624 dv = val[o->ci[2]] - v2; d2 += dv * dv;
380 180984624 dv = val[o->ci[3]] - v3; d2 += dv * dv;
381
2/2
✓ Branch 0 taken 3626548 times.
✓ Branch 1 taken 177358076 times.
 180984624 if (d2 < bestd) {
382 3626548 bestd = d2;
383 3626548 best = j;
384 }
385 }
386
1/2
✓ Branch 0 taken 583825 times.
✗ Branch 1 not taken.
 583825 *out_d2 = best >= 0 ? bestd : 0;
387 583825 return best;
388 }
389
390 #define CHECK_CELL3(a, b, c) do { \
391 const int e = s->cell[((a) * dim + (b)) * dim + (c)]; \
392 if (e > 0 && e - 1 != self && list[e - 1].alive) { \
393 const int dr = val[a] - v0; \
394 const int dg = val[b] - v1; \
395 const int db = val[c] - v2; \
396 const int d2 = dr * dr + dg * dg + db * db; \
397 if (d2 < bestd) { \
398 bestd = d2; \
399 best = e - 1; \
400 } \
401 } \
402 } while (0)
403
404 #define CHECK_CELL4(a, b, c, l) do { \
405 const int e = s->cell[(((a) * dim + (b)) * dim + (c)) * dim + (l)]; \
406 if (e > 0 && e - 1 != self && list[e - 1].alive) { \
407 const int dr = val[a] - v0; \
408 const int dg = val[b] - v1; \
409 const int db = val[c] - v2; \
410 const int da_ = val[l] - v3; \
411 const int d2 = dr * dr + dg * dg + db * db + da_ * da_; \
412 if (d2 < bestd) { \
413 bestd = d2; \
414 best = e - 1; \
415 } \
416 } \
417 } while (0)
418
419
1/2
✓ Branch 0 taken 2479265 times.
✗ Branch 1 not taken.
 2479265 for (int r = 1; r < dim; r++) {
420
4/4
✓ Branch 0 taken 1180449 times.
✓ Branch 1 taken 1298816 times.
✓ Branch 2 taken 1172876 times.
✓ Branch 3 taken 7573 times.
 2479265 if (best >= 0 && (int64_t)r * s->min_gap * r * s->min_gap > bestd)
421 1172876 break;
422
4/4
✓ Branch 0 taken 163520 times.
✓ Branch 1 taken 5233044 times.
✓ Branch 2 taken 4090175 times.
✓ Branch 3 taken 1306389 times.
 5396564 for (int a = FFMAX(i0 - r, 0); a <= FFMIN(i0 + r, dim - 1); a++) {
423 4090175 const int da = FFABS(a - i0);
424
4/4
✓ Branch 0 taken 510311 times.
✓ Branch 1 taken 16925648 times.
✓ Branch 2 taken 13345784 times.
✓ Branch 3 taken 4090175 times.
 17435959 for (int b = FFMAX(i1 - r, 0); b <= FFMIN(i1 + r, dim - 1); b++) {
425 13345784 const int dab = FFMAX(da, FFABS(b - i1));
426
427
1/2
✓ Branch 0 taken 13345784 times.
✗ Branch 1 not taken.
 13345784 if (s->nc == 3) {
428
2/2
✓ Branch 0 taken 10910630 times.
✓ Branch 1 taken 2435154 times.
 13345784 if (dab == r) {
429
4/4
✓ Branch 0 taken 1542386 times.
✓ Branch 1 taken 45265842 times.
✓ Branch 2 taken 35897598 times.
✓ Branch 3 taken 10910630 times.
 46808228 for (int c = FFMAX(i2 - r, 0); c <= FFMIN(i2 + r, dim - 1); c++)
430
2/2
✓ Branch 0 taken 18018521 times.
✓ Branch 1 taken 17879077 times.
 35897598 if (!((a + b + c) & 1))
431
7/8
✓ Branch 0 taken 13261835 times.
✓ Branch 1 taken 4756686 times.
✓ Branch 2 taken 13261835 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 8379222 times.
✓ Branch 5 taken 4882613 times.
✓ Branch 6 taken 1336984 times.
✓ Branch 7 taken 7042238 times.
 18018521 CHECK_CELL3(a, b, c);
432 } else {
433
4/4
✓ Branch 0 taken 2300647 times.
✓ Branch 1 taken 134507 times.
✓ Branch 2 taken 628516 times.
✓ Branch 3 taken 1672131 times.
 2435154 if (i2 - r >= 0 && !((a + b + i2 - r) & 1))
434
7/8
✓ Branch 0 taken 349720 times.
✓ Branch 1 taken 278796 times.
✓ Branch 2 taken 349720 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 71870 times.
✓ Branch 5 taken 277850 times.
✓ Branch 6 taken 22972 times.
✓ Branch 7 taken 48898 times.
 628516 CHECK_CELL3(a, b, i2 - r);
435
4/4
✓ Branch 0 taken 2295662 times.
✓ Branch 1 taken 139492 times.
✓ Branch 2 taken 626390 times.
✓ Branch 3 taken 1669272 times.
 2435154 if (i2 + r < dim && !((a + b + i2 + r) & 1))
436
7/8
✓ Branch 0 taken 349433 times.
✓ Branch 1 taken 276957 times.
✓ Branch 2 taken 349433 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 70224 times.
✓ Branch 5 taken 279209 times.
✓ Branch 6 taken 20879 times.
✓ Branch 7 taken 49345 times.
 626390 CHECK_CELL3(a, b, i2 + r);
437 }
438 } else {
439 ✗ for (int c = FFMAX(i2 - r, 0); c <= FFMIN(i2 + r, dim - 1); c++) {
440 ✗ if (FFMAX(dab, FFABS(c - i2)) == r) {
441 ✗ for (int l = FFMAX(i3 - r, 0); l <= FFMIN(i3 + r, dim - 1); l++)
442 ✗ if (!((a + b + c + l) & 1))
443 ✗ CHECK_CELL4(a, b, c, l);
444 } else {
445 ✗ if (i3 - r >= 0 && !((a + b + c + i3 - r) & 1))
446 ✗ CHECK_CELL4(a, b, c, i3 - r);
447 ✗ if (i3 + r < dim && !((a + b + c + i3 + r) & 1))
448 ✗ CHECK_CELL4(a, b, c, i3 + r);
449 }
450 }
451 }
452 }
453 }
454 }
455 #undef CHECK_CELL3
456 #undef CHECK_CELL4
457
458
1/2
✓ Branch 0 taken 1172876 times.
✗ Branch 1 not taken.
 1172876 *out_d2 = best >= 0 ? bestd : 0;
459 1172876 return best;
460 }
461
462 1451528 static void nn_search(LatticePalContext *s, int self)
463 {
464 int d2;
465
466 1451528 s->list[self].nn = nearest_alive(s, s->list[self].ci, self, &d2);
467 1451528 s->list[self].d2 = d2;
468 1451528 }
469
470 typedef struct HeapEnt {
471 int64_t imp; ///< impact of the removal when the entry was pushed
472 int idx; ///< used color list index
473 } HeapEnt;
474
475 1036755 static void heap_push(HeapEnt *heap, int *nb, int64_t imp, int idx)
476 {
477 1036755 int i = (*nb)++;
478
479
4/4
✓ Branch 0 taken 2039308 times.
✓ Branch 1 taken 773 times.
✓ Branch 2 taken 1003326 times.
✓ Branch 3 taken 1035982 times.
 2040081 while (i > 0 && heap[(i - 1) / 2].imp > imp) {
480 1003326 heap[i] = heap[(i - 1) / 2];
481 1003326 i = (i - 1) / 2;
482 }
483 1036755 heap[i].imp = imp;
484 1036755 heap[i].idx = idx;
485 1036755 }
486
487 905311 static HeapEnt heap_pop(HeapEnt *heap, int *nb)
488 {
489 905311 const HeapEnt top = heap[0];
490 905311 const HeapEnt last = heap[--*nb];
491 905311 int i = 0, c;
492
493
2/2
✓ Branch 0 taken 10296844 times.
✓ Branch 1 taken 691184 times.
 10988028 while ((c = 2 * i + 1) < *nb) {
494
4/4
✓ Branch 0 taken 10296367 times.
✓ Branch 1 taken 477 times.
✓ Branch 2 taken 4988223 times.
✓ Branch 3 taken 5308144 times.
 10296844 if (c + 1 < *nb && heap[c + 1].imp < heap[c].imp)
495 4988223 c++;
496
2/2
✓ Branch 0 taken 214127 times.
✓ Branch 1 taken 10082717 times.
 10296844 if (heap[c].imp >= last.imp)
497 214127 break;
498 10082717 heap[i] = heap[c];
499 10082717 i = c;
500 }
501 905311 heap[i] = last;
502 905311 return top;
503 }
504
505 /**
506 * Reduce the live colors down to target by repeatedly dropping the color
507 * whose removal has the least impact: its pixel count times the squared
508 * distance to the nearest remaining color, which then absorbs the
509 * dropped pixels.
510 *
511 * An impact can only grow: counts grow by absorption and the nearest
512 * neighbor distance grows when the neighbor is dropped. Stale heap entries
513 * therefore underestimate their color's impact, and validating at pop time
514 * and re-pushing the corrected entry yields the exact minimum.
515 */
516 114 static int reduce_colors(LatticePalContext *s, int target)
517 {
518 114 PalEntry *list = s->list;
519 int alive;
520 114 int nb_heap = 0, cap = s->nb_used + 64;
521 114 HeapEnt *heap = av_malloc_array(cap, sizeof(*heap));
522
523
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 114 times.
 114 if (!heap)
524 ✗ return AVERROR(ENOMEM);
525
526
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 103 times.
 114 if (s->alive_alloc < s->nb_used) {
527 11 av_freep(&s->alive_arr);
528 11 av_freep(&s->alive_pos);
529 11 s->alive_arr = av_malloc_array(s->nb_used, sizeof(*s->alive_arr));
530 11 s->alive_pos = av_malloc_array(s->nb_used, sizeof(*s->alive_pos));
531
2/4
✓ Branch 0 taken 11 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 11 times.
 11 if (!s->alive_arr || !s->alive_pos) {
532 ✗ av_free(heap);
533 ✗ return AVERROR(ENOMEM);
534 }
535 11 s->alive_alloc = s->nb_used;
536 }
537 114 s->nb_alive = 0;
538
2/2
✓ Branch 0 taken 1984836 times.
✓ Branch 1 taken 114 times.
 1984950 for (int i = 0; i < s->nb_used; i++) {
539
2/2
✓ Branch 0 taken 1342422 times.
✓ Branch 1 taken 642414 times.
 1984836 if (!list[i].alive)
540 1342422 continue;
541 642414 s->alive_pos[i] = s->nb_alive;
542 642414 s->alive_arr[s->nb_alive++] = i;
543 }
544 114 alive = s->nb_alive;
545
546
2/2
✓ Branch 0 taken 642414 times.
✓ Branch 1 taken 114 times.
 642528 for (int k = 0; k < s->nb_alive; k++) {
547 642414 const int i = s->alive_arr[k];
548
549 642414 nn_search(s, i);
550 642414 heap_push(heap, &nb_heap, list[i].count * list[i].d2, i);
551 }
552
553
2/2
✓ Branch 0 taken 905311 times.
✓ Branch 1 taken 114 times.
 905425 while (alive > target) {
554 905311 const HeapEnt top = heap_pop(heap, &nb_heap);
555 905311 const int i = top.idx;
556 int64_t imp;
557
558
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 905311 times.
 905311 if (!list[i].alive)
559 394341 continue;
560
2/2
✓ Branch 0 taken 401381 times.
✓ Branch 1 taken 503930 times.
 905311 if (!list[list[i].nn].alive)
561 401381 nn_search(s, i);
562 905311 imp = list[i].count * list[i].d2;
563
2/2
✓ Branch 0 taken 394341 times.
✓ Branch 1 taken 510970 times.
 905311 if (imp != top.imp) {
564 /* stale entry, reinsert with the corrected impact */
565
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 394341 times.
 394341 if (nb_heap == cap) {
566 ✗ HeapEnt *nh = av_realloc_array(heap, cap * 2, sizeof(*heap));
567 ✗ if (!nh) {
568 ✗ av_free(heap);
569 ✗ return AVERROR(ENOMEM);
570 }
571 ✗ heap = nh;
572 ✗ cap *= 2;
573 }
574 394341 heap_push(heap, &nb_heap, imp, i);
575 394341 continue;
576 }
577 510970 list[i].alive = 0;
578 510970 list[list[i].nn].count += list[i].count;
579 510970 alive--;
580 /* swap-remove from the compact live list */
581 510970 s->alive_arr[s->alive_pos[i]] = s->alive_arr[--s->nb_alive];
582 510970 s->alive_pos[s->alive_arr[s->nb_alive]] = s->alive_pos[i];
583 }
584
585 114 av_free(heap);
586 114 return 0;
587 }
588
589 /** Palette color (AARRGGBB) of a used color list entry. */
590 23223 static av_always_inline uint32_t entry_color(const LatticePalContext *s, const PalEntry *e)
591 {
592
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 23223 times.
 23223 return (s->nc == 4 ? (uint32_t)s->idx2val[e->ci[3]] << 24 : 0xFF000000) |
593 23223 s->idx2val[e->ci[0]] << 16 |
594 46446 s->idx2val[e->ci[1]] << 8 |
595 23223 s->idx2val[e->ci[2]];
596 }
597
598 /**
599 * Full refinement pass: rediffuse the whole frame against the final
600 * palette.
601 *
602 * The first pass diffused its error against the full lattice, so the shift
603 * from dropped colors to their nearest survivor is uncompensated and shows
604 * up as flat discolored patches exactly where the reduction hit. Re-run
605 * Floyd-Steinberg error diffusion on the original pixels, quantizing to
606 * the nearest final palette color, which redistributes that error by
607 * construction (error diffusion is average correct against any codebook).
608 *
609 * The nearest palette color is resolved at lattice cell granularity: used
610 * cells already hold their slot from the remap, cells first touched by the
611 * diffusion get a scan over the at most 256 survivors and are cached in
612 * the cell table and recorded for the per frame reset.
613 */
614 6 static int refine_full(LatticePalContext *s, AVFrame *out, const AVFrame *in)
615 {
616 6 const int w = in->width, h = in->height;
617 6 const int ro = s->ro, go = s->go, bo = s->bo, ao = s->ao, pixstep = s->pixstep;
618 6 const int nc = s->nc;
619 6 const uint32_t *pal = (const uint32_t *)out->data[1];
620
621 6 memset(s->err[0], 0, (w + 2) * nc * sizeof(*s->err[0]));
622 6 memset(s->err[1], 0, (w + 2) * nc * sizeof(*s->err[1]));
623
624
2/2
✓ Branch 0 taken 1728 times.
✓ Branch 1 taken 6 times.
 1734 for (int y = 0; y < h; y++) {
625 1728 const uint8_t *src = in->data[0] + y * in->linesize[0];
626 1728 uint8_t *dst = out->data[0] + y * out->linesize[0];
627
2/2
✓ Branch 0 taken 864 times.
✓ Branch 1 taken 864 times.
 1728 const int dir = (y & 1) ? -1 : 1;
628
2/2
✓ Branch 0 taken 864 times.
✓ Branch 1 taken 864 times.
 1728 const int x0 = dir > 0 ? 0 : w - 1;
629 1728 int32_t *err_cur = s->err[ y & 1] + nc;
630 1728 int32_t *err_next = s->err[(y + 1) & 1] + nc;
631 int f[4], px[4];
632
633 1728 px[3] = 255;
634 1728 memset(err_next - nc, 0, (w + 2) * nc * sizeof(*err_next));
635
636
2/2
✓ Branch 0 taken 608256 times.
✓ Branch 1 taken 1728 times.
 609984 for (int k = 0; k < w; k++) {
637 608256 const int x = x0 + k * dir;
638 608256 const int32_t *e = &err_cur[x * nc];
639 uint32_t c;
640 int pos, slot1;
641
642 608256 px[0] = av_clip_uint8(src[x * pixstep + ro] + ((e[0] + 8) >> 4));
643 608256 px[1] = av_clip_uint8(src[x * pixstep + go] + ((e[1] + 8) >> 4));
644 608256 px[2] = av_clip_uint8(src[x * pixstep + bo] + ((e[2] + 8) >> 4));
645
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 608256 times.
 608256 if (nc == 4)
646 ✗ px[3] = av_clip_uint8((ao >= 0 ? src[x * pixstep + ao] : 255) + ((e[3] + 8) >> 4));
647
648 608256 quant_dn(s, px, f);
649 608256 pos = f[0];
650
2/2
✓ Branch 0 taken 1216512 times.
✓ Branch 1 taken 608256 times.
 1824768 for (int i = 1; i < nc; i++)
651 1216512 pos = pos * s->dim + f[i];
652
653 608256 slot1 = s->cell[pos];
654
2/2
✓ Branch 0 taken 4772 times.
✓ Branch 1 taken 603484 times.
 608256 if (!slot1) {
655 4772 const uint8_t *val = s->idx2val;
656 4772 int bd = INT_MAX;
657
658
2/2
✓ Branch 0 taken 1221632 times.
✓ Branch 1 taken 4772 times.
 1226404 for (int k = 0; k < s->nb_alive; k++) {
659 1221632 const PalEntry *o = &s->list[s->alive_arr[k]];
660 int d2, dv;
661
662 1221632 dv = val[o->ci[0]] - val[f[0]]; d2 = dv * dv;
663 1221632 dv = val[o->ci[1]] - val[f[1]]; d2 += dv * dv;
664 1221632 dv = val[o->ci[2]] - val[f[2]]; d2 += dv * dv;
665
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1221632 times.
 1221632 if (nc == 4) {
666 ✗ dv = val[o->ci[3]] - val[f[3]]; d2 += dv * dv;
667 }
668
2/2
✓ Branch 0 taken 28893 times.
✓ Branch 1 taken 1192739 times.
 1221632 if (d2 < bd) {
669 28893 bd = d2;
670 28893 slot1 = o->nn + 1;
671 }
672 }
673
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4771 times.
 4772 if (s->nb_touched == s->touched_alloc) {
674 1 const int na = FFMAX(s->touched_alloc * 2, 1024);
675 1 int *nt = av_realloc_array(s->touched, na, sizeof(*nt));
676
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 1 if (!nt)
677 ✗ return AVERROR(ENOMEM);
678 1 s->touched = nt;
679 1 s->touched_alloc = na;
680 }
681 4772 s->touched[s->nb_touched++] = pos;
682 4772 s->cell[pos] = slot1;
683 }
684 608256 dst[x] = slot1 - 1;
685
686 608256 c = pal[slot1 - 1];
687
2/2
✓ Branch 0 taken 1824768 times.
✓ Branch 1 taken 608256 times.
 2433024 for (int i = 0; i < nc; i++) {
688 static const int sh[4] = { 16, 8, 0, 24 };
689 1824768 const int qerr = px[i] - (int)(c >> sh[i] & 0xff);
690
691 1824768 err_cur [(x + dir) * nc + i] += qerr * 7;
692 1824768 err_next[(x - dir) * nc + i] += qerr * 3;
693 1824768 err_next[ x * nc + i] += qerr * 5;
694 1824768 err_next[(x + dir) * nc + i] += qerr;
695 }
696 }
697 }
698 6 return 0;
699 }
700
701 /**
702 * Residual refinement pass: rediffuse only the error of the dropped
703 * colors, using the first pass quantized color as the diffusion target.
704 * The error stream then carries only the removal residuals: a pixel whose
705 * color survived and that receives no incoming residual picks its own
706 * color with zero error and is unchanged, keeping the character of the
707 * selected dither mode outside the reduced regions.
708 *
709 * Runs before the cell table is rewritten: cells hold list indices, and
710 * cells resolved on demand are cached as -(slot + 1).
711 */
712 6 static int refine_residual(LatticePalContext *s, AVFrame *out, const AVFrame *in)
713 {
714 6 const int w = in->width, h = in->height;
715 6 const int nc = s->nc;
716 6 const uint32_t *pal = (const uint32_t *)out->data[1];
717 6 const uint8_t *val = s->idx2val;
718 6 PalEntry *list = s->list;
719
720 6 memset(s->err[0], 0, (w + 2) * nc * sizeof(*s->err[0]));
721 6 memset(s->err[1], 0, (w + 2) * nc * sizeof(*s->err[1]));
722
723
2/2
✓ Branch 0 taken 1728 times.
✓ Branch 1 taken 6 times.
 1734 for (int y = 0; y < h; y++) {
724 1728 const uint32_t *ppos = s->pixpos + (size_t)y * w;
725 1728 uint8_t *dst = out->data[0] + y * out->linesize[0];
726
2/2
✓ Branch 0 taken 864 times.
✓ Branch 1 taken 864 times.
 1728 const int dir = (y & 1) ? -1 : 1;
727
2/2
✓ Branch 0 taken 864 times.
✓ Branch 1 taken 864 times.
 1728 const int x0 = dir > 0 ? 0 : w - 1;
728 1728 int32_t *err_cur = s->err[ y & 1] + nc;
729 1728 int32_t *err_next = s->err[(y + 1) & 1] + nc;
730 int f[4], px[4];
731
732 1728 px[3] = 255;
733 1728 memset(err_next - nc, 0, (w + 2) * nc * sizeof(*err_next));
734
735
2/2
✓ Branch 0 taken 608256 times.
✓ Branch 1 taken 1728 times.
 609984 for (int k = 0; k < w; k++) {
736 608256 const int x = x0 + k * dir;
737 608256 const PalEntry *e1 = &list[s->cell[ppos[x]] - 1];
738 608256 const int32_t *e = &err_cur[x * nc];
739 uint32_t c;
740 int pos, v, slot;
741
742
4/6
✓ Branch 0 taken 20885 times.
✓ Branch 1 taken 587371 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 20885 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 20885 times.
 608256 if (e1->alive && !(e[0] | e[1] | e[2] | (nc == 4 ? e[3] : 0))) {
743 /* surviving color, no incoming residual: unchanged */
744 ✗ dst[x] = e1->nn;
745 ✗ continue;
746 }
747
748 /* target = first pass color + carried residual */
749
2/2
✓ Branch 0 taken 1824768 times.
✓ Branch 1 taken 608256 times.
 2433024 for (int i = 0; i < nc; i++)
750 1824768 px[i] = av_clip_uint8(val[e1->ci[i]] + ((e[i] + 8) >> 4));
751
752 608256 quant_dn(s, px, f);
753 608256 pos = f[0];
754
2/2
✓ Branch 0 taken 1216512 times.
✓ Branch 1 taken 608256 times.
 1824768 for (int i = 1; i < nc; i++)
755 1216512 pos = pos * s->dim + f[i];
756
757 608256 v = s->cell[pos];
758
2/2
✓ Branch 0 taken 589263 times.
✓ Branch 1 taken 18993 times.
 608256 if (v > 0) {
759 589263 slot = list[v - 1].nn;
760
2/2
✓ Branch 0 taken 13999 times.
✓ Branch 1 taken 4994 times.
 18993 } else if (v < 0) {
761 13999 slot = -v - 1;
762 } else {
763 4994 int bd = INT_MAX;
764
765 4994 slot = 0;
766
2/2
✓ Branch 0 taken 1278464 times.
✓ Branch 1 taken 4994 times.
 1283458 for (int j = 0; j < s->nb_alive; j++) {
767 1278464 const PalEntry *o = &list[s->alive_arr[j]];
768 int d2, dv;
769
770 1278464 dv = val[o->ci[0]] - val[f[0]]; d2 = dv * dv;
771 1278464 dv = val[o->ci[1]] - val[f[1]]; d2 += dv * dv;
772 1278464 dv = val[o->ci[2]] - val[f[2]]; d2 += dv * dv;
773
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1278464 times.
 1278464 if (nc == 4) {
774 ✗ dv = val[o->ci[3]] - val[f[3]]; d2 += dv * dv;
775 }
776
2/2
✓ Branch 0 taken 30212 times.
✓ Branch 1 taken 1248252 times.
 1278464 if (d2 < bd) {
777 30212 bd = d2;
778 30212 slot = o->nn;
779 }
780 }
781
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4993 times.
 4994 if (s->nb_touched == s->touched_alloc) {
782 1 const int na = FFMAX(s->touched_alloc * 2, 1024);
783 1 int *nt = av_realloc_array(s->touched, na, sizeof(*nt));
784
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 1 if (!nt)
785 ✗ return AVERROR(ENOMEM);
786 1 s->touched = nt;
787 1 s->touched_alloc = na;
788 }
789 4994 s->touched[s->nb_touched++] = pos;
790 4994 s->cell[pos] = -(slot + 1);
791 }
792 608256 dst[x] = slot;
793
794 608256 c = pal[slot];
795
2/2
✓ Branch 0 taken 1824768 times.
✓ Branch 1 taken 608256 times.
 2433024 for (int i = 0; i < nc; i++) {
796 static const int sh[4] = { 16, 8, 0, 24 };
797 1824768 const int qerr = px[i] - (int)(c >> sh[i] & 0xff);
798
799 1824768 err_cur [(x + dir) * nc + i] += qerr * 7;
800 1824768 err_next[(x - dir) * nc + i] += qerr * 3;
801 1824768 err_next[ x * nc + i] += qerr * 5;
802 1824768 err_next[(x + dir) * nc + i] += qerr;
803 }
804 }
805 }
806 6 return 0;
807 }
808
809 /**
810 * Rediffuse the whole frame against the current live colors and reassign
811 * every pixel, recounting how often each live color is actually used.
812 *
813 * Cells resolving to a dead or unused state are cached as -(list index+1);
814 * stale caches from earlier rounds heal themselves through the alive check.
815 */
816 90 static int batch_assign(LatticePalContext *s, const AVFrame *in)
817 {
818 90 const int w = in->width, h = in->height;
819 90 const int ro = s->ro, go = s->go, bo = s->bo, ao = s->ao, pixstep = s->pixstep;
820 90 const int nc = s->nc;
821 90 const uint8_t *val = s->idx2val;
822 90 PalEntry *list = s->list;
823
824
2/2
✓ Branch 0 taken 126236 times.
✓ Branch 1 taken 90 times.
 126326 for (int k = 0; k < s->nb_alive; k++)
825 126236 list[s->alive_arr[k]].count = 0;
826
827 90 memset(s->err[0], 0, (w + 2) * nc * sizeof(*s->err[0]));
828 90 memset(s->err[1], 0, (w + 2) * nc * sizeof(*s->err[1]));
829
830
2/2
✓ Branch 0 taken 25920 times.
✓ Branch 1 taken 90 times.
 26010 for (int y = 0; y < h; y++) {
831 25920 const uint8_t *src = in->data[0] + y * in->linesize[0];
832 25920 uint32_t *ppos = s->pixpos + (size_t)y * w;
833
2/2
✓ Branch 0 taken 12960 times.
✓ Branch 1 taken 12960 times.
 25920 const int dir = (y & 1) ? -1 : 1;
834
2/2
✓ Branch 0 taken 12960 times.
✓ Branch 1 taken 12960 times.
 25920 const int x0 = dir > 0 ? 0 : w - 1;
835 25920 int32_t *err_cur = s->err[ y & 1] + nc;
836 25920 int32_t *err_next = s->err[(y + 1) & 1] + nc;
837 int f[4], px[4];
838
839 25920 px[3] = 255;
840 25920 memset(err_next - nc, 0, (w + 2) * nc * sizeof(*err_next));
841
842
2/2
✓ Branch 0 taken 9123840 times.
✓ Branch 1 taken 25920 times.
 9149760 for (int k = 0; k < w; k++) {
843 9123840 const int x = x0 + k * dir;
844 9123840 const int32_t *e = &err_cur[x * nc];
845 const PalEntry *o;
846 int pos, v, j;
847
848 9123840 px[0] = av_clip_uint8(src[x * pixstep + ro] + ((e[0] + 8) >> 4));
849 9123840 px[1] = av_clip_uint8(src[x * pixstep + go] + ((e[1] + 8) >> 4));
850 9123840 px[2] = av_clip_uint8(src[x * pixstep + bo] + ((e[2] + 8) >> 4));
851
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 9123840 times.
 9123840 if (nc == 4)
852 ✗ px[3] = av_clip_uint8((ao >= 0 ? src[x * pixstep + ao] : 255) + ((e[3] + 8) >> 4));
853
854 9123840 quant_dn(s, px, f);
855 9123840 pos = f[0];
856
2/2
✓ Branch 0 taken 18247680 times.
✓ Branch 1 taken 9123840 times.
 27371520 for (int i = 1; i < nc; i++)
857 18247680 pos = pos * s->dim + f[i];
858
859 9123840 v = s->cell[pos];
860
4/4
✓ Branch 0 taken 1206125 times.
✓ Branch 1 taken 7917715 times.
✓ Branch 2 taken 1102868 times.
✓ Branch 3 taken 103257 times.
 9123840 if (v > 0 && list[v - 1].alive) {
861 1102868 j = v - 1;
862
4/4
✓ Branch 0 taken 7914694 times.
✓ Branch 1 taken 106278 times.
✓ Branch 2 taken 7715799 times.
✓ Branch 3 taken 198895 times.
 8020972 } else if (v < 0 && list[-v - 1].alive) {
863 7715799 j = -v - 1;
864 } else {
865
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 305173 times.
 305173 const uint8_t fci[4] = { f[0], f[1], f[2], nc == 4 ? f[3] : 0 };
866 int d2;
867
868 305173 j = nearest_alive(s, fci, -1, &d2);
869
2/2
✓ Branch 0 taken 3021 times.
✓ Branch 1 taken 302152 times.
 305173 if (!v) {
870
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 3020 times.
 3021 if (s->nb_touched == s->touched_alloc) {
871 1 const int na = FFMAX(s->touched_alloc * 2, 1024);
872 1 int *nt = av_realloc_array(s->touched, na, sizeof(*nt));
873
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 1 if (!nt)
874 ✗ return AVERROR(ENOMEM);
875 1 s->touched = nt;
876 1 s->touched_alloc = na;
877 }
878 3021 s->touched[s->nb_touched++] = pos;
879 }
880 305173 s->cell[pos] = -(j + 1);
881 }
882 9123840 o = &list[j];
883 9123840 list[j].count++;
884 9123840 ppos[x] = j;
885
886
2/2
✓ Branch 0 taken 27371520 times.
✓ Branch 1 taken 9123840 times.
 36495360 for (int i = 0; i < nc; i++) {
887 27371520 const int qerr = px[i] - val[o->ci[i]];
888
889 27371520 err_cur [(x + dir) * nc + i] += qerr * 7;
890 27371520 err_next[(x - dir) * nc + i] += qerr * 3;
891 27371520 err_next[ x * nc + i] += qerr * 5;
892 27371520 err_next[(x + dir) * nc + i] += qerr;
893 }
894 }
895 }
896 90 return 0;
897 }
898
899 /**
900 * Batched reduction: instead of dropping all excess colors against the
901 * first pass statistics, drop half of the excess, rediffuse the frame
902 * against the survivors and recount from the actual assignments, then
903 * repeat. Colors whose pixels the rediffusion absorbed elsewhere become
904 * free to drop, while colors that dithering cannot reproduce (extremes of
905 * the used gamut) keep their pixels and with them a high removal impact,
906 * so they are protected in later rounds.
907 */
908 6 static int reduce_batched(LatticePalContext *s, const AVFrame *in)
909 {
910 6 int alive = s->nb_used;
911
912
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 6 times.
 96 while (alive > s->max_colors) {
913 90 const int excess = alive - s->max_colors;
914 90 const int target = s->max_colors + excess / 2;
915 90 int ret = reduce_colors(s, target);
916
917
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 90 times.
 90 if (ret < 0)
918 ✗ return ret;
919 90 alive = target;
920
921 90 ret = batch_assign(s, in);
922
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 90 times.
 90 if (ret < 0)
923 ✗ return ret;
924
925 /* drop the colors the rediffusion no longer uses */
926
2/2
✓ Branch 0 taken 126236 times.
✓ Branch 1 taken 90 times.
 126326 for (int k = 0; k < s->nb_alive;) {
927 126236 const int i = s->alive_arr[k];
928
929
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 126216 times.
 126236 if (!s->list[i].count) {
930 20 s->list[i].alive = 0;
931 20 s->alive_arr[k] = s->alive_arr[--s->nb_alive];
932 20 s->alive_pos[s->alive_arr[k]] = k;
933 20 alive--;
934 } else
935 126216 k++;
936 }
937 }
938 6 return 0;
939 }
940
941 36 static int filter_frame(AVFilterLink *inlink, AVFrame *in)
942 {
943 36 AVFilterContext *ctx = inlink->dst;
944 36 LatticePalContext *s = ctx->priv;
945 36 AVFilterLink *outlink = ctx->outputs[0];
946 36 const int w = in->width, h = in->height;
947 36 const int ro = s->ro, go = s->go, bo = s->bo, ao = s->ao, pixstep = s->pixstep;
948 36 const int nc = s->nc;
949 uint32_t *pal;
950 AVFrame *out;
951 36 int ret, reduced = 0;
952
953 36 out = ff_get_video_buffer(outlink, outlink->w, outlink->h);
954
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 36 times.
 36 if (!out) {
955 ✗ av_frame_free(&in);
956 ✗ return AVERROR(ENOMEM);
957 }
958 36 ret = av_frame_copy_props(out, in);
959
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 36 times.
 36 if (ret < 0)
960 ✗ goto fail;
961
962 36 s->nb_used = 0;
963 36 s->nb_alive = 0;
964
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 24 times.
 36 if (s->dither == DITHERING_FLOYD_STEINBERG) {
965 12 memset(s->err[0], 0, (w + 2) * nc * sizeof(*s->err[0]));
966 12 memset(s->err[1], 0, (w + 2) * nc * sizeof(*s->err[1]));
967 }
968
969 /* first pass: quantize, collect the used colors and their pixel counts */
970
2/2
✓ Branch 0 taken 10368 times.
✓ Branch 1 taken 36 times.
 10404 for (int y = 0; y < h; y++) {
971 10368 const uint8_t *src = in->data[0] + y * in->linesize[0];
972 10368 uint32_t *ppos = s->pixpos + (size_t)y * w;
973 int f[4], px[4], pos;
974
975 10368 px[3] = 255;
976
977
2/2
✓ Branch 0 taken 3456 times.
✓ Branch 1 taken 6912 times.
 10368 if (s->dither == DITHERING_FLOYD_STEINBERG) {
978 /* serpentine scan: odd lines run right to left with mirrored
979 * diffusion weights, avoiding directional drift artifacts */
980
2/2
✓ Branch 0 taken 1728 times.
✓ Branch 1 taken 1728 times.
 3456 const int dir = (y & 1) ? -1 : 1;
981
2/2
✓ Branch 0 taken 1728 times.
✓ Branch 1 taken 1728 times.
 3456 const int x0 = dir > 0 ? 0 : w - 1;
982 3456 int32_t *err_cur = s->err[ y & 1] + nc;
983 3456 int32_t *err_next = s->err[(y + 1) & 1] + nc;
984
985 3456 memset(err_next - nc, 0, (w + 2) * nc * sizeof(*err_next));
986
987
2/2
✓ Branch 0 taken 1216512 times.
✓ Branch 1 taken 3456 times.
 1219968 for (int k = 0; k < w; k++) {
988 1216512 const int x = x0 + k * dir;
989 1216512 const int32_t *e = &err_cur[x * nc];
990
991 1216512 px[0] = av_clip_uint8(src[x * pixstep + ro] + ((e[0] + 8) >> 4));
992 1216512 px[1] = av_clip_uint8(src[x * pixstep + go] + ((e[1] + 8) >> 4));
993 1216512 px[2] = av_clip_uint8(src[x * pixstep + bo] + ((e[2] + 8) >> 4));
994
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1216512 times.
 1216512 if (nc == 4)
995 ✗ px[3] = av_clip_uint8((ao >= 0 ? src[x * pixstep + ao] : 255) + ((e[3] + 8) >> 4));
996
997 1216512 quant_dn(s, px, f);
998 1216512 pos = color_inc(s, f);
999
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1216512 times.
 1216512 if (pos < 0) {
1000 ✗ ret = pos;
1001 ✗ goto fail;
1002 }
1003 1216512 ppos[x] = pos;
1004
1005
2/2
✓ Branch 0 taken 3649536 times.
✓ Branch 1 taken 1216512 times.
 4866048 for (int i = 0; i < nc; i++) {
1006 3649536 const int qerr = px[i] - s->idx2val[f[i]];
1007
1008 3649536 err_cur [(x + dir) * nc + i] += qerr * 7;
1009 3649536 err_next[(x - dir) * nc + i] += qerr * 3;
1010 3649536 err_next[ x * nc + i] += qerr * 5;
1011 3649536 err_next[(x + dir) * nc + i] += qerr;
1012 }
1013 }
1014
3/4
✓ Branch 0 taken 3456 times.
✓ Branch 1 taken 3456 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3456 times.
 10368 } else if (s->dither == DITHERING_BAYER || s->dither == DITHERING_BLUE_NOISE) {
1015 3456 const int blue = s->dither == DITHERING_BLUE_NOISE;
1016
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3456 times.
 3456 const int mask = blue ? VC_MASK : 7;
1017
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3456 times.
 3456 const int rowoff = blue ? (y & VC_MASK) << VC_SHIFT : (y & 7) << 3;
1018 const int *dt[4];
1019
1020
2/2
✓ Branch 0 taken 10368 times.
✓ Branch 1 taken 3456 times.
 13824 for (int i = 0; i < nc; i++)
1021
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10368 times.
 10368 dt[i] = (blue ? s->blue_dither[i] : s->ordered_dither[i]) + rowoff;
1022
1023
2/2
✓ Branch 0 taken 1216512 times.
✓ Branch 1 taken 3456 times.
 1219968 for (int x = 0; x < w; x++) {
1024 1216512 px[0] = src[x * pixstep + ro] + dt[0][x & mask];
1025 1216512 px[1] = src[x * pixstep + go] + dt[1][x & mask];
1026 1216512 px[2] = src[x * pixstep + bo] + dt[2][x & mask];
1027
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1216512 times.
 1216512 if (nc == 4)
1028 ✗ px[3] = (ao >= 0 ? src[x * pixstep + ao] : 255) + dt[3][x & mask];
1029
1030 1216512 quant_dn(s, px, f);
1031 1216512 pos = color_inc(s, f);
1032
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1216512 times.
 1216512 if (pos < 0) {
1033 ✗ ret = pos;
1034 ✗ goto fail;
1035 }
1036 1216512 ppos[x] = pos;
1037 }
1038 } else {
1039
2/2
✓ Branch 0 taken 1216512 times.
✓ Branch 1 taken 3456 times.
 1219968 for (int x = 0; x < w; x++) {
1040 1216512 px[0] = src[x * pixstep + ro];
1041 1216512 px[1] = src[x * pixstep + go];
1042 1216512 px[2] = src[x * pixstep + bo];
1043
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1216512 times.
 1216512 if (nc == 4)
1044 ✗ px[3] = ao >= 0 ? src[x * pixstep + ao] : 255;
1045
1046 1216512 quant_dn(s, px, f);
1047 1216512 pos = color_inc(s, f);
1048
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1216512 times.
 1216512 if (pos < 0) {
1049 ✗ ret = pos;
1050 ✗ goto fail;
1051 }
1052 1216512 ppos[x] = pos;
1053 }
1054 }
1055 }
1056
1057 36 reduced = s->nb_used > s->max_colors;
1058
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 6 times.
 36 if (reduced) {
1059
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 24 times.
 30 if (s->refine == REFINE_BATCHED)
1060 6 ret = reduce_batched(s, in);
1061 else
1062 24 ret = reduce_colors(s, s->max_colors);
1063
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 30 times.
 30 if (ret < 0)
1064 ✗ goto fail;
1065 30 av_log(ctx, AV_LOG_DEBUG,
1066 "pts %"PRId64": %d lattice colors used, %d dropped\n",
1067 30 in->pts, s->nb_used, s->nb_used - s->nb_alive);
1068 }
1069
1070 /* Assign palette slots so that each entry is identical or similar to
1071 * the same entry of the previous frame: static regions keep their
1072 * indices and both the index plane and the palette stay small under
1073 * inter prediction. Unclaimed slots keep the previous frame's color.
1074 * On the first frame the all black previous palette degenerates this
1075 * to insertion order. */
1076 {
1077 36 uint8_t claimed[AVPALETTE_COUNT] = { 0 };
1078
1079
2/2
✓ Branch 0 taken 519270 times.
✓ Branch 1 taken 36 times.
 519306 for (int i = 0; i < s->nb_used; i++) {
1080 519270 PalEntry *e = &s->list[i];
1081 uint32_t c;
1082
1083
2/2
✓ Branch 0 taken 510990 times.
✓ Branch 1 taken 8280 times.
 519270 if (!e->alive)
1084 510990 continue;
1085 8280 e->nn = -1;
1086 8280 c = entry_color(s, e);
1087
2/2
✓ Branch 0 taken 1910797 times.
✓ Branch 1 taken 6663 times.
 1917460 for (int slot = 0; slot < AVPALETTE_COUNT; slot++) {
1088
4/4
✓ Branch 0 taken 1771921 times.
✓ Branch 1 taken 138876 times.
✓ Branch 2 taken 1617 times.
✓ Branch 3 taken 1770304 times.
 1910797 if (!claimed[slot] && s->prev_pal[slot] == c) {
1089 1617 claimed[slot] = 1;
1090 1617 e->nn = slot;
1091 1617 break;
1092 }
1093 }
1094 }
1095
2/2
✓ Branch 0 taken 519270 times.
✓ Branch 1 taken 36 times.
 519306 for (int i = 0; i < s->nb_used; i++) {
1096 519270 PalEntry *e = &s->list[i];
1097 uint32_t c;
1098 519270 int bslot = -1;
1099 519270 int64_t bd = INT64_MAX;
1100
1101
4/4
✓ Branch 0 taken 8280 times.
✓ Branch 1 taken 510990 times.
✓ Branch 2 taken 1617 times.
✓ Branch 3 taken 6663 times.
 519270 if (!e->alive || e->nn >= 0)
1102 512607 continue;
1103 6663 c = entry_color(s, e);
1104
2/2
✓ Branch 0 taken 1705728 times.
✓ Branch 1 taken 6663 times.
 1712391 for (int slot = 0; slot < AVPALETTE_COUNT; slot++) {
1105 1705728 const uint32_t p = s->prev_pal[slot];
1106 1705728 const int da = (int)(p >> 24 ) - (int)(c >> 24 );
1107 1705728 const int dr = (int)(p >> 16 & 0xff) - (int)(c >> 16 & 0xff);
1108 1705728 const int dg = (int)(p >> 8 & 0xff) - (int)(c >> 8 & 0xff);
1109 1705728 const int db = (int)(p & 0xff) - (int)(c & 0xff);
1110 1705728 const int64_t d2 = (int64_t)da * da + dr * dr + dg * dg + db * db;
1111
1112
4/4
✓ Branch 0 taken 862494 times.
✓ Branch 1 taken 843234 times.
✓ Branch 2 taken 27228 times.
✓ Branch 3 taken 835266 times.
 1705728 if (!claimed[slot] && d2 < bd) {
1113 27228 bd = d2;
1114 27228 bslot = slot;
1115 }
1116 }
1117 6663 claimed[bslot] = 1;
1118 6663 e->nn = bslot;
1119 }
1120
1121 36 pal = (uint32_t *)out->data[1];
1122 36 memcpy(pal, s->prev_pal, AVPALETTE_SIZE);
1123
2/2
✓ Branch 0 taken 519270 times.
✓ Branch 1 taken 36 times.
 519306 for (int i = 0; i < s->nb_used; i++) {
1124 519270 const PalEntry *e = &s->list[i];
1125
1126
2/2
✓ Branch 0 taken 8280 times.
✓ Branch 1 taken 510990 times.
 519270 if (e->alive)
1127 8280 pal[e->nn] = entry_color(s, e);
1128 }
1129 36 memcpy(s->prev_pal, pal, AVPALETTE_SIZE);
1130 }
1131
3/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
 36 if (!(s->refine == REFINE_BATCHED && reduced)) {
1132
2/2
✓ Branch 0 taken 414477 times.
✓ Branch 1 taken 30 times.
 414507 for (int i = 0; i < s->nb_used; i++) {
1133 414477 PalEntry *e = &s->list[i];
1134
1135
2/2
✓ Branch 0 taken 407733 times.
✓ Branch 1 taken 6744 times.
 414477 if (!e->alive) {
1136 407733 nn_search(s, i);
1137 407733 e->nn = s->list[e->nn].nn;
1138 }
1139 }
1140 }
1141
1142
3/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 30 times.
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 36 if (s->refine == REFINE_BATCHED && reduced) {
1143 /* pixpos holds the list index assigned by the last rediffusion */
1144
2/2
✓ Branch 0 taken 1728 times.
✓ Branch 1 taken 6 times.
 1734 for (int y = 0; y < h; y++) {
1145 1728 const uint32_t *ppos = s->pixpos + (size_t)y * w;
1146 1728 uint8_t *dst = out->data[0] + y * out->linesize[0];
1147
1148
2/2
✓ Branch 0 taken 608256 times.
✓ Branch 1 taken 1728 times.
 609984 for (int x = 0; x < w; x++)
1149 608256 dst[x] = s->list[ppos[x]].nn;
1150 }
1151
3/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 30 } else if (s->refine == REFINE_RESIDUAL && reduced) {
1152 /* needs the cell table still holding list indices */
1153 6 ret = refine_residual(s, out, in);
1154
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (ret < 0)
1155 ✗ goto fail;
1156
3/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 18 times.
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 24 } else if (s->refine == REFINE_FULL && reduced) {
1157 /* rewrite the cell table to slot + 1, 0 keeps meaning unused */
1158
2/2
✓ Branch 0 taken 102799 times.
✓ Branch 1 taken 6 times.
 102805 for (int i = 0; i < s->nb_used; i++)
1159 102799 s->cell[s->list[i].pos] = s->list[i].nn + 1;
1160 6 ret = refine_full(s, out, in);
1161
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (ret < 0)
1162 ✗ goto fail;
1163 } else {
1164 /* second pass: write the palette indices */
1165
2/2
✓ Branch 0 taken 209128 times.
✓ Branch 1 taken 18 times.
 209146 for (int i = 0; i < s->nb_used; i++)
1166 209128 s->cell[s->list[i].pos] = s->list[i].nn;
1167
2/2
✓ Branch 0 taken 5184 times.
✓ Branch 1 taken 18 times.
 5202 for (int y = 0; y < h; y++) {
1168 5184 const uint32_t *ppos = s->pixpos + (size_t)y * w;
1169 5184 uint8_t *dst = out->data[0] + y * out->linesize[0];
1170
1171
2/2
✓ Branch 0 taken 1824768 times.
✓ Branch 1 taken 5184 times.
 1829952 for (int x = 0; x < w; x++)
1172 1824768 dst[x] = s->cell[ppos[x]];
1173 }
1174 }
1175
1176 /* reset the cell table for the next frame */
1177
2/2
✓ Branch 0 taken 519270 times.
✓ Branch 1 taken 36 times.
 519306 for (int i = 0; i < s->nb_used; i++)
1178 519270 s->cell[s->list[i].pos] = 0;
1179
2/2
✓ Branch 0 taken 12787 times.
✓ Branch 1 taken 36 times.
 12823 for (int i = 0; i < s->nb_touched; i++)
1180 12787 s->cell[s->touched[i]] = 0;
1181 36 s->nb_touched = 0;
1182
1183 36 av_frame_free(&in);
1184 36 return ff_filter_frame(outlink, out);
1185
1186 ✗ fail:
1187 ✗ for (int i = 0; i < s->nb_used; i++)
1188 ✗ s->cell[s->list[i].pos] = 0;
1189 ✗ for (int i = 0; i < s->nb_touched; i++)
1190 ✗ s->cell[s->touched[i]] = 0;
1191 ✗ s->nb_touched = 0;
1192 ✗ av_frame_free(&in);
1193 ✗ av_frame_free(&out);
1194 ✗ return ret;
1195 }
1196
1197 6 static int config_input(AVFilterLink *inlink)
1198 {
1199 6 AVFilterContext *ctx = inlink->dst;
1200 6 LatticePalContext *s = ctx->priv;
1201 6 const AVPixFmtDescriptor *desc = av_pix_fmt_desc_get(inlink->format);
1202 6 const int N = s->density;
1203
1204 6 s->pixstep = desc->comp[0].step;
1205 6 s->ro = desc->comp[0].offset;
1206 6 s->go = desc->comp[1].offset;
1207 6 s->bo = desc->comp[2].offset;
1208 ✗ s->ao = desc->nb_components == 4 && (desc->flags & AV_PIX_FMT_FLAG_ALPHA)
1209
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 ? desc->comp[3].offset : -1;
1210
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 s->nc = s->alpha ? 4 : 3;
1211
1212
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 6 if (s->alpha && N > MAX_DENSITY_ALPHA) {
1213 ✗ av_log(ctx, AV_LOG_ERROR,
1214 "density is limited to %d when the alpha channel is quantized\n",
1215 MAX_DENSITY_ALPHA);
1216 ✗ return AVERROR(EINVAL);
1217 }
1218
1219 6 s->scale = N / 255.f;
1220
2/2
✓ Branch 0 taken 173 times.
✓ Branch 1 taken 6 times.
 179 for (int i = 0; i <= N; i++)
1221 173 s->idx2val[i] = lrintf(i * 255.f / N);
1222
1223
2/2
✓ Branch 0 taken 1536 times.
✓ Branch 1 taken 6 times.
 1542 for (int i = 0; i < AVPALETTE_COUNT; i++)
1224 1536 s->prev_pal[i] = 0xFF000000;
1225
1226 6 s->dim = N + 1;
1227 6 s->min_gap = 255;
1228
2/2
✓ Branch 0 taken 167 times.
✓ Branch 1 taken 6 times.
 173 for (int i = 1; i <= N; i++)
1229 167 s->min_gap = FFMIN(s->min_gap, s->idx2val[i] - s->idx2val[i - 1]);
1230
1231 6 av_freep(&s->cell);
1232
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 12 s->cell = av_calloc(s->nc == 4 ? (size_t)s->dim * s->dim * s->dim * s->dim
1233 6 : (size_t)s->dim * s->dim * s->dim,
1234 sizeof(*s->cell));
1235 6 av_freep(&s->pixpos);
1236 6 s->pixpos = av_malloc_array((size_t)inlink->w * inlink->h, sizeof(*s->pixpos));
1237
2/4
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
 6 if (!s->cell || !s->pixpos)
1238 ✗ return AVERROR(ENOMEM);
1239
1240
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 4 times.
 6 if (s->dither == DITHERING_BAYER) {
1241 /* The per-channel period of the scaled D3 lattice is 2*step, not
1242 * step: translating the lattice by step*e_i flips the parity
1243 * constraint, only 2*step*e_i maps it onto itself. The dither
1244 * offsets must span one period for intermediate colors to be
1245 * reproduced on average, hence the amplitude of 2*step.
1246 *
1247 * The matrix and the per-channel decorrelation follow the classic
1248 * swscale ordered dither (libswscale/yuv2rgb.c): all channels use
1249 * ff_dither_8x8_73, green shifted by one column and blue with
1250 * flipped rows. The channel patterns are strongly anti-correlated
1251 * (-0.94 R/G, -0.60 R/B), which keeps the offset sum and with it
1252 * the luminance noise small, and it interacts well with the D3
1253 * quantizer: over a 40..215 color cube this scheme measures the
1254 * smallest flat field bias (max 8.3, mean 3.5) and the smallest
1255 * luminance RMS noise (15.3) of all evaluated 8x8 schemes. With
1256 * alpha, the fourth channel combines both transforms. */
1257 2 const float amp = 2.f * 255.f / N;
1258
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 2 times.
 18 for (int y = 0; y < 8; y++) {
1259
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 16 times.
 144 for (int x = 0; x < 8; x++) {
1260 128 const int i = y << 3 | x;
1261 128 s->ordered_dither[0][i] = lrintf(((dither_8x8_73[y][x] + 0.5f) / 64.f - 0.5f) * amp);
1262 128 s->ordered_dither[1][i] = lrintf(((dither_8x8_73[y][(x + 1) & 7] + 0.5f) / 64.f - 0.5f) * amp);
1263 128 s->ordered_dither[2][i] = lrintf(((dither_8x8_73[y ^ 7][x] + 0.5f) / 64.f - 0.5f) * amp);
1264 128 s->ordered_dither[3][i] = lrintf(((dither_8x8_73[y ^ 7][(x + 1) & 7] + 0.5f) / 64.f - 0.5f) * amp);
1265 }
1266 }
1267
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 } else if (s->dither == DITHERING_BLUE_NOISE) {
1268 /* Dither in a lattice adapted frame: step*(1,1,0), step*(1,-1,0)
1269 * and 2*step*(0,0,1) span an orthogonal sublattice of the color
1270 * lattice, so offsets drawn uniformly from its fundamental box tile
1271 * the color space under lattice translations, and since Dn Voronoi
1272 * cells are centrally symmetric the dithered average is exactly the
1273 * input color. Independently seeded void-and-cluster masks
1274 * a, b, c (and d with alpha) drive the axes:
1275 * tR = step * (a + b - 1)
1276 * tG = step * (a - b)
1277 * tB = step * (2c - 1)
1278 * Compared with independent per-channel offsets over the axis
1279 * aligned (-step,step)^3 box (index 4 instead of 2) this cuts the
1280 * red/green noise variance in half; the remaining full range axis
1281 * is assigned to blue, the perceptually least weighted channel.
1282 * For D4 the sublattice step*{(1,1,0,0), (1,-1,0,0), (0,0,1,1),
1283 * (0,0,1,-1)} is orthogonal with equally long axes, so all four
1284 * channels get the halved variance:
1285 * tB = step * (c + d - 1)
1286 * tA = step * (c - d) */
1287 ✗ const float step = 255.f / N;
1288 float kern[VC_KSIZE * VC_KSIZE];
1289 ✗ uint16_t *ranks[4] = { NULL };
1290 ✗ uint8_t *bits = NULL;
1291 ✗ float *energy = NULL, *e1 = NULL;
1292 ✗ int ret = 0;
1293
1294 ✗ for (int dy = -VC_RADIUS; dy <= VC_RADIUS; dy++)
1295 ✗ for (int dx = -VC_RADIUS; dx <= VC_RADIUS; dx++)
1296 ✗ kern[(dy + VC_RADIUS) * VC_KSIZE + dx + VC_RADIUS] =
1297 ✗ expf(-(dx * dx + dy * dy) / (2 * VC_SIGMA * VC_SIGMA));
1298
1299 ✗ bits = av_malloc_array(VC_AREA, sizeof(*bits));
1300 ✗ energy = av_malloc_array(VC_AREA, sizeof(*energy));
1301 ✗ e1 = av_malloc_array(VC_AREA, sizeof(*e1));
1302 ✗ ret = !bits || !energy || !e1 ? AVERROR(ENOMEM) : 0;
1303
1304 ✗ for (int p = 0; p < s->nc && ret >= 0; p++) {
1305 AVLFG lfg;
1306
1307 ✗ ranks[p] = av_malloc_array(VC_AREA, sizeof(*ranks[p]));
1308 ✗ if (!s->blue_dither[p])
1309 ✗ s->blue_dither[p] = av_malloc_array(VC_AREA, sizeof(*s->blue_dither[p]));
1310 ✗ if (!ranks[p] || !s->blue_dither[p]) {
1311 ✗ ret = AVERROR(ENOMEM);
1312 ✗ break;
1313 }
1314 ✗ av_lfg_init(&lfg, 0xB1DE + p);
1315 ✗ vc_generate(ranks[p], bits, energy, e1, kern, &lfg);
1316 }
1317
1318 ✗ if (ret >= 0) {
1319 ✗ for (int i = 0; i < VC_AREA; i++) {
1320 ✗ const float a = (ranks[0][i] + 0.5f) / VC_AREA;
1321 ✗ const float b = (ranks[1][i] + 0.5f) / VC_AREA;
1322 ✗ const float c = (ranks[2][i] + 0.5f) / VC_AREA;
1323
1324 ✗ s->blue_dither[0][i] = lrintf(step * (a + b - 1.f));
1325 ✗ s->blue_dither[1][i] = lrintf(step * (a - b));
1326 ✗ if (s->nc == 4) {
1327 ✗ const float dd = (ranks[3][i] + 0.5f) / VC_AREA;
1328
1329 ✗ s->blue_dither[2][i] = lrintf(step * (c + dd - 1.f));
1330 ✗ s->blue_dither[3][i] = lrintf(step * (c - dd));
1331 } else {
1332 ✗ s->blue_dither[2][i] = lrintf(step * (2.f * c - 1.f));
1333 }
1334 }
1335 }
1336
1337 ✗ av_freep(&ranks[0]);
1338 ✗ av_freep(&ranks[1]);
1339 ✗ av_freep(&ranks[2]);
1340 ✗ av_freep(&ranks[3]);
1341 ✗ av_freep(&bits);
1342 ✗ av_freep(&energy);
1343 ✗ av_freep(&e1);
1344 ✗ if (ret < 0)
1345 ✗ return ret;
1346 }
1347
4/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 2 times.
 6 if (s->dither == DITHERING_FLOYD_STEINBERG || s->refine) {
1348
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
 12 for (int i = 0; i < 2; i++) {
1349 8 av_freep(&s->err[i]);
1350 8 s->err[i] = av_calloc(inlink->w + 2, s->nc * sizeof(*s->err[i]));
1351
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 8 if (!s->err[i])
1352 ✗ return AVERROR(ENOMEM);
1353 }
1354 }
1355
1356 6 return 0;
1357 }
1358
1359 12 static av_cold void uninit(AVFilterContext *ctx)
1360 {
1361 12 LatticePalContext *s = ctx->priv;
1362
1363 12 av_freep(&s->err[0]);
1364 12 av_freep(&s->err[1]);
1365
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 12 times.
 60 for (int i = 0; i < 4; i++)
1366 48 av_freep(&s->blue_dither[i]);
1367 12 av_freep(&s->cell);
1368 12 av_freep(&s->pixpos);
1369 12 av_freep(&s->list);
1370 12 av_freep(&s->alive_arr);
1371 12 av_freep(&s->alive_pos);
1372 12 av_freep(&s->touched);
1373 12 }
1374
1375 static const AVFilterPad latticepal_inputs[] = {
1376 {
1377 .name = "default",
1378 .type = AVMEDIA_TYPE_VIDEO,
1379 .filter_frame = filter_frame,
1380 .config_props = config_input,
1381 },
1382 };
1383
1384 const FFFilter ff_vf_latticepal = {
1385 .p.name = "latticepal",
1386 .p.description = NULL_IF_CONFIG_SMALL("Convert RGB to PAL8 using a per-frame FCC lattice palette."),
1387 .p.priv_class = &latticepal_class,
1388 .priv_size = sizeof(LatticePalContext),
1389 .uninit = uninit,
1390 FILTER_INPUTS(latticepal_inputs),
1391 FILTER_OUTPUTS(ff_video_default_filterpad),
1392 FILTER_QUERY_FUNC2(query_formats),
1393 };
1394