[MPlayer-dev-eng] nut seeking without an index

[Rich Felker]

On Thu, Sep 08, 2005 at 10:34:40AM +0200, Michael Niedermayer wrote:
> > > > maybe richs idea with backward pointers at sync points can be amended a
> > > > little to solve the issue:
> > > > store a single pointer at every syncpoint which points back to a point so 
> > > > that every stream has at least 1 keyframe between the point and the current
> > > > sync point
> > > 
> > > This could be one hugeass useless backward pointer in the presence of
> > > subtitles. I know one anime movie (Tenshi no Tamago) with only about
> > > 10 lines of dialogue over 2 hours...
> > 
> > Unfortunately I can't come up with anything reasonable except either
> > having a backward pointer for each stream, or treating subtitle and
> > info streams separately and excluding them from the backpointer rules.
> > However I think the latter choice is bad, since it may be desirable to
> > seek according to an info stream, especially if the info stream
> > represents song/chapter/etc boundaries.
> 
> i still think the single pointer is enough, a file which stores keyframes
> once every 2 hours, can only be seeked to at 2hour granularity and yes

But obviously this isn't true at all for subtitle streams.
The key condition is that you only need to find a keyframe for stream
N if there will be another non-key frame for stream N before the
following keyframe for stream N.

Of course a lazy player that doesn't mind missing some data after a
seek doesn't even care, and can just disable all the streams except
the one on the basis of which it did the seek until a future keyframe
is found.

> you can by knowing that there are no non-keyframes in between skip
> over it in principle

Yes, this is the fundamental problem. When seeking to a time T, you
want to know not the prior keyframe for each stream, but rather the
earliest packet on which any subsequent packets in the stream can
depend. The prior keyframe gives a safe lower bound for the earliest
packet on which anything can depend.

> but you dont know that, not even with an index

An index could store a bit for each entry that tells whether or not
there have been any non-key frames between the last indexed keyframe
and the current indexed keyframe.

Similarly, if this bit and a separate backward pointer for each stream
is stored at each syncpoint, there is a binary search algorithm that
will find the correct place to start each frame.

> i rather think that we should do something about large gaps
> then find some hackisch way to support it

I don't like storing backward pointers for each frame. It's way too
much overhead. Of course our recommended max_distance is also
extremely small (basically it says put a syncpoint after every 2 or 3
frames, at normal bitrates) so perhaps we could compensate by
increasing it.

I'd rather find a better solution, though, like you say.

> > Personally I'd still be interested in seeing if there's any way we can
> > do a sane distributed index....
> 
> if we can drop the 1pass sequential writing requirement then this shouldnt
> be difficult,

IMO not acceptable. A non-pipable format sucks, and so does a format
that's not previewable while encoding. :(

> otherwise its complicated and fragile

I still think it can be done, but you're right that it may be too
fragile. Of course perfectly correct seeking without linear search is
very difficult anyway in the presence of corruption. Error recovery
might result in skipping some frames that could have been decoded if
the info to easily find them is missing.

Rich