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