Allow decoding forward instead of seeking.
authorTimothy B. Terriberry <tterribe@xiph.org>
Sun, 10 Feb 2013 04:40:16 +0000 (20:40 -0800)
committerTimothy B. Terriberry <tterribe@xiph.org>
Sun, 10 Feb 2013 04:54:56 +0000 (20:54 -0800)
This lets us seek forward by small amounts (currently less than
 90 ms) by decoding forward instead of actually seeking.
This is often a good idea, since we would have to decode at least
 80 ms of pre-roll anyway.
This optimization also handles the case of seeking to what is
 already the current position cheaply.

This became relatively easy after we dropped op_pcm_seek_page()
 from the public API.
However, because others may look to libopusfile's seeking code as a
 model, we've added an OP_SMALL_FOOTPRINT #define to cordon off
 some of these complex sections of code that are deeply specific to
 libopusfile's design, ancillary to the main seeking algorithm,
 and relatively unimportant to overall seeking performance.

src/opusfile.c

index 820254e..71d7ae0 100644 (file)
@@ -410,6 +410,9 @@ static opus_int64 op_get_last_page(OggOpusFile *_of,ogg_int64_t *_gp,
   OP_ASSERT(op_lookup_serialno(_serialno,_serialnos,_nserialnos));
   original_end=end=begin=_offset;
   _offset=-1;
+  /*We shouldn't have to initialize gp, but gcc is too dumb to figure out that
+     ret>=0 implies we entered the if(page_gp!=-1) block at least once.*/
+  gp=-1;
   chunk_size=OP_CHUNK_SIZE;
   do{
     int left_link;
@@ -423,7 +426,7 @@ static opus_int64 op_get_last_page(OggOpusFile *_of,ogg_int64_t *_gp,
       opus_int64   llret;
       ogg_uint32_t serialno;
       llret=op_get_next_page(_of,&og,end);
-      if(OP_UNLIKELY(llret<OP_FALSE))return (int)llret;
+      if(OP_UNLIKELY(llret<OP_FALSE))return llret;
       else if(llret==OP_FALSE)break;
       serialno=ogg_page_serialno(&og);
       if(serialno==_serialno){
@@ -778,7 +781,11 @@ static opus_int32 op_collect_audio_packets(OggOpusFile *_of,
     if(OP_UNLIKELY(ret<0)){
       /*We shouldn't get holes in the middle of pages.*/
       OP_ASSERT(op_count==0);
-      return OP_HOLE;
+      /*Set the return value and break out of the loop.
+        We want to make sure op_count gets set to 0, because we've ingested a
+         page, so any previously loaded packets are now invalid.*/
+      total_duration=OP_HOLE;
+      break;
     }
     _durations[op_count]=op_get_packet_duration(_of->op[op_count].packet,
      _of->op[op_count].bytes);
@@ -1369,7 +1376,15 @@ static int op_open_seekable2(OggOpusFile *_of){
   int               start_op_count;
   int               ret;
   /*We're partially open and have a first link header state in storage in _of.
-    Save off that stream state so we can come back to it.*/
+    Save off that stream state so we can come back to it.
+    It would be simpler to just dump all this state and seek back to
+     links[0].data_offset when we're done.
+    But we do the extra work to allow us to seek back to _exactly_ the same
+     stream position we're at now.
+    This allows, e.g., the HTTP backend to continue reading from the original
+     connection (if it's still available), instead of opening a new one.
+    This means we can open and start playing a normal Opus file with a single
+     link and reasonable packet sizes using only two HTTP requests.*/
   start_op_count=_of->op_count;
   /*This is a bit too large to put on the stack unconditionally.*/
   op_start=(ogg_packet *)_ogg_malloc(sizeof(*op_start)*start_op_count);
@@ -2129,6 +2144,12 @@ static ogg_int64_t op_get_granulepos(const OggOpusFile *_of,
   Two minutes seems to be a good default.*/
 #define OP_CUR_TIME_THRESH (120*48*(opus_int32)1000)
 
+/*Note: The OP_SMALL_FOOTPRINT #define doesn't (currently) save much code size,
+   but it's meant to serve as documentation for portions of the seeking
+   algorithm that are purely optional, to aid others learning from/porting this
+   code to other contexts.*/
+/*#define OP_SMALL_FOOTPRINT (1)*/
+
 /*Search within link _li for the page with the highest granule position
    preceding (or equal to) _target_gp.
   There is a danger here: missing pages or incorrect frame number information
@@ -2145,18 +2166,18 @@ static int op_pcm_seek_page(OggOpusFile *_of,
   ogg_int64_t   diff;
   ogg_uint32_t  serialno;
   opus_int32    pre_skip;
-  opus_int32    cur_discard_count;
   opus_int64    begin;
   opus_int64    end;
   opus_int64    boundary;
   opus_int64    best;
   opus_int64    page_offset;
-  opus_int64    d[3];
+  opus_int64    d0;
+  opus_int64    d1;
+  opus_int64    d2;
   int           force_bisect;
   int           ret;
   _of->bytes_tracked=0;
   _of->samples_tracked=0;
-  /*New search algorithm by HB (Nicholas Vinen).*/
   link=_of->links+_li;
   best_gp=pcm_start=link->pcm_start;
   pcm_end=link->pcm_end;
@@ -2175,6 +2196,7 @@ static int op_pcm_seek_page(OggOpusFile *_of,
   if(op_granpos_cmp(_target_gp,pcm_pre_skip)<0)end=boundary=begin;
   else{
     end=boundary=link->end_offset;
+#if !defined(OP_SMALL_FOOTPRINT)
     /*If we were decoding from this link, we can narrow the range a bit.*/
     if(_li==_of->cur_link&&_of->ready_state>=OP_INITSET){
       opus_int64 offset;
@@ -2188,15 +2210,15 @@ static int op_pcm_seek_page(OggOpusFile *_of,
       offset=_of->offset;
       if(op_count>0&&OP_LIKELY(offset<=end)){
         ogg_int64_t gp;
-        gp=_of->op[op_count-1].granulepos;
         /*Make sure the timestamp is valid.
           The granule position might be -1 if we collected the packets from a
            page without a granule position after reporting a hole.*/
+        gp=_of->op[op_count-1].granulepos;
         if(OP_LIKELY(gp!=-1)&&OP_LIKELY(op_granpos_cmp(pcm_start,gp)<0)
          &&OP_LIKELY(op_granpos_cmp(pcm_end,gp)>0)){
           OP_ALWAYS_TRUE(!op_granpos_diff(&diff,gp,_target_gp));
           /*We only actually use the current time if either
-            a) We can cut off more than half the range, or
+            a) We can cut off at least half the range, or
             b) We're seeking sufficiently close to the current position that
                 it's likely to be informative.
             Otherwise it appears using the whole link range to estimate the
@@ -2208,18 +2230,44 @@ static int op_pcm_seek_page(OggOpusFile *_of,
               best_gp=pcm_start=gp;
             }
           }
-          else if(offset-begin<=end-begin>>1||diff<OP_CUR_TIME_THRESH){
-            /*We really want the page start here, but this will do.*/
-            end=boundary=offset;
-            pcm_end=gp;
+          else{
+            ogg_int64_t prev_page_gp;
+            /*We might get lucky and already have the packet with the target
+               buffered.
+              Worth checking.
+              For very small files (with all of the data in a single page,
+               generally 1 second or less), we can loop them continuously
+               without seeking at all.*/
+            OP_ALWAYS_TRUE(!op_granpos_add(&prev_page_gp,_of->op[0].granulepos,
+             op_get_packet_duration(_of->op[0].packet,_of->op[0].bytes)));
+            if(op_granpos_cmp(prev_page_gp,_target_gp)<=0){
+              /*Don't call op_decode_clear(), because it will dump our
+                 packets.*/
+              _of->op_pos=0;
+              _of->od_buffer_size=0;
+              _of->prev_packet_gp=prev_page_gp;
+              _of->ready_state=OP_STREAMSET;
+              return op_make_decode_ready(_of);
+            }
+            /*No such luck.
+              Check if we can cut off at least half the range, though.*/
+            if(offset-begin<=end-begin>>1||diff<OP_CUR_TIME_THRESH){
+              /*We really want the page start here, but this will do.*/
+              end=boundary=offset;
+              pcm_end=gp;
+            }
           }
         }
       }
     }
+#endif
   }
+  /*This code was originally based on the "new search algorithm by HB (Nicholas
+     Vinen)" from libvorbisfile.
+    It has been modified substantially since.*/
   op_decode_clear(_of);
   /*Initialize the interval size history.*/
-  d[2]=d[1]=d[0]=end-begin;
+  d2=d1=d0=end-begin;
   force_bisect=0;
   while(begin<end){
     opus_int64 bisect;
@@ -2228,9 +2276,9 @@ static int op_pcm_seek_page(OggOpusFile *_of,
     if(end-begin<OP_CHUNK_SIZE)bisect=begin;
     else{
       /*Update the interval size history.*/
-      d[0]=d[1]>>1;
-      d[1]=d[2]>>1;
-      d[2]=end-begin>>1;
+      d0=d1>>1;
+      d1=d2>>1;
+      d2=end-begin>>1;
       if(force_bisect)bisect=begin+(end-begin>>1);
       else{
         ogg_int64_t diff2;
@@ -2308,7 +2356,7 @@ static int op_pcm_seek_page(OggOpusFile *_of,
             boundary=next_boundary;
             /*If we're not making much progress shrinking the interval size,
                start forcing straight bisection to limit the worst case.*/
-            force_bisect=end-begin>d[0]*2;
+            force_bisect=end-begin>d0*2;
             /*Don't let pcm_end get out of range!
               That could happen with an invalid timestamp.*/
             if(OP_LIKELY(op_granpos_cmp(pcm_end,gp)>0)
@@ -2322,7 +2370,8 @@ static int op_pcm_seek_page(OggOpusFile *_of,
     }
   }
   /*Found our page.
-    Seek right after it and update prev_packet_gp and cur_discard_count.
+    Seek to the end of it and update prev_packet_gp.
+    Our caller will set cur_discard_count.
     This is an easier case than op_raw_seek(), as we don't need to keep any
      packets from the page we found.*/
   /*Seek, if necessary.*/
@@ -2331,21 +2380,10 @@ static int op_pcm_seek_page(OggOpusFile *_of,
     ret=op_seek_helper(_of,best);
     if(OP_UNLIKELY(ret<0))return ret;
   }
-  /*By default, discard 80 ms of data after a seek, unless we seek
-     into the pre-skip region.*/
-  cur_discard_count=80*48;
-  OP_ALWAYS_TRUE(!op_granpos_diff(&diff,best_gp,pcm_start));
-  OP_ASSERT(diff>=0);
-  /*If we start at the beginning of the pre-skip region, or we're at least
-     80 ms from the end of the pre-skip region, we discard to the end of the
-     pre-skip region.
-    Otherwise, we still use the 80 ms default, which will discard past the end
-     of the pre-skip region.*/
-  if(diff<=OP_MAX(0,pre_skip-80*48))cur_discard_count=pre_skip-(int)diff;
+  OP_ASSERT(op_granpos_cmp(best_gp,pcm_start)>=0);
   _of->cur_link=_li;
   _of->ready_state=OP_STREAMSET;
   _of->prev_packet_gp=best_gp;
-  _of->cur_discard_count=cur_discard_count;
   ogg_stream_reset_serialno(&_of->os,serialno);
   ret=op_fetch_and_process_page(_of,page_offset<0?NULL:&og,page_offset,1,0,1);
   if(OP_UNLIKELY(ret<=0))return OP_EBADLINK;
@@ -2372,11 +2410,40 @@ int op_pcm_seek(OggOpusFile *_of,ogg_int64_t _pcm_offset){
   if(OP_UNLIKELY(_pcm_offset<0))return OP_EINVAL;
   target_gp=op_get_granulepos(_of,_pcm_offset,&li);
   if(OP_UNLIKELY(target_gp==-1))return OP_EINVAL;
-  ret=op_pcm_seek_page(_of,target_gp,li);
-  /*Now skip samples until we actually get to our target.*/
   link=_of->links+li;
   pcm_start=link->pcm_start;
   OP_ALWAYS_TRUE(!op_granpos_diff(&_pcm_offset,target_gp,pcm_start));
+#if !defined(OP_SMALL_FOOTPRINT)
+  /*For small (90 ms or less) forward seeks within the same link, just decode
+     forward.
+    This also optimizes the case of seeking to the current position.*/
+  if(li==_of->cur_link&&_of->ready_state>=OP_INITSET){
+    ogg_int64_t gp;
+    gp=_of->prev_packet_gp;
+    if(OP_LIKELY(gp!=-1)){
+      int nbuffered;
+      nbuffered=OP_MAX(_of->od_buffer_size-_of->od_buffer_pos,0);
+      OP_ALWAYS_TRUE(!op_granpos_add(&gp,gp,-nbuffered));
+      /*We do _not_ add cur_discard_count to gp.
+        Otherwise the total amount to discard could grow without bound, and it
+         would be better just to do a full seek.*/
+      if(OP_LIKELY(!op_granpos_diff(&diff,gp,pcm_start))){
+        ogg_int64_t discard_count;
+        discard_count=_pcm_offset-diff;
+        /*We use a threshold of 90 ms instead of 80, since 80 ms is the
+           _minimum_ we would have discarded after a full seek.
+          Assuming 20 ms frames (the default), we'd discard 90 ms on average.*/
+        if(discard_count>=0&&OP_UNLIKELY(discard_count<90*48)){
+          _of->cur_discard_count=(opus_int32)discard_count;
+          return 0;
+        }
+      }
+    }
+  }
+#endif
+  ret=op_pcm_seek_page(_of,target_gp,li);
+  if(OP_UNLIKELY(ret<0))return ret;
+  /*Now skip samples until we actually get to our target.*/
   /*Figure out where we should skip to.*/
   if(_pcm_offset<=link->head.pre_skip)skip=0;
   else skip=OP_MAX(_pcm_offset-80*48,0);