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 5021 : while (sz > 0)
64 : { // One sequence per loop
65 5005 : READ_COUNT;
66 5005 : n -= 2;
67 5005 : if (count < 0)
68 : { // negative count for repeats
69 3222 : if (0 == n)
70 0 : return false;
71 3222 : --n; // only decrement after checking for 0 to avoid a (harmless)
72 : // unsigned integer overflow warning with ossfuzz
73 3222 : Byte b = *src++;
74 3222 : sz += count;
75 3222 : if (sz < 0)
76 0 : return false;
77 523624 : while (0 != count++)
78 520402 : *dst++ = b;
79 : }
80 : else
81 : { // No repeats, count is positive
82 1783 : if (sz < count || n < static_cast<size_t>(count))
83 0 : return false;
84 1783 : sz -= count;
85 1783 : n -= count;
86 6056 : while (0 != count--)
87 4273 : *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 2459 : static bool blockread(Byte **ppByte, size_t &size, std::vector<unsigned int> &d)
222 : {
223 2459 : if (!ppByte || !size)
224 0 : return false;
225 :
226 2459 : Byte numBits = **ppByte;
227 2459 : Byte n = stib67[numBits >> 6];
228 2459 : numBits &= 63; // bits 0-5;
229 : // cppcheck-suppress knownConditionTrueFalse
230 2459 : if (numBits >= 32 || n == 0 || size < 1 + static_cast<size_t>(n))
231 0 : return false;
232 2459 : *ppByte += 1;
233 2459 : size -= 1;
234 :
235 2459 : unsigned int numElements = 0;
236 2459 : memcpy(&numElements, *ppByte, n);
237 2459 : *ppByte += n;
238 2459 : size -= n;
239 2459 : if (static_cast<size_t>(numElements) > d.size())
240 0 : return false;
241 2459 : 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 2459 : d.resize(numElements);
249 2459 : unsigned int numBytes = (numElements * numBits + 7) / 8;
250 2459 : if (size < numBytes)
251 0 : return false;
252 2459 : size -= numBytes;
253 :
254 2459 : int bits = 0; // Available in accumulator, at the high end
255 2459 : unsigned int acc = 0;
256 172685 : for (unsigned int &val : d)
257 : {
258 170226 : if (bits >= numBits)
259 : { // Enough bits in accumulator
260 132540 : val = acc >> (32 - numBits);
261 132540 : acc <<= numBits;
262 132540 : bits -= numBits;
263 132540 : continue;
264 : }
265 :
266 : // Need to reload the accumulator
267 37686 : val = 0;
268 37686 : if (bits)
269 : {
270 18883 : val = acc >> (32 - bits);
271 18883 : val <<= (numBits - bits);
272 : }
273 37686 : unsigned int nb = std::min(numBytes, 4u);
274 37686 : if (4u == nb)
275 37489 : memcpy(&acc, *ppByte, 4);
276 : else // Read only a few bytes at the high end of acc
277 197 : memcpy(reinterpret_cast<Byte *>(&acc) + (4 - nb), *ppByte, nb);
278 37686 : *ppByte += nb;
279 37686 : numBytes -= nb;
280 :
281 37686 : bits += 32 - numBits;
282 37686 : val |= acc >> bits;
283 37686 : acc <<= 32 - bits;
284 : }
285 2459 : 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.0 && maxValInImg != 1.0)
500 0 : return false; // Only 0 and 1 are valid
501 0 : bool v = (maxValInImg != 0.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 - zMin) / (2 * maxZError) > MAXQ) // max of 28 bits
622 80 : return (int)(1 + nValues * sizeof(float)); // Stored as such
623 16615 : unsigned int maxElem = static_cast<unsigned int>(
624 16615 : ((double)zMax - zMin) / (2 * maxZError) + 0.5);
625 16615 : int nb = 1 + numBytesFlt(zMin);
626 16615 : if (maxElem == 0)
627 3304 : return nb;
628 13311 : return nb + 1 + numBytesUInt(nValues) + (nValues * nBits(maxElem) + 7) / 8;
629 : }
630 :
631 : // Pass bArr == nullptr to estimate the size but skip the write
632 41 : bool Lerc1Image::writeTiles(double maxZError, int numTilesV, int numTilesH,
633 : Byte *bArr, int &numBytes, float &maxValInImg) const
634 : {
635 41 : if (numTilesV == 0 || numTilesH == 0)
636 0 : return false;
637 41 : numBytes = 0;
638 41 : maxValInImg = -FLT_MAX;
639 41 : int tileHeight = static_cast<int>(getHeight() / numTilesV);
640 41 : int tileWidth = static_cast<int>(getWidth() / numTilesH);
641 1291 : for (int v0 = 0; v0 < getHeight(); v0 += tileHeight)
642 : {
643 1250 : int v1 = std::min(getHeight(), v0 + tileHeight);
644 74980 : for (int h0 = 0; h0 < getWidth(); h0 += tileWidth)
645 : {
646 73730 : int h1 = std::min(getWidth(), h0 + tileWidth);
647 73730 : float zMin = 0, zMax = 0;
648 73730 : int numValidPixel = 0, numFinite = 0;
649 73730 : if (!computeZStats(v0, v1, h0, h1, zMin, zMax, numValidPixel,
650 : numFinite))
651 0 : return false;
652 :
653 73730 : if (maxValInImg < zMax)
654 125 : maxValInImg = zMax;
655 :
656 73730 : int numBytesNeeded = 1;
657 73730 : if (numValidPixel != 0)
658 : {
659 10613 : if (numFinite == 0 && numValidPixel == (v1 - v0) * (h1 - h0) &&
660 287 : isallsameval(v0, v1, h0, h1))
661 287 : numBytesNeeded = 5; // Stored as non-finite constant block
662 : else
663 : {
664 : numBytesNeeded =
665 10039 : numBytesZTile(numValidPixel, zMin, zMax, maxZError);
666 : // Try moving zMin up by almost maxZError,
667 : // it may require fewer bytes
668 10039 : float zm = static_cast<float>(zMin + 0.999999 * maxZError);
669 10039 : if (numFinite == numValidPixel && zm <= zMax)
670 : {
671 : int nBN =
672 6655 : numBytesZTile(numValidPixel, zm, zMax, maxZError);
673 : // Maybe an int value for zMin saves a few bytes?
674 6655 : if (zMin < floorf(zm))
675 : {
676 1 : int nBNi = numBytesZTile(numValidPixel, floorf(zm),
677 : zMax, maxZError);
678 1 : if (nBNi < nBN)
679 : {
680 1 : zm = floorf(zm);
681 1 : nBN = nBNi;
682 : }
683 : }
684 6655 : if (nBN < numBytesNeeded)
685 : {
686 2 : zMin = zm;
687 2 : numBytesNeeded = nBN;
688 : }
689 : }
690 : }
691 : }
692 73730 : numBytes += numBytesNeeded;
693 :
694 73730 : if (bArr)
695 : { // Skip the write if no pointer was provided
696 14505 : int numBytesWritten = 0;
697 14569 : if (numFinite == 0 && numValidPixel == (v1 - v0) * (h1 - h0) &&
698 64 : isallsameval(v0, v1, h0, h1))
699 : {
700 : // direct write as non-finite const block, 4 byte float
701 64 : *bArr++ = 3; // 3 | bits67[3]
702 64 : bArr = writeFlt(bArr, (*this)(v0, h0), sizeof(float));
703 64 : numBytesWritten = 5;
704 : }
705 : else
706 : {
707 14441 : if (!writeZTile(&bArr, numBytesWritten, v0, v1, h0, h1,
708 : numValidPixel, zMin, zMax, maxZError))
709 0 : return false;
710 : }
711 14505 : if (numBytesWritten != numBytesNeeded)
712 0 : return false;
713 : }
714 : }
715 : }
716 41 : return true;
717 : }
718 :
719 16 : bool Lerc1Image::readTiles(double maxZErrorInFile, int numTilesV, int numTilesH,
720 : float maxValInImg, Byte *bArr,
721 : size_t nRemainingBytes)
722 : {
723 16 : if (numTilesV == 0 || numTilesH == 0)
724 0 : return false;
725 16 : int tileHeight = static_cast<int>(getHeight() / numTilesV);
726 16 : int tileWidth = static_cast<int>(getWidth() / numTilesH);
727 16 : if (tileWidth <= 0 || tileHeight <= 0) // Prevent infinite loop
728 0 : return false;
729 267 : for (int r0 = 0; r0 < getHeight(); r0 += tileHeight)
730 : {
731 251 : int r1 = std::min(getHeight(), r0 + tileHeight);
732 14760 : for (int c0 = 0; c0 < getWidth(); c0 += tileWidth)
733 : {
734 14509 : int c1 = std::min(getWidth(), c0 + tileWidth);
735 14509 : if (!readZTile(&bArr, nRemainingBytes, r0, r1, c0, c1,
736 : maxZErrorInFile, maxValInImg))
737 0 : return false;
738 : }
739 : }
740 16 : return true;
741 : }
742 :
743 73730 : bool Lerc1Image::computeZStats(int r0, int r1, int c0, int c1, float &zMin,
744 : float &zMax, int &numValidPixel,
745 : int &numFinite) const
746 : {
747 73730 : if (r0 < 0 || c0 < 0 || r1 > getHeight() || c1 > getWidth())
748 0 : return false;
749 73730 : zMin = FLT_MAX;
750 73730 : zMax = -FLT_MAX;
751 73730 : numValidPixel = 0;
752 73730 : numFinite = 0;
753 713730 : for (int row = r0; row < r1; row++)
754 11387900 : for (int col = c0; col < c1; col++)
755 10747900 : if (IsValid(row, col))
756 : {
757 1050370 : numValidPixel++;
758 1050370 : float val = (*this)(row, col);
759 1050370 : if (std::isfinite(val))
760 1005590 : numFinite++;
761 : else
762 44785 : zMin = NAN; // Serves as a flag, this block will be stored
763 1050370 : if (val < zMin)
764 32396 : zMin = val;
765 1050370 : if (val > zMax)
766 37154 : zMax = val;
767 : }
768 73730 : if (0 == numValidPixel)
769 63404 : zMin = zMax = 0;
770 73730 : return true;
771 : }
772 :
773 : // Returns true if all floats in the region have exactly the same binary
774 : // representation This makes it usable for non-finite values
775 351 : bool Lerc1Image::isallsameval(int r0, int r1, int c0, int c1) const
776 : {
777 351 : uint32_t val = *reinterpret_cast<const uint32_t *>(&(*this)(r0, c0));
778 3959 : for (int row = r0; row < r1; row++)
779 42168 : for (int col = c0; col < c1; col++)
780 38560 : if (val != *reinterpret_cast<const uint32_t *>(&(*this)(row, col)))
781 0 : return false;
782 351 : return true;
783 : }
784 :
785 : //
786 : // Assumes that buffer at *ppByte is large enough for this particular block
787 : // Returns number of bytes used in numBytes
788 : //
789 14441 : bool Lerc1Image::writeZTile(Byte **ppByte, int &numBytes, int r0, int r1,
790 : int c0, int c1, int numValidPixel, float zMin,
791 : float zMax, double maxZError) const
792 : {
793 14441 : Byte *ptr = *ppByte;
794 14441 : int cntPixel = 0;
795 14441 : if (numValidPixel == 0 || (zMin == 0 && zMax == 0))
796 : {
797 10603 : *(*ppByte)++ = 2; // mark tile as constant 0
798 10603 : numBytes = 1;
799 10603 : return true;
800 : }
801 7657 : if (maxZError == 0 || !std::isfinite(zMin) || !std::isfinite(zMax) ||
802 3819 : ((double)zMax - zMin) / (2 * maxZError) > MAXQ)
803 : { // store valid pixels as floating point
804 19 : *ptr++ = 0;
805 228 : for (int row = r0; row < r1; row++)
806 2508 : for (int col = c0; col < c1; col++)
807 2299 : if (IsValid(row, col))
808 : {
809 2123 : memcpy(ptr, &((*this)(row, col)), sizeof(float));
810 2123 : ptr += sizeof(float);
811 2123 : cntPixel++;
812 : }
813 19 : if (cntPixel != numValidPixel)
814 0 : return false;
815 : }
816 : else
817 : {
818 3819 : Byte flag = 1; // bitstuffed int array
819 3819 : double f = 0.5 / maxZError; // conversion to int multiplier
820 3819 : unsigned int maxElem = (unsigned int)(((double)zMax - zMin) * f + 0.5);
821 3819 : if (maxElem == 0)
822 1364 : flag = 3; // mark tile as constant zMin
823 3819 : int n = numBytesFlt(zMin); // n in { 1, 2, 4 }
824 3819 : *ptr++ = (flag | bits67[n - 1]);
825 3819 : ptr = writeFlt(ptr, zMin, n);
826 3819 : if (maxElem > 0)
827 : {
828 2455 : int numBits = nBits(maxElem);
829 2455 : n = numBytesUInt(numValidPixel);
830 : // use bits67 to encode the type used for numElements: Byte, ushort, or uint
831 : // n is in {1, 2, 4}
832 : // 0xc0 is invalid, will trigger an error
833 2455 : *ptr++ = static_cast<Byte>(numBits | bits67[n - 1]);
834 2455 : memcpy(ptr, &numValidPixel, n);
835 2455 : ptr += n;
836 :
837 2455 : unsigned int acc = 0; // Accumulator
838 2455 : int bits = 32; // Available
839 :
840 26310 : for (int row = r0; row < r1; row++)
841 2281090 : for (int col = c0; col < c1; col++)
842 2257240 : if (IsValid(row, col))
843 : {
844 162134 : cntPixel++;
845 : auto val = static_cast<unsigned int>(
846 162134 : ((double)(*this)(row, col) - zMin) * f + 0.5);
847 :
848 162134 : if (bits >= numBits)
849 : { // no accumulator overflow
850 131812 : acc |= val << (bits - numBits);
851 131812 : bits -= numBits;
852 : }
853 : else
854 : { // accum overflowing
855 30322 : acc |= val >> (numBits - bits);
856 30322 : memcpy(ptr, &acc, sizeof(acc));
857 30322 : ptr += sizeof(acc);
858 30322 : bits += 32 - numBits; // under 32
859 30322 : acc = val << bits;
860 : }
861 : }
862 :
863 2455 : if (cntPixel != numValidPixel)
864 0 : return false;
865 :
866 : // There are between 1 and 4 bytes left in the accumulator
867 2455 : int nbytes = 4;
868 2747 : while (bits >= 8)
869 : {
870 292 : acc >>= 8;
871 292 : bits -= 8;
872 292 : nbytes--;
873 : }
874 2455 : memcpy(ptr, &acc, nbytes);
875 2455 : ptr += nbytes;
876 : }
877 : }
878 :
879 3838 : numBytes = static_cast<int>(ptr - *ppByte);
880 3838 : *ppByte = ptr;
881 3838 : return true;
882 : }
883 :
884 : // Read a float encoded as unsigned char, signed short or float
885 : // n is the number of bytes
886 3887 : static float readFlt(const Byte *ptr, int n)
887 : {
888 3887 : if (n == 4)
889 : {
890 : float val;
891 128 : memcpy(&val, ptr, 4);
892 128 : return val;
893 : }
894 3759 : if (n == 2)
895 : {
896 : signed short s;
897 169 : memcpy(&s, ptr, 2);
898 169 : return static_cast<float>(s);
899 : }
900 3590 : return static_cast<float>(static_cast<signed char>(*ptr));
901 : }
902 :
903 14509 : bool Lerc1Image::readZTile(Byte **ppByte, size_t &nRemainingBytes, int r0,
904 : int r1, int c0, int c1, double maxZErrorInFile,
905 : float maxZInImg)
906 : {
907 14509 : Byte *ptr = *ppByte;
908 :
909 14509 : if (nRemainingBytes < 1)
910 0 : return false;
911 14509 : Byte comprFlag = *ptr++;
912 14509 : nRemainingBytes -= 1;
913 : // Used if bit-stuffed
914 14509 : Byte n = stib67[comprFlag >> 6];
915 14509 : comprFlag &= 63;
916 : // cppcheck-suppress knownConditionTrueFalse
917 14509 : if (n == 0 || comprFlag > 3)
918 0 : return false;
919 :
920 14509 : if (comprFlag == 2)
921 : { // entire zTile is 0
922 101387 : for (int row = r0; row < r1; row++)
923 881936 : for (int col = c0; col < c1; col++)
924 791152 : (*this)(row, col) = 0.0f;
925 10603 : *ppByte = ptr;
926 10603 : return true;
927 : }
928 :
929 3906 : if (comprFlag == 0)
930 : { // Stored
931 228 : for (int row = r0; row < r1; row++)
932 2508 : for (int col = c0; col < c1; col++)
933 2299 : if (IsValid(row, col))
934 : {
935 2123 : if (nRemainingBytes < sizeof(float))
936 0 : return false;
937 2123 : memcpy(&(*this)(row, col), ptr, sizeof(float));
938 2123 : ptr += sizeof(float);
939 2123 : nRemainingBytes -= sizeof(float);
940 : }
941 19 : *ppByte = ptr;
942 19 : return true;
943 : }
944 :
945 3887 : if (nRemainingBytes < n)
946 0 : return false;
947 3887 : float minval = readFlt(ptr, n);
948 3887 : ptr += n;
949 3887 : nRemainingBytes -= n;
950 :
951 3887 : if (comprFlag == 3)
952 : { // all min val, regardless of mask
953 13044 : for (int row = r0; row < r1; row++)
954 106656 : for (int col = c0; col < c1; col++)
955 95040 : (*this)(row, col) = minval;
956 1428 : *ppByte = ptr;
957 1428 : return true;
958 : }
959 :
960 2459 : idataVec.resize((r1 - r0) * (c1 - c0)); // max size, gets adjusted
961 2459 : if (!blockread(&ptr, nRemainingBytes, idataVec))
962 0 : return false;
963 :
964 2459 : size_t numValid = idataVec.size();
965 2459 : size_t i = 0;
966 2459 : double q = maxZErrorInFile * 2; // quanta
967 28365 : for (int row = r0; row < r1; row++)
968 3334790 : for (int col = c0; col < c1; col++)
969 3308890 : if (IsValid(row, col))
970 : {
971 170226 : if (i >= numValid)
972 0 : return false;
973 170226 : (*this)(row, col) = std::min(
974 340452 : maxZInImg, static_cast<float>(minval + q * idataVec[i++]));
975 : }
976 2459 : if (i != numValid)
977 0 : return false;
978 :
979 2459 : *ppByte = ptr;
980 2459 : return true;
981 : }
982 :
983 : NAMESPACE_LERC1_END
|
