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