This is an automated email from the ASF dual-hosted git repository. bchapuis pushed a commit to branch pmtiles in repository https://gitbox.apache.org/repos/asf/incubator-baremaps.git
commit 697daeffde3c66a81b00943c4443d7d015e73e8e Author: Bertil Chapuis <[email protected]> AuthorDate: Thu Sep 7 00:11:57 2023 +0200 Port additional methods and tests --- .../apache/baremaps/tilestore/pmtiles/PMTiles.java | 158 ++++++++++++++++++++- .../baremaps/tilestore/pmtiles/PMTilesTest.java | 99 +++++++++++-- 2 files changed, 241 insertions(+), 16 deletions(-) diff --git a/baremaps-core/src/main/java/org/apache/baremaps/tilestore/pmtiles/PMTiles.java b/baremaps-core/src/main/java/org/apache/baremaps/tilestore/pmtiles/PMTiles.java index 3ec6d62e..1ff45353 100644 --- a/baremaps-core/src/main/java/org/apache/baremaps/tilestore/pmtiles/PMTiles.java +++ b/baremaps-core/src/main/java/org/apache/baremaps/tilestore/pmtiles/PMTiles.java @@ -15,6 +15,8 @@ package org.apache.baremaps.tilestore.pmtiles; import com.google.common.math.LongMath; import java.nio.ByteBuffer; import java.nio.ByteOrder; +import java.util.ArrayList; +import java.util.List; public class PMTiles { @@ -22,7 +24,7 @@ public class PMTiles { return high * 0x100000000L + low; } - public static long readVarintRemainder(long l, ByteBuffer buf) { + public static long readVarIntRemainder(long l, ByteBuffer buf) { long h, b; b = buf.get() & 0xff; h = (b & 0x70) >> 4; @@ -57,7 +59,18 @@ public class PMTiles { throw new RuntimeException("Expected varint not more than 10 bytes"); } - public static long readVarint(ByteBuffer buf) { + public static int encodeVarInt(ByteBuffer buf, long value) { + int n = 1; + while (value >= 0x80) { + buf.put((byte) (value | 0x80)); + value >>>= 7; + n++; + } + buf.put((byte) value); + return n; + } + + public static long decodeVarInt(ByteBuffer buf) { long val, b; b = buf.get() & 0xff; val = b & 0x7f; @@ -80,7 +93,7 @@ public class PMTiles { return val; } val |= (b & 0x0f) << 28; - return readVarintRemainder(val, buf); + return readVarIntRemainder(val, buf); } public static void rotate(long n, long[] xy, long rx, long ry) { @@ -172,6 +185,8 @@ public class PMTiles { Avif, } + private static final int HEADER_SIZE_BYTES = 127; + public record Header( int specVersion, long rootDirectoryOffset, @@ -201,7 +216,7 @@ public class PMTiles { String etag) { } - public static Header bytesToHeader(ByteBuffer buf, String etag) { + public static Header decodeHeader(ByteBuffer buf, String etag) { buf.order(ByteOrder.LITTLE_ENDIAN); return new Header( buf.get(7), @@ -232,7 +247,7 @@ public class PMTiles { etag); } - public static void headerToBytes(Header header, ByteBuffer buf) { + public static void encodeHeader(Header header, ByteBuffer buf) { buf.order(ByteOrder.LITTLE_ENDIAN); buf.put(0, (byte) 0x50); buf.put(1, (byte) 0x4D); @@ -268,4 +283,137 @@ public class PMTiles { buf.putInt(123, (int) (header.centerLat * 10000000)); } + public static class Entry { + private long tileId; + private long offset; + private long length; + private long runLength; + + public Entry() { + + } + + public Entry(long tileId, long offset, long length, long runLength) { + this.tileId = tileId; + this.offset = offset; + this.length = length; + this.runLength = runLength; + } + + public long getTileId() { + return tileId; + } + + public void setTileId(long tileId) { + this.tileId = tileId; + } + + public long getOffset() { + return offset; + } + + public void setOffset(long offset) { + this.offset = offset; + } + + public long getLength() { + return length; + } + + public void setLength(long length) { + this.length = length; + } + + public long getRunLength() { + return runLength; + } + + public void setRunLength(long runLength) { + this.runLength = runLength; + } + } + + public static void encodeDirectory(ByteBuffer buffer, List<Entry> entries) { + buffer.order(ByteOrder.LITTLE_ENDIAN); + encodeVarInt(buffer, entries.size()); + long lastId = 0; + for (Entry entry : entries) { + encodeVarInt(buffer, entry.getTileId() - lastId); + lastId = entry.getTileId(); + } + for (Entry entry : entries) { + encodeVarInt(buffer, entry.getRunLength()); + } + for (Entry entry : entries) { + encodeVarInt(buffer, entry.getLength()); + } + for (Entry entry : entries) { + if (entry.getOffset() == 0 && entry.getLength() > 0) { + Entry prevEntry = entries.get(entries.indexOf(entry) - 1); + encodeVarInt(buffer, prevEntry.offset + prevEntry.length + 1); + } else { + encodeVarInt(buffer, entry.getOffset() + 1); + } + } + } + + public static List<Entry> decodeDirectory(ByteBuffer buffer) { + buffer.order(ByteOrder.LITTLE_ENDIAN); + long numEntries = decodeVarInt(buffer); + List<Entry> entries = new ArrayList<>((int) numEntries); + long lastId = 0; + for (int i = 0; i < numEntries; i++) { + long value = decodeVarInt(buffer); + lastId = lastId + value; + Entry entry = new Entry(); + entry.setTileId(lastId); + entries.add(entry); + } + for (int i = 0; i < numEntries; i++) { + long value = decodeVarInt(buffer); + entries.get(i).setRunLength(value); + } + for (int i = 0; i < numEntries; i++) { + long value = decodeVarInt(buffer); + entries.get(i).setLength(value); + } + for (int i = 0; i < numEntries; i++) { + long value = decodeVarInt(buffer); + if (value == 0 && i > 0) { + Entry prevEntry = entries.get(i - 1); + entries.get(i).setOffset(prevEntry.offset + prevEntry.length);; + } else { + entries.get(i).setOffset(value - 1); + } + } + return entries; + } + + public static Entry findTile(List<Entry> entries, long tileId) { + int m = 0; + int n = entries.size() - 1; + while (m <= n) { + int k = (n + m) >> 1; + long cmp = tileId - entries.get(k).getTileId(); + if (cmp > 0) { + m = k + 1; + } else if (cmp < 0) { + n = k - 1; + } else { + return entries.get(k); + } + } + + // at this point, m > n + if (n >= 0) { + if (entries.get(n).runLength == 0) { + return entries.get(n); + } + if (tileId - entries.get(n).tileId < entries.get(n).runLength) { + return entries.get(n); + } + } + return null; + } + } diff --git a/baremaps-core/src/test/java/org/apache/baremaps/tilestore/pmtiles/PMTilesTest.java b/baremaps-core/src/test/java/org/apache/baremaps/tilestore/pmtiles/PMTilesTest.java index 1fdf7129..b5bea852 100644 --- a/baremaps-core/src/test/java/org/apache/baremaps/tilestore/pmtiles/PMTilesTest.java +++ b/baremaps-core/src/test/java/org/apache/baremaps/tilestore/pmtiles/PMTilesTest.java @@ -18,31 +18,51 @@ import com.google.common.math.LongMath; import java.io.IOException; import java.nio.ByteBuffer; import java.nio.file.Files; +import java.util.ArrayList; +import java.util.Optional; import org.apache.baremaps.testing.TestFiles; import org.apache.baremaps.tilestore.pmtiles.PMTiles.Compression; +import org.apache.baremaps.tilestore.pmtiles.PMTiles.Entry; import org.apache.baremaps.tilestore.pmtiles.PMTiles.TileType; import org.junit.jupiter.api.Test; class PMTilesTest { @Test - void varint() { + void decodeVarInt() { var b = ByteBuffer.wrap(new byte[] { (byte) 0, (byte) 1, (byte) 127, (byte) 0xe5, (byte) 0x8e, (byte) 0x26 }); - assertEquals(PMTiles.readVarint(b), 0); - assertEquals(PMTiles.readVarint(b), 1); - assertEquals(PMTiles.readVarint(b), 127); - assertEquals(PMTiles.readVarint(b), 624485); + assertEquals(PMTiles.decodeVarInt(b), 0); + assertEquals(PMTiles.decodeVarInt(b), 1); + assertEquals(PMTiles.decodeVarInt(b), 127); + assertEquals(PMTiles.decodeVarInt(b), 624485); b = ByteBuffer.wrap(new byte[] { (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0x0f, }); - assertEquals(PMTiles.readVarint(b), 9007199254740991L); + assertEquals(PMTiles.decodeVarInt(b), 9007199254740991L); + } + + @Test + void encodeVarInt() { + var buffer = ByteBuffer.allocate(10); + for (long i = 0; i < 1000; i++) { + PMTiles.encodeVarInt(buffer, i); + buffer.flip(); + assertEquals(i, PMTiles.decodeVarInt(buffer)); + buffer.clear(); + } + for (long i = Long.MAX_VALUE - 1000; i < Long.MAX_VALUE; i++) { + PMTiles.encodeVarInt(buffer, i); + buffer.flip(); + assertEquals(i, PMTiles.decodeVarInt(buffer)); + buffer.clear(); + } } @Test @@ -102,13 +122,13 @@ class PMTilesTest { } @Test - void bytesToHeader() throws IOException { + void decodeHeader() throws IOException { var file = TestFiles.resolve("pmtiles/test_fixture_1.pmtiles"); try (var channel = Files.newByteChannel(file)) { var buffer = ByteBuffer.allocate(127); channel.read(buffer); buffer.flip(); - var header = PMTiles.bytesToHeader(buffer, "1"); + var header = PMTiles.decodeHeader(buffer, "1"); assertEquals(header.rootDirectoryOffset(), 127); assertEquals(header.rootDirectoryLength(), 25); assertEquals(header.jsonMetadataOffset(), 152); @@ -134,7 +154,7 @@ class PMTilesTest { } @Test - void headerToBytes() throws IOException { + void encodeHeader() throws IOException { var etag = "1"; var buffer = ByteBuffer.allocate(127); var header = new PMTiles.Header( @@ -164,9 +184,66 @@ class PMTilesTest { 0, 0, etag); - PMTiles.headerToBytes(header, buffer); - var header2 = PMTiles.bytesToHeader(buffer, etag); + PMTiles.encodeHeader(header, buffer); + var header2 = PMTiles.decodeHeader(buffer, etag); assertEquals(header, header2); } + @Test + void searchForMissingEntry() { + var entries = new ArrayList<Entry>(); + assertEquals(PMTiles.findTile(entries, 101), Optional.empty()); + } + + @Test + void searchForFirstEntry() { + var entry = new Entry(100, 1, 1, 1); + var entries = new ArrayList<Entry>(); + entries.add(entry); + assertEquals(PMTiles.findTile(entries, 100), Optional.of(entry)); + } + + @Test + void searchWithRunLength() { + var entry = new Entry(3, 3, 1, 2); + var entries = new ArrayList<Entry>(); + entries.add(entry); + entries.add(new Entry(5, 5, 1, 2)); + assertEquals(PMTiles.findTile(entries, 4), Optional.of(entry)); + } + + @Test + void searchWithMultipleTileEntries() { + var entries = new ArrayList<Entry>(); + entries.add(new Entry(100, 1, 1, 2)); + var entry = PMTiles.findTile(entries, 101); + assertEquals(entry.getOffset(), 1); + assertEquals(entry.getLength(), 1); + + entries = new ArrayList<Entry>(); + entries.add(new Entry(100, 1, 1, 1)); + entries.add(new Entry(150, 2, 2, 2)); + entry = PMTiles.findTile(entries, 151); + assertEquals(entry.getOffset(), 2); + assertEquals(entry.getLength(), 2); + + entries = new ArrayList<>(); + entries.add(new Entry(50, 1, 1, 2)); + entries.add(new Entry(100, 2, 2, 1)); + entries.add(new Entry(150, 3, 3, 1)); + entry = PMTiles.findTile(entries, 51); + assertEquals(entry.getOffset(), 1); + assertEquals(entry.getLength(), 1); + } + + @Test + void leafSearch() { + var entries = new ArrayList<Entry>(); + entries.add(new Entry(100, 1, 1, 0)); + var entry = PMTiles.findTile(entries, 150); + assertEquals(entry.getOffset(), 1); + assertEquals(entry.getLength(), 1); + } + + }
