← Back to branch summary

~paparazzi-uav/paparazzi/v5.0-manual

« back to all changes in this revision

Viewing changes to sw/ext/opencv_bebop/opencv/3rdparty/openexr/IlmImf/ImfHuf.cpp

  • Committer: Paparazzi buildbot
  • Date: 2016-05-18 15:00:29 UTC
  • Revision ID: felix.ruess+docbot@gmail.com-20160518150029-e8lgzi5kvb4p7un9
Manual import commit 4b8bbb730080dac23cf816b98908dacfabe2a8ec from v5.0 branch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
sw/ext/opencv_bebop/opencv/3rdparty/openexr/IlmImf/ImfHuf.cpp
 
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
 
 
57
using namespace std;
 
58
using namespace Iex;
 
59
 
 
60
namespace Imf {
 
61
namespace {
 
62
 
 
63
 
 
64
const int HUF_ENCBITS = 16;                     // literal (value) bit length
 
65
const int HUF_DECBITS = 14;                     // decoding bit size (>= 8)
 
66
 
 
67
const int HUF_ENCSIZE = (1 << HUF_ENCBITS) + 1; // encoding table size
 
68
const int HUF_DECSIZE =  1 << HUF_DECBITS;      // decoding table size
 
69
const int HUF_DECMASK = HUF_DECSIZE - 1;
 
70
 
 
71
 
 
72
struct 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
 
 
81
void
 
82
invalidNBits ()
 
83
{
 
84
    throw InputExc ("Error in header for Huffman-encoded data "
 
85
            "(invalid number of bits).");
 
86
}
 
87
 
 
88
 
 
89
void
 
90
tooMuchData ()
 
91
{
 
92
    throw InputExc ("Error in Huffman-encoded data "
 
93
            "(decoded data are longer than expected).");
 
94
}
 
95
 
 
96
 
 
97
void
 
98
notEnoughData ()
 
99
{
 
100
    throw InputExc ("Error in Huffman-encoded data "
 
101
            "(decoded data are shorter than expected).");
 
102
}
 
103
 
 
104
 
 
105
void
 
106
invalidCode ()
 
107
{
 
108
    throw InputExc ("Error in Huffman-encoded data "
 
109
            "(invalid code).");
 
110
}
 
111
 
 
112
 
 
113
void
 
114
invalidTableSize ()
 
115
{
 
116
    throw InputExc ("Error in Huffman-encoded data "
 
117
            "(invalid code table size).");
 
118
}
 
119
 
 
120
 
 
121
void
 
122
unexpectedEndOfTable ()
 
123
{
 
124
    throw InputExc ("Error in Huffman-encoded data "
 
125
            "(unexpected end of code table data).");
 
126
}
 
127
 
 
128
 
 
129
void
 
130
tableTooLong ()
 
131
{
 
132
    throw InputExc ("Error in Huffman-encoded data "
 
133
            "(code table is longer than expected).");
 
134
}
 
135
 
 
136
 
 
137
void
 
138
invalidTableEntry ()
 
139
{
 
140
    throw InputExc ("Error in Huffman-encoded data "
 
141
            "(invalid code table entry).");
 
142
}
 
143
 
 
144
 
 
145
inline Int64
 
146
hufLength (Int64 code)
 
147
{
 
148
    return code & 63;
 
149
}
 
150
 
 
151
 
 
152
inline Int64
 
153
hufCode (Int64 code)
 
154
{
 
155
    return code >> 6;
 
156
}
 
157
 
 
158
 
 
159
inline void
 
160
outputBits (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
 
 
172
inline Int64
 
173
getBits (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
 
 
206
void
 
207
hufCanonicalCodeTable (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
 
 
265
struct FHeapCompare
 
266
{
 
267
    bool operator () (Int64 *a, Int64 *b) {return *a > *b;}
 
268
};
 
269
 
 
270
 
 
271
void
 
272
hufBuildEncTable
 
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
 
 
459
const int SHORT_ZEROCODE_RUN = 59;
 
460
const int LONG_ZEROCODE_RUN  = 63;
 
461
const int SHORTEST_LONG_RUN  = 2 + LONG_ZEROCODE_RUN - SHORT_ZEROCODE_RUN;
 
462
const int LONGEST_LONG_RUN   = 255 + SHORTEST_LONG_RUN;
 
463
 
 
464
 
 
465
void
 
466
hufPackEncTable
 
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
 
 
521
void
 
522
hufUnpackEncTable
 
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
// Clear a newly allocated decoding table so that it contains only zeroes.
 
583
//
 
584
 
 
585
void
 
586
hufClearDecTable
 
587
    (HufDec *           hdecod)         // io: (allocated by caller)
 
588
                        //     decoding table [HUF_DECSIZE]
 
589
{
 
590
    memset (hdecod, 0, sizeof (HufDec) * HUF_DECSIZE);
 
591
}
 
592
 
 
593
 
 
594
//
 
595
// Build a decoding hash table based on the encoding table hcode:
 
596
//      - short codes (<= HUF_DECBITS) are resolved with a single table access;
 
597
//      - long code entry allocations are not optimized, because long codes are
 
598
//        unfrequent;
 
599
//      - decoding tables are used by hufDecode();
 
600
//
 
601
 
 
602
void
 
603
hufBuildDecTable
 
604
    (const Int64*       hcode,          // i : encoding table
 
605
     int                im,             // i : min index in hcode
 
606
     int                iM,             // i : max index in hcode
 
607
     HufDec *           hdecod)         //  o: (allocated by caller)
 
608
                        //     decoding table [HUF_DECSIZE]
 
609
{
 
610
    //
 
611
    // Init hashtable & loop on all codes.
 
612
    // Assumes that hufClearDecTable(hdecod) has already been called.
 
613
    //
 
614
 
 
615
    for (; im <= iM; im++)
 
616
    {
 
617
    Int64 c = hufCode (hcode[im]);
 
618
    int l = hufLength (hcode[im]);
 
619
 
 
620
    if (c >> l)
 
621
    {
 
622
        //
 
623
        // Error: c is supposed to be an l-bit code,
 
624
        // but c contains a value that is greater
 
625
        // than the largest l-bit number.
 
626
        //
 
627
 
 
628
        invalidTableEntry();
 
629
    }
 
630
 
 
631
    if (l > HUF_DECBITS)
 
632
    {
 
633
        //
 
634
        // Long code: add a secondary entry
 
635
        //
 
636
 
 
637
        HufDec *pl = hdecod + (c >> (l - HUF_DECBITS));
 
638
 
 
639
        if (pl->len)
 
640
        {
 
641
        //
 
642
        // Error: a short code has already
 
643
        // been stored in table entry *pl.
 
644
        //
 
645
 
 
646
        invalidTableEntry();
 
647
        }
 
648
 
 
649
        pl->lit++;
 
650
 
 
651
        if (pl->p)
 
652
        {
 
653
        int *p = pl->p;
 
654
        pl->p = new int [pl->lit];
 
655
 
 
656
        for (int i = 0; i < pl->lit - 1; ++i)
 
657
            pl->p[i] = p[i];
 
658
 
 
659
        delete [] p;
 
660
        }
 
661
        else
 
662
        {
 
663
        pl->p = new int [1];
 
664
        }
 
665
 
 
666
        pl->p[pl->lit - 1]= im;
 
667
    }
 
668
    else if (l)
 
669
    {
 
670
        //
 
671
        // Short code: init all primary entries
 
672
        //
 
673
 
 
674
        HufDec *pl = hdecod + (c << (HUF_DECBITS - l));
 
675
 
 
676
        for (Int64 i = 1 << (HUF_DECBITS - l); i > 0; i--, pl++)
 
677
        {
 
678
        if (pl->len || pl->p)
 
679
        {
 
680
            //
 
681
            // Error: a short code or a long code has
 
682
            // already been stored in table entry *pl.
 
683
            //
 
684
 
 
685
            invalidTableEntry();
 
686
        }
 
687
 
 
688
        pl->len = l;
 
689
        pl->lit = im;
 
690
        }
 
691
    }
 
692
    }
 
693
}
 
694
 
 
695
 
 
696
//
 
697
// Free the long code entries of a decoding table built by hufBuildDecTable()
 
698
//
 
699
 
 
700
void
 
701
hufFreeDecTable (HufDec *hdecod)        // io: Decoding table
 
702
{
 
703
    for (int i = 0; i < HUF_DECSIZE; i++)
 
704
    {
 
705
    if (hdecod[i].p)
 
706
    {
 
707
        delete [] hdecod[i].p;
 
708
        hdecod[i].p = 0;
 
709
    }
 
710
    }
 
711
}
 
712
 
 
713
 
 
714
//
 
715
// ENCODING
 
716
//
 
717
 
 
718
inline void
 
719
outputCode (Int64 code, Int64 &c, int &lc, char *&out)
 
720
{
 
721
    outputBits (hufLength (code), hufCode (code), c, lc, out);
 
722
}
 
723
 
 
724
 
 
725
inline void
 
726
sendCode (Int64 sCode, int runCount, Int64 runCode,
 
727
      Int64 &c, int &lc, char *&out)
 
728
{
 
729
    static const int RLMIN = 32; // min count to activate run-length coding
 
730
 
 
731
    if (runCount > RLMIN)
 
732
    {
 
733
    outputCode (sCode, c, lc, out);
 
734
    outputCode (runCode, c, lc, out);
 
735
    outputBits (8, runCount, c, lc, out);
 
736
    }
 
737
    else
 
738
    {
 
739
    while (runCount-- >= 0)
 
740
        outputCode (sCode, c, lc, out);
 
741
    }
 
742
}
 
743
 
 
744
 
 
745
//
 
746
// Encode (compress) ni values based on the Huffman encoding table hcode:
 
747
//
 
748
 
 
749
int
 
750
hufEncode                               // return: output size (in bits)
 
751
    (const Int64*           hcode,      // i : encoding table
 
752
     const unsigned short*  in,         // i : uncompressed input buffer
 
753
     const int              ni,         // i : input buffer size (in bytes)
 
754
     int                    rlc,        // i : rl code
 
755
     char*                  out)        //  o: compressed output buffer
 
756
{
 
757
    char *outStart = out;
 
758
    Int64 c = 0;        // bits not yet written to out
 
759
    int lc = 0;         // number of valid bits in c (LSB)
 
760
    int s = in[0];
 
761
    int cs = 0;
 
762
 
 
763
    //
 
764
    // Loop on input values
 
765
    //
 
766
 
 
767
    for (int i = 1; i < ni; i++)
 
768
    {
 
769
    //
 
770
    // Count same values or send code
 
771
    //
 
772
 
 
773
    if (s == in[i] && cs < 255)
 
774
    {
 
775
        cs++;
 
776
    }
 
777
    else
 
778
    {
 
779
        sendCode (hcode[s], cs, hcode[rlc], c, lc, out);
 
780
        cs=0;
 
781
    }
 
782
 
 
783
    s = in[i];
 
784
    }
 
785
 
 
786
    //
 
787
    // Send remaining code
 
788
    //
 
789
 
 
790
    sendCode (hcode[s], cs, hcode[rlc], c, lc, out);
 
791
 
 
792
    if (lc)
 
793
    *out = (c << (8 - lc)) & 0xff;
 
794
 
 
795
    return (out - outStart) * 8 + lc;
 
796
}
 
797
 
 
798
 
 
799
//
 
800
// DECODING
 
801
//
 
802
 
 
803
//
 
804
// In order to force the compiler to inline them,
 
805
// getChar() and getCode() are implemented as macros
 
806
// instead of "inline" functions.
 
807
//
 
808
 
 
809
#define getChar(c, lc, in)                      \
 
810
{                                               \
 
811
    c = (c << 8) | *(unsigned char *)(in++);    \
 
812
    lc += 8;                                    \
 
813
}
 
814
 
 
815
 
 
816
#define getCode(po, rlc, c, lc, in, out, oe)    \
 
817
{                                               \
 
818
    if (po == rlc)                              \
 
819
    {                                           \
 
820
    if (lc < 8)                         \
 
821
        getChar(c, lc, in);                     \
 
822
                        \
 
823
    lc -= 8;                            \
 
824
                        \
 
825
    unsigned char cs = (c >> lc);               \
 
826
                        \
 
827
    if (out + cs > oe)                  \
 
828
        tooMuchData();                  \
 
829
                        \
 
830
    unsigned short s = out[-1];         \
 
831
                        \
 
832
    while (cs-- > 0)                    \
 
833
        *out++ = s;                             \
 
834
    }                                           \
 
835
    else if (out < oe)                          \
 
836
    {                                           \
 
837
    *out++ = po;                                \
 
838
    }                                           \
 
839
    else                                        \
 
840
    {                                           \
 
841
    tooMuchData();                              \
 
842
    }                                           \
 
843
}
 
844
 
 
845
 
 
846
//
 
847
// Decode (uncompress) ni bits based on encoding & decoding tables:
 
848
//
 
849
 
 
850
void
 
851
hufDecode
 
852
    (const Int64 *      hcode,  // i : encoding table
 
853
     const HufDec *     hdecod, // i : decoding table
 
854
     const char*        in,     // i : compressed input buffer
 
855
     int                ni,     // i : input size (in bits)
 
856
     int                rlc,    // i : run-length code
 
857
     int                no,     // i : expected output size (in bytes)
 
858
     unsigned short*    out)    //  o: uncompressed output buffer
 
859
{
 
860
    Int64 c = 0;
 
861
    int lc = 0;
 
862
    unsigned short * outb = out;
 
863
    unsigned short * oe = out + no;
 
864
    const char * ie = in + (ni + 7) / 8; // input byte size
 
865
 
 
866
    //
 
867
    // Loop on input bytes
 
868
    //
 
869
 
 
870
    while (in < ie)
 
871
    {
 
872
    getChar (c, lc, in);
 
873
 
 
874
    //
 
875
    // Access decoding table
 
876
    //
 
877
 
 
878
    while (lc >= HUF_DECBITS)
 
879
    {
 
880
        const HufDec pl = hdecod[(c >> (lc-HUF_DECBITS)) & HUF_DECMASK];
 
881
 
 
882
        if (pl.len)
 
883
        {
 
884
        //
 
885
        // Get short code
 
886
        //
 
887
 
 
888
        lc -= pl.len;
 
889
        getCode (pl.lit, rlc, c, lc, in, out, oe);
 
890
        }
 
891
        else
 
892
        {
 
893
        if (!pl.p)
 
894
            invalidCode(); // wrong code
 
895
 
 
896
        //
 
897
        // Search long code
 
898
        //
 
899
 
 
900
        int j;
 
901
 
 
902
        for (j = 0; j < pl.lit; j++)
 
903
        {
 
904
            int l = hufLength (hcode[pl.p[j]]);
 
905
 
 
906
            while (lc < l && in < ie)   // get more bits
 
907
            getChar (c, lc, in);
 
908
 
 
909
            if (lc >= l)
 
910
            {
 
911
            if (hufCode (hcode[pl.p[j]]) ==
 
912
                ((c >> (lc - l)) & ((Int64(1) << l) - 1)))
 
913
            {
 
914
                //
 
915
                // Found : get long code
 
916
                //
 
917
 
 
918
                lc -= l;
 
919
                getCode (pl.p[j], rlc, c, lc, in, out, oe);
 
920
                break;
 
921
            }
 
922
            }
 
923
        }
 
924
 
 
925
        if (j == pl.lit)
 
926
            invalidCode(); // Not found
 
927
        }
 
928
    }
 
929
    }
 
930
 
 
931
    //
 
932
    // Get remaining (short) codes
 
933
    //
 
934
 
 
935
    int i = (8 - ni) & 7;
 
936
    c >>= i;
 
937
    lc -= i;
 
938
 
 
939
    while (lc > 0)
 
940
    {
 
941
    const HufDec pl = hdecod[(c << (HUF_DECBITS - lc)) & HUF_DECMASK];
 
942
 
 
943
    if (pl.len)
 
944
    {
 
945
        lc -= pl.len;
 
946
        getCode (pl.lit, rlc, c, lc, in, out, oe);
 
947
    }
 
948
    else
 
949
    {
 
950
        invalidCode(); // wrong (long) code
 
951
    }
 
952
    }
 
953
 
 
954
    if (out - outb != no)
 
955
    notEnoughData ();
 
956
}
 
957
 
 
958
 
 
959
void
 
960
countFrequencies (Int64 freq[HUF_ENCSIZE],
 
961
          const unsigned short data[/*n*/],
 
962
          int n)
 
963
{
 
964
    for (int i = 0; i < HUF_ENCSIZE; ++i)
 
965
    freq[i] = 0;
 
966
 
 
967
    for (int i = 0; i < n; ++i)
 
968
    ++freq[data[i]];
 
969
}
 
970
 
 
971
 
 
972
void
 
973
writeUInt (char buf[4], unsigned int i)
 
974
{
 
975
    unsigned char *b = (unsigned char *) buf;
 
976
 
 
977
    b[0] = i;
 
978
    b[1] = i >> 8;
 
979
    b[2] = i >> 16;
 
980
    b[3] = i >> 24;
 
981
}
 
982
 
 
983
 
 
984
unsigned int
 
985
readUInt (const char buf[4])
 
986
{
 
987
    const unsigned char *b = (const unsigned char *) buf;
 
988
 
 
989
    return ( b[0]        & 0x000000ff) |
 
990
       ((b[1] <<  8) & 0x0000ff00) |
 
991
       ((b[2] << 16) & 0x00ff0000) |
 
992
       ((b[3] << 24) & 0xff000000);
 
993
}
 
994
 
 
995
} // namespace
 
996
 
 
997
 
 
998
//
 
999
// EXTERNAL INTERFACE
 
1000
//
 
1001
 
 
1002
 
 
1003
int
 
1004
hufCompress (const unsigned short raw[],
 
1005
         int nRaw,
 
1006
         char compressed[])
 
1007
{
 
1008
    if (nRaw == 0)
 
1009
    return 0;
 
1010
 
 
1011
    AutoArray <Int64, HUF_ENCSIZE> freq;
 
1012
 
 
1013
    countFrequencies (freq, raw, nRaw);
 
1014
 
 
1015
    int im, iM;
 
1016
    hufBuildEncTable (freq, &im, &iM);
 
1017
 
 
1018
    char *tableStart = compressed + 20;
 
1019
    char *tableEnd   = tableStart;
 
1020
    hufPackEncTable (freq, im, iM, &tableEnd);
 
1021
    int tableLength = tableEnd - tableStart;
 
1022
 
 
1023
    char *dataStart = tableEnd;
 
1024
    int nBits = hufEncode (freq, raw, nRaw, iM, dataStart);
 
1025
    int dataLength = (nBits + 7) / 8;
 
1026
 
 
1027
    writeUInt (compressed,      im);
 
1028
    writeUInt (compressed +  4, iM);
 
1029
    writeUInt (compressed +  8, tableLength);
 
1030
    writeUInt (compressed + 12, nBits);
 
1031
    writeUInt (compressed + 16, 0);     // room for future extensions
 
1032
 
 
1033
    return dataStart + dataLength - compressed;
 
1034
}
 
1035
 
 
1036
 
 
1037
void
 
1038
hufUncompress (const char compressed[],
 
1039
           int nCompressed,
 
1040
           unsigned short raw[],
 
1041
           int nRaw)
 
1042
{
 
1043
    if (nCompressed == 0)
 
1044
    {
 
1045
    if (nRaw != 0)
 
1046
        notEnoughData();
 
1047
 
 
1048
    return;
 
1049
    }
 
1050
 
 
1051
    int im = readUInt (compressed);
 
1052
    int iM = readUInt (compressed + 4);
 
1053
    // int tableLength = readUInt (compressed + 8);
 
1054
    int nBits = readUInt (compressed + 12);
 
1055
 
 
1056
    if (im < 0 || im >= HUF_ENCSIZE || iM < 0 || iM >= HUF_ENCSIZE)
 
1057
    invalidTableSize();
 
1058
 
 
1059
    const char *ptr = compressed + 20;
 
1060
 
 
1061
    AutoArray <Int64, HUF_ENCSIZE> freq;
 
1062
    AutoArray <HufDec, HUF_DECSIZE> hdec;
 
1063
 
 
1064
    hufClearDecTable (hdec);
 
1065
 
 
1066
    hufUnpackEncTable (&ptr, nCompressed - (ptr - compressed), im, iM, freq);
 
1067
 
 
1068
    try
 
1069
    {
 
1070
    if (nBits > 8 * (nCompressed - (ptr - compressed)))
 
1071
        invalidNBits();
 
1072
 
 
1073
    hufBuildDecTable (freq, im, iM, hdec);
 
1074
    hufDecode (freq, hdec, ptr, nBits, iM, nRaw, raw);
 
1075
    }
 
1076
    catch (...)
 
1077
    {
 
1078
    hufFreeDecTable (hdec);
 
1079
    throw;
 
1080
    }
 
1081
 
 
1082
    hufFreeDecTable (hdec);
 
1083
}
 
1084
 
 
1085
 
 
1086
} // namespace Imf