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