From 9229b7bf381246b5cf6c1ac47dd65eb94eda3d72 Mon Sep 17 00:00:00 2001 From: Monty Date: Wed, 10 Mar 2010 16:03:11 +0000 Subject: [PATCH] Update the VQ tools to pared down codebook abstraction. Eliminate long unused tools; they're still in SVN. svn path=/trunk/vorbis/; revision=16959 --- vq/Makefile.am | 7 +- vq/bookutil.c | 370 +++-------------------------- vq/huffbuild.c | 3 - vq/latticehint.c | 430 ---------------------------------- vq/latticepare.c | 595 ----------------------------------------------- vq/localcodebook.h | 46 +--- vq/make_residue_books.pl | 26 +-- 7 files changed, 47 insertions(+), 1430 deletions(-) delete mode 100644 vq/latticehint.c delete mode 100644 vq/latticepare.c diff --git a/vq/Makefile.am b/vq/Makefile.am index 2dc8a7a..f68fdbc 100644 --- a/vq/Makefile.am +++ b/vq/Makefile.am @@ -2,8 +2,7 @@ INCLUDES = -I../lib -I$(top_srcdir)/include @OGG_CFLAGS@ -EXTRA_PROGRAMS = latticebuild latticepare latticehint\ - latticetune huffbuild distribution +EXTRA_PROGRAMS = latticebuild latticetune huffbuild distribution CLEANFILES = $(EXTRA_PROGRAMS) AM_LDFLAGS = -static @@ -11,10 +10,6 @@ LDADD = ../lib/libvorbis.la latticebuild_SOURCES = latticebuild.c vqgen.c bookutil.c\ vqgen.h bookutil.h localcodebook.h -latticepare_SOURCES = latticepare.c vqgen.c bookutil.c vqsplit.c\ - vqgen.h vqsplit.h bookutil.h localcodebook.h -latticehint_SOURCES = latticehint.c bookutil.c\ - vqsplit.h bookutil.h localcodebook.h latticetune_SOURCES = latticetune.c vqgen.c bookutil.c\ vqgen.h bookutil.h localcodebook.h huffbuild_SOURCES = huffbuild.c vqgen.c bookutil.c\ diff --git a/vq/bookutil.c b/vq/bookutil.c index 0579362..95b5731 100644 --- a/vq/bookutil.c +++ b/vq/bookutil.c @@ -5,7 +5,7 @@ * 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-2001 * + * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2010 * * by the Xiph.Org Foundation http://www.xiph.org/ * * * ******************************************************************** @@ -22,69 +22,61 @@ #include #include "bookutil.h" +int _best(codebook *book, float *a, int step){ -/* as of current encoder, only centered, integer val, maptype 1 is in - use */ -int _best(codebook *book, int *a, int step){ int dim=book->dim; - int k,o; + 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(delta!=1){ - for(k=0,o=step*(dim-1);k>1))/delta; + if(del!=1){ + for(i=0,o=step*(dim-1);i>1))/del; int m = (v=qv?qv-1:m)); } }else{ - for(k=0,o=step*(dim-1);k=qv?qv-1:m)); } } - /* did the direct lookup find a used entry? */ - if(book->c->lengthlist[index]>0) - return(index); - - /* brute force it */ - { + if(book->c->lengthlist[index]<=0){ const static_codebook *c=book->c; - int i,besti=-1; - float best=0.f; - float *e=book->valuelist; + 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;ientries;i++){ if(c->lengthlist[i]>0){ - float this=_dist(dim,e,a,step); - if(besti==-1 || this=maxval) + e[j++]=0; + if(e[j]>=0) + e[j]+=book->delta; + e[j]= -e[j]; } - - /*if(savebest!=-1 && savebest!=besti){ - fprintf(stderr,"brute force/pigeonhole disagreement:\n" - "original:"); - for(i=0;ivaluelist+savebest*dim)[i]); - fprintf(stderr,"\n" - "bruteforce (entry %d, err %g):",besti,best); - for(i=0;ivaluelist+besti*dim)[i]); - fprintf(stderr,"\n"); - }*/ - return(besti); } -} + return index; +} /* A few little utils for reading files */ /* read a line. Use global, persistent buffering */ @@ -241,9 +233,6 @@ char *find_seek_to(FILE *in,char *s){ 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))); - encode_aux_nearestmatch *a=NULL; - encode_aux_threshmatch *t=NULL; - encode_aux_pigeonhole *p=NULL; int quant_to_read=0; FILE *in=fopen(filename,"r"); char *line; @@ -273,153 +262,6 @@ codebook *codebook_load(char *filename){ exit(1); } - /* find the auxiliary encode struct[s] (if any) */ - if(find_seek_to(in,"static const encode_aux_nearestmatch _vq_aux")){ - /* how big? */ - c->nearest_tree=a=_ogg_calloc(1,sizeof(encode_aux_nearestmatch)); - 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); - exit(1); - } - - /* load ptr0 */ - find_seek_to(in,"static const long _vq_ptr0"); - reset_next_value(); - a->ptr0=_ogg_malloc(sizeof(long)*a->aux); - for(i=0;iaux;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 const long _vq_ptr1"); - reset_next_value(); - a->ptr1=_ogg_malloc(sizeof(long)*a->aux); - for(i=0;iaux;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 const long _vq_p_"); - reset_next_value(); - a->p=_ogg_malloc(sizeof(long)*a->aux); - for(i=0;iaux;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 const long _vq_q_"); - reset_next_value(); - a->q=_ogg_malloc(sizeof(long)*a->aux); - for(i=0;iaux;i++) - if(get_next_ivalue(in,a->q+i)){ - fprintf(stderr,"out of data while reading codebook %s\n",filename); - exit(1); - } - } - - if(find_seek_to(in,"static const encode_aux_threshmatch _vq_aux")){ - /* how big? */ - c->thresh_tree=t=_ogg_calloc(1,sizeof(encode_aux_threshmatch)); - line=get_line(in); - line=get_line(in); - line=get_line(in); - if(sscanf(line,"%d",&(t->quantvals))!=1){ - fprintf(stderr,"3: syntax in %s in line:\t %s",filename,line); - exit(1); - } - line=get_line(in); - if(sscanf(line,"%d",&(t->threshvals))!=1){ - fprintf(stderr,"4: syntax in %s in line:\t %s",filename,line); - exit(1); - } - /* load quantthresh */ - find_seek_to(in,"static const float _vq_quantthresh_"); - reset_next_value(); - t->quantthresh=_ogg_malloc(sizeof(float)*t->threshvals); - for(i=0;ithreshvals-1;i++) - if(get_next_value(in,t->quantthresh+i)){ - fprintf(stderr,"out of data 1 while reading codebook %s\n",filename); - exit(1); - } - /* load quantmap */ - find_seek_to(in,"static const long _vq_quantmap_"); - reset_next_value(); - t->quantmap=_ogg_malloc(sizeof(long)*t->threshvals); - for(i=0;ithreshvals;i++) - if(get_next_ivalue(in,t->quantmap+i)){ - fprintf(stderr,"out of data 2 while reading codebook %s\n",filename); - exit(1); - } - } - - if(find_seek_to(in,"static const encode_aux_pigeonhole _vq_aux")){ - int pigeons=1,i; - /* how big? */ - c->pigeon_tree=p=_ogg_calloc(1,sizeof(encode_aux_pigeonhole)); - line=get_line(in); - if(sscanf(line,"%f, %f, %d, %d",&(p->min),&(p->del), - &(p->mapentries),&(p->quantvals))!=4){ - fprintf(stderr,"5: syntax in %s in line:\t %s",filename,line); - exit(1); - } - line=get_line(in); - line=get_line(in); - if(sscanf(line,"%ld",&(p->fittotal))!=1){ - fprintf(stderr,"6: syntax in %s in line:\t %s",filename,line); - exit(1); - } - /* load pigeonmap */ - find_seek_to(in,"static const long _vq_pigeonmap_"); - reset_next_value(); - p->pigeonmap=_ogg_malloc(sizeof(long)*p->mapentries); - for(i=0;imapentries;i++) - if(get_next_ivalue(in,p->pigeonmap+i)){ - fprintf(stderr,"out of data (pigeonmap) while reading codebook %s\n",filename); - exit(1); - } - /* load fitlist */ - find_seek_to(in,"static const long _vq_fitlist_"); - reset_next_value(); - p->fitlist=_ogg_malloc(sizeof(long)*p->fittotal); - for(i=0;ifittotal;i++) - if(get_next_ivalue(in,p->fitlist+i)){ - fprintf(stderr,"out of data (fitlist) while reading codebook %s\n",filename); - exit(1); - } - /* load fitmap */ - find_seek_to(in,"static const long _vq_fitmap_"); - reset_next_value(); - for(i=0;idim;i++)pigeons*=p->quantvals; - p->fitmap=_ogg_malloc(sizeof(long)*pigeons); - for(i=0;ifitmap+i)){ - fprintf(stderr,"out of data (fitmap) while reading codebook %s\n",filename); - exit(1); - } - - /* load fitlength */ - find_seek_to(in,"static const long _vq_fitlength_"); - reset_next_value(); - p->fitlength=_ogg_malloc(sizeof(long)*pigeons); - for(i=0;ifitlength+i)){ - fprintf(stderr,"out of data (fitlength) while reading codebook %s\n",filename); - exit(1); - } - } - switch(c->maptype){ case 0: quant_to_read=0; @@ -456,6 +298,7 @@ codebook *codebook_load(char *filename){ fclose(in); vorbis_book_init_encode(b,c); + b->valuelist=_book_unquantize(c,c->entries,NULL); return(b); } @@ -592,9 +435,6 @@ void build_tree_from_lengths0(int vals, long *hist, long *lengths){ } void write_codebook(FILE *out,char *name,const static_codebook *c){ - encode_aux_pigeonhole *p=c->pigeon_tree; - encode_aux_threshmatch *t=c->thresh_tree; - encode_aux_nearestmatch *n=c->nearest_tree; int i,j,k; /* save the book in C header form */ @@ -620,137 +460,6 @@ void write_codebook(FILE *out,char *name,const static_codebook *c){ } fprintf(out,"};\n\n"); - if(t){ - /* quantthresh */ - fprintf(out,"static const float _vq_quantthresh_%s[] = {\n",name); - for(j=0;jthreshvals-1;){ - fprintf(out,"\t"); - for(k=0;k<8 && jthreshvals-1;k++,j++) - fprintf(out,"%.5g, ",t->quantthresh[j]); - fprintf(out,"\n"); - } - fprintf(out,"};\n\n"); - - /* quantmap */ - fprintf(out,"static const long _vq_quantmap_%s[] = {\n",name); - for(j=0;jthreshvals;){ - fprintf(out,"\t"); - for(k=0;k<8 && jthreshvals;k++,j++) - fprintf(out,"%5ld,",t->quantmap[j]); - fprintf(out,"\n"); - } - fprintf(out,"};\n\n"); - - fprintf(out,"static const encode_aux_threshmatch _vq_auxt_%s = {\n",name); - fprintf(out,"\t(float *)_vq_quantthresh_%s,\n",name); - fprintf(out,"\t(long *)_vq_quantmap_%s,\n",name); - fprintf(out,"\t%d,\n",t->quantvals); - fprintf(out,"\t%d\n};\n\n",t->threshvals); - } - - if(p){ - int pigeons=1; - for(i=0;idim;i++)pigeons*=p->quantvals; - - /* pigeonmap */ - fprintf(out,"static const long _vq_pigeonmap_%s[] = {\n",name); - for(j=0;jmapentries;){ - fprintf(out,"\t"); - for(k=0;k<8 && jmapentries;k++,j++) - fprintf(out,"%5ld, ",p->pigeonmap[j]); - fprintf(out,"\n"); - } - fprintf(out,"};\n\n"); - /* fitlist */ - fprintf(out,"static const long _vq_fitlist_%s[] = {\n",name); - for(j=0;jfittotal;){ - fprintf(out,"\t"); - for(k=0;k<8 && jfittotal;k++,j++) - fprintf(out,"%5ld, ",p->fitlist[j]); - fprintf(out,"\n"); - } - fprintf(out,"};\n\n"); - /* fitmap */ - fprintf(out,"static const long _vq_fitmap_%s[] = {\n",name); - for(j=0;jfitmap[j]); - fprintf(out,"\n"); - } - fprintf(out,"};\n\n"); - /* fitlength */ - fprintf(out,"static const long _vq_fitlength_%s[] = {\n",name); - for(j=0;jfitlength[j]); - fprintf(out,"\n"); - } - fprintf(out,"};\n\n"); - - fprintf(out,"static const encode_aux_pigeonhole _vq_auxp_%s = {\n",name); - fprintf(out,"\t%g, %g, %d, %d,\n", - p->min,p->del,p->mapentries,p->quantvals); - - fprintf(out,"\t_vq_pigeonmap_%s,\n",name); - - fprintf(out,"\t%ld,\n",p->fittotal); - fprintf(out,"\t(long *)_vq_fitlist_%s,\n",name); - fprintf(out,"\t(long *)_vq_fitmap_%s,\n",name); - fprintf(out,"\t(long *)_vq_fitlength_%s\n};\n\n",name); - } - - if(n){ - - /* ptr0 */ - fprintf(out,"static const long _vq_ptr0_%s[] = {\n",name); - for(j=0;jaux;){ - fprintf(out,"\t"); - for(k=0;k<8 && jaux;k++,j++) - fprintf(out,"%6ld,",n->ptr0[j]); - fprintf(out,"\n"); - } - fprintf(out,"};\n\n"); - - /* ptr1 */ - fprintf(out,"static const long _vq_ptr1_%s[] = {\n",name); - for(j=0;jaux;){ - fprintf(out,"\t"); - for(k=0;k<8 && jaux;k++,j++) - fprintf(out,"%6ld,",n->ptr1[j]); - fprintf(out,"\n"); - } - fprintf(out,"};\n\n"); - - /* p */ - fprintf(out,"static const long _vq_p_%s[] = {\n",name); - for(j=0;jaux;){ - fprintf(out,"\t"); - for(k=0;k<8 && jaux;k++,j++) - fprintf(out,"%6ld,",n->p[j]*c->dim); - fprintf(out,"\n"); - } - fprintf(out,"};\n\n"); - - /* q */ - fprintf(out,"static const long _vq_q_%s[] = {\n",name); - for(j=0;jaux;){ - fprintf(out,"\t"); - for(k=0;k<8 && jaux;k++,j++) - fprintf(out,"%6ld,",n->q[j]*c->dim); - fprintf(out,"\n"); - } - fprintf(out,"};\n\n"); - - fprintf(out,"static const encode_aux_nearestmatch _vq_auxn_%s = {\n",name); - fprintf(out,"\t(long *)_vq_ptr0_%s,\n",name); - fprintf(out,"\t(long *)_vq_ptr1_%s,\n",name); - fprintf(out,"\t(long *)_vq_p_%s,\n",name); - fprintf(out,"\t(long *)_vq_q_%s,\n",name); - fprintf(out,"\t%ld, %ld\n};\n\n",n->aux,n->aux); - } - /* tie it all together */ fprintf(out,"static const static_codebook %s = {\n",name); @@ -764,18 +473,5 @@ void write_codebook(FILE *out,char *name,const static_codebook *c){ else fprintf(out,"\tNULL,\n"); - if(n) - fprintf(out,"\t(encode_aux_nearestmatch *)&_vq_auxn_%s,\n",name); - else - fprintf(out,"\tNULL,\n"); - if(t) - fprintf(out,"\t(encode_aux_threshmatch *)&_vq_auxt_%s,\n",name); - else - fprintf(out,"\tNULL,\n"); - if(p) - fprintf(out,"\t(encode_aux_pigeonhole *)&_vq_auxp_%s,\n",name); - else - fprintf(out,"\tNULL,\n"); - fprintf(out,"\t0\n};\n\n"); } diff --git a/vq/huffbuild.c b/vq/huffbuild.c index 2583211..9864acd 100644 --- a/vq/huffbuild.c +++ b/vq/huffbuild.c @@ -178,9 +178,6 @@ int main(int argc, char *argv[]){ fprintf(file,"\t0, 0, 0, 0, 0,\n"); fprintf(file,"\tNULL,\n"); - fprintf(file,"\tNULL,\n"); - fprintf(file,"\tNULL,\n"); - fprintf(file,"\tNULL,\n"); fprintf(file,"\t0\n};\n\n"); fclose(file); diff --git a/vq/latticehint.c b/vq/latticehint.c deleted file mode 100644 index 8bdf36e..0000000 --- a/vq/latticehint.c +++ /dev/null @@ -1,430 +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-2001 * - * by the Xiph.Org Foundation http://www.xiph.org/ * - * * - ******************************************************************** - - function: utility main for building thresh/pigeonhole encode hints - last mod: $Id$ - - ********************************************************************/ - -#include -#include -#include -#include -#include -#include "../lib/scales.h" -#include "bookutil.h" -#include "vqgen.h" -#include "vqsplit.h" - -/* The purpose of this util is to build encode hints for lattice - codebooks so that brute forcing each codebook entry isn't needed. - Threshhold hints are for books in which each scalar in the vector - is independant (eg, residue) and pigeonhole lookups provide a - minimum error fit for words where the scalars are interdependant - (each affecting the fit of the next in sequence) as in an LSP - sequential book (or can be used along with a sparse threshhold map, - like a splitting tree that need not be trained) - - If the input book is non-sequential, a threshhold hint is built. - If the input book is sequential, a pigeonholing hist is built. - If the book is sparse, a pigeonholing hint is built, possibly in addition - to the threshhold hint - - command line: - latticehint book.vqh [threshlist] - - latticehint produces book.vqh on stdout */ - -static int longsort(const void *a, const void *b){ - return(**((long **)a)-**((long **)b)); -} - -static int addtosearch(int entry,long **tempstack,long *tempcount,int add){ - long *ptr=tempstack[entry]; - long i=tempcount[entry]; - - if(ptr){ - while(i--) - if(*ptr++==add)return(0); - tempstack[entry]=_ogg_realloc(tempstack[entry], - (tempcount[entry]+1)*sizeof(long)); - }else{ - tempstack[entry]=_ogg_malloc(sizeof(long)); - } - - tempstack[entry][tempcount[entry]++]=add; - return(1); -} - -static void setvals(int dim,encode_aux_pigeonhole *p, - long *temptrack,float *tempmin,float *tempmax, - int seqp){ - int i; - float last=0.f; - for(i=0;idel+p->min+last; - tempmax[i]=tempmin[i]+p->del; - if(seqp)last=tempmin[i]; - } -} - -/* note that things are currently set up such that input fits that - quantize outside the pigeonmap are dropped and brute-forced. So we - can ignore the <0 and >=n boundary cases in min/max error */ - -static float minerror(int dim,float *a,encode_aux_pigeonhole *p, - long *temptrack,float *tempmin,float *tempmax){ - int i; - float err=0.f; - for(i=0;itempmax[i]){ - eval=a[i]-tempmax[i]; - } - err+=eval*eval; - } - return(err); -} - -static float maxerror(int dim,float *a,encode_aux_pigeonhole *p, - long *temptrack,float *tempmin,float *tempmax){ - int i; - float err=0.f,eval; - for(i=0;itempmax[i]){ - eval=a[i]-tempmin[i]; - }else{ - float t1=a[i]-tempmin[i]; - eval=tempmax[i]-a[i]; - if(t1>eval)eval=t1; - } - err+=eval*eval; - } - return(err); -} - -int main(int argc,char *argv[]){ - codebook *b; - static_codebook *c; - int entries=-1,dim=-1; - float min,del; - char *name; - long i,j; - float *suggestions; - int suggcount=0; - - if(argv[1]==NULL){ - fprintf(stderr,"Need a lattice book on the command line.\n"); - exit(1); - } - - { - char *ptr; - char *filename=strdup(argv[1]); - - b=codebook_load(filename); - c=(static_codebook *)(b->c); - - ptr=strrchr(filename,'.'); - if(ptr){ - *ptr='\0'; - name=strdup(filename); - }else{ - name=strdup(filename); - } - } - - if(c->maptype!=1){ - fprintf(stderr,"Provided book is not a latticebook.\n"); - exit(1); - } - - entries=b->entries; - dim=b->dim; - min=_float32_unpack(c->q_min); - del=_float32_unpack(c->q_delta); - - /* Do we want to gen a threshold hint? */ - if(c->q_sequencep==0){ - /* yes. Discard any preexisting threshhold hint */ - long quantvals=_book_maptype1_quantvals(c); - long **quantsort=alloca(quantvals*sizeof(long *)); - encode_aux_threshmatch *t=_ogg_calloc(1,sizeof(encode_aux_threshmatch)); - c->thresh_tree=t; - - fprintf(stderr,"Adding threshold hint to %s...\n",name); - - /* partial/complete suggestions */ - if(argv[2]){ - char *ptr=strdup(argv[2]); - suggestions=alloca(sizeof(float)*quantvals); - - for(suggcount=0;ptr && suggcountquantthresh=_ogg_calloc(quantvals-1,sizeof(float)); - t->quantmap=_ogg_calloc(quantvals,sizeof(int)); - t->threshvals=quantvals; - t->quantvals=quantvals; - - /* the quantvals may not be in order; sort em first */ - for(i=0;iquantlist+i; - qsort(quantsort,quantvals,sizeof(long *),longsort); - - /* ok, gen the map and thresholds */ - for(i=0;iquantmap[i]=quantsort[i]-c->quantlist; - for(i=0;iquantthresh[i]=suggestions[j]; - break; - } - - if(j==suggcount){ - t->quantthresh[i]=(v1+v2)*.5; - } - } - } - - /* Do we want to gen a pigeonhole hint? */ -#if 0 - for(i=0;ilengthlist[i]==0)break; - if(c->q_sequencep || ipigeon_tree=p; - - fprintf(stderr,"Adding pigeonhole hint to %s...\n",name); - - /* the idea is that we quantize uniformly, even in a nonuniform - lattice, so that quantization of one scalar has a predictable - result on the next sequential scalar in a greedy matching - algorithm. We generate a lookup based on the quantization of - the vector (pigeonmap groups quantized entries together) and - list the entries that could possible be the best fit for any - given member of that pigeonhole. The encode process then has a - much smaller list to brute force */ - - /* find our pigeonhole-specific quantization values, fill in the - quant value->pigeonhole map */ - factor=3; - p->del=del; - p->min=min; - p->quantvals=quantvals; - { - int max=0; - for(i=0;iquantlist[i])max=c->quantlist[i]; - p->mapentries=max; - } - p->pigeonmap=_ogg_malloc(p->mapentries*sizeof(long)); - p->quantvals=(quantvals+factor-1)/factor; - - /* pigeonhole roughly on the boundaries of the quantvals; the - exact pigeonhole grouping is an optimization issue, not a - correctness issue */ - for(i=0;imapentries;i++){ - float thisval=del*i+min; /* middle of the quant zone */ - int quant=0; - float err=fabs(c->quantlist[0]*del+min-thisval); - for(j=1;jquantlist[j]*del+min-thisval); - if(thiserrpigeonmap[i]=quant; - } - - /* pigeonmap complete. Now do the grungy business of finding the - entries that could possibly be the best fit for a value appearing - in the pigeonhole. The trick that allows the below to work is the - uniform quantization; even though the scalars may be 'sequential' - (each a delta from the last), the uniform quantization means that - the error variance is *not* dependant. Given a pigeonhole and an - entry, we can find the minimum and maximum possible errors - (relative to the entry) for any point that could appear in the - pigeonhole */ - - /* must iterate over both pigeonholes and entries */ - /* temporarily (in order to avoid thinking hard), we grow each - pigeonhole seperately, the build a stack of 'em later */ - pigeons=1; - subpigeons=1; - for(i=0;imapentries; - for(i=0;iquantvals; - temptrack=_ogg_calloc(dim,sizeof(long)); - tempmin=_ogg_calloc(dim,sizeof(float)); - tempmax=_ogg_calloc(dim,sizeof(float)); - tempstack=_ogg_calloc(pigeons,sizeof(long *)); - tempcount=_ogg_calloc(pigeons,sizeof(long)); - - while(1){ - float errorpost=-1; - char buffer[80]; - - /* map our current pigeonhole to a 'big pigeonhole' so we know - what list we're after */ - int entry=0; - for(i=dim-1;i>=0;i--)entry=entry*p->quantvals+p->pigeonmap[temptrack[i]]; - setvals(dim,p,temptrack,tempmin,tempmax,c->q_sequencep); - sprintf(buffer,"Building pigeonhole search list [%ld]...",totalstack); - - - /* Search all entries to find the one with the minimum possible - maximum error. Record that error */ - for(i=0;ilengthlist[i]>0){ - float this=maxerror(dim,b->valuelist+i*dim,p, - temptrack,tempmin,tempmax); - if(errorpost==-1 || thislengthlist[i]>0){ - spinnit(buffer,subpigeons); - if(minerror(dim,b->valuelist+i*dim,p, - temptrack,tempmin,tempmax)mapentries)break; - temptrack[i]=0; - } - if(i==dim)break; - subpigeons--; - } - - fprintf(stderr,"\r " - "\rTotal search list size (all entries): %ld\n",totalstack); - - /* pare the index of lists for improbable quantizations (where - improbable is determined by c->lengthlist; we assume that - pigeonholing is in sync with the codeword cells, which it is */ - /*for(i=0;ilengthlist[i]); - if(c->lengthlist[i]==0 || probability*entriesfitmap=_ogg_malloc(pigeons*sizeof(long)); - for(i=0;ifitmap[i]=-1; - while(changep){ - char buffer[80]; - changep=0; - - for(i=0;ifitmap[i]<0 && tempcount[i]){ - for(j=i+1;jfitmap[j]<0 && tempcount[j]){ - /* is one list a superset, or are they sufficiently similar? */ - int amiss=0,bmiss=0,ii,jj; - for(ii=0;iifitmap[j]=i; - changep=1; - } - } - } - sprintf(buffer,"Consolidating [%ld total, %s]... ",totalstack, - changep?"reit":"nochange"); - spinnit(buffer,pigeons-i); - } - } - } - - /* repack the temp stack in final form */ - fprintf(stderr,"\r " - "\rFinal total list size: %ld\n",totalstack); - - - p->fittotal=totalstack; - p->fitlist=_ogg_malloc((totalstack+1)*sizeof(long)); - p->fitlength=_ogg_malloc(pigeons*sizeof(long)); - { - long usage=0; - for(i=0;ifitmap[i]==-1){ - if(tempcount[i]) - memcpy(p->fitlist+usage,tempstack[i],tempcount[i]*sizeof(long)); - p->fitmap[i]=usage; - p->fitlength[i]=tempcount[i]; - usage+=tempcount[i]; - if(usage>totalstack){ - fprintf(stderr,"Internal error; usage>totalstack\n"); - exit(1); - } - }else{ - p->fitlength[i]=p->fitlength[p->fitmap[i]]; - p->fitmap[i]=p->fitmap[p->fitmap[i]]; - } - } - } - } -#endif - - write_codebook(stdout,name,c); - fprintf(stderr,"\r " - "\nDone.\n"); - exit(0); -} diff --git a/vq/latticepare.c b/vq/latticepare.c deleted file mode 100644 index c7ac068..0000000 --- a/vq/latticepare.c +++ /dev/null @@ -1,595 +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-2001 * - * by the Xiph.Org Foundation http://www.xiph.org/ * - * * - ******************************************************************** - - function: utility for paring low hit count cells from lattice codebook - last mod: $Id$ - - ********************************************************************/ - -#include -#include -#include -#include -#include -#include "../lib/scales.h" -#include "bookutil.h" -#include "vqgen.h" -#include "vqsplit.h" -#include "../lib/os.h" - -/* Lattice codebooks have two strengths: important fetaures that are - poorly modelled by global error minimization training (eg, strong - peaks) are not neglected 2) compact quantized representation. - - A fully populated lattice codebook, however, swings point 1 too far - in the opposite direction; rare features need not be modelled quite - so religiously and as such, we waste bits unless we eliminate the - least common cells. The codebook rep supports unused cells, so we - need to tag such cells and build an auxiliary (non-thresh) search - mechanism to find the proper match quickly */ - -/* two basic steps; first is pare the cell for which dispersal creates - the least additional error. This will naturally choose - low-population cells and cells that have not taken on points from - neighboring paring (but does not result in the lattice collapsing - inward and leaving low population ares totally unmodelled). After - paring has removed the desired number of cells, we need to build an - auxiliary search for each culled point */ - -/* Although lattice books (due to threshhold-based matching) do not - actually use error to make cell selections (in fact, it need not - bear any relation), the 'secondbest' entry finder here is in fact - error/distance based, so latticepare is only useful on such books */ - -/* command line: - latticepare latticebook.vqh input_data.vqd - - produces a new output book on stdout -*/ - -static float _dist(int el,float *a, float *b){ - int i; - float acc=0.f; - for(i=0;idim,i,j; - int step=n/dim; - for(i=0;ic->thresh_tree; - int dim=b->dim; - int i,k,o; - int best=0; - - /* what would be the closest match if the codebook was fully - populated? */ - - for(k=0,o=dim-1;kthreshvals-1;i++) - if(vec[o]quantthresh[i])break; - best=(best*tt->quantvals)+tt->quantmap[i]; - } - return(best); -} - -static int closest(codebook *b,float *vec,int current){ - encode_aux_threshmatch *tt=b->c->thresh_tree; - int dim=b->dim; - int i,k,o; - - float bestmetric=0; - int bestentry=-1; - int best=bestm(b,vec); - - if(current<0 && b->c->lengthlist[best]>0)return best; - - for(i=0;ientries;i++){ - if(b->c->lengthlist[i]>0 && i!=best && i!=current){ - float thismetric=_dist(dim, vec, b->valuelist+i*dim); - if(bestentry==-1 || thismetricvaluelist+secondbest*b->dim; - int best=bestm(b,ppt); - float *firstcell=b->valuelist+best*b->dim; - float error=_dist(b->dim,firstcell,secondcell); - float *zero=alloca(b->dim*sizeof(float)); - float fromzero; - - memset(zero,0,b->dim*sizeof(float)); - fromzero=sqrt(_dist(b->dim,firstcell,zero)); - - return(error/fromzero); -} - -static int longsort(const void *a, const void *b){ - return **(long **)b-**(long **)a; -} - -void usage(void){ - fprintf(stderr,"Ogg/Vorbis lattice codebook paring utility\n\n" - "usage: latticepare book.vqh data.vqd base\n" - "where is the desired number of final cells (or -1\n" - " for no change)\n" - " is the number of highest-hit count cells\n" - " to protect from dispersal\n" - " base is the base name (not including .vqh) of the new\n" - " book\n\n"); - exit(1); -} - -int main(int argc,char *argv[]){ - char *basename; - codebook *b=NULL; - int entries=0; - int dim=0; - long i,j,target=-1,protect=-1; - FILE *out=NULL; - - int argnum=0; - - argv++; - if(*argv==NULL){ - usage(); - exit(1); - } - - while(*argv){ - if(*argv[0]=='-'){ - - argv++; - - }else{ - switch (argnum++){ - case 0:case 1: - { - /* yes, this is evil. However, it's very convenient to parse file - extentions */ - - /* input file. What kind? */ - char *dot; - char *ext=NULL; - char *name=strdup(*argv++); - dot=strrchr(name,'.'); - if(dot) - ext=dot+1; - else{ - ext=""; - - } - - - /* codebook */ - if(!strcmp(ext,"vqh")){ - - basename=strrchr(name,'/'); - if(basename) - basename=strdup(basename)+1; - else - basename=strdup(name); - dot=strrchr(basename,'.'); - if(dot)*dot='\0'; - - b=codebook_load(name); - dim=b->dim; - entries=b->entries; - } - - /* data file; we do actually need to suck it into memory */ - /* we're dealing with just one book, so we can de-interleave */ - if(!strcmp(ext,"vqd") && !points){ - int cols; - long lines=0; - char *line; - float *vec; - FILE *in=fopen(name,"r"); - if(!in){ - fprintf(stderr,"Could not open input file %s\n",name); - exit(1); - } - - reset_next_value(); - line=setup_line(in); - /* count cols before we start reading */ - { - char *temp=line; - while(*temp==' ')temp++; - for(cols=0;*temp;cols++){ - while(*temp>32)temp++; - while(*temp==' ')temp++; - } - } - vec=alloca(cols*sizeof(float)); - /* count, then load, to avoid fragmenting the hell out of - memory */ - while(line){ - lines++; - for(j=0;jvaluelist[i*dim+j]; - - points/=dim; - - /* set up auxiliary vectors for error tracking */ - { - encode_aux_nearestmatch *nt=NULL; - long pointssofar=0; - long *pointindex; - long indexedpoints=0; - long *entryindex; - long *reventry; - long *membership=_ogg_malloc(points*sizeof(long)); - long *firsthead=_ogg_malloc(entries*sizeof(long)); - long *secondary=_ogg_malloc(points*sizeof(long)); - long *secondhead=_ogg_malloc(entries*sizeof(long)); - - long *cellcount=_ogg_calloc(entries,sizeof(long)); - long *cellcount2=_ogg_calloc(entries,sizeof(long)); - float *cellerror=_ogg_calloc(entries,sizeof(float)); - float *cellerrormax=_ogg_calloc(entries,sizeof(float)); - long cellsleft=entries; - for(i=0;ivaluelist+dim*firstentry,ppt); - float secondmetric=_dist(dim,b->valuelist+dim*secondentry,ppt); - - if(!(i&0xff))spinnit("initializing... ",points-i); - - membership[i]=firsthead[firstentry]; - firsthead[firstentry]=i; - secondary[i]=secondhead[secondentry]; - secondhead[secondentry]=i; - - if(ic->thresh_tree->quantvals); - entry/=b->c->thresh_tree->quantvals; - } - - fprintf(stderr,":%ld/%ld, ",cellcount[i],cellcount2[i]); - } - fprintf(stderr,"\n"); - } - - /* do the automatic cull request */ - while(cellsleft>target){ - int bestcell=-1; - float besterror=0; - float besterror2=0; - long head=-1; - char spinbuf[80]; - sprintf(spinbuf,"cells left to eliminate: %ld : ",cellsleft-target); - - /* find the cell with lowest removal impact */ - for(i=0;ic->lengthlist[i]>0){ - if(bestcell==-1 || cellerrormax[i]<=besterror2){ - if(bestcell==-1 || cellerrormax[i]cellerror[i]){ - besterror=cellerror[i]; - besterror2=cellerrormax[i]; - bestcell=i; - } - } - } - } - - fprintf(stderr,"\reliminating cell %d \n" - " dispersal error of %g max/%g total (%ld hits)\n", - bestcell,besterror2,besterror,cellcount[bestcell]); - - /* disperse it. move each point out, adding it (properly) to - the second best */ - b->c->lengthlist[bestcell]=0; - head=firsthead[bestcell]; - firsthead[bestcell]=-1; - while(head!=-1){ - /* head is a point number */ - float *ppt=pointlist+head*dim; - int firstentry=closest(b,ppt,-1); - int secondentry=closest(b,ppt,firstentry); - float firstmetric=_dist(dim,b->valuelist+dim*firstentry,ppt); - float secondmetric=_dist(dim,b->valuelist+dim*secondentry,ppt); - long next=membership[head]; - - if(headvaluelist+dim*bestcell,ppt); - /* new second closest error */ - float secondmetric=_dist(dim,b->valuelist+dim*secondentry,ppt); - long next=secondary[head]; - - if(headc->lengthlist[i]>0) - entryindex[target++]=i; - } - - /* make working space for a reverse entry index */ - reventry=_ogg_malloc(entries*sizeof(long)); - - /* do the split */ - nt=b->c->nearest_tree= - _ogg_calloc(1,sizeof(encode_aux_nearestmatch)); - - nt->alloc=4096; - nt->ptr0=_ogg_malloc(sizeof(long)*nt->alloc); - nt->ptr1=_ogg_malloc(sizeof(long)*nt->alloc); - nt->p=_ogg_malloc(sizeof(long)*nt->alloc); - nt->q=_ogg_malloc(sizeof(long)*nt->alloc); - nt->aux=0; - - fprintf(stderr,"Leaves added: %d \n", - lp_split(pointlist,points, - b,entryindex,target, - pointindex,indexedpoints, - membership,reventry, - 0,&pointssofar)); - free(membership); - free(reventry); - free(pointindex); - - /* hack alert. I should just change the damned splitter and - codebook writer */ - for(i=0;iaux;i++)nt->p[i]*=dim; - for(i=0;iaux;i++)nt->q[i]*=dim; - - /* recount hits. Build new lengthlist. reuse entryindex storage */ - for(i=0;iaux;i++)nt->p[i]/=dim; - for(i=0;iaux;i++)nt->q[i]/=dim; - - /* the lengthlist builder doesn't actually deal with 0 hit entries. - So, we pack the 'sparse' hit list into a dense list, then unpack - the lengths after the build */ - { - int upper=0; - long *lengthlist=_ogg_calloc(entries,sizeof(long)); - for(i=0;ic->lengthlist[i]>0) - entryindex[upper++]=entryindex[i]; - else{ - if(entryindex[i]>1){ - fprintf(stderr,"\nINTERNAL ERROR; _best matched to unused entry\n"); - exit(1); - } - } - } - - /* sanity check */ - if(upper != target){ - fprintf(stderr,"\nINTERNAL ERROR; packed the wrong number of entries\n"); - exit(1); - } - - build_tree_from_lengths(upper,entryindex,lengthlist); - - upper=0; - for(i=0;ic->lengthlist[i]>0) - b->c->lengthlist[i]=lengthlist[upper++]; - } - - } - } - /* we're done. write it out. */ - write_codebook(out,basename,b->c); - - fprintf(stderr,"\r \nDone.\n"); - return(0); -} - - - - diff --git a/vq/localcodebook.h b/vq/localcodebook.h index 7fc7d92..c95502a 100644 --- a/vq/localcodebook.h +++ b/vq/localcodebook.h @@ -52,50 +52,9 @@ typedef struct static_codebook{ long *quantlist; /* map == 1: (int)(entries^(1/dim)) element column map map == 2: list of dim*entries quantized entry vals */ - - /* encode helpers ********************************************************/ - struct encode_aux_nearestmatch *nearest_tree; - struct encode_aux_threshmatch *thresh_tree; - struct encode_aux_pigeonhole *pigeon_tree; - int allocedp; } static_codebook; -/* this structures an arbitrary trained book to quickly find the - nearest cell match */ -typedef struct encode_aux_nearestmatch{ - /* pre-calculated partitioning tree */ - long *ptr0; - long *ptr1; - - long *p; /* decision points (each is an entry) */ - long *q; /* decision points (each is an entry) */ - long aux; /* number of tree entries */ - long alloc; -} encode_aux_nearestmatch; - -/* assumes a maptype of 1; encode side only, so that's OK */ -typedef struct encode_aux_threshmatch{ - float *quantthresh; - long *quantmap; - int quantvals; - int threshvals; -} encode_aux_threshmatch; - -typedef struct encode_aux_pigeonhole{ - float min; - float del; - - int mapentries; - int quantvals; - long *pigeonmap; - - long fittotal; - long *fitlist; - long *fitmap; - long *fitlength; -} encode_aux_pigeonhole; - typedef struct codebook{ long dim; /* codebook dimensions (elements per vector) */ long entries; /* codebook entries */ @@ -114,6 +73,11 @@ typedef struct codebook{ int dec_firsttablen; int dec_maxlength; + /* The current encoder uses only centered, integer-only lattice books. */ + int quantvals; + int minval; + int delta; + } codebook; extern void vorbis_staticbook_clear(static_codebook *b); diff --git a/vq/make_residue_books.pl b/vq/make_residue_books.pl index b811fe2..b37d0dc 100755 --- a/vq/make_residue_books.pl +++ b/vq/make_residue_books.pl @@ -114,8 +114,8 @@ while($line=){ $plusminus=$val; } } - die "Couldn't open temp file temp$$.vql: $!" unless - open(G,">temp$$.vql"); + die "Couldn't open temp file $globalname$name.vql: $!" unless + open(G,">$globalname$name.vql"); print G "$count $dim 0 "; if($seqp=~/non/){ print G "0\n$list\n"; @@ -124,16 +124,11 @@ while($line=){ } close(G); - my $command="latticebuild temp$$.vql > $globalname$name.vqh"; + my $command="latticebuild $globalname$name.vql > $globalname$name.vqh"; print ">>> $command\n"; die "Couldn't build latticebook.\n\tcommand:$command\n" if syst($command); - my $command="latticehint $globalname$name.vqh $thlist > temp$$.vqh"; - print ">>> $command\n"; - die "Couldn't pre-hint latticebook.\n\tcommand:$command\n" - if syst($command); - if(-e $datafile){ if($interleave=~/non/){ @@ -143,32 +138,27 @@ while($line=){ } if($seqp=~/cull/){ - my $command="$restune temp$$.vqh $datafile 1 > $globalname$name.vqh"; + my $command="$restune $globalname$name.vqh $datafile 1 > temp$$.vqh"; print ">>> $command\n"; die "Couldn't tune latticebook.\n\tcommand:$command\n" if syst($command); }else{ - my $command="$restune temp$$.vqh $datafile > $globalname$name.vqh"; + my $command="$restune $globalname$name.vqh $datafile > temp$$.vqh"; print ">>> $command\n"; die "Couldn't tune latticebook.\n\tcommand:$command\n" if syst($command); } - my $command="latticehint $globalname$name.vqh $thlist > temp$$.vqh"; + my $command="mv temp$$.vqh $globalname$name.vqh"; print ">>> $command\n"; - die "Couldn't post-hint latticebook.\n\tcommand:$command\n" + die "Couldn't rename latticebook.\n\tcommand:$command\n" if syst($command); }else{ print "No matching training file; leaving this codebook untrained.\n"; } - my $command="mv temp$$.vqh $globalname$name.vqh"; - print ">>> $command\n"; - die "Couldn't rename latticebook.\n\tcommand:$command\n" - if syst($command); - - my $command="rm temp$$.vql"; + my $command="rm $globalname$name.vql"; print ">>> $command\n"; die "Couldn't remove temp files.\n\tcommand:$command\n" if syst($command); -- 2.7.4