Lattice codebook implementation should be complete and debugged at this point.

Monty

svn path=/branches/new_acoustics_pending_merge_20000328/vorbis/; revision=346

6 files changed, 360 insertions, 155 deletions

diff --git a/vq/bookutil.c b/vq/bookutil.c
index e479f7fe..bf68ebf9 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.12.4.4 2000/04/26 07:10:15 xiphmont Exp $
+ last mod: $Id: bookutil.c,v 1.12.4.5 2000/04/27 09:22:40 xiphmont Exp $
 
  ********************************************************************/
 
@@ -212,7 +212,7 @@ codebook *codebook_load(char *filename){
   }
   
   /* find the auxiliary encode struct[s] (if any) */
-  if(find_seek_to(in,"static encode_aux_nearestmatch _vq_aux_")){
+  if(find_seek_to(in,"static encode_aux_nearestmatch _vq_aux")){
     /* how big? */
     c->nearest_tree=a=calloc(1,sizeof(encode_aux_nearestmatch));
     line=get_line(in);
@@ -267,7 +267,7 @@ codebook *codebook_load(char *filename){
       }    
   }
   
-  if(find_seek_to(in,"static encode_aux_threshmatch _vq_aux_")){
+  if(find_seek_to(in,"static encode_aux_threshmatch _vq_aux")){
     /* how big? */
     c->thresh_tree=t=calloc(1,sizeof(encode_aux_threshmatch));
     line=get_line(in);
@@ -422,3 +422,155 @@ void build_tree_from_lengths(int vals, long *hist, long *lengths){
 
   free(membership);
 }
+
+void write_codebook(FILE *out,char *name,const static_codebook *c){
+  encode_aux_threshmatch *t=c->thresh_tree;
+  encode_aux_nearestmatch *n=c->nearest_tree;
+  int j,k;
+
+  /* save the book in C header form */
+  fprintf(out,
+ "/********************************************************************\n"
+ " *                                                                  *\n"
+ " * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE.  *\n"
+ " * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *\n"
+ " * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE.    *\n"
+ " * PLEASE READ THESE TERMS DISTRIBUTING.                            *\n"
+ " *                                                                  *\n"
+ " * THE OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-1999             *\n"
+ " * by 1999 Monty <monty@xiph.org> and The XIPHOPHORUS Company       *\n"
+ " * http://www.xiph.org/                                             *\n"
+ " *                                                                  *\n"
+ " ********************************************************************\n"
+ "\n"
+ " function: static codebook autogenerated by vq/somethingorother\n"
+ "\n"
+ " ********************************************************************/\n\n");
+
+  fprintf(out,"#ifndef _V_%s_VQH_\n#define _V_%s_VQH_\n",name,name);
+  fprintf(out,"#include \"vorbis/codebook.h\"\n\n");
+
+  /* first, the static vectors, then the book structure to tie it together. */
+  /* quantlist */
+  if(c->quantlist){
+    fprintf(out,"static long _vq_quantlist_%s[] = {\n",name);
+    for(j=0;j<_book_maptype1_quantvals(c);j++){
+      fprintf(out,"\t%ld,\n",c->quantlist[j]);
+    }
+    fprintf(out,"};\n\n");
+  }
+
+  /* lengthlist */
+  fprintf(out,"static long _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");
+
+  if(t){
+    /* quantthresh */
+    fprintf(out,"static double _vq_quantthresh_%s[] = {\n",name);
+    for(j=0;j<t->threshvals-1;){
+      fprintf(out,"\t");
+      for(k=0;k<8 && j<t->threshvals-1;k++,j++)
+	fprintf(out,"%.5g, ",t->quantthresh[j]);
+      fprintf(out,"\n");
+    }
+    fprintf(out,"};\n\n");
+
+    /* quantmap */
+    fprintf(out,"static long _vq_quantmap_%s[] = {\n",name);
+    for(j=0;j<t->threshvals;){
+      fprintf(out,"\t");
+      for(k=0;k<8 && j<t->threshvals;k++,j++)
+	fprintf(out,"%5ld,",t->quantmap[j]);
+      fprintf(out,"\n");
+    }
+    fprintf(out,"};\n\n");  
+
+    fprintf(out,"static encode_aux_threshmatch _vq_auxt_%s = {\n",name);
+    fprintf(out,"\t_vq_quantthresh_%s,\n",name);
+    fprintf(out,"\t_vq_quantmap_%s,\n",name);
+    fprintf(out,"\t%d,\n",t->quantvals);
+    fprintf(out,"\t%d\n};\n\n",t->threshvals);
+  }
+
+  if(n){
+    
+    /* ptr0 */
+    fprintf(out,"static long _vq_ptr0_%s[] = {\n",name);
+    for(j=0;j<n->aux;){
+      fprintf(out,"\t");
+      for(k=0;k<8 && j<n->aux;k++,j++)
+	fprintf(out,"%6ld,",n->ptr0[j]);
+      fprintf(out,"\n");
+    }
+    fprintf(out,"};\n\n");
+    
+    /* ptr1 */
+    fprintf(out,"static long _vq_ptr1_%s[] = {\n",name);
+    for(j=0;j<n->aux;){
+      fprintf(out,"\t");
+      for(k=0;k<8 && j<n->aux;k++,j++)
+	fprintf(out,"%6ld,",n->ptr1[j]);
+      fprintf(out,"\n");
+    }
+    fprintf(out,"};\n\n");
+    
+    /* p */
+    fprintf(out,"static long _vq_p_%s[] = {\n",name);
+    for(j=0;j<n->aux;){
+      fprintf(out,"\t");
+      for(k=0;k<8 && j<n->aux;k++,j++)
+	fprintf(out,"%6ld,",n->p[j]*c->dim);
+      fprintf(out,"\n");
+    }
+    fprintf(out,"};\n\n");
+    
+    /* q */
+    fprintf(out,"static long _vq_q_%s[] = {\n",name);
+    for(j=0;j<n->aux;){
+      fprintf(out,"\t");
+      for(k=0;k<8 && j<n->aux;k++,j++)
+	fprintf(out,"%6ld,",n->q[j]*c->dim);
+      fprintf(out,"\n");
+    }
+    fprintf(out,"};\n\n");
+  
+    fprintf(out,"static encode_aux_nearestmatch _vq_auxn_%s = {\n",name);
+    fprintf(out,"\t_vq_ptr0_%s,\n",name);
+    fprintf(out,"\t_vq_ptr1_%s,\n",name);
+    fprintf(out,"\t_vq_p_%s,\n",name);
+    fprintf(out,"\t_vq_q_%s,\n",name);
+    fprintf(out,"\t%ld, %ld\n};\n\n",n->aux,n->aux);
+  }
+
+  /* tie it all together */
+  
+  fprintf(out,"static static_codebook _vq_book_%s = {\n",name);
+  
+  fprintf(out,"\t%ld, %ld,\n",c->dim,c->entries);
+  fprintf(out,"\t_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_vq_quantlist_%s,\n",name);
+  else
+    fprintf(out,"\tNULL,\n");
+
+  if(n)
+    fprintf(out,"\t&_vq_auxn_%s\n",name);
+  else
+    fprintf(out,"\tNULL,\n");
+  if(t)
+    fprintf(out,"\t&_vq_auxt_%s\n",name);
+  else
+    fprintf(out,"\tNULL,\n");
+
+  fprintf(out,"};\n\n");
+
+  fprintf(out,"\n#endif\n");
+}
diff --git a/vq/bookutil.h b/vq/bookutil.h
index 4c712270..54789ad9 100644
--- a/vq/bookutil.h
+++ b/vq/bookutil.h
@@ -12,7 +12,7 @@
  ********************************************************************
 
  function: utility functions for loading .vqh and .vqd files
- last mod: $Id: bookutil.h,v 1.4.4.2 2000/04/21 16:35:40 xiphmont Exp $
+ last mod: $Id: bookutil.h,v 1.4.4.3 2000/04/27 09:22:40 xiphmont Exp $
 
  ********************************************************************/
 
@@ -34,6 +34,7 @@ extern int       get_vector(codebook *b,FILE *in,int start,int num,double *a);
 extern char     *find_seek_to(FILE *in,char *s);
 
 extern codebook *codebook_load(char *filename);
+extern void write_codebook(FILE *out,char *name,const static_codebook *c);
 
 extern void spinnit(char *s,int n);
 extern void build_tree_from_lengths(int vals, long *hist, long *lengths);
diff --git a/vq/build.c b/vq/build.c
index 41fd02f8..a71077af 100644
--- a/vq/build.c
+++ b/vq/build.c
@@ -12,7 +12,7 @@
  ********************************************************************
 
  function: utility main for building codebooks from training sets
- last mod: $Id: build.c,v 1.12.4.4 2000/04/21 16:35:40 xiphmont Exp $
+ last mod: $Id: build.c,v 1.12.4.5 2000/04/27 09:22:40 xiphmont Exp $
 
  ********************************************************************/
 
@@ -23,7 +23,7 @@
 #include <errno.h>
 #include "vorbis/codebook.h"
 #include "../lib/sharedbook.h"
-#include "../lib/scales.h"
+#include "bookutil.h"
 
 #include "vqgen.h"
 #include "vqsplit.h"
@@ -184,113 +184,12 @@ int main(int argc,char *argv[]){
   vqgen_unquantize(&v,&q);
 
   /* build the book */
+  c.maptype=2;
   vqsp_book(&v,&b,quantlist);
 
   /* save the book in C header form */
-  fprintf(out,
- "/********************************************************************\n"
- " *                                                                  *\n"
- " * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE.  *\n"
- " * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *\n"
- " * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE.    *\n"
- " * PLEASE READ THESE TERMS DISTRIBUTING.                            *\n"
- " *                                                                  *\n"
- " * THE OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-1999             *\n"
- " * by 1999 Monty <monty@xiph.org> and The XIPHOPHORUS Company       *\n"
- " * http://www.xiph.org/                                             *\n"
- " *                                                                  *\n"
- " ********************************************************************\n"
- "\n"
- " function: static codebook autogenerated by vq/vqbuild\n"
- "\n"
- " ********************************************************************/\n\n");
+  write_codebook(out,name,b.c);
 
-  fprintf(out,"#ifndef _V_%s_VQH_\n#define _V_%s_VQH_\n",name,name);
-  fprintf(out,"#include \"vorbis/codebook.h\"\n\n");
-
-  /* first, the static vectors, then the book structure to tie it together. */
-  /* quantlist */
-  fprintf(out,"static long _vq_quantlist_%s[] = {\n",name);
-  i=0;
-  for(j=0;j<c.entries;j++){
-    fprintf(out,"\t");
-    for(k=0;k<dim;k++)
-      fprintf(out,"%5ld, ",c.quantlist[i++]);
-    fprintf(out,"\n");
-  }
-  fprintf(out,"};\n\n");
-
-  /* lengthlist */
-  fprintf(out,"static long _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");
-
-  /* ptr0 */
-  fprintf(out,"static long _vq_ptr0_%s[] = {\n",name);
-  for(j=0;j<c.nearest_tree->aux;){
-    fprintf(out,"\t");
-    for(k=0;k<8 && j<c.nearest_tree->aux;k++,j++)
-      fprintf(out,"%6ld,",c.nearest_tree->ptr0[j]);
-    fprintf(out,"\n");
-  }
-  fprintf(out,"};\n\n");
-
-  /* ptr1 */
-  fprintf(out,"static long _vq_ptr1_%s[] = {\n",name);
-  for(j=0;j<c.nearest_tree->aux;){
-    fprintf(out,"\t");
-    for(k=0;k<8 && j<c.nearest_tree->aux;k++,j++)
-      fprintf(out,"%6ld,",c.nearest_tree->ptr1[j]);
-    fprintf(out,"\n");
-  }
-  fprintf(out,"};\n\n");
-
-  /* p */
-  fprintf(out,"static long _vq_p_%s[] = {\n",name);
-  for(j=0;j<c.nearest_tree->aux;){
-    fprintf(out,"\t");
-    for(k=0;k<8 && j<c.nearest_tree->aux;k++,j++)
-      fprintf(out,"%6ld,",c.nearest_tree->p[j]*c.dim);
-    fprintf(out,"\n");
-  }
-  fprintf(out,"};\n\n");
-
-  /* q */
-  fprintf(out,"static long _vq_q_%s[] = {\n",name);
-  for(j=0;j<c.nearest_tree->aux;){
-    fprintf(out,"\t");
-    for(k=0;k<8 && j<c.nearest_tree->aux;k++,j++)
-      fprintf(out,"%6ld,",c.nearest_tree->q[j]*c.dim);
-    fprintf(out,"\n");
-  }
-  fprintf(out,"};\n\n");
-
-  /* tie it all together */
-  
-  fprintf(out,"static encode_aux_nearestmatch _vq_aux_%s = {\n",name);
-  fprintf(out,"\t_vq_ptr0_%s,\n",name);
-  fprintf(out,"\t_vq_ptr1_%s,\n",name);
-  fprintf(out,"\t_vq_p_%s,\n",name);
-  fprintf(out,"\t_vq_q_%s,\n",name);
-  fprintf(out,"\t%ld, %ld\n};\n\n",c.nearest_tree->aux,c.nearest_tree->aux);
-  
-  fprintf(out,"static static_codebook _vq_book_%s = {\n",name);
-  
-  fprintf(out,"\t%ld, %ld,\n",c.dim,c.entries);
-  fprintf(out,"\t_vq_lengthlist_%s,\n",name);
-  fprintf(out,"\t2, %ld, %ld, %d, %d,\n",
-	  q.min,q.delta,q.quant,q.sequencep);
-  fprintf(out,"\t_vq_quantlist_%s,\n",name);
-  fprintf(out,"\t&_vq_aux_%s,\n",name);
-  fprintf(out,"\tNULL\n");
-  fprintf(out,"};\n\n");
-
-  fprintf(out,"\n#endif\n");
   fclose(out);
   exit(0);
 }
diff --git a/vq/latticepare.c b/vq/latticepare.c
index 2b9b5086..36e5f46f 100644
--- a/vq/latticepare.c
+++ b/vq/latticepare.c
@@ -12,7 +12,7 @@
  ********************************************************************
 
  function: utility for paring low hit count cells from lattice codebook
- last mod: $Id: latticepare.c,v 1.1.2.1 2000/04/26 07:10:16 xiphmont Exp $
+ last mod: $Id: latticepare.c,v 1.1.2.2 2000/04/27 09:22:40 xiphmont Exp $
 
  ********************************************************************/
 
@@ -24,6 +24,8 @@
 #include "vorbis/codebook.h"
 #include "../lib/sharedbook.h"
 #include "bookutil.h"
+#include "vqgen.h"
+#include "vqsplit.h"
 
 /* Lattice codebooks have two strengths: important fetaures that are
    poorly modelled by global error minimization training (eg, strong
@@ -82,10 +84,10 @@ void add_vector(codebook *b,double *vec,long n){
       if(points>=allocated){
 	if(allocated){
 	  allocated*=2;
-	  pointlist=realloc(pointlist,allocated*dim*sizeof(double));
+	  pointlist=realloc(pointlist,allocated*sizeof(double));
 	}else{
 	  allocated=1024*1024;
-	  pointlist=malloc(allocated*dim*sizeof(double));
+	  pointlist=malloc(allocated*sizeof(double));
 	}
       }
 
@@ -289,6 +291,7 @@ int main(int argc,char *argv[]){
   }
   dim=b->dim;
   entries=b->entries;
+  points/=dim;
 
   if(target==-1){
     fprintf(stderr,"Target number of cells required on command line\n");
@@ -297,6 +300,12 @@ int main(int argc,char *argv[]){
 
   /* set up auxiliary vectors for error tracking */
   {
+    encode_aux_nearestmatch *nt=NULL;
+    long pointssofar=0;
+    long *pointindex;
+    long indexedpoints=0;
+    long *entryindex;
+    long *reventry;
     long *membership=malloc(points*sizeof(long));
     long *cellhead=malloc(entries*sizeof(long));
     double *cellerror1=calloc(entries,sizeof(double)); /* error for
@@ -369,21 +378,106 @@ int main(int argc,char *argv[]){
 
       cellsleft--;
     }
-    free(membership);
+
+    /* paring is over.  Build decision trees using points that now fall
+       through the thresh matcher. */
+    /* we don't free membership; we flatten it in order to use in lp_split */
+
+    for(i=0;i<entries;i++){
+      long head=cellhead[i];
+      while(head!=-1){
+	long next=membership[head];
+	membership[head]=i;
+	head=next;
+      }
+    }
+
     free(cellhead);
     free(cellerror1);
     free(cellerror2);
-  }
 
-  for(i=0;i<entries;i++)
-    fprintf(stderr,"%ld, ",b->c->lengthlist[i]);
+    pointindex=malloc(points*sizeof(long));
+    /* make a point index of fall-through points */
+    for(i=0;i<points;i++){
+      int best=_best(b,pointlist+i*dim,1);
+      if(best==-1)
+	pointindex[indexedpoints++]=i;
+    }
 
-  /* paring is over.  Build decision trees using points that now fall
-     through the thresh matcher */
+    /* make an entry index */
+    entryindex=malloc(entries*sizeof(long));
+    target=0;
+    for(i=0;i<entries;i++){
+      if(b->c->lengthlist[i]>0)
+	entryindex[target++]=i;
+    }
 
+    /* make working space for a reverse entry index */
+    reventry=malloc(entries*sizeof(long));
+
+    /* do the split */
+    nt=b->c->nearest_tree=
+      calloc(1,sizeof(encode_aux_nearestmatch));
+
+    nt->alloc=4096;
+    nt->ptr0=malloc(sizeof(long)*nt->alloc);
+    nt->ptr1=malloc(sizeof(long)*nt->alloc);
+    nt->p=malloc(sizeof(long)*nt->alloc);
+    nt->q=malloc(sizeof(long)*nt->alloc);
+    nt->aux=0;
+
+    fprintf(stderr,"Leaves added: %d              \n",
+            lp_split(pointlist,points,
+                     b,entryindex,target,
+                     pointindex,indexedpoints,
+                     membership,reventry,
+                     0,&pointssofar));
+    free(membership);
+    free(reventry);
+    free(pointindex);
+    
+    /* recount hits.  Build new lengthlist. reuse entryindex storage */
+    for(i=0;i<entries;i++)entryindex[i]=1;
+    for(i=0;i<points;i++){
+      int best=_best(b,pointlist+i*dim,1);
+      if(!(i&0xff))spinnit("counting hits...",i);
+      if(best==-1){
+	fprintf(stderr,"\nINTERNAL ERROR; a point count not be matched to a\n"
+		"codebook entry.  The new decision tree is broken.\n");
+	exit(1);
+      }
+      entryindex[best]++;
+    }
+    
+    /* the lengthlist builder doesn't actually deal with 0 hit entries.
+       So, we pack the 'sparse' hit list into a dense list, then unpack
+       the lengths after the build */
+    {
+      int upper=0;
+      long *lengthlist=calloc(entries,sizeof(long));
+      for(i=0;i<entries;i++)
+	if(b->c->lengthlist[i]>0)
+	  entryindex[upper++]=entryindex[i];
+      
+      /* sanity check */
+      if(upper != target){
+	fprintf(stderr,"\nINTERNAL ERROR; packed the wrong number of entries\n");
+	exit(1);
+      }
+    
 
+      build_tree_from_lengths(upper,entryindex,lengthlist);
+      
+      upper=0;
+      for(i=0;i<entries;i++)
+	if(b->c->lengthlist[i]>0)
+	  b->c->lengthlist[i]=lengthlist[upper++];
+    }
+  }
+  /* we're done.  write it out. */
+  write_codebook(stdout,"foo",b->c);
 
-  fprintf(stderr,"\r                                        \nDone.");
+  fprintf(stderr,"\r                                        \nDone.\n");
   return(0);
 }
 
diff --git a/vq/vqsplit.c b/vq/vqsplit.c
index d5d283b8..308ee86f 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.18.4.4 2000/04/21 16:35:41 xiphmont Exp $
+ last mod: $Id: vqsplit.c,v 1.18.4.5 2000/04/27 09:22:40 xiphmont Exp $
 
  ********************************************************************/
 
@@ -68,23 +68,35 @@ int iascsort(const void *a,const void *b){
   return(av-bv);
 }
 
-/* grab it from vqgen.c */
-extern double _dist(vqgen *v,double *a, double *b);
+static double _Ndist(int el,double *a, double *b){
+  int i;
+  double acc=0.;
+  for(i=0;i<el;i++){
+    double val=(a[i]-b[i]);
+    acc+=val*val;
+  }
+  return sqrt(acc);
+}
+
+#define _Npoint(i) (pointlist+dim*(i))
+#define _Nnow(i) (entrylist+dim*(i))
+
 
 /* goes through the split, but just counts it and returns a metric*/
-int vqsp_count(vqgen *v,long *membership,long *reventry,
-		long *entryindex,long entries, 
+int vqsp_count(double *entrylist,double *pointlist,int dim,
+	       long *membership,long *reventry,
+	       long *entryindex,long entries, 
 	       long *pointindex,long points,int splitp,
-		long *entryA,long *entryB,
-		long besti,long bestj,
-		long *entriesA,long *entriesB,long *entriesC){
+	       long *entryA,long *entryB,
+	       long besti,long bestj,
+	       long *entriesA,long *entriesB,long *entriesC){
   long i,j;
   long A=0,B=0,C=0;
   long pointsA=0;
   long pointsB=0;
   long *temppointsA=NULL;
   long *temppointsB=NULL;
-
+  
   if(splitp){
     temppointsA=malloc(points*sizeof(long));
     temppointsB=malloc(points*sizeof(long));
@@ -97,7 +109,7 @@ int vqsp_count(vqgen *v,long *membership,long *reventry,
      both? */
 
   for(i=0;i<points;i++){
-    double *ppt=_point(v,pointindex[i]);
+    double *ppt=_Npoint(pointindex[i]);
     long   firstentry=membership[pointindex[i]];
 
     if(firstentry==besti){
@@ -111,8 +123,8 @@ int vqsp_count(vqgen *v,long *membership,long *reventry,
       continue;
     }
     {
-      double distA=_dist(v,ppt,_now(v,besti));
-      double distB=_dist(v,ppt,_now(v,bestj));
+      double distA=_Ndist(dim,ppt,_Nnow(besti));
+      double distB=_Ndist(dim,ppt,_Nnow(bestj));
       if(distA<distB){
 	entryA[reventry[firstentry]]=1;
 	if(splitp)temppointsA[pointsA++]=pointindex[i];
@@ -144,7 +156,8 @@ int vqsp_count(vqgen *v,long *membership,long *reventry,
   return(pointsA);
 }
 
-int lp_split(vqgen *v,codebook *b,
+int lp_split(double *pointlist,long totalpoints,
+	     codebook *b,
 	     long *entryindex,long entries, 
 	     long *pointindex,long points,
 	     long *membership,long *reventry,
@@ -158,6 +171,8 @@ int lp_split(vqgen *v,codebook *b,
      codebook set spacing and distribution using special metrics and
      even a midpoint division won't disturb the basic properties) */
 
+  int dim=b->dim;
+  double *entrylist=b->valuelist;
   long ret;
   long *entryA=calloc(entries,sizeof(long));
   long *entryB=calloc(entries,sizeof(long));
@@ -169,12 +184,12 @@ int lp_split(vqgen *v,codebook *b,
 
   long   besti=-1;
   long   bestj=-1;
-
+  
   char spinbuf[80];
-  sprintf(spinbuf,"splitting [%ld left]... ",v->points-*pointsofar);
+  sprintf(spinbuf,"splitting [%ld left]... ",totalpoints-*pointsofar);
 
   /* one reverse index needed */
-  for(i=0;i<v->entries;i++)reventry[i]=-1;
+  for(i=0;i<b->entries;i++)reventry[i]=-1;
   for(i=0;i<entries;i++)reventry[entryindex[i]]=i;
 
   /* We need to find the dividing hyperplane. find the median of each
@@ -190,7 +205,8 @@ int lp_split(vqgen *v,codebook *b,
     for(i=0;i<entries-1;i++){
       for(j=i+1;j<entries;j++){
 	spinnit(spinbuf,entries-i);
-	vqsp_count(v,membership,reventry,
+	vqsp_count(b->valuelist,pointlist,dim,
+		   membership,reventry,
 		   entryindex,entries, 
 		   pointindex,points,0,
 		   entryA,entryB,
@@ -214,20 +230,20 @@ int lp_split(vqgen *v,codebook *b,
       }
     }
   }else{
-    double *p=alloca(v->elements*sizeof(double));
-    double *q=alloca(v->elements*sizeof(double));
+    double *p=alloca(dim*sizeof(double));
+    double *q=alloca(dim*sizeof(double));
     double best=0.;
     
     /* try COG/normal and furthest pairs */
     /* meanpoint */
     /* eventually, we want to select the closest entry and figure n/c
        from p/q (because storing n/c is too large */
-    for(k=0;k<v->elements;k++){
+    for(k=0;k<dim;k++){
       spinnit(spinbuf,entries);
       
       p[k]=0.;
       for(j=0;j<entries;j++)
-	p[k]+=v->entrylist[entryindex[j]*v->elements+k];
+	p[k]+=b->valuelist[entryindex[j]*dim+k];
       p[k]/=entries;
 
     }
@@ -237,18 +253,18 @@ int lp_split(vqgen *v,codebook *b,
        center */
 
     for(i=0;i<entries;i++){
-      double *ppi=_now(v,entryindex[i]);
+      double *ppi=_Nnow(entryindex[i]);
       double ref_best=0.;
       double ref_j=-1;
       double this;
       spinnit(spinbuf,entries-i);
       
-      for(k=0;k<v->elements;k++)
+      for(k=0;k<dim;k++)
 	q[k]=2*p[k]-ppi[k];
 
       for(j=0;j<entries;j++){
 	if(j!=i){
-	  double this=_dist(v,q,_now(v,entryindex[j]));
+	  double this=_Ndist(dim,q,_Nnow(entryindex[j]));
 	  if(ref_j==-1 || this<=ref_best){ /* <=, not <; very important */
 	    ref_best=this;
 	    ref_j=entryindex[j];
@@ -256,7 +272,8 @@ int lp_split(vqgen *v,codebook *b,
 	}
       }
 
-      vqsp_count(v,membership,reventry,
+      vqsp_count(b->valuelist,pointlist,dim,
+		 membership,reventry,
 		 entryindex,entries, 
 		 pointindex,points,0,
 		 entryA,entryB,
@@ -289,7 +306,8 @@ int lp_split(vqgen *v,codebook *b,
   /* find cells enclosing points */
   /* count A/B points */
 
-  pointsA=vqsp_count(v,membership,reventry,
+  pointsA=vqsp_count(b->valuelist,pointlist,dim,
+		     membership,reventry,
 		     entryindex,entries, 
 		     pointindex,points,1,
 		     entryA,entryB,
@@ -317,7 +335,7 @@ int lp_split(vqgen *v,codebook *b,
       *pointsofar+=pointsA;
     }else{
       t->ptr0[thisaux]= -t->aux;
-      ret=lp_split(v,b,entryA,entriesA,pointindex,pointsA,
+      ret=lp_split(pointlist,totalpoints,b,entryA,entriesA,pointindex,pointsA,
 		   membership,reventry,depth+1,pointsofar); 
     }
     if(entriesB==1){
@@ -326,7 +344,7 @@ int lp_split(vqgen *v,codebook *b,
       *pointsofar+=points-pointsA;
     }else{
       t->ptr1[thisaux]= -t->aux;
-      ret+=lp_split(v,b,entryB,entriesB,pointindex+pointsA,
+      ret+=lp_split(pointlist,totalpoints,b,entryB,entriesB,pointindex+pointsA,
 		    points-pointsA,membership,reventry,
 		    depth+1,pointsofar); 
     }
@@ -368,7 +386,7 @@ void vqsp_book(vqgen *v, codebook *b, long *quantlist){
   for(i=0;i<v->entries;){
     /* duplicate? if so, eliminate */
     for(j=0;j<i;j++){
-      if(_dist(v,_now(v,i),_now(v,j))==0.){
+      if(_Ndist(v->elements,_now(v,i),_now(v,j))==0.){
 	fprintf(stderr,"found a duplicate entry!  removing...\n");
 	v->entries--;
 	memcpy(_now(v,i),_now(v,v->entries),sizeof(double)*v->elements);
@@ -384,13 +402,13 @@ void vqsp_book(vqgen *v, codebook *b, long *quantlist){
     v->assigned=calloc(v->entries,sizeof(long));
     for(i=0;i<v->points;i++){
       double *ppt=_point(v,i);
-      double firstmetric=_dist(v,_now(v,0),ppt);
+      double firstmetric=_Ndist(v->elements,_now(v,0),ppt);
       long   firstentry=0;
 
       if(!(i&0xff))spinnit("checking... ",v->points-i);
 
       for(j=0;j<v->entries;j++){
-	double thismetric=_dist(v,_now(v,j),ppt);
+	double thismetric=_Ndist(v->elements,_now(v,j),ppt);
 	if(thismetric<firstmetric){
 	  firstmetric=thismetric;
 	  firstentry=j;
@@ -435,18 +453,21 @@ void vqsp_book(vqgen *v, codebook *b, long *quantlist){
     c->dim=v->elements;
     c->entries=v->entries;
     c->lengthlist=calloc(c->entries,sizeof(long));
-    
+    b->valuelist=v->entrylist; /* temporary; replaced later */
+    b->dim=c->dim;
+    b->entries=c->entries;
+
     for(i=0;i<v->points;i++)membership[i]=-1;
     for(i=0;i<v->points;i++){
       double *ppt=_point(v,i);
       long   firstentry=0;
-      double firstmetric=_dist(v,_now(v,0),ppt);
+      double firstmetric=_Ndist(v->elements,_now(v,0),ppt);
     
       if(!(i&0xff))spinnit("assigning... ",v->points-i);
 
       for(j=1;j<v->entries;j++){
 	if(v->assigned[j]!=-1){
-	  double thismetric=_dist(v,_now(v,j),ppt);
+	  double thismetric=_Ndist(v->elements,_now(v,j),ppt);
 	  if(thismetric<=firstmetric){
 	    firstmetric=thismetric;
 	    firstentry=j;
@@ -458,7 +479,8 @@ void vqsp_book(vqgen *v, codebook *b, long *quantlist){
     }
 
     fprintf(stderr,"Leaves added: %d              \n",
-	    lp_split(v,b,entryindex,v->entries,
+	    lp_split(v->pointlist,v->points,
+		     b,entryindex,v->entries,
 		     pointindex,v->points,
 		     membership,reventry,
 		     0,&pointssofar));
@@ -525,7 +547,6 @@ void vqsp_book(vqgen *v, codebook *b, long *quantlist){
   {
     long *probability=malloc(c->entries*sizeof(long));
     for(i=0;i<c->entries;i++)probability[i]=1; /* trivial guard */
-    b->valuelist=v->entrylist; /* temporary for vqenc_entry; replaced later */
     b->dim=c->dim;
 
     /* sigh.  A necessary hack */
diff --git a/vq/vqsplit.h b/vq/vqsplit.h
new file mode 100644
index 00000000..60344d24
--- /dev/null
+++ b/vq/vqsplit.h
@@ -0,0 +1,38 @@
+/********************************************************************
+ *                                                                  *
+ * 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.                            *
+ *                                                                  *
+ * THE OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-2000             *
+ * by Monty <monty@xiph.org> and The XIPHOPHORUS Company            *
+ * http://www.xiph.org/                                             *
+ *                                                                  *
+ ********************************************************************
+
+ function: build a VQ codebook decision tree 
+ last mod: $Id: vqsplit.h,v 1.1.4.1 2000/04/27 09:22:40 xiphmont Exp $
+
+ ********************************************************************/
+
+#ifndef _VQSPL_H_
+#define _VQSPL_H_
+
+#include "vorbis/codebook.h"
+
+extern void vqsp_book(vqgen *v,codebook *b,long *quantlist);
+extern int vqenc_entry(codebook *b,double *val);
+extern int lp_split(double *pointlist,long totalpoints,
+		    codebook *b,
+		    long *entryindex,long entries, 
+		    long *pointindex,long points,
+		    long *membership,long *reventry,
+		    long depth, long *pointsofar);
+
+#endif
+
+
+
+
+