/********************************************************************
* *
- * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE. *
- * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
- * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE. *
- * PLEASE READ THESE TERMS DISTRIBUTING. *
+ * 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 OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-2000 *
- * by Monty <monty@xiph.org> and The XIPHOPHORUS Company *
- * http://www.xiph.org/ *
+ * 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
- last mod: $Id: bookutil.c,v 1.7 2000/01/28 09:05:19 xiphmont Exp $
********************************************************************/
#include <math.h>
#include <string.h>
#include <errno.h>
-#include "vorbis/codebook.h"
#include "bookutil.h"
-void codebook_unquantize(codebook *b){
- long j,k;
- const static_codebook *c=b->c;
- double mindel=float24_unpack(c->q_min);
- double delta=float24_unpack(c->q_delta);
- if(!b->valuelist)b->valuelist=malloc(sizeof(double)*c->entries*c->dim);
-
- for(j=0;j<c->entries;j++){
- double last=0.;
- for(k=0;k<c->dim;k++){
- double val=c->quantlist[j*c->dim+k]*delta+last+mindel;
- b->valuelist[j*c->dim+k]=val;
- if(c->q_sequencep)last=val;
+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 */
if(sofar+1>=lbufsize){
if(!lbufsize){
lbufsize=1024;
- linebuffer=malloc(lbufsize);
+ linebuffer=_ogg_malloc(lbufsize);
}else{
lbufsize*=2;
- linebuffer=realloc(linebuffer,lbufsize);
+ linebuffer=_ogg_realloc(linebuffer,lbufsize);
}
}
{
long c=fgetc(in);
switch(c){
case EOF:
- if(sofar==0)return(NULL);
- /* fallthrough correct */
+ if(sofar==0)return(NULL);
+ /* fallthrough correct */
case '\n':
linebuffer[sofar]='\0';
gotline=1;
/* read the next numerical value from the given file */
static char *value_line_buff=NULL;
-int get_line_value(FILE *in,double *value){
+int get_line_value(FILE *in,float *value){
char *next;
if(!value_line_buff)return(-1);
return(-1);
}else{
value_line_buff=next;
- while(*value_line_buff>32)value_line_buff++;
+ while(*value_line_buff>44)value_line_buff++;
+ if(*value_line_buff==44)value_line_buff++;
return(0);
}
}
-int get_next_value(FILE *in,double *value){
+int get_next_value(FILE *in,float *value){
while(1){
if(get_line_value(in,value)){
value_line_buff=get_line(in);
}
int get_next_ivalue(FILE *in,long *ivalue){
- double value;
+ float value;
int ret=get_next_value(in,&value);
*ivalue=value;
return(ret);
}
-static double sequence_base=0.;
+static float sequence_base=0.f;
static int v_sofar=0;
void reset_next_value(void){
value_line_buff=NULL;
- sequence_base=0.;
+ sequence_base=0.f;
v_sofar=0;
}
-int get_vector(codebook *b,FILE *in,int start, int n,double *a){
+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;
if(v_sofar==n || get_line_value(in,a)){
reset_next_value();
if(get_next_value(in,a))
- break;
+ break;
for(i=0;i<start;i++){
- sequence_base=*a;
- get_line_value(in,a);
+ sequence_base=*a;
+ get_line_value(in,a);
}
}
for(i=1;i<c->dim;i++)
if(get_line_value(in,a+i))
- break;
+ break;
if(i==c->dim){
- double temp=a[c->dim-1];
+ 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.;
+ sequence_base=0.f;
}
return(-1);
char *line=get_line(in);
if(line){
if(strstr(line,s))
- return(line);
+ return(line);
}else
return(NULL);
}
}
-/* this reads the format as written by vqbuild; innocent (legal)
- tweaking of the file that would not affect its valid header-ness
- will break this routine */
+/* 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=calloc(1,sizeof(codebook));
- static_codebook *c=(static_codebook *)(b->c=calloc(1,sizeof(static_codebook)));
- encode_aux *a=calloc(1,sizeof(encode_aux));
+ 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;
- c->encode_tree=a;
-
if(in==NULL){
fprintf(stderr,"Couldn't open codebook %s\n",filename);
exit(1);
}
/* find the codebook struct */
- find_seek_to(in,"static static_codebook _vq_book_");
+ find_seek_to(in,"static const static_codebook ");
/* get the major important values */
line=get_line(in);
- if(sscanf(line,"%ld, %ld, %ld, %ld, %d, %d",
- &(c->dim),&(c->entries),&(c->q_min),&(c->q_delta),&(c->q_quant),
- &(c->q_sequencep))!=6){
+ if(sscanf(line,"%ld, %ld,",
+ &(c->dim),&(c->entries))!=2){
fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);
exit(1);
}
-
- /* find the auxiliary encode struct (if any) */
- find_seek_to(in,"static encode_aux _vq_aux_");
- /* how big? */
- line=get_line(in);
- line=get_line(in);
- line=get_line(in);
line=get_line(in);
line=get_line(in);
- if(sscanf(line,"%ld, %ld",&(a->aux),&(a->alloc))!=2){
- fprintf(stderr,"2: syntax in %s in line:\t %s",filename,line);
+ 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 long _vq_quantlist_");
+ find_seek_to(in,"static const long _vq_quantlist_");
reset_next_value();
- c->quantlist=malloc(sizeof(long)*c->entries*c->dim);
- for(i=0;i<c->entries*c->dim;i++)
+ 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,"static long _vq_lengthlist");
+ find_seek_to(in,"_lengthlist");
reset_next_value();
- c->lengthlist=malloc(sizeof(long)*c->entries);
+ 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);
}
- /* load ptr0 */
- find_seek_to(in,"static long _vq_ptr0");
- reset_next_value();
- a->ptr0=malloc(sizeof(long)*a->aux);
- for(i=0;i<a->aux;i++)
- if(get_next_ivalue(in,a->ptr0+i)){
- fprintf(stderr,"out of data while reading codebook %s\n",filename);
- exit(1);
- }
-
- /* load ptr1 */
- find_seek_to(in,"static long _vq_ptr1");
- reset_next_value();
- a->ptr1=malloc(sizeof(long)*a->aux);
- for(i=0;i<a->aux;i++)
- if(get_next_ivalue(in,a->ptr1+i)){
- fprintf(stderr,"out of data while reading codebook %s\n",filename);
- exit(1);
- }
-
-
- /* load p */
- find_seek_to(in,"static long _vq_p_");
- reset_next_value();
- a->p=malloc(sizeof(long)*a->aux);
- for(i=0;i<a->aux;i++)
- if(get_next_ivalue(in,a->p+i)){
- fprintf(stderr,"out of data while reading codebook %s\n",filename);
- exit(1);
- }
-
- /* load q */
- find_seek_to(in,"static long _vq_q_");
- reset_next_value();
- a->q=malloc(sizeof(long)*a->aux);
- for(i=0;i<a->aux;i++)
- if(get_next_ivalue(in,a->q+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);
- /* might as well unquantize the entries while we're at it */
- codebook_unquantize(b);
-
- /* don't need n and c */
return(b);
}
-int codebook_entry(codebook *b,double *val){
- const static_codebook *c=b->c;
- encode_aux *t=c->encode_tree;
- int ptr=0,k;
- double *n=alloca(c->dim*sizeof(double));
-
- while(1){
- double C=0.;
- double *p=b->valuelist+t->p[ptr]*c->dim;
- double *q=b->valuelist+t->q[ptr]*c->dim;
-
- for(k=0;k<c->dim;k++){
- n[k]=p[k]-q[k];
- C-=(p[k]+q[k])*n[k];
- }
- C/=2.;
-
- for(k=0;k<c->dim;k++)
- C+=n[k]*val[k];
- if(C>0.) /* in A */
- ptr= -t->ptr0[ptr];
- else /* in B */
- ptr= -t->ptr1[ptr];
- if(ptr<=0)break;
- }
- return(-ptr);
-}
-
-/* 24 bit float (not IEEE; nonnormalized mantissa +
- biased exponent ): neeeeemm mmmmmmmm mmmmmmmm */
-
-long float24_pack(double val){
- int sign=0;
- long exp;
- long mant;
- if(val<0){
- sign=0x800000;
- val= -val;
- }
- exp= floor(log(val)/log(2));
- mant=rint(ldexp(val,17-exp));
- exp=(exp+VQ_FEXP_BIAS)<<18;
-
- return(sign|exp|mant);
-}
-
-double float24_unpack(long val){
- double mant=val&0x3ffff;
- double sign=val&0x800000;
- double exp =(val&0x7c0000)>>18;
- if(sign)mant= -mant;
- return(ldexp(mant,exp-17-VQ_FEXP_BIAS));
-}
-
void spinnit(char *s,int n){
static int p=0;
static long lasttime=0;
}
}
+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");
+}
projects / platform / upstream / libvorbis.git / blobdiff