[MPlayer-dev-eng] Nut startcodes

[Michael Niedermayer]

Hi

On Wednesday 28 April 2004 12:26, Ville Saari wrote:
> On Tue, Apr 27, 2004 at 01:15:03PM +0200, Michael Niedermayer wrote:
> > > It might be useful for the specification to require, that every stream
> > > must have at least one keyframe between any two startcodes. This would
> > > ensure that you never need to start more than two startcodes before X.
> >
> > that requirement has sideeffects, like causing very few startcodes, which
> > is problematic for seeking & error recovery
>
> The seeking can't make use of any more startcodes than there are keyframes
> in the most sparsely keyframed stream.
>
> I there are excess startcodes, then the frame-accurate seeking becomes
> harder. Starting from one startcode, finding that it leads past the seek
> point without keyframe and trying again form the previous startcode is
> O(N^2). Keeping startcodes rare keeps N small.
nonsense

the seeking time increases with the distance of the startcodes! so 1/2 as many 
startcodes and seeking will need twice as long, and u NEVER need O(n^2), its 
just O(log n) with a larger constant

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

do a binary search, using the following:
    for pos x search backward to the previous startcode (this may be
    implemented by searching through blocks in forward direction)
    follow pointer chain forward until we hit a keyframe which is after x
    return its position and timestamp

the complexity of the first step is half the average startcode distance, the 
complexity of the second step is half the average number of frames between 
keyframes, both are constant relative to the filesize -> O(log n)

>
> Another approach would be to store the max keyframe distance in the stream
> header. 
not possible, the muxer does not and cannot know this, it would require to 
scan through the whole input file for stream copy

[...]

-- 
Michael
level[i]= get_vlc(); i+=get_vlc();		(violates patent EP0266049)
median(mv[y-1][x], mv[y][x-1], mv[y+1][x+1]);	(violates patent #5,905,535)
buf[i]= qp - buf[i-1];				(violates patent #?)
for more examples, see http://mplayerhq.hu/~michael/patent.html
stop it, see http://petition.eurolinux.org & http://petition.ffii.org/eubsa/en