diff options
author | Aki <please@ignore.pl> | 2021-10-01 23:46:47 +0200 |
---|---|---|
committer | Aki <please@ignore.pl> | 2021-10-01 23:46:47 +0200 |
commit | ddd76aa4e1571c8d5965709db5c3cd47a89c9a38 (patch) | |
tree | 4e07bfaebede6531a70984fdebc855bca52f394a /vorbis/vq/bookutil.c | |
parent | 3a507e08b1d4e5970b27401a7e6517570d529400 (diff) | |
parent | c2d2c3551501110fddd78674d5435bfaa70382a3 (diff) | |
download | starshatter-ddd76aa4e1571c8d5965709db5c3cd47a89c9a38.zip starshatter-ddd76aa4e1571c8d5965709db5c3cd47a89c9a38.tar.gz starshatter-ddd76aa4e1571c8d5965709db5c3cd47a89c9a38.tar.bz2 |
Project is now built with CMake
Diffstat (limited to 'vorbis/vq/bookutil.c')
-rw-r--r-- | vorbis/vq/bookutil.c | 476 |
1 files changed, 476 insertions, 0 deletions
diff --git a/vorbis/vq/bookutil.c b/vorbis/vq/bookutil.c new file mode 100644 index 0000000..3046410 --- /dev/null +++ b/vorbis/vq/bookutil.c @@ -0,0 +1,476 @@ +/******************************************************************** + * * + * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE. * + * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS * + * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE * + * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. * + * * + * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2014 * + * by the Xiph.Org Foundation http://www.xiph.org/ * + * * + ******************************************************************** + + function: utility functions for loading .vqh and .vqd files + + ********************************************************************/ + +#include <stdlib.h> +#include <stdio.h> +#include <math.h> +#include <string.h> +#include <errno.h> +#include "bookutil.h" + +int _best(codebook *book, float *a, int step){ + + int dim=book->dim; + int i,j,o; + int minval=book->minval; + int del=book->delta; + int qv=book->quantvals; + int ze=(qv>>1); + int index=0; + /* assumes integer/centered encoder codebook maptype 1 no more than dim 8 */ + + if(del!=1){ + for(i=0,o=step*(dim-1);i<dim;i++,o-=step){ + int v = ((int)rint(a[o])-minval+(del>>1))/del; + int m = (v<ze ? ((ze-v)<<1)-1 : ((v-ze)<<1)); + index = index*qv+ (m<0?0:(m>=qv?qv-1:m)); + } + }else{ + for(i=0,o=step*(dim-1);i<dim;i++,o-=step){ + int v = (int)rint(a[o])-minval; + int m = (v<ze ? ((ze-v)<<1)-1 : ((v-ze)<<1)); + index = index*qv+ (m<0?0:(m>=qv?qv-1:m)); + } + } + + if(book->c->lengthlist[index]<=0){ + const static_codebook *c=book->c; + int best=-1; + /* assumes integer/centered encoder codebook maptype 1 no more than dim 8 */ + int e[8]={0,0,0,0,0,0,0,0}; + int maxval = book->minval + book->delta*(book->quantvals-1); + for(i=0;i<book->entries;i++){ + if(c->lengthlist[i]>0){ + float this=0; + for(j=0;j<dim;j++){ + float val=(e[j]-a[j*step]); + this+=val*val; + } + if(best==-1 || this<best){ + best=this; + index=i; + } + } + /* assumes the value patterning created by the tools in vq/ */ + j=0; + while(e[j]>=maxval) + e[j++]=0; + if(e[j]>=0) + e[j]+=book->delta; + e[j]= -e[j]; + } + } + + return index; +} + +/* A few little utils for reading files */ +/* read a line. Use global, persistent buffering */ +static char *linebuffer=NULL; +static int lbufsize=0; +char *get_line(FILE *in){ + long sofar=0; + if(feof(in))return NULL; + + while(1){ + int gotline=0; + + while(!gotline){ + if(sofar+1>=lbufsize){ + if(!lbufsize){ + lbufsize=1024; + linebuffer=_ogg_malloc(lbufsize); + }else{ + lbufsize*=2; + linebuffer=_ogg_realloc(linebuffer,lbufsize); + } + } + { + long c=fgetc(in); + switch(c){ + case EOF: + if(sofar==0)return(NULL); + /* fallthrough correct */ + case '\n': + linebuffer[sofar]='\0'; + gotline=1; + break; + default: + linebuffer[sofar++]=c; + linebuffer[sofar]='\0'; + break; + } + } + } + + if(linebuffer[0]=='#'){ + sofar=0; + }else{ + return(linebuffer); + } + } +} + +/* read the next numerical value from the given file */ +static char *value_line_buff=NULL; + +int get_line_value(FILE *in,float *value){ + char *next; + + if(!value_line_buff)return(-1); + + *value=strtod(value_line_buff, &next); + if(next==value_line_buff){ + value_line_buff=NULL; + return(-1); + }else{ + value_line_buff=next; + while(*value_line_buff>44)value_line_buff++; + if(*value_line_buff==44)value_line_buff++; + return(0); + } +} + +int get_next_value(FILE *in,float *value){ + while(1){ + if(get_line_value(in,value)){ + value_line_buff=get_line(in); + if(!value_line_buff)return(-1); + }else{ + return(0); + } + } +} + +int get_next_ivalue(FILE *in,long *ivalue){ + float value; + int ret=get_next_value(in,&value); + *ivalue=value; + return(ret); +} + +static float sequence_base=0.f; +static int v_sofar=0; +void reset_next_value(void){ + value_line_buff=NULL; + sequence_base=0.f; + v_sofar=0; +} + +char *setup_line(FILE *in){ + reset_next_value(); + value_line_buff=get_line(in); + return(value_line_buff); +} + + +int get_vector(codebook *b,FILE *in,int start, int n,float *a){ + int i; + const static_codebook *c=b->c; + + while(1){ + + if(v_sofar==n || get_line_value(in,a)){ + reset_next_value(); + if(get_next_value(in,a)) + break; + for(i=0;i<start;i++){ + sequence_base=*a; + get_line_value(in,a); + } + } + + for(i=1;i<c->dim;i++) + if(get_line_value(in,a+i)) + break; + + if(i==c->dim){ + float temp=a[c->dim-1]; + for(i=0;i<c->dim;i++)a[i]-=sequence_base; + if(c->q_sequencep)sequence_base=temp; + v_sofar++; + return(0); + } + sequence_base=0.f; + } + + return(-1); +} + +/* read lines fromt he beginning until we find one containing the + specified string */ +char *find_seek_to(FILE *in,char *s){ + rewind(in); + while(1){ + char *line=get_line(in); + if(line){ + if(strstr(line,s)) + return(line); + }else + return(NULL); + } +} + + +/* this reads the format as written by vqbuild/latticebuild; innocent + (legal) tweaking of the file that would not affect its valid + header-ness will break this routine */ + +codebook *codebook_load(char *filename){ + codebook *b=_ogg_calloc(1,sizeof(codebook)); + static_codebook *c=(static_codebook *)(b->c=_ogg_calloc(1,sizeof(static_codebook))); + int quant_to_read=0; + FILE *in=fopen(filename,"r"); + char *line; + long i; + + if(in==NULL){ + fprintf(stderr,"Couldn't open codebook %s\n",filename); + exit(1); + } + + /* find the codebook struct */ + find_seek_to(in,"static const static_codebook "); + + /* get the major important values */ + line=get_line(in); + if(sscanf(line,"%ld, %ld,", + &(c->dim),&(c->entries))!=2){ + fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line); + exit(1); + } + line=get_line(in); + line=get_line(in); + if(sscanf(line,"%d, %ld, %ld, %d, %d,", + &(c->maptype),&(c->q_min),&(c->q_delta),&(c->q_quant), + &(c->q_sequencep))!=5){ + fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line); + exit(1); + } + + switch(c->maptype){ + case 0: + quant_to_read=0; + break; + case 1: + quant_to_read=_book_maptype1_quantvals(c); + break; + case 2: + quant_to_read=c->entries*c->dim; + break; + } + + /* load the quantized entries */ + find_seek_to(in,"static const long _vq_quantlist_"); + reset_next_value(); + c->quantlist=_ogg_malloc(sizeof(long)*quant_to_read); + for(i=0;i<quant_to_read;i++) + if(get_next_ivalue(in,c->quantlist+i)){ + fprintf(stderr,"out of data while reading codebook %s\n",filename); + exit(1); + } + + /* load the lengthlist */ + find_seek_to(in,"_lengthlist"); + reset_next_value(); + c->lengthlist=_ogg_malloc(sizeof(long)*c->entries); + for(i=0;i<c->entries;i++) + if(get_next_ivalue(in,c->lengthlist+i)){ + fprintf(stderr,"out of data while reading codebook %s\n",filename); + exit(1); + } + + /* got it all */ + fclose(in); + + vorbis_book_init_encode(b,c); + b->valuelist=_book_unquantize(c,c->entries,NULL); + + return(b); +} + +void spinnit(char *s,int n){ + static int p=0; + static long lasttime=0; + long test; + struct timeval thistime; + + gettimeofday(&thistime,NULL); + test=thistime.tv_sec*10+thistime.tv_usec/100000; + if(lasttime!=test){ + lasttime=test; + + fprintf(stderr,"%s%d ",s,n); + + p++;if(p>3)p=0; + switch(p){ + case 0: + fprintf(stderr,"| \r"); + break; + case 1: + fprintf(stderr,"/ \r"); + break; + case 2: + fprintf(stderr,"- \r"); + break; + case 3: + fprintf(stderr,"\\ \r"); + break; + } + fflush(stderr); + } +} + +void build_tree_from_lengths(int vals, long *hist, long *lengths){ + int i,j; + long *membership=_ogg_malloc(vals*sizeof(long)); + long *histsave=alloca(vals*sizeof(long)); + memcpy(histsave,hist,vals*sizeof(long)); + + for(i=0;i<vals;i++)membership[i]=i; + + /* find codeword lengths */ + /* much more elegant means exist. Brute force n^2, minimum thought */ + for(i=vals;i>1;i--){ + int first=-1,second=-1; + long least=-1; + + spinnit("building... ",i); + + /* find the two nodes to join */ + for(j=0;j<vals;j++) + if(least==-1 || hist[j]<=least){ + least=hist[j]; + first=membership[j]; + } + least=-1; + for(j=0;j<vals;j++) + if((least==-1 || hist[j]<=least) && membership[j]!=first){ + least=hist[j]; + second=membership[j]; + } + if(first==-1 || second==-1){ + fprintf(stderr,"huffman fault; no free branch\n"); + exit(1); + } + + /* join them */ + least=hist[first]+hist[second]; + for(j=0;j<vals;j++) + if(membership[j]==first || membership[j]==second){ + membership[j]=first; + hist[j]=least; + lengths[j]++; + } + } + for(i=0;i<vals-1;i++) + if(membership[i]!=membership[i+1]){ + fprintf(stderr,"huffman fault; failed to build single tree\n"); + exit(1); + } + + /* for sanity check purposes: how many bits would it have taken to + encode the training set? */ + { + long bitsum=0; + long samples=0; + for(i=0;i<vals;i++){ + bitsum+=(histsave[i]-1)*lengths[i]; + samples+=histsave[i]-1; + } + + if(samples){ + fprintf(stderr,"\rTotal samples in training set: %ld \n",samples); + fprintf(stderr,"\rTotal bits used to represent training set: %ld\n", + bitsum); + } + } + + free(membership); +} + +/* wrap build_tree_from_lengths to allow zero entries in the histogram */ +void build_tree_from_lengths0(int vals, long *hist, long *lengths){ + + /* pack the 'sparse' hit list into a dense list, then unpack + the lengths after the build */ + + int upper=0,i; + long *lengthlist=_ogg_calloc(vals,sizeof(long)); + long *newhist=alloca(vals*sizeof(long)); + + for(i=0;i<vals;i++) + if(hist[i]>0) + newhist[upper++]=hist[i]; + + if(upper != vals){ + fprintf(stderr,"\rEliminating %d unused entries; %d entries remain\n", + vals-upper,upper); + } + + build_tree_from_lengths(upper,newhist,lengthlist); + + upper=0; + for(i=0;i<vals;i++) + if(hist[i]>0) + lengths[i]=lengthlist[upper++]; + else + lengths[i]=0; + + free(lengthlist); +} + +void write_codebook(FILE *out,char *name,const static_codebook *c){ + int i,j,k; + + /* save the book in C header form */ + + /* first, the static vectors, then the book structure to tie it together. */ + /* quantlist */ + if(c->quantlist){ + long vals=(c->maptype==1?_book_maptype1_quantvals(c):c->entries*c->dim); + fprintf(out,"static const long _vq_quantlist_%s[] = {\n",name); + for(j=0;j<vals;j++){ + fprintf(out,"\t%ld,\n",c->quantlist[j]); + } + fprintf(out,"};\n\n"); + } + + /* lengthlist */ + fprintf(out,"static const char _vq_lengthlist_%s[] = {\n",name); + for(j=0;j<c->entries;){ + fprintf(out,"\t"); + for(k=0;k<16 && j<c->entries;k++,j++) + fprintf(out,"%2ld,",c->lengthlist[j]); + fprintf(out,"\n"); + } + fprintf(out,"};\n\n"); + + /* tie it all together */ + + fprintf(out,"static const static_codebook %s = {\n",name); + + fprintf(out,"\t%ld, %ld,\n",c->dim,c->entries); + fprintf(out,"\t(char *)_vq_lengthlist_%s,\n",name); + fprintf(out,"\t%d, %ld, %ld, %d, %d,\n", + c->maptype,c->q_min,c->q_delta,c->q_quant,c->q_sequencep); + if(c->quantlist) + fprintf(out,"\t(long *)_vq_quantlist_%s,\n",name); + else + fprintf(out,"\tNULL,\n"); + + fprintf(out,"\t0\n};\n\n"); +} |