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 * Use a palette to downsample an input video stream.
24 */
25
26 #include "libavutil/bprint.h"
27 #include "libavutil/internal.h"
28 #include "libavutil/opt.h"
29 #include "libavutil/qsort.h"
30 #include "avfilter.h"
31 #include "framesync.h"
32 #include "internal.h"
33
34 enum dithering_mode {
35 DITHERING_NONE,
36 DITHERING_BAYER,
37 DITHERING_HECKBERT,
38 DITHERING_FLOYD_STEINBERG,
39 DITHERING_SIERRA2,
40 DITHERING_SIERRA2_4A,
41 NB_DITHERING
42 };
43
44 enum color_search_method {
45 COLOR_SEARCH_NNS_ITERATIVE,
46 COLOR_SEARCH_NNS_RECURSIVE,
47 COLOR_SEARCH_BRUTEFORCE,
48 NB_COLOR_SEARCHES
49 };
50
51 enum diff_mode {
52 DIFF_MODE_NONE,
53 DIFF_MODE_RECTANGLE,
54 NB_DIFF_MODE
55 };
56
57 struct color_node {
58 uint8_t val[4];
59 uint8_t palette_id;
60 int split;
61 int left_id, right_id;
62 };
63
64 #define NBITS 5
65 #define CACHE_SIZE (1<<(4*NBITS))
66
67 struct cached_color {
68 uint32_t color;
69 uint8_t pal_entry;
70 };
71
72 struct cache_node {
73 struct cached_color *entries;
74 int nb_entries;
75 };
76
77 struct PaletteUseContext;
78
79 typedef int (*set_frame_func)(struct PaletteUseContext *s, AVFrame *out, AVFrame *in,
80 int x_start, int y_start, int width, int height);
81
82 typedef struct PaletteUseContext {
83 const AVClass *class;
84 FFFrameSync fs;
85 struct cache_node cache[CACHE_SIZE]; /* lookup cache */
86 struct color_node map[AVPALETTE_COUNT]; /* 3D-Tree (KD-Tree with K=3) for reverse colormap */
87 uint32_t palette[AVPALETTE_COUNT];
88 int transparency_index; /* index in the palette of transparency. -1 if there is no transparency in the palette. */
89 int trans_thresh;
90 int use_alpha;
91 int palette_loaded;
92 int dither;
93 int new;
94 set_frame_func set_frame;
95 int bayer_scale;
96 int ordered_dither[8*8];
97 int diff_mode;
98 AVFrame *last_in;
99 AVFrame *last_out;
100
101 /* debug options */
102 char *dot_filename;
103 int color_search_method;
104 int calc_mean_err;
105 uint64_t total_mean_err;
106 int debug_accuracy;
107 } PaletteUseContext;
108
109 #define OFFSET(x) offsetof(PaletteUseContext, x)
110 #define FLAGS (AV_OPT_FLAG_FILTERING_PARAM | AV_OPT_FLAG_VIDEO_PARAM)
111 static const AVOption paletteuse_options[] = {
112 { "dither", "select dithering mode", OFFSET(dither), AV_OPT_TYPE_INT, {.i64=DITHERING_SIERRA2_4A}, 0, NB_DITHERING-1, FLAGS, "dithering_mode" },
113 { "bayer", "ordered 8x8 bayer dithering (deterministic)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_BAYER}, INT_MIN, INT_MAX, FLAGS, "dithering_mode" },
114 { "heckbert", "dithering as defined by Paul Heckbert in 1982 (simple error diffusion)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_HECKBERT}, INT_MIN, INT_MAX, FLAGS, "dithering_mode" },
115 { "floyd_steinberg", "Floyd and Steingberg dithering (error diffusion)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_FLOYD_STEINBERG}, INT_MIN, INT_MAX, FLAGS, "dithering_mode" },
116 { "sierra2", "Frankie Sierra dithering v2 (error diffusion)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_SIERRA2}, INT_MIN, INT_MAX, FLAGS, "dithering_mode" },
117 { "sierra2_4a", "Frankie Sierra dithering v2 \"Lite\" (error diffusion)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_SIERRA2_4A}, INT_MIN, INT_MAX, FLAGS, "dithering_mode" },
118 { "bayer_scale", "set scale for bayer dithering", OFFSET(bayer_scale), AV_OPT_TYPE_INT, {.i64=2}, 0, 5, FLAGS },
119 { "diff_mode", "set frame difference mode", OFFSET(diff_mode), AV_OPT_TYPE_INT, {.i64=DIFF_MODE_NONE}, 0, NB_DIFF_MODE-1, FLAGS, "diff_mode" },
120 { "rectangle", "process smallest different rectangle", 0, AV_OPT_TYPE_CONST, {.i64=DIFF_MODE_RECTANGLE}, INT_MIN, INT_MAX, FLAGS, "diff_mode" },
121 { "new", "take new palette for each output frame", OFFSET(new), AV_OPT_TYPE_BOOL, {.i64=0}, 0, 1, FLAGS },
122 { "alpha_threshold", "set the alpha threshold for transparency", OFFSET(trans_thresh), AV_OPT_TYPE_INT, {.i64=128}, 0, 255, FLAGS },
123 { "use_alpha", "use alpha channel for mapping", OFFSET(use_alpha), AV_OPT_TYPE_BOOL, {.i64=0}, 0, 1, FLAGS },
124
125 /* following are the debug options, not part of the official API */
126 { "debug_kdtree", "save Graphviz graph of the kdtree in specified file", OFFSET(dot_filename), AV_OPT_TYPE_STRING, {.str=NULL}, 0, 0, FLAGS },
127 { "color_search", "set reverse colormap color search method", OFFSET(color_search_method), AV_OPT_TYPE_INT, {.i64=COLOR_SEARCH_NNS_ITERATIVE}, 0, NB_COLOR_SEARCHES-1, FLAGS, "search" },
128 { "nns_iterative", "iterative search", 0, AV_OPT_TYPE_CONST, {.i64=COLOR_SEARCH_NNS_ITERATIVE}, INT_MIN, INT_MAX, FLAGS, "search" },
129 { "nns_recursive", "recursive search", 0, AV_OPT_TYPE_CONST, {.i64=COLOR_SEARCH_NNS_RECURSIVE}, INT_MIN, INT_MAX, FLAGS, "search" },
130 { "bruteforce", "brute-force into the palette", 0, AV_OPT_TYPE_CONST, {.i64=COLOR_SEARCH_BRUTEFORCE}, INT_MIN, INT_MAX, FLAGS, "search" },
131 { "mean_err", "compute and print mean error", OFFSET(calc_mean_err), AV_OPT_TYPE_BOOL, {.i64=0}, 0, 1, FLAGS },
132 { "debug_accuracy", "test color search accuracy", OFFSET(debug_accuracy), AV_OPT_TYPE_BOOL, {.i64=0}, 0, 1, FLAGS },
133 { NULL }
134 };
135
136 AVFILTER_DEFINE_CLASS(paletteuse);
137
138 static int load_apply_palette(FFFrameSync *fs);
139
query_formats(AVFilterContext * ctx)140 static int query_formats(AVFilterContext *ctx)
141 {
142 static const enum AVPixelFormat in_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE};
143 static const enum AVPixelFormat inpal_fmts[] = {AV_PIX_FMT_RGB32, AV_PIX_FMT_NONE};
144 static const enum AVPixelFormat out_fmts[] = {AV_PIX_FMT_PAL8, AV_PIX_FMT_NONE};
145 int ret;
146 if ((ret = ff_formats_ref(ff_make_format_list(in_fmts),
147 &ctx->inputs[0]->outcfg.formats)) < 0 ||
148 (ret = ff_formats_ref(ff_make_format_list(inpal_fmts),
149 &ctx->inputs[1]->outcfg.formats)) < 0 ||
150 (ret = ff_formats_ref(ff_make_format_list(out_fmts),
151 &ctx->outputs[0]->incfg.formats)) < 0)
152 return ret;
153 return 0;
154 }
155
dither_color(uint32_t px,int er,int eg,int eb,int scale,int shift)156 static av_always_inline uint32_t dither_color(uint32_t px, int er, int eg,
157 int eb, int scale, int shift)
158 {
159 return px >> 24 << 24
160 | av_clip_uint8((px >> 16 & 0xff) + ((er * scale) / (1<<shift))) << 16
161 | av_clip_uint8((px >> 8 & 0xff) + ((eg * scale) / (1<<shift))) << 8
162 | av_clip_uint8((px & 0xff) + ((eb * scale) / (1<<shift)));
163 }
164
diff(const uint8_t * c1,const uint8_t * c2,const PaletteUseContext * s)165 static av_always_inline int diff(const uint8_t *c1, const uint8_t *c2, const PaletteUseContext *s)
166 {
167 // XXX: try L*a*b with CIE76 (dL*dL + da*da + db*db)
168 const int da = c1[0] - c2[0];
169 const int dr = c1[1] - c2[1];
170 const int dg = c1[2] - c2[2];
171 const int db = c1[3] - c2[3];
172
173 if (s->use_alpha)
174 return da*da + dr*dr + dg*dg + db*db;
175
176 if (c1[0] < s->trans_thresh && c2[0] < s->trans_thresh) {
177 return 0;
178 } else if (c1[0] >= s->trans_thresh && c2[0] >= s->trans_thresh) {
179 return dr*dr + dg*dg + db*db;
180 } else {
181 return 255*255 + 255*255 + 255*255;
182 }
183 }
184
colormap_nearest_bruteforce(const PaletteUseContext * s,const uint8_t * argb)185 static av_always_inline uint8_t colormap_nearest_bruteforce(const PaletteUseContext *s, const uint8_t *argb)
186 {
187 int i, pal_id = -1, min_dist = INT_MAX;
188
189 for (i = 0; i < AVPALETTE_COUNT; i++) {
190 const uint32_t c = s->palette[i];
191
192 if (s->use_alpha || c >> 24 >= s->trans_thresh) { // ignore transparent entry
193 const uint8_t palargb[] = {
194 s->palette[i]>>24 & 0xff,
195 s->palette[i]>>16 & 0xff,
196 s->palette[i]>> 8 & 0xff,
197 s->palette[i] & 0xff,
198 };
199 const int d = diff(palargb, argb, s);
200 if (d < min_dist) {
201 pal_id = i;
202 min_dist = d;
203 }
204 }
205 }
206 return pal_id;
207 }
208
209 /* Recursive form, simpler but a bit slower. Kept for reference. */
210 struct nearest_color {
211 int node_pos;
212 int dist_sqd;
213 };
214
colormap_nearest_node(const PaletteUseContext * s,const struct color_node * map,const int node_pos,const uint8_t * target,struct nearest_color * nearest)215 static void colormap_nearest_node(const PaletteUseContext *s,
216 const struct color_node *map,
217 const int node_pos,
218 const uint8_t *target,
219 struct nearest_color *nearest)
220 {
221 const struct color_node *kd = map + node_pos;
222 const int split = kd->split;
223 int dx, nearer_kd_id, further_kd_id;
224 const uint8_t *current = kd->val;
225 const int current_to_target = diff(target, current, s);
226
227 if (current_to_target < nearest->dist_sqd) {
228 nearest->node_pos = node_pos;
229 nearest->dist_sqd = current_to_target;
230 }
231
232 if (kd->left_id != -1 || kd->right_id != -1) {
233 dx = target[split] - current[split];
234
235 if (dx <= 0) nearer_kd_id = kd->left_id, further_kd_id = kd->right_id;
236 else nearer_kd_id = kd->right_id, further_kd_id = kd->left_id;
237
238 if (nearer_kd_id != -1)
239 colormap_nearest_node(s, map, nearer_kd_id, target, nearest);
240
241 if (further_kd_id != -1 && dx*dx < nearest->dist_sqd)
242 colormap_nearest_node(s, map, further_kd_id, target, nearest);
243 }
244 }
245
colormap_nearest_recursive(const PaletteUseContext * s,const struct color_node * node,const uint8_t * rgb)246 static av_always_inline uint8_t colormap_nearest_recursive(const PaletteUseContext *s, const struct color_node *node, const uint8_t *rgb)
247 {
248 struct nearest_color res = {.dist_sqd = INT_MAX, .node_pos = -1};
249 colormap_nearest_node(s, node, 0, rgb, &res);
250 return node[res.node_pos].palette_id;
251 }
252
253 struct stack_node {
254 int color_id;
255 int dx2;
256 };
257
colormap_nearest_iterative(const PaletteUseContext * s,const struct color_node * root,const uint8_t * target)258 static av_always_inline uint8_t colormap_nearest_iterative(const PaletteUseContext *s, const struct color_node *root, const uint8_t *target)
259 {
260 int pos = 0, best_node_id = -1, best_dist = INT_MAX, cur_color_id = 0;
261 struct stack_node nodes[16];
262 struct stack_node *node = &nodes[0];
263
264 for (;;) {
265
266 const struct color_node *kd = &root[cur_color_id];
267 const uint8_t *current = kd->val;
268 const int current_to_target = diff(target, current, s);
269
270 /* Compare current color node to the target and update our best node if
271 * it's actually better. */
272 if (current_to_target < best_dist) {
273 best_node_id = cur_color_id;
274 if (!current_to_target)
275 goto end; // exact match, we can return immediately
276 best_dist = current_to_target;
277 }
278
279 /* Check if it's not a leaf */
280 if (kd->left_id != -1 || kd->right_id != -1) {
281 const int split = kd->split;
282 const int dx = target[split] - current[split];
283 int nearer_kd_id, further_kd_id;
284
285 /* Define which side is the most interesting. */
286 if (dx <= 0) nearer_kd_id = kd->left_id, further_kd_id = kd->right_id;
287 else nearer_kd_id = kd->right_id, further_kd_id = kd->left_id;
288
289 if (nearer_kd_id != -1) {
290 if (further_kd_id != -1) {
291 /* Here, both paths are defined, so we push a state for
292 * when we are going back. */
293 node->color_id = further_kd_id;
294 node->dx2 = dx*dx;
295 pos++;
296 node++;
297 }
298 /* We can now update current color with the most probable path
299 * (no need to create a state since there is nothing to save
300 * anymore). */
301 cur_color_id = nearer_kd_id;
302 continue;
303 } else if (dx*dx < best_dist) {
304 /* The nearest path isn't available, so there is only one path
305 * possible and it's the least probable. We enter it only if the
306 * distance from the current point to the hyper rectangle is
307 * less than our best distance. */
308 cur_color_id = further_kd_id;
309 continue;
310 }
311 }
312
313 /* Unstack as much as we can, typically as long as the least probable
314 * branch aren't actually probable. */
315 do {
316 if (--pos < 0)
317 goto end;
318 node--;
319 } while (node->dx2 >= best_dist);
320
321 /* We got a node where the least probable branch might actually contain
322 * a relevant color. */
323 cur_color_id = node->color_id;
324 }
325
326 end:
327 return root[best_node_id].palette_id;
328 }
329
330 #define COLORMAP_NEAREST(s, search, root, target) \
331 search == COLOR_SEARCH_NNS_ITERATIVE ? colormap_nearest_iterative(s, root, target) : \
332 search == COLOR_SEARCH_NNS_RECURSIVE ? colormap_nearest_recursive(s, root, target) : \
333 colormap_nearest_bruteforce(s, target)
334
335 /**
336 * Check if the requested color is in the cache already. If not, find it in the
337 * color tree and cache it.
338 * Note: a, r, g, and b are the components of color, but are passed as well to avoid
339 * recomputing them (they are generally computed by the caller for other uses).
340 */
color_get(PaletteUseContext * s,uint32_t color,uint8_t a,uint8_t r,uint8_t g,uint8_t b,const enum color_search_method search_method)341 static av_always_inline int color_get(PaletteUseContext *s, uint32_t color,
342 uint8_t a, uint8_t r, uint8_t g, uint8_t b,
343 const enum color_search_method search_method)
344 {
345 int i;
346 const uint8_t argb_elts[] = {a, r, g, b};
347 const uint8_t rhash = r & ((1<<NBITS)-1);
348 const uint8_t ghash = g & ((1<<NBITS)-1);
349 const uint8_t bhash = b & ((1<<NBITS)-1);
350 const unsigned hash = rhash<<(NBITS*2) | ghash<<NBITS | bhash;
351 struct cache_node *node = &s->cache[hash];
352 struct cached_color *e;
353
354 // first, check for transparency
355 if (a < s->trans_thresh && s->transparency_index >= 0) {
356 return s->transparency_index;
357 }
358
359 for (i = 0; i < node->nb_entries; i++) {
360 e = &node->entries[i];
361 if (e->color == color)
362 return e->pal_entry;
363 }
364
365 e = av_dynarray2_add((void**)&node->entries, &node->nb_entries,
366 sizeof(*node->entries), NULL);
367 if (!e)
368 return AVERROR(ENOMEM);
369 e->color = color;
370 e->pal_entry = COLORMAP_NEAREST(s, search_method, s->map, argb_elts);
371
372 return e->pal_entry;
373 }
374
get_dst_color_err(PaletteUseContext * s,uint32_t c,int * ea,int * er,int * eg,int * eb,const enum color_search_method search_method)375 static av_always_inline int get_dst_color_err(PaletteUseContext *s,
376 uint32_t c, int *ea, int *er, int *eg, int *eb,
377 const enum color_search_method search_method)
378 {
379 const uint8_t a = c >> 24 & 0xff;
380 const uint8_t r = c >> 16 & 0xff;
381 const uint8_t g = c >> 8 & 0xff;
382 const uint8_t b = c & 0xff;
383 uint32_t dstc;
384 const int dstx = color_get(s, c, a, r, g, b, search_method);
385 if (dstx < 0)
386 return dstx;
387 dstc = s->palette[dstx];
388 if (dstx == s->transparency_index) {
389 *ea =*er = *eg = *eb = 0;
390 } else {
391 *ea = (int)a - (int)(dstc >> 24 & 0xff);
392 *er = (int)r - (int)(dstc >> 16 & 0xff);
393 *eg = (int)g - (int)(dstc >> 8 & 0xff);
394 *eb = (int)b - (int)(dstc & 0xff);
395 }
396 return dstx;
397 }
398
set_frame(PaletteUseContext * s,AVFrame * out,AVFrame * in,int x_start,int y_start,int w,int h,enum dithering_mode dither,const enum color_search_method search_method)399 static av_always_inline int set_frame(PaletteUseContext *s, AVFrame *out, AVFrame *in,
400 int x_start, int y_start, int w, int h,
401 enum dithering_mode dither,
402 const enum color_search_method search_method)
403 {
404 int x, y;
405 const int src_linesize = in ->linesize[0] >> 2;
406 const int dst_linesize = out->linesize[0];
407 uint32_t *src = ((uint32_t *)in ->data[0]) + y_start*src_linesize;
408 uint8_t *dst = out->data[0] + y_start*dst_linesize;
409
410 w += x_start;
411 h += y_start;
412
413 for (y = y_start; y < h; y++) {
414 for (x = x_start; x < w; x++) {
415 int ea, er, eg, eb;
416
417 if (dither == DITHERING_BAYER) {
418 const int d = s->ordered_dither[(y & 7)<<3 | (x & 7)];
419 const uint8_t a8 = src[x] >> 24 & 0xff;
420 const uint8_t r8 = src[x] >> 16 & 0xff;
421 const uint8_t g8 = src[x] >> 8 & 0xff;
422 const uint8_t b8 = src[x] & 0xff;
423 const uint8_t r = av_clip_uint8(r8 + d);
424 const uint8_t g = av_clip_uint8(g8 + d);
425 const uint8_t b = av_clip_uint8(b8 + d);
426 const uint32_t color_new = (unsigned)(a8) << 24 | r << 16 | g << 8 | b;
427 const int color = color_get(s, color_new, a8, r, g, b, search_method);
428
429 if (color < 0)
430 return color;
431 dst[x] = color;
432
433 } else if (dither == DITHERING_HECKBERT) {
434 const int right = x < w - 1, down = y < h - 1;
435 const int color = get_dst_color_err(s, src[x], &ea, &er, &eg, &eb, search_method);
436
437 if (color < 0)
438 return color;
439 dst[x] = color;
440
441 if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 3, 3);
442 if ( down) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 3, 3);
443 if (right && down) src[src_linesize + x + 1] = dither_color(src[src_linesize + x + 1], er, eg, eb, 2, 3);
444
445 } else if (dither == DITHERING_FLOYD_STEINBERG) {
446 const int right = x < w - 1, down = y < h - 1, left = x > x_start;
447 const int color = get_dst_color_err(s, src[x], &ea, &er, &eg, &eb, search_method);
448
449 if (color < 0)
450 return color;
451 dst[x] = color;
452
453 if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 7, 4);
454 if (left && down) src[src_linesize + x - 1] = dither_color(src[src_linesize + x - 1], er, eg, eb, 3, 4);
455 if ( down) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 5, 4);
456 if (right && down) src[src_linesize + x + 1] = dither_color(src[src_linesize + x + 1], er, eg, eb, 1, 4);
457
458 } else if (dither == DITHERING_SIERRA2) {
459 const int right = x < w - 1, down = y < h - 1, left = x > x_start;
460 const int right2 = x < w - 2, left2 = x > x_start + 1;
461 const int color = get_dst_color_err(s, src[x], &ea, &er, &eg, &eb, search_method);
462
463 if (color < 0)
464 return color;
465 dst[x] = color;
466
467 if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 4, 4);
468 if (right2) src[ x + 2] = dither_color(src[ x + 2], er, eg, eb, 3, 4);
469
470 if (down) {
471 if (left2) src[ src_linesize + x - 2] = dither_color(src[ src_linesize + x - 2], er, eg, eb, 1, 4);
472 if (left) src[ src_linesize + x - 1] = dither_color(src[ src_linesize + x - 1], er, eg, eb, 2, 4);
473 if (1) src[ src_linesize + x ] = dither_color(src[ src_linesize + x ], er, eg, eb, 3, 4);
474 if (right) src[ src_linesize + x + 1] = dither_color(src[ src_linesize + x + 1], er, eg, eb, 2, 4);
475 if (right2) src[ src_linesize + x + 2] = dither_color(src[ src_linesize + x + 2], er, eg, eb, 1, 4);
476 }
477
478 } else if (dither == DITHERING_SIERRA2_4A) {
479 const int right = x < w - 1, down = y < h - 1, left = x > x_start;
480 const int color = get_dst_color_err(s, src[x], &ea, &er, &eg, &eb, search_method);
481
482 if (color < 0)
483 return color;
484 dst[x] = color;
485
486 if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 2, 2);
487 if (left && down) src[src_linesize + x - 1] = dither_color(src[src_linesize + x - 1], er, eg, eb, 1, 2);
488 if ( down) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 1, 2);
489
490 } else {
491 const uint8_t a = src[x] >> 24 & 0xff;
492 const uint8_t r = src[x] >> 16 & 0xff;
493 const uint8_t g = src[x] >> 8 & 0xff;
494 const uint8_t b = src[x] & 0xff;
495 const int color = color_get(s, src[x], a, r, g, b, search_method);
496
497 if (color < 0)
498 return color;
499 dst[x] = color;
500 }
501 }
502 src += src_linesize;
503 dst += dst_linesize;
504 }
505 return 0;
506 }
507
508 #define INDENT 4
disp_node(AVBPrint * buf,const struct color_node * map,int parent_id,int node_id,int depth)509 static void disp_node(AVBPrint *buf,
510 const struct color_node *map,
511 int parent_id, int node_id,
512 int depth)
513 {
514 const struct color_node *node = &map[node_id];
515 const uint32_t fontcolor = node->val[1] > 0x50 &&
516 node->val[2] > 0x50 &&
517 node->val[3] > 0x50 ? 0 : 0xffffff;
518 const int rgb_comp = node->split - 1;
519 av_bprintf(buf, "%*cnode%d ["
520 "label=\"%c%02X%c%02X%c%02X%c\" "
521 "fillcolor=\"#%02x%02x%02x\" "
522 "fontcolor=\"#%06"PRIX32"\"]\n",
523 depth*INDENT, ' ', node->palette_id,
524 "[ "[rgb_comp], node->val[1],
525 "][ "[rgb_comp], node->val[2],
526 " ]["[rgb_comp], node->val[3],
527 " ]"[rgb_comp],
528 node->val[1], node->val[2], node->val[3],
529 fontcolor);
530 if (parent_id != -1)
531 av_bprintf(buf, "%*cnode%d -> node%d\n", depth*INDENT, ' ',
532 map[parent_id].palette_id, node->palette_id);
533 if (node->left_id != -1) disp_node(buf, map, node_id, node->left_id, depth + 1);
534 if (node->right_id != -1) disp_node(buf, map, node_id, node->right_id, depth + 1);
535 }
536
537 // debug_kdtree=kdtree.dot -> dot -Tpng kdtree.dot > kdtree.png
disp_tree(const struct color_node * node,const char * fname)538 static int disp_tree(const struct color_node *node, const char *fname)
539 {
540 AVBPrint buf;
541 FILE *f = avpriv_fopen_utf8(fname, "w");
542
543 if (!f) {
544 int ret = AVERROR(errno);
545 av_log(NULL, AV_LOG_ERROR, "Cannot open file '%s' for writing: %s\n",
546 fname, av_err2str(ret));
547 return ret;
548 }
549
550 av_bprint_init(&buf, 0, AV_BPRINT_SIZE_UNLIMITED);
551
552 av_bprintf(&buf, "digraph {\n");
553 av_bprintf(&buf, " node [style=filled fontsize=10 shape=box]\n");
554 disp_node(&buf, node, -1, 0, 0);
555 av_bprintf(&buf, "}\n");
556
557 fwrite(buf.str, 1, buf.len, f);
558 fclose(f);
559 av_bprint_finalize(&buf, NULL);
560 return 0;
561 }
562
debug_accuracy(const PaletteUseContext * s)563 static int debug_accuracy(const PaletteUseContext *s)
564 {
565 int r, g, b, ret = 0;
566
567 for (r = 0; r < 256; r++) {
568 for (g = 0; g < 256; g++) {
569 for (b = 0; b < 256; b++) {
570 const uint8_t argb[] = {0xff, r, g, b};
571 const int r1 = COLORMAP_NEAREST(s, s->color_search_method, s->map, argb);
572 const int r2 = colormap_nearest_bruteforce(s, argb);
573 if (r1 != r2) {
574 const uint32_t c1 = s->palette[r1];
575 const uint32_t c2 = s->palette[r2];
576 const uint8_t a1 = s->use_alpha ? c1>>24 & 0xff : 0xff;
577 const uint8_t a2 = s->use_alpha ? c2>>24 & 0xff : 0xff;
578 const uint8_t palargb1[] = { a1, c1>>16 & 0xff, c1>> 8 & 0xff, c1 & 0xff };
579 const uint8_t palargb2[] = { a2, c2>>16 & 0xff, c2>> 8 & 0xff, c2 & 0xff };
580 const int d1 = diff(palargb1, argb, s);
581 const int d2 = diff(palargb2, argb, s);
582 if (d1 != d2) {
583 if (s->use_alpha)
584 av_log(NULL, AV_LOG_ERROR,
585 "/!\\ %02X%02X%02X: %d ! %d (%08"PRIX32" ! %08"PRIX32") / dist: %d ! %d\n",
586 r, g, b, r1, r2, c1, c2, d1, d2);
587 else
588 av_log(NULL, AV_LOG_ERROR,
589 "/!\\ %02X%02X%02X: %d ! %d (%06"PRIX32" ! %06"PRIX32") / dist: %d ! %d\n",
590 r, g, b, r1, r2, c1 & 0xffffff, c2 & 0xffffff, d1, d2);
591 ret = 1;
592 }
593 }
594 }
595 }
596 }
597 return ret;
598 }
599
600 struct color {
601 uint32_t value;
602 uint8_t pal_id;
603 };
604
605 struct color_rect {
606 uint8_t min[4];
607 uint8_t max[4];
608 };
609
610 typedef int (*cmp_func)(const void *, const void *);
611
612 #define DECLARE_CMP_FUNC(name, pos) \
613 static int cmp_##name(const void *pa, const void *pb) \
614 { \
615 const struct color *a = pa; \
616 const struct color *b = pb; \
617 return (int)(a->value >> (8 * (3 - (pos))) & 0xff) \
618 - (int)(b->value >> (8 * (3 - (pos))) & 0xff); \
619 }
620
621 DECLARE_CMP_FUNC(a, 0)
622 DECLARE_CMP_FUNC(r, 1)
623 DECLARE_CMP_FUNC(g, 2)
624 DECLARE_CMP_FUNC(b, 3)
625
626 static const cmp_func cmp_funcs[] = {cmp_a, cmp_r, cmp_g, cmp_b};
627
get_next_color(const uint8_t * color_used,const PaletteUseContext * s,int * component,const struct color_rect * box)628 static int get_next_color(const uint8_t *color_used, const PaletteUseContext *s,
629 int *component, const struct color_rect *box)
630 {
631 int wa, wr, wg, wb;
632 int i, longest = 0;
633 unsigned nb_color = 0;
634 struct color_rect ranges;
635 struct color tmp_pal[256];
636 cmp_func cmpf;
637
638 ranges.min[0] = ranges.min[1] = ranges.min[2] = ranges.min[3]= 0xff;
639 ranges.max[0] = ranges.max[1] = ranges.max[2] = ranges.max[3]= 0x00;
640
641 for (i = 0; i < AVPALETTE_COUNT; i++) {
642 const uint32_t c = s->palette[i];
643 const uint8_t a = c >> 24 & 0xff;
644 const uint8_t r = c >> 16 & 0xff;
645 const uint8_t g = c >> 8 & 0xff;
646 const uint8_t b = c & 0xff;
647
648 if (!s->use_alpha && a < s->trans_thresh) {
649 continue;
650 }
651
652 if (color_used[i] || (a != 0xff && !s->use_alpha) ||
653 r < box->min[1] || g < box->min[2] || b < box->min[3] ||
654 r > box->max[1] || g > box->max[2] || b > box->max[3])
655 continue;
656
657 if (s->use_alpha && (a < box->min[0] || a > box->max[0]))
658 continue;
659
660 if (a < ranges.min[0]) ranges.min[0] = a;
661 if (r < ranges.min[1]) ranges.min[1] = r;
662 if (g < ranges.min[2]) ranges.min[2] = g;
663 if (b < ranges.min[3]) ranges.min[3] = b;
664
665 if (a > ranges.max[0]) ranges.max[0] = a;
666 if (r > ranges.max[1]) ranges.max[1] = r;
667 if (g > ranges.max[2]) ranges.max[2] = g;
668 if (b > ranges.max[3]) ranges.max[3] = b;
669
670 tmp_pal[nb_color].value = c;
671 tmp_pal[nb_color].pal_id = i;
672
673 nb_color++;
674 }
675
676 if (!nb_color)
677 return -1;
678
679 /* define longest axis that will be the split component */
680 wa = ranges.max[0] - ranges.min[0];
681 wr = ranges.max[1] - ranges.min[1];
682 wg = ranges.max[2] - ranges.min[2];
683 wb = ranges.max[3] - ranges.min[3];
684
685 if (s->use_alpha) {
686 if (wa >= wr && wa >= wb && wa >= wg) longest = 0;
687 if (wr >= wg && wr >= wb && wr >= wa) longest = 1;
688 if (wg >= wr && wg >= wb && wg >= wa) longest = 2;
689 if (wb >= wr && wb >= wg && wb >= wa) longest = 3;
690 } else {
691 if (wr >= wg && wr >= wb) longest = 1;
692 if (wg >= wr && wg >= wb) longest = 2;
693 if (wb >= wr && wb >= wg) longest = 3;
694 }
695
696 cmpf = cmp_funcs[longest];
697 *component = longest;
698
699 /* sort along this axis to get median */
700 AV_QSORT(tmp_pal, nb_color, struct color, cmpf);
701
702 return tmp_pal[nb_color >> 1].pal_id;
703 }
704
colormap_insert(struct color_node * map,uint8_t * color_used,int * nb_used,const PaletteUseContext * s,const struct color_rect * box)705 static int colormap_insert(struct color_node *map,
706 uint8_t *color_used,
707 int *nb_used,
708 const PaletteUseContext *s,
709 const struct color_rect *box)
710 {
711 uint32_t c;
712 int component, cur_id;
713 int node_left_id = -1, node_right_id = -1;
714 struct color_node *node;
715 struct color_rect box1, box2;
716 const int pal_id = get_next_color(color_used, s, &component, box);
717
718 if (pal_id < 0)
719 return -1;
720
721 /* create new node with that color */
722 cur_id = (*nb_used)++;
723 c = s->palette[pal_id];
724 node = &map[cur_id];
725 node->split = component;
726 node->palette_id = pal_id;
727 node->val[0] = c>>24 & 0xff;
728 node->val[1] = c>>16 & 0xff;
729 node->val[2] = c>> 8 & 0xff;
730 node->val[3] = c & 0xff;
731
732 color_used[pal_id] = 1;
733
734 /* get the two boxes this node creates */
735 box1 = box2 = *box;
736 box1.max[component] = node->val[component];
737 box2.min[component] = FFMIN(node->val[component] + 1, 255);
738
739 node_left_id = colormap_insert(map, color_used, nb_used, s, &box1);
740
741 if (box2.min[component] <= box2.max[component])
742 node_right_id = colormap_insert(map, color_used, nb_used, s, &box2);
743
744 node->left_id = node_left_id;
745 node->right_id = node_right_id;
746
747 return cur_id;
748 }
749
cmp_pal_entry(const void * a,const void * b)750 static int cmp_pal_entry(const void *a, const void *b)
751 {
752 const int c1 = *(const uint32_t *)a & 0xffffff;
753 const int c2 = *(const uint32_t *)b & 0xffffff;
754 return c1 - c2;
755 }
756
cmp_pal_entry_alpha(const void * a,const void * b)757 static int cmp_pal_entry_alpha(const void *a, const void *b)
758 {
759 const int c1 = *(const uint32_t *)a;
760 const int c2 = *(const uint32_t *)b;
761 return c1 - c2;
762 }
763
load_colormap(PaletteUseContext * s)764 static void load_colormap(PaletteUseContext *s)
765 {
766 int i, nb_used = 0;
767 uint8_t color_used[AVPALETTE_COUNT] = {0};
768 uint32_t last_color = 0;
769 struct color_rect box;
770
771 if (!s->use_alpha && s->transparency_index >= 0) {
772 FFSWAP(uint32_t, s->palette[s->transparency_index], s->palette[255]);
773 }
774
775 /* disable transparent colors and dups */
776 qsort(s->palette, AVPALETTE_COUNT-(s->transparency_index >= 0), sizeof(*s->palette),
777 s->use_alpha ? cmp_pal_entry_alpha : cmp_pal_entry);
778
779 for (i = 0; i < AVPALETTE_COUNT; i++) {
780 const uint32_t c = s->palette[i];
781 if (i != 0 && c == last_color) {
782 color_used[i] = 1;
783 continue;
784 }
785 last_color = c;
786 if (!s->use_alpha && c >> 24 < s->trans_thresh) {
787 color_used[i] = 1; // ignore transparent color(s)
788 continue;
789 }
790 }
791
792 box.min[0] = box.min[1] = box.min[2] = box.min[3] = 0x00;
793 box.max[0] = box.max[1] = box.max[2] = box.max[3] = 0xff;
794
795 colormap_insert(s->map, color_used, &nb_used, s, &box);
796
797 if (s->dot_filename)
798 disp_tree(s->map, s->dot_filename);
799
800 if (s->debug_accuracy) {
801 if (!debug_accuracy(s))
802 av_log(NULL, AV_LOG_INFO, "Accuracy check passed\n");
803 }
804 }
805
debug_mean_error(PaletteUseContext * s,const AVFrame * in1,const AVFrame * in2,int frame_count)806 static void debug_mean_error(PaletteUseContext *s, const AVFrame *in1,
807 const AVFrame *in2, int frame_count)
808 {
809 int x, y;
810 const uint32_t *palette = s->palette;
811 uint32_t *src1 = (uint32_t *)in1->data[0];
812 uint8_t *src2 = in2->data[0];
813 const int src1_linesize = in1->linesize[0] >> 2;
814 const int src2_linesize = in2->linesize[0];
815 const float div = in1->width * in1->height * (s->use_alpha ? 4 : 3);
816 unsigned mean_err = 0;
817
818 for (y = 0; y < in1->height; y++) {
819 for (x = 0; x < in1->width; x++) {
820 const uint32_t c1 = src1[x];
821 const uint32_t c2 = palette[src2[x]];
822 const uint8_t a1 = s->use_alpha ? c1>>24 & 0xff : 0xff;
823 const uint8_t a2 = s->use_alpha ? c2>>24 & 0xff : 0xff;
824 const uint8_t argb1[] = {a1, c1 >> 16 & 0xff, c1 >> 8 & 0xff, c1 & 0xff};
825 const uint8_t argb2[] = {a2, c2 >> 16 & 0xff, c2 >> 8 & 0xff, c2 & 0xff};
826 mean_err += diff(argb1, argb2, s);
827 }
828 src1 += src1_linesize;
829 src2 += src2_linesize;
830 }
831
832 s->total_mean_err += mean_err;
833
834 av_log(NULL, AV_LOG_INFO, "MEP:%.3f TotalMEP:%.3f\n",
835 mean_err / div, s->total_mean_err / (div * frame_count));
836 }
837
set_processing_window(enum diff_mode diff_mode,const AVFrame * prv_src,const AVFrame * cur_src,const AVFrame * prv_dst,AVFrame * cur_dst,int * xp,int * yp,int * wp,int * hp)838 static void set_processing_window(enum diff_mode diff_mode,
839 const AVFrame *prv_src, const AVFrame *cur_src,
840 const AVFrame *prv_dst, AVFrame *cur_dst,
841 int *xp, int *yp, int *wp, int *hp)
842 {
843 int x_start = 0, y_start = 0;
844 int width = cur_src->width;
845 int height = cur_src->height;
846
847 if (prv_src->data[0] && diff_mode == DIFF_MODE_RECTANGLE) {
848 int y;
849 int x_end = cur_src->width - 1,
850 y_end = cur_src->height - 1;
851 const uint32_t *prv_srcp = (const uint32_t *)prv_src->data[0];
852 const uint32_t *cur_srcp = (const uint32_t *)cur_src->data[0];
853 const uint8_t *prv_dstp = prv_dst->data[0];
854 uint8_t *cur_dstp = cur_dst->data[0];
855
856 const int prv_src_linesize = prv_src->linesize[0] >> 2;
857 const int cur_src_linesize = cur_src->linesize[0] >> 2;
858 const int prv_dst_linesize = prv_dst->linesize[0];
859 const int cur_dst_linesize = cur_dst->linesize[0];
860
861 /* skip common lines */
862 while (y_start < y_end && !memcmp(prv_srcp + y_start*prv_src_linesize,
863 cur_srcp + y_start*cur_src_linesize,
864 cur_src->width * 4)) {
865 memcpy(cur_dstp + y_start*cur_dst_linesize,
866 prv_dstp + y_start*prv_dst_linesize,
867 cur_dst->width);
868 y_start++;
869 }
870 while (y_end > y_start && !memcmp(prv_srcp + y_end*prv_src_linesize,
871 cur_srcp + y_end*cur_src_linesize,
872 cur_src->width * 4)) {
873 memcpy(cur_dstp + y_end*cur_dst_linesize,
874 prv_dstp + y_end*prv_dst_linesize,
875 cur_dst->width);
876 y_end--;
877 }
878
879 height = y_end + 1 - y_start;
880
881 /* skip common columns */
882 while (x_start < x_end) {
883 int same_column = 1;
884 for (y = y_start; y <= y_end; y++) {
885 if (prv_srcp[y*prv_src_linesize + x_start] != cur_srcp[y*cur_src_linesize + x_start]) {
886 same_column = 0;
887 break;
888 }
889 }
890 if (!same_column)
891 break;
892 x_start++;
893 }
894 while (x_end > x_start) {
895 int same_column = 1;
896 for (y = y_start; y <= y_end; y++) {
897 if (prv_srcp[y*prv_src_linesize + x_end] != cur_srcp[y*cur_src_linesize + x_end]) {
898 same_column = 0;
899 break;
900 }
901 }
902 if (!same_column)
903 break;
904 x_end--;
905 }
906 width = x_end + 1 - x_start;
907
908 if (x_start) {
909 for (y = y_start; y <= y_end; y++)
910 memcpy(cur_dstp + y*cur_dst_linesize,
911 prv_dstp + y*prv_dst_linesize, x_start);
912 }
913 if (x_end != cur_src->width - 1) {
914 const int copy_len = cur_src->width - 1 - x_end;
915 for (y = y_start; y <= y_end; y++)
916 memcpy(cur_dstp + y*cur_dst_linesize + x_end + 1,
917 prv_dstp + y*prv_dst_linesize + x_end + 1,
918 copy_len);
919 }
920 }
921 *xp = x_start;
922 *yp = y_start;
923 *wp = width;
924 *hp = height;
925 }
926
apply_palette(AVFilterLink * inlink,AVFrame * in,AVFrame ** outf)927 static int apply_palette(AVFilterLink *inlink, AVFrame *in, AVFrame **outf)
928 {
929 int x, y, w, h, ret;
930 AVFilterContext *ctx = inlink->dst;
931 PaletteUseContext *s = ctx->priv;
932 AVFilterLink *outlink = inlink->dst->outputs[0];
933
934 AVFrame *out = ff_get_video_buffer(outlink, outlink->w, outlink->h);
935 if (!out) {
936 *outf = NULL;
937 return AVERROR(ENOMEM);
938 }
939 av_frame_copy_props(out, in);
940
941 set_processing_window(s->diff_mode, s->last_in, in,
942 s->last_out, out, &x, &y, &w, &h);
943 av_frame_unref(s->last_in);
944 av_frame_unref(s->last_out);
945 if ((ret = av_frame_ref(s->last_in, in)) < 0 ||
946 (ret = av_frame_ref(s->last_out, out)) < 0 ||
947 (ret = av_frame_make_writable(s->last_in)) < 0) {
948 av_frame_free(&out);
949 *outf = NULL;
950 return ret;
951 }
952
953 ff_dlog(ctx, "%dx%d rect: (%d;%d) -> (%d,%d) [area:%dx%d]\n",
954 w, h, x, y, x+w, y+h, in->width, in->height);
955
956 ret = s->set_frame(s, out, in, x, y, w, h);
957 if (ret < 0) {
958 av_frame_free(&out);
959 *outf = NULL;
960 return ret;
961 }
962 memcpy(out->data[1], s->palette, AVPALETTE_SIZE);
963 if (s->calc_mean_err)
964 debug_mean_error(s, in, out, inlink->frame_count_out);
965 *outf = out;
966 return 0;
967 }
968
config_output(AVFilterLink * outlink)969 static int config_output(AVFilterLink *outlink)
970 {
971 int ret;
972 AVFilterContext *ctx = outlink->src;
973 PaletteUseContext *s = ctx->priv;
974
975 ret = ff_framesync_init_dualinput(&s->fs, ctx);
976 if (ret < 0)
977 return ret;
978 s->fs.opt_repeatlast = 1; // only 1 frame in the palette
979 s->fs.in[1].before = s->fs.in[1].after = EXT_INFINITY;
980 s->fs.on_event = load_apply_palette;
981
982 outlink->w = ctx->inputs[0]->w;
983 outlink->h = ctx->inputs[0]->h;
984
985 outlink->time_base = ctx->inputs[0]->time_base;
986 if ((ret = ff_framesync_configure(&s->fs)) < 0)
987 return ret;
988 return 0;
989 }
990
config_input_palette(AVFilterLink * inlink)991 static int config_input_palette(AVFilterLink *inlink)
992 {
993 AVFilterContext *ctx = inlink->dst;
994
995 if (inlink->w * inlink->h != AVPALETTE_COUNT) {
996 av_log(ctx, AV_LOG_ERROR,
997 "Palette input must contain exactly %d pixels. "
998 "Specified input has %dx%d=%d pixels\n",
999 AVPALETTE_COUNT, inlink->w, inlink->h,
1000 inlink->w * inlink->h);
1001 return AVERROR(EINVAL);
1002 }
1003 return 0;
1004 }
1005
load_palette(PaletteUseContext * s,const AVFrame * palette_frame)1006 static void load_palette(PaletteUseContext *s, const AVFrame *palette_frame)
1007 {
1008 int i, x, y;
1009 const uint32_t *p = (const uint32_t *)palette_frame->data[0];
1010 const int p_linesize = palette_frame->linesize[0] >> 2;
1011
1012 s->transparency_index = -1;
1013
1014 if (s->new) {
1015 memset(s->palette, 0, sizeof(s->palette));
1016 memset(s->map, 0, sizeof(s->map));
1017 for (i = 0; i < CACHE_SIZE; i++)
1018 av_freep(&s->cache[i].entries);
1019 memset(s->cache, 0, sizeof(s->cache));
1020 }
1021
1022 i = 0;
1023 for (y = 0; y < palette_frame->height; y++) {
1024 for (x = 0; x < palette_frame->width; x++) {
1025 s->palette[i] = p[x];
1026 if (!s->use_alpha && p[x]>>24 < s->trans_thresh) {
1027 s->transparency_index = i; // we are assuming at most one transparent color in palette
1028 }
1029 i++;
1030 }
1031 p += p_linesize;
1032 }
1033
1034 load_colormap(s);
1035
1036 if (!s->new)
1037 s->palette_loaded = 1;
1038 }
1039
load_apply_palette(FFFrameSync * fs)1040 static int load_apply_palette(FFFrameSync *fs)
1041 {
1042 AVFilterContext *ctx = fs->parent;
1043 AVFilterLink *inlink = ctx->inputs[0];
1044 PaletteUseContext *s = ctx->priv;
1045 AVFrame *master, *second, *out = NULL;
1046 int ret;
1047
1048 // writable for error diffusal dithering
1049 ret = ff_framesync_dualinput_get_writable(fs, &master, &second);
1050 if (ret < 0)
1051 return ret;
1052 if (!master || !second) {
1053 av_frame_free(&master);
1054 return AVERROR_BUG;
1055 }
1056 if (!s->palette_loaded) {
1057 load_palette(s, second);
1058 }
1059 ret = apply_palette(inlink, master, &out);
1060 av_frame_free(&master);
1061 if (ret < 0)
1062 return ret;
1063 return ff_filter_frame(ctx->outputs[0], out);
1064 }
1065
1066 #define DEFINE_SET_FRAME(color_search, name, value) \
1067 static int set_frame_##name(PaletteUseContext *s, AVFrame *out, AVFrame *in, \
1068 int x_start, int y_start, int w, int h) \
1069 { \
1070 return set_frame(s, out, in, x_start, y_start, w, h, value, color_search); \
1071 }
1072
1073 #define DEFINE_SET_FRAME_COLOR_SEARCH(color_search, color_search_macro) \
1074 DEFINE_SET_FRAME(color_search_macro, color_search##_##none, DITHERING_NONE) \
1075 DEFINE_SET_FRAME(color_search_macro, color_search##_##bayer, DITHERING_BAYER) \
1076 DEFINE_SET_FRAME(color_search_macro, color_search##_##heckbert, DITHERING_HECKBERT) \
1077 DEFINE_SET_FRAME(color_search_macro, color_search##_##floyd_steinberg, DITHERING_FLOYD_STEINBERG) \
1078 DEFINE_SET_FRAME(color_search_macro, color_search##_##sierra2, DITHERING_SIERRA2) \
1079 DEFINE_SET_FRAME(color_search_macro, color_search##_##sierra2_4a, DITHERING_SIERRA2_4A) \
1080
1081 DEFINE_SET_FRAME_COLOR_SEARCH(nns_iterative, COLOR_SEARCH_NNS_ITERATIVE)
1082 DEFINE_SET_FRAME_COLOR_SEARCH(nns_recursive, COLOR_SEARCH_NNS_RECURSIVE)
1083 DEFINE_SET_FRAME_COLOR_SEARCH(bruteforce, COLOR_SEARCH_BRUTEFORCE)
1084
1085 #define DITHERING_ENTRIES(color_search) { \
1086 set_frame_##color_search##_none, \
1087 set_frame_##color_search##_bayer, \
1088 set_frame_##color_search##_heckbert, \
1089 set_frame_##color_search##_floyd_steinberg, \
1090 set_frame_##color_search##_sierra2, \
1091 set_frame_##color_search##_sierra2_4a, \
1092 }
1093
1094 static const set_frame_func set_frame_lut[NB_COLOR_SEARCHES][NB_DITHERING] = {
1095 DITHERING_ENTRIES(nns_iterative),
1096 DITHERING_ENTRIES(nns_recursive),
1097 DITHERING_ENTRIES(bruteforce),
1098 };
1099
dither_value(int p)1100 static int dither_value(int p)
1101 {
1102 const int q = p ^ (p >> 3);
1103 return (p & 4) >> 2 | (q & 4) >> 1 \
1104 | (p & 2) << 1 | (q & 2) << 2 \
1105 | (p & 1) << 4 | (q & 1) << 5;
1106 }
1107
init(AVFilterContext * ctx)1108 static av_cold int init(AVFilterContext *ctx)
1109 {
1110 PaletteUseContext *s = ctx->priv;
1111
1112 s->last_in = av_frame_alloc();
1113 s->last_out = av_frame_alloc();
1114 if (!s->last_in || !s->last_out)
1115 return AVERROR(ENOMEM);
1116
1117 s->set_frame = set_frame_lut[s->color_search_method][s->dither];
1118
1119 if (s->dither == DITHERING_BAYER) {
1120 int i;
1121 const int delta = 1 << (5 - s->bayer_scale); // to avoid too much luma
1122
1123 for (i = 0; i < FF_ARRAY_ELEMS(s->ordered_dither); i++)
1124 s->ordered_dither[i] = (dither_value(i) >> s->bayer_scale) - delta;
1125 }
1126
1127 return 0;
1128 }
1129
activate(AVFilterContext * ctx)1130 static int activate(AVFilterContext *ctx)
1131 {
1132 PaletteUseContext *s = ctx->priv;
1133 return ff_framesync_activate(&s->fs);
1134 }
1135
uninit(AVFilterContext * ctx)1136 static av_cold void uninit(AVFilterContext *ctx)
1137 {
1138 int i;
1139 PaletteUseContext *s = ctx->priv;
1140
1141 ff_framesync_uninit(&s->fs);
1142 for (i = 0; i < CACHE_SIZE; i++)
1143 av_freep(&s->cache[i].entries);
1144 av_frame_free(&s->last_in);
1145 av_frame_free(&s->last_out);
1146 }
1147
1148 static const AVFilterPad paletteuse_inputs[] = {
1149 {
1150 .name = "default",
1151 .type = AVMEDIA_TYPE_VIDEO,
1152 },{
1153 .name = "palette",
1154 .type = AVMEDIA_TYPE_VIDEO,
1155 .config_props = config_input_palette,
1156 },
1157 };
1158
1159 static const AVFilterPad paletteuse_outputs[] = {
1160 {
1161 .name = "default",
1162 .type = AVMEDIA_TYPE_VIDEO,
1163 .config_props = config_output,
1164 },
1165 };
1166
1167 const AVFilter ff_vf_paletteuse = {
1168 .name = "paletteuse",
1169 .description = NULL_IF_CONFIG_SMALL("Use a palette to downsample an input video stream."),
1170 .priv_size = sizeof(PaletteUseContext),
1171 .init = init,
1172 .uninit = uninit,
1173 .activate = activate,
1174 FILTER_INPUTS(paletteuse_inputs),
1175 FILTER_OUTPUTS(paletteuse_outputs),
1176 FILTER_QUERY_FUNC(query_formats),
1177 .priv_class = &paletteuse_class,
1178 };
1179