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 <stdlib.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 ogg_uint32_t bitreverse(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){
 214   long packed_entry=decode_packed_entry_number(book,b);
 215   if(packed_entry>=0)
 216     return(book->dec_index[packed_entry]);
 217
 218   /* if there's no dec_index, the codebook unpacking isn't collapsed */
 219   return(packed_entry);
 220 }
 221
 222 /* returns 0 on OK or -1 on eof *************************************/
 223 long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a,
 224                               oggpack_buffer *b,int n,int point){
 225   int step=n/book->dim;
 226   long *entry = (long *)alloca(sizeof(*entry)*step);
 227   ogg_int32_t **t = (ogg_int32_t **)alloca(sizeof(*t)*step);
 228   int i,j,o;
 229   int shift=point-book->binarypoint;
 230
 231   if(shift>=0){
 232     for (i = 0; i < step; i++) {
 233       entry[i]=decode_packed_entry_number(book,b);
 234       if(entry[i]==-1)return(-1);
 235       t[i] = book->valuelist+entry[i]*book->dim;
 236     }
 237     for(i=0,o=0;i<book->dim;i++,o+=step)
 238       for (j=0;j<step;j++)
 239         a[o+j]+=t[j][i]>>shift;
 240   }else{
 241     for (i = 0; i < step; i++) {
 242       entry[i]=decode_packed_entry_number(book,b);
 243       if(entry[i]==-1)return(-1);
 244       t[i] = book->valuelist+entry[i]*book->dim;
 245     }
 246     for(i=0,o=0;i<book->dim;i++,o+=step)
 247       for (j=0;j<step;j++)
 248         a[o+j]+=t[j][i]<<-shift;
 249   }
 250   return(0);
 251 }
 252
 253 long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a,
 254                              oggpack_buffer *b,int n,int point){
 255   int i,j,entry;
 256   ogg_int32_t *t;
 257   int shift=point-book->binarypoint;
 258
 259   if(shift>=0){
 260     for(i=0;i<n;){
 261       entry = decode_packed_entry_number(book,b);
 262       if(entry==-1)return(-1);
 263       t     = book->valuelist+entry*book->dim;
 264       for (j=0;j<book->dim;)
 265         a[i++]+=t[j++]>>shift;
 266     }
 267   }else{
 268     for(i=0;i<n;){
 269       entry = decode_packed_entry_number(book,b);
 270       if(entry==-1)return(-1);
 271       t     = book->valuelist+entry*book->dim;
 272       for (j=0;j<book->dim;)
 273         a[i++]+=t[j++]<<-shift;
 274     }
 275   }
 276   return(0);
 277 }
 278
 279 long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a,
 280                              oggpack_buffer *b,int n,int point){
 281   int i,j,entry;
 282   ogg_int32_t *t;
 283   int shift=point-book->binarypoint;
 284
 285   if(shift>=0){
 286
 287     for(i=0;i<n;){
 288       entry = decode_packed_entry_number(book,b);
 289       if(entry==-1)return(-1);
 290       t     = book->valuelist+entry*book->dim;
 291       for (j=0;j<book->dim;){
 292         a[i++]=t[j++]>>shift;
 293       }
 294     }
 295   }else{
 296
 297     for(i=0;i<n;){
 298       entry = decode_packed_entry_number(book,b);
 299       if(entry==-1)return(-1);
 300       t     = book->valuelist+entry*book->dim;
 301       for (j=0;j<book->dim;){
 302         a[i++]=t[j++]<<-shift;
 303       }
 304     }
 305   }
 306   return(0);
 307 }
 308
 309 long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,\
 310                               long offset,int ch,
 311                               oggpack_buffer *b,int n,int point){
 312   long i,j,entry;
 313   int chptr=0;
 314   int shift=point-book->binarypoint;
 315
 316   if(shift>=0){
 317
 318     for(i=offset;i<offset+n;){
 319       entry = decode_packed_entry_number(book,b);
 320       if(entry==-1)return(-1);
 321       {
 322         const ogg_int32_t *t = book->valuelist+entry*book->dim;
 323         for (j=0;j<book->dim;j++){
 324           a[chptr++][i]+=t[j]>>shift;
 325           if(chptr==ch){
 326             chptr=0;
 327             i++;
 328           }
 329         }
 330       }
 331     }
 332   }else{
 333
 334     for(i=offset;i<offset+n;){
 335       entry = decode_packed_entry_number(book,b);
 336       if(entry==-1)return(-1);
 337       {
 338         const ogg_int32_t *t = book->valuelist+entry*book->dim;
 339         for (j=0;j<book->dim;j++){
 340           a[chptr++][i]+=t[j]<<-shift;
 341           if(chptr==ch){
 342             chptr=0;
 343             i++;
 344           }
 345         }
 346       }
 347     }
 348   }
 349   return(0);
 350 }