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-2015             *
   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$
  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       char this=c->lengthlist[i];
  57       char last=c->lengthlist[i-1];
  58       if(this>last){
  59         for(j=last;j<this;j++){
  60           oggpack_write(opb,i-count,ov_ilog(c->entries-count));
  61           count=i;
  62         }
  63       }
  64     }
  65     oggpack_write(opb,i-count,ov_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(ov_ilog(s->dim)+ov_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,ov_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   /* Single entry codebooks use a firsttablen of 1 and a
 316      dec_maxlength of 1.  If a single-entry codebook gets here (due to
 317      failure to read one bit above), the next look attempt will also
 318      fail and we'll correctly kick out instead of trying to walk the
 319      underformed tree */
 320
 321   lok = oggpack_look(b, read);
 322
 323   while(lok<0 && read>1)
 324     lok = oggpack_look(b, --read);
 325   if(lok<0)return -1;
 326
 327   /* bisect search for the codeword in the ordered list */
 328   {
 329     ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
 330
 331     while(hi-lo>1){
 332       long p=(hi-lo)>>1;
 333       long test=book->codelist[lo+p]>testword;
 334       lo+=p&(test-1);
 335       hi-=p&(-test);
 336       }
 337
 338     if(book->dec_codelengths[lo]<=read){
 339       oggpack_adv(b, book->dec_codelengths[lo]);
 340       return(lo);
 341     }
 342   }
 343
 344   oggpack_adv(b, read);
 345
 346   return(-1);
 347 }
 348
 349 /* Decode side is specced and easier, because we don't need to find
 350    matches using different criteria; we simply read and map.  There are
 351    two things we need to do 'depending':
 352
 353    We may need to support interleave.  We don't really, but it's
 354    convenient to do it here rather than rebuild the vector later.
 355
 356    Cascades may be additive or multiplicitive; this is not inherent in
 357    the codebook, but set in the code using the codebook.  Like
 358    interleaving, it's easiest to do it here.
 359    addmul==0 -> declarative (set the value)
 360    addmul==1 -> additive
 361    addmul==2 -> multiplicitive */
 362
 363 /* returns the [original, not compacted] entry number or -1 on eof *********/
 364 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
 365   if(book->used_entries>0){
 366     long packed_entry=decode_packed_entry_number(book,b);
 367     if(packed_entry>=0)
 368       return(book->dec_index[packed_entry]);
 369   }
 370
 371   /* if there's no dec_index, the codebook unpacking isn't collapsed */
 372   return(-1);
 373 }
 374
 375 /* returns 0 on OK or -1 on eof *************************************/
 376 /* decode vector / dim granularity gaurding is done in the upper layer */
 377 long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
 378   if(book->used_entries>0){
 379     int step=n/book->dim;
 380     long *entry = alloca(sizeof(*entry)*step);
 381     float **t = alloca(sizeof(*t)*step);
 382     int i,j,o;
 383
 384     for (i = 0; i < step; i++) {
 385       entry[i]=decode_packed_entry_number(book,b);
 386       if(entry[i]==-1)return(-1);
 387       t[i] = book->valuelist+entry[i]*book->dim;
 388     }
 389     for(i=0,o=0;i<book->dim;i++,o+=step)
 390       for (j=0;j<step;j++)
 391         a[o+j]+=t[j][i];
 392   }
 393   return(0);
 394 }
 395
 396 /* decode vector / dim granularity gaurding is done in the upper layer */
 397 long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
 398   if(book->used_entries>0){
 399     int i,j,entry;
 400     float *t;
 401
 402     if(book->dim>8){
 403       for(i=0;i<n;){
 404         entry = decode_packed_entry_number(book,b);
 405         if(entry==-1)return(-1);
 406         t     = book->valuelist+entry*book->dim;
 407         for (j=0;j<book->dim;)
 408           a[i++]+=t[j++];
 409       }
 410     }else{
 411       for(i=0;i<n;){
 412         entry = decode_packed_entry_number(book,b);
 413         if(entry==-1)return(-1);
 414         t     = book->valuelist+entry*book->dim;
 415         j=0;
 416         switch((int)book->dim){
 417         case 8:
 418           a[i++]+=t[j++];
 419         case 7:
 420           a[i++]+=t[j++];
 421         case 6:
 422           a[i++]+=t[j++];
 423         case 5:
 424           a[i++]+=t[j++];
 425         case 4:
 426           a[i++]+=t[j++];
 427         case 3:
 428           a[i++]+=t[j++];
 429         case 2:
 430           a[i++]+=t[j++];
 431         case 1:
 432           a[i++]+=t[j++];
 433         case 0:
 434           break;
 435         }
 436       }
 437     }
 438   }
 439   return(0);
 440 }
 441
 442 /* unlike the others, we guard against n not being an integer number
 443    of <dim> internally rather than in the upper layer (called only by
 444    floor0) */
 445 long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
 446   if(book->used_entries>0){
 447     int i,j,entry;
 448     float *t;
 449
 450     for(i=0;i<n;){
 451       entry = decode_packed_entry_number(book,b);
 452       if(entry==-1)return(-1);
 453       t     = book->valuelist+entry*book->dim;
 454       for (j=0;i<n && j<book->dim;){
 455         a[i++]=t[j++];
 456       }
 457     }
 458   }else{
 459     int i;
 460
 461     for(i=0;i<n;){
 462       a[i++]=0.f;
 463     }
 464   }
 465   return(0);
 466 }
 467
 468 long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
 469                               oggpack_buffer *b,int n){
 470
 471   long i,j,entry;
 472   int chptr=0;
 473   if(book->used_entries>0){
 474     for(i=offset/ch;i<(offset+n)/ch;){
 475       entry = decode_packed_entry_number(book,b);
 476       if(entry==-1)return(-1);
 477       {
 478         const float *t = book->valuelist+entry*book->dim;
 479         for (j=0;j<book->dim;j++){
 480           a[chptr++][i]+=t[j];
 481           if(chptr==ch){
 482             chptr=0;
 483             i++;
 484           }
 485         }
 486       }
 487     }
 488   }
 489   return(0);
 490 }