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$
  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 int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){
 150   long i,j;
 151   memset(s,0,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     return(-1);
 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(0);
 253
 254  _errout:
 255  _eofout:
 256   vorbis_staticbook_clear(s);
 257   return(-1);
 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 /* One the encode side, our vector writers are each designed for a
 268 specific purpose, and the encoder is not flexible without modification:
 269
 270 The LSP vector coder uses a single stage nearest-match with no
 271 interleave, so no step and no error return.  This is specced by floor0
 272 and doesn't change.
 273
 274 Residue0 encoding interleaves, uses multiple stages, and each stage
 275 peels of a specific amount of resolution from a lattice (thus we want
 276 to match by threshold, not nearest match).  Residue doesn't *have* to
 277 be encoded that way, but to change it, one will need to add more
 278 infrastructure on the encode side (decode side is specced and simpler) */
 279
 280 /* floor0 LSP (single stage, non interleaved, nearest match) */
 281 /* returns entry number and *modifies a* to the quantization value *****/
 282 int vorbis_book_errorv(codebook *book,float *a){
 283   int dim=book->dim,k;
 284   int best=_best(book,a,1);
 285   for(k=0;k<dim;k++)
 286     a[k]=(book->valuelist+best*dim)[k];
 287   return(best);
 288 }
 289
 290 /* returns the number of bits and *modifies a* to the quantization value *****/
 291 int vorbis_book_encodev(codebook *book,int best,float *a,oggpack_buffer *b){
 292   int k,dim=book->dim;
 293   for(k=0;k<dim;k++)
 294     a[k]=(book->valuelist+best*dim)[k];
 295   return(vorbis_book_encode(book,best,b));
 296 }
 297
 298 /* the 'eliminate the decode tree' optimization actually requires the
 299    codewords to be MSb first, not LSb.  This is an annoying inelegancy
 300    (and one of the first places where carefully thought out design
 301    turned out to be wrong; Vorbis II and future Ogg codecs should go
 302    to an MSb bitpacker), but not actually the huge hit it appears to
 303    be.  The first-stage decode table catches most words so that
 304    bitreverse is not in the main execution path. */
 305
 306 static ogg_uint32_t bitreverse(ogg_uint32_t x){
 307   x=    ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
 308   x=    ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
 309   x=    ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
 310   x=    ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
 311   return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
 312 }
 313
 314 STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
 315   int  read=book->dec_maxlength;
 316   long lo,hi;
 317   long lok = oggpack_look(b,book->dec_firsttablen);
 318
 319   if (lok >= 0) {
 320     long entry = book->dec_firsttable[lok];
 321     if(entry&0x80000000UL){
 322       lo=(entry>>15)&0x7fff;
 323       hi=book->used_entries-(entry&0x7fff);
 324     }else{
 325       oggpack_adv(b, book->dec_codelengths[entry-1]);
 326       return(entry-1);
 327     }
 328   }else{
 329     lo=0;
 330     hi=book->used_entries;
 331   }
 332
 333   lok = oggpack_look(b, read);
 334
 335   while(lok<0 && read>1)
 336     lok = oggpack_look(b, --read);
 337   if(lok<0)return -1;
 338
 339   /* bisect search for the codeword in the ordered list */
 340   {
 341     ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
 342
 343     while(hi-lo>1){
 344       long p=(hi-lo)>>1;
 345       long test=book->codelist[lo+p]>testword;
 346       lo+=p&(test-1);
 347       hi-=p&(-test);
 348       }
 349
 350     if(book->dec_codelengths[lo]<=read){
 351       oggpack_adv(b, book->dec_codelengths[lo]);
 352       return(lo);
 353     }
 354   }
 355
 356   oggpack_adv(b, read);
 357
 358   return(-1);
 359 }
 360
 361 /* Decode side is specced and easier, because we don't need to find
 362    matches using different criteria; we simply read and map.  There are
 363    two things we need to do 'depending':
 364
 365    We may need to support interleave.  We don't really, but it's
 366    convenient to do it here rather than rebuild the vector later.
 367
 368    Cascades may be additive or multiplicitive; this is not inherent in
 369    the codebook, but set in the code using the codebook.  Like
 370    interleaving, it's easiest to do it here.
 371    addmul==0 -> declarative (set the value)
 372    addmul==1 -> additive
 373    addmul==2 -> multiplicitive */
 374
 375 /* returns the [original, not compacted] entry number or -1 on eof *********/
 376 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
 377   if(book->used_entries>0){
 378     long packed_entry=decode_packed_entry_number(book,b);
 379     if(packed_entry>=0)
 380       return(book->dec_index[packed_entry]);
 381   }
 382
 383   /* if there's no dec_index, the codebook unpacking isn't collapsed */
 384   return(-1);
 385 }
 386
 387 /* returns 0 on OK or -1 on eof *************************************/
 388 long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
 389   if(book->used_entries>0){
 390     int step=n/book->dim;
 391     long *entry = alloca(sizeof(*entry)*step);
 392     float **t = alloca(sizeof(*t)*step);
 393     int i,j,o;
 394
 395     for (i = 0; i < step; i++) {
 396       entry[i]=decode_packed_entry_number(book,b);
 397       if(entry[i]==-1)return(-1);
 398       t[i] = book->valuelist+entry[i]*book->dim;
 399     }
 400     for(i=0,o=0;i<book->dim;i++,o+=step)
 401       for (j=0;j<step;j++)
 402         a[o+j]+=t[j][i];
 403   }
 404   return(0);
 405 }
 406
 407 long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
 408   if(book->used_entries>0){
 409     int i,j,entry;
 410     float *t;
 411
 412     if(book->dim>8){
 413       for(i=0;i<n;){
 414         entry = decode_packed_entry_number(book,b);
 415         if(entry==-1)return(-1);
 416         t     = book->valuelist+entry*book->dim;
 417         for (j=0;j<book->dim;)
 418           a[i++]+=t[j++];
 419       }
 420     }else{
 421       for(i=0;i<n;){
 422         entry = decode_packed_entry_number(book,b);
 423         if(entry==-1)return(-1);
 424         t     = book->valuelist+entry*book->dim;
 425         j=0;
 426         switch((int)book->dim){
 427         case 8:
 428           a[i++]+=t[j++];
 429         case 7:
 430           a[i++]+=t[j++];
 431         case 6:
 432           a[i++]+=t[j++];
 433         case 5:
 434           a[i++]+=t[j++];
 435         case 4:
 436           a[i++]+=t[j++];
 437         case 3:
 438           a[i++]+=t[j++];
 439         case 2:
 440           a[i++]+=t[j++];
 441         case 1:
 442           a[i++]+=t[j++];
 443         case 0:
 444           break;
 445         }
 446       }
 447     }
 448   }
 449   return(0);
 450 }
 451
 452 long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
 453   if(book->used_entries>0){
 454     int i,j,entry;
 455     float *t;
 456
 457     for(i=0;i<n;){
 458       entry = decode_packed_entry_number(book,b);
 459       if(entry==-1)return(-1);
 460       t     = book->valuelist+entry*book->dim;
 461       for (j=0;j<book->dim;)
 462         a[i++]=t[j++];
 463     }
 464   }else{
 465     int i,j;
 466
 467     for(i=0;i<n;){
 468       for (j=0;j<book->dim;)
 469         a[i++]=0.f;
 470     }
 471   }
 472   return(0);
 473 }
 474
 475 long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
 476                               oggpack_buffer *b,int n){
 477
 478   long i,j,entry;
 479   int chptr=0;
 480   if(book->used_entries>0){
 481     for(i=offset/ch;i<(offset+n)/ch;){
 482       entry = decode_packed_entry_number(book,b);
 483       if(entry==-1)return(-1);
 484       {
 485         const float *t = book->valuelist+entry*book->dim;
 486         for (j=0;j<book->dim;j++){
 487           a[chptr++][i]+=t[j];
 488           if(chptr==ch){
 489             chptr=0;
 490             i++;
 491           }
 492         }
 493       }
 494     }
 495   }
 496   return(0);
 497 }
 498
 499 #ifdef _V_SELFTEST
 500 /* Simple enough; pack a few candidate codebooks, unpack them.  Code a
 501    number of vectors through (keeping track of the quantized values),
 502    and decode using the unpacked book.  quantized version of in should
 503    exactly equal out */
 504
 505 #include <stdio.h>
 506
 507 #include "vorbis/book/lsp20_0.vqh"
 508 #include "vorbis/book/res0a_13.vqh"
 509 #define TESTSIZE 40
 510
 511 float test1[TESTSIZE]={
 512   0.105939f,
 513   0.215373f,
 514   0.429117f,
 515   0.587974f,
 516
 517   0.181173f,
 518   0.296583f,
 519   0.515707f,
 520   0.715261f,
 521
 522   0.162327f,
 523   0.263834f,
 524   0.342876f,
 525   0.406025f,
 526
 527   0.103571f,
 528   0.223561f,
 529   0.368513f,
 530   0.540313f,
 531
 532   0.136672f,
 533   0.395882f,
 534   0.587183f,
 535   0.652476f,
 536
 537   0.114338f,
 538   0.417300f,
 539   0.525486f,
 540   0.698679f,
 541
 542   0.147492f,
 543   0.324481f,
 544   0.643089f,
 545   0.757582f,
 546
 547   0.139556f,
 548   0.215795f,
 549   0.324559f,
 550   0.399387f,
 551
 552   0.120236f,
 553   0.267420f,
 554   0.446940f,
 555   0.608760f,
 556
 557   0.115587f,
 558   0.287234f,
 559   0.571081f,
 560   0.708603f,
 561 };
 562
 563 float test3[TESTSIZE]={
 564   0,1,-2,3,4,-5,6,7,8,9,
 565   8,-2,7,-1,4,6,8,3,1,-9,
 566   10,11,12,13,14,15,26,17,18,19,
 567   30,-25,-30,-1,-5,-32,4,3,-2,0};
 568
 569 static_codebook *testlist[]={&_vq_book_lsp20_0,
 570                              &_vq_book_res0a_13,NULL};
 571 float   *testvec[]={test1,test3};
 572
 573 int main(){
 574   oggpack_buffer write;
 575   oggpack_buffer read;
 576   long ptr=0,i;
 577   oggpack_writeinit(&write);
 578
 579   fprintf(stderr,"Testing codebook abstraction...:\n");
 580
 581   while(testlist[ptr]){
 582     codebook c;
 583     static_codebook s;
 584     float *qv=alloca(sizeof(*qv)*TESTSIZE);
 585     float *iv=alloca(sizeof(*iv)*TESTSIZE);
 586     memcpy(qv,testvec[ptr],sizeof(*qv)*TESTSIZE);
 587     memset(iv,0,sizeof(*iv)*TESTSIZE);
 588
 589     fprintf(stderr,"\tpacking/coding %ld... ",ptr);
 590
 591     /* pack the codebook, write the testvector */
 592     oggpack_reset(&write);
 593     vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
 594                                                   we can write */
 595     vorbis_staticbook_pack(testlist[ptr],&write);
 596     fprintf(stderr,"Codebook size %ld bytes... ",oggpack_bytes(&write));
 597     for(i=0;i<TESTSIZE;i+=c.dim){
 598       int best=_best(&c,qv+i,1);
 599       vorbis_book_encodev(&c,best,qv+i,&write);
 600     }
 601     vorbis_book_clear(&c);
 602
 603     fprintf(stderr,"OK.\n");
 604     fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
 605
 606     /* transfer the write data to a read buffer and unpack/read */
 607     oggpack_readinit(&read,oggpack_get_buffer(&write),oggpack_bytes(&write));
 608     if(vorbis_staticbook_unpack(&read,&s)){
 609       fprintf(stderr,"Error unpacking codebook.\n");
 610       exit(1);
 611     }
 612     if(vorbis_book_init_decode(&c,&s)){
 613       fprintf(stderr,"Error initializing codebook.\n");
 614       exit(1);
 615     }
 616
 617     for(i=0;i<TESTSIZE;i+=c.dim)
 618       if(vorbis_book_decodev_set(&c,iv+i,&read,c.dim)==-1){
 619         fprintf(stderr,"Error reading codebook test data (EOP).\n");
 620         exit(1);
 621       }
 622     for(i=0;i<TESTSIZE;i++)
 623       if(fabs(qv[i]-iv[i])>.000001){
 624         fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
 625                 iv[i],qv[i],i);
 626         exit(1);
 627       }
 628
 629     fprintf(stderr,"OK\n");
 630     ptr++;
 631   }
 632
 633   /* The above is the trivial stuff; now try unquantizing a log scale codebook */
 634
 635   exit(0);
 636 }
 637
 638 #endif