author | llornkcor <llornkcor> | 2003-04-08 02:56:00 (UTC) |
---|---|---|
committer | llornkcor <llornkcor> | 2003-04-08 02:56:00 (UTC) |
commit | 4e998346fbe802e534db9f04f63fd04e96ba9501 (patch) (unidiff) | |
tree | c969faf216b7f75613c4cabece3b1d3441fc39a7 /core/multimedia/opieplayer/vorbis/tremor/sharedbook.c | |
parent | eee5531d24fdb17011debaa7acd42683330e55b6 (diff) | |
download | opie-4e998346fbe802e534db9f04f63fd04e96ba9501.zip opie-4e998346fbe802e534db9f04f63fd04e96ba9501.tar.gz opie-4e998346fbe802e534db9f04f63fd04e96ba9501.tar.bz2 |
vorbis lib and plugin for opieplayer1
Diffstat (limited to 'core/multimedia/opieplayer/vorbis/tremor/sharedbook.c') (more/less context) (show whitespace changes)
-rw-r--r-- | core/multimedia/opieplayer/vorbis/tremor/sharedbook.c | 443 |
1 files changed, 443 insertions, 0 deletions
diff --git a/core/multimedia/opieplayer/vorbis/tremor/sharedbook.c b/core/multimedia/opieplayer/vorbis/tremor/sharedbook.c new file mode 100644 index 0000000..a62211e --- a/dev/null +++ b/core/multimedia/opieplayer/vorbis/tremor/sharedbook.c | |||
@@ -0,0 +1,443 @@ | |||
1 | /******************************************************************** | ||
2 | * * | ||
3 | * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE. * | ||
4 | * * | ||
5 | * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS * | ||
6 | * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE * | ||
7 | * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. * | ||
8 | * * | ||
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 + | ||
38 | biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm | ||
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]; | ||
81 | |||
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 */ | ||
86 | |||
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; | ||
94 | |||
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--){ | ||
99 | |||
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 | } | ||
112 | |||
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 | } | ||
125 | |||
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; | ||
214 | int point; | ||
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); | ||
220 | |||
221 | if(b->q_sequencep){ | ||
222 | last=val; | ||
223 | lastpoint=point; | ||
224 | } | ||
225 | |||
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++){ | ||
248 | int point; | ||
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); | ||
254 | |||
255 | if(b->q_sequencep){ | ||
256 | last=val; | ||
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]; | ||
278 | |||
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){ | ||
319 | return (**(ogg_uint32_t **)a>**(ogg_uint32_t **)b)- | ||
320 | (**(ogg_uint32_t **)a<**(ogg_uint32_t **)b); | ||
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)); | ||
328 | |||
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 | |||
341 | /* two different remappings go on here. | ||
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); | ||
355 | |||
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 | |||
378 | |||
379 | c->valuelist=_book_unquantize(s,n,sortindex,&c->binarypoint); | ||
380 | c->dec_index=(int *)_ogg_malloc(n*sizeof(*c->dec_index)); | ||
381 | |||
382 | for(n=0,i=0;i<s->entries;i++) | ||
383 | if(s->lengthlist[i]>0) | ||
384 | c->dec_index[sortindex[n++]]=i; | ||
385 | |||
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++; | ||
420 | |||
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 | } | ||
436 | |||
437 | |||
438 | return(0); | ||
439 | err_out: | ||
440 | vorbis_book_clear(c); | ||
441 | return(-1); | ||
442 | } | ||
443 | |||