ref: 3cc27477538da445397eada4f609992165f4906b
parent: b4cdfcc760394cec9a33647b7acd272c91397ccc
author: Timothy B. Terriberry <[email protected]>
date: Sat Feb 9 15:40:16 EST 2013
Allow decoding forward instead of seeking. 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.
--- a/src/opusfile.c
+++ b/src/opusfile.c
@@ -410,6 +410,9 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
}
}
/*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 @@
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 @@
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);