You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@baremaps.apache.org by bc...@apache.org on 2023/09/07 15:26:14 UTC
[incubator-baremaps] 01/06: Add pmtiles functions
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 97ac1b6172b37e4bbcf82e1f98361d3d96f3098a
Author: Bertil Chapuis <bc...@gmail.com>
AuthorDate: Tue Sep 5 17:27:09 2023 +0200
Add pmtiles functions
---
.../apache/baremaps/tilestore/pmtiles/PMTiles.java | 145 +++++++++++++++++++++
.../baremaps/tilestore/pmtiles/PMTilesTest.java | 88 +++++++++++++
2 files changed, 233 insertions(+)
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
new file mode 100644
index 00000000..c84b19b2
--- /dev/null
+++ b/baremaps-core/src/main/java/org/apache/baremaps/tilestore/pmtiles/PMTiles.java
@@ -0,0 +1,145 @@
+package org.apache.baremaps.tilestore.pmtiles;
+
+import com.google.common.math.LongMath;
+
+import java.nio.ByteBuffer;
+
+public class PMTiles {
+
+ public static long toNum(long low, long high) {
+ return high * 0x100000000L + low;
+ }
+
+ public static long readVarintRemainder(long l, ByteBuffer buf) {
+ long h, b;
+ b = buf.get() & 0xff;
+ h = (b & 0x70) >> 4;
+ if (b < 0x80) {
+ return toNum(l, h);
+ }
+ b = buf.get() & 0xff;
+ h |= (b & 0x7f) << 3;
+ if (b < 0x80) {
+ return toNum(l, h);
+ }
+ b = buf.get() & 0xff;
+ h |= (b & 0x7f) << 10;
+ if (b < 0x80) {
+ return toNum(l, h);
+ }
+ b = buf.get() & 0xff;
+ h |= (b & 0x7f) << 17;
+ if (b < 0x80) {
+ return toNum(l, h);
+ }
+ b = buf.get() & 0xff;
+ h |= (b & 0x7f) << 24;
+ if (b < 0x80) {
+ return toNum(l, h);
+ }
+ b = buf.get() & 0xff;
+ h |= (b & 0x01) << 31;
+ if (b < 0x80) {
+ return toNum(l, h);
+ }
+ throw new RuntimeException("Expected varint not more than 10 bytes");
+ }
+
+ public static long readVarint(ByteBuffer buf) {
+ long val, b;
+ b = buf.get() & 0xff;
+ val = b & 0x7f;
+ if (b < 0x80) {
+ return val;
+ }
+ b = buf.get() & 0xff;
+ val |= (b & 0x7f) << 7;
+ if (b < 0x80) {
+ return val;
+ }
+ b = buf.get() & 0xff;
+ val |= (b & 0x7f) << 14;
+ if (b < 0x80) {
+ return val;
+ }
+ b = buf.get() & 0xff;
+ val |= (b & 0x7f) << 21;
+ if (b < 0x80) {
+ return val;
+ }
+ val |= (b & 0x0f) << 28;
+ return readVarintRemainder(val, buf);
+ }
+
+ public static void rotate(long n, long[] xy, long rx, long ry) {
+ if (ry == 0) {
+ if (rx == 1) {
+ xy[0] = n - 1 - xy[0];
+ xy[1] = n - 1 - xy[1];
+ }
+ long t = xy[0];
+ xy[0] = xy[1];
+ xy[1] = t;
+ }
+ }
+
+ public static long[] idOnLevel(int z, long pos) {
+ long n = LongMath.pow(2, z);
+ long rx, ry, t = pos;
+ long[] xy = new long[]{0, 0};
+ long s = 1;
+ while (s < n) {
+ rx = 1 & (t / 2);
+ ry = 1 & (t ^ rx);
+ rotate(s, xy, rx, ry);
+ xy[0] += s * rx;
+ xy[1] += s * ry;
+ t = t / 4;
+ s *= 2;
+ }
+ return new long[]{z, xy[0], xy[1]};
+ }
+
+ private static long[] tzValues = new long[]{
+ 0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381, 349525, 1398101, 5592405,
+ 22369621, 89478485, 357913941, 1431655765, 5726623061L, 22906492245L,
+ 91625968981L, 366503875925L, 1466015503701L, 5864062014805L, 23456248059221L,
+ 93824992236885L, 375299968947541L, 1501199875790165L,
+ };
+
+ public static long zxyToTileId(int z, long x, long y) {
+ if (z > 26) {
+ throw new RuntimeException("Tile zoom level exceeds max safe number limit (26)");
+ }
+ if (x > Math.pow(2, z) - 1 || y > Math.pow(2, z) - 1) {
+ throw new RuntimeException("tile x/y outside zoom level bounds");
+ }
+ long acc = tzValues[z];
+ long n = LongMath.pow(2, z);
+ long rx = 0;
+ long ry = 0;
+ long d = 0;
+ long[] xy = new long[]{x, y};
+ long s = n / 2;
+ while (s > 0) {
+ rx = (xy[0] & s) > 0 ? 1 : 0;
+ ry = (xy[1] & s) > 0 ? 1 : 0;
+ d += s * s * ((3 * rx) ^ ry);
+ rotate(s, xy, rx, ry);
+ s = s / 2;
+ }
+ return acc + d;
+ }
+
+ public static long[] tileIdToZxy(long i) {
+ long acc = 0;
+ for (int z = 0; z < 27; z++) {
+ long numTiles = (0x1L << z) * (0x1L << z);
+ if (acc + numTiles > i) {
+ return idOnLevel(z, i - acc);
+ }
+ acc += numTiles;
+ }
+ throw new RuntimeException("Tile zoom level exceeds max safe number limit (26)");
+ }
+}
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
new file mode 100644
index 00000000..c119a882
--- /dev/null
+++ b/baremaps-core/src/test/java/org/apache/baremaps/tilestore/pmtiles/PMTilesTest.java
@@ -0,0 +1,88 @@
+package org.apache.baremaps.tilestore.pmtiles;
+
+import com.google.common.math.LongMath;
+import org.junit.jupiter.api.Test;
+
+import java.nio.ByteBuffer;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class PMTilesTest {
+
+ @Test
+ void varint() {
+ 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);
+ 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);
+ }
+
+ @Test
+ void zxyToTileId() {
+ assertEquals(PMTiles.zxyToTileId(0, 0, 0), 0);
+ assertEquals(PMTiles.zxyToTileId(1, 0, 0), 1);
+ assertEquals(PMTiles.zxyToTileId(1, 0, 1), 2);
+ assertEquals(PMTiles.zxyToTileId(1, 1, 1), 3);
+ assertEquals(PMTiles.zxyToTileId(1, 1, 0), 4);
+ assertEquals(PMTiles.zxyToTileId(2, 0, 0), 5);
+ }
+
+ @Test
+ void tileIdToZxy() {
+ assertArrayEquals(PMTiles.tileIdToZxy(0), new long[]{0, 0, 0});
+ assertArrayEquals(PMTiles.tileIdToZxy(1), new long[]{1, 0, 0});
+ assertArrayEquals(PMTiles.tileIdToZxy(2), new long[]{1, 0, 1});
+ assertArrayEquals(PMTiles.tileIdToZxy(3), new long[]{1, 1, 1});
+ assertArrayEquals(PMTiles.tileIdToZxy(4), new long[]{1, 1, 0});
+ assertArrayEquals(PMTiles.tileIdToZxy(5), new long[]{2, 0, 0});
+ }
+
+ @Test
+ void aLotOfTiles() {
+ for (int z = 0; z < 9; z++) {
+ for (long x = 0; x < 1 << z; x++) {
+ for (long y = 0; y < 1 << z; y++) {
+ var result = PMTiles.tileIdToZxy(PMTiles.zxyToTileId(z, x, y));
+ if (result[0] != z || result[1] != x || result[2] != y) {
+ fail("roundtrip failed");
+ }
+ }
+ }
+ }
+ }
+
+ @Test
+ void tileExtremes() {
+ for (var z = 0; z < 27; z++) {
+ var dim = LongMath.pow(2, z) - 1;
+ var tl = PMTiles.tileIdToZxy(PMTiles.zxyToTileId(z, 0, 0));
+ assertArrayEquals(new long[]{z, 0, 0}, tl);
+ var tr = PMTiles.tileIdToZxy(PMTiles.zxyToTileId(z, dim, 0));
+ assertArrayEquals(new long[]{z, dim, 0}, tr);
+ var bl = PMTiles.tileIdToZxy(PMTiles.zxyToTileId(z, 0, dim));
+ assertArrayEquals(new long[]{z, 0, dim}, bl);
+ var br = PMTiles.tileIdToZxy(PMTiles.zxyToTileId(z, dim, dim));
+ assertArrayEquals(new long[]{z, dim, dim}, br);
+ }
+ }
+
+ @Test
+ void invalidTiles() {
+ assertThrows(RuntimeException.class, () -> PMTiles.tileIdToZxy(9007199254740991L));
+ assertThrows(RuntimeException.class, () -> PMTiles.zxyToTileId(27, 0, 0));
+ assertThrows(RuntimeException.class, () -> PMTiles.zxyToTileId(0, 1, 1));
+ }
+
+}
\ No newline at end of file