Mercurial > mplayer.hg
annotate tremor/codebook.c @ 25066:89c42f6f6e89
(cosmetics) Indentation fix of previous commit.
author | voroshil |
---|---|
date | Sun, 18 Nov 2007 11:15:14 +0000 |
parents | cd6b211be811 |
children | e83eef58b30a |
rev | line source |
---|---|
14280 | 1 /******************************************************************** |
2 * * | |
3 * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE. * | |
4 * * | |
19251
cd6b211be811
Replace tremor files that had old headers saying "ALL REDISTRIBUTION
uau
parents:
14280
diff
changeset
|
5 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS * |
cd6b211be811
Replace tremor files that had old headers saying "ALL REDISTRIBUTION
uau
parents:
14280
diff
changeset
|
6 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE * |
cd6b211be811
Replace tremor files that had old headers saying "ALL REDISTRIBUTION
uau
parents:
14280
diff
changeset
|
7 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. * |
cd6b211be811
Replace tremor files that had old headers saying "ALL REDISTRIBUTION
uau
parents:
14280
diff
changeset
|
8 * * |
14280 | 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 } |