Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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