[theora] Indexless interpolation search seeking code

[xiphmont at xiph.org]

On Tue, Apr 27, 2010 at 1:37 PM, Gregory Maxwell <gmaxwell at gmail.com> wrote:
> On Sun, Apr 25, 2010 at 11:57 PM, Chris Pearce <chris at pearce.org.nz> wrote:
>> 5-7 is pretty typical in my experience, it sometimes gets worse,
>> particularly for videos which have large or irregular sized keyframes,
>> where it's hard to get an accurate bitrate estimation on your
>> bissections. I asked if I could see the seek code to see if there was
>> some trick I wasn't doing. :)
>>
>> I agree that with non-exact seeking, or with low latency storage,
>> indexes aren't as necessary.
>
>
> "The Vorbis source distribution includes an example program called
> 'seeking_example' that does a stress-test of 5000 seeks of different
> kinds within an Ogg file. Testing here with SVN r17178, 5000 seeks
> within a 10GB Ogg file constructed by concatenating 22 short Ogg
> videos of varying bitrates together results in 17459 actual seek
> system calls. This yields a result of just under 3.5 real seeks per
> Ogg seek request when doing exact positioning within an Ogg file."

I have to admit in the process of performing that test I noticed that
seeking had been partially broken in vorbisfile last summer and
testing hadn't noticed.  Also, the seek algorithm as implemented by HB
had screwed up implementing the end-search short-circuit case and had
been doing 3X too many seeks all these years :-(

Details.... so important!

Monty