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 0167819998b7ec82285444679131362014217cbb Author: Bertil Chapuis <[email protected]> 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
