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 |
|
26 /* unpacks a codebook from the packet buffer into the codebook struct, |
|
27 readies the codebook auxiliary structures for decode *************/ |
|
28 int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){ |
|
29 long i,j; |
|
30 memset(s,0,sizeof(*s)); |
|
31 |
|
32 /* make sure alignment is correct */ |
|
33 if(oggpack_read(opb,24)!=0x564342)goto _eofout; |
|
34 |
|
35 /* first the basic parameters */ |
|
36 s->dim=oggpack_read(opb,16); |
|
37 s->entries=oggpack_read(opb,24); |
|
38 if(s->entries==-1)goto _eofout; |
|
39 |
|
40 /* codeword ordering.... length ordered or unordered? */ |
|
41 switch((int)oggpack_read(opb,1)){ |
|
42 case 0: |
|
43 /* unordered */ |
|
44 s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries); |
|
45 |
|
46 /* allocated but unused entries? */ |
|
47 if(oggpack_read(opb,1)){ |
|
48 /* yes, unused entries */ |
|
49 |
|
50 for(i=0;i<s->entries;i++){ |
|
51 if(oggpack_read(opb,1)){ |
|
52 long num=oggpack_read(opb,5); |
|
53 if(num==-1)goto _eofout; |
|
54 s->lengthlist[i]=num+1; |
|
55 }else |
|
56 s->lengthlist[i]=0; |
|
57 } |
|
58 }else{ |
|
59 /* all entries used; no tagging */ |
|
60 for(i=0;i<s->entries;i++){ |
|
61 long num=oggpack_read(opb,5); |
|
62 if(num==-1)goto _eofout; |
|
63 s->lengthlist[i]=num+1; |
|
64 } |
|
65 } |
|
66 |
|
67 break; |
|
68 case 1: |
|
69 /* ordered */ |
|
70 { |
|
71 long length=oggpack_read(opb,5)+1; |
|
72 s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries); |
|
73 |
|
74 for(i=0;i<s->entries;){ |
|
75 long num=oggpack_read(opb,_ilog(s->entries-i)); |
|
76 if(num==-1)goto _eofout; |
|
77 for(j=0;j<num && i<s->entries;j++,i++) |
|
78 s->lengthlist[i]=length; |
|
79 length++; |
|
80 } |
|
81 } |
|
82 break; |
|
83 default: |
|
84 /* EOF */ |
|
85 return(-1); |
|
86 } |
|
87 |
|
88 /* Do we have a mapping to unpack? */ |
|
89 switch((s->maptype=oggpack_read(opb,4))){ |
|
90 case 0: |
|
91 /* no mapping */ |
|
92 break; |
|
93 case 1: case 2: |
|
94 /* implicitly populated value mapping */ |
|
95 /* explicitly populated value mapping */ |
|
96 |
|
97 s->q_min=oggpack_read(opb,32); |
|
98 s->q_delta=oggpack_read(opb,32); |
|
99 s->q_quant=oggpack_read(opb,4)+1; |
|
100 s->q_sequencep=oggpack_read(opb,1); |
|
101 |
|
102 { |
|
103 int quantvals=0; |
|
104 switch(s->maptype){ |
|
105 case 1: |
|
106 quantvals=_book_maptype1_quantvals(s); |
|
107 break; |
|
108 case 2: |
|
109 quantvals=s->entries*s->dim; |
|
110 break; |
|
111 } |
|
112 |
|
113 /* quantized values */ |
|
114 s->quantlist=(long *)_ogg_malloc(sizeof(*s->quantlist)*quantvals); |
|
115 for(i=0;i<quantvals;i++) |
|
116 s->quantlist[i]=oggpack_read(opb,s->q_quant); |
|
117 |
|
118 if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout; |
|
119 } |
|
120 break; |
|
121 default: |
|
122 goto _errout; |
|
123 } |
|
124 |
|
125 /* all set */ |
|
126 return(0); |
|
127 |
|
128 _errout: |
|
129 _eofout: |
|
130 vorbis_staticbook_clear(s); |
|
131 return(-1); |
|
132 } |
|
133 |
|
134 /* the 'eliminate the decode tree' optimization actually requires the |
|
135 codewords to be MSb first, not LSb. This is an annoying inelegancy |
|
136 (and one of the first places where carefully thought out design |
|
137 turned out to be wrong; Vorbis II and future Ogg codecs should go |
|
138 to an MSb bitpacker), but not actually the huge hit it appears to |
|
139 be. The first-stage decode table catches most words so that |
|
140 bitreverse is not in the main execution path. */ |
|
141 |
|
142 static ogg_uint32_t bitreverse(ogg_uint32_t x){ |
|
143 x= ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000); |
|
144 x= ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00); |
|
145 x= ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0); |
|
146 x= ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc); |
|
147 return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa); |
|
148 } |
|
149 |
|
150 STIN long decode_packed_entry_number(codebook *book, |
|
151 oggpack_buffer *b){ |
|
152 int read=book->dec_maxlength; |
|
153 long lo,hi; |
|
154 long lok = oggpack_look(b,book->dec_firsttablen); |
|
155 |
|
156 if (lok >= 0) { |
|
157 long entry = book->dec_firsttable[lok]; |
|
158 if(entry&0x80000000UL){ |
|
159 lo=(entry>>15)&0x7fff; |
|
160 hi=book->used_entries-(entry&0x7fff); |
|
161 }else{ |
|
162 oggpack_adv(b, book->dec_codelengths[entry-1]); |
|
163 return(entry-1); |
|
164 } |
|
165 }else{ |
|
166 lo=0; |
|
167 hi=book->used_entries; |
|
168 } |
|
169 |
|
170 lok = oggpack_look(b, read); |
|
171 |
|
172 while(lok<0 && read>1) |
|
173 lok = oggpack_look(b, --read); |
|
174 |
|
175 if(lok<0){ |
|
176 oggpack_adv(b,1); /* force eop */ |
|
177 return -1; |
|
178 } |
|
179 |
|
180 /* bisect search for the codeword in the ordered list */ |
|
181 { |
|
182 ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok); |
|
183 |
|
184 while(hi-lo>1){ |
|
185 long p=(hi-lo)>>1; |
|
186 long test=book->codelist[lo+p]>testword; |
|
187 lo+=p&(test-1); |
|
188 hi-=p&(-test); |
|
189 } |
|
190 |
|
191 if(book->dec_codelengths[lo]<=read){ |
|
192 oggpack_adv(b, book->dec_codelengths[lo]); |
|
193 return(lo); |
|
194 } |
|
195 } |
|
196 |
|
197 oggpack_adv(b, read+1); |
|
198 return(-1); |
|
199 } |
|
200 |
|
201 /* Decode side is specced and easier, because we don't need to find |
|
202 matches using different criteria; we simply read and map. There are |
|
203 two things we need to do 'depending': |
|
204 |
|
205 We may need to support interleave. We don't really, but it's |
|
206 convenient to do it here rather than rebuild the vector later. |
|
207 |
|
208 Cascades may be additive or multiplicitive; this is not inherent in |
|
209 the codebook, but set in the code using the codebook. Like |
|
210 interleaving, it's easiest to do it here. |
|
211 addmul==0 -> declarative (set the value) |
|
212 addmul==1 -> additive |
|
213 addmul==2 -> multiplicitive */ |
|
214 |
|
215 /* returns the [original, not compacted] entry number or -1 on eof *********/ |
|
216 long vorbis_book_decode(codebook *book, oggpack_buffer *b){ |
|
217 if(book->used_entries>0){ |
|
218 long packed_entry=decode_packed_entry_number(book,b); |
|
219 if(packed_entry>=0) |
|
220 return(book->dec_index[packed_entry]); |
|
221 } |
|
222 |
|
223 /* if there's no dec_index, the codebook unpacking isn't collapsed */ |
|
224 return(-1); |
|
225 } |
|
226 |
|
227 /* returns 0 on OK or -1 on eof *************************************/ |
|
228 long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a, |
|
229 oggpack_buffer *b,int n,int point){ |
|
230 if(book->used_entries>0){ |
|
231 int step=n/book->dim; |
|
232 long *entry = (long *)alloca(sizeof(*entry)*step); |
|
233 ogg_int32_t **t = (ogg_int32_t **)alloca(sizeof(*t)*step); |
|
234 int i,j,o; |
|
235 int shift=point-book->binarypoint; |
|
236 |
|
237 if(shift>=0){ |
|
238 for (i = 0; i < step; i++) { |
|
239 entry[i]=decode_packed_entry_number(book,b); |
|
240 if(entry[i]==-1)return(-1); |
|
241 t[i] = book->valuelist+entry[i]*book->dim; |
|
242 } |
|
243 for(i=0,o=0;i<book->dim;i++,o+=step) |
|
244 for (j=0;j<step;j++) |
|
245 a[o+j]+=t[j][i]>>shift; |
|
246 }else{ |
|
247 for (i = 0; i < step; i++) { |
|
248 entry[i]=decode_packed_entry_number(book,b); |
|
249 if(entry[i]==-1)return(-1); |
|
250 t[i] = book->valuelist+entry[i]*book->dim; |
|
251 } |
|
252 for(i=0,o=0;i<book->dim;i++,o+=step) |
|
253 for (j=0;j<step;j++) |
|
254 a[o+j]+=t[j][i]<<-shift; |
|
255 } |
|
256 } |
|
257 return(0); |
|
258 } |
|
259 |
|
260 long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a, |
|
261 oggpack_buffer *b,int n,int point){ |
|
262 if(book->used_entries>0){ |
|
263 int i,j,entry; |
|
264 ogg_int32_t *t; |
|
265 int shift=point-book->binarypoint; |
|
266 |
|
267 if(shift>=0){ |
|
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 }else{ |
|
276 for(i=0;i<n;){ |
|
277 entry = decode_packed_entry_number(book,b); |
|
278 if(entry==-1)return(-1); |
|
279 t = book->valuelist+entry*book->dim; |
|
280 for (j=0;j<book->dim;) |
|
281 a[i++]+=t[j++]<<-shift; |
|
282 } |
|
283 } |
|
284 } |
|
285 return(0); |
|
286 } |
|
287 |
|
288 long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a, |
|
289 oggpack_buffer *b,int n,int point){ |
|
290 if(book->used_entries>0){ |
|
291 int i,j,entry; |
|
292 ogg_int32_t *t; |
|
293 int shift=point-book->binarypoint; |
|
294 |
|
295 if(shift>=0){ |
|
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 }else{ |
|
306 |
|
307 for(i=0;i<n;){ |
|
308 entry = decode_packed_entry_number(book,b); |
|
309 if(entry==-1)return(-1); |
|
310 t = book->valuelist+entry*book->dim; |
|
311 for (j=0;j<book->dim;){ |
|
312 a[i++]=t[j++]<<-shift; |
|
313 } |
|
314 } |
|
315 } |
|
316 }else{ |
|
317 |
|
318 int i,j; |
|
319 for(i=0;i<n;){ |
|
320 for (j=0;j<book->dim;){ |
|
321 a[i++]=0; |
|
322 } |
|
323 } |
|
324 } |
|
325 return(0); |
|
326 } |
|
327 |
|
328 long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,\ |
|
329 long offset,int ch, |
|
330 oggpack_buffer *b,int n,int point){ |
|
331 if(book->used_entries>0){ |
|
332 long i,j,entry; |
|
333 int chptr=0; |
|
334 int shift=point-book->binarypoint; |
|
335 |
|
336 if(shift>=0){ |
|
337 |
|
338 for(i=offset;i<offset+n;){ |
|
339 entry = decode_packed_entry_number(book,b); |
|
340 if(entry==-1)return(-1); |
|
341 { |
|
342 const ogg_int32_t *t = book->valuelist+entry*book->dim; |
|
343 for (j=0;j<book->dim;j++){ |
|
344 a[chptr++][i]+=t[j]>>shift; |
|
345 if(chptr==ch){ |
|
346 chptr=0; |
|
347 i++; |
|
348 } |
|
349 } |
|
350 } |
|
351 } |
|
352 }else{ |
|
353 |
|
354 for(i=offset;i<offset+n;){ |
|
355 entry = decode_packed_entry_number(book,b); |
|
356 if(entry==-1)return(-1); |
|
357 { |
|
358 const ogg_int32_t *t = book->valuelist+entry*book->dim; |
|
359 for (j=0;j<book->dim;j++){ |
|
360 a[chptr++][i]+=t[j]<<-shift; |
|
361 if(chptr==ch){ |
|
362 chptr=0; |
|
363 i++; |
|
364 } |
|
365 } |
|
366 } |
|
367 } |
|
368 } |
|
369 } |
|
370 return(0); |
|
371 } |
|