lavf/mov.c: Refine edit list start seek, based on PTS computed from CTTS.

Partially fixes t/6699.

Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>

3 files changed, 127 insertions, 43 deletions

diff --git a/libavformat/mov.c b/libavformat/mov.c
index 60f0228..7954db6 100644
--- a/libavformat/mov.c
+++ b/libavformat/mov.c
@@ -3014,34 +3014,99 @@ static int get_edit_list_entry(MOVContext *mov,
 }
 
 /**
- * Find the closest previous frame to the timestamp, in e_old index
+ * Find the closest previous frame to the timestamp_pts, in e_old index
  * entries. Searching for just any frame / just key frames can be controlled by
  * last argument 'flag'.
- * Returns the index of the entry in st->index_entries if successful,
- * else returns -1.
+ * Note that if ctts_data is not NULL, we will always search for a key frame
+ * irrespective of the value of 'flag'. If we don't find any keyframe, we will
+ * return the first frame of the video.
+ *
+ * Here the timestamp_pts is considered to be a presentation timestamp and
+ * the timestamp of index entries are considered to be decoding timestamps.
+ *
+ * Returns 0 if successful in finding a frame, else returns -1.
+ * Places the found index corresponding output arg.
+ *
+ * If ctts_old is not NULL, then refines the searched entry by searching
+ * backwards from the found timestamp, to find the frame with correct PTS.
+ *
+ * Places the found ctts_index and ctts_sample in corresponding output args.
  */
-static int64_t find_prev_closest_index(AVStream *st,
-                                       AVIndexEntry *e_old,
-                                       int nb_old,
-                                       int64_t timestamp,
-                                       int flag)
+static int find_prev_closest_index(AVStream *st,
+                                   AVIndexEntry *e_old,
+                                   int nb_old,
+                                   MOVStts* ctts_data,
+                                   int64_t ctts_count,
+                                   int64_t timestamp_pts,
+                                   int flag,
+                                   int64_t* index,
+                                   int64_t* ctts_index,
+                                   int64_t* ctts_sample)
 {
+    MOVStreamContext *msc = st->priv_data;
     AVIndexEntry *e_keep = st->index_entries;
     int nb_keep = st->nb_index_entries;
-    int64_t found = -1;
     int64_t i = 0;
+    int64_t index_ctts_count;
+
+    av_assert0(index);
+
+    // If dts_shift > 0, then all the index timestamps will have to be offset by
+    // at least dts_shift amount to obtain PTS.
+    // Hence we decrement the searched timestamp_pts by dts_shift to find the closest index element.
+    if (msc->dts_shift > 0) {
+        timestamp_pts -= msc->dts_shift;
+    }
 
     st->index_entries = e_old;
     st->nb_index_entries = nb_old;
-    found = av_index_search_timestamp(st, timestamp, flag | AVSEEK_FLAG_BACKWARD);
+    *index = av_index_search_timestamp(st, timestamp_pts, flag | AVSEEK_FLAG_BACKWARD);
 
     // Keep going backwards in the index entries until the timestamp is the same.
-    if (found >= 0) {
-        for (i = found; i > 0 && e_old[i].timestamp == e_old[i - 1].timestamp;
+    if (*index >= 0) {
+        for (i = *index; i > 0 && e_old[i].timestamp == e_old[i - 1].timestamp;
              i--) {
             if ((flag & AVSEEK_FLAG_ANY) ||
                 (e_old[i - 1].flags & AVINDEX_KEYFRAME)) {
-                found = i - 1;
+                *index = i - 1;
+            }
+        }
+    }
+
+    // If we have CTTS then refine the search, by searching backwards over PTS
+    // computed by adding corresponding CTTS durations to index timestamps.
+    if (ctts_data && *index >= 0) {
+        av_assert0(ctts_index);
+        av_assert0(ctts_sample);
+        // Find out the ctts_index for the found frame.
+        *ctts_index = 0;
+        *ctts_sample = 0;
+        for (index_ctts_count = 0; index_ctts_count < *index; index_ctts_count++) {
+            if (*ctts_index < ctts_count) {
+                (*ctts_sample)++;
+                if (ctts_data[*ctts_index].count == *ctts_sample) {
+                    (*ctts_index)++;
+                    *ctts_sample = 0;
+                }
+            }
+        }
+
+        while (*index >= 0 && (*ctts_index) >= 0) {
+            // Find a "key frame" with PTS <= timestamp_pts (So that we can decode B-frames correctly).
+            // No need to add dts_shift to the timestamp here becase timestamp_pts has already been
+            // compensated by dts_shift above.
+            if ((e_old[*index].timestamp + ctts_data[*ctts_index].duration) <= timestamp_pts &&
+                (e_old[*index].flags & AVINDEX_KEYFRAME)) {
+                break;
+            }
+
+            (*index)--;
+            if (*ctts_sample == 0) {
+                (*ctts_index)--;
+                if (*ctts_index >= 0)
+                  *ctts_sample = ctts_data[*ctts_index].count - 1;
+            } else {
+                (*ctts_sample)--;
             }
         }
     }
@@ -3049,7 +3114,7 @@ static int64_t find_prev_closest_index(AVStream *st,
     /* restore AVStream state*/
     st->index_entries = e_keep;
     st->nb_index_entries = nb_keep;
-    return found;
+    return *index >= 0 ? 0 : -1;
 }
 
 /**
@@ -3220,10 +3285,8 @@ static void mov_fix_index(MOVContext *mov, AVStream *st)
     int64_t empty_edits_sum_duration = 0;
     int64_t edit_list_index = 0;
     int64_t index;
-    int64_t index_ctts_count;
     int flags;
     int64_t start_dts = 0;
-    int64_t edit_list_media_time_dts = 0;
     int64_t edit_list_start_encountered = 0;
     int64_t search_timestamp = 0;
     int64_t* frame_duration_buffer = NULL;
@@ -3293,17 +3356,11 @@ static void mov_fix_index(MOVContext *mov, AVStream *st)
                 st->skip_samples = msc->start_pad = 0;
         }
 
-        //find closest previous key frame
-        edit_list_media_time_dts = edit_list_media_time;
-        if (msc->dts_shift > 0) {
-            edit_list_media_time_dts -= msc->dts_shift;
-        }
-
         // While reordering frame index according to edit list we must handle properly
         // the scenario when edit list entry starts from none key frame.
         // We find closest previous key frame and preserve it and consequent frames in index.
         // All frames which are outside edit list entry time boundaries will be dropped after decoding.
-        search_timestamp = edit_list_media_time_dts;
+        search_timestamp = edit_list_media_time;
         if (st->codecpar->codec_type == AVMEDIA_TYPE_AUDIO) {
             // Audio decoders like AAC need need a decoder delay samples previous to the current sample,
             // to correctly decode this frame. Hence for audio we seek to a frame 1 sec. before the
@@ -3311,38 +3368,24 @@ static void mov_fix_index(MOVContext *mov, AVStream *st)
             search_timestamp = FFMAX(search_timestamp - msc->time_scale, e_old[0].timestamp);
         }
 
-        index = find_prev_closest_index(st, e_old, nb_old, search_timestamp, 0);
-        if (index == -1) {
+        if (find_prev_closest_index(st, e_old, nb_old, ctts_data_old, ctts_count_old, search_timestamp, 0,
+                                    &index, &ctts_index_old, &ctts_sample_old) < 0) {
             av_log(mov->fc, AV_LOG_WARNING,
                    "st: %d edit list: %"PRId64" Missing key frame while searching for timestamp: %"PRId64"\n",
                    st->index, edit_list_index, search_timestamp);
-            index = find_prev_closest_index(st, e_old, nb_old, search_timestamp, AVSEEK_FLAG_ANY);
-
-            if (index == -1) {
+            if (find_prev_closest_index(st, e_old, nb_old, ctts_data_old, ctts_count_old, search_timestamp, AVSEEK_FLAG_ANY,
+                                        &index, &ctts_index_old, &ctts_sample_old) < 0) {
                 av_log(mov->fc, AV_LOG_WARNING,
                        "st: %d edit list %"PRId64" Cannot find an index entry before timestamp: %"PRId64".\n"
                        "Rounding edit list media time to zero.\n",
                        st->index, edit_list_index, search_timestamp);
                 index = 0;
+                ctts_index_old = 0;
+                ctts_sample_old = 0;
                 edit_list_media_time = 0;
             }
         }
         current = e_old + index;
-
-        ctts_index_old = 0;
-        ctts_sample_old = 0;
-
-        // set ctts_index properly for the found key frame
-        for (index_ctts_count = 0; index_ctts_count < index; index_ctts_count++) {
-            if (ctts_data_old && ctts_index_old < ctts_count_old) {
-                ctts_sample_old++;
-                if (ctts_data_old[ctts_index_old].count == ctts_sample_old) {
-                    ctts_index_old++;
-                    ctts_sample_old = 0;
-                }
-            }
-        }
-
         edit_list_start_ctts_sample = ctts_sample_old;
 
         // Iterate over index and arrange it according to edit list
diff --git a/tests/fate/mov.mak b/tests/fate/mov.mak
index 6815e4f..01893a0 100644
--- a/tests/fate/mov.mak
+++ b/tests/fate/mov.mak
@@ -9,6 +9,7 @@ FATE_MOV = fate-mov-3elist \
            fate-mov-invalid-elst-entry-count \
            fate-mov-gpmf-remux \
            fate-mov-440hz-10ms \
+           fate-mov-ibi-elst-starts-b \
 
 FATE_MOV_FFPROBE = fate-mov-aac-2048-priming \
                    fate-mov-zombie \
@@ -47,6 +48,13 @@ fate-mov-440hz-10ms: CMD = framemd5 -i $(TARGET_SAMPLES)/mov/440hz-10ms.m4a
 # Makes sure that we handle invalid edit list entry count correctly.
 fate-mov-invalid-elst-entry-count: CMD = framemd5 -flags +bitexact -i $(TARGET_SAMPLES)/mov/invalid_elst_entry_count.mov
 
+# Makes sure that 1st key-frame is picked when,
+#    i) One B-frame between 2 key-frames
+#   ii) Edit list starts on B-frame.
+#  iii) Both key-frames have their DTS < edit list start
+# i.e.  Pts Order: I-B-I
+fate-mov-ibi-elst-starts-b: CMD = framemd5 -flags +bitexact -i $(TARGET_SAMPLES)/mov/mov_ibi_elst_starts_b.mov
+
 fate-mov-aac-2048-priming: CMD = run ffprobe$(PROGSSUF)$(EXESUF) -show_packets -print_format compact $(TARGET_SAMPLES)/mov/aac-2048-priming.mov
 
 fate-mov-zombie: CMD = run ffprobe$(PROGSSUF)$(EXESUF) -show_streams -show_packets -show_frames -bitexact -print_format compact $(TARGET_SAMPLES)/mov/white_zombie_scrunch-part.mov
diff --git a/tests/ref/fate/mov-ibi-elst-starts-b b/tests/ref/fate/mov-ibi-elst-starts-b
new file mode 100644
index 0000000..1ab9c2a
--- /dev/null
+++ b/tests/ref/fate/mov-ibi-elst-starts-b
@@ -0,0 +1,33 @@
+#format: frame checksums
+#version: 2
+#hash: MD5
+#tb 0: 1/25
+#media_type 0: video
+#codec_id 0: rawvideo
+#dimensions 0: 320x240
+#sar 0: 1/1
+#stream#, dts,        pts, duration,     size, hash
+0,          0,          0,        1,   115200, 7e20f8729b6b53dc11791927bf4a5aec
+0,          1,          1,        1,   115200, 4e5dc2b806e394cd666c968f736fecd0
+0,          2,          2,        1,   115200, 7a3c7473d44c5f60c07655f6fc0c2ac3
+0,          3,          3,        1,   115200, 038254422a603a3270c09cdcd149707b
+0,          4,          4,        1,   115200, 7553b6b4547cb23ef8f0392ed5a5d4b0
+0,          5,          5,        1,   115200, 6d017ede7f446124af7308667cb0dc41
+0,          6,          6,        1,   115200, 77752f0288ae64f857732b8e62e47457
+0,          7,          7,        1,   115200, d656833951af99330625f7c6de7685c4
+0,          8,          8,        1,   115200, 14338b833e431e566ac98da841600bfe
+0,          9,          9,        1,   115200, 07ea95d1659f3c4424a470a546d0df6e
+0,         10,         10,        1,   115200, fd05b8cc83072f813e89d394d1f6efc6
+0,         11,         11,        1,   115200, 750b82ca5c7e901545e7b1aa69692426
+0,         12,         12,        1,   115200, 7347679ab09bc936047368b8caebcaff
+0,         13,         13,        1,   115200, 63a23fdd57ac8462b9ffbcb12ab717b3
+0,         14,         14,        1,   115200, 705257a1c99693db233e2a3ee027adcf
+0,         15,         15,        1,   115200, df861a2ec7a4ef70e82b1c28025e5a48
+0,         16,         16,        1,   115200, 2a8b403c077b6b43aa71eaf7d1537713
+0,         17,         17,        1,   115200, 973b5cd3ce473e3970dfa96045553172
+0,         18,         18,        1,   115200, fc612c0afeae3b6576b5ee2f3f119832
+0,         19,         19,        1,   115200, 97074fe5a0b6e7e8470729654092e56c
+0,         20,         20,        1,   115200, 8cf9337201065335b3aa4da21dc9b37a
+0,         21,         21,        1,   115200, 93ff3589294cc0673af3daee1e7fe42a
+0,         22,         22,        1,   115200, c0b6fd870a022f374f9d6c697e8e293d
+0,         23,         23,        1,   115200, bc4638ff7036b323c39a948a6407695d