[MPlayer-dev-eng] a few nut suggestions [back-reference packets]

[D Richard Felker III]

On Mon, Oct 04, 2004 at 01:48:18PM +0200, Michael Niedermayer wrote:
> > actually i said all this with realtime streams in mind too. if i made
> > a realtime streaming server, i would make it always send any
> > still-relevant info packets at the beginning of the transmission when
> > a new client connects.
> 
> ugh, so the server needs to parse and reorder the stream per client? my first 
> thought is this is braindamaged and i would avoid nut then if i had the 
> choice

doesn't need to, but it could be useful. in any case this needs to be
done to a minimal degree to send global headers to new clients when
they connect. and if the server offers the client several different
choices of bitrate/codec/language/etc. it may need to remux
per-client.

of course, in the most basic setup, none of this is necessary.

> > > the back reference becomes pretty much unnecessary as searching through
> > > 0.5 or so seconds of the bitstream is easy
> >
> > yes. but repeating data again and again could be very wasteful.
> > especially if it's big data. (and who knows what someone will want to
> > store in info packets...)
> 
> yes, if we reverse the keyframe -> syncpoint index change u purposed we could 
> use the index to find this data very efficiently in non realtime streams, and 
> for realtime we must repeat the packets anyway due to packet loss and similar

how do you propose doing that, though? if we index every keyframe, the
index will be huge since audio is typically all-keyframes! then nut
will suck just like avi... :(

i know you proposed the rule of only using startcodes & indexing a
keyframe when it's the first keyframe to come after a non-keyframe,
but this optimization just works based off the assumptions of current
codecs. what if you had a codec (audio or video) with a pattern like
IBIBIBI or IBBIBBIBBI? adding tons more startcodes and index entries
would be a serious overhead burden.

i do have a _clean_ idea for improving the seeking efficiency with an
index, but not non-index, see what you think: in the index, include
with each entry a bitfield marking which streams had a keyframe packet
between that syncpoint and the previous one. this makes it easy to
know which syncpoint you want to jump to for finding a keyframe at a
given timestamp.

of course the backreference pointers give you the same benefit with or
without index, so they might be a better approach.

> > > furthermore the demuxer is able to find video keyframes, so why shouldnt
> > > it also use the same method to find audio or subtitle keyframes?
> >
> > there will be a sane upper bound on distance between keyframes. is
> > there necessarily a sane upper bound on distance between subtitles or
> > infopackets? imo not...
> 
> imo there should be

i meant a natural upper bound. whether we want to impose one is
another matter.

> > anyway, the keyframe search algorithm basically goes like this, iirc:
> > 1. seek to a syncpoint (index O(1) or binary search O(n log n))
> > 2. scan for keyframe (linear search O(keyint))
> 
> no, this is wrong, it simply wont work, its

i agree. in my email i said it's actually a little more complicated
but i got the big-O's right.

> before the changes u requested it was possible to do a binary search to the 
> keyframe_startcode and u had a useable keyframe after this, maybe not the 
> closest keyframe but it was guaranteed to work as a low complexity seeking 
> implementation

imo implementations should provide correct seeking, not a bad hack to
be slightly simpler. so if the complexity of seeking is too high in
the current spec, we should fix that, one way or another.. and i think
you're probably right that it's too high.


rich