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