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