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