[FFmpeg-devel] [PATCH 1/2] avutil: Add Simple loop detector

[Michael Niedermayer]

On Thu, Aug 08, 2019 at 11:59:12AM +0200, Nicolas George wrote:
> Michael Niedermayer (12019-08-08):
> > This provides an alternative to retry counters.
> > Useful if there is no reasonable maximum number of iterations and
> > no ordering that naturally avoids loops.
> > 
> > Signed-off-by: Michael Niedermayer <michael at niedermayer.cc>
> > ---
> >  doc/APIchanges            |  3 ++
> >  libavutil/Makefile        |  1 +
> >  libavutil/loop_detector.h | 71 +++++++++++++++++++++++++++++++++++++++
> >  3 files changed, 75 insertions(+)
> >  create mode 100644 libavutil/loop_detector.h
> > 
> > diff --git a/doc/APIchanges b/doc/APIchanges
> > index 6603a8229e..eee4c30ec5 100644
> > --- a/doc/APIchanges
> > +++ b/doc/APIchanges
> > @@ -15,6 +15,9 @@ libavutil:     2017-10-21
> >  
> >  API changes, most recent first:
> >  
> > +2019-XX-XX - XXXXXXXXXX - lavu 56.XX.XXX - loop_detector.h
> > +  Add loop_detector.h, av_is_loop(), AVSimpleLoopDetector
> > +
> >  2019-07-27 - xxxxxxxxxx - lavu 56.33.100 - tx.h
> >    Add AV_TX_DOUBLE_FFT and AV_TX_DOUBLE_MDCT
> >  
> > diff --git a/libavutil/Makefile b/libavutil/Makefile
> > index 57e6e3d7e8..0b77fa6347 100644
> > --- a/libavutil/Makefile
> > +++ b/libavutil/Makefile
> > @@ -48,6 +48,7 @@ HEADERS = adler32.h                                                     \
> >            intreadwrite.h                                                \
> >            lfg.h                                                         \
> >            log.h                                                         \
> > +          loop_detector.h                                               \
> >            macros.h                                                      \
> >            mathematics.h                                                 \
> >            mastering_display_metadata.h                                  \
> > diff --git a/libavutil/loop_detector.h b/libavutil/loop_detector.h
> > new file mode 100644
> > index 0000000000..6f8643495a
> > --- /dev/null
> > +++ b/libavutil/loop_detector.h
> > @@ -0,0 +1,71 @@
> > +/*
> > + * Copyright (C) 2019 Michael Niedermayer (michael at niedermayer.cc)
> > + *
> > + * This file is part of FFmpeg
> > + *
> > + * FFmpeg is free software; you can redistribute it and/or
> > + * modify it under the terms of the GNU Lesser General Public
> > + * License as published by the Free Software Foundation; either
> > + * version 2.1 of the License, or (at your option) any later version.
> > + *
> > + * FFmpeg is distributed in the hope that it will be useful,
> > + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> > + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> > + * Lesser General Public License for more details.
> > + *
> > + * You should have received a copy of the GNU Lesser General Public
> > + * License along with FFmpeg; if not, write to the Free Software
> > + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> > + */
> > +
> > +
> > +/**
> > + * @file
> > + * Utilties for detecting infinite loops
> > + * @author Michael Niedermayer <michael at niedermayer.cc>
> > + */
> > +
> > +#ifndef AVUTIL_LOOP_DETECTOR_H
> > +#define AVUTIL_LOOP_DETECTOR_H
> > +
> > +typedef struct AVSimpleLoopDetector {
> > +    uint64_t count;
> > +    uint64_t state;
> > +} AVSimpleLoopDetector;
> > +
> > +/**
> > + * Checks if the list of states provided by the user fell into a cycle.
> > + *
> 
> > + * To initialize or reset the detector, the context is simply memset to 0.
> 
> I suggest:
> 
> #define AV_SIMPLE_LOOP_DETECTOR_INIT {0}
> 
> so we can extend it if needs be.

will change it


> 
> > + * This detector requires only 16bytes of context and minimal computations
> > + * per iteration. In exchange for this simplicity it takes a few iterations
> > + * into a loop before it is detected.
> > + * No deallocation or memory allocation is needed.
> > + *
> > + * @param c     The context, initialy and to reset, it is simply memset to 0.
> > + *              It is only 16bytes so as to be lightweight and not poison any
> > + *              data cache.
> > + *
> 
> > + * @param state The loop state, when this falls into a cycle the detector
> > + *              will after a few iterations return 1.
> > + *
> > + * @param max_iterations
> > + *              after this many iterations the detector will return 1 regardless
> > + *              of it falling into a cycle.
> 
> Even with the code, I do not manage to understand exactly what it means,
> in particular what the state is. The example uses a single state, so any
> cycle is trivial.

the idea is that until the state repeats the return will be 0
when there is a repeat the return may or may not switch to 1
when a final cycle is entered the return will reasonable quickly switch to 1
would this clarify it ? or should i explain this somehow differently 
or maybe the name for the variable isnt optimal ?
in practive it most often will likely be a single variable like a byte offset
in a file but i imagine it could be something more complex like a depth+offset
or tagname+offset or something

thx

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Everything should be made as simple as possible, but not simpler.
-- Albert Einstein
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 181 bytes
Desc: not available
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20190810/95db9253/attachment.sig>