Line data Source code
1 : /******************************************************************************
2 : *
3 : * Project: OpenGIS Simple Features Reference Implementation
4 : * Purpose: Implementation of PMTiles
5 : * Author: Even Rouault <even.rouault at spatialys.com>
6 : *
7 : ******************************************************************************
8 : * Copyright (c) 2023, Planet Labs
9 : *
10 : * Permission is hereby granted, free of charge, to any person obtaining a
11 : * copy of this software and associated documentation files (the "Software"),
12 : * to deal in the Software without restriction, including without limitation
13 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
14 : * and/or sell copies of the Software, and to permit persons to whom the
15 : * Software is furnished to do so, subject to the following conditions:
16 : *
17 : * The above copyright notice and this permission notice shall be included
18 : * in all copies or substantial portions of the Software.
19 : *
20 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
21 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
23 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
24 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
25 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
26 : * DEALINGS IN THE SOFTWARE.
27 : ****************************************************************************/
28 :
29 : #include "ogr_pmtiles.h"
30 :
31 : #include <algorithm>
32 : #include <limits>
33 :
34 : /************************************************************************/
35 : /* find_tile_idx_lesser_or_equal() */
36 : /************************************************************************/
37 :
38 : static int
39 1134 : find_tile_idx_lesser_or_equal(const std::vector<pmtiles::entryv3> &entries,
40 : uint64_t tile_id)
41 : {
42 1134 : if (!entries.empty() && tile_id <= entries[0].tile_id)
43 157 : return 0;
44 :
45 977 : int m = 0;
46 977 : int n = static_cast<int>(entries.size()) - 1;
47 3759 : while (m <= n)
48 : {
49 2863 : int k = (n + m) >> 1;
50 2863 : if (tile_id > entries[k].tile_id)
51 : {
52 1856 : m = k + 1;
53 : }
54 1007 : else if (tile_id < entries[k].tile_id)
55 : {
56 926 : n = k - 1;
57 : }
58 : else
59 : {
60 81 : return k;
61 : }
62 : }
63 :
64 896 : return n;
65 : }
66 :
67 : /************************************************************************/
68 : /* LoadRootDirectory() */
69 : /************************************************************************/
70 :
71 252 : bool OGRPMTilesTileIterator::LoadRootDirectory()
72 : {
73 252 : if (m_nZoomLevel >= 0)
74 : {
75 252 : CPLDebugOnly("PMTiles", "minx=%d miny=%d maxx=%d maxy=%d", m_nMinX,
76 : m_nMinY, m_nMaxX, m_nMaxY);
77 : // If we don't query too many tiles, establish the minimum
78 : // and maximum tile id, we are interested in.
79 : // (is there a clever way of figuring out this?)
80 252 : if (m_nMinX >= 0 && m_nMinY >= 0 && m_nMaxX >= m_nMinX &&
81 234 : m_nMaxY >= m_nMinY &&
82 234 : (m_nMaxX - m_nMinX + 1) <= 100 / (m_nMaxY - m_nMinY + 1))
83 : {
84 268 : for (int iY = m_nMinY; iY <= m_nMaxY; ++iY)
85 : {
86 735 : for (int iX = m_nMinX; iX <= m_nMaxX; ++iX)
87 : {
88 1144 : const uint64_t nTileId = pmtiles::zxy_to_tileid(
89 573 : static_cast<uint8_t>(m_nZoomLevel), iX, iY);
90 571 : m_nMinTileId = std::min(m_nMinTileId, nTileId);
91 571 : m_nMaxTileId = std::max(m_nMaxTileId, nTileId);
92 : }
93 104 : }
94 : }
95 : else
96 : {
97 292 : m_nMinTileId = pmtiles::zxy_to_tileid(
98 146 : static_cast<uint8_t>(m_nZoomLevel), 0, 0);
99 292 : m_nMaxTileId = pmtiles::zxy_to_tileid(
100 146 : static_cast<uint8_t>(m_nZoomLevel) + 1, 0, 0) -
101 : 1;
102 : }
103 :
104 : // If filtering by bbox and that the gap between min and max
105 : // tile id is too big, use an iteration over (x, y) space rather
106 : // than tile id space.
107 :
108 : // Config option for debugging purposes
109 250 : const unsigned nThreshold = static_cast<unsigned>(atoi(
110 250 : CPLGetConfigOption("OGR_PMTILES_ITERATOR_THRESHOLD", "10000")));
111 250 : if (m_nMinX >= 0 && m_nMinY >= 0 && m_nMaxX >= m_nMinX &&
112 232 : m_nMaxY >= m_nMinY &&
113 232 : !(m_nMinX == 0 && m_nMinY == 0 &&
114 143 : m_nMaxX == (1 << m_nZoomLevel) - 1 &&
115 130 : m_nMaxY == (1 << m_nZoomLevel) - 1) &&
116 104 : m_nMaxTileId - m_nMinTileId > nThreshold)
117 : {
118 4 : m_nCurX = m_nMinX;
119 4 : m_nCurY = m_nMinY;
120 8 : m_nMinTileId = pmtiles::zxy_to_tileid(
121 4 : static_cast<uint8_t>(m_nZoomLevel), m_nCurX, m_nCurY);
122 4 : m_nMaxTileId = m_nMinTileId;
123 : }
124 : }
125 :
126 250 : const auto &sHeader = m_poDS->GetHeader();
127 500 : const auto *posStr = m_poDS->ReadInternal(
128 250 : sHeader.root_dir_offset, static_cast<uint32_t>(sHeader.root_dir_bytes),
129 : "header");
130 250 : if (!posStr)
131 : {
132 0 : return false;
133 : }
134 :
135 500 : DirectoryContext sContext;
136 250 : sContext.sEntries = pmtiles::deserialize_directory(*posStr);
137 :
138 250 : if (m_nZoomLevel >= 0)
139 : {
140 250 : if (m_nCurX >= 0)
141 : {
142 : while (true)
143 : {
144 4 : const int nMinEntryIdx = find_tile_idx_lesser_or_equal(
145 : sContext.sEntries, m_nMinTileId);
146 4 : if (nMinEntryIdx < 0)
147 : {
148 0 : m_nCurX++;
149 0 : if (m_nCurX > m_nMaxX)
150 : {
151 0 : m_nCurX = m_nMinX;
152 0 : m_nCurY++;
153 0 : if (m_nCurY > m_nMaxY)
154 : {
155 0 : return false;
156 : }
157 : }
158 0 : m_nMinTileId = pmtiles::zxy_to_tileid(
159 0 : static_cast<uint8_t>(m_nZoomLevel), m_nCurX, m_nCurY);
160 0 : m_nMaxTileId = m_nMinTileId;
161 : }
162 : else
163 : {
164 4 : sContext.nIdxInEntries = nMinEntryIdx;
165 4 : break;
166 : }
167 0 : }
168 : }
169 : else
170 : {
171 : const int nMinEntryIdx =
172 246 : find_tile_idx_lesser_or_equal(sContext.sEntries, m_nMinTileId);
173 246 : if (nMinEntryIdx < 0)
174 : {
175 0 : return false;
176 : }
177 246 : sContext.nIdxInEntries = nMinEntryIdx;
178 : }
179 : }
180 :
181 250 : m_aoStack.emplace(std::move(sContext));
182 250 : return true;
183 : }
184 :
185 : /************************************************************************/
186 : /* SkipRunLength() */
187 : /************************************************************************/
188 :
189 2 : void OGRPMTilesTileIterator::SkipRunLength()
190 : {
191 2 : if (!m_aoStack.empty())
192 : {
193 2 : auto &topContext = m_aoStack.top();
194 2 : if (topContext.nIdxInEntries < topContext.sEntries.size())
195 : {
196 : const auto &sCurrentEntry =
197 2 : topContext.sEntries[topContext.nIdxInEntries];
198 2 : if (sCurrentEntry.run_length > 1)
199 : {
200 2 : m_nLastTileId =
201 2 : sCurrentEntry.tile_id + sCurrentEntry.run_length - 1;
202 2 : topContext.nIdxInRunLength = sCurrentEntry.run_length;
203 : }
204 : }
205 : }
206 2 : }
207 :
208 : /************************************************************************/
209 : /* GetNextTile() */
210 : /************************************************************************/
211 :
212 858 : pmtiles::entry_zxy OGRPMTilesTileIterator::GetNextTile(uint32_t *pnRunLength)
213 : {
214 858 : if (m_bEOF)
215 7 : return pmtiles::entry_zxy(0, 0, 0, 0, 0);
216 :
217 851 : const auto &sHeader = m_poDS->GetHeader();
218 : try
219 : {
220 : // Put the root directory as the first element of the stack
221 : // of directories, if the stack is empty
222 851 : if (m_aoStack.empty())
223 : {
224 252 : if (!LoadRootDirectory())
225 : {
226 0 : m_bEOF = true;
227 717 : return pmtiles::entry_zxy(0, 0, 0, 0, 0);
228 : }
229 : }
230 :
231 6980 : const auto AdvanceToNextTile = [this]()
232 : {
233 1513 : if (m_nCurX >= 0)
234 : {
235 : while (true)
236 : {
237 682 : m_nCurX++;
238 682 : if (m_nCurX > m_nMaxX)
239 : {
240 35 : m_nCurX = m_nMinX;
241 35 : m_nCurY++;
242 35 : if (m_nCurY > m_nMaxY)
243 : {
244 4 : m_bEOF = true;
245 4 : return false;
246 : }
247 : }
248 678 : if (!m_bEOF)
249 : {
250 1356 : m_nMinTileId = pmtiles::zxy_to_tileid(
251 678 : static_cast<uint8_t>(m_nZoomLevel), m_nCurX,
252 678 : m_nCurY);
253 678 : m_nMaxTileId = m_nMinTileId;
254 678 : m_nLastTileId = INVALID_LAST_TILE_ID;
255 678 : while (m_aoStack.size() > 1)
256 0 : m_aoStack.pop();
257 1356 : const int nMinEntryIdx = find_tile_idx_lesser_or_equal(
258 678 : m_aoStack.top().sEntries, m_nMinTileId);
259 678 : if (nMinEntryIdx < 0)
260 : {
261 0 : continue;
262 : }
263 678 : m_aoStack.top().nIdxInEntries = nMinEntryIdx;
264 678 : m_aoStack.top().nIdxInRunLength = 0;
265 678 : break;
266 : }
267 0 : }
268 678 : return true;
269 : }
270 831 : return false;
271 849 : };
272 :
273 : while (true)
274 : {
275 8474 : if (m_aoStack.top().nIdxInEntries ==
276 4237 : m_aoStack.top().sEntries.size())
277 : {
278 374 : if (m_aoStack.size() == 1 && AdvanceToNextTile())
279 129 : continue;
280 :
281 245 : m_aoStack.pop();
282 245 : if (m_aoStack.empty())
283 101 : break;
284 144 : continue;
285 : }
286 3863 : auto &topContext = m_aoStack.top();
287 : const auto &sCurrentEntry =
288 3863 : topContext.sEntries[topContext.nIdxInEntries];
289 3863 : if (sCurrentEntry.run_length == 0)
290 : {
291 : // Arbitrary limit. 5 seems to be the maximum value supported
292 : // by pmtiles.hpp::get_tile()
293 206 : if (m_aoStack.size() == 5)
294 : {
295 0 : m_bEOF = true;
296 0 : CPLError(CE_Failure, CPLE_AppDefined,
297 : "Too many levels of nested directories");
298 0 : break;
299 : }
300 :
301 412 : if (sHeader.leaf_dirs_offset >
302 206 : std::numeric_limits<uint64_t>::max() - sCurrentEntry.offset)
303 : {
304 0 : m_bEOF = true;
305 0 : CPLError(CE_Failure, CPLE_AppDefined,
306 : "Invalid directory offset");
307 0 : break;
308 : }
309 412 : const auto *posStr = m_poDS->ReadInternal(
310 206 : sHeader.leaf_dirs_offset + sCurrentEntry.offset,
311 206 : sCurrentEntry.length, "directory");
312 206 : if (!posStr)
313 : {
314 0 : m_bEOF = true;
315 0 : CPLError(
316 : CE_Failure, CPLE_AppDefined,
317 : "PMTILES: cannot read directory of size " CPL_FRMT_GUIB
318 : " at "
319 : "offset " CPL_FRMT_GUIB,
320 0 : static_cast<GUIntBig>(sHeader.leaf_dirs_offset +
321 0 : sCurrentEntry.offset),
322 0 : static_cast<GUIntBig>(sCurrentEntry.length));
323 0 : break;
324 : }
325 :
326 206 : DirectoryContext sContext;
327 206 : sContext.sEntries = pmtiles::deserialize_directory(*posStr);
328 206 : if (sContext.sEntries.empty())
329 : {
330 0 : m_bEOF = true;
331 : // In theory empty directories could exist, but for now
332 : // do not allow this to be more robust against hostile files
333 : // that could create many such empty directories
334 0 : CPLError(CE_Failure, CPLE_AppDefined,
335 : "Empty directory found");
336 0 : break;
337 : }
338 :
339 303 : if (m_nLastTileId != INVALID_LAST_TILE_ID &&
340 97 : sContext.sEntries[0].tile_id <= m_nLastTileId)
341 : {
342 0 : m_bEOF = true;
343 0 : CPLError(CE_Failure, CPLE_AppDefined,
344 : "Non increasing tile_id");
345 0 : break;
346 : }
347 :
348 206 : if (m_nZoomLevel >= 0)
349 : {
350 206 : const int nMinEntryIdx = find_tile_idx_lesser_or_equal(
351 : sContext.sEntries, m_nMinTileId);
352 206 : if (nMinEntryIdx < 0)
353 : {
354 0 : if (AdvanceToNextTile())
355 0 : continue;
356 0 : break;
357 : }
358 206 : sContext.nIdxInEntries = nMinEntryIdx;
359 : }
360 206 : m_nLastTileId =
361 206 : sContext.sEntries[sContext.nIdxInEntries].tile_id;
362 :
363 206 : m_aoStack.emplace(std::move(sContext));
364 :
365 206 : topContext.nIdxInEntries++;
366 : }
367 : else
368 : {
369 3657 : if (topContext.nIdxInRunLength == sCurrentEntry.run_length)
370 : {
371 1062 : topContext.nIdxInEntries++;
372 1062 : topContext.nIdxInRunLength = 0;
373 : }
374 : else
375 : {
376 2595 : const auto nIdxInRunLength = topContext.nIdxInRunLength;
377 2595 : const uint64_t nTileId =
378 2595 : sCurrentEntry.tile_id + nIdxInRunLength;
379 2595 : m_nLastTileId = nTileId;
380 2595 : const pmtiles::zxy zxy = pmtiles::tileid_to_zxy(nTileId);
381 :
382 : // Sanity check to limit risk of iterating forever on
383 : // broken run_length value
384 2624 : if (nIdxInRunLength == 0 && sCurrentEntry.run_length > 1 &&
385 29 : sCurrentEntry.run_length >
386 29 : pmtiles::zxy_to_tileid(zxy.z + 1, 0, 0) - nTileId)
387 : {
388 0 : m_bEOF = true;
389 0 : CPLError(CE_Failure, CPLE_AppDefined,
390 : "Invalid run_length");
391 31 : break;
392 : }
393 :
394 2595 : topContext.nIdxInRunLength++;
395 :
396 2595 : if (m_nZoomLevel >= 0)
397 : {
398 2595 : if (nTileId < m_nMinTileId)
399 : {
400 817 : if (sCurrentEntry.run_length > 1)
401 : {
402 19 : if (sCurrentEntry.tile_id +
403 19 : sCurrentEntry.run_length <=
404 19 : m_nMinTileId)
405 : {
406 0 : topContext.nIdxInRunLength =
407 0 : sCurrentEntry.run_length;
408 : }
409 : else
410 : {
411 19 : topContext.nIdxInRunLength =
412 : static_cast<uint32_t>(
413 19 : m_nMinTileId -
414 19 : sCurrentEntry.tile_id);
415 : }
416 19 : m_nLastTileId = sCurrentEntry.tile_id +
417 19 : topContext.nIdxInRunLength - 1;
418 : }
419 1847 : continue;
420 : }
421 1778 : else if (nTileId > m_nMaxTileId)
422 : {
423 566 : if (AdvanceToNextTile())
424 535 : continue;
425 31 : break;
426 : }
427 :
428 1212 : if (m_nMinX >= 0 &&
429 1189 : zxy.x < static_cast<uint32_t>(m_nMinX))
430 173 : continue;
431 1039 : if (m_nMinY >= 0 &&
432 1015 : zxy.y < static_cast<uint32_t>(m_nMinY))
433 42 : continue;
434 997 : if (m_nMaxX >= 0 &&
435 974 : zxy.x > static_cast<uint32_t>(m_nMaxX))
436 154 : continue;
437 843 : if (m_nMaxY >= 0 &&
438 819 : zxy.y > static_cast<uint32_t>(m_nMaxY))
439 126 : continue;
440 : }
441 :
442 1434 : if (sHeader.tile_data_offset >
443 717 : std::numeric_limits<uint64_t>::max() -
444 717 : sCurrentEntry.offset)
445 : {
446 0 : m_bEOF = true;
447 0 : CPLError(CE_Failure, CPLE_AppDefined,
448 : "Invalid tile offset");
449 0 : break;
450 : }
451 :
452 717 : if (pnRunLength)
453 : {
454 18 : *pnRunLength =
455 18 : sCurrentEntry.run_length - nIdxInRunLength;
456 : }
457 :
458 : // We must capture the result, before the below code
459 : // that updates (m_nCurX, m_nCurY) and invalidates
460 : // sCurrentEntry
461 : const auto res = pmtiles::entry_zxy(
462 717 : zxy.z, zxy.x, zxy.y,
463 717 : sHeader.tile_data_offset + sCurrentEntry.offset,
464 717 : sCurrentEntry.length);
465 :
466 717 : AdvanceToNextTile();
467 :
468 717 : return res;
469 : }
470 : }
471 3388 : }
472 : }
473 4 : catch (const std::exception &e)
474 : {
475 2 : CPLError(CE_Failure, CPLE_AppDefined, "GetNextTile() failed with %s",
476 2 : e.what());
477 : }
478 :
479 134 : m_bEOF = true;
480 134 : return pmtiles::entry_zxy(0, 0, 0, 0, 0);
481 : }
482 :
483 : /************************************************************************/
484 : /* DumpTiles() */
485 : /************************************************************************/
486 :
487 : #ifdef DEBUG_PMTILES
488 : void OGRPMTilesTileIterator::DumpTiles()
489 : {
490 : int count = 0;
491 : while (true)
492 : {
493 : const auto sTile = GetNextTile();
494 : if (sTile.offset == 0)
495 : break;
496 : ++count;
497 : printf("%d -> %d %d %d %d %d\n", // ok
498 : count, int(sTile.z), int(sTile.x), int(sTile.y),
499 : int(sTile.offset), int(sTile.length));
500 : }
501 : }
502 : #endif
|
