Tremor/sharedbook.c

   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