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