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 <cassert>
29 : #include <cstring>
30 : #include <utility>
31 : #include "Defines.h"
32 :
33 : NAMESPACE_LERC_START
34 :
35 : class Huffman
36 : {
37 : public:
38 7811 : Huffman() : m_maxHistoSize(1 << 15), m_maxNumBitsLUT(12), m_numBitsToSkipInTree(0), m_root(nullptr) {}
39 7811 : ~Huffman() { Clear(); }
40 :
41 : // Limitation: We limit the max Huffman code length to 32 bit. If this happens, the function ComputeCodes()
42 : // returns false. In that case don't use Huffman coding but Lerc only instead.
43 : // This won't happen easily. For the worst case input maximizing the Huffman code length the counts in the
44 : // histogram have to follow the Fibonacci sequence. Even then, for < 9,227,465 data values, 32 bit is
45 : // the max Huffman code length possible.
46 :
47 : bool ComputeCodes(const std::vector<int>& histo); // input histogram, size < 2^15
48 :
49 : bool ComputeCompressedSize(const std::vector<int>& histo, int& numBytes, double& avgBpp) const;
50 :
51 : // LUT of same size as histogram, each entry has length of Huffman bit code, and the bit code
52 3327 : const std::vector<std::pair<unsigned short, unsigned int> >& GetCodes() const { return m_codeTable; }
53 : bool SetCodes(const std::vector<std::pair<unsigned short, unsigned int> >& codeTable);
54 :
55 : bool WriteCodeTable(Byte** ppByte, int lerc2Version) const;
56 : bool ReadCodeTable(const Byte** ppByte, size_t& nBytesRemaining, int lerc2Version);
57 :
58 : bool BuildTreeFromCodes(int& numBitsLUT);
59 : inline bool DecodeOneValue(const Byte** ppSrc, size_t& nBytesRemaining, int& bitPos, int numBitsLUT, int& value) const;
60 : inline static bool PushValue(Byte** ppByte, int& bitPos, unsigned int value, int len);
61 : void Clear();
62 :
63 : private:
64 :
65 : struct Node
66 : {
67 : int weight;
68 : short value;
69 : Node *child0, *child1;
70 :
71 124239 : Node(short val, int cnt) // new leaf node for val
72 124239 : {
73 124239 : value = val;
74 124239 : weight = -cnt;
75 124239 : child0 = child1 = nullptr;
76 124239 : }
77 :
78 120664 : Node(Node* c0, Node* c1) // new internal node from children c0 and c1
79 120664 : {
80 120664 : value = -1;
81 120664 : weight = c0->weight + c1->weight;
82 120664 : child0 = c0;
83 120664 : child1 = c1;
84 120664 : }
85 :
86 1472780 : bool operator < (const Node& other) const { return weight < other.weight; }
87 :
88 244863 : bool TreeToLUT(unsigned short numBits, unsigned int bits, std::vector<std::pair<unsigned short, unsigned int> >& luTable) const
89 : {
90 244863 : if (child0)
91 : {
92 241332 : if (numBits == 32 // the max huffman code length we allow
93 120666 : || !child0->TreeToLUT(numBits + 1, (bits << 1) + 0, luTable)
94 241332 : || !child1->TreeToLUT(numBits + 1, (bits << 1) + 1, luTable))
95 : {
96 0 : return false;
97 : }
98 : }
99 : else
100 124197 : luTable[value] = std::pair<unsigned short, unsigned int>(numBits, bits);
101 :
102 244863 : return true;
103 : }
104 :
105 247250 : void FreeTree(int& n)
106 : {
107 247250 : if (child0)
108 : {
109 121864 : child0->FreeTree(n);
110 121864 : delete child0;
111 121864 : child0 = nullptr;
112 121864 : n--;
113 : }
114 247250 : if (child1)
115 : {
116 121813 : child1->FreeTree(n);
117 121813 : delete child1;
118 121813 : child1 = nullptr;
119 121813 : n--;
120 : }
121 247250 : }
122 : };
123 :
124 : private:
125 :
126 : size_t m_maxHistoSize;
127 : std::vector<std::pair<unsigned short, unsigned int> > m_codeTable;
128 : std::vector<std::pair<short, short> > m_decodeLUT;
129 : int m_maxNumBitsLUT;
130 : int m_numBitsToSkipInTree;
131 : Node* m_root;
132 :
133 1608160 : static int GetIndexWrapAround(int i, int size) { return i - (i < size ? 0 : size); }
134 :
135 : bool ComputeNumBytesCodeTable(int& numBytes) const;
136 : bool GetRange(int& i0, int& i1, int& maxCodeLength) const;
137 : bool BitStuffCodes(Byte** ppByte, int i0, int i1) const;
138 : bool BitUnStuffCodes(const Byte** ppByte, size_t& nBytesRemaining, int i0, int i1);
139 : bool ConvertCodesToCanonical();
140 : void ClearTree();
141 : };
142 :
143 : // -------------------------------------------------------------------------- ;
144 :
145 4896130 : inline bool Huffman::DecodeOneValue(const Byte** ppSrc, size_t& nBytesRemaining, int& bitPos, int numBitsLUT, int& value) const
146 : {
147 4896130 : const size_t s4 = sizeof(unsigned int);
148 :
149 4896130 : if (!ppSrc || !(*ppSrc) || bitPos < 0 || bitPos >= 32 || nBytesRemaining < s4)
150 0 : return false;
151 :
152 : // first get the next (up to) 12 bits as a copy
153 4897350 : unsigned int temp(0);
154 4897350 : memcpy(&temp, *ppSrc, s4);
155 4897350 : int valTmp = (temp << bitPos) >> (32 - numBitsLUT);
156 :
157 4897350 : if (32 - bitPos < numBitsLUT)
158 : {
159 1334730 : if (nBytesRemaining < 2 * s4)
160 0 : return false;
161 :
162 1334730 : memcpy(&temp, *ppSrc + s4, s4);
163 1334730 : valTmp |= temp >> (64 - bitPos - numBitsLUT);
164 : }
165 :
166 4897350 : if (m_decodeLUT[valTmp].first >= 0) // if there, move the correct number of bits and done
167 : {
168 4895460 : value = m_decodeLUT[valTmp].second;
169 4895110 : bitPos += m_decodeLUT[valTmp].first;
170 4894200 : if (bitPos >= 32)
171 : {
172 433483 : bitPos -= 32;
173 433483 : *ppSrc += s4;
174 433483 : nBytesRemaining -= s4;
175 : }
176 4894200 : return true;
177 : }
178 :
179 : // if not there, go through the tree (slower)
180 :
181 2284 : if (!m_root)
182 0 : return false;
183 :
184 : // skip leading 0 bits before entering the tree
185 2284 : bitPos += m_numBitsToSkipInTree;
186 2284 : if (bitPos >= 32)
187 : {
188 507 : bitPos -= 32;
189 507 : *ppSrc += s4;
190 507 : nBytesRemaining -= s4;
191 : }
192 :
193 2284 : const Node* node = m_root;
194 2284 : value = -1;
195 16264 : while (value < 0 && nBytesRemaining >= s4)
196 : {
197 13980 : memcpy(&temp, *ppSrc, s4);
198 13980 : int bit = (temp << bitPos) >> 31;
199 13980 : bitPos++;
200 13980 : if (bitPos == 32)
201 : {
202 435 : bitPos = 0;
203 435 : *ppSrc += s4;
204 435 : nBytesRemaining -= s4;
205 : }
206 :
207 13980 : node = bit ? node->child1 : node->child0;
208 13980 : if (!node)
209 0 : return false;
210 :
211 13980 : if (node->value >= 0) // reached a leaf node
212 2284 : value = node->value;
213 : }
214 :
215 2284 : return (value >= 0);
216 : }
217 :
218 : // -------------------------------------------------------------------------- ;
219 :
220 9335600 : inline bool Huffman::PushValue(Byte** ppByte, int& bitPos, unsigned int value, int len)
221 : {
222 9335600 : const size_t s4 = sizeof(unsigned int);
223 :
224 9335600 : if (!ppByte || !(*ppByte) || bitPos < 0 || bitPos >= 32 || len < 0 || len > 32)
225 0 : return false;
226 :
227 9335610 : if (32 - bitPos >= len)
228 : {
229 9076220 : if (bitPos == 0)
230 292988 : memset(*ppByte, 0, s4);
231 :
232 9076220 : unsigned int temp(0);
233 9076220 : memcpy(&temp, *ppByte, s4);
234 9076220 : temp |= value << (32 - bitPos - len);
235 9076220 : memcpy(*ppByte, &temp, s4);
236 :
237 9076220 : bitPos += len;
238 9076220 : if (bitPos == 32)
239 : {
240 291737 : bitPos = 0;
241 291737 : *ppByte += s4;
242 : }
243 : }
244 : else
245 : {
246 259384 : bitPos += len - 32;
247 259384 : assert(bitPos >= 0); // to make Coverity Scan happy
248 259384 : unsigned int temp(0);
249 259384 : memcpy(&temp, *ppByte, s4);
250 259384 : temp |= value >> bitPos;
251 259384 : memcpy(*ppByte, &temp, s4);
252 259384 : *ppByte += s4;
253 259384 : temp = value << (32 - bitPos);
254 259384 : memcpy(*ppByte, &temp, s4);
255 : }
256 :
257 9335610 : return true;
258 : }
259 :
260 : // -------------------------------------------------------------------------- ;
261 :
262 : NAMESPACE_LERC_END
263 : #endif
|
