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

[Rich Felker]

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.

It should be noted that in many (but not all) situations you can avoid
searching between A and the requested pts just by looking at the next
syncpoint C's back_ptrs, which you would know if you know the index.

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

Rich