[FFmpeg-user] Rewriting 'fieldmatch' using the State Machine Method
Mark Filipak
markfilipak.imdb at gmail.com
Tue Jun 10 14:09:01 EEST 2025
I've done a code review of 'fieldmatch.c'. You may be interested in reading the attachment.
The State Machine Method defies logic in the sense that you do not need to 'think out' whether you
have 100% code coverage. 100% code coverage is guaranteed.
And, you don't have to carry around a 'picture in your mind' about how the various pieces of your
code fit together. Everything is explicitly shown in your code in a straightforward manner.
The State Machine Method is a chip design method adapted to 'C' code. I have shown it to 'C'
codesmiths in the past. They had to use it because they worked for me and I insisted they use it.
They thanked me in the end. They said that it changed the way they think about code. They said that
it simplified.
I've chosen fieldmatch because there have been reports in the past of fieldmatch failing. Failure
should be impossible. Fieldmatch is a good example.
--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