* GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
* IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. *
* *
- * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2001 *
+ * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2002 *
* by the XIPHOPHORUS Company http://www.xiph.org/ *
-
+ * *
********************************************************************
function: basic codebook pack/unpack/code/decode operations
- last mod: $Id: codebook.c,v 1.33 2001/12/19 23:13:33 segher Exp $
+ last mod: $Id: codebook.c,v 1.39 2002/06/28 22:19:35 xiphmont Exp $
********************************************************************/
if(s->entries==-1)goto _eofout;
/* codeword ordering.... length ordered or unordered? */
- switch(oggpack_read(opb,1)){
+ switch((int)oggpack_read(opb,1)){
case 0:
/* unordered */
s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
return(vorbis_book_encode(book,best,b));
}
-/* res0 (multistage, interleave, lattice) */
-/* returns the number of bits and *modifies a* to the remainder value ********/
-int vorbis_book_encodevs(codebook *book,float *a,oggpack_buffer *b,
- int step,int addmul){
+/* 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 ogg_uint32_t bitreverse(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);
+}
- int best=vorbis_book_besterror(book,a,step,addmul);
- return(vorbis_book_encode(book,best,b));
+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 (lok >= 0) {
+ long entry = book->dec_firsttable[lok];
+ if(entry&0x80000000UL){
+ 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)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);
+ return(-1);
}
/* Decode side is specced and easier, because we don't need to find
addmul==1 -> additive
addmul==2 -> multiplicitive */
-/* returns the entry number or -1 on eof *************************************/
+/* returns the [original, not compacted] entry number or -1 on eof *********/
long vorbis_book_decode(codebook *book, oggpack_buffer *b){
- long ptr=0;
- decode_aux *t=book->decode_tree;
- int lok = oggpack_look(b, t->tabn);
-
- if (lok >= 0) {
- ptr = t->tab[lok];
- oggpack_adv(b, t->tabl[lok]);
- if (ptr <= 0)
- return -ptr;
- }
-
- do{
- switch(oggpack_read1(b)){
- case 0:
- ptr=t->ptr0[ptr];
- break;
- case 1:
- ptr=t->ptr1[ptr];
- break;
- case -1:
- return(-1);
- }
- }while(ptr>0);
- return(-ptr);
+ 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(packed_entry);
}
/* returns 0 on OK or -1 on eof *************************************/
int i,j,o;
for (i = 0; i < step; i++) {
- entry[i]=vorbis_book_decode(book,b);
+ entry[i]=decode_packed_entry_number(book,b);
if(entry[i]==-1)return(-1);
t[i] = book->valuelist+entry[i]*book->dim;
}
if(book->dim>8){
for(i=0;i<n;){
- entry = vorbis_book_decode(book,b);
+ entry = decode_packed_entry_number(book,b);
if(entry==-1)return(-1);
t = book->valuelist+entry*book->dim;
for (j=0;j<book->dim;)
}
}else{
for(i=0;i<n;){
- entry = vorbis_book_decode(book,b);
+ entry = decode_packed_entry_number(book,b);
if(entry==-1)return(-1);
t = book->valuelist+entry*book->dim;
j=0;
- switch(book->dim){
+ switch((int)book->dim){
case 8:
a[i++]+=t[j++];
case 7:
float *t;
for(i=0;i<n;){
- entry = vorbis_book_decode(book,b);
+ entry = decode_packed_entry_number(book,b);
if(entry==-1)return(-1);
t = book->valuelist+entry*book->dim;
for (j=0;j<book->dim;)
int chptr=0;
for(i=offset/ch;i<(offset+n)/ch;){
- entry = vorbis_book_decode(book,b);
+ entry = decode_packed_entry_number(book,b);
if(entry==-1)return(-1);
{
const float *t = book->valuelist+entry*book->dim;
projects / platform / upstream / libvorbis.git / blobdiff