misc/libtremor/sharedbook.c
changeset 5170 f7e49eff3708
equal deleted inserted replaced
5169:e353ca78d28b 5170:f7e49eff3708
       
     1 /********************************************************************
       
     2  *                                                                  *
       
     3  * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE.   *
       
     4  *                                                                  *
       
     5  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
       
     6  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
       
     7  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
       
     8  *                                                                  *
       
     9  * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2002    *
       
    10  * BY THE Xiph.Org FOUNDATION http://www.xiph.org/                  *
       
    11  *                                                                  *
       
    12  ********************************************************************
       
    13 
       
    14  function: basic shared codebook operations
       
    15 
       
    16  ********************************************************************/
       
    17 
       
    18 #include <stdlib.h>
       
    19 #include <math.h>
       
    20 #include <string.h>
       
    21 #include "ogg.h"
       
    22 #include "misc.h"
       
    23 #include "ivorbiscodec.h"
       
    24 #include "codebook.h"
       
    25 
       
    26 /**** pack/unpack helpers ******************************************/
       
    27 int _ilog(unsigned int v){
       
    28   int ret=0;
       
    29   while(v){
       
    30     ret++;
       
    31     v>>=1;
       
    32   }
       
    33   return(ret);
       
    34 }
       
    35 
       
    36 /* 32 bit float (not IEEE; nonnormalized mantissa +
       
    37    biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm 
       
    38    Why not IEEE?  It's just not that important here. */
       
    39 
       
    40 #define VQ_FEXP 10
       
    41 #define VQ_FMAN 21
       
    42 #define VQ_FEXP_BIAS 768 /* bias toward values smaller than 1. */
       
    43 
       
    44 static ogg_int32_t _float32_unpack(long val,int *point){
       
    45   long   mant=val&0x1fffff;
       
    46   int    sign=val&0x80000000;
       
    47   long   exp =(val&0x7fe00000L)>>VQ_FMAN;
       
    48 
       
    49   exp-=(VQ_FMAN-1)+VQ_FEXP_BIAS;
       
    50 
       
    51   if(mant){
       
    52     while(!(mant&0x40000000)){
       
    53       mant<<=1;
       
    54       exp-=1;
       
    55     }
       
    56 
       
    57     if(sign)mant= -mant;
       
    58   }else{
       
    59     sign=0;
       
    60     exp=-9999;
       
    61   }
       
    62 
       
    63   *point=exp;
       
    64   return mant;
       
    65 }
       
    66 
       
    67 /* given a list of word lengths, generate a list of codewords.  Works
       
    68    for length ordered or unordered, always assigns the lowest valued
       
    69    codewords first.  Extended to handle unused entries (length 0) */
       
    70 ogg_uint32_t *_make_words(long *l,long n,long sparsecount){
       
    71   long i,j,count=0;
       
    72   ogg_uint32_t marker[33];
       
    73   ogg_uint32_t *r=(ogg_uint32_t *)_ogg_malloc((sparsecount?sparsecount:n)*sizeof(*r));
       
    74   memset(marker,0,sizeof(marker));
       
    75 
       
    76   for(i=0;i<n;i++){
       
    77     long length=l[i];
       
    78     if(length>0){
       
    79       ogg_uint32_t entry=marker[length];
       
    80       
       
    81       /* when we claim a node for an entry, we also claim the nodes
       
    82 	 below it (pruning off the imagined tree that may have dangled
       
    83 	 from it) as well as blocking the use of any nodes directly
       
    84 	 above for leaves */
       
    85       
       
    86       /* update ourself */
       
    87       if(length<32 && (entry>>length)){
       
    88 	/* error condition; the lengths must specify an overpopulated tree */
       
    89 	_ogg_free(r);
       
    90 	return(NULL);
       
    91       }
       
    92       r[count++]=entry;
       
    93     
       
    94       /* Look to see if the next shorter marker points to the node
       
    95 	 above. if so, update it and repeat.  */
       
    96       {
       
    97 	for(j=length;j>0;j--){
       
    98 	  
       
    99 	  if(marker[j]&1){
       
   100 	    /* have to jump branches */
       
   101 	    if(j==1)
       
   102 	      marker[1]++;
       
   103 	    else
       
   104 	      marker[j]=marker[j-1]<<1;
       
   105 	    break; /* invariant says next upper marker would already
       
   106 		      have been moved if it was on the same path */
       
   107 	  }
       
   108 	  marker[j]++;
       
   109 	}
       
   110       }
       
   111       
       
   112       /* prune the tree; the implicit invariant says all the longer
       
   113 	 markers were dangling from our just-taken node.  Dangle them
       
   114 	 from our *new* node. */
       
   115       for(j=length+1;j<33;j++)
       
   116 	if((marker[j]>>1) == entry){
       
   117 	  entry=marker[j];
       
   118 	  marker[j]=marker[j-1]<<1;
       
   119 	}else
       
   120 	  break;
       
   121     }else
       
   122       if(sparsecount==0)count++;
       
   123   }
       
   124     
       
   125   /* bitreverse the words because our bitwise packer/unpacker is LSb
       
   126      endian */
       
   127   for(i=0,count=0;i<n;i++){
       
   128     ogg_uint32_t temp=0;
       
   129     for(j=0;j<l[i];j++){
       
   130       temp<<=1;
       
   131       temp|=(r[count]>>j)&1;
       
   132     }
       
   133 
       
   134     if(sparsecount){
       
   135       if(l[i])
       
   136 	r[count++]=temp;
       
   137     }else
       
   138       r[count++]=temp;
       
   139   }
       
   140 
       
   141   return(r);
       
   142 }
       
   143 
       
   144 /* there might be a straightforward one-line way to do the below
       
   145    that's portable and totally safe against roundoff, but I haven't
       
   146    thought of it.  Therefore, we opt on the side of caution */
       
   147 long _book_maptype1_quantvals(const static_codebook *b){
       
   148   /* get us a starting hint, we'll polish it below */
       
   149   int bits=_ilog(b->entries);
       
   150   int vals=b->entries>>((bits-1)*(b->dim-1)/b->dim);
       
   151 
       
   152   while(1){
       
   153     long acc=1;
       
   154     long acc1=1;
       
   155     int i;
       
   156     for(i=0;i<b->dim;i++){
       
   157       acc*=vals;
       
   158       acc1*=vals+1;
       
   159     }
       
   160     if(acc<=b->entries && acc1>b->entries){
       
   161       return(vals);
       
   162     }else{
       
   163       if(acc>b->entries){
       
   164 	vals--;
       
   165       }else{
       
   166 	vals++;
       
   167       }
       
   168     }
       
   169   }
       
   170 }
       
   171 
       
   172 /* different than what _book_unquantize does for mainline:
       
   173    we repack the book in a fixed point format that shares the same
       
   174    binary point.  Upon first use, we can shift point if needed */
       
   175 
       
   176 /* we need to deal with two map types: in map type 1, the values are
       
   177    generated algorithmically (each column of the vector counts through
       
   178    the values in the quant vector). in map type 2, all the values came
       
   179    in in an explicit list.  Both value lists must be unpacked */
       
   180 
       
   181 ogg_int32_t *_book_unquantize(const static_codebook *b,int n,int *sparsemap,
       
   182 			      int *maxpoint){
       
   183   long j,k,count=0;
       
   184   if(b->maptype==1 || b->maptype==2){
       
   185     int quantvals;
       
   186     int minpoint,delpoint;
       
   187     ogg_int32_t mindel=_float32_unpack(b->q_min,&minpoint);
       
   188     ogg_int32_t delta=_float32_unpack(b->q_delta,&delpoint);
       
   189     ogg_int32_t *r=(ogg_int32_t *)_ogg_calloc(n*b->dim,sizeof(*r));
       
   190     int *rp=(int *)_ogg_calloc(n*b->dim,sizeof(*rp));
       
   191 
       
   192     *maxpoint=minpoint;
       
   193 
       
   194     /* maptype 1 and 2 both use a quantized value vector, but
       
   195        different sizes */
       
   196     switch(b->maptype){
       
   197     case 1:
       
   198       /* most of the time, entries%dimensions == 0, but we need to be
       
   199 	 well defined.  We define that the possible vales at each
       
   200 	 scalar is values == entries/dim.  If entries%dim != 0, we'll
       
   201 	 have 'too few' values (values*dim<entries), which means that
       
   202 	 we'll have 'left over' entries; left over entries use zeroed
       
   203 	 values (and are wasted).  So don't generate codebooks like
       
   204 	 that */
       
   205       quantvals=_book_maptype1_quantvals(b);
       
   206       for(j=0;j<b->entries;j++){
       
   207 	if((sparsemap && b->lengthlist[j]) || !sparsemap){
       
   208 	  ogg_int32_t last=0;
       
   209 	  int lastpoint=0;
       
   210 	  int indexdiv=1;
       
   211 	  for(k=0;k<b->dim;k++){
       
   212 	    int index= (j/indexdiv)%quantvals;
       
   213 	    int point=0;
       
   214 	    int val=VFLOAT_MULTI(delta,delpoint,
       
   215 				 abs(b->quantlist[index]),&point);
       
   216 
       
   217 	    val=VFLOAT_ADD(mindel,minpoint,val,point,&point);
       
   218 	    val=VFLOAT_ADD(last,lastpoint,val,point,&point);
       
   219 	    
       
   220 	    if(b->q_sequencep){
       
   221 	      last=val;	  
       
   222 	      lastpoint=point;
       
   223 	    }
       
   224 	    
       
   225 	    if(sparsemap){
       
   226 	      r[sparsemap[count]*b->dim+k]=val;
       
   227 	      rp[sparsemap[count]*b->dim+k]=point;
       
   228 	    }else{
       
   229 	      r[count*b->dim+k]=val;
       
   230 	      rp[count*b->dim+k]=point;
       
   231 	    }
       
   232 	    if(*maxpoint<point)*maxpoint=point;
       
   233 	    indexdiv*=quantvals;
       
   234 	  }
       
   235 	  count++;
       
   236 	}
       
   237 
       
   238       }
       
   239       break;
       
   240     case 2:
       
   241       for(j=0;j<b->entries;j++){
       
   242 	if((sparsemap && b->lengthlist[j]) || !sparsemap){
       
   243 	  ogg_int32_t last=0;
       
   244 	  int         lastpoint=0;
       
   245 
       
   246 	  for(k=0;k<b->dim;k++){
       
   247 	    int point=0;
       
   248 	    int val=VFLOAT_MULTI(delta,delpoint,
       
   249 				 abs(b->quantlist[j*b->dim+k]),&point);
       
   250 
       
   251 	    val=VFLOAT_ADD(mindel,minpoint,val,point,&point);
       
   252 	    val=VFLOAT_ADD(last,lastpoint,val,point,&point);
       
   253 	    
       
   254 	    if(b->q_sequencep){
       
   255 	      last=val;	  
       
   256 	      lastpoint=point;
       
   257 	    }
       
   258 
       
   259 	    if(sparsemap){
       
   260 	      r[sparsemap[count]*b->dim+k]=val;
       
   261 	      rp[sparsemap[count]*b->dim+k]=point;
       
   262 	    }else{
       
   263 	      r[count*b->dim+k]=val;
       
   264 	      rp[count*b->dim+k]=point;
       
   265 	    }
       
   266 	    if(*maxpoint<point)*maxpoint=point;
       
   267 	  }
       
   268 	  count++;
       
   269 	}
       
   270       }
       
   271       break;
       
   272     }
       
   273 
       
   274     for(j=0;j<n*b->dim;j++)
       
   275       if(rp[j]<*maxpoint)
       
   276 	r[j]>>=*maxpoint-rp[j];
       
   277 	    
       
   278     _ogg_free(rp);
       
   279     return(r);
       
   280   }
       
   281   return(NULL);
       
   282 }
       
   283 
       
   284 void vorbis_staticbook_clear(static_codebook *b){
       
   285   if(b->quantlist)_ogg_free(b->quantlist);
       
   286   if(b->lengthlist)_ogg_free(b->lengthlist);
       
   287   memset(b,0,sizeof(*b));
       
   288 
       
   289 }
       
   290 
       
   291 void vorbis_staticbook_destroy(static_codebook *b){
       
   292   vorbis_staticbook_clear(b);
       
   293   _ogg_free(b);
       
   294 }
       
   295 
       
   296 void vorbis_book_clear(codebook *b){
       
   297   /* static book is not cleared; we're likely called on the lookup and
       
   298      the static codebook belongs to the info struct */
       
   299   if(b->valuelist)_ogg_free(b->valuelist);
       
   300   if(b->codelist)_ogg_free(b->codelist);
       
   301 
       
   302   if(b->dec_index)_ogg_free(b->dec_index);
       
   303   if(b->dec_codelengths)_ogg_free(b->dec_codelengths);
       
   304   if(b->dec_firsttable)_ogg_free(b->dec_firsttable);
       
   305 
       
   306   memset(b,0,sizeof(*b));
       
   307 }
       
   308 
       
   309 static ogg_uint32_t bitreverse(ogg_uint32_t x){
       
   310   x=    ((x>>16)&0x0000ffffUL) | ((x<<16)&0xffff0000UL);
       
   311   x=    ((x>> 8)&0x00ff00ffUL) | ((x<< 8)&0xff00ff00UL);
       
   312   x=    ((x>> 4)&0x0f0f0f0fUL) | ((x<< 4)&0xf0f0f0f0UL);
       
   313   x=    ((x>> 2)&0x33333333UL) | ((x<< 2)&0xccccccccUL);
       
   314   return((x>> 1)&0x55555555UL) | ((x<< 1)&0xaaaaaaaaUL);
       
   315 }
       
   316 
       
   317 static int sort32a(const void *a,const void *b){
       
   318   return (**(ogg_uint32_t **)a>**(ogg_uint32_t **)b)-
       
   319     (**(ogg_uint32_t **)a<**(ogg_uint32_t **)b);
       
   320 }
       
   321 
       
   322 /* decode codebook arrangement is more heavily optimized than encode */
       
   323 int vorbis_book_init_decode(codebook *c,const static_codebook *s){
       
   324   int i,j,n=0,tabn;
       
   325   int *sortindex;
       
   326   memset(c,0,sizeof(*c));
       
   327   
       
   328   /* count actually used entries */
       
   329   for(i=0;i<s->entries;i++)
       
   330     if(s->lengthlist[i]>0)
       
   331       n++;
       
   332 
       
   333   c->entries=s->entries;
       
   334   c->used_entries=n;
       
   335   c->dim=s->dim;
       
   336 
       
   337   if(n>0){
       
   338     /* two different remappings go on here.  
       
   339        
       
   340        First, we collapse the likely sparse codebook down only to
       
   341        actually represented values/words.  This collapsing needs to be
       
   342        indexed as map-valueless books are used to encode original entry
       
   343        positions as integers.
       
   344        
       
   345        Second, we reorder all vectors, including the entry index above,
       
   346        by sorted bitreversed codeword to allow treeless decode. */
       
   347     
       
   348     /* perform sort */
       
   349     ogg_uint32_t *codes=_make_words(s->lengthlist,s->entries,c->used_entries);
       
   350     ogg_uint32_t **codep=(ogg_uint32_t **)alloca(sizeof(*codep)*n);
       
   351     
       
   352     if(codes==NULL)goto err_out;
       
   353 
       
   354     for(i=0;i<n;i++){
       
   355       codes[i]=bitreverse(codes[i]);
       
   356       codep[i]=codes+i;
       
   357     }
       
   358 
       
   359     qsort(codep,n,sizeof(*codep),sort32a);
       
   360 
       
   361     sortindex=(int *)alloca(n*sizeof(*sortindex));
       
   362     c->codelist=(ogg_uint32_t *)_ogg_malloc(n*sizeof(*c->codelist));
       
   363     /* the index is a reverse index */
       
   364     for(i=0;i<n;i++){
       
   365       int position=codep[i]-codes;
       
   366       sortindex[position]=i;
       
   367     }
       
   368 
       
   369     for(i=0;i<n;i++)
       
   370       c->codelist[sortindex[i]]=codes[i];
       
   371     _ogg_free(codes);
       
   372     
       
   373     
       
   374     
       
   375     c->valuelist=_book_unquantize(s,n,sortindex,&c->binarypoint);
       
   376     c->dec_index=(int *)_ogg_malloc(n*sizeof(*c->dec_index));
       
   377     
       
   378     for(n=0,i=0;i<s->entries;i++)
       
   379       if(s->lengthlist[i]>0)
       
   380 	c->dec_index[sortindex[n++]]=i;
       
   381     
       
   382     c->dec_codelengths=(char *)_ogg_malloc(n*sizeof(*c->dec_codelengths));
       
   383     for(n=0,i=0;i<s->entries;i++)
       
   384       if(s->lengthlist[i]>0)
       
   385 	c->dec_codelengths[sortindex[n++]]=s->lengthlist[i];
       
   386     
       
   387     c->dec_firsttablen=_ilog(c->used_entries)-4; /* this is magic */
       
   388     if(c->dec_firsttablen<5)c->dec_firsttablen=5;
       
   389     if(c->dec_firsttablen>8)c->dec_firsttablen=8;
       
   390     
       
   391     tabn=1<<c->dec_firsttablen;
       
   392     c->dec_firsttable=(ogg_uint32_t *)_ogg_calloc(tabn,sizeof(*c->dec_firsttable));
       
   393     c->dec_maxlength=0;
       
   394     
       
   395     for(i=0;i<n;i++){
       
   396       if(c->dec_maxlength<c->dec_codelengths[i])
       
   397 	c->dec_maxlength=c->dec_codelengths[i];
       
   398       if(c->dec_codelengths[i]<=c->dec_firsttablen){
       
   399 	ogg_uint32_t orig=bitreverse(c->codelist[i]);
       
   400 	for(j=0;j<(1<<(c->dec_firsttablen-c->dec_codelengths[i]));j++)
       
   401 	  c->dec_firsttable[orig|(j<<c->dec_codelengths[i])]=i+1;
       
   402       }
       
   403     }
       
   404     
       
   405     /* now fill in 'unused' entries in the firsttable with hi/lo search
       
   406        hints for the non-direct-hits */
       
   407     {
       
   408       ogg_uint32_t mask=0xfffffffeUL<<(31-c->dec_firsttablen);
       
   409       long lo=0,hi=0;
       
   410       
       
   411       for(i=0;i<tabn;i++){
       
   412 	ogg_uint32_t word=i<<(32-c->dec_firsttablen);
       
   413 	if(c->dec_firsttable[bitreverse(word)]==0){
       
   414 	  while((lo+1)<n && c->codelist[lo+1]<=word)lo++;
       
   415 	  while(    hi<n && word>=(c->codelist[hi]&mask))hi++;
       
   416 	  
       
   417 	  /* we only actually have 15 bits per hint to play with here.
       
   418 	     In order to overflow gracefully (nothing breaks, efficiency
       
   419 	     just drops), encode as the difference from the extremes. */
       
   420 	  {
       
   421 	    unsigned long loval=lo;
       
   422 	    unsigned long hival=n-hi;
       
   423 	    
       
   424 	    if(loval>0x7fff)loval=0x7fff;
       
   425 	    if(hival>0x7fff)hival=0x7fff;
       
   426 	    c->dec_firsttable[bitreverse(word)]=
       
   427 	      0x80000000UL | (loval<<15) | hival;
       
   428 	  }
       
   429 	}
       
   430       }
       
   431     }
       
   432   }
       
   433 
       
   434   return(0);
       
   435  err_out:
       
   436   vorbis_book_clear(c);
       
   437   return(-1);
       
   438 }
       
   439