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 ******************************************/ 50int _ilog(unsigned int v){ 51 int ret=0; 52 while(v){ 53 ret++; 54 v>>=1; 55 } 56 return(ret); 57} 58 59static 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 102static 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 */ 122static 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) */ 137static 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 */ 144static 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 216static 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 */ 345long _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 370void 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 380int 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 *)alloca(sizeof(*lengthlist)*s->entries); 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 *)alloca(sizeof(*lengthlist)*s->entries); 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 return 0; 612 _errout: 613 _eofout: 614 vorbis_book_clear(s); 615 return -1; 616} 617 618#ifndef ONLY_C 619ogg_uint32_t decode_packed_entry_number(codebook *book, 620 oggpack_buffer *b); 621#else 622static inline ogg_uint32_t decode_packed_entry_number(codebook *book, 623 oggpack_buffer *b){ 624 ogg_uint32_t chase=0; 625 int read=book->dec_maxlength; 626 long lok = oggpack_look(b,read),i; 627 628 while(lok<0 && read>1) 629 lok = oggpack_look(b, --read); 630 631 if(lok<0){ 632 oggpack_adv(b,1); /* force eop */ 633 return -1; 634 } 635 636 /* chase the tree with the bits we got */ 637 switch (book->dec_method) 638 { 639 case 0: 640 { 641 /* book->dec_nodeb==1, book->dec_leafw==1 */ 642 /* 8/8 - Used */ 643 unsigned char *t=(unsigned char *)book->dec_table; 644 645 for(i=0;i<read;i++){ 646 chase=t[chase*2+((lok>>i)&1)]; 647 if(chase&0x80UL)break; 648 } 649 chase&=0x7fUL; 650 break; 651 } 652 case 1: 653 { 654 /* book->dec_nodeb==1, book->dec_leafw!=1 */ 655 /* 8/16 - Used by infile2 */ 656 unsigned char *t=(unsigned char *)book->dec_table; 657 for(i=0;i<read;i++){ 658 int bit=(lok>>i)&1; 659 int next=t[chase+bit]; 660 if(next&0x80){ 661 chase= (next<<8) | t[chase+bit+1+(!bit || t[chase]&0x80)]; 662 break; 663 } 664 chase=next; 665 } 666 //chase&=0x7fffUL; 667 chase&=~0x8000UL; 668 break; 669 } 670 case 2: 671 { 672 /* book->dec_nodeb==2, book->dec_leafw==1 */ 673 /* 16/16 - Used */ 674 for(i=0;i<read;i++){ 675 chase=((ogg_uint16_t *)(book->dec_table))[chase*2+((lok>>i)&1)]; 676 if(chase&0x8000UL)break; 677 } 678 //chase&=0x7fffUL; 679 chase&=~0x8000UL; 680 break; 681 } 682 case 3: 683 { 684 /* book->dec_nodeb==2, book->dec_leafw!=1 */ 685 /* 16/32 - Used by infile2 */ 686 ogg_uint16_t *t=(ogg_uint16_t *)book->dec_table; 687 for(i=0;i<read;i++){ 688 int bit=(lok>>i)&1; 689 int next=t[chase+bit]; 690 if(next&0x8000){ 691 chase= (next<<16) | t[chase+bit+1+(!bit || t[chase]&0x8000)]; 692 break; 693 } 694 chase=next; 695 } 696 //chase&=0x7fffffffUL; 697 chase&=~0x80000000UL; 698 break; 699 } 700 case 4: 701 { 702 //Output("32/32"); 703 for(i=0;i<read;i++){ 704 chase=((ogg_uint32_t *)(book->dec_table))[chase*2+((lok>>i)&1)]; 705 if(chase&0x80000000UL)break; 706 } 707 //chase&=0x7fffffffUL; 708 chase&=~0x80000000UL; 709 break; 710 } 711 } 712 713 if(i<read){ 714 oggpack_adv(b,i+1); 715 return chase; 716 } 717 oggpack_adv(b,read+1); 718 return(-1); 719} 720#endif 721 722/* returns the [original, not compacted] entry number or -1 on eof *********/ 723long vorbis_book_decode(codebook *book, oggpack_buffer *b){ 724 if(book->dec_type)return -1; 725 return decode_packed_entry_number(book,b); 726} 727 728#ifndef ONLY_C 729int decode_map(codebook *s, oggpack_buffer *b, ogg_int32_t *v, int point); 730#else 731static int decode_map(codebook *s, oggpack_buffer *b, ogg_int32_t *v, int point){ 732 ogg_uint32_t entry = decode_packed_entry_number(s,b); 733 int i; 734 if(oggpack_eop(b))return(-1); 735 736 /* 1 used by test file 0 */ 737 738 /* according to decode type */ 739 switch(s->dec_type){ 740 case 1:{ 741 /* packed vector of values */ 742 int mask=(1<<s->q_bits)-1; 743 for(i=0;i<s->dim;i++){ 744 v[i]=entry&mask; 745 entry>>=s->q_bits; 746 } 747 break; 748 } 749 case 2:{ 750 /* packed vector of column offsets */ 751 int mask=(1<<s->q_pack)-1; 752 for(i=0;i<s->dim;i++){ 753 if(s->q_bits<=8) 754 v[i]=((unsigned char *)(s->q_val))[entry&mask]; 755 else 756 v[i]=((ogg_uint16_t *)(s->q_val))[entry&mask]; 757 entry>>=s->q_pack; 758 } 759 break; 760 } 761 case 3:{ 762 /* offset into array */ 763 void *ptr=s->q_val+entry*s->q_pack; 764 765 if(s->q_bits<=8){ 766 for(i=0;i<s->dim;i++) 767 v[i]=((unsigned char *)ptr)[i]; 768 }else{ 769 for(i=0;i<s->dim;i++) 770 v[i]=((ogg_uint16_t *)ptr)[i]; 771 } 772 break; 773 } 774 default: 775 return -1; 776 } 777 778 /* we have the unpacked multiplicands; compute final vals */ 779 { 780 int shiftM = point-s->q_delp; 781 ogg_int32_t add = point-s->q_minp; 782 int mul = s->q_del; 783 784 if(add>0) 785 add= s->q_min >> add; 786 else 787 add= s->q_min << -add; 788 if (shiftM<0) 789 { 790 mul <<= -shiftM; 791 shiftM = 0; 792 } 793 add <<= shiftM; 794 795 for(i=0;i<s->dim;i++) 796 v[i]= ((add + v[i] * mul) >> shiftM); 797 798 if(s->q_seq) 799 for(i=1;i<s->dim;i++) 800 v[i]+=v[i-1]; 801 } 802 803 return 0; 804} 805#endif 806 807/* returns 0 on OK or -1 on eof *************************************/ 808long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a, 809 oggpack_buffer *b,int n,int point){ 810 if(book->used_entries>0){ 811 int step=n/book->dim; 812 ogg_int32_t *v = book->dec_buf;//(ogg_int32_t *)alloca(sizeof(*v)*book->dim); 813 int i,j,o; 814 if (!v) return -1; 815 816 for (j=0;j<step;j++){ 817 if(decode_map(book,b,v,point))return -1; 818 for(i=0,o=j;i<book->dim;i++,o+=step) 819 a[o]+=v[i]; 820 } 821 } 822 return 0; 823} 824 825long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a, 826 oggpack_buffer *b,int n,int point){ 827 if(book->used_entries>0){ 828 ogg_int32_t *v = book->dec_buf;//(ogg_int32_t *)alloca(sizeof(*v)*book->dim); 829 int i,j; 830 831 if (!v) return -1; 832 for(i=0;i<n;){ 833 if(decode_map(book,b,v,point))return -1; 834 for (j=0;j<book->dim;j++) 835 a[i++]+=v[j]; 836 } 837 } 838 return 0; 839} 840 841long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a, 842 oggpack_buffer *b,int n,int point){ 843 if(book->used_entries>0){ 844 ogg_int32_t *v = book->dec_buf;//(ogg_int32_t *)alloca(sizeof(*v)*book->dim); 845 int i,j; 846 847 if (!v) return -1; 848 for(i=0;i<n;){ 849 if(decode_map(book,b,v,point))return -1; 850 for (j=0;j<book->dim;j++) 851 a[i++]=v[j]; 852 } 853 }else{ 854 int i,j; 855 856 for(i=0;i<n;){ 857 for (j=0;j<book->dim;j++) 858 a[i++]=0; 859 } 860 } 861 862 return 0; 863} 864 865#ifndef ONLY_C 866long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a, 867 long offset,int ch, 868 oggpack_buffer *b,int n,int point); 869#else 870long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a, 871 long offset,int ch, 872 oggpack_buffer *b,int n,int point){ 873 if(book->used_entries>0){ 874 875 ogg_int32_t *v = book->dec_buf;//(ogg_int32_t *)alloca(sizeof(*v)*book->dim); 876 long i,j; 877 int chptr=0; 878 879 if (!v) return -1; 880 for(i=offset;i<offset+n;){ 881 if(decode_map(book,b,v,point))return -1; 882 for (j=0;j<book->dim;j++){ 883 a[chptr++][i]+=v[j]; 884 if(chptr==ch){ 885 chptr=0; 886 i++; 887 } 888 } 889 } 890 } 891 892 return 0; 893} 894#endif 895