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 *************/
vorbis_staticbook_unpack(oggpack_buffer * opb,static_codebook * s)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
bitreverse(ogg_uint32_t x)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
decode_packed_entry_number(codebook * book,oggpack_buffer * b)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 *********/
vorbis_book_decode(codebook * book,oggpack_buffer * b)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 *************************************/
vorbis_book_decodevs_add(codebook * book,ogg_int32_t * a,oggpack_buffer * b,int n,int point)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
vorbis_book_decodev_add(codebook * book,ogg_int32_t * a,oggpack_buffer * b,int n,int point)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
vorbis_book_decodev_set(codebook * book,ogg_int32_t * a,oggpack_buffer * b,int n,int point)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
vorbis_book_decodevv_add(codebook * book,ogg_int32_t ** a,long offset,int ch,oggpack_buffer * b,int n,int point)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 }
372