1 /********************************************************************
3 * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE. *
4 * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
5 * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE. *
6 * PLEASE READ THESE TERMS DISTRIBUTING. *
8 * THE OggSQUISH 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.16 2000/08/15 09:09:44 xiphmont Exp $
17 ********************************************************************/
24 #include "vorbis/codebook.h"
25 #include "../lib/sharedbook.h"
28 /* A few little utils for reading files */
29 /* read a line. Use global, persistent buffering */
30 static char *linebuffer=NULL;
31 static int lbufsize=0;
32 char *get_line(FILE *in){
34 if(feof(in))return NULL;
40 if(sofar+1>=lbufsize){
43 linebuffer=malloc(lbufsize);
46 linebuffer=realloc(linebuffer,lbufsize);
53 if(sofar==0)return(NULL);
54 /* fallthrough correct */
56 linebuffer[sofar]='\0';
60 linebuffer[sofar++]=c;
61 linebuffer[sofar]='\0';
67 if(linebuffer[0]=='#'){
75 /* read the next numerical value from the given file */
76 static char *value_line_buff=NULL;
78 int get_line_value(FILE *in,double *value){
81 if(!value_line_buff)return(-1);
83 *value=strtod(value_line_buff, &next);
84 if(next==value_line_buff){
89 while(*value_line_buff>44)value_line_buff++;
90 if(*value_line_buff==44)value_line_buff++;
95 int get_next_value(FILE *in,double *value){
97 if(get_line_value(in,value)){
98 value_line_buff=get_line(in);
99 if(!value_line_buff)return(-1);
106 int get_next_ivalue(FILE *in,long *ivalue){
108 int ret=get_next_value(in,&value);
113 static double sequence_base=0.;
114 static int v_sofar=0;
115 void reset_next_value(void){
116 value_line_buff=NULL;
121 char *setup_line(FILE *in){
123 value_line_buff=get_line(in);
124 return(value_line_buff);
128 int get_vector(codebook *b,FILE *in,int start, int n,double *a){
130 const static_codebook *c=b->c;
134 if(v_sofar==n || get_line_value(in,a)){
136 if(get_next_value(in,a))
138 for(i=0;i<start;i++){
140 get_line_value(in,a);
144 for(i=1;i<c->dim;i++)
145 if(get_line_value(in,a+i))
149 double temp=a[c->dim-1];
150 for(i=0;i<c->dim;i++)a[i]-=sequence_base;
151 if(c->q_sequencep)sequence_base=temp;
161 /* read lines fromt he beginning until we find one containing the
163 char *find_seek_to(FILE *in,char *s){
166 char *line=get_line(in);
176 /* this reads the format as written by vqbuild/latticebuild; innocent
177 (legal) tweaking of the file that would not affect its valid
178 header-ness will break this routine */
180 codebook *codebook_load(char *filename){
181 codebook *b=calloc(1,sizeof(codebook));
182 static_codebook *c=(static_codebook *)(b->c=calloc(1,sizeof(static_codebook)));
183 encode_aux_nearestmatch *a=NULL;
184 encode_aux_threshmatch *t=NULL;
185 encode_aux_pigeonhole *p=NULL;
187 FILE *in=fopen(filename,"r");
192 fprintf(stderr,"Couldn't open codebook %s\n",filename);
196 /* find the codebook struct */
197 find_seek_to(in,"static static_codebook _vq_book_");
199 /* get the major important values */
201 if(sscanf(line,"%ld, %ld,",
202 &(c->dim),&(c->entries))!=2){
203 fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);
208 if(sscanf(line,"%d, %ld, %ld, %d, %d,",
209 &(c->maptype),&(c->q_min),&(c->q_delta),&(c->q_quant),
210 &(c->q_sequencep))!=5){
211 fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);
215 /* find the auxiliary encode struct[s] (if any) */
216 if(find_seek_to(in,"static encode_aux_nearestmatch _vq_aux")){
218 c->nearest_tree=a=calloc(1,sizeof(encode_aux_nearestmatch));
224 if(sscanf(line,"%ld, %ld",&(a->aux),&(a->alloc))!=2){
225 fprintf(stderr,"2: syntax in %s in line:\t %s",filename,line);
230 find_seek_to(in,"static long _vq_ptr0");
232 a->ptr0=malloc(sizeof(long)*a->aux);
233 for(i=0;i<a->aux;i++)
234 if(get_next_ivalue(in,a->ptr0+i)){
235 fprintf(stderr,"out of data while reading codebook %s\n",filename);
240 find_seek_to(in,"static long _vq_ptr1");
242 a->ptr1=malloc(sizeof(long)*a->aux);
243 for(i=0;i<a->aux;i++)
244 if(get_next_ivalue(in,a->ptr1+i)){
245 fprintf(stderr,"out of data while reading codebook %s\n",filename);
251 find_seek_to(in,"static long _vq_p_");
253 a->p=malloc(sizeof(long)*a->aux);
254 for(i=0;i<a->aux;i++)
255 if(get_next_ivalue(in,a->p+i)){
256 fprintf(stderr,"out of data while reading codebook %s\n",filename);
261 find_seek_to(in,"static long _vq_q_");
263 a->q=malloc(sizeof(long)*a->aux);
264 for(i=0;i<a->aux;i++)
265 if(get_next_ivalue(in,a->q+i)){
266 fprintf(stderr,"out of data while reading codebook %s\n",filename);
271 if(find_seek_to(in,"static encode_aux_threshmatch _vq_aux")){
273 c->thresh_tree=t=calloc(1,sizeof(encode_aux_threshmatch));
277 if(sscanf(line,"%d",&(t->quantvals))!=1){
278 fprintf(stderr,"3: syntax in %s in line:\t %s",filename,line);
282 if(sscanf(line,"%d",&(t->threshvals))!=1){
283 fprintf(stderr,"4: syntax in %s in line:\t %s",filename,line);
286 /* load quantthresh */
287 find_seek_to(in,"static double _vq_quantthresh_");
289 t->quantthresh=malloc(sizeof(double)*t->threshvals);
290 for(i=0;i<t->threshvals-1;i++)
291 if(get_next_value(in,t->quantthresh+i)){
292 fprintf(stderr,"out of data 1 while reading codebook %s\n",filename);
296 find_seek_to(in,"static long _vq_quantmap_");
298 t->quantmap=malloc(sizeof(long)*t->threshvals);
299 for(i=0;i<t->threshvals;i++)
300 if(get_next_ivalue(in,t->quantmap+i)){
301 fprintf(stderr,"out of data 2 while reading codebook %s\n",filename);
306 if(find_seek_to(in,"static encode_aux_pigeonhole _vq_aux")){
309 c->pigeon_tree=p=calloc(1,sizeof(encode_aux_pigeonhole));
311 if(sscanf(line,"%lf, %lf, %d, %d",&(p->min),&(p->del),
312 &(p->mapentries),&(p->quantvals))!=4){
313 fprintf(stderr,"5: syntax in %s in line:\t %s",filename,line);
318 if(sscanf(line,"%ld",&(p->fittotal))!=1){
319 fprintf(stderr,"6: syntax in %s in line:\t %s",filename,line);
323 find_seek_to(in,"static long _vq_pigeonmap_");
325 p->pigeonmap=malloc(sizeof(long)*p->mapentries);
326 for(i=0;i<p->mapentries;i++)
327 if(get_next_ivalue(in,p->pigeonmap+i)){
328 fprintf(stderr,"out of data (pigeonmap) while reading codebook %s\n",filename);
332 find_seek_to(in,"static long _vq_fitlist_");
334 p->fitlist=malloc(sizeof(long)*p->fittotal);
335 for(i=0;i<p->fittotal;i++)
336 if(get_next_ivalue(in,p->fitlist+i)){
337 fprintf(stderr,"out of data (fitlist) while reading codebook %s\n",filename);
341 find_seek_to(in,"static long _vq_fitmap_");
343 for(i=0;i<c->dim;i++)pigeons*=p->quantvals;
344 p->fitmap=malloc(sizeof(long)*pigeons);
345 for(i=0;i<pigeons;i++)
346 if(get_next_ivalue(in,p->fitmap+i)){
347 fprintf(stderr,"out of data (fitmap) while reading codebook %s\n",filename);
352 find_seek_to(in,"static long _vq_fitlength_");
354 p->fitlength=malloc(sizeof(long)*pigeons);
355 for(i=0;i<pigeons;i++)
356 if(get_next_ivalue(in,p->fitlength+i)){
357 fprintf(stderr,"out of data (fitlength) while reading codebook %s\n",filename);
367 quant_to_read=_book_maptype1_quantvals(c);
370 quant_to_read=c->entries*c->dim;
374 /* load the quantized entries */
375 find_seek_to(in,"static long _vq_quantlist_");
377 c->quantlist=malloc(sizeof(long)*quant_to_read);
378 for(i=0;i<quant_to_read;i++)
379 if(get_next_ivalue(in,c->quantlist+i)){
380 fprintf(stderr,"out of data while reading codebook %s\n",filename);
384 /* load the lengthlist */
385 find_seek_to(in,"static long _vq_lengthlist");
387 c->lengthlist=malloc(sizeof(long)*c->entries);
388 for(i=0;i<c->entries;i++)
389 if(get_next_ivalue(in,c->lengthlist+i)){
390 fprintf(stderr,"out of data while reading codebook %s\n",filename);
397 vorbis_book_init_encode(b,c);
402 void spinnit(char *s,int n){
404 static long lasttime=0;
406 struct timeval thistime;
408 gettimeofday(&thistime,NULL);
409 test=thistime.tv_sec*10+thistime.tv_usec/100000;
413 fprintf(stderr,"%s%d ",s,n);
418 fprintf(stderr,"| \r");
421 fprintf(stderr,"/ \r");
424 fprintf(stderr,"- \r");
427 fprintf(stderr,"\\ \r");
434 void build_tree_from_lengths(int vals, long *hist, long *lengths){
436 long *membership=malloc(vals*sizeof(long));
437 long *histsave=alloca(vals*sizeof(long));
438 memcpy(histsave,hist,vals*sizeof(long));
440 for(i=0;i<vals;i++)membership[i]=i;
442 /* find codeword lengths */
443 /* much more elegant means exist. Brute force n^2, minimum thought */
445 int first=-1,second=-1;
448 spinnit("building... ",i);
450 /* find the two nodes to join */
452 if(least==-1 || hist[j]<least){
458 if((least==-1 || hist[j]<least) && membership[j]!=first){
460 second=membership[j];
462 if(first==-1 || second==-1){
463 fprintf(stderr,"huffman fault; no free branch\n");
468 least=hist[first]+hist[second];
470 if(membership[j]==first || membership[j]==second){
476 for(i=0;i<vals-1;i++)
477 if(membership[i]!=membership[i+1]){
478 fprintf(stderr,"huffman fault; failed to build single tree\n");
482 /* for sanity check purposes: how many bits would it have taken to
483 encode the training set? */
488 bitsum+=(histsave[i]-1)*lengths[i];
489 samples+=histsave[i]-1;
493 fprintf(stderr,"\rTotal samples in training set: %ld \n",samples);
494 fprintf(stderr,"\rTotal bits used to represent training set: %ld\n",
502 /* wrap build_tree_from_lengths to allow zero entries in the histogram */
503 void build_tree_from_lengths0(int vals, long *hist, long *lengths){
505 /* pack the 'sparse' hit list into a dense list, then unpack
506 the lengths after the build */
509 long *lengthlist=calloc(vals,sizeof(long));
510 long *newhist=alloca(vals*sizeof(long));
514 newhist[upper++]=hist[i];
517 fprintf(stderr,"\rEliminating %d unused entries; %d entries remain\n",
521 build_tree_from_lengths(upper,newhist,lengthlist);
526 lengths[i]=lengthlist[upper++];
533 void write_codebook(FILE *out,char *name,const static_codebook *c){
534 encode_aux_pigeonhole *p=c->pigeon_tree;
535 encode_aux_threshmatch *t=c->thresh_tree;
536 encode_aux_nearestmatch *n=c->nearest_tree;
539 /* save the book in C header form */
541 "/********************************************************************\n"
543 " * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE. *\n"
544 " * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *\n"
545 " * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE. *\n"
546 " * PLEASE READ THESE TERMS DISTRIBUTING. *\n"
548 " * THE OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-1999 *\n"
549 " * by 1999 Monty <monty@xiph.org> and The XIPHOPHORUS Company *\n"
550 " * http://www.xiph.org/ *\n"
552 " ********************************************************************\n"
554 " function: static codebook autogenerated by vq/somethingorother\n"
556 " ********************************************************************/\n\n");
558 fprintf(out,"#ifndef _V_%s_VQH_\n#define _V_%s_VQH_\n",name,name);
559 fprintf(out,"#include \"vorbis/codebook.h\"\n\n");
561 /* first, the static vectors, then the book structure to tie it together. */
564 long vals=(c->maptype==1?_book_maptype1_quantvals(c):c->entries*c->dim);
565 fprintf(out,"static long _vq_quantlist_%s[] = {\n",name);
567 fprintf(out,"\t%ld,\n",c->quantlist[j]);
569 fprintf(out,"};\n\n");
573 fprintf(out,"static long _vq_lengthlist_%s[] = {\n",name);
574 for(j=0;j<c->entries;){
576 for(k=0;k<16 && j<c->entries;k++,j++)
577 fprintf(out,"%2ld,",c->lengthlist[j]);
580 fprintf(out,"};\n\n");
584 fprintf(out,"static double _vq_quantthresh_%s[] = {\n",name);
585 for(j=0;j<t->threshvals-1;){
587 for(k=0;k<8 && j<t->threshvals-1;k++,j++)
588 fprintf(out,"%.5g, ",t->quantthresh[j]);
591 fprintf(out,"};\n\n");
594 fprintf(out,"static long _vq_quantmap_%s[] = {\n",name);
595 for(j=0;j<t->threshvals;){
597 for(k=0;k<8 && j<t->threshvals;k++,j++)
598 fprintf(out,"%5ld,",t->quantmap[j]);
601 fprintf(out,"};\n\n");
603 fprintf(out,"static encode_aux_threshmatch _vq_auxt_%s = {\n",name);
604 fprintf(out,"\t_vq_quantthresh_%s,\n",name);
605 fprintf(out,"\t_vq_quantmap_%s,\n",name);
606 fprintf(out,"\t%d,\n",t->quantvals);
607 fprintf(out,"\t%d\n};\n\n",t->threshvals);
612 for(i=0;i<c->dim;i++)pigeons*=p->quantvals;
615 fprintf(out,"static long _vq_pigeonmap_%s[] = {\n",name);
616 for(j=0;j<p->mapentries;){
618 for(k=0;k<8 && j<p->mapentries;k++,j++)
619 fprintf(out,"%5ld, ",p->pigeonmap[j]);
622 fprintf(out,"};\n\n");
624 fprintf(out,"static long _vq_fitlist_%s[] = {\n",name);
625 for(j=0;j<p->fittotal;){
627 for(k=0;k<8 && j<p->fittotal;k++,j++)
628 fprintf(out,"%5ld, ",p->fitlist[j]);
631 fprintf(out,"};\n\n");
633 fprintf(out,"static long _vq_fitmap_%s[] = {\n",name);
636 for(k=0;k<8 && j<pigeons;k++,j++)
637 fprintf(out,"%5ld, ",p->fitmap[j]);
640 fprintf(out,"};\n\n");
642 fprintf(out,"static long _vq_fitlength_%s[] = {\n",name);
645 for(k=0;k<8 && j<pigeons;k++,j++)
646 fprintf(out,"%5ld, ",p->fitlength[j]);
649 fprintf(out,"};\n\n");
651 fprintf(out,"static encode_aux_pigeonhole _vq_auxp_%s = {\n",name);
652 fprintf(out,"\t%g, %g, %d, %d,\n",
653 p->min,p->del,p->mapentries,p->quantvals);
655 fprintf(out,"\t_vq_pigeonmap_%s,\n",name);
657 fprintf(out,"\t%ld,\n",p->fittotal);
658 fprintf(out,"\t_vq_fitlist_%s,\n",name);
659 fprintf(out,"\t_vq_fitmap_%s,\n",name);
660 fprintf(out,"\t_vq_fitlength_%s\n};\n\n",name);
666 fprintf(out,"static long _vq_ptr0_%s[] = {\n",name);
669 for(k=0;k<8 && j<n->aux;k++,j++)
670 fprintf(out,"%6ld,",n->ptr0[j]);
673 fprintf(out,"};\n\n");
676 fprintf(out,"static long _vq_ptr1_%s[] = {\n",name);
679 for(k=0;k<8 && j<n->aux;k++,j++)
680 fprintf(out,"%6ld,",n->ptr1[j]);
683 fprintf(out,"};\n\n");
686 fprintf(out,"static long _vq_p_%s[] = {\n",name);
689 for(k=0;k<8 && j<n->aux;k++,j++)
690 fprintf(out,"%6ld,",n->p[j]*c->dim);
693 fprintf(out,"};\n\n");
696 fprintf(out,"static long _vq_q_%s[] = {\n",name);
699 for(k=0;k<8 && j<n->aux;k++,j++)
700 fprintf(out,"%6ld,",n->q[j]*c->dim);
703 fprintf(out,"};\n\n");
705 fprintf(out,"static encode_aux_nearestmatch _vq_auxn_%s = {\n",name);
706 fprintf(out,"\t_vq_ptr0_%s,\n",name);
707 fprintf(out,"\t_vq_ptr1_%s,\n",name);
708 fprintf(out,"\t_vq_p_%s,\n",name);
709 fprintf(out,"\t_vq_q_%s,\n",name);
710 fprintf(out,"\t%ld, %ld\n};\n\n",n->aux,n->aux);
713 /* tie it all together */
715 fprintf(out,"static static_codebook _vq_book_%s = {\n",name);
717 fprintf(out,"\t%ld, %ld,\n",c->dim,c->entries);
718 fprintf(out,"\t_vq_lengthlist_%s,\n",name);
719 fprintf(out,"\t%d, %ld, %ld, %d, %d,\n",
720 c->maptype,c->q_min,c->q_delta,c->q_quant,c->q_sequencep);
722 fprintf(out,"\t_vq_quantlist_%s,\n",name);
724 fprintf(out,"\tNULL,\n");
727 fprintf(out,"\t&_vq_auxn_%s,\n",name);
729 fprintf(out,"\tNULL,\n");
731 fprintf(out,"\t&_vq_auxt_%s,\n",name);
733 fprintf(out,"\tNULL,\n");
735 fprintf(out,"\t&_vq_auxp_%s,\n",name);
737 fprintf(out,"\tNULL,\n");
739 fprintf(out,"};\n\n");
741 fprintf(out,"\n#endif\n");