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

[Oded Shimon]

To sum up a rather long discussion between me and Rich today:

1. EOS
2. syncpoints must be max(dts) (min(pts)?)
3. strict interleaving method
4. my keyframe rule (keyframes further than max distance)
5. index can also have zero back ptr
6. seperate control and stream flags in frame code
7. real back ptr is back ptr / (10 + number of streams)
8. syncpoints too big?


1. EOS

End of Stream flag, add this to frame code table, it means this stream has 
ended for now, so back ptr's for this stream are effectively zero. Mostly 
for subtitles when nothing is appearing, back ptr in that case is just 
zero. Some rules about EOS I'm not very sure of - the frame itself must be 
zero byte (?), the frame itself is non keyframe (?).


2. syncpoints must be max(dts) (min(pts)?)

At the moment there's absolutely no rule about syncpoint pts, it can 
practically be random numbers and it's still legal. We say it must be 
either max dts across all streams, or min pts across all streams...
I think i preffer max dts. dts is "almost" monotone, making the syncpoint 
fit nicely between the frames...
Also, given subtitles, min(pts) is completely bogus. even with EOS, think 
during a subtitle.
Both methods basically make the syncpoints themselves also follow the MN 
rule. Which brings us to next thing...


3. strict interleaving method

We still have the deprecated DTS method in the spec. My vote is for MN 
rule, it has only one flaw IMO. you can do stupid things like audio 
preload if you set decode_delay higher than it should be.
Here is a text Rich and I prepared for MN rule a while ago..
-
all timestamps must satisfy a monotonicity condition: if I and J
are two frames, not necessarily from the same stream, and I
precedes J in the bitstream, then the _decode_ timestamp of I must
be less than or equal to the _presentation_ timestamp of J,
compared in a common time base.
-


4. my keyframe rule (keyframes further than max distance)

I actually came up with a good idea! :) Actually, I have a slight change 
since its original phrasing:
"If there has been syncpoint since the last keyframe in this stream, there 
must appear a syncpoint immediately before the next keyframe."
The full story:

P is requested pts
S1 is closest syncpoint before P
S2 is syncpoint pointed to by S1's back ptr
K is keyframe

S2 K ........................... S1 ... K P

going to S2 is bad, because what I really want is what's after S1... My 
rule makes this situation impossible. My rule gives this garuntee:
If the back_ptr if S1 is non zero, meaning, it points to another syncpoint 
instead of itself, there can not be keyframes between S1 to until the next 
syncpoint (S1 to P).
Rich, I just noticed, this new rule means you only have to linear scan ONE 
max_distance! Not 2. Only if back_ptr is zero do you need to continue past 
S1.
I'm still a little worried about this rule requiring too many syncpoints...
Hmm, yes, in the case of 2 intra only streams, this rule effectively means 
there will be a syncpoint before every frame, which is very bad. :/
OK, back to old phrasing of my rule, oops.
"If the last keyframe in this stream is more than max_distance away, a 
syncpoint must appear immediately before the next keyframe."

This means, to seek, you must do these steps:
Go to S2, linear seek until you either:
1. pass P
OR
2. you find a syncpoint AND (S1-S2) is more than max_distance.


5. index can also have zero back ptr

Michael, by your index suggestion I guess you didn't notice, back_ptr can 
sometimes be zero, meaning, the syncpoints points to itself. It only does 
this if the frame right infront of it is a keyframe. My suggestion: use the 
LSB of repeat to indicate wether you mean this syncpoint or the one right 
before it.

   repeat= get_v() + 2;
   for(k=0; k < (repeat>>1); k++)
      syncpoint[j+k].stream[i].back_ptr= syncpoint[j-(repeat&1)].pos_div8;
   j+= repeat>>1;

I checked, multiplying repeat by 2 adds extremely little to overhead, 400 
bytes out of 110kb or so.
BTW, 110kb for 700mb, this is way more than in our goals section which 
claims 10kb index for 1 hour movie.
Overall, your index idea is probably the best. It's actually bigger than 
our idea (110kb vs. 80kb), but provides more info and scales better with 
more streams.
Overhead percentage is about right in the goals, we stand at 1.5mb for 
700mb file, that's 0.2% as claimed.


6. seperate control and stream flags in frame code

Especially now with EOS, we have flags which just control frame codes 
(invalid and msb filesize) and flags which control the actual stream (key 
and EOS). To make an "absoloute minimal" frame code table you need atleast 
4 codes, not 1, to accomodate for all the EOS and key combinations. I 
partially agree that they should be seperated, but in this manner - to 
avoid bloating the frame code table, they should still be under the same 
variable, "flags", however another flag can be set, saying that you can 
only set the stream flags right before the frame. (key or EOS)
So, uhh, new set of flags... I've reordered them to what i think is more 
logical order...
0x01 - msb size
0x02 - set flags right before frame
0x04 - invalid frame code
stream flags
0x08 - keyframe
0x10 - EOS


7. real back ptr is back ptr / (10 + number of streams)

The smallest amount of space a syncpoint can take:

<8 byte startcode> <1 byte pts> <1 byte per back ptr> <1 byte frame code>

That's (10+number of streams), back ptr can divide by that, it actually 
does make the index about 1kb smaller or so...


8. syncpoints too big?

I still think that in my not-so-pathological scenario of 10 subtitles 
stream syncpoint overhead can be huge. More so with my syncpoint rule.
Rich, you said the scenario I gave won't happen:

<syncpoint> <tiny sub1> <syncpoint> <sub2> <syncpoint> <sub3> ...

all the subtitles change together, have a tiny size, and the syncpoints are 
huge, 20-30 bytes, you'll get 400 bytes of data with 1000 bytes of 
overhead.
However, this scenario CAN happen. Like you said, not after EOS, because it 
sets back_ptr and last_key effectively zero. BUT, it can be immediately 
after another subtitle! i.e. subtitle transition. In which case there is no 
EOS inbetween.

Rich had the idea of "stream group" which makes a group of streams be 
treated effectively as one for all back ptr purposes. Not so good...
Any other ideas to either reduce syncpoint overhead or calm down my 
keyframe rule?

A-ha, how about this idea.

"
If the last keyframe in this stream is more than max_distance away, a 
syncpoint must appear immediately before the next keyframe.
UNLESS
the pts of this syncpoint will be identical to the pts of the last 
syncpoint.
In which case, "queue" this syncpoint to be written RIGHT BEFORE the pts of 
the syncpoint will change.
"

So the syncpoint will have the same pts as it was supposed to, and it will 
still have the correct back_ptr, it just won't be immediately before the 
keyframe, but a little after.
Assuming my pathological 10 subtitle streams will have the same pts, this 
update to the rule saves quite a few bytes.

Maybe this is too complicated. It's not too hard to implement though.
Now that I think of it, even without this fix and all the insane 
syncpoints, overhead will probably not surpass 0.5% ....


Anyway, that was a mouthful, I think I'm gonna start working on a big patch 
for mpcf.txt to accomplish all this...
Other than all of this, I only see 2 items left on my TODO list in regards 
to mpcf.txt : max_distance definition needs to be refined that there must 
be atleast a single NUT packet between 2 syncpoints (The whole disucssion 
we had about headers surpassing max_distance), and giving more thought to 
info frames and info packets.
Once we finish that, AND my libnut is updated to do all of this (so we 
don't suddenly notice some kind of implementation problem along the way), 
we can close mpcf.txt .

If nobody replies to this mail I'm gonna be so pissed...

- ods15