X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=lib%2Fsharedbook.c;h=d389f6759b5b3da8835033a2dfed1914e5a623a3;hb=6537cf8fe711a5eeef722c9840e39758e47f4f9d;hp=11c02f6aafc893754824845818858f9db970e9c7;hpb=19101bc6f97f56a962e2f8f869e1bb7671945db8;p=platform%2Fupstream%2Flibvorbis.git diff --git a/lib/sharedbook.c b/lib/sharedbook.c index 11c02f6..d389f67 100644 --- a/lib/sharedbook.c +++ b/lib/sharedbook.c @@ -5,13 +5,13 @@ * 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-2009 * + * by the Xiph.Org Foundation http://www.xiph.org/ * * * ******************************************************************** function: basic shared codebook operations - last mod: $Id: sharedbook.c,v 1.29 2002/10/11 07:44:28 xiphmont Exp $ + last mod: $Id$ ********************************************************************/ @@ -36,7 +36,7 @@ int _ilog(unsigned int v){ } /* 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 @@ -52,7 +52,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++; } - + + /* sanity check the huffman tree; an underpopulated tree must be + rejected. The only exception is the one-node pseudo-nil tree, + which appears to be underpopulated because the tree doesn't + really exist; there's only one possible 'codeword' or zero bits, + but the above tree-gen code doesn't mark that. */ + if(sparsecount != 1){ + 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;ib->entries){ - vals--; + vals--; }else{ - vals++; + vals++; } } } @@ -193,49 +206,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; } @@ -245,34 +258,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){ @@ -296,7 +288,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); } @@ -310,7 +305,7 @@ 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)- + return ( **(ogg_uint32_t **)a>**(ogg_uint32_t **)b)- ( **(ogg_uint32_t **)a<**(ogg_uint32_t **)b); } @@ -319,7 +314,7 @@ 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 */ for(i=0;ientries;i++) if(s->lengthlist[i]>0) @@ -329,21 +324,22 @@ 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)); - 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]; + c->valuelist=_book_unquantize(s,n,sortindex); + c->dec_index=_ogg_malloc(n*sizeof(*c->dec_index)); - 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; + for(n=0,i=0;ientries;i++) + if(s->lengthlist[i]>0) + c->dec_index[sortindex[n++]]=i; - tabn=1<dec_firsttablen; - c->dec_firsttable=_ogg_calloc(tabn,sizeof(*c->dec_firsttable)); - c->dec_maxlength=0; + 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(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; + 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; + + tabn=1<dec_firsttablen; + c->dec_firsttable=_ogg_calloc(tabn,sizeof(*c->dec_firsttable)); + c->dec_maxlength=0; + + 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; + } } - } - /* 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; - } + /* 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: @@ -431,157 +427,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->thresh_tree; - -#if 0 - encode_aux_nearestmatch *nt=book->c->nearest_tree; - encode_aux_pigeonhole *pt=book->c->pigeon_tree; -#endif - int dim=book->dim; - int k,o; - /*int savebest=-1; - float saverr;*/ - - /* do we have a threshhold encode hint? */ - if(tt){ - int index=0,i; - /* find the quant val of each scalar */ - for(k=0,o=step*(dim-1);kthreshvals>>1; - if(a[o]quantthresh[i]){ - - for(;i>0;i--) - if(a[o]>=tt->quantthresh[i-1]) - break; - - }else{ - - for(i++;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); - } - -#if 0 - /* 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); - } -#endif - - /* 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); - } -} - long vorbis_book_codeword(codebook *book,int entry){ if(book->c) /* only use with encode; decode optimizations are allowed to break this */ @@ -624,10 +469,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, @@ -635,7 +480,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}; @@ -646,7 +491,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}; @@ -657,17 +502,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={ @@ -676,17 +521,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); @@ -700,15 +545,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); } } @@ -727,7 +572,7 @@ int main(){ fprintf(stderr,"OK\nDequant test 5... "); run_test(&test5,test5_result); fprintf(stderr,"OK\n\n"); - + return(0); }