diff mbox series

[FFmpeg-devel,1/2] avformat: Change avpriv_new_chapter() from O(n) to (1) in the common case

Message ID 20210107004328.27244-1-michael@niedermayer.cc
State New
Headers show
Series [FFmpeg-devel,1/2] avformat: Change avpriv_new_chapter() from O(n) to (1) in the common case
Related show

Checks

Context Check Description
andriy/x86_make success Make finished
andriy/x86_make_fate success Make fate finished
andriy/PPC64_make success Make finished
andriy/PPC64_make_fate success Make fate finished

Commit Message

Michael Niedermayer Jan. 7, 2021, 12:43 a.m. UTC
Fixes: timeout (slow -> 300ms)
Fixes: 28876/clusterfuzz-testcase-minimized-ffmpeg_dem_MOV_fuzzer-5664824587583488

Found-by: continuous fuzzing process https://github.com/google/oss-fuzz/tree/master/projects/ffmpeg
Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
---
 libavformat/internal.h |  5 +++++
 libavformat/utils.c    | 11 ++++++++---
 2 files changed, 13 insertions(+), 3 deletions(-)
diff mbox series

Patch

diff --git a/libavformat/internal.h b/libavformat/internal.h
index 49e82bfbca..f45b1cd6b4 100644
--- a/libavformat/internal.h
+++ b/libavformat/internal.h
@@ -142,6 +142,11 @@  struct AVFormatInternal {
      * Prefer the codec framerate for avg_frame_rate computation.
      */
     int prefer_codec_framerate;
+
+    /**
+     * Set if chapter ids are strictly monotonic.
+     */
+    int chapter_ids_monotonic;
 };
 
 struct AVStreamInternal {
diff --git a/libavformat/utils.c b/libavformat/utils.c
index 3ba4ae4123..a43d227128 100644
--- a/libavformat/utils.c
+++ b/libavformat/utils.c
@@ -4612,9 +4612,14 @@  AVChapter *avpriv_new_chapter(AVFormatContext *s, int id, AVRational time_base,
         return NULL;
     }
 
-    for (i = 0; i < s->nb_chapters; i++)
-        if (s->chapters[i]->id == id)
-            chapter = s->chapters[i];
+    if (!s->nb_chapters) {
+        s->internal->chapter_ids_monotonic = 1;
+    } else if (!s->internal->chapter_ids_monotonic || s->chapters[s->nb_chapters-1]->id >= id) {
+        s->internal->chapter_ids_monotonic = 0;
+        for (i = 0; i < s->nb_chapters; i++)
+            if (s->chapters[i]->id == id)
+                chapter = s->chapters[i];
+    }
 
     if (!chapter) {
         chapter = av_mallocz(sizeof(AVChapter));