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