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 STIN 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
 175   if(lok<0){
 176     oggpack_adv(b,1); /* force eop */
 177     return -1;
 178   }
 179
 180   /* bisect search for the codeword in the ordered list */
 181   {
 182     ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
 183
 184     while(hi-lo>1){
 185       long p=(hi-lo)>>1;
 186       long test=book->codelist[lo+p]>testword;
 187       lo+=p&(test-1);
 188       hi-=p&(-test);
 189     }
 190
 191     if(book->dec_codelengths[lo]<=read){
 192       oggpack_adv(b, book->dec_codelengths[lo]);
 193       return(lo);
 194     }
 195   }
 196
 197   oggpack_adv(b, read+1);
 198   return(-1);
 199 }
 200
 201 /* Decode side is specced and easier, because we don't need to find
 202    matches using different criteria; we simply read and map.  There are
 203    two things we need to do 'depending':
 204
 205    We may need to support interleave.  We don't really, but it's
 206    convenient to do it here rather than rebuild the vector later.
 207
 208    Cascades may be additive or multiplicitive; this is not inherent in
 209    the codebook, but set in the code using the codebook.  Like
 210    interleaving, it's easiest to do it here.
 211    addmul==0 -> declarative (set the value)
 212    addmul==1 -> additive
 213    addmul==2 -> multiplicitive */
 214
 215 /* returns the [original, not compacted] entry number or -1 on eof *********/
 216 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
 217   if(book->used_entries>0){
 218     long packed_entry=decode_packed_entry_number(book,b);
 219     if(packed_entry>=0)
 220       return(book->dec_index[packed_entry]);
 221   }
 222
 223   /* if there's no dec_index, the codebook unpacking isn't collapsed */
 224   return(-1);
 225 }
 226
 227 /* returns 0 on OK or -1 on eof *************************************/
 228 long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a,
 229                               oggpack_buffer *b,int n,int point){
 230   if(book->used_entries>0){
 231     int step=n/book->dim;
 232     long *entry = (long *)alloca(sizeof(*entry)*step);
 233     ogg_int32_t **t = (ogg_int32_t **)alloca(sizeof(*t)*step);
 234     int i,j,o;
 235     int shift=point-book->binarypoint;
 236
 237     if(shift>=0){
 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     }else{
 247       for (i = 0; i < step; i++) {
 248         entry[i]=decode_packed_entry_number(book,b);
 249         if(entry[i]==-1)return(-1);
 250         t[i] = book->valuelist+entry[i]*book->dim;
 251       }
 252       for(i=0,o=0;i<book->dim;i++,o+=step)
 253         for (j=0;j<step;j++)
 254           a[o+j]+=t[j][i]<<-shift;
 255     }
 256   }
 257   return(0);
 258 }
 259
 260 long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a,
 261                              oggpack_buffer *b,int n,int point){
 262   if(book->used_entries>0){
 263     int i,j,entry;
 264     ogg_int32_t *t;
 265     int shift=point-book->binarypoint;
 266
 267     if(shift>=0){
 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     }else{
 276       for(i=0;i<n;){
 277         entry = decode_packed_entry_number(book,b);
 278         if(entry==-1)return(-1);
 279         t     = book->valuelist+entry*book->dim;
 280         for (j=0;j<book->dim;)
 281           a[i++]+=t[j++]<<-shift;
 282       }
 283     }
 284   }
 285   return(0);
 286 }
 287
 288 long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a,
 289                              oggpack_buffer *b,int n,int point){
 290   if(book->used_entries>0){
 291     int i,j,entry;
 292     ogg_int32_t *t;
 293     int shift=point-book->binarypoint;
 294
 295     if(shift>=0){
 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     }else{
 306
 307       for(i=0;i<n;){
 308         entry = decode_packed_entry_number(book,b);
 309         if(entry==-1)return(-1);
 310         t     = book->valuelist+entry*book->dim;
 311         for (j=0;j<book->dim;){
 312           a[i++]=t[j++]<<-shift;
 313         }
 314       }
 315     }
 316   }else{
 317
 318     int i,j;
 319     for(i=0;i<n;){
 320       for (j=0;j<book->dim;){
 321         a[i++]=0;
 322       }
 323     }
 324   }
 325   return(0);
 326 }
 327
 328 long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,\
 329                               long offset,int ch,
 330                               oggpack_buffer *b,int n,int point){
 331   if(book->used_entries>0){
 332     long i,j,entry;
 333     int chptr=0;
 334     int shift=point-book->binarypoint;
 335
 336     if(shift>=0){
 337
 338       for(i=offset;i<offset+n;){
 339         entry = decode_packed_entry_number(book,b);
 340         if(entry==-1)return(-1);
 341         {
 342           const ogg_int32_t *t = book->valuelist+entry*book->dim;
 343           for (j=0;j<book->dim;j++){
 344             a[chptr++][i]+=t[j]>>shift;
 345             if(chptr==ch){
 346               chptr=0;
 347               i++;
 348             }
 349           }
 350         }
 351       }
 352     }else{
 353
 354       for(i=offset;i<offset+n;){
 355         entry = decode_packed_entry_number(book,b);
 356         if(entry==-1)return(-1);
 357         {
 358           const ogg_int32_t *t = book->valuelist+entry*book->dim;
 359           for (j=0;j<book->dim;j++){
 360             a[chptr++][i]+=t[j]<<-shift;
 361             if(chptr==ch){
 362               chptr=0;
 363               i++;
 364             }
 365           }
 366         }
 367       }
 368     }
 369   }
 370   return(0);
 371 }