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.17 2000/07/07 01:37:00 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 #include "os.h"
  30
  31 /* packs the given codebook into the bitstream **************************/
  32
  33 int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
  34   long i,j;
  35   int ordered=0;
  36
  37   /* first the basic parameters */
  38   _oggpack_write(opb,0x564342,24);
  39   _oggpack_write(opb,c->dim,16);
  40   _oggpack_write(opb,c->entries,24);
  41
  42   /* pack the codewords.  There are two packings; length ordered and
  43      length random.  Decide between the two now. */
  44
  45   for(i=1;i<c->entries;i++)
  46     if(c->lengthlist[i]<c->lengthlist[i-1])break;
  47   if(i==c->entries)ordered=1;
  48
  49   if(ordered){
  50     /* length ordered.  We only need to say how many codewords of
  51        each length.  The actual codewords are generated
  52        deterministically */
  53
  54     long count=0;
  55     _oggpack_write(opb,1,1);  /* ordered */
  56     _oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
  57
  58     for(i=1;i<c->entries;i++){
  59       long this=c->lengthlist[i];
  60       long last=c->lengthlist[i-1];
  61       if(this>last){
  62         for(j=last;j<this;j++){
  63           _oggpack_write(opb,i-count,_ilog(c->entries-count));
  64           count=i;
  65         }
  66       }
  67     }
  68     _oggpack_write(opb,i-count,_ilog(c->entries-count));
  69
  70   }else{
  71     /* length random.  Again, we don't code the codeword itself, just
  72        the length.  This time, though, we have to encode each length */
  73     _oggpack_write(opb,0,1);   /* unordered */
  74
  75     /* algortihmic mapping has use for 'unused entries', which we tag
  76        here.  The algorithmic mapping happens as usual, but the unused
  77        entry has no codeword. */
  78     for(i=0;i<c->entries;i++)
  79       if(c->lengthlist[i]==0)break;
  80
  81     if(i==c->entries){
  82       _oggpack_write(opb,0,1); /* no unused entries */
  83       for(i=0;i<c->entries;i++)
  84         _oggpack_write(opb,c->lengthlist[i]-1,5);
  85     }else{
  86       _oggpack_write(opb,1,1); /* we have unused entries; thus we tag */
  87       for(i=0;i<c->entries;i++){
  88         if(c->lengthlist[i]==0){
  89           _oggpack_write(opb,0,1);
  90         }else{
  91           _oggpack_write(opb,1,1);
  92           _oggpack_write(opb,c->lengthlist[i]-1,5);
  93         }
  94       }
  95     }
  96   }
  97
  98   /* is the entry number the desired return value, or do we have a
  99      mapping? If we have a mapping, what type? */
 100   _oggpack_write(opb,c->maptype,4);
 101   switch(c->maptype){
 102   case 0:
 103     /* no mapping */
 104     break;
 105   case 1:case 2:
 106     /* implicitly populated value mapping */
 107     /* explicitly populated value mapping */
 108
 109     if(!c->quantlist){
 110       /* no quantlist?  error */
 111       return(-1);
 112     }
 113
 114     /* values that define the dequantization */
 115     _oggpack_write(opb,c->q_min,32);
 116     _oggpack_write(opb,c->q_delta,32);
 117     _oggpack_write(opb,c->q_quant-1,4);
 118     _oggpack_write(opb,c->q_sequencep,1);
 119
 120     {
 121       int quantvals;
 122       switch(c->maptype){
 123       case 1:
 124         /* a single column of (c->entries/c->dim) quantized values for
 125            building a full value list algorithmically (square lattice) */
 126         quantvals=_book_maptype1_quantvals(c);
 127         break;
 128       case 2:
 129         /* every value (c->entries*c->dim total) specified explicitly */
 130         quantvals=c->entries*c->dim;
 131         break;
 132       }
 133
 134       /* quantized values */
 135       for(i=0;i<quantvals;i++)
 136         _oggpack_write(opb,labs(c->quantlist[i]),c->q_quant);
 137
 138     }
 139     break;
 140   default:
 141     /* error case; we don't have any other map types now */
 142     return(-1);
 143   }
 144
 145   return(0);
 146 }
 147
 148 /* unpacks a codebook from the packet buffer into the codebook struct,
 149    readies the codebook auxiliary structures for decode *************/
 150 int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){
 151   long i,j;
 152   memset(s,0,sizeof(static_codebook));
 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=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=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=malloc(sizeof(double)*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 threshhold, 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,double *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,double *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,double *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    stage==0 -> declarative (set the value)
 313    stage==1 -> additive
 314    stage==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   do{
 321     switch(_oggpack_read1(b)){
 322     case 0:
 323       ptr=t->ptr0[ptr];
 324       break;
 325     case 1:
 326       ptr=t->ptr1[ptr];
 327       break;
 328     case -1:
 329       return(-1);
 330     }
 331   }while(ptr>0);
 332   return(-ptr);
 333 }
 334
 335 /* returns the entry number or -1 on eof *************************************/
 336 long vorbis_book_decodevs(codebook *book,double *a,oggpack_buffer *b,
 337                           int step,int addmul){
 338   long entry=vorbis_book_decode(book,b);
 339   int i,o;
 340   if(entry==-1)return(-1);
 341   switch(addmul){
 342   case -1:
 343     for(i=0,o=0;i<book->dim;i++,o+=step)
 344       a[o]=(book->valuelist+entry*book->dim)[i];
 345     break;
 346   case 0:
 347     for(i=0,o=0;i<book->dim;i++,o+=step)
 348       a[o]+=(book->valuelist+entry*book->dim)[i];
 349     break;
 350   case 1:
 351     for(i=0,o=0;i<book->dim;i++,o+=step)
 352       a[o]*=(book->valuelist+entry*book->dim)[i];
 353     break;
 354   }
 355   return(entry);
 356 }
 357
 358 #ifdef _V_SELFTEST
 359
 360 /* Simple enough; pack a few candidate codebooks, unpack them.  Code a
 361    number of vectors through (keeping track of the quantized values),
 362    and decode using the unpacked book.  quantized version of in should
 363    exactly equal out */
 364
 365 #include <stdio.h>
 366
 367 #include "vorbis/book/lsp20_0.vqh"
 368 #include "vorbis/book/res0a_13.vqh"
 369 #define TESTSIZE 40
 370
 371 double test1[TESTSIZE]={
 372   0.105939,
 373   0.215373,
 374   0.429117,
 375   0.587974,
 376
 377   0.181173,
 378   0.296583,
 379   0.515707,
 380   0.715261,
 381
 382   0.162327,
 383   0.263834,
 384   0.342876,
 385   0.406025,
 386
 387   0.103571,
 388   0.223561,
 389   0.368513,
 390   0.540313,
 391
 392   0.136672,
 393   0.395882,
 394   0.587183,
 395   0.652476,
 396
 397   0.114338,
 398   0.417300,
 399   0.525486,
 400   0.698679,
 401
 402   0.147492,
 403   0.324481,
 404   0.643089,
 405   0.757582,
 406
 407   0.139556,
 408   0.215795,
 409   0.324559,
 410   0.399387,
 411
 412   0.120236,
 413   0.267420,
 414   0.446940,
 415   0.608760,
 416
 417   0.115587,
 418   0.287234,
 419   0.571081,
 420   0.708603,
 421 };
 422
 423 double test3[TESTSIZE]={
 424   0,1,-2,3,4,-5,6,7,8,9,
 425   8,-2,7,-1,4,6,8,3,1,-9,
 426   10,11,12,13,14,15,26,17,18,19,
 427   30,-25,-30,-1,-5,-32,4,3,-2,0};
 428
 429 static_codebook *testlist[]={&_vq_book_lsp20_0,
 430                              &_vq_book_res0a_13,NULL};
 431 double   *testvec[]={test1,test3};
 432
 433 int main(){
 434   oggpack_buffer write;
 435   oggpack_buffer read;
 436   long ptr=0,i;
 437   _oggpack_writeinit(&write);
 438
 439   fprintf(stderr,"Testing codebook abstraction...:\n");
 440
 441   while(testlist[ptr]){
 442     codebook c;
 443     static_codebook s;
 444     double *qv=alloca(sizeof(double)*TESTSIZE);
 445     double *iv=alloca(sizeof(double)*TESTSIZE);
 446     memcpy(qv,testvec[ptr],sizeof(double)*TESTSIZE);
 447     memset(iv,0,sizeof(double)*TESTSIZE);
 448
 449     fprintf(stderr,"\tpacking/coding %ld... ",ptr);
 450
 451     /* pack the codebook, write the testvector */
 452     _oggpack_reset(&write);
 453     vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
 454                                                   we can write */
 455     vorbis_staticbook_pack(testlist[ptr],&write);
 456     fprintf(stderr,"Codebook size %ld bytes... ",_oggpack_bytes(&write));
 457     for(i=0;i<TESTSIZE;i+=c.dim){
 458       int best=_best(&c,qv+i,1);
 459       vorbis_book_encodev(&c,best,qv+i,&write);
 460     }
 461     vorbis_book_clear(&c);
 462
 463     fprintf(stderr,"OK.\n");
 464     fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
 465
 466     /* transfer the write data to a read buffer and unpack/read */
 467     _oggpack_readinit(&read,_oggpack_buffer(&write),_oggpack_bytes(&write));
 468     if(vorbis_staticbook_unpack(&read,&s)){
 469       fprintf(stderr,"Error unpacking codebook.\n");
 470       exit(1);
 471     }
 472     if(vorbis_book_init_decode(&c,&s)){
 473       fprintf(stderr,"Error initializing codebook.\n");
 474       exit(1);
 475     }
 476
 477     for(i=0;i<TESTSIZE;i+=c.dim)
 478       if(vorbis_book_decodevs(&c,iv+i,&read,1,-1)==-1){
 479         fprintf(stderr,"Error reading codebook test data (EOP).\n");
 480         exit(1);
 481       }
 482     for(i=0;i<TESTSIZE;i++)
 483       if(fabs(qv[i]-iv[i])>.000001){
 484         fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
 485                 iv[i],qv[i],i);
 486         exit(1);
 487       }
 488
 489     fprintf(stderr,"OK\n");
 490     ptr++;
 491   }
 492
 493   /* The above is the trivial stuff; now try unquantizing a log scale codebook */
 494
 495   exit(0);
 496 }
 497
 498 #endif