Dependencies/libvorbis/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-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 }