[MPlayer-dev-eng] NUT backptr proposal

[Oded Shimon]

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.

- ods15