summaryrefslogtreecommitdiffhomepage
path: root/vorbis/lib/sharedbook.c
diff options
context:
space:
mode:
Diffstat (limited to 'vorbis/lib/sharedbook.c')
-rw-r--r--vorbis/lib/sharedbook.c595
1 files changed, 0 insertions, 595 deletions
diff --git a/vorbis/lib/sharedbook.c b/vorbis/lib/sharedbook.c
deleted file mode 100644
index 4545d4f..0000000
--- a/vorbis/lib/sharedbook.c
+++ /dev/null
@@ -1,595 +0,0 @@
-/********************************************************************
- * *
- * THIS FILE IS PART OF THE OggVorbis SOFTWARE 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 SOURCE CODE IS (C) COPYRIGHT 1994-2015 *
- * by the Xiph.Org Foundation http://www.xiph.org/ *
- * *
- ********************************************************************
-
- function: basic shared codebook operations
-
- ********************************************************************/
-
-#include <stdlib.h>
-#include <limits.h>
-#include <math.h>
-#include <string.h>
-#include <ogg/ogg.h>
-#include "os.h"
-#include "misc.h"
-#include "vorbis/codec.h"
-#include "codebook.h"
-#include "scales.h"
-
-/**** pack/unpack helpers ******************************************/
-
-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 +
- biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm
- Why not IEEE? It's just not that important here. */
-
-#define VQ_FEXP 10
-#define VQ_FMAN 21
-#define VQ_FEXP_BIAS 768 /* bias toward values smaller than 1. */
-
-/* doesn't currently guard under/overflow */
-long _float32_pack(float val){
- int sign=0;
- long exp;
- long mant;
- if(val<0){
- sign=0x80000000;
- val= -val;
- }
- exp= floor(log(val)/log(2.f)+.001); //+epsilon
- mant=rint(ldexp(val,(VQ_FMAN-1)-exp));
- exp=(exp+VQ_FEXP_BIAS)<<VQ_FMAN;
-
- return(sign|exp|mant);
-}
-
-float _float32_unpack(long val){
- double mant=val&0x1fffff;
- int sign=val&0x80000000;
- long exp =(val&0x7fe00000L)>>VQ_FMAN;
- if(sign)mant= -mant;
- return(ldexp(mant,exp-(VQ_FMAN-1)-VQ_FEXP_BIAS));
-}
-
-/* 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(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));
- memset(marker,0,sizeof(marker));
-
- for(i=0;i<n;i++){
- long length=l[i];
- if(length>0){
- ogg_uint32_t entry=marker[length];
-
- /* when we claim a node for an entry, we also claim the nodes
- below it (pruning off the imagined tree that may have dangled
- from it) as well as blocking the use of any nodes directly
- above for leaves */
-
- /* update ourself */
- if(length<32 && (entry>>length)){
- /* error condition; the lengths must specify an overpopulated tree */
- _ogg_free(r);
- return(NULL);
- }
- r[count++]=entry;
-
- /* Look to see if the next shorter marker points to the node
- above. if so, update it and repeat. */
- {
- for(j=length;j>0;j--){
-
- if(marker[j]&1){
- /* have to jump branches */
- if(j==1)
- marker[1]++;
- else
- marker[j]=marker[j-1]<<1;
- break; /* invariant says next upper marker would already
- have been moved if it was on the same path */
- }
- marker[j]++;
- }
- }
-
- /* prune the tree; the implicit invariant says all the longer
- markers were dangling from our just-taken node. Dangle them
- from our *new* node. */
- for(j=length+1;j<33;j++)
- if((marker[j]>>1) == entry){
- entry=marker[j];
- marker[j]=marker[j-1]<<1;
- }else
- break;
- }else
- if(sparsecount==0)count++;
- }
-
- /* 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);
- }
- }
-
- /* bitreverse the words because our bitwise packer/unpacker is LSb
- endian */
- for(i=0,count=0;i<n;i++){
- ogg_uint32_t temp=0;
- for(j=0;j<l[i];j++){
- temp<<=1;
- temp|=(r[count]>>j)&1;
- }
-
- if(sparsecount){
- if(l[i])
- r[count++]=temp;
- }else
- r[count++]=temp;
- }
-
- return(r);
-}
-
-/* there might be a straightforward one-line way to do the below
- 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;
- 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;
- if(LONG_MAX/(vals+1)<acc1)acc1=LONG_MAX;
- else acc1*=vals+1;
- }
- if(i>=b->dim && acc<=b->entries && acc1>b->entries){
- return(vals);
- }else{
- if(i<b->dim || acc>b->entries){
- vals--;
- }else{
- vals++;
- }
- }
- }
-}
-
-/* unpack the quantized list of values for encode/decode ***********/
-/* we need to deal with two map types: in map type 1, the values are
- generated algorithmically (each column of the vector counts through
- the values in the quant vector). in map type 2, all the values came
- in in an explicit list. Both value lists must be unpacked */
-float *_book_unquantize(const static_codebook *b,int n,int *sparsemap){
- long j,k,count=0;
- if(b->maptype==1 || b->maptype==2){
- int quantvals;
- float mindel=_float32_unpack(b->q_min);
- float delta=_float32_unpack(b->q_delta);
- float *r=_ogg_calloc(n*b->dim,sizeof(*r));
-
- /* maptype 1 and 2 both use a quantized value vector, but
- different sizes */
- switch(b->maptype){
- case 1:
- /* most of the time, entries%dimensions == 0, but we need to be
- well defined. We define that the possible vales at each
- scalar is values == entries/dim. If entries%dim != 0, we'll
- have 'too few' values (values*dim<entries), which means that
- we'll have 'left over' entries; left over entries use zeroed
- values (and are wasted). So don't generate codebooks like
- that */
- quantvals=_book_maptype1_quantvals(b);
- for(j=0;j<b->entries;j++){
- if((sparsemap && b->lengthlist[j]) || !sparsemap){
- float last=0.f;
- int indexdiv=1;
- for(k=0;k<b->dim;k++){
- int index= (j/indexdiv)%quantvals;
- float val=b->quantlist[index];
- val=fabs(val)*delta+mindel+last;
- if(b->q_sequencep)last=val;
- if(sparsemap)
- r[sparsemap[count]*b->dim+k]=val;
- else
- r[count*b->dim+k]=val;
- indexdiv*=quantvals;
- }
- count++;
- }
-
- }
- break;
- case 2:
- for(j=0;j<b->entries;j++){
- if((sparsemap && b->lengthlist[j]) || !sparsemap){
- float last=0.f;
-
- for(k=0;k<b->dim;k++){
- float val=b->quantlist[j*b->dim+k];
- val=fabs(val)*delta+mindel+last;
- if(b->q_sequencep)last=val;
- if(sparsemap)
- r[sparsemap[count]*b->dim+k]=val;
- else
- r[count*b->dim+k]=val;
- }
- count++;
- }
- }
- break;
- }
-
- return(r);
- }
- return(NULL);
-}
-
-void vorbis_staticbook_destroy(static_codebook *b){
- if(b->allocedp){
- if(b->quantlist)_ogg_free(b->quantlist);
- if(b->lengthlist)_ogg_free(b->lengthlist);
- memset(b,0,sizeof(*b));
- _ogg_free(b);
- } /* otherwise, it is in static memory */
-}
-
-void vorbis_book_clear(codebook *b){
- /* static book is not cleared; we're likely called on the lookup and
- the static codebook belongs to the info struct */
- if(b->valuelist)_ogg_free(b->valuelist);
- if(b->codelist)_ogg_free(b->codelist);
-
- if(b->dec_index)_ogg_free(b->dec_index);
- if(b->dec_codelengths)_ogg_free(b->dec_codelengths);
- if(b->dec_firsttable)_ogg_free(b->dec_firsttable);
-
- memset(b,0,sizeof(*b));
-}
-
-int vorbis_book_init_encode(codebook *c,const static_codebook *s){
-
- memset(c,0,sizeof(*c));
- c->c=s;
- c->entries=s->entries;
- 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->quantvals=_book_maptype1_quantvals(s);
- c->minval=(int)rint(_float32_unpack(s->q_min));
- c->delta=(int)rint(_float32_unpack(s->q_delta));
-
- return(0);
-}
-
-static ogg_uint32_t bitreverse(ogg_uint32_t x){
- x= ((x>>16)&0x0000ffffUL) | ((x<<16)&0xffff0000UL);
- x= ((x>> 8)&0x00ff00ffUL) | ((x<< 8)&0xff00ff00UL);
- x= ((x>> 4)&0x0f0f0f0fUL) | ((x<< 4)&0xf0f0f0f0UL);
- x= ((x>> 2)&0x33333333UL) | ((x<< 2)&0xccccccccUL);
- return((x>> 1)&0x55555555UL) | ((x<< 1)&0xaaaaaaaaUL);
-}
-
-static int sort32a(const void *a,const void *b){
- return ( **(ogg_uint32_t **)a>**(ogg_uint32_t **)b)-
- ( **(ogg_uint32_t **)a<**(ogg_uint32_t **)b);
-}
-
-/* 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;
- int *sortindex;
-
- memset(c,0,sizeof(*c));
-
- /* count actually used entries and find max length */
- for(i=0;i<s->entries;i++)
- if(s->lengthlist[i]>0)
- n++;
-
- c->entries=s->entries;
- c->used_entries=n;
- c->dim=s->dim;
-
- if(n>0){
- /* two different remappings go on here.
-
- First, we collapse the likely sparse codebook down only to
- actually represented values/words. This collapsing needs to be
- indexed as map-valueless books are used to encode original entry
- positions as integers.
-
- Second, we reorder all vectors, including the entry index above,
- by sorted bitreversed codeword to allow treeless decode. */
-
- /* perform sort */
- ogg_uint32_t *codes=_make_words(s->lengthlist,s->entries,c->used_entries);
- ogg_uint32_t **codep=alloca(sizeof(*codep)*n);
-
- if(codes==NULL)goto err_out;
-
- for(i=0;i<n;i++){
- codes[i]=bitreverse(codes[i]);
- codep[i]=codes+i;
- }
-
- qsort(codep,n,sizeof(*codep),sort32a);
-
- sortindex=alloca(n*sizeof(*sortindex));
- c->codelist=_ogg_malloc(n*sizeof(*c->codelist));
- /* the index is a reverse index */
- for(i=0;i<n;i++){
- int position=codep[i]-codes;
- sortindex[position]=i;
- }
-
- for(i=0;i<n;i++)
- 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));
-
- for(n=0,i=0;i<s->entries;i++)
- if(s->lengthlist[i]>0)
- 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){
- c->dec_codelengths[sortindex[n++]]=s->lengthlist[i];
- if(s->lengthlist[i]>c->dec_maxlength)
- c->dec_maxlength=s->lengthlist[i];
- }
-
- 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;
-
- }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;
- }
- }
- }
- }
- }
- }
-
- return(0);
- err_out:
- vorbis_book_clear(c);
- return(-1);
-}
-
-long vorbis_book_codeword(codebook *book,int entry){
- if(book->c) /* only use with encode; decode optimizations are
- allowed to break this */
- return book->codelist[entry];
- return -1;
-}
-
-long vorbis_book_codelen(codebook *book,int entry){
- if(book->c) /* only use with encode; decode optimizations are
- allowed to break this */
- return book->c->lengthlist[entry];
- return -1;
-}
-
-#ifdef _V_SELFTEST
-
-/* Unit tests of the dequantizer; this stuff will be OK
- cross-platform, I simply want to be sure that special mapping cases
- actually work properly; a bug could go unnoticed for a while */
-
-#include <stdio.h>
-
-/* cases:
-
- no mapping
- full, explicit mapping
- algorithmic mapping
-
- nonsequential
- sequential
-*/
-
-static long full_quantlist1[]={0,1,2,3, 4,5,6,7, 8,3,6,1};
-static long partial_quantlist1[]={0,7,2};
-
-/* no mapping */
-static_codebook test1={
- 4,16,
- NULL,
- 0,
- 0,0,0,0,
- NULL,
- 0
-};
-static float *test1_result=NULL;
-
-/* linear, full mapping, nonsequential */
-static_codebook test2={
- 4,3,
- NULL,
- 2,
- -533200896,1611661312,4,0,
- full_quantlist1,
- 0
-};
-static float test2_result[]={-3,-2,-1,0, 1,2,3,4, 5,0,3,-2};
-
-/* linear, full mapping, sequential */
-static_codebook test3={
- 4,3,
- NULL,
- 2,
- -533200896,1611661312,4,1,
- full_quantlist1,
- 0
-};
-static float test3_result[]={-3,-5,-6,-6, 1,3,6,10, 5,5,8,6};
-
-/* linear, algorithmic mapping, nonsequential */
-static_codebook test4={
- 3,27,
- NULL,
- 1,
- -533200896,1611661312,4,0,
- partial_quantlist1,
- 0
-};
-static float test4_result[]={-3,-3,-3, 4,-3,-3, -1,-3,-3,
- -3, 4,-3, 4, 4,-3, -1, 4,-3,
- -3,-1,-3, 4,-1,-3, -1,-1,-3,
- -3,-3, 4, 4,-3, 4, -1,-3, 4,
- -3, 4, 4, 4, 4, 4, -1, 4, 4,
- -3,-1, 4, 4,-1, 4, -1,-1, 4,
- -3,-3,-1, 4,-3,-1, -1,-3,-1,
- -3, 4,-1, 4, 4,-1, -1, 4,-1,
- -3,-1,-1, 4,-1,-1, -1,-1,-1};
-
-/* linear, algorithmic mapping, sequential */
-static_codebook test5={
- 3,27,
- NULL,
- 1,
- -533200896,1611661312,4,1,
- partial_quantlist1,
- 0
-};
-static float test5_result[]={-3,-6,-9, 4, 1,-2, -1,-4,-7,
- -3, 1,-2, 4, 8, 5, -1, 3, 0,
- -3,-4,-7, 4, 3, 0, -1,-2,-5,
- -3,-6,-2, 4, 1, 5, -1,-4, 0,
- -3, 1, 5, 4, 8,12, -1, 3, 7,
- -3,-4, 0, 4, 3, 7, -1,-2, 2,
- -3,-6,-7, 4, 1, 0, -1,-4,-5,
- -3, 1, 0, 4, 8, 7, -1, 3, 2,
- -3,-4,-5, 4, 3, 2, -1,-2,-3};
-
-void run_test(static_codebook *b,float *comp){
- float *out=_book_unquantize(b,b->entries,NULL);
- int i;
-
- if(comp){
- if(!out){
- fprintf(stderr,"_book_unquantize incorrectly returned NULL\n");
- exit(1);
- }
-
- for(i=0;i<b->entries*b->dim;i++)
- if(fabs(out[i]-comp[i])>.0001){
- fprintf(stderr,"disagreement in unquantized and reference data:\n"
- "position %d, %g != %g\n",i,out[i],comp[i]);
- exit(1);
- }
-
- }else{
- if(out){
- fprintf(stderr,"_book_unquantize returned a value array: \n"
- " correct result should have been NULL\n");
- exit(1);
- }
- }
-}
-
-int main(){
- /* run the nine dequant tests, and compare to the hand-rolled results */
- fprintf(stderr,"Dequant test 1... ");
- run_test(&test1,test1_result);
- fprintf(stderr,"OK\nDequant test 2... ");
- run_test(&test2,test2_result);
- fprintf(stderr,"OK\nDequant test 3... ");
- run_test(&test3,test3_result);
- fprintf(stderr,"OK\nDequant test 4... ");
- run_test(&test4,test4_result);
- fprintf(stderr,"OK\nDequant test 5... ");
- run_test(&test5,test5_result);
- fprintf(stderr,"OK\n\n");
-
- return(0);
-}
-
-#endif