X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=lib%2Fsharedbook.c;h=3c93d2d63e29912b26a866a3ef5ce3935eb8b3d6;hb=7e89d68b46200519edfd09196f672c29147c8d33;hp=7cc96b049a71d3d0e3402c36d0c6c4ac2e6f5ebb;hpb=6e6f1fbf6fda69be5419b8fe20180f8cad9f6513;p=platform%2Fupstream%2Flibvorbis.git

diff --git a/lib/sharedbook.c b/lib/sharedbook.c
index 7cc96b0..3c93d2d 100644
--- a/lib/sharedbook.c
+++ b/lib/sharedbook.c
@@ -5,17 +5,17 @@
  * 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-2009             *
+ * 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$
 
  ********************************************************************/
 
 #include <stdlib.h>
+#include <limits.h>
 #include <math.h>
 #include <string.h>
 #include <ogg/ogg.h>
@@ -26,13 +26,11 @@
 #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 +
@@ -52,7 +50,7 @@ long _float32_pack(float val){
     sign=0x80000000;
     val= -val;
   }
-  exp= floor(log(val)/log(2.f)+.001); //+epsilon
+  exp= floor(log(val)/log(2.f)+.001); /* +epsilon */
   mant=rint(ldexp(val,(VQ_FMAN-1)-exp));
   exp=(exp+VQ_FEXP_BIAS)<<VQ_FMAN;
 
@@ -64,13 +62,21 @@ float _float32_unpack(long val){
   int    sign=val&0x80000000;
   long   exp =(val&0x7fe00000L)>>VQ_FMAN;
   if(sign)mant= -mant;
-  return(ldexp(mant,exp-(VQ_FMAN-1)-VQ_FEXP_BIAS));
+  exp=exp-(VQ_FMAN-1)-VQ_FEXP_BIAS;
+  /* clamp excessive exponent values */
+  if (exp>63){
+    exp=63;
+  }
+  if (exp<-63){
+    exp-63;
+  }
+  return(ldexp(mant,exp));
 }
 
 /* given a list of word lengths, generate a list of codewords.  Works
    for length ordered or unordered, always assigns the lowest valued
    codewords first.  Extended to handle unused entries (length 0) */
-ogg_uint32_t *_make_words(long *l,long n,long sparsecount){
+ogg_uint32_t *_make_words(char *l,long n,long sparsecount){
   long i,j,count=0;
   ogg_uint32_t marker[33];
   ogg_uint32_t *r=_ogg_malloc((sparsecount?sparsecount:n)*sizeof(*r));
@@ -125,16 +131,15 @@ ogg_uint32_t *_make_words(long *l,long n,long sparsecount){
       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){
+  /* 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);
+        _ogg_free(r);
+        return(NULL);
       }
   }
 
@@ -161,25 +166,34 @@ ogg_uint32_t *_make_words(long *l,long n,long sparsecount){
    that's portable and totally safe against roundoff, but I haven't
    thought of it.  Therefore, we opt on the side of caution */
 long _book_maptype1_quantvals(const static_codebook *b){
-  long vals=floor(pow((float)b->entries,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;i<b->dim;i++){
+      if(b->entries/vals<acc)break;
       acc*=vals;
-      acc1*=vals+1;
+      if(LONG_MAX/(vals+1)<acc1)acc1=LONG_MAX;
+      else acc1*=vals+1;
     }
-    if(acc<=b->entries && acc1>b->entries){
+    if(i>=b->dim && acc<=b->entries && acc1>b->entries){
       return(vals);
     }else{
-      if(acc>b->entries){
+      if(i<b->dim || acc>b->entries){
         vals--;
       }else{
         vals++;
@@ -258,34 +272,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){
@@ -309,7 +302,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);
 }
@@ -331,9 +327,10 @@ static int sort32a(const void *a,const void *b){
 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;i<s->entries;i++)
     if(s->lengthlist[i]>0)
       n++;
@@ -343,7 +340,6 @@ int vorbis_book_init_decode(codebook *c,const static_codebook *s){
   c->dim=s->dim;
 
   if(n>0){
-
     /* two different remappings go on here.
 
     First, we collapse the likely sparse codebook down only to
@@ -379,7 +375,6 @@ int vorbis_book_init_decode(codebook *c,const static_codebook *s){
       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));
 
@@ -388,51 +383,62 @@ int vorbis_book_init_decode(codebook *c,const static_codebook *s){
         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)
+      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];
+      }
 
-    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<<c->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;i<n;i++){
-      if(c->dec_maxlength<c->dec_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<<c->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<<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;
+      /* 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;
+            }
           }
         }
       }
@@ -445,157 +451,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;i<el;i++){
-    float val=(ref[i]-b[i*step]);
-    acc+=val*val;
-  }
-  return(acc);
-}
-
-int _best(codebook *book, float *a, int step){
-  encode_aux_threshmatch *tt=book->c->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);k<dim;k++,o-=step){
-
-      i=tt->threshvals>>1;
-      if(a[o]<tt->quantthresh[i]){
-
-        for(;i>0;i--)
-          if(a[o]>=tt->quantthresh[i-1])
-            break;
-
-      }else{
-
-        for(i++;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);
-  }
-
-#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;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];
-      }
-    }
-
-    /* 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];
-        }
-      }
-
-      return(besti);
-    }
-  }
-
-  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;
-    }
-    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;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;
-        }
-      }
-      e+=dim;
-    }
-
-    /*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);
-  }
-}
-
 long vorbis_book_codeword(codebook *book,int entry){
   if(book->c) /* only use with encode; decode optimizations are
                  allowed to break this */
@@ -638,7 +493,6 @@ static_codebook test1={
   0,
   0,0,0,0,
   NULL,
-  NULL,NULL,NULL,
   0
 };
 static float *test1_result=NULL;
@@ -650,7 +504,6 @@ static_codebook test2={
   2,
   -533200896,1611661312,4,0,
   full_quantlist1,
-  NULL,NULL,NULL,
   0
 };
 static float test2_result[]={-3,-2,-1,0, 1,2,3,4, 5,0,3,-2};
@@ -662,7 +515,6 @@ static_codebook test3={
   2,
   -533200896,1611661312,4,1,
   full_quantlist1,
-  NULL,NULL,NULL,
   0
 };
 static float test3_result[]={-3,-5,-6,-6, 1,3,6,10, 5,5,8,6};
@@ -674,7 +526,6 @@ static_codebook test4={
   1,
   -533200896,1611661312,4,0,
   partial_quantlist1,
-  NULL,NULL,NULL,
   0
 };
 static float test4_result[]={-3,-3,-3, 4,-3,-3, -1,-3,-3,
@@ -694,7 +545,6 @@ static_codebook test5={
   1,
   -533200896,1611661312,4,1,
   partial_quantlist1,
-  NULL,NULL,NULL,
   0
 };
 static float test5_result[]={-3,-6,-9, 4, 1,-2, -1,-4,-7,