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=calloc((s->entries*2+1),sizeof(*work));
243 if (!work) return 1;
244 if(_make_words(lengthlist,s->entries,work,quantvals,s,opb,maptype)) goto error_out;
245 if (s->used_entries > INT_MAX/(s->dec_leafw+1)) goto error_out;
246 if (s->dec_nodeb && s->used_entries * (s->dec_leafw+1) > INT_MAX/s->dec_nodeb) goto error_out;
247 s->dec_table=_ogg_malloc((s->used_entries*(s->dec_leafw+1)-2)*
248 s->dec_nodeb);
249 if (!s->dec_table) goto error_out;
250
251 if(s->dec_leafw==1){
252 switch(s->dec_nodeb){
253 case 1:
254 for(i=0;i<s->used_entries*2-2;i++)
255 ((unsigned char *)s->dec_table)[i]=(unsigned char)
256 (((work[i] & 0x80000000UL) >> 24) | work[i]);
257 break;
258 case 2:
259 for(i=0;i<s->used_entries*2-2;i++)
260 ((ogg_uint16_t *)s->dec_table)[i]=(ogg_uint16_t)
261 (((work[i] & 0x80000000UL) >> 16) | work[i]);
262 break;
263 }
264
265 }else{
266 /* more complex; we have to do a two-pass repack that updates the
267 node indexing. */
268 long top=s->used_entries*3-2;
269 if(s->dec_nodeb==1){
270 unsigned char *out=(unsigned char *)s->dec_table;
271
272 for(i=s->used_entries*2-4;i>=0;i-=2){
273 if(work[i]&0x80000000UL){
274 if(work[i+1]&0x80000000UL){
275 top-=4;
276 out[top]=(work[i]>>8 & 0x7f)|0x80;
277 out[top+1]=(work[i+1]>>8 & 0x7f)|0x80;
278 out[top+2]=work[i] & 0xff;
279 out[top+3]=work[i+1] & 0xff;
280 }else{
281 top-=3;
282 out[top]=(work[i]>>8 & 0x7f)|0x80;
283 out[top+1]=work[work[i+1]*2];
284 out[top+2]=work[i] & 0xff;
285 }
286 }else{
287 if(work[i+1]&0x80000000UL){
288 top-=3;
289 out[top]=work[work[i]*2];
290 out[top+1]=(work[i+1]>>8 & 0x7f)|0x80;
291 out[top+2]=work[i+1] & 0xff;
292 }else{
293 top-=2;
294 out[top]=work[work[i]*2];
295 out[top+1]=work[work[i+1]*2];
296 }
297 }
298 work[i]=top;
299 }
300 }else{
301 ogg_uint16_t *out=(ogg_uint16_t *)s->dec_table;
302 for(i=s->used_entries*2-4;i>=0;i-=2){
303 if(work[i]&0x80000000UL){
304 if(work[i+1]&0x80000000UL){
305 top-=4;
306 out[top]=(work[i]>>16 & 0x7fff)|0x8000;
307 out[top+1]=(work[i+1]>>16 & 0x7fff)|0x8000;
308 out[top+2]=work[i] & 0xffff;
309 out[top+3]=work[i+1] & 0xffff;
310 }else{
311 top-=3;
312 out[top]=(work[i]>>16 & 0x7fff)|0x8000;
313 out[top+1]=work[work[i+1]*2];
314 out[top+2]=work[i] & 0xffff;
315 }
316 }else{
317 if(work[i+1]&0x80000000UL){
318 top-=3;
319 out[top]=work[work[i]*2];
320 out[top+1]=(work[i+1]>>16 & 0x7fff)|0x8000;
321 out[top+2]=work[i+1] & 0xffff;
322 }else{
323 top-=2;
324 out[top]=work[work[i]*2];
325 out[top+1]=work[work[i+1]*2];
326 }
327 }
328 work[i]=top;
329 }
330 }
331 }
332
333 free(work);
334 return 0;
335 error_out:
336 free(work);
337 return 1;
338 }
339
340 /* most of the time, entries%dimensions == 0, but we need to be
341 well defined. We define that the possible vales at each
342 scalar is values == entries/dim. If entries%dim != 0, we'll
343 have 'too few' values (values*dim<entries), which means that
344 we'll have 'left over' entries; left over entries use zeroed
345 values (and are wasted). So don't generate codebooks like
346 that */
347 /* there might be a straightforward one-line way to do the below
348 that's portable and totally safe against roundoff, but I haven't
349 thought of it. Therefore, we opt on the side of caution */
_book_maptype1_quantvals(codebook * b)350 long _book_maptype1_quantvals(codebook *b){
351 /* get us a starting hint, we'll polish it below */
352 int bits=_ilog(b->entries);
353 int vals=b->entries>>((bits-1)*(b->dim-1)/b->dim);
354
355 while(1){
356 long acc=1;
357 long acc1=1;
358 int i;
359 for(i=0;i<b->dim;i++){
360 acc*=vals;
361 acc1*=vals+1;
362 }
363 if(acc<=b->entries && acc1>b->entries){
364 return(vals);
365 }else{
366 if(acc>b->entries){
367 vals--;
368 }else{
369 vals++;
370 }
371 }
372 }
373 }
374
vorbis_book_clear(codebook * b)375 void vorbis_book_clear(codebook *b){
376 /* static book is not cleared; we're likely called on the lookup and
377 the static codebook belongs to the info struct */
378 if(b->q_val)_ogg_free(b->q_val);
379 if(b->dec_table)_ogg_free(b->dec_table);
380 if(b->dec_buf)_ogg_free(b->dec_buf);
381
382 memset(b,0,sizeof(*b));
383 }
384
vorbis_book_unpack(oggpack_buffer * opb,codebook * s)385 int vorbis_book_unpack(oggpack_buffer *opb,codebook *s){
386 char *lengthlist=NULL;
387 int quantvals=0;
388 long i,j;
389 int maptype;
390
391 memset(s,0,sizeof(*s));
392
393 /* make sure alignment is correct */
394 if(oggpack_read(opb,24)!=0x564342)goto _eofout;
395
396 /* first the basic parameters */
397 s->dim=oggpack_read(opb,16);
398 s->dec_buf=_ogg_malloc(sizeof(ogg_int32_t)*s->dim);
399 if (s->dec_buf == NULL)
400 goto _errout;
401 s->entries=oggpack_read(opb,24);
402 if(s->entries<=0)goto _eofout;
403 if(s->dim<=0)goto _eofout;
404 if(_ilog(s->dim)+_ilog(s->entries)>24)goto _eofout;
405 if (s->dim > INT_MAX/s->entries) goto _eofout;
406
407 /* codeword ordering.... length ordered or unordered? */
408 switch((int)oggpack_read(opb,1)){
409 case 0:
410 /* unordered */
411 lengthlist=(char *)calloc(s->entries, sizeof(*lengthlist));
412 if(!lengthlist) goto _eofout;
413
414 /* allocated but unused entries? */
415 if(oggpack_read(opb,1)){
416 /* yes, unused entries */
417
418 for(i=0;i<s->entries;i++){
419 if(oggpack_read(opb,1)){
420 long num=oggpack_read(opb,5);
421 if(num==-1)goto _eofout;
422 lengthlist[i]=(char)(num+1);
423 s->used_entries++;
424 if(num+1>s->dec_maxlength)s->dec_maxlength=num+1;
425 }else
426 lengthlist[i]=0;
427 }
428 }else{
429 /* all entries used; no tagging */
430 s->used_entries=s->entries;
431 for(i=0;i<s->entries;i++){
432 long num=oggpack_read(opb,5);
433 if(num==-1)goto _eofout;
434 lengthlist[i]=(char)(num+1);
435 if(num+1>s->dec_maxlength)s->dec_maxlength=num+1;
436 }
437 }
438
439 break;
440 case 1:
441 /* ordered */
442 {
443 long length=oggpack_read(opb,5)+1;
444
445 s->used_entries=s->entries;
446 lengthlist=(char *)calloc(s->entries, sizeof(*lengthlist));
447 if (!lengthlist) goto _eofout;
448
449 for(i=0;i<s->entries;){
450 long num=oggpack_read(opb,_ilog(s->entries-i));
451 if(num<0)goto _eofout;
452 for(j=0;j<num && i<s->entries;j++,i++)
453 lengthlist[i]=(char)length;
454 s->dec_maxlength=length;
455 length++;
456 }
457 }
458 break;
459 default:
460 /* EOF */
461 goto _eofout;
462 }
463
464
465 /* Do we have a mapping to unpack? */
466
467 if((maptype=oggpack_read(opb,4))>0){
468 s->q_min=_float32_unpack(oggpack_read(opb,32),&s->q_minp);
469 s->q_del=_float32_unpack(oggpack_read(opb,32),&s->q_delp);
470 s->q_bits=oggpack_read(opb,4)+1;
471 s->q_seq=oggpack_read(opb,1);
472
473 s->q_del>>=s->q_bits;
474 s->q_delp+=s->q_bits;
475 }
476
477 switch(maptype){
478 case 0:
479
480 /* no mapping; decode type 0 */
481
482 /* how many bytes for the indexing? */
483 /* this is the correct boundary here; we lose one bit to
484 node/leaf mark */
485 s->dec_nodeb=_determine_node_bytes(s->used_entries,_ilog(s->entries)/8+1);
486 s->dec_leafw=_determine_leaf_words(s->dec_nodeb,_ilog(s->entries)/8+1);
487 s->dec_type=0;
488
489 if(_make_decode_table(s,lengthlist,quantvals,opb,maptype)) goto _errout;
490 break;
491
492 case 1:
493
494 /* mapping type 1; implicit values by lattice position */
495 quantvals=_book_maptype1_quantvals(s);
496
497 /* dec_type choices here are 1,2; 3 doesn't make sense */
498 {
499 /* packed values */
500 long total1=(s->q_bits*s->dim+8)/8; /* remember flag bit */
501 if (s->dim > (INT_MAX-8)/s->q_bits) goto _eofout;
502 /* vector of column offsets; remember flag bit */
503 long total2=(_ilog(quantvals-1)*s->dim+8)/8+(s->q_bits+7)/8;
504
505
506 if(total1<=4 && total1<=total2){
507 /* use dec_type 1: vector of packed values */
508
509 /* need quantized values before */
510 s->q_val=alloca(sizeof(ogg_uint16_t)*quantvals);
511 if (!s->q_val) goto _eofout;
512 for(i=0;i<quantvals;i++)
513 ((ogg_uint16_t *)s->q_val)[i]=(ogg_uint16_t)oggpack_read(opb,s->q_bits);
514
515 if(oggpack_eop(opb)){
516 s->q_val=0; /* cleanup must not free alloca memory */
517 goto _eofout;
518 }
519
520 s->dec_type=1;
521 s->dec_nodeb=_determine_node_bytes(s->used_entries,
522 (s->q_bits*s->dim+8)/8);
523 s->dec_leafw=_determine_leaf_words(s->dec_nodeb,
524 (s->q_bits*s->dim+8)/8);
525 if(_make_decode_table(s,lengthlist,quantvals,opb,maptype)){
526 s->q_val=0; /* cleanup must not free alloca memory */
527 goto _errout;
528 }
529
530 s->q_val=0; /* about to go out of scope; _make_decode_table
531 was using it */
532
533 }else{
534 /* use dec_type 2: packed vector of column offsets */
535
536 /* need quantized values before */
537 if(s->q_bits<=8){
538 s->q_val=_ogg_malloc(quantvals);
539 if (!s->q_val) goto _eofout;
540 for(i=0;i<quantvals;i++)
541 ((unsigned char *)s->q_val)[i]=(unsigned char)oggpack_read(opb,s->q_bits);
542 }else{
543 s->q_val=_ogg_malloc(quantvals*2);
544 if (!s->q_val) goto _eofout;
545 for(i=0;i<quantvals;i++)
546 ((ogg_uint16_t *)s->q_val)[i]=(ogg_uint16_t)oggpack_read(opb,s->q_bits);
547 }
548
549 if(oggpack_eop(opb))goto _eofout;
550
551 s->q_pack=_ilog(quantvals-1);
552 s->dec_type=2;
553 s->dec_nodeb=_determine_node_bytes(s->used_entries,
554 (_ilog(quantvals-1)*s->dim+8)/8);
555 s->dec_leafw=_determine_leaf_words(s->dec_nodeb,
556 (_ilog(quantvals-1)*s->dim+8)/8);
557 if(_make_decode_table(s,lengthlist,quantvals,opb,maptype))goto _errout;
558
559 }
560 }
561 break;
562 case 2:
563
564 /* mapping type 2; explicit array of values */
565 quantvals=s->entries*s->dim;
566 /* dec_type choices here are 1,3; 2 is not possible */
567
568 if( (s->q_bits*s->dim+8)/8 <=4){ /* remember flag bit */
569 /* use dec_type 1: vector of packed values */
570
571 s->dec_type=1;
572 s->dec_nodeb=_determine_node_bytes(s->used_entries,(s->q_bits*s->dim+8)/8);
573 s->dec_leafw=_determine_leaf_words(s->dec_nodeb,(s->q_bits*s->dim+8)/8);
574 if(_make_decode_table(s,lengthlist,quantvals,opb,maptype))goto _errout;
575
576 }else{
577 /* use dec_type 3: scalar offset into packed value array */
578
579 s->dec_type=3;
580 s->dec_nodeb=_determine_node_bytes(s->used_entries,_ilog(s->used_entries-1)/8+1);
581 s->dec_leafw=_determine_leaf_words(s->dec_nodeb,_ilog(s->used_entries-1)/8+1);
582 if(_make_decode_table(s,lengthlist,quantvals,opb,maptype))goto _errout;
583
584 /* get the vals & pack them */
585 s->q_pack=(s->q_bits+7)/8*s->dim;
586 s->q_val=_ogg_malloc(s->q_pack*s->used_entries);
587
588 if(s->q_bits<=8){
589 for(i=0;i<s->used_entries*s->dim;i++)
590 ((unsigned char *)(s->q_val))[i]=(unsigned char)oggpack_read(opb,s->q_bits);
591 }else{
592 for(i=0;i<s->used_entries*s->dim;i++)
593 ((ogg_uint16_t *)(s->q_val))[i]=(ogg_uint16_t)oggpack_read(opb,s->q_bits);
594 }
595 }
596 break;
597 default:
598 goto _errout;
599 }
600
601 if (s->dec_nodeb==1)
602 if (s->dec_leafw == 1)
603 s->dec_method = 0;
604 else
605 s->dec_method = 1;
606 else if (s->dec_nodeb==2)
607 if (s->dec_leafw == 1)
608 s->dec_method = 2;
609 else
610 s->dec_method = 3;
611 else
612 s->dec_method = 4;
613
614 if(oggpack_eop(opb))goto _eofout;
615
616 free(lengthlist);
617 return 0;
618 _errout:
619 _eofout:
620 vorbis_book_clear(s);
621 free(lengthlist);
622 return -1;
623 }
624
625 #ifndef ONLY_C
626 ogg_uint32_t decode_packed_entry_number(codebook *book,
627 oggpack_buffer *b);
628 #else
decode_packed_entry_number(codebook * book,oggpack_buffer * b)629 static inline ogg_uint32_t decode_packed_entry_number(codebook *book,
630 oggpack_buffer *b){
631 ogg_uint32_t chase=0;
632 int read=book->dec_maxlength;
633 long lok = oggpack_look(b,read),i;
634
635 while(lok<0 && read>1)
636 lok = oggpack_look(b, --read);
637
638 if(lok<0){
639 oggpack_adv(b,1); /* force eop */
640 return -1;
641 }
642
643 /* chase the tree with the bits we got */
644 switch (book->dec_method)
645 {
646 case 0:
647 {
648 /* book->dec_nodeb==1, book->dec_leafw==1 */
649 /* 8/8 - Used */
650 unsigned char *t=(unsigned char *)book->dec_table;
651
652 for(i=0;i<read;i++){
653 chase=t[chase*2+((lok>>i)&1)];
654 if(chase&0x80UL)break;
655 }
656 chase&=0x7fUL;
657 break;
658 }
659 case 1:
660 {
661 /* book->dec_nodeb==1, book->dec_leafw!=1 */
662 /* 8/16 - Used by infile2 */
663 unsigned char *t=(unsigned char *)book->dec_table;
664 for(i=0;i<read;i++){
665 int bit=(lok>>i)&1;
666 int next=t[chase+bit];
667 if(next&0x80){
668 chase= (next<<8) | t[chase+bit+1+(!bit || t[chase]&0x80)];
669 break;
670 }
671 chase=next;
672 }
673 //chase&=0x7fffUL;
674 chase&=~0x8000UL;
675 break;
676 }
677 case 2:
678 {
679 /* book->dec_nodeb==2, book->dec_leafw==1 */
680 /* 16/16 - Used */
681 for(i=0;i<read;i++){
682 chase=((ogg_uint16_t *)(book->dec_table))[chase*2+((lok>>i)&1)];
683 if(chase&0x8000UL)break;
684 }
685 //chase&=0x7fffUL;
686 chase&=~0x8000UL;
687 break;
688 }
689 case 3:
690 {
691 /* book->dec_nodeb==2, book->dec_leafw!=1 */
692 /* 16/32 - Used by infile2 */
693 ogg_uint16_t *t=(ogg_uint16_t *)book->dec_table;
694 for(i=0;i<read;i++){
695 int bit=(lok>>i)&1;
696 int next=t[chase+bit];
697 if(next&0x8000){
698 chase= (next<<16) | t[chase+bit+1+(!bit || t[chase]&0x8000)];
699 break;
700 }
701 chase=next;
702 }
703 //chase&=0x7fffffffUL;
704 chase&=~0x80000000UL;
705 break;
706 }
707 case 4:
708 {
709 //Output("32/32");
710 for(i=0;i<read;i++){
711 chase=((ogg_uint32_t *)(book->dec_table))[chase*2+((lok>>i)&1)];
712 if(chase&0x80000000UL)break;
713 }
714 //chase&=0x7fffffffUL;
715 chase&=~0x80000000UL;
716 break;
717 }
718 }
719
720 if(i<read){
721 oggpack_adv(b,i+1);
722 return chase;
723 }
724 oggpack_adv(b,read+1);
725 return(-1);
726 }
727 #endif
728
729 /* returns the [original, not compacted] entry number or -1 on eof *********/
vorbis_book_decode(codebook * book,oggpack_buffer * b)730 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
731 if(book->dec_type)return -1;
732 return decode_packed_entry_number(book,b);
733 }
734
735 #ifndef ONLY_C
736 int decode_map(codebook *s, oggpack_buffer *b, ogg_int32_t *v, int point);
737 #else
decode_map(codebook * s,oggpack_buffer * b,ogg_int32_t * v,int point)738 static int decode_map(codebook *s, oggpack_buffer *b, ogg_int32_t *v, int point){
739 ogg_uint32_t entry = decode_packed_entry_number(s,b);
740 int i;
741 if(oggpack_eop(b))return(-1);
742
743 /* 1 used by test file 0 */
744
745 /* according to decode type */
746 switch(s->dec_type){
747 case 1:{
748 /* packed vector of values */
749 int mask=(1<<s->q_bits)-1;
750 for(i=0;i<s->dim;i++){
751 v[i]=entry&mask;
752 entry>>=s->q_bits;
753 }
754 break;
755 }
756 case 2:{
757 /* packed vector of column offsets */
758 int mask=(1<<s->q_pack)-1;
759 for(i=0;i<s->dim;i++){
760 if(s->q_bits<=8)
761 v[i]=((unsigned char *)(s->q_val))[entry&mask];
762 else
763 v[i]=((ogg_uint16_t *)(s->q_val))[entry&mask];
764 entry>>=s->q_pack;
765 }
766 break;
767 }
768 case 3:{
769 /* offset into array */
770 void *ptr=s->q_val+entry*s->q_pack;
771
772 if(s->q_bits<=8){
773 for(i=0;i<s->dim;i++)
774 v[i]=((unsigned char *)ptr)[i];
775 }else{
776 for(i=0;i<s->dim;i++)
777 v[i]=((ogg_uint16_t *)ptr)[i];
778 }
779 break;
780 }
781 default:
782 return -1;
783 }
784
785 /* we have the unpacked multiplicands; compute final vals */
786 {
787 int shiftM = point-s->q_delp;
788 ogg_int32_t add = point-s->q_minp;
789 int mul = s->q_del;
790
791 if(add>0)
792 add= s->q_min >> add;
793 else
794 add= s->q_min << -add;
795 if (shiftM<0)
796 {
797 mul <<= -shiftM;
798 shiftM = 0;
799 }
800 add <<= shiftM;
801
802 for(i=0;i<s->dim;i++)
803 v[i]= ((add + v[i] * mul) >> shiftM);
804
805 if(s->q_seq)
806 for(i=1;i<s->dim;i++)
807 v[i]+=v[i-1];
808 }
809
810 return 0;
811 }
812 #endif
813
814 /* 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)815 long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a,
816 oggpack_buffer *b,int n,int point){
817 if(book->used_entries>0){
818 int step=n/book->dim;
819 ogg_int32_t *v = book->dec_buf;//(ogg_int32_t *)alloca(sizeof(*v)*book->dim);
820 int i,j,o;
821 if (!v) return -1;
822
823 for (j=0;j<step;j++){
824 if(decode_map(book,b,v,point))return -1;
825 for(i=0,o=j;i<book->dim;i++,o+=step)
826 a[o]+=v[i];
827 }
828 }
829 return 0;
830 }
831
vorbis_book_decodev_add(codebook * book,ogg_int32_t * a,oggpack_buffer * b,int n,int point)832 long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a,
833 oggpack_buffer *b,int n,int point){
834 if(book->used_entries>0){
835 ogg_int32_t *v = book->dec_buf;//(ogg_int32_t *)alloca(sizeof(*v)*book->dim);
836 int i,j;
837
838 if (!v) return -1;
839 for(i=0;i<n;){
840 if(decode_map(book,b,v,point))return -1;
841 for (j=0;j<book->dim;j++)
842 a[i++]+=v[j];
843 }
844 }
845 return 0;
846 }
847
vorbis_book_decodev_set(codebook * book,ogg_int32_t * a,oggpack_buffer * b,int n,int point)848 long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a,
849 oggpack_buffer *b,int n,int point){
850 if(book->used_entries>0){
851 ogg_int32_t *v = book->dec_buf;//(ogg_int32_t *)alloca(sizeof(*v)*book->dim);
852 int i,j;
853
854 if (!v) return -1;
855 for(i=0;i<n;){
856 if(decode_map(book,b,v,point))return -1;
857 for (j=0;j<book->dim;j++)
858 a[i++]=v[j];
859 }
860 }else{
861 int i,j;
862
863 for(i=0;i<n;){
864 for (j=0;j<book->dim;j++)
865 a[i++]=0;
866 }
867 }
868
869 return 0;
870 }
871
872 #ifndef ONLY_C
873 long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,
874 long offset,int ch,
875 oggpack_buffer *b,int n,int point);
876 #else
vorbis_book_decodevv_add(codebook * book,ogg_int32_t ** a,long offset,int ch,oggpack_buffer * b,int n,int point)877 long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,
878 long offset,int ch,
879 oggpack_buffer *b,int n,int point){
880 if(book->used_entries>0){
881
882 ogg_int32_t *v = book->dec_buf;//(ogg_int32_t *)alloca(sizeof(*v)*book->dim);
883 long i,j;
884 int chptr=0;
885
886 if (!v) return -1;
887 for(i=offset;i<offset+n;){
888 if(decode_map(book,b,v,point))return -1;
889 for (j=0;j<book->dim;j++){
890 a[chptr++][i]+=v[j];
891 if(chptr==ch){
892 chptr=0;
893 i++;
894 }
895 }
896 }
897 }
898
899 return 0;
900 }
901 #endif
902