[FFmpeg-user] Getting 'fieldmatch' coverage to 100%
Mark Filipak
markfilipak.imdb at gmail.com
Sat Jun 7 20:18:21 EEST 2025
This is not a topic for casual users. It is intended for developers.
I've made the proposal an attachment because email line limits would wrap, and thereby destroy the text.
I would have submitted this to the ffmpeg-devel list but my attempts to join that list have failed.
--Mark.
-------------- next part --------------
Mark Filipak, 7 June 2025
This is a proposal to expand the coverage of 'fieldmatch' -- currently unknown -- to 100% via the State Machine Method.
It covers all pristine 2:3:2:3 and 2:3:3:2 telecines, including head- and tail-cuts, plus all possible cuts and splices including so-called 'bad' cuts and splices.
What would be covered?
- bff-2:3:2:3 telecines, with and without head- and tail-cuts
- tff-2:3:2:3 telecines, with and without head- and tail-cuts
- bff-2:3:2:3 telecines, spliced with bff-2:3:2:3 telecines, with and without head- and-or tail-cuts at the splice
- tff-2:3:2:3 telecines, spliced with tff-2:3:2:3 telecines, with and without head- and-or tail-cuts at the splice
- all of the above, but for 2:3:3:2 telecines.
What would not be covered?
- 2:3:2:3 telecines spliced with 2:3:3:2 telecines
- bff streams spliced with tff streams
- streams containing fewer than 5 frames.
Key:
[a+A] is Mark's Notation for a bff 'interlaced' frame containing bottom field 'a' and top field 'A'.
[A+a] is Mark's Notation for a tff 'interlaced' frame containing top field 'A' and bottom field 'a'.
[b+C] and [c+D], for example, are Mark's Notation for telecined frames that are bff.
[B+c] and [C+d], for example, are Mark's Notation for telecined frames that are tff.
[Aa] is Mark's Notation for a progressive frame, provided here for completeness but not applicable to this topic.
[aA] is Mark's Notation for a progressive frame in which odd-even lines are swapped -- an error -- provided here for completeness but not applicable to this topic.
What follows are 5 case analyzes utilizing Mark's Notation, covering bff-2:3:2:3 telecine plus 4 head-cuts.
match case 'ccppc'
[a+A][b+B][b+C][c+D][d+D][e+E][f+F][f+G][g+H][h+H]...
_____M_A_T_C_H_I_N_G_____ __R_E_A_R_R_A_N_G_I_N_G__
[a A] -> [a+A]
[b B] -> [b+B]
B [b ] -> [b+B]
: : C [c ] -> [c+C]
: : : : [d D] -> [d+D]
c c :..p :..p c [a+A][b+B][b+B][c+C][d+D]
decimation [a+A][b+B] [c+C][d+D]
match case 'cppcc'
- [b+B][b+C][c+D][d+D][e+E][f+F][f+G][g+H][h+H]...
_____M_A_T_C_H_I_N_G_____ __R_E_A_R_R_A_N_G_I_N_G__
[b B] -> [b+B]
B [b ] -> [b+B]
: : C [c ] -> [c+C]
: : : : [d D] -> [d+D]
: : : : [e E] -> [e+E]
c :..p :..p c c [b+B][b+B][c+C][d+D][e+E]
decimation [b+B] [c+C][d+D][e+E]
match case 'xpccc'
- - [b+C][c+D][d+D][e+E][f+F][f+G][g+H][h+H]...
_____M_A_T_C_H_I_N_G_____ __R_E_A_R_R_A_N_G_I_N_G__
[b ] -> <== no match
C [c ] -> [c+C]
: : [d D] -> [d+D]
: : [e E] -> [e+E]
: : [f F] -> [f+F]
x :..p c c c [c+C][d+D][e+E][f+F]
decimation [d+D][d+D][e+E][f+F]
match case 'xcccp'
- - - [c+D][d+D][e+E][f+F][f+G][g+H][h+H]...
_______M_A_T_C_H_I_N_G________ __R_E_A_R_R_A_N_G_I_N_G__
[c ] -> [c+c] <== no match (suggestion)
[d D] -> [d+D]
[e E] -> [e+E]
[f F] -> [f+F]
F [f ] -> [f+F]
x c c c :..p [c+c][d+D][e+E][f+F][f+F]
decimation [c+c][d+D][e+E][f+F]
match case 'cccpp'
- - - - [d+D][e+E][f+F][f+G][g+H][h+H]...
_______M_A_T_C_H_I_N_G________ __R_E_A_R_R_A_N_G_I_N_G__
[d D] -> [d+D]
[e E] -> [e+E]
[f F] -> [f+F]
F [f ] -> [f+F]
: : G [g ] -> [g+G]
c c c :..p :..p [d+D][e+E][f+F][f+F][g+G]
decimation [d+D][e+E][f+F] [g+G]
The above doesn't cover
- tff, or
- 2:3:3:2 telecine, or
- tail-cuts, or
- splicing.
But what follows does cover those conditions.
There are 116 cases. Here are all 116 cases.
The next case covers bff-2:3:2:3 telecine, no cuts (diagrammed above).
[a+A][b+B][c+B][d+C][d+D]...
The next 4 cases cover bff-2:3:2:3 telecine, head-cuts (diagrammed above).
- [b+B][c+B][d+C][d+D][e+E]...
- - [c+B][d+C][d+D][e+E][f+F]...
- - - [d+C][d+D][e+E][f+F][g+F]...
- - - - [d+D][e+E][f+F][g+F][h+G]...
The next 4 cases cover bff-2:3:2:3 telecine, tail-cuts.
...[a+A][b+B][c+B][d+C] -
...[a+A][b+B][c+B] - -
...[a+A][b+B] - - -
...[a+A] - - - -
The next 20 cases cover bff-2:3:2:3 telecine, cuts and splices.
[a+A][b+B][c+B][d+C] - [e+E]...
[a+A][b+B][c+B][d+C] - - [f+F]...
[a+A][b+B][c+B][d+C] - - - [g+F]...
[a+A][b+B][c+B][d+C] - - - - [h+G]...
[a+A][b+B][c+B][d+C] - - - - - [h+H]...
[a+A][b+B][c+B] - - [e+E][f+F]...
[a+A][b+B][c+B] - - - [f+F][g+F]...
[a+A][b+B][c+B] - - - - [g+F][h+G]...
[a+A][b+B][c+B] - - - - - [h+G][h+H]...
[a+A][b+B][c+B] - - - - - - [h+H][i+I]...
[a+A][b+B] - - - [e+E][f+F][g+F]...
[a+A][b+B] - - - - [f+F][g+F][h+G]...
[a+A][b+B] - - - - - [g+F][h+G][h+H]...
[a+A][b+B] - - - - - - [h+G][h+H][i+I]...
[a+A][b+B] - - - - - - - [h+H][i+I][j+J]...
[a+A] - - - - [e+E][f+F][g+F][h+G]...
[a+A] - - - - - [f+F][g+F][h+G][h+H]...
[a+A] - - - - - - [g+F][h+G][h+H][i+I]...
[a+A] - - - - - - - [h+G][h+H][i+I][j+J]...
[a+A] - - - - - - - - [h+H][i+I][j+J][j+K]...
The next case covers tff-2:3:2:3 telecine, no cuts.
[A+a][B+b][B+c][C+d][D+d]...
The next 4 cases cover tff-2:3:2:3 telecine, head-cuts.
- [b+B][B+c][C+d][d+D][e+E]...
- - [B+c][C+d][d+D][e+E][f+F]...
- - - [C+d][d+D][e+E][f+F][g+F]...
- - - - [d+D][e+E][f+F][g+F][h+G]...
The next 4 cases cover tff-2:3:2:3 telecine, tail-cuts.
...[A+a][B+b][B+c][C+d] -
...[A+a][B+b][B+c] - -
...[A+a][B+b] - - -
...[A+a] - - - -
The next 20 cases cover tff-2:3:2:3 telecine, cuts and splices.
[A+a][B+b][B+c][C+d] - [E+e]...
[A+a][B+b][B+c][C+d] - - [F+f]...
[A+a][B+b][B+c][C+d] - - - [F+g]...
[A+a][B+b][B+c][C+d] - - - - [G+h]...
[A+a][B+b][B+c][C+d] - - - - - [H+h]...
[A+a][B+b][B+c] - - [E+e][F+f]...
[A+a][B+b][B+c] - - - [F+f][F+g]...
[A+a][B+b][B+c] - - - - [F+g][G+h]...
[A+a][B+b][B+c] - - - - - [G+h][H+h]...
[A+a][B+b][B+c] - - - - - - [H+h][I+i]...
[A+a][B+b] - - - [E+e][F+f][F+g]...
[A+a][B+b] - - - - [F+f][F+g][G+h]...
[A+a][B+b] - - - - - [F+g][G+h][H+h]...
[A+a][B+b] - - - - - - [G+h][H+h][I+i]...
[A+a][B+b] - - - - - - - [H+h][I+i][J+j]...
[A+a] - - - - [E+e][F+f][F+g][G+h]...
[A+a] - - - - - [F+f][F+g][G+h][H+h]...
[A+a] - - - - - - [F+g][G+h][H+h][I+i]...
[A+a] - - - - - - - [G+h][H+h][I+i][J+j]...
[A+a] - - - - - - - - [H+h][I+i][J+j][J+k]...
The next case covers bff-2:3:3:2 telecine, no cuts.
[a+A][b+B][b+C][c+C][d+D]...
The next 4 cases cover bff-2:3:3:2 telecine, head-cuts.
- [b+B][b+C][c+C][d+D][e+E]...
- - [b+C][c+C][d+D][e+E][f+F]...
- - - [c+C][d+D][e+E][f+F][f+G]...
- - - - [d+D][e+E][f+F][f+G][g+G]...
The next 4 cases cover bff-2:3:3:2 telecine, tail-cuts.
...[a+A][b+B][b+C][c+C] -
...[a+A][b+B][b+C] - -
...[a+A][b+B] - - -
...[a+A] - - - -
The next 20 cases cover bff-2:3:3:2 telecine, cuts and splices.
[a+A][b+B][b+C][c+C] - [e+E]...
[a+A][b+B][b+C][c+C] - - [f+F]...
[a+A][b+B][b+C][c+C] - - - [f+G]...
[a+A][b+B][b+C][c+C] - - - - [g+G]...
[a+A][b+B][b+C][c+C] - - - - - [h+H]...
[a+A][b+B][b+C] - - [e+E][f+F]...
[a+A][b+B][b+C] - - - [f+F][f+G]...
[a+A][b+B][b+C] - - - - [f+G][g+G]...
[a+A][b+B][b+C] - - - - - [g+G][h+H]...
[a+A][b+B][b+C] - - - - - - [h+H][i+I]...
[a+A][b+B] - - - [e+E][f+F][f+G]...
[a+A][b+B] - - - - [f+F][f+G][g+G]...
[a+A][b+B] - - - - - [f+G][g+G][h+H]...
[a+A][b+B] - - - - - - [g+G][h+H][i+I]...
[a+A][b+B] - - - - - - - [h+H][i+I][j+J]...
[a+A] - - - - [e+E][f+F][f+G][g+G]...
[a+A] - - - - - [f+F][f+G][g+G][h+H]...
[a+A] - - - - - - [f+G][g+G][h+H][i+I]...
[a+A] - - - - - - - [g+G][h+H][i+I][j+J]...
[a+A] - - - - - - - - [h+H][i+I][j+J][j+K]...
The next case covers tff-2:3:3:2 telecine, no cuts.
[A+a][B+b][B+c][C+c][D+d]...
The next 4 cases cover tff-2:3:3:2 telecine, head-cuts.
- [B+b][B+c][C+c][D+d][E+e]...
- - [B+c][C+c][D+d][E+e][F+f]...
- - - [C+c][D+d][E+e][F+f][F+g]...
- - - - [D+d][E+e][F+f][F+g][G+g]...
The next 4 cases cover tff-2:3:3:2 telecine, tail-cuts.
...[A+a][B+b][B+c][C+c] -
...[A+a][B+b][B+c] - -
...[A+a][B+b] - - -
...[A+a] - - - -
The next 20 cases cover tff-2:3:3:2 telecine, cuts and splices.
[A+a][B+b][B+c][C+c] - [E+e]...
[A+a][B+b][B+c][C+c] - - [F+f]...
[A+a][B+b][B+c][C+c] - - - [F+g]...
[A+a][B+b][B+c][C+c] - - - - [G+g]...
[A+a][B+b][B+c][C+c] - - - - - [H+h]...
[A+a][B+b][B+c] - - [E+e][F+f]...
[A+a][B+b][B+c] - - - [F+f][F+g]...
[A+a][B+b][B+c] - - - - [F+g][G+g]...
[A+a][B+b][B+c] - - - - - [G+g][H+h]...
[A+a][B+b][B+c] - - - - - - [H+h][I+i]...
[A+a][B+b] - - - [E+e][F+f][F+g]...
[A+a][B+b] - - - - [F+f][F+g][G+g]...
[A+a][B+b] - - - - - [F+g][G+g][H+h]...
[A+a][B+b] - - - - - - [G+g][H+h][I+i]...
[A+a][B+b] - - - - - - - [H+h][I+i][J+j]...
[A+a] - - - - [E+e][F+f][F+g][G+g]...
[A+a] - - - - - [F+f][F+g][G+g][H+h]...
[A+a] - - - - - - [F+g][G+g][H+h][I+i]...
[A+a] - - - - - - - [G+g][H+h][I+i][J+j]...
[A+a] - - - - - - - - [H+h][I+i][J+j][J+k]...
Any code covering all 116 cases is guaranteed to have 100% coverage.
What would the code look like?
It would be the current 'pcn' comb detection and matching (for example, 'ccppc') but with 'x' (no match) added, followed by 'switch (state)', followed by 116 case statements, 'case (<ff><telecine><match>)'. Each case statement would simply output a fixed rearrangement of 5 frames (for example, output fields 0 1 2 3 4 3 6 5 8 9). The case statements would have no combinatorial logic whatsoever.
It's probable that several combinations produce the same match cases (for example, 'ccppc'). It's also probable that several match cases result in the same rearrangements (for example, output fields 0 1 2 3 4 3 6 5 8 9). Such cases will become known when all diagrams have been made.
But one thing is certain: With 100% coverage, when the code is done, the code is done, and forever bug-free -- there'll be no future patches to cover cases that hadn't been foreseen.
I've diagrammed the first 5 cases in this message. I could diagram the remaining 111 cases, but I want to see positive reactions to the idea of rewriting 'fieldmatch' before I spend any more time.
Note: I have reviewed the current 'fieldmatch.c' text.
More information about the ffmpeg-user
mailing list