Chris@1: /********************************************************************
Chris@1:  *                                                                  *
Chris@1:  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
Chris@1:  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
Chris@1:  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
Chris@1:  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
Chris@1:  *                                                                  *
Chris@1:  * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2001             *
Chris@1:  * by the Xiph.Org Foundation http://www.xiph.org/                  *
Chris@1:  *                                                                  *
Chris@1:  ********************************************************************
Chris@1: 
Chris@1:  function: hufftree builder
Chris@1:  last mod: $Id: huffbuild.c 16959 2010-03-10 16:03:11Z xiphmont $
Chris@1: 
Chris@1:  ********************************************************************/
Chris@1: 
Chris@1: #include <stdlib.h>
Chris@1: #include <string.h>
Chris@1: #include <math.h>
Chris@1: #include <stdio.h>
Chris@1: #include "bookutil.h"
Chris@1: 
Chris@1: static int nsofar=0;
Chris@1: static int getval(FILE *in,int begin,int n,int group,int max){
Chris@1:   float v;
Chris@1:   int i;
Chris@1:   long val=0;
Chris@1: 
Chris@1:   if(nsofar>=n || get_line_value(in,&v)){
Chris@1:     reset_next_value();
Chris@1:     nsofar=0;
Chris@1:     if(get_next_value(in,&v))
Chris@1:       return(-1);
Chris@1:     for(i=1;i<=begin;i++)
Chris@1:       get_line_value(in,&v);
Chris@1:   }
Chris@1: 
Chris@1:   val=(int)v;
Chris@1:   nsofar++;
Chris@1: 
Chris@1:   for(i=1;i<group;i++,nsofar++)
Chris@1:     if(nsofar>=n || get_line_value(in,&v))
Chris@1:       return(getval(in,begin,n,group,max));
Chris@1:     else
Chris@1:       val = val*max+(int)v;
Chris@1:   return(val);
Chris@1: }
Chris@1: 
Chris@1: static void usage(){
Chris@1:   fprintf(stderr,
Chris@1:           "usage:\n" 
Chris@1:           "huffbuild <input>.vqd <begin,n,group>|<lorange-hirange> [noguard]\n"
Chris@1:           "   where begin,n,group is first scalar, \n"
Chris@1:           "                          number of scalars of each in line,\n"
Chris@1:           "                          number of scalars in a group\n"
Chris@1:           "eg: huffbuild reslongaux.vqd 0,1024,4\n"
Chris@1:           "produces reslongaux.vqh\n\n");
Chris@1:   exit(1);
Chris@1: }
Chris@1: 
Chris@1: int main(int argc, char *argv[]){
Chris@1:   char *base;
Chris@1:   char *infile;
Chris@1:   int i,j,k,begin,n,subn,guard=1;
Chris@1:   FILE *file;
Chris@1:   int maxval=0;
Chris@1:   int loval=0;
Chris@1: 
Chris@1:   if(argc<3)usage();
Chris@1:   if(argc==4)guard=0;
Chris@1: 
Chris@1:   infile=strdup(argv[1]);
Chris@1:   base=strdup(infile);
Chris@1:   if(strrchr(base,'.'))
Chris@1:     strrchr(base,'.')[0]='\0';
Chris@1: 
Chris@1:   {
Chris@1:     char *pos=strchr(argv[2],',');
Chris@1:     char *dpos=strchr(argv[2],'-');
Chris@1:     if(dpos){
Chris@1:       loval=atoi(argv[2]);
Chris@1:       maxval=atoi(dpos+1);
Chris@1:       subn=1;
Chris@1:       begin=0;
Chris@1:     }else{
Chris@1:       begin=atoi(argv[2]);
Chris@1:       if(!pos)
Chris@1:         usage();
Chris@1:       else
Chris@1:         n=atoi(pos+1);
Chris@1:       pos=strchr(pos+1,',');
Chris@1:       if(!pos)
Chris@1:         usage();
Chris@1:       else
Chris@1:         subn=atoi(pos+1);
Chris@1:       if(n/subn*subn != n){
Chris@1:         fprintf(stderr,"n must be divisible by group\n");
Chris@1:         exit(1);
Chris@1:       }
Chris@1:     }
Chris@1:   }
Chris@1: 
Chris@1:   /* scan the file for maximum value */
Chris@1:   file=fopen(infile,"r");
Chris@1:   if(!file){
Chris@1:     fprintf(stderr,"Could not open file %s\n",infile);
Chris@1:     if(!maxval)
Chris@1:       exit(1);
Chris@1:     else
Chris@1:       fprintf(stderr,"  making untrained books.\n");
Chris@1: 
Chris@1:   }
Chris@1: 
Chris@1:   if(!maxval){
Chris@1:     i=0;
Chris@1:     while(1){
Chris@1:       long v;
Chris@1:       if(get_next_ivalue(file,&v))break;
Chris@1:       if(v>maxval)maxval=v;
Chris@1:       
Chris@1:       if(!(i++&0xff))spinnit("loading... ",i);
Chris@1:     }
Chris@1:     rewind(file);
Chris@1:     maxval++;
Chris@1:   }
Chris@1: 
Chris@1:   {
Chris@1:     long vals=pow(maxval,subn);
Chris@1:     long *hist=_ogg_calloc(vals,sizeof(long));
Chris@1:     long *lengths=_ogg_calloc(vals,sizeof(long));
Chris@1:     
Chris@1:     for(j=loval;j<vals;j++)hist[j]=guard;
Chris@1:     
Chris@1:     if(file){
Chris@1:       reset_next_value();
Chris@1:       i/=subn;
Chris@1:       while(!feof(file)){
Chris@1:         long val=getval(file,begin,n,subn,maxval);
Chris@1:         if(val==-1 || val>=vals)break;
Chris@1:         hist[val]++;
Chris@1:         if(!(i--&0xff))spinnit("loading... ",i*subn);
Chris@1:       }
Chris@1:       fclose(file);
Chris@1:     }
Chris@1:  
Chris@1:     /* we have the probabilities, build the tree */
Chris@1:     fprintf(stderr,"Building tree for %ld entries\n",vals);
Chris@1:     build_tree_from_lengths0(vals,hist,lengths);
Chris@1: 
Chris@1:     /* save the book */
Chris@1:     {
Chris@1:       char *buffer=alloca(strlen(base)+5);
Chris@1:       strcpy(buffer,base);
Chris@1:       strcat(buffer,".vqh");
Chris@1:       file=fopen(buffer,"w");
Chris@1:       if(!file){
Chris@1:         fprintf(stderr,"Could not open file %s\n",buffer);
Chris@1:         exit(1);
Chris@1:       }
Chris@1:     }
Chris@1:     
Chris@1:     /* first, the static vectors, then the book structure to tie it together. */
Chris@1:     /* lengthlist */
Chris@1:     fprintf(file,"static const long _huff_lengthlist_%s[] = {\n",base);
Chris@1:     for(j=0;j<vals;){
Chris@1:       fprintf(file,"\t");
Chris@1:       for(k=0;k<16 && j<vals;k++,j++)
Chris@1:         fprintf(file,"%2ld,",lengths[j]);
Chris@1:       fprintf(file,"\n");
Chris@1:     }
Chris@1:     fprintf(file,"};\n\n");
Chris@1:     
Chris@1:     /* the toplevel book */
Chris@1:     fprintf(file,"static const static_codebook _huff_book_%s = {\n",base);
Chris@1:     fprintf(file,"\t%d, %ld,\n",subn,vals);
Chris@1:     fprintf(file,"\t(long *)_huff_lengthlist_%s,\n",base);
Chris@1:     fprintf(file,"\t0, 0, 0, 0, 0,\n");
Chris@1:     fprintf(file,"\tNULL,\n");
Chris@1: 
Chris@1:     fprintf(file,"\t0\n};\n\n");
Chris@1:     
Chris@1:     fclose(file);
Chris@1:     fprintf(stderr,"Done.                                \n\n");
Chris@1:   }
Chris@1:   exit(0);
Chris@1: }
Chris@1: 
Chris@1: 
Chris@1: 
Chris@1: 
Chris@1: 
Chris@1: 
Chris@1: 
Chris@1: 
Chris@1: 
Chris@1: 
Chris@1: