[MPlayer-dev-eng] Lots of stuff for NUT

[Michael Niedermayer]

Hi

On Tue, Jan 03, 2006 at 12:00:53AM -0500, Rich Felker wrote:
> On Tue, Jan 03, 2006 at 05:27:31AM +0100, Michael Niedermayer wrote:
> > > > my claim is that your "solution" does not avoid linear searching that region
> > > > you just dont realize it, ill try to show this again, lets assume we are
> > > > "interrested" in all streams, i hope you will agree that in that case there
> > > > is no difference between 1 back pointer and per stream back pointers? now
> > > > if there is no difference we will need to search that region too ...
> > > 
> > > Search what region? Only the max_distance following the syncpoint
> > > which backptr points to, not the whole span between keyframes. This is
> > > the difference in 32k and 1-10 megs.
> > 
> > NO you MUST search the 1-10megs! nothing will avoid this you can have 
> > complete knowlegde of all keyframes its still needed
> 
> No, I'll outline the algorithm right here, allowing myself to make
> additional assumptions like no out-of-order frames and perfect
> timestamps just because we haven't finished working out how it works
> in more complicated real-world situations. Here we go...
> 
> 1. Start at the closest syncpoint A prior to the desired timestamp.
> 
> 2. For each stream, this syncpoint contains a back_ptr pointing to the
>    latest syncpoint B before the most recent keyframe prior to the
>    syncpoint timestamp.
> 
> 3. For each stream there are two possibilities. Either the latest
>    keyframe before the desired pts is between the syncpoint A and the
>    desired pts (in which case the back_ptr can't know about it), or it
>    is within the max_distance bytes following syncpoint B.
> 
> 4. In order to start at the latest point such that all streams will
>    have keyframes before pts, simply choose the earliest of the
>    back_ptrs and then the latest keyframes before the next syncpoint
>    (if a stream has more than one). Exclude the streams which have a
>    keyframe between syncpoint A and requested pts when making this
>    choice of earliest back_ptr.
> 
> This last exclusion is what Oded has been worrying about, trying to
> make syncpoint-placing rules to ensure that it doesn't happen. He
> wants to avoid having to linear search this region before following
> the back_ptrs.

hmm, ok i think i see the problem now, i had the impression that we where
talking about something else :)

so the problem is:
0123456 7 8 9
KFFFFFF S K S

and we want to seek to ts 8 -> we will end at syncpoint for ts=7 and the
previous keyframe which wont bring us to the optimal keyframe but an earlier
one, thats something i never saw as a problem as i never wanted to be able
to seek to every keyframe if now you want to find the optimal keyframe you
would need to search the whole GOP ...

ok, heres an attempt to avoid the issue, iam using a single back ptr as
example, generalizing it to multiple should be trivial ...

1. keep track of the last written back pointer and the current (not written)
back ptr / update it every time a new keyframe is given to the muxer
2. if the difference between the written and the internal pointers is
larger then some threshold t then write a syncpoint with the internal
back pointer
(3. write more syncpoints to satisfy the other rules ...)

the above case should then look like

0012345688
KSFFFFFFKS

there is one problem with this, it assumes that all timestamps are in the
same timebase, if thats false theres a very small chance you might end a
keyframe earlier, for me thats not a serious enough issue though ...
if you are crazy enough its possible to store the single back ptr
timestamp in the timebase of the farthest keyframe and store the corresponding
stream id too

[...]
> > > > you could agrue that things are different if we are just interrested in a
> > > > subset of the streams but IMHO such a file is simply broken its like adding
> > > > a broken stream and then designing a container which can "ignore" it
> > > 
> > > No, it's not nonsense. The most common example I can think of is a
> > > music video, where the audio is the "primary" stream. If you're just
> > > playing the audio you want to be able to seek to any timestamp, not
> > > just the video keyframes. Even if you will be playing the video you
> > > might want to ignore it for seeking and just display a black frame
> > > until the next video keyframe comes.
> > 
> > and that will work fine with an index it will work fine with a binary
> > search without back pointers (implemented and working in lavc so dont tell
> > me it wont)
> 
> I don't want to challenge you or say you're wrong on this, but I
> really don't understand how you can seek to the closest keyframe
> before a given timestamp without back_ptr. Could you explain? I'm not
> looking for pathological examples like uau is. I just want to know
> things work. If you have a system that works I'm sure it would settle
> Oded down and keep him from wasting all my time thinking about
> problems with NUT so I could get back to finishing libc.. :)

my system is trivial: linear search backward, for the case given it works
as audio has many small intra only frames in practice

[...]
-- 
Michael