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
The following commit(s) were added to refs/heads/pmtiles by this push:
new 3aad0673 Port additional methods and tests
3aad0673 is described below
commit 3aad06737ba6f6eb52a3f1b75f866a6b92aaf4de
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);
+ }
+
+
}
