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.1 2000/01/11 16:12:30 xiphmont Exp $
  16
  17  ********************************************************************/
  18
  19 #include <stdlib.h>
  20 #include "vorbis/codec.h"
  21 #include "vorbis/codebook.h"
  22 #include "bitwise.h"
  23
  24 /**** pack/unpack helpers ******************************************/
  25 static int ilog(unsigned int v){
  26   int ret=0;
  27   while(v){
  28     ret++;
  29     v>>=1;
  30   }
  31   return(ret);
  32 }
  33
  34 static long _float24_pack(double val){
  35   int sign=0;
  36   long exp;
  37   long mant;
  38   if(val<0){
  39     sign=0x800000;
  40     val= -val;
  41   }
  42   exp= floor(log(val)/log(2));
  43   mant=rint(ldexp(val,17-exp));
  44   exp=(exp+VQ_FEXP_BIAS)<<18;
  45
  46   return(sign|exp|mant);
  47 }
  48
  49 static double _float24_unpack(long val){
  50   double mant=val&0x3ffff;
  51   double sign=val&0x800000;
  52   double exp =(val&0x7c0000)>>18;
  53   if(sign)mant= -mant;
  54   return(ldexp(mant,exp-17-VQ_FEXP_BIAS));
  55 }
  56
  57 /* given a list of word lengths, generate a list of codewords.  Works
  58    for length ordered or unordered, always assigns the lowest valued
  59    codewords first */
  60 long *_make_words(long *l,long n){
  61   long i,j;
  62   long marker[33];
  63   long *r=malloc(n*sizeof(long));
  64   memset(marker,0,sizeof(marker));
  65
  66   for(i=0;i<n;i++){
  67     long length=l[i];
  68     long entry=marker[[i]];
  69
  70     /* when we claim a node for an entry, we also claim the nodes
  71        below it (pruning off the imagined tree that may have dangled
  72        from it) as well as blocking the use of any nodes directly
  73        above for leaves */
  74
  75     /* update ourself */
  76     if(length<32 && (entry>>length)){
  77       /* error condition; the lengths must specify an overpopulated tree */
  78       free(r);
  79       return(NULL);
  80     }
  81     r[i]=entry;
  82
  83     /* Look to see if the next shorter marker points to the node
  84        above. if so, update it and repeat.  */
  85     {
  86       for(j=length;j>0;j--){
  87
  88         if(marker[j]&1){
  89           /* have to jump branches */
  90           if(j==1)
  91             marker[1]++;
  92           else
  93             marker[j]=marker[j-1]<<1;
  94           break; /* invariant says next upper marker would already
  95                     have been moved if it was on the same path */
  96         }
  97         marker[j]++;
  98       }
  99     }
 100
 101     /* prune the tree; the implicit invariant says all the longer
 102        markers were dangling from our just-taken node.  Dangle them
 103        from our *new* node. */
 104     for(j=length+1;j<33;j++)
 105       marker[j]=marker[j-1]<<1;
 106   }
 107
 108   /* bitreverse the words because our bitwise packer/unpacker is LSb
 109      endian */
 110   for(i=0;i<n;i++){
 111     long temp=0;
 112     for(j=0;j<l[i];j++){
 113       temp<<=1;
 114       temp|=(r[i]>>j)&1;
 115     }
 116     r[i]=temp;
 117   }
 118
 119   return(r);
 120 }
 121
 122 /* unpack the quantized list of values for encode/decode ***********/
 123 static double *_book_unquantize(codebook *b){
 124   long j,k;
 125   double mindel=float24_unpack(b->q_min);
 126   double delta=float24_unpack(b->q_delta);
 127   double *r=malloc(sizeof(double)*b->entries*b->dim);
 128
 129   for(j=0;j<b->entries;j++){
 130     double last=0.;
 131     for(k=0;k<b->dim;k++){
 132       double val=b->quantlist[j*b->dim+k]*delta+last+mindel;
 133       r[j*b->dim+k]=val;
 134       if(b->q_sequencep)last=val;
 135     }
 136   }
 137   return(r);
 138 }
 139
 140 /**** Defend the abstraction ****************************************/
 141
 142 /* some elements in the codebook structure are assumed to be pointers
 143    to static/shared storage (the pointers are duped, and free below
 144    does not touch them.  The fields are unused by decode):
 145
 146    quantlist,
 147    lengthlist,
 148    encode_tree
 149
 150 */
 151
 152 codebook *vorbis_book_dup(const codebook *b){
 153   codebook *r=malloc(1,sizeof(codebook));
 154   memcpy(r,b,sizeof(codebook));
 155
 156   /* handle non-flat storage */
 157   if(b->valuelist){
 158     r->valuelist=malloc(sizeof(double)*b->dim*b->entries);
 159     memcpy(r->valuelist,b->valuelist,sizeof(double)*b->dim*b->entries);
 160   }
 161   if(b->codelist){
 162     r->codelist=malloc(sizeof(long)*b->entries);
 163     memcpy(r->codelist,b->codelist,sizeof(long)**b->entries);
 164   }
 165
 166   /* encode tree is assumed to be static storage; don't free it */
 167
 168   if(b->decode_tree){
 169     long aux=b->decode_tree->aux;
 170     r->decode_tree=malloc(sizeof(decode_aux));
 171     r->decode_tree->aux=aux;
 172     r->decode_tree->ptr0=malloc(sizeof(long)*aux);
 173     r->decode_tree->ptr1=malloc(sizeof(long)*aux);
 174
 175     memcpy(r->decode_tree->ptr0,b->decode_tree->ptr0,sizeof(long)*aux);
 176     memcpy(r->decode_tree->ptr1,b->decode_tree->ptr1,sizeof(long)*aux);
 177   }
 178   return(r);
 179 }
 180
 181 void vorbis_book_free(codebook *b){
 182   if(b){
 183     if(b->decode_tree){
 184       free(b->decode_tree->ptr0);
 185       free(b->decode_tree->ptr1);
 186       memset(b->decode_tree,0,sizeof(decode_aux));
 187       free(b->decode_tree);
 188     }
 189     if(b->valuelist)free(b->valuelist);
 190     if(b->codelist)free(b->codelist);
 191     memset(b,0,sizeof(codebook));
 192     free(b);
 193   }
 194 }
 195
 196 /* packs the given codebook into the bitstream
 197    side effects: populates the valuelist and codeword members ***********/
 198 int vorbis_book_pack(codebook *c,oggpack_buffer *b){
 199   long i,j;
 200   int ordered=0;
 201
 202   /* first the basic parameters */
 203   _oggpack_write(b,0x564342,24);
 204   _oggpack_write(b,c->dim,16);
 205   _oggpack_write(b,c->entries,24);
 206
 207   /* pack the codewords.  There are two packings; length ordered and
 208      length random.  Decide between the two now. */
 209
 210   for(i=1;i<c->entries;i++)
 211     if(c->lengthlist[i]<c->lengthlist[i-1])break;
 212   if(i==c->entries)ordered=1;
 213
 214   if(ordered){
 215     /* length ordered.  We only need to say how many codewords of
 216        each length.  The actual codewords are generated
 217        deterministically */
 218
 219     long count=0;
 220     _oggpack_write(b,1,1);  /* ordered */
 221     _oggpack_write(b,c->lengthlist[0]-1,5); /* 1 to 32 */
 222
 223     for(i=1;i<c->entries;i++){
 224       long this=c->lengthlist[i];
 225       long last=c->lengthlist[i-1];
 226       if(this>last){
 227         for(j=last;j<this;j++){
 228           _oggpack_write(b,i-count,ilog(c->entries-count));
 229           count=i;
 230         }
 231       }
 232     }
 233     _oggpack_write(b,i-count,ilog(count));
 234
 235   }else{
 236     /* length random.  Again, we don't code the codeword itself, just
 237        the length.  This time, though, we have to encode each length */
 238     _oggpack_write(b,0,1);   /* unordered */
 239     for(i=0;i<c->entries;i++)
 240       _oggpack_write(b,c->lengthlist[i]-1,5);
 241   }
 242
 243   /* is the entry number the desired return value, or do we have a
 244      mapping? */
 245   if(codebook->quantlist){
 246     /* we have a mapping.  bundle it out. */
 247     _oggpack_write(b,1,1);
 248
 249     /* values that define the dequantization */
 250     _oggpack_write(b,c->q_min,24);
 251     _oggpack_write(b,c->q_delta,24);
 252     _oggpack_write(b,c->q_quant-1,4);
 253     _oggpack_write(b,c->q_sequencep,1);
 254
 255     /* quantized values */
 256     for(i=0;i<c->entries*c->dim;i++)
 257       _oggpack_write(b,c->quantlist[i],c->q_quant);
 258
 259   }else{
 260     /* no mapping. */
 261     _oggpack_write(b,0,1);
 262   }
 263
 264   c->codelist=_make_words(c->lengthlist,c->entries);
 265   c->valuelist=_book_unquantize(c);
 266
 267   return(0);
 268 }
 269
 270 /* unpacks a codebook from the packet buffer into the codebook struct,
 271    readies the codebook auxiliary structures for decode *************/
 272 codebook *vorbis_book_unpack(oggpack_buffer *b){
 273   codebook *c=calloc(1,sizeof(codebook));
 274
 275   /* make sure alignment is correct */
 276   if(_oggpack_read(b,24)!=0x564342)goto _eofout;
 277
 278   /* first the basic parameters */
 279   c->dim=_oggpack_read(b,16);
 280   c->entries=_oggpack_read(b,24);
 281   if(c->entries==-1)goto _eofout;
 282
 283   /* codeword ordering.... length ordered or unordered? */
 284   switch(_oggpack_read(b,1)){
 285   case 0:
 286     /* unordered */
 287     c->lengthlist=malloc(sizeof(long)*c->entries);
 288     for(i=0;i<c->entries;i++){
 289       long num=_oggpack_read(b,5);
 290       if(num==-1)goto _eofout;
 291       c->lengthlist[i]=num+1;
 292     }
 293
 294     break;
 295   case 1:
 296     /* ordered */
 297     {
 298       long length=_oggpack_read(b,5)+1;
 299       c->lengthlist=malloc(sizeof(long)*c->entries);
 300
 301       for(i=0;i<c->entries){
 302         long num=_oggpack_read(b,ilog(c->entries-i));
 303         if(num==-1)goto _eofout;
 304         for(j=0;j<num;j++,i++)
 305           c->lengthlist[i]=length;
 306         length++;
 307       }
 308     }
 309     break;
 310   default:
 311     /* EOF */
 312     return(NULL);
 313   }
 314
 315   /* now we generate the codewords for the given lengths */
 316   c->codelist=_make_words(c->lengthlist,c->entries);
 317   if(c->codelist==NULL)goto _errout;
 318
 319   /* ...and the decode helper tree from the codewords */
 320   {
 321     long top=0;
 322     decode_aux *t=c->decode_tree=malloc(sizeof(decode_aux));
 323     long *ptr0=c->decode_tree->ptr0=calloc(c->entries*2,sizeof(long));
 324     long *ptr1=c->decode_tree->ptr1=calloc(c->entries*2,sizeof(long));
 325     c->decode_tree->aux=c->entries*2;
 326
 327     for(i=0;i<c->entries;i++){
 328       long ptr=0;
 329       for(j=0;j<c->lengthlist[i]-1;j++){
 330         int bit=(c->codelist[i]>>j)&1;
 331         if(!bit){
 332           if(!ptr0[ptr])
 333             ptr0[ptr]= ++top;
 334           ptr=ptr0[ptr];
 335         }else{
 336           if(!ptr1[ptr])
 337             ptr1[ptr]= ++top;
 338           ptr=ptr1[ptr];
 339         }
 340       }
 341       if(!((c->codelist[i]>>j)&1))
 342         ptr0[ptr]=-i;
 343       else
 344         ptr1[ptr]=-i;
 345     }
 346   }
 347   /* no longer needed */
 348   free(c->lengthlist);c->lengthlist=NULL;
 349   free(c->codelist);c->codelist=NULL;
 350
 351   /* Do we have a mapping to unpack? */
 352   if(_oggpack_read(b,1)){
 353
 354     /* values that define the dequantization */
 355     c->q_min=_oggpack_read(b,24);
 356     c->q_delta=_oggpack_read(b,24);
 357     c->q_quant=_oggpack_read(b,4)+1;
 358     c->q_sequencep=_oggpack_read(b,1);
 359
 360     /* quantized values */
 361     c->quantlist=malloc(sizeof(double)*c->entries*c->dim);
 362     for(i=0;i<c->entries*c->dim;i++)
 363       c->quantlist[i]=_oggpack_read(b,c->q_quant);
 364     if(c->quantlist[i-1]==-1)goto _eofout;
 365     vorbis_book_unquantize(c);
 366     free(c->quantlist);c->quantlist=NULL;
 367   }
 368
 369   /* all set */
 370   return(c);
 371
 372  _errout:
 373  _eofout:
 374   if(c->lengthlist)free(c->lengthlist);c->lengthlist=NULL;
 375   if(c->quantlist)free(c->quantlist);c->quantlist=NULL;
 376   vorbis_book_free(c);
 377   return(NULL);
 378
 379 }
 380
 381 /* returns the number of bits ***************************************/
 382 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
 383   _oggpack_write(b,book->codelist[a],book->lengthlist[a]);
 384   return(book->lengthlist[a]);
 385 }
 386
 387 /* returns the number of bits and *modifies a* to the entry value *****/
 388 int vorbis_book_encodev(codebook *book, double *a, oggpack_buffer *b){
 389   encode_aux *t=book->encode_tree;
 390   int dim=book->dim;
 391   int ptr=0,k;
 392
 393   while(1){
 394     double c=0.;
 395     double *p=book->valuelist+t->p[ptr];
 396     double *q=book->valuelist+t->q[ptr];
 397
 398     for(k=0;k<dim;k++)
 399       c+=(p[k]-q[k])*(a[k]-(p[k]+q[k])*.5);
 400
 401     if(c>0.) /* in A */
 402       ptr= -t->ptr0[ptr];
 403     else     /* in B */
 404       ptr= -t->ptr1[ptr];
 405     if(ptr<=0)break;
 406   }
 407   memcpy(a,book->valuelist-ptr*dim,dim*sizeof(double));
 408   return(vorbis_book_encode(book,-ptr,b));
 409 }
 410
 411 /* returns the entry number or -1 on eof ****************************/
 412 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
 413   long ptr=0;
 414   decode_aux *t=book->decode_tree;
 415   do{
 416     switch(__oggpack_read1(b)){
 417     case 0:
 418       ptr=t->ptr0[ptr];
 419       break;
 420     case 1:
 421       ptr=t->ptr1[ptr];
 422       break;
 423     case -1:
 424       return(-1);
 425     }
 426   }while(ptr>0);
 427   return(-ptr);
 428 }
 429
 430 /* returns the entry number or -1 on eof ****************************/
 431 long vorbis_book_decodev(codebook *book, double *a, oggpack_buffer *b){
 432   long entry=vorbis_book_decode(book,b);
 433   if(entry==-1)return(-1);
 434   memcpy(a,b->valuelist+entry*b->dim,sizeof(double)*b->dim);
 435   return(entry);
 436 }
 437