1 /************************************************************************
2 * Copyright (C) 2002-2009, Xiph.org Foundation
3 * Copyright (C) 2010, Robin Watts for Pinknoise Productions Ltd
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * * Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following disclaimer
14 * in the documentation and/or other materials provided with the
15 * distribution.
16 * * Neither the names of the Xiph.org Foundation nor Pinknoise
17 * Productions Ltd nor the names of its contributors may be used to
18 * endorse or promote products derived from this software without
19 * specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ************************************************************************
33
34 function: basic codebook pack/unpack/code/decode operations
35
36 ************************************************************************/
37
38 #include <stdlib.h>
39 #include <string.h>
40 #include <math.h>
41 #include <limits.h>
42 #include "ogg.h"
43 #include "ivorbiscodec.h"
44 #include "codebook.h"
45 #include "misc.h"
46 #include "os.h"
47
48
49 /**** pack/unpack helpers ******************************************/
_ilog(unsigned int v)50 int _ilog(unsigned int v){
51 int ret=0;
52 while(v){
53 ret++;
54 v>>=1;
55 }
56 return(ret);
57 }
58
decpack(long entry,long used_entry,long quantvals,codebook * b,oggpack_buffer * opb,int maptype)59 static ogg_uint32_t decpack(long entry,long used_entry,long quantvals,
60 codebook *b,oggpack_buffer *opb,int maptype){
61 ogg_uint32_t ret=0;
62 int j;
63
64 switch(b->dec_type){
65
66 case 0:
67 return (ogg_uint32_t)entry;
68
69 case 1:
70 if(maptype==1){
71 /* vals are already read into temporary column vector here */
72 for(j=0;j<b->dim;j++){
73 ogg_uint32_t off=entry%quantvals;
74 entry/=quantvals;
75 ret|=((ogg_uint16_t *)(b->q_val))[off]<<(b->q_bits*j);
76 }
77 }else{
78 for(j=0;j<b->dim;j++)
79 ret|=oggpack_read(opb,b->q_bits)<<(b->q_bits*j);
80 }
81 return ret;
82
83 case 2:
84 for(j=0;j<b->dim;j++){
85 ogg_uint32_t off=entry%quantvals;
86 entry/=quantvals;
87 ret|=off<<(b->q_pack*j);
88 }
89 return ret;
90
91 case 3:
92 return (ogg_uint32_t)used_entry;
93
94 }
95 return 0; /* silence compiler */
96 }
97
98 /* 32 bit float (not IEEE; nonnormalized mantissa +
99 biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm
100 Why not IEEE? It's just not that important here. */
101
_float32_unpack(long val,int * point)102 static ogg_int32_t _float32_unpack(long val,int *point){
103 long mant=val&0x1fffff;
104 int sign=val&0x80000000;
105
106 *point=((val&0x7fe00000L)>>21)-788;
107
108 if(mant){
109 while(!(mant&0x40000000)){
110 mant<<=1;
111 *point-=1;
112 }
113 if(sign)mant= -mant;
114 }else{
115 *point=-9999;
116 }
117 return mant;
118 }
119
120 /* choose the smallest supported node size that fits our decode table.
121 Legal bytewidths are 1/1 1/2 2/2 2/4 4/4 */
_determine_node_bytes(long used,int leafwidth)122 static int _determine_node_bytes(long used, int leafwidth){
123
124 /* special case small books to size 4 to avoid multiple special
125 cases in repack */
126 if(used<2)
127 return 4;
128
129 if(leafwidth==3)leafwidth=4;
130 if(_ilog(3*used-6)+1 <= leafwidth*4)
131 return leafwidth/2?leafwidth/2:1;
132 return leafwidth;
133 }
134
135 /* convenience/clarity; leaves are specified as multiple of node word
136 size (1 or 2) */
_determine_leaf_words(int nodeb,int leafwidth)137 static int _determine_leaf_words(int nodeb, int leafwidth){
138 if(leafwidth>nodeb)return 2;
139 return 1;
140 }
141
142 /* given a list of word lengths, number of used entries, and byte
143 width of a leaf, generate the decode table */
_make_words(char * l,long n,ogg_uint32_t * r,long quantvals,codebook * b,oggpack_buffer * opb,int maptype)144 static int _make_words(char *l,long n,ogg_uint32_t *r,long quantvals,
145 codebook *b, oggpack_buffer *opb,int maptype){
146 long i,j,count=0;
147 long top=0;
148 ogg_uint32_t marker[33];
149
150 if (n<1)
151 return 1;
152
153 if(n<2){
154 r[0]=0x80000000;
155 }else{
156 memset(marker,0,sizeof(marker));
157
158 for(i=0;i<n;i++){
159 long length=l[i];
160 if(length){
161 ogg_uint32_t entry=marker[length];
162 long chase=0;
163 if(count && !entry)return -1; /* overpopulated tree! */
164
165 /* chase the tree as far as it's already populated, fill in past */
166 for(j=0;j<length-1;j++){
167 int bit=(entry>>(length-j-1))&1;
168 if(chase>=top){
169 if (chase < 0 || chase >= n) return 1;
170 top++;
171 r[chase*2]=top;
172 r[chase*2+1]=0;
173 }else
174 if (chase < 0 || chase >= n || chase*2+bit > n*2+1) return 1;
175 if(!r[chase*2+bit])
176 r[chase*2+bit]=top;
177 chase=r[chase*2+bit];
178 if (chase < 0 || chase >= n) return 1;
179 }
180 {
181 int bit=(entry>>(length-j-1))&1;
182 if(chase>=top){
183 top++;
184 r[chase*2+1]=0;
185 }
186 r[chase*2+bit]= decpack(i,count++,quantvals,b,opb,maptype) |
187 0x80000000;
188 }
189
190 /* Look to see if the next shorter marker points to the node
191 above. if so, update it and repeat. */
192 for(j=length;j>0;j--){
193 if(marker[j]&1){
194 marker[j]=marker[j-1]<<1;
195 break;
196 }
197 marker[j]++;
198 }
199
200 /* prune the tree; the implicit invariant says all the longer
201 markers were dangling from our just-taken node. Dangle them
202 from our *new* node. */
203 for(j=length+1;j<33;j++)
204 if((marker[j]>>1) == entry){
205 entry=marker[j];
206 marker[j]=marker[j-1]<<1;
207 }else
208 break;
209 }
210 }
211 }
212
213 return 0;
214 }
215
_make_decode_table(codebook * s,char * lengthlist,long quantvals,oggpack_buffer * opb,int maptype)216 static int _make_decode_table(codebook *s,char *lengthlist,long quantvals,
217 oggpack_buffer *opb,int maptype){
218 int i;
219 ogg_uint32_t *work;
220
221 if (!lengthlist) return 1;
222 if(s->dec_nodeb==4){
223 /* Over-allocate by using s->entries instead of used_entries.
224 * This means that we can use s->entries to enforce size in
225 * _make_words without messing up length list looping.
226 * This probably wastes a bit of space, but it shouldn't
227 * impact behavior or size too much.
228 */
229 s->dec_table=_ogg_malloc((s->entries*2+1)*sizeof(*work));
230 if (!s->dec_table) return 1;
231 /* +1 (rather than -2) is to accommodate 0 and 1 sized books,
232 which are specialcased to nodeb==4 */
233 if(_make_words(lengthlist,s->entries,
234 s->dec_table,quantvals,s,opb,maptype))return 1;
235
236 return 0;
237 }
238
239 if (s->used_entries > INT_MAX/2 ||
240 s->used_entries*2 > INT_MAX/((long) sizeof(*work)) - 1) return 1;
241 /* Overallocate as above */
242 work=alloca((s->entries*2+1)*sizeof(*work));
243 if(_make_words(lengthlist,s->entries,work,quantvals,s,opb,maptype))return 1;
244 if (s->used_entries > INT_MAX/(s->dec_leafw+1)) return 1;
245 if (s->dec_nodeb && s->used_entries * (s->dec_leafw+1) > INT_MAX/s->dec_nodeb) return 1;
246 s->dec_table=_ogg_malloc((s->used_entries*(s->dec_leafw+1)-2)*
247 s->dec_nodeb);
248 if (!s->dec_table) return 1;
249
250 if(s->dec_leafw==1){
251 switch(s->dec_nodeb){
252 case 1:
253 for(i=0;i<s->used_entries*2-2;i++)
254 ((unsigned char *)s->dec_table)[i]=(unsigned char)
255 (((work[i] & 0x80000000UL) >> 24) | work[i]);
256 break;
257 case 2:
258 for(i=0;i<s->used_entries*2-2;i++)
259 ((ogg_uint16_t *)s->dec_table)[i]=(ogg_uint16_t)
260 (((work[i] & 0x80000000UL) >> 16) | work[i]);
261 break;
262 }
263
264 }else{
265 /* more complex; we have to do a two-pass repack that updates the
266 node indexing. */
267 long top=s->used_entries*3-2;
268 if(s->dec_nodeb==1){
269 unsigned char *out=(unsigned char *)s->dec_table;
270
271 for(i=s->used_entries*2-4;i>=0;i-=2){
272 if(work[i]&0x80000000UL){
273 if(work[i+1]&0x80000000UL){
274 top-=4;
275 out[top]=(work[i]>>8 & 0x7f)|0x80;
276 out[top+1]=(work[i+1]>>8 & 0x7f)|0x80;
277 out[top+2]=work[i] & 0xff;
278 out[top+3]=work[i+1] & 0xff;
279 }else{
280 top-=3;
281 out[top]=(work[i]>>8 & 0x7f)|0x80;
282 out[top+1]=work[work[i+1]*2];
283 out[top+2]=work[i] & 0xff;
284 }
285 }else{
286 if(work[i+1]&0x80000000UL){
287 top-=3;
288 out[top]=work[work[i]*2];
289 out[top+1]=(work[i+1]>>8 & 0x7f)|0x80;
290 out[top+2]=work[i+1] & 0xff;
291 }else{
292 top-=2;
293 out[top]=work[work[i]*2];
294 out[top+1]=work[work[i+1]*2];
295 }
296 }
297 work[i]=top;
298 }
299 }else{
300 ogg_uint16_t *out=(ogg_uint16_t *)s->dec_table;
301 for(i=s->used_entries*2-4;i>=0;i-=2){
302 if(work[i]&0x80000000UL){
303 if(work[i+1]&0x80000000UL){
304 top-=4;
305 out[top]=(work[i]>>16 & 0x7fff)|0x8000;
306 out[top+1]=(work[i+1]>>16 & 0x7fff)|0x8000;
307 out[top+2]=work[i] & 0xffff;
308 out[top+3]=work[i+1] & 0xffff;
309 }else{
310 top-=3;
311 out[top]=(work[i]>>16 & 0x7fff)|0x8000;
312 out[top+1]=work[work[i+1]*2];
313 out[top+2]=work[i] & 0xffff;
314 }
315 }else{
316 if(work[i+1]&0x80000000UL){
317 top-=3;
318 out[top]=work[work[i]*2];
319 out[top+1]=(work[i+1]>>16 & 0x7fff)|0x8000;
320 out[top+2]=work[i+1] & 0xffff;
321 }else{
322 top-=2;
323 out[top]=work[work[i]*2];
324 out[top+1]=work[work[i+1]*2];
325 }
326 }
327 work[i]=top;
328 }
329 }
330 }
331
332 return 0;
333 }
334
335 /* most of the time, entries%dimensions == 0, but we need to be
336 well defined. We define that the possible vales at each
337 scalar is values == entries/dim. If entries%dim != 0, we'll
338 have 'too few' values (values*dim<entries), which means that
339 we'll have 'left over' entries; left over entries use zeroed
340 values (and are wasted). So don't generate codebooks like
341 that */
342 /* there might be a straightforward one-line way to do the below
343 that's portable and totally safe against roundoff, but I haven't
344 thought of it. Therefore, we opt on the side of caution */
_book_maptype1_quantvals(codebook * b)345 long _book_maptype1_quantvals(codebook *b){
346 /* get us a starting hint, we'll polish it below */
347 int bits=_ilog(b->entries);
348 int vals=b->entries>>((bits-1)*(b->dim-1)/b->dim);
349
350 while(1){
351 long acc=1;
352 long acc1=1;
353 int i;
354 for(i=0;i<b->dim;i++){
355 acc*=vals;
356 acc1*=vals+1;
357 }
358 if(acc<=b->entries && acc1>b->entries){
359 return(vals);
360 }else{
361 if(acc>b->entries){
362 vals--;
363 }else{
364 vals++;
365 }
366 }
367 }
368 }
369
vorbis_book_clear(codebook * b)370 void vorbis_book_clear(codebook *b){
371 /* static book is not cleared; we're likely called on the lookup and
372 the static codebook belongs to the info struct */
373 if(b->q_val)_ogg_free(b->q_val);
374 if(b->dec_table)_ogg_free(b->dec_table);
375 if(b->dec_buf)_ogg_free(b->dec_buf);
376
377 memset(b,0,sizeof(*b));
378 }
379
vorbis_book_unpack(oggpack_buffer * opb,codebook * s)380 int vorbis_book_unpack(oggpack_buffer *opb,codebook *s){
381 char *lengthlist=NULL;
382 int quantvals=0;
383 long i,j;
384 int maptype;
385
386 memset(s,0,sizeof(*s));
387
388 /* make sure alignment is correct */
389 if(oggpack_read(opb,24)!=0x564342)goto _eofout;
390
391 /* first the basic parameters */
392 s->dim=oggpack_read(opb,16);
393 s->dec_buf=_ogg_malloc(sizeof(ogg_int32_t)*s->dim);
394 if (s->dec_buf == NULL)
395 goto _errout;
396 s->entries=oggpack_read(opb,24);
397 if(s->entries<=0)goto _eofout;
398 if(s->dim<=0)goto _eofout;
399 if(_ilog(s->dim)+_ilog(s->entries)>24)goto _eofout;
400 if (s->dim > INT_MAX/s->entries) goto _eofout;
401
402 /* codeword ordering.... length ordered or unordered? */
403 switch((int)oggpack_read(opb,1)){
404 case 0:
405 /* unordered */
406 lengthlist=(char *)alloca(sizeof(*lengthlist)*s->entries);
407 if(!lengthlist) goto _eofout;
408
409 /* allocated but unused entries? */
410 if(oggpack_read(opb,1)){
411 /* yes, unused entries */
412
413 for(i=0;i<s->entries;i++){
414 if(oggpack_read(opb,1)){
415 long num=oggpack_read(opb,5);
416 if(num==-1)goto _eofout;
417 lengthlist[i]=(char)(num+1);
418 s->used_entries++;
419 if(num+1>s->dec_maxlength)s->dec_maxlength=num+1;
420 }else
421 lengthlist[i]=0;
422 }
423 }else{
424 /* all entries used; no tagging */
425 s->used_entries=s->entries;
426 for(i=0;i<s->entries;i++){
427 long num=oggpack_read(opb,5);
428 if(num==-1)goto _eofout;
429 lengthlist[i]=(char)(num+1);
430 if(num+1>s->dec_maxlength)s->dec_maxlength=num+1;
431 }
432 }
433
434 break;
435 case 1:
436 /* ordered */
437 {
438 long length=oggpack_read(opb,5)+1;
439
440 s->used_entries=s->entries;
441 lengthlist=(char *)alloca(sizeof(*lengthlist)*s->entries);
442 if (!lengthlist) goto _eofout;
443
444 for(i=0;i<s->entries;){
445 long num=oggpack_read(opb,_ilog(s->entries-i));
446 if(num<0)goto _eofout;
447 for(j=0;j<num && i<s->entries;j++,i++)
448 lengthlist[i]=(char)length;
449 s->dec_maxlength=length;
450 length++;
451 }
452 }
453 break;
454 default:
455 /* EOF */
456 goto _eofout;
457 }
458
459
460 /* Do we have a mapping to unpack? */
461
462 if((maptype=oggpack_read(opb,4))>0){
463 s->q_min=_float32_unpack(oggpack_read(opb,32),&s->q_minp);
464 s->q_del=_float32_unpack(oggpack_read(opb,32),&s->q_delp);
465 s->q_bits=oggpack_read(opb,4)+1;
466 s->q_seq=oggpack_read(opb,1);
467
468 s->q_del>>=s->q_bits;
469 s->q_delp+=s->q_bits;
470 }
471
472 switch(maptype){
473 case 0:
474
475 /* no mapping; decode type 0 */
476
477 /* how many bytes for the indexing? */
478 /* this is the correct boundary here; we lose one bit to
479 node/leaf mark */
480 s->dec_nodeb=_determine_node_bytes(s->used_entries,_ilog(s->entries)/8+1);
481 s->dec_leafw=_determine_leaf_words(s->dec_nodeb,_ilog(s->entries)/8+1);
482 s->dec_type=0;
483
484 if(_make_decode_table(s,lengthlist,quantvals,opb,maptype)) goto _errout;
485 break;
486
487 case 1:
488
489 /* mapping type 1; implicit values by lattice position */
490 quantvals=_book_maptype1_quantvals(s);
491
492 /* dec_type choices here are 1,2; 3 doesn't make sense */
493 {
494 /* packed values */
495 long total1=(s->q_bits*s->dim+8)/8; /* remember flag bit */
496 if (s->dim > (INT_MAX-8)/s->q_bits) goto _eofout;
497 /* vector of column offsets; remember flag bit */
498 long total2=(_ilog(quantvals-1)*s->dim+8)/8+(s->q_bits+7)/8;
499
500
501 if(total1<=4 && total1<=total2){
502 /* use dec_type 1: vector of packed values */
503
504 /* need quantized values before */
505 s->q_val=alloca(sizeof(ogg_uint16_t)*quantvals);
506 if (!s->q_val) goto _eofout;
507 for(i=0;i<quantvals;i++)
508 ((ogg_uint16_t *)s->q_val)[i]=(ogg_uint16_t)oggpack_read(opb,s->q_bits);
509
510 if(oggpack_eop(opb)){
511 s->q_val=0; /* cleanup must not free alloca memory */
512 goto _eofout;
513 }
514
515 s->dec_type=1;
516 s->dec_nodeb=_determine_node_bytes(s->used_entries,
517 (s->q_bits*s->dim+8)/8);
518 s->dec_leafw=_determine_leaf_words(s->dec_nodeb,
519 (s->q_bits*s->dim+8)/8);
520 if(_make_decode_table(s,lengthlist,quantvals,opb,maptype)){
521 s->q_val=0; /* cleanup must not free alloca memory */
522 goto _errout;
523 }
524
525 s->q_val=0; /* about to go out of scope; _make_decode_table
526 was using it */
527
528 }else{
529 /* use dec_type 2: packed vector of column offsets */
530
531 /* need quantized values before */
532 if(s->q_bits<=8){
533 s->q_val=_ogg_malloc(quantvals);
534 if (!s->q_val) goto _eofout;
535 for(i=0;i<quantvals;i++)
536 ((unsigned char *)s->q_val)[i]=(unsigned char)oggpack_read(opb,s->q_bits);
537 }else{
538 s->q_val=_ogg_malloc(quantvals*2);
539 if (!s->q_val) goto _eofout;
540 for(i=0;i<quantvals;i++)
541 ((ogg_uint16_t *)s->q_val)[i]=(ogg_uint16_t)oggpack_read(opb,s->q_bits);
542 }
543
544 if(oggpack_eop(opb))goto _eofout;
545
546 s->q_pack=_ilog(quantvals-1);
547 s->dec_type=2;
548 s->dec_nodeb=_determine_node_bytes(s->used_entries,
549 (_ilog(quantvals-1)*s->dim+8)/8);
550 s->dec_leafw=_determine_leaf_words(s->dec_nodeb,
551 (_ilog(quantvals-1)*s->dim+8)/8);
552 if(_make_decode_table(s,lengthlist,quantvals,opb,maptype))goto _errout;
553
554 }
555 }
556 break;
557 case 2:
558
559 /* mapping type 2; explicit array of values */
560 quantvals=s->entries*s->dim;
561 /* dec_type choices here are 1,3; 2 is not possible */
562
563 if( (s->q_bits*s->dim+8)/8 <=4){ /* remember flag bit */
564 /* use dec_type 1: vector of packed values */
565
566 s->dec_type=1;
567 s->dec_nodeb=_determine_node_bytes(s->used_entries,(s->q_bits*s->dim+8)/8);
568 s->dec_leafw=_determine_leaf_words(s->dec_nodeb,(s->q_bits*s->dim+8)/8);
569 if(_make_decode_table(s,lengthlist,quantvals,opb,maptype))goto _errout;
570
571 }else{
572 /* use dec_type 3: scalar offset into packed value array */
573
574 s->dec_type=3;
575 s->dec_nodeb=_determine_node_bytes(s->used_entries,_ilog(s->used_entries-1)/8+1);
576 s->dec_leafw=_determine_leaf_words(s->dec_nodeb,_ilog(s->used_entries-1)/8+1);
577 if(_make_decode_table(s,lengthlist,quantvals,opb,maptype))goto _errout;
578
579 /* get the vals & pack them */
580 s->q_pack=(s->q_bits+7)/8*s->dim;
581 s->q_val=_ogg_malloc(s->q_pack*s->used_entries);
582
583 if(s->q_bits<=8){
584 for(i=0;i<s->used_entries*s->dim;i++)
585 ((unsigned char *)(s->q_val))[i]=(unsigned char)oggpack_read(opb,s->q_bits);
586 }else{
587 for(i=0;i<s->used_entries*s->dim;i++)
588 ((ogg_uint16_t *)(s->q_val))[i]=(ogg_uint16_t)oggpack_read(opb,s->q_bits);
589 }
590 }
591 break;
592 default:
593 goto _errout;
594 }
595
596 if (s->dec_nodeb==1)
597 if (s->dec_leafw == 1)
598 s->dec_method = 0;
599 else
600 s->dec_method = 1;
601 else if (s->dec_nodeb==2)
602 if (s->dec_leafw == 1)
603 s->dec_method = 2;
604 else
605 s->dec_method = 3;
606 else
607 s->dec_method = 4;
608
609 if(oggpack_eop(opb))goto _eofout;
610
611 return 0;
612 _errout:
613 _eofout:
614 vorbis_book_clear(s);
615 return -1;
616 }
617
618 #ifndef ONLY_C
619 ogg_uint32_t decode_packed_entry_number(codebook *book,
620 oggpack_buffer *b);
621 #else
decode_packed_entry_number(codebook * book,oggpack_buffer * b)622 static inline ogg_uint32_t decode_packed_entry_number(codebook *book,
623 oggpack_buffer *b){
624 ogg_uint32_t chase=0;
625 int read=book->dec_maxlength;
626 long lok = oggpack_look(b,read),i;
627
628 while(lok<0 && read>1)
629 lok = oggpack_look(b, --read);
630
631 if(lok<0){
632 oggpack_adv(b,1); /* force eop */
633 return -1;
634 }
635
636 /* chase the tree with the bits we got */
637 switch (book->dec_method)
638 {
639 case 0:
640 {
641 /* book->dec_nodeb==1, book->dec_leafw==1 */
642 /* 8/8 - Used */
643 unsigned char *t=(unsigned char *)book->dec_table;
644
645 for(i=0;i<read;i++){
646 chase=t[chase*2+((lok>>i)&1)];
647 if(chase&0x80UL)break;
648 }
649 chase&=0x7fUL;
650 break;
651 }
652 case 1:
653 {
654 /* book->dec_nodeb==1, book->dec_leafw!=1 */
655 /* 8/16 - Used by infile2 */
656 unsigned char *t=(unsigned char *)book->dec_table;
657 for(i=0;i<read;i++){
658 int bit=(lok>>i)&1;
659 int next=t[chase+bit];
660 if(next&0x80){
661 chase= (next<<8) | t[chase+bit+1+(!bit || t[chase]&0x80)];
662 break;
663 }
664 chase=next;
665 }
666 //chase&=0x7fffUL;
667 chase&=~0x8000UL;
668 break;
669 }
670 case 2:
671 {
672 /* book->dec_nodeb==2, book->dec_leafw==1 */
673 /* 16/16 - Used */
674 for(i=0;i<read;i++){
675 chase=((ogg_uint16_t *)(book->dec_table))[chase*2+((lok>>i)&1)];
676 if(chase&0x8000UL)break;
677 }
678 //chase&=0x7fffUL;
679 chase&=~0x8000UL;
680 break;
681 }
682 case 3:
683 {
684 /* book->dec_nodeb==2, book->dec_leafw!=1 */
685 /* 16/32 - Used by infile2 */
686 ogg_uint16_t *t=(ogg_uint16_t *)book->dec_table;
687 for(i=0;i<read;i++){
688 int bit=(lok>>i)&1;
689 int next=t[chase+bit];
690 if(next&0x8000){
691 chase= (next<<16) | t[chase+bit+1+(!bit || t[chase]&0x8000)];
692 break;
693 }
694 chase=next;
695 }
696 //chase&=0x7fffffffUL;
697 chase&=~0x80000000UL;
698 break;
699 }
700 case 4:
701 {
702 //Output("32/32");
703 for(i=0;i<read;i++){
704 chase=((ogg_uint32_t *)(book->dec_table))[chase*2+((lok>>i)&1)];
705 if(chase&0x80000000UL)break;
706 }
707 //chase&=0x7fffffffUL;
708 chase&=~0x80000000UL;
709 break;
710 }
711 }
712
713 if(i<read){
714 oggpack_adv(b,i+1);
715 return chase;
716 }
717 oggpack_adv(b,read+1);
718 return(-1);
719 }
720 #endif
721
722 /* returns the [original, not compacted] entry number or -1 on eof *********/
vorbis_book_decode(codebook * book,oggpack_buffer * b)723 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
724 if(book->dec_type)return -1;
725 return decode_packed_entry_number(book,b);
726 }
727
728 #ifndef ONLY_C
729 int decode_map(codebook *s, oggpack_buffer *b, ogg_int32_t *v, int point);
730 #else
decode_map(codebook * s,oggpack_buffer * b,ogg_int32_t * v,int point)731 static int decode_map(codebook *s, oggpack_buffer *b, ogg_int32_t *v, int point){
732 ogg_uint32_t entry = decode_packed_entry_number(s,b);
733 int i;
734 if(oggpack_eop(b))return(-1);
735
736 /* 1 used by test file 0 */
737
738 /* according to decode type */
739 switch(s->dec_type){
740 case 1:{
741 /* packed vector of values */
742 int mask=(1<<s->q_bits)-1;
743 for(i=0;i<s->dim;i++){
744 v[i]=entry&mask;
745 entry>>=s->q_bits;
746 }
747 break;
748 }
749 case 2:{
750 /* packed vector of column offsets */
751 int mask=(1<<s->q_pack)-1;
752 for(i=0;i<s->dim;i++){
753 if(s->q_bits<=8)
754 v[i]=((unsigned char *)(s->q_val))[entry&mask];
755 else
756 v[i]=((ogg_uint16_t *)(s->q_val))[entry&mask];
757 entry>>=s->q_pack;
758 }
759 break;
760 }
761 case 3:{
762 /* offset into array */
763 void *ptr=s->q_val+entry*s->q_pack;
764
765 if(s->q_bits<=8){
766 for(i=0;i<s->dim;i++)
767 v[i]=((unsigned char *)ptr)[i];
768 }else{
769 for(i=0;i<s->dim;i++)
770 v[i]=((ogg_uint16_t *)ptr)[i];
771 }
772 break;
773 }
774 default:
775 return -1;
776 }
777
778 /* we have the unpacked multiplicands; compute final vals */
779 {
780 int shiftM = point-s->q_delp;
781 ogg_int32_t add = point-s->q_minp;
782 int mul = s->q_del;
783
784 if(add>0)
785 add= s->q_min >> add;
786 else
787 add= s->q_min << -add;
788 if (shiftM<0)
789 {
790 mul <<= -shiftM;
791 shiftM = 0;
792 }
793 add <<= shiftM;
794
795 for(i=0;i<s->dim;i++)
796 v[i]= ((add + v[i] * mul) >> shiftM);
797
798 if(s->q_seq)
799 for(i=1;i<s->dim;i++)
800 v[i]+=v[i-1];
801 }
802
803 return 0;
804 }
805 #endif
806
807 /* 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)808 long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a,
809 oggpack_buffer *b,int n,int point){
810 if(book->used_entries>0){
811 int step=n/book->dim;
812 ogg_int32_t *v = book->dec_buf;//(ogg_int32_t *)alloca(sizeof(*v)*book->dim);
813 int i,j,o;
814 if (!v) return -1;
815
816 for (j=0;j<step;j++){
817 if(decode_map(book,b,v,point))return -1;
818 for(i=0,o=j;i<book->dim;i++,o+=step)
819 a[o]+=v[i];
820 }
821 }
822 return 0;
823 }
824
vorbis_book_decodev_add(codebook * book,ogg_int32_t * a,oggpack_buffer * b,int n,int point)825 long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a,
826 oggpack_buffer *b,int n,int point){
827 if(book->used_entries>0){
828 ogg_int32_t *v = book->dec_buf;//(ogg_int32_t *)alloca(sizeof(*v)*book->dim);
829 int i,j;
830
831 if (!v) return -1;
832 for(i=0;i<n;){
833 if(decode_map(book,b,v,point))return -1;
834 for (j=0;j<book->dim;j++)
835 a[i++]+=v[j];
836 }
837 }
838 return 0;
839 }
840
vorbis_book_decodev_set(codebook * book,ogg_int32_t * a,oggpack_buffer * b,int n,int point)841 long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a,
842 oggpack_buffer *b,int n,int point){
843 if(book->used_entries>0){
844 ogg_int32_t *v = book->dec_buf;//(ogg_int32_t *)alloca(sizeof(*v)*book->dim);
845 int i,j;
846
847 if (!v) return -1;
848 for(i=0;i<n;){
849 if(decode_map(book,b,v,point))return -1;
850 for (j=0;j<book->dim;j++)
851 a[i++]=v[j];
852 }
853 }else{
854 int i,j;
855
856 for(i=0;i<n;){
857 for (j=0;j<book->dim;j++)
858 a[i++]=0;
859 }
860 }
861
862 return 0;
863 }
864
865 #ifndef ONLY_C
866 long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,
867 long offset,int ch,
868 oggpack_buffer *b,int n,int point);
869 #else
vorbis_book_decodevv_add(codebook * book,ogg_int32_t ** a,long offset,int ch,oggpack_buffer * b,int n,int point)870 long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,
871 long offset,int ch,
872 oggpack_buffer *b,int n,int point){
873 if(book->used_entries>0){
874
875 ogg_int32_t *v = book->dec_buf;//(ogg_int32_t *)alloca(sizeof(*v)*book->dim);
876 long i,j;
877 int chptr=0;
878
879 if (!v) return -1;
880 for(i=offset;i<offset+n;){
881 if(decode_map(book,b,v,point))return -1;
882 for (j=0;j<book->dim;j++){
883 a[chptr++][i]+=v[j];
884 if(chptr==ch){
885 chptr=0;
886 i++;
887 }
888 }
889 }
890 }
891
892 return 0;
893 }
894 #endif
895