Dependencies/libvorbis/lib/codebook.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
   4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
   5  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
   6  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
   7  *                                                                  *
   8  * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2009             *
   9  * by the Xiph.Org Foundation http://www.xiph.org/                  *
  10  *                                                                  *
  11  ********************************************************************
  12
  13  function: basic codebook pack/unpack/code/decode operations
  14  last mod: $Id: codebook.c 17030 2010-03-25 06:52:55Z xiphmont $
  15
  16  ********************************************************************/
  17
  18 #include <stdlib.h>
  19 #include <string.h>
  20 #include <math.h>
  21 #include <ogg/ogg.h>
  22 #include "vorbis/codec.h"
  23 #include "codebook.h"
  24 #include "scales.h"
  25 #include "misc.h"
  26 #include "os.h"
  27
  28 /* packs the given codebook into the bitstream **************************/
  29
  30 int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
  31   long i,j;
  32   int ordered=0;
  33
  34   /* first the basic parameters */
  35   oggpack_write(opb,0x564342,24);
  36   oggpack_write(opb,c->dim,16);
  37   oggpack_write(opb,c->entries,24);
  38
  39   /* pack the codewords.  There are two packings; length ordered and
  40      length random.  Decide between the two now. */
  41
  42   for(i=1;i<c->entries;i++)
  43     if(c->lengthlist[i-1]==0 || c->lengthlist[i]<c->lengthlist[i-1])break;
  44   if(i==c->entries)ordered=1;
  45
  46   if(ordered){
  47     /* length ordered.  We only need to say how many codewords of
  48        each length.  The actual codewords are generated
  49        deterministically */
  50
  51     long count=0;
  52     oggpack_write(opb,1,1);  /* ordered */
  53     oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
  54
  55     for(i=1;i<c->entries;i++){
  56       long this=c->lengthlist[i];
  57       long last=c->lengthlist[i-1];
  58       if(this>last){
  59         for(j=last;j<this;j++){
  60           oggpack_write(opb,i-count,_ilog(c->entries-count));
  61           count=i;
  62         }
  63       }
  64     }
  65     oggpack_write(opb,i-count,_ilog(c->entries-count));
  66
  67   }else{
  68     /* length random.  Again, we don't code the codeword itself, just
  69        the length.  This time, though, we have to encode each length */
  70     oggpack_write(opb,0,1);   /* unordered */
  71
  72     /* algortihmic mapping has use for 'unused entries', which we tag
  73        here.  The algorithmic mapping happens as usual, but the unused
  74        entry has no codeword. */
  75     for(i=0;i<c->entries;i++)
  76       if(c->lengthlist[i]==0)break;
  77
  78     if(i==c->entries){
  79       oggpack_write(opb,0,1); /* no unused entries */
  80       for(i=0;i<c->entries;i++)
  81         oggpack_write(opb,c->lengthlist[i]-1,5);
  82     }else{
  83       oggpack_write(opb,1,1); /* we have unused entries; thus we tag */
  84       for(i=0;i<c->entries;i++){
  85         if(c->lengthlist[i]==0){
  86           oggpack_write(opb,0,1);
  87         }else{
  88           oggpack_write(opb,1,1);
  89           oggpack_write(opb,c->lengthlist[i]-1,5);
  90         }
  91       }
  92     }
  93   }
  94
  95   /* is the entry number the desired return value, or do we have a
  96      mapping? If we have a mapping, what type? */
  97   oggpack_write(opb,c->maptype,4);
  98   switch(c->maptype){
  99   case 0:
 100     /* no mapping */
 101     break;
 102   case 1:case 2:
 103     /* implicitly populated value mapping */
 104     /* explicitly populated value mapping */
 105
 106     if(!c->quantlist){
 107       /* no quantlist?  error */
 108       return(-1);
 109     }
 110
 111     /* values that define the dequantization */
 112     oggpack_write(opb,c->q_min,32);
 113     oggpack_write(opb,c->q_delta,32);
 114     oggpack_write(opb,c->q_quant-1,4);
 115     oggpack_write(opb,c->q_sequencep,1);
 116
 117     {
 118       int quantvals;
 119       switch(c->maptype){
 120       case 1:
 121         /* a single column of (c->entries/c->dim) quantized values for
 122            building a full value list algorithmically (square lattice) */
 123         quantvals=_book_maptype1_quantvals(c);
 124         break;
 125       case 2:
 126         /* every value (c->entries*c->dim total) specified explicitly */
 127         quantvals=c->entries*c->dim;
 128         break;
 129       default: /* NOT_REACHABLE */
 130         quantvals=-1;
 131       }
 132
 133       /* quantized values */
 134       for(i=0;i<quantvals;i++)
 135         oggpack_write(opb,labs(c->quantlist[i]),c->q_quant);
 136
 137     }
 138     break;
 139   default:
 140     /* error case; we don't have any other map types now */
 141     return(-1);
 142   }
 143
 144   return(0);
 145 }
 146
 147 /* unpacks a codebook from the packet buffer into the codebook struct,
 148    readies the codebook auxiliary structures for decode *************/
 149 static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){
 150   long i,j;
 151   static_codebook *s=_ogg_calloc(1,sizeof(*s));
 152   s->allocedp=1;
 153
 154   /* make sure alignment is correct */
 155   if(oggpack_read(opb,24)!=0x564342)goto _eofout;
 156
 157   /* first the basic parameters */
 158   s->dim=oggpack_read(opb,16);
 159   s->entries=oggpack_read(opb,24);
 160   if(s->entries==-1)goto _eofout;
 161
 162   if(_ilog(s->dim)+_ilog(s->entries)>24)goto _eofout;
 163
 164   /* codeword ordering.... length ordered or unordered? */
 165   switch((int)oggpack_read(opb,1)){
 166   case 0:
 167     /* unordered */
 168     s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
 169
 170     /* allocated but unused entries? */
 171     if(oggpack_read(opb,1)){
 172       /* yes, unused entries */
 173
 174       for(i=0;i<s->entries;i++){
 175         if(oggpack_read(opb,1)){
 176           long num=oggpack_read(opb,5);
 177           if(num==-1)goto _eofout;
 178           s->lengthlist[i]=num+1;
 179         }else
 180           s->lengthlist[i]=0;
 181       }
 182     }else{
 183       /* all entries used; no tagging */
 184       for(i=0;i<s->entries;i++){
 185         long num=oggpack_read(opb,5);
 186         if(num==-1)goto _eofout;
 187         s->lengthlist[i]=num+1;
 188       }
 189     }
 190
 191     break;
 192   case 1:
 193     /* ordered */
 194     {
 195       long length=oggpack_read(opb,5)+1;
 196       s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
 197
 198       for(i=0;i<s->entries;){
 199         long num=oggpack_read(opb,_ilog(s->entries-i));
 200         if(num==-1)goto _eofout;
 201         if(length>32)goto _errout;
 202         for(j=0;j<num && i<s->entries;j++,i++)
 203           s->lengthlist[i]=length;
 204         length++;
 205       }
 206     }
 207     break;
 208   default:
 209     /* EOF */
 210     goto _eofout;
 211   }
 212
 213   /* Do we have a mapping to unpack? */
 214   switch((s->maptype=oggpack_read(opb,4))){
 215   case 0:
 216     /* no mapping */
 217     break;
 218   case 1: case 2:
 219     /* implicitly populated value mapping */
 220     /* explicitly populated value mapping */
 221
 222     s->q_min=oggpack_read(opb,32);
 223     s->q_delta=oggpack_read(opb,32);
 224     s->q_quant=oggpack_read(opb,4)+1;
 225     s->q_sequencep=oggpack_read(opb,1);
 226     if(s->q_sequencep==-1)goto _eofout;
 227
 228     {
 229       int quantvals=0;
 230       switch(s->maptype){
 231       case 1:
 232         quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
 233         break;
 234       case 2:
 235         quantvals=s->entries*s->dim;
 236         break;
 237       }
 238
 239       /* quantized values */
 240       s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals);
 241       for(i=0;i<quantvals;i++)
 242         s->quantlist[i]=oggpack_read(opb,s->q_quant);
 243
 244       if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
 245     }
 246     break;
 247   default:
 248     goto _errout;
 249   }
 250
 251   /* all set */
 252   return(s);
 253
 254  _errout:
 255  _eofout:
 256   vorbis_staticbook_destroy(s);
 257   return(NULL);
 258 }
 259
 260 /* returns the number of bits ************************************************/
 261 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
 262   if(a<0 || a>=book->c->entries)return(0);
 263   oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
 264   return(book->c->lengthlist[a]);
 265 }
 266
 267 /* the 'eliminate the decode tree' optimization actually requires the
 268    codewords to be MSb first, not LSb.  This is an annoying inelegancy
 269    (and one of the first places where carefully thought out design
 270    turned out to be wrong; Vorbis II and future Ogg codecs should go
 271    to an MSb bitpacker), but not actually the huge hit it appears to
 272    be.  The first-stage decode table catches most words so that
 273    bitreverse is not in the main execution path. */
 274
 275 static ogg_uint32_t bitreverse(ogg_uint32_t x){
 276   x=    ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
 277   x=    ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
 278   x=    ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
 279   x=    ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
 280   return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
 281 }
 282
 283 STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
 284   int  read=book->dec_maxlength;
 285   long lo,hi;
 286   long lok = oggpack_look(b,book->dec_firsttablen);
 287
 288   if (lok >= 0) {
 289     long entry = book->dec_firsttable[lok];
 290     if(entry&0x80000000UL){
 291       lo=(entry>>15)&0x7fff;
 292       hi=book->used_entries-(entry&0x7fff);
 293     }else{
 294       oggpack_adv(b, book->dec_codelengths[entry-1]);
 295       return(entry-1);
 296     }
 297   }else{
 298     lo=0;
 299     hi=book->used_entries;
 300   }
 301
 302   lok = oggpack_look(b, read);
 303
 304   while(lok<0 && read>1)
 305     lok = oggpack_look(b, --read);
 306   if(lok<0)return -1;
 307
 308   /* bisect search for the codeword in the ordered list */
 309   {
 310     ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
 311
 312     while(hi-lo>1){
 313       long p=(hi-lo)>>1;
 314       long test=book->codelist[lo+p]>testword;
 315       lo+=p&(test-1);
 316       hi-=p&(-test);
 317       }
 318
 319     if(book->dec_codelengths[lo]<=read){
 320       oggpack_adv(b, book->dec_codelengths[lo]);
 321       return(lo);
 322     }
 323   }
 324
 325   oggpack_adv(b, read);
 326
 327   return(-1);
 328 }
 329
 330 /* Decode side is specced and easier, because we don't need to find
 331    matches using different criteria; we simply read and map.  There are
 332    two things we need to do 'depending':
 333
 334    We may need to support interleave.  We don't really, but it's
 335    convenient to do it here rather than rebuild the vector later.
 336
 337    Cascades may be additive or multiplicitive; this is not inherent in
 338    the codebook, but set in the code using the codebook.  Like
 339    interleaving, it's easiest to do it here.
 340    addmul==0 -> declarative (set the value)
 341    addmul==1 -> additive
 342    addmul==2 -> multiplicitive */
 343
 344 /* returns the [original, not compacted] entry number or -1 on eof *********/
 345 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
 346   if(book->used_entries>0){
 347     long packed_entry=decode_packed_entry_number(book,b);
 348     if(packed_entry>=0)
 349       return(book->dec_index[packed_entry]);
 350   }
 351
 352   /* if there's no dec_index, the codebook unpacking isn't collapsed */
 353   return(-1);
 354 }
 355
 356 /* returns 0 on OK or -1 on eof *************************************/
 357 long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
 358   if(book->used_entries>0){
 359     int step=n/book->dim;
 360     long *entry = alloca(sizeof(*entry)*step);
 361     float **t = alloca(sizeof(*t)*step);
 362     int i,j,o;
 363
 364     for (i = 0; i < step; i++) {
 365       entry[i]=decode_packed_entry_number(book,b);
 366       if(entry[i]==-1)return(-1);
 367       t[i] = book->valuelist+entry[i]*book->dim;
 368     }
 369     for(i=0,o=0;i<book->dim;i++,o+=step)
 370       for (j=0;j<step;j++)
 371         a[o+j]+=t[j][i];
 372   }
 373   return(0);
 374 }
 375
 376 long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
 377   if(book->used_entries>0){
 378     int i,j,entry;
 379     float *t;
 380
 381     if(book->dim>8){
 382       for(i=0;i<n;){
 383         entry = decode_packed_entry_number(book,b);
 384         if(entry==-1)return(-1);
 385         t     = book->valuelist+entry*book->dim;
 386         for (j=0;j<book->dim;)
 387           a[i++]+=t[j++];
 388       }
 389     }else{
 390       for(i=0;i<n;){
 391         entry = decode_packed_entry_number(book,b);
 392         if(entry==-1)return(-1);
 393         t     = book->valuelist+entry*book->dim;
 394         j=0;
 395         switch((int)book->dim){
 396         case 8:
 397           a[i++]+=t[j++];
 398         case 7:
 399           a[i++]+=t[j++];
 400         case 6:
 401           a[i++]+=t[j++];
 402         case 5:
 403           a[i++]+=t[j++];
 404         case 4:
 405           a[i++]+=t[j++];
 406         case 3:
 407           a[i++]+=t[j++];
 408         case 2:
 409           a[i++]+=t[j++];
 410         case 1:
 411           a[i++]+=t[j++];
 412         case 0:
 413           break;
 414         }
 415       }
 416     }
 417   }
 418   return(0);
 419 }
 420
 421 long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
 422   if(book->used_entries>0){
 423     int i,j,entry;
 424     float *t;
 425
 426     for(i=0;i<n;){
 427       entry = decode_packed_entry_number(book,b);
 428       if(entry==-1)return(-1);
 429       t     = book->valuelist+entry*book->dim;
 430       for (j=0;j<book->dim;)
 431         a[i++]=t[j++];
 432     }
 433   }else{
 434     int i,j;
 435
 436     for(i=0;i<n;){
 437       for (j=0;j<book->dim;)
 438         a[i++]=0.f;
 439     }
 440   }
 441   return(0);
 442 }
 443
 444 long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
 445                               oggpack_buffer *b,int n){
 446
 447   long i,j,entry;
 448   int chptr=0;
 449   if(book->used_entries>0){
 450     for(i=offset/ch;i<(offset+n)/ch;){
 451       entry = decode_packed_entry_number(book,b);
 452       if(entry==-1)return(-1);
 453       {
 454         const float *t = book->valuelist+entry*book->dim;
 455         for (j=0;j<book->dim;j++){
 456           a[chptr++][i]+=t[j];
 457           if(chptr==ch){
 458             chptr=0;
 459             i++;
 460           }
 461         }
 462       }
 463     }
 464   }
 465   return(0);
 466 }