apps/codecs/Tremor/codebook.c

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