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