floor 1 tuning and bugfixes

svn path=/branches/monty-branch-20010404/vorbis/; revision=1446

6 files changed, 517 insertions, 70 deletions

diff --git a/lib/floor1.c b/lib/floor1.c
index 9c088bb8..27a7e90e 100644
--- a/lib/floor1.c
+++ b/lib/floor1.c
@@ -11,7 +11,7 @@
  ********************************************************************
 
  function: floor backend 1 implementation
- last mod: $Id: floor1.c,v 1.1.2.5 2001/05/11 22:07:49 xiphmont Exp $
+ last mod: $Id: floor1.c,v 1.1.2.6 2001/05/13 22:40:24 xiphmont Exp $
 
  ********************************************************************/
 
@@ -516,20 +516,22 @@ static int accumulate_fit(const float *flr,const float *mdct,
 
   for(i=x0;i<x1;i++){
     int quantized=vorbis_floor1_dBquant(flr+i);
-    if(mdct[i]+info->twofitatten>=flr[i]){
-      xa  += i;
-      ya  += quantized;
-      x2a += i*i;
-      y2a += quantized*quantized;
-      xya += i*quantized;
-      na++;
-    }else{
-      xb  += i;
-      yb  += quantized;
-      x2b += i*i;
-      y2b += quantized*quantized;
-      xyb += i*quantized;
-      nb++;
+    if(quantized){
+      if(mdct[i]+info->twofitatten>=flr[i]){
+	xa  += i;
+	ya  += quantized;
+	x2a += i*i;
+	y2a += quantized*quantized;
+	xya += i*quantized;
+	na++;
+      }else{
+	xb  += i;
+	yb  += quantized;
+	x2b += i*i;
+	y2b += quantized*quantized;
+	xyb += i*quantized;
+	nb++;
+      }
     }
   }
 
@@ -640,7 +642,7 @@ static void fit_line_point(lsfit_acc *a,int fits,int *y0,int *y1){
   *y0=*y1=y;
 }
 
-static int inspect_error(int x0,int x1,int y0,int y1,const float *flr,
+static int inspect_error(int x0,int x1,int y0,int y1,const float *mask,
 			 const float *mdct,
 			 vorbis_info_floor1 *info){
   int dy=y1-y0;
@@ -651,13 +653,13 @@ static int inspect_error(int x0,int x1,int y0,int y1,const float *flr,
   int x=x0;
   int y=y0;
   int err=0;
-  int val=vorbis_floor1_dBquant(flr+x);
+  int val=vorbis_floor1_dBquant(mask+x);
   int mse=0;
   int n=0;
 
   ady-=abs(base*adx);
   
-  if(mdct[x]+info->twofitatten>=flr[x]){
+  if(mdct[x]+info->twofitatten>=mask[x]){
     if(y+info->maxover<val)return(1);
     if(y-info->maxunder>val)return(1);
     mse=(y-val);
@@ -674,8 +676,8 @@ static int inspect_error(int x0,int x1,int y0,int y1,const float *flr,
       y+=base;
     }
 
-    if(mdct[x]+info->twofitatten>=flr[x]){
-      val=vorbis_floor1_dBquant(flr+x);
+    if(mdct[x]+info->twofitatten>=mask[x]){
+      val=vorbis_floor1_dBquant(mask+x);
       if(val){
 	if(y+info->maxover<val)return(1);
 	if(y-info->maxunder>val)return(1);
@@ -685,9 +687,11 @@ static int inspect_error(int x0,int x1,int y0,int y1,const float *flr,
     }
   }
   
-  if(info->maxover*info->maxover/n>info->maxerr)return(0);
-  if(info->maxunder*info->maxunder/n>info->maxerr)return(0);
-  if(mse/n>info->maxerr)return(1);
+  if(n){
+    if(info->maxover*info->maxover/n>info->maxerr)return(0);
+    if(info->maxunder*info->maxunder/n>info->maxerr)return(0);
+    if(mse/n>info->maxerr)return(1);
+  }
   return(0);
 }
 
diff --git a/lib/mapping0.c b/lib/mapping0.c
index 6f2030c7..ab700a12 100644
--- a/lib/mapping0.c
+++ b/lib/mapping0.c
@@ -11,7 +11,7 @@
  ********************************************************************
 
  function: channel mapping 0 implementation
- last mod: $Id: mapping0.c,v 1.27.4.4 2001/05/11 22:07:50 xiphmont Exp $
+ last mod: $Id: mapping0.c,v 1.27.4.5 2001/05/13 22:40:24 xiphmont Exp $
 
  ********************************************************************/
 
@@ -279,7 +279,7 @@ static int mapping0_forward(vorbis_block *vb,vorbis_look_mapping *l){
 	      res,
 	      codedflr);
 
-    _analysis_output("codedflr",seq,codedflr,n/2,0,0);
+    _analysis_output("codedflr",seq,codedflr,n/2,0,1);
     _analysis_output("res",seq++,res,n/2,0,0);
       
 #ifdef TRAIN_RES
diff --git a/lib/modes/mode_A.h b/lib/modes/mode_A.h
index 478af771..d69ba681 100644
--- a/lib/modes/mode_A.h
+++ b/lib/modes/mode_A.h
@@ -11,7 +11,7 @@
  ********************************************************************
 
  function: predefined encoding modes
- last mod: $Id: mode_A.h,v 1.14.4.3 2001/05/11 22:07:53 xiphmont Exp $
+ last mod: $Id: mode_A.h,v 1.14.4.4 2001/05/13 22:40:25 xiphmont Exp $
 
  ********************************************************************/
 
@@ -259,7 +259,7 @@ static vorbis_info_floor1 _floor_set0A={4,
 					{3,3,3},
 					{1,2,2},
 					{0,1,2},
-					{{7,8},{-1,9,10,11},{-1,12,13,14}},
+					{{3,4},{-1,5,6,7},{-1,8,9,10}},
 
 					4,
 					{0,128,
@@ -270,30 +270,36 @@ static vorbis_info_floor1 _floor_set0A={4,
 					 45,30,73},
 					
 					60,30,600,
-					999,999,0,0.,
+					999,999,0,18.,
 					8,96};
 
 static vorbis_info_floor1 _floor_set1A={10,
-					{0,1,2,2,2,2,3,3,3,3},
+					{0,1,2,2,2,2,2, 3,3,3},
 					
 					{3,4,3,3},
 					{1,1,2,2},
-					{3,4,5,6},
-					{{15,16},{17,18},
-					 {-1,19,20,21},{-1,22,23,24}},
+					{11,12,13,14},
+					{{15,16},
+					 {17,18},
+					 {-1,19,20,21},
+					 {-1,22,23,24},
+					},
 
 					4,
 					{0,1024,
+
 					 88,31,243,
-					 14,54,143,460,
 
+					 14,54,143,460,
+					 
 					 6,3,10, 22,18,26, 41,36,47, 
 					 69,61,78, 112,99,126, 185,162,211,  
-					 329,282,387, 672,553,825},
+					 329,282,387, 672,553,825
+					 },
 					
 					60,30,600,
 					20,8,1,18.,
-					40,768};
+					20,768};
 
 static vorbis_info_residue0 _residue_set0A={0,96,16,6,25,
 					    {0,1,1,1,1,1},
@@ -341,27 +347,28 @@ codec_setup_info info_A={
   {&_huff_book_line0_class0, /* 0 */
    &_huff_book_line0_class1,
    &_huff_book_line0_class2, /* 2 */
-   &_huff_book_line1_class0,
-   &_huff_book_line1_class1, /* 4 */
-   &_huff_book_line1_class2,
-   &_huff_book_line1_class3, /* 6 */
    
-   &_huff_book_line0_0sub0,
+   &_huff_book_line0_0sub0,  /* 3 */
    &_huff_book_line0_0sub1,
-   &_huff_book_line0_1sub1,
+   &_huff_book_line0_1sub1,  /* 5 */
    &_huff_book_line0_1sub2,
-   &_huff_book_line0_1sub3,
+   &_huff_book_line0_1sub3,  /* 7 */
    &_huff_book_line0_2sub1,
-   &_huff_book_line0_2sub2,
-   &_huff_book_line0_2sub3, /* 14 */
+   &_huff_book_line0_2sub2,  /* 9 */
+   &_huff_book_line0_2sub3, 
+
+   &_huff_book_line1_class0,
+   &_huff_book_line1_class1, /* 12 */
+   &_huff_book_line1_class2,
+   &_huff_book_line1_class3, /* 14 */
 
    &_huff_book_line1_0sub0,
-   &_huff_book_line1_0sub1,
-   &_huff_book_line1_1sub0,
+   &_huff_book_line1_0sub1, /* 16 */
+   &_huff_book_line1_1sub0, 
    &_huff_book_line1_1sub1,
-   &_huff_book_line1_2sub1,
-   &_huff_book_line1_2sub2,
-   &_huff_book_line1_2sub3,
+   &_huff_book_line1_2sub1,  
+   &_huff_book_line1_2sub2, /* 20 */
+   &_huff_book_line1_2sub3, 
    &_huff_book_line1_3sub1,
    &_huff_book_line1_3sub2,
    &_huff_book_line1_3sub3, /* 24 */
diff --git a/lib/scales.h b/lib/scales.h
index 61fb9b39..84d8083b 100644
--- a/lib/scales.h
+++ b/lib/scales.h
@@ -11,7 +11,7 @@
  ********************************************************************
 
  function: linear scale -> dB, Bark and Mel scales
- last mod: $Id: scales.h,v 1.15.4.1 2001/05/11 22:07:50 xiphmont Exp $
+ last mod: $Id: scales.h,v 1.15.4.2 2001/05/13 22:40:24 xiphmont Exp $
 
  ********************************************************************/
 
@@ -23,7 +23,7 @@
 
 /* 20log10(x) */
 #ifdef VORBIS_IEEE_FLOAT32
-static float todB_LOOKUP[196]={
+static float todB_LOOKUP[256]={
         -140.277330f, -139.633636f, -139.034372f, -138.473797f, 
         -137.450747f, -136.535597f, -135.707743f, -134.951972f, 
         -134.256730f, -133.613036f, -133.013772f, -132.453198f, 
@@ -68,16 +68,31 @@ static float todB_LOOKUP[196]={
          -17.038749f,  -16.123599f,  -15.295746f,  -14.539974f, 
          -13.844732f,  -13.201039f,  -12.601774f,  -12.041200f, 
          -11.018149f,  -10.103000f,   -9.275146f,   -8.519375f, 
-          -7.824132f,  -7.180439f,    -6.581174f,   -6.020600f, 
-          -4.997549f,  -4.082400f,    -3.254546f,   -2.498775f, 
-          -1.803533f,  -1.159839f,    -0.560574f,    0.000000f, 
-           1.023050f,   1.938200f,     2.766054f,    3.521825f, 
-           4.217067f,   4.860761f,     5.460025f,    6.020600f 
+          -7.824132f,   -7.180439f,   -6.581174f,   -6.020600f, 
+          -4.997549f,   -4.082400f,   -3.254546f,   -2.498775f, 
+          -1.803533f,   -1.159839f,   -0.560574f,    0.000000f, 
+           1.023050f,    1.938200f,    2.766054f,    3.521825f, 
+	   4.217067f,    4.860761f,    5.460025f,    6.020600f, 
+           7.043650f,    7.958800f,    8.786654f,    9.542425f, 
+          10.237667f,   10.881361f,   11.480625f,   12.041200f, 
+          13.064250f,   13.979400f,   14.807254f,   15.563025f, 
+          16.258267f,   16.901961f,   17.501225f,   18.061800f, 
+          19.084850f,   20.000000f,   20.827854f,   21.583625f, 
+          22.278867f,   22.922561f,   23.521825f,   24.082400f, 
+          25.105450f,   26.020600f,   26.848453f,   27.604225f, 
+          28.299467f,   28.943161f,   29.542425f,   30.102999f, 
+          31.126050f,   32.041200f,   32.869053f,   33.624825f, 
+          34.320067f,   34.963760f,   35.563025f,   36.123599f, 
+          37.146650f,   38.061800f,   38.889653f,   39.645424f, 
+          40.340667f,   40.984360f,   41.583625f,   42.144199f, 
+          43.167250f,   44.082399f,   44.910253f,   45.666024f, 
+          46.361266f,   47.004960f,   47.604225f,   48.164799f, 
+          49.187850f,   50.102999f,   50.930853f,   51.686624f
 };
 
-static float todB(float *x) {
+static float todB(float *x){
   ogg_int32_t *i=(ogg_int32_t *)x;
-  ogg_int32_t temp=(*i&0x7fffffff)-0x33cfffff;
+  ogg_int32_t temp=((*i&0x7fffffff)-0x33cfffff)>>20;
   if(temp<0)return -400.f;
   return(todB_LOOKUP[temp]);
 }
@@ -86,8 +101,8 @@ static float todB(float *x) {
 
 #else
 
-#define todB(x)   ((*x)==0?-400.f:log((*x)*(*x))*4.34294480f)
-#define todB_nn(x)   ((*x)==0.f?-400.f:log(*x)*8.6858896f)
+#define todB(x)   (*(x)==0?-400.f:log(*(x)**(x))*4.34294480f)
+#define todB_nn(x)   (*(x)==0.f?-400.f:log(*(x))*8.6858896f)
 
 #endif 
 
diff --git a/vq/huffbuild.c b/vq/huffbuild.c
index dab5efad..5b0be469 100644
--- a/vq/huffbuild.c
+++ b/vq/huffbuild.c
@@ -11,7 +11,7 @@
  ********************************************************************
 
  function: hufftree builder
- last mod: $Id: huffbuild.c,v 1.8.4.1 2001/05/11 22:07:54 xiphmont Exp $
+ last mod: $Id: huffbuild.c,v 1.8.4.2 2001/05/13 22:40:26 xiphmont Exp $
 
  ********************************************************************/
 
@@ -106,7 +106,11 @@ int main(int argc, char *argv[]){
   file=fopen(infile,"r");
   if(!file){
     fprintf(stderr,"Could not open file %s\n",infile);
-    exit(1);
+    if(!maxval)
+      exit(1);
+    else
+      fprintf(stderr,"  making untrained books.\n");
+
   }
 
   if(!maxval){
@@ -129,15 +133,17 @@ int main(int argc, char *argv[]){
     
     for(j=loval;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 || val>=maxval)break;
-      hist[val]++;
-      if(!(i--&0xff))spinnit("loading... ",i*subn);
+    if(file){
+      reset_next_value();
+      i/=subn;
+      while(!feof(file)){
+	long val=getval(file,begin,n,subn,maxval);
+	if(val==-1 || val>=maxval)break;
+	hist[val]++;
+	if(!(i--&0xff))spinnit("loading... ",i*subn);
+      }
+      fclose(file);
     }
-    fclose(file);
  
     /* we have the probabilities, build the tree */
     fprintf(stderr,"Building tree for %ld entries\n",vals);
diff --git a/vq/latticehint.c b/vq/latticehint.c
new file mode 100644
index 00000000..9fd26e4d
--- /dev/null
+++ b/vq/latticehint.c
@@ -0,0 +1,415 @@
+/********************************************************************
+ *                                                                  *
+ * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
+ * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
+ * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
+ * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
+ *                                                                  *
+ * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2001             *
+ * by the XIPHOPHORUS Company http://www.xiph.org/                  *
+
+ ********************************************************************
+
+ function: utility main for building thresh/pigeonhole encode hints
+ last mod: $Id: latticehint.c,v 1.8.4.1 2001/05/13 22:40:26 xiphmont Exp $
+
+ ********************************************************************/
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <math.h>
+#include <string.h>
+#include <errno.h>
+#include "../lib/scales.h"
+#include "bookutil.h"
+#include "vqgen.h"
+#include "vqsplit.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]=_ogg_realloc(tempstack[entry],
+			     (tempcount[entry]+1)*sizeof(long));
+  }else{
+    tempstack[entry]=_ogg_malloc(sizeof(long));
+  }
+
+  tempstack[entry][tempcount[entry]++]=add;
+  return(1);
+}
+
+static void setvals(int dim,encode_aux_pigeonhole *p,
+		    long *temptrack,float *tempmin,float *tempmax,
+		    int seqp){
+  int i;
+  float last=0.f;
+  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 float minerror(int dim,float *a,encode_aux_pigeonhole *p,
+		       long *temptrack,float *tempmin,float *tempmax){
+  int i;
+  float err=0.f;
+  for(i=0;i<dim;i++){
+    float eval=0.f;
+    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 float maxerror(int dim,float *a,encode_aux_pigeonhole *p,
+		       long *temptrack,float *tempmin,float *tempmax){
+  int i;
+  float err=0.f,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{
+      float 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;
+  float min,del;
+  char *name;
+  long i,j;
+  long dB=0;
+
+  if(argv[1]==NULL){
+    fprintf(stderr,"Need a lattice book on the command line.\n");
+    exit(1);
+  }
+
+  if(argv[2])dB=1;
+
+  {
+    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=_ogg_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=_ogg_calloc(quantvals-1,sizeof(float));
+    t->quantmap=_ogg_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++){
+      float v1=*(quantsort[i])*del+min;
+      float v2=*(quantsort[i+1])*del+min;
+      if(dB){
+	if(fabs(v1)<.01)v1=(v1+v2)*.5;
+	if(fabs(v2)<.01)v2=(v1+v2)*.5;
+	t->quantthresh[i]=fromdB((todB(&v1)+todB(&v2))*.5);
+	if(v1<0 || v2<0)t->quantthresh[i]*=-1;
+
+      }else{
+	t->quantthresh[i]=(v1+v2)*.5;
+      }
+    }
+  }
+
+  /* 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;
+    float *tempmin;
+    float *tempmax;
+    long totalstack=0;
+    long pigeons;
+    long subpigeons;
+    long quantvals=_book_maptype1_quantvals(c);
+    int changep=1,factor;
+
+    encode_aux_pigeonhole *p=_ogg_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 */
+    factor=3;
+    p->del=del;
+    p->min=min;
+    p->quantvals=quantvals;
+    {
+      int max=0;
+      for(i=0;i<quantvals;i++)if(max<c->quantlist[i])max=c->quantlist[i];
+      p->mapentries=max;
+    }
+    p->pigeonmap=_ogg_malloc(p->mapentries*sizeof(long));
+    p->quantvals=(quantvals+factor-1)/factor;
+
+    /* 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++){
+      float thisval=del*i+min; /* middle of the quant zone */
+      int quant=0;
+      float err=fabs(c->quantlist[0]*del+min-thisval);
+      for(j=1;j<quantvals;j++){
+	float thiserr=fabs(c->quantlist[j]*del+min-thisval);
+	if(thiserr<err){
+	  quant=j/factor;
+	  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=_ogg_calloc(dim,sizeof(long));
+    tempmin=_ogg_calloc(dim,sizeof(float));
+    tempmax=_ogg_calloc(dim,sizeof(float));
+    tempstack=_ogg_calloc(pigeons,sizeof(long *));
+    tempcount=_ogg_calloc(pigeons,sizeof(long));
+
+    while(1){
+      float 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){
+	  float 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++){
+      float probability= 1.f/(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=_ogg_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 */
+    fprintf(stderr,"\r                                                       "
+	    "\rFinal total list size: %ld\n",totalstack);
+    
+
+    p->fittotal=totalstack;
+    p->fitlist=_ogg_malloc((totalstack+1)*sizeof(long));
+    p->fitlength=_ogg_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);
+}