michael@0: /********************************************************************
michael@0:  *                                                                  *
michael@0:  * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE.   *
michael@0:  *                                                                  *
michael@0:  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
michael@0:  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
michael@0:  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
michael@0:  *                                                                  *
michael@0:  * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2002    *
michael@0:  * BY THE Xiph.Org FOUNDATION http://www.xiph.org/                  *
michael@0:  *                                                                  *
michael@0:  ********************************************************************
michael@0: 
michael@0:  function: basic shared codebook operations
michael@0: 
michael@0:  ********************************************************************/
michael@0: 
michael@0: #include <stdlib.h>
michael@0: #include <math.h>
michael@0: #include <string.h>
michael@0: #include <ogg/ogg.h>
michael@0: #include "misc.h"
michael@0: #include "ivorbiscodec.h"
michael@0: #include "codebook.h"
michael@0: 
michael@0: /**** pack/unpack helpers ******************************************/
michael@0: int _ilog(unsigned int v){
michael@0:   int ret=0;
michael@0:   while(v){
michael@0:     ret++;
michael@0:     v>>=1;
michael@0:   }
michael@0:   return(ret);
michael@0: }
michael@0: 
michael@0: /* 32 bit float (not IEEE; nonnormalized mantissa +
michael@0:    biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm 
michael@0:    Why not IEEE?  It's just not that important here. */
michael@0: 
michael@0: #define VQ_FEXP 10
michael@0: #define VQ_FMAN 21
michael@0: #define VQ_FEXP_BIAS 768 /* bias toward values smaller than 1. */
michael@0: 
michael@0: static ogg_int32_t _float32_unpack(long val,int *point){
michael@0:   long   mant=val&0x1fffff;
michael@0:   int    sign=val&0x80000000;
michael@0:   long   exp =(val&0x7fe00000L)>>VQ_FMAN;
michael@0: 
michael@0:   exp-=(VQ_FMAN-1)+VQ_FEXP_BIAS;
michael@0: 
michael@0:   if(mant){
michael@0:     while(!(mant&0x40000000)){
michael@0:       mant<<=1;
michael@0:       exp-=1;
michael@0:     }
michael@0: 
michael@0:     if(sign)mant= -mant;
michael@0:   }else{
michael@0:     sign=0;
michael@0:     exp=-9999;
michael@0:   }
michael@0: 
michael@0:   *point=exp;
michael@0:   return mant;
michael@0: }
michael@0: 
michael@0: /* given a list of word lengths, generate a list of codewords.  Works
michael@0:    for length ordered or unordered, always assigns the lowest valued
michael@0:    codewords first.  Extended to handle unused entries (length 0) */
michael@0: ogg_uint32_t *_make_words(long *l,long n,long sparsecount){
michael@0:   long i,j,count=0;
michael@0:   ogg_uint32_t marker[33];
michael@0:   ogg_uint32_t *r=(ogg_uint32_t *)_ogg_malloc((sparsecount?sparsecount:n)*sizeof(*r));
michael@0:   memset(marker,0,sizeof(marker));
michael@0: 
michael@0:   for(i=0;i<n;i++){
michael@0:     long length=l[i];
michael@0:     if(length>0){
michael@0:       ogg_uint32_t entry=marker[length];
michael@0:       
michael@0:       /* when we claim a node for an entry, we also claim the nodes
michael@0: 	 below it (pruning off the imagined tree that may have dangled
michael@0: 	 from it) as well as blocking the use of any nodes directly
michael@0: 	 above for leaves */
michael@0:       
michael@0:       /* update ourself */
michael@0:       if(length<32 && (entry>>length)){
michael@0: 	/* error condition; the lengths must specify an overpopulated tree */
michael@0: 	_ogg_free(r);
michael@0: 	return(NULL);
michael@0:       }
michael@0:       r[count++]=entry;
michael@0:     
michael@0:       /* Look to see if the next shorter marker points to the node
michael@0: 	 above. if so, update it and repeat.  */
michael@0:       {
michael@0: 	for(j=length;j>0;j--){
michael@0: 	  
michael@0: 	  if(marker[j]&1){
michael@0: 	    /* have to jump branches */
michael@0: 	    if(j==1)
michael@0: 	      marker[1]++;
michael@0: 	    else
michael@0: 	      marker[j]=marker[j-1]<<1;
michael@0: 	    break; /* invariant says next upper marker would already
michael@0: 		      have been moved if it was on the same path */
michael@0: 	  }
michael@0: 	  marker[j]++;
michael@0: 	}
michael@0:       }
michael@0:       
michael@0:       /* prune the tree; the implicit invariant says all the longer
michael@0: 	 markers were dangling from our just-taken node.  Dangle them
michael@0: 	 from our *new* node. */
michael@0:       for(j=length+1;j<33;j++)
michael@0: 	if((marker[j]>>1) == entry){
michael@0: 	  entry=marker[j];
michael@0: 	  marker[j]=marker[j-1]<<1;
michael@0: 	}else
michael@0: 	  break;
michael@0:     }else
michael@0:       if(sparsecount==0)count++;
michael@0:   }
michael@0: 
michael@0:   /* sanity check the huffman tree; an underpopulated tree must be
michael@0:      rejected. The only exception is the one-node pseudo-nil tree,
michael@0:      which appears to be underpopulated because the tree doesn't
michael@0:      really exist; there's only one possible 'codeword' or zero bits,
michael@0:      but the above tree-gen code doesn't mark that. */
michael@0:   if(sparsecount != 1){
michael@0:     for(i=1;i<33;i++)
michael@0:       if(marker[i] & (0xffffffffUL>>(32-i))){
michael@0:        _ogg_free(r);
michael@0:        return(NULL);
michael@0:       }
michael@0:   }
michael@0: 
michael@0:   /* bitreverse the words because our bitwise packer/unpacker is LSb
michael@0:      endian */
michael@0:   for(i=0,count=0;i<n;i++){
michael@0:     ogg_uint32_t temp=0;
michael@0:     for(j=0;j<l[i];j++){
michael@0:       temp<<=1;
michael@0:       temp|=(r[count]>>j)&1;
michael@0:     }
michael@0: 
michael@0:     if(sparsecount){
michael@0:       if(l[i])
michael@0: 	r[count++]=temp;
michael@0:     }else
michael@0:       r[count++]=temp;
michael@0:   }
michael@0: 
michael@0:   return(r);
michael@0: }
michael@0: 
michael@0: /* there might be a straightforward one-line way to do the below
michael@0:    that's portable and totally safe against roundoff, but I haven't
michael@0:    thought of it.  Therefore, we opt on the side of caution */
michael@0: long _book_maptype1_quantvals(const static_codebook *b){
michael@0:   /* get us a starting hint, we'll polish it below */
michael@0:   int bits=_ilog(b->entries);
michael@0:   int vals=b->entries>>((bits-1)*(b->dim-1)/b->dim);
michael@0: 
michael@0:   while(1){
michael@0:     long acc=1;
michael@0:     long acc1=1;
michael@0:     int i;
michael@0:     for(i=0;i<b->dim;i++){
michael@0:       acc*=vals;
michael@0:       acc1*=vals+1;
michael@0:     }
michael@0:     if(acc<=b->entries && acc1>b->entries){
michael@0:       return(vals);
michael@0:     }else{
michael@0:       if(acc>b->entries){
michael@0: 	vals--;
michael@0:       }else{
michael@0: 	vals++;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: }
michael@0: 
michael@0: /* different than what _book_unquantize does for mainline:
michael@0:    we repack the book in a fixed point format that shares the same
michael@0:    binary point.  Upon first use, we can shift point if needed */
michael@0: 
michael@0: /* we need to deal with two map types: in map type 1, the values are
michael@0:    generated algorithmically (each column of the vector counts through
michael@0:    the values in the quant vector). in map type 2, all the values came
michael@0:    in in an explicit list.  Both value lists must be unpacked */
michael@0: 
michael@0: ogg_int32_t *_book_unquantize(const static_codebook *b,int n,int *sparsemap,
michael@0: 			      int *maxpoint){
michael@0:   long j,k,count=0;
michael@0:   if(b->maptype==1 || b->maptype==2){
michael@0:     int quantvals;
michael@0:     int minpoint,delpoint;
michael@0:     ogg_int32_t mindel=_float32_unpack(b->q_min,&minpoint);
michael@0:     ogg_int32_t delta=_float32_unpack(b->q_delta,&delpoint);
michael@0:     ogg_int32_t *r=(ogg_int32_t *)_ogg_calloc(n*b->dim,sizeof(*r));
michael@0:     int *rp=(int *)_ogg_calloc(n*b->dim,sizeof(*rp));
michael@0: 
michael@0:     *maxpoint=minpoint;
michael@0: 
michael@0:     /* maptype 1 and 2 both use a quantized value vector, but
michael@0:        different sizes */
michael@0:     switch(b->maptype){
michael@0:     case 1:
michael@0:       /* most of the time, entries%dimensions == 0, but we need to be
michael@0: 	 well defined.  We define that the possible vales at each
michael@0: 	 scalar is values == entries/dim.  If entries%dim != 0, we'll
michael@0: 	 have 'too few' values (values*dim<entries), which means that
michael@0: 	 we'll have 'left over' entries; left over entries use zeroed
michael@0: 	 values (and are wasted).  So don't generate codebooks like
michael@0: 	 that */
michael@0:       quantvals=_book_maptype1_quantvals(b);
michael@0:       for(j=0;j<b->entries;j++){
michael@0: 	if((sparsemap && b->lengthlist[j]) || !sparsemap){
michael@0: 	  ogg_int32_t last=0;
michael@0: 	  int lastpoint=0;
michael@0: 	  int indexdiv=1;
michael@0: 	  for(k=0;k<b->dim;k++){
michael@0: 	    int index= (j/indexdiv)%quantvals;
michael@0: 	    int point=0;
michael@0: 	    int val=VFLOAT_MULTI(delta,delpoint,
michael@0: 				 abs(b->quantlist[index]),&point);
michael@0: 
michael@0: 	    val=VFLOAT_ADD(mindel,minpoint,val,point,&point);
michael@0: 	    val=VFLOAT_ADD(last,lastpoint,val,point,&point);
michael@0: 	    
michael@0: 	    if(b->q_sequencep){
michael@0: 	      last=val;	  
michael@0: 	      lastpoint=point;
michael@0: 	    }
michael@0: 	    
michael@0: 	    if(sparsemap){
michael@0: 	      r[sparsemap[count]*b->dim+k]=val;
michael@0: 	      rp[sparsemap[count]*b->dim+k]=point;
michael@0: 	    }else{
michael@0: 	      r[count*b->dim+k]=val;
michael@0: 	      rp[count*b->dim+k]=point;
michael@0: 	    }
michael@0: 	    if(*maxpoint<point)*maxpoint=point;
michael@0: 	    indexdiv*=quantvals;
michael@0: 	  }
michael@0: 	  count++;
michael@0: 	}
michael@0: 
michael@0:       }
michael@0:       break;
michael@0:     case 2:
michael@0:       for(j=0;j<b->entries;j++){
michael@0: 	if((sparsemap && b->lengthlist[j]) || !sparsemap){
michael@0: 	  ogg_int32_t last=0;
michael@0: 	  int         lastpoint=0;
michael@0: 
michael@0: 	  for(k=0;k<b->dim;k++){
michael@0: 	    int point=0;
michael@0: 	    int val=VFLOAT_MULTI(delta,delpoint,
michael@0: 				 abs(b->quantlist[j*b->dim+k]),&point);
michael@0: 
michael@0: 	    val=VFLOAT_ADD(mindel,minpoint,val,point,&point);
michael@0: 	    val=VFLOAT_ADD(last,lastpoint,val,point,&point);
michael@0: 	    
michael@0: 	    if(b->q_sequencep){
michael@0: 	      last=val;	  
michael@0: 	      lastpoint=point;
michael@0: 	    }
michael@0: 
michael@0: 	    if(sparsemap){
michael@0: 	      r[sparsemap[count]*b->dim+k]=val;
michael@0: 	      rp[sparsemap[count]*b->dim+k]=point;
michael@0: 	    }else{
michael@0: 	      r[count*b->dim+k]=val;
michael@0: 	      rp[count*b->dim+k]=point;
michael@0: 	    }
michael@0: 	    if(*maxpoint<point)*maxpoint=point;
michael@0: 	  }
michael@0: 	  count++;
michael@0: 	}
michael@0:       }
michael@0:       break;
michael@0:     }
michael@0: 
michael@0:     for(j=0;j<n*b->dim;j++)
michael@0:       if(rp[j]<*maxpoint)
michael@0: 	r[j]>>=*maxpoint-rp[j];
michael@0: 	    
michael@0:     _ogg_free(rp);
michael@0:     return(r);
michael@0:   }
michael@0:   return(NULL);
michael@0: }
michael@0: 
michael@0: void vorbis_staticbook_destroy(static_codebook *b){
michael@0:   if(b->quantlist)_ogg_free(b->quantlist);
michael@0:   if(b->lengthlist)_ogg_free(b->lengthlist);
michael@0:   memset(b,0,sizeof(*b));
michael@0:   _ogg_free(b);
michael@0: }
michael@0: 
michael@0: void vorbis_book_clear(codebook *b){
michael@0:   /* static book is not cleared; we're likely called on the lookup and
michael@0:      the static codebook belongs to the info struct */
michael@0:   if(b->valuelist)_ogg_free(b->valuelist);
michael@0:   if(b->codelist)_ogg_free(b->codelist);
michael@0: 
michael@0:   if(b->dec_index)_ogg_free(b->dec_index);
michael@0:   if(b->dec_codelengths)_ogg_free(b->dec_codelengths);
michael@0:   if(b->dec_firsttable)_ogg_free(b->dec_firsttable);
michael@0: 
michael@0:   memset(b,0,sizeof(*b));
michael@0: }
michael@0: 
michael@0: static ogg_uint32_t bitreverse(ogg_uint32_t x){
michael@0:   x=    ((x>>16)&0x0000ffffUL) | ((x<<16)&0xffff0000UL);
michael@0:   x=    ((x>> 8)&0x00ff00ffUL) | ((x<< 8)&0xff00ff00UL);
michael@0:   x=    ((x>> 4)&0x0f0f0f0fUL) | ((x<< 4)&0xf0f0f0f0UL);
michael@0:   x=    ((x>> 2)&0x33333333UL) | ((x<< 2)&0xccccccccUL);
michael@0:   return((x>> 1)&0x55555555UL) | ((x<< 1)&0xaaaaaaaaUL);
michael@0: }
michael@0: 
michael@0: static int sort32a(const void *a,const void *b){
michael@0:   return (**(ogg_uint32_t **)a>**(ogg_uint32_t **)b)-
michael@0:     (**(ogg_uint32_t **)a<**(ogg_uint32_t **)b);
michael@0: }
michael@0: 
michael@0: /* decode codebook arrangement is more heavily optimized than encode */
michael@0: int vorbis_book_init_decode(codebook *c,const static_codebook *s){
michael@0:   int i,j,n=0,tabn;
michael@0:   int *sortindex;
michael@0:   memset(c,0,sizeof(*c));
michael@0:   
michael@0:   /* count actually used entries */
michael@0:   for(i=0;i<s->entries;i++)
michael@0:     if(s->lengthlist[i]>0)
michael@0:       n++;
michael@0: 
michael@0:   c->entries=s->entries;
michael@0:   c->used_entries=n;
michael@0:   c->dim=s->dim;
michael@0: 
michael@0:   if(n>0){
michael@0:     /* two different remappings go on here.  
michael@0:        
michael@0:        First, we collapse the likely sparse codebook down only to
michael@0:        actually represented values/words.  This collapsing needs to be
michael@0:        indexed as map-valueless books are used to encode original entry
michael@0:        positions as integers.
michael@0:        
michael@0:        Second, we reorder all vectors, including the entry index above,
michael@0:        by sorted bitreversed codeword to allow treeless decode. */
michael@0:     
michael@0:     /* perform sort */
michael@0:     ogg_uint32_t *codes=_make_words(s->lengthlist,s->entries,c->used_entries);
michael@0:     ogg_uint32_t **codep=(ogg_uint32_t **)alloca(sizeof(*codep)*n);
michael@0:     
michael@0:     if(codes==NULL)goto err_out;
michael@0: 
michael@0:     for(i=0;i<n;i++){
michael@0:       codes[i]=bitreverse(codes[i]);
michael@0:       codep[i]=codes+i;
michael@0:     }
michael@0: 
michael@0:     qsort(codep,n,sizeof(*codep),sort32a);
michael@0: 
michael@0:     sortindex=(int *)alloca(n*sizeof(*sortindex));
michael@0:     c->codelist=(ogg_uint32_t *)_ogg_malloc(n*sizeof(*c->codelist));
michael@0:     /* the index is a reverse index */
michael@0:     for(i=0;i<n;i++){
michael@0:       int position=codep[i]-codes;
michael@0:       sortindex[position]=i;
michael@0:     }
michael@0: 
michael@0:     for(i=0;i<n;i++)
michael@0:       c->codelist[sortindex[i]]=codes[i];
michael@0:     _ogg_free(codes);
michael@0:     
michael@0:     
michael@0:     
michael@0:     c->valuelist=_book_unquantize(s,n,sortindex,&c->binarypoint);
michael@0:     c->dec_index=(int *)_ogg_malloc(n*sizeof(*c->dec_index));
michael@0:     
michael@0:     for(n=0,i=0;i<s->entries;i++)
michael@0:       if(s->lengthlist[i]>0)
michael@0: 	c->dec_index[sortindex[n++]]=i;
michael@0:     
michael@0:     c->dec_codelengths=(char *)_ogg_malloc(n*sizeof(*c->dec_codelengths));
michael@0:     for(n=0,i=0;i<s->entries;i++)
michael@0:       if(s->lengthlist[i]>0)
michael@0: 	c->dec_codelengths[sortindex[n++]]=s->lengthlist[i];
michael@0:     
michael@0:     c->dec_firsttablen=_ilog(c->used_entries)-4; /* this is magic */
michael@0:     if(c->dec_firsttablen<5)c->dec_firsttablen=5;
michael@0:     if(c->dec_firsttablen>8)c->dec_firsttablen=8;
michael@0:     
michael@0:     tabn=1<<c->dec_firsttablen;
michael@0:     c->dec_firsttable=(ogg_uint32_t *)_ogg_calloc(tabn,sizeof(*c->dec_firsttable));
michael@0:     c->dec_maxlength=0;
michael@0:     
michael@0:     for(i=0;i<n;i++){
michael@0:       if(c->dec_maxlength<c->dec_codelengths[i])
michael@0: 	c->dec_maxlength=c->dec_codelengths[i];
michael@0:       if(c->dec_codelengths[i]<=c->dec_firsttablen){
michael@0: 	ogg_uint32_t orig=bitreverse(c->codelist[i]);
michael@0: 	for(j=0;j<(1<<(c->dec_firsttablen-c->dec_codelengths[i]));j++)
michael@0: 	  c->dec_firsttable[orig|(j<<c->dec_codelengths[i])]=i+1;
michael@0:       }
michael@0:     }
michael@0:     
michael@0:     /* now fill in 'unused' entries in the firsttable with hi/lo search
michael@0:        hints for the non-direct-hits */
michael@0:     {
michael@0:       ogg_uint32_t mask=0xfffffffeUL<<(31-c->dec_firsttablen);
michael@0:       long lo=0,hi=0;
michael@0:       
michael@0:       for(i=0;i<tabn;i++){
michael@0: 	ogg_uint32_t word=i<<(32-c->dec_firsttablen);
michael@0: 	if(c->dec_firsttable[bitreverse(word)]==0){
michael@0: 	  while((lo+1)<n && c->codelist[lo+1]<=word)lo++;
michael@0: 	  while(    hi<n && word>=(c->codelist[hi]&mask))hi++;
michael@0: 	  
michael@0: 	  /* we only actually have 15 bits per hint to play with here.
michael@0: 	     In order to overflow gracefully (nothing breaks, efficiency
michael@0: 	     just drops), encode as the difference from the extremes. */
michael@0: 	  {
michael@0: 	    unsigned long loval=lo;
michael@0: 	    unsigned long hival=n-hi;
michael@0: 	    
michael@0: 	    if(loval>0x7fff)loval=0x7fff;
michael@0: 	    if(hival>0x7fff)hival=0x7fff;
michael@0: 	    c->dec_firsttable[bitreverse(word)]=
michael@0: 	      0x80000000UL | (loval<<15) | hival;
michael@0: 	  }
michael@0: 	}
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   return(0);
michael@0:  err_out:
michael@0:   vorbis_book_clear(c);
michael@0:   return(-1);
michael@0: }
michael@0: