diff options
Diffstat (limited to 'apps/codecs/Tremor/codebook.c')
-rw-r--r-- | apps/codecs/Tremor/codebook.c | 350 |
1 files changed, 350 insertions, 0 deletions
diff --git a/apps/codecs/Tremor/codebook.c b/apps/codecs/Tremor/codebook.c new file mode 100644 index 0000000000..5da8957232 --- /dev/null +++ b/apps/codecs/Tremor/codebook.c | |||
@@ -0,0 +1,350 @@ | |||
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 <stdlib.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 ogg_uint32_t bitreverse(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 | static inline 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 (lok >= 0) { | ||
158 | long entry = book->dec_firsttable[lok]; | ||
159 | if(entry&0x80000000UL){ | ||
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 | if(lok<0)return -1; | ||
176 | |||
177 | /* bisect search for the codeword in the ordered list */ | ||
178 | { | ||
179 | ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok); | ||
180 | |||
181 | while(hi-lo>1){ | ||
182 | long p=(hi-lo)>>1; | ||
183 | long test=book->codelist[lo+p]>testword; | ||
184 | lo+=p&(test-1); | ||
185 | hi-=p&(-test); | ||
186 | } | ||
187 | |||
188 | if(book->dec_codelengths[lo]<=read){ | ||
189 | oggpack_adv(b, book->dec_codelengths[lo]); | ||
190 | return(lo); | ||
191 | } | ||
192 | } | ||
193 | |||
194 | oggpack_adv(b, read); | ||
195 | return(-1); | ||
196 | } | ||
197 | |||
198 | /* Decode side is specced and easier, because we don't need to find | ||
199 | matches using different criteria; we simply read and map. There are | ||
200 | two things we need to do 'depending': | ||
201 | |||
202 | We may need to support interleave. We don't really, but it's | ||
203 | convenient to do it here rather than rebuild the vector later. | ||
204 | |||
205 | Cascades may be additive or multiplicitive; this is not inherent in | ||
206 | the codebook, but set in the code using the codebook. Like | ||
207 | interleaving, it's easiest to do it here. | ||
208 | addmul==0 -> declarative (set the value) | ||
209 | addmul==1 -> additive | ||
210 | addmul==2 -> multiplicitive */ | ||
211 | |||
212 | /* returns the [original, not compacted] entry number or -1 on eof *********/ | ||
213 | long vorbis_book_decode(codebook *book, oggpack_buffer *b){ | ||
214 | long packed_entry=decode_packed_entry_number(book,b); | ||
215 | if(packed_entry>=0) | ||
216 | return(book->dec_index[packed_entry]); | ||
217 | |||
218 | /* if there's no dec_index, the codebook unpacking isn't collapsed */ | ||
219 | return(packed_entry); | ||
220 | } | ||
221 | |||
222 | /* returns 0 on OK or -1 on eof *************************************/ | ||
223 | long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a, | ||
224 | oggpack_buffer *b,int n,int point){ | ||
225 | int step=n/book->dim; | ||
226 | long *entry = (long *)alloca(sizeof(*entry)*step); | ||
227 | ogg_int32_t **t = (ogg_int32_t **)alloca(sizeof(*t)*step); | ||
228 | int i,j,o; | ||
229 | int shift=point-book->binarypoint; | ||
230 | |||
231 | if(shift>=0){ | ||
232 | for (i = 0; i < step; i++) { | ||
233 | entry[i]=decode_packed_entry_number(book,b); | ||
234 | if(entry[i]==-1)return(-1); | ||
235 | t[i] = book->valuelist+entry[i]*book->dim; | ||
236 | } | ||
237 | for(i=0,o=0;i<book->dim;i++,o+=step) | ||
238 | for (j=0;j<step;j++) | ||
239 | a[o+j]+=t[j][i]>>shift; | ||
240 | }else{ | ||
241 | for (i = 0; i < step; i++) { | ||
242 | entry[i]=decode_packed_entry_number(book,b); | ||
243 | if(entry[i]==-1)return(-1); | ||
244 | t[i] = book->valuelist+entry[i]*book->dim; | ||
245 | } | ||
246 | for(i=0,o=0;i<book->dim;i++,o+=step) | ||
247 | for (j=0;j<step;j++) | ||
248 | a[o+j]+=t[j][i]<<-shift; | ||
249 | } | ||
250 | return(0); | ||
251 | } | ||
252 | |||
253 | long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a, | ||
254 | oggpack_buffer *b,int n,int point){ | ||
255 | int i,j,entry; | ||
256 | ogg_int32_t *t; | ||
257 | int shift=point-book->binarypoint; | ||
258 | |||
259 | if(shift>=0){ | ||
260 | for(i=0;i<n;){ | ||
261 | entry = decode_packed_entry_number(book,b); | ||
262 | if(entry==-1)return(-1); | ||
263 | t = book->valuelist+entry*book->dim; | ||
264 | for (j=0;j<book->dim;) | ||
265 | a[i++]+=t[j++]>>shift; | ||
266 | } | ||
267 | }else{ | ||
268 | for(i=0;i<n;){ | ||
269 | entry = decode_packed_entry_number(book,b); | ||
270 | if(entry==-1)return(-1); | ||
271 | t = book->valuelist+entry*book->dim; | ||
272 | for (j=0;j<book->dim;) | ||
273 | a[i++]+=t[j++]<<-shift; | ||
274 | } | ||
275 | } | ||
276 | return(0); | ||
277 | } | ||
278 | |||
279 | long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a, | ||
280 | oggpack_buffer *b,int n,int point){ | ||
281 | int i,j,entry; | ||
282 | ogg_int32_t *t; | ||
283 | int shift=point-book->binarypoint; | ||
284 | |||
285 | if(shift>=0){ | ||
286 | |||
287 | for(i=0;i<n;){ | ||
288 | entry = decode_packed_entry_number(book,b); | ||
289 | if(entry==-1)return(-1); | ||
290 | t = book->valuelist+entry*book->dim; | ||
291 | for (j=0;j<book->dim;){ | ||
292 | a[i++]=t[j++]>>shift; | ||
293 | } | ||
294 | } | ||
295 | }else{ | ||
296 | |||
297 | for(i=0;i<n;){ | ||
298 | entry = decode_packed_entry_number(book,b); | ||
299 | if(entry==-1)return(-1); | ||
300 | t = book->valuelist+entry*book->dim; | ||
301 | for (j=0;j<book->dim;){ | ||
302 | a[i++]=t[j++]<<-shift; | ||
303 | } | ||
304 | } | ||
305 | } | ||
306 | return(0); | ||
307 | } | ||
308 | |||
309 | long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,\ | ||
310 | long offset,int ch, | ||
311 | oggpack_buffer *b,int n,int point){ | ||
312 | long i,j,entry; | ||
313 | int chptr=0; | ||
314 | int shift=point-book->binarypoint; | ||
315 | |||
316 | if(shift>=0){ | ||
317 | |||
318 | for(i=offset;i<offset+n;){ | ||
319 | entry = decode_packed_entry_number(book,b); | ||
320 | if(entry==-1)return(-1); | ||
321 | { | ||
322 | const ogg_int32_t *t = book->valuelist+entry*book->dim; | ||
323 | for (j=0;j<book->dim;j++){ | ||
324 | a[chptr++][i]+=t[j]>>shift; | ||
325 | if(chptr==ch){ | ||
326 | chptr=0; | ||
327 | i++; | ||
328 | } | ||
329 | } | ||
330 | } | ||
331 | } | ||
332 | }else{ | ||
333 | |||
334 | for(i=offset;i<offset+n;){ | ||
335 | entry = decode_packed_entry_number(book,b); | ||
336 | if(entry==-1)return(-1); | ||
337 | { | ||
338 | const ogg_int32_t *t = book->valuelist+entry*book->dim; | ||
339 | for (j=0;j<book->dim;j++){ | ||
340 | a[chptr++][i]+=t[j]<<-shift; | ||
341 | if(chptr==ch){ | ||
342 | chptr=0; | ||
343 | i++; | ||
344 | } | ||
345 | } | ||
346 | } | ||
347 | } | ||
348 | } | ||
349 | return(0); | ||
350 | } | ||