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.14 2000/05/08 20:49:48 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 the number of bits and *modifies a* to the quantization value *****/
 276 int vorbis_book_encodev(codebook *book,double *a,oggpack_buffer *b){
 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(vorbis_book_encode(book,best,b));
 282 }
 283
 284 /* res0 (multistage, interleave, lattice) */
 285 /* returns the number of bits and *modifies a* to the remainder value ********/
 286 int vorbis_book_encodevs(codebook *book,double *a,oggpack_buffer *b,
 287                          int step,int addmul){
 288
 289   int best=vorbis_book_besterror(book,a,step,addmul);
 290   return(vorbis_book_encode(book,best,b));
 291 }
 292
 293 /* Decode side is specced and easier, because we don't need to find
 294    matches using different criteria; we simply read and map.  There are
 295    two things we need to do 'depending':
 296
 297    We may need to support interleave.  We don't really, but it's
 298    convenient to do it here rather than rebuild the vector later.
 299
 300    Cascades may be additive or multiplicitive; this is not inherent in
 301    the codebook, but set in the code using the codebook.  Like
 302    interleaving, it's easiest to do it here.
 303    stage==0 -> declarative (set the value)
 304    stage==1 -> additive
 305    stage==2 -> multiplicitive */
 306
 307 /* returns the entry number or -1 on eof *************************************/
 308 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
 309   long ptr=0;
 310   decode_aux *t=book->decode_tree;
 311   do{
 312     switch(_oggpack_read1(b)){
 313     case 0:
 314       ptr=t->ptr0[ptr];
 315       break;
 316     case 1:
 317       ptr=t->ptr1[ptr];
 318       break;
 319     case -1:
 320       return(-1);
 321     }
 322   }while(ptr>0);
 323   return(-ptr);
 324 }
 325
 326 /* returns the entry number or -1 on eof *************************************/
 327 long vorbis_book_decodevs(codebook *book,double *a,oggpack_buffer *b,
 328                           int step,int addmul){
 329   long entry=vorbis_book_decode(book,b);
 330   int i,o;
 331   if(entry==-1)return(-1);
 332   switch(addmul){
 333   case -1:
 334     for(i=0,o=0;i<book->dim;i++,o+=step)
 335       a[o]=(book->valuelist+entry*book->dim)[i];
 336     break;
 337   case 0:
 338     for(i=0,o=0;i<book->dim;i++,o+=step)
 339       a[o]+=(book->valuelist+entry*book->dim)[i];
 340     break;
 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   }
 346   return(entry);
 347 }
 348
 349 #ifdef _V_SELFTEST
 350
 351 /* Simple enough; pack a few candidate codebooks, unpack them.  Code a
 352    number of vectors through (keeping track of the quantized values),
 353    and decode using the unpacked book.  quantized version of in should
 354    exactly equal out */
 355
 356 #include <stdio.h>
 357 #include "vorbis/book/lsp20_0.vqh"
 358 #include "vorbis/book/lsp32_0.vqh"
 359 #include "vorbis/book/res0_1a.vqh"
 360 #define TESTSIZE 40
 361
 362 double test1[TESTSIZE]={
 363   0.105939,
 364   0.215373,
 365   0.429117,
 366   0.587974,
 367
 368   0.181173,
 369   0.296583,
 370   0.515707,
 371   0.715261,
 372
 373   0.162327,
 374   0.263834,
 375   0.342876,
 376   0.406025,
 377
 378   0.103571,
 379   0.223561,
 380   0.368513,
 381   0.540313,
 382
 383   0.136672,
 384   0.395882,
 385   0.587183,
 386   0.652476,
 387
 388   0.114338,
 389   0.417300,
 390   0.525486,
 391   0.698679,
 392
 393   0.147492,
 394   0.324481,
 395   0.643089,
 396   0.757582,
 397
 398   0.139556,
 399   0.215795,
 400   0.324559,
 401   0.399387,
 402
 403   0.120236,
 404   0.267420,
 405   0.446940,
 406   0.608760,
 407
 408   0.115587,
 409   0.287234,
 410   0.571081,
 411   0.708603,
 412 };
 413
 414 double test2[TESTSIZE]={
 415   0.088654,
 416   0.165742,
 417   0.279013,
 418   0.395894,
 419
 420   0.110812,
 421   0.218422,
 422   0.283423,
 423   0.371719,
 424
 425   0.136985,
 426   0.186066,
 427   0.309814,
 428   0.381521,
 429
 430   0.123925,
 431   0.211707,
 432   0.314771,
 433   0.433026,
 434
 435   0.088619,
 436   0.192276,
 437   0.277568,
 438   0.343509,
 439
 440   0.068400,
 441   0.132901,
 442   0.223999,
 443   0.302538,
 444
 445   0.202159,
 446   0.306131,
 447   0.360362,
 448   0.416066,
 449
 450   0.072591,
 451   0.178019,
 452   0.304315,
 453   0.376516,
 454
 455   0.094336,
 456   0.188401,
 457   0.325119,
 458   0.390264,
 459
 460   0.091636,
 461   0.223099,
 462   0.282899,
 463   0.375124,
 464 };
 465
 466 double test3[TESTSIZE]={
 467   0,1,-2,3,4,-5,6,7,8,9,
 468   8,-2,7,-1,4,6,8,3,1,-9,
 469   10,11,12,13,14,15,26,17,18,19,
 470   30,-25,-30,-1,-5,-32,4,3,-2,0};
 471
 472 static_codebook *testlist[]={&_vq_book_lsp20_0,
 473                              &_vq_book_lsp32_0,
 474                              &_vq_book_res0_1a,NULL};
 475 double   *testvec[]={test1,test2,test3};
 476
 477 int main(){
 478   oggpack_buffer write;
 479   oggpack_buffer read;
 480   long ptr=0,i;
 481   _oggpack_writeinit(&write);
 482
 483   fprintf(stderr,"Testing codebook abstraction...:\n");
 484
 485   while(testlist[ptr]){
 486     codebook c;
 487     static_codebook s;
 488     double *qv=alloca(sizeof(double)*TESTSIZE);
 489     double *iv=alloca(sizeof(double)*TESTSIZE);
 490     memcpy(qv,testvec[ptr],sizeof(double)*TESTSIZE);
 491     memset(iv,0,sizeof(double)*TESTSIZE);
 492
 493     fprintf(stderr,"\tpacking/coding %ld... ",ptr);
 494
 495     /* pack the codebook, write the testvector */
 496     _oggpack_reset(&write);
 497     vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
 498                                                   we can write */
 499     vorbis_staticbook_pack(testlist[ptr],&write);
 500     fprintf(stderr,"Codebook size %ld bytes... ",_oggpack_bytes(&write));
 501     for(i=0;i<TESTSIZE;i+=c.dim)
 502       vorbis_book_encodev(&c,qv+i,&write);
 503     vorbis_book_clear(&c);
 504
 505     fprintf(stderr,"OK.\n");
 506     fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
 507
 508     /* transfer the write data to a read buffer and unpack/read */
 509     _oggpack_readinit(&read,_oggpack_buffer(&write),_oggpack_bytes(&write));
 510     if(vorbis_staticbook_unpack(&read,&s)){
 511       fprintf(stderr,"Error unpacking codebook.\n");
 512       exit(1);
 513     }
 514     if(vorbis_book_init_decode(&c,&s)){
 515       fprintf(stderr,"Error initializing codebook.\n");
 516       exit(1);
 517     }
 518
 519     for(i=0;i<TESTSIZE;i+=c.dim)
 520       if(vorbis_book_decodevs(&c,iv+i,&read,1,-1)==-1){
 521         fprintf(stderr,"Error reading codebook test data (EOP).\n");
 522         exit(1);
 523       }
 524     for(i=0;i<TESTSIZE;i++)
 525       if(fabs(qv[i]-iv[i])>.000001){
 526         fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
 527                 iv[i],qv[i],i);
 528         exit(1);
 529       }
 530
 531     fprintf(stderr,"OK\n");
 532     ptr++;
 533   }
 534
 535   /* The above is the trivial stuff; now try unquantizing a log scale codebook */
 536
 537   exit(0);
 538 }
 539
 540 #endif