/********************************************************************
* *
* 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-2010 *
* by the Xiph.Org Foundation http://www.xiph.org/ *
* *
********************************************************************
function: utility functions for loading .vqh and .vqd files
last mod: $Id: bookutil.c 16959 2010-03-10 16:03:11Z xiphmont $
********************************************************************/
#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 long _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(long *)_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");
}