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