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