[MPlayer-dev-eng] a few nut suggestions [seeking algorithm]

[D Richard Felker III]

On Mon, Oct 04, 2004 at 01:48:18PM +0200, Michael Niedermayer wrote:
> [...]
> > anyway, the keyframe search algorithm basically goes like this, iirc:
> > 1. seek to a syncpoint (index O(1) or binary search O(n log n))
> > 2. scan for keyframe (linear search O(keyint))
> 
> no, this is wrong, it simply wont work, its
> 
> find_prev{ search for the previous sync code linearly or by index }
> find_next{ follow and parse all framecodes until a keyframe after the 
> requested position is found }
> 2. do a binary search using {find_prev;find_next}

hmm, i've been thinking about it, and i think the seek algorithms are
as follows:

A. to seek to the next keyframe following a given timestamp (standard
forward seek):

1. use binary search or index to find the closest syncpoint before the
   given timestamp.
2. linear search forward until a keyframe is found and the timestamp
   of the keyframe is >= the given timestamp.

B. to seek to the previous keyframe before a given timestamp (standard
backwards seek):

1. use binary search or index to find the closest syncpoint after the
   given timestamp.
2. linear search backwards until a keyframe is found and the timestamp
   of the keyframe is <= the given timestamp.

but B.2 is actually more complicated since walking the file backwards
is nontrivial. you actually have to linear search backwards for a
syncpoint (or use the index), then linear search forward for
keyframes, repeating this process for every pair of syncpoints until
you find a keyframe. it's not particularly slow, but it is fairly
complex and requires a little more seeking that what might be desired.

so as i see it, case A is really trivial and has no problem. case B is
something of a pain. what i'd like is a solution to make case B
trivial too, without any significant increase in overhead and without
putting arbitrary rules in the spec that are dependent on the behavior
of present-day codecs or particular time scales.

rich