LCOV - code coverage report
Current view: top level - libavfilter - vf_paletteuse.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 372 560 66.4 %
Date: 2017-12-15 11:05:35 Functions: 27 50 54.0 %

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

Generated by: LCOV version 1.13