[MPlayer-dev-eng] NUT backptr proposal

[Michael Niedermayer]

Hi

On Thu, Dec 29, 2005 at 05:30:03PM +0200, Oded Shimon wrote:
> On Thu, Dec 29, 2005 at 03:24:05PM +0100, Michael Niedermayer wrote:
> > On Thu, Dec 29, 2005 at 11:07:08AM +0200, Oded Shimon wrote:
> > > 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.
> > 
> > hmm, trying to win that obfuscated code contest? ;)
> 
> Oh, I completely forgot about that, when does this year's contest start, I 
> still have my entry ready...
> 
> > if we do choose something like that why not:
> > 
> > n= get_v();
> > for(i = 0; i < n; i++) {
> >     syncpoint[i].pts     = syncpoint[i-1].pts      + get_v() + 1;
> >     syncpoint[i].pos_div8= syncpoint[i-1].pos_div8 + get_v() + 1;
> > }
> > 
> > for(i=0; i<stream_count; i++){
> >     s=0;
> >     for(j=0; j<n; j++){
> >         s+= get_v() + 1;
> >         repeat= get_v() + 1;
> >         while(repeat--){
> >             stream[i].entry[j  ].pts     = syncpoint[s].pts;
> >             stream[i].entry[j++].pos_div8= syncpoint[s].pos_div8;
> >         }
> >     }
> > }
> 
> I'm not sure I understand, but if I'm not mistaken, this means storing at 
> the very least, 2 bytes per each unrepeated syncpoint, plus v_len(pts) and 
> v_len(pos). This is bad, because for audio for ex. just about every 
> syncpoint is unrepeated. using our method, it's only
> v_len(pts) + v_len(pos+M) for each unrepeated syncpoint, much much less 
> space.

except that my code doesnt store v_len(pos) but a delta index into the
syncpoint table which needs fewer bits, anyway this can be improved
further (not that i think its worth it but ...)

n= get_v();
for(i = 0; i < n; i++) {
    syncpoint[i].pts     = syncpoint[i-1].pts      + get_v() + 1;
    syncpoint[i].pos_div8= syncpoint[i-1].pos_div8 + get_v() + 1;
}

for(i=0; i<stream_count; i++){
    type= get_v();
    j= get_v();
    if(type){
        while(j<n){
            repeat= get_v() + 1;
            for(k=0; k<repeat; k++)
                syncpoint[j+k].stream[i].back_ptr= syncpoint[j-1].pos_div8;
            j+= repeat;
        }
    }else{
        while(j<n){
            repeat= get_v();
            for(k=0; k<repeat; k++)
                syncpoint[j+k].stream[i].back_ptr= syncpoint[j+k-1].pos_div8;
            if(!repeat){
                syncpoint[j].stream[i].back_ptr= syncpoint[j-1].stream[i].back_ptr;
                j++;
            }
            j+= repeat;
        }
    }
}

that needs O(syncpoint_count + for every stream MIN(repeated,unrepeated)) bytes

[...]
-- 
Michael