1/////////////////////////////////////////////////////////////////////////// 2// 3// Copyright (c) 2002, Industrial Light & Magic, a division of Lucas 4// Digital Ltd. LLC 5// 6// All rights reserved. 7// 8// Redistribution and use in source and binary forms, with or without 9// modification, are permitted provided that the following conditions are 10// met: 11// * Redistributions of source code must retain the above copyright 12// notice, this list of conditions and the following disclaimer. 13// * Redistributions in binary form must reproduce the above 14// copyright notice, this list of conditions and the following disclaimer 15// in the documentation and/or other materials provided with the 16// distribution. 17// * Neither the name of Industrial Light & Magic nor the names of 18// its contributors may be used to endorse or promote products derived 19// from this software without 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 35 36 37 38//----------------------------------------------------------------------------- 39// 40// 16-bit Huffman compression and decompression. 41// 42// The source code in this file is derived from the 8-bit 43// Huffman compression and decompression routines written 44// by Christian Rouet for his PIZ image file format. 45// 46//----------------------------------------------------------------------------- 47 48#include <ImfHuf.h> 49#include <ImfInt64.h> 50#include <ImfAutoArray.h> 51#include "Iex.h" 52#include <string.h> 53#include <assert.h> 54#include <algorithm> 55 56 57using namespace std; 58using namespace Iex; 59 60namespace Imf { 61namespace { 62 63 64const int HUF_ENCBITS = 16; // literal (value) bit length 65const int HUF_DECBITS = 14; // decoding bit size (>= 8) 66 67const int HUF_ENCSIZE = (1 << HUF_ENCBITS) + 1; // encoding table size 68const int HUF_DECSIZE = 1 << HUF_DECBITS; // decoding table size 69const int HUF_DECMASK = HUF_DECSIZE - 1; 70 71 72struct HufDec 73{ // short code long code 74 //------------------------------- 75 int len:8; // code length 0 76 int lit:24; // lit p size 77 int * p; // 0 lits 78}; 79 80 81void 82invalidNBits () 83{ 84 throw InputExc ("Error in header for Huffman-encoded data " 85 "(invalid number of bits)."); 86} 87 88 89void 90tooMuchData () 91{ 92 throw InputExc ("Error in Huffman-encoded data " 93 "(decoded data are longer than expected)."); 94} 95 96 97void 98notEnoughData () 99{ 100 throw InputExc ("Error in Huffman-encoded data " 101 "(decoded data are shorter than expected)."); 102} 103 104 105void 106invalidCode () 107{ 108 throw InputExc ("Error in Huffman-encoded data " 109 "(invalid code)."); 110} 111 112 113void 114invalidTableSize () 115{ 116 throw InputExc ("Error in Huffman-encoded data " 117 "(invalid code table size)."); 118} 119 120 121void 122unexpectedEndOfTable () 123{ 124 throw InputExc ("Error in Huffman-encoded data " 125 "(unexpected end of code table data)."); 126} 127 128 129void 130tableTooLong () 131{ 132 throw InputExc ("Error in Huffman-encoded data " 133 "(code table is longer than expected)."); 134} 135 136 137void 138invalidTableEntry () 139{ 140 throw InputExc ("Error in Huffman-encoded data " 141 "(invalid code table entry)."); 142} 143 144 145inline Int64 146hufLength (Int64 code) 147{ 148 return code & 63; 149} 150 151 152inline Int64 153hufCode (Int64 code) 154{ 155 return code >> 6; 156} 157 158 159inline void 160outputBits (int nBits, Int64 bits, Int64 &c, int &lc, char *&out) 161{ 162 c <<= nBits; 163 lc += nBits; 164 165 c |= bits; 166 167 while (lc >= 8) 168 *out++ = (c >> (lc -= 8)); 169} 170 171 172inline Int64 173getBits (int nBits, Int64 &c, int &lc, const char *&in) 174{ 175 while (lc < nBits) 176 { 177 c = (c << 8) | *(unsigned char *)(in++); 178 lc += 8; 179 } 180 181 lc -= nBits; 182 return (c >> lc) & ((1 << nBits) - 1); 183} 184 185 186// 187// ENCODING TABLE BUILDING & (UN)PACKING 188// 189 190// 191// Build a "canonical" Huffman code table: 192// - for each (uncompressed) symbol, hcode contains the length 193// of the corresponding code (in the compressed data) 194// - canonical codes are computed and stored in hcode 195// - the rules for constructing canonical codes are as follows: 196// * shorter codes (if filled with zeroes to the right) 197// have a numerically higher value than longer codes 198// * for codes with the same length, numerical values 199// increase with numerical symbol values 200// - because the canonical code table can be constructed from 201// symbol lengths alone, the code table can be transmitted 202// without sending the actual code values 203// - see http://www.compressconsult.com/huffman/ 204// 205 206void 207hufCanonicalCodeTable (Int64 hcode[HUF_ENCSIZE]) 208{ 209 Int64 n[59]; 210 211 // 212 // For each i from 0 through 58, count the 213 // number of different codes of length i, and 214 // store the count in n[i]. 215 // 216 217 for (int i = 0; i <= 58; ++i) 218 n[i] = 0; 219 220 for (int i = 0; i < HUF_ENCSIZE; ++i) 221 n[hcode[i]] += 1; 222 223 // 224 // For each i from 58 through 1, compute the 225 // numerically lowest code with length i, and 226 // store that code in n[i]. 227 // 228 229 Int64 c = 0; 230 231 for (int i = 58; i > 0; --i) 232 { 233 Int64 nc = ((c + n[i]) >> 1); 234 n[i] = c; 235 c = nc; 236 } 237 238 // 239 // hcode[i] contains the length, l, of the 240 // code for symbol i. Assign the next available 241 // code of length l to the symbol and store both 242 // l and the code in hcode[i]. 243 // 244 245 for (int i = 0; i < HUF_ENCSIZE; ++i) 246 { 247 int l = hcode[i]; 248 249 if (l > 0) 250 hcode[i] = l | (n[l]++ << 6); 251 } 252} 253 254 255// 256// Compute Huffman codes (based on frq input) and store them in frq: 257// - code structure is : [63:lsb - 6:msb] | [5-0: bit length]; 258// - max code length is 58 bits; 259// - codes outside the range [im-iM] have a null length (unused values); 260// - original frequencies are destroyed; 261// - encoding tables are used by hufEncode() and hufBuildDecTable(); 262// 263 264 265struct FHeapCompare 266{ 267 bool operator () (Int64 *a, Int64 *b) {return *a > *b;} 268}; 269 270 271void 272hufBuildEncTable 273 (Int64* frq, // io: input frequencies [HUF_ENCSIZE], output table 274 int* im, // o: min frq index 275 int* iM) // o: max frq index 276{ 277 // 278 // This function assumes that when it is called, array frq 279 // indicates the frequency of all possible symbols in the data 280 // that are to be Huffman-encoded. (frq[i] contains the number 281 // of occurrences of symbol i in the data.) 282 // 283 // The loop below does three things: 284 // 285 // 1) Finds the minimum and maximum indices that point 286 // to non-zero entries in frq: 287 // 288 // frq[im] != 0, and frq[i] == 0 for all i < im 289 // frq[iM] != 0, and frq[i] == 0 for all i > iM 290 // 291 // 2) Fills array fHeap with pointers to all non-zero 292 // entries in frq. 293 // 294 // 3) Initializes array hlink such that hlink[i] == i 295 // for all array entries. 296 // 297 298 AutoArray <int, HUF_ENCSIZE> hlink; 299 AutoArray <Int64 *, HUF_ENCSIZE> fHeap; 300 301 *im = 0; 302 303 while (!frq[*im]) 304 (*im)++; 305 306 int nf = 0; 307 308 for (int i = *im; i < HUF_ENCSIZE; i++) 309 { 310 hlink[i] = i; 311 312 if (frq[i]) 313 { 314 fHeap[nf] = &frq[i]; 315 nf++; 316 *iM = i; 317 } 318 } 319 320 // 321 // Add a pseudo-symbol, with a frequency count of 1, to frq; 322 // adjust the fHeap and hlink array accordingly. Function 323 // hufEncode() uses the pseudo-symbol for run-length encoding. 324 // 325 326 (*iM)++; 327 frq[*iM] = 1; 328 fHeap[nf] = &frq[*iM]; 329 nf++; 330 331 // 332 // Build an array, scode, such that scode[i] contains the number 333 // of bits assigned to symbol i. Conceptually this is done by 334 // constructing a tree whose leaves are the symbols with non-zero 335 // frequency: 336 // 337 // Make a heap that contains all symbols with a non-zero frequency, 338 // with the least frequent symbol on top. 339 // 340 // Repeat until only one symbol is left on the heap: 341 // 342 // Take the two least frequent symbols off the top of the heap. 343 // Create a new node that has first two nodes as children, and 344 // whose frequency is the sum of the frequencies of the first 345 // two nodes. Put the new node back into the heap. 346 // 347 // The last node left on the heap is the root of the tree. For each 348 // leaf node, the distance between the root and the leaf is the length 349 // of the code for the corresponding symbol. 350 // 351 // The loop below doesn't actually build the tree; instead we compute 352 // the distances of the leaves from the root on the fly. When a new 353 // node is added to the heap, then that node's descendants are linked 354 // into a single linear list that starts at the new node, and the code 355 // lengths of the descendants (that is, their distance from the root 356 // of the tree) are incremented by one. 357 // 358 359 make_heap (&fHeap[0], &fHeap[nf], FHeapCompare()); 360 361 AutoArray <Int64, HUF_ENCSIZE> scode; 362 memset (scode, 0, sizeof (Int64) * HUF_ENCSIZE); 363 364 while (nf > 1) 365 { 366 // 367 // Find the indices, mm and m, of the two smallest non-zero frq 368 // values in fHeap, add the smallest frq to the second-smallest 369 // frq, and remove the smallest frq value from fHeap. 370 // 371 372 int mm = fHeap[0] - frq; 373 pop_heap (&fHeap[0], &fHeap[nf], FHeapCompare()); 374 --nf; 375 376 int m = fHeap[0] - frq; 377 pop_heap (&fHeap[0], &fHeap[nf], FHeapCompare()); 378 379 frq[m ] += frq[mm]; 380 push_heap (&fHeap[0], &fHeap[nf], FHeapCompare()); 381 382 // 383 // The entries in scode are linked into lists with the 384 // entries in hlink serving as "next" pointers and with 385 // the end of a list marked by hlink[j] == j. 386 // 387 // Traverse the lists that start at scode[m] and scode[mm]. 388 // For each element visited, increment the length of the 389 // corresponding code by one bit. (If we visit scode[j] 390 // during the traversal, then the code for symbol j becomes 391 // one bit longer.) 392 // 393 // Merge the lists that start at scode[m] and scode[mm] 394 // into a single list that starts at scode[m]. 395 // 396 397 // 398 // Add a bit to all codes in the first list. 399 // 400 401 for (int j = m; true; j = hlink[j]) 402 { 403 scode[j]++; 404 405 assert (scode[j] <= 58); 406 407 if (hlink[j] == j) 408 { 409 // 410 // Merge the two lists. 411 // 412 413 hlink[j] = mm; 414 break; 415 } 416 } 417 418 // 419 // Add a bit to all codes in the second list 420 // 421 422 for (int j = mm; true; j = hlink[j]) 423 { 424 scode[j]++; 425 426 assert (scode[j] <= 58); 427 428 if (hlink[j] == j) 429 break; 430 } 431 } 432 433 // 434 // Build a canonical Huffman code table, replacing the code 435 // lengths in scode with (code, code length) pairs. Copy the 436 // code table from scode into frq. 437 // 438 439 hufCanonicalCodeTable (scode); 440 memcpy (frq, scode, sizeof (Int64) * HUF_ENCSIZE); 441} 442 443 444// 445// Pack an encoding table: 446// - only code lengths, not actual codes, are stored 447// - runs of zeroes are compressed as follows: 448// 449// unpacked packed 450// -------------------------------- 451// 1 zero 0 (6 bits) 452// 2 zeroes 59 453// 3 zeroes 60 454// 4 zeroes 61 455// 5 zeroes 62 456// n zeroes (6 or more) 63 n-6 (6 + 8 bits) 457// 458 459const int SHORT_ZEROCODE_RUN = 59; 460const int LONG_ZEROCODE_RUN = 63; 461const int SHORTEST_LONG_RUN = 2 + LONG_ZEROCODE_RUN - SHORT_ZEROCODE_RUN; 462const int LONGEST_LONG_RUN = 255 + SHORTEST_LONG_RUN; 463 464 465void 466hufPackEncTable 467 (const Int64* hcode, // i : encoding table [HUF_ENCSIZE] 468 int im, // i : min hcode index 469 int iM, // i : max hcode index 470 char** pcode) // o: ptr to packed table (updated) 471{ 472 char *p = *pcode; 473 Int64 c = 0; 474 int lc = 0; 475 476 for (; im <= iM; im++) 477 { 478 int l = hufLength (hcode[im]); 479 480 if (l == 0) 481 { 482 int zerun = 1; 483 484 while ((im < iM) && (zerun < LONGEST_LONG_RUN)) 485 { 486 if (hufLength (hcode[im+1]) > 0 ) 487 break; 488 im++; 489 zerun++; 490 } 491 492 if (zerun >= 2) 493 { 494 if (zerun >= SHORTEST_LONG_RUN) 495 { 496 outputBits (6, LONG_ZEROCODE_RUN, c, lc, p); 497 outputBits (8, zerun - SHORTEST_LONG_RUN, c, lc, p); 498 } 499 else 500 { 501 outputBits (6, SHORT_ZEROCODE_RUN + zerun - 2, c, lc, p); 502 } 503 continue; 504 } 505 } 506 507 outputBits (6, l, c, lc, p); 508 } 509 510 if (lc > 0) 511 *p++ = (unsigned char) (c << (8 - lc)); 512 513 *pcode = p; 514} 515 516 517// 518// Unpack an encoding table packed by hufPackEncTable(): 519// 520 521void 522hufUnpackEncTable 523 (const char** pcode, // io: ptr to packed table (updated) 524 int ni, // i : input size (in bytes) 525 int im, // i : min hcode index 526 int iM, // i : max hcode index 527 Int64* hcode) // o: encoding table [HUF_ENCSIZE] 528{ 529 memset (hcode, 0, sizeof (Int64) * HUF_ENCSIZE); 530 531 const char *p = *pcode; 532 Int64 c = 0; 533 int lc = 0; 534 535 for (; im <= iM; im++) 536 { 537 if (p - *pcode > ni) 538 unexpectedEndOfTable(); 539 540 Int64 l = hcode[im] = getBits (6, c, lc, p); // code length 541 542 if (l == (Int64) LONG_ZEROCODE_RUN) 543 { 544 if (p - *pcode > ni) 545 unexpectedEndOfTable(); 546 547 int zerun = getBits (8, c, lc, p) + SHORTEST_LONG_RUN; 548 549 if (im + zerun > iM + 1) 550 tableTooLong(); 551 552 while (zerun--) 553 hcode[im++] = 0; 554 555 im--; 556 } 557 else if (l >= (Int64) SHORT_ZEROCODE_RUN) 558 { 559 int zerun = l - SHORT_ZEROCODE_RUN + 2; 560 561 if (im + zerun > iM + 1) 562 tableTooLong(); 563 564 while (zerun--) 565 hcode[im++] = 0; 566 567 im--; 568 } 569 } 570 571 *pcode = (char *) p; 572 573 hufCanonicalCodeTable (hcode); 574} 575 576 577// 578// DECODING TABLE BUILDING 579// 580 581// 582// Build a decoding hash table based on the encoding table hcode: 583// - short codes (<= HUF_DECBITS) are resolved with a single table access; 584// - long code entry allocations are not optimized, because long codes are 585// unfrequent; 586// - decoding tables are used by hufDecode(); 587// 588 589void 590hufBuildDecTable 591 (const Int64* hcode, // i : encoding table 592 int im, // i : min index in hcode 593 int iM, // i : max index in hcode 594 HufDec * hdecod) // o: (allocated by caller) 595 // decoding table [HUF_DECSIZE] 596{ 597 // 598 // Init hashtable & loop on all codes 599 // 600 601 memset (hdecod, 0, sizeof (HufDec) * HUF_DECSIZE); 602 603 for (; im <= iM; im++) 604 { 605 Int64 c = hufCode (hcode[im]); 606 int l = hufLength (hcode[im]); 607 608 if (c >> l) 609 { 610 // 611 // Error: c is supposed to be an l-bit code, 612 // but c contains a value that is greater 613 // than the largest l-bit number. 614 // 615 616 invalidTableEntry(); 617 } 618 619 if (l > HUF_DECBITS) 620 { 621 // 622 // Long code: add a secondary entry 623 // 624 625 HufDec *pl = hdecod + (c >> (l - HUF_DECBITS)); 626 627 if (pl->len) 628 { 629 // 630 // Error: a short code has already 631 // been stored in table entry *pl. 632 // 633 634 invalidTableEntry(); 635 } 636 637 pl->lit++; 638 639 if (pl->p) 640 { 641 int *p = pl->p; 642 pl->p = new int [pl->lit]; 643 644 for (int i = 0; i < pl->lit - 1; ++i) 645 pl->p[i] = p[i]; 646 647 delete [] p; 648 } 649 else 650 { 651 pl->p = new int [1]; 652 } 653 654 pl->p[pl->lit - 1]= im; 655 } 656 else if (l) 657 { 658 // 659 // Short code: init all primary entries 660 // 661 662 HufDec *pl = hdecod + (c << (HUF_DECBITS - l)); 663 664 for (Int64 i = 1 << (HUF_DECBITS - l); i > 0; i--, pl++) 665 { 666 if (pl->len || pl->p) 667 { 668 // 669 // Error: a short code or a long code has 670 // already been stored in table entry *pl. 671 // 672 673 invalidTableEntry(); 674 } 675 676 pl->len = l; 677 pl->lit = im; 678 } 679 } 680 } 681} 682 683 684// 685// Free the long code entries of a decoding table built by hufBuildDecTable() 686// 687 688void 689hufFreeDecTable (HufDec *hdecod) // io: Decoding table 690{ 691 for (int i = 0; i < HUF_DECSIZE; i++) 692 { 693 if (hdecod[i].p) 694 { 695 delete [] hdecod[i].p; 696 hdecod[i].p = 0; 697 } 698 } 699} 700 701 702// 703// ENCODING 704// 705 706inline void 707outputCode (Int64 code, Int64 &c, int &lc, char *&out) 708{ 709 outputBits (hufLength (code), hufCode (code), c, lc, out); 710} 711 712 713inline void 714sendCode (Int64 sCode, int runCount, Int64 runCode, 715 Int64 &c, int &lc, char *&out) 716{ 717 static const int RLMIN = 32; // min count to activate run-length coding 718 719 if (runCount > RLMIN) 720 { 721 outputCode (sCode, c, lc, out); 722 outputCode (runCode, c, lc, out); 723 outputBits (8, runCount, c, lc, out); 724 } 725 else 726 { 727 while (runCount-- >= 0) 728 outputCode (sCode, c, lc, out); 729 } 730} 731 732 733// 734// Encode (compress) ni values based on the Huffman encoding table hcode: 735// 736 737int 738hufEncode // return: output size (in bits) 739 (const Int64* hcode, // i : encoding table 740 const unsigned short* in, // i : uncompressed input buffer 741 const int ni, // i : input buffer size (in bytes) 742 int rlc, // i : rl code 743 char* out) // o: compressed output buffer 744{ 745 char *outStart = out; 746 Int64 c = 0; // bits not yet written to out 747 int lc = 0; // number of valid bits in c (LSB) 748 int s = in[0]; 749 int cs = 0; 750 751 // 752 // Loop on input values 753 // 754 755 for (int i = 1; i < ni; i++) 756 { 757 // 758 // Count same values or send code 759 // 760 761 if (s == in[i] && cs < 255) 762 { 763 cs++; 764 } 765 else 766 { 767 sendCode (hcode[s], cs, hcode[rlc], c, lc, out); 768 cs=0; 769 } 770 771 s = in[i]; 772 } 773 774 // 775 // Send remaining code 776 // 777 778 sendCode (hcode[s], cs, hcode[rlc], c, lc, out); 779 780 if (lc) 781 *out = (c << (8 - lc)) & 0xff; 782 783 return (out - outStart) * 8 + lc; 784} 785 786 787// 788// DECODING 789// 790 791// 792// In order to force the compiler to inline them, 793// getChar() and getCode() are implemented as macros 794// instead of "inline" functions. 795// 796 797#define getChar(c, lc, in) \ 798{ \ 799 c = (c << 8) | *(unsigned char *)(in++); \ 800 lc += 8; \ 801} 802 803 804#define getCode(po, rlc, c, lc, in, out, oe) \ 805{ \ 806 if (po == rlc) \ 807 { \ 808 if (lc < 8) \ 809 getChar(c, lc, in); \ 810 \ 811 lc -= 8; \ 812 \ 813 unsigned char cs = (c >> lc); \ 814 \ 815 if (out + cs > oe) \ 816 tooMuchData(); \ 817 \ 818 unsigned short s = out[-1]; \ 819 \ 820 while (cs-- > 0) \ 821 *out++ = s; \ 822 } \ 823 else if (out < oe) \ 824 { \ 825 *out++ = po; \ 826 } \ 827 else \ 828 { \ 829 tooMuchData(); \ 830 } \ 831} 832 833 834// 835// Decode (uncompress) ni bits based on encoding & decoding tables: 836// 837 838void 839hufDecode 840 (const Int64 * hcode, // i : encoding table 841 const HufDec * hdecod, // i : decoding table 842 const char* in, // i : compressed input buffer 843 int ni, // i : input size (in bits) 844 int rlc, // i : run-length code 845 int no, // i : expected output size (in bytes) 846 unsigned short* out) // o: uncompressed output buffer 847{ 848 Int64 c = 0; 849 int lc = 0; 850 unsigned short * outb = out; 851 unsigned short * oe = out + no; 852 const char * ie = in + (ni + 7) / 8; // input byte size 853 854 // 855 // Loop on input bytes 856 // 857 858 while (in < ie) 859 { 860 getChar (c, lc, in); 861 862 // 863 // Access decoding table 864 // 865 866 while (lc >= HUF_DECBITS) 867 { 868 const HufDec pl = hdecod[(c >> (lc-HUF_DECBITS)) & HUF_DECMASK]; 869 870 if (pl.len) 871 { 872 // 873 // Get short code 874 // 875 876 lc -= pl.len; 877 getCode (pl.lit, rlc, c, lc, in, out, oe); 878 } 879 else 880 { 881 if (!pl.p) 882 invalidCode(); // wrong code 883 884 // 885 // Search long code 886 // 887 888 int j; 889 890 for (j = 0; j < pl.lit; j++) 891 { 892 int l = hufLength (hcode[pl.p[j]]); 893 894 while (lc < l && in < ie) // get more bits 895 getChar (c, lc, in); 896 897 if (lc >= l) 898 { 899 if (hufCode (hcode[pl.p[j]]) == 900 ((c >> (lc - l)) & ((Int64(1) << l) - 1))) 901 { 902 // 903 // Found : get long code 904 // 905 906 lc -= l; 907 getCode (pl.p[j], rlc, c, lc, in, out, oe); 908 break; 909 } 910 } 911 } 912 913 if (j == pl.lit) 914 invalidCode(); // Not found 915 } 916 } 917 } 918 919 // 920 // Get remaining (short) codes 921 // 922 923 int i = (8 - ni) & 7; 924 c >>= i; 925 lc -= i; 926 927 while (lc > 0) 928 { 929 const HufDec pl = hdecod[(c << (HUF_DECBITS - lc)) & HUF_DECMASK]; 930 931 if (pl.len) 932 { 933 lc -= pl.len; 934 getCode (pl.lit, rlc, c, lc, in, out, oe); 935 } 936 else 937 { 938 invalidCode(); // wrong (long) code 939 } 940 } 941 942 if (out - outb != no) 943 notEnoughData (); 944} 945 946 947void 948countFrequencies (Int64 freq[HUF_ENCSIZE], 949 const unsigned short data[/*n*/], 950 int n) 951{ 952 for (int i = 0; i < HUF_ENCSIZE; ++i) 953 freq[i] = 0; 954 955 for (int i = 0; i < n; ++i) 956 ++freq[data[i]]; 957} 958 959 960void 961writeUInt (char buf[4], unsigned int i) 962{ 963 unsigned char *b = (unsigned char *) buf; 964 965 b[0] = i; 966 b[1] = i >> 8; 967 b[2] = i >> 16; 968 b[3] = i >> 24; 969} 970 971 972unsigned int 973readUInt (const char buf[4]) 974{ 975 const unsigned char *b = (const unsigned char *) buf; 976 977 return ( b[0] & 0x000000ff) | 978 ((b[1] << 8) & 0x0000ff00) | 979 ((b[2] << 16) & 0x00ff0000) | 980 ((b[3] << 24) & 0xff000000); 981} 982 983} // namespace 984 985 986// 987// EXTERNAL INTERFACE 988// 989 990 991int 992hufCompress (const unsigned short raw[], 993 int nRaw, 994 char compressed[]) 995{ 996 if (nRaw == 0) 997 return 0; 998 999 AutoArray <Int64, HUF_ENCSIZE> freq; 1000 1001 countFrequencies (freq, raw, nRaw); 1002 1003 int im, iM; 1004 hufBuildEncTable (freq, &im, &iM); 1005 1006 char *tableStart = compressed + 20; 1007 char *tableEnd = tableStart; 1008 hufPackEncTable (freq, im, iM, &tableEnd); 1009 int tableLength = tableEnd - tableStart; 1010 1011 char *dataStart = tableEnd; 1012 int nBits = hufEncode (freq, raw, nRaw, iM, dataStart); 1013 int dataLength = (nBits + 7) / 8; 1014 1015 writeUInt (compressed, im); 1016 writeUInt (compressed + 4, iM); 1017 writeUInt (compressed + 8, tableLength); 1018 writeUInt (compressed + 12, nBits); 1019 writeUInt (compressed + 16, 0); // room for future extensions 1020 1021 return dataStart + dataLength - compressed; 1022} 1023 1024 1025void 1026hufUncompress (const char compressed[], 1027 int nCompressed, 1028 unsigned short raw[], 1029 int nRaw) 1030{ 1031 if (nCompressed == 0) 1032 { 1033 if (nRaw != 0) 1034 notEnoughData(); 1035 1036 return; 1037 } 1038 1039 int im = readUInt (compressed); 1040 int iM = readUInt (compressed + 4); 1041 // int tableLength = readUInt (compressed + 8); 1042 int nBits = readUInt (compressed + 12); 1043 1044 if (im < 0 || im >= HUF_ENCSIZE || iM < 0 || iM >= HUF_ENCSIZE) 1045 invalidTableSize(); 1046 1047 const char *ptr = compressed + 20; 1048 1049 AutoArray <Int64, HUF_ENCSIZE> freq; 1050 AutoArray <HufDec, HUF_DECSIZE> hdec; 1051 1052 hufUnpackEncTable (&ptr, nCompressed - (ptr - compressed), im, iM, freq); 1053 1054 try 1055 { 1056 if (nBits > 8 * (nCompressed - (ptr - compressed))) 1057 invalidNBits(); 1058 1059 hufBuildDecTable (freq, im, iM, hdec); 1060 hufDecode (freq, hdec, ptr, nBits, iM, nRaw, raw); 1061 } 1062 catch (...) 1063 { 1064 hufFreeDecTable (hdec); 1065 throw; 1066 } 1067 1068 hufFreeDecTable (hdec); 1069} 1070 1071 1072} // namespace Imf 1073