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