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