| /******************************************************************** |
| * * |
| * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE. * |
| * * |
| * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS * |
| * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE * |
| * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. * |
| * * |
| * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2002 * |
| * BY THE Xiph.Org FOUNDATION http://www.xiph.org/ * |
| * * |
| ******************************************************************** |
| |
| function: basic codebook pack/unpack/code/decode operations |
| |
| ********************************************************************/ |
| |
| #include "config-tremor.h" |
| #include <string.h> |
| #include <math.h> |
| #include "ogg.h" |
| #include "ivorbiscodec.h" |
| #include "codebook.h" |
| #include "misc.h" |
| #include "os.h" |
| |
| /* unpacks a codebook from the packet buffer into the codebook struct, |
| readies the codebook auxiliary structures for decode *************/ |
| int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){ |
| long i,j; |
| memset(s,0,sizeof(*s)); |
| |
| /* make sure alignment is correct */ |
| if(oggpack_read(opb,24)!=0x564342)goto _eofout; |
| |
| /* first the basic parameters */ |
| s->dim=oggpack_read(opb,16); |
| s->entries=oggpack_read(opb,24); |
| if(s->entries==-1)goto _eofout; |
| |
| /* codeword ordering.... length ordered or unordered? */ |
| switch((int)oggpack_read(opb,1)){ |
| case 0: |
| /* unordered */ |
| s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries); |
| |
| /* allocated but unused entries? */ |
| if(oggpack_read(opb,1)){ |
| /* yes, unused entries */ |
| |
| for(i=0;i<s->entries;i++){ |
| if(oggpack_read(opb,1)){ |
| long num=oggpack_read(opb,5); |
| if(num==-1)goto _eofout; |
| s->lengthlist[i]=num+1; |
| }else |
| s->lengthlist[i]=0; |
| } |
| }else{ |
| /* all entries used; no tagging */ |
| for(i=0;i<s->entries;i++){ |
| long num=oggpack_read(opb,5); |
| if(num==-1)goto _eofout; |
| s->lengthlist[i]=num+1; |
| } |
| } |
| |
| break; |
| case 1: |
| /* ordered */ |
| { |
| long length=oggpack_read(opb,5)+1; |
| s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries); |
| |
| for(i=0;i<s->entries;){ |
| long num=oggpack_read(opb,_ilog(s->entries-i)); |
| if(num==-1)goto _eofout; |
| for(j=0;j<num && i<s->entries;j++,i++) |
| s->lengthlist[i]=length; |
| length++; |
| } |
| } |
| break; |
| default: |
| /* EOF */ |
| return(-1); |
| } |
| |
| /* Do we have a mapping to unpack? */ |
| switch((s->maptype=oggpack_read(opb,4))){ |
| case 0: |
| /* no mapping */ |
| break; |
| case 1: case 2: |
| /* implicitly populated value mapping */ |
| /* explicitly populated value mapping */ |
| |
| s->q_min=oggpack_read(opb,32); |
| s->q_delta=oggpack_read(opb,32); |
| s->q_quant=oggpack_read(opb,4)+1; |
| s->q_sequencep=oggpack_read(opb,1); |
| |
| { |
| int quantvals=0; |
| switch(s->maptype){ |
| case 1: |
| quantvals=_book_maptype1_quantvals(s); |
| break; |
| case 2: |
| quantvals=s->entries*s->dim; |
| break; |
| } |
| |
| /* quantized values */ |
| s->quantlist=(long *)_ogg_malloc(sizeof(*s->quantlist)*quantvals); |
| for(i=0;i<quantvals;i++) |
| s->quantlist[i]=oggpack_read(opb,s->q_quant); |
| |
| if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout; |
| } |
| break; |
| default: |
| goto _errout; |
| } |
| |
| /* all set */ |
| return(0); |
| |
| _errout: |
| _eofout: |
| vorbis_staticbook_clear(s); |
| return(-1); |
| } |
| |
| /* the 'eliminate the decode tree' optimization actually requires the |
| codewords to be MSb first, not LSb. This is an annoying inelegancy |
| (and one of the first places where carefully thought out design |
| turned out to be wrong; Vorbis II and future Ogg codecs should go |
| to an MSb bitpacker), but not actually the huge hit it appears to |
| be. The first-stage decode table catches most words so that |
| bitreverse is not in the main execution path. */ |
| |
| static inline ogg_uint32_t bitreverse(register ogg_uint32_t x){ |
| x= ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000); |
| x= ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00); |
| x= ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0); |
| x= ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc); |
| return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa); |
| } |
| |
| STIN long decode_packed_entry_number(codebook *book, |
| oggpack_buffer *b){ |
| int read=book->dec_maxlength; |
| long lo,hi; |
| long lok = oggpack_look(b,book->dec_firsttablen); |
| |
| if (EXPECT(lok >= 0, 1)) { |
| long entry = book->dec_firsttable[lok]; |
| if(EXPECT(entry&0x80000000UL, 0)){ |
| lo=(entry>>15)&0x7fff; |
| hi=book->used_entries-(entry&0x7fff); |
| }else{ |
| oggpack_adv(b, book->dec_codelengths[entry-1]); |
| return(entry-1); |
| } |
| }else{ |
| lo=0; |
| hi=book->used_entries; |
| } |
| |
| lok = oggpack_look(b, read); |
| |
| while(lok<0 && read>1) |
| lok = oggpack_look(b, --read); |
| |
| if(lok<0){ |
| oggpack_adv(b,1); /* force eop */ |
| return -1; |
| } |
| |
| /* bisect search for the codeword in the ordered list */ |
| { |
| ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok); |
| |
| while(hi-lo>1){ |
| long p=(hi-lo)>>1; |
| long test=book->codelist[lo+p]>testword; |
| lo+=p&(test-1); |
| hi-=p&(-test); |
| } |
| |
| if(book->dec_codelengths[lo]<=read){ |
| oggpack_adv(b, book->dec_codelengths[lo]); |
| return(lo); |
| } |
| } |
| |
| oggpack_adv(b, read+1); |
| return(-1); |
| } |
| |
| static inline long decode_packed_block(codebook *book, oggpack_buffer *b, |
| long *buf, int n){ |
| long *bufptr = buf; |
| long *bufend = buf + n; |
| |
| while (bufptr<bufend) { |
| if (b->headend > 8) { |
| ogg_uint32_t *ptr; |
| unsigned long bit, bitend; |
| unsigned long adr; |
| ogg_uint32_t cache = 0; |
| int cachesize = 0; |
| |
| adr = (unsigned long)b->headptr; |
| bit = (adr&3)*8+b->headbit; |
| ptr = (ogg_uint32_t *)(adr&~3); |
| bitend = ((adr&3)+b->headend)*8; |
| while (bufptr<bufend){ |
| long entry, lo, hi; |
| if (EXPECT(cachesize<book->dec_maxlength, 0)) { |
| if (bit-cachesize+32>=bitend) |
| break; |
| bit-=cachesize; |
| cache=letoh32(ptr[bit>>5]) >> (bit&31); |
| if (bit&31) |
| cache|=letoh32(ptr[(bit>>5)+1]) << (32-(bit&31)); |
| cachesize=32; |
| bit+=32; |
| } |
| |
| entry=book->dec_firsttable[cache&((1<<book->dec_firsttablen)-1)]; |
| if(EXPECT(entry&0x80000000UL, 0)){ |
| lo=(entry>>15)&0x7fff; |
| hi=book->used_entries-(entry&0x7fff); |
| { |
| ogg_uint32_t testword=bitreverse((ogg_uint32_t)cache); |
| |
| while(EXPECT(hi-lo>1, 1)){ |
| long p=(hi-lo)>>1; |
| if (book->codelist[lo+p]>testword) |
| hi-=p; |
| else |
| lo+=p; |
| } |
| entry=lo; |
| } |
| }else |
| entry--; |
| |
| *bufptr++=entry; |
| { |
| int l=book->dec_codelengths[entry]; |
| cachesize-=l; |
| cache>>=l; |
| } |
| } |
| |
| adr=(unsigned long)b->headptr; |
| bit-=(adr&3)*8+cachesize; |
| b->headend-=(bit/8); |
| b->headptr+=bit/8; |
| b->headbit=bit%8; |
| } else { |
| long r = decode_packed_entry_number(book, b); |
| if (r == -1) return bufptr-buf; |
| *bufptr++ = r; |
| } |
| } |
| return n; |
| } |
| |
| |
| /* Decode side is specced and easier, because we don't need to find |
| matches using different criteria; we simply read and map. There are |
| two things we need to do 'depending': |
| |
| We may need to support interleave. We don't really, but it's |
| convenient to do it here rather than rebuild the vector later. |
| |
| Cascades may be additive or multiplicitive; this is not inherent in |
| the codebook, but set in the code using the codebook. Like |
| interleaving, it's easiest to do it here. |
| addmul==0 -> declarative (set the value) |
| addmul==1 -> additive |
| addmul==2 -> multiplicitive */ |
| |
| /* returns the [original, not compacted] entry number or -1 on eof *********/ |
| long vorbis_book_decode(codebook *book, oggpack_buffer *b){ |
| if(book->used_entries>0){ |
| long packed_entry=decode_packed_entry_number(book,b); |
| if(packed_entry>=0) |
| return(book->dec_index[packed_entry]); |
| } |
| |
| /* if there's no dec_index, the codebook unpacking isn't collapsed */ |
| return(-1); |
| } |
| |
| /* returns 0 on OK or -1 on eof *************************************/ |
| long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a, |
| oggpack_buffer *b,int n,int point){ |
| if(book->used_entries>0){ |
| int step=n/book->dim; |
| long *entry = (long *)alloca(sizeof(*entry)*step); |
| ogg_int32_t **t = (ogg_int32_t **)alloca(sizeof(*t)*step); |
| int i,j,o; |
| int shift=point-book->binarypoint; |
| |
| if(shift>=0){ |
| for (i = 0; i < step; i++) { |
| entry[i]=decode_packed_entry_number(book,b); |
| if(entry[i]==-1)return(-1); |
| t[i] = book->valuelist+entry[i]*book->dim; |
| } |
| for(i=0,o=0;i<book->dim;i++,o+=step) |
| for (j=0;j<step;j++) |
| a[o+j]+=t[j][i]>>shift; |
| }else{ |
| for (i = 0; i < step; i++) { |
| entry[i]=decode_packed_entry_number(book,b); |
| if(entry[i]==-1)return(-1); |
| t[i] = book->valuelist+entry[i]*book->dim; |
| } |
| for(i=0,o=0;i<book->dim;i++,o+=step) |
| for (j=0;j<step;j++) |
| a[o+j]+=t[j][i]<<-shift; |
| } |
| } |
| return(0); |
| } |
| |
| long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a, |
| oggpack_buffer *b,int n,int point){ |
| if(book->used_entries>0){ |
| int i,j,entry; |
| ogg_int32_t *t; |
| int shift=point-book->binarypoint; |
| |
| if(shift>=0){ |
| for(i=0;i<n;){ |
| entry = decode_packed_entry_number(book,b); |
| if(entry==-1)return(-1); |
| t = book->valuelist+entry*book->dim; |
| for (j=0;j<book->dim;) |
| a[i++]+=t[j++]>>shift; |
| } |
| }else{ |
| shift = -shift; |
| for(i=0;i<n;){ |
| entry = decode_packed_entry_number(book,b); |
| if(entry==-1)return(-1); |
| t = book->valuelist+entry*book->dim; |
| for (j=0;j<book->dim;) |
| a[i++]+=t[j++]<<shift; |
| } |
| } |
| } |
| return(0); |
| } |
| |
| long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a, |
| oggpack_buffer *b,int n,int point){ |
| if(book->used_entries>0){ |
| int i,j,entry; |
| ogg_int32_t *t; |
| int shift=point-book->binarypoint; |
| |
| if(shift>=0){ |
| |
| for(i=0;i<n;){ |
| entry = decode_packed_entry_number(book,b); |
| if(entry==-1)return(-1); |
| t = book->valuelist+entry*book->dim; |
| for (j=0;j<book->dim;){ |
| a[i++]=t[j++]>>shift; |
| } |
| } |
| }else{ |
| shift = -shift; |
| for(i=0;i<n;){ |
| entry = decode_packed_entry_number(book,b); |
| if(entry==-1)return(-1); |
| t = book->valuelist+entry*book->dim; |
| for (j=0;j<book->dim;){ |
| a[i++]=t[j++]<<shift; |
| } |
| } |
| } |
| }else{ |
| |
| int i,j; |
| for(i=0;i<n;){ |
| for (j=0;j<book->dim;){ |
| a[i++]=0; |
| } |
| } |
| } |
| return(0); |
| } |
| |
| long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a, |
| long offset,int ch, |
| oggpack_buffer *b,int n,int point){ |
| if(book->used_entries>0){ |
| long i,j,k,chunk,read; |
| int chptr=0; |
| int shift=point-book->binarypoint; |
| long entries[32]; |
| |
| if(shift>=0){ |
| |
| for(i=offset;i<offset+n;){ |
| chunk=32; |
| if (chunk*book->dim>(offset+n-i)*ch) |
| chunk=((offset+n-i)*ch+book->dim-1)/book->dim; |
| read = decode_packed_block(book,b,entries,chunk); |
| for(k=0;k<read;k++){ |
| const ogg_int32_t *t = book->valuelist+entries[k]*book->dim; |
| for (j=0;j<book->dim;j++){ |
| a[chptr++][i]+=t[j]>>shift; |
| if(chptr==ch){ |
| chptr=0; |
| i++; |
| } |
| } |
| } |
| if (read<chunk)return-1; |
| } |
| }else{ |
| shift = -shift; |
| for(i=offset;i<offset+n;){ |
| chunk=32; |
| if (chunk*book->dim>(offset+n-i)*ch) |
| chunk=((offset+n-i)*ch+book->dim-1)/book->dim; |
| read = decode_packed_block(book,b,entries,chunk); |
| for(k=0;k<read;k++){ |
| const ogg_int32_t *t = book->valuelist+entries[k]*book->dim; |
| for (j=0;j<book->dim;j++){ |
| a[chptr++][i]+=t[j]<<shift; |
| if(chptr==ch){ |
| chptr=0; |
| i++; |
| } |
| } |
| } |
| if (read<chunk)return-1; |
| } |
| } |
| } |
| return(0); |
| } |