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-2001             *
   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.24 2001/05/27 06:43:59 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(static_codebook));
 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(oggpack_read(opb,1)){
 164   case 0:
 165     /* unordered */
 166     s->lengthlist=_ogg_malloc(sizeof(long)*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(long)*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;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;
 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(long)*quantvals);
 237       for(i=0;i<quantvals;i++)
 238         s->quantlist[i]=oggpack_read(opb,s->q_quant);
 239
 240       if(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 /* Decode side is specced and easier, because we don't need to find
 303    matches using different criteria; we simply read and map.  There are
 304    two things we need to do 'depending':
 305
 306    We may need to support interleave.  We don't really, but it's
 307    convenient to do it here rather than rebuild the vector later.
 308
 309    Cascades may be additive or multiplicitive; this is not inherent in
 310    the codebook, but set in the code using the codebook.  Like
 311    interleaving, it's easiest to do it here.
 312    addmul==0 -> declarative (set the value)
 313    addmul==1 -> additive
 314    addmul==2 -> multiplicitive */
 315
 316 /* returns the entry number or -1 on eof *************************************/
 317 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
 318   long ptr=0;
 319   decode_aux *t=book->decode_tree;
 320   int lok = oggpack_look(b, t->tabn);
 321
 322   if (lok >= 0) {
 323     ptr = t->tab[lok];
 324     oggpack_adv(b, t->tabl[lok]);
 325     if (ptr <= 0)
 326       return -ptr;
 327   }
 328
 329   do{
 330     switch(oggpack_read1(b)){
 331     case 0:
 332       ptr=t->ptr0[ptr];
 333       break;
 334     case 1:
 335       ptr=t->ptr1[ptr];
 336       break;
 337     case -1:
 338       return(-1);
 339     }
 340   }while(ptr>0);
 341   return(-ptr);
 342 }
 343
 344 /* returns the entry number or -1 on eof *************************************/
 345 long vorbis_book_decodevs(codebook *book,float *a,oggpack_buffer *b,
 346                           int step,int addmul){
 347   long entry=vorbis_book_decode(book,b);
 348   int i,o;
 349   float *t;
 350   if(entry==-1)return(-1);
 351   t = book->valuelist+entry*book->dim;
 352   switch(addmul){
 353   case -1:
 354     for(i=0,o=0;i<book->dim-3;i+=4,o+=4*step) {
 355       a[o]=t[i];
 356       a[o+step]=t[i+1];
 357       a[o+2*step]=t[i+2];
 358       a[o+3*step]=t[i+3];
 359     }
 360     for(;i<book->dim;i++,o+=step)
 361       a[o]=t[i];
 362     break;
 363   case 0:
 364     for(i=0,o=0;i<book->dim-3;i+=4,o+=4*step) {
 365       a[o]+=t[i];
 366       a[o+step]+=t[i+1];
 367       a[o+2*step]+=t[i+2];
 368       a[o+3*step]+=t[i+3];
 369     }
 370     for(;i<book->dim;i++,o+=step)
 371       a[o]+=t[i];
 372     break;
 373   case 1:
 374     for(i=0,o=0;i<book->dim-3;i+=4,o+=4*step) {
 375       a[o]*=t[i];
 376       a[o+step]*=t[i+1];
 377       a[o+2*step]*=t[i+2];
 378       a[o+3*step]*=t[i+3];
 379     }
 380     for(;i<book->dim;i++,o+=step)
 381       a[o]*=t[i];
 382     break;
 383   }
 384   return(entry);
 385 }
 386
 387 /* returns 0 on OK or -1 on eof *************************************/
 388 long s_vorbis_book_decodevs(codebook *book,float *a,oggpack_buffer *b,
 389                          int step,int addmul){
 390   long *entry = alloca(sizeof(long)*step);
 391   float **t = alloca(sizeof(float *)*step);
 392   int i,j,o;
 393
 394   for (i = 0; i < step; i++) {
 395     entry[i]=vorbis_book_decode(book,b);
 396     if(entry[i]==-1)return(-1);
 397     t[i] = book->valuelist+entry[i]*book->dim;
 398   }
 399   switch(addmul){
 400   case -1:
 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     break;
 405   case 0:
 406     for(i=0,o=0;i<book->dim;i++,o+=step)
 407       for (j=0;j<step;j++)
 408        a[o+j]+=t[j][i];
 409     break;
 410   case 1:
 411     for(i=0,o=0;i<book->dim;i++,o+=step)
 412       for (j=0;j<step;j++)
 413        a[o+j]*=t[j][i];
 414     break;
 415   }
 416   return(0);
 417 }
 418
 419 long s_vorbis_book_decodev(codebook *book,float *a,oggpack_buffer *b,
 420                            int partsize,int addmul){
 421   int i,j,entry;
 422   float *t;
 423
 424   switch(addmul){
 425   case -1:
 426     for(i=0;i<partsize;){
 427       entry = vorbis_book_decode(book,b);
 428       if(entry==-1)return(-1);
 429       t     = book->valuelist+entry*book->dim;
 430       for (j=0;j<book->dim;)
 431         a[i++]=t[j++];
 432     }
 433     break;
 434   case 0:
 435     for(i=0;i<partsize;){
 436       entry = vorbis_book_decode(book,b);
 437       if(entry==-1)return(-1);
 438       t     = book->valuelist+entry*book->dim;
 439       for (j=0;j<book->dim;)
 440         a[i++]+=t[j++];
 441     }
 442     break;
 443   case 1:
 444     for(i=0;i<partsize;){
 445       entry = vorbis_book_decode(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     break;
 452   }
 453   return(0);
 454 }
 455
 456 #ifdef _V_SELFTEST
 457
 458 /* Simple enough; pack a few candidate codebooks, unpack them.  Code a
 459    number of vectors through (keeping track of the quantized values),
 460    and decode using the unpacked book.  quantized version of in should
 461    exactly equal out */
 462
 463 #include <stdio.h>
 464
 465 #include "vorbis/book/lsp20_0.vqh"
 466 #include "vorbis/book/res0a_13.vqh"
 467 #define TESTSIZE 40
 468
 469 float test1[TESTSIZE]={
 470   0.105939f,
 471   0.215373f,
 472   0.429117f,
 473   0.587974f,
 474
 475   0.181173f,
 476   0.296583f,
 477   0.515707f,
 478   0.715261f,
 479
 480   0.162327f,
 481   0.263834f,
 482   0.342876f,
 483   0.406025f,
 484
 485   0.103571f,
 486   0.223561f,
 487   0.368513f,
 488   0.540313f,
 489
 490   0.136672f,
 491   0.395882f,
 492   0.587183f,
 493   0.652476f,
 494
 495   0.114338f,
 496   0.417300f,
 497   0.525486f,
 498   0.698679f,
 499
 500   0.147492f,
 501   0.324481f,
 502   0.643089f,
 503   0.757582f,
 504
 505   0.139556f,
 506   0.215795f,
 507   0.324559f,
 508   0.399387f,
 509
 510   0.120236f,
 511   0.267420f,
 512   0.446940f,
 513   0.608760f,
 514
 515   0.115587f,
 516   0.287234f,
 517   0.571081f,
 518   0.708603f,
 519 };
 520
 521 float test3[TESTSIZE]={
 522   0,1,-2,3,4,-5,6,7,8,9,
 523   8,-2,7,-1,4,6,8,3,1,-9,
 524   10,11,12,13,14,15,26,17,18,19,
 525   30,-25,-30,-1,-5,-32,4,3,-2,0};
 526
 527 static_codebook *testlist[]={&_vq_book_lsp20_0,
 528                              &_vq_book_res0a_13,NULL};
 529 float   *testvec[]={test1,test3};
 530
 531 int main(){
 532   oggpack_buffer write;
 533   oggpack_buffer read;
 534   long ptr=0,i;
 535   oggpack_writeinit(&write);
 536
 537   fprintf(stderr,"Testing codebook abstraction...:\n");
 538
 539   while(testlist[ptr]){
 540     codebook c;
 541     static_codebook s;
 542     float *qv=alloca(sizeof(float)*TESTSIZE);
 543     float *iv=alloca(sizeof(float)*TESTSIZE);
 544     memcpy(qv,testvec[ptr],sizeof(float)*TESTSIZE);
 545     memset(iv,0,sizeof(float)*TESTSIZE);
 546
 547     fprintf(stderr,"\tpacking/coding %ld... ",ptr);
 548
 549     /* pack the codebook, write the testvector */
 550     oggpack_reset(&write);
 551     vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
 552                                                   we can write */
 553     vorbis_staticbook_pack(testlist[ptr],&write);
 554     fprintf(stderr,"Codebook size %ld bytes... ",oggpack_bytes(&write));
 555     for(i=0;i<TESTSIZE;i+=c.dim){
 556       int best=_best(&c,qv+i,1);
 557       vorbis_book_encodev(&c,best,qv+i,&write);
 558     }
 559     vorbis_book_clear(&c);
 560
 561     fprintf(stderr,"OK.\n");
 562     fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
 563
 564     /* transfer the write data to a read buffer and unpack/read */
 565     oggpack_readinit(&read,oggpack_get_buffer(&write),oggpack_bytes(&write));
 566     if(vorbis_staticbook_unpack(&read,&s)){
 567       fprintf(stderr,"Error unpacking codebook.\n");
 568       exit(1);
 569     }
 570     if(vorbis_book_init_decode(&c,&s)){
 571       fprintf(stderr,"Error initializing codebook.\n");
 572       exit(1);
 573     }
 574
 575     for(i=0;i<TESTSIZE;i+=c.dim)
 576       if(vorbis_book_decodevs(&c,iv+i,&read,1,-1)==-1){
 577         fprintf(stderr,"Error reading codebook test data (EOP).\n");
 578         exit(1);
 579       }
 580     for(i=0;i<TESTSIZE;i++)
 581       if(fabs(qv[i]-iv[i])>.000001){
 582         fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
 583                 iv[i],qv[i],i);
 584         exit(1);
 585       }
 586
 587     fprintf(stderr,"OK\n");
 588     ptr++;
 589   }
 590
 591   /* The above is the trivial stuff; now try unquantizing a log scale codebook */
 592
 593   exit(0);
 594 }
 595
 596 #endif