avfilter/framequeue: add missing check for ASSERT_LEVEL
[ffmpeg.git] / libavfilter / vf_fieldmatch.c
1 /*
2  * Copyright (c) 2012 Fredrik Mellbin
3  * Copyright (c) 2013 Clément Bœsch
4  *
5  * This file is part of FFmpeg.
6  *
7  * FFmpeg is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * FFmpeg is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with FFmpeg; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21
22 /**
23  * @file
24  * Fieldmatching filter, ported from VFM filter (VapourSynth) by Clément.
25  * Fredrik Mellbin is the author of the VIVTC/VFM filter, which is itself a
26  * light clone of the TIVTC/TFM (AviSynth) filter written by Kevin Stone
27  * (tritical), the original author.
28  *
29  * @see http://bengal.missouri.edu/~kes25c/
30  * @see http://www.vapoursynth.com/about/
31  */
32
33 #include <inttypes.h>
34
35 #include "libavutil/avassert.h"
36 #include "libavutil/imgutils.h"
37 #include "libavutil/opt.h"
38 #include "libavutil/timestamp.h"
39 #include "avfilter.h"
40 #include "internal.h"
41
42 #define INPUT_MAIN     0
43 #define INPUT_CLEANSRC 1
44
45 enum fieldmatch_parity {
46     FM_PARITY_AUTO   = -1,
47     FM_PARITY_BOTTOM =  0,
48     FM_PARITY_TOP    =  1,
49 };
50
51 enum matching_mode {
52     MODE_PC,
53     MODE_PC_N,
54     MODE_PC_U,
55     MODE_PC_N_UB,
56     MODE_PCN,
57     MODE_PCN_UB,
58     NB_MODE
59 };
60
61 enum comb_matching_mode {
62     COMBMATCH_NONE,
63     COMBMATCH_SC,
64     COMBMATCH_FULL,
65     NB_COMBMATCH
66 };
67
68 enum comb_dbg {
69     COMBDBG_NONE,
70     COMBDBG_PCN,
71     COMBDBG_PCNUB,
72     NB_COMBDBG
73 };
74
75 typedef struct {
76     const AVClass *class;
77
78     AVFrame *prv,  *src,  *nxt;     ///< main sliding window of 3 frames
79     AVFrame *prv2, *src2, *nxt2;    ///< sliding window of the optional second stream
80     int got_frame[2];               ///< frame request flag for each input stream
81     int hsub, vsub;                 ///< chroma subsampling values
82     uint32_t eof;                   ///< bitmask for end of stream
83     int64_t lastscdiff;
84     int64_t lastn;
85
86     /* options */
87     int order;
88     int ppsrc;
89     int mode;                       ///< matching_mode
90     int field;
91     int mchroma;
92     int y0, y1;
93     int64_t scthresh;
94     double scthresh_flt;
95     int combmatch;                  ///< comb_matching_mode
96     int combdbg;
97     int cthresh;
98     int chroma;
99     int blockx, blocky;
100     int combpel;
101
102     /* misc buffers */
103     uint8_t *map_data[4];
104     int map_linesize[4];
105     uint8_t *cmask_data[4];
106     int cmask_linesize[4];
107     int *c_array;
108     int tpitchy, tpitchuv;
109     uint8_t *tbuffer;
110 } FieldMatchContext;
111
112 #define OFFSET(x) offsetof(FieldMatchContext, x)
113 #define FLAGS AV_OPT_FLAG_VIDEO_PARAM|AV_OPT_FLAG_FILTERING_PARAM
114
115 static const AVOption fieldmatch_options[] = {
116     { "order", "specify the assumed field order", OFFSET(order), AV_OPT_TYPE_INT, {.i64=FM_PARITY_AUTO}, -1, 1, FLAGS, "order" },
117         { "auto", "auto detect parity",        0, AV_OPT_TYPE_CONST, {.i64=FM_PARITY_AUTO},    INT_MIN, INT_MAX, FLAGS, "order" },
118         { "bff",  "assume bottom field first", 0, AV_OPT_TYPE_CONST, {.i64=FM_PARITY_BOTTOM},  INT_MIN, INT_MAX, FLAGS, "order" },
119         { "tff",  "assume top field first",    0, AV_OPT_TYPE_CONST, {.i64=FM_PARITY_TOP},     INT_MIN, INT_MAX, FLAGS, "order" },
120     { "mode", "set the matching mode or strategy to use", OFFSET(mode), AV_OPT_TYPE_INT, {.i64=MODE_PC_N}, MODE_PC, NB_MODE-1, FLAGS, "mode" },
121         { "pc",      "2-way match (p/c)",                                                                    0, AV_OPT_TYPE_CONST, {.i64=MODE_PC},      INT_MIN, INT_MAX, FLAGS, "mode" },
122         { "pc_n",    "2-way match + 3rd match on combed (p/c + u)",                                          0, AV_OPT_TYPE_CONST, {.i64=MODE_PC_N},    INT_MIN, INT_MAX, FLAGS, "mode" },
123         { "pc_u",    "2-way match + 3rd match (same order) on combed (p/c + u)",                             0, AV_OPT_TYPE_CONST, {.i64=MODE_PC_U},    INT_MIN, INT_MAX, FLAGS, "mode" },
124         { "pc_n_ub", "2-way match + 3rd match on combed + 4th/5th matches if still combed (p/c + u + u/b)",  0, AV_OPT_TYPE_CONST, {.i64=MODE_PC_N_UB}, INT_MIN, INT_MAX, FLAGS, "mode" },
125         { "pcn",     "3-way match (p/c/n)",                                                                  0, AV_OPT_TYPE_CONST, {.i64=MODE_PCN},     INT_MIN, INT_MAX, FLAGS, "mode" },
126         { "pcn_ub",  "3-way match + 4th/5th matches on combed (p/c/n + u/b)",                                0, AV_OPT_TYPE_CONST, {.i64=MODE_PCN_UB},  INT_MIN, INT_MAX, FLAGS, "mode" },
127     { "ppsrc", "mark main input as a pre-processed input and activate clean source input stream", OFFSET(ppsrc), AV_OPT_TYPE_BOOL, {.i64=0}, 0, 1, FLAGS },
128     { "field", "set the field to match from", OFFSET(field), AV_OPT_TYPE_INT, {.i64=FM_PARITY_AUTO}, -1, 1, FLAGS, "field" },
129         { "auto",   "automatic (same value as 'order')",    0, AV_OPT_TYPE_CONST, {.i64=FM_PARITY_AUTO},    INT_MIN, INT_MAX, FLAGS, "field" },
130         { "bottom", "bottom field",                         0, AV_OPT_TYPE_CONST, {.i64=FM_PARITY_BOTTOM},  INT_MIN, INT_MAX, FLAGS, "field" },
131         { "top",    "top field",                            0, AV_OPT_TYPE_CONST, {.i64=FM_PARITY_TOP},     INT_MIN, INT_MAX, FLAGS, "field" },
132     { "mchroma", "set whether or not chroma is included during the match comparisons", OFFSET(mchroma), AV_OPT_TYPE_BOOL, {.i64=1}, 0, 1,  FLAGS },
133     { "y0", "define an exclusion band which excludes the lines between y0 and y1 from the field matching decision", OFFSET(y0), AV_OPT_TYPE_INT, {.i64=0}, 0, INT_MAX, FLAGS },
134     { "y1", "define an exclusion band which excludes the lines between y0 and y1 from the field matching decision", OFFSET(y1), AV_OPT_TYPE_INT, {.i64=0}, 0, INT_MAX, FLAGS },
135     { "scthresh", "set scene change detection threshold", OFFSET(scthresh_flt), AV_OPT_TYPE_DOUBLE, {.dbl=12}, 0, 100, FLAGS },
136     { "combmatch", "set combmatching mode", OFFSET(combmatch), AV_OPT_TYPE_INT, {.i64=COMBMATCH_SC}, COMBMATCH_NONE, NB_COMBMATCH-1, FLAGS, "combmatching" },
137         { "none", "disable combmatching",                     0, AV_OPT_TYPE_CONST, {.i64=COMBMATCH_NONE}, INT_MIN, INT_MAX, FLAGS, "combmatching" },
138         { "sc",   "enable combmatching only on scene change", 0, AV_OPT_TYPE_CONST, {.i64=COMBMATCH_SC},   INT_MIN, INT_MAX, FLAGS, "combmatching" },
139         { "full", "enable combmatching all the time",         0, AV_OPT_TYPE_CONST, {.i64=COMBMATCH_FULL}, INT_MIN, INT_MAX, FLAGS, "combmatching" },
140     { "combdbg",   "enable comb debug", OFFSET(combdbg), AV_OPT_TYPE_INT, {.i64=COMBDBG_NONE}, COMBDBG_NONE, NB_COMBDBG-1, FLAGS, "dbglvl" },
141         { "none",  "no forced calculation", 0, AV_OPT_TYPE_CONST, {.i64=COMBDBG_NONE},  INT_MIN, INT_MAX, FLAGS, "dbglvl" },
142         { "pcn",   "calculate p/c/n",       0, AV_OPT_TYPE_CONST, {.i64=COMBDBG_PCN},   INT_MIN, INT_MAX, FLAGS, "dbglvl" },
143         { "pcnub", "calculate p/c/n/u/b",   0, AV_OPT_TYPE_CONST, {.i64=COMBDBG_PCNUB}, INT_MIN, INT_MAX, FLAGS, "dbglvl" },
144     { "cthresh", "set the area combing threshold used for combed frame detection",       OFFSET(cthresh), AV_OPT_TYPE_INT, {.i64= 9}, -1, 0xff, FLAGS },
145     { "chroma",  "set whether or not chroma is considered in the combed frame decision", OFFSET(chroma),  AV_OPT_TYPE_BOOL,{.i64= 0},  0,    1, FLAGS },
146     { "blockx",  "set the x-axis size of the window used during combed frame detection", OFFSET(blockx),  AV_OPT_TYPE_INT, {.i64=16},  4, 1<<9, FLAGS },
147     { "blocky",  "set the y-axis size of the window used during combed frame detection", OFFSET(blocky),  AV_OPT_TYPE_INT, {.i64=16},  4, 1<<9, FLAGS },
148     { "combpel", "set the number of combed pixels inside any of the blocky by blockx size blocks on the frame for the frame to be detected as combed", OFFSET(combpel), AV_OPT_TYPE_INT, {.i64=80}, 0, INT_MAX, FLAGS },
149     { NULL }
150 };
151
152 AVFILTER_DEFINE_CLASS(fieldmatch);
153
154 static int get_width(const FieldMatchContext *fm, const AVFrame *f, int plane)
155 {
156     return plane ? AV_CEIL_RSHIFT(f->width, fm->hsub) : f->width;
157 }
158
159 static int get_height(const FieldMatchContext *fm, const AVFrame *f, int plane)
160 {
161     return plane ? AV_CEIL_RSHIFT(f->height, fm->vsub) : f->height;
162 }
163
164 static int64_t luma_abs_diff(const AVFrame *f1, const AVFrame *f2)
165 {
166     int x, y;
167     const uint8_t *srcp1 = f1->data[0];
168     const uint8_t *srcp2 = f2->data[0];
169     const int src1_linesize = f1->linesize[0];
170     const int src2_linesize = f2->linesize[0];
171     const int width  = f1->width;
172     const int height = f1->height;
173     int64_t acc = 0;
174
175     for (y = 0; y < height; y++) {
176         for (x = 0; x < width; x++)
177             acc += abs(srcp1[x] - srcp2[x]);
178         srcp1 += src1_linesize;
179         srcp2 += src2_linesize;
180     }
181     return acc;
182 }
183
184 static void fill_buf(uint8_t *data, int w, int h, int linesize, uint8_t v)
185 {
186     int y;
187
188     for (y = 0; y < h; y++) {
189         memset(data, v, w);
190         data += linesize;
191     }
192 }
193
194 static int calc_combed_score(const FieldMatchContext *fm, const AVFrame *src)
195 {
196     int x, y, plane, max_v = 0;
197     const int cthresh = fm->cthresh;
198     const int cthresh6 = cthresh * 6;
199
200     for (plane = 0; plane < (fm->chroma ? 3 : 1); plane++) {
201         const uint8_t *srcp = src->data[plane];
202         const int src_linesize = src->linesize[plane];
203         const int width  = get_width (fm, src, plane);
204         const int height = get_height(fm, src, plane);
205         uint8_t *cmkp = fm->cmask_data[plane];
206         const int cmk_linesize = fm->cmask_linesize[plane];
207
208         if (cthresh < 0) {
209             fill_buf(cmkp, width, height, cmk_linesize, 0xff);
210             continue;
211         }
212         fill_buf(cmkp, width, height, cmk_linesize, 0);
213
214         /* [1 -3 4 -3 1] vertical filter */
215 #define FILTER(xm2, xm1, xp1, xp2) \
216         abs(  4 * srcp[x] \
217              -3 * (srcp[x + (xm1)*src_linesize] + srcp[x + (xp1)*src_linesize]) \
218              +    (srcp[x + (xm2)*src_linesize] + srcp[x + (xp2)*src_linesize])) > cthresh6
219
220         /* first line */
221         for (x = 0; x < width; x++) {
222             const int s1 = abs(srcp[x] - srcp[x + src_linesize]);
223             if (s1 > cthresh && FILTER(2, 1, 1, 2))
224                 cmkp[x] = 0xff;
225         }
226         srcp += src_linesize;
227         cmkp += cmk_linesize;
228
229         /* second line */
230         for (x = 0; x < width; x++) {
231             const int s1 = abs(srcp[x] - srcp[x - src_linesize]);
232             const int s2 = abs(srcp[x] - srcp[x + src_linesize]);
233             if (s1 > cthresh && s2 > cthresh && FILTER(2, -1, 1, 2))
234                 cmkp[x] = 0xff;
235         }
236         srcp += src_linesize;
237         cmkp += cmk_linesize;
238
239         /* all lines minus first two and last two */
240         for (y = 2; y < height-2; y++) {
241             for (x = 0; x < width; x++) {
242                 const int s1 = abs(srcp[x] - srcp[x - src_linesize]);
243                 const int s2 = abs(srcp[x] - srcp[x + src_linesize]);
244                 if (s1 > cthresh && s2 > cthresh && FILTER(-2, -1, 1, 2))
245                     cmkp[x] = 0xff;
246             }
247             srcp += src_linesize;
248             cmkp += cmk_linesize;
249         }
250
251         /* before-last line */
252         for (x = 0; x < width; x++) {
253             const int s1 = abs(srcp[x] - srcp[x - src_linesize]);
254             const int s2 = abs(srcp[x] - srcp[x + src_linesize]);
255             if (s1 > cthresh && s2 > cthresh && FILTER(-2, -1, 1, -2))
256                 cmkp[x] = 0xff;
257         }
258         srcp += src_linesize;
259         cmkp += cmk_linesize;
260
261         /* last line */
262         for (x = 0; x < width; x++) {
263             const int s1 = abs(srcp[x] - srcp[x - src_linesize]);
264             if (s1 > cthresh && FILTER(-2, -1, -1, -2))
265                 cmkp[x] = 0xff;
266         }
267     }
268
269     if (fm->chroma) {
270         uint8_t *cmkp  = fm->cmask_data[0];
271         uint8_t *cmkpU = fm->cmask_data[1];
272         uint8_t *cmkpV = fm->cmask_data[2];
273         const int width  = AV_CEIL_RSHIFT(src->width,  fm->hsub);
274         const int height = AV_CEIL_RSHIFT(src->height, fm->vsub);
275         const int cmk_linesize   = fm->cmask_linesize[0] << 1;
276         const int cmk_linesizeUV = fm->cmask_linesize[2];
277         uint8_t *cmkpp  = cmkp - (cmk_linesize>>1);
278         uint8_t *cmkpn  = cmkp + (cmk_linesize>>1);
279         uint8_t *cmkpnn = cmkp +  cmk_linesize;
280         for (y = 1; y < height - 1; y++) {
281             cmkpp  += cmk_linesize;
282             cmkp   += cmk_linesize;
283             cmkpn  += cmk_linesize;
284             cmkpnn += cmk_linesize;
285             cmkpV  += cmk_linesizeUV;
286             cmkpU  += cmk_linesizeUV;
287             for (x = 1; x < width - 1; x++) {
288 #define HAS_FF_AROUND(p, lz) (p[(x)-1 - (lz)] == 0xff || p[(x) - (lz)] == 0xff || p[(x)+1 - (lz)] == 0xff || \
289                               p[(x)-1       ] == 0xff ||                          p[(x)+1       ] == 0xff || \
290                               p[(x)-1 + (lz)] == 0xff || p[(x) + (lz)] == 0xff || p[(x)+1 + (lz)] == 0xff)
291                 if ((cmkpV[x] == 0xff && HAS_FF_AROUND(cmkpV, cmk_linesizeUV)) ||
292                     (cmkpU[x] == 0xff && HAS_FF_AROUND(cmkpU, cmk_linesizeUV))) {
293                     ((uint16_t*)cmkp)[x]  = 0xffff;
294                     ((uint16_t*)cmkpn)[x] = 0xffff;
295                     if (y&1) ((uint16_t*)cmkpp)[x]  = 0xffff;
296                     else     ((uint16_t*)cmkpnn)[x] = 0xffff;
297                 }
298             }
299         }
300     }
301
302     {
303         const int blockx = fm->blockx;
304         const int blocky = fm->blocky;
305         const int xhalf = blockx/2;
306         const int yhalf = blocky/2;
307         const int cmk_linesize = fm->cmask_linesize[0];
308         const uint8_t *cmkp    = fm->cmask_data[0] + cmk_linesize;
309         const int width  = src->width;
310         const int height = src->height;
311         const int xblocks = ((width+xhalf)/blockx) + 1;
312         const int xblocks4 = xblocks<<2;
313         const int yblocks = ((height+yhalf)/blocky) + 1;
314         int *c_array = fm->c_array;
315         const int arraysize = (xblocks*yblocks)<<2;
316         int      heighta = (height/(blocky/2))*(blocky/2);
317         const int widtha = (width /(blockx/2))*(blockx/2);
318         if (heighta == height)
319             heighta = height - yhalf;
320         memset(c_array, 0, arraysize * sizeof(*c_array));
321
322 #define C_ARRAY_ADD(v) do {                         \
323     const int box1 = (x / blockx) * 4;              \
324     const int box2 = ((x + xhalf) / blockx) * 4;    \
325     c_array[temp1 + box1    ] += v;                 \
326     c_array[temp1 + box2 + 1] += v;                 \
327     c_array[temp2 + box1 + 2] += v;                 \
328     c_array[temp2 + box2 + 3] += v;                 \
329 } while (0)
330
331 #define VERTICAL_HALF(y_start, y_end) do {                                  \
332     for (y = y_start; y < y_end; y++) {                                     \
333         const int temp1 = (y / blocky) * xblocks4;                          \
334         const int temp2 = ((y + yhalf) / blocky) * xblocks4;                \
335         for (x = 0; x < width; x++)                                         \
336             if (cmkp[x - cmk_linesize] == 0xff &&                           \
337                 cmkp[x               ] == 0xff &&                           \
338                 cmkp[x + cmk_linesize] == 0xff)                             \
339                 C_ARRAY_ADD(1);                                             \
340         cmkp += cmk_linesize;                                               \
341     }                                                                       \
342 } while (0)
343
344         VERTICAL_HALF(1, yhalf);
345
346         for (y = yhalf; y < heighta; y += yhalf) {
347             const int temp1 = (y / blocky) * xblocks4;
348             const int temp2 = ((y + yhalf) / blocky) * xblocks4;
349
350             for (x = 0; x < widtha; x += xhalf) {
351                 const uint8_t *cmkp_tmp = cmkp + x;
352                 int u, v, sum = 0;
353                 for (u = 0; u < yhalf; u++) {
354                     for (v = 0; v < xhalf; v++)
355                         if (cmkp_tmp[v - cmk_linesize] == 0xff &&
356                             cmkp_tmp[v               ] == 0xff &&
357                             cmkp_tmp[v + cmk_linesize] == 0xff)
358                             sum++;
359                     cmkp_tmp += cmk_linesize;
360                 }
361                 if (sum)
362                     C_ARRAY_ADD(sum);
363             }
364
365             for (x = widtha; x < width; x++) {
366                 const uint8_t *cmkp_tmp = cmkp + x;
367                 int u, sum = 0;
368                 for (u = 0; u < yhalf; u++) {
369                     if (cmkp_tmp[-cmk_linesize] == 0xff &&
370                         cmkp_tmp[            0] == 0xff &&
371                         cmkp_tmp[ cmk_linesize] == 0xff)
372                         sum++;
373                     cmkp_tmp += cmk_linesize;
374                 }
375                 if (sum)
376                     C_ARRAY_ADD(sum);
377             }
378
379             cmkp += cmk_linesize * yhalf;
380         }
381
382         VERTICAL_HALF(heighta, height - 1);
383
384         for (x = 0; x < arraysize; x++)
385             if (c_array[x] > max_v)
386                 max_v = c_array[x];
387     }
388     return max_v;
389 }
390
391 // the secret is that tbuffer is an interlaced, offset subset of all the lines
392 static void build_abs_diff_mask(const uint8_t *prvp, int prv_linesize,
393                                 const uint8_t *nxtp, int nxt_linesize,
394                                 uint8_t *tbuffer,    int tbuf_linesize,
395                                 int width, int height)
396 {
397     int y, x;
398
399     prvp -= prv_linesize;
400     nxtp -= nxt_linesize;
401     for (y = 0; y < height; y++) {
402         for (x = 0; x < width; x++)
403             tbuffer[x] = FFABS(prvp[x] - nxtp[x]);
404         prvp += prv_linesize;
405         nxtp += nxt_linesize;
406         tbuffer += tbuf_linesize;
407     }
408 }
409
410 /**
411  * Build a map over which pixels differ a lot/a little
412  */
413 static void build_diff_map(FieldMatchContext *fm,
414                            const uint8_t *prvp, int prv_linesize,
415                            const uint8_t *nxtp, int nxt_linesize,
416                            uint8_t *dstp, int dst_linesize, int height,
417                            int width, int plane)
418 {
419     int x, y, u, diff, count;
420     int tpitch = plane ? fm->tpitchuv : fm->tpitchy;
421     const uint8_t *dp = fm->tbuffer + tpitch;
422
423     build_abs_diff_mask(prvp, prv_linesize, nxtp, nxt_linesize,
424                         fm->tbuffer, tpitch, width, height>>1);
425
426     for (y = 2; y < height - 2; y += 2) {
427         for (x = 1; x < width - 1; x++) {
428             diff = dp[x];
429             if (diff > 3) {
430                 for (count = 0, u = x-1; u < x+2 && count < 2; u++) {
431                     count += dp[u-tpitch] > 3;
432                     count += dp[u       ] > 3;
433                     count += dp[u+tpitch] > 3;
434                 }
435                 if (count > 1) {
436                     dstp[x] = 1;
437                     if (diff > 19) {
438                         int upper = 0, lower = 0;
439                         for (count = 0, u = x-1; u < x+2 && count < 6; u++) {
440                             if (dp[u-tpitch] > 19) { count++; upper = 1; }
441                             if (dp[u       ] > 19)   count++;
442                             if (dp[u+tpitch] > 19) { count++; lower = 1; }
443                         }
444                         if (count > 3) {
445                             if (upper && lower) {
446                                 dstp[x] |= 1<<1;
447                             } else {
448                                 int upper2 = 0, lower2 = 0;
449                                 for (u = FFMAX(x-4,0); u < FFMIN(x+5,width); u++) {
450                                     if (y != 2 &&        dp[u-2*tpitch] > 19) upper2 = 1;
451                                     if (                 dp[u-  tpitch] > 19) upper  = 1;
452                                     if (                 dp[u+  tpitch] > 19) lower  = 1;
453                                     if (y != height-4 && dp[u+2*tpitch] > 19) lower2 = 1;
454                                 }
455                                 if ((upper && (lower || upper2)) ||
456                                     (lower && (upper || lower2)))
457                                     dstp[x] |= 1<<1;
458                                 else if (count > 5)
459                                     dstp[x] |= 1<<2;
460                             }
461                         }
462                     }
463                 }
464             }
465         }
466         dp += tpitch;
467         dstp += dst_linesize;
468     }
469 }
470
471 enum { mP, mC, mN, mB, mU };
472
473 static int get_field_base(int match, int field)
474 {
475     return match < 3 ? 2 - field : 1 + field;
476 }
477
478 static AVFrame *select_frame(FieldMatchContext *fm, int match)
479 {
480     if      (match == mP || match == mB) return fm->prv;
481     else if (match == mN || match == mU) return fm->nxt;
482     else  /* match == mC */              return fm->src;
483 }
484
485 static int compare_fields(FieldMatchContext *fm, int match1, int match2, int field)
486 {
487     int plane, ret;
488     uint64_t accumPc = 0, accumPm = 0, accumPml = 0;
489     uint64_t accumNc = 0, accumNm = 0, accumNml = 0;
490     int norm1, norm2, mtn1, mtn2;
491     float c1, c2, mr;
492     const AVFrame *src = fm->src;
493
494     for (plane = 0; plane < (fm->mchroma ? 3 : 1); plane++) {
495         int x, y, temp1, temp2, fbase;
496         const AVFrame *prev, *next;
497         uint8_t *mapp    = fm->map_data[plane];
498         int map_linesize = fm->map_linesize[plane];
499         const uint8_t *srcp = src->data[plane];
500         const int src_linesize  = src->linesize[plane];
501         const int srcf_linesize = src_linesize << 1;
502         int prv_linesize,  nxt_linesize;
503         int prvf_linesize, nxtf_linesize;
504         const int width  = get_width (fm, src, plane);
505         const int height = get_height(fm, src, plane);
506         const int y0a = fm->y0 >> (plane != 0);
507         const int y1a = fm->y1 >> (plane != 0);
508         const int startx = (plane == 0 ? 8 : 4);
509         const int stopx  = width - startx;
510         const uint8_t *srcpf, *srcf, *srcnf;
511         const uint8_t *prvpf, *prvnf, *nxtpf, *nxtnf;
512
513         fill_buf(mapp, width, height, map_linesize, 0);
514
515         /* match1 */
516         fbase = get_field_base(match1, field);
517         srcf  = srcp + (fbase + 1) * src_linesize;
518         srcpf = srcf - srcf_linesize;
519         srcnf = srcf + srcf_linesize;
520         mapp  = mapp + fbase * map_linesize;
521         prev = select_frame(fm, match1);
522         prv_linesize  = prev->linesize[plane];
523         prvf_linesize = prv_linesize << 1;
524         prvpf = prev->data[plane] + fbase * prv_linesize;   // previous frame, previous field
525         prvnf = prvpf + prvf_linesize;                      // previous frame, next     field
526
527         /* match2 */
528         fbase = get_field_base(match2, field);
529         next = select_frame(fm, match2);
530         nxt_linesize  = next->linesize[plane];
531         nxtf_linesize = nxt_linesize << 1;
532         nxtpf = next->data[plane] + fbase * nxt_linesize;   // next frame, previous field
533         nxtnf = nxtpf + nxtf_linesize;                      // next frame, next     field
534
535         map_linesize <<= 1;
536         if ((match1 >= 3 && field == 1) || (match1 < 3 && field != 1))
537             build_diff_map(fm, prvpf, prvf_linesize, nxtpf, nxtf_linesize,
538                            mapp, map_linesize, height, width, plane);
539         else
540             build_diff_map(fm, prvnf, prvf_linesize, nxtnf, nxtf_linesize,
541                            mapp + map_linesize, map_linesize, height, width, plane);
542
543         for (y = 2; y < height - 2; y += 2) {
544             if (y0a == y1a || y < y0a || y > y1a) {
545                 for (x = startx; x < stopx; x++) {
546                     if (mapp[x] > 0 || mapp[x + map_linesize] > 0) {
547                         temp1 = srcpf[x] + (srcf[x] << 2) + srcnf[x]; // [1 4 1]
548
549                         temp2 = abs(3 * (prvpf[x] + prvnf[x]) - temp1);
550                         if (temp2 > 23 && ((mapp[x]&1) || (mapp[x + map_linesize]&1)))
551                             accumPc += temp2;
552                         if (temp2 > 42) {
553                             if ((mapp[x]&2) || (mapp[x + map_linesize]&2))
554                                 accumPm += temp2;
555                             if ((mapp[x]&4) || (mapp[x + map_linesize]&4))
556                                 accumPml += temp2;
557                         }
558
559                         temp2 = abs(3 * (nxtpf[x] + nxtnf[x]) - temp1);
560                         if (temp2 > 23 && ((mapp[x]&1) || (mapp[x + map_linesize]&1)))
561                             accumNc += temp2;
562                         if (temp2 > 42) {
563                             if ((mapp[x]&2) || (mapp[x + map_linesize]&2))
564                                 accumNm += temp2;
565                             if ((mapp[x]&4) || (mapp[x + map_linesize]&4))
566                                 accumNml += temp2;
567                         }
568                     }
569                 }
570             }
571             prvpf += prvf_linesize;
572             prvnf += prvf_linesize;
573             srcpf += srcf_linesize;
574             srcf  += srcf_linesize;
575             srcnf += srcf_linesize;
576             nxtpf += nxtf_linesize;
577             nxtnf += nxtf_linesize;
578             mapp  += map_linesize;
579         }
580     }
581
582     if (accumPm < 500 && accumNm < 500 && (accumPml >= 500 || accumNml >= 500) &&
583         FFMAX(accumPml,accumNml) > 3*FFMIN(accumPml,accumNml)) {
584         accumPm = accumPml;
585         accumNm = accumNml;
586     }
587
588     norm1 = (int)((accumPc / 6.0f) + 0.5f);
589     norm2 = (int)((accumNc / 6.0f) + 0.5f);
590     mtn1  = (int)((accumPm / 6.0f) + 0.5f);
591     mtn2  = (int)((accumNm / 6.0f) + 0.5f);
592     c1 = ((float)FFMAX(norm1,norm2)) / ((float)FFMAX(FFMIN(norm1,norm2),1));
593     c2 = ((float)FFMAX(mtn1, mtn2))  / ((float)FFMAX(FFMIN(mtn1, mtn2), 1));
594     mr = ((float)FFMAX(mtn1, mtn2))  / ((float)FFMAX(FFMAX(norm1,norm2),1));
595     if (((mtn1 >=  500 || mtn2 >=  500) && (mtn1*2 < mtn2*1 || mtn2*2 < mtn1*1)) ||
596         ((mtn1 >= 1000 || mtn2 >= 1000) && (mtn1*3 < mtn2*2 || mtn2*3 < mtn1*2)) ||
597         ((mtn1 >= 2000 || mtn2 >= 2000) && (mtn1*5 < mtn2*4 || mtn2*5 < mtn1*4)) ||
598         ((mtn1 >= 4000 || mtn2 >= 4000) && c2 > c1))
599         ret = mtn1 > mtn2 ? match2 : match1;
600     else if (mr > 0.005 && FFMAX(mtn1, mtn2) > 150 && (mtn1*2 < mtn2*1 || mtn2*2 < mtn1*1))
601         ret = mtn1 > mtn2 ? match2 : match1;
602     else
603         ret = norm1 > norm2 ? match2 : match1;
604     return ret;
605 }
606
607 static void copy_fields(const FieldMatchContext *fm, AVFrame *dst,
608                         const AVFrame *src, int field)
609 {
610     int plane;
611     for (plane = 0; plane < 4 && src->data[plane] && src->linesize[plane]; plane++) {
612         const int plane_h = get_height(fm, src, plane);
613         const int nb_copy_fields = (plane_h >> 1) + (field ? 0 : (plane_h & 1));
614         av_image_copy_plane(dst->data[plane] + field*dst->linesize[plane], dst->linesize[plane] << 1,
615                             src->data[plane] + field*src->linesize[plane], src->linesize[plane] << 1,
616                             get_width(fm, src, plane), nb_copy_fields);
617     }
618 }
619
620 static AVFrame *create_weave_frame(AVFilterContext *ctx, int match, int field,
621                                    const AVFrame *prv, AVFrame *src, const AVFrame *nxt)
622 {
623     AVFrame *dst;
624     FieldMatchContext *fm = ctx->priv;
625
626     if (match == mC) {
627         dst = av_frame_clone(src);
628     } else {
629         AVFilterLink *outlink = ctx->outputs[0];
630
631         dst = ff_get_video_buffer(outlink, outlink->w, outlink->h);
632         if (!dst)
633             return NULL;
634         av_frame_copy_props(dst, src);
635
636         switch (match) {
637         case mP: copy_fields(fm, dst, src, 1-field); copy_fields(fm, dst, prv,   field); break;
638         case mN: copy_fields(fm, dst, src, 1-field); copy_fields(fm, dst, nxt,   field); break;
639         case mB: copy_fields(fm, dst, src,   field); copy_fields(fm, dst, prv, 1-field); break;
640         case mU: copy_fields(fm, dst, src,   field); copy_fields(fm, dst, nxt, 1-field); break;
641         default: av_assert0(0);
642         }
643     }
644     return dst;
645 }
646
647 static int checkmm(AVFilterContext *ctx, int *combs, int m1, int m2,
648                    AVFrame **gen_frames, int field)
649 {
650     const FieldMatchContext *fm = ctx->priv;
651
652 #define LOAD_COMB(mid) do {                                                     \
653     if (combs[mid] < 0) {                                                       \
654         if (!gen_frames[mid])                                                   \
655             gen_frames[mid] = create_weave_frame(ctx, mid, field,               \
656                                                  fm->prv, fm->src, fm->nxt);    \
657         combs[mid] = calc_combed_score(fm, gen_frames[mid]);                    \
658     }                                                                           \
659 } while (0)
660
661     LOAD_COMB(m1);
662     LOAD_COMB(m2);
663
664     if ((combs[m2] * 3 < combs[m1] || (combs[m2] * 2 < combs[m1] && combs[m1] > fm->combpel)) &&
665         abs(combs[m2] - combs[m1]) >= 30 && combs[m2] < fm->combpel)
666         return m2;
667     else
668         return m1;
669 }
670
671 static const int fxo0m[] = { mP, mC, mN, mB, mU };
672 static const int fxo1m[] = { mN, mC, mP, mU, mB };
673
674 static int filter_frame(AVFilterLink *inlink, AVFrame *in)
675 {
676     AVFilterContext *ctx  = inlink->dst;
677     AVFilterLink *outlink = ctx->outputs[0];
678     FieldMatchContext *fm = ctx->priv;
679     int combs[] = { -1, -1, -1, -1, -1 };
680     int order, field, i, match, sc = 0;
681     const int *fxo;
682     AVFrame *gen_frames[] = { NULL, NULL, NULL, NULL, NULL };
683     AVFrame *dst;
684
685     /* update frames queue(s) */
686 #define SLIDING_FRAME_WINDOW(prv, src, nxt) do {                \
687         if (prv != src) /* 2nd loop exception (1st has prv==src and we don't want to loose src) */ \
688             av_frame_free(&prv);                                \
689         prv = src;                                              \
690         src = nxt;                                              \
691         if (in)                                                 \
692             nxt = in;                                           \
693         if (!prv)                                               \
694             prv = src;                                          \
695         if (!prv) /* received only one frame at that point */   \
696             return 0;                                           \
697         av_assert0(prv && src && nxt);                          \
698 } while (0)
699     if (FF_INLINK_IDX(inlink) == INPUT_MAIN) {
700         SLIDING_FRAME_WINDOW(fm->prv, fm->src, fm->nxt);
701         fm->got_frame[INPUT_MAIN] = 1;
702     } else {
703         SLIDING_FRAME_WINDOW(fm->prv2, fm->src2, fm->nxt2);
704         fm->got_frame[INPUT_CLEANSRC] = 1;
705     }
706     if (!fm->got_frame[INPUT_MAIN] || (fm->ppsrc && !fm->got_frame[INPUT_CLEANSRC]))
707         return 0;
708     fm->got_frame[INPUT_MAIN] = fm->got_frame[INPUT_CLEANSRC] = 0;
709     in = fm->src;
710
711     /* parity */
712     order = fm->order != FM_PARITY_AUTO ? fm->order : (in->interlaced_frame ? in->top_field_first : 1);
713     field = fm->field != FM_PARITY_AUTO ? fm->field : order;
714     av_assert0(order == 0 || order == 1 || field == 0 || field == 1);
715     fxo = field ^ order ? fxo1m : fxo0m;
716
717     /* debug mode: we generate all the fields combinations and their associated
718      * combed score. XXX: inject as frame metadata? */
719     if (fm->combdbg) {
720         for (i = 0; i < FF_ARRAY_ELEMS(combs); i++) {
721             if (i > mN && fm->combdbg == COMBDBG_PCN)
722                 break;
723             gen_frames[i] = create_weave_frame(ctx, i, field, fm->prv, fm->src, fm->nxt);
724             if (!gen_frames[i])
725                 return AVERROR(ENOMEM);
726             combs[i] = calc_combed_score(fm, gen_frames[i]);
727         }
728         av_log(ctx, AV_LOG_INFO, "COMBS: %3d %3d %3d %3d %3d\n",
729                combs[0], combs[1], combs[2], combs[3], combs[4]);
730     } else {
731         gen_frames[mC] = av_frame_clone(fm->src);
732         if (!gen_frames[mC])
733             return AVERROR(ENOMEM);
734     }
735
736     /* p/c selection and optional 3-way p/c/n matches */
737     match = compare_fields(fm, fxo[mC], fxo[mP], field);
738     if (fm->mode == MODE_PCN || fm->mode == MODE_PCN_UB)
739         match = compare_fields(fm, match, fxo[mN], field);
740
741     /* scene change check */
742     if (fm->combmatch == COMBMATCH_SC) {
743         if (fm->lastn == outlink->frame_count_in - 1) {
744             if (fm->lastscdiff > fm->scthresh)
745                 sc = 1;
746         } else if (luma_abs_diff(fm->prv, fm->src) > fm->scthresh) {
747             sc = 1;
748         }
749
750         if (!sc) {
751             fm->lastn = outlink->frame_count_in;
752             fm->lastscdiff = luma_abs_diff(fm->src, fm->nxt);
753             sc = fm->lastscdiff > fm->scthresh;
754         }
755     }
756
757     if (fm->combmatch == COMBMATCH_FULL || (fm->combmatch == COMBMATCH_SC && sc)) {
758         switch (fm->mode) {
759         /* 2-way p/c matches */
760         case MODE_PC:
761             match = checkmm(ctx, combs, match, match == fxo[mP] ? fxo[mC] : fxo[mP], gen_frames, field);
762             break;
763         case MODE_PC_N:
764             match = checkmm(ctx, combs, match, fxo[mN], gen_frames, field);
765             break;
766         case MODE_PC_U:
767             match = checkmm(ctx, combs, match, fxo[mU], gen_frames, field);
768             break;
769         case MODE_PC_N_UB:
770             match = checkmm(ctx, combs, match, fxo[mN], gen_frames, field);
771             match = checkmm(ctx, combs, match, fxo[mU], gen_frames, field);
772             match = checkmm(ctx, combs, match, fxo[mB], gen_frames, field);
773             break;
774         /* 3-way p/c/n matches */
775         case MODE_PCN:
776             match = checkmm(ctx, combs, match, match == fxo[mP] ? fxo[mC] : fxo[mP], gen_frames, field);
777             break;
778         case MODE_PCN_UB:
779             match = checkmm(ctx, combs, match, fxo[mU], gen_frames, field);
780             match = checkmm(ctx, combs, match, fxo[mB], gen_frames, field);
781             break;
782         default:
783             av_assert0(0);
784         }
785     }
786
787     /* get output frame and drop the others */
788     if (fm->ppsrc) {
789         /* field matching was based on a filtered/post-processed input, we now
790          * pick the untouched fields from the clean source */
791         dst = create_weave_frame(ctx, match, field, fm->prv2, fm->src2, fm->nxt2);
792     } else {
793         if (!gen_frames[match]) { // XXX: is that possible?
794             dst = create_weave_frame(ctx, match, field, fm->prv, fm->src, fm->nxt);
795         } else {
796             dst = gen_frames[match];
797             gen_frames[match] = NULL;
798         }
799     }
800     if (!dst)
801         return AVERROR(ENOMEM);
802     for (i = 0; i < FF_ARRAY_ELEMS(gen_frames); i++)
803         av_frame_free(&gen_frames[i]);
804
805     /* mark the frame we are unable to match properly as interlaced so a proper
806      * de-interlacer can take the relay */
807     dst->interlaced_frame = combs[match] >= fm->combpel;
808     if (dst->interlaced_frame) {
809         av_log(ctx, AV_LOG_WARNING, "Frame #%"PRId64" at %s is still interlaced\n",
810                outlink->frame_count_in, av_ts2timestr(in->pts, &inlink->time_base));
811         dst->top_field_first = field;
812     }
813
814     av_log(ctx, AV_LOG_DEBUG, "SC:%d | COMBS: %3d %3d %3d %3d %3d (combpel=%d)"
815            " match=%d combed=%s\n", sc, combs[0], combs[1], combs[2], combs[3], combs[4],
816            fm->combpel, match, dst->interlaced_frame ? "YES" : "NO");
817
818     return ff_filter_frame(outlink, dst);
819 }
820
821 static int request_inlink(AVFilterContext *ctx, int lid)
822 {
823     int ret = 0;
824     FieldMatchContext *fm = ctx->priv;
825
826     if (!fm->got_frame[lid]) {
827         AVFilterLink *inlink = ctx->inputs[lid];
828         ret = ff_request_frame(inlink);
829         if (ret == AVERROR_EOF) { // flushing
830             fm->eof |= 1 << lid;
831             ret = filter_frame(inlink, NULL);
832         }
833     }
834     return ret;
835 }
836
837 static int request_frame(AVFilterLink *outlink)
838 {
839     int ret;
840     AVFilterContext *ctx = outlink->src;
841     FieldMatchContext *fm = ctx->priv;
842     const uint32_t eof_mask = 1<<INPUT_MAIN | fm->ppsrc<<INPUT_CLEANSRC;
843
844     if ((fm->eof & eof_mask) == eof_mask) // flush done?
845         return AVERROR_EOF;
846     if ((ret = request_inlink(ctx, INPUT_MAIN)) < 0)
847         return ret;
848     if (fm->ppsrc && (ret = request_inlink(ctx, INPUT_CLEANSRC)) < 0)
849         return ret;
850     return 0;
851 }
852
853 static int query_formats(AVFilterContext *ctx)
854 {
855     // TODO: second input source can support >8bit depth
856     static const enum AVPixelFormat pix_fmts[] = {
857         AV_PIX_FMT_YUV444P,  AV_PIX_FMT_YUV422P,  AV_PIX_FMT_YUV420P,
858         AV_PIX_FMT_YUV411P,  AV_PIX_FMT_YUV410P,
859         AV_PIX_FMT_NONE
860     };
861     AVFilterFormats *fmts_list = ff_make_format_list(pix_fmts);
862     if (!fmts_list)
863         return AVERROR(ENOMEM);
864     return ff_set_common_formats(ctx, fmts_list);
865 }
866
867 static int config_input(AVFilterLink *inlink)
868 {
869     int ret;
870     AVFilterContext *ctx = inlink->dst;
871     FieldMatchContext *fm = ctx->priv;
872     const AVPixFmtDescriptor *pix_desc = av_pix_fmt_desc_get(inlink->format);
873     const int w = inlink->w;
874     const int h = inlink->h;
875
876     fm->scthresh = (int64_t)((w * h * 255.0 * fm->scthresh_flt) / 100.0);
877
878     if ((ret = av_image_alloc(fm->map_data,   fm->map_linesize,   w, h, inlink->format, 32)) < 0 ||
879         (ret = av_image_alloc(fm->cmask_data, fm->cmask_linesize, w, h, inlink->format, 32)) < 0)
880         return ret;
881
882     fm->hsub = pix_desc->log2_chroma_w;
883     fm->vsub = pix_desc->log2_chroma_h;
884
885     fm->tpitchy  = FFALIGN(w,      16);
886     fm->tpitchuv = FFALIGN(w >> 1, 16);
887
888     fm->tbuffer = av_malloc(h/2 * fm->tpitchy);
889     fm->c_array = av_malloc((((w + fm->blockx/2)/fm->blockx)+1) *
890                             (((h + fm->blocky/2)/fm->blocky)+1) *
891                             4 * sizeof(*fm->c_array));
892     if (!fm->tbuffer || !fm->c_array)
893         return AVERROR(ENOMEM);
894
895     return 0;
896 }
897
898 static av_cold int fieldmatch_init(AVFilterContext *ctx)
899 {
900     const FieldMatchContext *fm = ctx->priv;
901     AVFilterPad pad = {
902         .name         = av_strdup("main"),
903         .type         = AVMEDIA_TYPE_VIDEO,
904         .filter_frame = filter_frame,
905         .config_props = config_input,
906     };
907
908     if (!pad.name)
909         return AVERROR(ENOMEM);
910     ff_insert_inpad(ctx, INPUT_MAIN, &pad);
911
912     if (fm->ppsrc) {
913         pad.name = av_strdup("clean_src");
914         pad.config_props = NULL;
915         if (!pad.name)
916             return AVERROR(ENOMEM);
917         ff_insert_inpad(ctx, INPUT_CLEANSRC, &pad);
918     }
919
920     if ((fm->blockx & (fm->blockx - 1)) ||
921         (fm->blocky & (fm->blocky - 1))) {
922         av_log(ctx, AV_LOG_ERROR, "blockx and blocky settings must be power of two\n");
923         return AVERROR(EINVAL);
924     }
925
926     if (fm->combpel > fm->blockx * fm->blocky) {
927         av_log(ctx, AV_LOG_ERROR, "Combed pixel should not be larger than blockx x blocky\n");
928         return AVERROR(EINVAL);
929     }
930
931     return 0;
932 }
933
934 static av_cold void fieldmatch_uninit(AVFilterContext *ctx)
935 {
936     int i;
937     FieldMatchContext *fm = ctx->priv;
938
939     if (fm->prv != fm->src)
940         av_frame_free(&fm->prv);
941     if (fm->nxt != fm->src)
942         av_frame_free(&fm->nxt);
943     av_frame_free(&fm->src);
944     av_freep(&fm->map_data[0]);
945     av_freep(&fm->cmask_data[0]);
946     av_freep(&fm->tbuffer);
947     av_freep(&fm->c_array);
948     for (i = 0; i < ctx->nb_inputs; i++)
949         av_freep(&ctx->input_pads[i].name);
950 }
951
952 static int config_output(AVFilterLink *outlink)
953 {
954     AVFilterContext *ctx  = outlink->src;
955     const FieldMatchContext *fm = ctx->priv;
956     const AVFilterLink *inlink =
957         ctx->inputs[fm->ppsrc ? INPUT_CLEANSRC : INPUT_MAIN];
958
959     outlink->time_base = inlink->time_base;
960     outlink->sample_aspect_ratio = inlink->sample_aspect_ratio;
961     outlink->frame_rate = inlink->frame_rate;
962     outlink->w = inlink->w;
963     outlink->h = inlink->h;
964     return 0;
965 }
966
967 static const AVFilterPad fieldmatch_outputs[] = {
968     {
969         .name          = "default",
970         .type          = AVMEDIA_TYPE_VIDEO,
971         .request_frame = request_frame,
972         .config_props  = config_output,
973     },
974     { NULL }
975 };
976
977 AVFilter ff_vf_fieldmatch = {
978     .name           = "fieldmatch",
979     .description    = NULL_IF_CONFIG_SMALL("Field matching for inverse telecine."),
980     .query_formats  = query_formats,
981     .priv_size      = sizeof(FieldMatchContext),
982     .init           = fieldmatch_init,
983     .uninit         = fieldmatch_uninit,
984     .inputs         = NULL,
985     .outputs        = fieldmatch_outputs,
986     .priv_class     = &fieldmatch_class,
987     .flags          = AVFILTER_FLAG_DYNAMIC_INPUTS,
988 };