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