X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=vq%2Fbookutil.c;h=58d78beeb153ece00a0fbbf3dfba2b9d888b9f27;hb=151868fb5812f1402c28b0a7f5c5397d5dc6eb09;hp=8976c3d8199d35583a9115da3d792077b97fa97d;hpb=a4f1fba5bb1f6199eb963442b3c8fd5a32257539;p=platform%2Fupstream%2Flibvorbis.git

diff --git a/vq/bookutil.c b/vq/bookutil.c
index 8976c3d..58d78be 100644
--- a/vq/bookutil.c
+++ b/vq/bookutil.c
@@ -1,18 +1,17 @@
 /********************************************************************
  *                                                                  *
- * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE.  *
- * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
- * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE.    *
- * PLEASE READ THESE TERMS DISTRIBUTING.                            *
+ * 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 OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-2000             *
- * by Monty <monty@xiph.org> and The XIPHOPHORUS Company            *
- * http://www.xiph.org/                                             *
+ * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2014             *
+ * by the Xiph.Org Foundation http://www.xiph.org/                  *
  *                                                                  *
  ********************************************************************
 
  function: utility functions for loading .vqh and .vqd files
- last mod: $Id: bookutil.c,v 1.11 2000/02/21 01:12:53 xiphmont Exp $
+ last mod: $Id$
 
  ********************************************************************/
 
@@ -21,25 +20,62 @@
 #include <math.h>
 #include <string.h>
 #include <errno.h>
-#include "vorbis/codebook.h"
 #include "bookutil.h"
 
-void codebook_unquantize(codebook *b){
-  long j,k;
-  const static_codebook *c=b->c;
-  double mindel=float24_unpack(c->q_min);
-  double delta=float24_unpack(c->q_delta);
-  if(!b->valuelist)b->valuelist=malloc(sizeof(double)*c->entries*c->dim);
-  
-  for(j=0;j<c->entries;j++){
-    double last=0.;
-    for(k=0;k<c->dim;k++){
-      double val=c->quantlist[j*c->dim+k]*delta+last+mindel;
-      b->valuelist[j*c->dim+k]=val;
-      if(c->q_sequencep)last=val;
+int _best(codebook *book, float *a, int step){
+
+  int dim=book->dim;
+  int i,j,o;
+  int minval=book->minval;
+  int del=book->delta;
+  int qv=book->quantvals;
+  int ze=(qv>>1);
+  int index=0;
+  /* assumes integer/centered encoder codebook maptype 1 no more than dim 8 */
+
+  if(del!=1){
+    for(i=0,o=step*(dim-1);i<dim;i++,o-=step){
+      int v = ((int)rint(a[o])-minval+(del>>1))/del;
+      int m = (v<ze ? ((ze-v)<<1)-1 : ((v-ze)<<1));
+      index = index*qv+ (m<0?0:(m>=qv?qv-1:m));
+    }
+  }else{
+    for(i=0,o=step*(dim-1);i<dim;i++,o-=step){
+      int v = (int)rint(a[o])-minval;
+      int m = (v<ze ? ((ze-v)<<1)-1 : ((v-ze)<<1));
+      index = index*qv+ (m<0?0:(m>=qv?qv-1:m));
+    }
+  }
 
+  if(book->c->lengthlist[index]<=0){
+    const static_codebook *c=book->c;
+    int best=-1;
+    /* assumes integer/centered encoder codebook maptype 1 no more than dim 8 */
+    int e[8]={0,0,0,0,0,0,0,0};
+    int maxval = book->minval + book->delta*(book->quantvals-1);
+    for(i=0;i<book->entries;i++){
+      if(c->lengthlist[i]>0){
+        float this=0;
+        for(j=0;j<dim;j++){
+          float val=(e[j]-a[j*step]);
+          this+=val*val;
+        }
+        if(best==-1 || this<best){
+          best=this;
+          index=i;
+        }
+      }
+      /* assumes the value patterning created by the tools in vq/ */
+      j=0;
+      while(e[j]>=maxval)
+        e[j++]=0;
+      if(e[j]>=0)
+        e[j]+=book->delta;
+      e[j]= -e[j];
     }
   }
+
+  return index;
 }
 
 /* A few little utils for reading files */
@@ -57,18 +93,18 @@ char *get_line(FILE *in){
       if(sofar+1>=lbufsize){
         if(!lbufsize){  
           lbufsize=1024;
-          linebuffer=malloc(lbufsize);
+          linebuffer=_ogg_malloc(lbufsize);
         }else{
           lbufsize*=2;
-          linebuffer=realloc(linebuffer,lbufsize);
+          linebuffer=_ogg_realloc(linebuffer,lbufsize);
         }
       }
       {
         long c=fgetc(in);
         switch(c){
         case EOF:
-	  if(sofar==0)return(NULL);
-	  /* fallthrough correct */
+          if(sofar==0)return(NULL);
+          /* fallthrough correct */
         case '\n':
           linebuffer[sofar]='\0';
           gotline=1;
@@ -92,7 +128,7 @@ char *get_line(FILE *in){
 /* read the next numerical value from the given file */
 static char *value_line_buff=NULL;
 
-int get_line_value(FILE *in,double *value){
+int get_line_value(FILE *in,float *value){
   char *next;
 
   if(!value_line_buff)return(-1);
@@ -109,7 +145,7 @@ int get_line_value(FILE *in,double *value){
   }
 }
 
-int get_next_value(FILE *in,double *value){
+int get_next_value(FILE *in,float *value){
   while(1){
     if(get_line_value(in,value)){
       value_line_buff=get_line(in);
@@ -121,21 +157,28 @@ int get_next_value(FILE *in,double *value){
 }
 
 int get_next_ivalue(FILE *in,long *ivalue){
-  double value;
+  float value;
   int ret=get_next_value(in,&value);
   *ivalue=value;
   return(ret);
 }
 
-static double sequence_base=0.;
+static float sequence_base=0.f;
 static int v_sofar=0;
 void reset_next_value(void){
   value_line_buff=NULL;
-  sequence_base=0.;
+  sequence_base=0.f;
   v_sofar=0;
 }
 
-int get_vector(codebook *b,FILE *in,int start, int n,double *a){
+char *setup_line(FILE *in){
+  reset_next_value();
+  value_line_buff=get_line(in);
+  return(value_line_buff);
+}
+
+
+int get_vector(codebook *b,FILE *in,int start, int n,float *a){
   int i;
   const static_codebook *c=b->c;
 
@@ -144,25 +187,25 @@ int get_vector(codebook *b,FILE *in,int start, int n,double *a){
     if(v_sofar==n || get_line_value(in,a)){
       reset_next_value();
       if(get_next_value(in,a))
-	break;
+        break;
       for(i=0;i<start;i++){
-	sequence_base=*a;
-	get_line_value(in,a);
+        sequence_base=*a;
+        get_line_value(in,a);
       }
     }
 
     for(i=1;i<c->dim;i++)
       if(get_line_value(in,a+i))
-	break;
+        break;
     
     if(i==c->dim){
-      double temp=a[c->dim-1];
+      float temp=a[c->dim-1];
       for(i=0;i<c->dim;i++)a[i]-=sequence_base;
       if(c->q_sequencep)sequence_base=temp;
       v_sofar++;
       return(0);
     }
-    sequence_base=0.;
+    sequence_base=0.f;
   }
 
   return(-1);
@@ -176,218 +219,88 @@ char *find_seek_to(FILE *in,char *s){
     char *line=get_line(in);
     if(line){
       if(strstr(line,s))
-	return(line);
+        return(line);
     }else
       return(NULL);
   }
 }
 
 
-/* this reads the format as written by vqbuild; innocent (legal)
-   tweaking of the file that would not affect its valid header-ness
-   will break this routine */
+/* this reads the format as written by vqbuild/latticebuild; innocent
+   (legal) tweaking of the file that would not affect its valid
+   header-ness will break this routine */
 
 codebook *codebook_load(char *filename){
-  codebook *b=calloc(1,sizeof(codebook));
-  static_codebook *c=(static_codebook *)(b->c=calloc(1,sizeof(static_codebook)));
-  encode_aux *a=calloc(1,sizeof(encode_aux));
+  codebook *b=_ogg_calloc(1,sizeof(codebook));
+  static_codebook *c=(static_codebook *)(b->c=_ogg_calloc(1,sizeof(static_codebook)));
+  int quant_to_read=0;
   FILE *in=fopen(filename,"r");
   char *line;
   long i;
 
-  c->encode_tree=a;
-
   if(in==NULL){
     fprintf(stderr,"Couldn't open codebook %s\n",filename);
     exit(1);
   }
 
   /* find the codebook struct */
-  find_seek_to(in,"static static_codebook _vq_book_");
+  find_seek_to(in,"static const static_codebook ");
 
   /* get the major important values */
   line=get_line(in);
-  if(sscanf(line,"%ld, %ld, %ld, %ld, %d, %d",
-	    &(c->dim),&(c->entries),&(c->q_min),&(c->q_delta),&(c->q_quant),
-	    &(c->q_sequencep))!=6){
+  if(sscanf(line,"%ld, %ld,",
+            &(c->dim),&(c->entries))!=2){
     fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);
     exit(1);
   }
-
-  /* find the auxiliary encode struct (if any) */
-  find_seek_to(in,"static encode_aux _vq_aux_");
-  /* how big? */
-  line=get_line(in);
   line=get_line(in);
   line=get_line(in);
-  line=get_line(in);
-  line=get_line(in);
-  if(sscanf(line,"%ld, %ld",&(a->aux),&(a->alloc))!=2){
-    fprintf(stderr,"2: syntax in %s in line:\t %s",filename,line);
+  if(sscanf(line,"%d, %ld, %ld, %d, %d,",
+            &(c->maptype),&(c->q_min),&(c->q_delta),&(c->q_quant),
+            &(c->q_sequencep))!=5){
+    fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);
     exit(1);
   }
+  
+  switch(c->maptype){
+  case 0:
+    quant_to_read=0;
+    break;
+  case 1:
+    quant_to_read=_book_maptype1_quantvals(c);
+    break;
+  case 2:
+    quant_to_read=c->entries*c->dim;
+    break;
+  }
     
   /* load the quantized entries */
-  find_seek_to(in,"static long _vq_quantlist_");
+  find_seek_to(in,"static const long _vq_quantlist_");
   reset_next_value();
-  c->quantlist=malloc(sizeof(long)*c->entries*c->dim);
-  for(i=0;i<c->entries*c->dim;i++)
+  c->quantlist=_ogg_malloc(sizeof(long)*quant_to_read);
+  for(i=0;i<quant_to_read;i++)
     if(get_next_ivalue(in,c->quantlist+i)){
       fprintf(stderr,"out of data while reading codebook %s\n",filename);
       exit(1);
     }
-
+  
   /* load the lengthlist */
-  find_seek_to(in,"static long _vq_lengthlist");
+  find_seek_to(in,"_lengthlist");
   reset_next_value();
-  c->lengthlist=malloc(sizeof(long)*c->entries);
+  c->lengthlist=_ogg_malloc(sizeof(long)*c->entries);
   for(i=0;i<c->entries;i++)
     if(get_next_ivalue(in,c->lengthlist+i)){
       fprintf(stderr,"out of data while reading codebook %s\n",filename);
       exit(1);
     }
 
-  /* load ptr0 */
-  find_seek_to(in,"static long _vq_ptr0");
-  reset_next_value();
-  a->ptr0=malloc(sizeof(long)*a->aux);
-  for(i=0;i<a->aux;i++)
-    if(get_next_ivalue(in,a->ptr0+i)){
-      fprintf(stderr,"out of data while reading codebook %s\n",filename);
-      exit(1);
-    }
-
-  /* load ptr1 */
-  find_seek_to(in,"static long _vq_ptr1");
-  reset_next_value();
-  a->ptr1=malloc(sizeof(long)*a->aux);
-  for(i=0;i<a->aux;i++)
-    if(get_next_ivalue(in,a->ptr1+i)){
-      fprintf(stderr,"out of data while reading codebook %s\n",filename);
-      exit(1);
-    }
-
-
-  /* load p */
-  find_seek_to(in,"static long _vq_p_");
-  reset_next_value();
-  a->p=malloc(sizeof(long)*a->aux);
-  for(i=0;i<a->aux;i++)
-    if(get_next_ivalue(in,a->p+i)){
-      fprintf(stderr,"out of data while reading codebook %s\n",filename);
-      exit(1);
-    }
-
-  /* load q */
-  find_seek_to(in,"static long _vq_q_");
-  reset_next_value();
-  a->q=malloc(sizeof(long)*a->aux);
-  for(i=0;i<a->aux;i++)
-    if(get_next_ivalue(in,a->q+i)){
-      fprintf(stderr,"out of data while reading codebook %s\n",filename);
-      exit(1);
-    }
-
   /* got it all */
   fclose(in);
-
-  /* might as well unquantize the entries while we're at it */
-  codebook_unquantize(b);
-
-  /* don't need n and c */
-  return(b);
-}
-
-
-/* the new version!  we have ptr0[0] distinct trees in the auxiliary
-   encoding structure.  Find the best match in each one, choosing the
-   best global match */
-
-int codebook_entry(codebook *b,double *val){
-  const static_codebook *c=b->c;
-  encode_aux *t=c->encode_tree;
-  int trees=t->ptr0[0];
-
-  /*{
-    brute force 
-    double this,best=_dist(c->dim,val,b->valuelist);
-    int i;
-    for(i=1;i<c->entries;i++){
-      this=_dist(c->dim,val,b->valuelist+i*c->dim);
-      if(this<best){
-        ptr=-i;
-        best=this;
-      }
-    }
-  }*/
   
-  double *n=alloca(c->dim*sizeof(double));
-  double bestmetric;
-  double best=-1;
-  while(trees>0){
-    int ptr=t->ptr0[--trees],k;
-
-    while(1){
-      double C=0.;
-      double *p=b->valuelist+t->p[ptr];
-      double *q=b->valuelist+t->q[ptr];
-      
-      for(k=0;k<c->dim;k++){
-	n[k]=p[k]-q[k];
-	C-=(p[k]+q[k])*n[k];
-      }
-      C/=2.;
-      
-      for(k=0;k<c->dim;k++)
-	C+=n[k]*val[k];
-      
-      if(C>0.) /* in A */
-	ptr= -t->ptr0[ptr];
-      else     /* in B */
-	ptr= -t->ptr1[ptr];
-      if(ptr<=0)break;
-    }
-
-    {
-      double dist=0.;
-      for(k=0;k<c->dim;k++){
-	double one=val[k]-(b->valuelist-ptr*c->dim)[k];
-	dist+=one*one;
-      }
-      if(best==-1 || dist<bestmetric){
-	best=-ptr;
-	bestmetric=dist;
-      }
-    }
-  }
-
-  return(best);
-}
-
-/* 24 bit float (not IEEE; nonnormalized mantissa +
-   biased exponent ): neeeeemm mmmmmmmm mmmmmmmm */
+  vorbis_book_init_encode(b,c);
+  b->valuelist=_book_unquantize(c,c->entries,NULL);
 
-long float24_pack(double val){
-  int sign=0;
-  long exp;
-  long mant;
-  if(val<0){
-    sign=0x800000;
-    val= -val;
-  }
-  exp= floor(log(val)/log(2));
-  mant=rint(ldexp(val,17-exp));
-  exp=(exp+VQ_FEXP_BIAS)<<18;
-
-  return(sign|exp|mant);
-}
-
-double float24_unpack(long val){
-  double mant=val&0x3ffff;
-  double sign=val&0x800000;
-  double exp =(val&0x7c0000)>>18;
-  if(sign)mant= -mant;
-  return(ldexp(mant,exp-17-VQ_FEXP_BIAS));
+  return(b);
 }
 
 void spinnit(char *s,int n){
@@ -424,8 +337,10 @@ void spinnit(char *s,int n){
 
 void build_tree_from_lengths(int vals, long *hist, long *lengths){
   int i,j;
-  long *membership=malloc(vals*sizeof(long));
-      
+  long *membership=_ogg_malloc(vals*sizeof(long));
+  long *histsave=alloca(vals*sizeof(long));
+  memcpy(histsave,hist,vals*sizeof(long));
+
   for(i=0;i<vals;i++)membership[i]=i;
 
   /* find codeword lengths */
@@ -433,20 +348,20 @@ void build_tree_from_lengths(int vals, long *hist, long *lengths){
   for(i=vals;i>1;i--){
     int first=-1,second=-1;
     long least=-1;
-	
+        
     spinnit("building... ",i);
     
     /* find the two nodes to join */
     for(j=0;j<vals;j++)
-      if(least==-1 || hist[j]<least){
-	least=hist[j];
-	first=membership[j];
+      if(least==-1 || hist[j]<=least){
+        least=hist[j];
+        first=membership[j];
       }
     least=-1;
     for(j=0;j<vals;j++)
-      if((least==-1 || hist[j]<least) && membership[j]!=first){
-	least=hist[j];
-	second=membership[j];
+      if((least==-1 || hist[j]<=least) && membership[j]!=first){
+        least=hist[j];
+        second=membership[j];
       }
     if(first==-1 || second==-1){
       fprintf(stderr,"huffman fault; no free branch\n");
@@ -457,9 +372,9 @@ void build_tree_from_lengths(int vals, long *hist, long *lengths){
     least=hist[first]+hist[second];
     for(j=0;j<vals;j++)
       if(membership[j]==first || membership[j]==second){
-	membership[j]=first;
-	hist[j]=least;
-	lengths[j]++;
+        membership[j]=first;
+        hist[j]=least;
+        lengths[j]++;
       }
   }
   for(i=0;i<vals-1;i++)
@@ -467,6 +382,96 @@ void build_tree_from_lengths(int vals, long *hist, long *lengths){
       fprintf(stderr,"huffman fault; failed to build single tree\n");
       exit(1);
     }
-  
+
+  /* for sanity check purposes: how many bits would it have taken to
+     encode the training set? */
+  {
+    long bitsum=0;
+    long samples=0;
+    for(i=0;i<vals;i++){
+      bitsum+=(histsave[i]-1)*lengths[i];
+      samples+=histsave[i]-1;
+    }
+
+    if(samples){
+      fprintf(stderr,"\rTotal samples in training set: %ld      \n",samples);
+      fprintf(stderr,"\rTotal bits used to represent training set: %ld\n",
+              bitsum);
+    }
+  }
+
   free(membership);
 }
+
+/* wrap build_tree_from_lengths to allow zero entries in the histogram */
+void build_tree_from_lengths0(int vals, long *hist, long *lengths){
+
+  /* pack the 'sparse' hit list into a dense list, then unpack
+     the lengths after the build */
+
+  int upper=0,i;
+  long *lengthlist=_ogg_calloc(vals,sizeof(long));
+  long *newhist=alloca(vals*sizeof(long));
+
+  for(i=0;i<vals;i++)
+    if(hist[i]>0)
+      newhist[upper++]=hist[i];
+
+  if(upper != vals){
+    fprintf(stderr,"\rEliminating %d unused entries; %d entries remain\n",
+            vals-upper,upper);
+  }
+    
+  build_tree_from_lengths(upper,newhist,lengthlist);
+      
+  upper=0;
+  for(i=0;i<vals;i++)
+    if(hist[i]>0)
+      lengths[i]=lengthlist[upper++];
+    else
+      lengths[i]=0;
+
+  free(lengthlist);
+}
+
+void write_codebook(FILE *out,char *name,const static_codebook *c){
+  int i,j,k;
+
+  /* save the book in C header form */
+
+  /* first, the static vectors, then the book structure to tie it together. */
+  /* quantlist */
+  if(c->quantlist){
+    long vals=(c->maptype==1?_book_maptype1_quantvals(c):c->entries*c->dim);
+    fprintf(out,"static const long _vq_quantlist_%s[] = {\n",name);
+    for(j=0;j<vals;j++){
+      fprintf(out,"\t%ld,\n",c->quantlist[j]);
+    }
+    fprintf(out,"};\n\n");
+  }
+
+  /* lengthlist */
+  fprintf(out,"static const char _vq_lengthlist_%s[] = {\n",name);
+  for(j=0;j<c->entries;){
+    fprintf(out,"\t");
+    for(k=0;k<16 && j<c->entries;k++,j++)
+      fprintf(out,"%2ld,",c->lengthlist[j]);
+    fprintf(out,"\n");
+  }
+  fprintf(out,"};\n\n");
+
+  /* tie it all together */
+  
+  fprintf(out,"static const static_codebook %s = {\n",name);
+  
+  fprintf(out,"\t%ld, %ld,\n",c->dim,c->entries);
+  fprintf(out,"\t(char *)_vq_lengthlist_%s,\n",name);
+  fprintf(out,"\t%d, %ld, %ld, %d, %d,\n",
+          c->maptype,c->q_min,c->q_delta,c->q_quant,c->q_sequencep);
+  if(c->quantlist)
+    fprintf(out,"\t(long *)_vq_quantlist_%s,\n",name);
+  else
+    fprintf(out,"\tNULL,\n");
+
+  fprintf(out,"\t0\n};\n\n");
+}