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