X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=lib%2Fsharedbook.c;h=4545d4f45903e3a7dce12a2e1e67c66892588f7a;hb=018ca26dece618457dd13585cad52941193c4a25;hp=40235fcb87b8e33f30c8538a54b25ab8d36dabe4;hpb=175628aa2f16e99ebe2ca235ac998439299621c6;p=platform%2Fupstream%2Flibvorbis.git diff --git a/lib/sharedbook.c b/lib/sharedbook.c index 40235fc..4545d4f 100644 --- a/lib/sharedbook.c +++ b/lib/sharedbook.c @@ -5,37 +5,36 @@ * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE * * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. * * * - * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2002 * - * by the XIPHOPHORUS Company http://www.xiph.org/ * + * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2015 * + * by the Xiph.Org Foundation http://www.xiph.org/ * * * ******************************************************************** function: basic shared codebook operations - last mod: $Id: sharedbook.c,v 1.25 2002/01/21 20:51:28 xiphmont Exp $ ********************************************************************/ #include +#include #include #include #include #include "os.h" +#include "misc.h" #include "vorbis/codec.h" #include "codebook.h" #include "scales.h" /**** pack/unpack helpers ******************************************/ -int _ilog(unsigned int v){ - int ret=0; - while(v){ - ret++; - v>>=1; - } - return(ret); + +int ov_ilog(ogg_uint32_t v){ + int ret; + for(ret=0;v;ret++)v>>=1; + return ret; } /* 32 bit float (not IEEE; nonnormalized mantissa + - biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm + biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm Why not IEEE? It's just not that important here. */ #define VQ_FEXP 10 @@ -51,7 +50,7 @@ long _float32_pack(float val){ sign=0x80000000; val= -val; } - exp= floor(log(val)/log(2.f)); + exp= floor(log(val)/log(2.f)+.001); //+epsilon mant=rint(ldexp(val,(VQ_FMAN-1)-exp)); exp=(exp+VQ_FEXP_BIAS)<0){ ogg_uint32_t entry=marker[length]; - + /* when we claim a node for an entry, we also claim the nodes - below it (pruning off the imagined tree that may have dangled - from it) as well as blocking the use of any nodes directly - above for leaves */ - + below it (pruning off the imagined tree that may have dangled + from it) as well as blocking the use of any nodes directly + above for leaves */ + /* update ourself */ if(length<32 && (entry>>length)){ - /* error condition; the lengths must specify an overpopulated tree */ - _ogg_free(r); - return(NULL); + /* error condition; the lengths must specify an overpopulated tree */ + _ogg_free(r); + return(NULL); } r[count++]=entry; - + /* Look to see if the next shorter marker points to the node - above. if so, update it and repeat. */ + above. if so, update it and repeat. */ { - for(j=length;j>0;j--){ - - if(marker[j]&1){ - /* have to jump branches */ - if(j==1) - marker[1]++; - else - marker[j]=marker[j-1]<<1; - break; /* invariant says next upper marker would already - have been moved if it was on the same path */ - } - marker[j]++; - } + for(j=length;j>0;j--){ + + if(marker[j]&1){ + /* have to jump branches */ + if(j==1) + marker[1]++; + else + marker[j]=marker[j-1]<<1; + break; /* invariant says next upper marker would already + have been moved if it was on the same path */ + } + marker[j]++; + } } - + /* prune the tree; the implicit invariant says all the longer - markers were dangling from our just-taken node. Dangle them - from our *new* node. */ + markers were dangling from our just-taken node. Dangle them + from our *new* node. */ for(j=length+1;j<33;j++) - if((marker[j]>>1) == entry){ - entry=marker[j]; - marker[j]=marker[j-1]<<1; - }else - break; + if((marker[j]>>1) == entry){ + entry=marker[j]; + marker[j]=marker[j-1]<<1; + }else + break; }else if(sparsecount==0)count++; } - + + /* any underpopulated tree must be rejected. */ + /* Single-entry codebooks are a retconned extension to the spec. + They have a single codeword '0' of length 1 that results in an + underpopulated tree. Shield that case from the underformed tree check. */ + if(!(count==1 && marker[2]==2)){ + for(i=1;i<33;i++) + if(marker[i] & (0xffffffffUL>>(32-i))){ + _ogg_free(r); + return(NULL); + } + } + /* bitreverse the words because our bitwise packer/unpacker is LSb endian */ for(i=0,count=0;ientries,1.f/b->dim)); + long vals; + if(b->entries<1){ + return(0); + } + vals=floor(pow((float)b->entries,1.f/b->dim)); /* the above *should* be reliable, but we'll not assume that FP is ever reliable when bitstream sync is at stake; verify via integer means that vals really is the greatest value of dim for which vals^b->bim <= b->entries */ /* treat the above as an initial guess */ + if(vals<1){ + vals=1; + } while(1){ long acc=1; long acc1=1; int i; for(i=0;idim;i++){ + if(b->entries/valsentries && acc1>b->entries){ + if(i>=b->dim && acc<=b->entries && acc1>b->entries){ return(vals); }else{ - if(acc>b->entries){ - vals--; + if(idim || acc>b->entries){ + vals--; }else{ - vals++; + vals++; } } } @@ -192,49 +212,49 @@ float *_book_unquantize(const static_codebook *b,int n,int *sparsemap){ switch(b->maptype){ case 1: /* most of the time, entries%dimensions == 0, but we need to be - 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*dimentries;j++){ - if((sparsemap && b->lengthlist[j]) || !sparsemap){ - float last=0.f; - int indexdiv=1; - for(k=0;kdim;k++){ - int index= (j/indexdiv)%quantvals; - float val=b->quantlist[index]; - val=fabs(val)*delta+mindel+last; - if(b->q_sequencep)last=val; - if(sparsemap) - r[sparsemap[count]*b->dim+k]=val; - else - r[count*b->dim+k]=val; - indexdiv*=quantvals; - } - count++; - } + if((sparsemap && b->lengthlist[j]) || !sparsemap){ + float last=0.f; + int indexdiv=1; + for(k=0;kdim;k++){ + int index= (j/indexdiv)%quantvals; + float val=b->quantlist[index]; + val=fabs(val)*delta+mindel+last; + if(b->q_sequencep)last=val; + if(sparsemap) + r[sparsemap[count]*b->dim+k]=val; + else + r[count*b->dim+k]=val; + indexdiv*=quantvals; + } + count++; + } } break; case 2: for(j=0;jentries;j++){ - if((sparsemap && b->lengthlist[j]) || !sparsemap){ - float last=0.f; - - for(k=0;kdim;k++){ - float val=b->quantlist[j*b->dim+k]; - val=fabs(val)*delta+mindel+last; - if(b->q_sequencep)last=val; - if(sparsemap) - r[sparsemap[count]*b->dim+k]=val; - else - r[count*b->dim+k]=val; - } - count++; - } + if((sparsemap && b->lengthlist[j]) || !sparsemap){ + float last=0.f; + + for(k=0;kdim;k++){ + float val=b->quantlist[j*b->dim+k]; + val=fabs(val)*delta+mindel+last; + if(b->q_sequencep)last=val; + if(sparsemap) + r[sparsemap[count]*b->dim+k]=val; + else + r[count*b->dim+k]=val; + } + count++; + } } break; } @@ -244,34 +264,13 @@ float *_book_unquantize(const static_codebook *b,int n,int *sparsemap){ return(NULL); } -void vorbis_staticbook_clear(static_codebook *b){ +void vorbis_staticbook_destroy(static_codebook *b){ if(b->allocedp){ if(b->quantlist)_ogg_free(b->quantlist); if(b->lengthlist)_ogg_free(b->lengthlist); - if(b->nearest_tree){ - _ogg_free(b->nearest_tree->ptr0); - _ogg_free(b->nearest_tree->ptr1); - _ogg_free(b->nearest_tree->p); - _ogg_free(b->nearest_tree->q); - memset(b->nearest_tree,0,sizeof(*b->nearest_tree)); - _ogg_free(b->nearest_tree); - } - if(b->thresh_tree){ - _ogg_free(b->thresh_tree->quantthresh); - _ogg_free(b->thresh_tree->quantmap); - memset(b->thresh_tree,0,sizeof(*b->thresh_tree)); - _ogg_free(b->thresh_tree); - } - memset(b,0,sizeof(*b)); - } -} - -void vorbis_staticbook_destroy(static_codebook *b){ - if(b->allocedp){ - vorbis_staticbook_clear(b); _ogg_free(b); - } + } /* otherwise, it is in static memory */ } void vorbis_book_clear(codebook *b){ @@ -295,7 +294,10 @@ int vorbis_book_init_encode(codebook *c,const static_codebook *s){ c->used_entries=s->entries; c->dim=s->dim; c->codelist=_make_words(s->lengthlist,s->entries,0); - c->valuelist=_book_unquantize(s,s->entries,NULL); + //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)); return(0); } @@ -309,16 +311,18 @@ static ogg_uint32_t bitreverse(ogg_uint32_t x){ } static int sort32a(const void *a,const void *b){ - return ( (**(ogg_uint32_t **)a>**(ogg_uint32_t **)b)<<1)-1; + return ( **(ogg_uint32_t **)a>**(ogg_uint32_t **)b)- + ( **(ogg_uint32_t **)a<**(ogg_uint32_t **)b); } /* decode codebook arrangement is more heavily optimized than encode */ int vorbis_book_init_decode(codebook *c,const static_codebook *s){ int i,j,n=0,tabn; int *sortindex; + memset(c,0,sizeof(*c)); - - /* count actually used entries */ + + /* count actually used entries and find max length */ for(i=0;ientries;i++) if(s->lengthlist[i]>0) n++; @@ -327,21 +331,21 @@ int vorbis_book_init_decode(codebook *c,const static_codebook *s){ c->used_entries=n; c->dim=s->dim; - /* two different remappings go on here. + if(n>0){ + /* two different remappings go on here. - 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. + 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. - Second, we reorder all vectors, including the entry index above, - by sorted bitreversed codeword to allow treeless decode. */ + Second, we reorder all vectors, including the entry index above, + by sorted bitreversed codeword to allow treeless decode. */ - { /* perform sort */ ogg_uint32_t *codes=_make_words(s->lengthlist,s->entries,c->used_entries); ogg_uint32_t **codep=alloca(sizeof(*codep)*n); - + if(codes==NULL)goto err_out; for(i=0;icodelist[sortindex[i]]=codes[i]; _ogg_free(codes); - } - c->valuelist=_book_unquantize(s,n,sortindex); - c->dec_index=_ogg_malloc(n*sizeof(*c->dec_index)); + c->valuelist=_book_unquantize(s,n,sortindex); + c->dec_index=_ogg_malloc(n*sizeof(*c->dec_index)); - for(n=0,i=0;ientries;i++) - if(s->lengthlist[i]>0) - c->dec_index[sortindex[n++]]=i; - - c->dec_codelengths=_ogg_malloc(n*sizeof(*c->dec_codelengths)); - for(n=0,i=0;ientries;i++) - if(s->lengthlist[i]>0) - c->dec_codelengths[sortindex[n++]]=s->lengthlist[i]; + for(n=0,i=0;ientries;i++) + if(s->lengthlist[i]>0) + c->dec_index[sortindex[n++]]=i; - c->dec_firsttablen=_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; + c->dec_codelengths=_ogg_malloc(n*sizeof(*c->dec_codelengths)); + c->dec_maxlength=0; + for(n=0,i=0;ientries;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]; + } - tabn=1<dec_firsttablen; - c->dec_firsttable=_ogg_calloc(tabn,sizeof(*c->dec_firsttable)); - c->dec_maxlength=0; + 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; - for(i=0;idec_maxlengthdec_codelengths[i]) - c->dec_maxlength=c->dec_codelengths[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<dec_codelengths[i])]=i+1; - } - } + }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<dec_firsttablen; + c->dec_firsttable=_ogg_calloc(tabn,sizeof(*c->dec_firsttable)); + + for(i=0;idec_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<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); - - for(i=0;idec_firsttable[i]==0){ - ogg_uint32_t testword=bitreverse(i); - long lo=0,hi=0; - while((lo+1)codelist[lo+1]<=testword)lo++; - while( hi=(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[i]=0x80000000UL | (loval<<15) | hival; - } + /* 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;idec_firsttablen); + if(c->dec_firsttable[bitreverse(word)]==0){ + while((lo+1)codelist[lo+1]<=word)lo++; + while( hi=(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; + } + } + } } } } - return(0); err_out: @@ -428,167 +443,6 @@ int vorbis_book_init_decode(codebook *c,const static_codebook *s){ return(-1); } -static float _dist(int el,float *ref, float *b,int step){ - int i; - float acc=0.f; - for(i=0;ic->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 ~8 entries, it would be faster to bisect, this would be - a misplaced optimization for now */ - for(i=0;ithreshvals-1;i++) - if(a[o]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); - } - - /* do we have a pigeonhole encode hint? */ - if(pt){ - const static_codebook *c=book->c; - int i,besti=-1; - float best=0.f; - 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;kmin)/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);kmin)/pt->del); - if(pv<0 || pv>=pt->mapentries)break; - entry=entry*pt->quantvals+pt->pigeonmap[pv]; - } - } - - /* 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;ifitlength[entry];i++){ - float this=_dist(dim,book->valuelist+list[i]*dim,a,step); - if(besti==-1 || thisvaluelist+nt->p[ptr]; - float *q=book->valuelist+nt->q[ptr]; - - for(k=0,o=0;k0.f) /* in A */ - ptr= -nt->ptr0[ptr]; - else /* in B */ - ptr= -nt->ptr1[ptr]; - if(ptr<=0)break; - } - return(-ptr); - } - - /* brute force it! */ - { - const static_codebook *c=book->c; - int i,besti=-1; - float best=0.f; - float *e=book->valuelist; - for(i=0;ientries;i++){ - if(c->lengthlist[i]>0){ - float this=_dist(dim,e,a,step); - if(besti==-1 || thisvaluelist+savebest*dim)[i]); - fprintf(stderr,"\n" - "bruteforce (entry %d, err %g):",besti,best); - for(i=0;ivaluelist+besti*dim)[i]); - fprintf(stderr,"\n"); - }*/ - return(besti); - } -} - -/* 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;ivaluelist+best*dim)[i]; - break; - case 1: - for(i=0,o=0;ivaluelist+best*dim)[i]; - if(val==0){ - a[o]=0; - }else{ - a[o]/=val; - } - } - break; - } - return(best); -} - long vorbis_book_codeword(codebook *book,int entry){ if(book->c) /* only use with encode; decode optimizations are allowed to break this */ @@ -631,10 +485,10 @@ static_codebook test1={ 0, 0,0,0,0, NULL, - NULL,NULL + 0 }; static float *test1_result=NULL; - + /* linear, full mapping, nonsequential */ static_codebook test2={ 4,3, @@ -642,7 +496,7 @@ static_codebook test2={ 2, -533200896,1611661312,4,0, full_quantlist1, - NULL,NULL + 0 }; static float test2_result[]={-3,-2,-1,0, 1,2,3,4, 5,0,3,-2}; @@ -653,7 +507,7 @@ static_codebook test3={ 2, -533200896,1611661312,4,1, full_quantlist1, - NULL,NULL + 0 }; static float test3_result[]={-3,-5,-6,-6, 1,3,6,10, 5,5,8,6}; @@ -664,17 +518,17 @@ static_codebook test4={ 1, -533200896,1611661312,4,0, partial_quantlist1, - NULL,NULL + 0 }; static float test4_result[]={-3,-3,-3, 4,-3,-3, -1,-3,-3, - -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}; /* linear, algorithmic mapping, sequential */ static_codebook test5={ @@ -683,17 +537,17 @@ static_codebook test5={ 1, -533200896,1611661312,4,1, partial_quantlist1, - NULL,NULL + 0 }; static float test5_result[]={-3,-6,-9, 4, 1,-2, -1,-4,-7, - -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}; void run_test(static_codebook *b,float *comp){ float *out=_book_unquantize(b,b->entries,NULL); @@ -707,15 +561,15 @@ void run_test(static_codebook *b,float *comp){ for(i=0;ientries*b->dim;i++) if(fabs(out[i]-comp[i])>.0001){ - fprintf(stderr,"disagreement in unquantized and reference data:\n" - "position %d, %g != %g\n",i,out[i],comp[i]); - exit(1); + fprintf(stderr,"disagreement in unquantized and reference data:\n" + "position %d, %g != %g\n",i,out[i],comp[i]); + exit(1); } }else{ if(out){ fprintf(stderr,"_book_unquantize returned a value array: \n" - " correct result should have been NULL\n"); + " correct result should have been NULL\n"); exit(1); } } @@ -734,7 +588,7 @@ int main(){ fprintf(stderr,"OK\nDequant test 5... "); run_test(&test5,test5_result); fprintf(stderr,"OK\n\n"); - + return(0); }