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.5 2000/02/05 23:23:58 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 entry value *****/
 365 int vorbis_book_encodev(codebook *book, double *a, oggpack_buffer *b){
 366   encode_aux *t=book->c->encode_tree;
 367   int dim=book->dim;
 368   int ptr=0,k;
 369
 370   while(1){
 371     double c=0.;
 372     double *p=book->valuelist+t->p[ptr];
 373     double *q=book->valuelist+t->q[ptr];
 374
 375     for(k=0;k<dim;k++)
 376       c+=(p[k]-q[k])*(a[k]-(p[k]+q[k])*.5);
 377
 378     if(c>0.) /* in A */
 379       ptr= -t->ptr0[ptr];
 380     else     /* in B */
 381       ptr= -t->ptr1[ptr];
 382     if(ptr<=0)break;
 383   }
 384   memcpy(a,book->valuelist-ptr*dim,dim*sizeof(double));
 385   return(vorbis_book_encode(book,-ptr,b));
 386 }
 387
 388 /* returns the entry number or -1 on eof ****************************/
 389 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
 390   long ptr=0;
 391   decode_aux *t=book->decode_tree;
 392   do{
 393     switch(_oggpack_read1(b)){
 394     case 0:
 395       ptr=t->ptr0[ptr];
 396       break;
 397     case 1:
 398       ptr=t->ptr1[ptr];
 399       break;
 400     case -1:
 401       return(-1);
 402     }
 403   }while(ptr>0);
 404   return(-ptr);
 405 }
 406
 407 /* returns the entry number or -1 on eof ****************************/
 408 long vorbis_book_decodev(codebook *book, double *a, oggpack_buffer *b){
 409   long entry=vorbis_book_decode(book,b);
 410   if(entry==-1)return(-1);
 411   memcpy(a,book->valuelist+entry*book->dim,sizeof(double)*book->dim);
 412   return(0);
 413 }
 414
 415 #ifdef _V_SELFTEST
 416
 417 /* Simple enough; pack a few candidate codebooks, unpack them.  Code a
 418    number of vectors through (keeping track of the quantized values),
 419    and decode using the unpacked book.  quantized version of in should
 420    exactly equal out */
 421
 422 #include <stdio.h>
 423 #include "vorbis/book/lsp20_0.vqh"
 424 #include "vorbis/book/lsp32_0.vqh"
 425 #define TESTSIZE 40
 426 #define TESTDIM 4
 427
 428 double test1[40]={
 429   0.105939,
 430   0.215373,
 431   0.429117,
 432   0.587974,
 433
 434   0.181173,
 435   0.296583,
 436   0.515707,
 437   0.715261,
 438
 439   0.162327,
 440   0.263834,
 441   0.342876,
 442   0.406025,
 443
 444   0.103571,
 445   0.223561,
 446   0.368513,
 447   0.540313,
 448
 449   0.136672,
 450   0.395882,
 451   0.587183,
 452   0.652476,
 453
 454   0.114338,
 455   0.417300,
 456   0.525486,
 457   0.698679,
 458
 459   0.147492,
 460   0.324481,
 461   0.643089,
 462   0.757582,
 463
 464   0.139556,
 465   0.215795,
 466   0.324559,
 467   0.399387,
 468
 469   0.120236,
 470   0.267420,
 471   0.446940,
 472   0.608760,
 473
 474   0.115587,
 475   0.287234,
 476   0.571081,
 477   0.708603,
 478 };
 479
 480 double test2[40]={
 481   0.088654,
 482   0.165742,
 483   0.279013,
 484   0.395894,
 485
 486   0.110812,
 487   0.218422,
 488   0.283423,
 489   0.371719,
 490
 491   0.136985,
 492   0.186066,
 493   0.309814,
 494   0.381521,
 495
 496   0.123925,
 497   0.211707,
 498   0.314771,
 499   0.433026,
 500
 501   0.088619,
 502   0.192276,
 503   0.277568,
 504   0.343509,
 505
 506   0.068400,
 507   0.132901,
 508   0.223999,
 509   0.302538,
 510
 511   0.202159,
 512   0.306131,
 513   0.360362,
 514   0.416066,
 515
 516   0.072591,
 517   0.178019,
 518   0.304315,
 519   0.376516,
 520
 521   0.094336,
 522   0.188401,
 523   0.325119,
 524   0.390264,
 525
 526   0.091636,
 527   0.223099,
 528   0.282899,
 529   0.375124,
 530 };
 531
 532 static_codebook *testlist[]={&_vq_book_lsp20_0,&_vq_book_lsp32_0,NULL};
 533 double   *testvec[]={test1,test2};
 534
 535 int main(){
 536   oggpack_buffer write;
 537   oggpack_buffer read;
 538   long ptr=0,i;
 539   _oggpack_writeinit(&write);
 540
 541   fprintf(stderr,"Testing codebook abstraction...:\n");
 542
 543   while(testlist[ptr]){
 544     codebook c;
 545     static_codebook s;
 546     double *qv=alloca(sizeof(double)*TESTSIZE);
 547     double *iv=alloca(sizeof(double)*TESTSIZE);
 548     memcpy(qv,testvec[ptr],sizeof(double)*TESTSIZE);
 549
 550     fprintf(stderr,"\tpacking/coding %ld... ",ptr);
 551
 552     /* pack the codebook, write the testvector */
 553     _oggpack_reset(&write);
 554     vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
 555                                                   we can write */
 556     vorbis_staticbook_pack(testlist[ptr],&write);
 557     fprintf(stderr,"Codebook size %ld bytes... ",_oggpack_bytes(&write));
 558     for(i=0;i<TESTSIZE;i+=TESTDIM)
 559       vorbis_book_encodev(&c,qv+i,&write);
 560     vorbis_book_clear(&c);
 561
 562     fprintf(stderr,"OK.\n");
 563     fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
 564
 565     /* transfer the write data to a read buffer and unpack/read */
 566     _oggpack_readinit(&read,_oggpack_buffer(&write),_oggpack_bytes(&write));
 567     if(vorbis_staticbook_unpack(&read,&s)){
 568       fprintf(stderr,"Error unpacking codebook.\n");
 569       exit(1);
 570     }
 571     if(vorbis_book_init_decode(&c,&s)){
 572       fprintf(stderr,"Error initializing codebook.\n");
 573       exit(1);
 574     }
 575
 576     for(i=0;i<TESTSIZE;i+=TESTDIM)
 577       if(vorbis_book_decodev(&c,iv+i,&read)){
 578         fprintf(stderr,"Error reading codebook test data (EOP).\n");
 579         exit(1);
 580       }
 581     for(i=0;i<TESTSIZE;i++)
 582       if(qv[i]!=iv[i]){
 583         fprintf(stderr,"input (%g) != output (%g) at position (%ld)\n",
 584                 iv[i],qv[i],i);
 585         exit(1);
 586       }
 587
 588     fprintf(stderr,"OK\n");
 589     ptr++;
 590   }
 591   exit(0);
 592 }
 593
 594 #endif