Incremental update

svn path=/branches/monty_branch_20000724/vorbis/; revision=541

2 files changed, 1140 insertions, 0 deletions

diff --git a/vq/bookutil.c b/vq/bookutil.c
new file mode 100644
index 00000000..8193d321
--- /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.15.2.1 2000/08/03 21:12:53 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,double *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,double *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){
+  double value;
+  int ret=get_next_value(in,&value);
+  *ivalue=value;
+  return(ret);
+}
+
+static double 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,double *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){
+      double 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 double _vq_quantthresh_");
+    reset_next_value();
+    t->quantthresh=malloc(sizeof(double)*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,"%lf, %lf, %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 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(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/latticehint.c b/vq/latticehint.c
new file mode 100644
index 00000000..357fe0d8
--- /dev/null
+++ b/vq/latticehint.c
@@ -0,0 +1,398 @@
+/********************************************************************
+ *                                                                  *
+ * 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 thresh/pigeonhole encode hints
+ last mod: $Id: latticehint.c,v 1.1.2.1 2000/08/03 21:12:53 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"
+
+/* The purpose of this util is to build encode hints for lattice
+   codebooks so that brute forcing each codebook entry isn't needed.
+   Threshhold hints are for books in which each scalar in the vector
+   is independant (eg, residue) and pigeonhole lookups provide a
+   minimum error fit for words where the scalars are interdependant
+   (each affecting the fit of the next in sequence) as in an LSP
+   sequential book (or can be used along with a sparse threshhold map,
+   like a splitting tree that need not be trained) 
+
+   If the input book is non-sequential, a threshhold hint is built.
+   If the input book is sequential, a pigeonholing hist is built.
+   If the book is sparse, a pigeonholing hint is built, possibly in addition
+     to the threshhold hint 
+
+   command line:
+   latticehint book.vqh
+
+   latticehint produces book.vqh on stdout */
+
+static int longsort(const void *a, const void *b){
+  return(**((long **)a)-**((long **)b));
+}
+
+static int addtosearch(int entry,long **tempstack,long *tempcount,int add){
+  long *ptr=tempstack[entry];
+  long i=tempcount[entry];
+
+  if(ptr){
+    while(i--)
+      if(*ptr++==add)return(0);
+    tempstack[entry]=realloc(tempstack[entry],
+			     (tempcount[entry]+1)*sizeof(long));
+  }else{
+    tempstack[entry]=malloc(sizeof(long));
+  }
+
+  tempstack[entry][tempcount[entry]++]=add;
+  return(1);
+}
+
+static void setvals(int dim,encode_aux_pigeonhole *p,
+		    long *temptrack,double *tempmin,double *tempmax,
+		    int seqp){
+  int i;
+  double last=0.;
+  for(i=0;i<dim;i++){
+    tempmin[i]=(temptrack[i])*p->del+p->min+last;
+    tempmax[i]=tempmin[i]+p->del;
+    if(seqp)last=tempmin[i];
+  }
+}
+
+/* note that things are currently set up such that input fits that
+   quantize outside the pigeonmap are dropped and brute-forced.  So we
+   can ignore the <0 and >=n boundary cases in min/max error */
+
+static double minerror(int dim,double *a,encode_aux_pigeonhole *p,
+		       long *temptrack,double *tempmin,double *tempmax){
+  int i;
+  double err=0.;
+  for(i=0;i<dim;i++){
+    double eval=0.;
+    if(a[i]<tempmin[i]){
+      eval=tempmin[i]-a[i];
+    }else if(a[i]>tempmax[i]){
+      eval=a[i]-tempmax[i];
+    }
+    err+=eval*eval;
+  }
+  return(err);
+}
+
+static double maxerror(int dim,double *a,encode_aux_pigeonhole *p,
+		       long *temptrack,double *tempmin,double *tempmax){
+  int i;
+  double err=0.,eval;
+  for(i=0;i<dim;i++){
+    if(a[i]<tempmin[i]){
+      eval=tempmax[i]-a[i];
+    }else if(a[i]>tempmax[i]){
+      eval=a[i]-tempmin[i];
+    }else{
+      double t1=a[i]-tempmin[i];
+      eval=tempmax[i]-a[i];
+      if(t1>eval)eval=t1;
+    }
+    err+=eval*eval;
+  }
+  return(err);
+}
+
+int main(int argc,char *argv[]){
+  codebook *b;
+  static_codebook *c;
+  int entries=-1,dim=-1;
+  double min,del,cutoff=1.;
+  char *name;
+  long i,j;
+
+  if(argv[1]==NULL){
+    fprintf(stderr,"Need a lattice book on the command line.\n");
+    exit(1);
+  }
+
+  if(argv[2])cutoff=atof(argv[2]);
+
+  {
+    char *ptr;
+    char *filename=strdup(argv[1]);
+
+    b=codebook_load(filename);
+    c=(static_codebook *)(b->c);
+    
+    ptr=strrchr(filename,'.');
+    if(ptr){
+      *ptr='\0';
+      name=strdup(filename);
+    }else{
+      name=strdup(filename);
+    }
+  }
+
+  if(c->maptype!=1){
+    fprintf(stderr,"Provided book is not a latticebook.\n");
+    exit(1);
+  }
+
+  entries=b->entries;
+  dim=b->dim;
+  min=_float32_unpack(c->q_min);
+  del=_float32_unpack(c->q_delta);
+
+  /* Do we want to gen a threshold hint? */
+  if(c->q_sequencep==0){
+    /* yes. Discard any preexisting threshhold hint */
+    long quantvals=_book_maptype1_quantvals(c);
+    long **quantsort=alloca(quantvals*sizeof(long *));
+    encode_aux_threshmatch *t=calloc(1,sizeof(encode_aux_threshmatch));
+    c->thresh_tree=t;
+
+    fprintf(stderr,"Adding threshold hint to %s...\n",name);
+
+    /* simplest possible threshold hint only */
+    t->quantthresh=calloc(quantvals-1,sizeof(double));
+    t->quantmap=calloc(quantvals,sizeof(int));
+    t->threshvals=quantvals;
+    t->quantvals=quantvals;
+
+    /* the quantvals may not be in order; sort em first */
+    for(i=0;i<quantvals;i++)quantsort[i]=c->quantlist+i;
+    qsort(quantsort,quantvals,sizeof(long *),longsort);
+
+    /* ok, gen the map and thresholds */
+    for(i=0;i<quantvals;i++)t->quantmap[i]=quantsort[i]-c->quantlist;
+    for(i=0;i<quantvals-1;i++)
+      t->quantthresh[i]=(*(quantsort[i])+*(quantsort[i+1]))*.5*del+min;
+  }
+
+  /* Do we want to gen a pigeonhole hint? */
+  for(i=0;i<entries;i++)if(c->lengthlist[i]==0)break;
+  if(c->q_sequencep || i<entries){
+    long **tempstack;
+    long *tempcount;
+    long *temptrack;
+    double *tempmin;
+    double *tempmax;
+    long totalstack=0;
+    long pigeons;
+    long subpigeons;
+    long quantvals=_book_maptype1_quantvals(c);
+    int changep=1;
+
+    encode_aux_pigeonhole *p=calloc(1,sizeof(encode_aux_pigeonhole));
+    c->pigeon_tree=p;
+
+    fprintf(stderr,"Adding pigeonhole hint to %s...\n",name);
+    
+    /* the idea is that we quantize uniformly, even in a nonuniform
+       lattice, so that quantization of one scalar has a predictable
+       result on the next sequential scalar in a greedy matching
+       algorithm.  We generate a lookup based on the quantization of
+       the vector (pigeonmap groups quantized entries together) and
+       list the entries that could possible be the best fit for any
+       given member of that pigeonhole.  The encode process then has a
+       much smaller list to brute force */
+
+    /* find our pigeonhole-specific quantization values, fill in the
+       quant value->pigeonhole map */
+    p->del=del;
+    p->min=min-del*.5;
+    p->quantvals=(quantvals+1)/2;
+    {
+      int max=0;
+      for(i=0;i<quantvals;i++)if(max<c->quantlist[i])max=c->quantlist[i];
+      p->mapentries=max;
+    }
+    p->pigeonmap=malloc(p->mapentries*sizeof(long));
+
+    /* pigeonhole roughly on the boundaries of the quantvals; the
+       exact pigeonhole grouping is an optimization issue, not a
+       correctness issue */
+    for(i=0;i<p->mapentries;i++){
+      double thisval=del*(i+.5)+min; /* middle of the quant zone */
+      int quant=0;
+      double err=fabs(c->quantlist[0]*del+min-thisval);
+      for(j=1;j<quantvals;j++){
+	double thiserr=fabs(c->quantlist[j]*del+min-thisval);
+	if(thiserr<err){
+	  quant=j/2;
+	  err=thiserr;
+	}
+      }
+      p->pigeonmap[i]=quant;
+    }
+    
+    /* pigeonmap complete.  Now do the grungy business of finding the
+    entries that could possibly be the best fit for a value appearing
+    in the pigeonhole. The trick that allows the below to work is the
+    uniform quantization; even though the scalars may be 'sequential'
+    (each a delta from the last), the uniform quantization means that
+    the error variance is *not* dependant.  Given a pigeonhole and an
+    entry, we can find the minimum and maximum possible errors
+    (relative to the entry) for any point that could appear in the
+    pigeonhole */
+    
+    /* must iterate over both pigeonholes and entries */
+    /* temporarily (in order to avoid thinking hard), we grow each
+       pigeonhole seperately, the build a stack of 'em later */
+    pigeons=1;
+    subpigeons=1;
+    for(i=0;i<dim;i++)subpigeons*=p->mapentries;
+    for(i=0;i<dim;i++)pigeons*=p->quantvals;
+    temptrack=calloc(dim,sizeof(long));
+    tempmin=calloc(dim,sizeof(double));
+    tempmax=calloc(dim,sizeof(double));
+    tempstack=calloc(pigeons,sizeof(long *));
+    tempcount=calloc(pigeons,sizeof(long));
+
+    while(1){
+      double errorpost=-1;
+      char buffer[80];
+
+      /* map our current pigeonhole to a 'big pigeonhole' so we know
+         what list we're after */
+      int entry=0;
+      for(i=dim-1;i>=0;i--)entry=entry*p->quantvals+p->pigeonmap[temptrack[i]];
+      setvals(dim,p,temptrack,tempmin,tempmax,c->q_sequencep);
+      sprintf(buffer,"Building pigeonhole search list [%ld]...",totalstack);
+
+
+      /* Search all entries to find the one with the minimum possible
+         maximum error.  Record that error */
+      for(i=0;i<entries;i++){
+	if(c->lengthlist[i]>0){
+	  double this=maxerror(dim,b->valuelist+i*dim,p,
+			       temptrack,tempmin,tempmax);
+	  if(errorpost==-1 || this<errorpost)errorpost=this;
+	  spinnit(buffer,subpigeons);
+	}
+      }
+
+      /* Our search list will contain all entries with a minimum
+         possible error <= our errorpost */
+      for(i=0;i<entries;i++)
+	if(c->lengthlist[i]>0){
+	  spinnit(buffer,subpigeons);
+	  if(minerror(dim,b->valuelist+i*dim,p,
+		      temptrack,tempmin,tempmax)<errorpost)
+	    totalstack+=addtosearch(entry,tempstack,tempcount,i);
+	}
+
+      for(i=0;i<dim;i++){
+	temptrack[i]++;
+	if(temptrack[i]<p->mapentries)break;
+	temptrack[i]=0;
+      }
+      if(i==dim)break;
+      subpigeons--;
+    }
+
+    fprintf(stderr,"\r                                                     "
+	    "\rTotal search list size (all entries): %ld\n",totalstack);
+
+    /* pare the index of lists for improbable quantizations (where
+       improbable is determined by c->lengthlist; we assume that
+       pigeonholing is in sync with the codeword cells, which it is */
+    /*for(i=0;i<entries;i++){
+      double probability= 1./(1<<c->lengthlist[i]);
+      if(c->lengthlist[i]==0 || probability*entries<cutoff){
+	totalstack-=tempcount[i];
+	tempcount[i]=0;
+      }
+      }*/
+
+    /* pare the list of shortlists; merge contained and similar lists
+       together */
+    p->fitmap=malloc(pigeons*sizeof(long));
+    for(i=0;i<pigeons;i++)p->fitmap[i]=-1;
+    while(changep){
+      char buffer[80];
+      changep=0;
+
+      for(i=0;i<pigeons;i++){
+	if(p->fitmap[i]<0 && tempcount[i]){
+	  for(j=i+1;j<pigeons;j++){
+	    if(p->fitmap[j]<0 && tempcount[j]){
+	      /* is one list a superset, or are they sufficiently similar? */
+	      int amiss=0,bmiss=0,ii,jj;
+	      for(ii=0;ii<tempcount[i];ii++){
+		for(jj=0;jj<tempcount[j];jj++)
+		  if(tempstack[i][ii]==tempstack[j][jj])break;
+		if(jj==tempcount[j])amiss++;
+	      }
+	      for(jj=0;jj<tempcount[j];jj++){
+		for(ii=0;ii<tempcount[i];ii++)
+		  if(tempstack[i][ii]==tempstack[j][jj])break;
+		if(ii==tempcount[i])bmiss++;
+	      }
+	      if(amiss==0 ||
+		 bmiss==0 ||
+		 (amiss*2<tempcount[i] && bmiss*2<tempcount[j] &&
+		  tempcount[i]+bmiss<entries/30)){
+
+		/*superset/similar  Add all of one to the other. */
+		for(jj=0;jj<tempcount[j];jj++)
+		  totalstack+=addtosearch(i,tempstack,tempcount,
+					  tempstack[j][jj]);
+		totalstack-=tempcount[j];
+		p->fitmap[j]=i;
+		changep=1;
+	      }
+	    }
+	  }
+	  sprintf(buffer,"Consolidating [%ld total, %s]... ",totalstack,
+		  changep?"reit":"nochange");
+	  spinnit(buffer,pigeons-i);
+	}
+      }
+    }
+
+    /* repack the temp stack in final form */
+
+    p->fittotal=totalstack;
+    p->fitlist=malloc((totalstack+1)*sizeof(long));
+    p->fitlength=malloc(pigeons*sizeof(long));
+    {
+      long usage=0;
+      for(i=0;i<pigeons;i++){
+	if(p->fitmap[i]==-1){
+	  if(tempcount[i])
+	    memcpy(p->fitlist+usage,tempstack[i],tempcount[i]*sizeof(long));
+	  p->fitmap[i]=usage;
+	  p->fitlength[i]=tempcount[i];
+	  usage+=tempcount[i];
+	  if(usage>totalstack){
+	    fprintf(stderr,"Internal error; usage>totalstack\n");
+	    exit(1);
+	  }
+	}else{
+	  p->fitlength[i]=p->fitlength[p->fitmap[i]];
+	  p->fitmap[i]=p->fitmap[p->fitmap[i]];
+	}
+      }
+    }
+  }
+
+  write_codebook(stdout,name,c); 
+  fprintf(stderr,"\r                                                     "
+	  "\nDone.\n");
+  exit(0);
+}