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

[Michael Niedermayer]

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


> 
> * 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?

[...]
-- 
Michael