FFmpeg coverage


Directory: ../../../ffmpeg/
File: src/libavfilter/vf_palettegen.c
Date: 2022-12-05 03:11:11
Exec Total Coverage
Lines: 233 274 85.0%
Functions: 22 24 91.7%
Branches: 150 204 73.5%

Line Branch Exec Source
1 /*
2 * Copyright (c) 2015 Stupeflix
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 * Generate one palette for a whole video stream.
24 */
25
26 #include "libavutil/avassert.h"
27 #include "libavutil/internal.h"
28 #include "libavutil/opt.h"
29 #include "libavutil/qsort.h"
30 #include "libavutil/intreadwrite.h"
31 #include "avfilter.h"
32 #include "internal.h"
33
34 /* Reference a color and how much it's used */
35 struct color_ref {
36 uint32_t color;
37 uint64_t count;
38 };
39
40 /* Store a range of colors */
41 struct range_box {
42 uint32_t color; // average color
43 int64_t variance; // overall variance of the box (how much the colors are spread)
44 int start; // index in PaletteGenContext->refs
45 int len; // number of referenced colors
46 int sorted_by; // whether range of colors is sorted by red (0), green (1) or blue (2)
47 };
48
49 struct hist_node {
50 struct color_ref *entries;
51 int nb_entries;
52 };
53
54 enum {
55 STATS_MODE_ALL_FRAMES,
56 STATS_MODE_DIFF_FRAMES,
57 STATS_MODE_SINGLE_FRAMES,
58 NB_STATS_MODE
59 };
60
61 #define NBITS 5
62 #define HIST_SIZE (1<<(4*NBITS))
63
64 typedef struct PaletteGenContext {
65 const AVClass *class;
66
67 int max_colors;
68 int reserve_transparent;
69 int stats_mode;
70 int use_alpha;
71
72 AVFrame *prev_frame; // previous frame used for the diff stats_mode
73 struct hist_node histogram[HIST_SIZE]; // histogram/hashtable of the colors
74 struct color_ref **refs; // references of all the colors used in the stream
75 int nb_refs; // number of color references (or number of different colors)
76 struct range_box boxes[256]; // define the segmentation of the colorspace (the final palette)
77 int nb_boxes; // number of boxes (increase will segmenting them)
78 int palette_pushed; // if the palette frame is pushed into the outlink or not
79 uint8_t transparency_color[4]; // background color for transparency
80 } PaletteGenContext;
81
82 #define OFFSET(x) offsetof(PaletteGenContext, x)
83 #define FLAGS AV_OPT_FLAG_FILTERING_PARAM|AV_OPT_FLAG_VIDEO_PARAM
84 static const AVOption palettegen_options[] = {
85 { "max_colors", "set the maximum number of colors to use in the palette", OFFSET(max_colors), AV_OPT_TYPE_INT, {.i64=256}, 4, 256, FLAGS },
86 { "reserve_transparent", "reserve a palette entry for transparency", OFFSET(reserve_transparent), AV_OPT_TYPE_BOOL, {.i64=1}, 0, 1, FLAGS },
87 { "transparency_color", "set a background color for transparency", OFFSET(transparency_color), AV_OPT_TYPE_COLOR, {.str="lime"}, 0, 0, FLAGS },
88 { "stats_mode", "set statistics mode", OFFSET(stats_mode), AV_OPT_TYPE_INT, {.i64=STATS_MODE_ALL_FRAMES}, 0, NB_STATS_MODE-1, FLAGS, "mode" },
89 { "full", "compute full frame histograms", 0, AV_OPT_TYPE_CONST, {.i64=STATS_MODE_ALL_FRAMES}, INT_MIN, INT_MAX, FLAGS, "mode" },
90 { "diff", "compute histograms only for the part that differs from previous frame", 0, AV_OPT_TYPE_CONST, {.i64=STATS_MODE_DIFF_FRAMES}, INT_MIN, INT_MAX, FLAGS, "mode" },
91 { "single", "compute new histogram for each frame", 0, AV_OPT_TYPE_CONST, {.i64=STATS_MODE_SINGLE_FRAMES}, INT_MIN, INT_MAX, FLAGS, "mode" },
92 { "use_alpha", "create a palette including alpha values", OFFSET(use_alpha), AV_OPT_TYPE_BOOL, {.i64 = 0}, 0, 1, FLAGS },
93 { NULL }
94 };
95
96 AVFILTER_DEFINE_CLASS(palettegen);
97
98 2 static int query_formats(AVFilterContext *ctx)
99 {
100 static const enum AVPixelFormat in_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE};
101 static const enum AVPixelFormat out_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE};
102 int ret;
103
104
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
2 if ((ret = ff_formats_ref(ff_make_format_list(in_fmts) , &ctx->inputs[0]->outcfg.formats)) < 0)
105 return ret;
106
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
2 if ((ret = ff_formats_ref(ff_make_format_list(out_fmts), &ctx->outputs[0]->incfg.formats)) < 0)
107 return ret;
108 2 return 0;
109 }
110
111 typedef int (*cmp_func)(const void *, const void *);
112
113 #define DECLARE_CMP_FUNC(name, pos) \
114 static int cmp_##name(const void *pa, const void *pb) \
115 { \
116 const struct color_ref * const *a = pa; \
117 const struct color_ref * const *b = pb; \
118 return (int)((*a)->color >> (8 * (3 - (pos))) & 0xff) \
119 - (int)((*b)->color >> (8 * (3 - (pos))) & 0xff); \
120 }
121
122 DECLARE_CMP_FUNC(a, 0)
123 994576 DECLARE_CMP_FUNC(r, 1)
124 1151413 DECLARE_CMP_FUNC(g, 2)
125 921067 DECLARE_CMP_FUNC(b, 3)
126
127 static const cmp_func cmp_funcs[] = {cmp_a, cmp_r, cmp_g, cmp_b};
128
129 /**
130 * Simple color comparison for sorting the final palette
131 */
132 2461 static int cmp_color(const void *a, const void *b)
133 {
134 2461 const struct range_box *box1 = a;
135 2461 const struct range_box *box2 = b;
136 2461 return FFDIFFSIGN(box1->color , box2->color);
137 }
138
139 370991 static av_always_inline int diff(const uint32_t a, const uint32_t b)
140 {
141 370991 const uint8_t c1[] = {a >> 16 & 0xff, a >> 8 & 0xff, a & 0xff};
142 370991 const uint8_t c2[] = {b >> 16 & 0xff, b >> 8 & 0xff, b & 0xff};
143 370991 const int dr = c1[0] - c2[0];
144 370991 const int dg = c1[1] - c2[1];
145 370991 const int db = c1[2] - c2[2];
146 370991 return dr*dr + dg*dg + db*db;
147 }
148
149 static av_always_inline int diff_alpha(const uint32_t a, const uint32_t b)
150 {
151 const uint8_t c1[] = {a >> 24 & 0xff, a >> 16 & 0xff, a >> 8 & 0xff, a & 0xff};
152 const uint8_t c2[] = {b >> 24 & 0xff, b >> 16 & 0xff, b >> 8 & 0xff, b & 0xff};
153 const int da = c1[0] - c2[0];
154 const int dr = c1[1] - c2[1];
155 const int dg = c1[2] - c2[2];
156 const int db = c1[3] - c2[3];
157 return da*da + dr*dr + dg*dg + db*db;
158 }
159
160 /**
161 * Find the next box to split: pick the one with the highest variance
162 */
163 381 static int get_next_box_id_to_split(PaletteGenContext *s)
164 {
165 381 int box_id, i, best_box_id = -1;
166 381 int64_t max_variance = -1;
167
168
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 379 times.
381 if (s->nb_boxes == s->max_colors - s->reserve_transparent)
169 2 return -1;
170
171
2/2
✓ Branch 0 taken 40511 times.
✓ Branch 1 taken 379 times.
40890 for (box_id = 0; box_id < s->nb_boxes; box_id++) {
172 40511 struct range_box *box = &s->boxes[box_id];
173
174
2/2
✓ Branch 0 taken 40428 times.
✓ Branch 1 taken 83 times.
40511 if (s->boxes[box_id].len >= 2) {
175
176
2/2
✓ Branch 0 taken 756 times.
✓ Branch 1 taken 39672 times.
40428 if (box->variance == -1) {
177 756 int64_t variance = 0;
178
179
2/2
✓ Branch 0 taken 370991 times.
✓ Branch 1 taken 756 times.
371747 for (i = 0; i < box->len; i++) {
180 370991 const struct color_ref *ref = s->refs[box->start + i];
181
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 370991 times.
370991 if (s->use_alpha)
182 variance += (int64_t)diff_alpha(ref->color, box->color) * ref->count;
183 else
184 370991 variance += (int64_t)diff(ref->color, box->color) * ref->count;
185 }
186 756 box->variance = variance;
187 }
188
2/2
✓ Branch 0 taken 1575 times.
✓ Branch 1 taken 38853 times.
40428 if (box->variance > max_variance) {
189 1575 best_box_id = box_id;
190 1575 max_variance = box->variance;
191 }
192 } else {
193 83 box->variance = -1;
194 }
195 }
196 379 return best_box_id;
197 }
198
199 /**
200 * Get the 32-bit average color for the range of RGB colors enclosed in the
201 * specified box. Takes into account the weight of each color.
202 */
203 764 static uint32_t get_avg_color(struct color_ref * const *refs,
204 const struct range_box *box, int use_alpha)
205 {
206 int i;
207 764 const int n = box->len;
208 764 uint64_t a = 0, r = 0, g = 0, b = 0, div = 0;
209
210
2/2
✓ Branch 0 taken 416246 times.
✓ Branch 1 taken 764 times.
417010 for (i = 0; i < n; i++) {
211 416246 const struct color_ref *ref = refs[box->start + i];
212
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 416246 times.
416246 if (use_alpha)
213 a += (ref->color >> 24 & 0xff) * ref->count;
214 416246 r += (ref->color >> 16 & 0xff) * ref->count;
215 416246 g += (ref->color >> 8 & 0xff) * ref->count;
216 416246 b += (ref->color & 0xff) * ref->count;
217 416246 div += ref->count;
218 }
219
220
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 764 times.
764 if (use_alpha)
221 a = a / div;
222 764 r = r / div;
223 764 g = g / div;
224 764 b = b / div;
225
226
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 764 times.
764 if (use_alpha)
227 return a<<24 | r<<16 | g<<8 | b;
228
229 764 return 0xffU<<24 | r<<16 | g<<8 | b;
230 }
231
232 /**
233 * Split given box in two at position n. The original box becomes the left part
234 * of the split, and the new index box is the right part.
235 */
236 381 static void split_box(PaletteGenContext *s, struct range_box *box, int n)
237 {
238 381 struct range_box *new_box = &s->boxes[s->nb_boxes++];
239 381 new_box->start = n + 1;
240 381 new_box->len = box->start + box->len - new_box->start;
241 381 new_box->sorted_by = box->sorted_by;
242 381 box->len -= new_box->len;
243
244
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 381 times.
381 av_assert0(box->len >= 1);
245
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 381 times.
381 av_assert0(new_box->len >= 1);
246
247 381 box->color = get_avg_color(s->refs, box, s->use_alpha);
248 381 new_box->color = get_avg_color(s->refs, new_box, s->use_alpha);
249 381 box->variance = -1;
250 381 new_box->variance = -1;
251 381 }
252
253 /**
254 * Write the palette into the output frame.
255 */
256 2 static void write_palette(AVFilterContext *ctx, AVFrame *out)
257 {
258 2 const PaletteGenContext *s = ctx->priv;
259 2 int x, y, box_id = 0;
260 2 uint32_t *pal = (uint32_t *)out->data[0];
261 2 const int pal_linesize = out->linesize[0] >> 2;
262 2 uint32_t last_color = 0;
263
264
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 2 times.
34 for (y = 0; y < out->height; y++) {
265
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 32 times.
544 for (x = 0; x < out->width; x++) {
266
2/2
✓ Branch 0 taken 383 times.
✓ Branch 1 taken 129 times.
512 if (box_id < s->nb_boxes) {
267 383 pal[x] = s->boxes[box_id++].color;
268
5/6
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 359 times.
✓ Branch 2 taken 22 times.
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 381 times.
383 if ((x || y) && pal[x] == last_color)
269 av_log(ctx, AV_LOG_WARNING, "Duped color: %08"PRIX32"\n", pal[x]);
270 383 last_color = pal[x];
271 } else {
272 129 pal[x] = last_color; // pad with last color
273 }
274 }
275 32 pal += pal_linesize;
276 }
277
278
3/4
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
2 if (s->reserve_transparent && !s->use_alpha) {
279
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
1 av_assert0(s->nb_boxes < 256);
280 1 pal[out->width - pal_linesize - 1] = AV_RB32(&s->transparency_color) >> 8;
281 }
282 2 }
283
284 /**
285 * Crawl the histogram to get all the defined colors, and create a linear list
286 * of them (each color reference entry is a pointer to the value in the
287 * histogram/hash table).
288 */
289 2 static struct color_ref **load_color_refs(const struct hist_node *hist, int nb_refs)
290 {
291 2 int i, j, k = 0;
292 2 struct color_ref **refs = av_malloc_array(nb_refs, sizeof(*refs));
293
294
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
2 if (!refs)
295 return NULL;
296
297
2/2
✓ Branch 0 taken 2097152 times.
✓ Branch 1 taken 2 times.
2097154 for (j = 0; j < HIST_SIZE; j++) {
298 2097152 const struct hist_node *node = &hist[j];
299
300
2/2
✓ Branch 0 taken 44830 times.
✓ Branch 1 taken 2097152 times.
2141982 for (i = 0; i < node->nb_entries; i++)
301 44830 refs[k++] = &node->entries[i];
302 }
303
304 2 return refs;
305 }
306
307 2 static double set_colorquant_ratio_meta(AVFrame *out, int nb_out, int nb_in)
308 {
309 char buf[32];
310 2 const double ratio = (double)nb_out / nb_in;
311 2 snprintf(buf, sizeof(buf), "%f", ratio);
312 2 av_dict_set(&out->metadata, "lavfi.color_quant_ratio", buf, 0);
313 2 return ratio;
314 }
315
316 /**
317 * Main function implementing the Median Cut Algorithm defined by Paul Heckbert
318 * in Color Image Quantization for Frame Buffer Display (1982)
319 */
320 2 static AVFrame *get_palette_frame(AVFilterContext *ctx)
321 {
322 AVFrame *out;
323 2 PaletteGenContext *s = ctx->priv;
324 2 AVFilterLink *outlink = ctx->outputs[0];
325 double ratio;
326 2 int box_id = 0;
327 struct range_box *box;
328
329 /* reference only the used colors from histogram */
330 2 s->refs = load_color_refs(s->histogram, s->nb_refs);
331
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
2 if (!s->refs) {
332 av_log(ctx, AV_LOG_ERROR, "Unable to allocate references for %d different colors\n", s->nb_refs);
333 return NULL;
334 }
335
336 /* create the palette frame */
337 2 out = ff_get_video_buffer(outlink, outlink->w, outlink->h);
338
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
2 if (!out)
339 return NULL;
340 2 out->pts = 0;
341
342 /* set first box for 0..nb_refs */
343 2 box = &s->boxes[box_id];
344 2 box->len = s->nb_refs;
345 2 box->sorted_by = -1;
346 2 box->color = get_avg_color(s->refs, box, s->use_alpha);
347 2 box->variance = -1;
348 2 s->nb_boxes = 1;
349
350
3/4
✓ Branch 0 taken 381 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 381 times.
✗ Branch 3 not taken.
383 while (box && box->len > 1) {
351 int i, ar, rr, gr, br, longest;
352 381 uint64_t median, box_weight = 0;
353
354 /* compute the box weight (sum all the weights of the colors in the
355 * range) and its boundings */
356 381 uint8_t min[4] = {0xff, 0xff, 0xff, 0xff};
357 381 uint8_t max[4] = {0x00, 0x00, 0x00, 0x00};
358
2/2
✓ Branch 0 taken 371416 times.
✓ Branch 1 taken 381 times.
371797 for (i = box->start; i < box->start + box->len; i++) {
359 371416 const struct color_ref *ref = s->refs[i];
360 371416 const uint32_t rgb = ref->color;
361 371416 const uint8_t a = rgb >> 24 & 0xff, r = rgb >> 16 & 0xff, g = rgb >> 8 & 0xff, b = rgb & 0xff;
362 371416 min[0] = FFMIN(a, min[0]); max[0] = FFMAX(a, max[0]);
363 371416 min[1] = FFMIN(r, min[1]); max[1] = FFMAX(r, max[1]);
364 371416 min[2] = FFMIN(g, min[2]); max[2] = FFMAX(g, max[2]);
365 371416 min[3] = FFMIN(b, min[3]); max[3] = FFMAX(b, max[3]);
366 371416 box_weight += ref->count;
367 }
368
369 /* define the axis to sort by according to the widest range of colors */
370 381 ar = max[0] - min[0];
371 381 rr = max[1] - min[1];
372 381 gr = max[2] - min[2];
373 381 br = max[3] - min[3];
374 381 longest = 2; // pick green by default (the color the eye is the most sensitive to)
375
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 381 times.
381 if (s->use_alpha) {
376 if (ar >= rr && ar >= br && ar >= gr) longest = 0;
377 if (br >= rr && br >= gr && br >= ar) longest = 3;
378 if (rr >= gr && rr >= br && rr >= ar) longest = 1;
379 if (gr >= rr && gr >= br && gr >= ar) longest = 2; // prefer green again
380 } else {
381
4/4
✓ Branch 0 taken 190 times.
✓ Branch 1 taken 191 times.
✓ Branch 2 taken 137 times.
✓ Branch 3 taken 53 times.
381 if (br >= rr && br >= gr) longest = 3;
382
4/4
✓ Branch 0 taken 217 times.
✓ Branch 1 taken 164 times.
✓ Branch 2 taken 132 times.
✓ Branch 3 taken 85 times.
381 if (rr >= gr && rr >= br) longest = 1;
383
4/4
✓ Branch 0 taken 178 times.
✓ Branch 1 taken 203 times.
✓ Branch 2 taken 133 times.
✓ Branch 3 taken 45 times.
381 if (gr >= rr && gr >= br) longest = 2; // prefer green again
384 }
385
386 ff_dlog(ctx, "box #%02X [%6d..%-6d] (%6d) w:%-6"PRIu64" ranges:[%2x %2x %2x %2x] sort by %c (already sorted:%c) ",
387 box_id, box->start, box->start + box->len - 1, box->len, box_weight,
388 ar, rr, gr, br, "argb"[longest], box->sorted_by == longest ? 'y' : 'n');
389
390 /* sort the range by its longest axis if it's not already sorted */
391
2/2
✓ Branch 0 taken 263 times.
✓ Branch 1 taken 118 times.
381 if (box->sorted_by != longest) {
392 263 cmp_func cmpf = cmp_funcs[longest];
393
44/44
✓ Branch 0 taken 59862 times.
✓ Branch 1 taken 6707 times.
✓ Branch 3 taken 10359 times.
✓ Branch 4 taken 49503 times.
✓ Branch 6 taken 799 times.
✓ Branch 7 taken 9560 times.
✓ Branch 9 taken 4985 times.
✓ Branch 10 taken 44518 times.
✓ Branch 12 taken 6667 times.
✓ Branch 13 taken 53195 times.
✓ Branch 14 taken 5928 times.
✓ Branch 15 taken 53934 times.
✓ Branch 16 taken 1355424 times.
✓ Branch 17 taken 6191 times.
✓ Branch 19 taken 651006 times.
✓ Branch 20 taken 704418 times.
✓ Branch 21 taken 1304787 times.
✓ Branch 22 taken 13369 times.
✓ Branch 24 taken 607547 times.
✓ Branch 25 taken 697240 times.
✓ Branch 26 taken 13369 times.
✓ Branch 27 taken 697240 times.
✓ Branch 28 taken 710609 times.
✓ Branch 29 taken 53934 times.
✓ Branch 30 taken 35139 times.
✓ Branch 31 taken 18795 times.
✓ Branch 32 taken 22009 times.
✓ Branch 33 taken 13130 times.
✓ Branch 34 taken 11519 times.
✓ Branch 35 taken 10490 times.
✓ Branch 36 taken 220552 times.
✓ Branch 37 taken 18740 times.
✓ Branch 39 taken 214643 times.
✓ Branch 40 taken 5909 times.
✓ Branch 41 taken 18740 times.
✓ Branch 42 taken 5909 times.
✓ Branch 43 taken 17442 times.
✓ Branch 44 taken 17752 times.
✓ Branch 46 taken 956 times.
✓ Branch 47 taken 5751 times.
✓ Branch 48 taken 66569 times.
✓ Branch 49 taken 4082 times.
✓ Branch 50 taken 35457 times.
✓ Branch 51 taken 263 times.
2308653 AV_QSORT(&s->refs[box->start], box->len, const struct color_ref *, cmpf);
394 263 box->sorted_by = longest;
395 }
396
397 /* locate the median where to split */
398 381 median = (box_weight + 1) >> 1;
399 381 box_weight = 0;
400 /* if you have 2 boxes, the maximum is actually #0: you must have at
401 * least 1 color on each side of the split, hence the -2 */
402
2/2
✓ Branch 0 taken 219739 times.
✓ Branch 1 taken 2 times.
219741 for (i = box->start; i < box->start + box->len - 2; i++) {
403 219739 box_weight += s->refs[i]->count;
404
2/2
✓ Branch 0 taken 379 times.
✓ Branch 1 taken 219360 times.
219739 if (box_weight > median)
405 379 break;
406 }
407 ff_dlog(ctx, "split @ i=%-6d with w=%-6"PRIu64" (target=%6"PRIu64")\n", i, box_weight, median);
408 381 split_box(s, box, i);
409
410 381 box_id = get_next_box_id_to_split(s);
411
2/2
✓ Branch 0 taken 379 times.
✓ Branch 1 taken 2 times.
381 box = box_id >= 0 ? &s->boxes[box_id] : NULL;
412 }
413
414 2 ratio = set_colorquant_ratio_meta(out, s->nb_boxes, s->nb_refs);
415 2 av_log(ctx, AV_LOG_INFO, "%d%s colors generated out of %d colors; ratio=%f\n",
416
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
2 s->nb_boxes, s->reserve_transparent ? "(+1)" : "", s->nb_refs, ratio);
417
418 2 qsort(s->boxes, s->nb_boxes, sizeof(*s->boxes), cmp_color);
419
420 2 write_palette(ctx, out);
421
422 2 return out;
423 }
424
425 /**
426 * Hashing function for the color.
427 * It keeps the NBITS least significant bit of each component to make it
428 * "random" even if the scene doesn't have much different colors.
429 */
430 4329458 static inline unsigned color_hash(uint32_t color, int use_alpha)
431 {
432 4329458 const uint8_t r = color >> 16 & ((1<<NBITS)-1);
433 4329458 const uint8_t g = color >> 8 & ((1<<NBITS)-1);
434 4329458 const uint8_t b = color & ((1<<NBITS)-1);
435
436
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4329458 times.
4329458 if (use_alpha) {
437 const uint8_t a = color >> 24 & ((1 << NBITS) - 1);
438 return a << (NBITS * 3) | r << (NBITS * 2) | g << NBITS | b;
439 }
440
441 4329458 return r << (NBITS * 2) | g << NBITS | b;
442 }
443
444 /**
445 * Locate the color in the hash table and increment its counter.
446 */
447 4329458 static int color_inc(struct hist_node *hist, uint32_t color, int use_alpha)
448 {
449 int i;
450 4329458 const unsigned hash = color_hash(color, use_alpha);
451 4329458 struct hist_node *node = &hist[hash];
452 struct color_ref *e;
453
454
2/2
✓ Branch 0 taken 5601985 times.
✓ Branch 1 taken 44830 times.
5646815 for (i = 0; i < node->nb_entries; i++) {
455 5601985 e = &node->entries[i];
456
2/2
✓ Branch 0 taken 4284628 times.
✓ Branch 1 taken 1317357 times.
5601985 if (e->color == color) {
457 4284628 e->count++;
458 4284628 return 0;
459 }
460 }
461
462 44830 e = av_dynarray2_add((void**)&node->entries, &node->nb_entries,
463 sizeof(*node->entries), NULL);
464
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 44830 times.
44830 if (!e)
465 return AVERROR(ENOMEM);
466 44830 e->color = color;
467 44830 e->count = 1;
468 44830 return 1;
469 }
470
471 /**
472 * Update histogram when pixels differ from previous frame.
473 */
474 70 static int update_histogram_diff(struct hist_node *hist,
475 const AVFrame *f1, const AVFrame *f2, int use_alpha)
476 {
477 70 int x, y, ret, nb_diff_colors = 0;
478
479
2/2
✓ Branch 0 taken 12600 times.
✓ Branch 1 taken 70 times.
12670 for (y = 0; y < f1->height; y++) {
480 12600 const uint32_t *p = (const uint32_t *)(f1->data[0] + y*f1->linesize[0]);
481 12600 const uint32_t *q = (const uint32_t *)(f2->data[0] + y*f2->linesize[0]);
482
483
2/2
✓ Branch 0 taken 4032000 times.
✓ Branch 1 taken 12600 times.
4044600 for (x = 0; x < f1->width; x++) {
484
2/2
✓ Branch 0 taken 3849742 times.
✓ Branch 1 taken 182258 times.
4032000 if (p[x] == q[x])
485 3849742 continue;
486 182258 ret = color_inc(hist, p[x], use_alpha);
487
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 182258 times.
182258 if (ret < 0)
488 return ret;
489 182258 nb_diff_colors += ret;
490 }
491 }
492 70 return nb_diff_colors;
493 }
494
495 /**
496 * Simple histogram of the frame.
497 */
498 72 static int update_histogram_frame(struct hist_node *hist, const AVFrame *f, int use_alpha)
499 {
500 72 int x, y, ret, nb_diff_colors = 0;
501
502
2/2
✓ Branch 0 taken 12960 times.
✓ Branch 1 taken 72 times.
13032 for (y = 0; y < f->height; y++) {
503 12960 const uint32_t *p = (const uint32_t *)(f->data[0] + y*f->linesize[0]);
504
505
2/2
✓ Branch 0 taken 4147200 times.
✓ Branch 1 taken 12960 times.
4160160 for (x = 0; x < f->width; x++) {
506 4147200 ret = color_inc(hist, p[x], use_alpha);
507
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4147200 times.
4147200 if (ret < 0)
508 return ret;
509 4147200 nb_diff_colors += ret;
510 }
511 }
512 72 return nb_diff_colors;
513 }
514
515 /**
516 * Update the histogram for each passing frame. No frame will be pushed here.
517 */
518 142 static int filter_frame(AVFilterLink *inlink, AVFrame *in)
519 {
520 142 AVFilterContext *ctx = inlink->dst;
521 142 PaletteGenContext *s = ctx->priv;
522 70 int ret = s->prev_frame ? update_histogram_diff(s->histogram, s->prev_frame, in, s->use_alpha)
523
2/2
✓ Branch 0 taken 70 times.
✓ Branch 1 taken 72 times.
142 : update_histogram_frame(s->histogram, in, s->use_alpha);
524
525
2/2
✓ Branch 0 taken 137 times.
✓ Branch 1 taken 5 times.
142 if (ret > 0)
526 137 s->nb_refs += ret;
527
528
2/2
✓ Branch 0 taken 71 times.
✓ Branch 1 taken 71 times.
142 if (s->stats_mode == STATS_MODE_DIFF_FRAMES) {
529 71 av_frame_free(&s->prev_frame);
530 71 s->prev_frame = in;
531
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 71 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
71 } else if (s->stats_mode == STATS_MODE_SINGLE_FRAMES && s->nb_refs > 0) {
532 AVFrame *out;
533 int i;
534
535 out = get_palette_frame(ctx);
536 out->pts = in->pts;
537 av_frame_free(&in);
538 ret = ff_filter_frame(ctx->outputs[0], out);
539 for (i = 0; i < HIST_SIZE; i++)
540 av_freep(&s->histogram[i].entries);
541 av_freep(&s->refs);
542 s->nb_refs = 0;
543 s->nb_boxes = 0;
544 memset(s->boxes, 0, sizeof(s->boxes));
545 memset(s->histogram, 0, sizeof(s->histogram));
546 } else {
547 71 av_frame_free(&in);
548 }
549
550 142 return ret;
551 }
552
553 /**
554 * Returns only one frame at the end containing the full palette.
555 */
556 146 static int request_frame(AVFilterLink *outlink)
557 {
558 146 AVFilterContext *ctx = outlink->src;
559 146 AVFilterLink *inlink = ctx->inputs[0];
560 146 PaletteGenContext *s = ctx->priv;
561 int r;
562
563 146 r = ff_request_frame(inlink);
564
6/8
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 142 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
146 if (r == AVERROR_EOF && !s->palette_pushed && s->nb_refs && s->stats_mode != STATS_MODE_SINGLE_FRAMES) {
565 2 r = ff_filter_frame(outlink, get_palette_frame(ctx));
566 2 s->palette_pushed = 1;
567 2 return r;
568 }
569 144 return r;
570 }
571
572 /**
573 * The output is one simple 16x16 squared-pixels palette.
574 */
575 2 static int config_output(AVFilterLink *outlink)
576 {
577 2 outlink->w = outlink->h = 16;
578 2 outlink->sample_aspect_ratio = av_make_q(1, 1);
579 2 return 0;
580 }
581
582 2 static int init(AVFilterContext *ctx)
583 {
584 2 PaletteGenContext* s = ctx->priv;
585
586
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
2 if (s->use_alpha && s->reserve_transparent)
587 s->reserve_transparent = 0;
588
589 2 return 0;
590 }
591
592 2 static av_cold void uninit(AVFilterContext *ctx)
593 {
594 int i;
595 2 PaletteGenContext *s = ctx->priv;
596
597
2/2
✓ Branch 0 taken 2097152 times.
✓ Branch 1 taken 2 times.
2097154 for (i = 0; i < HIST_SIZE; i++)
598 2097152 av_freep(&s->histogram[i].entries);
599 2 av_freep(&s->refs);
600 2 av_frame_free(&s->prev_frame);
601 2 }
602
603 static const AVFilterPad palettegen_inputs[] = {
604 {
605 .name = "default",
606 .type = AVMEDIA_TYPE_VIDEO,
607 .filter_frame = filter_frame,
608 },
609 };
610
611 static const AVFilterPad palettegen_outputs[] = {
612 {
613 .name = "default",
614 .type = AVMEDIA_TYPE_VIDEO,
615 .config_props = config_output,
616 .request_frame = request_frame,
617 },
618 };
619
620 const AVFilter ff_vf_palettegen = {
621 .name = "palettegen",
622 .description = NULL_IF_CONFIG_SMALL("Find the optimal palette for a given stream."),
623 .priv_size = sizeof(PaletteGenContext),
624 .init = init,
625 .uninit = uninit,
626 FILTER_INPUTS(palettegen_inputs),
627 FILTER_OUTPUTS(palettegen_outputs),
628 FILTER_QUERY_FUNC(query_formats),
629 .priv_class = &palettegen_class,
630 };
631