[FFmpeg-user] Rewriting 'fieldmatch' using the State Machine Method

[Mark Filipak]

I've removed the attachment. Go to my original message to get the attachment if you are interested.

Apparently, the people that I meant to reach have not been reached. So, in order to gain 
credibility, I'm going to show you what I did for 25 years.

           .---------------------------.
           ¦            ___            ¦
           ¦           |   |           ¦    ___
           ¦    ___    | R |           ¦   |   |
           ¦   |   |   | E |           ¦   | L |
           ¦   | L |   | G |           '-->| O |
inputs ---'-->| O |   | I |               | G |--> outputs
               | G |-->| S |-- state --.-->| I |
           .-->| I |   | T |           ¦   | C |
           ¦   | C |   | E |           ¦   |___|
           ¦   |___|   | R |           ¦
clock ----¦-----------> S |           ¦
           ¦           |___|           ¦
           '---------------------------'

The diagram above is a Mealy-Moore state machine. You can think of it as a digital sequencer. It 
runs on inputs and current state, not code. Such machines are at the heart of every CPU code cracker 
and cache controller and more, multiprocessor shared cache protocols, memory management chips, 
ethernet chips, GPUs, and much more.

There's no such thing as a hardware field update. Hardware must have 100% coverage and must be 
bug-free. If a state machine has a bug, it's time to refund all the customers' monies. If a state 
machine has a bug, it's time for its designer to find another way to make a living.

                        ___
                       |   |
                ___    | R |                ___
               |   |   | E |               |   |
               | L |   | G |               | L |
inputs ------>| O |   | I |               | O |
               | G |-->| S |-- state --.-->| G |--> outputs
           .-->| I |   | T |           ¦   | I |
           ¦   | C |   | E |           ¦   | C |
           ¦   |___|   | R |           ¦   |___|
clock ----¦-----------> S |           ¦
           ¦           |___|           ¦
           '---------------------------'

The diagram above is a Moore state machine.

The 'C' equivalent of a Moore machine is switch(state) and case. The output logic is the code in the 
case statements. For reliability, combinatorial logic is not allowed in output logic -- believe it 
or not, that's actually not a hindrance. The machine state coverage is 100%.

I learned Mealy-Moore machine design from Dr. Frank Battocletti of Ohio State University the same 
year that Dr. Mealy made his addition to Dr. Moore's work. Electromagnetic Sciences Laboratory moved 
me out to California upon graduation. I taught Mealy-Moore state machine design to other hardware 
engineers in Silicon Valley, and I taught Moore state machine design in the form of switch-case to 
'C' programmers who worked for me. They wrote bug-free code that had 100% coverage and 100% 
testability. And you know what? Those codesmiths said that, once they got the hang of it, it took 
them less coding time than the trial-and-error coding. And you know what? They experienced less 
stress. And you know what? Their code ran faster.

Now, you can discount what I write, but you can't discount that you code by trial and error. It's up 
to you.


=== original message ===

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.