FFmpeg
vf_paletteuse.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2015 Stupeflix
3  * Copyright (c) 2022 Clément Bœsch <u pkh me>
4  *
5  * This file is part of FFmpeg.
6  *
7  * FFmpeg is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * FFmpeg is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with FFmpeg; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21 
22 /**
23  * @file
24  * Use a palette to downsample an input video stream.
25  */
26 
27 #include "libavutil/bprint.h"
28 #include "libavutil/file_open.h"
29 #include "libavutil/internal.h"
30 #include "libavutil/mem.h"
31 #include "libavutil/opt.h"
32 #include "libavutil/qsort.h"
33 #include "avfilter.h"
34 #include "filters.h"
35 #include "formats.h"
36 #include "framesync.h"
37 #include "internal.h"
38 #include "palette.h"
39 #include "video.h"
40 
52 };
53 
54 enum diff_mode {
58 };
59 
60 struct color_info {
61  uint32_t srgb;
63 };
64 
65 struct color_node {
66  struct color_info c;
67  uint8_t palette_id;
68  int split;
70 };
71 
72 #define CACHE_SIZE (1<<15)
73 
74 struct cached_color {
75  uint32_t color;
76  uint8_t pal_entry;
77 };
78 
79 struct cache_node {
82 };
83 
84 struct PaletteUseContext;
85 
87  int x_start, int y_start, int width, int height);
88 
89 typedef struct PaletteUseContext {
90  const AVClass *class;
92  struct cache_node cache[CACHE_SIZE]; /* lookup cache */
93  struct color_node map[AVPALETTE_COUNT]; /* 3D-Tree (KD-Tree with K=3) for reverse colormap */
95  int transparency_index; /* index in the palette of transparency. -1 if there is no transparency in the palette. */
98  int dither;
99  int new;
102  int ordered_dither[8*8];
106 
107  /* debug options */
110  uint64_t total_mean_err;
112 
113 #define OFFSET(x) offsetof(PaletteUseContext, x)
114 #define FLAGS AV_OPT_FLAG_FILTERING_PARAM|AV_OPT_FLAG_VIDEO_PARAM
115 static const AVOption paletteuse_options[] = {
116  { "dither", "select dithering mode", OFFSET(dither), AV_OPT_TYPE_INT, {.i64=DITHERING_SIERRA2_4A}, 0, NB_DITHERING-1, FLAGS, .unit = "dithering_mode" },
117  { "bayer", "ordered 8x8 bayer dithering (deterministic)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_BAYER}, INT_MIN, INT_MAX, FLAGS, .unit = "dithering_mode" },
118  { "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, .unit = "dithering_mode" },
119  { "floyd_steinberg", "Floyd and Steingberg dithering (error diffusion)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_FLOYD_STEINBERG}, INT_MIN, INT_MAX, FLAGS, .unit = "dithering_mode" },
120  { "sierra2", "Frankie Sierra dithering v2 (error diffusion)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_SIERRA2}, INT_MIN, INT_MAX, FLAGS, .unit = "dithering_mode" },
121  { "sierra2_4a", "Frankie Sierra dithering v2 \"Lite\" (error diffusion)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_SIERRA2_4A}, INT_MIN, INT_MAX, FLAGS, .unit = "dithering_mode" },
122  { "sierra3", "Frankie Sierra dithering v3 (error diffusion)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_SIERRA3}, INT_MIN, INT_MAX, FLAGS, .unit = "dithering_mode" },
123  { "burkes", "Burkes dithering (error diffusion)", 0, AV_OPT_TYPE_CONST, {.i64=DITHERING_BURKES}, INT_MIN, INT_MAX, FLAGS, .unit = "dithering_mode" },
124  { "atkinson", "Atkinson dithering by Bill Atkinson at Apple Computer (error diffusion)",0, AV_OPT_TYPE_CONST, {.i64=DITHERING_ATKINSON}, INT_MIN, INT_MAX, FLAGS, .unit = "dithering_mode" },
125  { "bayer_scale", "set scale for bayer dithering", OFFSET(bayer_scale), AV_OPT_TYPE_INT, {.i64=2}, 0, 5, FLAGS },
126  { "diff_mode", "set frame difference mode", OFFSET(diff_mode), AV_OPT_TYPE_INT, {.i64=DIFF_MODE_NONE}, 0, NB_DIFF_MODE-1, FLAGS, .unit = "diff_mode" },
127  { "rectangle", "process smallest different rectangle", 0, AV_OPT_TYPE_CONST, {.i64=DIFF_MODE_RECTANGLE}, INT_MIN, INT_MAX, FLAGS, .unit = "diff_mode" },
128  { "new", "take new palette for each output frame", OFFSET(new), AV_OPT_TYPE_BOOL, {.i64=0}, 0, 1, FLAGS },
129  { "alpha_threshold", "set the alpha threshold for transparency", OFFSET(trans_thresh), AV_OPT_TYPE_INT, {.i64=128}, 0, 255, FLAGS },
130 
131  /* following are the debug options, not part of the official API */
132  { "debug_kdtree", "save Graphviz graph of the kdtree in specified file", OFFSET(dot_filename), AV_OPT_TYPE_STRING, {.str=NULL}, 0, 0, FLAGS },
133  { NULL }
134 };
135 
136 AVFILTER_DEFINE_CLASS(paletteuse);
137 
138 static int load_apply_palette(FFFrameSync *fs);
139 
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 ||
151  &ctx->outputs[0]->incfg.formats)) < 0)
152  return ret;
153  return 0;
154 }
155 
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 & 0xff000000)
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 
165 static av_always_inline int diff(const struct color_info *a, const struct color_info *b, const int trans_thresh)
166 {
167  const uint8_t alpha_a = a->srgb >> 24;
168  const uint8_t alpha_b = b->srgb >> 24;
169 
170  if (alpha_a < trans_thresh && alpha_b < trans_thresh) {
171  return 0;
172  } else if (alpha_a >= trans_thresh && alpha_b >= trans_thresh) {
173  const int64_t dL = a->lab[0] - b->lab[0];
174  const int64_t da = a->lab[1] - b->lab[1];
175  const int64_t db = a->lab[2] - b->lab[2];
176  const int64_t ret = dL*dL + da*da + db*db;
177  return FFMIN(ret, INT32_MAX - 1);
178  } else {
179  return INT32_MAX - 1;
180  }
181 }
182 
183 static struct color_info get_color_from_srgb(uint32_t srgb)
184 {
185  const struct Lab lab = ff_srgb_u8_to_oklab_int(srgb);
186  struct color_info ret = {.srgb=srgb, .lab={lab.L, lab.a, lab.b}};
187  return ret;
188 }
189 
191  int node_pos;
192  int64_t dist_sqd;
193 };
194 
195 static void colormap_nearest_node(const struct color_node *map,
196  const int node_pos,
197  const struct color_info *target,
198  const int trans_thresh,
199  struct nearest_color *nearest)
200 {
201  const struct color_node *kd = map + node_pos;
202  int nearer_kd_id, further_kd_id;
203  const struct color_info *current = &kd->c;
204  const int64_t current_to_target = diff(target, current, trans_thresh);
205 
206  if (current_to_target < nearest->dist_sqd) {
207  nearest->node_pos = node_pos;
208  nearest->dist_sqd = current_to_target;
209  }
210 
211  if (kd->left_id != -1 || kd->right_id != -1) {
212  const int64_t dx = target->lab[kd->split] - current->lab[kd->split];
213 
214  if (dx <= 0) nearer_kd_id = kd->left_id, further_kd_id = kd->right_id;
215  else nearer_kd_id = kd->right_id, further_kd_id = kd->left_id;
216 
217  if (nearer_kd_id != -1)
218  colormap_nearest_node(map, nearer_kd_id, target, trans_thresh, nearest);
219 
220  if (further_kd_id != -1 && dx*dx < nearest->dist_sqd)
221  colormap_nearest_node(map, further_kd_id, target, trans_thresh, nearest);
222  }
223 }
224 
225 static av_always_inline uint8_t colormap_nearest(const struct color_node *node, const struct color_info *target, const int trans_thresh)
226 {
227  struct nearest_color res = {.dist_sqd = INT_MAX, .node_pos = -1};
228  colormap_nearest_node(node, 0, target, trans_thresh, &res);
229  return node[res.node_pos].palette_id;
230 }
231 
232 struct stack_node {
233  int color_id;
234  int dx2;
235 };
236 
237 /**
238  * Check if the requested color is in the cache already. If not, find it in the
239  * color tree and cache it.
240  */
242 {
243  struct color_info clrinfo;
244  const uint32_t hash = ff_lowbias32(color) & (CACHE_SIZE - 1);
245  struct cache_node *node = &s->cache[hash];
246  struct cached_color *e;
247 
248  // first, check for transparency
249  if (color>>24 < s->trans_thresh && s->transparency_index >= 0) {
250  return s->transparency_index;
251  }
252 
253  for (int i = 0; i < node->nb_entries; i++) {
254  e = &node->entries[i];
255  if (e->color == color)
256  return e->pal_entry;
257  }
258 
259  e = av_dynarray2_add((void**)&node->entries, &node->nb_entries,
260  sizeof(*node->entries), NULL);
261  if (!e)
262  return AVERROR(ENOMEM);
263  e->color = color;
264  clrinfo = get_color_from_srgb(color);
265  e->pal_entry = colormap_nearest(s->map, &clrinfo, s->trans_thresh);
266 
267  return e->pal_entry;
268 }
269 
271  uint32_t c, int *er, int *eg, int *eb)
272 {
273  uint32_t dstc;
274  const int dstx = color_get(s, c);
275  if (dstx < 0)
276  return dstx;
277  dstc = s->palette[dstx];
278  if (dstx == s->transparency_index) {
279  *er = *eg = *eb = 0;
280  } else {
281  const uint8_t r = c >> 16 & 0xff;
282  const uint8_t g = c >> 8 & 0xff;
283  const uint8_t b = c & 0xff;
284  *er = (int)r - (int)(dstc >> 16 & 0xff);
285  *eg = (int)g - (int)(dstc >> 8 & 0xff);
286  *eb = (int)b - (int)(dstc & 0xff);
287  }
288  return dstx;
289 }
290 
292  int x_start, int y_start, int w, int h,
293  enum dithering_mode dither)
294 {
295  const int src_linesize = in ->linesize[0] >> 2;
296  const int dst_linesize = out->linesize[0];
297  uint32_t *src = ((uint32_t *)in ->data[0]) + y_start*src_linesize;
298  uint8_t *dst = out->data[0] + y_start*dst_linesize;
299 
300  w += x_start;
301  h += y_start;
302 
303  for (int y = y_start; y < h; y++) {
304  for (int x = x_start; x < w; x++) {
305  int er, eg, eb;
306 
307  if (dither == DITHERING_BAYER) {
308  const int d = s->ordered_dither[(y & 7)<<3 | (x & 7)];
309  const uint8_t a8 = src[x] >> 24;
310  const uint8_t r8 = src[x] >> 16 & 0xff;
311  const uint8_t g8 = src[x] >> 8 & 0xff;
312  const uint8_t b8 = src[x] & 0xff;
313  const uint8_t r = av_clip_uint8(r8 + d);
314  const uint8_t g = av_clip_uint8(g8 + d);
315  const uint8_t b = av_clip_uint8(b8 + d);
316  const uint32_t color_new = (unsigned)(a8) << 24 | r << 16 | g << 8 | b;
317  const int color = color_get(s, color_new);
318 
319  if (color < 0)
320  return color;
321  dst[x] = color;
322 
323  } else if (dither == DITHERING_HECKBERT) {
324  const int right = x < w - 1, down = y < h - 1;
325  const int color = get_dst_color_err(s, src[x], &er, &eg, &eb);
326 
327  if (color < 0)
328  return color;
329  dst[x] = color;
330 
331  if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 3, 3);
332  if ( down) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 3, 3);
333  if (right && down) src[src_linesize + x + 1] = dither_color(src[src_linesize + x + 1], er, eg, eb, 2, 3);
334 
335  } else if (dither == DITHERING_FLOYD_STEINBERG) {
336  const int right = x < w - 1, down = y < h - 1, left = x > x_start;
337  const int color = get_dst_color_err(s, src[x], &er, &eg, &eb);
338 
339  if (color < 0)
340  return color;
341  dst[x] = color;
342 
343  if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 7, 4);
344  if (left && down) src[src_linesize + x - 1] = dither_color(src[src_linesize + x - 1], er, eg, eb, 3, 4);
345  if ( down) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 5, 4);
346  if (right && down) src[src_linesize + x + 1] = dither_color(src[src_linesize + x + 1], er, eg, eb, 1, 4);
347 
348  } else if (dither == DITHERING_SIERRA2) {
349  const int right = x < w - 1, down = y < h - 1, left = x > x_start;
350  const int right2 = x < w - 2, left2 = x > x_start + 1;
351  const int color = get_dst_color_err(s, src[x], &er, &eg, &eb);
352 
353  if (color < 0)
354  return color;
355  dst[x] = color;
356 
357  if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 4, 4);
358  if (right2) src[ x + 2] = dither_color(src[ x + 2], er, eg, eb, 3, 4);
359 
360  if (down) {
361  if (left2) src[ src_linesize + x - 2] = dither_color(src[ src_linesize + x - 2], er, eg, eb, 1, 4);
362  if (left) src[ src_linesize + x - 1] = dither_color(src[ src_linesize + x - 1], er, eg, eb, 2, 4);
363  if (1) src[ src_linesize + x ] = dither_color(src[ src_linesize + x ], er, eg, eb, 3, 4);
364  if (right) src[ src_linesize + x + 1] = dither_color(src[ src_linesize + x + 1], er, eg, eb, 2, 4);
365  if (right2) src[ src_linesize + x + 2] = dither_color(src[ src_linesize + x + 2], er, eg, eb, 1, 4);
366  }
367 
368  } else if (dither == DITHERING_SIERRA2_4A) {
369  const int right = x < w - 1, down = y < h - 1, left = x > x_start;
370  const int color = get_dst_color_err(s, src[x], &er, &eg, &eb);
371 
372  if (color < 0)
373  return color;
374  dst[x] = color;
375 
376  if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 2, 2);
377  if (left && down) src[src_linesize + x - 1] = dither_color(src[src_linesize + x - 1], er, eg, eb, 1, 2);
378  if ( down) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 1, 2);
379 
380  } else if (dither == DITHERING_SIERRA3) {
381  const int right = x < w - 1, down = y < h - 1, left = x > x_start;
382  const int right2 = x < w - 2, down2 = y < h - 2, left2 = x > x_start + 1;
383  const int color = get_dst_color_err(s, src[x], &er, &eg, &eb);
384 
385  if (color < 0)
386  return color;
387  dst[x] = color;
388 
389  if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 5, 5);
390  if (right2) src[ x + 2] = dither_color(src[ x + 2], er, eg, eb, 3, 5);
391 
392  if (down) {
393  if (left2) src[src_linesize + x - 2] = dither_color(src[src_linesize + x - 2], er, eg, eb, 2, 5);
394  if (left) src[src_linesize + x - 1] = dither_color(src[src_linesize + x - 1], er, eg, eb, 4, 5);
395  if (1) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 5, 5);
396  if (right) src[src_linesize + x + 1] = dither_color(src[src_linesize + x + 1], er, eg, eb, 4, 5);
397  if (right2) src[src_linesize + x + 2] = dither_color(src[src_linesize + x + 2], er, eg, eb, 2, 5);
398 
399  if (down2) {
400  if (left) src[src_linesize*2 + x - 1] = dither_color(src[src_linesize*2 + x - 1], er, eg, eb, 2, 5);
401  if (1) src[src_linesize*2 + x ] = dither_color(src[src_linesize*2 + x ], er, eg, eb, 3, 5);
402  if (right) src[src_linesize*2 + x + 1] = dither_color(src[src_linesize*2 + x + 1], er, eg, eb, 2, 5);
403  }
404  }
405 
406  } else if (dither == DITHERING_BURKES) {
407  const int right = x < w - 1, down = y < h - 1, left = x > x_start;
408  const int right2 = x < w - 2, left2 = x > x_start + 1;
409  const int color = get_dst_color_err(s, src[x], &er, &eg, &eb);
410 
411  if (color < 0)
412  return color;
413  dst[x] = color;
414 
415  if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 8, 5);
416  if (right2) src[ x + 2] = dither_color(src[ x + 2], er, eg, eb, 4, 5);
417 
418  if (down) {
419  if (left2) src[src_linesize + x - 2] = dither_color(src[src_linesize + x - 2], er, eg, eb, 2, 5);
420  if (left) src[src_linesize + x - 1] = dither_color(src[src_linesize + x - 1], er, eg, eb, 4, 5);
421  if (1) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 8, 5);
422  if (right) src[src_linesize + x + 1] = dither_color(src[src_linesize + x + 1], er, eg, eb, 4, 5);
423  if (right2) src[src_linesize + x + 2] = dither_color(src[src_linesize + x + 2], er, eg, eb, 2, 5);
424  }
425 
426  } else if (dither == DITHERING_ATKINSON) {
427  const int right = x < w - 1, down = y < h - 1, left = x > x_start;
428  const int right2 = x < w - 2, down2 = y < h - 2;
429  const int color = get_dst_color_err(s, src[x], &er, &eg, &eb);
430 
431  if (color < 0)
432  return color;
433  dst[x] = color;
434 
435  if (right) src[ x + 1] = dither_color(src[ x + 1], er, eg, eb, 1, 3);
436  if (right2) src[ x + 2] = dither_color(src[ x + 2], er, eg, eb, 1, 3);
437 
438  if (down) {
439  if (left) src[src_linesize + x - 1] = dither_color(src[src_linesize + x - 1], er, eg, eb, 1, 3);
440  if (1) src[src_linesize + x ] = dither_color(src[src_linesize + x ], er, eg, eb, 1, 3);
441  if (right) src[src_linesize + x + 1] = dither_color(src[src_linesize + x + 1], er, eg, eb, 1, 3);
442  if (down2) src[src_linesize*2 + x ] = dither_color(src[src_linesize*2 + x ], er, eg, eb, 1, 3);
443  }
444 
445  } else {
446  const int color = color_get(s, src[x]);
447 
448  if (color < 0)
449  return color;
450  dst[x] = color;
451  }
452  }
453  src += src_linesize;
454  dst += dst_linesize;
455  }
456  return 0;
457 }
458 
459 #define INDENT 4
460 static void disp_node(AVBPrint *buf,
461  const struct color_node *map,
462  int parent_id, int node_id,
463  int depth)
464 {
465  const struct color_node *node = &map[node_id];
466  const uint32_t fontcolor = node->c.lab[0] > 0x7fff ? 0 : 0xffffff;
467  const int lab_comp = node->split;
468  av_bprintf(buf, "%*cnode%d ["
469  "label=\"%c%d%c%d%c%d%c\" "
470  "fillcolor=\"#%06"PRIX32"\" "
471  "fontcolor=\"#%06"PRIX32"\"]\n",
472  depth*INDENT, ' ', node->palette_id,
473  "[ "[lab_comp], node->c.lab[0],
474  "][ "[lab_comp], node->c.lab[1],
475  " ]["[lab_comp], node->c.lab[2],
476  " ]"[lab_comp],
477  node->c.srgb & 0xffffff,
478  fontcolor);
479  if (parent_id != -1)
480  av_bprintf(buf, "%*cnode%d -> node%d\n", depth*INDENT, ' ',
481  map[parent_id].palette_id, node->palette_id);
482  if (node->left_id != -1) disp_node(buf, map, node_id, node->left_id, depth + 1);
483  if (node->right_id != -1) disp_node(buf, map, node_id, node->right_id, depth + 1);
484 }
485 
486 // debug_kdtree=kdtree.dot -> dot -Tpng kdtree.dot > kdtree.png
487 static int disp_tree(const struct color_node *node, const char *fname)
488 {
489  AVBPrint buf;
490  FILE *f = avpriv_fopen_utf8(fname, "w");
491 
492  if (!f) {
493  int ret = AVERROR(errno);
494  av_log(NULL, AV_LOG_ERROR, "Cannot open file '%s' for writing: %s\n",
495  fname, av_err2str(ret));
496  return ret;
497  }
498 
500 
501  av_bprintf(&buf, "digraph {\n");
502  av_bprintf(&buf, " node [style=filled fontsize=10 shape=box]\n");
503  disp_node(&buf, node, -1, 0, 0);
504  av_bprintf(&buf, "}\n");
505 
506  fwrite(buf.str, 1, buf.len, f);
507  fclose(f);
508  av_bprint_finalize(&buf, NULL);
509  return 0;
510 }
511 
512 struct color {
513  struct Lab value;
514  uint8_t pal_id;
515 };
516 
517 struct color_rect {
520 };
521 
522 typedef int (*cmp_func)(const void *, const void *);
523 
524 #define DECLARE_CMP_FUNC(name) \
525 static int cmp_##name(const void *pa, const void *pb) \
526 { \
527  const struct color *a = pa; \
528  const struct color *b = pb; \
529  return FFDIFFSIGN(a->value.name, b->value.name); \
530 }
531 
535 
536 static const cmp_func cmp_funcs[] = {cmp_L, cmp_a, cmp_b};
537 
538 static int get_next_color(const uint8_t *color_used, const uint32_t *palette,
539  int *component, const struct color_rect *box)
540 {
541  int wL, wa, wb;
542  int longest = 0;
543  unsigned nb_color = 0;
544  struct color_rect ranges;
545  struct color tmp_pal[256];
546  cmp_func cmpf;
547 
548  ranges.min[0] = ranges.min[1] = ranges.min[2] = 0xffff;
549  ranges.max[0] = ranges.max[1] = ranges.max[2] = -0xffff;
550 
551  for (int i = 0; i < AVPALETTE_COUNT; i++) {
552  const uint32_t c = palette[i];
553  const uint8_t a = c >> 24;
554  const struct Lab lab = ff_srgb_u8_to_oklab_int(c);
555 
556  if (color_used[i] || (a != 0xff) ||
557  lab.L < box->min[0] || lab.a < box->min[1] || lab.b < box->min[2] ||
558  lab.L > box->max[0] || lab.a > box->max[1] || lab.b > box->max[2])
559  continue;
560 
561  if (lab.L < ranges.min[0]) ranges.min[0] = lab.L;
562  if (lab.a < ranges.min[1]) ranges.min[1] = lab.a;
563  if (lab.b < ranges.min[2]) ranges.min[2] = lab.b;
564 
565  if (lab.L > ranges.max[0]) ranges.max[0] = lab.L;
566  if (lab.a > ranges.max[1]) ranges.max[1] = lab.a;
567  if (lab.b > ranges.max[2]) ranges.max[2] = lab.b;
568 
569  tmp_pal[nb_color].value = lab;
570  tmp_pal[nb_color].pal_id = i;
571 
572  nb_color++;
573  }
574 
575  if (!nb_color)
576  return -1;
577 
578  /* define longest axis that will be the split component */
579  wL = ranges.max[0] - ranges.min[0];
580  wa = ranges.max[1] - ranges.min[1];
581  wb = ranges.max[2] - ranges.min[2];
582  if (wb >= wL && wb >= wa) longest = 2;
583  if (wa >= wL && wa >= wb) longest = 1;
584  if (wL >= wa && wL >= wb) longest = 0;
585  cmpf = cmp_funcs[longest];
586  *component = longest;
587 
588  /* sort along this axis to get median */
589  AV_QSORT(tmp_pal, nb_color, struct color, cmpf);
590 
591  return tmp_pal[nb_color >> 1].pal_id;
592 }
593 
594 static int colormap_insert(struct color_node *map,
595  uint8_t *color_used,
596  int *nb_used,
597  const uint32_t *palette,
598  const int trans_thresh,
599  const struct color_rect *box)
600 {
601  int component, cur_id;
602  int comp_value;
603  int node_left_id = -1, node_right_id = -1;
604  struct color_node *node;
605  struct color_rect box1, box2;
606  const int pal_id = get_next_color(color_used, palette, &component, box);
607 
608  if (pal_id < 0)
609  return -1;
610 
611  /* create new node with that color */
612  cur_id = (*nb_used)++;
613  node = &map[cur_id];
614  node->split = component;
615  node->palette_id = pal_id;
616  node->c = get_color_from_srgb(palette[pal_id]);
617 
618  color_used[pal_id] = 1;
619 
620  /* get the two boxes this node creates */
621  box1 = box2 = *box;
622  comp_value = node->c.lab[component];
623  box1.max[component] = comp_value;
624  box2.min[component] = FFMIN(comp_value + 1, 0xffff);
625 
626  node_left_id = colormap_insert(map, color_used, nb_used, palette, trans_thresh, &box1);
627 
628  if (box2.min[component] <= box2.max[component])
629  node_right_id = colormap_insert(map, color_used, nb_used, palette, trans_thresh, &box2);
630 
631  node->left_id = node_left_id;
632  node->right_id = node_right_id;
633 
634  return cur_id;
635 }
636 
637 static int cmp_pal_entry(const void *a, const void *b)
638 {
639  const int c1 = *(const uint32_t *)a & 0xffffff;
640  const int c2 = *(const uint32_t *)b & 0xffffff;
641  return c1 - c2;
642 }
643 
645 {
646  int nb_used = 0;
647  uint8_t color_used[AVPALETTE_COUNT] = {0};
648  uint32_t last_color = 0;
649  struct color_rect box;
650 
651  if (s->transparency_index >= 0) {
652  FFSWAP(uint32_t, s->palette[s->transparency_index], s->palette[255]);
653  }
654 
655  /* disable transparent colors and dups */
656  qsort(s->palette, AVPALETTE_COUNT-(s->transparency_index >= 0), sizeof(*s->palette), cmp_pal_entry);
657 
658  for (int i = 0; i < AVPALETTE_COUNT; i++) {
659  const uint32_t c = s->palette[i];
660  if (i != 0 && c == last_color) {
661  color_used[i] = 1;
662  continue;
663  }
664  last_color = c;
665  if (c >> 24 < s->trans_thresh) {
666  color_used[i] = 1; // ignore transparent color(s)
667  continue;
668  }
669  }
670 
671  box.min[0] = box.min[1] = box.min[2] = -0xffff;
672  box.max[0] = box.max[1] = box.max[2] = 0xffff;
673 
674  colormap_insert(s->map, color_used, &nb_used, s->palette, s->trans_thresh, &box);
675 
676  if (s->dot_filename)
677  disp_tree(s->map, s->dot_filename);
678 }
679 
681  const AVFrame *prv_src, const AVFrame *cur_src,
682  const AVFrame *prv_dst, AVFrame *cur_dst,
683  int *xp, int *yp, int *wp, int *hp)
684 {
685  int x_start = 0, y_start = 0;
686  int width = cur_src->width;
687  int height = cur_src->height;
688 
689  if (prv_src->data[0] && diff_mode == DIFF_MODE_RECTANGLE) {
690  int y;
691  int x_end = cur_src->width - 1,
692  y_end = cur_src->height - 1;
693  const uint32_t *prv_srcp = (const uint32_t *)prv_src->data[0];
694  const uint32_t *cur_srcp = (const uint32_t *)cur_src->data[0];
695  const uint8_t *prv_dstp = prv_dst->data[0];
696  uint8_t *cur_dstp = cur_dst->data[0];
697 
698  const int prv_src_linesize = prv_src->linesize[0] >> 2;
699  const int cur_src_linesize = cur_src->linesize[0] >> 2;
700  const int prv_dst_linesize = prv_dst->linesize[0];
701  const int cur_dst_linesize = cur_dst->linesize[0];
702 
703  /* skip common lines */
704  while (y_start < y_end && !memcmp(prv_srcp + y_start*prv_src_linesize,
705  cur_srcp + y_start*cur_src_linesize,
706  cur_src->width * 4)) {
707  memcpy(cur_dstp + y_start*cur_dst_linesize,
708  prv_dstp + y_start*prv_dst_linesize,
709  cur_dst->width);
710  y_start++;
711  }
712  while (y_end > y_start && !memcmp(prv_srcp + y_end*prv_src_linesize,
713  cur_srcp + y_end*cur_src_linesize,
714  cur_src->width * 4)) {
715  memcpy(cur_dstp + y_end*cur_dst_linesize,
716  prv_dstp + y_end*prv_dst_linesize,
717  cur_dst->width);
718  y_end--;
719  }
720 
721  height = y_end + 1 - y_start;
722 
723  /* skip common columns */
724  while (x_start < x_end) {
725  int same_column = 1;
726  for (y = y_start; y <= y_end; y++) {
727  if (prv_srcp[y*prv_src_linesize + x_start] != cur_srcp[y*cur_src_linesize + x_start]) {
728  same_column = 0;
729  break;
730  }
731  }
732  if (!same_column)
733  break;
734  x_start++;
735  }
736  while (x_end > x_start) {
737  int same_column = 1;
738  for (y = y_start; y <= y_end; y++) {
739  if (prv_srcp[y*prv_src_linesize + x_end] != cur_srcp[y*cur_src_linesize + x_end]) {
740  same_column = 0;
741  break;
742  }
743  }
744  if (!same_column)
745  break;
746  x_end--;
747  }
748  width = x_end + 1 - x_start;
749 
750  if (x_start) {
751  for (y = y_start; y <= y_end; y++)
752  memcpy(cur_dstp + y*cur_dst_linesize,
753  prv_dstp + y*prv_dst_linesize, x_start);
754  }
755  if (x_end != cur_src->width - 1) {
756  const int copy_len = cur_src->width - 1 - x_end;
757  for (y = y_start; y <= y_end; y++)
758  memcpy(cur_dstp + y*cur_dst_linesize + x_end + 1,
759  prv_dstp + y*prv_dst_linesize + x_end + 1,
760  copy_len);
761  }
762  }
763  *xp = x_start;
764  *yp = y_start;
765  *wp = width;
766  *hp = height;
767 }
768 
770 {
771  int x, y, w, h, ret;
772  AVFilterContext *ctx = inlink->dst;
773  PaletteUseContext *s = ctx->priv;
774  AVFilterLink *outlink = inlink->dst->outputs[0];
775 
776  AVFrame *out = ff_get_video_buffer(outlink, outlink->w, outlink->h);
777  if (!out) {
778  *outf = NULL;
779  return AVERROR(ENOMEM);
780  }
782 
783  set_processing_window(s->diff_mode, s->last_in, in,
784  s->last_out, out, &x, &y, &w, &h);
785  av_frame_unref(s->last_out);
786  if ((ret = av_frame_replace(s->last_in, in)) < 0 ||
787  (ret = av_frame_ref(s->last_out, out)) < 0 ||
788  (ret = ff_inlink_make_frame_writable(inlink, &s->last_in)) < 0) {
789  av_frame_free(&out);
790  *outf = NULL;
791  return ret;
792  }
793 
794  ff_dlog(ctx, "%dx%d rect: (%d;%d) -> (%d,%d) [area:%dx%d]\n",
795  w, h, x, y, x+w, y+h, in->width, in->height);
796 
797  ret = s->set_frame(s, out, in, x, y, w, h);
798  if (ret < 0) {
799  av_frame_free(&out);
800  *outf = NULL;
801  return ret;
802  }
803  memcpy(out->data[1], s->palette, AVPALETTE_SIZE);
804  *outf = out;
805  return 0;
806 }
807 
808 static int config_output(AVFilterLink *outlink)
809 {
810  int ret;
811  AVFilterContext *ctx = outlink->src;
812  PaletteUseContext *s = ctx->priv;
813 
815  if (ret < 0)
816  return ret;
817  s->fs.opt_repeatlast = 1; // only 1 frame in the palette
818  s->fs.in[1].before = s->fs.in[1].after = EXT_INFINITY;
819  s->fs.on_event = load_apply_palette;
820 
821  outlink->w = ctx->inputs[0]->w;
822  outlink->h = ctx->inputs[0]->h;
823 
824  outlink->time_base = ctx->inputs[0]->time_base;
825  if ((ret = ff_framesync_configure(&s->fs)) < 0)
826  return ret;
827  return 0;
828 }
829 
831 {
832  AVFilterContext *ctx = inlink->dst;
833 
834  if (inlink->w * inlink->h != AVPALETTE_COUNT) {
836  "Palette input must contain exactly %d pixels. "
837  "Specified input has %dx%d=%d pixels\n",
838  AVPALETTE_COUNT, inlink->w, inlink->h,
839  inlink->w * inlink->h);
840  return AVERROR(EINVAL);
841  }
842  return 0;
843 }
844 
845 static void load_palette(PaletteUseContext *s, const AVFrame *palette_frame)
846 {
847  int i, x, y;
848  const uint32_t *p = (const uint32_t *)palette_frame->data[0];
849  const ptrdiff_t p_linesize = palette_frame->linesize[0] >> 2;
850 
851  s->transparency_index = -1;
852 
853  if (s->new) {
854  memset(s->palette, 0, sizeof(s->palette));
855  memset(s->map, 0, sizeof(s->map));
856  for (i = 0; i < CACHE_SIZE; i++)
857  av_freep(&s->cache[i].entries);
858  memset(s->cache, 0, sizeof(s->cache));
859  }
860 
861  i = 0;
862  for (y = 0; y < palette_frame->height; y++) {
863  for (x = 0; x < palette_frame->width; x++) {
864  s->palette[i] = p[x];
865  if (p[x]>>24 < s->trans_thresh) {
866  s->transparency_index = i; // we are assuming at most one transparent color in palette
867  }
868  i++;
869  }
870  p += p_linesize;
871  }
872 
873  load_colormap(s);
874 
875  if (!s->new)
876  s->palette_loaded = 1;
877 }
878 
880 {
881  AVFilterContext *ctx = fs->parent;
882  AVFilterLink *inlink = ctx->inputs[0];
883  PaletteUseContext *s = ctx->priv;
884  AVFrame *master, *second, *out = NULL;
885  int ret;
886 
887  // writable for error diffusal dithering
889  if (ret < 0)
890  return ret;
891  if (!master || !second) {
893  return AVERROR_BUG;
894  }
895  if (!s->palette_loaded) {
896  load_palette(s, second);
897  }
900  if (ret < 0)
901  return ret;
902  return ff_filter_frame(ctx->outputs[0], out);
903 }
904 
905 #define DEFINE_SET_FRAME(name, value) \
906 static int set_frame_##name(PaletteUseContext *s, AVFrame *out, AVFrame *in, \
907  int x_start, int y_start, int w, int h) \
908 { \
909  return set_frame(s, out, in, x_start, y_start, w, h, value); \
910 }
911 
921 
923  [DITHERING_NONE] = set_frame_none,
924  [DITHERING_BAYER] = set_frame_bayer,
925  [DITHERING_HECKBERT] = set_frame_heckbert,
926  [DITHERING_FLOYD_STEINBERG] = set_frame_floyd_steinberg,
927  [DITHERING_SIERRA2] = set_frame_sierra2,
928  [DITHERING_SIERRA2_4A] = set_frame_sierra2_4a,
929  [DITHERING_SIERRA3] = set_frame_sierra3,
930  [DITHERING_BURKES] = set_frame_burkes,
931  [DITHERING_ATKINSON] = set_frame_atkinson,
932 };
933 
934 static int dither_value(int p)
935 {
936  const int q = p ^ (p >> 3);
937  return (p & 4) >> 2 | (q & 4) >> 1 \
938  | (p & 2) << 1 | (q & 2) << 2 \
939  | (p & 1) << 4 | (q & 1) << 5;
940 }
941 
943 {
944  PaletteUseContext *s = ctx->priv;
945 
946  s->last_in = av_frame_alloc();
947  s->last_out = av_frame_alloc();
948  if (!s->last_in || !s->last_out)
949  return AVERROR(ENOMEM);
950 
951  s->set_frame = set_frame_lut[s->dither];
952 
953  if (s->dither == DITHERING_BAYER) {
954  const int delta = 1 << (5 - s->bayer_scale); // to avoid too much luma
955 
956  for (int i = 0; i < FF_ARRAY_ELEMS(s->ordered_dither); i++)
957  s->ordered_dither[i] = (dither_value(i) >> s->bayer_scale) - delta;
958  }
959 
960  return 0;
961 }
962 
964 {
965  PaletteUseContext *s = ctx->priv;
966  return ff_framesync_activate(&s->fs);
967 }
968 
970 {
971  PaletteUseContext *s = ctx->priv;
972 
973  ff_framesync_uninit(&s->fs);
974  for (int i = 0; i < CACHE_SIZE; i++)
975  av_freep(&s->cache[i].entries);
976  av_frame_free(&s->last_in);
977  av_frame_free(&s->last_out);
978 }
979 
980 static const AVFilterPad paletteuse_inputs[] = {
981  {
982  .name = "default",
983  .type = AVMEDIA_TYPE_VIDEO,
984  },{
985  .name = "palette",
986  .type = AVMEDIA_TYPE_VIDEO,
987  .config_props = config_input_palette,
988  },
989 };
990 
991 static const AVFilterPad paletteuse_outputs[] = {
992  {
993  .name = "default",
994  .type = AVMEDIA_TYPE_VIDEO,
995  .config_props = config_output,
996  },
997 };
998 
1000  .name = "paletteuse",
1001  .description = NULL_IF_CONFIG_SMALL("Use a palette to downsample an input video stream."),
1002  .priv_size = sizeof(PaletteUseContext),
1003  .init = init,
1004  .uninit = uninit,
1005  .activate = activate,
1009  .priv_class = &paletteuse_class,
1010 };
ff_get_video_buffer
AVFrame * ff_get_video_buffer(AVFilterLink *link, int w, int h)
Request a picture buffer with a specific set of permissions.
Definition: video.c:112
cached_color::color
uint32_t color
Definition: vf_paletteuse.c:75
ff_framesync_configure
int ff_framesync_configure(FFFrameSync *fs)
Configure a frame sync structure.
Definition: framesync.c:134
AV_BPRINT_SIZE_UNLIMITED
#define AV_BPRINT_SIZE_UNLIMITED
config_input_palette
static int config_input_palette(AVFilterLink *inlink)
Definition: vf_paletteuse.c:830
AVPixelFormat
AVPixelFormat
Pixel format.
Definition: pixfmt.h:71
query_formats
static int query_formats(AVFilterContext *ctx)
Definition: vf_paletteuse.c:140
set_frame
static av_always_inline int set_frame(PaletteUseContext *s, AVFrame *out, AVFrame *in, int x_start, int y_start, int w, int h, enum dithering_mode dither)
Definition: vf_paletteuse.c:291
PaletteUseContext::dot_filename
char * dot_filename
Definition: vf_paletteuse.c:108
r
const char * r
Definition: vf_curves.c:127
AVERROR
Filter the word “frame” indicates either a video frame or a group of audio as stored in an AVFrame structure Format for each input and each output the list of supported formats For video that means pixel format For audio that means channel sample they are references to shared objects When the negotiation mechanism computes the intersection of the formats supported at each end of a all references to both lists are replaced with a reference to the intersection And when a single format is eventually chosen for a link amongst the remaining all references to the list are updated That means that if a filter requires that its input and output have the same format amongst a supported all it has to do is use a reference to the same list of formats query_formats can leave some formats unset and return AVERROR(EAGAIN) to cause the negotiation mechanism toagain later. That can be used by filters with complex requirements to use the format negotiated on one link to set the formats supported on another. Frame references ownership and permissions
opt.h
ff_make_format_list
AVFilterFormats * ff_make_format_list(const int *fmts)
Create a list of supported formats.
Definition: formats.c:436
color_node::c
struct color_info c
Definition: vf_paletteuse.c:66
ff_framesync_uninit
void ff_framesync_uninit(FFFrameSync *fs)
Free all memory currently allocated.
Definition: framesync.c:304
out
FILE * out
Definition: movenc.c:55
color
Definition: vf_paletteuse.c:512
av_bprint_init
void av_bprint_init(AVBPrint *buf, unsigned size_init, unsigned size_max)
Definition: bprint.c:69
color_get
static av_always_inline int color_get(PaletteUseContext *s, uint32_t color)
Check if the requested color is in the cache already.
Definition: vf_paletteuse.c:241
ff_filter_frame
int ff_filter_frame(AVFilterLink *link, AVFrame *frame)
Send a frame of data to the next filter.
Definition: avfilter.c:1015
palette.h
PaletteUseContext::last_out
AVFrame * last_out
Definition: vf_paletteuse.c:105
dither_color
static av_always_inline uint32_t dither_color(uint32_t px, int er, int eg, int eb, int scale, int shift)
Definition: vf_paletteuse.c:156
inlink
The exact code depends on how similar the blocks are and how related they are to the and needs to apply these operations to the correct inlink or outlink if there are several Macros are available to factor that when no extra processing is inlink
Definition: filter_design.txt:212
av_frame_free
void av_frame_free(AVFrame **frame)
Free the frame and any dynamically allocated objects in it, e.g.
Definition: frame.c:160
colormap_nearest_node
static void colormap_nearest_node(const struct color_node *map, const int node_pos, const struct color_info *target, const int trans_thresh, struct nearest_color *nearest)
Definition: vf_paletteuse.c:195
init
static av_cold int init(AVFilterContext *ctx)
Definition: vf_paletteuse.c:942
set_frame_func
int(* set_frame_func)(struct PaletteUseContext *s, AVFrame *out, AVFrame *in, int x_start, int y_start, int width, int height)
Definition: vf_paletteuse.c:86
AVFrame
This structure describes decoded (raw) audio or video data.
Definition: frame.h:374
uninit
static av_cold void uninit(AVFilterContext *ctx)
Definition: vf_paletteuse.c:969
AVFrame::width
int width
Definition: frame.h:446
w
uint8_t w
Definition: llviddspenc.c:38
av_dynarray2_add
void * av_dynarray2_add(void **tab_ptr, int *nb_ptr, size_t elem_size, const uint8_t *elem_data)
Add an element of size elem_size to a dynamic array.
Definition: mem.c:343
AVOption
AVOption.
Definition: opt.h:346
b
#define b
Definition: input.c:41
FILTER_QUERY_FUNC
#define FILTER_QUERY_FUNC(func)
Definition: internal.h:159
stack_node::dx2
int dx2
Definition: vf_paletteuse.c:234
data
const char data[16]
Definition: mxf.c:148
PaletteUseContext::set_frame
set_frame_func set_frame
Definition: vf_paletteuse.c:100
disp_tree
static int disp_tree(const struct color_node *node, const char *fname)
Definition: vf_paletteuse.c:487
get_dst_color_err
static av_always_inline int get_dst_color_err(PaletteUseContext *s, uint32_t c, int *er, int *eg, int *eb)
Definition: vf_paletteuse.c:270
AVFilter::name
const char * name
Filter name.
Definition: avfilter.h:170
c1
static const uint64_t c1
Definition: murmur3.c:52
FFFrameSync
Frame sync structure.
Definition: framesync.h:168
EXT_INFINITY
@ EXT_INFINITY
Extend the frame to infinity.
Definition: framesync.h:75
video.h
hash
uint8_t hash[HASH_SIZE]
Definition: movenc.c:58
Lab::a
int32_t a
Definition: palette.h:31
PaletteUseContext::palette_loaded
int palette_loaded
Definition: vf_paletteuse.c:97
AVFrame::data
uint8_t * data[AV_NUM_DATA_POINTERS]
pointer to the picture/channel planes.
Definition: frame.h:395
formats.h
stack_node::color_id
int color_id
Definition: vf_paletteuse.c:233
DIFF_MODE_NONE
@ DIFF_MODE_NONE
Definition: vf_paletteuse.c:55
NB_DITHERING
@ NB_DITHERING
Definition: vf_paletteuse.c:51
Lab::b
int32_t b
Definition: palette.h:31
dither_value
static int dither_value(int p)
Definition: vf_paletteuse.c:934
apply_palette
static int apply_palette(AVFilterLink *inlink, AVFrame *in, AVFrame **outf)
Definition: vf_paletteuse.c:769
PaletteUseContext::cache
struct cache_node cache[CACHE_SIZE]
Definition: vf_paletteuse.c:92
AVFilterPad
A filter pad used for either input or output.
Definition: internal.h:33
colormap_insert
static int colormap_insert(struct color_node *map, uint8_t *color_used, int *nb_used, const uint32_t *palette, const int trans_thresh, const struct color_rect *box)
Definition: vf_paletteuse.c:594
av_frame_alloc
AVFrame * av_frame_alloc(void)
Allocate an AVFrame and set its fields to default values.
Definition: frame.c:148
color_info
Definition: vf_paletteuse.c:60
PaletteUseContext::ordered_dither
int ordered_dither[8 *8]
Definition: vf_paletteuse.c:102
AV_LOG_ERROR
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:180
set_processing_window
static void 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)
Definition: vf_paletteuse.c:680
FF_ARRAY_ELEMS
#define FF_ARRAY_ELEMS(a)
Definition: sinewin_tablegen.c:29
av_cold
#define av_cold
Definition: attributes.h:90
INDENT
#define INDENT
Definition: vf_paletteuse.c:459
color_rect
Definition: vf_paletteuse.c:517
color_info::srgb
uint32_t srgb
Definition: vf_paletteuse.c:61
PaletteUseContext::bayer_scale
int bayer_scale
Definition: vf_paletteuse.c:101
width
#define width
s
#define s(width, name)
Definition: cbs_vp9.c:198
dithering_mode
dithering_mode
Definition: vf_paletteuse.c:41
config_output
static int config_output(AVFilterLink *outlink)
Definition: vf_paletteuse.c:808
g
const char * g
Definition: vf_curves.c:128
ff_formats_ref
int ff_formats_ref(AVFilterFormats *f, AVFilterFormats **ref)
Add *ref as a new reference to formats.
Definition: formats.c:679
color_node::right_id
int right_id
Definition: vf_paletteuse.c:69
DITHERING_HECKBERT
@ DITHERING_HECKBERT
Definition: vf_paletteuse.c:44
stack_node
Definition: vf_paletteuse.c:232
filters.h
ctx
AVFormatContext * ctx
Definition: movenc.c:49
ff_lowbias32
uint32_t ff_lowbias32(uint32_t x)
Definition: palette.c:211
FILTER_INPUTS
#define FILTER_INPUTS(array)
Definition: internal.h:182
file_open.h
ff_inlink_make_frame_writable
int ff_inlink_make_frame_writable(AVFilterLink *link, AVFrame **rframe)
Make sure a frame is writable.
Definition: avfilter.c:1489
colormap_nearest
static av_always_inline uint8_t colormap_nearest(const struct color_node *node, const struct color_info *target, const int trans_thresh)
Definition: vf_paletteuse.c:225
if
if(ret)
Definition: filter_design.txt:179
color_node::palette_id
uint8_t palette_id
Definition: vf_paletteuse.c:67
load_apply_palette
static int load_apply_palette(FFFrameSync *fs)
Definition: vf_paletteuse.c:879
AVClass
Describe the class of an AVClass context structure.
Definition: log.h:66
NULL
#define NULL
Definition: coverity.c:32
ff_vf_paletteuse
const AVFilter ff_vf_paletteuse
Definition: vf_paletteuse.c:999
av_frame_copy_props
int av_frame_copy_props(AVFrame *dst, const AVFrame *src)
Copy only "metadata" fields from src to dst.
Definition: frame.c:709
PaletteUseContext::dither
int dither
Definition: vf_paletteuse.c:98
fs
#define fs(width, name, subs,...)
Definition: cbs_vp9.c:200
color_info::lab
int32_t lab[3]
Definition: vf_paletteuse.c:62
get_next_color
static int get_next_color(const uint8_t *color_used, const uint32_t *palette, int *component, const struct color_rect *box)
Definition: vf_paletteuse.c:538
AVPALETTE_SIZE
#define AVPALETTE_SIZE
Definition: pixfmt.h:32
set_frame_lut
static const set_frame_func set_frame_lut[NB_DITHERING]
Definition: vf_paletteuse.c:922
PaletteUseContext
Definition: vf_paletteuse.c:89
c
Undefined Behavior In the C some operations are like signed integer dereferencing freed accessing outside allocated Undefined Behavior must not occur in a C it is not safe even if the output of undefined operations is unused The unsafety may seem nit picking but Optimizing compilers have in fact optimized code on the assumption that no undefined Behavior occurs Optimizing code based on wrong assumptions can and has in some cases lead to effects beyond the output of computations The signed integer overflow problem in speed critical code Code which is highly optimized and works with signed integers sometimes has the problem that often the output of the computation does not c
Definition: undefined.txt:32
cmp_funcs
static const cmp_func cmp_funcs[]
Definition: vf_paletteuse.c:536
AVPALETTE_COUNT
#define AVPALETTE_COUNT
Definition: pixfmt.h:33
disp_node
static void disp_node(AVBPrint *buf, const struct color_node *map, int parent_id, int node_id, int depth)
Definition: vf_paletteuse.c:460
DITHERING_NONE
@ DITHERING_NONE
Definition: vf_paletteuse.c:42
paletteuse_options
static const AVOption paletteuse_options[]
Definition: vf_paletteuse.c:115
ff_dlog
#define ff_dlog(a,...)
Definition: tableprint_vlc.h:28
PaletteUseContext::trans_thresh
int trans_thresh
Definition: vf_paletteuse.c:96
qsort.h
f
f
Definition: af_crystalizer.c:121
NULL_IF_CONFIG_SMALL
#define NULL_IF_CONFIG_SMALL(x)
Return NULL if CONFIG_SMALL is true, otherwise the argument without modification.
Definition: internal.h:94
ff_framesync_init_dualinput
int ff_framesync_init_dualinput(FFFrameSync *fs, AVFilterContext *parent)
Initialize a frame sync structure for dualinput.
Definition: framesync.c:375
master
const char * master
Definition: vf_curves.c:130
av_frame_ref
int av_frame_ref(AVFrame *dst, const AVFrame *src)
Set up a new reference to the data described by the source frame.
Definition: frame.c:384
av_bprint_finalize
int av_bprint_finalize(AVBPrint *buf, char **ret_str)
Finalize a print buffer.
Definition: bprint.c:240
nearest_color
Definition: vf_paletteuse.c:190
shift
static int shift(int a, int b)
Definition: bonk.c:261
DITHERING_BAYER
@ DITHERING_BAYER
Definition: vf_paletteuse.c:43
av_err2str
#define av_err2str(errnum)
Convenience macro, the return value should be used only directly in function arguments but never stan...
Definition: error.h:121
DITHERING_FLOYD_STEINBERG
@ DITHERING_FLOYD_STEINBERG
Definition: vf_paletteuse.c:45
Lab
Definition: palette.h:30
PaletteUseContext::palette
uint32_t palette[AVPALETTE_COUNT]
Definition: vf_paletteuse.c:94
color
static const uint32_t color[16+AV_CLASS_CATEGORY_NB]
Definition: log.c:94
DITHERING_SIERRA2
@ DITHERING_SIERRA2
Definition: vf_paletteuse.c:46
color::value
struct Lab value
Definition: vf_paletteuse.c:513
PaletteUseContext::fs
FFFrameSync fs
Definition: vf_paletteuse.c:91
diff
static av_always_inline int diff(const struct color_info *a, const struct color_info *b, const int trans_thresh)
Definition: vf_paletteuse.c:165
height
#define height
AV_PIX_FMT_RGB32
#define AV_PIX_FMT_RGB32
Definition: pixfmt.h:451
a
The reader does not expect b to be semantically here and if the code is changed by maybe adding a a division or other the signedness will almost certainly be mistaken To avoid this confusion a new type was SUINT is the C unsigned type but it holds a signed int to use the same example SUINT a
Definition: undefined.txt:41
DITHERING_SIERRA2_4A
@ DITHERING_SIERRA2_4A
Definition: vf_paletteuse.c:47
PaletteUseContext::transparency_index
int transparency_index
Definition: vf_paletteuse.c:95
internal.h
DITHERING_SIERRA3
@ DITHERING_SIERRA3
Definition: vf_paletteuse.c:48
activate
static int activate(AVFilterContext *ctx)
Definition: vf_paletteuse.c:963
OFFSET
#define OFFSET(x)
Definition: vf_paletteuse.c:113
color_rect::min
int32_t min[3]
Definition: vf_paletteuse.c:518
bprint.h
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:256
cache_node
Definition: vf_paletteuse.c:79
AV_QSORT
#define AV_QSORT(p, num, type, cmp)
Quicksort This sort is fast, and fully inplace but not stable and it is possible to construct input t...
Definition: qsort.h:33
internal.h
color_rect::max
int32_t max[3]
Definition: vf_paletteuse.c:519
cmp_pal_entry
static int cmp_pal_entry(const void *a, const void *b)
Definition: vf_paletteuse.c:637
delta
float delta
Definition: vorbis_enc_data.h:430
av_always_inline
#define av_always_inline
Definition: attributes.h:49
FFMIN
#define FFMIN(a, b)
Definition: macros.h:49
cache_node::entries
struct cached_color * entries
Definition: vf_paletteuse.c:80
av_frame_unref
void av_frame_unref(AVFrame *frame)
Unreference all the buffers referenced by frame and reset the frame fields.
Definition: frame.c:606
AVFilterPad::name
const char * name
Pad name.
Definition: internal.h:39
avpriv_fopen_utf8
FILE * avpriv_fopen_utf8(const char *path, const char *mode)
Open a file using a UTF-8 filename.
Definition: file_open.c:159
PaletteUseContext::diff_mode
int diff_mode
Definition: vf_paletteuse.c:103
color_node::split
int split
Definition: vf_paletteuse.c:68
cached_color::pal_entry
uint8_t pal_entry
Definition: vf_paletteuse.c:76
load_colormap
static void load_colormap(PaletteUseContext *s)
Definition: vf_paletteuse.c:644
PaletteUseContext::total_mean_err
uint64_t total_mean_err
Definition: vf_paletteuse.c:110
diff_mode
diff_mode
Definition: vf_paletteuse.c:54
FLAGS
#define FLAGS
Definition: vf_paletteuse.c:114
AVFilter
Filter definition.
Definition: avfilter.h:166
cache_node::nb_entries
int nb_entries
Definition: vf_paletteuse.c:81
AV_PIX_FMT_PAL8
@ AV_PIX_FMT_PAL8
8 bits with AV_PIX_FMT_RGB32 palette
Definition: pixfmt.h:84
ret
ret
Definition: filter_design.txt:187
FFSWAP
#define FFSWAP(type, a, b)
Definition: macros.h:52
av_bprintf
void av_bprintf(AVBPrint *buf, const char *fmt,...)
Definition: bprint.c:99
DECLARE_CMP_FUNC
#define DECLARE_CMP_FUNC(name)
Definition: vf_paletteuse.c:524
left
Tag MUST be and< 10hcoeff half pel interpolation filter coefficients, hcoeff[0] are the 2 middle coefficients[1] are the next outer ones and so on, resulting in a filter like:...eff[2], hcoeff[1], hcoeff[0], hcoeff[0], hcoeff[1], hcoeff[2] ... the sign of the coefficients is not explicitly stored but alternates after each coeff and coeff[0] is positive, so ...,+,-,+,-,+,+,-,+,-,+,... hcoeff[0] is not explicitly stored but found by subtracting the sum of all stored coefficients with signs from 32 hcoeff[0]=32 - hcoeff[1] - hcoeff[2] - ... a good choice for hcoeff and htaps is htaps=6 hcoeff={40,-10, 2} an alternative which requires more computations at both encoder and decoder side and may or may not be better is htaps=8 hcoeff={42,-14, 6,-2}ref_frames minimum of the number of available reference frames and max_ref_frames for example the first frame after a key frame always has ref_frames=1spatial_decomposition_type wavelet type 0 is a 9/7 symmetric compact integer wavelet 1 is a 5/3 symmetric compact integer wavelet others are reserved stored as delta from last, last is reset to 0 if always_reset||keyframeqlog quality(logarithmic quantizer scale) stored as delta from last, last is reset to 0 if always_reset||keyframemv_scale stored as delta from last, last is reset to 0 if always_reset||keyframe FIXME check that everything works fine if this changes between framesqbias dequantization bias stored as delta from last, last is reset to 0 if always_reset||keyframeblock_max_depth maximum depth of the block tree stored as delta from last, last is reset to 0 if always_reset||keyframequant_table quantization tableHighlevel bitstream structure:==============================--------------------------------------------|Header|--------------------------------------------|------------------------------------|||Block0||||split?||||yes no||||......... intra?||||:Block01 :yes no||||:Block02 :....... ..........||||:Block03 ::y DC ::ref index:||||:Block04 ::cb DC ::motion x :||||......... :cr DC ::motion y :||||....... ..........|||------------------------------------||------------------------------------|||Block1|||...|--------------------------------------------|------------ ------------ ------------|||Y subbands||Cb subbands||Cr subbands||||--- ---||--- ---||--- ---|||||LL0||HL0||||LL0||HL0||||LL0||HL0|||||--- ---||--- ---||--- ---||||--- ---||--- ---||--- ---|||||LH0||HH0||||LH0||HH0||||LH0||HH0|||||--- ---||--- ---||--- ---||||--- ---||--- ---||--- ---|||||HL1||LH1||||HL1||LH1||||HL1||LH1|||||--- ---||--- ---||--- ---||||--- ---||--- ---||--- ---|||||HH1||HL2||||HH1||HL2||||HH1||HL2|||||...||...||...|||------------ ------------ ------------|--------------------------------------------Decoding process:=================------------|||Subbands|------------||||------------|Intra DC||||LL0 subband prediction ------------|\ Dequantization ------------------- \||Reference frames|\ IDWT|------- -------|Motion \|||Frame 0||Frame 1||Compensation . OBMC v -------|------- -------|--------------. \------> Frame n output Frame Frame<----------------------------------/|...|------------------- Range Coder:============Binary Range Coder:------------------- The implemented range coder is an adapted version based upon "Range encoding: an algorithm for removing redundancy from a digitised message." by G. N. N. Martin. The symbols encoded by the Snow range coder are bits(0|1). The associated probabilities are not fix but change depending on the symbol mix seen so far. bit seen|new state ---------+----------------------------------------------- 0|256 - state_transition_table[256 - old_state];1|state_transition_table[old_state];state_transition_table={ 0, 0, 0, 0, 0, 0, 0, 0, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 190, 191, 192, 194, 194, 195, 196, 197, 198, 199, 200, 201, 202, 202, 204, 205, 206, 207, 208, 209, 209, 210, 211, 212, 213, 215, 215, 216, 217, 218, 219, 220, 220, 222, 223, 224, 225, 226, 227, 227, 229, 229, 230, 231, 232, 234, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 248, 0, 0, 0, 0, 0, 0, 0};FIXME Range Coding of integers:------------------------- FIXME Neighboring Blocks:===================left and top are set to the respective blocks unless they are outside of the image in which case they are set to the Null block top-left is set to the top left block unless it is outside of the image in which case it is set to the left block if this block has no larger parent block or it is at the left side of its parent block and the top right block is not outside of the image then the top right block is used for top-right else the top-left block is used Null block y, cb, cr are 128 level, ref, mx and my are 0 Motion Vector Prediction:=========================1. the motion vectors of all the neighboring blocks are scaled to compensate for the difference of reference frames scaled_mv=(mv *(256 *(current_reference+1)/(mv.reference+1))+128)> the median of the scaled left
Definition: snow.txt:386
av_frame_replace
int av_frame_replace(AVFrame *dst, const AVFrame *src)
Ensure the destination frame refers to the same data described by the source frame,...
Definition: frame.c:483
AVFrame::height
int height
Definition: frame.h:446
c2
static const uint64_t c2
Definition: murmur3.c:53
framesync.h
DIFF_MODE_RECTANGLE
@ DIFF_MODE_RECTANGLE
Definition: vf_paletteuse.c:56
AV_PIX_FMT_NONE
@ AV_PIX_FMT_NONE
Definition: pixfmt.h:72
AV_OPT_TYPE_INT
@ AV_OPT_TYPE_INT
Definition: opt.h:235
avfilter.h
cmp_func
int(* cmp_func)(const void *, const void *)
Definition: vf_paletteuse.c:522
PaletteUseContext::map
struct color_node map[AVPALETTE_COUNT]
Definition: vf_paletteuse.c:93
L
#define L(x)
Definition: vpx_arith.h:36
av_clip_uint8
#define av_clip_uint8
Definition: common.h:105
AVFilterContext
An instance of a filter.
Definition: avfilter.h:407
AVMEDIA_TYPE_VIDEO
@ AVMEDIA_TYPE_VIDEO
Definition: avutil.h:201
mem.h
CACHE_SIZE
#define CACHE_SIZE
Definition: vf_paletteuse.c:72
map
const VDPAUPixFmtMap * map
Definition: hwcontext_vdpau.c:71
color::pal_id
uint8_t pal_id
Definition: vf_paletteuse.c:514
scale
static void scale(int *out, const int *in, const int w, const int h, const int shift)
Definition: intra.c:291
DITHERING_BURKES
@ DITHERING_BURKES
Definition: vf_paletteuse.c:49
AV_OPT_TYPE_BOOL
@ AV_OPT_TYPE_BOOL
Definition: opt.h:251
FILTER_OUTPUTS
#define FILTER_OUTPUTS(array)
Definition: internal.h:183
DEFINE_SET_FRAME
#define DEFINE_SET_FRAME(name, value)
Definition: vf_paletteuse.c:905
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:34
src
INIT_CLIP pixel * src
Definition: h264pred_template.c:418
DITHERING_ATKINSON
@ DITHERING_ATKINSON
Definition: vf_paletteuse.c:50
get_color_from_srgb
static struct color_info get_color_from_srgb(uint32_t srgb)
Definition: vf_paletteuse.c:183
d
d
Definition: ffmpeg_filter.c:424
paletteuse_outputs
static const AVFilterPad paletteuse_outputs[]
Definition: vf_paletteuse.c:991
int32_t
int32_t
Definition: audioconvert.c:56
PaletteUseContext::calc_mean_err
int calc_mean_err
Definition: vf_paletteuse.c:109
AVERROR_BUG
#define AVERROR_BUG
Internal bug, also see AVERROR_BUG2.
Definition: error.h:52
AVFrame::linesize
int linesize[AV_NUM_DATA_POINTERS]
For video, a positive or negative value, which is typically indicating the size in bytes of each pict...
Definition: frame.h:419
av_log
#define av_log(a,...)
Definition: tableprint_vlc.h:27
h
h
Definition: vp9dsp_template.c:2038
ff_framesync_activate
int ff_framesync_activate(FFFrameSync *fs)
Examine the frames in the filter's input and try to produce output.
Definition: framesync.c:355
color_node::left_id
int left_id
Definition: vf_paletteuse.c:69
color_node
Definition: vf_paletteuse.c:65
AVFILTER_DEFINE_CLASS
AVFILTER_DEFINE_CLASS(paletteuse)
AV_OPT_TYPE_STRING
@ AV_OPT_TYPE_STRING
Definition: opt.h:239
ff_framesync_dualinput_get_writable
int ff_framesync_dualinput_get_writable(FFFrameSync *fs, AVFrame **f0, AVFrame **f1)
Same as ff_framesync_dualinput_get(), but make sure that f0 is writable.
Definition: framesync.c:413
int
int
Definition: ffmpeg_filter.c:424
PaletteUseContext::last_in
AVFrame * last_in
Definition: vf_paletteuse.c:104
nearest_color::node_pos
int node_pos
Definition: vf_paletteuse.c:191
AV_OPT_TYPE_CONST
@ AV_OPT_TYPE_CONST
Definition: opt.h:244
paletteuse_inputs
static const AVFilterPad paletteuse_inputs[]
Definition: vf_paletteuse.c:980
load_palette
static void load_palette(PaletteUseContext *s, const AVFrame *palette_frame)
Definition: vf_paletteuse.c:845
cached_color
Definition: vf_paletteuse.c:74
ff_srgb_u8_to_oklab_int
struct Lab ff_srgb_u8_to_oklab_int(uint32_t srgb)
sRGB (non-linear) to OkLab conversion
Definition: palette.c:170
nearest_color::dist_sqd
int64_t dist_sqd
Definition: vf_paletteuse.c:192
NB_DIFF_MODE
@ NB_DIFF_MODE
Definition: vf_paletteuse.c:57
Lab::L
int32_t L
Definition: palette.h:31
dither
static const uint8_t dither[8][8]
Definition: vf_fspp.c:61