changeset 355:46029c682234 libavformat

seeking stuff adaptively change middle position selection algo for seeking, this avoids some ugly worstcases of the interpolated variant avoid backward search for mpeg where possible, its 17 times slower then forward according to my benchmark
author michael
date Sat, 17 Jan 2004 20:26:44 +0000
parents 6770ca07abe2
children 72c7cf2f3a7a
files asf.c mpeg.c
diffstat 2 files changed, 67 insertions(+), 50 deletions(-) [+]
line wrap: on
line diff
--- a/asf.c	Sat Jan 17 18:06:52 2004 +0000
+++ b/asf.c	Sat Jan 17 20:26:44 2004 +0000
@@ -1401,6 +1401,7 @@
     AVStream *st;
     int64_t pos;
     int64_t pos_min, pos_max, pts_min, pts_max, cur_pts, pos_limit;
+    int no_change;
     
     if (stream_index == -1)
         stream_index= av_find_default_stream_index(s);
@@ -1454,14 +1455,24 @@
         pos_limit= pos_max;
     } 
 
+    no_change=0;
     while (pos_min < pos_limit) {
         int64_t start_pos;
         assert(pos_limit <= pos_max);
 
-        // interpolate position (better than dichotomy)
-        pos = (int64_t)((double)(pos_limit - pos_min) *
-                        (double)(pts - pts_min) /
-                        (double)(pts_max - pts_min)) + pos_min;
+        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)(pts - pts_min) /
+                            (double)(pts_max - pts_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 keyframes between min/max
+            pos=pos_min;
+        }
         if(pos <= pos_min)
             pos= pos_min + 1;
         else if(pos > pos_limit)
@@ -1470,13 +1481,16 @@
 
         // read the next timestamp 
     	cur_pts = asf_read_pts(s, &pos, stream_index);    
+        if(pos == pos_max)
+            no_change++;
+        else
+            no_change=0;
+
 #ifdef DEBUG_SEEK
 printf("%Ld %Ld %Ld / %Ld %Ld %Ld target:%Ld limit:%Ld start:%Ld\n", pos_min, pos, pos_max, pts_min, cur_pts, pts_max, pts, pos_limit, start_pos);
 #endif
-        if (cur_pts == AV_NOPTS_VALUE) {
-            printf("NOPTS\n");
-            return -1;
-        } else if (pts < cur_pts) {
+        assert (cur_pts != AV_NOPTS_VALUE);
+        if (pts < cur_pts) {
             pos_limit = start_pos - 1;
             pos_max = pos;
             pts_max = cur_pts;
--- a/mpeg.c	Sat Jan 17 18:06:52 2004 +0000
+++ b/mpeg.c	Sat Jan 17 20:26:44 2004 +0000
@@ -1037,9 +1037,9 @@
 static int mpegps_read_seek(AVFormatContext *s, 
                             int stream_index, int64_t timestamp)
 {
-    int64_t pos_min, pos_max, pos;
+    int64_t pos_min, pos_max, pos, pos_limit;
     int64_t dts_min, dts_max, dts;
-    int index;
+    int index, no_change;
     AVStream *st;
 
     timestamp = (timestamp * 90000) / AV_TIME_BASE;
@@ -1057,6 +1057,7 @@
     
     dts_max=
     dts_min= AV_NOPTS_VALUE;
+    pos_limit= -1; //gcc falsely says it may be uninitalized
 
     st= s->streams[stream_index];
     if(st->index_entries){
@@ -1080,6 +1081,7 @@
             assert(e->timestamp >= timestamp);
             pos_max= e->pos;
             dts_max= e->timestamp;
+            pos_limit= pos_max - e->min_distance;
 #ifdef DEBUG_SEEK
         printf("unsing cached pos_max=0x%llx dts_max=%0.3f\n", 
                pos_max,dts_max / 90000.0);
@@ -1099,61 +1101,62 @@
     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_limit= pos_max;
     }
-    
-    while (pos_min <= pos_max) {
+
+    no_change=0;
+    while (pos_min < pos_limit) {
 #ifdef DEBUG_SEEK
         printf("pos_min=0x%llx pos_max=0x%llx dts_min=%0.3f dts_max=%0.3f\n", 
                pos_min, pos_max,
                dts_min / 90000.0, dts_max / 90000.0);
 #endif
-        if (timestamp <= dts_min) {
-            pos = pos_min;
-            goto found;
-        } else if (timestamp >= dts_max) {
-            pos = pos_max;
-            goto found;
-        } else {
-            /* interpolate position (better than dichotomy) */
-            pos = (int64_t)((double)(pos_max - pos_min) * 
+        int64_t start_pos;
+        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)(timestamp - dts_min) /
-                            (double)(dts_max - dts_min)) + pos_min;
+                            (double)(dts_max - dts_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;
+
+        // read the next timestamp 
+    	dts = mpegps_read_dts(s, stream_index, &pos, 1);
+        if(pos == pos_max)
+            no_change++;
+        else
+            no_change=0;
 #ifdef DEBUG_SEEK
-        printf("pos=0x%llx\n", pos);
+printf("%Ld %Ld %Ld / %Ld %Ld %Ld target:%Ld limit:%Ld start:%Ld noc:%d\n", pos_min, pos, pos_max, dts_min, dts, dts_max, timestamp, pos_limit, start_pos, no_change);
 #endif
-        /* read the next timestamp */
-        dts = mpegps_read_dts(s, stream_index, &pos, 1);
-        /* check if we are lucky */
-        if (dts == AV_NOPTS_VALUE) {
-            /* should never happen */
-            pos = pos_min;
-            goto found;
-        } else if (timestamp == dts) {
-            goto found;
-        } else if (timestamp < dts) {
+        assert(dts != AV_NOPTS_VALUE);
+        if (timestamp < dts) {
+            pos_limit = start_pos - 1;
             pos_max = pos;
-            dts_max = mpegps_read_dts(s, stream_index, &pos_max, 0);
-            if (dts_max == AV_NOPTS_VALUE) {
-                /* should never happen */
-                break;
-            } else if (timestamp >= dts_max) {
-                pos = pos_max;
-                goto found;
-            }
+            dts_max = dts;
         } else {
-            pos_min = pos + 1;
-            dts_min = mpegps_read_dts(s, stream_index, &pos_min, 1);
-            if (dts_min == AV_NOPTS_VALUE) {
-                /* should never happen */
-                goto found;
-            } else if (timestamp <= dts_min) {
-                goto found;
-            }
+            pos_min = pos;
+            dts_min = dts;
+            /* check if we are lucky */
+            if (timestamp == dts)
+                break;
         }
     }
+    
     pos = pos_min;
- found:
 #ifdef DEBUG_SEEK
     pos_min = pos;
     dts_min = mpegps_read_dts(s, stream_index, &pos_min, 1);