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