diff mbox series

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

Message ID 20201121172429.18034-1-michael@niedermayer.cc
State Superseded
Headers show
Series [FFmpeg-devel] avformat/utils: Change compute_chapters_end() from O(n²) to O(n log n)
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 Nov. 21, 2020, 5:24 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 | 43 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 43 insertions(+)

Comments

Lynne Nov. 21, 2020, 6:32 p.m. UTC | #1
Nov 21, 2020, 18:24 by michael@niedermayer.cc:

> 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 | 43 +++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 43 insertions(+)
>
> diff --git a/libavformat/utils.c b/libavformat/utils.c
> index 503e583ad0..9fac3fc2aa 100644
> --- a/libavformat/utils.c
> +++ b/libavformat/utils.c
> @@ -3191,15 +3191,58 @@ enum AVCodecID av_codec_get_id(const AVCodecTag *const *tags, unsigned int tag)
>  return AV_CODEC_ID_NONE;
>  }
>  
> +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 void compute_chapters_end(AVFormatContext *s)
>  {
>  unsigned int i, j;
>  int64_t max_time = 0;
> +    int computations = 0;
>  
>  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)
> +            computations ++;
> +
> +    if (computations > 5) {
> +        AVChapter **timetable = av_malloc(s->nb_chapters * sizeof(*timetable));
> +        if (timetable) {
>

Its a void function, but shouldn't you change it to make it return
AVERROR(ENOMEM) and then handle that in the caller?
No memory is pretty catastrophic.
Michael Niedermayer Nov. 21, 2020, 9:01 p.m. UTC | #2
On Sat, Nov 21, 2020 at 07:32:31PM +0100, Lynne wrote:
> Nov 21, 2020, 18:24 by michael@niedermayer.cc:
> 
> > 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 | 43 +++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 43 insertions(+)
> >
> > diff --git a/libavformat/utils.c b/libavformat/utils.c
> > index 503e583ad0..9fac3fc2aa 100644
> > --- a/libavformat/utils.c
> > +++ b/libavformat/utils.c
> > @@ -3191,15 +3191,58 @@ enum AVCodecID av_codec_get_id(const AVCodecTag *const *tags, unsigned int tag)
> >  return AV_CODEC_ID_NONE;
> >  }
> >  
> > +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 void compute_chapters_end(AVFormatContext *s)
> >  {
> >  unsigned int i, j;
> >  int64_t max_time = 0;
> > +    int computations = 0;
> >  
> >  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)
> > +            computations ++;
> > +
> > +    if (computations > 5) {
> > +        AVChapter **timetable = av_malloc(s->nb_chapters * sizeof(*timetable));
> > +        if (timetable) {
> >
> 
> Its a void function, but shouldn't you change it to make it return
> AVERROR(ENOMEM) and then handle that in the caller?
> No memory is pretty catastrophic.

you are probably correct, that fallback isnt worth it, ill drop it and
return failure

thx

[...]
diff mbox series

Patch

diff --git a/libavformat/utils.c b/libavformat/utils.c
index 503e583ad0..9fac3fc2aa 100644
--- a/libavformat/utils.c
+++ b/libavformat/utils.c
@@ -3191,15 +3191,58 @@  enum AVCodecID av_codec_get_id(const AVCodecTag *const *tags, unsigned int tag)
     return AV_CODEC_ID_NONE;
 }
 
+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 void compute_chapters_end(AVFormatContext *s)
 {
     unsigned int i, j;
     int64_t max_time = 0;
+    int computations = 0;
 
     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)
+            computations ++;
+
+    if (computations > 5) {
+        AVChapter **timetable = av_malloc(s->nb_chapters * sizeof(*timetable));
+        if (timetable) {
+            for (i = 0; i < s->nb_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;
+
+                    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 (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;
+        }
+    }
+
     for (i = 0; i < s->nb_chapters; i++)
         if (s->chapters[i]->end == AV_NOPTS_VALUE) {
             AVChapter *ch = s->chapters[i];