1 | /******************************************************************** |
---|
2 | * * |
---|
3 | * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE. * |
---|
4 | * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS * |
---|
5 | * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE * |
---|
6 | * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. * |
---|
7 | * * |
---|
8 | * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2001 * |
---|
9 | * by the Xiph.Org Foundation http://www.xiph.org/ * |
---|
10 | * * |
---|
11 | ******************************************************************** |
---|
12 | |
---|
13 | function: utility main for building thresh/pigeonhole encode hints |
---|
14 | last mod: $Id: latticehint.c 13293 2007-07-24 00:09:47Z xiphmont $ |
---|
15 | |
---|
16 | ********************************************************************/ |
---|
17 | |
---|
18 | #include <stdlib.h> |
---|
19 | #include <stdio.h> |
---|
20 | #include <math.h> |
---|
21 | #include <string.h> |
---|
22 | #include <errno.h> |
---|
23 | #include "../lib/scales.h" |
---|
24 | #include "bookutil.h" |
---|
25 | #include "vqgen.h" |
---|
26 | #include "vqsplit.h" |
---|
27 | |
---|
28 | /* The purpose of this util is to build encode hints for lattice |
---|
29 | codebooks so that brute forcing each codebook entry isn't needed. |
---|
30 | Threshhold hints are for books in which each scalar in the vector |
---|
31 | is independant (eg, residue) and pigeonhole lookups provide a |
---|
32 | minimum error fit for words where the scalars are interdependant |
---|
33 | (each affecting the fit of the next in sequence) as in an LSP |
---|
34 | sequential book (or can be used along with a sparse threshhold map, |
---|
35 | like a splitting tree that need not be trained) |
---|
36 | |
---|
37 | If the input book is non-sequential, a threshhold hint is built. |
---|
38 | If the input book is sequential, a pigeonholing hist is built. |
---|
39 | If the book is sparse, a pigeonholing hint is built, possibly in addition |
---|
40 | to the threshhold hint |
---|
41 | |
---|
42 | command line: |
---|
43 | latticehint book.vqh [threshlist] |
---|
44 | |
---|
45 | latticehint produces book.vqh on stdout */ |
---|
46 | |
---|
47 | static int longsort(const void *a, const void *b){ |
---|
48 | return(**((long **)a)-**((long **)b)); |
---|
49 | } |
---|
50 | |
---|
51 | static int addtosearch(int entry,long **tempstack,long *tempcount,int add){ |
---|
52 | long *ptr=tempstack[entry]; |
---|
53 | long i=tempcount[entry]; |
---|
54 | |
---|
55 | if(ptr){ |
---|
56 | while(i--) |
---|
57 | if(*ptr++==add)return(0); |
---|
58 | tempstack[entry]=_ogg_realloc(tempstack[entry], |
---|
59 | (tempcount[entry]+1)*sizeof(long)); |
---|
60 | }else{ |
---|
61 | tempstack[entry]=_ogg_malloc(sizeof(long)); |
---|
62 | } |
---|
63 | |
---|
64 | tempstack[entry][tempcount[entry]++]=add; |
---|
65 | return(1); |
---|
66 | } |
---|
67 | |
---|
68 | static void setvals(int dim,encode_aux_pigeonhole *p, |
---|
69 | long *temptrack,float *tempmin,float *tempmax, |
---|
70 | int seqp){ |
---|
71 | int i; |
---|
72 | float last=0.f; |
---|
73 | for(i=0;i<dim;i++){ |
---|
74 | tempmin[i]=(temptrack[i])*p->del+p->min+last; |
---|
75 | tempmax[i]=tempmin[i]+p->del; |
---|
76 | if(seqp)last=tempmin[i]; |
---|
77 | } |
---|
78 | } |
---|
79 | |
---|
80 | /* note that things are currently set up such that input fits that |
---|
81 | quantize outside the pigeonmap are dropped and brute-forced. So we |
---|
82 | can ignore the <0 and >=n boundary cases in min/max error */ |
---|
83 | |
---|
84 | static float minerror(int dim,float *a,encode_aux_pigeonhole *p, |
---|
85 | long *temptrack,float *tempmin,float *tempmax){ |
---|
86 | int i; |
---|
87 | float err=0.f; |
---|
88 | for(i=0;i<dim;i++){ |
---|
89 | float eval=0.f; |
---|
90 | if(a[i]<tempmin[i]){ |
---|
91 | eval=tempmin[i]-a[i]; |
---|
92 | }else if(a[i]>tempmax[i]){ |
---|
93 | eval=a[i]-tempmax[i]; |
---|
94 | } |
---|
95 | err+=eval*eval; |
---|
96 | } |
---|
97 | return(err); |
---|
98 | } |
---|
99 | |
---|
100 | static float maxerror(int dim,float *a,encode_aux_pigeonhole *p, |
---|
101 | long *temptrack,float *tempmin,float *tempmax){ |
---|
102 | int i; |
---|
103 | float err=0.f,eval; |
---|
104 | for(i=0;i<dim;i++){ |
---|
105 | if(a[i]<tempmin[i]){ |
---|
106 | eval=tempmax[i]-a[i]; |
---|
107 | }else if(a[i]>tempmax[i]){ |
---|
108 | eval=a[i]-tempmin[i]; |
---|
109 | }else{ |
---|
110 | float t1=a[i]-tempmin[i]; |
---|
111 | eval=tempmax[i]-a[i]; |
---|
112 | if(t1>eval)eval=t1; |
---|
113 | } |
---|
114 | err+=eval*eval; |
---|
115 | } |
---|
116 | return(err); |
---|
117 | } |
---|
118 | |
---|
119 | int main(int argc,char *argv[]){ |
---|
120 | codebook *b; |
---|
121 | static_codebook *c; |
---|
122 | int entries=-1,dim=-1; |
---|
123 | float min,del; |
---|
124 | char *name; |
---|
125 | long i,j; |
---|
126 | float *suggestions; |
---|
127 | int suggcount=0; |
---|
128 | |
---|
129 | if(argv[1]==NULL){ |
---|
130 | fprintf(stderr,"Need a lattice book on the command line.\n"); |
---|
131 | exit(1); |
---|
132 | } |
---|
133 | |
---|
134 | { |
---|
135 | char *ptr; |
---|
136 | char *filename=strdup(argv[1]); |
---|
137 | |
---|
138 | b=codebook_load(filename); |
---|
139 | c=(static_codebook *)(b->c); |
---|
140 | |
---|
141 | ptr=strrchr(filename,'.'); |
---|
142 | if(ptr){ |
---|
143 | *ptr='\0'; |
---|
144 | name=strdup(filename); |
---|
145 | }else{ |
---|
146 | name=strdup(filename); |
---|
147 | } |
---|
148 | } |
---|
149 | |
---|
150 | if(c->maptype!=1){ |
---|
151 | fprintf(stderr,"Provided book is not a latticebook.\n"); |
---|
152 | exit(1); |
---|
153 | } |
---|
154 | |
---|
155 | entries=b->entries; |
---|
156 | dim=b->dim; |
---|
157 | min=_float32_unpack(c->q_min); |
---|
158 | del=_float32_unpack(c->q_delta); |
---|
159 | |
---|
160 | /* Do we want to gen a threshold hint? */ |
---|
161 | if(c->q_sequencep==0){ |
---|
162 | /* yes. Discard any preexisting threshhold hint */ |
---|
163 | long quantvals=_book_maptype1_quantvals(c); |
---|
164 | long **quantsort=alloca(quantvals*sizeof(long *)); |
---|
165 | encode_aux_threshmatch *t=_ogg_calloc(1,sizeof(encode_aux_threshmatch)); |
---|
166 | c->thresh_tree=t; |
---|
167 | |
---|
168 | fprintf(stderr,"Adding threshold hint to %s...\n",name); |
---|
169 | |
---|
170 | /* partial/complete suggestions */ |
---|
171 | if(argv[2]){ |
---|
172 | char *ptr=strdup(argv[2]); |
---|
173 | suggestions=alloca(sizeof(float)*quantvals); |
---|
174 | |
---|
175 | for(suggcount=0;ptr && suggcount<quantvals;suggcount++){ |
---|
176 | char *ptr2=strchr(ptr,','); |
---|
177 | if(ptr2)*ptr2++='\0'; |
---|
178 | suggestions[suggcount]=atof(ptr); |
---|
179 | ptr=ptr2; |
---|
180 | } |
---|
181 | } |
---|
182 | |
---|
183 | /* simplest possible threshold hint only */ |
---|
184 | t->quantthresh=_ogg_calloc(quantvals-1,sizeof(float)); |
---|
185 | t->quantmap=_ogg_calloc(quantvals,sizeof(int)); |
---|
186 | t->threshvals=quantvals; |
---|
187 | t->quantvals=quantvals; |
---|
188 | |
---|
189 | /* the quantvals may not be in order; sort em first */ |
---|
190 | for(i=0;i<quantvals;i++)quantsort[i]=c->quantlist+i; |
---|
191 | qsort(quantsort,quantvals,sizeof(long *),longsort); |
---|
192 | |
---|
193 | /* ok, gen the map and thresholds */ |
---|
194 | for(i=0;i<quantvals;i++)t->quantmap[i]=quantsort[i]-c->quantlist; |
---|
195 | for(i=0;i<quantvals-1;i++){ |
---|
196 | float v1=*(quantsort[i])*del+min; |
---|
197 | float v2=*(quantsort[i+1])*del+min; |
---|
198 | |
---|
199 | for(j=0;j<suggcount;j++) |
---|
200 | if(v1<suggestions[j] && suggestions[j]<v2){ |
---|
201 | t->quantthresh[i]=suggestions[j]; |
---|
202 | break; |
---|
203 | } |
---|
204 | |
---|
205 | if(j==suggcount){ |
---|
206 | t->quantthresh[i]=(v1+v2)*.5; |
---|
207 | } |
---|
208 | } |
---|
209 | } |
---|
210 | |
---|
211 | /* Do we want to gen a pigeonhole hint? */ |
---|
212 | #if 0 |
---|
213 | for(i=0;i<entries;i++)if(c->lengthlist[i]==0)break; |
---|
214 | if(c->q_sequencep || i<entries){ |
---|
215 | long **tempstack; |
---|
216 | long *tempcount; |
---|
217 | long *temptrack; |
---|
218 | float *tempmin; |
---|
219 | float *tempmax; |
---|
220 | long totalstack=0; |
---|
221 | long pigeons; |
---|
222 | long subpigeons; |
---|
223 | long quantvals=_book_maptype1_quantvals(c); |
---|
224 | int changep=1,factor; |
---|
225 | |
---|
226 | encode_aux_pigeonhole *p=_ogg_calloc(1,sizeof(encode_aux_pigeonhole)); |
---|
227 | c->pigeon_tree=p; |
---|
228 | |
---|
229 | fprintf(stderr,"Adding pigeonhole hint to %s...\n",name); |
---|
230 | |
---|
231 | /* the idea is that we quantize uniformly, even in a nonuniform |
---|
232 | lattice, so that quantization of one scalar has a predictable |
---|
233 | result on the next sequential scalar in a greedy matching |
---|
234 | algorithm. We generate a lookup based on the quantization of |
---|
235 | the vector (pigeonmap groups quantized entries together) and |
---|
236 | list the entries that could possible be the best fit for any |
---|
237 | given member of that pigeonhole. The encode process then has a |
---|
238 | much smaller list to brute force */ |
---|
239 | |
---|
240 | /* find our pigeonhole-specific quantization values, fill in the |
---|
241 | quant value->pigeonhole map */ |
---|
242 | factor=3; |
---|
243 | p->del=del; |
---|
244 | p->min=min; |
---|
245 | p->quantvals=quantvals; |
---|
246 | { |
---|
247 | int max=0; |
---|
248 | for(i=0;i<quantvals;i++)if(max<c->quantlist[i])max=c->quantlist[i]; |
---|
249 | p->mapentries=max; |
---|
250 | } |
---|
251 | p->pigeonmap=_ogg_malloc(p->mapentries*sizeof(long)); |
---|
252 | p->quantvals=(quantvals+factor-1)/factor; |
---|
253 | |
---|
254 | /* pigeonhole roughly on the boundaries of the quantvals; the |
---|
255 | exact pigeonhole grouping is an optimization issue, not a |
---|
256 | correctness issue */ |
---|
257 | for(i=0;i<p->mapentries;i++){ |
---|
258 | float thisval=del*i+min; /* middle of the quant zone */ |
---|
259 | int quant=0; |
---|
260 | float err=fabs(c->quantlist[0]*del+min-thisval); |
---|
261 | for(j=1;j<quantvals;j++){ |
---|
262 | float thiserr=fabs(c->quantlist[j]*del+min-thisval); |
---|
263 | if(thiserr<err){ |
---|
264 | quant=j/factor; |
---|
265 | err=thiserr; |
---|
266 | } |
---|
267 | } |
---|
268 | p->pigeonmap[i]=quant; |
---|
269 | } |
---|
270 | |
---|
271 | /* pigeonmap complete. Now do the grungy business of finding the |
---|
272 | entries that could possibly be the best fit for a value appearing |
---|
273 | in the pigeonhole. The trick that allows the below to work is the |
---|
274 | uniform quantization; even though the scalars may be 'sequential' |
---|
275 | (each a delta from the last), the uniform quantization means that |
---|
276 | the error variance is *not* dependant. Given a pigeonhole and an |
---|
277 | entry, we can find the minimum and maximum possible errors |
---|
278 | (relative to the entry) for any point that could appear in the |
---|
279 | pigeonhole */ |
---|
280 | |
---|
281 | /* must iterate over both pigeonholes and entries */ |
---|
282 | /* temporarily (in order to avoid thinking hard), we grow each |
---|
283 | pigeonhole seperately, the build a stack of 'em later */ |
---|
284 | pigeons=1; |
---|
285 | subpigeons=1; |
---|
286 | for(i=0;i<dim;i++)subpigeons*=p->mapentries; |
---|
287 | for(i=0;i<dim;i++)pigeons*=p->quantvals; |
---|
288 | temptrack=_ogg_calloc(dim,sizeof(long)); |
---|
289 | tempmin=_ogg_calloc(dim,sizeof(float)); |
---|
290 | tempmax=_ogg_calloc(dim,sizeof(float)); |
---|
291 | tempstack=_ogg_calloc(pigeons,sizeof(long *)); |
---|
292 | tempcount=_ogg_calloc(pigeons,sizeof(long)); |
---|
293 | |
---|
294 | while(1){ |
---|
295 | float errorpost=-1; |
---|
296 | char buffer[80]; |
---|
297 | |
---|
298 | /* map our current pigeonhole to a 'big pigeonhole' so we know |
---|
299 | what list we're after */ |
---|
300 | int entry=0; |
---|
301 | for(i=dim-1;i>=0;i--)entry=entry*p->quantvals+p->pigeonmap[temptrack[i]]; |
---|
302 | setvals(dim,p,temptrack,tempmin,tempmax,c->q_sequencep); |
---|
303 | sprintf(buffer,"Building pigeonhole search list [%ld]...",totalstack); |
---|
304 | |
---|
305 | |
---|
306 | /* Search all entries to find the one with the minimum possible |
---|
307 | maximum error. Record that error */ |
---|
308 | for(i=0;i<entries;i++){ |
---|
309 | if(c->lengthlist[i]>0){ |
---|
310 | float this=maxerror(dim,b->valuelist+i*dim,p, |
---|
311 | temptrack,tempmin,tempmax); |
---|
312 | if(errorpost==-1 || this<errorpost)errorpost=this; |
---|
313 | spinnit(buffer,subpigeons); |
---|
314 | } |
---|
315 | } |
---|
316 | |
---|
317 | /* Our search list will contain all entries with a minimum |
---|
318 | possible error <= our errorpost */ |
---|
319 | for(i=0;i<entries;i++) |
---|
320 | if(c->lengthlist[i]>0){ |
---|
321 | spinnit(buffer,subpigeons); |
---|
322 | if(minerror(dim,b->valuelist+i*dim,p, |
---|
323 | temptrack,tempmin,tempmax)<errorpost) |
---|
324 | totalstack+=addtosearch(entry,tempstack,tempcount,i); |
---|
325 | } |
---|
326 | |
---|
327 | for(i=0;i<dim;i++){ |
---|
328 | temptrack[i]++; |
---|
329 | if(temptrack[i]<p->mapentries)break; |
---|
330 | temptrack[i]=0; |
---|
331 | } |
---|
332 | if(i==dim)break; |
---|
333 | subpigeons--; |
---|
334 | } |
---|
335 | |
---|
336 | fprintf(stderr,"\r " |
---|
337 | "\rTotal search list size (all entries): %ld\n",totalstack); |
---|
338 | |
---|
339 | /* pare the index of lists for improbable quantizations (where |
---|
340 | improbable is determined by c->lengthlist; we assume that |
---|
341 | pigeonholing is in sync with the codeword cells, which it is */ |
---|
342 | /*for(i=0;i<entries;i++){ |
---|
343 | float probability= 1.f/(1<<c->lengthlist[i]); |
---|
344 | if(c->lengthlist[i]==0 || probability*entries<cutoff){ |
---|
345 | totalstack-=tempcount[i]; |
---|
346 | tempcount[i]=0; |
---|
347 | } |
---|
348 | }*/ |
---|
349 | |
---|
350 | /* pare the list of shortlists; merge contained and similar lists |
---|
351 | together */ |
---|
352 | p->fitmap=_ogg_malloc(pigeons*sizeof(long)); |
---|
353 | for(i=0;i<pigeons;i++)p->fitmap[i]=-1; |
---|
354 | while(changep){ |
---|
355 | char buffer[80]; |
---|
356 | changep=0; |
---|
357 | |
---|
358 | for(i=0;i<pigeons;i++){ |
---|
359 | if(p->fitmap[i]<0 && tempcount[i]){ |
---|
360 | for(j=i+1;j<pigeons;j++){ |
---|
361 | if(p->fitmap[j]<0 && tempcount[j]){ |
---|
362 | /* is one list a superset, or are they sufficiently similar? */ |
---|
363 | int amiss=0,bmiss=0,ii,jj; |
---|
364 | for(ii=0;ii<tempcount[i];ii++){ |
---|
365 | for(jj=0;jj<tempcount[j];jj++) |
---|
366 | if(tempstack[i][ii]==tempstack[j][jj])break; |
---|
367 | if(jj==tempcount[j])amiss++; |
---|
368 | } |
---|
369 | for(jj=0;jj<tempcount[j];jj++){ |
---|
370 | for(ii=0;ii<tempcount[i];ii++) |
---|
371 | if(tempstack[i][ii]==tempstack[j][jj])break; |
---|
372 | if(ii==tempcount[i])bmiss++; |
---|
373 | } |
---|
374 | if(amiss==0 || |
---|
375 | bmiss==0 || |
---|
376 | (amiss*2<tempcount[i] && bmiss*2<tempcount[j] && |
---|
377 | tempcount[i]+bmiss<entries/30)){ |
---|
378 | |
---|
379 | /*superset/similar Add all of one to the other. */ |
---|
380 | for(jj=0;jj<tempcount[j];jj++) |
---|
381 | totalstack+=addtosearch(i,tempstack,tempcount, |
---|
382 | tempstack[j][jj]); |
---|
383 | totalstack-=tempcount[j]; |
---|
384 | p->fitmap[j]=i; |
---|
385 | changep=1; |
---|
386 | } |
---|
387 | } |
---|
388 | } |
---|
389 | sprintf(buffer,"Consolidating [%ld total, %s]... ",totalstack, |
---|
390 | changep?"reit":"nochange"); |
---|
391 | spinnit(buffer,pigeons-i); |
---|
392 | } |
---|
393 | } |
---|
394 | } |
---|
395 | |
---|
396 | /* repack the temp stack in final form */ |
---|
397 | fprintf(stderr,"\r " |
---|
398 | "\rFinal total list size: %ld\n",totalstack); |
---|
399 | |
---|
400 | |
---|
401 | p->fittotal=totalstack; |
---|
402 | p->fitlist=_ogg_malloc((totalstack+1)*sizeof(long)); |
---|
403 | p->fitlength=_ogg_malloc(pigeons*sizeof(long)); |
---|
404 | { |
---|
405 | long usage=0; |
---|
406 | for(i=0;i<pigeons;i++){ |
---|
407 | if(p->fitmap[i]==-1){ |
---|
408 | if(tempcount[i]) |
---|
409 | memcpy(p->fitlist+usage,tempstack[i],tempcount[i]*sizeof(long)); |
---|
410 | p->fitmap[i]=usage; |
---|
411 | p->fitlength[i]=tempcount[i]; |
---|
412 | usage+=tempcount[i]; |
---|
413 | if(usage>totalstack){ |
---|
414 | fprintf(stderr,"Internal error; usage>totalstack\n"); |
---|
415 | exit(1); |
---|
416 | } |
---|
417 | }else{ |
---|
418 | p->fitlength[i]=p->fitlength[p->fitmap[i]]; |
---|
419 | p->fitmap[i]=p->fitmap[p->fitmap[i]]; |
---|
420 | } |
---|
421 | } |
---|
422 | } |
---|
423 | } |
---|
424 | #endif |
---|
425 | |
---|
426 | write_codebook(stdout,name,c); |
---|
427 | fprintf(stderr,"\r " |
---|
428 | "\nDone.\n"); |
---|
429 | exit(0); |
---|
430 | } |
---|