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

[Michael Niedermayer]

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

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

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
* updating the timetamps in the syncpoints to match the farthest rightward
keyframe of any stream require seekig back (i think this one wasnt proposed)

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

comments?


-- 
Michael