Mercurial > mplayer.hg
annotate tremor/sharedbook.c @ 17050:cd540846d052
Add support to get the list of files from a file containing one filename
per line. Patch from devik (devik .at. cdi .dot. cz).
author | albeu |
---|---|
date | Sat, 26 Nov 2005 17:10:17 +0000 |
parents | c820ccd4f5eb |
children | cd6b211be811 |
rev | line source |
---|---|
14280 | 1 /******************************************************************** |
2 * * | |
3 * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE. * | |
4 * * | |
5 * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2002 * | |
6 * BY THE Xiph.Org FOUNDATION http://www.xiph.org/ * | |
7 * ALL REDISTRIBUTION RIGHTS RESERVED. * | |
8 * * | |
9 ******************************************************************** | |
10 | |
11 function: basic shared codebook operations | |
12 | |
13 ********************************************************************/ | |
14 | |
15 #include <stdlib.h> | |
16 #include <math.h> | |
17 #include <string.h> | |
18 #include "ogg.h" | |
19 #include "os.h" | |
20 #include "misc.h" | |
21 #include "ivorbiscodec.h" | |
22 #include "codebook.h" | |
23 | |
24 /**** pack/unpack helpers ******************************************/ | |
25 int _ilog(unsigned int v){ | |
26 int ret=0; | |
27 while(v){ | |
28 ret++; | |
29 v>>=1; | |
30 } | |
31 return(ret); | |
32 } | |
33 | |
34 /* 32 bit float (not IEEE; nonnormalized mantissa + | |
35 biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm | |
36 Why not IEEE? It's just not that important here. */ | |
37 | |
38 #define VQ_FEXP 10 | |
39 #define VQ_FMAN 21 | |
40 #define VQ_FEXP_BIAS 768 /* bias toward values smaller than 1. */ | |
41 | |
42 static ogg_int32_t _float32_unpack(long val,int *point){ | |
43 long mant=val&0x1fffff; | |
44 int sign=val&0x80000000; | |
45 long exp =(val&0x7fe00000L)>>VQ_FMAN; | |
46 | |
47 exp-=(VQ_FMAN-1)+VQ_FEXP_BIAS; | |
48 | |
49 if(mant){ | |
50 while(!(mant&0x40000000)){ | |
51 mant<<=1; | |
52 exp-=1; | |
53 } | |
54 | |
55 if(sign)mant= -mant; | |
56 }else{ | |
57 sign=0; | |
58 exp=-9999; | |
59 } | |
60 | |
61 *point=exp; | |
62 return mant; | |
63 } | |
64 | |
65 /* given a list of word lengths, generate a list of codewords. Works | |
66 for length ordered or unordered, always assigns the lowest valued | |
67 codewords first. Extended to handle unused entries (length 0) */ | |
68 ogg_uint32_t *_make_words(long *l,long n,long sparsecount){ | |
69 long i,j,count=0; | |
70 ogg_uint32_t marker[33]; | |
71 ogg_uint32_t *r=(ogg_uint32_t *)_ogg_malloc((sparsecount?sparsecount:n)*sizeof(*r)); | |
72 memset(marker,0,sizeof(marker)); | |
73 | |
74 for(i=0;i<n;i++){ | |
75 long length=l[i]; | |
76 if(length>0){ | |
77 ogg_uint32_t entry=marker[length]; | |
78 | |
79 /* when we claim a node for an entry, we also claim the nodes | |
80 below it (pruning off the imagined tree that may have dangled | |
81 from it) as well as blocking the use of any nodes directly | |
82 above for leaves */ | |
83 | |
84 /* update ourself */ | |
85 if(length<32 && (entry>>length)){ | |
86 /* error condition; the lengths must specify an overpopulated tree */ | |
87 _ogg_free(r); | |
88 return(NULL); | |
89 } | |
90 r[count++]=entry; | |
91 | |
92 /* Look to see if the next shorter marker points to the node | |
93 above. if so, update it and repeat. */ | |
94 { | |
95 for(j=length;j>0;j--){ | |
96 | |
97 if(marker[j]&1){ | |
98 /* have to jump branches */ | |
99 if(j==1) | |
100 marker[1]++; | |
101 else | |
102 marker[j]=marker[j-1]<<1; | |
103 break; /* invariant says next upper marker would already | |
104 have been moved if it was on the same path */ | |
105 } | |
106 marker[j]++; | |
107 } | |
108 } | |
109 | |
110 /* prune the tree; the implicit invariant says all the longer | |
111 markers were dangling from our just-taken node. Dangle them | |
112 from our *new* node. */ | |
113 for(j=length+1;j<33;j++) | |
114 if((marker[j]>>1) == entry){ | |
115 entry=marker[j]; | |
116 marker[j]=marker[j-1]<<1; | |
117 }else | |
118 break; | |
119 }else | |
120 if(sparsecount==0)count++; | |
121 } | |
122 | |
123 /* bitreverse the words because our bitwise packer/unpacker is LSb | |
124 endian */ | |
125 for(i=0,count=0;i<n;i++){ | |
126 ogg_uint32_t temp=0; | |
127 for(j=0;j<l[i];j++){ | |
128 temp<<=1; | |
129 temp|=(r[count]>>j)&1; | |
130 } | |
131 | |
132 if(sparsecount){ | |
133 if(l[i]) | |
134 r[count++]=temp; | |
135 }else | |
136 r[count++]=temp; | |
137 } | |
138 | |
139 return(r); | |
140 } | |
141 | |
142 /* there might be a straightforward one-line way to do the below | |
143 that's portable and totally safe against roundoff, but I haven't | |
144 thought of it. Therefore, we opt on the side of caution */ | |
145 long _book_maptype1_quantvals(const static_codebook *b){ | |
146 /* get us a starting hint, we'll polish it below */ | |
147 int bits=_ilog(b->entries); | |
148 int vals=b->entries>>((bits-1)*(b->dim-1)/b->dim); | |
149 | |
150 while(1){ | |
151 long acc=1; | |
152 long acc1=1; | |
153 int i; | |
154 for(i=0;i<b->dim;i++){ | |
155 acc*=vals; | |
156 acc1*=vals+1; | |
157 } | |
158 if(acc<=b->entries && acc1>b->entries){ | |
159 return(vals); | |
160 }else{ | |
161 if(acc>b->entries){ | |
162 vals--; | |
163 }else{ | |
164 vals++; | |
165 } | |
166 } | |
167 } | |
168 } | |
169 | |
170 /* different than what _book_unquantize does for mainline: | |
171 we repack the book in a fixed point format that shares the same | |
172 binary point. Upon first use, we can shift point if needed */ | |
173 | |
174 /* we need to deal with two map types: in map type 1, the values are | |
175 generated algorithmically (each column of the vector counts through | |
176 the values in the quant vector). in map type 2, all the values came | |
177 in in an explicit list. Both value lists must be unpacked */ | |
178 | |
179 ogg_int32_t *_book_unquantize(const static_codebook *b,int n,int *sparsemap, | |
180 int *maxpoint){ | |
181 long j,k,count=0; | |
182 if(b->maptype==1 || b->maptype==2){ | |
183 int quantvals; | |
184 int minpoint,delpoint; | |
185 ogg_int32_t mindel=_float32_unpack(b->q_min,&minpoint); | |
186 ogg_int32_t delta=_float32_unpack(b->q_delta,&delpoint); | |
187 ogg_int32_t *r=(ogg_int32_t *)_ogg_calloc(n*b->dim,sizeof(*r)); | |
188 int *rp=(int *)_ogg_calloc(n*b->dim,sizeof(*rp)); | |
189 | |
190 *maxpoint=minpoint; | |
191 | |
192 /* maptype 1 and 2 both use a quantized value vector, but | |
193 different sizes */ | |
194 switch(b->maptype){ | |
195 case 1: | |
196 /* most of the time, entries%dimensions == 0, but we need to be | |
197 well defined. We define that the possible vales at each | |
198 scalar is values == entries/dim. If entries%dim != 0, we'll | |
199 have 'too few' values (values*dim<entries), which means that | |
200 we'll have 'left over' entries; left over entries use zeroed | |
201 values (and are wasted). So don't generate codebooks like | |
202 that */ | |
203 quantvals=_book_maptype1_quantvals(b); | |
204 for(j=0;j<b->entries;j++){ | |
205 if((sparsemap && b->lengthlist[j]) || !sparsemap){ | |
206 ogg_int32_t last=0; | |
207 int lastpoint=0; | |
208 int indexdiv=1; | |
209 for(k=0;k<b->dim;k++){ | |
210 int index= (j/indexdiv)%quantvals; | |
16266
c820ccd4f5eb
fix warnings and decoding on CYGWIN (produced only noise before this change)
faust3
parents:
14280
diff
changeset
|
211 ogg_int32_t point; |
14280 | 212 int val=VFLOAT_MULTI(delta,delpoint, |
213 abs(b->quantlist[index]),&point); | |
214 | |
215 val=VFLOAT_ADD(mindel,minpoint,val,point,&point); | |
216 val=VFLOAT_ADD(last,lastpoint,val,point,&point); | |
217 | |
218 if(b->q_sequencep){ | |
219 last=val; | |
220 lastpoint=point; | |
221 } | |
222 | |
223 if(sparsemap){ | |
224 r[sparsemap[count]*b->dim+k]=val; | |
225 rp[sparsemap[count]*b->dim+k]=point; | |
226 }else{ | |
227 r[count*b->dim+k]=val; | |
228 rp[count*b->dim+k]=point; | |
229 } | |
230 if(*maxpoint<point)*maxpoint=point; | |
231 indexdiv*=quantvals; | |
232 } | |
233 count++; | |
234 } | |
235 | |
236 } | |
237 break; | |
238 case 2: | |
239 for(j=0;j<b->entries;j++){ | |
240 if((sparsemap && b->lengthlist[j]) || !sparsemap){ | |
241 ogg_int32_t last=0; | |
242 int lastpoint=0; | |
243 | |
244 for(k=0;k<b->dim;k++){ | |
16266
c820ccd4f5eb
fix warnings and decoding on CYGWIN (produced only noise before this change)
faust3
parents:
14280
diff
changeset
|
245 ogg_int32_t point; |
14280 | 246 int val=VFLOAT_MULTI(delta,delpoint, |
247 abs(b->quantlist[j*b->dim+k]),&point); | |
248 | |
249 val=VFLOAT_ADD(mindel,minpoint,val,point,&point); | |
250 val=VFLOAT_ADD(last,lastpoint,val,point,&point); | |
251 | |
252 if(b->q_sequencep){ | |
253 last=val; | |
254 lastpoint=point; | |
255 } | |
256 | |
257 if(sparsemap){ | |
258 r[sparsemap[count]*b->dim+k]=val; | |
259 rp[sparsemap[count]*b->dim+k]=point; | |
260 }else{ | |
261 r[count*b->dim+k]=val; | |
262 rp[count*b->dim+k]=point; | |
263 } | |
264 if(*maxpoint<point)*maxpoint=point; | |
265 } | |
266 count++; | |
267 } | |
268 } | |
269 break; | |
270 } | |
271 | |
272 for(j=0;j<n*b->dim;j++) | |
273 if(rp[j]<*maxpoint) | |
274 r[j]>>=*maxpoint-rp[j]; | |
275 | |
276 _ogg_free(rp); | |
277 return(r); | |
278 } | |
279 return(NULL); | |
280 } | |
281 | |
282 void vorbis_staticbook_clear(static_codebook *b){ | |
283 if(b->quantlist)_ogg_free(b->quantlist); | |
284 if(b->lengthlist)_ogg_free(b->lengthlist); | |
285 memset(b,0,sizeof(*b)); | |
286 | |
287 } | |
288 | |
289 void vorbis_staticbook_destroy(static_codebook *b){ | |
290 vorbis_staticbook_clear(b); | |
291 _ogg_free(b); | |
292 } | |
293 | |
294 void vorbis_book_clear(codebook *b){ | |
295 /* static book is not cleared; we're likely called on the lookup and | |
296 the static codebook belongs to the info struct */ | |
297 if(b->valuelist)_ogg_free(b->valuelist); | |
298 if(b->codelist)_ogg_free(b->codelist); | |
299 | |
300 if(b->dec_index)_ogg_free(b->dec_index); | |
301 if(b->dec_codelengths)_ogg_free(b->dec_codelengths); | |
302 if(b->dec_firsttable)_ogg_free(b->dec_firsttable); | |
303 | |
304 memset(b,0,sizeof(*b)); | |
305 } | |
306 | |
307 static ogg_uint32_t bitreverse(ogg_uint32_t x){ | |
308 x= ((x>>16)&0x0000ffffUL) | ((x<<16)&0xffff0000UL); | |
309 x= ((x>> 8)&0x00ff00ffUL) | ((x<< 8)&0xff00ff00UL); | |
310 x= ((x>> 4)&0x0f0f0f0fUL) | ((x<< 4)&0xf0f0f0f0UL); | |
311 x= ((x>> 2)&0x33333333UL) | ((x<< 2)&0xccccccccUL); | |
312 return((x>> 1)&0x55555555UL) | ((x<< 1)&0xaaaaaaaaUL); | |
313 } | |
314 | |
315 static int sort32a(const void *a,const void *b){ | |
316 return ( (**(ogg_uint32_t **)a>**(ogg_uint32_t **)b)<<1)-1; | |
317 } | |
318 | |
319 /* decode codebook arrangement is more heavily optimized than encode */ | |
320 int vorbis_book_init_decode(codebook *c,const static_codebook *s){ | |
321 int i,j,n=0,tabn; | |
322 int *sortindex; | |
323 memset(c,0,sizeof(*c)); | |
324 | |
325 /* count actually used entries */ | |
326 for(i=0;i<s->entries;i++) | |
327 if(s->lengthlist[i]>0) | |
328 n++; | |
329 | |
330 c->entries=s->entries; | |
331 c->used_entries=n; | |
332 c->dim=s->dim; | |
333 | |
334 c->q_min=s->q_min; | |
335 c->q_delta=s->q_delta; | |
336 | |
337 /* two different remappings go on here. | |
338 | |
339 First, we collapse the likely sparse codebook down only to | |
340 actually represented values/words. This collapsing needs to be | |
341 indexed as map-valueless books are used to encode original entry | |
342 positions as integers. | |
343 | |
344 Second, we reorder all vectors, including the entry index above, | |
345 by sorted bitreversed codeword to allow treeless decode. */ | |
346 | |
347 { | |
348 /* perform sort */ | |
349 ogg_uint32_t *codes=_make_words(s->lengthlist,s->entries,c->used_entries); | |
350 ogg_uint32_t **codep=(ogg_uint32_t **)alloca(sizeof(*codep)*n); | |
351 | |
352 if(codes==NULL)goto err_out; | |
353 | |
354 for(i=0;i<n;i++){ | |
355 codes[i]=bitreverse(codes[i]); | |
356 codep[i]=codes+i; | |
357 } | |
358 | |
359 qsort(codep,n,sizeof(*codep),sort32a); | |
360 | |
361 sortindex=(int *)alloca(n*sizeof(*sortindex)); | |
362 c->codelist=(ogg_uint32_t *)_ogg_malloc(n*sizeof(*c->codelist)); | |
363 /* the index is a reverse index */ | |
364 for(i=0;i<n;i++){ | |
365 int position=codep[i]-codes; | |
366 sortindex[position]=i; | |
367 } | |
368 | |
369 for(i=0;i<n;i++) | |
370 c->codelist[sortindex[i]]=codes[i]; | |
371 _ogg_free(codes); | |
372 } | |
373 | |
374 | |
375 c->valuelist=_book_unquantize(s,n,sortindex,&c->binarypoint); | |
376 c->dec_index=(int *)_ogg_malloc(n*sizeof(*c->dec_index)); | |
377 | |
378 for(n=0,i=0;i<s->entries;i++) | |
379 if(s->lengthlist[i]>0) | |
380 c->dec_index[sortindex[n++]]=i; | |
381 | |
382 c->dec_codelengths=(char *)_ogg_malloc(n*sizeof(*c->dec_codelengths)); | |
383 for(n=0,i=0;i<s->entries;i++) | |
384 if(s->lengthlist[i]>0) | |
385 c->dec_codelengths[sortindex[n++]]=s->lengthlist[i]; | |
386 | |
387 c->dec_firsttablen=_ilog(c->used_entries)-4; /* this is magic */ | |
388 if(c->dec_firsttablen<5)c->dec_firsttablen=5; | |
389 if(c->dec_firsttablen>8)c->dec_firsttablen=8; | |
390 | |
391 tabn=1<<c->dec_firsttablen; | |
392 c->dec_firsttable=(ogg_uint32_t *)_ogg_calloc(tabn,sizeof(*c->dec_firsttable)); | |
393 c->dec_maxlength=0; | |
394 | |
395 for(i=0;i<n;i++){ | |
396 if(c->dec_maxlength<c->dec_codelengths[i]) | |
397 c->dec_maxlength=c->dec_codelengths[i]; | |
398 if(c->dec_codelengths[i]<=c->dec_firsttablen){ | |
399 ogg_uint32_t orig=bitreverse(c->codelist[i]); | |
400 for(j=0;j<(1<<(c->dec_firsttablen-c->dec_codelengths[i]));j++) | |
401 c->dec_firsttable[orig|(j<<c->dec_codelengths[i])]=i+1; | |
402 } | |
403 } | |
404 | |
405 /* now fill in 'unused' entries in the firsttable with hi/lo search | |
406 hints for the non-direct-hits */ | |
407 { | |
408 ogg_uint32_t mask=0xfffffffeUL<<(31-c->dec_firsttablen); | |
409 long lo=0,hi=0; | |
410 | |
411 for(i=0;i<tabn;i++){ | |
412 ogg_uint32_t word=i<<(32-c->dec_firsttablen); | |
413 if(c->dec_firsttable[bitreverse(word)]==0){ | |
414 while((lo+1)<n && c->codelist[lo+1]<=word)lo++; | |
415 while( hi<n && word>=(c->codelist[hi]&mask))hi++; | |
416 | |
417 /* we only actually have 15 bits per hint to play with here. | |
418 In order to overflow gracefully (nothing breaks, efficiency | |
419 just drops), encode as the difference from the extremes. */ | |
420 { | |
421 unsigned long loval=lo; | |
422 unsigned long hival=n-hi; | |
423 | |
424 if(loval>0x7fff)loval=0x7fff; | |
425 if(hival>0x7fff)hival=0x7fff; | |
426 c->dec_firsttable[bitreverse(word)]= | |
427 0x80000000UL | (loval<<15) | hival; | |
428 } | |
429 } | |
430 } | |
431 } | |
432 | |
433 | |
434 return(0); | |
435 err_out: | |
436 vorbis_book_clear(c); | |
437 return(-1); | |
438 } | |
439 |