1 /********************************************************************
3 * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE. *
4 * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
5 * THE GNU LESSER/LIBRARY PUBLIC LICENSE, WHICH IS INCLUDED WITH *
6 * THIS SOURCE. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. *
8 * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2000 *
9 * by Monty <monty@xiph.org> and the XIPHOPHORUS Company *
10 * http://www.xiph.org/ *
12 ********************************************************************
14 function: utility functions for loading .vqh and .vqd files
15 last mod: $Id: bookutil.c,v 1.19 2000/11/08 03:23:23 xiphmont Exp $
17 ********************************************************************/
26 /* A few little utils for reading files */
27 /* read a line. Use global, persistent buffering */
28 static char *linebuffer=NULL;
29 static int lbufsize=0;
30 char *get_line(FILE *in){
32 if(feof(in))return NULL;
38 if(sofar+1>=lbufsize){
41 linebuffer=_ogg_malloc(lbufsize);
44 linebuffer=_ogg_realloc(linebuffer,lbufsize);
51 if(sofar==0)return(NULL);
52 /* fallthrough correct */
54 linebuffer[sofar]='\0';
58 linebuffer[sofar++]=c;
59 linebuffer[sofar]='\0';
65 if(linebuffer[0]=='#'){
73 /* read the next numerical value from the given file */
74 static char *value_line_buff=NULL;
76 int get_line_value(FILE *in,float *value){
79 if(!value_line_buff)return(-1);
81 *value=strtod(value_line_buff, &next);
82 if(next==value_line_buff){
87 while(*value_line_buff>44)value_line_buff++;
88 if(*value_line_buff==44)value_line_buff++;
93 int get_next_value(FILE *in,float *value){
95 if(get_line_value(in,value)){
96 value_line_buff=get_line(in);
97 if(!value_line_buff)return(-1);
104 int get_next_ivalue(FILE *in,long *ivalue){
106 int ret=get_next_value(in,&value);
111 static float sequence_base=0.;
112 static int v_sofar=0;
113 void reset_next_value(void){
114 value_line_buff=NULL;
119 char *setup_line(FILE *in){
121 value_line_buff=get_line(in);
122 return(value_line_buff);
126 int get_vector(codebook *b,FILE *in,int start, int n,float *a){
128 const static_codebook *c=b->c;
132 if(v_sofar==n || get_line_value(in,a)){
134 if(get_next_value(in,a))
136 for(i=0;i<start;i++){
138 get_line_value(in,a);
142 for(i=1;i<c->dim;i++)
143 if(get_line_value(in,a+i))
147 float temp=a[c->dim-1];
148 for(i=0;i<c->dim;i++)a[i]-=sequence_base;
149 if(c->q_sequencep)sequence_base=temp;
159 /* read lines fromt he beginning until we find one containing the
161 char *find_seek_to(FILE *in,char *s){
164 char *line=get_line(in);
174 /* this reads the format as written by vqbuild/latticebuild; innocent
175 (legal) tweaking of the file that would not affect its valid
176 header-ness will break this routine */
178 codebook *codebook_load(char *filename){
179 codebook *b=_ogg_calloc(1,sizeof(codebook));
180 static_codebook *c=(static_codebook *)(b->c=_ogg_calloc(1,sizeof(static_codebook)));
181 encode_aux_nearestmatch *a=NULL;
182 encode_aux_threshmatch *t=NULL;
183 encode_aux_pigeonhole *p=NULL;
185 FILE *in=fopen(filename,"r");
190 fprintf(stderr,"Couldn't open codebook %s\n",filename);
194 /* find the codebook struct */
195 find_seek_to(in,"static static_codebook _vq_book_");
197 /* get the major important values */
199 if(sscanf(line,"%ld, %ld,",
200 &(c->dim),&(c->entries))!=2){
201 fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);
206 if(sscanf(line,"%d, %ld, %ld, %d, %d,",
207 &(c->maptype),&(c->q_min),&(c->q_delta),&(c->q_quant),
208 &(c->q_sequencep))!=5){
209 fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);
213 /* find the auxiliary encode struct[s] (if any) */
214 if(find_seek_to(in,"static encode_aux_nearestmatch _vq_aux")){
216 c->nearest_tree=a=_ogg_calloc(1,sizeof(encode_aux_nearestmatch));
222 if(sscanf(line,"%ld, %ld",&(a->aux),&(a->alloc))!=2){
223 fprintf(stderr,"2: syntax in %s in line:\t %s",filename,line);
228 find_seek_to(in,"static long _vq_ptr0");
230 a->ptr0=_ogg_malloc(sizeof(long)*a->aux);
231 for(i=0;i<a->aux;i++)
232 if(get_next_ivalue(in,a->ptr0+i)){
233 fprintf(stderr,"out of data while reading codebook %s\n",filename);
238 find_seek_to(in,"static long _vq_ptr1");
240 a->ptr1=_ogg_malloc(sizeof(long)*a->aux);
241 for(i=0;i<a->aux;i++)
242 if(get_next_ivalue(in,a->ptr1+i)){
243 fprintf(stderr,"out of data while reading codebook %s\n",filename);
249 find_seek_to(in,"static long _vq_p_");
251 a->p=_ogg_malloc(sizeof(long)*a->aux);
252 for(i=0;i<a->aux;i++)
253 if(get_next_ivalue(in,a->p+i)){
254 fprintf(stderr,"out of data while reading codebook %s\n",filename);
259 find_seek_to(in,"static long _vq_q_");
261 a->q=_ogg_malloc(sizeof(long)*a->aux);
262 for(i=0;i<a->aux;i++)
263 if(get_next_ivalue(in,a->q+i)){
264 fprintf(stderr,"out of data while reading codebook %s\n",filename);
269 if(find_seek_to(in,"static encode_aux_threshmatch _vq_aux")){
271 c->thresh_tree=t=_ogg_calloc(1,sizeof(encode_aux_threshmatch));
275 if(sscanf(line,"%d",&(t->quantvals))!=1){
276 fprintf(stderr,"3: syntax in %s in line:\t %s",filename,line);
280 if(sscanf(line,"%d",&(t->threshvals))!=1){
281 fprintf(stderr,"4: syntax in %s in line:\t %s",filename,line);
284 /* load quantthresh */
285 find_seek_to(in,"static float _vq_quantthresh_");
287 t->quantthresh=_ogg_malloc(sizeof(float)*t->threshvals);
288 for(i=0;i<t->threshvals-1;i++)
289 if(get_next_value(in,t->quantthresh+i)){
290 fprintf(stderr,"out of data 1 while reading codebook %s\n",filename);
294 find_seek_to(in,"static long _vq_quantmap_");
296 t->quantmap=_ogg_malloc(sizeof(long)*t->threshvals);
297 for(i=0;i<t->threshvals;i++)
298 if(get_next_ivalue(in,t->quantmap+i)){
299 fprintf(stderr,"out of data 2 while reading codebook %s\n",filename);
304 if(find_seek_to(in,"static encode_aux_pigeonhole _vq_aux")){
307 c->pigeon_tree=p=_ogg_calloc(1,sizeof(encode_aux_pigeonhole));
309 if(sscanf(line,"%f, %f, %d, %d",&(p->min),&(p->del),
310 &(p->mapentries),&(p->quantvals))!=4){
311 fprintf(stderr,"5: syntax in %s in line:\t %s",filename,line);
316 if(sscanf(line,"%ld",&(p->fittotal))!=1){
317 fprintf(stderr,"6: syntax in %s in line:\t %s",filename,line);
321 find_seek_to(in,"static long _vq_pigeonmap_");
323 p->pigeonmap=_ogg_malloc(sizeof(long)*p->mapentries);
324 for(i=0;i<p->mapentries;i++)
325 if(get_next_ivalue(in,p->pigeonmap+i)){
326 fprintf(stderr,"out of data (pigeonmap) while reading codebook %s\n",filename);
330 find_seek_to(in,"static long _vq_fitlist_");
332 p->fitlist=_ogg_malloc(sizeof(long)*p->fittotal);
333 for(i=0;i<p->fittotal;i++)
334 if(get_next_ivalue(in,p->fitlist+i)){
335 fprintf(stderr,"out of data (fitlist) while reading codebook %s\n",filename);
339 find_seek_to(in,"static long _vq_fitmap_");
341 for(i=0;i<c->dim;i++)pigeons*=p->quantvals;
342 p->fitmap=_ogg_malloc(sizeof(long)*pigeons);
343 for(i=0;i<pigeons;i++)
344 if(get_next_ivalue(in,p->fitmap+i)){
345 fprintf(stderr,"out of data (fitmap) while reading codebook %s\n",filename);
350 find_seek_to(in,"static long _vq_fitlength_");
352 p->fitlength=_ogg_malloc(sizeof(long)*pigeons);
353 for(i=0;i<pigeons;i++)
354 if(get_next_ivalue(in,p->fitlength+i)){
355 fprintf(stderr,"out of data (fitlength) while reading codebook %s\n",filename);
365 quant_to_read=_book_maptype1_quantvals(c);
368 quant_to_read=c->entries*c->dim;
372 /* load the quantized entries */
373 find_seek_to(in,"static long _vq_quantlist_");
375 c->quantlist=_ogg_malloc(sizeof(long)*quant_to_read);
376 for(i=0;i<quant_to_read;i++)
377 if(get_next_ivalue(in,c->quantlist+i)){
378 fprintf(stderr,"out of data while reading codebook %s\n",filename);
382 /* load the lengthlist */
383 find_seek_to(in,"static long _vq_lengthlist");
385 c->lengthlist=_ogg_malloc(sizeof(long)*c->entries);
386 for(i=0;i<c->entries;i++)
387 if(get_next_ivalue(in,c->lengthlist+i)){
388 fprintf(stderr,"out of data while reading codebook %s\n",filename);
395 vorbis_book_init_encode(b,c);
400 void spinnit(char *s,int n){
402 static long lasttime=0;
404 struct timeval thistime;
406 gettimeofday(&thistime,NULL);
407 test=thistime.tv_sec*10+thistime.tv_usec/100000;
411 fprintf(stderr,"%s%d ",s,n);
416 fprintf(stderr,"| \r");
419 fprintf(stderr,"/ \r");
422 fprintf(stderr,"- \r");
425 fprintf(stderr,"\\ \r");
432 void build_tree_from_lengths(int vals, long *hist, long *lengths){
434 long *membership=_ogg_malloc(vals*sizeof(long));
435 long *histsave=alloca(vals*sizeof(long));
436 memcpy(histsave,hist,vals*sizeof(long));
438 for(i=0;i<vals;i++)membership[i]=i;
440 /* find codeword lengths */
441 /* much more elegant means exist. Brute force n^2, minimum thought */
443 int first=-1,second=-1;
446 spinnit("building... ",i);
448 /* find the two nodes to join */
450 if(least==-1 || hist[j]<least){
456 if((least==-1 || hist[j]<least) && membership[j]!=first){
458 second=membership[j];
460 if(first==-1 || second==-1){
461 fprintf(stderr,"huffman fault; no free branch\n");
466 least=hist[first]+hist[second];
468 if(membership[j]==first || membership[j]==second){
474 for(i=0;i<vals-1;i++)
475 if(membership[i]!=membership[i+1]){
476 fprintf(stderr,"huffman fault; failed to build single tree\n");
480 /* for sanity check purposes: how many bits would it have taken to
481 encode the training set? */
486 bitsum+=(histsave[i]-1)*lengths[i];
487 samples+=histsave[i]-1;
491 fprintf(stderr,"\rTotal samples in training set: %ld \n",samples);
492 fprintf(stderr,"\rTotal bits used to represent training set: %ld\n",
500 /* wrap build_tree_from_lengths to allow zero entries in the histogram */
501 void build_tree_from_lengths0(int vals, long *hist, long *lengths){
503 /* pack the 'sparse' hit list into a dense list, then unpack
504 the lengths after the build */
507 long *lengthlist=_ogg_calloc(vals,sizeof(long));
508 long *newhist=alloca(vals*sizeof(long));
512 newhist[upper++]=hist[i];
515 fprintf(stderr,"\rEliminating %d unused entries; %d entries remain\n",
519 build_tree_from_lengths(upper,newhist,lengthlist);
524 lengths[i]=lengthlist[upper++];
531 void write_codebook(FILE *out,char *name,const static_codebook *c){
532 encode_aux_pigeonhole *p=c->pigeon_tree;
533 encode_aux_threshmatch *t=c->thresh_tree;
534 encode_aux_nearestmatch *n=c->nearest_tree;
537 /* save the book in C header form */
539 "/********************************************************************\n"
541 " * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE. *\n"
542 " * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *\n"
543 " * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE. *\n"
544 " * PLEASE READ THESE TERMS DISTRIBUTING. *\n"
546 " * THE OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-1999 *\n"
547 " * by 1999 Monty <monty@xiph.org> and The XIPHOPHORUS Company *\n"
548 " * http://www.xiph.org/ *\n"
550 " ********************************************************************\n"
552 " function: static codebook autogenerated by vq/somethingorother\n"
554 " ********************************************************************/\n\n");
556 fprintf(out,"#ifndef _V_%s_VQH_\n#define _V_%s_VQH_\n",name,name);
557 fprintf(out,"#include \"codebook.h\"\n\n");
559 /* first, the static vectors, then the book structure to tie it together. */
562 long vals=(c->maptype==1?_book_maptype1_quantvals(c):c->entries*c->dim);
563 fprintf(out,"static long _vq_quantlist_%s[] = {\n",name);
565 fprintf(out,"\t%ld,\n",c->quantlist[j]);
567 fprintf(out,"};\n\n");
571 fprintf(out,"static long _vq_lengthlist_%s[] = {\n",name);
572 for(j=0;j<c->entries;){
574 for(k=0;k<16 && j<c->entries;k++,j++)
575 fprintf(out,"%2ld,",c->lengthlist[j]);
578 fprintf(out,"};\n\n");
582 fprintf(out,"static float _vq_quantthresh_%s[] = {\n",name);
583 for(j=0;j<t->threshvals-1;){
585 for(k=0;k<8 && j<t->threshvals-1;k++,j++)
586 fprintf(out,"%.5g, ",t->quantthresh[j]);
589 fprintf(out,"};\n\n");
592 fprintf(out,"static long _vq_quantmap_%s[] = {\n",name);
593 for(j=0;j<t->threshvals;){
595 for(k=0;k<8 && j<t->threshvals;k++,j++)
596 fprintf(out,"%5ld,",t->quantmap[j]);
599 fprintf(out,"};\n\n");
601 fprintf(out,"static encode_aux_threshmatch _vq_auxt_%s = {\n",name);
602 fprintf(out,"\t_vq_quantthresh_%s,\n",name);
603 fprintf(out,"\t_vq_quantmap_%s,\n",name);
604 fprintf(out,"\t%d,\n",t->quantvals);
605 fprintf(out,"\t%d\n};\n\n",t->threshvals);
610 for(i=0;i<c->dim;i++)pigeons*=p->quantvals;
613 fprintf(out,"static long _vq_pigeonmap_%s[] = {\n",name);
614 for(j=0;j<p->mapentries;){
616 for(k=0;k<8 && j<p->mapentries;k++,j++)
617 fprintf(out,"%5ld, ",p->pigeonmap[j]);
620 fprintf(out,"};\n\n");
622 fprintf(out,"static long _vq_fitlist_%s[] = {\n",name);
623 for(j=0;j<p->fittotal;){
625 for(k=0;k<8 && j<p->fittotal;k++,j++)
626 fprintf(out,"%5ld, ",p->fitlist[j]);
629 fprintf(out,"};\n\n");
631 fprintf(out,"static long _vq_fitmap_%s[] = {\n",name);
634 for(k=0;k<8 && j<pigeons;k++,j++)
635 fprintf(out,"%5ld, ",p->fitmap[j]);
638 fprintf(out,"};\n\n");
640 fprintf(out,"static long _vq_fitlength_%s[] = {\n",name);
643 for(k=0;k<8 && j<pigeons;k++,j++)
644 fprintf(out,"%5ld, ",p->fitlength[j]);
647 fprintf(out,"};\n\n");
649 fprintf(out,"static encode_aux_pigeonhole _vq_auxp_%s = {\n",name);
650 fprintf(out,"\t%g, %g, %d, %d,\n",
651 p->min,p->del,p->mapentries,p->quantvals);
653 fprintf(out,"\t_vq_pigeonmap_%s,\n",name);
655 fprintf(out,"\t%ld,\n",p->fittotal);
656 fprintf(out,"\t_vq_fitlist_%s,\n",name);
657 fprintf(out,"\t_vq_fitmap_%s,\n",name);
658 fprintf(out,"\t_vq_fitlength_%s\n};\n\n",name);
664 fprintf(out,"static long _vq_ptr0_%s[] = {\n",name);
667 for(k=0;k<8 && j<n->aux;k++,j++)
668 fprintf(out,"%6ld,",n->ptr0[j]);
671 fprintf(out,"};\n\n");
674 fprintf(out,"static long _vq_ptr1_%s[] = {\n",name);
677 for(k=0;k<8 && j<n->aux;k++,j++)
678 fprintf(out,"%6ld,",n->ptr1[j]);
681 fprintf(out,"};\n\n");
684 fprintf(out,"static long _vq_p_%s[] = {\n",name);
687 for(k=0;k<8 && j<n->aux;k++,j++)
688 fprintf(out,"%6ld,",n->p[j]*c->dim);
691 fprintf(out,"};\n\n");
694 fprintf(out,"static long _vq_q_%s[] = {\n",name);
697 for(k=0;k<8 && j<n->aux;k++,j++)
698 fprintf(out,"%6ld,",n->q[j]*c->dim);
701 fprintf(out,"};\n\n");
703 fprintf(out,"static encode_aux_nearestmatch _vq_auxn_%s = {\n",name);
704 fprintf(out,"\t_vq_ptr0_%s,\n",name);
705 fprintf(out,"\t_vq_ptr1_%s,\n",name);
706 fprintf(out,"\t_vq_p_%s,\n",name);
707 fprintf(out,"\t_vq_q_%s,\n",name);
708 fprintf(out,"\t%ld, %ld\n};\n\n",n->aux,n->aux);
711 /* tie it all together */
713 fprintf(out,"static static_codebook _vq_book_%s = {\n",name);
715 fprintf(out,"\t%ld, %ld,\n",c->dim,c->entries);
716 fprintf(out,"\t_vq_lengthlist_%s,\n",name);
717 fprintf(out,"\t%d, %ld, %ld, %d, %d,\n",
718 c->maptype,c->q_min,c->q_delta,c->q_quant,c->q_sequencep);
720 fprintf(out,"\t_vq_quantlist_%s,\n",name);
722 fprintf(out,"\tNULL,\n");
725 fprintf(out,"\t&_vq_auxn_%s,\n",name);
727 fprintf(out,"\tNULL,\n");
729 fprintf(out,"\t&_vq_auxt_%s,\n",name);
731 fprintf(out,"\tNULL,\n");
733 fprintf(out,"\t&_vq_auxp_%s,\n",name);
735 fprintf(out,"\tNULL,\n");
737 fprintf(out,"\t0\n};\n\n");
739 fprintf(out,"\n#endif\n");