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 
_best(codebook * book,float * a,int step)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;
get_line(FILE * in)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 
get_line_value(FILE * in,float * value)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 
get_next_value(FILE * in,float * value)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 
get_next_ivalue(FILE * in,long * ivalue)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;
reset_next_value(void)168 void reset_next_value(void){
169   value_line_buff=NULL;
170   sequence_base=0.f;
171   v_sofar=0;
172 }
173 
setup_line(FILE * in)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 
get_vector(codebook * b,FILE * in,int start,int n,float * a)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 */
find_seek_to(FILE * in,char * s)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 
codebook_load(char * filename)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 
spinnit(char * s,int n)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 
build_tree_from_lengths(int vals,long * hist,long * lengths)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 */
build_tree_from_lengths0(int vals,long * hist,long * lengths)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 
write_codebook(FILE * out,char * name,const static_codebook * c)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