[FFmpeg-devel] [PATCH] avformat/mov: Speed up finding MOVFragmentIndexItem

[FFmpeg-devel] [PATCH] avformat/mov: Speed up finding MOVFragmentIndexItem

[Andreas Rheinhardt]

The MOVFragmentIndexItems of a MOVFragmentIndex are ordered
by increasing moof_offset; yet get_frag_stream_info_from_pkt()
searched the array of index items linearly for the item
with moof_offset <= pos < moof_offset of next index (if existing).

This commit changes this: First, it is checked, whether
the current item or the next item are the desired items;
it this fails, a array is searched via binary search.

Fixes ticket #9941.

Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@outlook.com>
---
The earlier code reused current in case pkt->pos is before
the first moof_offset. I kept this behaviour, although I don't know
whether this can actually happen.

 libavformat/mov.c | 44 +++++++++++++++++++++++++++++---------------
 1 file changed, 29 insertions(+), 15 deletions(-)

diff --git a/libavformat/mov.c b/libavformat/mov.c
index 1f436e21d6..79331638b0 100644
--- a/libavformat/mov.c
+++ b/libavformat/mov.c
@@ -7192,26 +7192,40 @@ static int cenc_decrypt(MOVContext *c, MOVStreamContext *sc, AVEncryptionInfo *s
 static MOVFragmentStreamInfo *get_frag_stream_info_from_pkt(MOVFragmentIndex *frag_index, AVPacket *pkt, int id)
 {
     int current = frag_index->current;
+    int next = -1;
 
     if (!frag_index->nb_items)
         return NULL;
 
     // Check frag_index->current is the right one for pkt. It can out of sync.
-    if (current >= 0 && current < frag_index->nb_items) {
-        if (frag_index->item[current].moof_offset < pkt->pos &&
-            (current + 1 == frag_index->nb_items ||
-             frag_index->item[current + 1].moof_offset > pkt->pos))
-            return get_frag_stream_info(frag_index, current, id);
-    }
-
-
-    for (int i = 0; i < frag_index->nb_items; i++) {
-        if (frag_index->item[i].moof_offset > pkt->pos)
-            break;
-        current = i;
-    }
-    frag_index->current = current;
-    return get_frag_stream_info(frag_index, current, id);
+    if (current >= 0 && current < frag_index->nb_items &&
+        frag_index->item[current].moof_offset <= pkt->pos) {
+        if (current + 1U == frag_index->nb_items ||
+            frag_index->item[current + 1].moof_offset > pkt->pos) {
+            next = current;
+        } else if (current + 2U == frag_index->nb_items ||
+                   frag_index->item[current + 2].moof_offset > pkt->pos)
+            next = current + 1;
+    }
+
+    if (next < 0) {
+        if (pkt->pos < frag_index->item[0].moof_offset) {
+            /* Can this happen? Does this make sense? */
+            next = current;
+        } else {
+            next = search_frag_moof_offset(frag_index, pkt->pos);
+            /* If there is no exact match for pkt->pos, then
+             * search_frag_moof_offset() returns the index of
+             * the first item with moof_offset > pkt->pos
+             * (or frag_index->nb_items if no such item exists). */
+            if (next == frag_index->nb_items)
+                next = frag_index->nb_items - 1;
+            else if (frag_index->item[next].moof_offset > pkt->pos)
+                next--;
+        }
+    }
+    frag_index->current = next;
+    return get_frag_stream_info(frag_index, next, id);
 }
 
 static int cenc_filter(MOVContext *mov, AVStream* st, MOVStreamContext *sc, AVPacket *pkt, int current_index)
-- 
2.34.1

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

Re: [FFmpeg-devel] [PATCH] avformat/mov: Speed up finding MOVFragmentIndexItem

[Zhao Zhili]

> -----Original Message-----
> From: ffmpeg-devel-bounces@ffmpeg.org <ffmpeg-devel-bounces@ffmpeg.org> On Behalf Of Andreas Rheinhardt
> Sent: 2022年9月25日 7:21
> To: ffmpeg-devel@ffmpeg.org
> Cc: Andreas Rheinhardt <andreas.rheinhardt@outlook.com>
> Subject: [FFmpeg-devel] [PATCH] avformat/mov: Speed up finding MOVFragmentIndexItem
> 
> The MOVFragmentIndexItems of a MOVFragmentIndex are ordered
> by increasing moof_offset; yet get_frag_stream_info_from_pkt()
> searched the array of index items linearly for the item
> with moof_offset <= pos < moof_offset of next index (if existing).
> 
> This commit changes this: First, it is checked, whether
> the current item or the next item are the desired items;
> it this fails, a array is searched via binary search.
> 
> Fixes ticket #9941.
> 
> Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@outlook.com>
> ---
> The earlier code reused current in case pkt->pos is before
> the first moof_offset. I kept this behaviour, although I don't know
> whether this can actually happen.
> 
>  libavformat/mov.c | 44 +++++++++++++++++++++++++++++---------------
>  1 file changed, 29 insertions(+), 15 deletions(-)
> 
> diff --git a/libavformat/mov.c b/libavformat/mov.c
> index 1f436e21d6..79331638b0 100644
> --- a/libavformat/mov.c
> +++ b/libavformat/mov.c
> @@ -7192,26 +7192,40 @@ static int cenc_decrypt(MOVContext *c, MOVStreamContext *sc, AVEncryptionInfo *s
>  static MOVFragmentStreamInfo *get_frag_stream_info_from_pkt(MOVFragmentIndex *frag_index, AVPacket *pkt, int id)
>  {
>      int current = frag_index->current;
> +    int next = -1;
> 
>      if (!frag_index->nb_items)
>          return NULL;
> 
>      // Check frag_index->current is the right one for pkt. It can out of sync.
> -    if (current >= 0 && current < frag_index->nb_items) {
> -        if (frag_index->item[current].moof_offset < pkt->pos &&
> -            (current + 1 == frag_index->nb_items ||
> -             frag_index->item[current + 1].moof_offset > pkt->pos))
> -            return get_frag_stream_info(frag_index, current, id);
> -    }
> -
> -
> -    for (int i = 0; i < frag_index->nb_items; i++) {
> -        if (frag_index->item[i].moof_offset > pkt->pos)
> -            break;
> -        current = i;
> -    }
> -    frag_index->current = current;
> -    return get_frag_stream_info(frag_index, current, id);
> +    if (current >= 0 && current < frag_index->nb_items &&
> +        frag_index->item[current].moof_offset <= pkt->pos) {
> +        if (current + 1U == frag_index->nb_items ||
> +            frag_index->item[current + 1].moof_offset > pkt->pos) {
> +            next = current;
> +        } else if (current + 2U == frag_index->nb_items ||
> +                   frag_index->item[current + 2].moof_offset > pkt->pos)
> +            next = current + 1;
> +    }
> +
> +    if (next < 0) {
> +        if (pkt->pos < frag_index->item[0].moof_offset) {
> +            /* Can this happen? Does this make sense? */
> +            next = current;

A file can be created with mdat before it's moof, or anywhere. Of course it
make no sense, and will break the search strategy. Maybe print a warning
message and return NULL.

> +        } else {
> +            next = search_frag_moof_offset(frag_index, pkt->pos);
> +            /* If there is no exact match for pkt->pos, then
> +             * search_frag_moof_offset() returns the index of
> +             * the first item with moof_offset > pkt->pos
> +             * (or frag_index->nb_items if no such item exists). */
> +            if (next == frag_index->nb_items)
> +                next = frag_index->nb_items - 1;
> +            else if (frag_index->item[next].moof_offset > pkt->pos)
> +                next--;
> +        }

search_frag_moof_offset() was meant to search moof from moof_offset
exactly, now it is used for a second purpose, and the code depends on the
implementation details of search_frag_moof_offset() to return the next
item with moof_offset > pkt->pos. I think search_frag_moof_offset() needs
a simple comments. This part LGTM.

> +    }
> +    frag_index->current = next;
> +    return get_frag_stream_info(frag_index, next, id);
>  }
> 
>  static int cenc_filter(MOVContext *mov, AVStream* st, MOVStreamContext *sc, AVPacket *pkt, int current_index)
> --
> 2.34.1
> 
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel@ffmpeg.org
> https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
> 
> To unsubscribe, visit link above, or email
> ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".