* 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-2009 *
+ * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2015 *
* by the Xiph.Org Foundation http://www.xiph.org/ *
* *
********************************************************************
function: basic shared codebook operations
- last mod: $Id$
********************************************************************/
#include <stdlib.h>
+#include <limits.h>
#include <math.h>
#include <string.h>
#include <ogg/ogg.h>
#include "scales.h"
/**** pack/unpack helpers ******************************************/
-int _ilog(unsigned int v){
- int ret=0;
- while(v){
- ret++;
- v>>=1;
- }
- return(ret);
+
+int ov_ilog(ogg_uint32_t v){
+ int ret;
+ for(ret=0;v;ret++)v>>=1;
+ return ret;
}
/* 32 bit float (not IEEE; nonnormalized mantissa +
sign=0x80000000;
val= -val;
}
- exp= floor(log(val)/log(2.f)+.001); //+epsilon
+ exp= floor(log(val)/log(2.f)+.001); /* +epsilon */
mant=rint(ldexp(val,(VQ_FMAN-1)-exp));
exp=(exp+VQ_FEXP_BIAS)<<VQ_FMAN;
int sign=val&0x80000000;
long exp =(val&0x7fe00000L)>>VQ_FMAN;
if(sign)mant= -mant;
- return(ldexp(mant,exp-(VQ_FMAN-1)-VQ_FEXP_BIAS));
+ exp=exp-(VQ_FMAN-1)-VQ_FEXP_BIAS;
+ /* clamp excessive exponent values */
+ if (exp>63){
+ exp=63;
+ }
+ if (exp<-63){
+ exp-63;
+ }
+ return(ldexp(mant,exp));
}
/* given a list of word lengths, generate a list of codewords. Works
for length ordered or unordered, always assigns the lowest valued
codewords first. Extended to handle unused entries (length 0) */
-ogg_uint32_t *_make_words(long *l,long n,long sparsecount){
+ogg_uint32_t *_make_words(char *l,long n,long sparsecount){
long i,j,count=0;
ogg_uint32_t marker[33];
ogg_uint32_t *r=_ogg_malloc((sparsecount?sparsecount:n)*sizeof(*r));
if(sparsecount==0)count++;
}
- /* sanity check the huffman tree; an underpopulated tree must be
- rejected. The only exception is the one-node pseudo-nil tree,
- which appears to be underpopulated because the tree doesn't
- really exist; there's only one possible 'codeword' or zero bits,
- but the above tree-gen code doesn't mark that. */
- if(sparsecount != 1){
+ /* any underpopulated tree must be rejected. */
+ /* Single-entry codebooks are a retconned extension to the spec.
+ They have a single codeword '0' of length 1 that results in an
+ underpopulated tree. Shield that case from the underformed tree check. */
+ if(!(count==1 && marker[2]==2)){
for(i=1;i<33;i++)
if(marker[i] & (0xffffffffUL>>(32-i))){
- _ogg_free(r);
- return(NULL);
+ _ogg_free(r);
+ return(NULL);
}
}
that's portable and totally safe against roundoff, but I haven't
thought of it. Therefore, we opt on the side of caution */
long _book_maptype1_quantvals(const static_codebook *b){
- long vals=floor(pow((float)b->entries,1.f/b->dim));
+ long vals;
+ if(b->entries<1){
+ return(0);
+ }
+ vals=floor(pow((float)b->entries,1.f/b->dim));
/* the above *should* be reliable, but we'll not assume that FP is
ever reliable when bitstream sync is at stake; verify via integer
means that vals really is the greatest value of dim for which
vals^b->bim <= b->entries */
/* treat the above as an initial guess */
+ if(vals<1){
+ vals=1;
+ }
while(1){
long acc=1;
long acc1=1;
int i;
for(i=0;i<b->dim;i++){
+ if(b->entries/vals<acc)break;
acc*=vals;
- acc1*=vals+1;
+ if(LONG_MAX/(vals+1)<acc1)acc1=LONG_MAX;
+ else acc1*=vals+1;
}
- if(acc<=b->entries && acc1>b->entries){
+ if(i>=b->dim && acc<=b->entries && acc1>b->entries){
return(vals);
}else{
- if(acc>b->entries){
+ if(i<b->dim || acc>b->entries){
vals--;
}else{
vals++;
c->used_entries=s->entries;
c->dim=s->dim;
c->codelist=_make_words(s->lengthlist,s->entries,0);
- //c->valuelist=_book_unquantize(s,s->entries,NULL);
+ /* c->valuelist=_book_unquantize(s,s->entries,NULL); */
c->quantvals=_book_maptype1_quantvals(s);
c->minval=(int)rint(_float32_unpack(s->q_min));
c->delta=(int)rint(_float32_unpack(s->q_delta));
int vorbis_book_init_decode(codebook *c,const static_codebook *s){
int i,j,n=0,tabn;
int *sortindex;
+
memset(c,0,sizeof(*c));
- /* count actually used entries */
+ /* count actually used entries and find max length */
for(i=0;i<s->entries;i++)
if(s->lengthlist[i]>0)
n++;
c->dim=s->dim;
if(n>0){
-
/* two different remappings go on here.
First, we collapse the likely sparse codebook down only to
c->codelist[sortindex[i]]=codes[i];
_ogg_free(codes);
-
c->valuelist=_book_unquantize(s,n,sortindex);
c->dec_index=_ogg_malloc(n*sizeof(*c->dec_index));
c->dec_index[sortindex[n++]]=i;
c->dec_codelengths=_ogg_malloc(n*sizeof(*c->dec_codelengths));
+ c->dec_maxlength=0;
for(n=0,i=0;i<s->entries;i++)
- if(s->lengthlist[i]>0)
+ if(s->lengthlist[i]>0){
c->dec_codelengths[sortindex[n++]]=s->lengthlist[i];
+ if(s->lengthlist[i]>c->dec_maxlength)
+ c->dec_maxlength=s->lengthlist[i];
+ }
- c->dec_firsttablen=_ilog(c->used_entries)-4; /* this is magic */
- if(c->dec_firsttablen<5)c->dec_firsttablen=5;
- if(c->dec_firsttablen>8)c->dec_firsttablen=8;
-
- tabn=1<<c->dec_firsttablen;
- c->dec_firsttable=_ogg_calloc(tabn,sizeof(*c->dec_firsttable));
- c->dec_maxlength=0;
+ if(n==1 && c->dec_maxlength==1){
+ /* special case the 'single entry codebook' with a single bit
+ fastpath table (that always returns entry 0 )in order to use
+ unmodified decode paths. */
+ c->dec_firsttablen=1;
+ c->dec_firsttable=_ogg_calloc(2,sizeof(*c->dec_firsttable));
+ c->dec_firsttable[0]=c->dec_firsttable[1]=1;
- for(i=0;i<n;i++){
- if(c->dec_maxlength<c->dec_codelengths[i])
- c->dec_maxlength=c->dec_codelengths[i];
- 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+1;
+ }else{
+ c->dec_firsttablen=ov_ilog(c->used_entries)-4; /* this is magic */
+ if(c->dec_firsttablen<5)c->dec_firsttablen=5;
+ if(c->dec_firsttablen>8)c->dec_firsttablen=8;
+
+ tabn=1<<c->dec_firsttablen;
+ c->dec_firsttable=_ogg_calloc(tabn,sizeof(*c->dec_firsttable));
+
+ for(i=0;i<n;i++){
+ 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+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);
- long lo=0,hi=0;
-
- for(i=0;i<tabn;i++){
- ogg_uint32_t word=i<<(32-c->dec_firsttablen);
- if(c->dec_firsttable[bitreverse(word)]==0){
- while((lo+1)<n && c->codelist[lo+1]<=word)lo++;
- while( hi<n && word>=(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[bitreverse(word)]=
- 0x80000000UL | (loval<<15) | hival;
+ /* 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);
+ long lo=0,hi=0;
+
+ for(i=0;i<tabn;i++){
+ ogg_uint32_t word=i<<(32-c->dec_firsttablen);
+ if(c->dec_firsttable[bitreverse(word)]==0){
+ while((lo+1)<n && c->codelist[lo+1]<=word)lo++;
+ while( hi<n && word>=(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[bitreverse(word)]=
+ 0x80000000UL | (loval<<15) | hival;
+ }
}
}
}
projects / platform / upstream / libvorbis.git / blobdiff