- return(r);
-}
-
-/* build the decode helper tree from the codewords */
-decode_aux *_make_decode_tree(codebook *c){
- const static_codebook *s=c->c;
- long top=0,i,j,n;
- decode_aux *t=_ogg_malloc(sizeof(*t));
- long *ptr0=t->ptr0=_ogg_calloc(c->entries*2,sizeof(*ptr0));
- long *ptr1=t->ptr1=_ogg_calloc(c->entries*2,sizeof(*ptr1));
- long *codelist=_make_words(s->lengthlist,s->entries);
-
- if(codelist==NULL)return(NULL);
- t->aux=c->entries*2;
-
- for(i=0;i<c->entries;i++){
- if(s->lengthlist[i]>0){
- long ptr=0;
- for(j=0;j<s->lengthlist[i]-1;j++){
- int bit=(codelist[i]>>j)&1;
- if(!bit){
- if(!ptr0[ptr])
- ptr0[ptr]= ++top;
- ptr=ptr0[ptr];
- }else{
- if(!ptr1[ptr])
- ptr1[ptr]= ++top;
- ptr=ptr1[ptr];
- }
- }
- if(!((codelist[i]>>j)&1))
- ptr0[ptr]=-i;
- else
- ptr1[ptr]=-i;
- }
- }
- _ogg_free(codelist);
-
- t->tabn = _ilog(c->entries)-4; /* this is magic */
- if(t->tabn<5)t->tabn=5;
- n = 1<<t->tabn;
- t->tab = _ogg_malloc(n*sizeof(*t->tab));
- t->tabl = _ogg_malloc(n*sizeof(*t->tabl));
- for (i = 0; i < n; i++) {
- long p = 0;
- for (j = 0; j < t->tabn && (p > 0 || j == 0); j++) {
- if (i & (1 << j))
- p = ptr1[p];
- else
- p = ptr0[p];
- }
- /* now j == length, and p == -code */
- t->tab[i] = p;
- t->tabl[i] = j;
+ if(sparsecount){
+ if(l[i])
+ r[count++]=temp;
+ }else
+ r[count++]=temp;
- well defined. We define that the possible vales at each
- scalar is values == entries/dim. If entries%dim != 0, we'll
- have 'too few' values (values*dim<entries), which means that
- we'll have 'left over' entries; left over entries use zeroed
- values (and are wasted). So don't generate codebooks like
- that */
+ well defined. We define that the possible vales at each
+ scalar is values == entries/dim. If entries%dim != 0, we'll
+ have 'too few' values (values*dim<entries), which means that
+ we'll have 'left over' entries; left over entries use zeroed
+ values (and are wasted). So don't generate codebooks like
+ that */
- c->codelist=_make_words(s->lengthlist,s->entries);
- c->valuelist=_book_unquantize(s);
-
- /* set the 'zero entry' */
- c->zeroentry=-1;
- if(c->valuelist){
- for(j=0;j<s->entries;j++){
- int flag=1;
- for(k=0;k<s->dim;k++){
- if(fabs(c->valuelist[j*s->dim+k])>1e-12f){
- flag=0;
- break;
- }
- }
- if(flag)
- c->zeroentry=j;
- }
- }
+ c->codelist=_make_words(s->lengthlist,s->entries,0);
+ /* c->valuelist=_book_unquantize(s,s->entries,NULL); */
+ c->quantvals=_book_maptype1_quantvals(s);
+ c->minval=(int)rint(_float32_unpack(s->q_min));
+ c->delta=(int)rint(_float32_unpack(s->q_delta));
-#include <stdio.h>
-int _best(codebook *book, float *a, int step){
- encode_aux_nearestmatch *nt=book->c->nearest_tree;
- encode_aux_threshmatch *tt=book->c->thresh_tree;
- encode_aux_pigeonhole *pt=book->c->pigeon_tree;
- int dim=book->dim;
- int ptr=0,k,o;
- /*int savebest=-1;
- float saverr;*/
-
- /* do we have a threshhold encode hint? */
- if(tt){
- int index=0;
- /* find the quant val of each scalar */
- for(k=0,o=step*(dim-1);k<dim;k++,o-=step){
- int i;
- /* linear search the quant list for now; it's small and although
- with > ~8 entries, it would be faster to bisect, this would be
- a misplaced optimization for now */
- for(i=0;i<tt->threshvals-1;i++)
- if(a[o]<tt->quantthresh[i])break;
-
- index=(index*tt->quantvals)+tt->quantmap[i];
- }
- /* regular lattices are easy :-) */
- if(book->c->lengthlist[index]>0) /* is this unused? If so, we'll
- use a decision tree after all
- and fall through*/
- return(index);
- }
+ First, we collapse the likely sparse codebook down only to
+ actually represented values/words. This collapsing needs to be
+ indexed as map-valueless books are used to encode original entry
+ positions as integers.
- /* do we have a pigeonhole encode hint? */
- if(pt){
- const static_codebook *c=book->c;
- int i,besti=-1;
- float best;
- int entry=0;
-
- /* dealing with sequentialness is a pain in the ass */
- if(c->q_sequencep){
- int pv;
- long mul=1;
- float qlast=0;
- for(k=0,o=0;k<dim;k++,o+=step){
- pv=(int)((a[o]-qlast-pt->min)/pt->del);
- if(pv<0 || pv>=pt->mapentries)break;
- entry+=pt->pigeonmap[pv]*mul;
- mul*=pt->quantvals;
- qlast+=pv*pt->del+pt->min;
- }
- }else{
- for(k=0,o=step*(dim-1);k<dim;k++,o-=step){
- int pv=(int)((a[o]-pt->min)/pt->del);
- if(pv<0 || pv>=pt->mapentries)break;
- entry=entry*pt->quantvals+pt->pigeonmap[pv];
- }
- }
+ Second, we reorder all vectors, including the entry index above,
+ by sorted bitreversed codeword to allow treeless decode. */
- /* must be within the pigeonholable range; if we quant outside (or
- in an entry that we define no list for), brute force it */
- if(k==dim && pt->fitlength[entry]){
- /* search the abbreviated list */
- long *list=pt->fitlist+pt->fitmap[entry];
- for(i=0;i<pt->fitlength[entry];i++){
- float this=_dist(dim,book->valuelist+list[i]*dim,a,step);
- if(besti==-1 || this<best){
- best=this;
- besti=list[i];
- }
- }
+ /* perform sort */
+ ogg_uint32_t *codes=_make_words(s->lengthlist,s->entries,c->used_entries);
+ ogg_uint32_t **codep=alloca(sizeof(*codep)*n);
- if(nt){
- /* optimized using the decision tree */
- while(1){
- float c=0.f;
- float *p=book->valuelist+nt->p[ptr];
- float *q=book->valuelist+nt->q[ptr];
-
- for(k=0,o=0;k<dim;k++,o+=step)
- c+=(p[k]-q[k])*(a[o]-(p[k]+q[k])*.5);
-
- if(c>0.f) /* in A */
- ptr= -nt->ptr0[ptr];
- else /* in B */
- ptr= -nt->ptr1[ptr];
- if(ptr<=0)break;
+ qsort(codep,n,sizeof(*codep),sort32a);
+
+ sortindex=alloca(n*sizeof(*sortindex));
+ c->codelist=_ogg_malloc(n*sizeof(*c->codelist));
+ /* the index is a reverse index */
+ for(i=0;i<n;i++){
+ int position=codep[i]-codes;
+ sortindex[position]=i;
- /* brute force it! */
- {
- const static_codebook *c=book->c;
- int i,besti=-1;
- float best;
- float *e=book->valuelist;
- for(i=0;i<book->entries;i++){
- if(c->lengthlist[i]>0){
- float this=_dist(dim,e,a,step);
- if(besti==-1 || this<best){
- best=this;
- besti=i;
- }
+ for(i=0;i<n;i++)
+ c->codelist[sortindex[i]]=codes[i];
+ _ogg_free(codes);
+
+ c->valuelist=_book_unquantize(s,n,sortindex);
+ c->dec_index=_ogg_malloc(n*sizeof(*c->dec_index));
+
+ for(n=0,i=0;i<s->entries;i++)
+ if(s->lengthlist[i]>0)
+ c->dec_index[sortindex[n++]]=i;
+
+ c->dec_codelengths=_ogg_malloc(n*sizeof(*c->dec_codelengths));
+ c->dec_maxlength=0;
+ for(n=0,i=0;i<s->entries;i++)
+ if(s->lengthlist[i]>0){
+ c->dec_codelengths[sortindex[n++]]=s->lengthlist[i];
+ if(s->lengthlist[i]>c->dec_maxlength)
+ c->dec_maxlength=s->lengthlist[i];
- /*if(savebest!=-1 && savebest!=besti){
- fprintf(stderr,"brute force/pigeonhole disagreement:\n"
- "original:");
- for(i=0;i<dim*step;i+=step)fprintf(stderr,"%g,",a[i]);
- fprintf(stderr,"\n"
- "pigeonhole (entry %d, err %g):",savebest,saverr);
- for(i=0;i<dim;i++)fprintf(stderr,"%g,",
- (book->valuelist+savebest*dim)[i]);
- fprintf(stderr,"\n"
- "bruteforce (entry %d, err %g):",besti,best);
- for(i=0;i<dim;i++)fprintf(stderr,"%g,",
- (book->valuelist+besti*dim)[i]);
- fprintf(stderr,"\n");
- }*/
- return(besti);
- }
-}
+ if(n==1 && c->dec_maxlength==1){
+ /* special case the 'single entry codebook' with a single bit
+ fastpath table (that always returns entry 0 )in order to use
+ unmodified decode paths. */
+ c->dec_firsttablen=1;
+ c->dec_firsttable=_ogg_calloc(2,sizeof(*c->dec_firsttable));
+ c->dec_firsttable[0]=c->dec_firsttable[1]=1;
-/* returns the entry number and *modifies a* to the remainder value ********/
-int vorbis_book_besterror(codebook *book,float *a,int step,int addmul){
- int dim=book->dim,i,o;
- int best=_best(book,a,step);
- switch(addmul){
- case 0:
- for(i=0,o=0;i<dim;i++,o+=step)
- a[o]-=(book->valuelist+best*dim)[i];
- break;
- case 1:
- for(i=0,o=0;i<dim;i++,o+=step){
- float val=(book->valuelist+best*dim)[i];
- if(val==0){
- a[o]=0;
- }else{
- a[o]/=val;
+ }else{
+ c->dec_firsttablen=ov_ilog(c->used_entries)-4; /* this is magic */
+ if(c->dec_firsttablen<5)c->dec_firsttablen=5;
+ if(c->dec_firsttablen>8)c->dec_firsttablen=8;
+
+ tabn=1<<c->dec_firsttablen;
+ c->dec_firsttable=_ogg_calloc(tabn,sizeof(*c->dec_firsttable));
+
+ for(i=0;i<n;i++){
+ if(c->dec_codelengths[i]<=c->dec_firsttablen){
+ ogg_uint32_t orig=bitreverse(c->codelist[i]);
+ for(j=0;j<(1<<(c->dec_firsttablen-c->dec_codelengths[i]));j++)
+ c->dec_firsttable[orig|(j<<c->dec_codelengths[i])]=i+1;
+ }
+ }
+
+ /* now fill in 'unused' entries in the firsttable with hi/lo search
+ hints for the non-direct-hits */
+ {
+ ogg_uint32_t mask=0xfffffffeUL<<(31-c->dec_firsttablen);
+ long lo=0,hi=0;
+
+ for(i=0;i<tabn;i++){
+ ogg_uint32_t word=i<<(32-c->dec_firsttablen);
+ if(c->dec_firsttable[bitreverse(word)]==0){
+ while((lo+1)<n && c->codelist[lo+1]<=word)lo++;
+ while( hi<n && word>=(c->codelist[hi]&mask))hi++;
+
+ /* we only actually have 15 bits per hint to play with here.
+ In order to overflow gracefully (nothing breaks, efficiency
+ just drops), encode as the difference from the extremes. */
+ {
+ unsigned long loval=lo;
+ unsigned long hival=n-hi;
+
+ if(loval>0x7fff)loval=0x7fff;
+ if(hival>0x7fff)hival=0x7fff;
+ c->dec_firsttable[bitreverse(word)]=
+ 0x80000000UL | (loval<<15) | hival;
+ }
+ }
+ }
- -3, 4,-3, 4, 4,-3, -1, 4,-3,
- -3,-1,-3, 4,-1,-3, -1,-1,-3,
- -3,-3, 4, 4,-3, 4, -1,-3, 4,
- -3, 4, 4, 4, 4, 4, -1, 4, 4,
- -3,-1, 4, 4,-1, 4, -1,-1, 4,
- -3,-3,-1, 4,-3,-1, -1,-3,-1,
- -3, 4,-1, 4, 4,-1, -1, 4,-1,
- -3,-1,-1, 4,-1,-1, -1,-1,-1};
+ -3, 4,-3, 4, 4,-3, -1, 4,-3,
+ -3,-1,-3, 4,-1,-3, -1,-1,-3,
+ -3,-3, 4, 4,-3, 4, -1,-3, 4,
+ -3, 4, 4, 4, 4, 4, -1, 4, 4,
+ -3,-1, 4, 4,-1, 4, -1,-1, 4,
+ -3,-3,-1, 4,-3,-1, -1,-3,-1,
+ -3, 4,-1, 4, 4,-1, -1, 4,-1,
+ -3,-1,-1, 4,-1,-1, -1,-1,-1};
- -3, 1,-2, 4, 8, 5, -1, 3, 0,
- -3,-4,-7, 4, 3, 0, -1,-2,-5,
- -3,-6,-2, 4, 1, 5, -1,-4, 0,
- -3, 1, 5, 4, 8,12, -1, 3, 7,
- -3,-4, 0, 4, 3, 7, -1,-2, 2,
- -3,-6,-7, 4, 1, 0, -1,-4,-5,
- -3, 1, 0, 4, 8, 7, -1, 3, 2,
- -3,-4,-5, 4, 3, 2, -1,-2,-3};
+ -3, 1,-2, 4, 8, 5, -1, 3, 0,
+ -3,-4,-7, 4, 3, 0, -1,-2,-5,
+ -3,-6,-2, 4, 1, 5, -1,-4, 0,
+ -3, 1, 5, 4, 8,12, -1, 3, 7,
+ -3,-4, 0, 4, 3, 7, -1,-2, 2,
+ -3,-6,-7, 4, 1, 0, -1,-4,-5,
+ -3, 1, 0, 4, 8, 7, -1, 3, 2,
+ -3,-4,-5, 4, 3, 2, -1,-2,-3};