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