Incremental update toward first cut

svn path=/trunk/vorbis/; revision=268

3 files changed, 92 insertions, 192 deletions

diff --git a/vq/bookutil.c b/vq/bookutil.c
index 8976c3d8..cb4d43a2 100644
--- a/vq/bookutil.c
+++ b/vq/bookutil.c
@@ -12,7 +12,7 @@
  ********************************************************************
 
  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: bookutil.c,v 1.12 2000/02/23 09:10:10 xiphmont Exp $
 
  ********************************************************************/
 
@@ -291,77 +291,40 @@ codebook *codebook_load(char *filename){
   /* got it all */
   fclose(in);
 
-  /* might as well unquantize the entries while we're at it */
+  /* 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;
-    }
+  int ptr=0,k;
 
-    {
-      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;
-      }
+  do{
+    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];
+  }while(ptr>0);
 
-  return(best);
+  return(-ptr);
 }
 
 /* 24 bit float (not IEEE; nonnormalized mantissa +
@@ -425,7 +388,7 @@ 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));
-      
+
   for(i=0;i<vals;i++)membership[i]=i;
 
   /* find codeword lengths */
@@ -467,6 +430,6 @@ void build_tree_from_lengths(int vals, long *hist, long *lengths){
       fprintf(stderr,"huffman fault; failed to build single tree\n");
       exit(1);
     }
-  
+
   free(membership);
 }
diff --git a/vq/run.c b/vq/run.c
index 1d32c955..b6b55279 100644
--- a/vq/run.c
+++ b/vq/run.c
@@ -12,7 +12,7 @@
  ********************************************************************
 
  function: utility main for loading and operating on codebooks
- last mod: $Id: run.c,v 1.8 2000/01/21 13:42:40 xiphmont Exp $
+ last mod: $Id: run.c,v 1.9 2000/02/23 09:10:11 xiphmont Exp $
 
  ********************************************************************/
 
@@ -79,7 +79,7 @@ int main(int argc,char *argv[]){
       char *dot;
       char *ext=NULL;
       char *name=strdup(*argv++);
-      dot=strchr(name,'.');
+      dot=strrchr(name,'.');
       if(dot)
 	ext=dot+1;
       else
@@ -95,10 +95,10 @@ int main(int argc,char *argv[]){
 
 	basename=strrchr(name,'/');
 	if(basename)
-	  basename=strdup(basename);
+	  basename=strdup(basename)+1;
 	else
 	  basename=strdup(name);
-	dot=strchr(basename,'.');
+	dot=strrchr(basename,'.');
 	if(dot)*dot='\0';
 
 	b=realloc(b,sizeof(codebook *)*(books+2));
diff --git a/vq/vqsplit.c b/vq/vqsplit.c
index f9cc02b6..26552055 100644
--- a/vq/vqsplit.c
+++ b/vq/vqsplit.c
@@ -12,7 +12,7 @@
  ********************************************************************
 
  function: build a VQ codebook and the encoding decision 'tree'
- last mod: $Id: vqsplit.c,v 1.17 2000/02/21 01:13:02 xiphmont Exp $
+ last mod: $Id: vqsplit.c,v 1.18 2000/02/23 09:10:13 xiphmont Exp $
 
  ********************************************************************/
 
@@ -454,152 +454,83 @@ void vqsp_book(vqgen *v, codebook *b, long *quantlist){
 
   fprintf(stderr,"Building a book with %ld unique entries...\n",v->entries);
 
-  /* We don't always generate a single tree; it tends to be large.  We
-     trade off by splitting the cell and point sets into n totally
-     non-overlapping subsets (where the decision tree tends to have
-     substantial overlap in hyperplane splits) and generating a tree
-     for each.  Because the tree depth is O(n) o(lg(n)), the smaller
-     data set will get us much better storage usage for worst cases
-     (and we will run toward worst case) */
-
   {
-    /* split data set... */
-    int trees=v->entries/(32+log(v->entries)/log(2)*2)+1; /* a guess */
-    long *entrymap=malloc(v->entries*sizeof(long *));
-    long **entryindex=malloc(trees*sizeof(long *));
-    long *entries=calloc(trees,sizeof(long));
-    long *pointmap=malloc(v->points*sizeof(long));
-    long desired=(v->entries/trees)+1;
-    int booknum;
+    long *entryindex=malloc(v->entries*sizeof(long *));
+    long *pointindex=malloc(v->points*sizeof(long));
     long pointssofar=0;
       
-    for(i=0;i<trees;i++)entryindex[i]=calloc(desired,sizeof(long));
-
-    fprintf(stderr,"Prepartitioning into %d trees...\n",trees);
-
-    /* map points to cells */
-    for(i=0;i<v->points;i++){
-      double *ppt=_point(v,i);
-      double firstmetric=_dist(v,_now(v,0),ppt);
-      long   firstentry=0;
-      
-      if(!(i&0xff))spinnit("parititoning... ",v->points-i);
-
-      for(j=0;j<v->entries;j++){
-	double thismetric=_dist(v,_now(v,j),ppt);
-	if(thismetric<firstmetric){
-	  firstmetric=thismetric;
-	  firstentry=j;
-	}
-      }
-      pointmap[i]=firstentry;
-    }
-
-    /* this could be more effective; long, narrow slices are probably
-       better than these porous blobs */
+    for(i=0;i<v->entries;i++)entryindex[i]=i;
+    for(i=0;i<v->points;i++)pointindex[i]=i;
 
-    for(j=0;j<v->entries;j++){
-      int choice=-1;
-      for(i=0;i<trees;i++){
-	if(entries[i]<desired){ /* still has open space */
-	  choice=i;
-	  break;
-	}
-      }
-
-      entryindex[choice][entries[choice]++]=j;
-      entrymap[j]=choice;
-    }
-
-    
-    /* we overload the static codebook ptrs just a bit...  the first
-       <tree> ptr0s just point to the starting point in the struct for
-       that tree.  The first ptr0 points to the first tree at offset
-       <tree>, and thus can be used as the tree count.  Clever but
-       totally opaque :-( . */
-    
     t->alloc=4096;
     t->ptr0=malloc(sizeof(long)*t->alloc);
     t->ptr1=malloc(sizeof(long)*t->alloc);
     t->p=malloc(sizeof(long)*t->alloc);
     t->q=malloc(sizeof(long)*t->alloc);
-    t->aux=trees; 
+    t->aux=0;
     c->dim=v->elements;
     c->entries=v->entries;
     c->lengthlist=calloc(c->entries,sizeof(long));
     
-    for(booknum=0;booknum<trees;booknum++){
-      long points=0;
-      long *pointindex;
-
-      t->ptr0[booknum]=t->aux;
-      for(i=0;i<v->points;i++)
-	if(entrymap[pointmap[i]]==booknum)points++;
-      pointindex=malloc(points*sizeof(long));
-      points=0;
-      for(i=0;i<v->points;i++)
-	if(entrymap[pointmap[i]]==booknum)pointindex[points++]=i;
-
-      /* generate the encoding decision heirarchy */
-      fprintf(stderr,"Leaves added: %d              \n",
-	      lp_split(v,b,entryindex[booknum],entries[booknum],
-		       pointindex,points,0,&pointssofar));
+    fprintf(stderr,"Leaves added: %d              \n",
+	    lp_split(v,b,entryindex,v->entries,
+		     pointindex,v->points,0,&pointssofar));
       
-      free(pointindex);
-      fprintf(stderr,"Paring/rerouting redundant branches... ");
-
-      /* The tree is likely big and redundant.  Pare and reroute branches */
-      {
-	int changedflag=1;
+    free(pointindex);
+    
+    fprintf(stderr,"Paring/rerouting redundant branches... ");
+    
+    /* The tree is likely big and redundant.  Pare and reroute branches */
+    {
+      int changedflag=1;
+      
+      while(changedflag){
+	changedflag=0;
 	
-	while(changedflag){
-	  changedflag=0;
-	  
-	  /* span the tree node by node; list unique decision nodes and
-	     short circuit redundant branches */
+	/* span the tree node by node; list unique decision nodes and
+	   short circuit redundant branches */
+	
+	for(i=0;i<t->aux;){
+	  int k;
 	  
-	  for(i=t->ptr0[booknum];i<t->aux;){
-	    int k;
-
-	    /* check list of unique decisions */
-	    for(j=t->ptr0[booknum];j<i;j++)
-	      if(_node_eq(t,i,j))break;
-
-	    if(j<i){
-	      /* a redundant entry; find all higher nodes referencing it and
-		 short circuit them to the previously noted unique entry */
-	      changedflag=1;
-	      for(k=0;k<t->aux;k++){
-		if(t->ptr0[k]==-i)t->ptr0[k]=-j;
-		if(t->ptr1[k]==-i)t->ptr1[k]=-j;
-	      }
-
-	      /* Now, we need to fill in the hole from this redundant
-		 entry in the listing.  Insert the last entry in the list.
-		 Fix the forward pointers to that last entry */
-	      t->aux--;
-	      t->ptr0[i]=t->ptr0[t->aux];
-	      t->ptr1[i]=t->ptr1[t->aux];
-	      t->p[i]=t->p[t->aux];
-	      t->q[i]=t->q[t->aux];
-	      for(k=0;k<t->aux;k++){
-		if(t->ptr0[k]==-t->aux)t->ptr0[k]=-i;
-		if(t->ptr1[k]==-t->aux)t->ptr1[k]=-i;
-	      }
-	      /* hole plugged */
-	      
-	    }else
-	      i++;
-	  }
+	  /* check list of unique decisions */
+	  for(j=0;j<i;j++)
+	    if(_node_eq(t,i,j))break;
 	  
-	  fprintf(stderr,"\rParing/rerouting redundant branches... "
-		  "%ld remaining   ",t->aux);
+	  if(j<i){
+	    /* a redundant entry; find all higher nodes referencing it and
+	       short circuit them to the previously noted unique entry */
+	    changedflag=1;
+	    for(k=0;k<t->aux;k++){
+	      if(t->ptr0[k]==-i)t->ptr0[k]=-j;
+	      if(t->ptr1[k]==-i)t->ptr1[k]=-j;
+	    }
+	    
+	    /* Now, we need to fill in the hole from this redundant
+	       entry in the listing.  Insert the last entry in the list.
+	       Fix the forward pointers to that last entry */
+	    t->aux--;
+	    t->ptr0[i]=t->ptr0[t->aux];
+	    t->ptr1[i]=t->ptr1[t->aux];
+	    t->p[i]=t->p[t->aux];
+	    t->q[i]=t->q[t->aux];
+	    for(k=0;k<t->aux;k++){
+	      if(t->ptr0[k]==-t->aux)t->ptr0[k]=-i;
+	      if(t->ptr1[k]==-t->aux)t->ptr1[k]=-i;
+	    }
+	    /* hole plugged */
+	    
+	  }else
+	    i++;
 	}
-	fprintf(stderr,"\n");
+	
+	fprintf(stderr,"\rParing/rerouting redundant branches... "
+		"%ld remaining   ",t->aux);
       }
+      fprintf(stderr,"\n");
     }
   }
-
+  
   /* run all training points through the decision tree to get a final
      probability count */
   {
@@ -607,11 +538,17 @@ void vqsp_book(vqgen *v, codebook *b, long *quantlist){
     for(i=0;i<c->entries;i++)probability[i]=1; /* trivial guard */
     b->valuelist=v->entrylist; /* temporary for vqenc_entry; replaced later */
 
+    /* sigh.  A necessary hack */
+    for(i=0;i<t->aux;i++)t->p[i]*=c->dim;
+    for(i=0;i<t->aux;i++)t->q[i]*=c->dim;
+    
     for(i=0;i<v->points;i++){
       int ret=codebook_entry(b,v->pointlist+i*v->elements);
       probability[ret]++;
       if(!(i&0xff))spinnit("counting hits... ",v->points-i);
     }
+    for(i=0;i<t->aux;i++)t->p[i]/=c->dim;
+    for(i=0;i<t->aux;i++)t->q[i]/=c->dim;
 
     build_tree_from_lengths(c->entries,probability,c->lengthlist);
     
@@ -632,7 +569,7 @@ void vqsp_book(vqgen *v, codebook *b, long *quantlist){
     /* rearrange storage; ptr0/1 first as it needs a reverse index */
     /* n and c stay unchanged */
     for(i=0;i<c->entries;i++)revindex[index[i]]=i;
-    for(i=t->ptr0[0];i<t->aux;i++){
+    for(i=0;i<t->aux;i++){
       if(!(i&0x3f))spinnit("sorting... ",t->aux-i);
 
       if(t->ptr0[i]>=0)t->ptr0[i]=revindex[t->ptr0[i]];