summaryrefslogtreecommitdiffhomepage
path: root/vorbis/vq/bookutil.c
diff options
context:
space:
mode:
Diffstat (limited to 'vorbis/vq/bookutil.c')
-rw-r--r--vorbis/vq/bookutil.c476
1 files changed, 0 insertions, 476 deletions
diff --git a/vorbis/vq/bookutil.c b/vorbis/vq/bookutil.c
deleted file mode 100644
index 3046410..0000000
--- a/vorbis/vq/bookutil.c
+++ /dev/null
@@ -1,476 +0,0 @@
-/********************************************************************
- * *
- * 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");
-}