TerrainGen coverage

terraingen/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
212 / 215
98.6%
Branches:
146 / 155
94.2%
Functions:
28 / 28
100.0%
raster/geotiff/tiff_codecs.cpp
Line Branch Exec Source
1 #include "terraingen/raster/geotiff/tiff_codecs.h"
2
3 #include "terraingen/raster/geotiff/geotiff.h"
4
5 #include <miniz.h>
6
7 #include <array>
8 #include <cstring>
9
10 namespace terraingen::detail {
11
12 namespace {
13
14 constexpr int kClear = 256;
15 constexpr int kEndOfInfo = 257;
16 constexpr int kFirstCode = 258;
17 constexpr int kMaxCode = 4096;
18
19 /// Reads MSB-first codes of varying width.
20 class BitReader {
21 public:
22 126 explicit BitReader(std::span<const std::uint8_t> data) : data_(data) {}
23
24 /// The next `width`-bit code, or EndOfInfo when the data runs out.
25 567784 int Next(int width) {
26
2/2
✓ Branch 0 taken 786615 times.
✓ Branch 1 taken 567784 times.
 1354399 while (count_ < width) {
27
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 786615 times.
 786615 if (position_ >= data_.size()) {
28 ✗ return kEndOfInfo;
29 }
30 786615 buffer_ = (buffer_ << 8) | data_[position_++];
31 786615 count_ += 8;
32 }
33 567784 count_ -= width;
34 567784 return static_cast<int>((buffer_ >> count_) & ((1u << width) - 1u));
35 }
36
37 private:
38 std::span<const std::uint8_t> data_;
39 std::size_t position_ = 0;
40 std::uint32_t buffer_ = 0;
41 int count_ = 0;
42 };
43
44 /// Writes MSB-first codes of varying width.
45 class BitWriter {
46 public:
47 86112819 void Put(int code, int width) {
48 86112819 buffer_ = (buffer_ << width) | static_cast<std::uint32_t>(code);
49 86112819 count_ += width;
50
2/2
✓ Branch 0 taken 121069862 times.
✓ Branch 1 taken 86112819 times.
 207182681 while (count_ >= 8) {
51 121069862 count_ -= 8;
52
1/1
✓ Branch 1 taken 121069862 times.
 121069862 bytes_.push_back(static_cast<std::uint8_t>(buffer_ >> count_));
53 }
54 86112819 }
55
56 1636 std::vector<std::uint8_t> Finish() {
57
2/2
✓ Branch 0 taken 1564 times.
✓ Branch 1 taken 72 times.
 1636 if (count_ > 0) {
58
1/1
✓ Branch 1 taken 1564 times.
 1564 bytes_.push_back(static_cast<std::uint8_t>(buffer_ << (8 - count_)));
59 1564 count_ = 0;
60 }
61 1636 return std::move(bytes_);
62 }
63
64 private:
65 std::vector<std::uint8_t> bytes_;
66 std::uint32_t buffer_ = 0;
67 int count_ = 0;
68 };
69
70 2 [[noreturn]] void Corrupt(const char* what) {
71
3/3
✓ Branch 2 taken 2 times.
✓ Branch 5 taken 2 times.
✓ Branch 8 taken 2 times.
 6 throw GeoTiffError(std::string("Corrupt LZW data: ") + what);
72 }
73
74 /// The LZW string table for decoding: each code's string as its prefix code and last byte.
75 class LzwDecodeTable {
76 public:
77 126 LzwDecodeTable() {
78
2/2
✓ Branch 0 taken 32256 times.
✓ Branch 1 taken 126 times.
 32382 for (int code = 0; code < 256; ++code) {
79 32256 suffix_[static_cast<std::size_t>(code)] = static_cast<std::uint8_t>(code);
80 32256 length_[static_cast<std::size_t>(code)] = 1;
81 }
82 126 }
83
84 /// The code the next added string gets.
85 2269288 int Next() const {
86 2269288 return next_;
87 }
88
89 /// Forgets every added string, as after Clear.
90 230 void Reset() {
91 230 next_ = kFirstCode;
92 230 }
93
94 /// Adds the string of `previous` followed by `last`.
95 567322 void Add(int previous, std::uint8_t last) {
96 567322 const auto entry = static_cast<std::size_t>(next_++);
97 567322 prefix_[entry] = static_cast<std::uint16_t>(previous);
98 567322 suffix_[entry] = last;
99 1134644 length_[entry] =
100 567322 static_cast<std::uint16_t>(length_[static_cast<std::size_t>(previous)] + 1);
101 567322 }
102
103 /// Appends the string of `code` to `out` and returns its first byte.
104 567551 std::uint8_t Emit(int code, std::vector<std::uint8_t>& out) const {
105 567551 const std::size_t start = out.size();
106 567551 out.resize(start + length_[static_cast<std::size_t>(code)]);
107
2/2
✓ Branch 1 taken 12907372 times.
✓ Branch 2 taken 567551 times.
 13474923 for (std::size_t i = out.size(); i > start; --i) {
108 12907372 out[i - 1] = suffix_[static_cast<std::size_t>(code)];
109 12907372 code = prefix_[static_cast<std::size_t>(code)];
110 }
111 567551 return out[start];
112 }
113
114 private:
115 std::array<std::uint16_t, kMaxCode> prefix_{};
116 std::array<std::uint8_t, kMaxCode> suffix_{};
117 std::array<std::uint16_t, kMaxCode> length_{};
118 int next_ = kFirstCode;
119 };
120
121 /// The LZW string table for encoding: (prefix code, next byte) -> code, open-addressed with a
122 /// generation stamp so that clearing it is constant time.
123 class LzwTable {
124 public:
125
3/3
✓ Branch 1 taken 1636 times.
✓ Branch 4 taken 1636 times.
✓ Branch 7 taken 1636 times.
 9816 LzwTable() : keys_(kSlots), codes_(kSlots), stamps_(kSlots, 0) {}
126
127 21707 void Clear() {
128 21707 ++generation_;
129 21707 }
130
131 /// The code for `key`, or -1.
132 417901232 int Find(std::uint32_t key) const {
133 417901232 for (std::size_t slot = Hash(key);; slot = (slot + 1) & (kSlots - 1)) {
134
2/2
✓ Branch 1 taken 86086205 times.
✓ Branch 2 taken 354343304 times.
 440429509 if (stamps_[slot] != generation_) {
135 86086205 return -1;
136 }
137
2/2
✓ Branch 1 taken 331815027 times.
✓ Branch 2 taken 22528277 times.
 354343304 if (keys_[slot] == key) {
138 331815027 return codes_[slot];
139 }
140 }
141 }
142
143 86086205 void Insert(std::uint32_t key, int code) {
144 86086205 std::size_t slot = Hash(key);
145
2/2
✓ Branch 1 taken 10737878 times.
✓ Branch 2 taken 86086205 times.
 96824083 while (stamps_[slot] == generation_) {
146 10737878 slot = (slot + 1) & (kSlots - 1);
147 }
148 86086205 keys_[slot] = key;
149 86086205 codes_[slot] = static_cast<std::uint16_t>(code);
150 86086205 stamps_[slot] = generation_;
151 86086205 }
152
153 private:
154 static constexpr std::size_t kSlots = 16384;
155
156 503987437 static std::size_t Hash(std::uint32_t key) {
157 503987437 return static_cast<std::size_t>((key * 2654435761u) >> 18) & (kSlots - 1);
158 }
159
160 std::vector<std::uint32_t> keys_;
161 std::vector<std::uint16_t> codes_;
162 std::vector<std::uint32_t> stamps_;
163 std::uint32_t generation_ = 1;
164 };
165
166 /// Writes LZW codes, widening them one code early as the table grows.
167 class LzwCodeWriter {
168 public:
169 1636 LzwCodeWriter() {
170
1/1
✓ Branch 1 taken 1636 times.
 1636 writer_.Put(kClear, width_);
171 1636 }
172
173 /// The code the next string gets.
174 172172410 int Next() const {
175 172172410 return next_;
176 }
177
178 /// Writes `code`; the encoder adds a string for every code it writes.
179 86087840 void PutCode(int code) {
180 86087840 writer_.Put(code, width_);
181 86087840 ++next_;
182 86087840 width_ = LzwNextWidth(next_, width_);
183 86087840 }
184
185 /// Writes Clear and starts again from 9-bit codes.
186 21707 void Clear() {
187 21707 writer_.Put(kClear, width_);
188 21707 width_ = 9;
189 21707 next_ = kFirstCode;
190 21707 }
191
192 1636 std::vector<std::uint8_t> Finish() {
193 1636 writer_.Put(kEndOfInfo, width_);
194 1636 return writer_.Finish();
195 }
196
197 private:
198 BitWriter writer_;
199 int width_ = 9;
200 int next_ = kFirstCode;
201 };
202
203 } // namespace
204
205 86655166 int LzwNextWidth(int codes, int width) {
206
4/4
✓ Branch 0 taken 69231 times.
✓ Branch 1 taken 86585935 times.
✓ Branch 2 taken 69230 times.
✓ Branch 3 taken 1 time.
 86655166 return codes >= (1 << width) && width < 12 ? width + 1 : width;
207 }
208
209 127 std::vector<std::uint8_t> DecodeLzw(std::span<const std::uint8_t> data, std::size_t size) {
210
6/8
✓ Branch 1 taken 127 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 time.
✓ Branch 5 taken 126 times.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 9 taken 1 time.
✓ Branch 10 taken 126 times.
 127 if (data.size() >= 2 && data[0] == 0 && (data[1] & 1u) != 0) {
211
1/1
✓ Branch 2 taken 1 time.
 1 throw GeoTiffError("Old-style LZW compression is not supported");
212 }
213 126 LzwDecodeTable table;
214 126 std::vector<std::uint8_t> out;
215
1/1
✓ Branch 1 taken 126 times.
 126 out.reserve(size);
216 126 BitReader reader(data);
217 126 int width = 9;
218 126 int previous = -1;
219
2/2
✓ Branch 1 taken 567784 times.
✓ Branch 2 taken 123 times.
 567907 while (out.size() < size) {
220 567784 const int code = reader.Next(width);
221
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 567783 times.
 567784 if (code == kEndOfInfo) {
222 1 break;
223 }
224
2/2
✓ Branch 0 taken 230 times.
✓ Branch 1 taken 567553 times.
 567783 if (code == kClear) {
225 230 width = 9;
226 230 table.Reset();
227 230 previous = -1;
228 459 continue;
229 }
230
2/2
✓ Branch 0 taken 231 times.
✓ Branch 1 taken 567322 times.
 567553 if (previous < 0) {
231
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 229 times.
 231 if (code > 255) {
232 2 Corrupt("first code after Clear is not a byte");
233 }
234
1/1
✓ Branch 1 taken 229 times.
 229 table.Emit(code, out);
235 229 previous = code;
236 229 continue;
237 }
238
3/6
✓ Branch 1 taken 567322 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 567322 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 567322 times.
 567322 if (code > table.Next() || table.Next() >= kMaxCode) {
239 ✗ Corrupt("code out of range");
240 }
241 567322 std::uint8_t first = 0;
242
2/2
✓ Branch 1 taken 537599 times.
✓ Branch 2 taken 29723 times.
 567322 if (code < table.Next()) {
243
1/1
✓ Branch 1 taken 537599 times.
 537599 first = table.Emit(code, out);
244 } else {
245
1/1
✓ Branch 1 taken 29723 times.
 29723 first = table.Emit(previous, out);
246
1/1
✓ Branch 1 taken 29723 times.
 29723 out.push_back(first);
247 }
248 567322 table.Add(previous, first);
249 567322 width = LzwNextWidth(table.Next() + 1, width);
250 567322 previous = code;
251 }
252
2/2
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 123 times.
 124 if (out.size() < size) {
253
4/4
✓ Branch 2 taken 1 time.
✓ Branch 5 taken 1 time.
✓ Branch 8 taken 1 time.
✓ Branch 11 taken 1 time.
 2 throw GeoTiffError("Corrupt LZW data: decoded " + std::to_string(out.size()) + " of " +
254
3/3
✓ Branch 2 taken 1 time.
✓ Branch 5 taken 1 time.
✓ Branch 8 taken 1 time.
 3 std::to_string(size) + " bytes");
255 }
256
1/1
✓ Branch 1 taken 123 times.
 123 out.resize(size);
257 246 return out;
258 3 }
259
260 1636 std::vector<std::uint8_t> EncodeLzw(std::span<const std::uint8_t> data) {
261
1/1
✓ Branch 1 taken 1636 times.
 1636 LzwCodeWriter writer;
262
1/1
✓ Branch 1 taken 1636 times.
 1636 LzwTable table;
263 1636 int current = -1;
264
2/2
✓ Branch 5 taken 417902867 times.
✓ Branch 6 taken 1636 times.
 417904503 for (const std::uint8_t byte : data) {
265
2/2
✓ Branch 0 taken 1635 times.
✓ Branch 1 taken 417901232 times.
 417902867 if (current < 0) {
266 1635 current = byte;
267 1635 continue;
268 }
269 417901232 const std::uint32_t key = (static_cast<std::uint32_t>(current) << 8) | byte;
270
3/3
✓ Branch 1 taken 417901232 times.
✓ Branch 3 taken 331815027 times.
✓ Branch 4 taken 86086205 times.
 417901232 if (const int found = table.Find(key); found >= 0) {
271 331815027 current = found;
272 331815027 continue;
273 }
274
1/1
✓ Branch 2 taken 86086205 times.
 86086205 table.Insert(key, writer.Next());
275
1/1
✓ Branch 1 taken 86086205 times.
 86086205 writer.PutCode(current);
276
2/2
✓ Branch 1 taken 21707 times.
✓ Branch 2 taken 86064498 times.
 86086205 if (writer.Next() >= kMaxCode - 2) {
277
1/1
✓ Branch 1 taken 21707 times.
 21707 writer.Clear();
278 21707 table.Clear();
279 }
280 86086205 current = byte;
281 }
282
2/2
✓ Branch 0 taken 1635 times.
✓ Branch 1 taken 1 time.
 1636 if (current >= 0) {
283
1/1
✓ Branch 1 taken 1635 times.
 1635 writer.PutCode(current);
284 }
285
1/1
✓ Branch 1 taken 1636 times.
 3272 return writer.Finish();
286 1636 }
287
288 45 std::vector<std::uint8_t> DecodeDeflate(std::span<const std::uint8_t> data, std::size_t size) {
289
1/1
✓ Branch 1 taken 45 times.
 45 std::vector<std::uint8_t> out(size);
290
1/1
✓ Branch 3 taken 45 times.
 135 const std::size_t written = tinfl_decompress_mem_to_mem(
291 90 out.data(), out.size(), data.data(), data.size(), TINFL_FLAG_PARSE_ZLIB_HEADER);
292
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 43 times.
 45 if (written == TINFL_DECOMPRESS_MEM_TO_MEM_FAILED) {
293
1/1
✓ Branch 2 taken 2 times.
 2 throw GeoTiffError("Corrupt Deflate data");
294 }
295
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 42 times.
 43 if (written != size) {
296
4/4
✓ Branch 1 taken 1 time.
✓ Branch 4 taken 1 time.
✓ Branch 7 taken 1 time.
✓ Branch 10 taken 1 time.
 2 throw GeoTiffError("Corrupt Deflate data: decoded " + std::to_string(written) + " of " +
297
3/3
✓ Branch 2 taken 1 time.
✓ Branch 5 taken 1 time.
✓ Branch 8 taken 1 time.
 3 std::to_string(size) + " bytes");
298 }
299 42 return out;
300 3 }
301
302 33 std::vector<std::uint8_t> EncodeDeflate(std::span<const std::uint8_t> data) {
303 33 constexpr int kLevel = 6;
304 33 constexpr int kWindowBits = 15;
305 const mz_uint flags =
306
1/1
✓ Branch 1 taken 33 times.
 33 tdefl_create_comp_flags_from_zip_params(kLevel, kWindowBits, MZ_DEFAULT_STRATEGY);
307 33 std::size_t length = 0;
308 void* compressed =
309
1/1
✓ Branch 3 taken 33 times.
 33 tdefl_compress_mem_to_heap(data.data(), data.size(), &length, static_cast<int>(flags));
310
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 33 times.
 33 if (compressed == nullptr) {
311
0/1
✗ Branch 2 not taken.
 ✗ throw GeoTiffError("Deflate compression failed");
312 }
313 33 const auto* bytes = static_cast<const std::uint8_t*>(compressed);
314
1/1
✓ Branch 1 taken 33 times.
 33 std::vector<std::uint8_t> out(bytes, bytes + length);
315
1/1
✓ Branch 1 taken 33 times.
 33 mz_free(compressed);
316 66 return out;
317 }
318
319 5 std::vector<std::uint8_t> DecodePackBits(std::span<const std::uint8_t> data, std::size_t size) {
320 5 std::vector<std::uint8_t> out;
321
1/1
✓ Branch 1 taken 5 times.
 5 out.reserve(size);
322 5 std::size_t i = 0;
323
6/6
✓ Branch 1 taken 25 times.
✓ Branch 2 taken 2 times.
✓ Branch 4 taken 24 times.
✓ Branch 5 taken 1 time.
✓ Branch 6 taken 24 times.
✓ Branch 7 taken 3 times.
 27 while (out.size() < size && i < data.size()) {
324 24 const auto header = static_cast<std::int8_t>(data[i++]);
325
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 2 times.
 24 if (header >= 0) {
326 22 const std::size_t count = static_cast<std::size_t>(header) + 1;
327
2/2
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 21 times.
 22 if (i + count > data.size()) {
328
1/1
✓ Branch 2 taken 1 time.
 1 throw GeoTiffError("Corrupt PackBits data: literal run past the end");
329 }
330
1/1
✓ Branch 6 taken 21 times.
 21 out.insert(out.end(), data.begin() + static_cast<std::ptrdiff_t>(i),
331 21 data.begin() + static_cast<std::ptrdiff_t>(i + count));
332 21 i += count;
333
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
 2 } else if (header != -128) {
334
2/2
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 1 time.
 2 if (i >= data.size()) {
335
1/1
✓ Branch 2 taken 1 time.
 1 throw GeoTiffError("Corrupt PackBits data: repeat run past the end");
336 }
337
1/1
✓ Branch 4 taken 1 time.
 1 out.insert(out.end(), static_cast<std::size_t>(1 - header), data[i++]);
338 }
339 }
340
2/2
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 2 times.
 3 if (out.size() < size) {
341
4/4
✓ Branch 2 taken 1 time.
✓ Branch 5 taken 1 time.
✓ Branch 8 taken 1 time.
✓ Branch 11 taken 1 time.
 2 throw GeoTiffError("Corrupt PackBits data: decoded " + std::to_string(out.size()) + " of " +
342
3/3
✓ Branch 2 taken 1 time.
✓ Branch 5 taken 1 time.
✓ Branch 8 taken 1 time.
 3 std::to_string(size) + " bytes");
343 }
344
1/1
✓ Branch 1 taken 2 times.
 2 out.resize(size);
345 2 return out;
346 3 }
347
348 408882 void EncodeFloatPredictorRow(std::uint8_t* row, std::size_t sampleBytes, std::size_t rowSamples,
349 std::size_t stride) {
350 408882 const std::size_t rowBytes = rowSamples * sampleBytes;
351
1/1
✓ Branch 1 taken 408882 times.
 408882 std::vector<std::uint8_t> native(row, row + rowBytes);
352
2/2
✓ Branch 0 taken 104416012 times.
✓ Branch 1 taken 408882 times.
 104824894 for (std::size_t sample = 0; sample < rowSamples; ++sample) {
353
2/2
✓ Branch 0 taken 417664048 times.
✓ Branch 1 taken 104416012 times.
 522080060 for (std::size_t byte = 0; byte < sampleBytes; ++byte) {
354 417664048 row[(sampleBytes - byte - 1) * rowSamples + sample] =
355 417664048 native[sample * sampleBytes + byte];
356 }
357 }
358
2/2
✓ Branch 0 taken 417255165 times.
✓ Branch 1 taken 408882 times.
 417664047 for (std::size_t i = rowBytes - 1; i >= stride; --i) {
359 417255165 row[i] = static_cast<std::uint8_t>(row[i] - row[i - stride]);
360 }
361 408882 }
362
363 13704 void DecodeFloatPredictorRow(std::uint8_t* row, std::size_t sampleBytes, std::size_t rowSamples,
364 std::size_t stride) {
365 13704 const std::size_t rowBytes = rowSamples * sampleBytes;
366
2/2
✓ Branch 0 taken 12664607 times.
✓ Branch 1 taken 13704 times.
 12678311 for (std::size_t i = stride; i < rowBytes; ++i) {
367 12664607 row[i] = static_cast<std::uint8_t>(row[i] + row[i - stride]);
368 }
369
1/1
✓ Branch 1 taken 13704 times.
 13704 const std::vector<std::uint8_t> planes(row, row + rowBytes);
370
2/2
✓ Branch 0 taken 3168554 times.
✓ Branch 1 taken 13704 times.
 3182258 for (std::size_t sample = 0; sample < rowSamples; ++sample) {
371
2/2
✓ Branch 0 taken 12678312 times.
✓ Branch 1 taken 3168554 times.
 15846866 for (std::size_t byte = 0; byte < sampleBytes; ++byte) {
372 12678312 row[sample * sampleBytes + byte] =
373 12678312 planes[(sampleBytes - byte - 1) * rowSamples + sample];
374 }
375 }
376 13704 }
377
378 } // namespace terraingen::detail
379