From 175628aa2f16e99ebe2ca235ac998439299621c6 Mon Sep 17 00:00:00 2001 From: Monty Date: Mon, 21 Jan 2002 20:51:28 +0000 Subject: [PATCH] Additional optimization to new bisection search codebook decode svn path=/trunk/vorbis/; revision=2970 --- lib/codebook.c | 31 ++++++++++++++++--------------- lib/codebook.h | 4 ++-- lib/sharedbook.c | 36 +++++++++++++++++++++++++++++++----- 3 files changed, 49 insertions(+), 22 deletions(-) diff --git a/lib/codebook.c b/lib/codebook.c index b89f077..469a530 100644 --- a/lib/codebook.c +++ b/lib/codebook.c @@ -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 @@ static ogg_uint32_t bitreverse(ogg_uint32_t x){ 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; } diff --git a/lib/codebook.h b/lib/codebook.h index 538169f..5800546 100644 --- a/lib/codebook.h +++ b/lib/codebook.h @@ -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 @@ typedef struct codebook{ 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; diff --git a/lib/sharedbook.c b/lib/sharedbook.c index e6746c3..40235fc 100644 --- a/lib/sharedbook.c +++ b/lib/sharedbook.c @@ -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 @@ static int sort32a(const void *a,const void *b){ 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 @@ int vorbis_book_init_decode(codebook *c,const static_codebook *s){ if(c->dec_firsttablen>8)c->dec_firsttablen=8; tabn=1<dec_firsttablen; - c->dec_firsttable=_ogg_malloc(tabn*sizeof(*c->dec_firsttable)); - for(i=0;idec_firsttable[i]=-1; + c->dec_firsttable=_ogg_calloc(tabn,sizeof(*c->dec_firsttable)); c->dec_maxlength=0; for(i=0;idec_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<dec_codelengths[i])]=i; + c->dec_firsttable[orig|(j<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;idec_firsttable[i]==0){ + ogg_uint32_t testword=bitreverse(i); + long lo=0,hi=0; + while((lo+1)codelist[lo+1]<=testword)lo++; + while( hi=(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: -- 2.7.4