git.mutantstargoat.com Git - laserbrain_demo/blob - libs/vorbis/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 18183 2012-02-03 20:51:27Z 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     long unused;
 168     /* allocated but unused entries? */
 169     unused=oggpack_read(opb,1);
 170     if((s->entries*(unused?1:5)+7)>>3>opb->storage-oggpack_bytes(opb))
 171       goto _eofout;
 172     /* unordered */
 173     s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
 174
 175     /* allocated but unused entries? */
 176     if(unused){
 177       /* yes, unused entries */
 178
 179       for(i=0;i<s->entries;i++){
 180         if(oggpack_read(opb,1)){
 181           long num=oggpack_read(opb,5);
 182           if(num==-1)goto _eofout;
 183           s->lengthlist[i]=num+1;
 184         }else
 185           s->lengthlist[i]=0;
 186       }
 187     }else{
 188       /* all entries used; no tagging */
 189       for(i=0;i<s->entries;i++){
 190         long num=oggpack_read(opb,5);
 191         if(num==-1)goto _eofout;
 192         s->lengthlist[i]=num+1;
 193       }
 194     }
 195
 196     break;
 197   }
 198   case 1:
 199     /* ordered */
 200     {
 201       long length=oggpack_read(opb,5)+1;
 202       if(length==0)goto _eofout;
 203       s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
 204
 205       for(i=0;i<s->entries;){
 206         long num=oggpack_read(opb,_ilog(s->entries-i));
 207         if(num==-1)goto _eofout;
 208         if(length>32 || num>s->entries-i ||
 209            (num>0 && (num-1)>>(length-1)>1)){
 210           goto _errout;
 211         }
 212         if(length>32)goto _errout;
 213         for(j=0;j<num;j++,i++)
 214           s->lengthlist[i]=length;
 215         length++;
 216       }
 217     }
 218     break;
 219   default:
 220     /* EOF */
 221     goto _eofout;
 222   }
 223
 224   /* Do we have a mapping to unpack? */
 225   switch((s->maptype=oggpack_read(opb,4))){
 226   case 0:
 227     /* no mapping */
 228     break;
 229   case 1: case 2:
 230     /* implicitly populated value mapping */
 231     /* explicitly populated value mapping */
 232
 233     s->q_min=oggpack_read(opb,32);
 234     s->q_delta=oggpack_read(opb,32);
 235     s->q_quant=oggpack_read(opb,4)+1;
 236     s->q_sequencep=oggpack_read(opb,1);
 237     if(s->q_sequencep==-1)goto _eofout;
 238
 239     {
 240       int quantvals=0;
 241       switch(s->maptype){
 242       case 1:
 243         quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
 244         break;
 245       case 2:
 246         quantvals=s->entries*s->dim;
 247         break;
 248       }
 249
 250       /* quantized values */
 251       if(((quantvals*s->q_quant+7)>>3)>opb->storage-oggpack_bytes(opb))
 252         goto _eofout;
 253       s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals);
 254       for(i=0;i<quantvals;i++)
 255         s->quantlist[i]=oggpack_read(opb,s->q_quant);
 256
 257       if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
 258     }
 259     break;
 260   default:
 261     goto _errout;
 262   }
 263
 264   /* all set */
 265   return(s);
 266
 267  _errout:
 268  _eofout:
 269   vorbis_staticbook_destroy(s);
 270   return(NULL);
 271 }
 272
 273 /* returns the number of bits ************************************************/
 274 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
 275   if(a<0 || a>=book->c->entries)return(0);
 276   oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
 277   return(book->c->lengthlist[a]);
 278 }
 279
 280 /* the 'eliminate the decode tree' optimization actually requires the
 281    codewords to be MSb first, not LSb.  This is an annoying inelegancy
 282    (and one of the first places where carefully thought out design
 283    turned out to be wrong; Vorbis II and future Ogg codecs should go
 284    to an MSb bitpacker), but not actually the huge hit it appears to
 285    be.  The first-stage decode table catches most words so that
 286    bitreverse is not in the main execution path. */
 287
 288 static ogg_uint32_t bitreverse(ogg_uint32_t x){
 289   x=    ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
 290   x=    ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
 291   x=    ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
 292   x=    ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
 293   return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
 294 }
 295
 296 STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
 297   int  read=book->dec_maxlength;
 298   long lo,hi;
 299   long lok = oggpack_look(b,book->dec_firsttablen);
 300
 301   if (lok >= 0) {
 302     long entry = book->dec_firsttable[lok];
 303     if(entry&0x80000000UL){
 304       lo=(entry>>15)&0x7fff;
 305       hi=book->used_entries-(entry&0x7fff);
 306     }else{
 307       oggpack_adv(b, book->dec_codelengths[entry-1]);
 308       return(entry-1);
 309     }
 310   }else{
 311     lo=0;
 312     hi=book->used_entries;
 313   }
 314
 315   lok = oggpack_look(b, read);
 316
 317   while(lok<0 && read>1)
 318     lok = oggpack_look(b, --read);
 319   if(lok<0)return -1;
 320
 321   /* bisect search for the codeword in the ordered list */
 322   {
 323     ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
 324
 325     while(hi-lo>1){
 326       long p=(hi-lo)>>1;
 327       long test=book->codelist[lo+p]>testword;
 328       lo+=p&(test-1);
 329       hi-=p&(-test);
 330       }
 331
 332     if(book->dec_codelengths[lo]<=read){
 333       oggpack_adv(b, book->dec_codelengths[lo]);
 334       return(lo);
 335     }
 336   }
 337
 338   oggpack_adv(b, read);
 339
 340   return(-1);
 341 }
 342
 343 /* Decode side is specced and easier, because we don't need to find
 344    matches using different criteria; we simply read and map.  There are
 345    two things we need to do 'depending':
 346
 347    We may need to support interleave.  We don't really, but it's
 348    convenient to do it here rather than rebuild the vector later.
 349
 350    Cascades may be additive or multiplicitive; this is not inherent in
 351    the codebook, but set in the code using the codebook.  Like
 352    interleaving, it's easiest to do it here.
 353    addmul==0 -> declarative (set the value)
 354    addmul==1 -> additive
 355    addmul==2 -> multiplicitive */
 356
 357 /* returns the [original, not compacted] entry number or -1 on eof *********/
 358 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
 359   if(book->used_entries>0){
 360     long packed_entry=decode_packed_entry_number(book,b);
 361     if(packed_entry>=0)
 362       return(book->dec_index[packed_entry]);
 363   }
 364
 365   /* if there's no dec_index, the codebook unpacking isn't collapsed */
 366   return(-1);
 367 }
 368
 369 /* returns 0 on OK or -1 on eof *************************************/
 370 /* decode vector / dim granularity gaurding is done in the upper layer */
 371 long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
 372   if(book->used_entries>0){
 373     int step=n/book->dim;
 374     long *entry = alloca(sizeof(*entry)*step);
 375     float **t = alloca(sizeof(*t)*step);
 376     int i,j,o;
 377
 378     for (i = 0; i < step; i++) {
 379       entry[i]=decode_packed_entry_number(book,b);
 380       if(entry[i]==-1)return(-1);
 381       t[i] = book->valuelist+entry[i]*book->dim;
 382     }
 383     for(i=0,o=0;i<book->dim;i++,o+=step)
 384       for (j=0;j<step;j++)
 385         a[o+j]+=t[j][i];
 386   }
 387   return(0);
 388 }
 389
 390 /* decode vector / dim granularity gaurding is done in the upper layer */
 391 long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
 392   if(book->used_entries>0){
 393     int i,j,entry;
 394     float *t;
 395
 396     if(book->dim>8){
 397       for(i=0;i<n;){
 398         entry = decode_packed_entry_number(book,b);
 399         if(entry==-1)return(-1);
 400         t     = book->valuelist+entry*book->dim;
 401         for (j=0;j<book->dim;)
 402           a[i++]+=t[j++];
 403       }
 404     }else{
 405       for(i=0;i<n;){
 406         entry = decode_packed_entry_number(book,b);
 407         if(entry==-1)return(-1);
 408         t     = book->valuelist+entry*book->dim;
 409         j=0;
 410         switch((int)book->dim){
 411         case 8:
 412           a[i++]+=t[j++];
 413         case 7:
 414           a[i++]+=t[j++];
 415         case 6:
 416           a[i++]+=t[j++];
 417         case 5:
 418           a[i++]+=t[j++];
 419         case 4:
 420           a[i++]+=t[j++];
 421         case 3:
 422           a[i++]+=t[j++];
 423         case 2:
 424           a[i++]+=t[j++];
 425         case 1:
 426           a[i++]+=t[j++];
 427         case 0:
 428           break;
 429         }
 430       }
 431     }
 432   }
 433   return(0);
 434 }
 435
 436 /* unlike the others, we guard against n not being an integer number
 437    of <dim> internally rather than in the upper layer (called only by
 438    floor0) */
 439 long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
 440   if(book->used_entries>0){
 441     int i,j,entry;
 442     float *t;
 443
 444     for(i=0;i<n;){
 445       entry = decode_packed_entry_number(book,b);
 446       if(entry==-1)return(-1);
 447       t     = book->valuelist+entry*book->dim;
 448       for (j=0;i<n && j<book->dim;){
 449         a[i++]=t[j++];
 450       }
 451     }
 452   }else{
 453     int i;
 454
 455     for(i=0;i<n;){
 456       a[i++]=0.f;
 457     }
 458   }
 459   return(0);
 460 }
 461
 462 long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
 463                               oggpack_buffer *b,int n){
 464
 465   long i,j,entry;
 466   int chptr=0;
 467   if(book->used_entries>0){
 468     for(i=offset/ch;i<(offset+n)/ch;){
 469       entry = decode_packed_entry_number(book,b);
 470       if(entry==-1)return(-1);
 471       {
 472         const float *t = book->valuelist+entry*book->dim;
 473         for (j=0;j<book->dim;j++){
 474           a[chptr++][i]+=t[j];
 475           if(chptr==ch){
 476             chptr=0;
 477             i++;
 478           }
 479         }
 480       }
 481     }
 482   }
 483   return(0);
 484 }