[MPlayer-dev-eng] NUT backptr proposal

[Oded Shimon]

On Thu, Dec 29, 2005 at 11:07:08AM +0200, Oded Shimon wrote:
> On Thu, Dec 29, 2005 at 03:44:37AM -0500, Rich Felker wrote:
> > beyond: the index..
> > 
> > naturally an index that simply points to each syncpoint can be used;
> > however that increases the required media-seek operations to 2 per
> > seek instead of just 1. storing back_ptr values in the index seems
> > desirable if it can be done without severe overhead costs. oded will
> > hopefully be sending a proposal based on some of our ideas for the
> > index to go with per-stream back_ptr.
> 
> Now it's my turn.
> I feel it is easiest to describe this complicated index with code:
> 
> for (i = 0; i < ss; i++) s[i].repeat = 1;
> get_v(syncpoints);
> get_v(M);
> for(i = 0; i < syncpoints; i++) {
> 	int j, flag = 0;
> 	for (j = 0; j < ss; j++) if (!--s[j].repeat) flag = 1;
> 	if (!flag) continue;
> 	get_v(pts);
> 	for (j = 0; j < ss; j++) {
> 		if (!s[j].repeat) {
> 			get_v(back_ptr);
> 			if (back_ptr < M) {
> 				int k;
> 				for (k = 0; k < back_ptr; k++) {
> 					s[j].back_ptr[i+k] = { pts, s[j].back_ptr[i-1] };
> 				}
> 				s[j].repeat = back_ptr;
> 			} else {
> 				back_ptr -= M;
> 				back_ptr *= 8;
> 				if (i) back_ptr + =s[j].back_ptr[i-1]
> 				s[j].back_ptr[i] = { pts, back_ptr };
> 			}
> 		}
> 	}
> }
> 
> This code assumes a very very stupid way of storing the index... Basically 
> stores EVERY syncpoint for every stream, instead of just the repeated ones.
> 
> Anyway, here's my best attempt to decribe the index in words:
> 
> index:
> 	max_pts					v
> 	syncpoints				v
> 	M					v
> 	for (i = 0; i < syncpoints; i++){
> 		if (no entry to read on all streams) continue;
> 		pts				v
> 		for (j = 0; j < streams; j++){
> 			if (no entry to read) continue;
> 			back_ptr		v
> 		}
> 	}
> 
> back_ptr can have 2 meanings.
> If it is bigger than M, then "back_ptr - M" is the real back_ptr of this 
> syncpoint.
> If it is smaller than M, it's a repeat count. all the following back_ptr's 
> of this same stream are the same as the last back_ptr. "no entry to read" 
> is set for all following back_ptr's for the following repeat count 
> syncpoints. if all streams are marked, no pts is read until one of the 
> streams is unmarked.
> 
> IMO, M should be about 256.
> 
> I can only guess, but my estimate is that this is a 100kb index for a 700mb 
> file. maybe much less. As an absoloute max, the overhead for storing the 
> syncpoints like this minus the actual 8 byte syncpoint, it is 220kb. index 
> should be much much less.

index is 82kb for 700mb file. I think that's fair, the syncpoints are about 
440kb anyway. btw, with the old back ptr method, the syncpoints were 390kb, 
so, no big loss there.
In general a 700mb file has about 1mb of overhead, maybe 1.5mb. mkv for 
this file has 1.56mb overhead.

However, I have some other bad news - In the not so pathological situation 
of a DVD rip with 10-15 subtitles, syncpoint overhead will be HUGE. Due to 
big back_ptr's of subtites, you could end up with over 50 bytes per 
syncpoint, meaning about 2mb of overhead for syncpoints. index will not be 
as wasteful, but syncpoint needs to be rethought.

- ods15