Line data Source code
1 : /*
2 : Copyright 2015 - 2021 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 : A local copy of the license and additional notices are located with the
16 : source distribution at:
17 :
18 : http://github.com/Esri/lerc/
19 :
20 : Contributors: Thomas Maurer
21 : Lucian Plesea
22 : */
23 :
24 : #include "Lerc1Image.h"
25 : #include <cstdint>
26 : #include <cmath>
27 : #include <cfloat>
28 : #include <string>
29 : #include <algorithm>
30 :
31 : NAMESPACE_LERC1_START
32 :
33 : // max quantized value, 28 bits
34 : // It is wasting a few bits, because a float has only 24bits of precision
35 : static const double MAXQ = 0x1000000;
36 :
37 : // RLE constants
38 : static const int MAX_RUN = 32767;
39 : static const int MIN_RUN = 5;
40 : // End of Transmission
41 : static const int EOT = -(MAX_RUN + 1);
42 :
43 : // Decode a RLE bitmask, size should be already set
44 : // Returns false if input seems wrong
45 : // Zero size mask is fine, only checks the end marker
46 16 : bool BitMaskV1::RLEdecompress(const Byte *src, size_t n)
47 : {
48 16 : Byte *dst = bits.data();
49 16 : int sz = size();
50 : short int count;
51 :
52 : // Read a low endian short int
53 : #define READ_COUNT \
54 : if (true) \
55 : { \
56 : if (n < 2) \
57 : return false; \
58 : count = *src++; \
59 : count += (*src++ << 8); \
60 : }
61 5021 : while (sz > 0)
62 : { // One sequence per loop
63 5005 : READ_COUNT;
64 5005 : n -= 2;
65 5005 : if (count < 0)
66 : { // negative count for repeats
67 3222 : if (0 == n)
68 0 : return false;
69 3222 : --n; // only decrement after checking for 0 to avoid a (harmless)
70 : // unsigned integer overflow warning with ossfuzz
71 3222 : Byte b = *src++;
72 3222 : sz += count;
73 3222 : if (sz < 0)
74 0 : return false;
75 523624 : while (0 != count++)
76 520402 : *dst++ = b;
77 : }
78 : else
79 : { // No repeats, count is positive
80 1783 : if (sz < count || n < static_cast<size_t>(count))
81 0 : return false;
82 1783 : sz -= count;
83 1783 : n -= count;
84 6056 : while (0 != count--)
85 4273 : *dst++ = *src++;
86 : }
87 : }
88 16 : READ_COUNT;
89 16 : return (count == EOT);
90 : }
91 :
92 : // Encode helper function
93 : // It returns how many times the byte at *s is repeated
94 : // a value between 1 and min(max_count, MAX_RUN)
95 5296 : inline static int run_length(const Byte *s, int max_count)
96 : {
97 5296 : if (max_count > MAX_RUN)
98 24 : max_count = MAX_RUN;
99 786894 : for (int i = 1; i < max_count; i++)
100 786870 : if (s[0] != s[i])
101 5272 : return i;
102 24 : return max_count;
103 : }
104 :
105 : // RLE compressed size is bound by n + 4 + 2 * (n - 1) / 32767
106 12 : int BitMaskV1::RLEcompress(Byte *dst) const
107 : {
108 12 : const Byte *src = bits.data(); // Next input byte
109 12 : Byte *start = dst;
110 12 : int sz = size(); // left to process
111 12 : Byte *pCnt = dst; // Pointer to current sequence count
112 12 : int oddrun = 0; // non-repeated byte count
113 :
114 : // Store val as short low endian integer
115 : #define WRITE_COUNT(val) \
116 : if (true) \
117 : { \
118 : *pCnt++ = Byte(val & 0xff); \
119 : *pCnt++ = Byte(val >> 8); \
120 : }
121 : // Flush an existing odd run
122 : #define FLUSH \
123 : if (oddrun) \
124 : { \
125 : WRITE_COUNT(oddrun); \
126 : pCnt += oddrun; \
127 : dst = pCnt + 2; \
128 : oddrun = 0; \
129 : }
130 :
131 12 : dst += 2; // Skip the space for the first count
132 2660 : while (sz > 0)
133 : {
134 2648 : int run = run_length(src, sz);
135 2648 : if (run < MIN_RUN)
136 : { // Use one byte
137 817 : *dst++ = *src++;
138 817 : sz--;
139 817 : if (MAX_RUN == ++oddrun)
140 0 : FLUSH;
141 : }
142 : else
143 : { // Found a run
144 1831 : FLUSH;
145 1831 : WRITE_COUNT(-run);
146 1831 : *pCnt++ = *src;
147 1831 : src += run;
148 1831 : sz -= run;
149 : // cppcheck-suppress redundantAssignment
150 1831 : dst = pCnt + 2; // after the next marker
151 : }
152 : }
153 : // cppcheck-suppress uselessAssignmentPtrArg
154 12 : FLUSH;
155 : (void)oddrun;
156 : (void)dst;
157 12 : WRITE_COUNT(EOT); // End marker
158 : // return compressed output size
159 12 : return int(pCnt - start);
160 : }
161 :
162 : // calculate encoded size
163 12 : int BitMaskV1::RLEsize() const
164 : {
165 12 : const Byte *src = bits.data(); // Next input byte
166 12 : int sz = size(); // left to process
167 12 : int oddrun = 0; // current non-repeated byte count
168 : // Simulate an odd run flush
169 : #define SIMFLUSH \
170 : if (oddrun) \
171 : { \
172 : osz += oddrun + 2; \
173 : oddrun = 0; \
174 : }
175 12 : int osz = 2; // output size, start with size of end marker
176 2660 : while (sz)
177 : {
178 2648 : int run = run_length(src, sz);
179 2648 : if (run < MIN_RUN)
180 : {
181 817 : src++;
182 817 : sz--;
183 817 : if (MAX_RUN == ++oddrun)
184 0 : SIMFLUSH;
185 : }
186 : else
187 : {
188 1831 : SIMFLUSH;
189 1831 : src += run;
190 1831 : sz -= run;
191 1831 : osz += 3; // Any run is 3 bytes
192 : }
193 : }
194 12 : return oddrun ? (osz + oddrun + 2) : osz;
195 : }
196 :
197 : // Lookup tables for number of bytes in float and int, forward and reverse
198 : static const Byte bits67[4] = {0x80, 0x40, 0xc0, 0}; // shifted left 6 bits
199 : static const Byte stib67[4] = {4, 2, 1, 0}; // Last one is not used
200 :
201 15766 : static int numBytesUInt(unsigned int k)
202 : {
203 15766 : return (k <= 0xff) ? 1 : (k <= 0xffff) ? 2 : 4;
204 : }
205 :
206 : // Bits required to store v
207 15766 : static int nBits(unsigned int v)
208 : {
209 15766 : int n = 0;
210 116738 : while (v >> n)
211 100972 : n++;
212 15766 : return n;
213 : }
214 :
215 : // see the old stream IO functions below on how to call.
216 : // if you change write(...) / read(...), don't forget to update
217 : // computeNumBytesNeeded(...).
218 2455 : static bool blockwrite(Byte **ppByte, const std::vector<unsigned int> &d)
219 : {
220 2455 : if (!ppByte || d.empty())
221 0 : return false;
222 :
223 2455 : unsigned int maxElem = *std::max_element(d.begin(), d.end());
224 2455 : unsigned int numElements = (unsigned int)d.size();
225 2455 : int n = numBytesUInt(numElements);
226 2455 : int numBits = nBits(maxElem); // 0 to 28
227 :
228 : // use bits67 to encode the type used for numElements: Byte, ushort, or uint
229 : // n is in {1, 2, 4}
230 : // 0xc0 is invalid, will trigger an error
231 2455 : **ppByte = static_cast<Byte>(numBits | bits67[n - 1]);
232 2455 : (*ppByte)++;
233 2455 : memcpy(*ppByte, &numElements, n);
234 2455 : *ppByte += n;
235 2455 : if (numBits == 0)
236 0 : return true;
237 :
238 2455 : int bits = 32; // Available
239 2455 : unsigned int acc = 0; // Accumulator
240 164589 : for (unsigned int val : d)
241 : {
242 162134 : if (bits >= numBits)
243 : { // no accumulator overflow
244 131812 : acc |= val << (bits - numBits);
245 131812 : bits -= numBits;
246 : }
247 : else
248 : { // accum overflowing
249 30322 : acc |= val >> (numBits - bits);
250 30322 : memcpy(*ppByte, &acc, sizeof(acc));
251 30322 : *ppByte += sizeof(acc);
252 30322 : bits += 32 - numBits; // under 32
253 30322 : acc = val << bits;
254 : }
255 : }
256 :
257 : // There are between 1 and 4 bytes left to write
258 2455 : int nbytes = 4;
259 2747 : while (bits >= 8)
260 : {
261 292 : acc >>= 8;
262 292 : bits -= 8;
263 292 : nbytes--;
264 : }
265 2455 : memcpy(*ppByte, &acc, nbytes);
266 2455 : *ppByte += nbytes;
267 2455 : return true;
268 : }
269 :
270 2459 : static bool blockread(Byte **ppByte, size_t &size, std::vector<unsigned int> &d)
271 : {
272 2459 : if (!ppByte || !size)
273 0 : return false;
274 :
275 2459 : Byte numBits = **ppByte;
276 2459 : Byte n = stib67[numBits >> 6];
277 2459 : numBits &= 63; // bits 0-5;
278 : // cppcheck-suppress knownConditionTrueFalse
279 2459 : if (numBits >= 32 || n == 0 || size < 1 + static_cast<size_t>(n))
280 0 : return false;
281 2459 : *ppByte += 1;
282 2459 : size -= 1;
283 :
284 2459 : unsigned int numElements = 0;
285 2459 : memcpy(&numElements, *ppByte, n);
286 2459 : *ppByte += n;
287 2459 : size -= n;
288 2459 : if (static_cast<size_t>(numElements) > d.size())
289 0 : return false;
290 2459 : if (numBits == 0)
291 : { // Nothing to read, all zeros
292 0 : d.resize(0);
293 0 : d.resize(numElements, 0);
294 0 : return true;
295 : }
296 :
297 2459 : d.resize(numElements);
298 2459 : unsigned int numBytes = (numElements * numBits + 7) / 8;
299 2459 : if (size < numBytes)
300 0 : return false;
301 2459 : size -= numBytes;
302 :
303 2459 : int bits = 0; // Available in accumulator, at the high end
304 2459 : unsigned int acc = 0;
305 172685 : for (unsigned int &val : d)
306 : {
307 170226 : if (bits >= numBits)
308 : { // Enough bits in accumulator
309 132540 : val = acc >> (32 - numBits);
310 132540 : acc <<= numBits;
311 132540 : bits -= numBits;
312 132540 : continue;
313 : }
314 :
315 : // Need to reload the accumulator
316 37686 : val = 0;
317 37686 : if (bits)
318 : {
319 18883 : val = acc >> (32 - bits);
320 18883 : val <<= (numBits - bits);
321 : }
322 37686 : unsigned int nb = std::min(numBytes, 4u);
323 37686 : if (4u == nb)
324 37489 : memcpy(&acc, *ppByte, 4);
325 : else // Read only a few bytes at the high end of acc
326 197 : memcpy(reinterpret_cast<Byte *>(&acc) + (4 - nb), *ppByte, nb);
327 37686 : *ppByte += nb;
328 37686 : numBytes -= nb;
329 :
330 37686 : bits += 32 - numBits;
331 37686 : val |= acc >> bits;
332 37686 : acc <<= 32 - bits;
333 : }
334 2459 : return numBytes == 0;
335 : }
336 :
337 : static const int CNT_Z = 8;
338 : static const int CNT_Z_VER = 11;
339 : static const std::string sCntZImage("CntZImage "); // Includes a space
340 :
341 : // computes the size of a CntZImage of any width and height, but all void /
342 : // invalid, and then compressed
343 1647 : unsigned int Lerc1Image::computeNumBytesNeededToWriteVoidImage()
344 : {
345 : unsigned int sz =
346 1647 : (unsigned int)sCntZImage.size() + 4 * sizeof(int) + sizeof(double);
347 : // cnt part
348 1647 : sz += 3 * sizeof(int) + sizeof(float);
349 : // z part, 1 is the empty Tile if all invalid
350 1647 : sz += 3 * sizeof(int) + sizeof(float) + 1;
351 1647 : return sz; // 67
352 : }
353 :
354 : unsigned int
355 12 : Lerc1Image::computeNumBytesNeededToWrite(double maxZError, bool onlyZPart,
356 : InfoFromComputeNumBytes *info) const
357 : {
358 : int numBytesOpt;
359 : unsigned int sz =
360 12 : (unsigned int)sCntZImage.size() + 4 * sizeof(int) + sizeof(double);
361 12 : if (!onlyZPart)
362 : {
363 : float cntMin, cntMax;
364 12 : computeCntStats(cntMin, cntMax);
365 :
366 12 : numBytesOpt = 0;
367 12 : if (cntMin != cntMax)
368 12 : numBytesOpt = mask.RLEsize();
369 :
370 12 : info->numTilesVertCnt = 0;
371 12 : info->numTilesHoriCnt = 0;
372 12 : info->numBytesCnt = numBytesOpt;
373 12 : info->maxCntInImg = cntMax;
374 :
375 12 : sz += 3 * sizeof(int) + sizeof(float) + numBytesOpt;
376 : }
377 :
378 : // z part
379 : int numTilesVert, numTilesHori;
380 : float maxValInImg;
381 12 : if (!findTiling(maxZError, numTilesVert, numTilesHori, numBytesOpt,
382 : maxValInImg))
383 0 : return 0;
384 :
385 12 : info->maxZError = maxZError;
386 12 : info->numTilesVertZ = numTilesVert;
387 12 : info->numTilesHoriZ = numTilesHori;
388 12 : info->numBytesZ = numBytesOpt;
389 12 : info->maxZInImg = maxValInImg;
390 :
391 12 : sz += 3 * sizeof(int) + sizeof(float) + numBytesOpt;
392 12 : return sz;
393 : }
394 :
395 : // if you change the file format, don't forget to update not only write and
396 : // read functions, and the file version number, but also the computeNumBytes...
397 : // and numBytes... functions
398 12 : bool Lerc1Image::write(Byte **ppByte, double maxZError, bool zPart) const
399 : {
400 : // Local macro, write an unaligned variable, adjust pointer
401 : #define WRVAR(VAR, PTR) \
402 : memcpy((PTR), &(VAR), sizeof(VAR)); \
403 : (PTR) += sizeof(VAR)
404 12 : if (getSize() == 0)
405 0 : return false;
406 :
407 : // signature
408 12 : memcpy(*ppByte, sCntZImage.c_str(), sCntZImage.size());
409 12 : *ppByte += sCntZImage.size();
410 :
411 12 : int height = getHeight();
412 12 : int width = getWidth();
413 12 : WRVAR(CNT_Z_VER, *ppByte);
414 12 : WRVAR(CNT_Z, *ppByte);
415 12 : WRVAR(height, *ppByte);
416 12 : WRVAR(width, *ppByte);
417 12 : WRVAR(maxZError, *ppByte);
418 :
419 12 : InfoFromComputeNumBytes info;
420 12 : if (0 == computeNumBytesNeededToWrite(maxZError, zPart, &info))
421 0 : return false;
422 :
423 24 : do
424 : {
425 24 : int numTilesVert, numTilesHori, numBytesOpt, numBytesWritten = 0;
426 : float maxValInImg;
427 :
428 24 : if (!zPart)
429 : {
430 12 : numTilesVert = info.numTilesVertCnt;
431 12 : numTilesHori = info.numTilesHoriCnt;
432 12 : numBytesOpt = info.numBytesCnt;
433 12 : maxValInImg = info.maxCntInImg;
434 : }
435 : else
436 : {
437 12 : numTilesVert = info.numTilesVertZ;
438 12 : numTilesHori = info.numTilesHoriZ;
439 12 : numBytesOpt = info.numBytesZ;
440 12 : maxValInImg = info.maxZInImg;
441 : }
442 :
443 24 : WRVAR(numTilesVert, *ppByte);
444 24 : WRVAR(numTilesHori, *ppByte);
445 24 : WRVAR(numBytesOpt, *ppByte);
446 24 : WRVAR(maxValInImg, *ppByte);
447 :
448 24 : if (!zPart && numTilesVert == 0 && numTilesHori == 0)
449 : { // no tiling for cnt part
450 12 : if (numBytesOpt > 0) // cnt part is binary mask, use fast RLE class
451 12 : numBytesWritten = mask.RLEcompress(*ppByte);
452 : }
453 : else
454 : { // encode tiles to buffer, always z part
455 : float maxVal;
456 12 : if (!writeTiles(maxZError, numTilesVert, numTilesHori, *ppByte,
457 : numBytesWritten, maxVal))
458 0 : return false;
459 : }
460 :
461 24 : if (numBytesWritten != numBytesOpt)
462 0 : return false;
463 :
464 24 : *ppByte += numBytesWritten;
465 24 : zPart = !zPart;
466 : } while (zPart);
467 12 : return true;
468 : #undef WRVAR
469 : }
470 :
471 : // To avoid excessive memory allocation attempts, this is still 1.8GB!!
472 : static size_t TOO_LARGE = 1800 * 1000 * 1000 / static_cast<int>(sizeof(float));
473 :
474 16 : bool Lerc1Image::read(Byte **ppByte, size_t &nRemainingBytes, double maxZError,
475 : bool ZPart)
476 : {
477 : // Local macro, read an unaligned variable, adjust pointer
478 : #define RDVAR(PTR, VAR) \
479 : memcpy(&(VAR), (PTR), sizeof(VAR)); \
480 : (PTR) += sizeof(VAR)
481 16 : size_t len = sCntZImage.length();
482 16 : if (nRemainingBytes < len)
483 0 : return false;
484 :
485 32 : std::string typeStr(reinterpret_cast<char *>(*ppByte), len);
486 16 : if (typeStr != sCntZImage)
487 0 : return false;
488 16 : *ppByte += len;
489 16 : nRemainingBytes -= len;
490 :
491 16 : int version = 0, type = 0;
492 16 : int width = 0, height = 0;
493 16 : double maxZErrorInFile = 0;
494 :
495 16 : if (nRemainingBytes < (4 * sizeof(int) + sizeof(double)))
496 0 : return false;
497 16 : RDVAR(*ppByte, version);
498 16 : RDVAR(*ppByte, type);
499 16 : RDVAR(*ppByte, height);
500 16 : RDVAR(*ppByte, width);
501 16 : RDVAR(*ppByte, maxZErrorInFile);
502 16 : nRemainingBytes -= 4 * sizeof(int) + sizeof(double);
503 :
504 16 : if (version != CNT_Z_VER || type != CNT_Z)
505 0 : return false;
506 16 : if (width <= 0 || width > 20000 || height <= 0 || height > 20000 ||
507 16 : maxZErrorInFile > maxZError)
508 0 : return false;
509 16 : if (static_cast<size_t>(width) * height > TOO_LARGE)
510 0 : return false;
511 :
512 16 : if (ZPart)
513 : {
514 0 : if (width != getWidth() || height != getHeight())
515 0 : return false;
516 : }
517 : else
518 : { // Resize clears the buffer
519 16 : resize(width, height);
520 : }
521 :
522 32 : do
523 : {
524 32 : int numTilesVert = 0, numTilesHori = 0, numBytes = 0;
525 32 : float maxValInImg = 0;
526 32 : if (nRemainingBytes < 3 * sizeof(int) + sizeof(float))
527 0 : return false;
528 32 : RDVAR(*ppByte, numTilesVert);
529 32 : RDVAR(*ppByte, numTilesHori);
530 32 : RDVAR(*ppByte, numBytes);
531 32 : RDVAR(*ppByte, maxValInImg);
532 32 : nRemainingBytes -= 3 * sizeof(int) + sizeof(float);
533 :
534 32 : if (numBytes < 0 || nRemainingBytes < static_cast<size_t>(numBytes))
535 0 : return false;
536 32 : if (ZPart)
537 : {
538 16 : if (!readTiles(maxZErrorInFile, numTilesVert, numTilesHori,
539 : maxValInImg, *ppByte, numBytes))
540 0 : return false;
541 : }
542 : else
543 : { // no tiling allowed for the cnt part
544 16 : if (numTilesVert != 0 && numTilesHori != 0)
545 0 : return false;
546 16 : if (numBytes == 0)
547 : { // cnt part is const
548 0 : if (maxValInImg != 0.0 && maxValInImg != 1.0)
549 0 : return false; // Only 0 and 1 are valid
550 0 : bool v = (maxValInImg != 0.0);
551 0 : for (int k = 0; k < getSize(); k++)
552 0 : mask.Set(k, v);
553 : }
554 : else
555 : { // cnt part is binary mask, RLE compressed
556 16 : if (!mask.RLEdecompress(*ppByte, static_cast<size_t>(numBytes)))
557 0 : return false;
558 : }
559 : }
560 32 : *ppByte += numBytes;
561 32 : nRemainingBytes -= numBytes;
562 32 : ZPart = !ZPart;
563 : } while (ZPart); // Stop after writing Z
564 16 : return true;
565 : }
566 :
567 : // Initialize from the given header, return true if it worked
568 : // It could read more info from the header, if needed
569 5 : bool Lerc1Image::getwh(const Byte *pByte, size_t nBytes, int &width,
570 : int &height)
571 : {
572 5 : size_t len = sCntZImage.length();
573 5 : if (nBytes < len)
574 0 : return false;
575 :
576 10 : std::string typeStr(reinterpret_cast<const char *>(pByte), len);
577 5 : if (typeStr != sCntZImage)
578 0 : return false;
579 5 : pByte += len;
580 5 : nBytes -= len;
581 :
582 5 : int version = 0, type = 0;
583 5 : double maxZErrorInFile = 0;
584 :
585 5 : if (nBytes < (4 * sizeof(int) + sizeof(double)))
586 0 : return false;
587 5 : RDVAR(pByte, version);
588 5 : RDVAR(pByte, type);
589 5 : RDVAR(pByte, height);
590 5 : RDVAR(pByte, width);
591 5 : RDVAR(pByte, maxZErrorInFile);
592 : (void)pByte;
593 :
594 5 : if (version != CNT_Z_VER || type != CNT_Z)
595 0 : return false;
596 5 : if (width <= 0 || width > 20000 || height <= 0 || height > 20000)
597 0 : return false;
598 5 : if (static_cast<size_t>(width) * height > TOO_LARGE)
599 0 : return false;
600 :
601 5 : return true;
602 : #undef RDVAR
603 : }
604 :
605 12 : bool Lerc1Image::findTiling(double maxZError, int &numTilesVertA,
606 : int &numTilesHoriA, int &numBytesOptA,
607 : float &maxValInImgA) const
608 : {
609 : // entire image as 1 block, this is usually the worst case
610 12 : numTilesVertA = numTilesHoriA = 1;
611 12 : if (!writeTiles(maxZError, 1, 1, nullptr, numBytesOptA, maxValInImgA))
612 0 : return false;
613 : // The actual figure may be different due to round-down
614 12 : static const std::vector<int> tileWidthArr = {8, 11, 15, 20, 32, 64};
615 17 : for (auto tileWidth : tileWidthArr)
616 : {
617 17 : int numTilesVert = static_cast<int>(getHeight() / tileWidth);
618 17 : int numTilesHori = static_cast<int>(getWidth() / tileWidth);
619 :
620 17 : if (numTilesVert * numTilesHori < 2)
621 0 : return true;
622 :
623 17 : int numBytes = 0;
624 : float maxVal;
625 17 : if (!writeTiles(maxZError, numTilesVert, numTilesHori, nullptr,
626 : numBytes, maxVal))
627 0 : return false;
628 17 : if (numBytes > numBytesOptA)
629 12 : break; // Stop when size start to increase
630 5 : if (numBytes < numBytesOptA)
631 : {
632 5 : numTilesVertA = numTilesVert;
633 5 : numTilesHoriA = numTilesHori;
634 5 : numBytesOptA = numBytes;
635 : }
636 : }
637 12 : return true;
638 : }
639 :
640 : // n is 1, 2 or 4
641 3883 : static Byte *writeFlt(Byte *ptr, float z, int n)
642 : {
643 3883 : if (4 == n)
644 125 : memcpy(ptr, &z, 4);
645 3758 : else if (1 == n)
646 3589 : *ptr = static_cast<Byte>(static_cast<signed char>(z));
647 : else
648 : {
649 169 : signed short s = static_cast<signed short>(z);
650 169 : memcpy(ptr, &s, 2);
651 : }
652 3883 : return ptr + n;
653 : }
654 :
655 : // Only small, exact integer values return 1 or 2, otherwise 4
656 20434 : static int numBytesFlt(float z)
657 : {
658 20434 : float s = static_cast<float>(static_cast<signed short>(z));
659 20434 : float c = static_cast<float>(static_cast<signed char>(z));
660 20434 : return (c == z) ? 1 : (s == z) ? 2 : 4;
661 : }
662 :
663 16695 : static int numBytesZTile(int nValues, float zMin, float zMax, double maxZError)
664 : {
665 16695 : if (nValues == 0 || (zMin == 0 && zMax == 0))
666 0 : return 1;
667 33310 : if (maxZError == 0 || !std::isfinite(zMin) || !std::isfinite(zMax) ||
668 16615 : ((double)zMax - zMin) / (2 * maxZError) > MAXQ) // max of 28 bits
669 80 : return (int)(1 + nValues * sizeof(float)); // Stored as such
670 16615 : unsigned int maxElem = static_cast<unsigned int>(
671 16615 : ((double)zMax - zMin) / (2 * maxZError) + 0.5);
672 16615 : int nb = 1 + numBytesFlt(zMin);
673 16615 : if (maxElem == 0)
674 3304 : return nb;
675 13311 : return nb + 1 + numBytesUInt(nValues) + (nValues * nBits(maxElem) + 7) / 8;
676 : }
677 :
678 : // Pass bArr == nullptr to estimate the size but skip the write
679 41 : bool Lerc1Image::writeTiles(double maxZError, int numTilesV, int numTilesH,
680 : Byte *bArr, int &numBytes, float &maxValInImg) const
681 : {
682 41 : if (numTilesV == 0 || numTilesH == 0)
683 0 : return false;
684 41 : numBytes = 0;
685 41 : maxValInImg = -FLT_MAX;
686 41 : int tileHeight = static_cast<int>(getHeight() / numTilesV);
687 41 : int tileWidth = static_cast<int>(getWidth() / numTilesH);
688 41 : int v0 = 0;
689 1291 : while (v0 < getHeight())
690 : {
691 1250 : int v1 = std::min(getHeight(), v0 + tileHeight);
692 1250 : int h0 = 0;
693 74980 : while (h0 < getWidth())
694 : {
695 73730 : int h1 = std::min(getWidth(), h0 + tileWidth);
696 73730 : float zMin = 0, zMax = 0;
697 73730 : int numValidPixel = 0, numFinite = 0;
698 73730 : if (!computeZStats(v0, v1, h0, h1, zMin, zMax, numValidPixel,
699 : numFinite))
700 0 : return false;
701 :
702 73730 : if (maxValInImg < zMax)
703 125 : maxValInImg = zMax;
704 :
705 73730 : int numBytesNeeded = 1;
706 73730 : if (numValidPixel != 0)
707 : {
708 10613 : if (numFinite == 0 && numValidPixel == (v1 - v0) * (h1 - h0) &&
709 287 : isallsameval(v0, v1, h0, h1))
710 287 : numBytesNeeded = 5; // Stored as non-finite constant block
711 : else
712 : {
713 : numBytesNeeded =
714 10039 : numBytesZTile(numValidPixel, zMin, zMax, maxZError);
715 : // Try moving zMin up by maxZError, it may require fewer
716 : // bytes A bit less than maxZError, to avoid quantization
717 : // underflow
718 10039 : float zm = static_cast<float>(zMin + 0.999999 * maxZError);
719 10039 : if (numFinite == numValidPixel && zm <= zMax)
720 : {
721 : int nBN =
722 6655 : numBytesZTile(numValidPixel, zm, zMax, maxZError);
723 : // Maybe an int value for zMin saves a few bytes?
724 6655 : if (zMin < floorf(zm))
725 : {
726 1 : int nBNi = numBytesZTile(numValidPixel, floorf(zm),
727 : zMax, maxZError);
728 1 : if (nBNi < nBN)
729 : {
730 1 : zm = floorf(zm);
731 1 : nBN = nBNi;
732 : }
733 : }
734 6655 : if (nBN < numBytesNeeded)
735 : {
736 2 : zMin = zm;
737 2 : numBytesNeeded = nBN;
738 : }
739 : }
740 : }
741 : }
742 73730 : numBytes += numBytesNeeded;
743 :
744 73730 : if (bArr)
745 : { // Skip the write if no pointer was provided
746 14505 : int numBytesWritten = 0;
747 14569 : if (numFinite == 0 && numValidPixel == (v1 - v0) * (h1 - h0) &&
748 64 : isallsameval(v0, v1, h0, h1))
749 : {
750 : // direct write as non-finite const block, 4 byte float
751 64 : *bArr++ = 3; // 3 | bits67[3]
752 64 : bArr = writeFlt(bArr, (*this)(v0, h0), sizeof(float));
753 64 : numBytesWritten = 5;
754 : }
755 : else
756 : {
757 14441 : if (!writeZTile(&bArr, numBytesWritten, v0, v1, h0, h1,
758 : numValidPixel, zMin, zMax, maxZError))
759 0 : return false;
760 : }
761 14505 : if (numBytesWritten != numBytesNeeded)
762 0 : return false;
763 : }
764 73730 : h0 = h1;
765 : }
766 1250 : v0 = v1;
767 : }
768 41 : return true;
769 : }
770 :
771 16 : bool Lerc1Image::readTiles(double maxZErrorInFile, int numTilesV, int numTilesH,
772 : float maxValInImg, Byte *bArr,
773 : size_t nRemainingBytes)
774 : {
775 16 : if (numTilesV == 0 || numTilesH == 0)
776 0 : return false;
777 16 : int tileHeight = static_cast<int>(getHeight() / numTilesV);
778 16 : int tileWidth = static_cast<int>(getWidth() / numTilesH);
779 16 : if (tileWidth <= 0 || tileHeight <= 0) // Prevent infinite loop
780 0 : return false;
781 16 : int r0 = 0;
782 267 : while (r0 < getHeight())
783 : {
784 251 : int r1 = std::min(getHeight(), r0 + tileHeight);
785 251 : int c0 = 0;
786 14760 : while (c0 < getWidth())
787 : {
788 14509 : int c1 = std::min(getWidth(), c0 + tileWidth);
789 14509 : if (!readZTile(&bArr, nRemainingBytes, r0, r1, c0, c1,
790 : maxZErrorInFile, maxValInImg))
791 0 : return false;
792 14509 : c0 = c1;
793 : }
794 251 : r0 = r1;
795 : }
796 16 : return true;
797 : }
798 :
799 12 : void Lerc1Image::computeCntStats(float &cntMin, float &cntMax) const
800 : {
801 12 : cntMin = cntMax = static_cast<float>(mask.IsValid(0) ? 1.0f : 0.0f);
802 1512 : for (int k = 0; k < getSize() && cntMin == cntMax; k++)
803 1500 : if (mask.IsValid(k))
804 1488 : cntMax = 1.0f;
805 : else
806 12 : cntMin = 0.0f;
807 12 : }
808 :
809 73730 : bool Lerc1Image::computeZStats(int r0, int r1, int c0, int c1, float &zMin,
810 : float &zMax, int &numValidPixel,
811 : int &numFinite) const
812 : {
813 73730 : if (r0 < 0 || c0 < 0 || r1 > getHeight() || c1 > getWidth())
814 0 : return false;
815 73730 : zMin = FLT_MAX;
816 73730 : zMax = -FLT_MAX;
817 73730 : numValidPixel = 0;
818 73730 : numFinite = 0;
819 713730 : for (int row = r0; row < r1; row++)
820 11387900 : for (int col = c0; col < c1; col++)
821 10747900 : if (IsValid(row, col))
822 : {
823 1050370 : numValidPixel++;
824 1050370 : float val = (*this)(row, col);
825 1050370 : if (!std::isfinite(val))
826 44785 : zMin = NAN; // Serves as a flag, this block will be stored
827 : else
828 1005590 : numFinite++;
829 1050370 : if (val < zMin)
830 32396 : zMin = val;
831 1050370 : if (val > zMax)
832 37154 : zMax = val;
833 : }
834 73730 : if (0 == numValidPixel)
835 63404 : zMin = zMax = 0;
836 73730 : return true;
837 : }
838 :
839 : // Returns true if all floats in the region have exactly the same binary
840 : // representation This makes it usable for non-finite values
841 351 : bool Lerc1Image::isallsameval(int r0, int r1, int c0, int c1) const
842 : {
843 351 : uint32_t val = *reinterpret_cast<const uint32_t *>(&(*this)(r0, c0));
844 3959 : for (int row = r0; row < r1; row++)
845 42168 : for (int col = c0; col < c1; col++)
846 38560 : if (val != *reinterpret_cast<const uint32_t *>(&(*this)(row, col)))
847 0 : return false;
848 351 : return true;
849 : }
850 :
851 : //
852 : // Assumes that buffer at *ppByte is large enough for this particular block
853 : // Returns number of bytes used in numBytes
854 : //
855 14441 : bool Lerc1Image::writeZTile(Byte **ppByte, int &numBytes, int r0, int r1,
856 : int c0, int c1, int numValidPixel, float zMin,
857 : float zMax, double maxZError) const
858 : {
859 14441 : Byte *ptr = *ppByte;
860 14441 : int cntPixel = 0;
861 14441 : if (numValidPixel == 0 || (zMin == 0 && zMax == 0))
862 : { // special cases
863 10603 : *(*ppByte)++ =
864 : 2; // set compression flag to 2 to mark tile as constant 0
865 10603 : numBytes = 1;
866 10603 : return true;
867 : }
868 7657 : if (maxZError == 0 || !std::isfinite(zMin) || !std::isfinite(zMax) ||
869 3819 : ((double)zMax - zMin) / (2 * maxZError) > MAXQ)
870 : { // we'd need > 28 bit
871 : // write z's as flt arr uncompressed
872 19 : *ptr++ = 0; // flag
873 228 : for (int row = r0; row < r1; row++)
874 2508 : for (int col = c0; col < c1; col++)
875 2299 : if (IsValid(row, col))
876 : {
877 2123 : memcpy(ptr, &((*this)(row, col)), sizeof(float));
878 2123 : ptr += sizeof(float);
879 2123 : cntPixel++;
880 : }
881 19 : if (cntPixel != numValidPixel)
882 0 : return false;
883 : }
884 : else
885 : { // write z's as int arr bit stuffed
886 3819 : Byte flag = 1;
887 3819 : unsigned int maxElem =
888 3819 : (unsigned int)(((double)zMax - zMin) / (2 * maxZError) + 0.5);
889 3819 : if (maxElem == 0)
890 1364 : flag =
891 : 3; // set compression flag to 3 to mark tile as constant zMin
892 3819 : int n = numBytesFlt(zMin); // n in { 1, 2, 4 }
893 3819 : *ptr++ = (flag | bits67[n - 1]);
894 3819 : ptr = writeFlt(ptr, zMin, n);
895 3819 : if (maxElem > 0)
896 : {
897 2455 : std::vector<unsigned int> odataVec;
898 26310 : for (int row = r0; row < r1; row++)
899 2281090 : for (int col = c0; col < c1; col++)
900 2257240 : if (IsValid(row, col))
901 162134 : odataVec.push_back(
902 324268 : (unsigned int)(((double)(*this)(row, col) - zMin) /
903 162134 : (2 * maxZError) +
904 : 0.5));
905 2455 : if (odataVec.size() != static_cast<size_t>(numValidPixel))
906 0 : return false;
907 2455 : if (!blockwrite(&ptr, odataVec))
908 0 : return false;
909 : }
910 : }
911 :
912 3838 : numBytes = (int)(ptr - *ppByte);
913 3838 : *ppByte = ptr;
914 3838 : return true;
915 : }
916 :
917 : // Read a float encoded as unsigned char, signed short or float
918 : // n is the number of bytes
919 3887 : static float readFlt(const Byte *ptr, int n)
920 : {
921 3887 : if (n == 4)
922 : {
923 : float val;
924 128 : memcpy(&val, ptr, 4);
925 128 : return val;
926 : }
927 3759 : if (n == 2)
928 : {
929 : signed short s;
930 169 : memcpy(&s, ptr, 2);
931 169 : return static_cast<float>(s);
932 : }
933 3590 : return static_cast<float>(static_cast<signed char>(*ptr));
934 : }
935 :
936 14509 : bool Lerc1Image::readZTile(Byte **ppByte, size_t &nRemainingBytes, int r0,
937 : int r1, int c0, int c1, double maxZErrorInFile,
938 : float maxZInImg)
939 : {
940 14509 : Byte *ptr = *ppByte;
941 :
942 14509 : if (nRemainingBytes < 1)
943 0 : return false;
944 14509 : Byte comprFlag = *ptr++;
945 14509 : nRemainingBytes -= 1;
946 : // Used if bit-stuffed
947 14509 : Byte n = stib67[comprFlag >> 6];
948 14509 : comprFlag &= 63;
949 : // cppcheck-suppress knownConditionTrueFalse
950 14509 : if (n == 0 || comprFlag > 3)
951 0 : return false;
952 :
953 14509 : if (comprFlag == 2)
954 : { // entire zTile is 0
955 101387 : for (int row = r0; row < r1; row++)
956 881936 : for (int col = c0; col < c1; col++)
957 791152 : (*this)(row, col) = 0.0f;
958 10603 : *ppByte = ptr;
959 10603 : return true;
960 : }
961 :
962 3906 : if (comprFlag == 0)
963 : { // Stored
964 228 : for (int row = r0; row < r1; row++)
965 2508 : for (int col = c0; col < c1; col++)
966 2299 : if (IsValid(row, col))
967 : {
968 2123 : if (nRemainingBytes < sizeof(float))
969 0 : return false;
970 2123 : memcpy(&(*this)(row, col), ptr, sizeof(float));
971 2123 : ptr += sizeof(float);
972 2123 : nRemainingBytes -= sizeof(float);
973 : }
974 19 : *ppByte = ptr;
975 19 : return true;
976 : }
977 :
978 3887 : if (nRemainingBytes < n)
979 0 : return false;
980 3887 : float bminval = readFlt(ptr, n);
981 3887 : ptr += n;
982 3887 : nRemainingBytes -= n;
983 :
984 3887 : if (comprFlag == 3)
985 : { // all min val, regardless of mask
986 13044 : for (int row = r0; row < r1; row++)
987 106656 : for (int col = c0; col < c1; col++)
988 95040 : (*this)(row, col) = bminval;
989 1428 : *ppByte = ptr;
990 1428 : return true;
991 : }
992 :
993 2459 : idataVec.resize((r1 - r0) * (c1 - c0)); // max size
994 2459 : if (!blockread(&ptr, nRemainingBytes, idataVec))
995 0 : return false;
996 :
997 2459 : size_t nDataVecIdx = 0;
998 28365 : for (int row = r0; row < r1; row++)
999 3334790 : for (int col = c0; col < c1; col++)
1000 3308890 : if (IsValid(row, col))
1001 : {
1002 170226 : if (nDataVecIdx >= idataVec.size())
1003 0 : return false;
1004 170226 : (*this)(row, col) = std::min(
1005 : maxZInImg,
1006 170226 : static_cast<float>(bminval + maxZErrorInFile * 2 *
1007 170226 : idataVec[nDataVecIdx++]));
1008 : }
1009 :
1010 2459 : *ppByte = ptr;
1011 2459 : return true;
1012 : }
1013 :
1014 : NAMESPACE_LERC1_END
|
