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