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 : #if defined(__GNUC__)
236 : #pragma GCC diagnostic push
237 : #pragma GCC diagnostic ignored "-Wnull-dereference"
238 : #endif
239 982 : m_tmpLutVec.insert(m_tmpLutVec.begin(), 0); // put back in the 0
240 : #if defined(__GNUC__)
241 : #pragma GCC diagnostic pop
242 : #endif
243 61462 : for (unsigned int i = 0; i < numElements; i++)
244 : {
245 : #ifdef GDAL_COMPILATION
246 60480 : if (dataVec[i] >= m_tmpLutVec.size())
247 0 : return false;
248 : #endif
249 60480 : dataVec[i] = m_tmpLutVec[dataVec[i]];
250 : }
251 : }
252 : else
253 : {
254 : // unstuff indexes
255 73982 : if (!BitUnStuff_Before_Lerc2v3(ppByte, nBytesRemaining, dataVec, numElements, nBitsLut))
256 0 : return false;
257 :
258 : // replace indexes by values
259 : #if defined(__GNUC__)
260 : #pragma GCC diagnostic push
261 : #pragma GCC diagnostic ignored "-Wnull-dereference"
262 : #endif
263 73982 : m_tmpLutVec.insert(m_tmpLutVec.begin(), 0); // put back in the 0
264 : #if defined(__GNUC__)
265 : #pragma GCC diagnostic pop
266 : #endif
267 4992960 : for (unsigned int i = 0; i < numElements; i++)
268 : {
269 4918980 : if (dataVec[i] >= m_tmpLutVec.size())
270 0 : return false;
271 :
272 4918980 : dataVec[i] = m_tmpLutVec[dataVec[i]];
273 : }
274 : }
275 : }
276 :
277 113518 : return true;
278 : }
279 :
280 : // -------------------------------------------------------------------------- ;
281 :
282 709569 : unsigned int BitStuffer2::ComputeNumBytesNeededLut(const vector<pair<unsigned int, unsigned int> >& sortedDataVec, bool& doLut)
283 : {
284 709569 : unsigned int maxElem = sortedDataVec.back().first;
285 709569 : unsigned int numElem = (unsigned int)sortedDataVec.size();
286 :
287 709569 : int numBits = 0;
288 3591790 : while ((numBits < 32) && (maxElem >> numBits))
289 2882220 : numBits++;
290 709569 : unsigned int numBytes = 1 + NumBytesUInt(numElem) + ((numElem * numBits + 7) >> 3);
291 :
292 : // go through and count how often the value changes
293 709569 : int nLut = 0;
294 71172000 : for (unsigned int i = 1; i < numElem; i++)
295 70462500 : if (sortedDataVec[i].first != sortedDataVec[i - 1].first)
296 1145300 : nLut++;
297 :
298 709569 : int nBitsLut = 0;
299 1655040 : while (nLut >> nBitsLut)
300 945475 : nBitsLut++;
301 :
302 709569 : unsigned int numBitsTotalLut = nLut * numBits; // num bits w/o the 0
303 709569 : unsigned int numBytesLut = 1 + NumBytesUInt(numElem) + 1 + ((numBitsTotalLut + 7) >> 3) + ((numElem * nBitsLut + 7) >> 3);
304 :
305 709569 : doLut = numBytesLut < numBytes;
306 709569 : return min(numBytesLut, numBytes);
307 : }
308 :
309 : // -------------------------------------------------------------------------- ;
310 : // -------------------------------------------------------------------------- ;
311 :
312 463870 : void BitStuffer2::BitStuff_Before_Lerc2v3(Byte** ppByte, const vector<unsigned int>& dataVec, int numBits)
313 : {
314 463870 : unsigned int numElements = (unsigned int)dataVec.size();
315 463870 : unsigned int numUInts = (numElements * numBits + 31) / 32;
316 463870 : unsigned int numBytes = numUInts * sizeof(unsigned int);
317 463870 : unsigned int* arr = (unsigned int*)(*ppByte);
318 :
319 463870 : memset(arr, 0, numBytes);
320 :
321 : // do the stuffing
322 463870 : const unsigned int* srcPtr = &dataVec[0];
323 463870 : unsigned int* dstPtr = arr;
324 463870 : int bitPos = 0;
325 :
326 17363600 : for (unsigned int i = 0; i < numElements; i++)
327 : {
328 16899800 : if (32 - bitPos >= numBits)
329 : {
330 : unsigned int dstValue;
331 16897100 : memcpy(&dstValue, dstPtr, sizeof(unsigned int));
332 16897100 : dstValue |= (*srcPtr++) << (32 - bitPos - numBits);
333 16897100 : memcpy(dstPtr, &dstValue, sizeof(unsigned int));
334 16897100 : bitPos += numBits;
335 16897100 : if (bitPos == 32) // shift >= 32 is undefined
336 : {
337 641691 : bitPos = 0;
338 641691 : dstPtr++;
339 : }
340 : }
341 : else
342 : {
343 : unsigned int dstValue;
344 2634 : int n = numBits - (32 - bitPos);
345 2634 : memcpy(&dstValue, dstPtr, sizeof(unsigned int));
346 2634 : dstValue |= (*srcPtr) >> n;
347 2634 : memcpy(dstPtr, &dstValue, sizeof(unsigned int));
348 2634 : dstPtr++;
349 2634 : memcpy(&dstValue, dstPtr, sizeof(unsigned int));
350 2634 : dstValue |= (*srcPtr++) << (32 - n);
351 2634 : memcpy(dstPtr, &dstValue, sizeof(unsigned int));
352 2634 : bitPos = n;
353 : }
354 : }
355 :
356 : // save the 0-3 bytes not used in the last UInt
357 463870 : unsigned int numBytesNotNeeded = NumTailBytesNotNeeded(numElements, numBits);
358 463870 : unsigned int n = numBytesNotNeeded;
359 1060330 : for (; n; --n)
360 : {
361 : unsigned int dstValue;
362 596462 : memcpy(&dstValue, dstPtr, sizeof(unsigned int));
363 596462 : dstValue >>= 8;
364 596462 : memcpy(dstPtr, &dstValue, sizeof(unsigned int));
365 : }
366 :
367 463870 : *ppByte += numBytes - numBytesNotNeeded;
368 463870 : }
369 :
370 : // -------------------------------------------------------------------------- ;
371 :
372 156172 : bool BitStuffer2::BitUnStuff_Before_Lerc2v3(const Byte** ppByte, size_t& nBytesRemaining,
373 : vector<unsigned int>& dataVec, unsigned int numElements, int numBits) const
374 : {
375 156172 : if (numElements == 0 || numBits >= 32)
376 0 : return false;
377 156172 : unsigned long long numUIntsLL = ((unsigned long long)numElements * numBits + 31) / 32;
378 156172 : unsigned long long numBytesLL = numUIntsLL * sizeof(unsigned int);
379 156172 : size_t numBytes = (size_t)numBytesLL; // could theoretically overflow on 32 bit system
380 156172 : size_t numUInts = (size_t)numUIntsLL;
381 156172 : unsigned int ntbnn = NumTailBytesNotNeeded(numElements, numBits);
382 156172 : if (numBytes != numBytesLL || nBytesRemaining + ntbnn < numBytes)
383 0 : return false;
384 :
385 : try
386 : {
387 156172 : dataVec.resize(numElements, 0); // init with 0
388 156172 : m_tmpBitStuffVec.resize(numUInts);
389 : }
390 0 : catch( const std::exception& )
391 : {
392 0 : return false;
393 : }
394 :
395 156172 : m_tmpBitStuffVec[numUInts - 1] = 0; // set last uint to 0
396 :
397 156172 : unsigned int nBytesToCopy = (numElements * numBits + 7) / 8;
398 156172 : memcpy(&m_tmpBitStuffVec[0], *ppByte, nBytesToCopy);
399 :
400 156172 : unsigned int* pLastULong = &m_tmpBitStuffVec[numUInts - 1];
401 356374 : while (ntbnn)
402 : {
403 200202 : -- ntbnn;
404 200202 : *pLastULong <<= 8;
405 : }
406 :
407 156172 : unsigned int* srcPtr = &m_tmpBitStuffVec[0];
408 156172 : unsigned int* dstPtr = &dataVec[0];
409 156172 : int bitPos = 0;
410 :
411 5855250 : for (unsigned int i = 0; i < numElements; i++)
412 : {
413 5699080 : if (32 - bitPos >= numBits)
414 : {
415 : unsigned int val;
416 5697570 : memcpy(&val, srcPtr, sizeof(unsigned int));
417 5697570 : unsigned int n = val << bitPos;
418 5697570 : *dstPtr++ = n >> (32 - numBits);
419 5697570 : bitPos += numBits;
420 :
421 5697570 : if (bitPos == 32) // shift >= 32 is undefined
422 : {
423 216619 : bitPos = 0;
424 216619 : srcPtr++;
425 : }
426 : }
427 : else
428 : {
429 : unsigned int val;
430 1511 : memcpy(&val, srcPtr, sizeof(unsigned int));
431 1511 : srcPtr++;
432 1511 : unsigned int n = val << bitPos;
433 1511 : *dstPtr = n >> (32 - numBits);
434 1511 : bitPos -= (32 - numBits);
435 1511 : memcpy(&val, srcPtr, sizeof(unsigned int));
436 1511 : *dstPtr++ |= val >> (32 - bitPos);
437 : }
438 : }
439 :
440 156172 : *ppByte += nBytesToCopy;
441 156172 : nBytesRemaining -= nBytesToCopy;
442 :
443 156172 : return true;
444 : }
445 :
446 : // -------------------------------------------------------------------------- ;
447 :
448 : // starting with version Lerc2v3: integer >> into local uint buffer, plus final memcpy
449 :
450 20511 : void BitStuffer2::BitStuff(Byte** ppByte, const vector<unsigned int>& dataVec, int numBits) const
451 : {
452 20511 : unsigned int numElements = (unsigned int)dataVec.size();
453 20511 : unsigned int numUInts = (numElements * numBits + 31) / 32;
454 20511 : unsigned int numBytes = numUInts * sizeof(unsigned int);
455 :
456 20511 : m_tmpBitStuffVec.resize(numUInts);
457 20511 : unsigned int* dstPtr = &m_tmpBitStuffVec[0];
458 :
459 20511 : memset(dstPtr, 0, numBytes);
460 :
461 : // do the stuffing
462 20511 : const unsigned int* srcPtr = &dataVec[0];
463 20511 : int bitPos = 0;
464 20511 : assert(numBits <= 32); // to avoid coverity warning about large shift a bit later, when doing (*srcPtr++) >> (32 - bitPos)
465 :
466 1354360 : for (unsigned int i = 0; i < numElements; i++)
467 : {
468 1333840 : if (32 - bitPos >= numBits)
469 : {
470 1253960 : *dstPtr |= (*srcPtr++) << bitPos;
471 1253960 : bitPos += numBits;
472 1253960 : if (bitPos == 32) // shift >= 32 is undefined
473 : {
474 97956 : dstPtr++;
475 97956 : bitPos = 0;
476 : }
477 : }
478 : else
479 : {
480 79880 : *dstPtr++ |= (*srcPtr) << bitPos;
481 79880 : *dstPtr |= (*srcPtr++) >> (32 - bitPos);
482 79880 : bitPos += numBits - 32;
483 : }
484 : }
485 :
486 : // copy the bytes to the outgoing byte stream
487 20511 : size_t numBytesUsed = numBytes - NumTailBytesNotNeeded(numElements, numBits);
488 : #ifdef CSA_BUILD
489 : assert( numElements );
490 : #endif
491 20511 : memcpy(*ppByte, m_tmpBitStuffVec.data(), numBytesUsed);
492 :
493 20511 : *ppByte += numBytesUsed;
494 20511 : }
495 :
496 : // -------------------------------------------------------------------------- ;
497 :
498 32310 : bool BitStuffer2::BitUnStuff(const Byte** ppByte, size_t& nBytesRemaining, vector<unsigned int>& dataVec,
499 : unsigned int numElements, int numBits) const
500 : {
501 32310 : if (numElements == 0 || numBits >= 32)
502 0 : return false;
503 32310 : unsigned long long numUIntsLL = ((unsigned long long)numElements * numBits + 31) / 32;
504 32310 : unsigned long long numBytesLL = numUIntsLL * sizeof(unsigned int);
505 32310 : size_t numBytes = (size_t)numBytesLL; // could theoretically overflow on 32 bit system
506 32310 : if (numBytes != numBytesLL)
507 0 : return false;
508 32310 : size_t numUInts = (size_t)numUIntsLL;
509 :
510 : // copy the bytes from the incoming byte stream
511 32310 : const size_t numBytesUsed = numBytes - NumTailBytesNotNeeded(numElements, numBits);
512 :
513 32310 : if (nBytesRemaining < numBytesUsed)
514 0 : return false;
515 :
516 : try
517 : {
518 32310 : dataVec.resize(numElements);
519 : }
520 0 : catch( const std::exception& )
521 : {
522 0 : return false;
523 : }
524 :
525 : try
526 : {
527 32310 : m_tmpBitStuffVec.resize(numUInts);
528 : }
529 0 : catch( const std::exception& )
530 : {
531 0 : return false;
532 : }
533 :
534 32310 : m_tmpBitStuffVec[numUInts - 1] = 0; // set last uint to 0
535 :
536 32310 : memcpy(&m_tmpBitStuffVec[0], *ppByte, numBytesUsed);
537 :
538 : // do the un-stuffing
539 32310 : unsigned int* srcPtr = &m_tmpBitStuffVec[0];
540 32310 : unsigned int* dstPtr = &dataVec[0];
541 32310 : int bitPos = 0;
542 32310 : int nb = 32 - numBits;
543 :
544 2089430 : for (unsigned int i = 0; i < numElements; i++)
545 : {
546 2057120 : if (nb - bitPos >= 0)
547 : {
548 1948520 : *dstPtr++ = ((*srcPtr) << (nb - bitPos)) >> nb;
549 1948520 : bitPos += numBits;
550 1948520 : if (bitPos == 32) // shift >= 32 is undefined
551 : {
552 159164 : srcPtr++;
553 159164 : bitPos = 0;
554 : }
555 : }
556 : else
557 : {
558 108600 : *dstPtr = (*srcPtr++) >> bitPos;
559 108600 : *dstPtr++ |= ((*srcPtr) << (64 - numBits - bitPos)) >> nb;
560 108600 : bitPos -= nb;
561 : }
562 : }
563 :
564 32310 : *ppByte += numBytesUsed;
565 32310 : nBytesRemaining -= numBytesUsed;
566 32310 : return true;
567 : }
568 :
569 : // -------------------------------------------------------------------------- ;
570 :
|
