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

[Nicolas George]

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.

> + * 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.

> + *
> + * @return 1 if a loop is detected, 0 otherwise, no errors are possible.
> + *         The code will always return 1 once it returned 1 until its reset.
> + */
> +static inline int av_is_loop(AVSimpleLoopDetector *c, uint64_t state, uint64_t max_iterations)
> +{
> +    if (c->count && c->state == state)
> +        c->count = max_iterations;
> +    if (c->count >= max_iterations)
> +        return 1;
> +    c->count ++;
> +    if (!(c->count & (c->count - 1)))
> +        c->state = state;
> +    return 0;
> +}
> +
> +#endif /* AVUTIL_LOOP_DETECTOR_H */

Regards,

-- 
  Nicolas George
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: not available
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20190808/6cc7aa5e/attachment.sig>