diff options
Diffstat (limited to 'apps/codecs/libtremor/codebook.c')
-rw-r--r-- | apps/codecs/libtremor/codebook.c | 504 |
1 files changed, 504 insertions, 0 deletions
diff --git a/apps/codecs/libtremor/codebook.c b/apps/codecs/libtremor/codebook.c new file mode 100644 index 0000000000..8c319ab49e --- /dev/null +++ b/apps/codecs/libtremor/codebook.c | |||
@@ -0,0 +1,504 @@ | |||
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 codebook pack/unpack/code/decode operations | ||
15 | |||
16 | ********************************************************************/ | ||
17 | |||
18 | #include "config-tremor.h" | ||
19 | #include <string.h> | ||
20 | #include <math.h> | ||
21 | #include "ogg.h" | ||
22 | #include "ivorbiscodec.h" | ||
23 | #include "codebook.h" | ||
24 | #include "misc.h" | ||
25 | #include "os.h" | ||
26 | |||
27 | /* unpacks a codebook from the packet buffer into the codebook struct, | ||
28 | readies the codebook auxiliary structures for decode *************/ | ||
29 | int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){ | ||
30 | long i,j; | ||
31 | memset(s,0,sizeof(*s)); | ||
32 | |||
33 | /* make sure alignment is correct */ | ||
34 | if(oggpack_read(opb,24)!=0x564342)goto _eofout; | ||
35 | |||
36 | /* first the basic parameters */ | ||
37 | s->dim=oggpack_read(opb,16); | ||
38 | s->entries=oggpack_read(opb,24); | ||
39 | if(s->entries==-1)goto _eofout; | ||
40 | |||
41 | /* codeword ordering.... length ordered or unordered? */ | ||
42 | switch((int)oggpack_read(opb,1)){ | ||
43 | case 0: | ||
44 | /* unordered */ | ||
45 | s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries); | ||
46 | |||
47 | /* allocated but unused entries? */ | ||
48 | if(oggpack_read(opb,1)){ | ||
49 | /* yes, unused entries */ | ||
50 | |||
51 | for(i=0;i<s->entries;i++){ | ||
52 | if(oggpack_read(opb,1)){ | ||
53 | long num=oggpack_read(opb,5); | ||
54 | if(num==-1)goto _eofout; | ||
55 | s->lengthlist[i]=num+1; | ||
56 | }else | ||
57 | s->lengthlist[i]=0; | ||
58 | } | ||
59 | }else{ | ||
60 | /* all entries used; no tagging */ | ||
61 | for(i=0;i<s->entries;i++){ | ||
62 | long num=oggpack_read(opb,5); | ||
63 | if(num==-1)goto _eofout; | ||
64 | s->lengthlist[i]=num+1; | ||
65 | } | ||
66 | } | ||
67 | |||
68 | break; | ||
69 | case 1: | ||
70 | /* ordered */ | ||
71 | { | ||
72 | long length=oggpack_read(opb,5)+1; | ||
73 | s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries); | ||
74 | |||
75 | for(i=0;i<s->entries;){ | ||
76 | long num=oggpack_read(opb,_ilog(s->entries-i)); | ||
77 | if(num==-1)goto _eofout; | ||
78 | for(j=0;j<num && i<s->entries;j++,i++) | ||
79 | s->lengthlist[i]=length; | ||
80 | length++; | ||
81 | } | ||
82 | } | ||
83 | break; | ||
84 | default: | ||
85 | /* EOF */ | ||
86 | return(-1); | ||
87 | } | ||
88 | |||
89 | /* Do we have a mapping to unpack? */ | ||
90 | switch((s->maptype=oggpack_read(opb,4))){ | ||
91 | case 0: | ||
92 | /* no mapping */ | ||
93 | break; | ||
94 | case 1: case 2: | ||
95 | /* implicitly populated value mapping */ | ||
96 | /* explicitly populated value mapping */ | ||
97 | |||
98 | s->q_min=oggpack_read(opb,32); | ||
99 | s->q_delta=oggpack_read(opb,32); | ||
100 | s->q_quant=oggpack_read(opb,4)+1; | ||
101 | s->q_sequencep=oggpack_read(opb,1); | ||
102 | |||
103 | { | ||
104 | int quantvals=0; | ||
105 | switch(s->maptype){ | ||
106 | case 1: | ||
107 | quantvals=_book_maptype1_quantvals(s); | ||
108 | break; | ||
109 | case 2: | ||
110 | quantvals=s->entries*s->dim; | ||
111 | break; | ||
112 | } | ||
113 | |||
114 | /* quantized values */ | ||
115 | s->quantlist=(long *)_ogg_malloc(sizeof(*s->quantlist)*quantvals); | ||
116 | for(i=0;i<quantvals;i++) | ||
117 | s->quantlist[i]=oggpack_read(opb,s->q_quant); | ||
118 | |||
119 | if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout; | ||
120 | } | ||
121 | break; | ||
122 | default: | ||
123 | goto _errout; | ||
124 | } | ||
125 | |||
126 | /* all set */ | ||
127 | return(0); | ||
128 | |||
129 | _errout: | ||
130 | _eofout: | ||
131 | vorbis_staticbook_clear(s); | ||
132 | return(-1); | ||
133 | } | ||
134 | |||
135 | /* the 'eliminate the decode tree' optimization actually requires the | ||
136 | codewords to be MSb first, not LSb. This is an annoying inelegancy | ||
137 | (and one of the first places where carefully thought out design | ||
138 | turned out to be wrong; Vorbis II and future Ogg codecs should go | ||
139 | to an MSb bitpacker), but not actually the huge hit it appears to | ||
140 | be. The first-stage decode table catches most words so that | ||
141 | bitreverse is not in the main execution path. */ | ||
142 | |||
143 | static inline ogg_uint32_t bitreverse(register ogg_uint32_t x){ | ||
144 | x= ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000); | ||
145 | x= ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00); | ||
146 | x= ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0); | ||
147 | x= ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc); | ||
148 | return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa); | ||
149 | } | ||
150 | |||
151 | STIN long decode_packed_entry_number(codebook *book, | ||
152 | oggpack_buffer *b){ | ||
153 | int read=book->dec_maxlength; | ||
154 | long lo,hi; | ||
155 | long lok = oggpack_look(b,book->dec_firsttablen); | ||
156 | |||
157 | if (EXPECT(lok >= 0, 1)) { | ||
158 | long entry = book->dec_firsttable[lok]; | ||
159 | if(EXPECT(entry&0x80000000UL, 0)){ | ||
160 | lo=(entry>>15)&0x7fff; | ||
161 | hi=book->used_entries-(entry&0x7fff); | ||
162 | }else{ | ||
163 | oggpack_adv(b, book->dec_codelengths[entry-1]); | ||
164 | return(entry-1); | ||
165 | } | ||
166 | }else{ | ||
167 | lo=0; | ||
168 | hi=book->used_entries; | ||
169 | } | ||
170 | |||
171 | lok = oggpack_look(b, read); | ||
172 | |||
173 | while(lok<0 && read>1) | ||
174 | lok = oggpack_look(b, --read); | ||
175 | |||
176 | if(lok<0){ | ||
177 | oggpack_adv(b,1); /* force eop */ | ||
178 | return -1; | ||
179 | } | ||
180 | |||
181 | /* bisect search for the codeword in the ordered list */ | ||
182 | { | ||
183 | ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok); | ||
184 | |||
185 | while(hi-lo>1){ | ||
186 | long p=(hi-lo)>>1; | ||
187 | long test=book->codelist[lo+p]>testword; | ||
188 | lo+=p&(test-1); | ||
189 | hi-=p&(-test); | ||
190 | } | ||
191 | |||
192 | if(book->dec_codelengths[lo]<=read){ | ||
193 | oggpack_adv(b, book->dec_codelengths[lo]); | ||
194 | return(lo); | ||
195 | } | ||
196 | } | ||
197 | |||
198 | oggpack_adv(b, read+1); | ||
199 | return(-1); | ||
200 | } | ||
201 | |||
202 | static long decode_packed_block(codebook *book, oggpack_buffer *b, | ||
203 | long *buf, int n){ | ||
204 | long *bufptr = buf; | ||
205 | long *bufend = buf + n; | ||
206 | |||
207 | while (bufptr<bufend) { | ||
208 | if (b->headend > 8) { | ||
209 | ogg_uint32_t *ptr; | ||
210 | unsigned long bit, bitend; | ||
211 | unsigned long adr; | ||
212 | ogg_uint32_t cache = 0; | ||
213 | int cachesize = 0; | ||
214 | |||
215 | adr = (unsigned long)b->headptr; | ||
216 | bit = (adr&3)*8+b->headbit; | ||
217 | ptr = (ogg_uint32_t *)(adr&~3); | ||
218 | bitend = ((adr&3)+b->headend)*8; | ||
219 | while (bufptr<bufend){ | ||
220 | long entry, lo, hi; | ||
221 | if (EXPECT(cachesize<book->dec_maxlength, 0)) { | ||
222 | if (bit-cachesize+32>=bitend) | ||
223 | break; | ||
224 | bit-=cachesize; | ||
225 | cache=letoh32(ptr[bit>>5]) >> (bit&31); | ||
226 | if (bit&31) | ||
227 | cache|=letoh32(ptr[(bit>>5)+1]) << (32-(bit&31)); | ||
228 | cachesize=32; | ||
229 | bit+=32; | ||
230 | } | ||
231 | |||
232 | entry=book->dec_firsttable[cache&((1<<book->dec_firsttablen)-1)]; | ||
233 | if(EXPECT(entry&0x80000000UL, 0)){ | ||
234 | lo=(entry>>15)&0x7fff; | ||
235 | hi=book->used_entries-(entry&0x7fff); | ||
236 | { | ||
237 | ogg_uint32_t testword=bitreverse((ogg_uint32_t)cache); | ||
238 | |||
239 | while(EXPECT(hi-lo>1, 1)){ | ||
240 | long p=(hi-lo)>>1; | ||
241 | if (book->codelist[lo+p]>testword) | ||
242 | hi-=p; | ||
243 | else | ||
244 | lo+=p; | ||
245 | } | ||
246 | entry=lo; | ||
247 | } | ||
248 | }else | ||
249 | entry--; | ||
250 | |||
251 | *bufptr++=entry; | ||
252 | { | ||
253 | int l=book->dec_codelengths[entry]; | ||
254 | cachesize-=l; | ||
255 | cache>>=l; | ||
256 | } | ||
257 | } | ||
258 | |||
259 | adr=(unsigned long)b->headptr; | ||
260 | bit-=(adr&3)*8+cachesize; | ||
261 | b->headend-=(bit/8); | ||
262 | b->headptr+=bit/8; | ||
263 | b->headbit=bit%8; | ||
264 | } else { | ||
265 | long r = decode_packed_entry_number(book, b); | ||
266 | if (r == -1) return bufptr-buf; | ||
267 | *bufptr++ = r; | ||
268 | } | ||
269 | } | ||
270 | return n; | ||
271 | } | ||
272 | |||
273 | |||
274 | /* Decode side is specced and easier, because we don't need to find | ||
275 | matches using different criteria; we simply read and map. There are | ||
276 | two things we need to do 'depending': | ||
277 | |||
278 | We may need to support interleave. We don't really, but it's | ||
279 | convenient to do it here rather than rebuild the vector later. | ||
280 | |||
281 | Cascades may be additive or multiplicitive; this is not inherent in | ||
282 | the codebook, but set in the code using the codebook. Like | ||
283 | interleaving, it's easiest to do it here. | ||
284 | addmul==0 -> declarative (set the value) | ||
285 | addmul==1 -> additive | ||
286 | addmul==2 -> multiplicitive */ | ||
287 | |||
288 | /* returns the [original, not compacted] entry number or -1 on eof *********/ | ||
289 | long vorbis_book_decode(codebook *book, oggpack_buffer *b){ | ||
290 | if(book->used_entries>0){ | ||
291 | long packed_entry=decode_packed_entry_number(book,b); | ||
292 | if(packed_entry>=0) | ||
293 | return(book->dec_index[packed_entry]); | ||
294 | } | ||
295 | |||
296 | /* if there's no dec_index, the codebook unpacking isn't collapsed */ | ||
297 | return(-1); | ||
298 | } | ||
299 | |||
300 | /* returns 0 on OK or -1 on eof *************************************/ | ||
301 | long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a, | ||
302 | oggpack_buffer *b,int n,int point){ | ||
303 | if(book->used_entries>0){ | ||
304 | int step=n/book->dim; | ||
305 | long *entry = (long *)alloca(sizeof(*entry)*step); | ||
306 | ogg_int32_t **t = (ogg_int32_t **)alloca(sizeof(*t)*step); | ||
307 | int i,j,o; | ||
308 | int shift=point-book->binarypoint; | ||
309 | |||
310 | if(shift>=0){ | ||
311 | for (i = 0; i < step; i++) { | ||
312 | entry[i]=decode_packed_entry_number(book,b); | ||
313 | if(entry[i]==-1)return(-1); | ||
314 | t[i] = book->valuelist+entry[i]*book->dim; | ||
315 | } | ||
316 | for(i=0,o=0;i<book->dim;i++,o+=step) | ||
317 | for (j=0;j<step;j++) | ||
318 | a[o+j]+=t[j][i]>>shift; | ||
319 | }else{ | ||
320 | for (i = 0; i < step; i++) { | ||
321 | entry[i]=decode_packed_entry_number(book,b); | ||
322 | if(entry[i]==-1)return(-1); | ||
323 | t[i] = book->valuelist+entry[i]*book->dim; | ||
324 | } | ||
325 | for(i=0,o=0;i<book->dim;i++,o+=step) | ||
326 | for (j=0;j<step;j++) | ||
327 | a[o+j]+=t[j][i]<<-shift; | ||
328 | } | ||
329 | } | ||
330 | return(0); | ||
331 | } | ||
332 | |||
333 | long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a, | ||
334 | oggpack_buffer *b,int n,int point){ | ||
335 | if(book->used_entries>0){ | ||
336 | int i,j,entry; | ||
337 | ogg_int32_t *t; | ||
338 | int shift=point-book->binarypoint; | ||
339 | |||
340 | if(shift>=0){ | ||
341 | for(i=0;i<n;){ | ||
342 | entry = decode_packed_entry_number(book,b); | ||
343 | if(entry==-1)return(-1); | ||
344 | t = book->valuelist+entry*book->dim; | ||
345 | for (j=0;j<book->dim;) | ||
346 | a[i++]+=t[j++]>>shift; | ||
347 | } | ||
348 | }else{ | ||
349 | shift = -shift; | ||
350 | for(i=0;i<n;){ | ||
351 | entry = decode_packed_entry_number(book,b); | ||
352 | if(entry==-1)return(-1); | ||
353 | t = book->valuelist+entry*book->dim; | ||
354 | for (j=0;j<book->dim;) | ||
355 | a[i++]+=t[j++]<<shift; | ||
356 | } | ||
357 | } | ||
358 | } | ||
359 | return(0); | ||
360 | } | ||
361 | |||
362 | long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a, | ||
363 | oggpack_buffer *b,int n,int point){ | ||
364 | if(book->used_entries>0){ | ||
365 | int i,j,entry; | ||
366 | ogg_int32_t *t; | ||
367 | int shift=point-book->binarypoint; | ||
368 | |||
369 | if(shift>=0){ | ||
370 | |||
371 | for(i=0;i<n;){ | ||
372 | entry = decode_packed_entry_number(book,b); | ||
373 | if(entry==-1)return(-1); | ||
374 | t = book->valuelist+entry*book->dim; | ||
375 | for (j=0;j<book->dim;){ | ||
376 | a[i++]=t[j++]>>shift; | ||
377 | } | ||
378 | } | ||
379 | }else{ | ||
380 | shift = -shift; | ||
381 | for(i=0;i<n;){ | ||
382 | entry = decode_packed_entry_number(book,b); | ||
383 | if(entry==-1)return(-1); | ||
384 | t = book->valuelist+entry*book->dim; | ||
385 | for (j=0;j<book->dim;){ | ||
386 | a[i++]=t[j++]<<shift; | ||
387 | } | ||
388 | } | ||
389 | } | ||
390 | }else{ | ||
391 | |||
392 | int i,j; | ||
393 | for(i=0;i<n;){ | ||
394 | for (j=0;j<book->dim;){ | ||
395 | a[i++]=0; | ||
396 | } | ||
397 | } | ||
398 | } | ||
399 | return(0); | ||
400 | } | ||
401 | |||
402 | static long vorbis_book_decodevv_add_2ch_even(codebook *book,ogg_int32_t **a, | ||
403 | long offset,oggpack_buffer *b, | ||
404 | int n,int point){ | ||
405 | long i,k,chunk,read; | ||
406 | int shift=point-book->binarypoint; | ||
407 | long entries[32]; | ||
408 | ogg_int32_t *p0 = &(a[0][offset]); | ||
409 | ogg_int32_t *p1 = &(a[1][offset]); | ||
410 | |||
411 | if(shift>=0){ | ||
412 | |||
413 | for(i=0;i<n;){ | ||
414 | chunk=32; | ||
415 | if (chunk*book->dim>(n-i)*2) | ||
416 | chunk=((n-i)*2+book->dim-1)/book->dim; | ||
417 | read = decode_packed_block(book,b,entries,chunk); | ||
418 | for(k=0;k<read;k++){ | ||
419 | const ogg_int32_t *t = book->valuelist+entries[k]*book->dim; | ||
420 | const ogg_int32_t *u = t+book->dim; | ||
421 | do{ | ||
422 | *p0++ += *t++>>shift; | ||
423 | *p1++ += *t++>>shift; | ||
424 | }while(t<u); | ||
425 | } | ||
426 | if (read<chunk)return-1; | ||
427 | i += read*book->dim/2; | ||
428 | } | ||
429 | }else{ | ||
430 | shift = -shift; | ||
431 | for(i=0;i<n;){ | ||
432 | chunk=32; | ||
433 | if (chunk*book->dim>(n-i)*2) | ||
434 | chunk=((n-i)*2+book->dim-1)/book->dim; | ||
435 | read = decode_packed_block(book,b,entries,chunk); | ||
436 | for(k=0;k<read;k++){ | ||
437 | const ogg_int32_t *t = book->valuelist+entries[k]*book->dim; | ||
438 | const ogg_int32_t *u = t+book->dim; | ||
439 | do{ | ||
440 | *p0++ += *t++<<shift; | ||
441 | *p1++ += *t++<<shift; | ||
442 | }while(t<u); | ||
443 | } | ||
444 | if (read<chunk)return-1; | ||
445 | i += read*book->dim/2; | ||
446 | } | ||
447 | } | ||
448 | return(0); | ||
449 | } | ||
450 | |||
451 | long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a, | ||
452 | long offset,int ch, | ||
453 | oggpack_buffer *b,int n,int point){ | ||
454 | if(book->used_entries>0){ | ||
455 | long i,j,k,chunk,read; | ||
456 | int chptr=0; | ||
457 | int shift=point-book->binarypoint; | ||
458 | long entries[32]; | ||
459 | |||
460 | if (!(book->dim&1) && ch==2) | ||
461 | return vorbis_book_decodevv_add_2ch_even(book,a,offset,b,n,point); | ||
462 | |||
463 | if(shift>=0){ | ||
464 | |||
465 | for(i=offset;i<offset+n;){ | ||
466 | chunk=32; | ||
467 | if (chunk*book->dim>(offset+n-i)*ch) | ||
468 | chunk=((offset+n-i)*ch+book->dim-1)/book->dim; | ||
469 | read = decode_packed_block(book,b,entries,chunk); | ||
470 | for(k=0;k<read;k++){ | ||
471 | const ogg_int32_t *t = book->valuelist+entries[k]*book->dim; | ||
472 | for (j=0;j<book->dim;j++){ | ||
473 | a[chptr++][i]+=t[j]>>shift; | ||
474 | if(chptr==ch){ | ||
475 | chptr=0; | ||
476 | i++; | ||
477 | } | ||
478 | } | ||
479 | } | ||
480 | if (read<chunk)return-1; | ||
481 | } | ||
482 | }else{ | ||
483 | shift = -shift; | ||
484 | for(i=offset;i<offset+n;){ | ||
485 | chunk=32; | ||
486 | if (chunk*book->dim>(offset+n-i)*ch) | ||
487 | chunk=((offset+n-i)*ch+book->dim-1)/book->dim; | ||
488 | read = decode_packed_block(book,b,entries,chunk); | ||
489 | for(k=0;k<read;k++){ | ||
490 | const ogg_int32_t *t = book->valuelist+entries[k]*book->dim; | ||
491 | for (j=0;j<book->dim;j++){ | ||
492 | a[chptr++][i]+=t[j]<<shift; | ||
493 | if(chptr==ch){ | ||
494 | chptr=0; | ||
495 | i++; | ||
496 | } | ||
497 | } | ||
498 | } | ||
499 | if (read<chunk)return-1; | ||
500 | } | ||
501 | } | ||
502 | } | ||
503 | return(0); | ||
504 | } | ||