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 ******************************************/ 52 int _ilog(unsigned int v){ 53 int ret=0; 54 while(v){ 55 ret++; 56 v>>=1; 57 } 58 return(ret); 59 } 60 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 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 */ 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) */ 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 */ 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 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 */ 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 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 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 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 *********/ 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 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 *************************************/ 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 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 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 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
