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

[Michael Niedermayer]

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.
+ * 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.
+ *
+ * @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 */
-- 
2.22.0