tremor/codebook.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE.   *
   4  *                                                                  *
   5  * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2002    *
   6  * BY THE Xiph.Org FOUNDATION http://www.xiph.org/                  *
   7  * ALL REDISTRIBUTION RIGHTS RESERVED.                              *
   8  *                                                                  *
   9  ********************************************************************
  10
  11  function: basic codebook pack/unpack/code/decode operations
  12
  13  ********************************************************************/
  14
  15 #include <stdlib.h>
  16 #include <string.h>
  17 #include <math.h>
  18 #include "ogg.h"
  19 #include "ivorbiscodec.h"
  20 #include "codebook.h"
  21 #include "misc.h"
  22 #include "os.h"
  23
  24 /* unpacks a codebook from the packet buffer into the codebook struct,
  25    readies the codebook auxiliary structures for decode *************/
  26 int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){
  27   long i,j;
  28   memset(s,0,sizeof(*s));
  29
  30   /* make sure alignment is correct */
  31   if(oggpack_read(opb,24)!=0x564342)goto _eofout;
  32
  33   /* first the basic parameters */
  34   s->dim=oggpack_read(opb,16);
  35   s->entries=oggpack_read(opb,24);
  36   if(s->entries==-1)goto _eofout;
  37
  38   /* codeword ordering.... length ordered or unordered? */
  39   switch((int)oggpack_read(opb,1)){
  40   case 0:
  41     /* unordered */
  42     s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
  43
  44     /* allocated but unused entries? */
  45     if(oggpack_read(opb,1)){
  46       /* yes, unused entries */
  47
  48       for(i=0;i<s->entries;i++){
  49         if(oggpack_read(opb,1)){
  50           long num=oggpack_read(opb,5);
  51           if(num==-1)goto _eofout;
  52           s->lengthlist[i]=num+1;
  53         }else
  54           s->lengthlist[i]=0;
  55       }
  56     }else{
  57       /* all entries used; no tagging */
  58       for(i=0;i<s->entries;i++){
  59         long num=oggpack_read(opb,5);
  60         if(num==-1)goto _eofout;
  61         s->lengthlist[i]=num+1;
  62       }
  63     }
  64
  65     break;
  66   case 1:
  67     /* ordered */
  68     {
  69       long length=oggpack_read(opb,5)+1;
  70       s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
  71
  72       for(i=0;i<s->entries;){
  73         long num=oggpack_read(opb,_ilog(s->entries-i));
  74         if(num==-1)goto _eofout;
  75         for(j=0;j<num && i<s->entries;j++,i++)
  76           s->lengthlist[i]=length;
  77         length++;
  78       }
  79     }
  80     break;
  81   default:
  82     /* EOF */
  83     return(-1);
  84   }
  85
  86   /* Do we have a mapping to unpack? */
  87   switch((s->maptype=oggpack_read(opb,4))){
  88   case 0:
  89     /* no mapping */
  90     break;
  91   case 1: case 2:
  92     /* implicitly populated value mapping */
  93     /* explicitly populated value mapping */
  94
  95     s->q_min=oggpack_read(opb,32);
  96     s->q_delta=oggpack_read(opb,32);
  97     s->q_quant=oggpack_read(opb,4)+1;
  98     s->q_sequencep=oggpack_read(opb,1);
  99
 100     {
 101       int quantvals=0;
 102       switch(s->maptype){
 103       case 1:
 104         quantvals=_book_maptype1_quantvals(s);
 105         break;
 106       case 2:
 107         quantvals=s->entries*s->dim;
 108         break;
 109       }
 110
 111       /* quantized values */
 112       s->quantlist=(long *)_ogg_malloc(sizeof(*s->quantlist)*quantvals);
 113       for(i=0;i<quantvals;i++)
 114         s->quantlist[i]=oggpack_read(opb,s->q_quant);
 115
 116       if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
 117     }
 118     break;
 119   default:
 120     goto _errout;
 121   }
 122
 123   /* all set */
 124   return(0);
 125
 126  _errout:
 127  _eofout:
 128   vorbis_staticbook_clear(s);
 129   return(-1);
 130 }
 131
 132 /* the 'eliminate the decode tree' optimization actually requires the
 133    codewords to be MSb first, not LSb.  This is an annoying inelegancy
 134    (and one of the first places where carefully thought out design
 135    turned out to be wrong; Vorbis II and future Ogg codecs should go
 136    to an MSb bitpacker), but not actually the huge hit it appears to
 137    be.  The first-stage decode table catches most words so that
 138    bitreverse is not in the main execution path. */
 139
 140 static ogg_uint32_t bitreverse(ogg_uint32_t x){
 141   x=    ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
 142   x=    ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
 143   x=    ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
 144   x=    ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
 145   return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
 146 }
 147
 148 static inline long decode_packed_entry_number(codebook *book,
 149                                               oggpack_buffer *b){
 150   int  read=book->dec_maxlength;
 151   long lo,hi;
 152   long lok = oggpack_look(b,book->dec_firsttablen);
 153
 154   if (lok >= 0) {
 155     long entry = book->dec_firsttable[lok];
 156     if(entry&0x80000000UL){
 157       lo=(entry>>15)&0x7fff;
 158       hi=book->used_entries-(entry&0x7fff);
 159     }else{
 160       oggpack_adv(b, book->dec_codelengths[entry-1]);
 161       return(entry-1);
 162     }
 163   }else{
 164     lo=0;
 165     hi=book->used_entries;
 166   }
 167
 168   lok = oggpack_look(b, read);
 169
 170   while(lok<0 && read>1)
 171     lok = oggpack_look(b, --read);
 172   if(lok<0)return -1;
 173
 174   /* bisect search for the codeword in the ordered list */
 175   {
 176     ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
 177
 178     while(hi-lo>1){
 179       long p=(hi-lo)>>1;
 180       long test=book->codelist[lo+p]>testword;
 181       lo+=p&(test-1);
 182       hi-=p&(-test);
 183     }
 184
 185     if(book->dec_codelengths[lo]<=read){
 186       oggpack_adv(b, book->dec_codelengths[lo]);
 187       return(lo);
 188     }
 189   }
 190
 191   oggpack_adv(b, read);
 192   return(-1);
 193 }
 194
 195 /* Decode side is specced and easier, because we don't need to find
 196    matches using different criteria; we simply read and map.  There are
 197    two things we need to do 'depending':
 198
 199    We may need to support interleave.  We don't really, but it's
 200    convenient to do it here rather than rebuild the vector later.
 201
 202    Cascades may be additive or multiplicitive; this is not inherent in
 203    the codebook, but set in the code using the codebook.  Like
 204    interleaving, it's easiest to do it here.
 205    addmul==0 -> declarative (set the value)
 206    addmul==1 -> additive
 207    addmul==2 -> multiplicitive */
 208
 209 /* returns the [original, not compacted] entry number or -1 on eof *********/
 210 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
 211   long packed_entry=decode_packed_entry_number(book,b);
 212   if(packed_entry>=0)
 213     return(book->dec_index[packed_entry]);
 214
 215   /* if there's no dec_index, the codebook unpacking isn't collapsed */
 216   return(packed_entry);
 217 }
 218
 219 /* returns 0 on OK or -1 on eof *************************************/
 220 long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a,
 221                               oggpack_buffer *b,int n,int point){
 222   int step=n/book->dim;
 223   long *entry = (long *)alloca(sizeof(*entry)*step);
 224   ogg_int32_t **t = (ogg_int32_t **)alloca(sizeof(*t)*step);
 225   int i,j,o;
 226   int shift=point-book->binarypoint;
 227
 228   if(shift>=0){
 229     for (i = 0; i < step; i++) {
 230       entry[i]=decode_packed_entry_number(book,b);
 231       if(entry[i]==-1)return(-1);
 232       t[i] = book->valuelist+entry[i]*book->dim;
 233     }
 234     for(i=0,o=0;i<book->dim;i++,o+=step)
 235       for (j=0;j<step;j++)
 236         a[o+j]+=t[j][i]>>shift;
 237   }else{
 238     for (i = 0; i < step; i++) {
 239       entry[i]=decode_packed_entry_number(book,b);
 240       if(entry[i]==-1)return(-1);
 241       t[i] = book->valuelist+entry[i]*book->dim;
 242     }
 243     for(i=0,o=0;i<book->dim;i++,o+=step)
 244       for (j=0;j<step;j++)
 245         a[o+j]+=t[j][i]<<-shift;
 246   }
 247   return(0);
 248 }
 249
 250 long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a,
 251                              oggpack_buffer *b,int n,int point){
 252   int i,j,entry;
 253   ogg_int32_t *t;
 254   int shift=point-book->binarypoint;
 255
 256   if(shift>=0){
 257     for(i=0;i<n;){
 258       entry = decode_packed_entry_number(book,b);
 259       if(entry==-1)return(-1);
 260       t     = book->valuelist+entry*book->dim;
 261       for (j=0;j<book->dim;)
 262         a[i++]+=t[j++]>>shift;
 263     }
 264   }else{
 265     for(i=0;i<n;){
 266       entry = decode_packed_entry_number(book,b);
 267       if(entry==-1)return(-1);
 268       t     = book->valuelist+entry*book->dim;
 269       for (j=0;j<book->dim;)
 270         a[i++]+=t[j++]<<-shift;
 271     }
 272   }
 273   return(0);
 274 }
 275
 276 long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a,
 277                              oggpack_buffer *b,int n,int point){
 278   int i,j,entry;
 279   ogg_int32_t *t;
 280   int shift=point-book->binarypoint;
 281
 282   if(shift>=0){
 283
 284     for(i=0;i<n;){
 285       entry = decode_packed_entry_number(book,b);
 286       if(entry==-1)return(-1);
 287       t     = book->valuelist+entry*book->dim;
 288       for (j=0;j<book->dim;){
 289         a[i++]=t[j++]>>shift;
 290       }
 291     }
 292   }else{
 293
 294     for(i=0;i<n;){
 295       entry = decode_packed_entry_number(book,b);
 296       if(entry==-1)return(-1);
 297       t     = book->valuelist+entry*book->dim;
 298       for (j=0;j<book->dim;){
 299         a[i++]=t[j++]<<-shift;
 300       }
 301     }
 302   }
 303   return(0);
 304 }
 305
 306 long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,\
 307                               long offset,int ch,
 308                               oggpack_buffer *b,int n,int point){
 309   long i,j,entry;
 310   int chptr=0;
 311   int shift=point-book->binarypoint;
 312
 313   if(shift>=0){
 314
 315     for(i=offset;i<offset+n;){
 316       entry = decode_packed_entry_number(book,b);
 317       if(entry==-1)return(-1);
 318       {
 319         const ogg_int32_t *t = book->valuelist+entry*book->dim;
 320         for (j=0;j<book->dim;j++){
 321           a[chptr++][i]+=t[j]>>shift;
 322           if(chptr==ch){
 323             chptr=0;
 324             i++;
 325           }
 326         }
 327       }
 328     }
 329   }else{
 330
 331     for(i=offset;i<offset+n;){
 332       entry = decode_packed_entry_number(book,b);
 333       if(entry==-1)return(-1);
 334       {
 335         const ogg_int32_t *t = book->valuelist+entry*book->dim;
 336         for (j=0;j<book->dim;j++){
 337           a[chptr++][i]+=t[j]<<-shift;
 338           if(chptr==ch){
 339             chptr=0;
 340             i++;
 341           }
 342         }
 343       }
 344     }
 345   }
 346   return(0);
 347 }