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 : // cppcheck-suppress bufferAccessOutOfBounds
541 5 : RDVAR(pByte, height);
542 : // cppcheck-suppress bufferAccessOutOfBounds
543 5 : RDVAR(pByte, width);
544 5 : RDVAR(pByte, maxZErrorInFile);
545 : (void)pByte;
546 :
547 5 : if (version != CNT_Z_VER || type != CNT_Z)
548 0 : return false;
549 5 : if (width <= 0 || width > 20000 || height <= 0 || height > 20000)
550 0 : return false;
551 5 : if (static_cast<size_t>(width) * height > TOO_LARGE)
552 0 : return false;
553 :
554 5 : return true;
555 : #undef RDVAR
556 : }
557 :
558 12 : bool Lerc1Image::findTiling(double maxZError, int &numTilesVertA,
559 : int &numTilesHoriA, int &numBytesOptA,
560 : float &maxValInImgA) const
561 : {
562 : // entire image as 1 block, this is usually the worst case
563 12 : numTilesVertA = numTilesHoriA = 1;
564 12 : if (!writeTiles(maxZError, 1, 1, nullptr, numBytesOptA, maxValInImgA))
565 0 : return false;
566 : // The actual figure may be different due to round-down
567 12 : static const std::vector<int> tileWidthArr = {8, 11, 15, 20, 32, 64};
568 17 : for (auto tileWidth : tileWidthArr)
569 : {
570 17 : int numTilesVert = static_cast<int>(getHeight() / tileWidth);
571 17 : int numTilesHori = static_cast<int>(getWidth() / tileWidth);
572 :
573 17 : if (numTilesVert * numTilesHori < 2)
574 0 : return true;
575 :
576 17 : int numBytes = 0;
577 : float maxVal;
578 17 : if (!writeTiles(maxZError, numTilesVert, numTilesHori, nullptr,
579 : numBytes, maxVal))
580 0 : return false;
581 17 : if (numBytes > numBytesOptA)
582 12 : break; // Stop when size start to increase
583 5 : if (numBytes < numBytesOptA)
584 : {
585 5 : numTilesVertA = numTilesVert;
586 5 : numTilesHoriA = numTilesHori;
587 5 : numBytesOptA = numBytes;
588 : }
589 : }
590 12 : return true;
591 : }
592 :
593 : // n is 1, 2 or 4
594 3883 : static Byte *writeFlt(Byte *ptr, float z, int n)
595 : {
596 3883 : if (4 == n)
597 125 : memcpy(ptr, &z, 4);
598 3758 : else if (1 == n)
599 3589 : *ptr = static_cast<Byte>(static_cast<signed char>(z));
600 : else
601 : {
602 169 : signed short s = static_cast<signed short>(z);
603 169 : memcpy(ptr, &s, 2);
604 : }
605 3883 : return ptr + n;
606 : }
607 :
608 : // Only small, exact integer values return 1 or 2, otherwise 4
609 20434 : static int numBytesFlt(float z)
610 : {
611 20434 : if (!std::isfinite(z) || z > SHRT_MAX || z < SHRT_MIN || z != int16_t(z))
612 6974 : return 4;
613 13460 : if (z > SCHAR_MAX || z < SCHAR_MIN)
614 668 : return 2;
615 12792 : return 1;
616 : }
617 :
618 16695 : static int numBytesZTile(int nValues, float zMin, float zMax, double maxZError)
619 : {
620 16695 : if (nValues == 0 || (zMin == 0 && zMax == 0))
621 0 : return 1;
622 33310 : if (maxZError == 0 || !std::isfinite(zMin) || !std::isfinite(zMax) ||
623 16615 : ((double)zMax - (double)zMin) / (2 * maxZError) >
624 : MAXQ) // max of 28 bits
625 80 : return (int)(1 + nValues * sizeof(float)); // Stored as such
626 16615 : unsigned int maxElem = static_cast<unsigned int>(
627 16615 : ((double)zMax - (double)zMin) / (2 * maxZError) + 0.5);
628 16615 : int nb = 1 + numBytesFlt(zMin);
629 16615 : if (maxElem == 0)
630 3304 : return nb;
631 13311 : return nb + 1 + numBytesUInt(nValues) + (nValues * nBits(maxElem) + 7) / 8;
632 : }
633 :
634 : // Pass bArr == nullptr to estimate the size but skip the write
635 41 : bool Lerc1Image::writeTiles(double maxZError, int numTilesV, int numTilesH,
636 : Byte *bArr, int &numBytes, float &maxValInImg) const
637 : {
638 41 : if (numTilesV == 0 || numTilesH == 0)
639 0 : return false;
640 41 : numBytes = 0;
641 41 : maxValInImg = -FLT_MAX;
642 41 : int tileHeight = static_cast<int>(getHeight() / numTilesV);
643 41 : int tileWidth = static_cast<int>(getWidth() / numTilesH);
644 1291 : for (int v0 = 0; v0 < getHeight(); v0 += tileHeight)
645 : {
646 1250 : int v1 = std::min(getHeight(), v0 + tileHeight);
647 74980 : for (int h0 = 0; h0 < getWidth(); h0 += tileWidth)
648 : {
649 73730 : int h1 = std::min(getWidth(), h0 + tileWidth);
650 73730 : float zMin = 0, zMax = 0;
651 73730 : int numValidPixel = 0, numFinite = 0;
652 73730 : if (!computeZStats(v0, v1, h0, h1, zMin, zMax, numValidPixel,
653 : numFinite))
654 0 : return false;
655 :
656 73730 : if (maxValInImg < zMax)
657 125 : maxValInImg = zMax;
658 :
659 73730 : int numBytesNeeded = 1;
660 73730 : if (numValidPixel != 0)
661 : {
662 10613 : if (numFinite == 0 && numValidPixel == (v1 - v0) * (h1 - h0) &&
663 287 : isallsameval(v0, v1, h0, h1))
664 287 : numBytesNeeded = 5; // Stored as non-finite constant block
665 : else
666 : {
667 : numBytesNeeded =
668 10039 : numBytesZTile(numValidPixel, zMin, zMax, maxZError);
669 : // Try moving zMin up by almost maxZError,
670 : // it may require fewer bytes
671 10039 : float zm = static_cast<float>(zMin + 0.999999 * maxZError);
672 10039 : if (numFinite == numValidPixel && zm <= zMax)
673 : {
674 : int nBN =
675 6655 : numBytesZTile(numValidPixel, zm, zMax, maxZError);
676 : // Maybe an int value for zMin saves a few bytes?
677 6655 : if (zMin < floorf(zm))
678 : {
679 1 : int nBNi = numBytesZTile(numValidPixel, floorf(zm),
680 : zMax, maxZError);
681 1 : if (nBNi < nBN)
682 : {
683 1 : zm = floorf(zm);
684 1 : nBN = nBNi;
685 : }
686 : }
687 6655 : if (nBN < numBytesNeeded)
688 : {
689 2 : zMin = zm;
690 2 : numBytesNeeded = nBN;
691 : }
692 : }
693 : }
694 : }
695 73730 : numBytes += numBytesNeeded;
696 :
697 73730 : if (bArr)
698 : { // Skip the write if no pointer was provided
699 14505 : int numBytesWritten = 0;
700 14569 : if (numFinite == 0 && numValidPixel == (v1 - v0) * (h1 - h0) &&
701 64 : isallsameval(v0, v1, h0, h1))
702 : {
703 : // direct write as non-finite const block, 4 byte float
704 64 : *bArr++ = 3; // 3 | bits67[3]
705 64 : bArr = writeFlt(bArr, (*this)(v0, h0), sizeof(float));
706 64 : numBytesWritten = 5;
707 : }
708 : else
709 : {
710 14441 : if (!writeZTile(&bArr, numBytesWritten, v0, v1, h0, h1,
711 : numValidPixel, zMin, zMax, maxZError))
712 0 : return false;
713 : }
714 14505 : if (numBytesWritten != numBytesNeeded)
715 0 : return false;
716 : }
717 : }
718 : }
719 41 : return true;
720 : }
721 :
722 16 : bool Lerc1Image::readTiles(double maxZErrorInFile, int numTilesV, int numTilesH,
723 : float maxValInImg, Byte *bArr,
724 : size_t nRemainingBytes)
725 : {
726 16 : if (numTilesV == 0 || numTilesH == 0)
727 0 : return false;
728 16 : int tileHeight = static_cast<int>(getHeight() / numTilesV);
729 16 : int tileWidth = static_cast<int>(getWidth() / numTilesH);
730 16 : if (tileWidth <= 0 || tileHeight <= 0) // Prevent infinite loop
731 0 : return false;
732 267 : for (int r0 = 0; r0 < getHeight(); r0 += tileHeight)
733 : {
734 251 : int r1 = std::min(getHeight(), r0 + tileHeight);
735 14760 : for (int c0 = 0; c0 < getWidth(); c0 += tileWidth)
736 : {
737 14509 : int c1 = std::min(getWidth(), c0 + tileWidth);
738 14509 : if (!readZTile(&bArr, nRemainingBytes, r0, r1, c0, c1,
739 : maxZErrorInFile, maxValInImg))
740 0 : return false;
741 : }
742 : }
743 16 : return true;
744 : }
745 :
746 73730 : bool Lerc1Image::computeZStats(int r0, int r1, int c0, int c1, float &zMin,
747 : float &zMax, int &numValidPixel,
748 : int &numFinite) const
749 : {
750 73730 : if (r0 < 0 || c0 < 0 || r1 > getHeight() || c1 > getWidth())
751 0 : return false;
752 73730 : zMin = FLT_MAX;
753 73730 : zMax = -FLT_MAX;
754 73730 : numValidPixel = 0;
755 73730 : numFinite = 0;
756 713730 : for (int row = r0; row < r1; row++)
757 11387900 : for (int col = c0; col < c1; col++)
758 10747900 : if (IsValid(row, col))
759 : {
760 1050370 : numValidPixel++;
761 1050370 : float val = (*this)(row, col);
762 1050370 : if (std::isfinite(val))
763 1005590 : numFinite++;
764 : else
765 44785 : zMin = NAN; // Serves as a flag, this block will be stored
766 1050370 : if (val < zMin)
767 32396 : zMin = val;
768 1050370 : if (val > zMax)
769 37154 : zMax = val;
770 : }
771 73730 : if (0 == numValidPixel)
772 63404 : zMin = zMax = 0;
773 73730 : return true;
774 : }
775 :
776 : // Returns true if all floats in the region have exactly the same binary
777 : // representation This makes it usable for non-finite values
778 351 : bool Lerc1Image::isallsameval(int r0, int r1, int c0, int c1) const
779 : {
780 351 : uint32_t val = *reinterpret_cast<const uint32_t *>(&(*this)(r0, c0));
781 3959 : for (int row = r0; row < r1; row++)
782 42168 : for (int col = c0; col < c1; col++)
783 38560 : if (val != *reinterpret_cast<const uint32_t *>(&(*this)(row, col)))
784 0 : return false;
785 351 : return true;
786 : }
787 :
788 : //
789 : // Assumes that buffer at *ppByte is large enough for this particular block
790 : // Returns number of bytes used in numBytes
791 : //
792 14441 : bool Lerc1Image::writeZTile(Byte **ppByte, int &numBytes, int r0, int r1,
793 : int c0, int c1, int numValidPixel, float zMin,
794 : float zMax, double maxZError) const
795 : {
796 14441 : Byte *ptr = *ppByte;
797 14441 : int cntPixel = 0;
798 14441 : if (numValidPixel == 0 || (zMin == 0 && zMax == 0))
799 : {
800 10603 : *(*ppByte)++ = 2; // mark tile as constant 0
801 10603 : numBytes = 1;
802 10603 : return true;
803 : }
804 7657 : if (maxZError == 0 || !std::isfinite(zMin) || !std::isfinite(zMax) ||
805 3819 : ((double)zMax - zMin) / (2 * maxZError) > MAXQ)
806 : { // store valid pixels as floating point
807 19 : *ptr++ = 0;
808 228 : for (int row = r0; row < r1; row++)
809 2508 : for (int col = c0; col < c1; col++)
810 2299 : if (IsValid(row, col))
811 : {
812 2123 : memcpy(ptr, &((*this)(row, col)), sizeof(float));
813 2123 : ptr += sizeof(float);
814 2123 : cntPixel++;
815 : }
816 19 : if (cntPixel != numValidPixel)
817 0 : return false;
818 : }
819 : else
820 : {
821 3819 : Byte flag = 1; // bitstuffed int array
822 3819 : double f = 0.5 / maxZError; // conversion to int multiplier
823 3819 : unsigned int maxElem = (unsigned int)(((double)zMax - zMin) * f + 0.5);
824 3819 : if (maxElem == 0)
825 1364 : flag = 3; // mark tile as constant zMin
826 3819 : int n = numBytesFlt(zMin); // n in { 1, 2, 4 }
827 3819 : *ptr++ = (flag | bits67[n - 1]);
828 3819 : ptr = writeFlt(ptr, zMin, n);
829 3819 : if (maxElem > 0)
830 : {
831 2455 : int numBits = nBits(maxElem);
832 2455 : n = numBytesUInt(numValidPixel);
833 : // use bits67 to encode the type used for numElements: Byte, ushort, or uint
834 : // n is in {1, 2, 4}
835 : // 0xc0 is invalid, will trigger an error
836 2455 : *ptr++ = static_cast<Byte>(numBits | bits67[n - 1]);
837 2455 : memcpy(ptr, &numValidPixel, n);
838 2455 : ptr += n;
839 :
840 2455 : unsigned int acc = 0; // Accumulator
841 2455 : int bits = 32; // Available
842 :
843 26310 : for (int row = r0; row < r1; row++)
844 2281090 : for (int col = c0; col < c1; col++)
845 2257240 : if (IsValid(row, col))
846 : {
847 162134 : cntPixel++;
848 : auto val = static_cast<unsigned int>(
849 162134 : ((double)(*this)(row, col) - zMin) * f + 0.5);
850 :
851 162134 : if (bits >= numBits)
852 : { // no accumulator overflow
853 131812 : acc |= val << (bits - numBits);
854 131812 : bits -= numBits;
855 : }
856 : else
857 : { // accum overflowing
858 30322 : acc |= val >> (numBits - bits);
859 30322 : memcpy(ptr, &acc, sizeof(acc));
860 30322 : ptr += sizeof(acc);
861 30322 : bits += 32 - numBits; // under 32
862 30322 : acc = val << bits;
863 : }
864 : }
865 :
866 2455 : if (cntPixel != numValidPixel)
867 0 : return false;
868 :
869 : // There are between 1 and 4 bytes left in the accumulator
870 2455 : int nbytes = 4;
871 2747 : while (bits >= 8)
872 : {
873 292 : acc >>= 8;
874 292 : bits -= 8;
875 292 : nbytes--;
876 : }
877 2455 : memcpy(ptr, &acc, nbytes);
878 2455 : ptr += nbytes;
879 : }
880 : }
881 :
882 3838 : numBytes = static_cast<int>(ptr - *ppByte);
883 3838 : *ppByte = ptr;
884 3838 : return true;
885 : }
886 :
887 : // Read a float encoded as unsigned char, signed short or float
888 : // n is the number of bytes
889 3884 : static float readFlt(const Byte *ptr, int n)
890 : {
891 3884 : if (n == 4)
892 : {
893 : float val;
894 125 : memcpy(&val, ptr, 4);
895 125 : return val;
896 : }
897 3759 : if (n == 2)
898 : {
899 : signed short s;
900 169 : memcpy(&s, ptr, 2);
901 169 : return static_cast<float>(s);
902 : }
903 3590 : return static_cast<float>(static_cast<signed char>(*ptr));
904 : }
905 :
906 14509 : bool Lerc1Image::readZTile(Byte **ppByte, size_t &nRemainingBytes, int r0,
907 : int r1, int c0, int c1, double maxZErrorInFile,
908 : float maxZInImg)
909 : {
910 14509 : Byte *ptr = *ppByte;
911 :
912 14509 : if (nRemainingBytes < 1)
913 0 : return false;
914 14509 : Byte comprFlag = *ptr++;
915 14509 : nRemainingBytes -= 1;
916 : // Used if bit-stuffed
917 14509 : Byte n = stib67[comprFlag >> 6];
918 14509 : comprFlag &= 63;
919 : // cppcheck-suppress knownConditionTrueFalse
920 14509 : if (n == 0 || comprFlag > 3)
921 0 : return false;
922 :
923 14509 : if (comprFlag == 2)
924 : { // entire zTile is 0
925 101387 : for (int row = r0; row < r1; row++)
926 881936 : for (int col = c0; col < c1; col++)
927 791152 : (*this)(row, col) = 0.0f;
928 10603 : *ppByte = ptr;
929 10603 : return true;
930 : }
931 :
932 3906 : if (comprFlag == 0)
933 : { // Stored
934 1770 : for (int row = r0; row < r1; row++)
935 793554 : for (int col = c0; col < c1; col++)
936 791806 : if (IsValid(row, col))
937 : {
938 9731 : if (nRemainingBytes < sizeof(float))
939 0 : return false;
940 9731 : memcpy(&(*this)(row, col), ptr, sizeof(float));
941 9731 : ptr += sizeof(float);
942 9731 : nRemainingBytes -= sizeof(float);
943 : }
944 22 : *ppByte = ptr;
945 22 : return true;
946 : }
947 :
948 3884 : if (nRemainingBytes < n)
949 0 : return false;
950 3884 : float minval = readFlt(ptr, n);
951 3884 : ptr += n;
952 3884 : nRemainingBytes -= n;
953 :
954 3884 : if (comprFlag == 3)
955 : { // all min val, regardless of mask
956 13044 : for (int row = r0; row < r1; row++)
957 106656 : for (int col = c0; col < c1; col++)
958 95040 : (*this)(row, col) = minval;
959 1428 : *ppByte = ptr;
960 1428 : return true;
961 : }
962 :
963 2456 : idataVec.resize(static_cast<size_t>(r1 - r0) *
964 2456 : (c1 - c0)); // max size, gets adjusted
965 2456 : if (!blockread(&ptr, nRemainingBytes, idataVec))
966 0 : return false;
967 :
968 2456 : size_t numValid = idataVec.size();
969 2456 : size_t i = 0;
970 2456 : double q = maxZErrorInFile * 2; // quanta
971 26823 : for (int row = r0; row < r1; row++)
972 2543750 : for (int col = c0; col < c1; col++)
973 2519380 : if (IsValid(row, col))
974 : {
975 162534 : if (i >= numValid)
976 0 : return false;
977 162534 : (*this)(row, col) = std::min(
978 325068 : maxZInImg, static_cast<float>(minval + q * idataVec[i++]));
979 : }
980 2456 : if (i != numValid)
981 0 : return false;
982 :
983 2456 : *ppByte = ptr;
984 2456 : return true;
985 : }
986 :
987 : NAMESPACE_LERC1_END
|
