[MPlayer-dev-eng] NUT (informal) proposal, based on discussions

[Rich Felker]

On Wed, Jan 18, 2006 at 12:44:02AM +0100, Michael Niedermayer wrote:
> Hi
> 
> On Tue, Jan 17, 2006 at 05:59:23PM -0500, Rich Felker wrote:
> [...]
> > Without index:
> > 
> > 1. Binary search for the latest syncpoint with timestamp less than the
> >    requested PTS.
> > 
> > 2. Linear search forward until next syncpoint (bounded by
> >    max_distance). If a keyframe is found for each [active] stream with
> >    PTS less than the target PTS, you are done searching.
> > 
> > 3. If any [active] stream is missing a keyframe when you reach the
> >    next syncpoint, use the back_ptr values stored in this syncpoint
> >    (at the end of the search range) to seek back and linear search for
> >    the missing keyframes (bounded by max_distance).
> > 
> > Example with out-of-order frames, provided by Oded...sort of a
> > worst-case thing:
> > 
> > S1 K2 .....several_megs_no_K..... K15 S13 ...no_K_or_S... S24
> > 
> > * Trying to seek to timestamp 14. Should get K15.
> 
> hmm shouldnt that be timestamp 16? otherwise a keyframe at ts=15 seems
> wrong ideal target ...

oops yeah, sorry. i meant the right thing, just wrote it wrong.. :)

> > * Binary search will put you at S13. S13's back_ptr points all the way
> >   back to S1, which is incorrect.
> > 
> > * Linear search S13 to S24. Keyframe not found.
> > 
> > * Jump back to S24's back_ptr. This will (necessarily) point to K15.
> > 
> > * Win!
> > 
> > The main disadvantage of this method is that it cannot guarantee that
> > you will not perform an additional media seek after the binary search.
> > But just like the index case, I see no way to guarantee this without
> > full per-stream pts which would be very large at the syncpoint level
> > (since you can't code them relative to previous syncpoint).
> 
> what about
> 
> S1 K2 .....several_megs_no_K..... K15 S13 K17 ...no_K_or_S... S24
> 
> * Trying to seek to timestamp 16. Should get K15.
> * Binary search will put you at S13. S13's back_ptr points all the way
>   back to S1, which is not optimal.
> * Linear search S13 to S24. K17 found but thats after ts=16
> * Jump back to S24's back_ptr. This points to K17/S13 again not helpfull
> 
> -> K15 not found, or did i violate some rule?

yes, there are problems we've been discussing on irc too. some of the
problems have a fix by changing the definition of the back_ptr
appropriately, but i don't know if they all do. i'm still
investigating. will let you know when there's an update, unless you
come up with a brilliant idea first. :)

rich