diff options
Diffstat (limited to 'lib/rbcodec/codecs/libtremor/sharedbook.c')
-rw-r--r-- | lib/rbcodec/codecs/libtremor/sharedbook.c | 460 |
1 files changed, 460 insertions, 0 deletions
diff --git a/lib/rbcodec/codecs/libtremor/sharedbook.c b/lib/rbcodec/codecs/libtremor/sharedbook.c new file mode 100644 index 0000000000..8b046217c7 --- /dev/null +++ b/lib/rbcodec/codecs/libtremor/sharedbook.c | |||
@@ -0,0 +1,460 @@ | |||
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 "config-tremor.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 | static 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 | /* sanity check the huffman tree; an underpopulated tree must be | ||
127 | rejected. The only exception is the one-node pseudo-nil tree, | ||
128 | which appears to be underpopulated because the tree doesn't | ||
129 | really exist; there's only one possible 'codeword' or zero bits, | ||
130 | but the above tree-gen code doesn't mark that. */ | ||
131 | if(sparsecount != 1){ | ||
132 | for(i=1;i<33;i++) | ||
133 | if(marker[i] & (0xffffffffUL>>(32-i))){ | ||
134 | _ogg_free(r); | ||
135 | return(NULL); | ||
136 | } | ||
137 | } | ||
138 | |||
139 | /* bitreverse the words because our bitwise packer/unpacker is LSb | ||
140 | endian */ | ||
141 | for(i=0,count=0;i<n;i++){ | ||
142 | ogg_uint32_t temp=0; | ||
143 | for(j=0;j<l[i];j++){ | ||
144 | temp<<=1; | ||
145 | temp|=(r[count]>>j)&1; | ||
146 | } | ||
147 | |||
148 | if(sparsecount){ | ||
149 | if(l[i]) | ||
150 | r[count++]=temp; | ||
151 | }else | ||
152 | r[count++]=temp; | ||
153 | } | ||
154 | |||
155 | return(r); | ||
156 | } | ||
157 | |||
158 | /* there might be a straightforward one-line way to do the below | ||
159 | that's portable and totally safe against roundoff, but I haven't | ||
160 | thought of it. Therefore, we opt on the side of caution */ | ||
161 | long _book_maptype1_quantvals(const static_codebook *b){ | ||
162 | /* get us a starting hint, we'll polish it below */ | ||
163 | int bits=_ilog(b->entries); | ||
164 | int vals=b->entries>>((bits-1)*(b->dim-1)/b->dim); | ||
165 | |||
166 | while(1){ | ||
167 | long acc=1; | ||
168 | long acc1=1; | ||
169 | int i; | ||
170 | for(i=0;i<b->dim;i++){ | ||
171 | acc*=vals; | ||
172 | acc1*=vals+1; | ||
173 | } | ||
174 | if(acc<=b->entries && acc1>b->entries){ | ||
175 | return(vals); | ||
176 | }else{ | ||
177 | if(acc>b->entries){ | ||
178 | vals--; | ||
179 | }else{ | ||
180 | vals++; | ||
181 | } | ||
182 | } | ||
183 | } | ||
184 | } | ||
185 | |||
186 | /* different than what _book_unquantize does for mainline: | ||
187 | we repack the book in a fixed point format that shares the same | ||
188 | binary point. Upon first use, we can shift point if needed */ | ||
189 | |||
190 | /* we need to deal with two map types: in map type 1, the values are | ||
191 | generated algorithmically (each column of the vector counts through | ||
192 | the values in the quant vector). in map type 2, all the values came | ||
193 | in in an explicit list. Both value lists must be unpacked */ | ||
194 | |||
195 | static ogg_int32_t *_book_unquantize(const static_codebook *b,int n, | ||
196 | int *sparsemap,int *maxpoint){ | ||
197 | long j,k,count=0; | ||
198 | if(b->maptype==1 || b->maptype==2){ | ||
199 | int quantvals; | ||
200 | int minpoint,delpoint; | ||
201 | ogg_int32_t mindel=_float32_unpack(b->q_min,&minpoint); | ||
202 | ogg_int32_t delta=_float32_unpack(b->q_delta,&delpoint); | ||
203 | ogg_int32_t *r=(ogg_int32_t *)_ogg_calloc(n*b->dim,sizeof(*r)); | ||
204 | int *rp=(int *)_ogg_calloc(n*b->dim,sizeof(*rp)); | ||
205 | |||
206 | *maxpoint=minpoint; | ||
207 | |||
208 | /* maptype 1 and 2 both use a quantized value vector, but | ||
209 | different sizes */ | ||
210 | switch(b->maptype){ | ||
211 | case 1: | ||
212 | /* most of the time, entries%dimensions == 0, but we need to be | ||
213 | well defined. We define that the possible vales at each | ||
214 | scalar is values == entries/dim. If entries%dim != 0, we'll | ||
215 | have 'too few' values (values*dim<entries), which means that | ||
216 | we'll have 'left over' entries; left over entries use zeroed | ||
217 | values (and are wasted). So don't generate codebooks like | ||
218 | that */ | ||
219 | quantvals=_book_maptype1_quantvals(b); | ||
220 | for(j=0;j<b->entries;j++){ | ||
221 | if((sparsemap && b->lengthlist[j]) || !sparsemap){ | ||
222 | ogg_int32_t last=0; | ||
223 | int lastpoint=0; | ||
224 | int indexdiv=1; | ||
225 | for(k=0;k<b->dim;k++){ | ||
226 | int index= (j/indexdiv)%quantvals; | ||
227 | ogg_int32_t point=0; | ||
228 | int val=VFLOAT_MULTI(delta,delpoint, | ||
229 | abs(b->quantlist[index]),&point); | ||
230 | |||
231 | val=VFLOAT_ADD(mindel,minpoint,val,point,&point); | ||
232 | val=VFLOAT_ADD(last,lastpoint,val,point,&point); | ||
233 | |||
234 | if(b->q_sequencep){ | ||
235 | last=val; | ||
236 | lastpoint=point; | ||
237 | } | ||
238 | |||
239 | if(sparsemap){ | ||
240 | r[sparsemap[count]*b->dim+k]=val; | ||
241 | rp[sparsemap[count]*b->dim+k]=point; | ||
242 | }else{ | ||
243 | r[count*b->dim+k]=val; | ||
244 | rp[count*b->dim+k]=point; | ||
245 | } | ||
246 | if(*maxpoint<point)*maxpoint=point; | ||
247 | indexdiv*=quantvals; | ||
248 | } | ||
249 | count++; | ||
250 | } | ||
251 | |||
252 | } | ||
253 | break; | ||
254 | case 2: | ||
255 | for(j=0;j<b->entries;j++){ | ||
256 | if((sparsemap && b->lengthlist[j]) || !sparsemap){ | ||
257 | ogg_int32_t last=0; | ||
258 | int lastpoint=0; | ||
259 | |||
260 | for(k=0;k<b->dim;k++){ | ||
261 | ogg_int32_t point=0; | ||
262 | int val=VFLOAT_MULTI(delta,delpoint, | ||
263 | abs(b->quantlist[j*b->dim+k]),&point); | ||
264 | |||
265 | val=VFLOAT_ADD(mindel,minpoint,val,point,&point); | ||
266 | val=VFLOAT_ADD(last,lastpoint,val,point,&point); | ||
267 | |||
268 | if(b->q_sequencep){ | ||
269 | last=val; | ||
270 | lastpoint=point; | ||
271 | } | ||
272 | |||
273 | if(sparsemap){ | ||
274 | r[sparsemap[count]*b->dim+k]=val; | ||
275 | rp[sparsemap[count]*b->dim+k]=point; | ||
276 | }else{ | ||
277 | r[count*b->dim+k]=val; | ||
278 | rp[count*b->dim+k]=point; | ||
279 | } | ||
280 | if(*maxpoint<point)*maxpoint=point; | ||
281 | } | ||
282 | count++; | ||
283 | } | ||
284 | } | ||
285 | break; | ||
286 | } | ||
287 | |||
288 | for(j=0;j<n*b->dim;j++) | ||
289 | if(rp[j]<*maxpoint) | ||
290 | r[j]>>=*maxpoint-rp[j]; | ||
291 | |||
292 | _ogg_free(rp); | ||
293 | return(r); | ||
294 | } | ||
295 | return(NULL); | ||
296 | } | ||
297 | |||
298 | void vorbis_staticbook_destroy(static_codebook *b){ | ||
299 | if(b->quantlist)_ogg_free(b->quantlist); | ||
300 | if(b->lengthlist)_ogg_free(b->lengthlist); | ||
301 | memset(b,0,sizeof(*b)); | ||
302 | _ogg_free(b); | ||
303 | } | ||
304 | |||
305 | void vorbis_book_clear(codebook *b){ | ||
306 | /* static book is not cleared; we're likely called on the lookup and | ||
307 | the static codebook belongs to the info struct */ | ||
308 | if(b->valuelist)_ogg_free(b->valuelist); | ||
309 | if(b->codelist)_ogg_free(b->codelist); | ||
310 | |||
311 | if(b->dec_index)_ogg_free(b->dec_index); | ||
312 | if(b->dec_codelengths)_ogg_free(b->dec_codelengths); | ||
313 | if(b->dec_firsttable)_ogg_free(b->dec_firsttable); | ||
314 | |||
315 | memset(b,0,sizeof(*b)); | ||
316 | } | ||
317 | |||
318 | static ogg_uint32_t bitreverse(ogg_uint32_t x){ | ||
319 | x= ((x>>16)&0x0000ffffUL) | ((x<<16)&0xffff0000UL); | ||
320 | x= ((x>> 8)&0x00ff00ffUL) | ((x<< 8)&0xff00ff00UL); | ||
321 | x= ((x>> 4)&0x0f0f0f0fUL) | ((x<< 4)&0xf0f0f0f0UL); | ||
322 | x= ((x>> 2)&0x33333333UL) | ((x<< 2)&0xccccccccUL); | ||
323 | return((x>> 1)&0x55555555UL) | ((x<< 1)&0xaaaaaaaaUL); | ||
324 | } | ||
325 | |||
326 | static int sort32a(const void *a,const void *b){ | ||
327 | return (**(ogg_uint32_t **)a>**(ogg_uint32_t **)b)- | ||
328 | (**(ogg_uint32_t **)a<**(ogg_uint32_t **)b); | ||
329 | } | ||
330 | |||
331 | /* decode codebook arrangement is more heavily optimized than encode */ | ||
332 | int vorbis_book_init_decode(codebook *c,const static_codebook *s){ | ||
333 | int i,j,n=0,tabn; | ||
334 | int *sortindex; | ||
335 | memset(c,0,sizeof(*c)); | ||
336 | |||
337 | /* count actually used entries */ | ||
338 | for(i=0;i<s->entries;i++) | ||
339 | if(s->lengthlist[i]>0) | ||
340 | n++; | ||
341 | |||
342 | c->entries=s->entries; | ||
343 | c->used_entries=n; | ||
344 | c->dim=s->dim; | ||
345 | |||
346 | if(n>0){ | ||
347 | /* two different remappings go on here. | ||
348 | |||
349 | First, we collapse the likely sparse codebook down only to | ||
350 | actually represented values/words. This collapsing needs to be | ||
351 | indexed as map-valueless books are used to encode original entry | ||
352 | positions as integers. | ||
353 | |||
354 | Second, we reorder all vectors, including the entry index above, | ||
355 | by sorted bitreversed codeword to allow treeless decode. */ | ||
356 | |||
357 | /* perform sort */ | ||
358 | ogg_uint32_t *codes=_make_words(s->lengthlist,s->entries,c->used_entries); | ||
359 | ogg_uint32_t **codep=(ogg_uint32_t **)_ogg_malloc(sizeof(*codep)*n); | ||
360 | |||
361 | if(codes==NULL||codep==NULL){ | ||
362 | _ogg_free(codep); | ||
363 | _ogg_free(codes); | ||
364 | goto err_out; | ||
365 | } | ||
366 | |||
367 | for(i=0;i<n;i++){ | ||
368 | codes[i]=bitreverse(codes[i]); | ||
369 | codep[i]=codes+i; | ||
370 | } | ||
371 | |||
372 | qsort(codep,n,sizeof(*codep),sort32a); | ||
373 | |||
374 | sortindex=(int *)_ogg_malloc(n*sizeof(*sortindex)); | ||
375 | c->codelist=(ogg_uint32_t *)_ogg_malloc(n*sizeof(*c->codelist)); | ||
376 | /* the index is a reverse index */ | ||
377 | for(i=0;i<n;i++){ | ||
378 | int position=codep[i]-codes; | ||
379 | sortindex[position]=i; | ||
380 | } | ||
381 | |||
382 | for(i=0;i<n;i++) | ||
383 | c->codelist[sortindex[i]]=codes[i]; | ||
384 | _ogg_free(codep); | ||
385 | _ogg_free(codes); | ||
386 | |||
387 | |||
388 | |||
389 | c->valuelist=_book_unquantize(s,n,sortindex,&c->binarypoint); | ||
390 | c->dec_index=(int *)_ogg_malloc(n*sizeof(*c->dec_index)); | ||
391 | |||
392 | for(n=0,i=0;i<s->entries;i++) | ||
393 | if(s->lengthlist[i]>0) | ||
394 | c->dec_index[sortindex[n++]]=i; | ||
395 | |||
396 | c->dec_codelengths=(char *)_ogg_malloc(n*sizeof(*c->dec_codelengths)); | ||
397 | for(n=0,i=0;i<s->entries;i++) | ||
398 | if(s->lengthlist[i]>0) | ||
399 | c->dec_codelengths[sortindex[n++]]=s->lengthlist[i]; | ||
400 | |||
401 | _ogg_free(sortindex); | ||
402 | /* Use a larger cache size when we have a large codec buffer, helps decoding | ||
403 | speed especially on targets with slow memory and high bitrate files */ | ||
404 | #if CODEC_SIZE < 0x100000 | ||
405 | c->dec_firsttablen=_ilog(c->used_entries)-4; /* this is magic */ | ||
406 | #else | ||
407 | c->dec_firsttablen=_ilog(c->used_entries)+1; /* this is magic */ | ||
408 | #endif | ||
409 | if(c->dec_firsttablen<5)c->dec_firsttablen=5; | ||
410 | if(c->dec_firsttablen>8)c->dec_firsttablen=8; | ||
411 | |||
412 | tabn=1<<c->dec_firsttablen; | ||
413 | c->dec_firsttable=(ogg_uint32_t *)_ogg_calloc(tabn,sizeof(*c->dec_firsttable)); | ||
414 | c->dec_maxlength=0; | ||
415 | |||
416 | for(i=0;i<n;i++){ | ||
417 | if(c->dec_maxlength<c->dec_codelengths[i]) | ||
418 | c->dec_maxlength=c->dec_codelengths[i]; | ||
419 | if(c->dec_codelengths[i]<=c->dec_firsttablen){ | ||
420 | ogg_uint32_t orig=bitreverse(c->codelist[i]); | ||
421 | for(j=0;j<(1<<(c->dec_firsttablen-c->dec_codelengths[i]));j++) | ||
422 | c->dec_firsttable[orig|(j<<c->dec_codelengths[i])]=i+1; | ||
423 | } | ||
424 | } | ||
425 | |||
426 | /* now fill in 'unused' entries in the firsttable with hi/lo search | ||
427 | hints for the non-direct-hits */ | ||
428 | { | ||
429 | ogg_uint32_t mask=0xfffffffeUL<<(31-c->dec_firsttablen); | ||
430 | long lo=0,hi=0; | ||
431 | |||
432 | for(i=0;i<tabn;i++){ | ||
433 | ogg_uint32_t word=i<<(32-c->dec_firsttablen); | ||
434 | if(c->dec_firsttable[bitreverse(word)]==0){ | ||
435 | while((lo+1)<n && c->codelist[lo+1]<=word)lo++; | ||
436 | while( hi<n && word>=(c->codelist[hi]&mask))hi++; | ||
437 | |||
438 | /* we only actually have 15 bits per hint to play with here. | ||
439 | In order to overflow gracefully (nothing breaks, efficiency | ||
440 | just drops), encode as the difference from the extremes. */ | ||
441 | { | ||
442 | unsigned long loval=lo; | ||
443 | unsigned long hival=n-hi; | ||
444 | |||
445 | if(loval>0x7fff)loval=0x7fff; | ||
446 | if(hival>0x7fff)hival=0x7fff; | ||
447 | c->dec_firsttable[bitreverse(word)]= | ||
448 | 0x80000000UL | (loval<<15) | hival; | ||
449 | } | ||
450 | } | ||
451 | } | ||
452 | } | ||
453 | } | ||
454 | |||
455 | return(0); | ||
456 | err_out: | ||
457 | vorbis_book_clear(c); | ||
458 | return(-1); | ||
459 | } | ||
460 | |||