trainer fixes and a working vq/ Makefile for Greg

Monty

svn path=/branches/branch_beta3/vorbis/; revision=861

6 files changed, 1748 insertions, 0 deletions

diff --git a/vq/Makefile b/vq/Makefile
new file mode 100644
index 00000000..b2de889e
--- /dev/null
+++ b/vq/Makefile
@@ -0,0 +1,90 @@
+# $Id: Makefile,v 1.1.2.1 2000/10/31 08:25:17 xiphmont Exp $
+
+###############################################################################
+#                                                                             #
+# These are vq codebook generation tools for use by team members.  This       #
+# makefile assumes gcc.                                                       #
+#                                                                             #
+# One need not build these utils to make libvorbis                            #
+#                                                                             #
+###############################################################################
+
+FLAGS=-I. -I../include 
+OPT=-O20 $(FLAGS)
+DEBUG=-g -Wall $(FLAGS)
+PROFILE=-g -pg -O20 $(FLAGS)
+CC=gcc
+LD=gcc
+LDFLAGS=$(FLAGS)
+LIBS=-lm 
+
+HFILES =	../include/vorbis/codebook.h vqgen.h vqext.h bookutil.h
+
+OFILES = 	vqgen.o vqsplit.o bookutil.o ../lib/sharedbook.o
+ALLOFILES = 	$(OFILES) lspdata.o genericdata.o train.o build.o run.o\
+		cascade.o partition.o metrics.o residuedata.o latticebuild.o\
+		latticepare.o latticehint.o latticetune.o
+
+all:
+	$(MAKE) target CFLAGS="$(OPT)"
+
+debug:	
+	$(MAKE) target CFLAGS="$(DEBUG)"
+
+profile: 
+	$(MAKE) target CFLAGS="$(PROFILE)"
+
+target:	lspvqtrain genericvqtrain residuevqtrain vqbuild vqcascade vqmetrics latticebuild latticepare latticehint latticetune huffbuild residuesplit
+
+lspvqtrain:	$(OFILES) lspdata.o train.o
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@ $(LIBS)
+
+residuevqtrain:	$(OFILES) residuedata.o train.o
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@ $(LIBS)
+
+genericvqtrain:	$(OFILES) genericdata.o train.o
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@ $(LIBS)
+
+vqbuild:	$(OFILES) build.o
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@ $(LIBS)
+
+vqcascade:	$(OFILES) run.o cascade.o
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@ $(LIBS)
+
+vqmetrics:	$(OFILES) run.o metrics.o
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@ $(LIBS)
+
+latticebuild:	$(OFILES) latticebuild.o
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@ $(LIBS)
+
+latticehint:	$(OFILES) latticehint.o
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@ $(LIBS)
+
+latticepare:	$(OFILES) latticepare.o
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@ $(LIBS)
+
+latticetune:	$(OFILES) latticetune.o
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@ $(LIBS)
+
+huffbuild:	$(OFILES) huffbuild.o
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@ $(LIBS)
+
+residuesplit:	$(OFILES) residuesplit.o
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@ $(LIBS)
+
+
+$(ALLOFILES): 	$(HFILES)
+
+.c.o:
+	$(CC) $(CFLAGS) -c $<
+
+$(OFILES):	$(HFILES)
+
+clean:
+	-rm -f *.o *.a test* *~ *.out *.m config.* \
+		lspvqtrain genericvqtrain residuevqtrain\
+		vqbuild vqmetrics latticebuild vqcascade latticepare\
+		huffbuild residuesplit
+
+distclean:	clean
+	-rm -f Makefile
diff --git a/vq/bookutil.c b/vq/bookutil.c
new file mode 100644
index 00000000..a157e07c
--- /dev/null
+++ b/vq/bookutil.c
@@ -0,0 +1,742 @@
+/********************************************************************
+ *                                                                  *
+ * 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: utility functions for loading .vqh and .vqd files
+ last mod: $Id: bookutil.c,v 1.17.2.1 2000/10/31 08:25:17 xiphmont Exp $
+
+ ********************************************************************/
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <math.h>
+#include <string.h>
+#include <errno.h>
+#include "vorbis/codebook.h"
+#include "../lib/sharedbook.h"
+#include "bookutil.h"
+
+/* A few little utils for reading files */
+/* read a line.  Use global, persistent buffering */
+static char *linebuffer=NULL;
+static int  lbufsize=0;
+char *get_line(FILE *in){
+  long sofar=0;
+  if(feof(in))return NULL;
+
+  while(1){
+    int gotline=0;
+
+    while(!gotline){
+      if(sofar+1>=lbufsize){
+        if(!lbufsize){  
+          lbufsize=1024;
+          linebuffer=malloc(lbufsize);
+        }else{
+          lbufsize*=2;
+          linebuffer=realloc(linebuffer,lbufsize);
+        }
+      }
+      {
+        long c=fgetc(in);
+        switch(c){
+        case EOF:
+	  if(sofar==0)return(NULL);
+	  /* fallthrough correct */
+        case '\n':
+          linebuffer[sofar]='\0';
+          gotline=1;
+          break;
+        default:
+          linebuffer[sofar++]=c;
+          linebuffer[sofar]='\0';
+          break;
+        }
+      }
+    }
+    
+    if(linebuffer[0]=='#'){
+      sofar=0;
+    }else{
+      return(linebuffer);
+    }
+  }
+}
+
+/* read the next numerical value from the given file */
+static char *value_line_buff=NULL;
+
+int get_line_value(FILE *in,float *value){
+  char *next;
+
+  if(!value_line_buff)return(-1);
+
+  *value=strtod(value_line_buff, &next);
+  if(next==value_line_buff){
+    value_line_buff=NULL;
+    return(-1);
+  }else{
+    value_line_buff=next;
+    while(*value_line_buff>44)value_line_buff++;
+    if(*value_line_buff==44)value_line_buff++;
+    return(0);
+  }
+}
+
+int get_next_value(FILE *in,float *value){
+  while(1){
+    if(get_line_value(in,value)){
+      value_line_buff=get_line(in);
+      if(!value_line_buff)return(-1);
+    }else{
+      return(0);
+    }
+  }
+}
+
+int get_next_ivalue(FILE *in,long *ivalue){
+  float value;
+  int ret=get_next_value(in,&value);
+  *ivalue=value;
+  return(ret);
+}
+
+static float sequence_base=0.;
+static int v_sofar=0;
+void reset_next_value(void){
+  value_line_buff=NULL;
+  sequence_base=0.;
+  v_sofar=0;
+}
+
+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;
+
+  while(1){
+
+    if(v_sofar==n || get_line_value(in,a)){
+      reset_next_value();
+      if(get_next_value(in,a))
+	break;
+      for(i=0;i<start;i++){
+	sequence_base=*a;
+	get_line_value(in,a);
+      }
+    }
+
+    for(i=1;i<c->dim;i++)
+      if(get_line_value(in,a+i))
+	break;
+    
+    if(i==c->dim){
+      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.;
+  }
+
+  return(-1);
+}
+
+/* read lines fromt he beginning until we find one containing the
+   specified string */
+char *find_seek_to(FILE *in,char *s){
+  rewind(in);
+  while(1){
+    char *line=get_line(in);
+    if(line){
+      if(strstr(line,s))
+	return(line);
+    }else
+      return(NULL);
+  }
+}
+
+
+/* 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_nearestmatch *a=NULL;
+  encode_aux_threshmatch *t=NULL;
+  encode_aux_pigeonhole *p=NULL;
+  int quant_to_read=0;
+  FILE *in=fopen(filename,"r");
+  char *line;
+  long i;
+
+  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_");
+
+  /* get the major important values */
+  line=get_line(in);
+  if(sscanf(line,"%ld, %ld,",
+	    &(c->dim),&(c->entries))!=2){
+    fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);
+    exit(1);
+  }
+  line=get_line(in);
+  line=get_line(in);
+  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);
+  }
+  
+  /* find the auxiliary encode struct[s] (if any) */
+  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);
+    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);
+      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);
+      }    
+  }
+  
+  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);
+    line=get_line(in);
+    line=get_line(in);
+    if(sscanf(line,"%d",&(t->quantvals))!=1){
+      fprintf(stderr,"3: syntax in %s in line:\t %s",filename,line);
+      exit(1);
+    }
+    line=get_line(in);
+    if(sscanf(line,"%d",&(t->threshvals))!=1){
+      fprintf(stderr,"4: syntax in %s in line:\t %s",filename,line);
+      exit(1);
+    }
+    /* load quantthresh */
+    find_seek_to(in,"static float _vq_quantthresh_");
+    reset_next_value();
+    t->quantthresh=malloc(sizeof(float)*t->threshvals);
+    for(i=0;i<t->threshvals-1;i++)
+      if(get_next_value(in,t->quantthresh+i)){
+	fprintf(stderr,"out of data 1 while reading codebook %s\n",filename);
+	exit(1);
+      }    
+    /* load quantmap */
+    find_seek_to(in,"static long _vq_quantmap_");
+    reset_next_value();
+    t->quantmap=malloc(sizeof(long)*t->threshvals);
+    for(i=0;i<t->threshvals;i++)
+      if(get_next_ivalue(in,t->quantmap+i)){
+	fprintf(stderr,"out of data 2 while reading codebook %s\n",filename);
+	exit(1);
+      }    
+  }
+    
+  if(find_seek_to(in,"static encode_aux_pigeonhole _vq_aux")){
+    int pigeons=1,i;
+    /* how big? */
+    c->pigeon_tree=p=calloc(1,sizeof(encode_aux_pigeonhole));
+    line=get_line(in);
+    if(sscanf(line,"%f, %f, %d, %d",&(p->min),&(p->del),
+	      &(p->mapentries),&(p->quantvals))!=4){
+      fprintf(stderr,"5: syntax in %s in line:\t %s",filename,line);
+      exit(1);
+    }
+    line=get_line(in);
+    line=get_line(in);
+    if(sscanf(line,"%ld",&(p->fittotal))!=1){
+      fprintf(stderr,"6: syntax in %s in line:\t %s",filename,line);
+      exit(1);
+    }
+    /* load pigeonmap */
+    find_seek_to(in,"static long _vq_pigeonmap_");
+    reset_next_value();
+    p->pigeonmap=malloc(sizeof(long)*p->mapentries);
+    for(i=0;i<p->mapentries;i++)
+      if(get_next_ivalue(in,p->pigeonmap+i)){
+	fprintf(stderr,"out of data (pigeonmap) while reading codebook %s\n",filename);
+	exit(1);
+      }    
+    /* load fitlist */
+    find_seek_to(in,"static long _vq_fitlist_");
+    reset_next_value();
+    p->fitlist=malloc(sizeof(long)*p->fittotal);
+    for(i=0;i<p->fittotal;i++)
+      if(get_next_ivalue(in,p->fitlist+i)){
+	fprintf(stderr,"out of data (fitlist) while reading codebook %s\n",filename);
+	exit(1);
+      }    
+    /* load fitmap */
+    find_seek_to(in,"static long _vq_fitmap_");
+    reset_next_value();
+    for(i=0;i<c->dim;i++)pigeons*=p->quantvals;
+    p->fitmap=malloc(sizeof(long)*pigeons);
+    for(i=0;i<pigeons;i++)
+      if(get_next_ivalue(in,p->fitmap+i)){
+	fprintf(stderr,"out of data (fitmap) while reading codebook %s\n",filename);
+	exit(1);
+      }    
+ 
+    /* load fitlength */
+    find_seek_to(in,"static long _vq_fitlength_");
+    reset_next_value();
+    p->fitlength=malloc(sizeof(long)*pigeons);
+    for(i=0;i<pigeons;i++)
+      if(get_next_ivalue(in,p->fitlength+i)){
+	fprintf(stderr,"out of data (fitlength) while reading codebook %s\n",filename);
+	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_");
+  reset_next_value();
+  c->quantlist=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");
+  reset_next_value();
+  c->lengthlist=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);
+    }
+
+  /* got it all */
+  fclose(in);
+  
+  vorbis_book_init_encode(b,c);
+
+  return(b);
+}
+
+void spinnit(char *s,int n){
+  static int p=0;
+  static long lasttime=0;
+  long test;
+  struct timeval thistime;
+
+  gettimeofday(&thistime,NULL);
+  test=thistime.tv_sec*10+thistime.tv_usec/100000;
+  if(lasttime!=test){
+    lasttime=test;
+
+    fprintf(stderr,"%s%d ",s,n);
+
+    p++;if(p>3)p=0;
+    switch(p){
+    case 0:
+      fprintf(stderr,"|    \r");
+      break;
+    case 1:
+      fprintf(stderr,"/    \r");
+      break;
+    case 2:
+      fprintf(stderr,"-    \r");
+      break;
+    case 3:
+      fprintf(stderr,"\\    \r");
+      break;
+    }
+    fflush(stderr);
+  }
+}
+
+void build_tree_from_lengths(int vals, long *hist, long *lengths){
+  int i,j;
+  long *membership=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 */
+  /* much more elegant means exist.  Brute force n^2, minimum thought */
+  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];
+      }
+    least=-1;
+    for(j=0;j<vals;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");
+      exit(1);
+    }
+    
+    /* join them */
+    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]++;
+      }
+  }
+  for(i=0;i<vals-1;i++)
+    if(membership[i]!=membership[i+1]){
+      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=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){
+  encode_aux_pigeonhole *p=c->pigeon_tree;
+  encode_aux_threshmatch *t=c->thresh_tree;
+  encode_aux_nearestmatch *n=c->nearest_tree;
+  int i,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){
+    long vals=(c->maptype==1?_book_maptype1_quantvals(c):c->entries*c->dim);
+    fprintf(out,"static 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 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 float _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(p){
+    int pigeons=1;
+    for(i=0;i<c->dim;i++)pigeons*=p->quantvals;
+
+    /* pigeonmap */
+    fprintf(out,"static long _vq_pigeonmap_%s[] = {\n",name);
+    for(j=0;j<p->mapentries;){
+      fprintf(out,"\t");
+      for(k=0;k<8 && j<p->mapentries;k++,j++)
+	fprintf(out,"%5ld, ",p->pigeonmap[j]);
+      fprintf(out,"\n");
+    }
+    fprintf(out,"};\n\n");
+    /* fitlist */
+    fprintf(out,"static long _vq_fitlist_%s[] = {\n",name);
+    for(j=0;j<p->fittotal;){
+      fprintf(out,"\t");
+      for(k=0;k<8 && j<p->fittotal;k++,j++)
+	fprintf(out,"%5ld, ",p->fitlist[j]);
+      fprintf(out,"\n");
+    }
+    fprintf(out,"};\n\n");
+    /* fitmap */
+    fprintf(out,"static long _vq_fitmap_%s[] = {\n",name);
+    for(j=0;j<pigeons;){
+      fprintf(out,"\t");
+      for(k=0;k<8 && j<pigeons;k++,j++)
+	fprintf(out,"%5ld, ",p->fitmap[j]);
+      fprintf(out,"\n");
+    }
+    fprintf(out,"};\n\n");
+    /* fitlength */
+    fprintf(out,"static long _vq_fitlength_%s[] = {\n",name);
+    for(j=0;j<pigeons;){
+      fprintf(out,"\t");
+      for(k=0;k<8 && j<pigeons;k++,j++)
+	fprintf(out,"%5ld, ",p->fitlength[j]);
+      fprintf(out,"\n");
+    }
+    fprintf(out,"};\n\n");
+
+    fprintf(out,"static encode_aux_pigeonhole _vq_auxp_%s = {\n",name);
+    fprintf(out,"\t%g, %g, %d, %d,\n",
+	    p->min,p->del,p->mapentries,p->quantvals);
+
+    fprintf(out,"\t_vq_pigeonmap_%s,\n",name);
+
+    fprintf(out,"\t%ld,\n",p->fittotal);
+    fprintf(out,"\t_vq_fitlist_%s,\n",name);
+    fprintf(out,"\t_vq_fitmap_%s,\n",name);
+    fprintf(out,"\t_vq_fitlength_%s\n};\n\n",name);
+  }
+
+  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");
+  if(p)
+    fprintf(out,"\t&_vq_auxp_%s,\n",name);
+  else
+    fprintf(out,"\tNULL,\n");
+
+  fprintf(out,"};\n\n");
+
+  fprintf(out,"\n#endif\n");
+}
diff --git a/vq/build.c b/vq/build.c
new file mode 100644
index 00000000..4c96bcd8
--- /dev/null
+++ b/vq/build.c
@@ -0,0 +1,198 @@
+/********************************************************************
+ *                                                                  *
+ * 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: utility main for building codebooks from training sets
+ last mod: $Id: build.c,v 1.15.2.1 2000/10/31 08:25:17 xiphmont Exp $
+
+ ********************************************************************/
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <math.h>
+#include <string.h>
+#include <errno.h>
+#include "vorbis/codebook.h"
+#include "../lib/sharedbook.h"
+#include "bookutil.h"
+
+#include "vqgen.h"
+#include "vqsplit.h"
+
+static char *linebuffer=NULL;
+static int  lbufsize=0;
+static char *rline(FILE *in,FILE *out){
+  long sofar=0;
+  if(feof(in))return NULL;
+
+  while(1){
+    int gotline=0;
+
+    while(!gotline){
+      if(sofar>=lbufsize){
+	if(!lbufsize){	
+	  lbufsize=1024;
+	  linebuffer=malloc(lbufsize);
+	}else{
+	  lbufsize*=2;
+	  linebuffer=realloc(linebuffer,lbufsize);
+	}
+      }
+      {
+	long c=fgetc(in);
+	switch(c){
+	case '\n':
+	case EOF:
+	  gotline=1;
+	  break;
+	default:
+	  linebuffer[sofar++]=c;
+	  linebuffer[sofar]='\0';
+	  break;
+	}
+      }
+    }
+    
+    if(linebuffer[0]=='#'){
+      sofar=0;
+    }else{
+      return(linebuffer);
+    }
+  }
+}
+
+/* command line:
+   buildvq file
+*/
+
+int main(int argc,char *argv[]){
+  vqgen v;
+  static_codebook c;
+  codebook b;
+  quant_meta q;
+
+  long *quantlist=NULL;
+  int entries=-1,dim=-1,aux=-1;
+  FILE *out=NULL;
+  FILE *in=NULL;
+  char *line,*name;
+  long i,j,k;
+
+  b.c=&c;
+
+  if(argv[1]==NULL){
+    fprintf(stderr,"Need a trained data set on the command line.\n");
+    exit(1);
+  }
+
+  {
+    char *ptr;
+    char *filename=strdup(argv[1]);
+
+    in=fopen(filename,"r");
+    if(!in){
+      fprintf(stderr,"Could not open input file %s\n",filename);
+      exit(1);
+    }
+    
+    ptr=strrchr(filename,'-');
+    if(ptr){
+      *ptr='\0';
+      name=strdup(filename);
+      sprintf(ptr,".vqh");
+    }else{
+      name=strdup(filename);
+      strcat(filename,".vqh");
+    }
+
+    out=fopen(filename,"w");
+    if(out==NULL){
+      fprintf(stderr,"Unable to open %s for writing\n",filename);
+      exit(1);
+    }
+  }
+
+  /* suck in the trained book */
+
+  /* read book type, but it doesn't matter */
+  line=rline(in,out);
+  
+  line=rline(in,out);
+  if(sscanf(line,"%d %d %d",&entries,&dim,&aux)!=3){
+    fprintf(stderr,"Syntax error reading book file\n");
+    exit(1);
+  }
+  
+  /* just use it to allocate mem */
+  vqgen_init(&v,dim,0,entries,0.,NULL,NULL,0);
+  
+  /* quant */
+  line=rline(in,out);
+  if(sscanf(line,"%ld %ld %d %d",&q.min,&q.delta,
+	    &q.quant,&q.sequencep)!=4){
+    fprintf(stderr,"Syntax error reading book file\n");
+    exit(1);
+  }
+  
+  /* quantized entries */
+  /* save quant data; we don't want to requantize later as our method
+     is currently imperfect wrt repeated application */
+  i=0;
+  quantlist=malloc(sizeof(long)*v.elements*v.entries);
+  for(j=0;j<entries;j++){
+    float a;
+    for(k=0;k<dim;k++){
+      line=rline(in,out);
+      sscanf(line,"%f",&a);
+      v.entrylist[i]=a;
+      quantlist[i++]=rint(a);
+    }
+  }    
+  
+  /* ignore bias */
+  for(j=0;j<entries;j++)line=rline(in,out);
+  free(v.bias);
+  v.bias=NULL;
+  
+  /* training points */
+  {
+    float *b=alloca(sizeof(float)*(dim+aux));
+    i=0;
+    v.entries=0; /* hack to avoid reseeding */
+    while(1){
+      for(k=0;k<dim+aux;k++){
+	line=rline(in,out);
+	if(!line)break;
+	sscanf(line,"%f",b+k);
+      }
+      if(feof(in))break;
+      vqgen_addpoint(&v,b,NULL);
+    }
+    v.entries=entries;
+  }
+  
+  fclose(in);
+  vqgen_unquantize(&v,&q);
+
+  /* build the book */
+  vqsp_book(&v,&b,quantlist);
+  c.q_min=q.min;
+  c.q_delta=q.delta;
+  c.q_quant=q.quant;
+  c.q_sequencep=q.sequencep;
+
+  /* save the book in C header form */
+  write_codebook(out,name,b.c);
+
+  fclose(out);
+  exit(0);
+}
diff --git a/vq/huffbuild.c b/vq/huffbuild.c
new file mode 100644
index 00000000..1de087eb
--- /dev/null
+++ b/vq/huffbuild.c
@@ -0,0 +1,195 @@
+/********************************************************************
+ *                                                                  *
+ * 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: hufftree builder
+ last mod: $Id: huffbuild.c,v 1.5.2.1 2000/10/31 08:25:17 xiphmont Exp $
+
+ ********************************************************************/
+
+#include <stdlib.h>
+#include <string.h>
+#include <math.h>
+#include <stdio.h>
+#include "bookutil.h"
+
+static int nsofar=0;
+static int getval(FILE *in,int begin,int n,int group,int max){
+  float v;
+  int i;
+  long val=0;
+
+  if(nsofar>=n || get_line_value(in,&v)){
+    reset_next_value();
+    nsofar=0;
+    if(get_next_value(in,&v))
+      return(-1);
+    for(i=1;i<=begin;i++)
+      get_line_value(in,&v);
+  }
+
+  val=(int)v;
+  nsofar++;
+
+  for(i=1;i<group;i++,nsofar++)
+    if(nsofar>=n || get_line_value(in,&v))
+      return(getval(in,begin,n,group,max));
+    else
+      val = val*max+(int)v;
+  return(val);
+}
+
+static void usage(){
+  fprintf(stderr,
+	  "usage:\n" 
+	  "huffbuild <input>.vqd <begin,n,group> [noguard]\n"
+	  "   where begin,n,group is first scalar, \n"
+	  "                          number of scalars of each in line,\n"
+	  "                          number of scalars in a group\n"
+	  "eg: huffbuild reslongaux.vqd 0,1024,4\n"
+	  "produces reslongaux.vqh\n\n");
+  exit(1);
+}
+
+int main(int argc, char *argv[]){
+  char *base;
+  char *infile;
+  int i,j,k,begin,n,subn,guard=1;
+  FILE *file;
+  int maxval=0;
+
+  if(argc<3)usage();
+  if(argc==4)guard=0;
+
+  infile=strdup(argv[1]);
+  base=strdup(infile);
+  if(strrchr(base,'.'))
+    strrchr(base,'.')[0]='\0';
+
+  {
+    char *pos=strchr(argv[2],',');
+    begin=atoi(argv[2]);
+    if(!pos)
+      usage();
+    else
+      n=atoi(pos+1);
+    pos=strchr(pos+1,',');
+    if(!pos)
+      usage();
+    else
+      subn=atoi(pos+1);
+    if(n/subn*subn != n){
+      fprintf(stderr,"n must be divisible by group\n");
+      exit(1);
+    }
+  }
+
+  /* scan the file for maximum value */
+  file=fopen(infile,"r");
+  if(!file){
+    fprintf(stderr,"Could not open file %s\n",infile);
+    exit(1);
+  }
+  i=0;
+  while(1){
+    long v;
+    if(get_next_ivalue(file,&v))break;
+    if(v>maxval)maxval=v;
+
+    if(!(i++&0xff))spinnit("loading... ",i);
+  }
+  rewind(file);
+  maxval++;
+
+  {
+    long vals=pow(maxval,subn);
+    long *hist=malloc(vals*sizeof(long));
+    long *lengths=malloc(vals*sizeof(long));
+    
+    for(j=0;j<vals;j++)hist[j]=guard;
+    
+    reset_next_value();
+    i/=subn;
+    while(!feof(file)){
+      long val=getval(file,begin,n,subn,maxval);
+      if(val==-1)break;
+      hist[val]++;
+      if(!(i--&0xff))spinnit("loading... ",i*subn);
+    }
+    fclose(file);
+ 
+    /* we have the probabilities, build the tree */
+    fprintf(stderr,"Building tree for %ld entries\n",vals);
+    build_tree_from_lengths0(vals,hist,lengths);
+
+    /* save the book */
+    {
+      char *buffer=alloca(strlen(base)+5);
+      strcpy(buffer,base);
+      strcat(buffer,".vqh");
+      file=fopen(buffer,"w");
+      if(!file){
+	fprintf(stderr,"Could not open file %s\n",buffer);
+	exit(1);
+      }
+    }
+    
+    fprintf(file,
+ "/********************************************************************\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 huff/huffbuld\n"
+ "\n"
+ " ********************************************************************/\n\n");
+
+    fprintf(file,"#ifndef _V_%s_VQH_\n#define _V_%s_VQH_\n",base,base);
+    fprintf(file,"#include \"vorbis/codebook.h\"\n\n");
+    
+    /* first, the static vectors, then the book structure to tie it together. */
+    /* lengthlist */
+    fprintf(file,"static long _huff_lengthlist_%s[] = {\n",base);
+    for(j=0;j<vals;){
+      fprintf(file,"\t");
+      for(k=0;k<16 && j<vals;k++,j++)
+	fprintf(file,"%2ld,",lengths[j]);
+      fprintf(file,"\n");
+    }
+    fprintf(file,"};\n\n");
+    
+    /* the toplevel book */
+    fprintf(file,"static static_codebook _huff_book_%s = {\n",base);
+    fprintf(file,"\t%d, %ld,\n",subn,vals);
+    fprintf(file,"\t_huff_lengthlist_%s,\n",base);
+    fprintf(file,"\t0, 0, 0, 0, 0,\n");
+    fprintf(file,"\tNULL,\n");
+    fprintf(file,"\tNULL,\n");
+    fprintf(file,"\tNULL,\n");
+    fprintf(file,"};\n\n");
+    
+    fprintf(file,"\n#endif\n");
+    fclose(file);
+    fprintf(stderr,"Done.                                \n\n");
+  }
+  exit(0);
+}
+
+
diff --git a/vq/lspdata.c b/vq/lspdata.c
new file mode 100644
index 00000000..ee1bf989
--- /dev/null
+++ b/vq/lspdata.c
@@ -0,0 +1,158 @@
+/********************************************************************
+ *                                                                  *
+ * 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: metrics and quantization code for LSP VQ codebooks
+ last mod: $Id: lspdata.c,v 1.13.2.1 2000/10/31 08:25:17 xiphmont Exp $
+
+ ********************************************************************/
+
+#include <stdlib.h>
+#include <math.h>
+#include <stdio.h>
+#include "vqgen.h"
+#include "vqext.h"
+#include "../lib/sharedbook.h"
+
+char *vqext_booktype="LSPdata";  
+quant_meta q={0,0,0,1};          /* set sequence data */
+int vqext_aux=1;
+
+float global_maxdel=M_PI;
+float global_mindel=M_PI;
+#if 0
+void vqext_quantize(vqgen *v,quant_meta *q){
+  float delta,mindel;
+  float maxquant=((1<<q->quant)-1);
+  int j,k;
+
+  /* first find the basic delta amount from the maximum span to be
+     encoded.  Loosen the delta slightly to allow for additional error
+     during sequence quantization */
+
+  delta=(global_maxdel-global_mindel)/((1<<q->quant)-1.5);
+  
+  q->min=_float32_pack(global_mindel);
+  q->delta=_float32_pack(delta);
+
+  mindel=_float32_unpack(q->min);
+  delta=_float32_unpack(q->delta);
+
+  for(j=0;j<v->entries;j++){
+    float last=0;
+    for(k=0;k<v->elements;k++){
+      float val=_now(v,j)[k];
+      float now=rint((val-last-mindel)/delta);
+      
+      _now(v,j)[k]=now;
+      if(now<0){
+	/* be paranoid; this should be impossible */
+	fprintf(stderr,"fault; quantized value<0\n");
+	exit(1);
+      }
+
+      if(now>maxquant){
+	/* be paranoid; this should be impossible */
+	fprintf(stderr,"fault; quantized value>max\n");
+	exit(1);
+      }
+      last=(now*delta)+mindel+last;
+    }
+  }
+
+}
+#else
+void vqext_quantize(vqgen *v,quant_meta *q){
+  vqgen_quantize(v,q);
+}
+#endif
+
+float *weight=NULL;
+#if 0
+/* LSP training metric.  We weight error proportional to distance
+   *between* LSP vector values.  The idea of this metric is not to set
+   final cells, but get the midpoint spacing into a form conducive to
+   what we want, which is weighting toward preserving narrower
+   features. */
+
+#define FUDGE (global_maxdel-weight[i])
+
+float *vqext_weight(vqgen *v,float *p){
+  int i;
+  int el=v->elements;
+  float lastp=0.;
+  for(i=0;i<el;i++){
+    float predist=(p[i]-lastp);
+    float postdist=(p[i+1]-p[i]);
+    weight[i]=(predist<postdist?predist:postdist);
+    lastp=p[i];
+  }
+  return p;
+}
+#else
+#define FUDGE 1.
+float *vqext_weight(vqgen *v,float *p){
+  return p;
+}
+#endif
+
+                            /* candidate,actual */
+float vqext_metric(vqgen *v,float *e, float *p){
+  int i;
+  int el=v->elements;
+  float acc=0.;
+  for(i=0;i<el;i++){
+    float val=(p[i]-e[i])*FUDGE;
+    acc+=val*val;
+  }
+  return sqrt(acc/v->elements);
+}
+
+/* Data files are line-vectors, now just deltas.  The codebook entries
+   want to be monotonically increasing, so we adjust */
+
+/* assume vqext_aux==1 */
+void vqext_addpoint_adj(vqgen *v,float *b,int start,int dim,int cols,int num){
+  float *a=alloca(sizeof(float)*(dim+1)); /* +aux */
+  float base=0;
+  int i;
+
+  for(i=0;i<dim;i++)
+    base=a[i]=b[i+start]+base;
+
+  if(start+dim+1>cols) /* +aux */
+    a[i]=M_PI;
+  else
+    a[i]=b[i+start]+base;
+  
+  vqgen_addpoint(v,a,a+dim);
+}
+
+/* we just need to calc the global_maxdel from the training set */
+void vqext_preprocess(vqgen *v){
+  long j,k;
+
+  global_maxdel=0.;
+  global_mindel=M_PI;
+  for(j=0;j<v->points;j++){
+    float last=0.;
+    for(k=0;k<v->elements+v->aux;k++){
+      float p=_point(v,j)[k];
+      if(p-last>global_maxdel)global_maxdel=p-last;
+      if(p-last<global_mindel)global_mindel=p-last;
+      last=p;
+    }
+  }
+
+  weight=malloc(sizeof(float)*v->elements);
+}
+
diff --git a/vq/train.c b/vq/train.c
new file mode 100644
index 00000000..12a4a0b2
--- /dev/null
+++ b/vq/train.c
@@ -0,0 +1,365 @@
+/********************************************************************
+ *                                                                  *
+ * 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: utility main for training codebooks
+ last mod: $Id: train.c,v 1.19.2.1 2000/10/31 08:25:17 xiphmont Exp $
+
+ ********************************************************************/
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <math.h>
+#include <string.h>
+#include <errno.h>
+#include <signal.h>
+#include "vqgen.h"
+#include "vqext.h"
+#include "bookutil.h"
+
+static char *rline(FILE *in,FILE *out,int pass){
+  while(1){
+    char *line=get_line(in);
+    if(line && line[0]=='#'){
+      if(pass)fprintf(out,"%s\n",line);
+    }else{
+      return(line);
+    }
+  }
+}
+
+/* command line:
+   trainvq  vqfile [options] trainfile [trainfile]
+
+   options: -params     entries,dim,quant
+            -subvector  start[,num]
+	    -error      desired_error
+	    -iterations iterations
+*/
+
+static void usage(void){
+  fprintf(stderr, "\nOggVorbis %s VQ codebook trainer\n\n"
+	  "<foo>vqtrain vqfile [options] [datasetfile] [datasetfile]\n"
+	  "options: -p[arams]     <entries,dim,quant>\n"
+	  "         -s[ubvector]  <start[,num]>\n"
+	  "         -e[rror]      <desired_error>\n"
+	  "         -i[terations] <maxiterations>\n"
+	  "         -d[istance]   quantization mesh spacing for density limitation\n"
+	  "         -b <dummy>    eliminate cell size biasing; use normal LBG\n\n"
+	  "         -c <dummy>    Use centroid (not median) midpoints\n"
+
+	  "examples:\n"
+	  "   train a new codebook to 1%% tolerance on datafile 'foo':\n"
+	  "      xxxvqtrain book -p 256,6,8 -e .01 foo\n"
+	  "      (produces a trained set in book-0.vqi)\n\n"
+	  "   continue training 'book-0.vqi' (produces book-1.vqi):\n"
+	  "      xxxvqtrain book-0.vqi\n\n"
+	  "   add subvector from element 1 to <dimension> from files\n"
+	  "      data*.m to the training in progress, prodicing book-1.vqi:\n"
+	  "      xxxvqtrain book-0.vqi -s 1,1 data*.m\n\n",vqext_booktype);
+}
+
+int exiting=0;
+void setexit(int dummy){
+  fprintf(stderr,"\nexiting... please wait to finish this iteration\n");
+  exiting=1;
+}
+
+int main(int argc,char *argv[]){
+  vqgen v;
+
+  int entries=-1,dim=-1;
+  int start=0,num=-1;
+  float desired=.05,mindist=0.;
+  int iter=1000;
+  int biasp=1;
+  int centroid=0;
+
+  FILE *out=NULL;
+  char *line;
+  long i,j,k;
+  int init=0;
+  q.quant=-1;
+
+  argv++;
+  if(!*argv){
+    usage();
+    exit(0);
+  }
+
+  /* get the book name, a preexisting book to continue training */
+  {
+    FILE *in=NULL;
+    char *filename=alloca(strlen(*argv)+30),*ptr;
+
+    strcpy(filename,*argv);
+    in=fopen(filename,"r");
+    ptr=strrchr(filename,'-');
+    if(ptr){
+      int num;
+      ptr++;
+      num=atoi(ptr);
+      sprintf(ptr,"%d.vqi",num+1);
+    }else
+      strcat(filename,"-0.vqi");
+    
+    out=fopen(filename,"w");
+    if(out==NULL){
+      fprintf(stderr,"Unable to open %s for writing\n",filename);
+      exit(1);
+    }
+    
+    if(in){
+      /* we wish to suck in a preexisting book and continue to train it */
+      float a;
+      
+      line=rline(in,out,1);
+      if(strcmp(line,vqext_booktype)){
+	fprintf(stderr,"wrong book type; %s!=%s\n",line,vqext_booktype);
+	exit(1);
+      } 
+      
+      line=rline(in,out,1);
+      if(sscanf(line,"%d %d %d",&entries,&dim,&vqext_aux)!=3){
+	fprintf(stderr,"Syntax error reading book file\n");
+	exit(1);
+      }
+      
+      vqgen_init(&v,dim,vqext_aux,entries,mindist,
+		 vqext_metric,vqext_weight,centroid);
+      init=1;
+      
+      /* quant setup */
+      line=rline(in,out,1);
+      if(sscanf(line,"%ld %ld %d %d",&q.min,&q.delta,
+		&q.quant,&q.sequencep)!=4){
+	fprintf(stderr,"Syntax error reading book file\n");
+	exit(1);
+      }
+      
+      /* quantized entries */
+      i=0;
+      for(j=0;j<entries;j++){
+	for(k=0;k<dim;k++){
+	  line=rline(in,out,0);
+	  sscanf(line,"%f",&a);
+	  v.entrylist[i++]=a;
+	}
+      }      
+      vqgen_unquantize(&v,&q);
+
+      /* bias */
+      i=0;
+      for(j=0;j<entries;j++){
+	line=rline(in,out,0);
+	sscanf(line,"%f",&a);
+	v.bias[i++]=a;
+      }
+      
+      v.seeded=1;
+      {
+	float *b=alloca((dim+vqext_aux)*sizeof(float));
+	i=0;
+	while(1){
+	  for(k=0;k<dim+vqext_aux;k++){
+	    line=rline(in,out,0);
+	    if(!line)break;
+	    sscanf(line,"%f",b+k);
+	  }
+	  if(feof(in))break;
+	  vqgen_addpoint(&v,b,b+dim);
+	}
+      }
+      
+      fclose(in);
+    }
+  }
+  
+  /* get the rest... */
+  argv=argv++;
+  while(*argv){
+    if(argv[0][0]=='-'){
+      /* it's an option */
+      if(!argv[1]){
+	fprintf(stderr,"Option %s missing argument.\n",argv[0]);
+	exit(1);
+      }
+      switch(argv[0][1]){
+      case 'p':
+	if(sscanf(argv[1],"%d,%d,%d",&entries,&dim,&q.quant)!=3)
+	  goto syner;
+	break;
+      case 's':
+	if(sscanf(argv[1],"%d,%d",&start,&num)!=2){
+	  num= -1;
+	  if(sscanf(argv[1],"%d",&start)!=1)
+	    goto syner;
+	}
+	break;
+      case 'e':
+	if(sscanf(argv[1],"%f",&desired)!=1)
+	  goto syner;
+	break;
+      case 'd':
+	if(sscanf(argv[1],"%f",&mindist)!=1)
+	  goto syner;
+	if(init)v.mindist=mindist;
+	break;
+      case 'i':
+	if(sscanf(argv[1],"%d",&iter)!=1)
+	  goto syner;
+	break;
+      case 'b':
+	biasp=0;
+	break;
+      case 'c':
+	centroid=1;
+	break;
+      default:
+	fprintf(stderr,"Unknown option %s\n",argv[0]);
+	exit(1);
+      }
+      argv+=2;
+    }else{
+      /* it's an input file */
+      char *file=strdup(*argv++);
+      FILE *in;
+      int cols=-1;
+
+      if(!init){
+	if(dim==-1 || entries==-1 || q.quant==-1){
+	  fprintf(stderr,"-p required when training a new set\n");
+	  exit(1);
+	}
+	vqgen_init(&v,dim,vqext_aux,entries,mindist,
+		   vqext_metric,vqext_weight,centroid);
+	init=1;
+      }
+
+      in=fopen(file,"r");
+      if(in==NULL){
+	fprintf(stderr,"Could not open input file %s\n",file);
+	exit(1);
+      }
+      fprintf(out,"# training file entry: %s\n",file);
+
+      while((line=rline(in,out,0))){
+	if(cols==-1){
+	  char *temp=line;
+	  while(*temp==' ')temp++;
+	  for(cols=0;*temp;cols++){
+	    while(*temp>32)temp++;
+	    while(*temp==' ')temp++;
+	  }
+
+	  fprintf(stderr,"%d colums per line in file %s\n",cols,file);
+
+	}
+	{
+	  int i;
+	  float b[cols];
+	  if(start+num*dim>cols){
+	    fprintf(stderr,"ran out of columns reading %s\n",file);
+	    exit(1);
+	  }
+	  while(*line==' ')line++;
+	  for(i=0;i<cols;i++){
+
+	    /* static length buffer bug workaround */
+	    char *temp=line;
+	    char old;
+	    while(*temp>32)temp++;
+
+	    old=temp[0];
+	    temp[0]='\0';
+	    b[i]=atof(line);
+	    temp[0]=old;
+	    
+	    while(*line>32)line++;
+	    while(*line==' ')line++;
+	  }
+	  if(num<=0)num=(cols-start)/dim;
+	  for(i=0;i<num;i++)
+	    vqext_addpoint_adj(&v,b,start+i*dim,dim,cols,num);
+
+	}
+      }
+      fclose(in);
+    }
+  }
+
+  if(!init){
+    fprintf(stderr,"No input files!\n");
+    exit(1);
+  }
+
+  vqext_preprocess(&v);
+
+  /* train the book */
+  signal(SIGTERM,setexit);
+  signal(SIGINT,setexit);
+
+  for(i=0;i<iter && !exiting;i++){
+    float result;
+    if(i!=0){
+      vqgen_unquantize(&v,&q);
+      vqgen_cellmetric(&v);
+    }
+    result=vqgen_iterate(&v,biasp);
+    vqext_quantize(&v,&q);
+    if(result<desired)break;
+  }
+
+  /* save the book */
+
+  fprintf(out,"# OggVorbis VQ codebook trainer, intermediate file\n");
+  fprintf(out,"%s\n",vqext_booktype);
+  fprintf(out,"%d %d %d\n",entries,dim,vqext_aux);
+  fprintf(out,"%ld %ld %d %d\n",
+	  q.min,q.delta,q.quant,q.sequencep);
+
+  /* quantized entries */
+  fprintf(out,"# quantized entries---\n");
+  i=0;
+  for(j=0;j<entries;j++)
+    for(k=0;k<dim;k++)
+      fprintf(out,"%d\n",(int)(rint(v.entrylist[i++])));
+  
+  fprintf(out,"# biases---\n");
+  i=0;
+  for(j=0;j<entries;j++)
+    fprintf(out,"%f\n",v.bias[i++]);
+
+  /* we may have done the density limiting mesh trick; refetch the
+     training points from the temp file */
+
+  rewind(v.asciipoints);
+  fprintf(out,"# points---\n");
+  {
+    /* sloppy, no error handling */
+    long bytes;
+    char buff[4096];
+    while((bytes=fread(buff,1,4096,v.asciipoints)))
+      while(bytes)bytes-=fwrite(buff,1,bytes,out);
+  }
+
+  fclose(out);
+  fclose(v.asciipoints);
+
+  vqgen_unquantize(&v,&q);
+  vqgen_cellmetric(&v);
+  exit(0);
+
+  syner:
+    fprintf(stderr,"Syntax error in argument '%s'\n",*argv);
+    exit(1);
+}