2e6d09b69d51fa9fbfe6afc04edb0ecf5fa629aa
[vlc.git] / modules / video_filter / deinterlace / algo_ivtc.c
1 /*****************************************************************************
2  * algo_ivtc.c : IVTC (inverse telecine) algorithm for the VLC deinterlacer
3  *****************************************************************************
4  * Copyright (C) 2010-2011 the VideoLAN team
5  *
6  * Author: Juha Jeronen <juha.jeronen@jyu.fi>
7  *
8  * This program is free software; you can redistribute it and/or modify it
9  * under the terms of the GNU Lesser General Public License as published by
10  * the Free Software Foundation; either version 2.1 of the License, or
11  * (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU Lesser General Public License for more details.
17  *
18  * You should have received a copy of the GNU Lesser General Public License
19  * along with this program; if not, write to the Free Software Foundation,
20  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
21  *****************************************************************************/
22
23 #ifdef HAVE_CONFIG_H
24 #   include "config.h"
25 #endif
26
27 #ifdef CAN_COMPILE_MMXEXT
28 #   include "mmx.h"
29 #endif
30
31 #include <stdint.h>
32 #include <assert.h>
33
34 #include <vlc_common.h>
35 #include <vlc_cpu.h>
36 #include <vlc_picture.h>
37 #include <vlc_filter.h>
38
39 #include "deinterlace.h" /* filter_sys_t */
40 #include "helpers.h"
41
42 #include "algo_ivtc.h"
43
44 /*****************************************************************************
45  * Local data
46  *****************************************************************************/
47
48 /* Fasten your seatbelt - lots of IVTC constants follow... */
49
50 /**
51  * IVTC filter modes.
52  *
53  * Hard telecine: burned into video stream.
54  * Soft telecine: stream consists of progressive frames;
55  *                telecining handled by stream flags.
56  *
57  * @see ivtc_sys_t
58  * @see RenderIVTC()
59  */
60 typedef enum { IVTC_MODE_DETECTING           = 0,
61                IVTC_MODE_TELECINED_NTSC_HARD = 1,
62                IVTC_MODE_TELECINED_NTSC_SOFT = 2 } ivtc_mode;
63
64 /**
65  *  Field pair combinations from successive frames in the PCN stencil.
66  *  T = top, B = bottom, P = previous, C = current, N = next
67  *  These are used as array indices; hence the explicit numbering.
68  */
69 typedef enum { FIELD_PAIR_TPBP = 0, FIELD_PAIR_TPBC = 1,
70                FIELD_PAIR_TCBP = 2, FIELD_PAIR_TCBC = 3,
71                FIELD_PAIR_TCBN = 4, FIELD_PAIR_TNBC = 5,
72                FIELD_PAIR_TNBN = 6 } ivtc_field_pair;
73
74 /* Note: only valid ones count for NUM */
75 #define NUM_CADENCE_POS 9
76 /**
77  * Cadence positions for the PCN stencil (PCN, Previous Current Next).
78  *
79  * Note that "dea" in both cadence tables and a pure progressive signal
80  * are indistinguishable.
81  *
82  * Used as array indices except the -1.
83  *
84  * This is a combined raw position containing both i_cadence_pos
85  * and telecine field dominance.
86  * @see pi_detected_pos_to_cadence_pos
87  * @see pi_detected_pos_to_tfd
88  */
89 typedef enum { CADENCE_POS_INVALID     = -1,
90                CADENCE_POS_PROGRESSIVE =  0,
91                CADENCE_POS_TFF_ABC     =  1,
92                CADENCE_POS_TFF_BCD     =  2,
93                CADENCE_POS_TFF_CDE     =  3,
94                CADENCE_POS_TFF_EAB     =  4,
95                CADENCE_POS_BFF_ABC     =  5,
96                CADENCE_POS_BFF_BCD     =  6,
97                CADENCE_POS_BFF_CDE     =  7,
98                CADENCE_POS_BFF_EAB     =  8 } ivtc_cadence_pos;
99 /* First and one-past-end for TFF-only and BFF-only raw positions. */
100 #define CADENCE_POS_TFF_FIRST 1
101 #define CADENCE_POS_TFF_END   5
102 #define CADENCE_POS_BFF_FIRST 5
103 #define CADENCE_POS_BFF_END   9
104
105 /**
106  * For the "vektor" cadence detector algorithm.
107  *
108  * The algorithm produces a set of possible positions instead of a unique
109  * position, until it locks on. The set is represented as a bitmask.
110  *
111  * The bitmask is stored in a word, and its layout is:
112  * blank blank BFF_CARRY BFF4 BFF3 BFF2 BFF1 BFF0   (high byte)
113  * blank blank TFF_CARRY TFF4 TFF3 TFF2 TFF1 TFF0   (low byte)
114  *
115  * This allows predicting the next position by left-shifting the previous
116  * result by one bit, copying the CARRY bits to the respective zeroth position,
117  * and ANDing with 0x1F1F.
118  *
119  * This table is indexed with a valid ivtc_cadence_pos.
120  * @see ivtc_cadence_pos
121  */
122 const int pi_detected_pos_to_bitmask[NUM_CADENCE_POS] = { 0x0808, /* prog. */
123                                                           0x0001, /* TFF ABC */
124                                                           0x0002, /* TFF BCD */
125                                                           0x0004, /* TFF CDE */
126                                                           0x0010, /* TFF EAB */
127                                                           0x0100, /* BFF ABC */
128                                                           0x0200, /* BFF BCD */
129                                                           0x0400, /* BFF CDE */
130                                                           0x1000, /* BFF EAB */
131                                                         };
132 #define VEKTOR_CADENCE_POS_ALL 0x1F1F
133 #define VEKTOR_CADENCE_POS_TFF 0x00FF
134 #define VEKTOR_CADENCE_POS_BFF 0xFF00
135 #define VEKTOR_CADENCE_POS_TFF_HIGH 0x0010
136 #define VEKTOR_CADENCE_POS_TFF_LOW  0x0001
137 #define VEKTOR_CADENCE_POS_BFF_HIGH 0x1000
138 #define VEKTOR_CADENCE_POS_BFF_LOW  0x0100
139
140 /* Telecine field dominance */
141 typedef enum { TFD_INVALID = -1, TFD_TFF = 0, TFD_BFF = 1 } ivtc_tfd;
142
143 /**
144  * Position detection table for the "scores" cadence detector algorithm.
145  *
146  * These are the (only) field pair combinations that should give progressive
147  * frames. There are three for each position.
148  *
149  * First index: ivtc_cadence_pos
150  */
151 static const ivtc_field_pair pi_best_field_pairs[NUM_CADENCE_POS][3] = {
152     {FIELD_PAIR_TPBP, FIELD_PAIR_TCBC, FIELD_PAIR_TNBN}, /* prog. */
153
154     {FIELD_PAIR_TPBP, FIELD_PAIR_TCBP, FIELD_PAIR_TNBC}, /* TFF ABC */
155     {FIELD_PAIR_TCBP, FIELD_PAIR_TNBC, FIELD_PAIR_TNBN}, /* TFF BCD */
156     {FIELD_PAIR_TCBP, FIELD_PAIR_TCBC, FIELD_PAIR_TNBN}, /* TFF CDE */
157     {FIELD_PAIR_TPBP, FIELD_PAIR_TCBC, FIELD_PAIR_TNBC}, /* TFF EAB */
158
159     {FIELD_PAIR_TPBP, FIELD_PAIR_TPBC, FIELD_PAIR_TCBN}, /* BFF ABC */
160     {FIELD_PAIR_TPBC, FIELD_PAIR_TCBN, FIELD_PAIR_TNBN}, /* BFF BCD */
161     {FIELD_PAIR_TPBC, FIELD_PAIR_TCBC, FIELD_PAIR_TNBN}, /* BFF CDE */
162     {FIELD_PAIR_TPBP, FIELD_PAIR_TCBC, FIELD_PAIR_TCBN}, /* BFF EAB */
163 };
164
165 /**
166  * Alternative position detection table for the "scores" cadence detector
167  * algorithm.
168  *
169  * These field pair combinations should give only interlaced frames.
170  * There are four for each position.
171  *
172  * First index: ivtc_cadence_pos
173  *
174  * Currently unused. During development it was tested that whether we detect
175  * best or worst, the resulting detected cadence positions are identical
176  * (neither strategy performs any different from the other).
177  */
178 #if 0
179 static const ivtc_field_pair pi_worst_field_pairs[NUM_CADENCE_POS][4] = {
180     {FIELD_PAIR_TPBC, FIELD_PAIR_TCBP,
181         FIELD_PAIR_TCBN, FIELD_PAIR_TNBC}, /* prog. */
182
183     {FIELD_PAIR_TPBC, FIELD_PAIR_TCBC,
184         FIELD_PAIR_TCBN, FIELD_PAIR_TNBN}, /* TFF ABC */
185     {FIELD_PAIR_TPBP, FIELD_PAIR_TPBC,
186         FIELD_PAIR_TCBC, FIELD_PAIR_TCBN}, /* TFF BCD */
187     {FIELD_PAIR_TPBP, FIELD_PAIR_TPBC,
188         FIELD_PAIR_TCBN, FIELD_PAIR_TNBC}, /* TFF CDE */
189     {FIELD_PAIR_TPBC, FIELD_PAIR_TCBP,
190         FIELD_PAIR_TCBN, FIELD_PAIR_TNBN}, /* TFF EAB */
191
192     {FIELD_PAIR_TCBP, FIELD_PAIR_TCBC,
193         FIELD_PAIR_TNBC, FIELD_PAIR_TNBN}, /* BFF ABC */
194     {FIELD_PAIR_TPBP, FIELD_PAIR_TCBP,
195         FIELD_PAIR_TCBC, FIELD_PAIR_TNBC}, /* BFF BCD */
196     {FIELD_PAIR_TPBP, FIELD_PAIR_TCBP,
197         FIELD_PAIR_TNBC, FIELD_PAIR_TCBN}, /* BFF CDE */
198     {FIELD_PAIR_TCBP, FIELD_PAIR_TPBC,
199         FIELD_PAIR_TNBC, FIELD_PAIR_TNBN}, /* BFF EAB */
200 };
201 #endif
202
203 /**
204  * Table for extracting the i_cadence_pos part of detected cadence position
205  * (ivtc_cadence_pos).
206  *
207  * The counter goes from 0 to 4, where "abc" = 0, "bcd" = 1, ...
208  *
209  * @see ivtc_cadence_pos
210  */
211 static const int pi_detected_pos_to_cadence_pos[NUM_CADENCE_POS] = {
212     3, /* prog. */
213     0, /* TFF ABC */
214     1, /* TFF BCD */
215     2, /* TFF CDE */
216     4, /* TFF EAB */
217     0, /* BFF ABC */
218     1, /* BFF BCD */
219     2, /* BFF CDE */
220     4, /* BFF EAB */
221 };
222
223 /**
224  * Table for extracting the telecine field dominance part of detected
225  * cadence position (ivtc_cadence_pos).
226  *
227  * The position "dea" does not provide TFF/BFF information, because it is
228  * indistinguishable from progressive.
229  *
230  * @see ivtc_cadence_pos
231  */
232 static const int pi_detected_pos_to_tfd[NUM_CADENCE_POS] = {
233     TFD_INVALID, /* prog. */
234     TFD_TFF, /* TFF ABC */
235     TFD_TFF, /* TFF BCD */
236     TFD_TFF, /* TFF CDE */
237     TFD_TFF, /* TFF EAB */
238     TFD_BFF, /* BFF ABC */
239     TFD_BFF, /* BFF BCD */
240     TFD_BFF, /* BFF CDE */
241     TFD_BFF, /* BFF EAB */
242 };
243
244 /* Valid telecine sequences (TFF and BFF). Indices: [TFD][i_cadence_pos] */
245 /* Currently unused and left here for documentation only.
246    There is an easier way - just decode the i_cadence_pos part of the
247    detected position using the pi_detected_pos_to_cadence_pos table,
248    and check that it is successive mod 5. See IVTCCadenceAnalyze(). */
249 /*static const int pi_valid_cadences[2][5] = { {CADENCE_POS_TFF_ABC,
250                                              CADENCE_POS_TFF_BCD,
251                                              CADENCE_POS_TFF_CDE,
252                                              CADENCE_POS_PROGRESSIVE,
253                                              CADENCE_POS_TFF_EAB},
254
255                                              {CADENCE_POS_BFF_ABC,
256                                              CADENCE_POS_BFF_BCD,
257                                              CADENCE_POS_BFF_CDE,
258                                              CADENCE_POS_PROGRESSIVE,
259                                              CADENCE_POS_BFF_EAB},
260                                            };
261 */
262
263 /**
264  * Operations needed in film frame reconstruction.
265  */
266 typedef enum { IVTC_OP_DROP_FRAME,
267                IVTC_OP_COPY_N,
268                IVTC_OP_COPY_C,
269                IVTC_OP_COMPOSE_TNBC,
270                IVTC_OP_COMPOSE_TCBN } ivtc_op;
271
272 /* Note: During hard IVTC, we must avoid COPY_C and do a compose instead.
273    If we COPY_C, some subtitles will flicker badly, even if we use the
274    cadence-based film frame reconstruction. Try the first scene in
275    Kanon (2006) vol. 3 to see the problem.
276
277    COPY_C can be used without problems when it is used consistently
278    (not constantly mixed in with COPY_N and compose operations),
279    for example in soft IVTC.
280 */
281 /**
282  * Operation table for film frame reconstruction depending on cadence position.
283  * Indices: [TFD][i_cadence_pos]
284  * @see pi_detected_pos_to_tfd
285  * @see pi_detected_pos_to_cadence_pos
286  */
287 static const ivtc_op pi_reconstruction_ops[2][5] = { /* TFF */
288                                                      {IVTC_OP_COMPOSE_TNBC,
289                                                       IVTC_OP_COPY_N,
290                                                       IVTC_OP_COPY_N,
291                                                       IVTC_OP_DROP_FRAME,
292                                                       IVTC_OP_COMPOSE_TNBC},
293
294                                                      /* BFF */
295                                                      {IVTC_OP_COMPOSE_TCBN,
296                                                       IVTC_OP_COPY_N,
297                                                       IVTC_OP_COPY_N,
298                                                       IVTC_OP_DROP_FRAME,
299                                                       IVTC_OP_COMPOSE_TCBN},
300                                                    };
301
302 /**
303  * Timestamp mangling table.
304  *
305  * This is used in the 29.97 -> 23.976 fps conversion.
306  *
307  * Index: i_cadence_pos, 0..4.
308  *
309  * Valid values are nonnegative. The -1 corresponds to the dropped frame
310  * and is never used, except for a debug assert.
311  *
312  * The unit of the values is 1/4 of frame duration.
313  * See the function documentation of RenderIVTC() for an explanation.
314  * @see ivtc_cadence_pos
315  * @see pi_detected_pos_to_cadence_pos
316  * @see pi_reconstruction_ops
317  * @see RenderIVTC()
318  */
319 static const int pi_timestamp_deltas[5] = { 1, 2, 3, -1, 0 };
320
321 /*****************************************************************************
322  * Internal functions
323  *****************************************************************************/
324
325 /**
326  * Internal helper function for RenderIVTC(): performs initialization
327  * at the start of a new frame.
328  *
329  * In practice, this slides detector histories.
330  *
331  * This function should only perform initialization that does NOT require
332  * the input frame history buffer. This runs at every frame, including
333  * the first two.
334  *
335  * This is an internal function only used by RenderIVTC().
336  * There is no need to call this function manually.
337  *
338  * @param p_filter The filter instance.
339  * @see RenderIVTC()
340  */
341 static void IVTCFrameInit( filter_t *p_filter )
342 {
343     assert( p_filter != NULL );
344
345     filter_sys_t *p_sys = p_filter->p_sys;
346     ivtc_sys_t *p_ivtc  = &p_sys->ivtc;
347
348     /* Slide detector histories */
349     for( int i = 1; i < IVTC_DETECTION_HISTORY_SIZE; i++ )
350     {
351         p_ivtc->pi_top_rep[i-1] = p_ivtc->pi_top_rep[i];
352         p_ivtc->pi_bot_rep[i-1] = p_ivtc->pi_bot_rep[i];
353         p_ivtc->pi_motion[i-1]  = p_ivtc->pi_motion[i];
354
355         p_ivtc->pi_s_cadence_pos[i-1] = p_ivtc->pi_s_cadence_pos[i];
356         p_ivtc->pb_s_reliable[i-1]    = p_ivtc->pb_s_reliable[i];
357         p_ivtc->pi_v_cadence_pos[i-1] = p_ivtc->pi_v_cadence_pos[i];
358         p_ivtc->pi_v_raw[i-1]         = p_ivtc->pi_v_raw[i];
359         p_ivtc->pb_v_reliable[i-1]    = p_ivtc->pb_v_reliable[i];
360
361         p_ivtc->pi_cadence_pos_history[i-1]
362                                       = p_ivtc->pi_cadence_pos_history[i];
363
364         p_ivtc->pb_all_progressives[i-1] = p_ivtc->pb_all_progressives[i];
365     }
366     /* The latest position has not been detected yet. */
367     p_ivtc->pi_s_cadence_pos[IVTC_LATEST] = CADENCE_POS_INVALID;
368     p_ivtc->pb_s_reliable[IVTC_LATEST]    = false;
369     p_ivtc->pi_v_cadence_pos[IVTC_LATEST] = CADENCE_POS_INVALID;
370     p_ivtc->pi_v_raw[IVTC_LATEST]         = VEKTOR_CADENCE_POS_ALL;
371     p_ivtc->pb_v_reliable[IVTC_LATEST]    = false;
372     p_ivtc->pi_cadence_pos_history[IVTC_LATEST] = CADENCE_POS_INVALID;
373     p_ivtc->pi_top_rep[IVTC_LATEST] =  0;
374     p_ivtc->pi_bot_rep[IVTC_LATEST] =  0;
375     p_ivtc->pi_motion[IVTC_LATEST]  = -1;
376     p_ivtc->pb_all_progressives[IVTC_LATEST] = false;
377
378     /* Slide history of field pair interlace scores */
379     p_ivtc->pi_scores[FIELD_PAIR_TPBP] = p_ivtc->pi_scores[FIELD_PAIR_TCBC];
380     p_ivtc->pi_scores[FIELD_PAIR_TPBC] = p_ivtc->pi_scores[FIELD_PAIR_TCBN];
381     p_ivtc->pi_scores[FIELD_PAIR_TCBP] = p_ivtc->pi_scores[FIELD_PAIR_TNBC];
382     p_ivtc->pi_scores[FIELD_PAIR_TCBC] = p_ivtc->pi_scores[FIELD_PAIR_TNBN];
383     /* These have not been detected yet */
384     p_ivtc->pi_scores[FIELD_PAIR_TCBN] = 0;
385     p_ivtc->pi_scores[FIELD_PAIR_TNBC] = 0;
386     p_ivtc->pi_scores[FIELD_PAIR_TNBN] = 0;
387 }
388
389 /**
390  * Internal helper function for RenderIVTC(): computes various raw detector
391  * data at the start of a new frame.
392  *
393  * This function requires the input frame history buffer.
394  * IVTCFrameInit() must have been called first.
395  * Last two frames must be available in the history buffer.
396  *
397  * This is an internal function only used by RenderIVTC().
398  * There is no need to call this function manually.
399  *
400  * @param p_filter The filter instance.
401  * @see RenderIVTC()
402  * @see IVTCFrameInit()
403  */
404 static void IVTCLowLevelDetect( filter_t *p_filter )
405 {
406     assert( p_filter != NULL );
407
408     filter_sys_t *p_sys = p_filter->p_sys;
409     ivtc_sys_t *p_ivtc  = &p_sys->ivtc;
410     picture_t *p_curr = p_sys->context.pp_history[1];
411     picture_t *p_next = p_sys->context.pp_history[2];
412
413     assert( p_next != NULL );
414     assert( p_curr != NULL );
415
416     /* Compute interlace scores for TNBN, TNBC and TCBN.
417         Note that p_next contains TNBN. */
418     p_ivtc->pi_scores[FIELD_PAIR_TNBN] = CalculateInterlaceScore( p_next,
419                                                                   p_next );
420     p_ivtc->pi_scores[FIELD_PAIR_TNBC] = CalculateInterlaceScore( p_next,
421                                                                   p_curr );
422     p_ivtc->pi_scores[FIELD_PAIR_TCBN] = CalculateInterlaceScore( p_curr,
423                                                                   p_next );
424
425     int i_top = 0, i_bot = 0;
426     int i_motion = EstimateNumBlocksWithMotion(p_curr, p_next, &i_top, &i_bot);
427     p_ivtc->pi_motion[IVTC_LATEST] = i_motion;
428
429     /* If one field changes "clearly more" than the other, we know the
430        less changed one is a likely duplicate.
431
432        Threshold 1/2 is too low for some scenes (e.g. pan of the space junk
433        at beginning of The Third ep. 1, right after the OP). Thus, we use 2/3,
434        which seems to work.
435     */
436     p_ivtc->pi_top_rep[IVTC_LATEST] = (i_top <= 2*i_bot/3);
437     p_ivtc->pi_bot_rep[IVTC_LATEST] = (i_bot <= 2*i_top/3);
438 }
439
440 /**
441  * Internal helper function for RenderIVTC(): using raw detector data,
442  * detect cadence position by an interlace scores based algorithm ("scores").
443  *
444  * IVTCFrameInit() and IVTCLowLevelDetect() must have been called first.
445  * Last frame must be available in the history buffer.
446  *
447  * This is an internal function only used by RenderIVTC().
448  * There is no need to call this function manually.
449  *
450  * @param p_filter The filter instance.
451  * @see RenderIVTC()
452  * @see IVTCFrameInit()
453  * @see IVTCLowLevelDetect()
454  * @see IVTCCadenceDetectFinalize()
455  */
456 static void IVTCCadenceDetectAlgoScores( filter_t *p_filter )
457 {
458     assert( p_filter != NULL );
459
460     filter_sys_t *p_sys = p_filter->p_sys;
461     ivtc_sys_t *p_ivtc  = &p_sys->ivtc;
462     picture_t *p_next = p_sys->context.pp_history[2];
463
464     assert( p_next != NULL );
465
466     /* Detect likely cadence position according to the tables,
467        using the tabulated combinations of all 7 available interlace scores.
468     */
469     int pi_ivtc_scores[NUM_CADENCE_POS];
470     for( int i = 0; i < NUM_CADENCE_POS; i++ )
471         pi_ivtc_scores[i] = p_ivtc->pi_scores[ pi_best_field_pairs[i][0] ]
472                           + p_ivtc->pi_scores[ pi_best_field_pairs[i][1] ]
473                           + p_ivtc->pi_scores[ pi_best_field_pairs[i][2] ];
474     /* Find minimum */
475     int j = CADENCE_POS_PROGRESSIVE; /* valid regardless of TFD */
476     int minscore = pi_ivtc_scores[j];
477     /* A TFF (respectively BFF) stream may only have TFF (respectively BFF)
478        telecine. Don't bother looking at the wrong table. */
479     int imin = CADENCE_POS_TFF_FIRST; /* first TFF-only entry */
480     int iend = CADENCE_POS_TFF_END;   /* one past last TFF-only entry */
481     if( !p_next->b_top_field_first )
482     {
483         imin = CADENCE_POS_BFF_FIRST; /* first BFF-only entry */
484         iend = CADENCE_POS_BFF_END;   /* one past last BFF-only entry */
485     }
486     for( int i = imin; i < iend; i++ )
487     {
488         if( pi_ivtc_scores[i] < minscore )
489         {
490             minscore = pi_ivtc_scores[i];
491             j = i;
492         }
493     }
494
495     /* Now "j" contains the most likely position according to the tables,
496        accounting also for video TFF/BFF. */
497     p_ivtc->pi_s_cadence_pos[IVTC_LATEST] = j;
498
499     /* Estimate reliability of detector result.
500
501        We do this by checking if the winner is an outlier at least
502        to some extent. For anyone better versed in statistics,
503        feel free to improve this.
504     */
505
506     /* Compute sample mean with the winner included and without.
507
508        Sample mean is defined as mu = sum( x_i, i ) / N ,
509        where N is the number of samples.
510     */
511     int mean = pi_ivtc_scores[CADENCE_POS_PROGRESSIVE];
512     int mean_except_min = 0;
513     if( j != CADENCE_POS_PROGRESSIVE )
514         mean_except_min = pi_ivtc_scores[CADENCE_POS_PROGRESSIVE];
515     for( int i = imin; i < iend; i++ )
516     {
517         mean += pi_ivtc_scores[i];
518         if( i != j )
519             mean_except_min += pi_ivtc_scores[i];
520     }
521     /* iend points one past end, but progressive counts as the +1. */
522     mean /= (iend - imin + 1);
523     mean_except_min /= (iend - imin);
524
525     /* Check how much excluding the winner changes the mean. */
526     double mean_ratio = (double)mean_except_min / (double)mean;
527
528     /* Let's pretend that the detected position is a stochastic variable.
529        Compute sample variance with the winner included and without.
530
531        var = sum( (x_i - mu)^2, i ) / N ,
532
533        where mu is the sample mean.
534
535        Note that we really need int64_t; the numbers are pretty large.
536     */
537     int64_t diff = (int64_t)(pi_ivtc_scores[CADENCE_POS_PROGRESSIVE] - mean);
538     int64_t var = diff*diff;
539     int64_t var_except_min = 0;
540     if( j != CADENCE_POS_PROGRESSIVE )
541     {
542         int64_t diff_exm = (int64_t)(pi_ivtc_scores[CADENCE_POS_PROGRESSIVE]
543                                       - mean_except_min);
544         var_except_min = diff_exm*diff_exm;
545     }
546     for( int i = imin; i < iend; i++ )
547     {
548         diff = (int64_t)(pi_ivtc_scores[i] - mean);
549         var += (diff*diff);
550         if( i != j )
551         {
552             int64_t diff_exm = (int64_t)(pi_ivtc_scores[i] - mean_except_min);
553             var_except_min += (diff_exm*diff_exm);
554         }
555     }
556     /* iend points one past end, but progressive counts as the +1. */
557     var /= (uint64_t)(iend - imin + 1);
558     var_except_min /= (uint64_t)(iend - imin);
559
560     /* Extract cadence counter part of detected positions for the
561        last two frames.
562
563        Note that for the previous frame, we use the final detected cadence
564        position, which was not necessarily produced by this algorithm.
565        It is the result that was judged the most reliable.
566     */
567     int j_curr = p_ivtc->pi_cadence_pos_history[IVTC_LATEST-1];
568     int pos_next = pi_detected_pos_to_cadence_pos[j];
569
570     /* Be optimistic when unsure. We bias the detection toward accepting
571        the next "correct" position, even if the variance check comes up bad.
572     */
573     bool b_expected = false;
574     if( j_curr != CADENCE_POS_INVALID )
575     {
576         int pos_curr = pi_detected_pos_to_cadence_pos[j_curr];
577         b_expected = (pos_next == (pos_curr + 1) % 5);
578     }
579
580     /* Use motion detect result as a final sanity check.
581        If no motion, the result from this algorithm cannot be reliable.
582     */
583     int i_blocks_with_motion = p_ivtc->pi_motion[IVTC_LATEST];
584
585     /* The numbers given here are empirical constants that have been tuned
586        through trial and error. The test material used was NTSC anime DVDs.
587
588         Easy-to-detect parts seem to give variance boosts of 40-70%, but
589         hard-to-detect parts sometimes only 18%. Anything with a smaller boost
590         in variance doesn't seem reliable for catching a new lock-on,
591
592         Additionally, it seems that if the mean changes by less than 0.5%,
593         the result is not reliable.
594
595         Note that the numbers given are only valid for the pi_best_field_pairs
596         detector strategy.
597
598         For motion detection, the detector seems good enough so that
599         we can threshold at zero.
600     */
601     bool b_result_reliable =
602       ( i_blocks_with_motion > 0      &&
603         mean_ratio           > 1.005  &&
604         ( b_expected || ( (double)var > 1.17*(double)var_except_min ) )
605       );
606     p_ivtc->pb_s_reliable[IVTC_LATEST] = b_result_reliable;
607 }
608
609 /**
610  * Internal helper function for RenderIVTC(): using raw detector data,
611  * detect cadence position by a hard field repeat based algorithm ("vektor").
612  *
613  * This algorithm is inspired by the classic TVTime/Xine IVTC filter
614  * by Billy Biggs (Vektor); hence the name. There are however some
615  * differences between this and the TVTime/Xine filter.
616  *
617  * IVTCFrameInit() and IVTCLowLevelDetect() must have been called first.
618  * Last frame must be available in the history buffer.
619  *
620  * This is an internal function only used by RenderIVTC().
621  * There is no need to call this function manually.
622  *
623  * @param p_filter The filter instance.
624  * @see RenderIVTC()
625  * @see IVTCFrameInit()
626  * @see IVTCLowLevelDetect()
627  * @see IVTCCadenceDetectFinalize()
628  */
629 static void IVTCCadenceDetectAlgoVektor( filter_t *p_filter )
630 {
631     assert( p_filter != NULL );
632
633     filter_sys_t *p_sys = p_filter->p_sys;
634     ivtc_sys_t *p_ivtc  = &p_sys->ivtc;
635
636     picture_t *p_next = p_sys->context.pp_history[2];
637
638     assert( p_next != NULL );
639
640     /* This algorithm is based on detecting hard-repeated fields (by motion
641        detection), and conservatively estimating what the seen repeats could
642        mean for the cadence position.
643
644        "Conservative" means that we do not rule out possibilities if repeats
645        are *not* seen, but only *add* possibilities based on what repeats
646        *are* seen. This is important. Otherwise full-frame repeats in the
647        original film (8fps or 12fps animation is very common in anime),
648        causing spurious field repeats, would mess up the detection.
649        With this strategy, spurious repeats will only slow down the lock-on,
650        and will not break an existing lock-on once acquired.
651
652        Several possibilities are kept open until the sequence gives enough
653        information to make a unique detection. When the sequence becomes
654        inconsistent (e.g. bad cut), the detector resets itself.
655
656        The main ideas taken from the TVTime/Xine algorithm are:
657         1) Conservatively using information from detected field repeats,
658         2) Cadence counting the earlier detection results and combining with
659            the new detection result, and
660         3) The observation that video TFF/BFF uniquely determines TFD.
661
662        The main differences are
663         1) Different motion detection (see EstimateNumBlocksWithMotion()).
664            Vektor's original estimates the average top/bottom field diff
665            over the last 3 frames, while ours uses a block-based approach
666            for diffing and just compares the field diffs between "curr" and
667            "next" against each other (see IVTCLowLevelDetect()).
668            Both approaches are adaptive, but in a different way.
669         2) The specific detection logic used is a bit different (see both
670            codes for details; the original is in xine-lib, function
671            determine_pulldown_offset_short_history_new() in pulldown.c;
672            ours is obviously given below). I think the one given here
673            is a bit simpler.
674
675        Note that we don't have to worry about getting a detection in all cases.
676        It's enough if we work reliably, say, 99% of the time, and the other 1%
677        of the time just admit that we don't know the cadence position.
678        (This mostly happens after a bad cut, when the new scene has
679        "difficult" motion characteristics, such as repeated film frames.)
680        Our frame composer is built to handle also cases where we have no
681        reliable detection of the cadence position; see IVTCOutputOrDropFrame().
682        More important is to never lock on incorrectly, as this would both
683        generate interlacing artifacts where none existed, and cause motion
684        to stutter (because duplicate frames would be shown and unique ones
685        dropped).
686     */
687
688     /* Progressive requires no repeats, so it is always a possibility.
689        Filtering will drop it out if we know that the current position
690        cannot be "dea".
691     */
692     int detected = 0;
693     detected |= pi_detected_pos_to_bitmask[ CADENCE_POS_PROGRESSIVE ];
694
695     /* Add in other possibilities depending on field repeats seen during the
696        last three input frames (i.e. two transitions between input frames).
697        See the "Dups." column in the cadence tables.
698     */
699     bool b_top_rep     = p_ivtc->pi_top_rep[IVTC_LATEST];
700     bool b_bot_rep     = p_ivtc->pi_bot_rep[IVTC_LATEST];
701     bool b_old_top_rep = p_ivtc->pi_top_rep[IVTC_LATEST-1];
702     bool b_old_bot_rep = p_ivtc->pi_bot_rep[IVTC_LATEST-1];
703     if( b_top_rep )
704     {
705         detected |= pi_detected_pos_to_bitmask[ CADENCE_POS_TFF_EAB ];
706         detected |= pi_detected_pos_to_bitmask[ CADENCE_POS_BFF_BCD ];
707     }
708     if( b_old_top_rep )
709     {
710         detected |= pi_detected_pos_to_bitmask[ CADENCE_POS_TFF_ABC ];
711         detected |= pi_detected_pos_to_bitmask[ CADENCE_POS_BFF_CDE ];
712     }
713     if( b_bot_rep )
714     {
715         detected |= pi_detected_pos_to_bitmask[ CADENCE_POS_TFF_BCD ];
716         detected |= pi_detected_pos_to_bitmask[ CADENCE_POS_BFF_EAB ];
717     }
718     if( b_old_bot_rep )
719     {
720         detected |= pi_detected_pos_to_bitmask[ CADENCE_POS_TFF_CDE ];
721         detected |= pi_detected_pos_to_bitmask[ CADENCE_POS_BFF_ABC ];
722     }
723
724     /* A TFF stream may only have TFF telecine, and similarly for BFF.
725        Discard the possibility we know to be incorrect for this stream.
726        (The stream may flipflop between the possibilities if it contains
727         soft-telecined sequences or lone field repeats, so we must keep
728         detecting this for each incoming frame.)
729     */
730     bool b_tff = p_next->b_top_field_first;
731     if( b_tff )
732         detected &= VEKTOR_CADENCE_POS_TFF;
733     else
734         detected &= VEKTOR_CADENCE_POS_BFF;
735
736     /* Predict possible next positions based on our last detection.
737        Begin with a shift and carry. */
738     int predicted = p_ivtc->pi_v_raw[IVTC_LATEST-1];
739     bool b_wrap_tff = false;
740     bool b_wrap_bff = false;
741     if( predicted & VEKTOR_CADENCE_POS_TFF_HIGH )
742         b_wrap_tff = true;
743     if( predicted & VEKTOR_CADENCE_POS_BFF_HIGH )
744         b_wrap_bff = true;
745     /* bump to next position and keep only valid bits */
746     predicted = (predicted << 1) & VEKTOR_CADENCE_POS_ALL;
747     /* carry */
748     if( b_wrap_tff )
749         predicted |= VEKTOR_CADENCE_POS_TFF_LOW;
750     if( b_wrap_bff )
751         predicted |= VEKTOR_CADENCE_POS_BFF_LOW;
752
753     /* Filter: narrow down possibilities based on previous detection,
754        if consistent. If not consistent, reset the detector.
755        Reset works better than just using the latest raw detection.
756     */
757     if( (detected & predicted) != 0 )
758         detected = detected & predicted;
759     else
760         detected = VEKTOR_CADENCE_POS_ALL;
761
762     /* We're done. Save result to our internal storage so we can use it
763        for prediction at the next frame.
764
765        Note that the outgoing frame check in IVTCOutputOrDropFrame()
766        has a veto right, resetting our state if it determines that
767        the cadence has become broken.
768     */
769     p_ivtc->pi_v_raw[IVTC_LATEST] = detected;
770
771     /* See if the position has been detected uniquely.
772        If so, we have acquired a lock-on. */
773     ivtc_cadence_pos exact = CADENCE_POS_INVALID;
774     if( detected != 0 )
775     {
776         for( int i = 0; i < NUM_CADENCE_POS; i++ )
777         {
778             /* Note that we must use "&" instead of just equality to catch
779                the progressive case, and also not to trigger on an incomplete
780                detection. */
781             if( detected == (detected & pi_detected_pos_to_bitmask[i]) )
782             {
783                 exact = i;
784                 break;
785             }
786         }
787     }
788
789     /* If the result was unique, now "exact" contains the detected
790        cadence position (and otherwise CADENCE_POS_INVALID).
791
792        In practice, if the result from this algorithm is unique,
793        it is always reliable.
794     */
795     p_ivtc->pi_v_cadence_pos[IVTC_LATEST] =  exact;
796     p_ivtc->pb_v_reliable[IVTC_LATEST]    = (exact != CADENCE_POS_INVALID);
797 }
798
799 /**
800  * Internal helper function for RenderIVTC(): decide the final detected
801  * cadence position for the current position of the PCN stencil,
802  * using the results of the different cadence detection algorithms.
803  *
804  * Must be called after all IVTCCadenceDetectAlgo*() functions.
805  *
806  * This is an internal function only used by RenderIVTC().
807  * There is no need to call this function manually.
808  *
809  * @param p_filter The filter instance.
810  * @see RenderIVTC()
811  * @see IVTCCadenceDetectAlgoScores()
812  * @see IVTCCadenceDetectAlgoVektor()
813  */
814 static void IVTCCadenceDetectFinalize( filter_t *p_filter )
815 {
816     assert( p_filter != NULL );
817
818     filter_sys_t *p_sys = p_filter->p_sys;
819     ivtc_sys_t *p_ivtc  = &p_sys->ivtc;
820
821     /* In practice "vektor" is more reliable than "scores", but it may
822        take longer to lock on. Thus, we prefer "vektor" if its reliable bit
823        is set, then "scores", and finally just give up.
824
825        For progressive sequences, "vektor" outputs "3, -, 3, -, ...",
826        because the repeated progressive position is an inconsistent prediction.
827        In this case, "scores" fills in the blanks. (This particular task
828        could also be done without another cadence detector, by just
829        detecting the alternating pattern of "3" and no result.)
830     */
831     int pos = CADENCE_POS_INVALID;
832     if( p_ivtc->pb_v_reliable[IVTC_LATEST] )
833         pos = p_ivtc->pi_v_cadence_pos[IVTC_LATEST];
834     else if( p_ivtc->pb_s_reliable[IVTC_LATEST] )
835         pos = p_ivtc->pi_s_cadence_pos[IVTC_LATEST];
836     p_ivtc->pi_cadence_pos_history[IVTC_LATEST] = pos;
837 }
838
839 /**
840  * Internal helper function for RenderIVTC(): using stream flags,
841  * detect soft telecine.
842  *
843  * This function is different from the other detectors; it may enter or exit
844  * IVTC_MODE_TELECINED_NTSC_SOFT, if it detects that soft telecine has just
845  * been entered or exited.
846  *
847  * Upon exit from soft telecine, the filter will resume operation in its
848  * previous mode (which it had when soft telecine was entered).
849  *
850  * Last three frames must be available in the history buffer.
851  *
852  * This is an internal function only used by RenderIVTC().
853  * There is no need to call this function manually.
854  *
855  * @param p_filter The filter instance.
856  * @see RenderIVTC()
857  */
858 static void IVTCSoftTelecineDetect( filter_t *p_filter )
859 {
860     assert( p_filter != NULL );
861
862     filter_sys_t *p_sys = p_filter->p_sys;
863     ivtc_sys_t *p_ivtc  = &p_sys->ivtc;
864     picture_t *p_prev = p_sys->context.pp_history[0];
865     picture_t *p_curr = p_sys->context.pp_history[1];
866     picture_t *p_next = p_sys->context.pp_history[2];
867
868     assert( p_next != NULL );
869     assert( p_curr != NULL );
870     assert( p_prev != NULL );
871
872     /* Soft telecine can be detected from the flag pattern:
873        nb_fields = 3,2,3,2,... and *video* TFF = true, false, false, true
874        (TFF telecine) or false, true, true, false (BFF telecine).
875
876        We don't particularly care which field goes first, because in soft TC
877        we're working with progressive frames. And in any case, the video FDs
878        of successive frames must match any field repeats in order for field
879        renderers (such as traditional DVD player + CRT TV) to work correctly.
880        Thus the video TFF/BFF flag provides no additional useful information
881        for us on top of checking nb_fields.
882
883        The only thing to *do* to soft telecine in an IVTC filter is to even
884        out the outgoing PTS diffs to 2.5 fields each, so that we get
885        a steady 24fps output. Thus, we can do this processing even if it turns
886        out that we saw a lone field repeat (which are also sometimes used,
887        such as in the Silent Mobius OP and in Sol Bianca). We can be aggressive
888        and don't need to care about false positives - as long as we are equally
889        aggressive about dropping out of soft telecine mode the moment a "2" is
890        followed by another "2" and not a "3" as in soft TC.
891
892        Finally, we conclude that the one-frame future buffer is enough for us
893        to make soft TC decisions just in time for rendering the frame in the
894        "current" position. The flag patterns given below constitute proof
895        of this property.
896
897        Soft telecine is relatively rare at least in anime, but it exists;
898        e.g. Angel Links OP, Silent Mobius, and Stellvia of the Universe have
899        sequences that are soft telecined. Stellvia, especially, alternates
900        between soft and hard telecine all the time.
901     */
902
903     /* Valid stream flag patterns for soft telecine. There are three: */
904
905     /* Entering soft telecine at frame curr, or running inside it already */
906     bool b_soft_telecine_1 = (p_prev->i_nb_fields == 2) &&
907                              (p_curr->i_nb_fields == 3) &&
908                              (p_next->i_nb_fields == 2);
909     /* Running inside soft telecine */
910     bool b_soft_telecine_2 = (p_prev->i_nb_fields == 3) &&
911                              (p_curr->i_nb_fields == 2) &&
912                              (p_next->i_nb_fields == 3);
913     /* Exiting soft telecine at frame curr (curr is the last frame
914        that should be handled as soft TC) */
915     bool b_soft_telecine_3 = (p_prev->i_nb_fields == 3) &&
916                              (p_curr->i_nb_fields == 2) &&
917                              (p_next->i_nb_fields == 2);
918
919     /* Soft telecine is very clear-cut - the moment we see or do not see
920        a valid flag pattern, we can change the filter mode.
921     */
922     if( b_soft_telecine_1 || b_soft_telecine_2 || b_soft_telecine_3 )
923     {
924         if( p_ivtc->i_mode != IVTC_MODE_TELECINED_NTSC_SOFT )
925         {
926             msg_Dbg( p_filter, "IVTC: 3:2 pulldown: NTSC soft telecine "\
927                                "detected." );
928             p_ivtc->i_old_mode = p_ivtc->i_mode;
929         }
930
931         /* Valid flag pattern seen, this frame is soft telecined */
932         p_ivtc->i_mode = IVTC_MODE_TELECINED_NTSC_SOFT;
933
934         /* Only used during IVTC'ing hard telecine. */
935         p_ivtc->i_cadence_pos = CADENCE_POS_INVALID;
936         p_ivtc->i_tfd         = TFD_INVALID;
937     }
938     /* Note: no flag pattern match now */
939     else if( p_ivtc->i_mode == IVTC_MODE_TELECINED_NTSC_SOFT )
940     {
941         msg_Dbg( p_filter, "IVTC: 3:2 pulldown: NTSC soft telecine ended. "\
942                            "Returning to previous mode." );
943
944         /* No longer soft telecined, return filter to the mode it had earlier.
945            This is needed to fix cases where we came in from hard telecine, and
946            should go back, but can't catch a cadence in time before telecined
947            frames slip through. Kickstarting back to hard IVTC, using the
948            emergency frame composer until the cadence locks on again,
949            fixes the problem. This happens a lot in Stellvia.
950         */
951         p_ivtc->i_mode = p_ivtc->i_old_mode;
952         p_ivtc->i_cadence_pos = 0; /* Wild guess. The film frame reconstruction
953                                       will start in emergency mode, and this
954                                       will be filled in by the detector ASAP.*/
955         /* I suppose video field dominance no longer flipflops. */
956         p_ivtc->i_tfd = !p_next->b_top_field_first; /* tff  <=>  TFD == 0 */
957     }
958 }
959
960 /**
961  * Internal helper function for RenderIVTC(): using the history of detected
962  * cadence positions, analyze the cadence and enter or exit
963  * IVTC_MODE_TELECINED_NTSC_HARD when appropriate.
964  *
965  * This also updates b_sequence_valid.
966  *
967  * Last three frames must be available in the history buffer.
968  *
969  * This is an internal function only used by RenderIVTC().
970  * There is no need to call this function manually.
971  *
972  * @param p_filter The filter instance.
973  * @see RenderIVTC()
974  */
975 static void IVTCCadenceAnalyze( filter_t *p_filter )
976 {
977     assert( p_filter != NULL );
978
979     filter_sys_t *p_sys = p_filter->p_sys;
980     ivtc_sys_t *p_ivtc  = &p_sys->ivtc;
981     picture_t *p_prev = p_sys->context.pp_history[0];
982     picture_t *p_curr = p_sys->context.pp_history[1];
983     picture_t *p_next = p_sys->context.pp_history[2];
984
985     assert( p_next != NULL );
986     assert( p_curr != NULL );
987     assert( p_prev != NULL );
988
989     /* Determine which frames in the buffer qualify for analysis.
990
991        Note that hard telecine always has nb_fields = 2 and
992        video TFF = constant (i.e. the stream flags look no different from
993        a true interlaced or true progressive stream). Basically, no one ever
994        sets the progressive frame flag for the input frames d, e, and a -
995        in practice they're all flagged as interlaced.
996
997        A frame may qualify for hard TC analysis if it has no soft field repeat
998        (i.e. it cannot be part of a soft telecine). The condition
999        nb_fields == 2 must always match.
1000
1001        Additionally, curr and next must have had motion with respect to the
1002        previous frame, to ensure that the different field combinations have
1003        produced unique pictures.
1004
1005        Alternatively, if there was no motion, but the cadence position was
1006        reliably detected and it was the expected one, we qualify the frame
1007        for analysis (mainly, for TFD voting).
1008
1009        We only proceed with the cadence analysis if all three frames
1010        in the buffer qualify.
1011     */
1012
1013     /* Note that these are the final detected positions
1014        produced by IVTCCadenceDetectFinalize(). */
1015     int j_next = p_ivtc->pi_cadence_pos_history[IVTC_LATEST];
1016     int j_curr = p_ivtc->pi_cadence_pos_history[IVTC_LATEST-1];
1017     int j_prev = p_ivtc->pi_cadence_pos_history[IVTC_LATEST-2];
1018
1019     bool b_expected = false;
1020     if( j_next != CADENCE_POS_INVALID  &&  j_curr != CADENCE_POS_INVALID )
1021     {
1022         int pos_next = pi_detected_pos_to_cadence_pos[j_next];
1023         int pos_curr = pi_detected_pos_to_cadence_pos[j_curr];
1024         b_expected = (pos_next == (pos_curr + 1) % 5);
1025     }
1026     bool b_old_expected  = false;
1027     if( j_curr != CADENCE_POS_INVALID  &&  j_prev != CADENCE_POS_INVALID )
1028     {
1029         int pos_curr = pi_detected_pos_to_cadence_pos[j_curr];
1030         int pos_prev = pi_detected_pos_to_cadence_pos[j_prev];
1031         b_old_expected = (pos_curr == (pos_prev + 1) % 5);
1032     }
1033
1034     int i_motion     = p_ivtc->pi_motion[IVTC_LATEST];
1035     int i_old_motion = p_ivtc->pi_motion[IVTC_LATEST-1];
1036
1037     bool b_prev_valid  = (p_prev->i_nb_fields == 2);
1038     bool b_curr_valid  = (p_curr->i_nb_fields == 2)  &&
1039                          (i_old_motion > 0  ||  b_old_expected);
1040     bool b_next_valid  = (p_next->i_nb_fields == 2)  &&
1041                          (i_motion > 0      ||  b_expected);
1042     bool b_no_invalids = (b_prev_valid && b_curr_valid && b_next_valid);
1043
1044     /* Final sanity check: see that the detection history has been
1045        completely filled,  i.e. the latest three positions of the stencil
1046        have given a result from the cadence detector.
1047     */
1048     if( b_no_invalids )
1049     {
1050         for( int i = 0; i < IVTC_DETECTION_HISTORY_SIZE; ++i )
1051         {
1052             const int i_detected_pos = p_ivtc->pi_cadence_pos_history[i];
1053             if( i_detected_pos == CADENCE_POS_INVALID )
1054             {
1055                 b_no_invalids = false;
1056                 break;
1057             }
1058         }
1059     }
1060
1061     /* If still ok, do the analysis. */
1062     p_ivtc->b_sequence_valid = false; /* needed in frame reconstruction */
1063     if( b_no_invalids )
1064     {
1065         /* Convert the history elements to cadence position and TFD. */
1066         int pi_tfd[IVTC_DETECTION_HISTORY_SIZE];
1067         int pi_pos[IVTC_DETECTION_HISTORY_SIZE];
1068         for( int i = 0; i < IVTC_DETECTION_HISTORY_SIZE; ++i )
1069         {
1070             const int i_detected_pos = p_ivtc->pi_cadence_pos_history[i];
1071             pi_pos[i] = pi_detected_pos_to_cadence_pos[i_detected_pos];
1072             pi_tfd[i] = pi_detected_pos_to_tfd[i_detected_pos];
1073         }
1074
1075         /* See if the sequence is valid. The cadence positions must be
1076            successive mod 5. We can't say anything about TFF/BFF yet,
1077            because the progressive-looking position "dea" may be there.
1078            If the sequence otherwise looks valid, we handle that last
1079            by voting.
1080
1081            We also test for a progressive signal here, so that we know
1082            when to exit IVTC_MODE_TELECINED_NTSC_HARD.
1083         */
1084         p_ivtc->b_sequence_valid = true;
1085         bool b_all_progressive = (pi_pos[0] == 3);
1086         int j = pi_pos[0];
1087         for( int i = 1; i < IVTC_DETECTION_HISTORY_SIZE; ++i )
1088         {
1089             if( pi_pos[i] != (++j % 5) )
1090                 p_ivtc->b_sequence_valid = false;
1091             if( pi_pos[i] != 3 )
1092                 b_all_progressive = false;
1093         }
1094         p_ivtc->pb_all_progressives[IVTC_LATEST] = b_all_progressive;
1095
1096         if( p_ivtc->b_sequence_valid )
1097         {
1098             /* Determine TFF/BFF. */
1099             int i_vote_invalid = 0;
1100             int i_vote_tff     = 0;
1101             int i_vote_bff     = 0;
1102             for( int i = 0; i < IVTC_DETECTION_HISTORY_SIZE; ++i )
1103             {
1104                 if( pi_tfd[i] == TFD_INVALID )
1105                     i_vote_invalid++;
1106                 else if( pi_tfd[i] == TFD_TFF )
1107                     i_vote_tff++;
1108                 else if( pi_tfd[i] == TFD_BFF )
1109                     i_vote_bff++;
1110             }
1111
1112             /* With three entries, two votes for any one item are enough
1113                to decide this conclusively. */
1114             int i_telecine_field_dominance = TFD_INVALID;
1115             if( i_vote_tff >= 2)
1116                 i_telecine_field_dominance = TFD_TFF;
1117             else if( i_vote_bff >= 2)
1118                 i_telecine_field_dominance = TFD_BFF;
1119             /* In all other cases, "invalid" won or no winner.
1120                This means no NTSC telecine detected. */
1121
1122             /* Lock on to the cadence if it was valid and TFF/BFF was found.
1123
1124                Also, aggressively update the cadence counter from the
1125                lock-on data whenever we can. In practice this has been found
1126                to be a reliable strategy (if the cadence detectors are
1127                good enough).
1128             */
1129             if( i_telecine_field_dominance == TFD_TFF )
1130             {
1131                 if( p_ivtc->i_mode != IVTC_MODE_TELECINED_NTSC_HARD )
1132                     msg_Dbg( p_filter, "IVTC: 3:2 pulldown: NTSC TFF "\
1133                                        "hard telecine detected." );
1134                 p_ivtc->i_mode        = IVTC_MODE_TELECINED_NTSC_HARD;
1135                 p_ivtc->i_cadence_pos = pi_pos[IVTC_LATEST];
1136                 p_ivtc->i_tfd         = TFD_TFF;
1137             }
1138             else if( i_telecine_field_dominance == TFD_BFF )
1139             {
1140                 if( p_ivtc->i_mode != IVTC_MODE_TELECINED_NTSC_HARD )
1141                     msg_Dbg( p_filter, "IVTC: 3:2 pulldown: NTSC BFF "\
1142                                        "hard telecine detected." );
1143                 p_ivtc->i_mode        = IVTC_MODE_TELECINED_NTSC_HARD;
1144                 p_ivtc->i_cadence_pos = pi_pos[IVTC_LATEST];
1145                 p_ivtc->i_tfd         = TFD_BFF;
1146             }
1147         }
1148         /* No telecine... maybe a progressive signal? */
1149         else if( b_all_progressive )
1150         {
1151             /* It seems that in practice, three "3"s in a row can still be
1152                a fluke rather often. Four or five usually are not.
1153                This fixes the Stellvia OP. */
1154
1155             bool b_really_all_progressive = true;
1156             for( int i = 0; i < IVTC_DETECTION_HISTORY_SIZE ; i++ )
1157             {
1158                 if( p_ivtc->pb_all_progressives[i] == false )
1159                 {
1160                     b_really_all_progressive = false;
1161                     break;
1162                 }
1163             }
1164
1165             /* If we still think the signal is progressive... */
1166             if( b_really_all_progressive )
1167             {
1168                 /* ...exit film mode immediately. This does not break
1169                    soft TC handling, because for soft TC at least one
1170                    of the frames will not qualify (due to i_nb_fields == 3),
1171                    and in that case this analysis will not run.
1172                 */
1173                 if( p_ivtc->i_mode == IVTC_MODE_TELECINED_NTSC_HARD )
1174                     msg_Dbg( p_filter, "IVTC: 3:2 pulldown: progressive "\
1175                                        "signal detected." );
1176                 p_ivtc->i_mode        = IVTC_MODE_DETECTING;
1177                 p_ivtc->i_cadence_pos = CADENCE_POS_INVALID;
1178                 p_ivtc->i_tfd         = TFD_INVALID;
1179             }
1180         }
1181         /* Final missing "else": no valid NTSC telecine sequence detected.
1182
1183            Either there is no telecine, or the detector - although it produced
1184            results - had trouble finding it. In this case we do nothing,
1185            as it's not a good idea to act on unreliable data.
1186
1187            Note that if we are already in IVTC_MODE_TELECINED_NTSC_HARD, this
1188            case means that we have lost the lock-on, but are still (probably)
1189            in a hard-telecined stream. This will start the emergency mode
1190            for film frame reconstruction. See IVTCOutputOrDropFrame().
1191         */
1192     }
1193 }
1194
1195 /**
1196  * Internal helper function for RenderIVTC(): render or drop frame,
1197  * whichever needs to be done. This also sets the output frame PTS.
1198  *
1199  * Last two frames must be available in the history buffer.
1200  *
1201  * This is an internal function only used by RenderIVTC().
1202  * There is no need to call this function manually.
1203  *
1204  * @param p_filter The filter instance. Must be non-NULL.
1205  * @param[out] p_dst Frame will be rendered here. Must be non-NULL.
1206  * @return Whether a frame was constructed.
1207  * @retval true Yes, output frame is in p_dst.
1208  * @retval false No, this frame was dropped as part of normal IVTC operation.
1209  * @see RenderIVTC()
1210  */
1211 static bool IVTCOutputOrDropFrame( filter_t *p_filter, picture_t *p_dst )
1212 {
1213     assert( p_filter != NULL );
1214     assert( p_dst != NULL );
1215
1216     filter_sys_t *p_sys = p_filter->p_sys;
1217     ivtc_sys_t *p_ivtc  = &p_sys->ivtc;
1218     vlc_tick_t t_final = VLC_TICK_INVALID; /* for custom timestamp mangling */
1219
1220     picture_t *p_curr = p_sys->context.pp_history[1];
1221     picture_t *p_next = p_sys->context.pp_history[2];
1222
1223     assert( p_next != NULL );
1224     assert( p_curr != NULL );
1225
1226     /* Perform IVTC if we're in film mode (either hard or soft telecine).
1227
1228        Note that we don't necessarily have a lock-on, even if we are in
1229        IVTC_MODE_TELECINED_NTSC_HARD. We *may* be locked on, or alternatively,
1230        we have seen a valid cadence some time in the past, but lock-on has
1231        since been lost, and we have not seen a progressive signal after that.
1232        The latter case usually results from bad cuts, which interrupt
1233        the cadence.
1234
1235        Lock-on state is given by p_ivtc->b_sequence_valid.
1236     */
1237     int i_result_score = -1;
1238     int op;
1239     if( p_ivtc->i_mode == IVTC_MODE_TELECINED_NTSC_HARD )
1240     {
1241         /* Decide what to do. The operation table is only enabled
1242            if the cadence seems reliable. Otherwise we use a backup strategy.
1243         */
1244         if( p_ivtc->b_sequence_valid )
1245         {
1246             assert( p_ivtc->i_cadence_pos != CADENCE_POS_INVALID );
1247             assert( p_ivtc->i_tfd != TFD_INVALID );
1248
1249             /* Pick correct operation from the operation table. */
1250             op = pi_reconstruction_ops[p_ivtc->i_tfd][p_ivtc->i_cadence_pos];
1251
1252             if( op == IVTC_OP_DROP_FRAME )
1253             {
1254                 /* Bump cadence counter into the next expected position */
1255                 p_ivtc->i_cadence_pos = (p_ivtc->i_cadence_pos + 1) % 5;
1256
1257                 /* Drop frame. We're done. */
1258                 return false;
1259             }
1260             else
1261             {
1262                 if( op == IVTC_OP_COPY_N )
1263                     i_result_score = p_ivtc->pi_scores[FIELD_PAIR_TNBN];
1264                 else if( op == IVTC_OP_COPY_C )
1265                     i_result_score = p_ivtc->pi_scores[FIELD_PAIR_TCBC];
1266                 else if( op == IVTC_OP_COMPOSE_TNBC )
1267                     i_result_score = p_ivtc->pi_scores[FIELD_PAIR_TNBC];
1268                 else if( op == IVTC_OP_COMPOSE_TCBN )
1269                     i_result_score = p_ivtc->pi_scores[FIELD_PAIR_TCBN];
1270
1271                 /* Sanity check the result */
1272
1273                 /* Compute running mean of outgoing interlace score.
1274                    See below for history mechanism. */
1275                 int i_avg = 0;
1276                 for( int i = 0; i < IVTC_DETECTION_HISTORY_SIZE; i++)
1277                     i_avg += p_ivtc->pi_final_scores[i];
1278                 i_avg /= IVTC_DETECTION_HISTORY_SIZE;
1279
1280                 /* Check if the score suddenly became "clearly larger".
1281                    Also, filter out spurious peaks at the low end. */
1282                 if( i_result_score > 1000  &&  i_result_score > 2*i_avg )
1283                 {
1284                     /* Sequence wasn't reliable after all; we'll use
1285                        the Transcode strategy for this frame. */
1286                     p_ivtc->b_sequence_valid = false;
1287                     msg_Dbg( p_filter, "Rejected cadence-based frame "\
1288                                        "construction: interlace score %d "\
1289                                        "(running average %d)",
1290                                        i_result_score, i_avg );
1291
1292                     /* We also reset the detector used in the "vektor"
1293                        algorithm, as it depends on having a reliable previous
1294                        position. In practice, we continue using the Transcode
1295                        strategy until the cadence becomes locked on again.
1296                        (At that point, b_sequence_valid will become true again,
1297                        and we continue with this strategy.)
1298                     */
1299                     p_ivtc->pi_v_raw[IVTC_LATEST] = VEKTOR_CADENCE_POS_ALL;
1300                 }
1301             }
1302         }
1303
1304         /* Frame not dropped, and the cadence counter seems unreliable.
1305
1306             Note that this is not an "else" to the previous case. This may
1307             begin with a valid sequence, and then the above logic decides
1308             that it wasn't valid after all.
1309         */
1310         if( !p_ivtc->b_sequence_valid )
1311         {
1312             /* In this case, we must proceed with no cadence information.
1313                 We use a Transcode-like strategy.
1314
1315                 We check which field paired with TN or BN (accounting for
1316                 the field dominance) gives the smallest interlace score,
1317                 and declare that combination the resulting progressive frame.
1318
1319                 This strategy gives good results on average, but often fails
1320                 in talking scenes in anime. Those can be handled more reliably
1321                 with a locked-on cadence produced by the "vektor" algorithm.
1322             */
1323
1324             int tnbn = p_ivtc->pi_scores[FIELD_PAIR_TNBN]; /* TFF and BFF */
1325             int tnbc = p_ivtc->pi_scores[FIELD_PAIR_TNBC]; /* TFF only */
1326             int tcbn = p_ivtc->pi_scores[FIELD_PAIR_TCBN]; /* BFF only */
1327
1328             if( p_next->b_top_field_first )
1329             {
1330                 if( tnbn <= tnbc )
1331                 {
1332                     op = IVTC_OP_COPY_N;
1333                     i_result_score = tnbn;
1334                 }
1335                 else
1336                 {
1337                     op = IVTC_OP_COMPOSE_TNBC;
1338                     i_result_score = tnbc;
1339                 }
1340             }
1341             else
1342             {
1343                 if( tnbn <= tcbn )
1344                 {
1345                     op = IVTC_OP_COPY_N;
1346                     i_result_score = tnbn;
1347                 }
1348                 else
1349                 {
1350                     op = IVTC_OP_COMPOSE_TCBN;
1351                     i_result_score = tcbn;
1352                 }
1353             }
1354         }
1355
1356         /* Mangle timestamps when locked on.
1357
1358            "Current" is the frame that is being extracted now. Use its original
1359            timestamp as the base.
1360
1361            Note that this way there will be no extra delay compared to the
1362            raw stream, even though we look one frame into the future.
1363         */
1364         if( p_ivtc->b_sequence_valid )
1365         {
1366             /* Convert 29.97 -> 23.976 fps. We get to this point only if we
1367                didn't drop the frame, so we always get a valid delta.
1368             */
1369             int i_timestamp_delta = pi_timestamp_deltas[p_ivtc->i_cadence_pos];
1370             assert( i_timestamp_delta >= 0 );
1371
1372             /* FIXME: use field length as measured by Deinterlace()? */
1373             t_final = p_curr->date
1374                     + (p_next->date - p_curr->date)*i_timestamp_delta/4;
1375         }
1376         else /* Do not mangle timestamps (or drop frames, either) if cadence
1377                 is not locked on. This causes one of five output frames - if
1378                 all are reconstructed correctly - to be a duplicate, but in
1379                 practice at least with anime (which is the kind of material
1380                 that tends to have this problem) this is less noticeable than
1381                 a sudden jump in the cadence. Especially, a consistently wrong
1382                 lock-on will cause a very visible stutter, which we wish
1383                 to avoid. */
1384         {
1385             t_final = p_curr->date;
1386         }
1387
1388         /* Bump cadence counter into the next expected position. */
1389         p_ivtc->i_cadence_pos = (p_ivtc->i_cadence_pos + 1) % 5;
1390     }
1391     else if( p_ivtc->i_mode == IVTC_MODE_TELECINED_NTSC_SOFT )
1392     {
1393         /* Soft telecine. We have the progressive frames already;
1394            even out PTS diffs only. */
1395
1396         /* Pass through the "current" frame. We must choose the frame "current"
1397            in order to be able to detect soft telecine before we have to output
1398            the frame. See IVTCSoftTelecineDetect(). Also, this allows
1399            us to peek at the next timestamp to calculate the duration of
1400            "current".
1401         */
1402         op = IVTC_OP_COPY_C;
1403         i_result_score = p_ivtc->pi_scores[FIELD_PAIR_TCBC];
1404
1405         /* Timestamp mangling for soft telecine: bump "threes" forward by
1406            0.5 field durations. This is more forgiving for the renderer
1407            than bumping the "twos" back (which would require to render
1408            them sooner),
1409         */
1410         if( p_curr->i_nb_fields == 3 )
1411         {
1412             /* Approximate field duration from the PTS difference. */
1413             /* FIXME: use field length as measured by Deinterlace()? */
1414             vlc_tick_t i_half_field_dur = ( (p_next->date - p_curr->date)/3 ) / 2;
1415             t_final = p_curr->date + i_half_field_dur;
1416         }
1417         else /* Otherwise, use original PTS of the outgoing frame. */
1418         {
1419             t_final = p_curr->date;
1420         }
1421     }
1422     else /* Not film mode, timestamp mangling bypassed. */
1423     {
1424         op = IVTC_OP_COPY_N;
1425         i_result_score = p_ivtc->pi_scores[FIELD_PAIR_TNBN];
1426
1427         /* Preserve original PTS (note that now, in principle,
1428                                   "next" is the outgoing frame) */
1429         t_final = p_next->date;
1430     }
1431
1432     /* There is only one case where we should drop the frame,
1433        and it was already handled above. */
1434     assert( op != IVTC_OP_DROP_FRAME );
1435
1436     /* Render into p_dst according to the final operation chosen. */
1437     if( op == IVTC_OP_COPY_N )
1438         picture_Copy( p_dst, p_next );
1439     else if( op == IVTC_OP_COPY_C )
1440         picture_Copy( p_dst, p_curr );
1441     else if( op == IVTC_OP_COMPOSE_TNBC )
1442         ComposeFrame( p_filter, p_dst, p_next, p_curr, CC_ALTLINE, false );
1443     else if( op == IVTC_OP_COMPOSE_TCBN )
1444         ComposeFrame( p_filter, p_dst, p_curr, p_next, CC_ALTLINE, false );
1445
1446     /* Slide history of outgoing interlace scores. This must be done last,
1447        and only if the frame was not dropped, so we do it here.
1448
1449        This is used during the reconstruction to get an idea of what is
1450        (in the temporally local sense) an acceptable interlace score
1451        for a correctly reconstructed frame. See above.
1452     */
1453     for( int i = 1; i < IVTC_DETECTION_HISTORY_SIZE; i++ )
1454         p_ivtc->pi_final_scores[i-1] = p_ivtc->pi_final_scores[i];
1455     p_ivtc->pi_final_scores[IVTC_LATEST] = i_result_score;
1456
1457     /* Note that picture_Copy() copies the PTS, too. Apply timestamp mangling
1458        now, if any was needed.
1459     */
1460     if( t_final != VLC_TICK_INVALID )
1461         p_dst->date = t_final;
1462
1463     return true;
1464 }
1465
1466 /*****************************************************************************
1467  * Public functions
1468  *****************************************************************************/
1469
1470 /* See function doc in header. */
1471 int RenderIVTC( filter_t *p_filter, picture_t *p_dst, picture_t *p_pic )
1472 {
1473     VLC_UNUSED(p_pic);
1474     assert( p_filter != NULL );
1475     assert( p_dst != NULL );
1476
1477     filter_sys_t *p_sys = p_filter->p_sys;
1478     ivtc_sys_t *p_ivtc  = &p_sys->ivtc;
1479
1480     picture_t *p_prev = p_sys->context.pp_history[0];
1481     picture_t *p_curr = p_sys->context.pp_history[1];
1482     picture_t *p_next = p_sys->context.pp_history[2];
1483
1484     /* If the history mechanism has failed, we have nothing to do. */
1485     if( !p_next )
1486         return VLC_EGENERIC;
1487
1488     /* Slide algorithm-specific histories */
1489     IVTCFrameInit( p_filter );
1490
1491     /* Filter if we have all the pictures we need.
1492        Note that we always have p_next at this point. */
1493     if( p_prev && p_curr )
1494     {
1495         /* Update raw data for motion, field repeats, interlace scores... */
1496         IVTCLowLevelDetect( p_filter );
1497
1498         /* Detect soft telecine.
1499
1500            Enter/exit IVTC_MODE_TELECINED_NTSC_SOFT when needed.
1501         */
1502         IVTCSoftTelecineDetect( p_filter );
1503
1504         /* Detect hard telecine.
1505
1506            Enter/exit IVTC_MODE_TELECINED_NTSC_HARD when needed.
1507
1508            If we happen to be running in IVTC_MODE_TELECINED_NTSC_SOFT,
1509            we nevertheless let the algorithms see for themselves that
1510            the stream is progressive. This doesn't break anything,
1511            and this way the full filter state gets updated at each frame.
1512
1513            See the individual function docs for details.
1514         */
1515         IVTCCadenceDetectAlgoScores( p_filter );
1516         IVTCCadenceDetectAlgoVektor( p_filter );
1517         IVTCCadenceDetectFinalize( p_filter ); /* pick winner */
1518         IVTCCadenceAnalyze( p_filter ); /* update filter state */
1519
1520         /* Now we can... */
1521         bool b_have_output_frame = IVTCOutputOrDropFrame( p_filter, p_dst );
1522
1523         if( b_have_output_frame )
1524             return VLC_SUCCESS;
1525         else
1526             return VLC_EGENERIC; /* Signal the caller not to expect a frame */
1527     }
1528     else if( !p_prev && !p_curr ) /* first frame */
1529     {
1530         /* Render the first frame as-is, so that a picture appears immediately.
1531
1532            We will also do some init for the filter. This score will become
1533            TPBP by the time the actual filter starts. Note that the sliding of
1534            final scores only starts when the filter has started (third frame).
1535         */
1536         int i_score = CalculateInterlaceScore( p_next, p_next );
1537         p_ivtc->pi_scores[FIELD_PAIR_TNBN] = i_score;
1538         p_ivtc->pi_final_scores[0]         = i_score;
1539
1540         picture_Copy( p_dst, p_next );
1541         return VLC_SUCCESS;
1542     }
1543     else /* second frame */
1544     {
1545         /* If the history sliding mechanism works correctly,
1546            the only remaining possibility is that: */
1547         assert( p_curr && !p_prev );
1548
1549         /* We need three frames for the cadence detector to work, so we just
1550            do some init for the detector and pass the frame through.
1551            Passthrough for second frame, too, works better than drop
1552            for some still-image DVD menus.
1553
1554            Now that we have two frames, we can run a full IVTCLowLevelDetect().
1555
1556            The interlace scores from here will become TCBC, TCBP and TPBC
1557            when the filter starts. The score for the current TCBC has already
1558            been computed at the first frame, and slid into place at the start
1559            of this frame (by IVTCFrameInit()).
1560         */
1561         IVTCLowLevelDetect( p_filter );
1562
1563         /* Note that the sliding mechanism for output scores only starts
1564            when the actual filter does.
1565         */
1566         p_ivtc->pi_final_scores[1] = p_ivtc->pi_scores[FIELD_PAIR_TNBN];
1567
1568         picture_Copy( p_dst, p_next );
1569         return VLC_SUCCESS;
1570     }
1571 }
1572
1573 /* See function doc in header. */
1574 void IVTCClearState( filter_t *p_filter )
1575 {
1576     assert( p_filter != NULL );
1577
1578     filter_sys_t *p_sys = p_filter->p_sys;
1579     ivtc_sys_t *p_ivtc = &p_sys->ivtc;
1580
1581     p_ivtc->i_cadence_pos = CADENCE_POS_INVALID;
1582     p_ivtc->i_tfd         = TFD_INVALID;
1583     p_ivtc->b_sequence_valid = false;
1584     p_ivtc->i_mode     = IVTC_MODE_DETECTING;
1585     p_ivtc->i_old_mode = IVTC_MODE_DETECTING;
1586     for( int i = 0; i < IVTC_NUM_FIELD_PAIRS; i++ )
1587         p_ivtc->pi_scores[i] = 0;
1588     for( int i = 0; i < IVTC_DETECTION_HISTORY_SIZE; i++ )
1589     {
1590         p_ivtc->pi_cadence_pos_history[i] = CADENCE_POS_INVALID;
1591
1592         p_ivtc->pi_s_cadence_pos[i] = CADENCE_POS_INVALID;
1593         p_ivtc->pb_s_reliable[i]    = false;
1594         p_ivtc->pi_v_cadence_pos[i] = CADENCE_POS_INVALID;
1595         p_ivtc->pb_v_reliable[i]    = false;
1596
1597         p_ivtc->pi_v_raw[i]         = VEKTOR_CADENCE_POS_ALL;
1598
1599         p_ivtc->pi_top_rep[i] =  0;
1600         p_ivtc->pi_bot_rep[i] =  0;
1601         p_ivtc->pi_motion[i]  = -1;
1602
1603         p_ivtc->pb_all_progressives[i] = false;
1604
1605         p_ivtc->pi_final_scores[i] = 0;
1606     }
1607 }