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

[Michael Niedermayer]

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


> 
> step-5:
>   change goals slightly..
>   max_index_distance removed
>   index changed to combination of syncpoint index and pts for keyframes, 
>   using ideas by michael and myself
>   syncpoint still single back_ptr and pts, however back_ptr is changed - 
>   points to most correct keyframe, not most recent.
>   syncpoint timestamp is max(last_dts)

OK


> 
> cosmetic:
>   move things around to IMO more logical positions.

abstain / dont care either way :)


[...]
> BTW, does anyone have a good idea for efficient but simple data structure 
> for decoded index?... The naive way requires 
> streams*syncpoints*sizeof(uint64_t) memory, which is too much. (5mb of 
> ram?..) Any other idea I can think of requires some complication for 
> just using the values or changing them... (I still want the ability to 
> dynamically build the index while playing)

5mb? i came up with 10mb for a 4gb 10stream file, and for thouse now shouting
10mb isnt an issue for 4gb files, it is a big issue as thats RAM and a DVD
player shouldnt need 10mb RAM for the index
ahh, one solution, drop the PTS and the index will need <200kb in RAM
and yes every demuxer will do this IMHO, it doesnt even break optimal
seeking:
exact seeking: find the prevous syncpoint P for timestamp X then find the
earliest syncpoint which has a keyframe prior P in every wanted stream
optimal seeking: do the same but additionally check if syncpoint P itself
already contains a keyframe for every stream we want (0 seeks) and if so
check if they are before X (1 extra seek)
now let the flamewars begin again about why 10mb memory, 64x larger RAM 
and 10x larger index in the file is worth saving 1 _rarely_needed_ seek
for optimal seeking


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

[...]

-- 
Michael