lib/codebook.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE.  *
   4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
   5  * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE.    *
   6  * PLEASE READ THESE TERMS DISTRIBUTING.                            *
   7  *                                                                  *
   8  * THE OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-2000             *
   9  * by Monty <monty@xiph.org> and The XIPHOPHORUS Company            *
  10  * http://www.xiph.org/                                             *
  11  *                                                                  *
  12  ********************************************************************
  13
  14  function: basic codebook pack/unpack/code/decode operations
  15  last mod: $Id: codebook.c,v 1.15 2000/06/14 01:38:31 xiphmont Exp $
  16
  17  ********************************************************************/
  18
  19 #include <stdlib.h>
  20 #include <string.h>
  21 #include <math.h>
  22 #include "vorbis/codec.h"
  23 #include "vorbis/codebook.h"
  24 #include "bitwise.h"
  25 #include "scales.h"
  26 #include "sharedbook.h"
  27 #include "bookinternal.h"
  28 #include "misc.h"
  29
  30 /* packs the given codebook into the bitstream **************************/
  31
  32 int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
  33   long i,j;
  34   int ordered=0;
  35
  36   /* first the basic parameters */
  37   _oggpack_write(opb,0x564342,24);
  38   _oggpack_write(opb,c->dim,16);
  39   _oggpack_write(opb,c->entries,24);
  40
  41   /* pack the codewords.  There are two packings; length ordered and
  42      length random.  Decide between the two now. */
  43
  44   for(i=1;i<c->entries;i++)
  45     if(c->lengthlist[i]<c->lengthlist[i-1])break;
  46   if(i==c->entries)ordered=1;
  47
  48   if(ordered){
  49     /* length ordered.  We only need to say how many codewords of
  50        each length.  The actual codewords are generated
  51        deterministically */
  52
  53     long count=0;
  54     _oggpack_write(opb,1,1);  /* ordered */
  55     _oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
  56
  57     for(i=1;i<c->entries;i++){
  58       long this=c->lengthlist[i];
  59       long last=c->lengthlist[i-1];
  60       if(this>last){
  61         for(j=last;j<this;j++){
  62           _oggpack_write(opb,i-count,_ilog(c->entries-count));
  63           count=i;
  64         }
  65       }
  66     }
  67     _oggpack_write(opb,i-count,_ilog(c->entries-count));
  68
  69   }else{
  70     /* length random.  Again, we don't code the codeword itself, just
  71        the length.  This time, though, we have to encode each length */
  72     _oggpack_write(opb,0,1);   /* unordered */
  73
  74     /* algortihmic mapping has use for 'unused entries', which we tag
  75        here.  The algorithmic mapping happens as usual, but the unused
  76        entry has no codeword. */
  77     for(i=0;i<c->entries;i++)
  78       if(c->lengthlist[i]==0)break;
  79
  80     if(i==c->entries){
  81       _oggpack_write(opb,0,1); /* no unused entries */
  82       for(i=0;i<c->entries;i++)
  83         _oggpack_write(opb,c->lengthlist[i]-1,5);
  84     }else{
  85       _oggpack_write(opb,1,1); /* we have unused entries; thus we tag */
  86       for(i=0;i<c->entries;i++){
  87         if(c->lengthlist[i]==0){
  88           _oggpack_write(opb,0,1);
  89         }else{
  90           _oggpack_write(opb,1,1);
  91           _oggpack_write(opb,c->lengthlist[i]-1,5);
  92         }
  93       }
  94     }
  95   }
  96
  97   /* is the entry number the desired return value, or do we have a
  98      mapping? If we have a mapping, what type? */
  99   _oggpack_write(opb,c->maptype,4);
 100   switch(c->maptype){
 101   case 0:
 102     /* no mapping */
 103     break;
 104   case 1:case 2:
 105     /* implicitly populated value mapping */
 106     /* explicitly populated value mapping */
 107
 108     if(!c->quantlist){
 109       /* no quantlist?  error */
 110       return(-1);
 111     }
 112
 113     /* values that define the dequantization */
 114     _oggpack_write(opb,c->q_min,32);
 115     _oggpack_write(opb,c->q_delta,32);
 116     _oggpack_write(opb,c->q_quant-1,4);
 117     _oggpack_write(opb,c->q_sequencep,1);
 118
 119     {
 120       int quantvals;
 121       switch(c->maptype){
 122       case 1:
 123         /* a single column of (c->entries/c->dim) quantized values for
 124            building a full value list algorithmically (square lattice) */
 125         quantvals=_book_maptype1_quantvals(c);
 126         break;
 127       case 2:
 128         /* every value (c->entries*c->dim total) specified explicitly */
 129         quantvals=c->entries*c->dim;
 130         break;
 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
 153   /* make sure alignment is correct */
 154   if(_oggpack_read(opb,24)!=0x564342)goto _eofout;
 155
 156   /* first the basic parameters */
 157   s->dim=_oggpack_read(opb,16);
 158   s->entries=_oggpack_read(opb,24);
 159   if(s->entries==-1)goto _eofout;
 160
 161   /* codeword ordering.... length ordered or unordered? */
 162   switch(_oggpack_read(opb,1)){
 163   case 0:
 164     /* unordered */
 165     s->lengthlist=malloc(sizeof(long)*s->entries);
 166
 167     /* allocated but unused entries? */
 168     if(_oggpack_read(opb,1)){
 169       /* yes, unused entries */
 170
 171       for(i=0;i<s->entries;i++){
 172         if(_oggpack_read(opb,1)){
 173           long num=_oggpack_read(opb,5);
 174           if(num==-1)goto _eofout;
 175           s->lengthlist[i]=num+1;
 176         }else
 177           s->lengthlist[i]=0;
 178       }
 179     }else{
 180       /* all entries used; no tagging */
 181       for(i=0;i<s->entries;i++){
 182         long num=_oggpack_read(opb,5);
 183         if(num==-1)goto _eofout;
 184         s->lengthlist[i]=num+1;
 185       }
 186     }
 187
 188     break;
 189   case 1:
 190     /* ordered */
 191     {
 192       long length=_oggpack_read(opb,5)+1;
 193       s->lengthlist=malloc(sizeof(long)*s->entries);
 194
 195       for(i=0;i<s->entries;){
 196         long num=_oggpack_read(opb,_ilog(s->entries-i));
 197         if(num==-1)goto _eofout;
 198         for(j=0;j<num;j++,i++)
 199           s->lengthlist[i]=length;
 200         length++;
 201       }
 202     }
 203     break;
 204   default:
 205     /* EOF */
 206     return(-1);
 207   }
 208
 209   /* Do we have a mapping to unpack? */
 210   switch((s->maptype=_oggpack_read(opb,4))){
 211   case 0:
 212     /* no mapping */
 213     break;
 214   case 1: case 2:
 215     /* implicitly populated value mapping */
 216     /* explicitly populated value mapping */
 217
 218     s->q_min=_oggpack_read(opb,32);
 219     s->q_delta=_oggpack_read(opb,32);
 220     s->q_quant=_oggpack_read(opb,4)+1;
 221     s->q_sequencep=_oggpack_read(opb,1);
 222
 223     {
 224       int quantvals;
 225       switch(s->maptype){
 226       case 1:
 227         quantvals=_book_maptype1_quantvals(s);
 228         break;
 229       case 2:
 230         quantvals=s->entries*s->dim;
 231         break;
 232       }
 233
 234       /* quantized values */
 235       s->quantlist=malloc(sizeof(double)*quantvals);
 236       for(i=0;i<quantvals;i++)
 237         s->quantlist[i]=_oggpack_read(opb,s->q_quant);
 238
 239       if(s->quantlist[quantvals-1]==-1)goto _eofout;
 240     }
 241     break;
 242   default:
 243     goto _errout;
 244   }
 245
 246   /* all set */
 247   return(0);
 248
 249  _errout:
 250  _eofout:
 251   vorbis_staticbook_clear(s);
 252   return(-1);
 253 }
 254
 255 /* returns the number of bits ************************************************/
 256 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
 257   _oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
 258   return(book->c->lengthlist[a]);
 259 }
 260
 261 /* One the encode side, our vector writers are each designed for a
 262 specific purpose, and the encoder is not flexible without modification:
 263
 264 The LSP vector coder uses a single stage nearest-match with no
 265 interleave, so no step and no error return.  This is specced by floor0
 266 and doesn't change.
 267
 268 Residue0 encoding interleaves, uses multiple stages, and each stage
 269 peels of a specific amount of resolution from a lattice (thus we want
 270 to match by threshhold, not nearest match).  Residue doesn't *have* to
 271 be encoded that way, but to change it, one will need to add more
 272 infrastructure on the encode side (decode side is specced and simpler) */
 273
 274 /* floor0 LSP (single stage, non interleaved, nearest match) */
 275 /* returns entry number and *modifies a* to the quantization value *****/
 276 int vorbis_book_errorv(codebook *book,double *a){
 277   int dim=book->dim,k;
 278   int best=_best(book,a,1);
 279   for(k=0;k<dim;k++)
 280     a[k]=(book->valuelist+best*dim)[k];
 281   return(best);
 282 }
 283
 284 /* returns the number of bits and *modifies a* to the quantization value *****/
 285 int vorbis_book_encodev(codebook *book,int best,double *a,oggpack_buffer *b){
 286   int k,dim=book->dim;
 287   for(k=0;k<dim;k++)
 288     a[k]=(book->valuelist+best*dim)[k];
 289   return(vorbis_book_encode(book,best,b));
 290 }
 291
 292 /* res0 (multistage, interleave, lattice) */
 293 /* returns the number of bits and *modifies a* to the remainder value ********/
 294 int vorbis_book_encodevs(codebook *book,double *a,oggpack_buffer *b,
 295                          int step,int addmul){
 296
 297   int best=vorbis_book_besterror(book,a,step,addmul);
 298   return(vorbis_book_encode(book,best,b));
 299 }
 300
 301 /* Decode side is specced and easier, because we don't need to find
 302    matches using different criteria; we simply read and map.  There are
 303    two things we need to do 'depending':
 304
 305    We may need to support interleave.  We don't really, but it's
 306    convenient to do it here rather than rebuild the vector later.
 307
 308    Cascades may be additive or multiplicitive; this is not inherent in
 309    the codebook, but set in the code using the codebook.  Like
 310    interleaving, it's easiest to do it here.
 311    stage==0 -> declarative (set the value)
 312    stage==1 -> additive
 313    stage==2 -> multiplicitive */
 314
 315 /* returns the entry number or -1 on eof *************************************/
 316 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
 317   long ptr=0;
 318   decode_aux *t=book->decode_tree;
 319   do{
 320     switch(_oggpack_read1(b)){
 321     case 0:
 322       ptr=t->ptr0[ptr];
 323       break;
 324     case 1:
 325       ptr=t->ptr1[ptr];
 326       break;
 327     case -1:
 328       return(-1);
 329     }
 330   }while(ptr>0);
 331   return(-ptr);
 332 }
 333
 334 /* returns the entry number or -1 on eof *************************************/
 335 long vorbis_book_decodevs(codebook *book,double *a,oggpack_buffer *b,
 336                           int step,int addmul){
 337   long entry=vorbis_book_decode(book,b);
 338   int i,o;
 339   if(entry==-1)return(-1);
 340   switch(addmul){
 341   case -1:
 342     for(i=0,o=0;i<book->dim;i++,o+=step)
 343       a[o]=(book->valuelist+entry*book->dim)[i];
 344     break;
 345   case 0:
 346     for(i=0,o=0;i<book->dim;i++,o+=step)
 347       a[o]+=(book->valuelist+entry*book->dim)[i];
 348     break;
 349   case 1:
 350     for(i=0,o=0;i<book->dim;i++,o+=step)
 351       a[o]*=(book->valuelist+entry*book->dim)[i];
 352     break;
 353   }
 354   return(entry);
 355 }
 356
 357 #ifdef _V_SELFTEST
 358
 359 /* Simple enough; pack a few candidate codebooks, unpack them.  Code a
 360    number of vectors through (keeping track of the quantized values),
 361    and decode using the unpacked book.  quantized version of in should
 362    exactly equal out */
 363
 364 #include <stdio.h>
 365 #include "vorbis/book/lsp20_0.vqh"
 366 #include "vorbis/book/lsp32_0.vqh"
 367 #include "vorbis/book/res0_1a.vqh"
 368 #define TESTSIZE 40
 369
 370 double test1[TESTSIZE]={
 371   0.105939,
 372   0.215373,
 373   0.429117,
 374   0.587974,
 375
 376   0.181173,
 377   0.296583,
 378   0.515707,
 379   0.715261,
 380
 381   0.162327,
 382   0.263834,
 383   0.342876,
 384   0.406025,
 385
 386   0.103571,
 387   0.223561,
 388   0.368513,
 389   0.540313,
 390
 391   0.136672,
 392   0.395882,
 393   0.587183,
 394   0.652476,
 395
 396   0.114338,
 397   0.417300,
 398   0.525486,
 399   0.698679,
 400
 401   0.147492,
 402   0.324481,
 403   0.643089,
 404   0.757582,
 405
 406   0.139556,
 407   0.215795,
 408   0.324559,
 409   0.399387,
 410
 411   0.120236,
 412   0.267420,
 413   0.446940,
 414   0.608760,
 415
 416   0.115587,
 417   0.287234,
 418   0.571081,
 419   0.708603,
 420 };
 421
 422 double test2[TESTSIZE]={
 423   0.088654,
 424   0.165742,
 425   0.279013,
 426   0.395894,
 427
 428   0.110812,
 429   0.218422,
 430   0.283423,
 431   0.371719,
 432
 433   0.136985,
 434   0.186066,
 435   0.309814,
 436   0.381521,
 437
 438   0.123925,
 439   0.211707,
 440   0.314771,
 441   0.433026,
 442
 443   0.088619,
 444   0.192276,
 445   0.277568,
 446   0.343509,
 447
 448   0.068400,
 449   0.132901,
 450   0.223999,
 451   0.302538,
 452
 453   0.202159,
 454   0.306131,
 455   0.360362,
 456   0.416066,
 457
 458   0.072591,
 459   0.178019,
 460   0.304315,
 461   0.376516,
 462
 463   0.094336,
 464   0.188401,
 465   0.325119,
 466   0.390264,
 467
 468   0.091636,
 469   0.223099,
 470   0.282899,
 471   0.375124,
 472 };
 473
 474 double test3[TESTSIZE]={
 475   0,1,-2,3,4,-5,6,7,8,9,
 476   8,-2,7,-1,4,6,8,3,1,-9,
 477   10,11,12,13,14,15,26,17,18,19,
 478   30,-25,-30,-1,-5,-32,4,3,-2,0};
 479
 480 static_codebook *testlist[]={&_vq_book_lsp20_0,
 481                              &_vq_book_lsp32_0,
 482                              &_vq_book_res0_1a,NULL};
 483 double   *testvec[]={test1,test2,test3};
 484
 485 int main(){
 486   oggpack_buffer write;
 487   oggpack_buffer read;
 488   long ptr=0,i;
 489   _oggpack_writeinit(&write);
 490
 491   fprintf(stderr,"Testing codebook abstraction...:\n");
 492
 493   while(testlist[ptr]){
 494     codebook c;
 495     static_codebook s;
 496     double *qv=alloca(sizeof(double)*TESTSIZE);
 497     double *iv=alloca(sizeof(double)*TESTSIZE);
 498     memcpy(qv,testvec[ptr],sizeof(double)*TESTSIZE);
 499     memset(iv,0,sizeof(double)*TESTSIZE);
 500
 501     fprintf(stderr,"\tpacking/coding %ld... ",ptr);
 502
 503     /* pack the codebook, write the testvector */
 504     _oggpack_reset(&write);
 505     vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
 506                                                   we can write */
 507     vorbis_staticbook_pack(testlist[ptr],&write);
 508     fprintf(stderr,"Codebook size %ld bytes... ",_oggpack_bytes(&write));
 509     for(i=0;i<TESTSIZE;i+=c.dim)
 510       vorbis_book_encodev(&c,qv+i,&write);
 511     vorbis_book_clear(&c);
 512
 513     fprintf(stderr,"OK.\n");
 514     fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
 515
 516     /* transfer the write data to a read buffer and unpack/read */
 517     _oggpack_readinit(&read,_oggpack_buffer(&write),_oggpack_bytes(&write));
 518     if(vorbis_staticbook_unpack(&read,&s)){
 519       fprintf(stderr,"Error unpacking codebook.\n");
 520       exit(1);
 521     }
 522     if(vorbis_book_init_decode(&c,&s)){
 523       fprintf(stderr,"Error initializing codebook.\n");
 524       exit(1);
 525     }
 526
 527     for(i=0;i<TESTSIZE;i+=c.dim)
 528       if(vorbis_book_decodevs(&c,iv+i,&read,1,-1)==-1){
 529         fprintf(stderr,"Error reading codebook test data (EOP).\n");
 530         exit(1);
 531       }
 532     for(i=0;i<TESTSIZE;i++)
 533       if(fabs(qv[i]-iv[i])>.000001){
 534         fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
 535                 iv[i],qv[i],i);
 536         exit(1);
 537       }
 538
 539     fprintf(stderr,"OK\n");
 540     ptr++;
 541   }
 542
 543   /* The above is the trivial stuff; now try unquantizing a log scale codebook */
 544
 545   exit(0);
 546 }
 547
 548 #endif