moving nearly identical binary search code from nut/mpeg/asf to utils.c

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

1 files changed, 12 insertions, 147 deletions

diff --git a/libavformat/nut.c b/libavformat/nut.c
index 83bb8841ea..56d733f7cb 100644
--- a/libavformat/nut.c
+++ b/libavformat/nut.c
@@ -1107,10 +1107,11 @@ static int decode_frame(NUTContext *nut, AVPacket *pkt, int frame_code, int fram
         if(flags & FLAG_FULL_PTS){
             pts= get_v(bc);
             if(frame_type && key_frame){
+                int64_t av_pts= pts * AV_TIME_BASE * stream->rate_den / stream->rate_num;
                 av_add_index_entry(
                     s->streams[stream_id], 
                     frame_start, 
-                    pts, 
+                    av_pts, 
                     frame_start - nut->stream[stream_id].last_sync_pos,
                     AVINDEX_KEYFRAME);
                 nut->stream[stream_id].last_sync_pos= frame_start;
@@ -1231,8 +1232,9 @@ av_log(s, AV_LOG_DEBUG, "steping back to %lld next %d\n", pos, size);
     }
 }
 
-static int64_t read_timestamp(AVFormatContext *s, int stream_index, int64_t *pos_arg, int64_t pos_limit){
+static int64_t nut_read_timestamp(AVFormatContext *s, int stream_index, int64_t *pos_arg, int64_t pos_limit){
     NUTContext *nut = s->priv_data;
+    StreamContext *stream;
     ByteIOContext *bc = &s->pb;
     int64_t pos, pts;
     uint64_t code;
@@ -1305,7 +1307,8 @@ av_log(s, AV_LOG_DEBUG, "read_timestamp(X,%d,%lld,%lld)\n", stream_index, *pos_a
             if(stream_id >= s->nb_streams)
                 goto resync;
                 
-            pts= get_v(bc);
+            stream= &nut->stream[stream_id];
+            pts= get_v(bc) * AV_TIME_BASE * stream->rate_den / stream->rate_num;
     
             if(flags & FLAG_KEY_FRAME){
                 av_add_index_entry(
@@ -1336,155 +1339,16 @@ av_log(s, AV_LOG_DEBUG, "syncing from %lld\n", nut->packet_start+1);
     return AV_NOPTS_VALUE;
 }
 
-#define DEBUG_SEEK
 static int nut_read_seek(AVFormatContext *s, int stream_index, int64_t target_ts){
     NUTContext *nut = s->priv_data;
-    StreamContext *stream;
-    int64_t pos_min, pos_max, pos, pos_limit;
-    int64_t ts_min, ts_max, ts;
-    int64_t start_pos;
-    int index, no_change,i;
-    AVStream *st;
-
-    if (stream_index < 0) {
-        stream_index = av_find_default_stream_index(s);
-        if (stream_index < 0)
-            return -1;
-    }
-    stream= &nut->stream[stream_index];
-    target_ts= (av_rescale(target_ts, stream->rate_num, stream->rate_den) + AV_TIME_BASE/2) / AV_TIME_BASE;
-
-#ifdef DEBUG_SEEK
-    av_log(s, AV_LOG_DEBUG, "read_seek: %d %lld\n", stream_index, target_ts);
-#endif
-
-    ts_max=
-    ts_min= AV_NOPTS_VALUE;
-    pos_limit= -1; //gcc falsely says it may be uninitalized
-
-    st= s->streams[stream_index];
-    if(st->index_entries){
-        AVIndexEntry *e;
-
-        index= av_index_search_timestamp(st, target_ts);
-        e= &st->index_entries[index];
-
-        if(e->timestamp <= target_ts || e->pos == e->min_distance){
-            pos_min= e->pos;
-            ts_min= e->timestamp;
-#ifdef DEBUG_SEEK
-        av_log(s, AV_LOG_DEBUG, "unsing cached pos_min=0x%llx dts_min=%lld\n", 
-               pos_min,ts_min);
-#endif
-        }else{
-            assert(index==0);
-        }
-        index++;
-        if(index < st->nb_index_entries){
-            e= &st->index_entries[index];
-            assert(e->timestamp >= target_ts);
-            pos_max= e->pos;
-            ts_max= e->timestamp;
-            pos_limit= pos_max - e->min_distance;
-#ifdef DEBUG_SEEK
-        av_log(s, AV_LOG_DEBUG, "unsing cached pos_max=0x%llx pos_limit=0x%llx dts_max=%lld\n", 
-               pos_max,pos_limit, ts_max);
-#endif
-        }
-    }
-
-    if(ts_min == AV_NOPTS_VALUE){
-        pos_min = 0;
-        ts_min = read_timestamp(s, stream_index, &pos_min, INT64_MAX);
-        if (ts_min == AV_NOPTS_VALUE)
-            return -1;
-    }
-
-    if(ts_max == AV_NOPTS_VALUE){
-        int step= 1024;
-        pos_max = url_filesize(url_fileno(&s->pb)) - 1;
-        do{
-            pos_max -= step;
-            ts_max = read_timestamp(s, stream_index, &pos_max, pos_max + step);
-            step += step;
-        }while(ts_max == AV_NOPTS_VALUE && pos_max >= step);
-        if (ts_max == AV_NOPTS_VALUE)
-            return -1;
-        
-        for(;;){
-            int64_t tmp_pos= pos_max + 1;
-            int64_t tmp_ts= read_timestamp(s, stream_index, &tmp_pos, INT64_MAX);
-            if(tmp_ts == AV_NOPTS_VALUE)
-                break;
-            ts_max= tmp_ts;
-            pos_max= tmp_pos;
-        }
-        pos_limit= pos_max;
-    }
+    int64_t pos;
+    int i;
 
-    no_change=0;
-    while (pos_min < pos_limit) {
-#ifdef DEBUG_SEEK
-        av_log(s, AV_LOG_DEBUG, "pos_min=0x%llx pos_max=0x%llx dts_min=%lld dts_max=%lld\n", 
-               pos_min, pos_max,
-               ts_min, ts_max);
-#endif
-        assert(pos_limit <= pos_max);
-
-        if(no_change==0){
-            int64_t approximate_keyframe_distance= pos_max - pos_limit;
-            // interpolate position (better than dichotomy)
-            pos = (int64_t)((double)(pos_max - pos_min) *
-                            (double)(target_ts - ts_min) /
-                            (double)(ts_max - ts_min)) + pos_min - approximate_keyframe_distance;
-        }else if(no_change==1){
-            // bisection, if interpolation failed to change min or max pos last time
-            pos = (pos_min + pos_limit)>>1;
-        }else{
-            // linear search if bisection failed, can only happen if there are very few or no keframes between min/max
-            pos=pos_min;
-        }
-        if(pos <= pos_min)
-            pos= pos_min + 1;
-        else if(pos > pos_limit)
-            pos= pos_limit;
-        start_pos= pos;
-
-        ts = read_timestamp(s, stream_index, &pos, INT64_MAX); //may pass pos_limit instead of -1
-        if(pos == pos_max)
-            no_change++;
-        else
-            no_change=0;
-#ifdef DEBUG_SEEK
-av_log(s, AV_LOG_DEBUG, "%Ld %Ld %Ld / %Ld %Ld %Ld target:%Ld limit:%Ld start:%Ld noc:%d\n", pos_min, pos, pos_max, ts_min, ts, ts_max, target_ts, pos_limit, start_pos, no_change);
-#endif
-        assert(ts != AV_NOPTS_VALUE);
-        if (target_ts < ts) {
-            pos_limit = start_pos - 1;
-            pos_max = pos;
-            ts_max = ts;
-        } else {
-            pos_min = pos;
-            ts_min = ts;
-            /* check if we are lucky */
-            if (target_ts == ts)
-                break;
-        }
-    }
-    
-    pos = pos_min;
-#ifdef DEBUG_SEEK
-    pos_min = pos;
-    ts_min = read_timestamp(s, stream_index, &pos_min, INT64_MAX);
-    pos_min++;
-    ts_max = read_timestamp(s, stream_index, &pos_min, INT64_MAX);
-    av_log(s, AV_LOG_DEBUG, "pos=0x%llx %lld<=%lld<=%lld\n", 
-           pos, ts_min, target_ts, ts_max);
-#endif
-    /* do the seek */
-    url_fseek(&s->pb, pos, SEEK_SET);
+    if(av_seek_frame_binary(s, stream_index, target_ts) < 0)
+        return -1;
 
     nut->written_packet_size= -1;
+    pos= url_ftell(&s->pb);
     for(i=0; i<s->nb_streams; i++)
         nut->stream[i].last_sync_pos= pos;
 
@@ -1513,6 +1377,7 @@ static AVInputFormat nut_iformat = {
     nut_read_packet,
     nut_read_close,
     nut_read_seek,
+    nut_read_timestamp,
     .extensions = "nut",
 };