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 https://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;o+j<n && 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     for(i=0;i<n;){
 402       entry = decode_packed_entry_number(book,b);
 403       if(entry==-1)return(-1);
 404       t     = book->valuelist+entry*book->dim;
 405       for(j=0;i<n && j<book->dim;)
 406         a[i++]+=t[j++];
 407     }
 408   }
 409   return(0);
 410 }
 411
 412 /* unlike the others, we guard against n not being an integer number
 413    of <dim> internally rather than in the upper layer (called only by
 414    floor0) */
 415 long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
 416   if(book->used_entries>0){
 417     int i,j,entry;
 418     float *t;
 419
 420     for(i=0;i<n;){
 421       entry = decode_packed_entry_number(book,b);
 422       if(entry==-1)return(-1);
 423       t     = book->valuelist+entry*book->dim;
 424       for (j=0;i<n && j<book->dim;){
 425         a[i++]=t[j++];
 426       }
 427     }
 428   }else{
 429     int i;
 430
 431     for(i=0;i<n;){
 432       a[i++]=0.f;
 433     }
 434   }
 435   return(0);
 436 }
 437
 438 long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
 439                               oggpack_buffer *b,int n){
 440
 441   long i,j,entry;
 442   int chptr=0;
 443   if(book->used_entries>0){
 444     int m=(offset+n)/ch;
 445     for(i=offset/ch;i<m;){
 446       entry = decode_packed_entry_number(book,b);
 447       if(entry==-1)return(-1);
 448       {
 449         const float *t = book->valuelist+entry*book->dim;
 450         for (j=0;i<m && j<book->dim;j++){
 451           a[chptr++][i]+=t[j];
 452           if(chptr==ch){
 453             chptr=0;
 454             i++;
 455           }
 456         }
 457       }
 458     }
 459   }
 460   return(0);
 461 }