apps/codecs/libtremor/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 STIN 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 (LIKELY(lok >= 0)) {
 158     long entry = book->dec_firsttable[lok];
 159     if(UNLIKELY(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
 176   if(lok<0){
 177     oggpack_adv(b,1); /* force eop */
 178     return -1;
 179   }
 180
 181   /* bisect search for the codeword in the ordered list */
 182   {
 183     ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
 184
 185     while(hi-lo>1){
 186       long p=(hi-lo)>>1;
 187       long test=book->codelist[lo+p]>testword;
 188       lo+=p&(test-1);
 189       hi-=p&(-test);
 190     }
 191
 192     if(book->dec_codelengths[lo]<=read){
 193       oggpack_adv(b, book->dec_codelengths[lo]);
 194       return(lo);
 195     }
 196   }
 197
 198   oggpack_adv(b, read+1);
 199   return(-1);
 200 }
 201
 202 static long decode_packed_block(codebook *book, oggpack_buffer *b,
 203                                 long *buf, int n){
 204   long *bufptr = buf;
 205   long *bufend = buf + n;
 206
 207   while (bufptr<bufend) {
 208     if (b->headend > 8) {
 209       ogg_uint32_t *ptr;
 210       unsigned long bit, bitend;
 211       unsigned long adr;
 212       ogg_uint32_t cache = 0;
 213       int cachesize = 0;
 214
 215       adr = (unsigned long)b->headptr;
 216       bit = (adr&3)*8+b->headbit;
 217       ptr = (ogg_uint32_t *)(adr&~3);
 218       bitend = ((adr&3)+b->headend)*8;
 219       while (bufptr<bufend){
 220         long entry, lo, hi;
 221         if (UNLIKELY(cachesize<book->dec_maxlength)) {
 222           if (bit-cachesize+32>=bitend)
 223             break;
 224           bit-=cachesize;
 225           cache=letoh32(ptr[bit>>5]) >> (bit&31);
 226           if (bit&31)
 227             cache|=letoh32(ptr[(bit>>5)+1]) << (32-(bit&31));
 228           cachesize=32;
 229           bit+=32;
 230         }
 231
 232         entry=book->dec_firsttable[cache&((1<<book->dec_firsttablen)-1)];
 233         if(UNLIKELY(entry&0x80000000UL)){
 234           lo=(entry>>15)&0x7fff;
 235           hi=book->used_entries-(entry&0x7fff);
 236           {
 237             ogg_uint32_t testword=bitreverse((ogg_uint32_t)cache);
 238
 239             while(LIKELY(hi-lo>1)){
 240               long p=(hi-lo)>>1;
 241               if (book->codelist[lo+p]>testword)
 242                 hi-=p;
 243               else
 244                 lo+=p;
 245             }
 246             entry=lo;
 247           }
 248         }else
 249           entry--;
 250
 251         *bufptr++=entry;
 252         {
 253           int l=book->dec_codelengths[entry];
 254           cachesize-=l;
 255           cache>>=l;
 256         }
 257       }
 258
 259       adr=(unsigned long)b->headptr;
 260       bit-=(adr&3)*8+cachesize;
 261       b->headend-=(bit/8);
 262       b->headptr+=bit/8;
 263       b->headbit=bit%8;
 264     } else {
 265       long r = decode_packed_entry_number(book, b);
 266       if (r == -1) return bufptr-buf;
 267       *bufptr++ = r;
 268     }
 269   }
 270   return n;
 271 }
 272
 273
 274 /* Decode side is specced and easier, because we don't need to find
 275    matches using different criteria; we simply read and map.  There are
 276    two things we need to do 'depending':
 277
 278    We may need to support interleave.  We don't really, but it's
 279    convenient to do it here rather than rebuild the vector later.
 280
 281    Cascades may be additive or multiplicitive; this is not inherent in
 282    the codebook, but set in the code using the codebook.  Like
 283    interleaving, it's easiest to do it here.
 284    addmul==0 -> declarative (set the value)
 285    addmul==1 -> additive
 286    addmul==2 -> multiplicitive */
 287
 288 /* returns the [original, not compacted] entry number or -1 on eof *********/
 289 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
 290   if(book->used_entries>0){
 291     long packed_entry=decode_packed_entry_number(book,b);
 292     if(packed_entry>=0)
 293       return(book->dec_index[packed_entry]);
 294   }
 295
 296   /* if there's no dec_index, the codebook unpacking isn't collapsed */
 297   return(-1);
 298 }
 299
 300 /* returns 0 on OK or -1 on eof *************************************/
 301 long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a,
 302                               oggpack_buffer *b,int n,int point){
 303   if(book->used_entries>0){
 304     int step=n/book->dim;
 305     long *entry = (long *)alloca(sizeof(*entry)*step);
 306     ogg_int32_t **t = (ogg_int32_t **)alloca(sizeof(*t)*step);
 307     int i,j,o;
 308     int shift=point-book->binarypoint;
 309
 310     if(shift>=0){
 311       for (i = 0; i < step; i++) {
 312         entry[i]=decode_packed_entry_number(book,b);
 313         if(entry[i]==-1)return(-1);
 314         t[i] = book->valuelist+entry[i]*book->dim;
 315       }
 316       for(i=0,o=0;i<book->dim;i++,o+=step)
 317         for (j=0;j<step;j++)
 318           a[o+j]+=t[j][i]>>shift;
 319     }else{
 320       for (i = 0; i < step; i++) {
 321         entry[i]=decode_packed_entry_number(book,b);
 322         if(entry[i]==-1)return(-1);
 323         t[i] = book->valuelist+entry[i]*book->dim;
 324       }
 325       for(i=0,o=0;i<book->dim;i++,o+=step)
 326         for (j=0;j<step;j++)
 327           a[o+j]+=t[j][i]<<-shift;
 328     }
 329   }
 330   return(0);
 331 }
 332
 333 long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a,
 334                              oggpack_buffer *b,int n,int point){
 335   if(book->used_entries>0){
 336     int i,j,entry;
 337     ogg_int32_t *t;
 338     int shift=point-book->binarypoint;
 339
 340     if(shift>=0){
 341       for(i=0;i<n;){
 342         entry = decode_packed_entry_number(book,b);
 343         if(entry==-1)return(-1);
 344         t     = book->valuelist+entry*book->dim;
 345         for (j=0;j<book->dim;)
 346           a[i++]+=t[j++]>>shift;
 347       }
 348     }else{
 349       shift = -shift;
 350       for(i=0;i<n;){
 351         entry = decode_packed_entry_number(book,b);
 352         if(entry==-1)return(-1);
 353         t     = book->valuelist+entry*book->dim;
 354         for (j=0;j<book->dim;)
 355           a[i++]+=t[j++]<<shift;
 356       }
 357     }
 358   }
 359   return(0);
 360 }
 361
 362 long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a,
 363                              oggpack_buffer *b,int n,int point){
 364   if(book->used_entries>0){
 365     int i,j,entry;
 366     ogg_int32_t *t;
 367     int shift=point-book->binarypoint;
 368
 369     if(shift>=0){
 370
 371       for(i=0;i<n;){
 372         entry = decode_packed_entry_number(book,b);
 373         if(entry==-1)return(-1);
 374         t     = book->valuelist+entry*book->dim;
 375         for (j=0;j<book->dim;){
 376           a[i++]=t[j++]>>shift;
 377         }
 378       }
 379     }else{
 380       shift = -shift;
 381       for(i=0;i<n;){
 382         entry = decode_packed_entry_number(book,b);
 383         if(entry==-1)return(-1);
 384         t     = book->valuelist+entry*book->dim;
 385         for (j=0;j<book->dim;){
 386           a[i++]=t[j++]<<shift;
 387         }
 388       }
 389     }
 390   }else{
 391
 392     int i,j;
 393     for(i=0;i<n;){
 394       for (j=0;j<book->dim;){
 395         a[i++]=0;
 396       }
 397     }
 398   }
 399   return(0);
 400 }
 401
 402 static long vorbis_book_decodevv_add_2ch_even(codebook *book,ogg_int32_t **a,
 403                                               long offset,oggpack_buffer *b,
 404                                               int n,int point){
 405   long i,k,chunk,read;
 406   int shift=point-book->binarypoint;
 407   long entries[32];
 408   ogg_int32_t *p0 = &(a[0][offset]);
 409   ogg_int32_t *p1 = &(a[1][offset]);
 410
 411   if(shift>=0){
 412
 413     for(i=0;i<n;){
 414       chunk=32;
 415       if (chunk*book->dim>(n-i)*2)
 416         chunk=((n-i)*2+book->dim-1)/book->dim;
 417       read = decode_packed_block(book,b,entries,chunk);
 418       for(k=0;k<read;k++){
 419         const ogg_int32_t *t = book->valuelist+entries[k]*book->dim;
 420         const ogg_int32_t *u = t+book->dim;
 421         do{
 422           *p0++ += *t++>>shift;
 423           *p1++ += *t++>>shift;
 424         }while(t<u);
 425       }
 426       if (read<chunk)return-1;
 427       i += read*book->dim/2;
 428     }
 429   }else{
 430     shift = -shift;
 431     for(i=0;i<n;){
 432       chunk=32;
 433       if (chunk*book->dim>(n-i)*2)
 434         chunk=((n-i)*2+book->dim-1)/book->dim;
 435       read = decode_packed_block(book,b,entries,chunk);
 436       for(k=0;k<read;k++){
 437         const ogg_int32_t *t = book->valuelist+entries[k]*book->dim;
 438         const ogg_int32_t *u = t+book->dim;
 439         do{
 440           *p0++ += *t++<<shift;
 441           *p1++ += *t++<<shift;
 442         }while(t<u);
 443       }
 444       if (read<chunk)return-1;
 445       i += read*book->dim/2;
 446     }
 447   }
 448   return(0);
 449 }
 450
 451 long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,
 452                               long offset,int ch,
 453                               oggpack_buffer *b,int n,int point){
 454   if(LIKELY(book->used_entries>0)){
 455     long i,j,k,chunk,read;
 456     int chptr=0;
 457     int shift=point-book->binarypoint;
 458     long entries[32];
 459
 460     if (!(book->dim&1) && ch==2)
 461       return vorbis_book_decodevv_add_2ch_even(book,a,offset,b,n,point);
 462
 463     if(shift>=0){
 464
 465       for(i=offset;i<offset+n;){
 466         chunk=32;
 467         if (chunk*book->dim>(offset+n-i)*ch)
 468           chunk=((offset+n-i)*ch+book->dim-1)/book->dim;
 469         read = decode_packed_block(book,b,entries,chunk);
 470         for(k=0;k<read;k++){
 471           const ogg_int32_t *t = book->valuelist+entries[k]*book->dim;
 472           for (j=0;j<book->dim;j++){
 473             a[chptr++][i]+=t[j]>>shift;
 474             if(chptr==ch){
 475               chptr=0;
 476               i++;
 477             }
 478           }
 479         }
 480         if (read<chunk)return-1;
 481       }
 482     }else{
 483       shift = -shift;
 484       for(i=offset;i<offset+n;){
 485         chunk=32;
 486         if (chunk*book->dim>(offset+n-i)*ch)
 487           chunk=((offset+n-i)*ch+book->dim-1)/book->dim;
 488         read = decode_packed_block(book,b,entries,chunk);
 489         for(k=0;k<read;k++){
 490           const ogg_int32_t *t = book->valuelist+entries[k]*book->dim;
 491           for (j=0;j<book->dim;j++){
 492             a[chptr++][i]+=t[j]<<shift;
 493             if(chptr==ch){
 494               chptr=0;
 495               i++;
 496             }
 497           }
 498         }
 499         if (read<chunk)return-1;
 500       }
 501     }
 502   }
 503   return(0);
 504 }