vq/latticebuild.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
   4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
   5  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
   6  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
   7  *                                                                  *
   8  * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2001             *
   9  * by the Xiph.Org Foundation http://www.xiph.org/                  *
  10  *                                                                  *
  11  ********************************************************************
  12
  13  function: utility main for building codebooks from lattice descriptions
  14
  15  ********************************************************************/
  16
  17 #include <stdlib.h>
  18 #include <stdio.h>
  19 #include <math.h>
  20 #include <string.h>
  21 #include <errno.h>
  22 #include "bookutil.h"
  23
  24 /* The purpose of this util is just to finish packaging the
  25    description into a static codebook.  It used to count hits for a
  26    histogram, but I've divorced that out to add some flexibility (it
  27    currently generates an equal probability codebook)
  28
  29    command line:
  30    latticebuild description.vql
  31
  32    the lattice description file contains two lines:
  33
  34    <n> <dim> <multiplicitavep> <sequentialp>
  35    <value_0> <value_1> <value_2> ... <value_n-1>
  36
  37    a threshmap (or pigeonmap) struct is generated by latticehint;
  38    there are fun tricks one can do with the threshmap and cascades,
  39    but the utils don't know them...
  40
  41    entropy encoding is done by feeding an entry list collected from a
  42    training set and feeding it to latticetune along with the book.
  43
  44    latticebuild produces a codebook on stdout */
  45
  46 static int ilog(unsigned int v){
  47   int ret=0;
  48   while(v){
  49     ret++;
  50     v>>=1;
  51   }
  52   return(ret);
  53 }
  54
  55 int main(int argc,char *argv[]){
  56   codebook b;
  57   static_codebook c;
  58   double *quantlist;
  59   long *hits;
  60
  61   int entries=-1,dim=-1,quantvals=-1,addmul=-1,sequencep=0;
  62   FILE *in=NULL;
  63   char *line,*name;
  64   long i,j;
  65
  66   memset(&b,0,sizeof(b));
  67   memset(&c,0,sizeof(c));
  68
  69   if(argv[1]==NULL){
  70     fprintf(stderr,"Need a lattice description file on the command line.\n");
  71     exit(1);
  72   }
  73
  74   {
  75     char *ptr;
  76     char *filename=_ogg_calloc(strlen(argv[1])+4,1);
  77
  78     strcpy(filename,argv[1]);
  79     in=fopen(filename,"r");
  80     if(!in){
  81       fprintf(stderr,"Could not open input file %s\n",filename);
  82       exit(1);
  83     }
  84
  85     ptr=strrchr(filename,'.');
  86     if(ptr){
  87       *ptr='\0';
  88       name=strdup(filename);
  89     }else{
  90       name=strdup(filename);
  91     }
  92
  93   }
  94
  95   /* read the description */
  96   line=get_line(in);
  97   if(sscanf(line,"%d %d %d %d",&quantvals,&dim,&addmul,&sequencep)!=4){
  98     if(sscanf(line,"%d %d %d",&quantvals,&dim,&addmul)!=3){
  99       fprintf(stderr,"Syntax error reading description file (line 1)\n");
 100       exit(1);
 101     }
 102   }
 103   entries=pow(quantvals,dim);
 104   c.dim=dim;
 105   c.entries=entries;
 106   c.lengthlist=_ogg_malloc(entries*sizeof(long));
 107   c.maptype=1;
 108   c.q_sequencep=sequencep;
 109   c.quantlist=_ogg_calloc(quantvals,sizeof(long));
 110
 111   quantlist=_ogg_malloc(sizeof(double)*c.dim*c.entries);
 112   hits=_ogg_malloc(c.entries*sizeof(long));
 113   for(j=0;j<entries;j++)hits[j]=1;
 114   for(j=0;j<entries;j++)c.lengthlist[j]=1;
 115
 116   reset_next_value();
 117   line=setup_line(in);
 118   for(j=0;j<quantvals;j++){
 119     char *temp;
 120     if(!line || sscanf(line,"%lf",quantlist+j)!=1){
 121       fprintf(stderr,"Ran out of data on line 2 of description file\n");
 122       exit(1);
 123     }
 124     temp=strchr(line,',');
 125     if(!temp)temp=strchr(line,' ');
 126     if(temp)temp++;
 127     line=temp;
 128   }
 129
 130   /* gen a real quant list from the more easily human-grokked input */
 131   {
 132     double min=quantlist[0];
 133     double mindel=-1;
 134     int fac=1;
 135     for(j=1;j<quantvals;j++)if(quantlist[j]<min)min=quantlist[j];
 136     for(j=0;j<quantvals;j++)
 137       for(i=j+1;i<quantvals;i++)
 138         if(mindel==-1 || fabs(quantlist[j]-quantlist[i])<mindel)
 139           mindel=fabs(quantlist[j]-quantlist[i]);
 140
 141     j=0;
 142     while(j<quantvals){
 143       for(j=0;j<quantvals;j++){
 144         double test=fac*(quantlist[j]-min)/mindel;
 145         if( fabs(rint(test)-test)>.00001f) break;
 146       }
 147       if(fac>100)break;
 148       if(j<quantvals)fac++;
 149     }
 150
 151     mindel/=fac;
 152     fprintf(stderr,"min=%g mindel=%g\n",min,mindel);
 153
 154     c.q_min=_float32_pack(min);
 155     c.q_delta=_float32_pack(mindel);
 156     c.q_quant=0;
 157
 158     min=_float32_unpack(c.q_min);
 159     mindel=_float32_unpack(c.q_delta);
 160     for(j=0;j<quantvals;j++){
 161       c.quantlist[j]=rint((quantlist[j]-min)/mindel);
 162       if(ilog(c.quantlist[j])>c.q_quant)c.q_quant=ilog(c.quantlist[j]);
 163     }
 164   }
 165
 166   /* build the [default] codeword lengths */
 167   memset(c.lengthlist,0,sizeof(long)*entries);
 168   for(i=0;i<entries;i++)hits[i]=1;
 169   build_tree_from_lengths(entries,hits,c.lengthlist);
 170
 171   /* save the book in C header form */
 172   write_codebook(stdout,name,&c);
 173   fprintf(stderr,"\r                                                     "
 174           "\nDone.\n");
 175   exit(0);
 176 }