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.3 2000/01/22 13:28:17 xiphmont Exp $
  16
  17  ********************************************************************/
  18
  19 #include <stdlib.h>
  20 #include <math.h>
  21 #include "vorbis/codec.h"
  22 #include "vorbis/codebook.h"
  23 #include "bitwise.h"
  24 #include "bookinternal.h"
  25
  26 /**** pack/unpack helpers ******************************************/
  27 static int ilog(unsigned int v){
  28   int ret=0;
  29   while(v){
  30     ret++;
  31     v>>=1;
  32   }
  33   return(ret);
  34 }
  35
  36 static long _float24_pack(double val){
  37   int sign=0;
  38   long exp;
  39   long mant;
  40   if(val<0){
  41     sign=0x800000;
  42     val= -val;
  43   }
  44   exp= floor(log(val)/log(2));
  45   mant=rint(ldexp(val,17-exp));
  46   exp=(exp+VQ_FEXP_BIAS)<<18;
  47
  48   return(sign|exp|mant);
  49 }
  50
  51 static double _float24_unpack(long val){
  52   double mant=val&0x3ffff;
  53   double sign=val&0x800000;
  54   double exp =(val&0x7c0000)>>18;
  55   if(sign)mant= -mant;
  56   return(ldexp(mant,exp-17-VQ_FEXP_BIAS));
  57 }
  58
  59 /* given a list of word lengths, generate a list of codewords.  Works
  60    for length ordered or unordered, always assigns the lowest valued
  61    codewords first */
  62 long *_make_words(long *l,long n){
  63   long i,j;
  64   long marker[33];
  65   long *r=malloc(n*sizeof(long));
  66   memset(marker,0,sizeof(marker));
  67
  68   for(i=0;i<n;i++){
  69     long length=l[i];
  70     long entry=marker[l[i]];
  71
  72     /* when we claim a node for an entry, we also claim the nodes
  73        below it (pruning off the imagined tree that may have dangled
  74        from it) as well as blocking the use of any nodes directly
  75        above for leaves */
  76
  77     /* update ourself */
  78     if(length<32 && (entry>>length)){
  79       /* error condition; the lengths must specify an overpopulated tree */
  80       free(r);
  81       return(NULL);
  82     }
  83     r[i]=entry;
  84
  85     /* Look to see if the next shorter marker points to the node
  86        above. if so, update it and repeat.  */
  87     {
  88       for(j=length;j>0;j--){
  89
  90         if(marker[j]&1){
  91           /* have to jump branches */
  92           if(j==1)
  93             marker[1]++;
  94           else
  95             marker[j]=marker[j-1]<<1;
  96           break; /* invariant says next upper marker would already
  97                     have been moved if it was on the same path */
  98         }
  99         marker[j]++;
 100       }
 101     }
 102
 103     /* prune the tree; the implicit invariant says all the longer
 104        markers were dangling from our just-taken node.  Dangle them
 105        from our *new* node. */
 106     for(j=length+1;j<33;j++)
 107       marker[j]=marker[j-1]<<1;
 108   }
 109
 110   /* bitreverse the words because our bitwise packer/unpacker is LSb
 111      endian */
 112   for(i=0;i<n;i++){
 113     long temp=0;
 114     for(j=0;j<l[i];j++){
 115       temp<<=1;
 116       temp|=(r[i]>>j)&1;
 117     }
 118     r[i]=temp;
 119   }
 120
 121   return(r);
 122 }
 123
 124 /* unpack the quantized list of values for encode/decode ***********/
 125 static double *_book_unquantize(static_codebook *b){
 126   long j,k;
 127   double mindel=_float24_unpack(b->q_min);
 128   double delta=_float24_unpack(b->q_delta);
 129   double *r=malloc(sizeof(double)*b->entries*b->dim);
 130
 131   for(j=0;j<b->entries;j++){
 132     double last=0.;
 133     for(k=0;k<b->dim;k++){
 134       double val=b->quantlist[j*b->dim+k]*delta+last+mindel;
 135       r[j*b->dim+k]=val;
 136       if(b->q_sequencep)last=val;
 137     }
 138   }
 139   return(r);
 140 }
 141
 142 void vorbis_book_clear(codebook *b){
 143   /* static book is not cleared.  It exists only in encode */
 144   if(b->decode_tree){
 145     free(b->decode_tree->ptr0);
 146     free(b->decode_tree->ptr1);
 147     memset(b->decode_tree,0,sizeof(decode_aux));
 148     free(b->decode_tree);
 149   }
 150   if(b->valuelist)free(b->valuelist);
 151   if(b->codelist)free(b->codelist);
 152   memset(b,0,sizeof(codebook));
 153 }
 154
 155 int vorbis_book_finish(codebook *c, static_codebook *s){
 156   memset(c,0,sizeof(codebook));
 157   c->c=s;
 158   c->elements=s->elements;
 159   c->dim=s->dim;
 160   c->codelist=_make_words(c->lengthlist,c->entries);
 161   c->valuelist=_book_unquantize(c);
 162   return(0);
 163 }
 164
 165 /* packs the given codebook into the bitstream **************************/
 166
 167 int vorbis_book_pack(static_codebook *c,oggpack_buffer *opb){
 168   long i,j;
 169   int ordered=0;
 170
 171   /* first the basic parameters */
 172   _oggpack_write(opb,0x564342,24);
 173   _oggpack_write(opb,c->dim,16);
 174   _oggpack_write(opb,c->entries,24);
 175
 176   /* pack the codewords.  There are two packings; length ordered and
 177      length random.  Decide between the two now. */
 178
 179   for(i=1;i<c->entries;i++)
 180     if(c->lengthlist[i]<c->lengthlist[i-1])break;
 181   if(i==c->entries)ordered=1;
 182
 183   if(ordered){
 184     /* length ordered.  We only need to say how many codewords of
 185        each length.  The actual codewords are generated
 186        deterministically */
 187
 188     long count=0;
 189     _oggpack_write(opb,1,1);  /* ordered */
 190     _oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
 191
 192     for(i=1;i<c->entries;i++){
 193       long this=c->lengthlist[i];
 194       long last=c->lengthlist[i-1];
 195       if(this>last){
 196         for(j=last;j<this;j++){
 197           _oggpack_write(opb,i-count,ilog(c->entries-count));
 198           count=i;
 199         }
 200       }
 201     }
 202     _oggpack_write(opb,i-count,ilog(c->entries-count));
 203
 204   }else{
 205     /* length random.  Again, we don't code the codeword itself, just
 206        the length.  This time, though, we have to encode each length */
 207     _oggpack_write(opb,0,1);   /* unordered */
 208     for(i=0;i<c->entries;i++)
 209       _oggpack_write(opb,c->lengthlist[i]-1,5);
 210   }
 211
 212   /* is the entry number the desired return value, or do we have a
 213      mapping? */
 214   if(c->quantlist){
 215     /* we have a mapping.  bundle it out. */
 216     _oggpack_write(opb,1,1);
 217
 218     /* values that define the dequantization */
 219     _oggpack_write(opb,c->q_min,24);
 220     _oggpack_write(opb,c->q_delta,24);
 221     _oggpack_write(opb,c->q_quant-1,4);
 222     _oggpack_write(opb,c->q_sequencep,1);
 223
 224     /* quantized values */
 225     for(i=0;i<c->entries*c->dim;i++)
 226       _oggpack_write(opb,c->quantlist[i],c->q_quant);
 227
 228   }else{
 229     /* no mapping. */
 230     _oggpack_write(opb,0,1);
 231   }
 232
 233   return(0);
 234 }
 235
 236 /* unpacks a codebook from the packet buffer into the codebook struct,
 237    readies the codebook auxiliary structures for decode *************/
 238 int vorbis_book_unpack(oggpack_buffer *opb,codebook *c){
 239   long i,j;
 240   long *lengthlist=NULL;
 241   long *codelist=NULL;
 242   static codebook s;
 243   memset(c,0,sizeof(codebook));
 244   memset(&s,0,sizeof(s));
 245
 246   /* make sure alignment is correct */
 247   if(_oggpack_read(opb,24)!=0x564342)goto _eofout;
 248
 249   /* first the basic parameters */
 250   c->dim=_oggpack_read(opb,16);
 251   c->entries=_oggpack_read(opb,24);
 252   if(c->entries==-1)goto _eofout;
 253
 254   /* codeword ordering.... length ordered or unordered? */
 255   switch(_oggpack_read(opb,1)){
 256   case 0:
 257     /* unordered */
 258     lengthlist=malloc(sizeof(long)*c->entries);
 259     for(i=0;i<c->entries;i++){
 260       long num=_oggpack_read(opb,5);
 261       if(num==-1)goto _eofout;
 262       lengthlist[i]=num+1;
 263     }
 264
 265     break;
 266   case 1:
 267     /* ordered */
 268     {
 269       long length=_oggpack_read(opb,5)+1;
 270       lengthlist=malloc(sizeof(long)*c->entries);
 271
 272       for(i=0;i<c->entries;){
 273         long num=_oggpack_read(opb,ilog(c->entries-i));
 274         if(num==-1)goto _eofout;
 275         for(j=0;j<num;j++,i++)
 276           lengthlist[i]=length;
 277         length++;
 278       }
 279     }
 280     break;
 281   default:
 282     /* EOF */
 283     return(-1);
 284   }
 285
 286   /* now we generate the codewords for the given lengths */
 287   codelist=_make_words(c->lengthlist,c->entries);
 288   if(codelist==NULL)goto _errout;
 289
 290   /* ...and the decode helper tree from the codewords */
 291   {
 292     long top=0;
 293     decode_aux *t=c->decode_tree=malloc(sizeof(decode_aux));
 294     long *ptr0=t->ptr0=calloc(c->entries*2,sizeof(long));
 295     long *ptr1=t->ptr1=calloc(c->entries*2,sizeof(long));
 296     t->aux=c->entries*2;
 297
 298     for(i=0;i<c->entries;i++){
 299       long ptr=0;
 300       for(j=0;j<lengthlist[i]-1;j++){
 301         int bit=(codelist[i]>>j)&1;
 302         if(!bit){
 303           if(!ptr0[ptr])
 304             ptr0[ptr]= ++top;
 305           ptr=ptr0[ptr];
 306         }else{
 307           if(!ptr1[ptr])
 308             ptr1[ptr]= ++top;
 309           ptr=ptr1[ptr];
 310         }
 311       }
 312       if(!((codelist[i]>>j)&1))
 313         ptr0[ptr]=-i;
 314       else
 315         ptr1[ptr]=-i;
 316     }
 317   }
 318   /* no longer needed */
 319   free(lengthlist);
 320   free(codelist);
 321
 322   /* Do we have a mapping to unpack? */
 323   if(_oggpack_read(opb,1)){
 324
 325     /* values that define the dequantization */
 326     s.q_min=_oggpack_read(opb,24);
 327     s.q_delta=_oggpack_read(opb,24);
 328     s.q_quant=_oggpack_read(opb,4)+1;
 329     s.q_sequencep=_oggpack_read(opb,1);
 330     s.dim=c->dim;
 331     s.entries=c->entries;
 332
 333     /* quantized values */
 334     s.quantlist=malloc(sizeof(double)*c->entries*c->dim);
 335     for(i=0;i<c->entries*c->dim;i++)
 336       s.quantlist[i]=_oggpack_read(opb,s.q_quant);
 337     if(s.quantlist[i-1]==-1)goto _eofout;
 338     c->valuelist=_book_unquantize(&s);
 339     free(s.quantlist);memset(&s,0,sizeof(s));
 340   }
 341
 342   /* all set */
 343   return(0);
 344
 345  _errout:
 346  _eofout:
 347   if(lengthlist)free(lengthlist);
 348   if(s.quantlist)free(s.quantlist);
 349   if(codelist)free(codelist);
 350   vorbis_book_clear(c);
 351   return(-1);
 352
 353 }
 354
 355 /* returns the number of bits ***************************************/
 356 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
 357   _oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
 358   return(book->c->lengthlist[a]);
 359 }
 360
 361 /* returns the number of bits and *modifies a* to the entry value *****/
 362 int vorbis_book_encodev(codebook *book, double *a, oggpack_buffer *b){
 363   encode_aux *t=book->c->encode_tree;
 364   int dim=book->dim;
 365   int ptr=0,k;
 366
 367   while(1){
 368     double c=0.;
 369     double *p=book->valuelist+t->p[ptr];
 370     double *q=book->valuelist+t->q[ptr];
 371
 372     for(k=0;k<dim;k++)
 373       c+=(p[k]-q[k])*(a[k]-(p[k]+q[k])*.5);
 374
 375     if(c>0.) /* in A */
 376       ptr= -t->ptr0[ptr];
 377     else     /* in B */
 378       ptr= -t->ptr1[ptr];
 379     if(ptr<=0)break;
 380   }
 381   memcpy(a,book->valuelist-ptr*dim,dim*sizeof(double));
 382   return(vorbis_book_encode(book,-ptr,b));
 383 }
 384
 385 /* returns the entry number or -1 on eof ****************************/
 386 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
 387   long ptr=0;
 388   decode_aux *t=book->decode_tree;
 389   do{
 390     switch(_oggpack_read1(b)){
 391     case 0:
 392       ptr=t->ptr0[ptr];
 393       break;
 394     case 1:
 395       ptr=t->ptr1[ptr];
 396       break;
 397     case -1:
 398       return(-1);
 399     }
 400   }while(ptr>0);
 401   return(-ptr);
 402 }
 403
 404 /* returns the entry number or -1 on eof ****************************/
 405 long vorbis_book_decodev(codebook *book, double *a, oggpack_buffer *b){
 406   long entry=vorbis_book_decode(book,b);
 407   if(entry==-1)return(-1);
 408   memcpy(a,book->valuelist+entry*book->dim,sizeof(double)*book->dim);
 409   return(0);
 410 }
 411
 412 #ifdef _V_SELFTEST
 413
 414 /* Simple enough; pack a few candidate codebooks, unpack them.  Code a
 415    number of vectors through (keeping track of the quantized values),
 416    and decode using the unpacked book.  quantized version of in should
 417    exactly equal out */
 418
 419 #include <stdio.h>
 420 #include "vorbis/book/lsp20_0.vqh"
 421 #include "vorbis/book/lsp32_0.vqh"
 422 #define TESTSIZE 40
 423 #define TESTDIM 4
 424
 425 double test1[40]={
 426   0.105939,
 427   0.215373,
 428   0.429117,
 429   0.587974,
 430
 431   0.181173,
 432   0.296583,
 433   0.515707,
 434   0.715261,
 435
 436   0.162327,
 437   0.263834,
 438   0.342876,
 439   0.406025,
 440
 441   0.103571,
 442   0.223561,
 443   0.368513,
 444   0.540313,
 445
 446   0.136672,
 447   0.395882,
 448   0.587183,
 449   0.652476,
 450
 451   0.114338,
 452   0.417300,
 453   0.525486,
 454   0.698679,
 455
 456   0.147492,
 457   0.324481,
 458   0.643089,
 459   0.757582,
 460
 461   0.139556,
 462   0.215795,
 463   0.324559,
 464   0.399387,
 465
 466   0.120236,
 467   0.267420,
 468   0.446940,
 469   0.608760,
 470
 471   0.115587,
 472   0.287234,
 473   0.571081,
 474   0.708603,
 475 };
 476
 477 double test2[40]={
 478   0.088654,
 479   0.165742,
 480   0.279013,
 481   0.395894,
 482
 483   0.110812,
 484   0.218422,
 485   0.283423,
 486   0.371719,
 487
 488   0.136985,
 489   0.186066,
 490   0.309814,
 491   0.381521,
 492
 493   0.123925,
 494   0.211707,
 495   0.314771,
 496   0.433026,
 497
 498   0.088619,
 499   0.192276,
 500   0.277568,
 501   0.343509,
 502
 503   0.068400,
 504   0.132901,
 505   0.223999,
 506   0.302538,
 507
 508   0.202159,
 509   0.306131,
 510   0.360362,
 511   0.416066,
 512
 513   0.072591,
 514   0.178019,
 515   0.304315,
 516   0.376516,
 517
 518   0.094336,
 519   0.188401,
 520   0.325119,
 521   0.390264,
 522
 523   0.091636,
 524   0.223099,
 525   0.282899,
 526   0.375124,
 527 };
 528
 529 static_codebook *testlist[]={&_vq_book_lsp20_0,&_vq_book_lsp32_0,NULL};
 530 double   *testvec[]={test1,test2};
 531
 532 int main(){
 533   oggpack_buffer write;
 534   oggpack_buffer read;
 535   long ptr=0,i;
 536   _oggpack_writeinit(&write);
 537
 538   fprintf(stderr,"Testing codebook abstraction...:\n");
 539
 540   while(testlist[ptr]){
 541     codebook c;
 542     double *qv=alloca(sizeof(double)*TESTSIZE);
 543     double *iv=alloca(sizeof(double)*TESTSIZE);
 544     memcpy(qv,testvec[ptr],sizeof(double)*TESTSIZE);
 545
 546     fprintf(stderr,"\tpacking/coding %ld... ",ptr);
 547
 548     /* pack the codebook, write the testvector */
 549     _oggpack_reset(&write);
 550     vorbis_book_finish(&c,testlist[ptr]); /* get it into memory we can write */
 551     vorbis_book_pack(&c,&write);
 552     fprintf(stderr,"Codebook size %ld bytes... ",_oggpack_bytes(&write));
 553     for(i=0;i<TESTSIZE;i+=TESTDIM)
 554       vorbis_book_encodev(&c,qv+i,&write);
 555     vorbis_book_clear(&c);
 556
 557     fprintf(stderr,"OK.\n");
 558     fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
 559
 560     /* transfer the write data to a read buffer and unpack/read */
 561     _oggpack_readinit(&read,_oggpack_buffer(&write),_oggpack_bytes(&write));
 562     if(vorbis_book_unpack(&read,&c)){
 563       fprintf(stderr,"Error unpacking codebook.\n");
 564       exit(1);
 565     }
 566     for(i=0;i<TESTSIZE;i+=TESTDIM)
 567       if(vorbis_book_decodev(&c,iv+i,&read)){
 568         fprintf(stderr,"Error reading codebook test data (EOP).\n");
 569         exit(1);
 570       }
 571     for(i=0;i<TESTSIZE;i++)
 572       if(qv[i]!=iv[i]){
 573         fprintf(stderr,"input (%g) != output (%g) at position (%ld)\n",
 574                 iv[i],qv[i],i);
 575         exit(1);
 576       }
 577
 578     fprintf(stderr,"OK\n");
 579     ptr++;
 580   }
 581   exit(0);
 582 }
 583
 584 #endif