[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 at 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