[MPlayer-dev-eng] Nut startcodes

[D Richard Felker III]

On Thu, Apr 29, 2004 at 08:28:23PM +0300, Ville Saari wrote:
> On Thu, Apr 29, 2004 at 02:40:20AM +0200, Michael Niedermayer wrote:
> 
> > ok, heres the explanation on how this is possible, its not easy unless we 
> > restrict ourselfs to seeking to frames with an immediatly preceeding 
> > startcode, in which case it would be easy ...
> 
> That requires an assumption that there is only one stream or that all
> the streams have their keyframe positions synchronized. In more general
> case only one of the streams might have a keyframe immediately after the
> startcode and all the other streams have to be decoded starting from
> their last keyframes. That keyframe has to be located somehow.
> 
> If there can be an arbitrary number of startcodes between the seek
> position and the last keyframe before the seek position, then finding
> the keyframes is tricky.
> 
> You might want to optimize the amount of seeks on typical case by
> starting form the second last startcode and then start decoding each
> stream as the keyframes are met, but then in the worst case you have
> to re-try multiple times from earlier startcodes and re-decode. That's
> O(n^2) if you try all the startcodes (can be made O(n*log(n)) if the skips
> backwards are progressively increased).

No, there is never anything O(n^2). This is total nonsense. The
absolute worst bound is ALWAYS O(n) since you can just start at the
beginning of the file and search for the time you want. But this is
stupid too. Binary search is O(log n)!!

BTW do you know what binary search means??

Rich