1 /* ------------------------------------------------------------------ 2 * Copyright (C) 1998-2009 PacketVideo 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 13 * express or implied. 14 * See the License for the specific language governing permissions 15 * and limitations under the License. 16 * ------------------------------------------------------------------- 17 */ 18 /* 19 20 Pathname: ./src/decode_huff_cw_binary.c 21 Funtions: 22 decode_huff_cw_tab1 23 decode_huff_cw_tab2 24 decode_huff_cw_tab3 25 decode_huff_cw_tab4 26 decode_huff_cw_tab5 27 decode_huff_cw_tab6 28 decode_huff_cw_tab7 29 decode_huff_cw_tab8 30 decode_huff_cw_tab9 31 decode_huff_cw_tab10 32 decode_huff_cw_tab11 33 decode_huff_cw_scl 34 35 36 ------------------------------------------------------------------------------ 37 REVISION HISTORY 38 39 Description: Updated per review comments 40 (1) make cw sgined and change "if(cw&0x80000000)" to if(cw<0) 41 (2) 42 43 Description: Create specific functions for different huffman tables. 44 45 46 Description: Added ( Int16) castings to eliminate several compiler warnings 47 48 49 Description: Modified huffman tables to allocate int32 variables instead of 50 int16, which lead to data missaligned for some compiler. 51 Eliminated casting and unused variables 52 53 54 Who: Date: 55 Description: 56 57 ------------------------------------------------------------------------------ 58 INPUT AND OUTPUT DEFINITIONS 59 60 Inputs: 61 BITS *pInputStream = pointer to input bit stream 62 63 Local Stores/Buffers/Pointers Needed: 64 65 66 Global Stores/Buffers/Pointers Needed: 67 68 69 Outputs: 70 idx = bit field extracted from a leaf entry of packed Huffman Tables 71 72 Pointers and Buffers Modified: 73 74 Local Stores Modified: 75 76 Global Stores Modified: 77 78 79 ------------------------------------------------------------------------------ 80 FUNCTION DESCRIPTION 81 82 These functions are used to decode huffman codewords from the input 83 bitstream using combined binary search and look-up table approach. 84 85 First the codewords are grouped and the input symbol is determined 86 which group it belongs. Then within that group, a look-up table is 87 used to determine which codeword the symbol is. 88 The table is created by ordering the codeword in the table according to their 89 normalized shifted binary value, i.e., all the codewords are left 90 shifted to meet the maximum codelength. Example, max codelength is 91 10, the codeword with lenth 3 will left shift by 7. 92 The binary values of after the shift are sorted. 93 Then the sorted table is divided into several partition. 94 At the VLC decoding period, input is read in at max codelenght. 95 The partition is decided using if-else logic. 96 Inside each partition, a look-up table is used to map the input value 97 to a correct symbol. Table entries can appear to be repeated according 98 to the humming distance between adjacent codewords. 99 100 ------------------------------------------------------------------------------ 101 REQUIREMENTS 102 103 104 ------------------------------------------------------------------------------ 105 REFERENCES 106 107 (1) MPEG-2 NBC Audio Decoder 108 "This software module was originally developed by AT&T, Dolby 109 Laboratories, Fraunhofer Gesellschaft IIS in the course of development 110 of the MPEG-2 NBC/MPEG-4 Audio standard ISO/IEC 13818-7, 14496-1,2 and 111 3. This software module is an implementation of a part of one or more 112 MPEG-2 NBC/MPEG-4 Audio tools as specified by the MPEG-2 NBC/MPEG-4 113 Audio standard. ISO/IEC gives users of the MPEG-2 NBC/MPEG-4 Audio 114 standards free license to this software module or modifications thereof 115 for use in hardware or software products claiming conformance to the 116 MPEG-2 NBC/MPEG-4 Audio standards. Those intending to use this software 117 module in hardware or software products are advised that this use may 118 infringe existing patents. The original developer of this software 119 module and his/her company, the subsequent editors and their companies, 120 and ISO/IEC have no liability for use of this software module or 121 modifications thereof in an implementation. Copyright is not released 122 for non MPEG-2 NBC/MPEG-4 Audio conforming products.The original 123 developer retains full right to use the code for his/her own purpose, 124 assign or donate the code to a third party and to inhibit third party 125 from using the code for non MPEG-2 NBC/MPEG-4 Audio conforming products. 126 This copyright notice must be included in all copies or derivative 127 works." 128 Copyright(c)1996. 129 130 (2) Introduction to Algorithms, 131 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. 132 The MIT press, 1990 133 134 (3) "Selecting an Optimal Huffman Decoder for AAC", 135 Vladimir Z. Mesarovic, et al. 136 AES 111th Convention, September 21-24, 2001, New York, USA 137 138 ------------------------------------------------------------------------------ 139 PSEUDO-CODE 140 141 142 ------------------------------------------------------------------------------ 143 RESOURCES USED 144 When the code is written for a specific target processor the 145 the resources used should be documented below. 146 147 STACK USAGE: 148 149 DATA MEMORY USED: x words 150 151 PROGRAM MEMORY USED: x words 152 153 CLOCK CYCLES: 154 155 156 ------------------------------------------------------------------------------ 157 */ 158 159 160 /*---------------------------------------------------------------------------- 161 ; INCLUDES 162 ----------------------------------------------------------------------------*/ 163 #include "pv_audio_type_defs.h" 164 #include "huffman.h" 165 166 167 /*---------------------------------------------------------------------------- 168 ; MACROS 169 ; Define module specific macros here 170 ----------------------------------------------------------------------------*/ 171 172 173 /*---------------------------------------------------------------------------- 174 ; DEFINES 175 ; Include all pre-processor statements here. Include conditional 176 ; compile variables also. 177 ----------------------------------------------------------------------------*/ 178 #define MAX_CW_LEN (19) 179 #define MASK_IDX (0x1FF) 180 #define MASK_RIGHT (0xFE00) 181 182 #define UPPER16 (16) 183 #define MASK_LOW16 (0xFFFF) 184 /*---------------------------------------------------------------------------- 185 ; LOCAL FUNCTION DEFINITIONS 186 ; Function Prototype declaration 187 ----------------------------------------------------------------------------*/ 188 189 190 /*---------------------------------------------------------------------------- 191 ; LOCAL STORE/BUFFER/POINTER DEFINITIONS 192 ; Variable declaration - defined here and used outside this module 193 ----------------------------------------------------------------------------*/ 194 195 196 /*---------------------------------------------------------------------------- 197 ; EXTERNAL FUNCTION REFERENCES 198 ; Declare functions defined elsewhere and referenced in this module 199 ----------------------------------------------------------------------------*/ 200 201 202 /*---------------------------------------------------------------------------- 203 ; EXTERNAL GLOBAL STORE/BUFFER/POINTER REFERENCES 204 ; Declare variables used in this module but defined elsewhere 205 ----------------------------------------------------------------------------*/ 206 207 /*---------------------------------------------------------------------------- 208 ; FUNCTION CODE 209 ----------------------------------------------------------------------------*/ 210 211 Int decode_huff_cw_tab1( 212 BITS *pInputStream) 213 { 214 Int32 tab; 215 Int32 cw; 216 217 cw = get17_n_lessbits( 218 11, 219 pInputStream); 220 if ((cw >> 10) == 0) 221 { 222 pInputStream->usedBits -= (11 - 1); 223 return 40; /* idx is 40 */ 224 } 225 else if ((cw >> 6) <= 23) 226 { 227 tab = (cw >> 6) - 16; 228 } 229 else if ((cw >> 4) <= 119) 230 { 231 tab = (cw >> 4) - 96 + 8; 232 } 233 else if ((cw >> 2) <= 503) 234 { 235 tab = (cw >> 2) - 480 + 32; 236 } 237 else 238 { 239 tab = cw - 2016 + 56; 240 } 241 242 tab = *(huff_tab1 + tab); 243 244 pInputStream->usedBits -= (11 - (tab & MASK_LOW16)); 245 return ((Int)(tab >> UPPER16)); 246 } 247 248 249 Int decode_huff_cw_tab2( 250 BITS *pInputStream) 251 { 252 Int32 tab; 253 Int32 cw; 254 255 cw = get9_n_lessbits( 256 9, 257 pInputStream); 258 if ((cw >> 6) == 0) 259 { 260 pInputStream->usedBits -= (9 - 3); /* used 3 bits */ 261 return 40; /* idx is 40 */ 262 } 263 else if ((cw >> 3) <= 49) 264 { 265 tab = (cw >> 3) - 8; 266 } 267 else if ((cw >> 2) <= 114) 268 { 269 tab = (cw >> 2) - 100 + 42; 270 } 271 else if ((cw >> 1) <= 248) 272 { 273 tab = (cw >> 1) - 230 + 57; 274 } 275 else 276 { 277 tab = cw - 498 + 76; 278 } 279 280 tab = *(huff_tab2 + tab); 281 282 pInputStream->usedBits -= (9 - (tab & MASK_LOW16)); 283 return ((Int)(tab >> UPPER16)); 284 } 285 286 287 Int decode_huff_cw_tab3( 288 BITS *pInputStream) 289 { 290 Int32 tab; 291 Int32 cw; 292 293 cw = get17_n_lessbits( 294 16, 295 pInputStream); 296 if ((cw >> 15) == 0) 297 { 298 pInputStream->usedBits -= (16 - 1); /* used 1 bits */ 299 return 0; /* idx is 0 */ 300 } 301 else if ((cw >> 10) <= 57) 302 { 303 tab = (cw >> 10) - 32; 304 } 305 else if ((cw >> 7) <= 500) 306 { 307 tab = (cw >> 7) - 464 + 26; 308 } 309 else if ((cw >> 6) <= 1016) 310 { 311 tab = (cw >> 6) - 1002 + 63; 312 } 313 else if ((cw >> 4) <= 4092) 314 { 315 tab = (cw >> 4) - 4068 + 78; 316 } 317 else 318 { 319 tab = cw - 65488 + 103; 320 } 321 322 tab = *(huff_tab3 + tab); 323 324 pInputStream->usedBits -= (16 - (tab & MASK_LOW16)); 325 return ((Int)(tab >> UPPER16)); 326 } 327 328 329 Int decode_huff_cw_tab4( 330 BITS *pInputStream) 331 { 332 Int32 tab; 333 Int32 cw; 334 335 cw = get17_n_lessbits( 336 12, 337 pInputStream); 338 339 if ((cw >> 7) <= 25) 340 { 341 tab = (cw >> 7); 342 } 343 else if ((cw >> 4) <= 246) 344 { 345 tab = (cw >> 4) - 208 + 26; 346 } 347 else if ((cw >> 2) <= 1017) 348 { 349 tab = (cw >> 2) - 988 + 65; 350 } 351 else 352 { 353 tab = cw - 4072 + 95; 354 } 355 356 tab = *(huff_tab4 + tab); 357 358 pInputStream->usedBits -= (12 - (tab & MASK_LOW16)); 359 return ((Int)(tab >> UPPER16)); 360 } 361 362 363 364 Int decode_huff_cw_tab5( 365 BITS *pInputStream) 366 { 367 Int32 tab; 368 Int32 cw; 369 370 cw = get17_n_lessbits( 371 13, 372 pInputStream); 373 374 if ((cw >> 12) == 0) 375 { 376 pInputStream->usedBits -= (13 - 1); /* used 1 bits */ 377 return 40; /* idx is 40 */ 378 } 379 else if ((cw >> 8) <= 27) 380 { 381 tab = (cw >> 8) - 16; 382 } 383 else if ((cw >> 5) <= 243) 384 { 385 tab = (cw >> 5) - 224 + 12; 386 } 387 else if ((cw >> 3) <= 1011) 388 { 389 tab = (cw >> 3) - 976 + 32; 390 } 391 else if ((cw >> 2) <= 2041) 392 { 393 tab = (cw >> 2) - 2024 + 68; 394 } 395 else 396 { 397 tab = cw - 8168 + 86; 398 } 399 400 tab = *(huff_tab5 + tab); 401 402 pInputStream->usedBits -= (13 - (tab & MASK_LOW16)); 403 return ((Int)(tab >> UPPER16)); 404 } 405 406 407 408 Int decode_huff_cw_tab6( 409 BITS *pInputStream) 410 { 411 Int32 tab; 412 Int32 cw; 413 414 cw = get17_n_lessbits( 415 11, 416 pInputStream); 417 418 if ((cw >> 7) <= 8) 419 { 420 tab = (cw >> 7); 421 } 422 else if ((cw >> 4) <= 116) 423 { 424 tab = (cw >> 4) - 72 + 9; 425 } 426 else if ((cw >> 2) <= 506) 427 { 428 tab = (cw >> 2) - 468 + 54; 429 } 430 else 431 { 432 tab = cw - 2028 + 93; 433 } 434 435 tab = *(huff_tab6 + tab); 436 437 pInputStream->usedBits -= (11 - (tab & MASK_LOW16)); 438 return ((Int)(tab >> UPPER16)); 439 } 440 441 442 443 Int decode_huff_cw_tab7( 444 BITS *pInputStream) 445 { 446 Int32 tab; 447 Int32 cw; 448 449 cw = get17_n_lessbits( 450 12, 451 pInputStream); 452 453 if ((cw >> 11) == 0) 454 { 455 pInputStream->usedBits -= (12 - 1); /* used 1 bits */ 456 return 0; /* idx is 0 */ 457 } 458 else if ((cw >> 6) <= 55) 459 { 460 tab = (cw >> 6) - 32; 461 } 462 else if ((cw >> 4) <= 243) 463 { 464 tab = (cw >> 4) - 224 + 24; 465 } 466 else if ((cw >> 2) <= 1018) 467 { 468 tab = (cw >> 2) - 976 + 44; 469 } 470 else 471 { 472 tab = cw - 4076 + 87; 473 } 474 475 tab = *(huff_tab7 + tab); 476 477 pInputStream->usedBits -= (12 - (tab & MASK_LOW16)); 478 return ((Int)(tab >> UPPER16)); 479 } 480 481 482 483 Int decode_huff_cw_tab8( 484 BITS *pInputStream) 485 { 486 Int32 tab; 487 Int32 cw; 488 489 cw = get17_n_lessbits( 490 10, 491 pInputStream); 492 493 if ((cw >> 5) <= 20) 494 { 495 tab = (cw >> 5); 496 } 497 else if ((cw >> 3) <= 117) 498 { 499 tab = (cw >> 3) - 84 + 21; 500 } 501 else if ((cw >> 2) <= 250) 502 { 503 tab = (cw >> 2) - 236 + 55; 504 } 505 else 506 { 507 tab = cw - 1004 + 70; 508 } 509 510 tab = *(huff_tab8 + tab); 511 512 pInputStream->usedBits -= (10 - (tab & MASK_LOW16)); 513 return ((Int)(tab >> UPPER16)); 514 } 515 516 517 Int decode_huff_cw_tab9( 518 BITS *pInputStream) 519 { 520 Int32 tab; 521 Int32 cw; 522 523 cw = get17_n_lessbits( 524 15, 525 pInputStream); 526 527 if ((cw >> 11) <= 12) 528 { 529 tab = (cw >> 11); 530 } 531 else if ((cw >> 8) <= 114) 532 { 533 tab = (cw >> 8) - 104 + 13; 534 } 535 else if ((cw >> 6) <= 486) 536 { 537 tab = (cw >> 6) - 460 + 24; 538 } 539 else if ((cw >> 5) <= 993) 540 { 541 tab = (cw >> 5) - 974 + 51; 542 } 543 else if ((cw >> 4) <= 2018) 544 { 545 tab = (cw >> 4) - 1988 + 71; 546 } 547 else if ((cw >> 3) <= 4075) 548 { 549 tab = (cw >> 3) - 4038 + 102; 550 } 551 else if ((cw >> 2) <= 8183) 552 { 553 tab = (cw >> 2) - 8152 + 140; 554 } 555 else 556 { 557 tab = cw - 32736 + 172; 558 } 559 560 tab = *(huff_tab9 + tab); 561 562 pInputStream->usedBits -= (15 - (tab & MASK_LOW16)); 563 return ((Int)(tab >> UPPER16)); 564 } 565 566 567 Int decode_huff_cw_tab10( 568 BITS *pInputStream) 569 { 570 Int32 tab; 571 Int32 cw; 572 573 cw = get17_n_lessbits( 574 12, 575 pInputStream); 576 577 if ((cw >> 6) <= 41) 578 { 579 tab = (cw >> 6); 580 } 581 else if ((cw >> 5) <= 100) 582 { 583 tab = (cw >> 5) - 84 + 42; 584 } 585 else if ((cw >> 4) <= 226) 586 { 587 tab = (cw >> 4) - 202 + 59; 588 } 589 else if ((cw >> 3) <= 484) 590 { 591 tab = (cw >> 3) - 454 + 84; 592 } 593 else if ((cw >> 2) <= 1010) 594 { 595 tab = (cw >> 2) - 970 + 115; 596 } 597 else if ((cw >> 1) <= 2043) 598 { 599 tab = (cw >> 1) - 2022 + 156; 600 } 601 else 602 { 603 tab = cw - 4088 + 178; 604 } 605 606 tab = *(huff_tab10 + tab); 607 608 pInputStream->usedBits -= (12 - (tab & MASK_LOW16)); 609 return ((Int)(tab >> UPPER16)); 610 } 611 612 613 Int decode_huff_cw_tab11( 614 BITS *pInputStream) 615 { 616 Int32 tab; 617 Int32 cw; 618 619 cw = get17_n_lessbits( 620 12, 621 pInputStream); 622 623 if ((cw >> 6) <= 26) 624 { 625 tab = (cw >> 6); 626 } 627 else if ((cw >> 5) <= 69) 628 { 629 tab = (cw >> 5) - 54 + 27; 630 } 631 else if ((cw >> 4) <= 198) 632 { 633 tab = (cw >> 4) - 140 + 43; 634 } 635 else if ((cw >> 3) <= 452) 636 { 637 tab = (cw >> 3) - 398 + 102; 638 } 639 else if ((cw >> 2) <= 1000) 640 { 641 tab = (cw >> 2) - 906 + 157; 642 } 643 else if ((cw >> 1) <= 2044) 644 { 645 tab = (cw >> 1) - 2002 + 252; 646 } 647 else 648 { 649 tab = cw - 4090 + 295; 650 } 651 652 tab = *(huff_tab11 + tab); 653 654 pInputStream->usedBits -= (12 - (tab & MASK_LOW16)); 655 return ((Int)(tab >> UPPER16)); 656 } 657 658 659 Int decode_huff_scl( 660 BITS *pInputStream) 661 { 662 Int32 tab; 663 Int32 cw; 664 665 cw = getbits( 666 19, 667 pInputStream); 668 669 if ((cw >> 18) == 0) 670 { 671 pInputStream->usedBits -= (19 - 1); /* used 1 bits */ 672 return 60; /* idx is 60 */ 673 } 674 else if ((cw >> 13) <= 59) 675 { 676 tab = (cw >> 13) - 32; 677 } 678 else if ((cw >> 10) <= 505) 679 { 680 tab = (cw >> 10) - 480 + 28; 681 } 682 else if ((cw >> 7) <= 4089) 683 { 684 tab = (cw >> 7) - 4048 + 54; 685 } 686 else if ((cw >> 5) <= 16377) 687 { 688 tab = (cw >> 5) - 16360 + 96; 689 } 690 else if ((cw >> 3) <= 65526) 691 { 692 tab = (cw >> 3) - 65512 + 114; 693 } 694 else if ((cw >> 1) <= 262120) 695 { 696 tab = (cw >> 1) - 262108 + 129; 697 } 698 else 699 { 700 tab = cw - 524242 + 142; 701 } 702 703 tab = *(huff_tab_scl + tab); 704 705 pInputStream->usedBits -= (19 - (tab & MASK_LOW16)); 706 return ((Int)(tab >> UPPER16)); 707 } 708 709