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

[Michael Niedermayer]

Hi

On Tuesday 05 October 2004 00:15, D Richard Felker III wrote:
> 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.

great, just dont forget to consider that
1. seeking of damaged streams should be possible without inconsistencies
2. we want to cache keyframe positions to speed future seeking up

both are fine with the current and past spec, and fully implemented in 
libavformat/nut.c 

anyway i will not contribute to current nut any further, i havnt decided yet 
if i will fork it and reverse many things or leave nut development and work 
on other things, but we clearly have very different opinions about how things 
should be done, and many of your ideas simply lead to problems which are 
quite complicated to workaround and iam the one who has to write 98% of these 
workarounds, maybe i just dont understand the reasons behind some of your 
suggestions but i simply dont see the need to redesign well working code 
several times
the original nut spec with subpackets had problems, like buffering 
requirements and such, a redesign was needed no doubt
alex`s info packet change made storing arbitrary info data impossible and 
complicated the design
the short startcodes while cute serve no purpose at all
the syncpoints instead of keyframe based indexes create a heap of problems 
which we havnt found solutions for yet
....

but please dont missunderstand me, if i do fork nut iam not doing it with the 
goal to finish it alone, instead its supposed to be some experimental variant 
which i can freely change as i like without long discussions and which we 
will hopefully merge back at the end

[...]
-- 
Michael

"I do not agree with what you have to say, but I'll defend to the death your
right to say it." -- Voltaire