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