caching of timestamps for mpeg-ps so seeking is faster

move (av_)find_stream_index() to utils.c as its usefull outside mpeg.c
assert checking enabled, to find bugs quicker, should obviously be disabled later
(av_)add_index_entry() inserts new entries so that the list stays ordered and updates entries if already in it
(av_)index_search_timestamp() cleanup (kill ugly goto) and shorter

Originally committed as revision 2697 to svn://svn.ffmpeg.org/ffmpeg/trunk

3 files changed, 128 insertions, 51 deletions

diff --git a/libavformat/avformat.h b/libavformat/avformat.h
index 64bea9c1cd..b098247ab3 100644
--- a/libavformat/avformat.h
+++ b/libavformat/avformat.h
@@ -195,6 +195,9 @@ typedef struct AVIndexEntry {
     int64_t pos;
     int64_t timestamp;
 #define AVINDEX_KEYFRAME 0x0001
+/* the following 2 flags indicate that the next/prev keyframe is known, and scaning for it isnt needed */
+#define AVINDEX_NEXT_KNOWN 0x0002
+#define AVINDEX_PREV_KNOWN 0x0004
     int flags;
 } AVIndexEntry;
 
@@ -544,6 +547,11 @@ AVStream *av_new_stream(AVFormatContext *s, int id);
 void av_set_pts_info(AVFormatContext *s, int pts_wrap_bits,
                      int pts_num, int pts_den);
 
+int av_find_default_stream_index(AVFormatContext *s);
+int av_index_search_timestamp(AVStream *st, int timestamp);
+void av_add_index_entry(AVStream *st,
+                            int64_t pos, int64_t timestamp, int flags);
+
 /* media file output */
 int av_set_parameters(AVFormatContext *s, AVFormatParameters *ap);
 int av_write_header(AVFormatContext *s);
diff --git a/libavformat/mpeg.c b/libavformat/mpeg.c
index 5fcc7f6084..5bd7215d6c 100644
--- a/libavformat/mpeg.c
+++ b/libavformat/mpeg.c
@@ -21,6 +21,9 @@
 #define MAX_PAYLOAD_SIZE 4096
 //#define DEBUG_SEEK
 
+#undef NDEBUG
+#include <assert.h>
+
 typedef struct {
     uint8_t buffer[MAX_PAYLOAD_SIZE];
     int buffer_ptr;
@@ -902,6 +905,15 @@ static int mpegps_read_pes_header(AVFormatContext *s,
             len -= 3;
         }
     }
+    if(dts != AV_NOPTS_VALUE && ppos){
+        int i;
+        for(i=0; i<s->nb_streams; i++){
+            if(startcode == s->streams[i]->id) {
+                av_add_index_entry(s->streams[i], *ppos, dts, 0 /* FIXME keyframe? */);
+            }
+        }
+    }
+    
     *pstart_code = startcode;
     *ppts = pts;
     *pdts = dts;
@@ -913,10 +925,10 @@ static int mpegps_read_packet(AVFormatContext *s,
 {
     AVStream *st;
     int len, startcode, i, type, codec_id;
-    int64_t pts, dts;
+    int64_t pts, dts, dummy_pos; //dummy_pos is needed for the index building to work
 
  redo:
-    len = mpegps_read_pes_header(s, NULL, &startcode, &pts, &dts, 1);
+    len = mpegps_read_pes_header(s, &dummy_pos, &startcode, &pts, &dts, 1);
     if (len < 0)
         return len;
     
@@ -1022,27 +1034,13 @@ static int64_t mpegps_read_dts(AVFormatContext *s, int stream_index,
     return dts;
 }
 
-static int find_stream_index(AVFormatContext *s)
-{
-    int i;
-    AVStream *st;
-
-    if (s->nb_streams <= 0)
-        return -1;
-    for(i = 0; i < s->nb_streams; i++) {
-        st = s->streams[i];
-        if (st->codec.codec_type == CODEC_TYPE_VIDEO) {
-            return i;
-        }
-    }
-    return 0;
-}
-
 static int mpegps_read_seek(AVFormatContext *s, 
                             int stream_index, int64_t timestamp)
 {
     int64_t pos_min, pos_max, pos;
     int64_t dts_min, dts_max, dts;
+    int index;
+    AVStream *st;
 
     timestamp = (timestamp * 90000) / AV_TIME_BASE;
 
@@ -1052,19 +1050,56 @@ static int mpegps_read_seek(AVFormatContext *s,
 
     /* XXX: find stream_index by looking at the first PES packet found */
     if (stream_index < 0) {
-        stream_index = find_stream_index(s);
+        stream_index = av_find_default_stream_index(s);
         if (stream_index < 0)
             return -1;
     }
-    pos_min = 0;
-    dts_min = mpegps_read_dts(s, stream_index, &pos_min, 1);
-    if (dts_min == AV_NOPTS_VALUE) {
-        /* we can reach this case only if no PTS are present in
-           the whole stream */
-        return -1;
+    
+    dts_max=
+    dts_min= AV_NOPTS_VALUE;
+
+    st= s->streams[stream_index];
+    if(st->index_entries){
+        AVIndexEntry *e;
+
+        index= av_index_search_timestamp(st, timestamp);
+        e= &st->index_entries[index];
+        if(e->timestamp <= timestamp){
+            pos_min= e->pos;
+            dts_min= e->timestamp;
+#ifdef DEBUG_SEEK
+        printf("unsing cached pos_min=0x%llx dts_min=%0.3f\n", 
+               pos_min,dts_min / 90000.0);
+#endif
+        }else{
+            assert(index==0);
+        }
+        index++;
+        if(index < st->nb_index_entries){
+            e= &st->index_entries[index];
+            assert(e->timestamp >= timestamp);
+            pos_max= e->pos;
+            dts_max= e->timestamp;
+#ifdef DEBUG_SEEK
+        printf("unsing cached pos_max=0x%llx dts_max=%0.3f\n", 
+               pos_max,dts_max / 90000.0);
+#endif
+        }
+    }
+
+    if(dts_min == AV_NOPTS_VALUE){
+        pos_min = 0;
+        dts_min = mpegps_read_dts(s, stream_index, &pos_min, 1);
+        if (dts_min == AV_NOPTS_VALUE) {
+            /* we can reach this case only if no PTS are present in
+               the whole stream */
+            return -1;
+        }
+    }
+    if(dts_max == AV_NOPTS_VALUE){
+        pos_max = url_filesize(url_fileno(&s->pb)) - 1;
+        dts_max = mpegps_read_dts(s, stream_index, &pos_max, 0);
     }
-    pos_max = url_filesize(url_fileno(&s->pb)) - 1;
-    dts_max = mpegps_read_dts(s, stream_index, &pos_max, 0);
     
     while (pos_min <= pos_max) {
 #ifdef DEBUG_SEEK
diff --git a/libavformat/utils.c b/libavformat/utils.c
index 81f833073b..18f031db46 100644
--- a/libavformat/utils.c
+++ b/libavformat/utils.c
@@ -18,6 +18,9 @@
  */
 #include "avformat.h"
 
+#undef NDEBUG
+#include <assert.h>
+
 AVInputFormat *first_iformat;
 AVOutputFormat *first_oformat;
 AVImageFormat *first_image_format;
@@ -811,6 +814,22 @@ static void flush_packet_queue(AVFormatContext *s)
 /*******************************************************/
 /* seek support */
 
+int av_find_default_stream_index(AVFormatContext *s)
+{
+    int i;
+    AVStream *st;
+
+    if (s->nb_streams <= 0)
+        return -1;
+    for(i = 0; i < s->nb_streams; i++) {
+        st = s->streams[i];
+        if (st->codec.codec_type == CODEC_TYPE_VIDEO) {
+            return i;
+        }
+    }
+    return 0;
+}
+
 /* flush the frame reader */
 static void av_read_frame_flush(AVFormatContext *s)
 {
@@ -841,22 +860,42 @@ static void av_read_frame_flush(AVFormatContext *s)
     }
 }
 
-static void add_index_entry(AVStream *st,
+/* add a index entry into a sorted list updateing if it is already there */
+void av_add_index_entry(AVStream *st,
                             int64_t pos, int64_t timestamp, int flags)
 {
     AVIndexEntry *entries, *ie;
+    int index;
     
     entries = av_fast_realloc(st->index_entries,
                               &st->index_entries_allocated_size,
                               (st->nb_index_entries + 1) * 
                               sizeof(AVIndexEntry));
-    if (entries) {
-        st->index_entries = entries;
-        ie = &entries[st->nb_index_entries++];
-        ie->pos = pos;
-        ie->timestamp = timestamp;
-        ie->flags = flags;
-    }
+    st->index_entries= entries;
+
+    if(st->nb_index_entries){
+        index= av_index_search_timestamp(st, timestamp);
+        ie= &entries[index];
+
+        if(ie->timestamp != timestamp){
+            if(ie->timestamp < timestamp){
+                index++; //index points to next instead of previous entry, maybe nonexistant
+                ie= &st->index_entries[index];
+            }else
+                assert(index==0);
+                
+            if(index != st->nb_index_entries){
+                assert(index < st->nb_index_entries);
+                memmove(entries + index + 1, entries + index, sizeof(AVIndexEntry)*(st->nb_index_entries - index));
+            }
+            st->nb_index_entries++;
+        }
+    }else
+        ie= &entries[st->nb_index_entries++];
+    
+    ie->pos = pos;
+    ie->timestamp = timestamp;
+    ie->flags = flags;
 }
 
 /* build an index for raw streams using a parser */
@@ -876,7 +915,7 @@ static void av_build_index_raw(AVFormatContext *s)
             break;
         if (pkt->stream_index == 0 && st->parser &&
             (pkt->flags & PKT_FLAG_KEY)) {
-            add_index_entry(st, st->parser->frame_offset, pkt->dts, 
+            av_add_index_entry(st, st->parser->frame_offset, pkt->dts, 
                             AVINDEX_KEYFRAME);
         }
         av_free_packet(pkt);
@@ -899,9 +938,10 @@ static int is_raw_stream(AVFormatContext *s)
 
 /* return the largest index entry whose timestamp is <=
    wanted_timestamp */
-static int index_search_timestamp(AVIndexEntry *entries, 
-                                  int nb_entries, int wanted_timestamp)
+int av_index_search_timestamp(AVStream *st, int wanted_timestamp)
 {
+    AVIndexEntry *entries= st->index_entries;
+    int nb_entries= st->nb_index_entries;
     int a, b, m;
     int64_t timestamp;
 
@@ -910,22 +950,17 @@ static int index_search_timestamp(AVIndexEntry *entries,
     
     a = 0;
     b = nb_entries - 1;
-    while (a <= b) {
-        m = (a + b) >> 1;
+
+    while (a < b) {
+        m = (a + b + 1) >> 1;
         timestamp = entries[m].timestamp;
-        if (timestamp == wanted_timestamp)
-            goto found;
-        else if (timestamp > wanted_timestamp) {
+        if (timestamp > wanted_timestamp) {
             b = m - 1;
         } else {
-            a = m + 1;
+            a = m;
         }
     }
-    m = a;
-    if (m > 0)
-        m--;
- found:
-    return m;
+    return a;
 }
 
 static int av_seek_frame_generic(AVFormatContext *s, 
@@ -947,8 +982,7 @@ static int av_seek_frame_generic(AVFormatContext *s,
     if (stream_index < 0)
         stream_index = 0;
     st = s->streams[stream_index];
-    index = index_search_timestamp(st->index_entries, st->nb_index_entries,
-                                   timestamp);
+    index = av_index_search_timestamp(st, timestamp);
     if (index < 0)
         return -1;