Line data Source code
1 : /*
2 : Copyright 2015 Esri
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 express or implied.
13 : See the License for the specific language governing permissions and
14 : limitations under the License.
15 :
16 : A local copy of the license and additional notices are located with the
17 : source distribution at:
18 :
19 : http://github.com/Esri/lerc/
20 :
21 : Contributors: Thomas Maurer
22 : */
23 :
24 : #ifndef HUFFMAN_H
25 : #define HUFFMAN_H
26 :
27 : #include <vector>
28 : #include <cstring>
29 : #include <utility>
30 : #include "Defines.h"
31 :
32 : NAMESPACE_LERC_START
33 :
34 : class Huffman
35 : {
36 : public:
37 7703 : Huffman() : m_maxHistoSize(1 << 15), m_maxNumBitsLUT(12), m_numBitsToSkipInTree(0), m_root(nullptr) {}
38 7703 : ~Huffman() { Clear(); }
39 :
40 : // Limitation: We limit the max Huffman code length to 32 bit. If this happens, the function ComputeCodes()
41 : // returns false. In that case don't use Huffman coding but Lerc only instead.
42 : // This won't happen easily. For the worst case input maximizing the Huffman code length the counts in the
43 : // histogram have to follow the Fibonacci sequence. Even then, for < 9,227,465 data values, 32 bit is
44 : // the max Huffman code length possible.
45 :
46 : bool ComputeCodes(const std::vector<int>& histo); // input histogram, size < 2^15
47 :
48 : bool ComputeCompressedSize(const std::vector<int>& histo, int& numBytes, double& avgBpp) const;
49 :
50 : // LUT of same size as histogram, each entry has length of Huffman bit code, and the bit code
51 3327 : const std::vector<std::pair<unsigned short, unsigned int> >& GetCodes() const { return m_codeTable; }
52 : bool SetCodes(const std::vector<std::pair<unsigned short, unsigned int> >& codeTable);
53 :
54 : bool WriteCodeTable(Byte** ppByte, int lerc2Version) const;
55 : bool ReadCodeTable(const Byte** ppByte, size_t& nBytesRemaining, int lerc2Version);
56 :
57 : bool BuildTreeFromCodes(int& numBitsLUT);
58 : bool DecodeOneValue(const unsigned int** ppSrc, size_t& nBytesRemaining, int& bitPos, int numBitsLUT, int& value) const;
59 : bool DecodeOneValue_NoOverrunCheck(const unsigned int** ppSrc, size_t& nBytesRemaining, int& bitPos, int numBitsLUT, int& value) const;
60 : void Clear();
61 :
62 : private:
63 :
64 : struct Node
65 : {
66 : int weight;
67 : short value;
68 : Node *child0, *child1;
69 :
70 124221 : Node(short val, int cnt) // new leaf node for val
71 124221 : {
72 124221 : value = val;
73 124221 : weight = -cnt;
74 124221 : child0 = child1 = nullptr;
75 124221 : }
76 :
77 120660 : Node(Node* c0, Node* c1) // new internal node from children c0 and c1
78 120660 : {
79 120660 : value = -1;
80 120660 : weight = c0->weight + c1->weight;
81 120660 : child0 = c0;
82 120660 : child1 = c1;
83 120660 : }
84 :
85 1472800 : bool operator < (const Node& other) const { return weight < other.weight; }
86 :
87 244760 : bool TreeToLUT(unsigned short numBits, unsigned int bits, std::vector<std::pair<unsigned short, unsigned int> >& luTable) const
88 : {
89 244760 : if (child0)
90 : {
91 241270 : if (numBits == 32 // the max huffman code length we allow
92 120638 : || !child0->TreeToLUT(numBits + 1, (bits << 1) + 0, luTable)
93 241263 : || !child1->TreeToLUT(numBits + 1, (bits << 1) + 1, luTable))
94 : {
95 0 : return false;
96 : }
97 : }
98 : else
99 124122 : luTable[value] = std::pair<unsigned short, unsigned int>(numBits, bits);
100 :
101 244768 : return true;
102 : }
103 :
104 246576 : void FreeTree(int& n)
105 : {
106 246576 : if (child0)
107 : {
108 121527 : child0->FreeTree(n);
109 121539 : delete child0;
110 121555 : child0 = nullptr;
111 121555 : n--;
112 : }
113 246604 : if (child1)
114 : {
115 121513 : child1->FreeTree(n);
116 121491 : delete child1;
117 121510 : child1 = nullptr;
118 121510 : n--;
119 : }
120 246601 : }
121 : };
122 :
123 : private:
124 :
125 : size_t m_maxHistoSize;
126 : std::vector<std::pair<unsigned short, unsigned int> > m_codeTable;
127 : std::vector<std::pair<short, short> > m_decodeLUT;
128 : int m_maxNumBitsLUT;
129 : int m_numBitsToSkipInTree;
130 : Node* m_root;
131 :
132 1520960 : static int GetIndexWrapAround(int i, int size) { return i - (i < size ? 0 : size); }
133 :
134 : bool ComputeNumBytesCodeTable(int& numBytes) const;
135 : bool GetRange(int& i0, int& i1, int& maxCodeLength) const;
136 : bool BitStuffCodes(Byte** ppByte, int i0, int i1) const;
137 : bool BitUnStuffCodes(const Byte** ppByte, size_t& nBytesRemaining, int i0, int i1);
138 : bool ConvertCodesToCanonical();
139 : void ClearTree();
140 : };
141 :
142 : // -------------------------------------------------------------------------- ;
143 :
144 10471 : inline bool Huffman::DecodeOneValue(const unsigned int** ppSrc, size_t& nBytesRemaining, int& bitPos, int numBitsLUT, int& value) const
145 : {
146 10471 : const size_t sizeUInt = sizeof(unsigned int);
147 :
148 10471 : if (!ppSrc || !(*ppSrc) || bitPos < 0 || bitPos >= 32 || nBytesRemaining < sizeUInt)
149 0 : return false;
150 :
151 : // first get the next (up to) 12 bits as a copy
152 10471 : int valTmp = ((**ppSrc) << bitPos) >> (32 - numBitsLUT);
153 10471 : if (32 - bitPos < numBitsLUT)
154 : {
155 1911 : if (nBytesRemaining < 2 * sizeUInt)
156 0 : return false;
157 :
158 1911 : valTmp |= (*(*ppSrc + 1)) >> (64 - bitPos - numBitsLUT);
159 : }
160 :
161 10471 : if (m_decodeLUT[valTmp].first >= 0) // if there, move the correct number of bits and done
162 : {
163 10471 : value = m_decodeLUT[valTmp].second;
164 10471 : bitPos += m_decodeLUT[valTmp].first;
165 10471 : if (bitPos >= 32)
166 : {
167 413 : bitPos -= 32;
168 413 : (*ppSrc)++;
169 413 : nBytesRemaining -= sizeUInt;
170 : }
171 10471 : return true;
172 : }
173 :
174 : // if not there, go through the tree (slower)
175 :
176 0 : if (!m_root)
177 0 : return false;
178 :
179 : // skip leading 0 bits before entering the tree
180 0 : bitPos += m_numBitsToSkipInTree;
181 0 : if (bitPos >= 32)
182 : {
183 0 : bitPos -= 32;
184 0 : (*ppSrc)++;
185 0 : nBytesRemaining -= sizeUInt;
186 : }
187 :
188 0 : const Node* node = m_root;
189 0 : value = -1;
190 0 : while (value < 0 && nBytesRemaining >= sizeUInt)
191 : {
192 0 : int bit = ((**ppSrc) << bitPos) >> 31;
193 0 : bitPos++;
194 0 : if (bitPos == 32)
195 : {
196 0 : bitPos = 0;
197 0 : (*ppSrc)++;
198 0 : nBytesRemaining -= sizeUInt;
199 : }
200 :
201 0 : node = bit ? node->child1 : node->child0;
202 0 : if (!node)
203 0 : return false;
204 :
205 0 : if (node->value >= 0) // reached a leaf node
206 0 : value = node->value;
207 : }
208 :
209 0 : return (value >= 0);
210 : }
211 :
212 : // -------------------------------------------------------------------------- ;
213 :
214 4660520 : inline bool Huffman::DecodeOneValue_NoOverrunCheck(const unsigned int** ppSrc, size_t& nBytesRemaining, int& bitPos, int numBitsLUT, int& value) const
215 : {
216 4660520 : const size_t sizeUInt = sizeof(unsigned int);
217 :
218 4660520 : if (!ppSrc || !(*ppSrc) || bitPos < 0 || bitPos >= 32)
219 0 : return false;
220 :
221 : // first get the next (up to) 12 bits as a copy
222 4661400 : int valTmp = ((**ppSrc) << bitPos) >> (32 - numBitsLUT);
223 4661400 : if (32 - bitPos < numBitsLUT)
224 : {
225 1263250 : valTmp |= (*(*ppSrc + 1)) >> (64 - bitPos - numBitsLUT);
226 : }
227 :
228 4661400 : if (m_decodeLUT[valTmp].first >= 0) // if there, move the correct number of bits and done
229 : {
230 4659320 : value = m_decodeLUT[valTmp].second;
231 4658560 : bitPos += m_decodeLUT[valTmp].first;
232 4658820 : if (bitPos >= 32)
233 : {
234 399168 : bitPos -= 32;
235 399168 : (*ppSrc)++;
236 399168 : nBytesRemaining -= sizeUInt;
237 : }
238 4658820 : return true;
239 : }
240 :
241 : // if not there, go through the tree (slower)
242 :
243 1984 : if (!m_root)
244 0 : return false;
245 :
246 : // skip leading 0 bits before entering the tree
247 1984 : bitPos += m_numBitsToSkipInTree;
248 1984 : if (bitPos >= 32)
249 : {
250 417 : bitPos -= 32;
251 417 : (*ppSrc)++;
252 417 : nBytesRemaining -= sizeUInt;
253 : }
254 :
255 1984 : const Node* node = m_root;
256 1984 : value = -1;
257 14464 : while (value < 0)
258 : {
259 12480 : int bit = ((**ppSrc) << bitPos) >> 31;
260 12480 : bitPos++;
261 12480 : if (bitPos == 32)
262 : {
263 405 : bitPos = 0;
264 405 : (*ppSrc)++;
265 405 : nBytesRemaining -= sizeUInt;
266 : }
267 :
268 12480 : node = bit ? node->child1 : node->child0;
269 12480 : if (!node)
270 0 : return false;
271 :
272 12480 : if (node->value >= 0) // reached a leaf node
273 1984 : value = node->value;
274 : }
275 :
276 1984 : return (value >= 0);
277 : }
278 :
279 : // -------------------------------------------------------------------------- ;
280 :
281 : NAMESPACE_LERC_END
282 : #endif
|
