[theora] Indexing Ogg files for faster seeking

[Chris Pearce]

On 27/01/2010 5:59 p.m., Benjamin M. Schwartz wrote:
> Chris Pearce wrote:
>    
>> What's the alternative? Specify that the index must exactly index every
>> keyframe? That denies authors the ability tune their indexes.
>>      
> I see two alternatives:
> 0. Remove the concept of validity/verifiability.
>    

Unacceptable. We must be able to tell if the indexes out tools are 
outputting are correct. We need some concept of validity.

> 1. Make "valid" represent something closer to "useful".  My best
> suggestion is that the index header include b_max, the maximum number of
> bytes you might have to skip to get from the nearest upstream index point
> to your target seek point (i.e. the page start).  When b_max is zero, the
> index is lossless and complete (every page containing a keyframe is
> indexed exactly).  An index header is invalid if there is some potential
> target page start that cannot be reached without skipping more than b_max
> bytes.
>    

So with b_max as 0, your proposed scheme is equivalent to our current 
approach. Good to hear you consider our current indexing scheme 
"something closer to useful".
>
>> I'm not an expert on Dirac. Can it be the case with Dirac that all the
>> data for a later keyframe lies before all the data for an earlier keyframe?
>>      
> My head hurts trying to work out the behavior in the case where time is
> not monotonic with granpos.  Things should get even more interesting with
> rolling intra.
>    

Ultimately, there's one offset where you must start decoding from in 
order to playback from the keyframe onwards. That's what's indexed.

>>>   Perhaps. Could you provide a spec for the index packet so we can see how
>>> this would work?
>>>        
> I will be happy to draw up something clearer than this e-mail.
>    

You'll need numbers and sample code to back up any claims. My primary 
concern here is that any such approach would add considerable 
implementation difficulty for little gain. I have little desire to 
rework the indexers again. Dropping a few keypoints from the index isn't 
a terrible trade-off in my opinion. Better off keeping it simple.

We've spent plenty of time on the index already, it's time we locked it 
down and got the ball rolling on this.


Chris P.