1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
///////////////////////////////////////////////////////////////////////////
//
// Copyright (c) 2009-2014 DreamWorks Animation LLC.
//
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
// * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
// * Neither the name of DreamWorks Animation nor the names of
// its contributors may be used to endorse or promote products derived
// from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
///////////////////////////////////////////////////////////////////////////
#ifndef INCLUDED_IMF_FAST_HUF_H
#define INCLUDED_IMF_FAST_HUF_H
#include "ImfInt64.h"
#include "ImfNamespace.h"
OPENEXR_IMF_INTERNAL_NAMESPACE_HEADER_ENTER
//
// Alternative Canonical Huffman decoder:
//
// Canonical Huffman decoder based on 'On the Implementation of Minimum
// Redundancy Prefix Codes' by Moffat and Turpin - highly recommended
// reading as a good description of the problem space, as well as
// a fast decoding algorithm.
//
// The premise is that instead of working directly with the coded
// symbols, we create a new ordering based on the frequency of symbols.
// Less frequent symbols (and thus longer codes) are ordered earler.
// We're calling the values in this ordering 'Ids', as oppsed to
// 'Symbols' - which are the short values we eventually want decoded.
//
// With this new ordering, a few small tables can be derived ('base'
// and 'offset') which drive the decoding. To cut down on the
// linear scanning of these tables, you can add a small table
// to directly look up short codes (as you might in a traditional
// lookup-table driven decoder).
//
// The decoder is meant to be compatible with the encoder (and decoder)
// in ImfHuf.cpp, just faster. For ease of implementation, this decoder
// should only be used on compressed bitstreams >= 128 bits long.
//
class FastHufDecoder
{
public:
//
// Longest compressed code length that ImfHuf supports (58 bits)
//
static const int MAX_CODE_LEN = 58;
//
// Number of bits in our acceleration table. Should match all
// codes up to TABLE_LOOKUP_BITS in length.
//
static const int TABLE_LOOKUP_BITS = 12;
FastHufDecoder (const char*& table,
int numBytes,
int minSymbol,
int maxSymbol,
int rleSymbol);
~FastHufDecoder ();
static bool enabled ();
void decode (const unsigned char *src,
int numSrcBits,
unsigned short *dst,
int numDstElems);
private:
void buildTables (Int64*, Int64*);
void refill (Int64&, int, Int64&, int&, const unsigned char *&, int&);
Int64 readBits (int, Int64&, int&, const char *&);
int _rleSymbol; // RLE symbol written by the encoder.
// This could be 65536, so beware
// when you use shorts to hold things.
int _numSymbols; // Number of symbols in the codebook.
unsigned char _minCodeLength; // Minimum code length, in bits.
unsigned char _maxCodeLength; // Maximum code length, in bits.
int *_idToSymbol; // Maps Ids to symbols. Ids are a symbol
// ordering sorted first in terms of
// code length, and by code within
// the same length. Ids run from 0
// to mNumSymbols-1.
Int64 _ljBase[MAX_CODE_LEN + 1]; // the 'left justified base' table.
// Takes base[i] (i = code length)
// and 'left justifies' it into an Int64
Int64 _ljOffset[MAX_CODE_LEN +1 ]; // There are some other terms that can
// be folded into constants when taking
// the 'left justified' decode path. This
// holds those constants, indexed by
// code length
//
// We can accelerate the 'left justified' processing by running the
// top TABLE_LOOKUP_BITS through a LUT, to find the symbol and code
// length. These are those acceleration tables.
//
// Even though our evental 'symbols' are ushort's, the encoder adds
// a symbol to indicate RLE. So with a dense code book, we could
// have 2^16+1 codes, so both mIdToSymbol and mTableSymbol need
// to be bigger than 16 bits.
//
int _tableSymbol[1 << TABLE_LOOKUP_BITS];
unsigned char _tableCodeLen[1 << TABLE_LOOKUP_BITS];
Int64 _tableMin;
};
OPENEXR_IMF_INTERNAL_NAMESPACE_HEADER_EXIT
#endif
|
