18e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels/******************************************************************** 28e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels * * 38e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE. * 48e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS * 58e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE * 68e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. * 78e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels * * 88e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2001 * 98e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels * by the Xiph.Org Foundation http://www.xiph.org/ * 108e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels * * 118e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels ******************************************************************** 128e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 138e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels function: hufftree builder 148e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels last mod: $Id: huffbuild.c 16959 2010-03-10 16:03:11Z xiphmont $ 158e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 168e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels ********************************************************************/ 178e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 188e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels#include <stdlib.h> 198e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels#include <string.h> 208e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels#include <math.h> 218e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels#include <stdio.h> 228e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels#include "bookutil.h" 238e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 248e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsstatic int nsofar=0; 258e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsstatic int getval(FILE *in,int begin,int n,int group,int max){ 268e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels float v; 278e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels int i; 288e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels long val=0; 298e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 308e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(nsofar>=n || get_line_value(in,&v)){ 318e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels reset_next_value(); 328e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels nsofar=0; 338e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(get_next_value(in,&v)) 348e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels return(-1); 358e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels for(i=1;i<=begin;i++) 368e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels get_line_value(in,&v); 378e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 388e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 398e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels val=(int)v; 408e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels nsofar++; 418e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 428e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels for(i=1;i<group;i++,nsofar++) 438e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(nsofar>=n || get_line_value(in,&v)) 448e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels return(getval(in,begin,n,group,max)); 458e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels else 468e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels val = val*max+(int)v; 478e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels return(val); 488e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels} 498e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 508e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsstatic void usage(){ 518e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(stderr, 528e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels "usage:\n" 538e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels "huffbuild <input>.vqd <begin,n,group>|<lorange-hirange> [noguard]\n" 548e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels " where begin,n,group is first scalar, \n" 558e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels " number of scalars of each in line,\n" 568e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels " number of scalars in a group\n" 578e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels "eg: huffbuild reslongaux.vqd 0,1024,4\n" 588e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels "produces reslongaux.vqh\n\n"); 598e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels exit(1); 608e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels} 618e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 628e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsint main(int argc, char *argv[]){ 638e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels char *base; 648e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels char *infile; 658e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels int i,j,k,begin,n,subn,guard=1; 668e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels FILE *file; 678e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels int maxval=0; 688e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels int loval=0; 698e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 708e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(argc<3)usage(); 718e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(argc==4)guard=0; 728e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 738e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels infile=strdup(argv[1]); 748e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels base=strdup(infile); 758e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(strrchr(base,'.')) 768e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels strrchr(base,'.')[0]='\0'; 778e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 788e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels { 798e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels char *pos=strchr(argv[2],','); 808e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels char *dpos=strchr(argv[2],'-'); 818e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(dpos){ 828e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels loval=atoi(argv[2]); 838e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels maxval=atoi(dpos+1); 848e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels subn=1; 858e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels begin=0; 868e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels }else{ 878e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels begin=atoi(argv[2]); 888e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(!pos) 898e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels usage(); 908e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels else 918e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels n=atoi(pos+1); 928e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels pos=strchr(pos+1,','); 938e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(!pos) 948e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels usage(); 958e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels else 968e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels subn=atoi(pos+1); 978e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(n/subn*subn != n){ 988e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(stderr,"n must be divisible by group\n"); 998e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels exit(1); 1008e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 1018e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 1028e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 1038e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1048e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels /* scan the file for maximum value */ 1058e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels file=fopen(infile,"r"); 1068e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(!file){ 1078e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(stderr,"Could not open file %s\n",infile); 1088e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(!maxval) 1098e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels exit(1); 1108e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels else 1118e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(stderr," making untrained books.\n"); 1128e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1138e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 1148e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1158e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(!maxval){ 1168e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels i=0; 1178e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels while(1){ 1188e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels long v; 1198e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(get_next_ivalue(file,&v))break; 1208e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(v>maxval)maxval=v; 1218e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1228e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(!(i++&0xff))spinnit("loading... ",i); 1238e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 1248e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels rewind(file); 1258e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels maxval++; 1268e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 1278e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1288e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels { 1298e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels long vals=pow(maxval,subn); 1308e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels long *hist=_ogg_calloc(vals,sizeof(long)); 1318e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels long *lengths=_ogg_calloc(vals,sizeof(long)); 1328e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1338e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels for(j=loval;j<vals;j++)hist[j]=guard; 1348e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1358e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(file){ 1368e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels reset_next_value(); 1378e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels i/=subn; 1388e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels while(!feof(file)){ 1398e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels long val=getval(file,begin,n,subn,maxval); 1408e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(val==-1 || val>=vals)break; 1418e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels hist[val]++; 1428e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(!(i--&0xff))spinnit("loading... ",i*subn); 1438e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 1448e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fclose(file); 1458e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 1468e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1478e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels /* we have the probabilities, build the tree */ 1488e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(stderr,"Building tree for %ld entries\n",vals); 1498e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels build_tree_from_lengths0(vals,hist,lengths); 1508e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1518e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels /* save the book */ 1528e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels { 1538e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels char *buffer=alloca(strlen(base)+5); 1548e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels strcpy(buffer,base); 1558e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels strcat(buffer,".vqh"); 1568e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels file=fopen(buffer,"w"); 1578e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if(!file){ 1588e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(stderr,"Could not open file %s\n",buffer); 1598e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels exit(1); 1608e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 1618e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 1628e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1638e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels /* first, the static vectors, then the book structure to tie it together. */ 1648e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels /* lengthlist */ 1658e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(file,"static const long _huff_lengthlist_%s[] = {\n",base); 1668e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels for(j=0;j<vals;){ 1678e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(file,"\t"); 1688e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels for(k=0;k<16 && j<vals;k++,j++) 1698e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(file,"%2ld,",lengths[j]); 1708e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(file,"\n"); 1718e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 1728e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(file,"};\n\n"); 1738e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1748e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels /* the toplevel book */ 1758e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(file,"static const static_codebook _huff_book_%s = {\n",base); 1768e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(file,"\t%d, %ld,\n",subn,vals); 1778e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(file,"\t(long *)_huff_lengthlist_%s,\n",base); 1788e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(file,"\t0, 0, 0, 0, 0,\n"); 1798e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(file,"\tNULL,\n"); 1808e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1818e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(file,"\t0\n};\n\n"); 1828e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1838e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fclose(file); 1848e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels fprintf(stderr,"Done. \n\n"); 1858e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 1868e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels exit(0); 1878e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels} 1888e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1898e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1908e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1918e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1928e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1938e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1948e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1958e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1968e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1978e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1988e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 199