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