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