Home | History | Annotate | Download | only in vq 
      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-2010             *
      9  * by the Xiph.Org Foundation http://www.xiph.org/                  *
     10  *                                                                  *
     11  ********************************************************************
     12 
     13  function: utility functions for loading .vqh and .vqd files
     14  last mod: $Id: bookutil.c 16959 2010-03-10 16:03:11Z xiphmont $
     15 
     16  ********************************************************************/
     17 
     18 #include <stdlib.h>
     19 #include <stdio.h>
     20 #include <math.h>
     21 #include <string.h>
     22 #include <errno.h>
     23 #include "bookutil.h"
     24 
     25 int _best(codebook *book, float *a, int step){
     26 
     27   int dim=book->dim;
     28   int i,j,o;
     29   int minval=book->minval;
     30   int del=book->delta;
     31   int qv=book->quantvals;
     32   int ze=(qv>>1);
     33   int index=0;
     34   /* assumes integer/centered encoder codebook maptype 1 no more than dim 8 */
     35 
     36   if(del!=1){
     37     for(i=0,o=step*(dim-1);i<dim;i++,o-=step){
     38       int v = ((int)rint(a[o])-minval+(del>>1))/del;
     39       int m = (v<ze ? ((ze-v)<<1)-1 : ((v-ze)<<1));
     40       index = index*qv+ (m<0?0:(m>=qv?qv-1:m));
     41     }
     42   }else{
     43     for(i=0,o=step*(dim-1);i<dim;i++,o-=step){
     44       int v = (int)rint(a[o])-minval;
     45       int m = (v<ze ? ((ze-v)<<1)-1 : ((v-ze)<<1));
     46       index = index*qv+ (m<0?0:(m>=qv?qv-1:m));
     47     }
     48   }
     49 
     50   if(book->c->lengthlist[index]<=0){
     51     const static_codebook *c=book->c;
     52     int best=-1;
     53     /* assumes integer/centered encoder codebook maptype 1 no more than dim 8 */
     54     int e[8]={0,0,0,0,0,0,0,0};
     55     int maxval = book->minval + book->delta*(book->quantvals-1);
     56     for(i=0;i<book->entries;i++){
     57       if(c->lengthlist[i]>0){
     58         float this=0;
     59         for(j=0;j<dim;j++){
     60           float val=(e[j]-a[j*step]);
     61           this+=val*val;
     62         }
     63         if(best==-1 || this<best){
     64           best=this;
     65           index=i;
     66         }
     67       }
     68       /* assumes the value patterning created by the tools in vq/ */
     69       j=0;
     70       while(e[j]>=maxval)
     71         e[j++]=0;
     72       if(e[j]>=0)
     73         e[j]+=book->delta;
     74       e[j]= -e[j];
     75     }
     76   }
     77 
     78   return index;
     79 }
     80 
     81 /* A few little utils for reading files */
     82 /* read a line.  Use global, persistent buffering */
     83 static char *linebuffer=NULL;
     84 static int  lbufsize=0;
     85 char *get_line(FILE *in){
     86   long sofar=0;
     87   if(feof(in))return NULL;
     88 
     89   while(1){
     90     int gotline=0;
     91 
     92     while(!gotline){
     93       if(sofar+1>=lbufsize){
     94         if(!lbufsize){
     95           lbufsize=1024;
     96           linebuffer=_ogg_malloc(lbufsize);
     97         }else{
     98           lbufsize*=2;
     99           linebuffer=_ogg_realloc(linebuffer,lbufsize);
    100         }
    101       }
    102       {
    103         long c=fgetc(in);
    104         switch(c){
    105         case EOF:
    106           if(sofar==0)return(NULL);
    107           /* fallthrough correct */
    108         case '\n':
    109           linebuffer[sofar]='\0';
    110           gotline=1;
    111           break;
    112         default:
    113           linebuffer[sofar++]=c;
    114           linebuffer[sofar]='\0';
    115           break;
    116         }
    117       }
    118     }
    119 
    120     if(linebuffer[0]=='#'){
    121       sofar=0;
    122     }else{
    123       return(linebuffer);
    124     }
    125   }
    126 }
    127 
    128 /* read the next numerical value from the given file */
    129 static char *value_line_buff=NULL;
    130 
    131 int get_line_value(FILE *in,float *value){
    132   char *next;
    133 
    134   if(!value_line_buff)return(-1);
    135 
    136   *value=strtod(value_line_buff, &next);
    137   if(next==value_line_buff){
    138     value_line_buff=NULL;
    139     return(-1);
    140   }else{
    141     value_line_buff=next;
    142     while(*value_line_buff>44)value_line_buff++;
    143     if(*value_line_buff==44)value_line_buff++;
    144     return(0);
    145   }
    146 }
    147 
    148 int get_next_value(FILE *in,float *value){
    149   while(1){
    150     if(get_line_value(in,value)){
    151       value_line_buff=get_line(in);
    152       if(!value_line_buff)return(-1);
    153     }else{
    154       return(0);
    155     }
    156   }
    157 }
    158 
    159 int get_next_ivalue(FILE *in,long *ivalue){
    160   float value;
    161   int ret=get_next_value(in,&value);
    162   *ivalue=value;
    163   return(ret);
    164 }
    165 
    166 static float sequence_base=0.f;
    167 static int v_sofar=0;
    168 void reset_next_value(void){
    169   value_line_buff=NULL;
    170   sequence_base=0.f;
    171   v_sofar=0;
    172 }
    173 
    174 char *setup_line(FILE *in){
    175   reset_next_value();
    176   value_line_buff=get_line(in);
    177   return(value_line_buff);
    178 }
    179 
    180 
    181 int get_vector(codebook *b,FILE *in,int start, int n,float *a){
    182   int i;
    183   const static_codebook *c=b->c;
    184 
    185   while(1){
    186 
    187     if(v_sofar==n || get_line_value(in,a)){
    188       reset_next_value();
    189       if(get_next_value(in,a))
    190         break;
    191       for(i=0;i<start;i++){
    192         sequence_base=*a;
    193         get_line_value(in,a);
    194       }
    195     }
    196 
    197     for(i=1;i<c->dim;i++)
    198       if(get_line_value(in,a+i))
    199         break;
    200 
    201     if(i==c->dim){
    202       float temp=a[c->dim-1];
    203       for(i=0;i<c->dim;i++)a[i]-=sequence_base;
    204       if(c->q_sequencep)sequence_base=temp;
    205       v_sofar++;
    206       return(0);
    207     }
    208     sequence_base=0.f;
    209   }
    210 
    211   return(-1);
    212 }
    213 
    214 /* read lines fromt he beginning until we find one containing the
    215    specified string */
    216 char *find_seek_to(FILE *in,char *s){
    217   rewind(in);
    218   while(1){
    219     char *line=get_line(in);
    220     if(line){
    221       if(strstr(line,s))
    222         return(line);
    223     }else
    224       return(NULL);
    225   }
    226 }
    227 
    228 
    229 /* this reads the format as written by vqbuild/latticebuild; innocent
    230    (legal) tweaking of the file that would not affect its valid
    231    header-ness will break this routine */
    232 
    233 codebook *codebook_load(char *filename){
    234   codebook *b=_ogg_calloc(1,sizeof(codebook));
    235   static_codebook *c=(static_codebook *)(b->c=_ogg_calloc(1,sizeof(static_codebook)));
    236   int quant_to_read=0;
    237   FILE *in=fopen(filename,"r");
    238   char *line;
    239   long i;
    240 
    241   if(in==NULL){
    242     fprintf(stderr,"Couldn't open codebook %s\n",filename);
    243     exit(1);
    244   }
    245 
    246   /* find the codebook struct */
    247   find_seek_to(in,"static const static_codebook ");
    248 
    249   /* get the major important values */
    250   line=get_line(in);
    251   if(sscanf(line,"%ld, %ld,",
    252             &(c->dim),&(c->entries))!=2){
    253     fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);
    254     exit(1);
    255   }
    256   line=get_line(in);
    257   line=get_line(in);
    258   if(sscanf(line,"%d, %ld, %ld, %d, %d,",
    259             &(c->maptype),&(c->q_min),&(c->q_delta),&(c->q_quant),
    260             &(c->q_sequencep))!=5){
    261     fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);
    262     exit(1);
    263   }
    264 
    265   switch(c->maptype){
    266   case 0:
    267     quant_to_read=0;
    268     break;
    269   case 1:
    270     quant_to_read=_book_maptype1_quantvals(c);
    271     break;
    272   case 2:
    273     quant_to_read=c->entries*c->dim;
    274     break;
    275   }
    276 
    277   /* load the quantized entries */
    278   find_seek_to(in,"static const long _vq_quantlist_");
    279   reset_next_value();
    280   c->quantlist=_ogg_malloc(sizeof(long)*quant_to_read);
    281   for(i=0;i<quant_to_read;i++)
    282     if(get_next_ivalue(in,c->quantlist+i)){
    283       fprintf(stderr,"out of data while reading codebook %s\n",filename);
    284       exit(1);
    285     }
    286 
    287   /* load the lengthlist */
    288   find_seek_to(in,"_lengthlist");
    289   reset_next_value();
    290   c->lengthlist=_ogg_malloc(sizeof(long)*c->entries);
    291   for(i=0;i<c->entries;i++)
    292     if(get_next_ivalue(in,c->lengthlist+i)){
    293       fprintf(stderr,"out of data while reading codebook %s\n",filename);
    294       exit(1);
    295     }
    296 
    297   /* got it all */
    298   fclose(in);
    299 
    300   vorbis_book_init_encode(b,c);
    301   b->valuelist=_book_unquantize(c,c->entries,NULL);
    302 
    303   return(b);
    304 }
    305 
    306 void spinnit(char *s,int n){
    307   static int p=0;
    308   static long lasttime=0;
    309   long test;
    310   struct timeval thistime;
    311 
    312   gettimeofday(&thistime,NULL);
    313   test=thistime.tv_sec*10+thistime.tv_usec/100000;
    314   if(lasttime!=test){
    315     lasttime=test;
    316 
    317     fprintf(stderr,"%s%d ",s,n);
    318 
    319     p++;if(p>3)p=0;
    320     switch(p){
    321     case 0:
    322       fprintf(stderr,"|    \r");
    323       break;
    324     case 1:
    325       fprintf(stderr,"/    \r");
    326       break;
    327     case 2:
    328       fprintf(stderr,"-    \r");
    329       break;
    330     case 3:
    331       fprintf(stderr,"\\    \r");
    332       break;
    333     }
    334     fflush(stderr);
    335   }
    336 }
    337 
    338 void build_tree_from_lengths(int vals, long *hist, long *lengths){
    339   int i,j;
    340   long *membership=_ogg_malloc(vals*sizeof(long));
    341   long *histsave=alloca(vals*sizeof(long));
    342   memcpy(histsave,hist,vals*sizeof(long));
    343 
    344   for(i=0;i<vals;i++)membership[i]=i;
    345 
    346   /* find codeword lengths */
    347   /* much more elegant means exist.  Brute force n^2, minimum thought */
    348   for(i=vals;i>1;i--){
    349     int first=-1,second=-1;
    350     long least=-1;
    351 
    352     spinnit("building... ",i);
    353 
    354     /* find the two nodes to join */
    355     for(j=0;j<vals;j++)
    356       if(least==-1 || hist[j]<=least){
    357         least=hist[j];
    358         first=membership[j];
    359       }
    360     least=-1;
    361     for(j=0;j<vals;j++)
    362       if((least==-1 || hist[j]<=least) && membership[j]!=first){
    363         least=hist[j];
    364         second=membership[j];
    365       }
    366     if(first==-1 || second==-1){
    367       fprintf(stderr,"huffman fault; no free branch\n");
    368       exit(1);
    369     }
    370 
    371     /* join them */
    372     least=hist[first]+hist[second];
    373     for(j=0;j<vals;j++)
    374       if(membership[j]==first || membership[j]==second){
    375         membership[j]=first;
    376         hist[j]=least;
    377         lengths[j]++;
    378       }
    379   }
    380   for(i=0;i<vals-1;i++)
    381     if(membership[i]!=membership[i+1]){
    382       fprintf(stderr,"huffman fault; failed to build single tree\n");
    383       exit(1);
    384     }
    385 
    386   /* for sanity check purposes: how many bits would it have taken to
    387      encode the training set? */
    388   {
    389     long bitsum=0;
    390     long samples=0;
    391     for(i=0;i<vals;i++){
    392       bitsum+=(histsave[i]-1)*lengths[i];
    393       samples+=histsave[i]-1;
    394     }
    395 
    396     if(samples){
    397       fprintf(stderr,"\rTotal samples in training set: %ld      \n",samples);
    398       fprintf(stderr,"\rTotal bits used to represent training set: %ld\n",
    399               bitsum);
    400     }
    401   }
    402 
    403   free(membership);
    404 }
    405 
    406 /* wrap build_tree_from_lengths to allow zero entries in the histogram */
    407 void build_tree_from_lengths0(int vals, long *hist, long *lengths){
    408 
    409   /* pack the 'sparse' hit list into a dense list, then unpack
    410      the lengths after the build */
    411 
    412   int upper=0,i;
    413   long *lengthlist=_ogg_calloc(vals,sizeof(long));
    414   long *newhist=alloca(vals*sizeof(long));
    415 
    416   for(i=0;i<vals;i++)
    417     if(hist[i]>0)
    418       newhist[upper++]=hist[i];
    419 
    420   if(upper != vals){
    421     fprintf(stderr,"\rEliminating %d unused entries; %d entries remain\n",
    422             vals-upper,upper);
    423   }
    424 
    425   build_tree_from_lengths(upper,newhist,lengthlist);
    426 
    427   upper=0;
    428   for(i=0;i<vals;i++)
    429     if(hist[i]>0)
    430       lengths[i]=lengthlist[upper++];
    431     else
    432       lengths[i]=0;
    433 
    434   free(lengthlist);
    435 }
    436 
    437 void write_codebook(FILE *out,char *name,const static_codebook *c){
    438   int i,j,k;
    439 
    440   /* save the book in C header form */
    441 
    442   /* first, the static vectors, then the book structure to tie it together. */
    443   /* quantlist */
    444   if(c->quantlist){
    445     long vals=(c->maptype==1?_book_maptype1_quantvals(c):c->entries*c->dim);
    446     fprintf(out,"static const long _vq_quantlist_%s[] = {\n",name);
    447     for(j=0;j<vals;j++){
    448       fprintf(out,"\t%ld,\n",c->quantlist[j]);
    449     }
    450     fprintf(out,"};\n\n");
    451   }
    452 
    453   /* lengthlist */
    454   fprintf(out,"static const long _vq_lengthlist_%s[] = {\n",name);
    455   for(j=0;j<c->entries;){
    456     fprintf(out,"\t");
    457     for(k=0;k<16 && j<c->entries;k++,j++)
    458       fprintf(out,"%2ld,",c->lengthlist[j]);
    459     fprintf(out,"\n");
    460   }
    461   fprintf(out,"};\n\n");
    462 
    463   /* tie it all together */
    464 
    465   fprintf(out,"static const static_codebook %s = {\n",name);
    466 
    467   fprintf(out,"\t%ld, %ld,\n",c->dim,c->entries);
    468   fprintf(out,"\t(long *)_vq_lengthlist_%s,\n",name);
    469   fprintf(out,"\t%d, %ld, %ld, %d, %d,\n",
    470           c->maptype,c->q_min,c->q_delta,c->q_quant,c->q_sequencep);
    471   if(c->quantlist)
    472     fprintf(out,"\t(long *)_vq_quantlist_%s,\n",name);
    473   else
    474     fprintf(out,"\tNULL,\n");
    475 
    476   fprintf(out,"\t0\n};\n\n");
    477 }
    478