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