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