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