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