avfilter/af_afir: do not over allocate fft buffer
[ffmpeg.git] / libavfilter / vf_minterpolate.c
1 /**
2  * Copyright (c) 2014-2015 Michael Niedermayer <michaelni@gmx.at>
3  * Copyright (c) 2016 Davinder Singh (DSM_) <ds.mudhar<@gmail.com>
4  *
5  * This file is part of FFmpeg.
6  *
7  * FFmpeg is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * FFmpeg is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with FFmpeg; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21
22 #include "motion_estimation.h"
23 #include "libavcodec/mathops.h"
24 #include "libavutil/avassert.h"
25 #include "libavutil/common.h"
26 #include "libavutil/motion_vector.h"
27 #include "libavutil/opt.h"
28 #include "libavutil/pixdesc.h"
29 #include "avfilter.h"
30 #include "formats.h"
31 #include "internal.h"
32 #include "video.h"
33 #include "scene_sad.h"
34
35 #define ME_MODE_BIDIR 0
36 #define ME_MODE_BILAT 1
37
38 #define MC_MODE_OBMC 0
39 #define MC_MODE_AOBMC 1
40
41 #define SCD_METHOD_NONE 0
42 #define SCD_METHOD_FDIFF 1
43
44 #define NB_FRAMES 4
45 #define NB_PIXEL_MVS 32
46 #define NB_CLUSTERS 128
47
48 #define ALPHA_MAX 1024
49 #define CLUSTER_THRESHOLD 4
50 #define PX_WEIGHT_MAX 255
51 #define COST_PRED_SCALE 64
52
53 static const uint8_t obmc_linear32[1024] = {
54   0,  0,  0,  0,  4,  4,  4,  4,  4,  4,  4,  4,  8,  8,  8,  8,  8,  8,  8,  8,  4,  4,  4,  4,  4,  4,  4,  4,  0,  0,  0,  0,
55   0,  4,  4,  4,  8,  8,  8, 12, 12, 16, 16, 16, 20, 20, 20, 24, 24, 20, 20, 20, 16, 16, 16, 12, 12,  8,  8,  8,  4,  4,  4,  0,
56   0,  4,  8,  8, 12, 12, 16, 20, 20, 24, 28, 28, 32, 32, 36, 40, 40, 36, 32, 32, 28, 28, 24, 20, 20, 16, 12, 12,  8,  8,  4,  0,
57   0,  4,  8, 12, 16, 20, 24, 28, 28, 32, 36, 40, 44, 48, 52, 56, 56, 52, 48, 44, 40, 36, 32, 28, 28, 24, 20, 16, 12,  8,  4,  0,
58   4,  8, 12, 16, 20, 24, 28, 32, 40, 44, 48, 52, 56, 60, 64, 68, 68, 64, 60, 56, 52, 48, 44, 40, 32, 28, 24, 20, 16, 12,  8,  4,
59   4,  8, 12, 20, 24, 32, 36, 40, 48, 52, 56, 64, 68, 76, 80, 84, 84, 80, 76, 68, 64, 56, 52, 48, 40, 36, 32, 24, 20, 12,  8,  4,
60   4,  8, 16, 24, 28, 36, 44, 48, 56, 60, 68, 76, 80, 88, 96,100,100, 96, 88, 80, 76, 68, 60, 56, 48, 44, 36, 28, 24, 16,  8,  4,
61   4, 12, 20, 28, 32, 40, 48, 56, 64, 72, 80, 88, 92,100,108,116,116,108,100, 92, 88, 80, 72, 64, 56, 48, 40, 32, 28, 20, 12,  4,
62   4, 12, 20, 28, 40, 48, 56, 64, 72, 80, 88, 96,108,116,124,132,132,124,116,108, 96, 88, 80, 72, 64, 56, 48, 40, 28, 20, 12,  4,
63   4, 16, 24, 32, 44, 52, 60, 72, 80, 92,100,108,120,128,136,148,148,136,128,120,108,100, 92, 80, 72, 60, 52, 44, 32, 24, 16,  4,
64   4, 16, 28, 36, 48, 56, 68, 80, 88,100,112,120,132,140,152,164,164,152,140,132,120,112,100, 88, 80, 68, 56, 48, 36, 28, 16,  4,
65   4, 16, 28, 40, 52, 64, 76, 88, 96,108,120,132,144,156,168,180,180,168,156,144,132,120,108, 96, 88, 76, 64, 52, 40, 28, 16,  4,
66   8, 20, 32, 44, 56, 68, 80, 92,108,120,132,144,156,168,180,192,192,180,168,156,144,132,120,108, 92, 80, 68, 56, 44, 32, 20,  8,
67   8, 20, 32, 48, 60, 76, 88,100,116,128,140,156,168,184,196,208,208,196,184,168,156,140,128,116,100, 88, 76, 60, 48, 32, 20,  8,
68   8, 20, 36, 52, 64, 80, 96,108,124,136,152,168,180,196,212,224,224,212,196,180,168,152,136,124,108, 96, 80, 64, 52, 36, 20,  8,
69   8, 24, 40, 56, 68, 84,100,116,132,148,164,180,192,208,224,240,240,224,208,192,180,164,148,132,116,100, 84, 68, 56, 40, 24,  8,
70   8, 24, 40, 56, 68, 84,100,116,132,148,164,180,192,208,224,240,240,224,208,192,180,164,148,132,116,100, 84, 68, 56, 40, 24,  8,
71   8, 20, 36, 52, 64, 80, 96,108,124,136,152,168,180,196,212,224,224,212,196,180,168,152,136,124,108, 96, 80, 64, 52, 36, 20,  8,
72   8, 20, 32, 48, 60, 76, 88,100,116,128,140,156,168,184,196,208,208,196,184,168,156,140,128,116,100, 88, 76, 60, 48, 32, 20,  8,
73   8, 20, 32, 44, 56, 68, 80, 92,108,120,132,144,156,168,180,192,192,180,168,156,144,132,120,108, 92, 80, 68, 56, 44, 32, 20,  8,
74   4, 16, 28, 40, 52, 64, 76, 88, 96,108,120,132,144,156,168,180,180,168,156,144,132,120,108, 96, 88, 76, 64, 52, 40, 28, 16,  4,
75   4, 16, 28, 36, 48, 56, 68, 80, 88,100,112,120,132,140,152,164,164,152,140,132,120,112,100, 88, 80, 68, 56, 48, 36, 28, 16,  4,
76   4, 16, 24, 32, 44, 52, 60, 72, 80, 92,100,108,120,128,136,148,148,136,128,120,108,100, 92, 80, 72, 60, 52, 44, 32, 24, 16,  4,
77   4, 12, 20, 28, 40, 48, 56, 64, 72, 80, 88, 96,108,116,124,132,132,124,116,108, 96, 88, 80, 72, 64, 56, 48, 40, 28, 20, 12,  4,
78   4, 12, 20, 28, 32, 40, 48, 56, 64, 72, 80, 88, 92,100,108,116,116,108,100, 92, 88, 80, 72, 64, 56, 48, 40, 32, 28, 20, 12,  4,
79   4,  8, 16, 24, 28, 36, 44, 48, 56, 60, 68, 76, 80, 88, 96,100,100, 96, 88, 80, 76, 68, 60, 56, 48, 44, 36, 28, 24, 16,  8,  4,
80   4,  8, 12, 20, 24, 32, 36, 40, 48, 52, 56, 64, 68, 76, 80, 84, 84, 80, 76, 68, 64, 56, 52, 48, 40, 36, 32, 24, 20, 12,  8,  4,
81   4,  8, 12, 16, 20, 24, 28, 32, 40, 44, 48, 52, 56, 60, 64, 68, 68, 64, 60, 56, 52, 48, 44, 40, 32, 28, 24, 20, 16, 12,  8,  4,
82   0,  4,  8, 12, 16, 20, 24, 28, 28, 32, 36, 40, 44, 48, 52, 56, 56, 52, 48, 44, 40, 36, 32, 28, 28, 24, 20, 16, 12,  8,  4,  0,
83   0,  4,  8,  8, 12, 12, 16, 20, 20, 24, 28, 28, 32, 32, 36, 40, 40, 36, 32, 32, 28, 28, 24, 20, 20, 16, 12, 12,  8,  8,  4,  0,
84   0,  4,  4,  4,  8,  8,  8, 12, 12, 16, 16, 16, 20, 20, 20, 24, 24, 20, 20, 20, 16, 16, 16, 12, 12,  8,  8,  8,  4,  4,  4,  0,
85   0,  0,  0,  0,  4,  4,  4,  4,  4,  4,  4,  4,  8,  8,  8,  8,  8,  8,  8,  8,  4,  4,  4,  4,  4,  4,  4,  4,  0,  0,  0,  0,
86 };
87
88 static const uint8_t obmc_linear16[256] = {
89   0,  4,  4,  8,  8, 12, 12, 16, 16, 12, 12,  8,  8,  4,  4,  0,
90   4,  8, 16, 20, 28, 32, 40, 44, 44, 40, 32, 28, 20, 16,  8,  4,
91   4, 16, 24, 36, 44, 56, 64, 76, 76, 64, 56, 44, 36, 24, 16,  4,
92   8, 20, 36, 48, 64, 76, 92,104,104, 92, 76, 64, 48, 36, 20,  8,
93   8, 28, 44, 64, 80,100,116,136,136,116,100, 80, 64, 44, 28,  8,
94  12, 32, 56, 76,100,120,144,164,164,144,120,100, 76, 56, 32, 12,
95  12, 40, 64, 92,116,144,168,196,196,168,144,116, 92, 64, 40, 12,
96  16, 44, 76,104,136,164,196,224,224,196,164,136,104, 76, 44, 16,
97  16, 44, 76,104,136,164,196,224,224,196,164,136,104, 76, 44, 16,
98  12, 40, 64, 92,116,144,168,196,196,168,144,116, 92, 64, 40, 12,
99  12, 32, 56, 76,100,120,144,164,164,144,120,100, 76, 56, 32, 12,
100   8, 28, 44, 64, 80,100,116,136,136,116,100, 80, 64, 44, 28,  8,
101   8, 20, 36, 48, 64, 76, 92,104,104, 92, 76, 64, 48, 36, 20,  8,
102   4, 16, 24, 36, 44, 56, 64, 76, 76, 64, 56, 44, 36, 24, 16,  4,
103   4,  8, 16, 20, 28, 32, 40, 44, 44, 40, 32, 28, 20, 16,  8,  4,
104   0,  4,  4,  8,  8, 12, 12, 16, 16, 12, 12,  8,  8,  4,  4,  0,
105 };
106
107 static const uint8_t obmc_linear8[64] = {
108   4, 12, 20, 28, 28, 20, 12,  4,
109  12, 36, 60, 84, 84, 60, 36, 12,
110  20, 60,100,140,140,100, 60, 20,
111  28, 84,140,196,196,140, 84, 28,
112  28, 84,140,196,196,140, 84, 28,
113  20, 60,100,140,140,100, 60, 20,
114  12, 36, 60, 84, 84, 60, 36, 12,
115   4, 12, 20, 28, 28, 20, 12,  4,
116 };
117
118 static const uint8_t obmc_linear4[16] = {
119  16, 48, 48, 16,
120  48,144,144, 48,
121  48,144,144, 48,
122  16, 48, 48, 16,
123 };
124
125 static const uint8_t * const obmc_tab_linear[4]= {
126     obmc_linear32, obmc_linear16, obmc_linear8, obmc_linear4
127 };
128
129 enum MIMode {
130     MI_MODE_DUP         = 0,
131     MI_MODE_BLEND       = 1,
132     MI_MODE_MCI         = 2,
133 };
134
135 typedef struct Cluster {
136     int64_t sum[2];
137     int nb;
138 } Cluster;
139
140 typedef struct Block {
141     int16_t mvs[2][2];
142     int cid;
143     uint64_t sbad;
144     int sb;
145     struct Block *subs;
146 } Block;
147
148 typedef struct PixelMVS {
149     int16_t mvs[NB_PIXEL_MVS][2];
150 } PixelMVS;
151
152 typedef struct PixelWeights {
153     uint32_t weights[NB_PIXEL_MVS];
154 } PixelWeights;
155
156 typedef struct PixelRefs {
157     int8_t refs[NB_PIXEL_MVS];
158     int nb;
159 } PixelRefs;
160
161 typedef struct Frame {
162     AVFrame *avf;
163     Block *blocks;
164 } Frame;
165
166 typedef struct MIContext {
167     const AVClass *class;
168     AVMotionEstContext me_ctx;
169     AVRational frame_rate;
170     enum MIMode mi_mode;
171     int mc_mode;
172     int me_mode;
173     int me_method;
174     int mb_size;
175     int search_param;
176     int vsbmc;
177
178     Frame frames[NB_FRAMES];
179     Cluster clusters[NB_CLUSTERS];
180     Block *int_blocks;
181     PixelMVS *pixel_mvs;
182     PixelWeights *pixel_weights;
183     PixelRefs *pixel_refs;
184     int (*mv_table[3])[2][2];
185     int64_t out_pts;
186     int b_width, b_height, b_count;
187     int log2_mb_size;
188
189     int scd_method;
190     int scene_changed;
191     ff_scene_sad_fn sad;
192     double prev_mafd;
193     double scd_threshold;
194
195     int log2_chroma_w;
196     int log2_chroma_h;
197     int nb_planes;
198 } MIContext;
199
200 #define OFFSET(x) offsetof(MIContext, x)
201 #define FLAGS AV_OPT_FLAG_VIDEO_PARAM|AV_OPT_FLAG_FILTERING_PARAM
202 #define CONST(name, help, val, unit) { name, help, 0, AV_OPT_TYPE_CONST, {.i64=val}, 0, 0, FLAGS, unit }
203
204 static const AVOption minterpolate_options[] = {
205     { "fps", "output's frame rate", OFFSET(frame_rate), AV_OPT_TYPE_VIDEO_RATE, {.str = "60"}, 0, INT_MAX, FLAGS },
206     { "mi_mode", "motion interpolation mode", OFFSET(mi_mode), AV_OPT_TYPE_INT, {.i64 = MI_MODE_MCI}, MI_MODE_DUP, MI_MODE_MCI, FLAGS, "mi_mode" },
207         CONST("dup",    "duplicate frames",                     MI_MODE_DUP,            "mi_mode"),
208         CONST("blend",  "blend frames",                         MI_MODE_BLEND,          "mi_mode"),
209         CONST("mci",    "motion compensated interpolation",     MI_MODE_MCI,            "mi_mode"),
210     { "mc_mode", "motion compensation mode", OFFSET(mc_mode), AV_OPT_TYPE_INT, {.i64 = MC_MODE_OBMC}, MC_MODE_OBMC, MC_MODE_AOBMC, FLAGS, "mc_mode" },
211         CONST("obmc",   "overlapped block motion compensation", MC_MODE_OBMC,           "mc_mode"),
212         CONST("aobmc",  "adaptive overlapped block motion compensation", MC_MODE_AOBMC, "mc_mode"),
213     { "me_mode", "motion estimation mode", OFFSET(me_mode), AV_OPT_TYPE_INT, {.i64 = ME_MODE_BILAT}, ME_MODE_BIDIR, ME_MODE_BILAT, FLAGS, "me_mode" },
214         CONST("bidir",  "bidirectional motion estimation",      ME_MODE_BIDIR,          "me_mode"),
215         CONST("bilat",  "bilateral motion estimation",          ME_MODE_BILAT,          "me_mode"),
216     { "me", "motion estimation method", OFFSET(me_method), AV_OPT_TYPE_INT, {.i64 = AV_ME_METHOD_EPZS}, AV_ME_METHOD_ESA, AV_ME_METHOD_UMH, FLAGS, "me" },
217         CONST("esa",    "exhaustive search",                    AV_ME_METHOD_ESA,       "me"),
218         CONST("tss",    "three step search",                    AV_ME_METHOD_TSS,       "me"),
219         CONST("tdls",   "two dimensional logarithmic search",   AV_ME_METHOD_TDLS,      "me"),
220         CONST("ntss",   "new three step search",                AV_ME_METHOD_NTSS,      "me"),
221         CONST("fss",    "four step search",                     AV_ME_METHOD_FSS,       "me"),
222         CONST("ds",     "diamond search",                       AV_ME_METHOD_DS,        "me"),
223         CONST("hexbs",  "hexagon-based search",                 AV_ME_METHOD_HEXBS,     "me"),
224         CONST("epzs",   "enhanced predictive zonal search",     AV_ME_METHOD_EPZS,      "me"),
225         CONST("umh",    "uneven multi-hexagon search",          AV_ME_METHOD_UMH,       "me"),
226     { "mb_size", "macroblock size", OFFSET(mb_size), AV_OPT_TYPE_INT, {.i64 = 16}, 4, 16, FLAGS },
227     { "search_param", "search parameter", OFFSET(search_param), AV_OPT_TYPE_INT, {.i64 = 32}, 4, INT_MAX, FLAGS },
228     { "vsbmc", "variable-size block motion compensation", OFFSET(vsbmc), AV_OPT_TYPE_INT, {.i64 = 0}, 0, 1, FLAGS },
229     { "scd", "scene change detection method", OFFSET(scd_method), AV_OPT_TYPE_INT, {.i64 = SCD_METHOD_FDIFF}, SCD_METHOD_NONE, SCD_METHOD_FDIFF, FLAGS, "scene" },
230         CONST("none",   "disable detection",                    SCD_METHOD_NONE,        "scene"),
231         CONST("fdiff",  "frame difference",                     SCD_METHOD_FDIFF,       "scene"),
232     { "scd_threshold", "scene change threshold", OFFSET(scd_threshold), AV_OPT_TYPE_DOUBLE, {.dbl = 5.0}, 0, 100.0, FLAGS },
233     { NULL }
234 };
235
236 AVFILTER_DEFINE_CLASS(minterpolate);
237
238 static int query_formats(AVFilterContext *ctx)
239 {
240     static const enum AVPixelFormat pix_fmts[] = {
241         AV_PIX_FMT_YUV410P, AV_PIX_FMT_YUV411P,
242         AV_PIX_FMT_YUV420P, AV_PIX_FMT_YUV422P,
243         AV_PIX_FMT_YUV440P, AV_PIX_FMT_YUV444P,
244         AV_PIX_FMT_YUVJ444P, AV_PIX_FMT_YUVJ440P,
245         AV_PIX_FMT_YUVJ422P, AV_PIX_FMT_YUVJ420P,
246         AV_PIX_FMT_YUVJ411P,
247         AV_PIX_FMT_YUVA420P, AV_PIX_FMT_YUVA422P, AV_PIX_FMT_YUVA444P,
248         AV_PIX_FMT_GRAY8,
249         AV_PIX_FMT_NONE
250     };
251
252     AVFilterFormats *fmts_list = ff_make_format_list(pix_fmts);
253     if (!fmts_list)
254         return AVERROR(ENOMEM);
255     return ff_set_common_formats(ctx, fmts_list);
256 }
257
258 static uint64_t get_sbad(AVMotionEstContext *me_ctx, int x, int y, int x_mv, int y_mv)
259 {
260     uint8_t *data_cur = me_ctx->data_cur;
261     uint8_t *data_next = me_ctx->data_ref;
262     int linesize = me_ctx->linesize;
263     int mv_x1 = x_mv - x;
264     int mv_y1 = y_mv - y;
265     int mv_x, mv_y, i, j;
266     uint64_t sbad = 0;
267
268     x = av_clip(x, me_ctx->x_min, me_ctx->x_max);
269     y = av_clip(y, me_ctx->y_min, me_ctx->y_max);
270     mv_x = av_clip(x_mv - x, -FFMIN(x - me_ctx->x_min, me_ctx->x_max - x), FFMIN(x - me_ctx->x_min, me_ctx->x_max - x));
271     mv_y = av_clip(y_mv - y, -FFMIN(y - me_ctx->y_min, me_ctx->y_max - y), FFMIN(y - me_ctx->y_min, me_ctx->y_max - y));
272
273     data_cur += (y + mv_y) * linesize;
274     data_next += (y - mv_y) * linesize;
275
276     for (j = 0; j < me_ctx->mb_size; j++)
277         for (i = 0; i < me_ctx->mb_size; i++)
278             sbad += FFABS(data_cur[x + mv_x + i + j * linesize] - data_next[x - mv_x + i + j * linesize]);
279
280     return sbad + (FFABS(mv_x1 - me_ctx->pred_x) + FFABS(mv_y1 - me_ctx->pred_y)) * COST_PRED_SCALE;
281 }
282
283 static uint64_t get_sbad_ob(AVMotionEstContext *me_ctx, int x, int y, int x_mv, int y_mv)
284 {
285     uint8_t *data_cur = me_ctx->data_cur;
286     uint8_t *data_next = me_ctx->data_ref;
287     int linesize = me_ctx->linesize;
288     int x_min = me_ctx->x_min + me_ctx->mb_size / 2;
289     int x_max = me_ctx->x_max - me_ctx->mb_size / 2;
290     int y_min = me_ctx->y_min + me_ctx->mb_size / 2;
291     int y_max = me_ctx->y_max - me_ctx->mb_size / 2;
292     int mv_x1 = x_mv - x;
293     int mv_y1 = y_mv - y;
294     int mv_x, mv_y, i, j;
295     uint64_t sbad = 0;
296
297     x = av_clip(x, x_min, x_max);
298     y = av_clip(y, y_min, y_max);
299     mv_x = av_clip(x_mv - x, -FFMIN(x - x_min, x_max - x), FFMIN(x - x_min, x_max - x));
300     mv_y = av_clip(y_mv - y, -FFMIN(y - y_min, y_max - y), FFMIN(y - y_min, y_max - y));
301
302     for (j = -me_ctx->mb_size / 2; j < me_ctx->mb_size * 3 / 2; j++)
303         for (i = -me_ctx->mb_size / 2; i < me_ctx->mb_size * 3 / 2; i++)
304             sbad += FFABS(data_cur[x + mv_x + i + (y + mv_y + j) * linesize] - data_next[x - mv_x + i + (y - mv_y + j) * linesize]);
305
306     return sbad + (FFABS(mv_x1 - me_ctx->pred_x) + FFABS(mv_y1 - me_ctx->pred_y)) * COST_PRED_SCALE;
307 }
308
309 static uint64_t get_sad_ob(AVMotionEstContext *me_ctx, int x, int y, int x_mv, int y_mv)
310 {
311     uint8_t *data_ref = me_ctx->data_ref;
312     uint8_t *data_cur = me_ctx->data_cur;
313     int linesize = me_ctx->linesize;
314     int x_min = me_ctx->x_min + me_ctx->mb_size / 2;
315     int x_max = me_ctx->x_max - me_ctx->mb_size / 2;
316     int y_min = me_ctx->y_min + me_ctx->mb_size / 2;
317     int y_max = me_ctx->y_max - me_ctx->mb_size / 2;
318     int mv_x = x_mv - x;
319     int mv_y = y_mv - y;
320     int i, j;
321     uint64_t sad = 0;
322
323     x = av_clip(x, x_min, x_max);
324     y = av_clip(y, y_min, y_max);
325     x_mv = av_clip(x_mv, x_min, x_max);
326     y_mv = av_clip(y_mv, y_min, y_max);
327
328     for (j = -me_ctx->mb_size / 2; j < me_ctx->mb_size * 3 / 2; j++)
329         for (i = -me_ctx->mb_size / 2; i < me_ctx->mb_size * 3 / 2; i++)
330             sad += FFABS(data_ref[x_mv + i + (y_mv + j) * linesize] - data_cur[x + i + (y + j) * linesize]);
331
332     return sad + (FFABS(mv_x - me_ctx->pred_x) + FFABS(mv_y - me_ctx->pred_y)) * COST_PRED_SCALE;
333 }
334
335 static int config_input(AVFilterLink *inlink)
336 {
337     MIContext *mi_ctx = inlink->dst->priv;
338     AVMotionEstContext *me_ctx = &mi_ctx->me_ctx;
339     const AVPixFmtDescriptor *desc = av_pix_fmt_desc_get(inlink->format);
340     const int height = inlink->h;
341     const int width  = inlink->w;
342     int i, ret = 0;
343
344     mi_ctx->log2_chroma_h = desc->log2_chroma_h;
345     mi_ctx->log2_chroma_w = desc->log2_chroma_w;
346
347     mi_ctx->nb_planes = av_pix_fmt_count_planes(inlink->format);
348
349     mi_ctx->log2_mb_size = av_ceil_log2_c(mi_ctx->mb_size);
350     mi_ctx->mb_size = 1 << mi_ctx->log2_mb_size;
351
352     mi_ctx->b_width  = width >> mi_ctx->log2_mb_size;
353     mi_ctx->b_height = height >> mi_ctx->log2_mb_size;
354     mi_ctx->b_count = mi_ctx->b_width * mi_ctx->b_height;
355
356     for (i = 0; i < NB_FRAMES; i++) {
357         Frame *frame = &mi_ctx->frames[i];
358         frame->blocks = av_mallocz_array(mi_ctx->b_count, sizeof(Block));
359         if (!frame->blocks)
360             return AVERROR(ENOMEM);
361     }
362
363     if (mi_ctx->mi_mode == MI_MODE_MCI) {
364         mi_ctx->pixel_mvs = av_mallocz_array(width * height, sizeof(PixelMVS));
365         mi_ctx->pixel_weights = av_mallocz_array(width * height, sizeof(PixelWeights));
366         mi_ctx->pixel_refs = av_mallocz_array(width * height, sizeof(PixelRefs));
367         if (!mi_ctx->pixel_mvs || !mi_ctx->pixel_weights || !mi_ctx->pixel_refs) {
368             ret = AVERROR(ENOMEM);
369             goto fail;
370         }
371
372         if (mi_ctx->me_mode == ME_MODE_BILAT)
373             if (!(mi_ctx->int_blocks = av_mallocz_array(mi_ctx->b_count, sizeof(Block))))
374                 return AVERROR(ENOMEM);
375
376         if (mi_ctx->me_method == AV_ME_METHOD_EPZS) {
377             for (i = 0; i < 3; i++) {
378                 mi_ctx->mv_table[i] = av_mallocz_array(mi_ctx->b_count, sizeof(*mi_ctx->mv_table[0]));
379                 if (!mi_ctx->mv_table[i])
380                     return AVERROR(ENOMEM);
381             }
382         }
383     }
384
385     if (mi_ctx->scd_method == SCD_METHOD_FDIFF) {
386         mi_ctx->sad = ff_scene_sad_get_fn(8);
387         if (!mi_ctx->sad)
388             return AVERROR(EINVAL);
389     }
390
391     ff_me_init_context(me_ctx, mi_ctx->mb_size, mi_ctx->search_param, width, height, 0, (mi_ctx->b_width - 1) << mi_ctx->log2_mb_size, 0, (mi_ctx->b_height - 1) << mi_ctx->log2_mb_size);
392
393     if (mi_ctx->me_mode == ME_MODE_BIDIR)
394         me_ctx->get_cost = &get_sad_ob;
395     else if (mi_ctx->me_mode == ME_MODE_BILAT)
396         me_ctx->get_cost = &get_sbad_ob;
397
398     return 0;
399 fail:
400     for (i = 0; i < NB_FRAMES; i++)
401         av_freep(&mi_ctx->frames[i].blocks);
402     av_freep(&mi_ctx->pixel_mvs);
403     av_freep(&mi_ctx->pixel_weights);
404     av_freep(&mi_ctx->pixel_refs);
405     return ret;
406 }
407
408 static int config_output(AVFilterLink *outlink)
409 {
410     MIContext *mi_ctx = outlink->src->priv;
411
412     outlink->frame_rate = mi_ctx->frame_rate;
413     outlink->time_base  = av_inv_q(mi_ctx->frame_rate);
414
415     return 0;
416 }
417
418 #define ADD_PRED(preds, px, py)\
419     do {\
420         preds.mvs[preds.nb][0] = px;\
421         preds.mvs[preds.nb][1] = py;\
422         preds.nb++;\
423     } while(0)
424
425 static void search_mv(MIContext *mi_ctx, Block *blocks, int mb_x, int mb_y, int dir)
426 {
427     AVMotionEstContext *me_ctx = &mi_ctx->me_ctx;
428     AVMotionEstPredictor *preds = me_ctx->preds;
429     Block *block = &blocks[mb_x + mb_y * mi_ctx->b_width];
430
431     const int x_mb = mb_x << mi_ctx->log2_mb_size;
432     const int y_mb = mb_y << mi_ctx->log2_mb_size;
433     const int mb_i = mb_x + mb_y * mi_ctx->b_width;
434     int mv[2] = {x_mb, y_mb};
435
436     switch (mi_ctx->me_method) {
437         case AV_ME_METHOD_ESA:
438             ff_me_search_esa(me_ctx, x_mb, y_mb, mv);
439             break;
440         case AV_ME_METHOD_TSS:
441             ff_me_search_tss(me_ctx, x_mb, y_mb, mv);
442             break;
443         case AV_ME_METHOD_TDLS:
444             ff_me_search_tdls(me_ctx, x_mb, y_mb, mv);
445             break;
446         case AV_ME_METHOD_NTSS:
447             ff_me_search_ntss(me_ctx, x_mb, y_mb, mv);
448             break;
449         case AV_ME_METHOD_FSS:
450             ff_me_search_fss(me_ctx, x_mb, y_mb, mv);
451             break;
452         case AV_ME_METHOD_DS:
453             ff_me_search_ds(me_ctx, x_mb, y_mb, mv);
454             break;
455         case AV_ME_METHOD_HEXBS:
456             ff_me_search_hexbs(me_ctx, x_mb, y_mb, mv);
457             break;
458         case AV_ME_METHOD_EPZS:
459
460             preds[0].nb = 0;
461             preds[1].nb = 0;
462
463             ADD_PRED(preds[0], 0, 0);
464
465             //left mb in current frame
466             if (mb_x > 0)
467                 ADD_PRED(preds[0], mi_ctx->mv_table[0][mb_i - 1][dir][0], mi_ctx->mv_table[0][mb_i - 1][dir][1]);
468
469             //top mb in current frame
470             if (mb_y > 0)
471                 ADD_PRED(preds[0], mi_ctx->mv_table[0][mb_i - mi_ctx->b_width][dir][0], mi_ctx->mv_table[0][mb_i - mi_ctx->b_width][dir][1]);
472
473             //top-right mb in current frame
474             if (mb_y > 0 && mb_x + 1 < mi_ctx->b_width)
475                 ADD_PRED(preds[0], mi_ctx->mv_table[0][mb_i - mi_ctx->b_width + 1][dir][0], mi_ctx->mv_table[0][mb_i - mi_ctx->b_width + 1][dir][1]);
476
477             //median predictor
478             if (preds[0].nb == 4) {
479                 me_ctx->pred_x = mid_pred(preds[0].mvs[1][0], preds[0].mvs[2][0], preds[0].mvs[3][0]);
480                 me_ctx->pred_y = mid_pred(preds[0].mvs[1][1], preds[0].mvs[2][1], preds[0].mvs[3][1]);
481             } else if (preds[0].nb == 3) {
482                 me_ctx->pred_x = mid_pred(0, preds[0].mvs[1][0], preds[0].mvs[2][0]);
483                 me_ctx->pred_y = mid_pred(0, preds[0].mvs[1][1], preds[0].mvs[2][1]);
484             } else if (preds[0].nb == 2) {
485                 me_ctx->pred_x = preds[0].mvs[1][0];
486                 me_ctx->pred_y = preds[0].mvs[1][1];
487             } else {
488                 me_ctx->pred_x = 0;
489                 me_ctx->pred_y = 0;
490             }
491
492             //collocated mb in prev frame
493             ADD_PRED(preds[0], mi_ctx->mv_table[1][mb_i][dir][0], mi_ctx->mv_table[1][mb_i][dir][1]);
494
495             //accelerator motion vector of collocated block in prev frame
496             ADD_PRED(preds[1], mi_ctx->mv_table[1][mb_i][dir][0] + (mi_ctx->mv_table[1][mb_i][dir][0] - mi_ctx->mv_table[2][mb_i][dir][0]),
497                                mi_ctx->mv_table[1][mb_i][dir][1] + (mi_ctx->mv_table[1][mb_i][dir][1] - mi_ctx->mv_table[2][mb_i][dir][1]));
498
499             //left mb in prev frame
500             if (mb_x > 0)
501                 ADD_PRED(preds[1], mi_ctx->mv_table[1][mb_i - 1][dir][0], mi_ctx->mv_table[1][mb_i - 1][dir][1]);
502
503             //top mb in prev frame
504             if (mb_y > 0)
505                 ADD_PRED(preds[1], mi_ctx->mv_table[1][mb_i - mi_ctx->b_width][dir][0], mi_ctx->mv_table[1][mb_i - mi_ctx->b_width][dir][1]);
506
507             //right mb in prev frame
508             if (mb_x + 1 < mi_ctx->b_width)
509                 ADD_PRED(preds[1], mi_ctx->mv_table[1][mb_i + 1][dir][0], mi_ctx->mv_table[1][mb_i + 1][dir][1]);
510
511             //bottom mb in prev frame
512             if (mb_y + 1 < mi_ctx->b_height)
513                 ADD_PRED(preds[1], mi_ctx->mv_table[1][mb_i + mi_ctx->b_width][dir][0], mi_ctx->mv_table[1][mb_i + mi_ctx->b_width][dir][1]);
514
515             ff_me_search_epzs(me_ctx, x_mb, y_mb, mv);
516
517             mi_ctx->mv_table[0][mb_i][dir][0] = mv[0] - x_mb;
518             mi_ctx->mv_table[0][mb_i][dir][1] = mv[1] - y_mb;
519
520             break;
521         case AV_ME_METHOD_UMH:
522
523             preds[0].nb = 0;
524
525             ADD_PRED(preds[0], 0, 0);
526
527             //left mb in current frame
528             if (mb_x > 0)
529                 ADD_PRED(preds[0], blocks[mb_i - 1].mvs[dir][0], blocks[mb_i - 1].mvs[dir][1]);
530
531             if (mb_y > 0) {
532                 //top mb in current frame
533                 ADD_PRED(preds[0], blocks[mb_i - mi_ctx->b_width].mvs[dir][0], blocks[mb_i - mi_ctx->b_width].mvs[dir][1]);
534
535                 //top-right mb in current frame
536                 if (mb_x + 1 < mi_ctx->b_width)
537                     ADD_PRED(preds[0], blocks[mb_i - mi_ctx->b_width + 1].mvs[dir][0], blocks[mb_i - mi_ctx->b_width + 1].mvs[dir][1]);
538                 //top-left mb in current frame
539                 else if (mb_x > 0)
540                     ADD_PRED(preds[0], blocks[mb_i - mi_ctx->b_width - 1].mvs[dir][0], blocks[mb_i - mi_ctx->b_width - 1].mvs[dir][1]);
541             }
542
543             //median predictor
544             if (preds[0].nb == 4) {
545                 me_ctx->pred_x = mid_pred(preds[0].mvs[1][0], preds[0].mvs[2][0], preds[0].mvs[3][0]);
546                 me_ctx->pred_y = mid_pred(preds[0].mvs[1][1], preds[0].mvs[2][1], preds[0].mvs[3][1]);
547             } else if (preds[0].nb == 3) {
548                 me_ctx->pred_x = mid_pred(0, preds[0].mvs[1][0], preds[0].mvs[2][0]);
549                 me_ctx->pred_y = mid_pred(0, preds[0].mvs[1][1], preds[0].mvs[2][1]);
550             } else if (preds[0].nb == 2) {
551                 me_ctx->pred_x = preds[0].mvs[1][0];
552                 me_ctx->pred_y = preds[0].mvs[1][1];
553             } else {
554                 me_ctx->pred_x = 0;
555                 me_ctx->pred_y = 0;
556             }
557
558             ff_me_search_umh(me_ctx, x_mb, y_mb, mv);
559
560             break;
561     }
562
563     block->mvs[dir][0] = mv[0] - x_mb;
564     block->mvs[dir][1] = mv[1] - y_mb;
565 }
566
567 static void bilateral_me(MIContext *mi_ctx)
568 {
569     Block *block;
570     int mb_x, mb_y;
571
572     for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
573         for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++) {
574             block = &mi_ctx->int_blocks[mb_x + mb_y * mi_ctx->b_width];
575
576             block->cid = 0;
577             block->sb = 0;
578
579             block->mvs[0][0] = 0;
580             block->mvs[0][1] = 0;
581         }
582
583     for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
584         for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++)
585             search_mv(mi_ctx, mi_ctx->int_blocks, mb_x, mb_y, 0);
586 }
587
588 static int var_size_bme(MIContext *mi_ctx, Block *block, int x_mb, int y_mb, int n)
589 {
590     AVMotionEstContext *me_ctx = &mi_ctx->me_ctx;
591     uint64_t cost_sb, cost_old;
592     int mb_size = me_ctx->mb_size;
593     int search_param = me_ctx->search_param;
594     int mv_x, mv_y;
595     int x, y;
596     int ret;
597
598     me_ctx->mb_size = 1 << n;
599     cost_old = me_ctx->get_cost(me_ctx, x_mb, y_mb, x_mb + block->mvs[0][0], y_mb + block->mvs[0][1]);
600     me_ctx->mb_size = mb_size;
601
602     if (!cost_old) {
603         block->sb = 0;
604         return 0;
605     }
606
607     if (!block->subs) {
608         block->subs = av_mallocz_array(4, sizeof(Block));
609         if (!block->subs)
610             return AVERROR(ENOMEM);
611     }
612
613     block->sb = 1;
614
615     for (y = 0; y < 2; y++)
616         for (x = 0; x < 2; x++) {
617             Block *sb = &block->subs[x + y * 2];
618             int mv[2] = {x_mb + block->mvs[0][0], y_mb + block->mvs[0][1]};
619
620             me_ctx->mb_size = 1 << (n - 1);
621             me_ctx->search_param = 2;
622             me_ctx->pred_x = block->mvs[0][0];
623             me_ctx->pred_y = block->mvs[0][1];
624
625             cost_sb = ff_me_search_ds(&mi_ctx->me_ctx, x_mb + block->mvs[0][0], y_mb + block->mvs[0][1], mv);
626             mv_x = mv[0] - x_mb;
627             mv_y = mv[1] - y_mb;
628
629             me_ctx->mb_size = mb_size;
630             me_ctx->search_param = search_param;
631
632             if (cost_sb < cost_old / 4) {
633                 sb->mvs[0][0] = mv_x;
634                 sb->mvs[0][1] = mv_y;
635
636                 if (n > 1) {
637                     if (ret = var_size_bme(mi_ctx, sb, x_mb + (x << (n - 1)), y_mb + (y << (n - 1)), n - 1))
638                         return ret;
639                 } else
640                     sb->sb = 0;
641             } else {
642                 block->sb = 0;
643                 return 0;
644             }
645         }
646
647     return 0;
648 }
649
650 static int cluster_mvs(MIContext *mi_ctx)
651 {
652     int changed, c, c_max = 0;
653     int mb_x, mb_y, x, y;
654     int mv_x, mv_y, avg_x, avg_y, dx, dy;
655     int d, ret;
656     Block *block;
657     Cluster *cluster, *cluster_new;
658
659     do {
660         changed = 0;
661         for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
662             for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++) {
663                 block = &mi_ctx->int_blocks[mb_x + mb_y * mi_ctx->b_width];
664                 c = block->cid;
665                 cluster = &mi_ctx->clusters[c];
666                 mv_x = block->mvs[0][0];
667                 mv_y = block->mvs[0][1];
668
669                 if (cluster->nb < 2)
670                     continue;
671
672                 avg_x = cluster->sum[0] / cluster->nb;
673                 avg_y = cluster->sum[1] / cluster->nb;
674                 dx = avg_x - mv_x;
675                 dy = avg_y - mv_y;
676
677                 if (FFABS(dx) > CLUSTER_THRESHOLD || FFABS(dy) > CLUSTER_THRESHOLD) {
678
679                     for (d = 1; d < 5; d++)
680                         for (y = FFMAX(mb_y - d, 0); y < FFMIN(mb_y + d + 1, mi_ctx->b_height); y++)
681                             for (x = FFMAX(mb_x - d, 0); x < FFMIN(mb_x + d + 1, mi_ctx->b_width); x++) {
682                                 Block *nb = &mi_ctx->int_blocks[x + y * mi_ctx->b_width];
683                                 if (nb->cid > block->cid) {
684                                     if (nb->cid < c || c == block->cid)
685                                         c = nb->cid;
686                                 }
687                             }
688
689                     if (c == block->cid)
690                         c = c_max + 1;
691
692                     if (c >= NB_CLUSTERS) {
693                         continue;
694                     }
695
696                     cluster_new = &mi_ctx->clusters[c];
697                     cluster_new->sum[0] += mv_x;
698                     cluster_new->sum[1] += mv_y;
699                     cluster->sum[0] -= mv_x;
700                     cluster->sum[1] -= mv_y;
701                     cluster_new->nb++;
702                     cluster->nb--;
703
704                     c_max = FFMAX(c_max, c);
705                     block->cid = c;
706
707                     changed = 1;
708                 }
709             }
710     } while (changed);
711
712     /* find boundaries */
713     for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
714         for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++) {
715             block = &mi_ctx->int_blocks[mb_x + mb_y * mi_ctx->b_width];
716             for (y = FFMAX(mb_y - 1, 0); y < FFMIN(mb_y + 2, mi_ctx->b_height); y++)
717                 for (x = FFMAX(mb_x - 1, 0); x < FFMIN(mb_x + 2, mi_ctx->b_width); x++) {
718                     dx = x - mb_x;
719                     dy = y - mb_y;
720
721                     if ((x - mb_x) && (y - mb_y) || !dx && !dy)
722                         continue;
723
724                     if (!mb_x || !mb_y || mb_x == mi_ctx->b_width - 1 || mb_y == mi_ctx->b_height - 1)
725                         continue;
726
727                     if (block->cid != mi_ctx->int_blocks[x + y * mi_ctx->b_width].cid) {
728                         if (!dx && block->cid == mi_ctx->int_blocks[x + (mb_y - dy) * mi_ctx->b_width].cid ||
729                             !dy && block->cid == mi_ctx->int_blocks[(mb_x - dx) + y * mi_ctx->b_width].cid) {
730                             if (ret = var_size_bme(mi_ctx, block, mb_x << mi_ctx->log2_mb_size, mb_y << mi_ctx->log2_mb_size, mi_ctx->log2_mb_size))
731                                 return ret;
732                         }
733                     }
734                 }
735         }
736
737     return 0;
738 }
739
740 static int inject_frame(AVFilterLink *inlink, AVFrame *avf_in)
741 {
742     AVFilterContext *ctx = inlink->dst;
743     MIContext *mi_ctx = ctx->priv;
744     Frame frame_tmp;
745     int mb_x, mb_y, dir;
746
747     av_frame_free(&mi_ctx->frames[0].avf);
748     frame_tmp = mi_ctx->frames[0];
749     memmove(&mi_ctx->frames[0], &mi_ctx->frames[1], sizeof(mi_ctx->frames[0]) * (NB_FRAMES - 1));
750     mi_ctx->frames[NB_FRAMES - 1] = frame_tmp;
751     mi_ctx->frames[NB_FRAMES - 1].avf = avf_in;
752
753     if (mi_ctx->mi_mode == MI_MODE_MCI) {
754
755         if (mi_ctx->me_method == AV_ME_METHOD_EPZS) {
756             mi_ctx->mv_table[2] = memcpy(mi_ctx->mv_table[2], mi_ctx->mv_table[1], sizeof(*mi_ctx->mv_table[1]) * mi_ctx->b_count);
757             mi_ctx->mv_table[1] = memcpy(mi_ctx->mv_table[1], mi_ctx->mv_table[0], sizeof(*mi_ctx->mv_table[0]) * mi_ctx->b_count);
758         }
759
760         if (mi_ctx->me_mode == ME_MODE_BIDIR) {
761
762             if (mi_ctx->frames[1].avf) {
763                 for (dir = 0; dir < 2; dir++) {
764                     mi_ctx->me_ctx.linesize = mi_ctx->frames[2].avf->linesize[0];
765                     mi_ctx->me_ctx.data_cur = mi_ctx->frames[2].avf->data[0];
766                     mi_ctx->me_ctx.data_ref = mi_ctx->frames[dir ? 3 : 1].avf->data[0];
767
768                     for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
769                         for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++)
770                             search_mv(mi_ctx, mi_ctx->frames[2].blocks, mb_x, mb_y, dir);
771                 }
772             }
773
774         } else if (mi_ctx->me_mode == ME_MODE_BILAT) {
775             Block *block;
776             int i, ret;
777
778             if (!mi_ctx->frames[0].avf)
779                 return 0;
780
781             mi_ctx->me_ctx.linesize = mi_ctx->frames[0].avf->linesize[0];
782             mi_ctx->me_ctx.data_cur = mi_ctx->frames[1].avf->data[0];
783             mi_ctx->me_ctx.data_ref = mi_ctx->frames[2].avf->data[0];
784
785             bilateral_me(mi_ctx);
786
787             if (mi_ctx->mc_mode == MC_MODE_AOBMC) {
788
789                 for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
790                     for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++) {
791                         int x_mb = mb_x << mi_ctx->log2_mb_size;
792                         int y_mb = mb_y << mi_ctx->log2_mb_size;
793                         block = &mi_ctx->int_blocks[mb_x + mb_y * mi_ctx->b_width];
794
795                         block->sbad = get_sbad(&mi_ctx->me_ctx, x_mb, y_mb, x_mb + block->mvs[0][0], y_mb + block->mvs[0][1]);
796                     }
797             }
798
799             if (mi_ctx->vsbmc) {
800
801                 for (i = 0; i < NB_CLUSTERS; i++) {
802                     mi_ctx->clusters[i].sum[0] = 0;
803                     mi_ctx->clusters[i].sum[1] = 0;
804                     mi_ctx->clusters[i].nb = 0;
805                 }
806
807                 for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
808                     for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++) {
809                         block = &mi_ctx->int_blocks[mb_x + mb_y * mi_ctx->b_width];
810
811                         mi_ctx->clusters[0].sum[0] += block->mvs[0][0];
812                         mi_ctx->clusters[0].sum[1] += block->mvs[0][1];
813                     }
814
815                 mi_ctx->clusters[0].nb = mi_ctx->b_count;
816
817                 if (ret = cluster_mvs(mi_ctx))
818                     return ret;
819             }
820         }
821     }
822
823     return 0;
824 }
825
826 static int detect_scene_change(MIContext *mi_ctx)
827 {
828     AVMotionEstContext *me_ctx = &mi_ctx->me_ctx;
829     uint8_t *p1 = mi_ctx->frames[1].avf->data[0];
830     ptrdiff_t linesize1 = mi_ctx->frames[1].avf->linesize[0];
831     uint8_t *p2 = mi_ctx->frames[2].avf->data[0];
832     ptrdiff_t linesize2 = mi_ctx->frames[2].avf->linesize[0];
833
834     if (mi_ctx->scd_method == SCD_METHOD_FDIFF) {
835         double ret = 0, mafd, diff;
836         uint64_t sad;
837         mi_ctx->sad(p1, linesize1, p2, linesize2, me_ctx->width, me_ctx->height, &sad);
838         emms_c();
839         mafd = (double) sad / (me_ctx->height * me_ctx->width * 3);
840         diff = fabs(mafd - mi_ctx->prev_mafd);
841         ret  = av_clipf(FFMIN(mafd, diff), 0, 100.0);
842         mi_ctx->prev_mafd = mafd;
843
844         return ret >= mi_ctx->scd_threshold;
845     }
846
847     return 0;
848 }
849
850 #define ADD_PIXELS(b_weight, mv_x, mv_y)\
851     do {\
852         if (!b_weight || pixel_refs->nb + 1 >= NB_PIXEL_MVS)\
853             continue;\
854         pixel_refs->refs[pixel_refs->nb] = 1;\
855         pixel_weights->weights[pixel_refs->nb] = b_weight * (ALPHA_MAX - alpha);\
856         pixel_mvs->mvs[pixel_refs->nb][0] = av_clip((mv_x * alpha) / ALPHA_MAX, x_min, x_max);\
857         pixel_mvs->mvs[pixel_refs->nb][1] = av_clip((mv_y * alpha) / ALPHA_MAX, y_min, y_max);\
858         pixel_refs->nb++;\
859         pixel_refs->refs[pixel_refs->nb] = 2;\
860         pixel_weights->weights[pixel_refs->nb] = b_weight * alpha;\
861         pixel_mvs->mvs[pixel_refs->nb][0] = av_clip(-mv_x * (ALPHA_MAX - alpha) / ALPHA_MAX, x_min, x_max);\
862         pixel_mvs->mvs[pixel_refs->nb][1] = av_clip(-mv_y * (ALPHA_MAX - alpha) / ALPHA_MAX, y_min, y_max);\
863         pixel_refs->nb++;\
864     } while(0)
865
866 static void bidirectional_obmc(MIContext *mi_ctx, int alpha)
867 {
868     int x, y;
869     int width = mi_ctx->frames[0].avf->width;
870     int height = mi_ctx->frames[0].avf->height;
871     int mb_y, mb_x, dir;
872
873     for (y = 0; y < height; y++)
874         for (x = 0; x < width; x++)
875             mi_ctx->pixel_refs[x + y * width].nb = 0;
876
877     for (dir = 0; dir < 2; dir++)
878         for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
879             for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++) {
880                 int a = dir ? alpha : (ALPHA_MAX - alpha);
881                 int mv_x = mi_ctx->frames[2 - dir].blocks[mb_x + mb_y * mi_ctx->b_width].mvs[dir][0];
882                 int mv_y = mi_ctx->frames[2 - dir].blocks[mb_x + mb_y * mi_ctx->b_width].mvs[dir][1];
883                 int start_x, start_y;
884                 int startc_x, startc_y, endc_x, endc_y;
885
886                 start_x = (mb_x << mi_ctx->log2_mb_size) - mi_ctx->mb_size / 2 + mv_x * a / ALPHA_MAX;
887                 start_y = (mb_y << mi_ctx->log2_mb_size) - mi_ctx->mb_size / 2 + mv_y * a / ALPHA_MAX;
888
889                 startc_x = av_clip(start_x, 0, width - 1);
890                 startc_y = av_clip(start_y, 0, height - 1);
891                 endc_x = av_clip(start_x + (2 << mi_ctx->log2_mb_size), 0, width - 1);
892                 endc_y = av_clip(start_y + (2 << mi_ctx->log2_mb_size), 0, height - 1);
893
894                 if (dir) {
895                     mv_x = -mv_x;
896                     mv_y = -mv_y;
897                 }
898
899                 for (y = startc_y; y < endc_y; y++) {
900                     int y_min = -y;
901                     int y_max = height - y - 1;
902                     for (x = startc_x; x < endc_x; x++) {
903                         int x_min = -x;
904                         int x_max = width - x - 1;
905                         int obmc_weight = obmc_tab_linear[4 - mi_ctx->log2_mb_size][(x - start_x) + ((y - start_y) << (mi_ctx->log2_mb_size + 1))];
906                         PixelMVS *pixel_mvs = &mi_ctx->pixel_mvs[x + y * width];
907                         PixelWeights *pixel_weights = &mi_ctx->pixel_weights[x + y * width];
908                         PixelRefs *pixel_refs = &mi_ctx->pixel_refs[x + y * width];
909
910                         ADD_PIXELS(obmc_weight, mv_x, mv_y);
911                     }
912                 }
913             }
914 }
915
916 static void set_frame_data(MIContext *mi_ctx, int alpha, AVFrame *avf_out)
917 {
918     int x, y, plane;
919
920     for (plane = 0; plane < mi_ctx->nb_planes; plane++) {
921         int width = avf_out->width;
922         int height = avf_out->height;
923         int chroma = plane == 1 || plane == 2;
924
925         for (y = 0; y < height; y++)
926             for (x = 0; x < width; x++) {
927                 int x_mv, y_mv;
928                 int weight_sum = 0;
929                 int i, val = 0;
930                 PixelMVS *pixel_mvs = &mi_ctx->pixel_mvs[x + y * avf_out->width];
931                 PixelWeights *pixel_weights = &mi_ctx->pixel_weights[x + y * avf_out->width];
932                 PixelRefs *pixel_refs = &mi_ctx->pixel_refs[x + y * avf_out->width];
933
934                 for (i = 0; i < pixel_refs->nb; i++)
935                     weight_sum += pixel_weights->weights[i];
936
937                 if (!weight_sum || !pixel_refs->nb) {
938                     pixel_weights->weights[0] = ALPHA_MAX - alpha;
939                     pixel_refs->refs[0] = 1;
940                     pixel_mvs->mvs[0][0] = 0;
941                     pixel_mvs->mvs[0][1] = 0;
942                     pixel_weights->weights[1] = alpha;
943                     pixel_refs->refs[1] = 2;
944                     pixel_mvs->mvs[1][0] = 0;
945                     pixel_mvs->mvs[1][1] = 0;
946                     pixel_refs->nb = 2;
947
948                     weight_sum = ALPHA_MAX;
949                 }
950
951                 for (i = 0; i < pixel_refs->nb; i++) {
952                     Frame *frame = &mi_ctx->frames[pixel_refs->refs[i]];
953                     if (chroma) {
954                         x_mv = (x >> mi_ctx->log2_chroma_w) + pixel_mvs->mvs[i][0] / (1 << mi_ctx->log2_chroma_w);
955                         y_mv = (y >> mi_ctx->log2_chroma_h) + pixel_mvs->mvs[i][1] / (1 << mi_ctx->log2_chroma_h);
956                     } else {
957                         x_mv = x + pixel_mvs->mvs[i][0];
958                         y_mv = y + pixel_mvs->mvs[i][1];
959                     }
960
961                     val += pixel_weights->weights[i] * frame->avf->data[plane][x_mv + y_mv * frame->avf->linesize[plane]];
962                 }
963
964                 val = ROUNDED_DIV(val, weight_sum);
965
966                 if (chroma)
967                     avf_out->data[plane][(x >> mi_ctx->log2_chroma_w) + (y >> mi_ctx->log2_chroma_h) * avf_out->linesize[plane]] = val;
968                 else
969                     avf_out->data[plane][x + y * avf_out->linesize[plane]] = val;
970             }
971     }
972 }
973
974 static void var_size_bmc(MIContext *mi_ctx, Block *block, int x_mb, int y_mb, int n, int alpha)
975 {
976     int sb_x, sb_y;
977     int width = mi_ctx->frames[0].avf->width;
978     int height = mi_ctx->frames[0].avf->height;
979
980     for (sb_y = 0; sb_y < 2; sb_y++)
981         for (sb_x = 0; sb_x < 2; sb_x++) {
982             Block *sb = &block->subs[sb_x + sb_y * 2];
983
984             if (sb->sb)
985                 var_size_bmc(mi_ctx, sb, x_mb + (sb_x << (n - 1)), y_mb + (sb_y << (n - 1)), n - 1, alpha);
986             else {
987                 int x, y;
988                 int mv_x = sb->mvs[0][0] * 2;
989                 int mv_y = sb->mvs[0][1] * 2;
990
991                 int start_x = x_mb + (sb_x << (n - 1));
992                 int start_y = y_mb + (sb_y << (n - 1));
993                 int end_x = start_x + (1 << (n - 1));
994                 int end_y = start_y + (1 << (n - 1));
995
996                 for (y = start_y; y < end_y; y++)  {
997                     int y_min = -y;
998                     int y_max = height - y - 1;
999                     for (x = start_x; x < end_x; x++) {
1000                         int x_min = -x;
1001                         int x_max = width - x - 1;
1002                         PixelMVS *pixel_mvs = &mi_ctx->pixel_mvs[x + y * width];
1003                         PixelWeights *pixel_weights = &mi_ctx->pixel_weights[x + y * width];
1004                         PixelRefs *pixel_refs = &mi_ctx->pixel_refs[x + y * width];
1005
1006                         ADD_PIXELS(PX_WEIGHT_MAX, mv_x, mv_y);
1007                     }
1008                 }
1009             }
1010         }
1011 }
1012
1013 static void bilateral_obmc(MIContext *mi_ctx, Block *block, int mb_x, int mb_y, int alpha)
1014 {
1015     int x, y;
1016     int width = mi_ctx->frames[0].avf->width;
1017     int height = mi_ctx->frames[0].avf->height;
1018
1019     Block *nb;
1020     int nb_x, nb_y;
1021     uint64_t sbads[9];
1022
1023     int mv_x = block->mvs[0][0] * 2;
1024     int mv_y = block->mvs[0][1] * 2;
1025     int start_x, start_y;
1026     int startc_x, startc_y, endc_x, endc_y;
1027
1028     if (mi_ctx->mc_mode == MC_MODE_AOBMC)
1029         for (nb_y = FFMAX(0, mb_y - 1); nb_y < FFMIN(mb_y + 2, mi_ctx->b_height); nb_y++)
1030             for (nb_x = FFMAX(0, mb_x - 1); nb_x < FFMIN(mb_x + 2, mi_ctx->b_width); nb_x++) {
1031                 int x_nb = nb_x << mi_ctx->log2_mb_size;
1032                 int y_nb = nb_y << mi_ctx->log2_mb_size;
1033
1034                 if (nb_x - mb_x || nb_y - mb_y)
1035                     sbads[nb_x - mb_x + 1 + (nb_y - mb_y + 1) * 3] = get_sbad(&mi_ctx->me_ctx, x_nb, y_nb, x_nb + block->mvs[0][0], y_nb + block->mvs[0][1]);
1036             }
1037
1038     start_x = (mb_x << mi_ctx->log2_mb_size) - mi_ctx->mb_size / 2;
1039     start_y = (mb_y << mi_ctx->log2_mb_size) - mi_ctx->mb_size / 2;
1040
1041     startc_x = av_clip(start_x, 0, width - 1);
1042     startc_y = av_clip(start_y, 0, height - 1);
1043     endc_x = av_clip(start_x + (2 << mi_ctx->log2_mb_size), 0, width - 1);
1044     endc_y = av_clip(start_y + (2 << mi_ctx->log2_mb_size), 0, height - 1);
1045
1046     for (y = startc_y; y < endc_y; y++) {
1047         int y_min = -y;
1048         int y_max = height - y - 1;
1049         for (x = startc_x; x < endc_x; x++) {
1050             int x_min = -x;
1051             int x_max = width - x - 1;
1052             int obmc_weight = obmc_tab_linear[4 - mi_ctx->log2_mb_size][(x - start_x) + ((y - start_y) << (mi_ctx->log2_mb_size + 1))];
1053             PixelMVS *pixel_mvs = &mi_ctx->pixel_mvs[x + y * width];
1054             PixelWeights *pixel_weights = &mi_ctx->pixel_weights[x + y * width];
1055             PixelRefs *pixel_refs = &mi_ctx->pixel_refs[x + y * width];
1056
1057             if (mi_ctx->mc_mode == MC_MODE_AOBMC) {
1058                 nb_x = (((x - start_x) >> (mi_ctx->log2_mb_size - 1)) * 2 - 3) / 2;
1059                 nb_y = (((y - start_y) >> (mi_ctx->log2_mb_size - 1)) * 2 - 3) / 2;
1060
1061                 if (nb_x || nb_y) {
1062                     uint64_t sbad = sbads[nb_x + 1 + (nb_y + 1) * 3];
1063                     nb = &mi_ctx->int_blocks[mb_x + nb_x + (mb_y + nb_y) * mi_ctx->b_width];
1064
1065                     if (sbad && sbad != UINT64_MAX && nb->sbad != UINT64_MAX) {
1066                         int phi = av_clip(ALPHA_MAX * nb->sbad / sbad, 0, ALPHA_MAX);
1067                         obmc_weight = obmc_weight * phi / ALPHA_MAX;
1068                     }
1069                 }
1070             }
1071
1072             ADD_PIXELS(obmc_weight, mv_x, mv_y);
1073         }
1074     }
1075 }
1076
1077 static void interpolate(AVFilterLink *inlink, AVFrame *avf_out)
1078 {
1079     AVFilterContext *ctx = inlink->dst;
1080     AVFilterLink *outlink = ctx->outputs[0];
1081     MIContext *mi_ctx = ctx->priv;
1082     int x, y;
1083     int plane, alpha;
1084     int64_t pts;
1085
1086     pts = av_rescale(avf_out->pts, (int64_t) ALPHA_MAX * outlink->time_base.num * inlink->time_base.den,
1087                                    (int64_t)             outlink->time_base.den * inlink->time_base.num);
1088
1089     alpha = (pts - mi_ctx->frames[1].avf->pts * ALPHA_MAX) / (mi_ctx->frames[2].avf->pts - mi_ctx->frames[1].avf->pts);
1090     alpha = av_clip(alpha, 0, ALPHA_MAX);
1091
1092     if (alpha == 0 || alpha == ALPHA_MAX) {
1093         av_frame_copy(avf_out, alpha ? mi_ctx->frames[2].avf : mi_ctx->frames[1].avf);
1094         return;
1095     }
1096
1097     if (mi_ctx->scene_changed) {
1098         /* duplicate frame */
1099         av_frame_copy(avf_out, alpha > ALPHA_MAX / 2 ? mi_ctx->frames[2].avf : mi_ctx->frames[1].avf);
1100         return;
1101     }
1102
1103     switch(mi_ctx->mi_mode) {
1104         case MI_MODE_DUP:
1105             av_frame_copy(avf_out, alpha > ALPHA_MAX / 2 ? mi_ctx->frames[2].avf : mi_ctx->frames[1].avf);
1106
1107             break;
1108         case MI_MODE_BLEND:
1109             for (plane = 0; plane < mi_ctx->nb_planes; plane++) {
1110                 int width = avf_out->width;
1111                 int height = avf_out->height;
1112
1113                 if (plane == 1 || plane == 2) {
1114                     width = AV_CEIL_RSHIFT(width, mi_ctx->log2_chroma_w);
1115                     height = AV_CEIL_RSHIFT(height, mi_ctx->log2_chroma_h);
1116                 }
1117
1118                 for (y = 0; y < height; y++) {
1119                     for (x = 0; x < width; x++) {
1120                         avf_out->data[plane][x + y * avf_out->linesize[plane]] =
1121                             (alpha  * mi_ctx->frames[2].avf->data[plane][x + y * mi_ctx->frames[2].avf->linesize[plane]] +
1122                              (ALPHA_MAX - alpha) * mi_ctx->frames[1].avf->data[plane][x + y * mi_ctx->frames[1].avf->linesize[plane]] + 512) >> 10;
1123                     }
1124                 }
1125             }
1126
1127             break;
1128         case MI_MODE_MCI:
1129             if (mi_ctx->me_mode == ME_MODE_BIDIR) {
1130                 bidirectional_obmc(mi_ctx, alpha);
1131                 set_frame_data(mi_ctx, alpha, avf_out);
1132
1133             } else if (mi_ctx->me_mode == ME_MODE_BILAT) {
1134                 int mb_x, mb_y;
1135                 Block *block;
1136
1137                 for (y = 0; y < mi_ctx->frames[0].avf->height; y++)
1138                     for (x = 0; x < mi_ctx->frames[0].avf->width; x++)
1139                         mi_ctx->pixel_refs[x + y * mi_ctx->frames[0].avf->width].nb = 0;
1140
1141                 for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
1142                     for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++) {
1143                         block = &mi_ctx->int_blocks[mb_x + mb_y * mi_ctx->b_width];
1144
1145                         if (block->sb)
1146                             var_size_bmc(mi_ctx, block, mb_x << mi_ctx->log2_mb_size, mb_y << mi_ctx->log2_mb_size, mi_ctx->log2_mb_size, alpha);
1147
1148                         bilateral_obmc(mi_ctx, block, mb_x, mb_y, alpha);
1149
1150                     }
1151
1152                 set_frame_data(mi_ctx, alpha, avf_out);
1153             }
1154
1155             break;
1156     }
1157 }
1158
1159 static int filter_frame(AVFilterLink *inlink, AVFrame *avf_in)
1160 {
1161     AVFilterContext *ctx = inlink->dst;
1162     AVFilterLink *outlink = ctx->outputs[0];
1163     MIContext *mi_ctx = ctx->priv;
1164     int ret;
1165
1166     if (avf_in->pts == AV_NOPTS_VALUE) {
1167         ret = ff_filter_frame(ctx->outputs[0], avf_in);
1168         return ret;
1169     }
1170
1171     if (!mi_ctx->frames[NB_FRAMES - 1].avf || avf_in->pts < mi_ctx->frames[NB_FRAMES - 1].avf->pts) {
1172         av_log(ctx, AV_LOG_VERBOSE, "Initializing out pts from input pts %"PRId64"\n", avf_in->pts);
1173         mi_ctx->out_pts = av_rescale_q(avf_in->pts, inlink->time_base, outlink->time_base);
1174     }
1175
1176     if (!mi_ctx->frames[NB_FRAMES - 1].avf)
1177         if (ret = inject_frame(inlink, av_frame_clone(avf_in)))
1178             return ret;
1179
1180     if (ret = inject_frame(inlink, avf_in))
1181         return ret;
1182
1183     if (!mi_ctx->frames[0].avf)
1184         return 0;
1185
1186     mi_ctx->scene_changed = detect_scene_change(mi_ctx);
1187
1188     for (;;) {
1189         AVFrame *avf_out;
1190
1191         if (av_compare_ts(mi_ctx->out_pts, outlink->time_base, mi_ctx->frames[2].avf->pts, inlink->time_base) > 0)
1192             break;
1193
1194         if (!(avf_out = ff_get_video_buffer(ctx->outputs[0], inlink->w, inlink->h)))
1195             return AVERROR(ENOMEM);
1196
1197         av_frame_copy_props(avf_out, mi_ctx->frames[NB_FRAMES - 1].avf);
1198         avf_out->pts = mi_ctx->out_pts++;
1199
1200         interpolate(inlink, avf_out);
1201
1202         if ((ret = ff_filter_frame(ctx->outputs[0], avf_out)) < 0)
1203             return ret;
1204     }
1205
1206     return 0;
1207 }
1208
1209 static av_cold void free_blocks(Block *block, int sb)
1210 {
1211     if (block->subs)
1212         free_blocks(block->subs, 1);
1213     if (sb)
1214         av_freep(&block);
1215 }
1216
1217 static av_cold void uninit(AVFilterContext *ctx)
1218 {
1219     MIContext *mi_ctx = ctx->priv;
1220     int i, m;
1221
1222     av_freep(&mi_ctx->pixel_mvs);
1223     av_freep(&mi_ctx->pixel_weights);
1224     av_freep(&mi_ctx->pixel_refs);
1225     if (mi_ctx->int_blocks)
1226         for (m = 0; m < mi_ctx->b_count; m++)
1227             free_blocks(&mi_ctx->int_blocks[m], 0);
1228     av_freep(&mi_ctx->int_blocks);
1229
1230     for (i = 0; i < NB_FRAMES; i++) {
1231         Frame *frame = &mi_ctx->frames[i];
1232         av_freep(&frame->blocks);
1233         av_frame_free(&frame->avf);
1234     }
1235
1236     for (i = 0; i < 3; i++)
1237         av_freep(&mi_ctx->mv_table[i]);
1238 }
1239
1240 static const AVFilterPad minterpolate_inputs[] = {
1241     {
1242         .name          = "default",
1243         .type          = AVMEDIA_TYPE_VIDEO,
1244         .filter_frame  = filter_frame,
1245         .config_props  = config_input,
1246     },
1247     { NULL }
1248 };
1249
1250 static const AVFilterPad minterpolate_outputs[] = {
1251     {
1252         .name          = "default",
1253         .type          = AVMEDIA_TYPE_VIDEO,
1254         .config_props  = config_output,
1255     },
1256     { NULL }
1257 };
1258
1259 AVFilter ff_vf_minterpolate = {
1260     .name          = "minterpolate",
1261     .description   = NULL_IF_CONFIG_SMALL("Frame rate conversion using Motion Interpolation."),
1262     .priv_size     = sizeof(MIContext),
1263     .priv_class    = &minterpolate_class,
1264     .uninit        = uninit,
1265     .query_formats = query_formats,
1266     .inputs        = minterpolate_inputs,
1267     .outputs       = minterpolate_outputs,
1268 };