[xiph-cvs] cvs commit: vorbis/lib codebook.c codebook.h sharedbook.c
Monty
xiphmont at xiph.org
Mon Jan 21 12:51:29 PST 2002
xiphmont 02/01/21 12:51:29
Modified: lib codebook.c codebook.h sharedbook.c
Log:
Additional optimization to new bisection search codebook decode
Revision Changes Path
1.37 +15 -14 vorbis/lib/codebook.c
Index: codebook.c
===================================================================
RCS file: /usr/local/cvsroot/vorbis/lib/codebook.c,v
retrieving revision 1.36
retrieving revision 1.37
diff -u -r1.36 -r1.37
--- codebook.c 2002/01/19 04:52:39 1.36
+++ codebook.c 2002/01/21 20:51:28 1.37
@@ -11,7 +11,7 @@
********************************************************************
function: basic codebook pack/unpack/code/decode operations
- last mod: $Id: codebook.c,v 1.36 2002/01/19 04:52:39 xiphmont Exp $
+ last mod: $Id: codebook.c,v 1.37 2002/01/21 20:51:28 xiphmont Exp $
********************************************************************/
@@ -315,39 +315,40 @@
return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
}
+
static long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
- int read;
+ 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>=0){
- oggpack_adv(b, book->dec_codelengths[entry]);
- return(entry);
+ 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;
}
- read=book->dec_maxlength;
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);
-
- long lo=0;
- long hi=book->used_entries;
long p=(lo+hi)>>1;
while(hi-lo>1){
- if(book->codelist[p]<=testword)
- lo=p;
- else
- hi=p;
+ long test=(book->codelist[p]<=testword)-1;
+ lo+=(p-lo)&(~test);
+ hi-=(hi-p)&test;
p=(lo+hi)>>1;
}
<p><p>1.12 +2 -2 vorbis/lib/codebook.h
Index: codebook.h
===================================================================
RCS file: /usr/local/cvsroot/vorbis/lib/codebook.h,v
retrieving revision 1.11
retrieving revision 1.12
diff -u -r1.11 -r1.12
--- codebook.h 2002/01/19 04:52:40 1.11
+++ codebook.h 2002/01/21 20:51:28 1.12
@@ -11,7 +11,7 @@
********************************************************************
function: basic shared codebook operations
- last mod: $Id: codebook.h,v 1.11 2002/01/19 04:52:40 xiphmont Exp $
+ last mod: $Id: codebook.h,v 1.12 2002/01/21 20:51:28 xiphmont Exp $
********************************************************************/
@@ -110,7 +110,7 @@
int *dec_index; /* only used if sparseness collapsed */
char *dec_codelengths;
- int *dec_firsttable;
+ ogg_uint32_t *dec_firsttable;
int dec_firsttablen;
int dec_maxlength;
<p><p>1.25 +31 -5 vorbis/lib/sharedbook.c
Index: sharedbook.c
===================================================================
RCS file: /usr/local/cvsroot/vorbis/lib/sharedbook.c,v
retrieving revision 1.24
retrieving revision 1.25
diff -u -r1.24 -r1.25
--- sharedbook.c 2002/01/19 05:01:44 1.24
+++ sharedbook.c 2002/01/21 20:51:28 1.25
@@ -11,7 +11,7 @@
********************************************************************
function: basic shared codebook operations
- last mod: $Id: sharedbook.c,v 1.24 2002/01/19 05:01:44 xiphmont Exp $
+ last mod: $Id: sharedbook.c,v 1.25 2002/01/21 20:51:28 xiphmont Exp $
********************************************************************/
@@ -312,7 +312,6 @@
return ( (**(ogg_uint32_t **)a>**(ogg_uint32_t **)b)<<1)-1;
}
-
/* decode codebook arrangement is more heavily optimized than encode */
int vorbis_book_init_decode(codebook *c,const static_codebook *s){
int i,j,n=0,tabn;
@@ -382,8 +381,7 @@
if(c->dec_firsttablen>8)c->dec_firsttablen=8;
tabn=1<<c->dec_firsttablen;
- c->dec_firsttable=_ogg_malloc(tabn*sizeof(*c->dec_firsttable));
- for(i=0;i<tabn;i++)c->dec_firsttable[i]=-1;
+ c->dec_firsttable=_ogg_calloc(tabn,sizeof(*c->dec_firsttable));
c->dec_maxlength=0;
for(i=0;i<n;i++){
@@ -392,9 +390,37 @@
if(c->dec_codelengths[i]<=c->dec_firsttablen){
ogg_uint32_t orig=bitreverse(c->codelist[i]);
for(j=0;j<(1<<(c->dec_firsttablen-c->dec_codelengths[i]));j++)
- c->dec_firsttable[orig|(j<<c->dec_codelengths[i])]=i;
+ c->dec_firsttable[orig|(j<<c->dec_codelengths[i])]=i+1;
}
}
+
+ /* now fill in 'unused' entries in the firsttable with hi/lo search
+ hints for the non-direct-hits */
+ {
+ ogg_uint32_t mask=0xfffffffeUL<<(31-c->dec_firsttablen);
+
+ for(i=0;i<tabn;i++){
+ if(c->dec_firsttable[i]==0){
+ ogg_uint32_t testword=bitreverse(i);
+ long lo=0,hi=0;
+ while((lo+1)<n && c->codelist[lo+1]<=testword)lo++;
+ while( hi<n && testword>=(c->codelist[hi]&mask))hi++;
+
+ /* we only actually have 15 bits per hint to play with here.
+ In order to overflow gracefully (nothing breaks, efficiency
+ just drops), encode as the difference from the extremes. */
+ {
+ unsigned long loval=lo;
+ unsigned long hival=n-hi;
+
+ if(loval>0x7fff)loval=0x7fff;
+ if(hival>0x7fff)hival=0x7fff;
+ c->dec_firsttable[i]=0x80000000UL | (loval<<15) | hival;
+ }
+ }
+ }
+ }
+
return(0);
err_out:
<p><p><p>--- >8 ----
List archives: http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to 'cvs-request at xiph.org'
containing only the word 'unsubscribe' in the body. No subject is needed.
Unsubscribe messages sent to the list will be ignored/filtered.
More information about the commits
mailing list