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 1151 : find_tile_idx_lesser_or_equal(const std::vector<pmtiles::entryv3> &entries,
24 : uint64_t tile_id)
25 : {
26 1151 : if (!entries.empty() && tile_id <= entries[0].tile_id)
27 162 : return 0;
28 :
29 989 : int m = 0;
30 989 : int n = static_cast<int>(entries.size()) - 1;
31 3799 : while (m <= n)
32 : {
33 2891 : int k = (n + m) >> 1;
34 2891 : if (tile_id > entries[k].tile_id)
35 : {
36 1874 : m = k + 1;
37 : }
38 1017 : else if (tile_id < entries[k].tile_id)
39 : {
40 936 : n = k - 1;
41 : }
42 : else
43 : {
44 81 : return k;
45 : }
46 : }
47 :
48 908 : return n;
49 : }
50 :
51 : /************************************************************************/
52 : /* LoadRootDirectory() */
53 : /************************************************************************/
54 :
55 260 : bool OGRPMTilesTileIterator::LoadRootDirectory()
56 : {
57 260 : if (m_nZoomLevel >= 0)
58 : {
59 260 : 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 260 : if (m_nMinX >= 0 && m_nMinY >= 0 && m_nMaxX >= m_nMinX &&
65 242 : m_nMaxY >= m_nMinY &&
66 242 : (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 308 : m_nMinTileId = pmtiles::zxy_to_tileid(
82 154 : static_cast<uint8_t>(m_nZoomLevel), 0, 0);
83 308 : m_nMaxTileId = pmtiles::zxy_to_tileid(
84 154 : 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 258 : const unsigned nThreshold = static_cast<unsigned>(atoi(
94 258 : CPLGetConfigOption("OGR_PMTILES_ITERATOR_THRESHOLD", "10000")));
95 258 : if (m_nMinX >= 0 && m_nMinY >= 0 && m_nMaxX >= m_nMinX &&
96 240 : m_nMaxY >= m_nMinY &&
97 240 : !(m_nMinX == 0 && m_nMinY == 0 &&
98 151 : m_nMaxX == (1 << m_nZoomLevel) - 1 &&
99 138 : 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 258 : const auto &sHeader = m_poDS->GetHeader();
111 516 : const auto *posStr = m_poDS->ReadInternal(
112 258 : sHeader.root_dir_offset, static_cast<uint32_t>(sHeader.root_dir_bytes),
113 : "header");
114 258 : if (!posStr)
115 : {
116 0 : return false;
117 : }
118 :
119 516 : DirectoryContext sContext;
120 258 : sContext.sEntries = pmtiles::deserialize_directory(*posStr);
121 :
122 258 : if (m_nZoomLevel >= 0)
123 : {
124 258 : 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 254 : find_tile_idx_lesser_or_equal(sContext.sEntries, m_nMinTileId);
157 254 : if (nMinEntryIdx < 0)
158 : {
159 0 : return false;
160 : }
161 254 : sContext.nIdxInEntries = nMinEntryIdx;
162 : }
163 : }
164 :
165 258 : m_aoStack.emplace(std::move(sContext));
166 258 : 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 884 : pmtiles::entry_zxy OGRPMTilesTileIterator::GetNextTile(uint32_t *pnRunLength)
197 : {
198 884 : if (m_bEOF)
199 15 : return pmtiles::entry_zxy(0, 0, 0, 0, 0);
200 :
201 869 : 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 869 : if (m_aoStack.empty())
207 : {
208 260 : if (!LoadRootDirectory())
209 : {
210 0 : m_bEOF = true;
211 731 : return pmtiles::entry_zxy(0, 0, 0, 0, 0);
212 : }
213 : }
214 :
215 6998 : const auto AdvanceToNextTile = [this]()
216 : {
217 1531 : 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 849 : return false;
255 867 : };
256 :
257 : while (true)
258 : {
259 8594 : if (m_aoStack.top().nIdxInEntries ==
260 4297 : m_aoStack.top().sEntries.size())
261 : {
262 385 : if (m_aoStack.size() == 1 && AdvanceToNextTile())
263 129 : continue;
264 :
265 256 : m_aoStack.pop();
266 256 : if (m_aoStack.empty())
267 105 : break;
268 151 : continue;
269 : }
270 3912 : auto &topContext = m_aoStack.top();
271 : const auto &sCurrentEntry =
272 3912 : topContext.sEntries[topContext.nIdxInEntries];
273 3912 : if (sCurrentEntry.run_length == 0)
274 : {
275 : // Arbitrary limit. 5 seems to be the maximum value supported
276 : // by pmtiles.hpp::get_tile()
277 215 : 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 430 : if (sHeader.leaf_dirs_offset >
286 215 : 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 430 : const auto *posStr = m_poDS->ReadInternal(
294 215 : sHeader.leaf_dirs_offset + sCurrentEntry.offset,
295 215 : sCurrentEntry.length, "directory");
296 215 : 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 215 : DirectoryContext sContext;
311 215 : sContext.sEntries = pmtiles::deserialize_directory(*posStr);
312 215 : 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 317 : if (m_nLastTileId != INVALID_LAST_TILE_ID &&
324 102 : 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 215 : if (m_nZoomLevel >= 0)
333 : {
334 215 : const int nMinEntryIdx = find_tile_idx_lesser_or_equal(
335 : sContext.sEntries, m_nMinTileId);
336 215 : if (nMinEntryIdx < 0)
337 : {
338 0 : if (AdvanceToNextTile())
339 0 : continue;
340 0 : break;
341 : }
342 215 : sContext.nIdxInEntries = nMinEntryIdx;
343 : }
344 215 : m_nLastTileId =
345 215 : sContext.sEntries[sContext.nIdxInEntries].tile_id;
346 :
347 215 : m_aoStack.emplace(std::move(sContext));
348 :
349 215 : topContext.nIdxInEntries++;
350 : }
351 : else
352 : {
353 3697 : if (topContext.nIdxInRunLength == sCurrentEntry.run_length)
354 : {
355 1080 : topContext.nIdxInEntries++;
356 1080 : topContext.nIdxInRunLength = 0;
357 : }
358 : else
359 : {
360 2617 : const auto nIdxInRunLength = topContext.nIdxInRunLength;
361 2617 : const uint64_t nTileId =
362 2617 : sCurrentEntry.tile_id + nIdxInRunLength;
363 2617 : m_nLastTileId = nTileId;
364 2617 : 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 2646 : 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 2617 : topContext.nIdxInRunLength++;
379 :
380 2617 : if (m_nZoomLevel >= 0)
381 : {
382 2617 : if (nTileId < m_nMinTileId)
383 : {
384 825 : 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 1855 : continue;
404 : }
405 1792 : else if (nTileId > m_nMaxTileId)
406 : {
407 566 : if (AdvanceToNextTile())
408 535 : continue;
409 31 : break;
410 : }
411 :
412 1226 : if (m_nMinX >= 0 &&
413 1203 : zxy.x < static_cast<uint32_t>(m_nMinX))
414 173 : continue;
415 1053 : if (m_nMinY >= 0 &&
416 1029 : zxy.y < static_cast<uint32_t>(m_nMinY))
417 42 : continue;
418 1011 : if (m_nMaxX >= 0 &&
419 988 : zxy.x > static_cast<uint32_t>(m_nMaxX))
420 154 : continue;
421 857 : if (m_nMaxY >= 0 &&
422 833 : zxy.y > static_cast<uint32_t>(m_nMaxY))
423 126 : continue;
424 : }
425 :
426 1462 : if (sHeader.tile_data_offset >
427 731 : std::numeric_limits<uint64_t>::max() -
428 731 : 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 731 : 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 731 : zxy.z, zxy.x, zxy.y,
447 731 : sHeader.tile_data_offset + sCurrentEntry.offset,
448 731 : sCurrentEntry.length);
449 :
450 731 : AdvanceToNextTile();
451 :
452 731 : return res;
453 : }
454 : }
455 3430 : }
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 138 : m_bEOF = true;
464 138 : 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
|
