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 static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){
  30   long i,j;
  31   static_codebook *s=_ogg_calloc(1,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   if(_ilog(s->dim)+_ilog(s->entries)>24)goto _eofout;
  42
  43   /* codeword ordering.... length ordered or unordered? */
  44   switch((int)oggpack_read(opb,1)){
  45   case 0:
  46     /* unordered */
  47     s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
  48
  49     /* allocated but unused entries? */
  50     if(oggpack_read(opb,1)){
  51       /* yes, unused entries */
  52
  53       for(i=0;i<s->entries;i++){
  54         if(oggpack_read(opb,1)){
  55           long num=oggpack_read(opb,5);
  56           if(num==-1)goto _eofout;
  57           s->lengthlist[i]=num+1;
  58         }else
  59           s->lengthlist[i]=0;
  60       }
  61     }else{
  62       /* all entries used; no tagging */
  63       for(i=0;i<s->entries;i++){
  64         long num=oggpack_read(opb,5);
  65         if(num==-1)goto _eofout;
  66         s->lengthlist[i]=num+1;
  67       }
  68     }
  69
  70     break;
  71   case 1:
  72     /* ordered */
  73     {
  74       long length=oggpack_read(opb,5)+1;
  75       s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
  76
  77       for(i=0;i<s->entries;){
  78         long num=oggpack_read(opb,_ilog(s->entries-i));
  79         if(num==-1)goto _eofout;
  80         if(length>32)goto _errout;
  81         for(j=0;j<num && i<s->entries;j++,i++)
  82           s->lengthlist[i]=length;
  83         length++;
  84       }
  85     }
  86     break;
  87   default:
  88     /* EOF */
  89     goto _eofout;
  90   }
  91
  92   /* Do we have a mapping to unpack? */
  93   switch((s->maptype=oggpack_read(opb,4))){
  94   case 0:
  95     /* no mapping */
  96     break;
  97   case 1: case 2:
  98     /* implicitly populated value mapping */
  99     /* explicitly populated value mapping */
 100
 101     s->q_min=oggpack_read(opb,32);
 102     s->q_delta=oggpack_read(opb,32);
 103     s->q_quant=oggpack_read(opb,4)+1;
 104     s->q_sequencep=oggpack_read(opb,1);
 105     if(s->q_sequencep==-1)goto _eofout;
 106
 107     {
 108       int quantvals=0;
 109       switch(s->maptype){
 110       case 1:
 111         quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
 112         break;
 113       case 2:
 114         quantvals=s->entries*s->dim;
 115         break;
 116       }
 117
 118       /* quantized values */
 119       s->quantlist=(long *)_ogg_malloc(sizeof(*s->quantlist)*quantvals);
 120       for(i=0;i<quantvals;i++)
 121         s->quantlist[i]=oggpack_read(opb,s->q_quant);
 122
 123       if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
 124     }
 125     break;
 126   default:
 127     goto _errout;
 128   }
 129
 130   /* all set */
 131   return(s);
 132
 133  _errout:
 134  _eofout:
 135   vorbis_staticbook_destroy(s);
 136   return(NULL);
 137 }
 138
 139 /* the 'eliminate the decode tree' optimization actually requires the
 140    codewords to be MSb first, not LSb.  This is an annoying inelegancy
 141    (and one of the first places where carefully thought out design
 142    turned out to be wrong; Vorbis II and future Ogg codecs should go
 143    to an MSb bitpacker), but not actually the huge hit it appears to
 144    be.  The first-stage decode table catches most words so that
 145    bitreverse is not in the main execution path. */
 146
 147 static inline ogg_uint32_t bitreverse(register ogg_uint32_t x)
 148 {
 149   unsigned tmp, ret;
 150 #ifdef _ARM_ASSEM_
 151 #if ARM_ARCH >= 6
 152   unsigned mask = 0x0f0f0f0f;
 153 #else
 154   unsigned mask = 0x00ff00ff;
 155 #endif
 156   asm (
 157 #if ARM_ARCH >= 6
 158     "rev     %[r], %[x]              \n"  /* swap halfwords and bytes */
 159     "and     %[t], %[m], %[r]        \n"  /* Sequence is one instruction */
 160     "eor     %[r], %[t], %[r]        \n"  /*   longer than on <= ARMv5, but */
 161     "mov     %[t], %[t], lsl #4      \n"  /*   interlock free */
 162     "orr     %[r], %[t], %[r], lsr #4\n"  /* nibbles swapped */
 163     "eor     %[m], %[m], %[m], lsl #2\n"  /* mask = 0x33333333 */
 164     "and     %[t], %[m], %[r]        \n"
 165     "eor     %[r], %[t], %[r]        \n"
 166     "mov     %[t], %[t], lsl #2      \n"
 167     "orr     %[r], %[t], %[r], lsr #2\n"  /* dibits swapped */
 168     "eor     %[m], %[m], %[m], lsl #1\n"  /* mask = 0x55555555 */
 169     "and     %[t], %[m], %[r]        \n"
 170     "eor     %[r], %[t], %[r]        \n"
 171     "mov     %[t], %[t], lsl #1      \n"
 172     "orr     %[r], %[t], %[r], lsr #1\n"  /* bits swapped */
 173 #else /* ARM_ARCH <= 5 */
 174     "mov     %[r], %[x], ror #16     \n"  /* swap halfwords */
 175     "and     %[t], %[m], %[r], lsr #8\n"
 176     "eor     %[r], %[r], %[t], lsl #8\n"
 177     "orr     %[r], %[t], %[r], lsl #8\n"  /* bytes swapped */
 178     "eor     %[m], %[m], %[m], lsl #4\n"  /* mask = 0x0f0f0f0f */
 179     "and     %[t], %[m], %[r], lsr #4\n"
 180     "eor     %[r], %[r], %[t], lsl #4\n"
 181     "orr     %[r], %[t], %[r], lsl #4\n"  /* nibbles swapped */
 182     "eor     %[m], %[m], %[m], lsl #2\n"  /* mask = 0x33333333 */
 183     "and     %[t], %[m], %[r], lsr #2\n"
 184     "eor     %[r], %[r], %[t], lsl #2\n"
 185     "orr     %[r], %[t], %[r], lsl #2\n"  /* dibits swapped */
 186     "eor     %[m], %[m], %[m], lsl #1\n"  /* mask = 0x55555555 */
 187     "and     %[t], %[m], %[r], lsr #1\n"
 188     "eor     %[r], %[r], %[t], lsl #1\n"
 189     "orr     %[r], %[t], %[r], lsl #1\n"  /* bits swapped */
 190 #endif /* ARM_ARCH */
 191     : /* outputs */
 192     [m]"+r"(mask),
 193     [r]"=r"(ret),
 194     [t]"=r"(tmp)
 195     : /* inputs */
 196     [x]"r"(x)
 197   );
 198 #else /* !_ARM_ASSEM_ */
 199
 200 #ifdef CPU_COLDFIRE
 201   ret = x;
 202   asm ("swap  %[r]" : [r] "+d" (ret));   /* swap halfwords */
 203 #else
 204   ret = (x>>16) | (x<<16);
 205 #endif
 206   tmp = ret & 0x00ff00ff;
 207   ret ^= tmp;
 208   ret = (ret >> 8) | (tmp << 8);         /* bytes swapped */
 209   tmp = ret & 0x0f0f0f0f;
 210   ret ^= tmp;
 211   ret = (ret >> 4) | (tmp << 4);         /* 4-bit units swapped */
 212   tmp = ret & 0x33333333;
 213   ret ^= tmp;
 214   ret = (ret >> 2) | (tmp << 2);         /* 2-bit units swapped */
 215   tmp = ret & 0x55555555;
 216   ret ^= tmp;
 217   ret = (ret >> 1) | (tmp << 1);         /* done */
 218 #endif /* !_ARM_ASSEM_ */
 219   return ret;
 220 }
 221
 222 static inline long bisect_codelist(long lo, long hi, ogg_uint32_t cache,
 223                                    const ogg_uint32_t *codelist)
 224 {
 225   ogg_uint32_t testword=bitreverse(cache);
 226   long p;
 227   while(LIKELY(p = (hi-lo) >> 1) > 0){
 228     if(codelist[lo+p] > testword)
 229       hi -= p;
 230     else
 231       lo += p;
 232   }
 233   return lo;
 234 }
 235
 236 STIN long decode_packed_entry_number(codebook *book,
 237                                               oggpack_buffer *b){
 238   int  read=book->dec_maxlength;
 239   long lo,hi;
 240   long lok = oggpack_look(b,book->dec_firsttablen);
 241
 242   if (LIKELY(lok >= 0)) {
 243     ogg_int32_t entry = book->dec_firsttable[lok];
 244     if(UNLIKELY(entry < 0)){
 245       lo=(entry>>15)&0x7fff;
 246       hi=book->used_entries-(entry&0x7fff);
 247     }else{
 248       oggpack_adv(b, book->dec_codelengths[entry-1]);
 249       return(entry-1);
 250     }
 251   }else{
 252     lo=0;
 253     hi=book->used_entries;
 254   }
 255
 256   lok = oggpack_look(b, read);
 257
 258   while(lok<0 && read>1)
 259     lok = oggpack_look(b, --read);
 260
 261   if(lok<0){
 262     oggpack_adv(b,1); /* force eop */
 263     return -1;
 264   }
 265
 266   /* bisect search for the codeword in the ordered list */
 267   {
 268     lo = bisect_codelist(lo, hi, lok, book->codelist);
 269
 270     if(book->dec_codelengths[lo]<=read){
 271       oggpack_adv(b, book->dec_codelengths[lo]);
 272       return(lo);
 273     }
 274   }
 275
 276   oggpack_adv(b, read+1);
 277   return(-1);
 278 }
 279
 280 static long decode_packed_block(codebook *book, oggpack_buffer *b,
 281                                 long *buf, int n){
 282   long *bufptr = buf;
 283   long *bufend = buf + n;
 284
 285   while (bufptr<bufend) {
 286     if(b->endbyte < b->storage - 8) {
 287       ogg_uint32_t *ptr;
 288       unsigned long bit, bitend;
 289       unsigned long adr;
 290       ogg_uint32_t cache = 0;
 291       int cachesize = 0;
 292       const unsigned int cachemask = (1<<book->dec_firsttablen)-1;
 293       const int          book_dec_maxlength = book->dec_maxlength;
 294       const ogg_uint32_t *book_dec_firsttable = book->dec_firsttable;
 295       const long         book_used_entries = book->used_entries;
 296       const ogg_uint32_t *book_codelist = book->codelist;
 297       const char         *book_dec_codelengths = book->dec_codelengths;
 298
 299       adr = (unsigned long)b->ptr;
 300       bit = (adr&3)*8+b->endbit;
 301       ptr = (ogg_uint32_t*)(adr&~3);
 302       bitend = ((adr&3)+(b->storage-b->endbyte))*8;
 303       while (bufptr<bufend){
 304         if (UNLIKELY(cachesize<book_dec_maxlength)) {
 305           if (bit-cachesize+32>=bitend)
 306             break;
 307           bit-=cachesize;
 308           cache = letoh32(ptr[bit>>5]);
 309           if (bit&31) {
 310             cache >>= (bit&31);
 311             cache |= letoh32(ptr[(bit>>5)+1]) << (32-(bit&31));
 312           }
 313           cachesize=32;
 314           bit+=32;
 315         }
 316
 317         ogg_int32_t entry = book_dec_firsttable[cache&cachemask];
 318         if(UNLIKELY(entry < 0)){
 319           const long lo = (entry>>15)&0x7fff, hi = book_used_entries-(entry&0x7fff);
 320           entry = bisect_codelist(lo, hi, cache, book_codelist);
 321         }else
 322           entry--;
 323
 324         *bufptr++ = entry;
 325         int l = book_dec_codelengths[entry];
 326         cachesize -= l;
 327         cache >>= l;
 328       }
 329
 330       adr=(unsigned long)b->ptr;
 331       bit-=(adr&3)*8+cachesize;
 332       b->endbyte+=bit/8;
 333       b->ptr+=bit/8;
 334       b->endbit=bit&7;
 335     } else {
 336       long r = decode_packed_entry_number(book, b);
 337       if (r == -1) return bufptr-buf;
 338       *bufptr++ = r;
 339     }
 340   }
 341   return n;
 342 }
 343
 344 /* Decode side is specced and easier, because we don't need to find
 345    matches using different criteria; we simply read and map.  There are
 346    two things we need to do 'depending':
 347
 348    We may need to support interleave.  We don't really, but it's
 349    convenient to do it here rather than rebuild the vector later.
 350
 351    Cascades may be additive or multiplicitive; this is not inherent in
 352    the codebook, but set in the code using the codebook.  Like
 353    interleaving, it's easiest to do it here.
 354    addmul==0 -> declarative (set the value)
 355    addmul==1 -> additive
 356    addmul==2 -> multiplicitive */
 357
 358 /* returns the [original, not compacted] entry number or -1 on eof *********/
 359 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
 360   if(book->used_entries>0){
 361     long packed_entry=decode_packed_entry_number(book,b);
 362     if(packed_entry>=0)
 363       return(book->dec_index[packed_entry]);
 364   }
 365
 366   /* if there's no dec_index, the codebook unpacking isn't collapsed */
 367   return(-1);
 368 }
 369
 370 /* returns 0 on OK or -1 on eof *************************************/
 371 long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a,
 372                               oggpack_buffer *b,int n,int point){
 373   if(book->used_entries>0){
 374     int step=n/book->dim;
 375     long *entry = (long *)alloca(sizeof(*entry)*step);
 376     ogg_int32_t **t = (ogg_int32_t **)alloca(sizeof(*t)*step);
 377     int i,j,o;
 378     int shift=point-book->binarypoint;
 379
 380     if(shift>=0){
 381       for (i = 0; i < step; i++) {
 382         entry[i]=decode_packed_entry_number(book,b);
 383         if(entry[i]==-1)return(-1);
 384         t[i] = book->valuelist+entry[i]*book->dim;
 385       }
 386       for(i=0,o=0;i<book->dim;i++,o+=step)
 387         for (j=0;j<step;j++)
 388           a[o+j]+=t[j][i]>>shift;
 389     }else{
 390       for (i = 0; i < step; i++) {
 391         entry[i]=decode_packed_entry_number(book,b);
 392         if(entry[i]==-1)return(-1);
 393         t[i] = book->valuelist+entry[i]*book->dim;
 394       }
 395       for(i=0,o=0;i<book->dim;i++,o+=step)
 396         for (j=0;j<step;j++)
 397           a[o+j]+=t[j][i]<<-shift;
 398     }
 399   }
 400   return(0);
 401 }
 402
 403 long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a,
 404                              oggpack_buffer *b,int n,int point){
 405   if(book->used_entries>0){
 406     int i,j,entry;
 407     ogg_int32_t *t;
 408     int shift=point-book->binarypoint;
 409
 410     if(shift>=0){
 411       for(i=0;i<n;){
 412         entry = decode_packed_entry_number(book,b);
 413         if(entry==-1)return(-1);
 414         t     = book->valuelist+entry*book->dim;
 415         for (j=0;j<book->dim;)
 416           a[i++]+=t[j++]>>shift;
 417       }
 418     }else{
 419       shift = -shift;
 420       for(i=0;i<n;){
 421         entry = decode_packed_entry_number(book,b);
 422         if(entry==-1)return(-1);
 423         t     = book->valuelist+entry*book->dim;
 424         for (j=0;j<book->dim;)
 425           a[i++]+=t[j++]<<shift;
 426       }
 427     }
 428   }
 429   return(0);
 430 }
 431
 432 long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a,
 433                              oggpack_buffer *b,int n,int point){
 434   if(book->used_entries>0){
 435     int i,j,entry;
 436     ogg_int32_t *t;
 437     int shift=point-book->binarypoint;
 438
 439     if(shift>=0){
 440
 441       for(i=0;i<n;){
 442         entry = decode_packed_entry_number(book,b);
 443         if(entry==-1)return(-1);
 444         t     = book->valuelist+entry*book->dim;
 445         for (j=0;j<book->dim;){
 446           a[i++]=t[j++]>>shift;
 447         }
 448       }
 449     }else{
 450       shift = -shift;
 451       for(i=0;i<n;){
 452         entry = decode_packed_entry_number(book,b);
 453         if(entry==-1)return(-1);
 454         t     = book->valuelist+entry*book->dim;
 455         for (j=0;j<book->dim;){
 456           a[i++]=t[j++]<<shift;
 457         }
 458       }
 459     }
 460   }else{
 461
 462     int i,j;
 463     for(i=0;i<n;){
 464       for (j=0;j<book->dim;){
 465         a[i++]=0;
 466       }
 467     }
 468   }
 469   return(0);
 470 }
 471
 472 static long vorbis_book_decodevv_add_2ch_even(codebook *book,ogg_int32_t **a,
 473                                               long offset,oggpack_buffer *b,
 474                                               unsigned int n,int point){
 475   long k,chunk,read;
 476   int shift=point-book->binarypoint;
 477   long entries[32];
 478   ogg_int32_t *p0 = &(a[0][offset]);
 479   ogg_int32_t *p1 = &(a[1][offset]);
 480   const unsigned long dim = book->dim;
 481   const ogg_int32_t * const vlist = book->valuelist;
 482
 483   if(shift>=0){
 484     while(n>0){
 485       chunk=32;
 486       if (16*dim>n)
 487         chunk=(n*2-1)/dim + 1;
 488       read = decode_packed_block(book,b,entries,chunk);
 489       for(k=0;k<read;k++){
 490         const ogg_int32_t *t = vlist+entries[k]*dim;
 491         const ogg_int32_t *u = t+dim;
 492         do{
 493           *p0++ += *t++>>shift;
 494           *p1++ += *t++>>shift;
 495         }while(t<u);
 496       }
 497       if (read<chunk)return-1;
 498       n -= read*dim/2;
 499     }
 500   }else{
 501     shift = -shift;
 502     while(n>0){
 503       chunk=32;
 504       if (16*dim>n)
 505         chunk=(n*2-1)/dim + 1;
 506       read = decode_packed_block(book,b,entries,chunk);
 507       for(k=0;k<read;k++){
 508         const ogg_int32_t *t = vlist+entries[k]*dim;
 509         const ogg_int32_t *u = t+dim;
 510         do{
 511           *p0++ += *t++<<shift;
 512           *p1++ += *t++<<shift;
 513         }while(t<u);
 514       }
 515       if (read<chunk)return-1;
 516       n -= read*dim/2;
 517     }
 518   }
 519   return(0);
 520 }
 521
 522 long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,
 523                               long offset,int ch,
 524                               oggpack_buffer *b,int n,int point){
 525   if(LIKELY(book->used_entries>0)){
 526     long i,j,k,chunk,read;
 527     int chptr=0;
 528     int shift=point-book->binarypoint;
 529     long entries[32];
 530
 531     if (!(book->dim&1) && ch==2)
 532       return vorbis_book_decodevv_add_2ch_even(book,a,offset,b,n,point);
 533
 534     if(shift>=0){
 535
 536       for(i=offset;i<offset+n;){
 537         chunk=32;
 538         if (chunk*book->dim>(offset+n-i)*ch)
 539           chunk=((offset+n-i)*ch+book->dim-1)/book->dim;
 540         read = decode_packed_block(book,b,entries,chunk);
 541         for(k=0;k<read;k++){
 542           const ogg_int32_t *t = book->valuelist+entries[k]*book->dim;
 543           for (j=0;j<book->dim;j++){
 544             a[chptr++][i]+=t[j]>>shift;
 545             if(chptr==ch){
 546               chptr=0;
 547               i++;
 548             }
 549           }
 550         }
 551         if (read<chunk)return-1;
 552       }
 553     }else{
 554       shift = -shift;
 555       for(i=offset;i<offset+n;){
 556         chunk=32;
 557         if (chunk*book->dim>(offset+n-i)*ch)
 558           chunk=((offset+n-i)*ch+book->dim-1)/book->dim;
 559         read = decode_packed_block(book,b,entries,chunk);
 560         for(k=0;k<read;k++){
 561           const ogg_int32_t *t = book->valuelist+entries[k]*book->dim;
 562           for (j=0;j<book->dim;j++){
 563             a[chptr++][i]+=t[j]<<shift;
 564             if(chptr==ch){
 565               chptr=0;
 566               i++;
 567             }
 568           }
 569         }
 570         if (read<chunk)return-1;
 571       }
 572     }
 573   }
 574   return(0);
 575 }
 576