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

[Oded Shimon]

On Fri, Jan 20, 2006 at 02:59:25PM +0100, Michael Niedermayer wrote:
> Hi
> 
> On Fri, Jan 20, 2006 at 09:53:18AM +0200, Oded Shimon wrote:
> > On Wed, Jan 18, 2006 at 11:32:47PM -0500, Rich Felker wrote:
> > > On Wed, Jan 18, 2006 at 11:23:07PM +0100, Michael Niedermayer wrote:
> > > > Hi
> > > > 
> > > > On Tue, Jan 17, 2006 at 05:59:23PM -0500, Rich Felker wrote:
> > > > [...]
> > > > > Comments?
> > > > 
> > > > after thinking about this again a little i think i am strongly in favor
> > > > of a single pts and single ptr per syncpoint and nothing more complicated
> > > > 
> > > > with index: optimal seeking
> > > > without index: seeking to a point which has a keyframe in every stream
> > > > prior to the user specified timestamp
> > > > 
> > > > so even witout an index you can do exact seeking, and normal use of
> > > > video+audio+subtitle files will be fine, only the case where you
> > > > want very quick and exact seeking to a subset of streams will not
> > > > work as well as with the more complicated cases but i really think
> > > > that simplicity and overhead of the format is more important then
> > > > that
> > > 
> > > ok, with all of our ideas to fix the problem failing, i've talked to
> > > oded and i'm willing to give up per-stream back_ptr in syncpoints,
> > > provided we have a provable algorithm to do exact seeking in any
> > > stream with O(back_ptr) linear search. unless we're mistaken and
> > > missing a stupid case, i think this can be done without any problem.
> > > implementations are of course free to skip any further steps and just
> > > use the back_ptr as-is.
> > > 
> > > one of us will send an updated proposal soon.
> > 
> > Here it is..
> > 
> > step-4:
> >   add EOR
> >   add coded stream flags
> >   rearrange header a little bit - the actual changes are that tmp_mul and 
> >   tmp_pts are after tmp_stream, and everything has a default value.
> 
> and i still strongly disagree with the default values, heres an example to
> demonstrate that they suck
> 
> 1 video stream, 1 audio stream
> 
> old framecode:
> flag=nonkey, fields=2, pts=0, mul=X, flag=key, fields=0, flag=nonkey, fields=1, pts=1, flag=key, fields=0
> flag=key, fields=3, pts=0, mul=Y, stream=1, flag=key, fields=1, pts=1
> 
> your reordered framecode:
> flag=nonkey, fields=3, sflag, stream=0, mul=X, flag=key, fields=3, sflag, stream=0, mul=X, flag=nonkey, 
> fields=4, sflag, stream=0, mul=X, pts=1, flag=key, fields=4, sflag, stream=0, mul=X, pts=1
> flag=key, fields=3, sflag, stream=1, mul=Y, flag=key, fields=4, sflag, stream=1, mul=Y, pts=1

Ahhh... ok, now I finally understand it... 1 thing I'd like to point out 
for my defense, sflag is new and necessary to be split, so you just 
exploited it to make my method seem even worse :) unless you want it 
msb coded in flag or something...

One thing I'd atleast want changed is initial values for tmp_*, before the 
loop.

> > BTW2, with linear interpolation, for a 700mb file, seeks average to 4-10 
> > underlying seeks for the binary search.
> 
> 1pass encoded or 2pass with some high motion and low motion scenes?
> note, be carefull with pure linear interpolation search, it has
> O(n) worst case / O(1) best case behavior where choosing the middle
> has O(log n) worst case, so you need to detect failures and do something
> about them ...

I dunno how this file was created, most likely 2 pass, it's your average 
high quality file found on the net...

As for detecton, the full code:

if (hi - lo < nut->max_distance) guess = lo + 8;
else {
    double a = (double)(hi - lo) / (hip - lop);
    guess = lo + a * (pts - lop);
    if (hi - guess < nut->max_distance) guess = hi - nut->max_distance;
}
if (guess < lo + 8) guess = lo + 8;



Index results:

high quality 700mb  0 subtitle streams: 81031
high quality 700mb 10 subtitle streams: 102475
low  quality 620mb  0 subtitle streams: 65790
low  quality 620mb 10 subtitle streams: 109409

BTW, my repeat stuff is apperantely quite unhelpful, it can be removed at 
the cost of 3kb or so for the sake of simplicity.

I'm sending a new patch soon and asking for immediatte aproval for 
commit...

- ods15