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