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

[Rich Felker]

On Wed, Sep 07, 2005 at 09:54:27PM +0200, Michael Niedermayer wrote:
> Hi
> 
> as we know exact seeking without an index isnt easy, thats caused by the
> various goals (no (large) buffering anywhere, no seeking back during 
> encoding, no index ...)

IMO the "no seeking back during encoding" isn't a major issue to
efficient non-index seeking. That is to say, I believe that most/all
good solutions to non-index seeking can be implemented in a way that
doesn't require seeking to write the nut file, with a little bit of
cleverness. But this is just a hunch. :)

> let me first describe the issue again
> we have several streams with possibly large keyframe distances, 10sec is
> common for mpeg4 in avi, dts reordering and gaps worsen it a little too
> but IMHO the keyframe distance is the bigger factor
> now when we do a binary search we can easily find any sync point for
> a given direction and timestamp in O(sync_distance * log filesize)
> but then we need to search backward to find a keyframe for each stream
> which needs O(key_distance) thats bad as it can be expensive, several 
> seconds is not unrealistic on slow media

Agree, it's an issue we need to address.

> various solutions have been proposed by me and rich but none was really 
> liked by either of us
> * backward pointers at syncpoints, one pointer for each stream has high
> overhead in some cases

> * various mix the index into the rest of the file methods simply have too
> high complexity

They also have the disadvantage that it's slow to load the whole index
at startup, especially if seeking is expensive (and this is when
having an index is most important). Maybe it would be ok with a full
index at EOF too though!

> * updating the timetamps in the syncpoints to match the farthest rightward
> keyframe of any stream require seekig back (i think this one wasnt proposed)

Could you explain this better? It sounds like it might be very good,
but I don't really understand what you mean.

> 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...

> with that seeking is a matter of finding a syncpoint before the time we want
> to seek to and then following the pointer backward
> generating these backward pointers is quite easy too, we just need to keep 
> track of where the most recent keyframe for each stream and the previous
> syncpoint is

I'm confused again. But you may be onto something, so please explain!

> comments?

Glad you're thinking about this. :))

Rich