[MPlayer-dev-eng] NUT (informal) proposal, based on discussions

[Rich Felker]

OK, first of all, starting a new thread because the old one is way too
long. :)

Now that I'm back, I've read the discussion that took place while I
was gone and discussed it some with Oded. I _think_ we have a proposal
that might be agreeable. I'm just going to outline what information is
stored where, not how it's stored. Michael and Oded already have some
good ideas for making storage more efficient which are separate from
the actual issue of what information is stored. So.....

Index:

1. List of all syncpoints positions

2. Between each pair of consecutive syncpoints, a flag for which
   streams have keyframes.

3. For each stream which has a keyframe in the interval between
   syncpoints, the pts of the first keyframe.

Without this information, Oded's goal of single media seek when using
index (which is also Ivan's goal) is simply not possible.

Note that while this looks like "per-stream pts" it's really much
less. Streams with sparse keyframes (or sparse frames altogether) will
very rarely have a pts stored in the index and hardly contribute to
size. The only size issue comes from multiple intra-only streams with
frequent frames, i.e. most audio codecs.


Syncpoints:

1. No syncpoint placement rules except for max_distance.

2. Each syncpoint has a timestamp compatible with MN rule, i.e. it is
   greater than the DTS of all previous frames and less than the PTS
   of all future frames. (Equality case needs to be decided BTW)

3. For each (non-EOR) stream, the syncpoint has a back_ptr value
   pointing to the most recent keyframe with PTS less than the
   syncpoint's timestamp. (Not necessarily the most recent one written
   -- this is Oded's and Michael's solution to eliminating per-stream
   pts nonsense.)


Seeking algorithms:

With index:

Choose the latest syncpoint such, for each [active] stream, that there
is at least one subsequent occurrance of a syncpoint interval with
stream PTS less than target PTS.

Without index:

1. Binary search for the latest syncpoint with timestamp less than the
   requested PTS.

2. Linear search forward until next syncpoint (bounded by
   max_distance). If a keyframe is found for each [active] stream with
   PTS less than the target PTS, you are done searching.

3. If any [active] stream is missing a keyframe when you reach the
   next syncpoint, use the back_ptr values stored in this syncpoint
   (at the end of the search range) to seek back and linear search for
   the missing keyframes (bounded by max_distance).

Example with out-of-order frames, provided by Oded...sort of a
worst-case thing:

S1 K2 .....several_megs_no_K..... K15 S13 ...no_K_or_S... S24

* Trying to seek to timestamp 14. Should get K15.

* Binary search will put you at S13. S13's back_ptr points all the way
  back to S1, which is incorrect.

* Linear search S13 to S24. Keyframe not found.

* Jump back to S24's back_ptr. This will (necessarily) point to K15.

* Win!

The main disadvantage of this method is that it cannot guarantee that
you will not perform an additional media seek after the binary search.
But just like the index case, I see no way to guarantee this without
full per-stream pts which would be very large at the syncpoint level
(since you can't code them relative to previous syncpoint).

I have not entirely confirmed this, but Oded and I believe it is
possible to dynamically build from these syncpoints a data structure
which matches the index, so that after a region of the file has been
'mapped out' by the demuxer, future seeks to that region require only
one media seek and only max_distance worth of reading.

It may be possible to use 1/max_distance scaled back_ptr values
instead of 1/8 to reduce syncpoint size, with minor modifications.
However I have not verified this.

Comments?

Rich