/src/gdal/ogr/ogrsf_frmts/pmtiles/ogrpmtilestileiterator.cpp

Source
/******************************************************************************
 *
 * Project:  OpenGIS Simple Features Reference Implementation
 * Purpose:  Implementation of PMTiles
 * Author:   Even Rouault <even.rouault at spatialys.com>
 *
 ******************************************************************************
 * Copyright (c) 2023, Planet Labs
 *
 * SPDX-License-Identifier: MIT
 ****************************************************************************/

#include "ogr_pmtiles.h"

#include <algorithm>
#include <limits>

/************************************************************************/
/*                 find_tile_idx_lesser_or_equal()                      */
/************************************************************************/

static int
find_tile_idx_lesser_or_equal(const std::vector<pmtiles::entryv3> &entries,
                              uint64_t tile_id)
{
    if (!entries.empty() && tile_id <= entries[0].tile_id)
        return 0;

    int m = 0;
    int n = static_cast<int>(entries.size()) - 1;
    while (m <= n)
    {
        int k = (n + m) >> 1;
        if (tile_id > entries[k].tile_id)
        {
            m = k + 1;
        }
        else if (tile_id < entries[k].tile_id)
        {
            n = k - 1;
        }
        else
        {
            return k;
        }
    }

    return n;
}

/************************************************************************/
/*                      LoadRootDirectory()                             */
/************************************************************************/

bool OGRPMTilesTileIterator::LoadRootDirectory()
{
    if (m_nZoomLevel >= 0)
    {
        CPLDebugOnly("PMTiles", "minx=%d miny=%d maxx=%d maxy=%d", m_nMinX,
                     m_nMinY, m_nMaxX, m_nMaxY);
        // If we don't query too many tiles, establish the minimum
        // and maximum tile id, we are interested in.
        // (is there a clever way of figuring out this?)
        if (m_nMinX >= 0 && m_nMinY >= 0 && m_nMaxX >= m_nMinX &&
            m_nMaxY >= m_nMinY &&
            (m_nMaxX - m_nMinX + 1) <= 100 / (m_nMaxY - m_nMinY + 1))
        {
            for (int iY = m_nMinY; iY <= m_nMaxY; ++iY)
            {
                for (int iX = m_nMinX; iX <= m_nMaxX; ++iX)
                {
                    const uint64_t nTileId = pmtiles::zxy_to_tileid(
                        static_cast<uint8_t>(m_nZoomLevel), iX, iY);
                    m_nMinTileId = std::min(m_nMinTileId, nTileId);
                    m_nMaxTileId = std::max(m_nMaxTileId, nTileId);
                }
            }
        }
        else
        {
            m_nMinTileId = pmtiles::zxy_to_tileid(
                static_cast<uint8_t>(m_nZoomLevel), 0, 0);
            m_nMaxTileId = pmtiles::zxy_to_tileid(
                               static_cast<uint8_t>(m_nZoomLevel) + 1, 0, 0) -
                           1;
        }

        // If filtering by bbox and that the gap between min and max
        // tile id is too big, use an iteration over (x, y) space rather
        // than tile id space.

        // Config option for debugging purposes
        const unsigned nThreshold = static_cast<unsigned>(atoi(
            CPLGetConfigOption("OGR_PMTILES_ITERATOR_THRESHOLD", "10000")));
        if (m_nMinX >= 0 && m_nMinY >= 0 && m_nMaxX >= m_nMinX &&
            m_nMaxY >= m_nMinY &&
            !(m_nMinX == 0 && m_nMinY == 0 &&
              m_nMaxX == (1 << m_nZoomLevel) - 1 &&
              m_nMaxY == (1 << m_nZoomLevel) - 1) &&
            m_nMaxTileId - m_nMinTileId > nThreshold)
        {
            m_nCurX = m_nMinX;
            m_nCurY = m_nMinY;
            m_nMinTileId = pmtiles::zxy_to_tileid(
                static_cast<uint8_t>(m_nZoomLevel), m_nCurX, m_nCurY);
            m_nMaxTileId = m_nMinTileId;
        }
    }

    const auto &sHeader = m_poDS->GetHeader();
    const auto *posStr = m_poDS->ReadInternal(
        sHeader.root_dir_offset, static_cast<uint32_t>(sHeader.root_dir_bytes),
        "header");
    if (!posStr)
    {
        return false;
    }

    DirectoryContext sContext;
    sContext.sEntries = pmtiles::deserialize_directory(*posStr);

    if (m_nZoomLevel >= 0)
    {
        if (m_nCurX >= 0)
        {
            while (true)
            {
                const int nMinEntryIdx = find_tile_idx_lesser_or_equal(
                    sContext.sEntries, m_nMinTileId);
                if (nMinEntryIdx < 0)
                {
                    m_nCurX++;
                    if (m_nCurX > m_nMaxX)
                    {
                        m_nCurX = m_nMinX;
                        m_nCurY++;
                        if (m_nCurY > m_nMaxY)
                        {
                            return false;
                        }
                    }
                    m_nMinTileId = pmtiles::zxy_to_tileid(
                        static_cast<uint8_t>(m_nZoomLevel), m_nCurX, m_nCurY);
                    m_nMaxTileId = m_nMinTileId;
                }
                else
                {
                    sContext.nIdxInEntries = nMinEntryIdx;
                    break;
                }
            }
        }
        else
        {
            const int nMinEntryIdx =
                find_tile_idx_lesser_or_equal(sContext.sEntries, m_nMinTileId);
            if (nMinEntryIdx < 0)
            {
                return false;
            }
            sContext.nIdxInEntries = nMinEntryIdx;
        }
    }

    m_aoStack.emplace(std::move(sContext));
    return true;
}

/************************************************************************/
/*                        SkipRunLength()                               */
/************************************************************************/

void OGRPMTilesTileIterator::SkipRunLength()
{
    if (!m_aoStack.empty())
    {
        auto &topContext = m_aoStack.top();
        if (topContext.nIdxInEntries < topContext.sEntries.size())
        {
            const auto &sCurrentEntry =
                topContext.sEntries[topContext.nIdxInEntries];
            if (sCurrentEntry.run_length > 1)
            {
                m_nLastTileId =
                    sCurrentEntry.tile_id + sCurrentEntry.run_length - 1;
                topContext.nIdxInRunLength = sCurrentEntry.run_length;
            }
        }
    }
}

/************************************************************************/
/*                          GetNextTile()                               */
/************************************************************************/

pmtiles::entry_zxy OGRPMTilesTileIterator::GetNextTile(uint32_t *pnRunLength)
{
    if (m_bEOF)
        return pmtiles::entry_zxy(0, 0, 0, 0, 0);

    const auto &sHeader = m_poDS->GetHeader();
    try
    {
        // Put the root directory as the first element of the stack
        // of directories, if the stack is empty
        if (m_aoStack.empty())
        {
            if (!LoadRootDirectory())
            {
                m_bEOF = true;
                return pmtiles::entry_zxy(0, 0, 0, 0, 0);
            }
        }

        const auto AdvanceToNextTile = [this]()
        {
            if (m_nCurX >= 0)
            {
                while (true)
                {
                    m_nCurX++;
                    if (m_nCurX > m_nMaxX)
                    {
                        m_nCurX = m_nMinX;
                        m_nCurY++;
                        if (m_nCurY > m_nMaxY)
                        {
                            m_bEOF = true;
                            return false;
                        }
                    }
                    if (!m_bEOF)
                    {
                        m_nMinTileId = pmtiles::zxy_to_tileid(
                            static_cast<uint8_t>(m_nZoomLevel), m_nCurX,
                            m_nCurY);
                        m_nMaxTileId = m_nMinTileId;
                        m_nLastTileId = INVALID_LAST_TILE_ID;
                        while (m_aoStack.size() > 1)
                            m_aoStack.pop();
                        const int nMinEntryIdx = find_tile_idx_lesser_or_equal(
                            m_aoStack.top().sEntries, m_nMinTileId);
                        if (nMinEntryIdx < 0)
                        {
                            continue;
                        }
                        m_aoStack.top().nIdxInEntries = nMinEntryIdx;
                        m_aoStack.top().nIdxInRunLength = 0;
                        break;
                    }
                }
                return true;
            }
            return false;
        };

        while (true)
        {
            if (m_aoStack.top().nIdxInEntries ==
                m_aoStack.top().sEntries.size())
            {
                if (m_aoStack.size() == 1 && AdvanceToNextTile())
                    continue;

                m_aoStack.pop();
                if (m_aoStack.empty())
                    break;
                continue;
            }
            auto &topContext = m_aoStack.top();
            const auto &sCurrentEntry =
                topContext.sEntries[topContext.nIdxInEntries];
            if (sCurrentEntry.run_length == 0)
            {
                // Arbitrary limit. 5 seems to be the maximum value supported
                // by pmtiles.hpp::get_tile()
                if (m_aoStack.size() == 5)
                {
                    m_bEOF = true;
                    CPLError(CE_Failure, CPLE_AppDefined,
                             "Too many levels of nested directories");
                    break;
                }

                if (sHeader.leaf_dirs_offset >
                    std::numeric_limits<uint64_t>::max() - sCurrentEntry.offset)
                {
                    m_bEOF = true;
                    CPLError(CE_Failure, CPLE_AppDefined,
                             "Invalid directory offset");
                    break;
                }
                const auto *posStr = m_poDS->ReadInternal(
                    sHeader.leaf_dirs_offset + sCurrentEntry.offset,
                    sCurrentEntry.length, "directory");
                if (!posStr)
                {
                    m_bEOF = true;
                    CPLError(
                        CE_Failure, CPLE_AppDefined,
                        "PMTILES: cannot read directory of size " CPL_FRMT_GUIB
                        " at "
                        "offset " CPL_FRMT_GUIB,
                        static_cast<GUIntBig>(sHeader.leaf_dirs_offset +
                                              sCurrentEntry.offset),
                        static_cast<GUIntBig>(sCurrentEntry.length));
                    break;
                }

                DirectoryContext sContext;
                sContext.sEntries = pmtiles::deserialize_directory(*posStr);
                if (sContext.sEntries.empty())
                {
                    m_bEOF = true;
                    // In theory empty directories could exist, but for now
                    // do not allow this to be more robust against hostile files
                    // that could create many such empty directories
                    CPLError(CE_Failure, CPLE_AppDefined,
                             "Empty directory found");
                    break;
                }

                if (m_nLastTileId != INVALID_LAST_TILE_ID &&
                    sContext.sEntries[0].tile_id <= m_nLastTileId)
                {
                    m_bEOF = true;
                    CPLError(CE_Failure, CPLE_AppDefined,
                             "Non increasing tile_id");
                    break;
                }

                if (m_nZoomLevel >= 0)
                {
                    const int nMinEntryIdx = find_tile_idx_lesser_or_equal(
                        sContext.sEntries, m_nMinTileId);
                    if (nMinEntryIdx < 0)
                    {
                        if (AdvanceToNextTile())
                            continue;
                        break;
                    }
                    sContext.nIdxInEntries = nMinEntryIdx;
                }
                m_nLastTileId =
                    sContext.sEntries[sContext.nIdxInEntries].tile_id;

                m_aoStack.emplace(std::move(sContext));

                topContext.nIdxInEntries++;
            }
            else
            {
                if (topContext.nIdxInRunLength == sCurrentEntry.run_length)
                {
                    topContext.nIdxInEntries++;
                    topContext.nIdxInRunLength = 0;
                }
                else
                {
                    const auto nIdxInRunLength = topContext.nIdxInRunLength;
                    const uint64_t nTileId =
                        sCurrentEntry.tile_id + nIdxInRunLength;
                    m_nLastTileId = nTileId;
                    const pmtiles::zxy zxy = pmtiles::tileid_to_zxy(nTileId);

                    // Sanity check to limit risk of iterating forever on
                    // broken run_length value
                    if (nIdxInRunLength == 0 && sCurrentEntry.run_length > 1 &&
                        sCurrentEntry.run_length >
                            pmtiles::zxy_to_tileid(zxy.z + 1, 0, 0) - nTileId)
                    {
                        m_bEOF = true;
                        CPLError(CE_Failure, CPLE_AppDefined,
                                 "Invalid run_length");
                        break;
                    }

                    topContext.nIdxInRunLength++;

                    if (m_nZoomLevel >= 0)
                    {
                        if (nTileId < m_nMinTileId)
                        {
                            if (sCurrentEntry.run_length > 1)
                            {
                                if (sCurrentEntry.tile_id +
                                        sCurrentEntry.run_length <=
                                    m_nMinTileId)
                                {
                                    topContext.nIdxInRunLength =
                                        sCurrentEntry.run_length;
                                }
                                else
                                {
                                    topContext.nIdxInRunLength =
                                        static_cast<uint32_t>(
                                            m_nMinTileId -
                                            sCurrentEntry.tile_id);
                                }
                                m_nLastTileId = sCurrentEntry.tile_id +
                                                topContext.nIdxInRunLength - 1;
                            }
                            continue;
                        }
                        else if (nTileId > m_nMaxTileId)
                        {
                            if (AdvanceToNextTile())
                                continue;
                            break;
                        }

                        if (m_nMinX >= 0 &&
                            zxy.x < static_cast<uint32_t>(m_nMinX))
                            continue;
                        if (m_nMinY >= 0 &&
                            zxy.y < static_cast<uint32_t>(m_nMinY))
                            continue;
                        if (m_nMaxX >= 0 &&
                            zxy.x > static_cast<uint32_t>(m_nMaxX))
                            continue;
                        if (m_nMaxY >= 0 &&
                            zxy.y > static_cast<uint32_t>(m_nMaxY))
                            continue;
                    }

                    if (sHeader.tile_data_offset >
                        std::numeric_limits<uint64_t>::max() -
                            sCurrentEntry.offset)
                    {
                        m_bEOF = true;
                        CPLError(CE_Failure, CPLE_AppDefined,
                                 "Invalid tile offset");
                        break;
                    }

                    if (pnRunLength)
                    {
                        *pnRunLength =
                            sCurrentEntry.run_length - nIdxInRunLength;
                    }

                    // We must capture the result, before the below code
                    // that updates (m_nCurX, m_nCurY) and invalidates
                    // sCurrentEntry
                    const auto res = pmtiles::entry_zxy(
                        zxy.z, zxy.x, zxy.y,
                        sHeader.tile_data_offset + sCurrentEntry.offset,
                        sCurrentEntry.length);

                    AdvanceToNextTile();

                    return res;
                }
            }
        }
    }
    catch (const std::exception &e)
    {
        CPLError(CE_Failure, CPLE_AppDefined, "GetNextTile() failed with %s",
                 e.what());
    }

    m_bEOF = true;
    return pmtiles::entry_zxy(0, 0, 0, 0, 0);
}

/************************************************************************/
/*                           DumpTiles()                                */
/************************************************************************/

#ifdef DEBUG_PMTILES
void OGRPMTilesTileIterator::DumpTiles()
{
    int count = 0;
    while (true)
    {
        const auto sTile = GetNextTile();
        if (sTile.offset == 0)
            break;
        ++count;
        printf("%d -> %d %d %d %d %d\n",  // ok
               count, int(sTile.z), int(sTile.x), int(sTile.y),
               int(sTile.offset), int(sTile.length));
    }
}
#endif

Coverage Report

Created: 2025-11-15 08:43

Line	Count	Source
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		find_tile_idx_lesser_or_equal(const std::vector<pmtiles::entryv3> &entries,
24		uint64_t tile_id)
25	72	{
26	72	if (!entries.empty() && tile_id <= entries[0].tile_id)
27	29	return 0;
28
29	43	int m = 0;
30	43	int n = static_cast<int>(entries.size()) - 1;
31	172	while (m <= n)
32	129	{
33	129	int k = (n + m) >> 1;
34	129	if (tile_id > entries[k].tile_id)
35	69	{
36	69	m = k + 1;
37	69	}
38	60	else if (tile_id < entries[k].tile_id)
39	60	{
40	60	n = k - 1;
41	60	}
42	0	else
43	0	{
44	0	return k;
45	0	}
46	129	}
47
48	43	return n;
49	43	}
50
51		/************************************************************************/
52		/* LoadRootDirectory() */
53		/************************************************************************/
54
55		bool OGRPMTilesTileIterator::LoadRootDirectory()
56	25	{
57	25	if (m_nZoomLevel >= 0)
58	25	{
59	25	CPLDebugOnly("PMTiles", "minx=%d miny=%d maxx=%d maxy=%d", m_nMinX,
60	25	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	25	if (m_nMinX >= 0 && m_nMinY >= 0 && m_nMaxX >= m_nMinX &&
65	21	m_nMaxY >= m_nMinY &&
66	21	(m_nMaxX - m_nMinX + 1) <= 100 / (m_nMaxY - m_nMinY + 1))
67	0	{
68	0	for (int iY = m_nMinY; iY <= m_nMaxY; ++iY)
69	0	{
70	0	for (int iX = m_nMinX; iX <= m_nMaxX; ++iX)
71	0	{
72	0	const uint64_t nTileId = pmtiles::zxy_to_tileid(
73	0	static_cast<uint8_t>(m_nZoomLevel), iX, iY);
74	0	m_nMinTileId = std::min(m_nMinTileId, nTileId);
75	0	m_nMaxTileId = std::max(m_nMaxTileId, nTileId);
76	0	}
77	0	}
78	0	}
79	25	else
80	25	{
81	25	m_nMinTileId = pmtiles::zxy_to_tileid(
82	25	static_cast<uint8_t>(m_nZoomLevel), 0, 0);
83	25	m_nMaxTileId = pmtiles::zxy_to_tileid(
84	25	static_cast<uint8_t>(m_nZoomLevel) + 1, 0, 0) -
85	25	1;
86	25	}
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	25	const unsigned nThreshold = static_cast<unsigned>(atoi(
94	25	CPLGetConfigOption("OGR_PMTILES_ITERATOR_THRESHOLD", "10000")));
95	25	if (m_nMinX >= 0 && m_nMinY >= 0 && m_nMaxX >= m_nMinX &&
96	21	m_nMaxY >= m_nMinY &&
97	21	!(m_nMinX == 0 && m_nMinY == 0 &&
98	21	m_nMaxX == (1 << m_nZoomLevel) - 1 &&
99	21	m_nMaxY == (1 << m_nZoomLevel) - 1) &&
100	0	m_nMaxTileId - m_nMinTileId > nThreshold)
101	0	{
102	0	m_nCurX = m_nMinX;
103	0	m_nCurY = m_nMinY;
104	0	m_nMinTileId = pmtiles::zxy_to_tileid(
105	0	static_cast<uint8_t>(m_nZoomLevel), m_nCurX, m_nCurY);
106	0	m_nMaxTileId = m_nMinTileId;
107	0	}
108	25	}
109
110	25	const auto &sHeader = m_poDS->GetHeader();
111	25	const auto *posStr = m_poDS->ReadInternal(
112	25	sHeader.root_dir_offset, static_cast<uint32_t>(sHeader.root_dir_bytes),
113	25	"header");
114	25	if (!posStr)
115	0	{
116	0	return false;
117	0	}
118
119	25	DirectoryContext sContext;
120	25	sContext.sEntries = pmtiles::deserialize_directory(*posStr);
121
122	25	if (m_nZoomLevel >= 0)
123	25	{
124	25	if (m_nCurX >= 0)
125	0	{
126	0	while (true)
127	0	{
128	0	const int nMinEntryIdx = find_tile_idx_lesser_or_equal(
129	0	sContext.sEntries, m_nMinTileId);
130	0	if (nMinEntryIdx < 0)
131	0	{
132	0	m_nCurX++;
133	0	if (m_nCurX > m_nMaxX)
134	0	{
135	0	m_nCurX = m_nMinX;
136	0	m_nCurY++;
137	0	if (m_nCurY > m_nMaxY)
138	0	{
139	0	return false;
140	0	}
141	0	}
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	0	}
146	0	else
147	0	{
148	0	sContext.nIdxInEntries = nMinEntryIdx;
149	0	break;
150	0	}
151	0	}
152	0	}
153	25	else
154	25	{
155	25	const int nMinEntryIdx =
156	25	find_tile_idx_lesser_or_equal(sContext.sEntries, m_nMinTileId);
157	25	if (nMinEntryIdx < 0)
158	0	{
159	0	return false;
160	0	}
161	25	sContext.nIdxInEntries = nMinEntryIdx;
162	25	}
163	25	}
164
165	25	m_aoStack.emplace(std::move(sContext));
166	25	return true;
167	25	}
168
169		/************************************************************************/
170		/* SkipRunLength() */
171		/************************************************************************/
172
173		void OGRPMTilesTileIterator::SkipRunLength()
174	0	{
175	0	if (!m_aoStack.empty())
176	0	{
177	0	auto &topContext = m_aoStack.top();
178	0	if (topContext.nIdxInEntries < topContext.sEntries.size())
179	0	{
180	0	const auto &sCurrentEntry =
181	0	topContext.sEntries[topContext.nIdxInEntries];
182	0	if (sCurrentEntry.run_length > 1)
183	0	{
184	0	m_nLastTileId =
185	0	sCurrentEntry.tile_id + sCurrentEntry.run_length - 1;
186	0	topContext.nIdxInRunLength = sCurrentEntry.run_length;
187	0	}
188	0	}
189	0	}
190	0	}
191
192		/************************************************************************/
193		/* GetNextTile() */
194		/************************************************************************/
195
196		pmtiles::entry_zxy OGRPMTilesTileIterator::GetNextTile(uint32_t *pnRunLength)
197	15.0k	{
198	15.0k	if (m_bEOF)
199	0	return pmtiles::entry_zxy(0, 0, 0, 0, 0);
200
201	15.0k	const auto &sHeader = m_poDS->GetHeader();
202	15.0k	try
203	15.0k	{
204		// Put the root directory as the first element of the stack
205		// of directories, if the stack is empty
206	15.0k	if (m_aoStack.empty())
207	25	{
208	25	if (!LoadRootDirectory())
209	0	{
210	0	m_bEOF = true;
211	0	return pmtiles::entry_zxy(0, 0, 0, 0, 0);
212	0	}
213	25	}
214
215	15.0k	const auto AdvanceToNextTile = [this]()
216	15.0k	{
217	15.0k	if (m_nCurX >= 0)
218	0	{
219	0	while (true)
220	0	{
221	0	m_nCurX++;
222	0	if (m_nCurX > m_nMaxX)
223	0	{
224	0	m_nCurX = m_nMinX;
225	0	m_nCurY++;
226	0	if (m_nCurY > m_nMaxY)
227	0	{
228	0	m_bEOF = true;
229	0	return false;
230	0	}
231	0	}
232	0	if (!m_bEOF)
233	0	{
234	0	m_nMinTileId = pmtiles::zxy_to_tileid(
235	0	static_cast<uint8_t>(m_nZoomLevel), m_nCurX,
236	0	m_nCurY);
237	0	m_nMaxTileId = m_nMinTileId;
238	0	m_nLastTileId = INVALID_LAST_TILE_ID;
239	0	while (m_aoStack.size() > 1)
240	0	m_aoStack.pop();
241	0	const int nMinEntryIdx = find_tile_idx_lesser_or_equal(
242	0	m_aoStack.top().sEntries, m_nMinTileId);
243	0	if (nMinEntryIdx < 0)
244	0	{
245	0	continue;
246	0	}
247	0	m_aoStack.top().nIdxInEntries = nMinEntryIdx;
248	0	m_aoStack.top().nIdxInRunLength = 0;
249	0	break;
250	0	}
251	0	}
252	0	return true;
253	0	}
254	15.0k	return false;
255	15.0k	};
256
257	26.8k	while (true)
258	26.8k	{
259	26.8k	if (m_aoStack.top().nIdxInEntries ==
260	26.8k	m_aoStack.top().sEntries.size())
261	45	{
262	45	if (m_aoStack.size() == 1 && AdvanceToNextTile())
263	0	continue;
264
265	45	m_aoStack.pop();
266	45	if (m_aoStack.empty())
267	8	break;
268	37	continue;
269	45	}
270	26.8k	auto &topContext = m_aoStack.top();
271	26.8k	const auto &sCurrentEntry =
272	26.8k	topContext.sEntries[topContext.nIdxInEntries];
273	26.8k	if (sCurrentEntry.run_length == 0)
274	52	{
275		// Arbitrary limit. 5 seems to be the maximum value supported
276		// by pmtiles.hpp::get_tile()
277	52	if (m_aoStack.size() == 5)
278	0	{
279	0	m_bEOF = true;
280	0	CPLError(CE_Failure, CPLE_AppDefined,
281	0	"Too many levels of nested directories");
282	0	break;
283	0	}
284
285	52	if (sHeader.leaf_dirs_offset >
286	52	std::numeric_limits<uint64_t>::max() - sCurrentEntry.offset)
287	0	{
288	0	m_bEOF = true;
289	0	CPLError(CE_Failure, CPLE_AppDefined,
290	0	"Invalid directory offset");
291	0	break;
292	0	}
293	52	const auto *posStr = m_poDS->ReadInternal(
294	52	sHeader.leaf_dirs_offset + sCurrentEntry.offset,
295	52	sCurrentEntry.length, "directory");
296	52	if (!posStr)
297	5	{
298	5	m_bEOF = true;
299	5	CPLError(
300	5	CE_Failure, CPLE_AppDefined,
301	5	"PMTILES: cannot read directory of size " CPL_FRMT_GUIB
302	5	" at "
303	5	"offset " CPL_FRMT_GUIB,
304	5	static_cast<GUIntBig>(sHeader.leaf_dirs_offset +
305	5	sCurrentEntry.offset),
306	5	static_cast<GUIntBig>(sCurrentEntry.length));
307	5	break;
308	5	}
309
310	47	DirectoryContext sContext;
311	47	sContext.sEntries = pmtiles::deserialize_directory(*posStr);
312	47	if (sContext.sEntries.empty())
313	0	{
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	0	"Empty directory found");
320	0	break;
321	0	}
322
323	47	if (m_nLastTileId != INVALID_LAST_TILE_ID &&
324	29	sContext.sEntries[0].tile_id <= m_nLastTileId)
325	0	{
326	0	m_bEOF = true;
327	0	CPLError(CE_Failure, CPLE_AppDefined,
328	0	"Non increasing tile_id");
329	0	break;
330	0	}
331
332	47	if (m_nZoomLevel >= 0)
333	47	{
334	47	const int nMinEntryIdx = find_tile_idx_lesser_or_equal(
335	47	sContext.sEntries, m_nMinTileId);
336	47	if (nMinEntryIdx < 0)
337	0	{
338	0	if (AdvanceToNextTile())
339	0	continue;
340	0	break;
341	0	}
342	47	sContext.nIdxInEntries = nMinEntryIdx;
343	47	}
344	47	m_nLastTileId =
345	47	sContext.sEntries[sContext.nIdxInEntries].tile_id;
346
347	47	m_aoStack.emplace(std::move(sContext));
348
349	47	topContext.nIdxInEntries++;
350	47	}
351	26.7k	else
352	26.7k	{
353	26.7k	if (topContext.nIdxInRunLength == sCurrentEntry.run_length)
354	11.6k	{
355	11.6k	topContext.nIdxInEntries++;
356	11.6k	topContext.nIdxInRunLength = 0;
357	11.6k	}
358	15.1k	else
359	15.1k	{
360	15.1k	const auto nIdxInRunLength = topContext.nIdxInRunLength;
361	15.1k	const uint64_t nTileId =
362	15.1k	sCurrentEntry.tile_id + nIdxInRunLength;
363	15.1k	m_nLastTileId = nTileId;
364	15.1k	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	15.1k	if (nIdxInRunLength == 0 && sCurrentEntry.run_length > 1 &&
369	1.36k	sCurrentEntry.run_length >
370	1.36k	pmtiles::zxy_to_tileid(zxy.z + 1, 0, 0) - nTileId)
371	0	{
372	0	m_bEOF = true;
373	0	CPLError(CE_Failure, CPLE_AppDefined,
374	0	"Invalid run_length");
375	0	break;
376	0	}
377
378	15.1k	topContext.nIdxInRunLength++;
379
380	15.1k	if (m_nZoomLevel >= 0)
381	15.1k	{
382	15.1k	if (nTileId < m_nMinTileId)
383	21	{
384	21	if (sCurrentEntry.run_length > 1)
385	0	{
386	0	if (sCurrentEntry.tile_id +
387	0	sCurrentEntry.run_length <=
388	0	m_nMinTileId)
389	0	{
390	0	topContext.nIdxInRunLength =
391	0	sCurrentEntry.run_length;
392	0	}
393	0	else
394	0	{
395	0	topContext.nIdxInRunLength =
396	0	static_cast<uint32_t>(
397	0	m_nMinTileId -
398	0	sCurrentEntry.tile_id);
399	0	}
400	0	m_nLastTileId = sCurrentEntry.tile_id +
401	0	topContext.nIdxInRunLength - 1;
402	0	}
403	21	continue;
404	21	}
405	15.0k	else if (nTileId > m_nMaxTileId)
406	0	{
407	0	if (AdvanceToNextTile())
408	0	continue;
409	0	break;
410	0	}
411
412	15.0k	if (m_nMinX >= 0 &&
413	62	zxy.x < static_cast<uint32_t>(m_nMinX))
414	0	continue;
415	15.0k	if (m_nMinY >= 0 &&
416	62	zxy.y < static_cast<uint32_t>(m_nMinY))
417	0	continue;
418	15.0k	if (m_nMaxX >= 0 &&
419	62	zxy.x > static_cast<uint32_t>(m_nMaxX))
420	0	continue;
421	15.0k	if (m_nMaxY >= 0 &&
422	62	zxy.y > static_cast<uint32_t>(m_nMaxY))
423	0	continue;
424	15.0k	}
425
426	15.0k	if (sHeader.tile_data_offset >
427	15.0k	std::numeric_limits<uint64_t>::max() -
428	15.0k	sCurrentEntry.offset)
429	0	{
430	0	m_bEOF = true;
431	0	CPLError(CE_Failure, CPLE_AppDefined,
432	0	"Invalid tile offset");
433	0	break;
434	0	}
435
436	15.0k	if (pnRunLength)
437	15.0k	{
438	15.0k	*pnRunLength =
439	15.0k	sCurrentEntry.run_length - nIdxInRunLength;
440	15.0k	}
441
442		// We must capture the result, before the below code
443		// that updates (m_nCurX, m_nCurY) and invalidates
444		// sCurrentEntry
445	15.0k	const auto res = pmtiles::entry_zxy(
446	15.0k	zxy.z, zxy.x, zxy.y,
447	15.0k	sHeader.tile_data_offset + sCurrentEntry.offset,
448	15.0k	sCurrentEntry.length);
449
450	15.0k	AdvanceToNextTile();
451
452	15.0k	return res;
453	15.0k	}
454	26.7k	}
455	26.8k	}
456	15.0k	}
457	15.0k	catch (const std::exception &e)
458	15.0k	{
459	0	CPLError(CE_Failure, CPLE_AppDefined, "GetNextTile() failed with %s",
460	0	e.what());
461	0	}
462
463	13	m_bEOF = true;
464	13	return pmtiles::entry_zxy(0, 0, 0, 0, 0);
465	15.0k	}
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