cannam@86: /********************************************************************
cannam@86:  *                                                                  *
cannam@86:  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
cannam@86:  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
cannam@86:  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
cannam@86:  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
cannam@86:  *                                                                  *
cannam@86:  * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2010             *
cannam@86:  * by the Xiph.Org Foundation http://www.xiph.org/                  *
cannam@86:  *                                                                  *
cannam@86:  ********************************************************************
cannam@86: 
cannam@86:  function: utility functions for loading .vqh and .vqd files
cannam@86:  last mod: $Id: bookutil.c 16959 2010-03-10 16:03:11Z xiphmont $
cannam@86: 
cannam@86:  ********************************************************************/
cannam@86: 
cannam@86: #include <stdlib.h>
cannam@86: #include <stdio.h>
cannam@86: #include <math.h>
cannam@86: #include <string.h>
cannam@86: #include <errno.h>
cannam@86: #include "bookutil.h"
cannam@86: 
cannam@86: int _best(codebook *book, float *a, int step){
cannam@86: 
cannam@86:   int dim=book->dim;
cannam@86:   int i,j,o;
cannam@86:   int minval=book->minval;
cannam@86:   int del=book->delta;
cannam@86:   int qv=book->quantvals;
cannam@86:   int ze=(qv>>1);
cannam@86:   int index=0;
cannam@86:   /* assumes integer/centered encoder codebook maptype 1 no more than dim 8 */
cannam@86: 
cannam@86:   if(del!=1){
cannam@86:     for(i=0,o=step*(dim-1);i<dim;i++,o-=step){
cannam@86:       int v = ((int)rint(a[o])-minval+(del>>1))/del;
cannam@86:       int m = (v<ze ? ((ze-v)<<1)-1 : ((v-ze)<<1));
cannam@86:       index = index*qv+ (m<0?0:(m>=qv?qv-1:m));
cannam@86:     }
cannam@86:   }else{
cannam@86:     for(i=0,o=step*(dim-1);i<dim;i++,o-=step){
cannam@86:       int v = (int)rint(a[o])-minval;
cannam@86:       int m = (v<ze ? ((ze-v)<<1)-1 : ((v-ze)<<1));
cannam@86:       index = index*qv+ (m<0?0:(m>=qv?qv-1:m));
cannam@86:     }
cannam@86:   }
cannam@86: 
cannam@86:   if(book->c->lengthlist[index]<=0){
cannam@86:     const static_codebook *c=book->c;
cannam@86:     int best=-1;
cannam@86:     /* assumes integer/centered encoder codebook maptype 1 no more than dim 8 */
cannam@86:     int e[8]={0,0,0,0,0,0,0,0};
cannam@86:     int maxval = book->minval + book->delta*(book->quantvals-1);
cannam@86:     for(i=0;i<book->entries;i++){
cannam@86:       if(c->lengthlist[i]>0){
cannam@86:         float this=0;
cannam@86:         for(j=0;j<dim;j++){
cannam@86:           float val=(e[j]-a[j*step]);
cannam@86:           this+=val*val;
cannam@86:         }
cannam@86:         if(best==-1 || this<best){
cannam@86:           best=this;
cannam@86:           index=i;
cannam@86:         }
cannam@86:       }
cannam@86:       /* assumes the value patterning created by the tools in vq/ */
cannam@86:       j=0;
cannam@86:       while(e[j]>=maxval)
cannam@86:         e[j++]=0;
cannam@86:       if(e[j]>=0)
cannam@86:         e[j]+=book->delta;
cannam@86:       e[j]= -e[j];
cannam@86:     }
cannam@86:   }
cannam@86: 
cannam@86:   return index;
cannam@86: }
cannam@86: 
cannam@86: /* A few little utils for reading files */
cannam@86: /* read a line.  Use global, persistent buffering */
cannam@86: static char *linebuffer=NULL;
cannam@86: static int  lbufsize=0;
cannam@86: char *get_line(FILE *in){
cannam@86:   long sofar=0;
cannam@86:   if(feof(in))return NULL;
cannam@86: 
cannam@86:   while(1){
cannam@86:     int gotline=0;
cannam@86: 
cannam@86:     while(!gotline){
cannam@86:       if(sofar+1>=lbufsize){
cannam@86:         if(!lbufsize){  
cannam@86:           lbufsize=1024;
cannam@86:           linebuffer=_ogg_malloc(lbufsize);
cannam@86:         }else{
cannam@86:           lbufsize*=2;
cannam@86:           linebuffer=_ogg_realloc(linebuffer,lbufsize);
cannam@86:         }
cannam@86:       }
cannam@86:       {
cannam@86:         long c=fgetc(in);
cannam@86:         switch(c){
cannam@86:         case EOF:
cannam@86:           if(sofar==0)return(NULL);
cannam@86:           /* fallthrough correct */
cannam@86:         case '\n':
cannam@86:           linebuffer[sofar]='\0';
cannam@86:           gotline=1;
cannam@86:           break;
cannam@86:         default:
cannam@86:           linebuffer[sofar++]=c;
cannam@86:           linebuffer[sofar]='\0';
cannam@86:           break;
cannam@86:         }
cannam@86:       }
cannam@86:     }
cannam@86:     
cannam@86:     if(linebuffer[0]=='#'){
cannam@86:       sofar=0;
cannam@86:     }else{
cannam@86:       return(linebuffer);
cannam@86:     }
cannam@86:   }
cannam@86: }
cannam@86: 
cannam@86: /* read the next numerical value from the given file */
cannam@86: static char *value_line_buff=NULL;
cannam@86: 
cannam@86: int get_line_value(FILE *in,float *value){
cannam@86:   char *next;
cannam@86: 
cannam@86:   if(!value_line_buff)return(-1);
cannam@86: 
cannam@86:   *value=strtod(value_line_buff, &next);
cannam@86:   if(next==value_line_buff){
cannam@86:     value_line_buff=NULL;
cannam@86:     return(-1);
cannam@86:   }else{
cannam@86:     value_line_buff=next;
cannam@86:     while(*value_line_buff>44)value_line_buff++;
cannam@86:     if(*value_line_buff==44)value_line_buff++;
cannam@86:     return(0);
cannam@86:   }
cannam@86: }
cannam@86: 
cannam@86: int get_next_value(FILE *in,float *value){
cannam@86:   while(1){
cannam@86:     if(get_line_value(in,value)){
cannam@86:       value_line_buff=get_line(in);
cannam@86:       if(!value_line_buff)return(-1);
cannam@86:     }else{
cannam@86:       return(0);
cannam@86:     }
cannam@86:   }
cannam@86: }
cannam@86: 
cannam@86: int get_next_ivalue(FILE *in,long *ivalue){
cannam@86:   float value;
cannam@86:   int ret=get_next_value(in,&value);
cannam@86:   *ivalue=value;
cannam@86:   return(ret);
cannam@86: }
cannam@86: 
cannam@86: static float sequence_base=0.f;
cannam@86: static int v_sofar=0;
cannam@86: void reset_next_value(void){
cannam@86:   value_line_buff=NULL;
cannam@86:   sequence_base=0.f;
cannam@86:   v_sofar=0;
cannam@86: }
cannam@86: 
cannam@86: char *setup_line(FILE *in){
cannam@86:   reset_next_value();
cannam@86:   value_line_buff=get_line(in);
cannam@86:   return(value_line_buff);
cannam@86: }
cannam@86: 
cannam@86: 
cannam@86: int get_vector(codebook *b,FILE *in,int start, int n,float *a){
cannam@86:   int i;
cannam@86:   const static_codebook *c=b->c;
cannam@86: 
cannam@86:   while(1){
cannam@86: 
cannam@86:     if(v_sofar==n || get_line_value(in,a)){
cannam@86:       reset_next_value();
cannam@86:       if(get_next_value(in,a))
cannam@86:         break;
cannam@86:       for(i=0;i<start;i++){
cannam@86:         sequence_base=*a;
cannam@86:         get_line_value(in,a);
cannam@86:       }
cannam@86:     }
cannam@86: 
cannam@86:     for(i=1;i<c->dim;i++)
cannam@86:       if(get_line_value(in,a+i))
cannam@86:         break;
cannam@86:     
cannam@86:     if(i==c->dim){
cannam@86:       float temp=a[c->dim-1];
cannam@86:       for(i=0;i<c->dim;i++)a[i]-=sequence_base;
cannam@86:       if(c->q_sequencep)sequence_base=temp;
cannam@86:       v_sofar++;
cannam@86:       return(0);
cannam@86:     }
cannam@86:     sequence_base=0.f;
cannam@86:   }
cannam@86: 
cannam@86:   return(-1);
cannam@86: }
cannam@86: 
cannam@86: /* read lines fromt he beginning until we find one containing the
cannam@86:    specified string */
cannam@86: char *find_seek_to(FILE *in,char *s){
cannam@86:   rewind(in);
cannam@86:   while(1){
cannam@86:     char *line=get_line(in);
cannam@86:     if(line){
cannam@86:       if(strstr(line,s))
cannam@86:         return(line);
cannam@86:     }else
cannam@86:       return(NULL);
cannam@86:   }
cannam@86: }
cannam@86: 
cannam@86: 
cannam@86: /* this reads the format as written by vqbuild/latticebuild; innocent
cannam@86:    (legal) tweaking of the file that would not affect its valid
cannam@86:    header-ness will break this routine */
cannam@86: 
cannam@86: codebook *codebook_load(char *filename){
cannam@86:   codebook *b=_ogg_calloc(1,sizeof(codebook));
cannam@86:   static_codebook *c=(static_codebook *)(b->c=_ogg_calloc(1,sizeof(static_codebook)));
cannam@86:   int quant_to_read=0;
cannam@86:   FILE *in=fopen(filename,"r");
cannam@86:   char *line;
cannam@86:   long i;
cannam@86: 
cannam@86:   if(in==NULL){
cannam@86:     fprintf(stderr,"Couldn't open codebook %s\n",filename);
cannam@86:     exit(1);
cannam@86:   }
cannam@86: 
cannam@86:   /* find the codebook struct */
cannam@86:   find_seek_to(in,"static const static_codebook ");
cannam@86: 
cannam@86:   /* get the major important values */
cannam@86:   line=get_line(in);
cannam@86:   if(sscanf(line,"%ld, %ld,",
cannam@86:             &(c->dim),&(c->entries))!=2){
cannam@86:     fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);
cannam@86:     exit(1);
cannam@86:   }
cannam@86:   line=get_line(in);
cannam@86:   line=get_line(in);
cannam@86:   if(sscanf(line,"%d, %ld, %ld, %d, %d,",
cannam@86:             &(c->maptype),&(c->q_min),&(c->q_delta),&(c->q_quant),
cannam@86:             &(c->q_sequencep))!=5){
cannam@86:     fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);
cannam@86:     exit(1);
cannam@86:   }
cannam@86:   
cannam@86:   switch(c->maptype){
cannam@86:   case 0:
cannam@86:     quant_to_read=0;
cannam@86:     break;
cannam@86:   case 1:
cannam@86:     quant_to_read=_book_maptype1_quantvals(c);
cannam@86:     break;
cannam@86:   case 2:
cannam@86:     quant_to_read=c->entries*c->dim;
cannam@86:     break;
cannam@86:   }
cannam@86:     
cannam@86:   /* load the quantized entries */
cannam@86:   find_seek_to(in,"static const long _vq_quantlist_");
cannam@86:   reset_next_value();
cannam@86:   c->quantlist=_ogg_malloc(sizeof(long)*quant_to_read);
cannam@86:   for(i=0;i<quant_to_read;i++)
cannam@86:     if(get_next_ivalue(in,c->quantlist+i)){
cannam@86:       fprintf(stderr,"out of data while reading codebook %s\n",filename);
cannam@86:       exit(1);
cannam@86:     }
cannam@86:   
cannam@86:   /* load the lengthlist */
cannam@86:   find_seek_to(in,"_lengthlist");
cannam@86:   reset_next_value();
cannam@86:   c->lengthlist=_ogg_malloc(sizeof(long)*c->entries);
cannam@86:   for(i=0;i<c->entries;i++)
cannam@86:     if(get_next_ivalue(in,c->lengthlist+i)){
cannam@86:       fprintf(stderr,"out of data while reading codebook %s\n",filename);
cannam@86:       exit(1);
cannam@86:     }
cannam@86: 
cannam@86:   /* got it all */
cannam@86:   fclose(in);
cannam@86:   
cannam@86:   vorbis_book_init_encode(b,c);
cannam@86:   b->valuelist=_book_unquantize(c,c->entries,NULL);
cannam@86: 
cannam@86:   return(b);
cannam@86: }
cannam@86: 
cannam@86: void spinnit(char *s,int n){
cannam@86:   static int p=0;
cannam@86:   static long lasttime=0;
cannam@86:   long test;
cannam@86:   struct timeval thistime;
cannam@86: 
cannam@86:   gettimeofday(&thistime,NULL);
cannam@86:   test=thistime.tv_sec*10+thistime.tv_usec/100000;
cannam@86:   if(lasttime!=test){
cannam@86:     lasttime=test;
cannam@86: 
cannam@86:     fprintf(stderr,"%s%d ",s,n);
cannam@86: 
cannam@86:     p++;if(p>3)p=0;
cannam@86:     switch(p){
cannam@86:     case 0:
cannam@86:       fprintf(stderr,"|    \r");
cannam@86:       break;
cannam@86:     case 1:
cannam@86:       fprintf(stderr,"/    \r");
cannam@86:       break;
cannam@86:     case 2:
cannam@86:       fprintf(stderr,"-    \r");
cannam@86:       break;
cannam@86:     case 3:
cannam@86:       fprintf(stderr,"\\    \r");
cannam@86:       break;
cannam@86:     }
cannam@86:     fflush(stderr);
cannam@86:   }
cannam@86: }
cannam@86: 
cannam@86: void build_tree_from_lengths(int vals, long *hist, long *lengths){
cannam@86:   int i,j;
cannam@86:   long *membership=_ogg_malloc(vals*sizeof(long));
cannam@86:   long *histsave=alloca(vals*sizeof(long));
cannam@86:   memcpy(histsave,hist,vals*sizeof(long));
cannam@86: 
cannam@86:   for(i=0;i<vals;i++)membership[i]=i;
cannam@86: 
cannam@86:   /* find codeword lengths */
cannam@86:   /* much more elegant means exist.  Brute force n^2, minimum thought */
cannam@86:   for(i=vals;i>1;i--){
cannam@86:     int first=-1,second=-1;
cannam@86:     long least=-1;
cannam@86:         
cannam@86:     spinnit("building... ",i);
cannam@86:     
cannam@86:     /* find the two nodes to join */
cannam@86:     for(j=0;j<vals;j++)
cannam@86:       if(least==-1 || hist[j]<=least){
cannam@86:         least=hist[j];
cannam@86:         first=membership[j];
cannam@86:       }
cannam@86:     least=-1;
cannam@86:     for(j=0;j<vals;j++)
cannam@86:       if((least==-1 || hist[j]<=least) && membership[j]!=first){
cannam@86:         least=hist[j];
cannam@86:         second=membership[j];
cannam@86:       }
cannam@86:     if(first==-1 || second==-1){
cannam@86:       fprintf(stderr,"huffman fault; no free branch\n");
cannam@86:       exit(1);
cannam@86:     }
cannam@86:     
cannam@86:     /* join them */
cannam@86:     least=hist[first]+hist[second];
cannam@86:     for(j=0;j<vals;j++)
cannam@86:       if(membership[j]==first || membership[j]==second){
cannam@86:         membership[j]=first;
cannam@86:         hist[j]=least;
cannam@86:         lengths[j]++;
cannam@86:       }
cannam@86:   }
cannam@86:   for(i=0;i<vals-1;i++)
cannam@86:     if(membership[i]!=membership[i+1]){
cannam@86:       fprintf(stderr,"huffman fault; failed to build single tree\n");
cannam@86:       exit(1);
cannam@86:     }
cannam@86: 
cannam@86:   /* for sanity check purposes: how many bits would it have taken to
cannam@86:      encode the training set? */
cannam@86:   {
cannam@86:     long bitsum=0;
cannam@86:     long samples=0;
cannam@86:     for(i=0;i<vals;i++){
cannam@86:       bitsum+=(histsave[i]-1)*lengths[i];
cannam@86:       samples+=histsave[i]-1;
cannam@86:     }
cannam@86: 
cannam@86:     if(samples){
cannam@86:       fprintf(stderr,"\rTotal samples in training set: %ld      \n",samples);
cannam@86:       fprintf(stderr,"\rTotal bits used to represent training set: %ld\n",
cannam@86:               bitsum);
cannam@86:     }
cannam@86:   }
cannam@86: 
cannam@86:   free(membership);
cannam@86: }
cannam@86: 
cannam@86: /* wrap build_tree_from_lengths to allow zero entries in the histogram */
cannam@86: void build_tree_from_lengths0(int vals, long *hist, long *lengths){
cannam@86: 
cannam@86:   /* pack the 'sparse' hit list into a dense list, then unpack
cannam@86:      the lengths after the build */
cannam@86: 
cannam@86:   int upper=0,i;
cannam@86:   long *lengthlist=_ogg_calloc(vals,sizeof(long));
cannam@86:   long *newhist=alloca(vals*sizeof(long));
cannam@86: 
cannam@86:   for(i=0;i<vals;i++)
cannam@86:     if(hist[i]>0)
cannam@86:       newhist[upper++]=hist[i];
cannam@86: 
cannam@86:   if(upper != vals){
cannam@86:     fprintf(stderr,"\rEliminating %d unused entries; %d entries remain\n",
cannam@86:             vals-upper,upper);
cannam@86:   }
cannam@86:     
cannam@86:   build_tree_from_lengths(upper,newhist,lengthlist);
cannam@86:       
cannam@86:   upper=0;
cannam@86:   for(i=0;i<vals;i++)
cannam@86:     if(hist[i]>0)
cannam@86:       lengths[i]=lengthlist[upper++];
cannam@86:     else
cannam@86:       lengths[i]=0;
cannam@86: 
cannam@86:   free(lengthlist);
cannam@86: }
cannam@86: 
cannam@86: void write_codebook(FILE *out,char *name,const static_codebook *c){
cannam@86:   int i,j,k;
cannam@86: 
cannam@86:   /* save the book in C header form */
cannam@86: 
cannam@86:   /* first, the static vectors, then the book structure to tie it together. */
cannam@86:   /* quantlist */
cannam@86:   if(c->quantlist){
cannam@86:     long vals=(c->maptype==1?_book_maptype1_quantvals(c):c->entries*c->dim);
cannam@86:     fprintf(out,"static const long _vq_quantlist_%s[] = {\n",name);
cannam@86:     for(j=0;j<vals;j++){
cannam@86:       fprintf(out,"\t%ld,\n",c->quantlist[j]);
cannam@86:     }
cannam@86:     fprintf(out,"};\n\n");
cannam@86:   }
cannam@86: 
cannam@86:   /* lengthlist */
cannam@86:   fprintf(out,"static const long _vq_lengthlist_%s[] = {\n",name);
cannam@86:   for(j=0;j<c->entries;){
cannam@86:     fprintf(out,"\t");
cannam@86:     for(k=0;k<16 && j<c->entries;k++,j++)
cannam@86:       fprintf(out,"%2ld,",c->lengthlist[j]);
cannam@86:     fprintf(out,"\n");
cannam@86:   }
cannam@86:   fprintf(out,"};\n\n");
cannam@86: 
cannam@86:   /* tie it all together */
cannam@86:   
cannam@86:   fprintf(out,"static const static_codebook %s = {\n",name);
cannam@86:   
cannam@86:   fprintf(out,"\t%ld, %ld,\n",c->dim,c->entries);
cannam@86:   fprintf(out,"\t(long *)_vq_lengthlist_%s,\n",name);
cannam@86:   fprintf(out,"\t%d, %ld, %ld, %d, %d,\n",
cannam@86:           c->maptype,c->q_min,c->q_delta,c->q_quant,c->q_sequencep);
cannam@86:   if(c->quantlist)
cannam@86:     fprintf(out,"\t(long *)_vq_quantlist_%s,\n",name);
cannam@86:   else
cannam@86:     fprintf(out,"\tNULL,\n");
cannam@86: 
cannam@86:   fprintf(out,"\t0\n};\n\n");
cannam@86: }