diff mbox series

[FFmpeg-devel,1/2] avformat/utils: Change compute_chapters_end() from O(n²) to O(n log n)

Message ID 20201122153733.26513-1-michael@niedermayer.cc
State New
Headers show
Series [FFmpeg-devel,1/2] avformat/utils: Change compute_chapters_end() from O(n²) to O(n log n) | expand

Checks

Context Check Description
andriy/x86_make_warn warning New warnings during build
andriy/x86_make success Make finished
andriy/x86_make_fate success Make fate finished

Commit Message

Michael Niedermayer Nov. 22, 2020, 3:37 p.m. UTC 
Fixes: Timeout (49sec -> 9sec)
Fixes: 27427/clusterfuzz-testcase-minimized-ffmpeg_dem_FFMETADATA_fuzzer-5140589838073856

Found-by: continuous fuzzing process https://github.com/google/oss-fuzz/tree/master/projects/ffmpeg
Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
---
 libavformat/utils.c | 42 ++++++++++++++++++++++++++++++++----------
 1 file changed, 32 insertions(+), 10 deletions(-)

Comments

Anton Khirnov Dec. 4, 2020, 10:21 a.m. UTC | #1 
Quoting Michael Niedermayer (2020-11-22 16:37:32)
> Fixes: Timeout (49sec -> 9sec)
> Fixes: 27427/clusterfuzz-testcase-minimized-ffmpeg_dem_FFMETADATA_fuzzer-5140589838073856
> 
> Found-by: continuous fuzzing process https://github.com/google/oss-fuzz/tree/master/projects/ffmpeg
> Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
> ---

Not objecting to the patch itself, but just wondering: do we actually
want to compute chapter ends when the file doesn't store them?
I can imagine users might want to distinguish whether the end time is
explicitly specified or not.
Michael Niedermayer Jan. 8, 2021, 6:22 p.m. UTC | #2 
On Fri, Dec 04, 2020 at 11:21:22AM +0100, Anton Khirnov wrote:
> Quoting Michael Niedermayer (2020-11-22 16:37:32)
> > Fixes: Timeout (49sec -> 9sec)
> > Fixes: 27427/clusterfuzz-testcase-minimized-ffmpeg_dem_FFMETADATA_fuzzer-5140589838073856
> > 
> > Found-by: continuous fuzzing process https://github.com/google/oss-fuzz/tree/master/projects/ffmpeg
> > Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
> > ---
> 
> Not objecting to the patch itself, but just wondering: do we actually
> want to compute chapter ends when the file doesn't store them?
> I can imagine users might want to distinguish whether the end time is
> explicitly specified or not.

seems noone had a comment so ill apply the patch

thx

[...]
diff mbox series

Patch

diff --git a/libavformat/utils.c b/libavformat/utils.c
index 503e583ad0..db4b54aebe 100644
--- a/libavformat/utils.c
+++ b/libavformat/utils.c
@@ -3191,31 +3191,51 @@  enum AVCodecID av_codec_get_id(const AVCodecTag *const *tags, unsigned int tag)
     return AV_CODEC_ID_NONE;
 }
 
-static void compute_chapters_end(AVFormatContext *s)
+static int chapter_start_cmp(const void *p1, const void *p2)
+{
+    AVChapter *ch1 = *(AVChapter**)p1;
+    AVChapter *ch2 = *(AVChapter**)p2;
+    int delta = av_compare_ts(ch1->start, ch1->time_base, ch2->start, ch2->time_base);
+    if (delta)
+        return delta;
+    return (ch1 > ch2) - (ch1 < ch2);
+}
+
+static int compute_chapters_end(AVFormatContext *s)
 {
     unsigned int i, j;
     int64_t max_time = 0;
+    AVChapter **timetable = av_malloc(s->nb_chapters * sizeof(*timetable));
+
+    if (!timetable)
+        return AVERROR(ENOMEM);
 
     if (s->duration > 0 && s->start_time < INT64_MAX - s->duration)
         max_time = s->duration +
                        ((s->start_time == AV_NOPTS_VALUE) ? 0 : s->start_time);
 
     for (i = 0; i < s->nb_chapters; i++)
-        if (s->chapters[i]->end == AV_NOPTS_VALUE) {
-            AVChapter *ch = s->chapters[i];
+        timetable[i] = s->chapters[i];
+    qsort(timetable, s->nb_chapters, sizeof(*timetable), chapter_start_cmp);
+
+    for (i = 0; i < s->nb_chapters; i++)
+        if (timetable[i]->end == AV_NOPTS_VALUE) {
+            AVChapter *ch = timetable[i];
             int64_t end = max_time ? av_rescale_q(max_time, AV_TIME_BASE_Q,
-                                                  ch->time_base)
-                                   : INT64_MAX;
+                                                ch->time_base)
+                                : INT64_MAX;
 
-            for (j = 0; j < s->nb_chapters; j++) {
-                AVChapter *ch1     = s->chapters[j];
+            if (i + 1 < s->nb_chapters) {
+                AVChapter *ch1     = timetable[i + 1];
                 int64_t next_start = av_rescale_q(ch1->start, ch1->time_base,
-                                                  ch->time_base);
-                if (j != i && next_start > ch->start && next_start < end)
+                                                ch->time_base);
+                if (next_start > ch->start && next_start < end)
                     end = next_start;
             }
             ch->end = (end == INT64_MAX || end < ch->start) ? ch->start : end;
         }
+    av_free(timetable);
+    return 0;
 }
 
 static int get_std_framerate(int i)
@@ -4071,7 +4091,9 @@  FF_ENABLE_DEPRECATION_WARNINGS
         }
     }
 
-    compute_chapters_end(ic);
+    ret = compute_chapters_end(ic);
+    if (ret < 0)
+        goto find_stream_info_err;
 
     /* update the stream parameters from the internal codec contexts */
     for (i = 0; i < ic->nb_streams; i++) {