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 : #include <algorithm>
25 : #include <cassert>
26 : #include "Defines.h"
27 : #include "BitStuffer2.h"
28 :
29 : using namespace std;
30 : USING_NAMESPACE_LERC
31 :
32 : // -------------------------------------------------------------------------- ;
33 :
34 : // if you change Encode(...) / Decode(...), don't forget to update ComputeNumBytesNeeded(...)
35 :
36 42549 : bool BitStuffer2::EncodeSimple(Byte** ppByte, const vector<unsigned int>& dataVec, int lerc2Version) const
37 : {
38 42549 : if (!ppByte || dataVec.empty())
39 0 : return false;
40 :
41 42549 : unsigned int maxElem = *max_element(dataVec.begin(), dataVec.end());
42 42549 : int numBits = 0;
43 150067 : while ((numBits < 32) && (maxElem >> numBits))
44 107518 : numBits++;
45 :
46 42549 : if (numBits >= 32)
47 0 : return false;
48 :
49 42549 : Byte numBitsByte = (Byte)numBits;
50 42549 : unsigned int numElements = (unsigned int)dataVec.size();
51 42549 : unsigned int numUInts = (numElements * numBits + 31) / 32;
52 :
53 : // use the upper 2 bits to encode the type used for numElements: Byte, ushort, or uint
54 42549 : int n = NumBytesUInt(numElements);
55 42549 : int bits67 = (n == 4) ? 0 : 3 - n;
56 42549 : numBitsByte |= bits67 << 6;
57 :
58 : // bit5 = 0 means simple mode
59 :
60 42549 : **ppByte = numBitsByte;
61 42549 : (*ppByte)++;
62 :
63 42549 : if (!EncodeUInt(ppByte, numElements, n))
64 0 : return false;
65 :
66 42549 : if (numUInts > 0) // numBits can be 0, then we only write the header
67 : {
68 42549 : if (lerc2Version >= 3)
69 18287 : BitStuff(ppByte, dataVec, numBits);
70 : else
71 24262 : BitStuff_Before_Lerc2v3(ppByte, dataVec, numBits);
72 : }
73 :
74 42549 : return true;
75 : }
76 :
77 : // -------------------------------------------------------------------------- ;
78 :
79 220916 : bool BitStuffer2::EncodeLut(Byte** ppByte, const vector<pair<unsigned int, unsigned int> >& sortedDataVec, int lerc2Version) const
80 : {
81 220916 : if (!ppByte || sortedDataVec.empty())
82 0 : return false;
83 :
84 220916 : if (sortedDataVec[0].first != 0) // corresponds to min
85 0 : return false;
86 :
87 : // collect the different values for the lut
88 220916 : unsigned int numElem = (unsigned int)sortedDataVec.size();
89 220916 : unsigned int indexLut = 0;
90 :
91 220916 : m_tmpLutVec.resize(0); // omit the 0 throughout that corresponds to min
92 220916 : m_tmpIndexVec.assign(numElem, 0);
93 :
94 14708400 : for (unsigned int i = 1; i < numElem; i++)
95 : {
96 14487500 : unsigned int prev = sortedDataVec[i - 1].first;
97 14487500 : m_tmpIndexVec[sortedDataVec[i - 1].second] = indexLut;
98 :
99 14487500 : if (sortedDataVec[i].first != prev)
100 : {
101 320862 : m_tmpLutVec.push_back(sortedDataVec[i].first);
102 320862 : indexLut++;
103 : }
104 : }
105 220916 : m_tmpIndexVec[sortedDataVec[numElem - 1].second] = indexLut; // don't forget the last one
106 :
107 : // write first 2 data elements same as simple, but bit5 set to 1
108 220916 : unsigned int maxElem = m_tmpLutVec.back();
109 220916 : int numBits = 0;
110 1182940 : while ((numBits < 32) && (maxElem >> numBits))
111 962025 : numBits++;
112 :
113 220916 : if (numBits >= 32)
114 0 : return false;
115 :
116 220916 : Byte numBitsByte = (Byte)numBits;
117 :
118 : // use the upper 2 bits to encode the type used for numElem: byte, ushort, or uint
119 220916 : int n = NumBytesUInt(numElem);
120 220916 : int bits67 = (n == 4) ? 0 : 3 - n;
121 220916 : numBitsByte |= bits67 << 6;
122 :
123 220916 : numBitsByte |= (1 << 5); // bit 5 = 1 means lut mode
124 :
125 220916 : **ppByte = numBitsByte;
126 220916 : (*ppByte)++;
127 :
128 220916 : if (!EncodeUInt(ppByte, numElem, n)) // numElements = numIndexes to lut
129 0 : return false;
130 :
131 220916 : unsigned int nLut = (unsigned int)m_tmpLutVec.size();
132 220916 : if (nLut < 1 || nLut >= 255)
133 0 : return false;
134 :
135 220916 : **ppByte = (Byte)nLut + 1; // size of lut, incl the 0
136 220916 : (*ppByte)++;
137 :
138 220916 : if (lerc2Version >= 3)
139 1112 : BitStuff(ppByte, m_tmpLutVec, numBits); // lut
140 : else
141 219804 : BitStuff_Before_Lerc2v3(ppByte, m_tmpLutVec, numBits);
142 :
143 220916 : int nBitsLut = 0;
144 496289 : while (nLut >> nBitsLut) // indexes are in [0 .. nLut]
145 275373 : nBitsLut++;
146 :
147 220916 : if (lerc2Version >= 3)
148 1112 : BitStuff(ppByte, m_tmpIndexVec, nBitsLut); // indexes
149 : else
150 219804 : BitStuff_Before_Lerc2v3(ppByte, m_tmpIndexVec, nBitsLut);
151 :
152 220916 : return true;
153 : }
154 :
155 : // -------------------------------------------------------------------------- ;
156 :
157 : // if you change Encode(...) / Decode(...), don't forget to update ComputeNumBytesNeeded(...)
158 :
159 113518 : bool BitStuffer2::Decode(const Byte** ppByte, size_t& nBytesRemaining, vector<unsigned int>& dataVec, size_t maxElementCount, int lerc2Version) const
160 : {
161 113518 : if (!ppByte || nBytesRemaining < 1)
162 0 : return false;
163 :
164 113518 : Byte numBitsByte = **ppByte;
165 113518 : (*ppByte)++;
166 113518 : nBytesRemaining--;
167 :
168 113518 : int bits67 = numBitsByte >> 6;
169 113518 : int nb = (bits67 == 0) ? 4 : 3 - bits67;
170 :
171 113518 : bool doLut = (numBitsByte & (1 << 5)) ? true : false; // bit 5
172 113518 : numBitsByte &= 31; // bits 0-4;
173 113518 : int numBits = numBitsByte;
174 :
175 113518 : unsigned int numElements = 0;
176 113518 : if (!DecodeUInt(ppByte, nBytesRemaining, numElements, nb))
177 0 : return false;
178 113518 : if (numElements > maxElementCount)
179 0 : return false;
180 :
181 113518 : if (!doLut)
182 : {
183 38554 : if (numBits > 0) // numBits can be 0
184 : {
185 38554 : if (lerc2Version >= 3)
186 : {
187 30346 : if (!BitUnStuff(ppByte, nBytesRemaining, dataVec, numElements, numBits))
188 0 : return false;
189 : }
190 : else
191 : {
192 8208 : if (!BitUnStuff_Before_Lerc2v3(ppByte, nBytesRemaining, dataVec, numElements, numBits))
193 0 : return false;
194 : }
195 : }
196 : }
197 : else
198 : {
199 74964 : if (numBits == 0) // fail gracefully in case of corrupted blob for old version <= 2 which had no checksum
200 0 : return false;
201 74964 : if (nBytesRemaining < 1)
202 0 : return false;
203 :
204 74964 : Byte nLutByte = **ppByte;
205 74964 : (*ppByte)++;
206 74964 : nBytesRemaining--;
207 :
208 74964 : int nLut = nLutByte - 1;
209 :
210 : // unstuff lut w/o the 0
211 74964 : if (lerc2Version >= 3)
212 : {
213 982 : if (!BitUnStuff(ppByte, nBytesRemaining, m_tmpLutVec, nLut, numBits))
214 0 : return false;
215 : }
216 : else
217 : {
218 73982 : if (!BitUnStuff_Before_Lerc2v3(ppByte, nBytesRemaining, m_tmpLutVec, nLut, numBits))
219 0 : return false;
220 : }
221 :
222 74964 : int nBitsLut = 0;
223 169423 : while (nLut >> nBitsLut)
224 94459 : nBitsLut++;
225 74964 : if (nBitsLut == 0)
226 0 : return false;
227 :
228 74964 : if (lerc2Version >= 3)
229 : {
230 : // unstuff indexes
231 982 : if (!BitUnStuff(ppByte, nBytesRemaining, dataVec, numElements, nBitsLut))
232 0 : return false;
233 :
234 : // replace indexes by values
235 982 : m_tmpLutVec.insert(m_tmpLutVec.begin(), 0); // put back in the 0
236 61462 : for (unsigned int i = 0; i < numElements; i++)
237 : {
238 : #ifdef GDAL_COMPILATION
239 60480 : if (dataVec[i] >= m_tmpLutVec.size())
240 0 : return false;
241 : #endif
242 60480 : dataVec[i] = m_tmpLutVec[dataVec[i]];
243 : }
244 : }
245 : else
246 : {
247 : // unstuff indexes
248 73982 : if (!BitUnStuff_Before_Lerc2v3(ppByte, nBytesRemaining, dataVec, numElements, nBitsLut))
249 0 : return false;
250 :
251 : // replace indexes by values
252 73982 : m_tmpLutVec.insert(m_tmpLutVec.begin(), 0); // put back in the 0
253 4992960 : for (unsigned int i = 0; i < numElements; i++)
254 : {
255 4918980 : if (dataVec[i] >= m_tmpLutVec.size())
256 0 : return false;
257 :
258 4918980 : dataVec[i] = m_tmpLutVec[dataVec[i]];
259 : }
260 : }
261 : }
262 :
263 113518 : return true;
264 : }
265 :
266 : // -------------------------------------------------------------------------- ;
267 :
268 709569 : unsigned int BitStuffer2::ComputeNumBytesNeededLut(const vector<pair<unsigned int, unsigned int> >& sortedDataVec, bool& doLut)
269 : {
270 709569 : unsigned int maxElem = sortedDataVec.back().first;
271 709569 : unsigned int numElem = (unsigned int)sortedDataVec.size();
272 :
273 709569 : int numBits = 0;
274 3591790 : while ((numBits < 32) && (maxElem >> numBits))
275 2882220 : numBits++;
276 709569 : unsigned int numBytes = 1 + NumBytesUInt(numElem) + ((numElem * numBits + 7) >> 3);
277 :
278 : // go through and count how often the value changes
279 709569 : int nLut = 0;
280 71172000 : for (unsigned int i = 1; i < numElem; i++)
281 70462500 : if (sortedDataVec[i].first != sortedDataVec[i - 1].first)
282 1145300 : nLut++;
283 :
284 709569 : int nBitsLut = 0;
285 1655040 : while (nLut >> nBitsLut)
286 945475 : nBitsLut++;
287 :
288 709569 : unsigned int numBitsTotalLut = nLut * numBits; // num bits w/o the 0
289 709569 : unsigned int numBytesLut = 1 + NumBytesUInt(numElem) + 1 + ((numBitsTotalLut + 7) >> 3) + ((numElem * nBitsLut + 7) >> 3);
290 :
291 709569 : doLut = numBytesLut < numBytes;
292 709569 : return min(numBytesLut, numBytes);
293 : }
294 :
295 : // -------------------------------------------------------------------------- ;
296 : // -------------------------------------------------------------------------- ;
297 :
298 463870 : void BitStuffer2::BitStuff_Before_Lerc2v3(Byte** ppByte, const vector<unsigned int>& dataVec, int numBits)
299 : {
300 463870 : unsigned int numElements = (unsigned int)dataVec.size();
301 463870 : unsigned int numUInts = (numElements * numBits + 31) / 32;
302 463870 : unsigned int numBytes = numUInts * sizeof(unsigned int);
303 463870 : unsigned int* arr = (unsigned int*)(*ppByte);
304 :
305 463870 : memset(arr, 0, numBytes);
306 :
307 : // do the stuffing
308 463870 : const unsigned int* srcPtr = &dataVec[0];
309 463870 : unsigned int* dstPtr = arr;
310 463870 : int bitPos = 0;
311 :
312 17363600 : for (unsigned int i = 0; i < numElements; i++)
313 : {
314 16899800 : if (32 - bitPos >= numBits)
315 : {
316 : unsigned int dstValue;
317 16897100 : memcpy(&dstValue, dstPtr, sizeof(unsigned int));
318 16897100 : dstValue |= (*srcPtr++) << (32 - bitPos - numBits);
319 16897100 : memcpy(dstPtr, &dstValue, sizeof(unsigned int));
320 16897100 : bitPos += numBits;
321 16897100 : if (bitPos == 32) // shift >= 32 is undefined
322 : {
323 641691 : bitPos = 0;
324 641691 : dstPtr++;
325 : }
326 : }
327 : else
328 : {
329 : unsigned int dstValue;
330 2634 : int n = numBits - (32 - bitPos);
331 2634 : memcpy(&dstValue, dstPtr, sizeof(unsigned int));
332 2634 : dstValue |= (*srcPtr) >> n;
333 2634 : memcpy(dstPtr, &dstValue, sizeof(unsigned int));
334 2634 : dstPtr++;
335 2634 : memcpy(&dstValue, dstPtr, sizeof(unsigned int));
336 2634 : dstValue |= (*srcPtr++) << (32 - n);
337 2634 : memcpy(dstPtr, &dstValue, sizeof(unsigned int));
338 2634 : bitPos = n;
339 : }
340 : }
341 :
342 : // save the 0-3 bytes not used in the last UInt
343 463870 : unsigned int numBytesNotNeeded = NumTailBytesNotNeeded(numElements, numBits);
344 463870 : unsigned int n = numBytesNotNeeded;
345 1060330 : for (; n; --n)
346 : {
347 : unsigned int dstValue;
348 596462 : memcpy(&dstValue, dstPtr, sizeof(unsigned int));
349 596462 : dstValue >>= 8;
350 596462 : memcpy(dstPtr, &dstValue, sizeof(unsigned int));
351 : }
352 :
353 463870 : *ppByte += numBytes - numBytesNotNeeded;
354 463870 : }
355 :
356 : // -------------------------------------------------------------------------- ;
357 :
358 156172 : bool BitStuffer2::BitUnStuff_Before_Lerc2v3(const Byte** ppByte, size_t& nBytesRemaining,
359 : vector<unsigned int>& dataVec, unsigned int numElements, int numBits) const
360 : {
361 156172 : if (numElements == 0 || numBits >= 32)
362 0 : return false;
363 156172 : unsigned long long numUIntsLL = ((unsigned long long)numElements * numBits + 31) / 32;
364 156172 : unsigned long long numBytesLL = numUIntsLL * sizeof(unsigned int);
365 156172 : size_t numBytes = (size_t)numBytesLL; // could theoretically overflow on 32 bit system
366 156172 : size_t numUInts = (size_t)numUIntsLL;
367 156172 : unsigned int ntbnn = NumTailBytesNotNeeded(numElements, numBits);
368 156172 : if (numBytes != numBytesLL || nBytesRemaining + ntbnn < numBytes)
369 0 : return false;
370 :
371 : try
372 : {
373 156172 : dataVec.resize(numElements, 0); // init with 0
374 156172 : m_tmpBitStuffVec.resize(numUInts);
375 : }
376 0 : catch( const std::exception& )
377 : {
378 0 : return false;
379 : }
380 :
381 156172 : m_tmpBitStuffVec[numUInts - 1] = 0; // set last uint to 0
382 :
383 156172 : unsigned int nBytesToCopy = (numElements * numBits + 7) / 8;
384 156172 : memcpy(&m_tmpBitStuffVec[0], *ppByte, nBytesToCopy);
385 :
386 156172 : unsigned int* pLastULong = &m_tmpBitStuffVec[numUInts - 1];
387 356374 : while (ntbnn)
388 : {
389 200202 : -- ntbnn;
390 200202 : *pLastULong <<= 8;
391 : }
392 :
393 156172 : unsigned int* srcPtr = &m_tmpBitStuffVec[0];
394 156172 : unsigned int* dstPtr = &dataVec[0];
395 156172 : int bitPos = 0;
396 :
397 5855250 : for (unsigned int i = 0; i < numElements; i++)
398 : {
399 5699080 : if (32 - bitPos >= numBits)
400 : {
401 : unsigned int val;
402 5697570 : memcpy(&val, srcPtr, sizeof(unsigned int));
403 5697570 : unsigned int n = val << bitPos;
404 5697570 : *dstPtr++ = n >> (32 - numBits);
405 5697570 : bitPos += numBits;
406 :
407 5697570 : if (bitPos == 32) // shift >= 32 is undefined
408 : {
409 216619 : bitPos = 0;
410 216619 : srcPtr++;
411 : }
412 : }
413 : else
414 : {
415 : unsigned int val;
416 1511 : memcpy(&val, srcPtr, sizeof(unsigned int));
417 1511 : srcPtr++;
418 1511 : unsigned int n = val << bitPos;
419 1511 : *dstPtr = n >> (32 - numBits);
420 1511 : bitPos -= (32 - numBits);
421 1511 : memcpy(&val, srcPtr, sizeof(unsigned int));
422 1511 : *dstPtr++ |= val >> (32 - bitPos);
423 : }
424 : }
425 :
426 156172 : *ppByte += nBytesToCopy;
427 156172 : nBytesRemaining -= nBytesToCopy;
428 :
429 156172 : return true;
430 : }
431 :
432 : // -------------------------------------------------------------------------- ;
433 :
434 : // starting with version Lerc2v3: integer >> into local uint buffer, plus final memcpy
435 :
436 20511 : void BitStuffer2::BitStuff(Byte** ppByte, const vector<unsigned int>& dataVec, int numBits) const
437 : {
438 20511 : unsigned int numElements = (unsigned int)dataVec.size();
439 20511 : unsigned int numUInts = (numElements * numBits + 31) / 32;
440 20511 : unsigned int numBytes = numUInts * sizeof(unsigned int);
441 :
442 20511 : m_tmpBitStuffVec.resize(numUInts);
443 20511 : unsigned int* dstPtr = &m_tmpBitStuffVec[0];
444 :
445 20511 : memset(dstPtr, 0, numBytes);
446 :
447 : // do the stuffing
448 20511 : const unsigned int* srcPtr = &dataVec[0];
449 20511 : int bitPos = 0;
450 20511 : assert(numBits <= 32); // to avoid coverity warning about large shift a bit later, when doing (*srcPtr++) >> (32 - bitPos)
451 :
452 1354360 : for (unsigned int i = 0; i < numElements; i++)
453 : {
454 1333850 : if (32 - bitPos >= numBits)
455 : {
456 1253970 : *dstPtr |= (*srcPtr++) << bitPos;
457 1253970 : bitPos += numBits;
458 1253970 : if (bitPos == 32) // shift >= 32 is undefined
459 : {
460 97956 : dstPtr++;
461 97956 : bitPos = 0;
462 : }
463 : }
464 : else
465 : {
466 79880 : *dstPtr++ |= (*srcPtr) << bitPos;
467 79880 : *dstPtr |= (*srcPtr++) >> (32 - bitPos);
468 79880 : bitPos += numBits - 32;
469 : }
470 : }
471 :
472 : // copy the bytes to the outgoing byte stream
473 20511 : size_t numBytesUsed = numBytes - NumTailBytesNotNeeded(numElements, numBits);
474 : #ifdef CSA_BUILD
475 : assert( numElements );
476 : #endif
477 20511 : memcpy(*ppByte, m_tmpBitStuffVec.data(), numBytesUsed);
478 :
479 20511 : *ppByte += numBytesUsed;
480 20511 : }
481 :
482 : // -------------------------------------------------------------------------- ;
483 :
484 32310 : bool BitStuffer2::BitUnStuff(const Byte** ppByte, size_t& nBytesRemaining, vector<unsigned int>& dataVec,
485 : unsigned int numElements, int numBits) const
486 : {
487 32310 : if (numElements == 0 || numBits >= 32)
488 0 : return false;
489 32310 : unsigned long long numUIntsLL = ((unsigned long long)numElements * numBits + 31) / 32;
490 32310 : unsigned long long numBytesLL = numUIntsLL * sizeof(unsigned int);
491 32310 : size_t numBytes = (size_t)numBytesLL; // could theoretically overflow on 32 bit system
492 32310 : if (numBytes != numBytesLL)
493 0 : return false;
494 32310 : size_t numUInts = (size_t)numUIntsLL;
495 :
496 : // copy the bytes from the incoming byte stream
497 32310 : const size_t numBytesUsed = numBytes - NumTailBytesNotNeeded(numElements, numBits);
498 :
499 32310 : if (nBytesRemaining < numBytesUsed)
500 0 : return false;
501 :
502 : try
503 : {
504 32310 : dataVec.resize(numElements);
505 : }
506 0 : catch( const std::exception& )
507 : {
508 0 : return false;
509 : }
510 :
511 : try
512 : {
513 32310 : m_tmpBitStuffVec.resize(numUInts);
514 : }
515 0 : catch( const std::exception& )
516 : {
517 0 : return false;
518 : }
519 :
520 32310 : m_tmpBitStuffVec[numUInts - 1] = 0; // set last uint to 0
521 :
522 32310 : memcpy(&m_tmpBitStuffVec[0], *ppByte, numBytesUsed);
523 :
524 : // do the un-stuffing
525 32310 : unsigned int* srcPtr = &m_tmpBitStuffVec[0];
526 32310 : unsigned int* dstPtr = &dataVec[0];
527 32310 : int bitPos = 0;
528 32310 : int nb = 32 - numBits;
529 :
530 2089430 : for (unsigned int i = 0; i < numElements; i++)
531 : {
532 2057120 : if (nb - bitPos >= 0)
533 : {
534 1948520 : *dstPtr++ = ((*srcPtr) << (nb - bitPos)) >> nb;
535 1948520 : bitPos += numBits;
536 1948520 : if (bitPos == 32) // shift >= 32 is undefined
537 : {
538 159164 : srcPtr++;
539 159164 : bitPos = 0;
540 : }
541 : }
542 : else
543 : {
544 108600 : *dstPtr = (*srcPtr++) >> bitPos;
545 108600 : *dstPtr++ |= ((*srcPtr) << (64 - numBits - bitPos)) >> nb;
546 108600 : bitPos -= nb;
547 : }
548 : }
549 :
550 32310 : *ppByte += numBytesUsed;
551 32310 : nBytesRemaining -= numBytesUsed;
552 32310 : return true;
553 : }
554 :
555 : // -------------------------------------------------------------------------- ;
556 :
|
