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