Created
May 28, 2024 16:44
-
-
Save CraigglesO/00d1baa61635f36cd99212d06592ac9d to your computer and use it in GitHub Desktop.
Cloud Optimized S2 Tile spec
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import fs from 'fs' | |
import zlib, { brotliCompressSync, brotliDecompressSync } from 'zlib' | |
import * as S2CellID from 's2projection/s2CellID' | |
import type { Face } from 's2projection' | |
/** Types **/ | |
type DrawType = 1 | 2 | 3 | 4 // 1: points, 2: lines, 3: poly | |
type Node = [number, number] | |
export interface LayerFields { | |
[layerFieldKey: string]: Array<'Number' | 'String' | 'Boolean'> | |
} | |
export interface LayerMetaData { | |
[layer: string]: { // layer | |
description?: string | |
minzoom: number | |
maxzoom: number | |
drawTypes: DrawType[] | |
fields: LayerFields // max fields size of 10 | |
} | |
} | |
export interface TileStatsMetadata { | |
total: number | |
0: { total: number } | |
1: { total: number } | |
2: { total: number } | |
3: { total: number } | |
4: { total: number } | |
5: { total: number } | |
} | |
export interface Metadata { | |
name: string | |
format: 'fzxy' | |
description: string | |
type: 'vector' | 'raster' | 'rasterDEM' | 'rasterData' | 'json' | 'buffer' | |
encoding: 'gz' | 'br' | 'none' | |
faces: Face[] | |
facesbounds: { // facesbounds[face][zoom] = [...] | |
0: { [zoom: number]: [number, number, number, number] } | |
1: { [zoom: number]: [number, number, number, number] } | |
2: { [zoom: number]: [number, number, number, number] } | |
3: { [zoom: number]: [number, number, number, number] } | |
4: { [zoom: number]: [number, number, number, number] } | |
5: { [zoom: number]: [number, number, number, number] } | |
} | |
minzoom: number | |
maxzoom: number | |
attributions: { [name: string]: string } // { ['human readable string']: 'href' } | |
layers: LayerMetaData | |
tilestats: TileStatsMetadata | |
} | |
export interface Options { | |
readonly?: boolean | |
walClean?: boolean | |
wal?: boolean | |
maxzoom?: number | |
} | |
export interface TileSet { | |
face: number | |
zoom: number | |
x: number | |
y: number | |
data: Buffer | |
} | |
export type Directory = [offset: number, length: number] // list of [offset (6 bytes), length (4 bytes)] | |
const NODE_SIZE = 10 // [offset, length] => [6 bytes, 4 bytes] | |
const DIR_SIZE = 1_365 * NODE_SIZE // (13_650) -> 6 levels, the 6th level has both node and leaf (1+4+16+64+256+1024)*2 => (1365)+1365 => 2_730 | |
const ROOT_DIR_SIZE = DIR_SIZE * 6 // 27_300 * 6 = 163_800 | |
// assuming all tiles exist for every face from 0->30 the max leafs to reach depth of 30 is 5 | |
// root: 6sides * 27_300bytes/dir = (163_800 bytes) | |
// all leafs at 6: 1024 * 6sides * 27_300bytes/dir (0.167731 GB) | |
// al leafs at 12: 524_288 * 6sides * 27_300bytes/dir (85.8783744 GB) - obviously most of this is water | |
export default class S2Tiles { | |
file: number | |
offset = 0 | |
version = 1 | |
maxzoom: number | |
metadata: Metadata = defaultMetadata() | |
constructor (path: string, options: Options = {}) { | |
// build file if it does not exist yet | |
if (!fs.existsSync(path)) { | |
const buf = Buffer.alloc(20 + ROOT_DIR_SIZE) // also allocate room for metadataLength, metadataPosition, and some potential future information. Lastly store the roote directory | |
buf[0] = 83 // S | |
buf[1] = 50 // 2 | |
buf.writeUInt16LE(this.version, 2) | |
fs.appendFileSync(path, buf) | |
} | |
this.maxzoom = options.maxzoom ?? 20 | |
// open file | |
this.file = fs.openSync(path, options.readonly === true ? 'r' : 'r+') | |
// parse | |
this.#readHeader() | |
} | |
// if the header doesn't exist, we create it really quick | |
#readHeader (): void { | |
const { size } = fs.fstatSync(this.file) | |
this.offset = size | |
// read the id, version, and metadata | |
const rootDirData = Buffer.alloc(20) | |
fs.readSync(this.file, rootDirData, 0, 20, 0) | |
console.log(rootDirData) | |
if (rootDirData[0] !== 83 || rootDirData[1] !== 50) throw Error('This file is not an "S2Tiles" format') | |
// version | |
const version = rootDirData.readUint16LE(2) | |
this.version = version | |
// metadata | |
const mLen = rootDirData.readUint32LE(4) | |
const mPos = _readUInt48LE(rootDirData, 8) | |
if (mLen !== 0) { | |
const metadataBuf = Buffer.alloc(mLen) | |
fs.readSync(this.file, metadataBuf, 0, mLen, mPos) | |
this.metadata = JSON.parse(String(brotliDecompressSync(metadataBuf))) | |
this.maxzoom = this.metadata.maxzoom | |
} | |
} | |
putMetadata (metadata: Metadata): void { | |
// store metadata and metadata length | |
const metaBuf = brotliEncode(Buffer.from(JSON.stringify(metadata))) | |
fs.writeSync(this.file, metaBuf, 0, metaBuf.length, this.offset) | |
// store length and position | |
const metaLenPosBuf = Buffer.alloc(10) | |
metaLenPosBuf.writeUInt32LE(metaBuf.length) | |
_writeUInt48LE(metaLenPosBuf, this.offset, 4) | |
// update the offset | |
this.offset += metaBuf.length | |
fs.writeSync(this.file, metaLenPosBuf, 0, metaLenPosBuf.length, 4) | |
} | |
getTile (id: bigint): null | Buffer { | |
// if we made it here, we need to pull out the node and read in the contents | |
const [offset, length] = this._readNode(id) | |
if (length !== 0) { | |
const buf = Buffer.alloc(length) | |
fs.readSync(this.file, buf, 0, length, offset) | |
return buf | |
} else { return null } | |
} | |
getTileIJ (face: Face, level: number, i: number, j: number): null | Buffer { | |
const id = S2CellID.fromIJ(face, i, j, level) | |
return this.getTile(id) | |
} | |
// given a cell ID, find the offset and length | |
_readNode (id: bigint): Node { | |
// use the s2cellID and move the cursor | |
const cursor = this.#walk(id) | |
if (cursor === 0) return [0, 0] | |
// read contents at cursor position | |
const node = Buffer.alloc(NODE_SIZE) | |
fs.readSync(this.file, node, 0, NODE_SIZE, cursor) | |
return [_readUInt48LE(node), node.readUint32LE(6)] | |
} | |
// Inserts a tile into the S2Tiles store. | |
putTile (id: bigint, data: Uint8Array): void { | |
const length = data.byteLength | |
// first create node, setting offset | |
const node: Node = [this.offset, length] | |
fs.writeSync(this.file, data, 0, length, this.offset) | |
this.offset += length | |
// store node in the correct directory | |
this._putNodeInDir(id, node) | |
} | |
putTileIJ ( | |
face: Face, | |
level: number, | |
i: number, | |
j: number, | |
data: Uint8Array | |
): void { | |
const id = S2CellID.fromIJ(face, i, j, level) | |
this.putTile(id, data) | |
} | |
putBuffer (data: Buffer): void { | |
fs.writeSync(this.file, data, 0, data.length, this.offset) | |
this.offset += data.length | |
} | |
editBuffer (data: Buffer, offset: number): void { | |
fs.writeSync(this.file, data, 0, data.length, offset) | |
} | |
// Work our way towards the correct parent directory. | |
// If parent directory does not exists, we create it. | |
_putNodeInDir (id: bigint, node: Node): void { | |
// use the s2cellID and move the cursor | |
const cursor = this.#walk(id, true) | |
// finally store | |
this.#writeNode(cursor, node) | |
} | |
// given position and level, explain where to adust the cursor to file | |
#walk (id: bigint, create = false): number { | |
const { maxzoom } = this | |
// grab properties | |
const level: number = S2CellID.level(id) | |
const [face, i, j] = S2CellID.toIJ(id, level) | |
const leafNode = Buffer.alloc(NODE_SIZE) | |
let cursor: number = 20 + (DIR_SIZE * face) | |
// let dirPos: bigint = 61n | |
let leaf: number | |
let depth = 0 | |
const path = getPath(level, i, j) | |
while (path.length !== 0) { | |
// grab movement | |
const shift = path.shift() ?? 0 | |
depth++ | |
// update cursor position | |
cursor += shift * NODE_SIZE | |
if (path.length !== 0) { // if we hit a leaf, adjust nodePos position and move cursor to new directory | |
// if we are at the max zoom, we are already in the correct position (the "leaf" is actually a node instead) | |
if (maxzoom % 5 === 0 && path.length === 1 && level === maxzoom && path[0] === 0) return cursor | |
// grab the leaf from the file | |
fs.readSync(this.file, leafNode, 0, NODE_SIZE, cursor) | |
leaf = _readUInt48LE(leafNode) | |
// if the leaf doesn't, we create, otherwise we move to the leaf | |
if (leaf === 0) { | |
if (create) cursor = this.#createLeaf(cursor, depth * 5) | |
else return 0 | |
} else { cursor = leaf } // move to where leaf is pointing | |
} | |
} | |
return cursor | |
} | |
#createLeaf (cursor: number, depth: number): number { | |
// build directory size according to maxzoom | |
const dirSize = _buildDirSize(depth, this.maxzoom) | |
// let dirSize = DIR_SIZE | |
// create offset & node | |
const offset = this.offset | |
const node: Node = [offset, dirSize] | |
// create a dir of said size and update to new offset | |
fs.writeSync(this.file, Buffer.alloc(dirSize), 0, dirSize, offset) | |
this.offset += dirSize | |
// store our newly created directory as a leaf directory in our current directory | |
this.#writeNode(cursor, node) | |
// return the offset of the leaf directory | |
return offset | |
} | |
#writeNode (cursor: number, node: Node): void { | |
const [offset, length] = node | |
// write offset and length to buffer | |
const nodeBuf = Buffer.alloc(NODE_SIZE) | |
_writeUInt48LE(nodeBuf, offset) | |
nodeBuf.writeUInt32LE(length, 6) | |
// write buffer to file at directory offset | |
fs.writeSync(this.file, nodeBuf, 0, NODE_SIZE, cursor) | |
} | |
} | |
export function getDirPos (pos: number): [zoom: number, x: number, y: number] { | |
const { pow, floor } = Math | |
// first pull out zoom | |
let zoom = 0 | |
let zoomPos = pow(1 << zoom, 2) | |
while (zoomPos <= pos) { | |
pos -= zoomPos | |
zoom++ | |
zoomPos = pow(1 << zoom, 2) | |
} | |
// than figure out y | |
const zoomShift = (1 << zoom) | |
const y = floor(pos / zoomShift) | |
const x = pos % zoomShift | |
return [zoom, x, y] | |
} | |
// write a 32 bit and a 16 bit | |
function _writeUInt48LE ( | |
buffer: Buffer, | |
num: number, | |
offset = 0 | |
): void { | |
const lower = num & 0xFFFF | |
const upper = num / (1 << 16) | |
buffer.writeUInt16LE(lower, offset) | |
buffer.writeUInt32LE(upper, offset + 2) | |
} | |
function _readUInt48LE (buffer: Buffer, offset = 0): number { | |
return buffer.readUint32LE(2 + offset) * (1 << 16) + buffer.readUint16LE(offset) | |
} | |
function _buildDirSize (depth: number, maxzoom: number): number { | |
const { min, pow } = Math | |
let dirSize = 0 | |
// grab the remainder | |
let remainder = min(maxzoom - depth, 5) // must be increments of 5, so if level 4 then inc is 0 but if 5, inc is 5 | |
// for each remainder (including 0), we add a quadrant | |
do { dirSize += pow(1 << remainder, 2) } while (remainder-- !== 0) | |
return dirSize * NODE_SIZE | |
} | |
export function defaultMetadata (): Metadata { | |
return { | |
name: 'default', | |
format: 'fzxy', | |
type: 'vector', | |
encoding: 'none', | |
minzoom: Infinity, | |
maxzoom: -Infinity, | |
faces: [], | |
facesbounds: { | |
0: {}, | |
1: {}, | |
2: {}, | |
3: {}, | |
4: {}, | |
5: {} | |
}, | |
layers: {}, | |
attributions: {}, | |
description: '', | |
tilestats: { | |
total: 0, | |
0: { total: 0 }, | |
1: { total: 0 }, | |
2: { total: 0 }, | |
3: { total: 0 }, | |
4: { total: 0 }, | |
5: { total: 0 } | |
} | |
} | |
} | |
export function updateMetaData ( | |
metadata: Metadata, | |
face: Face, | |
zoom: number, | |
x: number, | |
y: number, | |
layers: string[], | |
layerFields: { [layer: string]: LayerFields } // { layer: { [layer-field-key]: [value, value, value] } } | |
): void { | |
const { min, max } = Math | |
// update tile stats | |
metadata.tilestats.total++ | |
metadata.tilestats[face].total++ | |
// update zoom metadata | |
metadata.maxzoom = max(metadata.maxzoom, zoom) | |
metadata.minzoom = min(metadata.minzoom, zoom) | |
// update face metadata | |
metadata.faces.push(face) | |
metadata.faces = [...(new Set(metadata.faces))] | |
if (metadata.facesbounds[face] === undefined) metadata.facesbounds[face] = {} | |
if (metadata.facesbounds[face][zoom] === undefined) metadata.facesbounds[face][zoom] = [Infinity, Infinity, -Infinity, -Infinity] | |
const fbfz = metadata.facesbounds[face][zoom] | |
if (fbfz[0] > x) fbfz[0] = x | |
if (fbfz[2] < x) fbfz[2] = x | |
if (fbfz[1] > y) fbfz[1] = y | |
if (fbfz[3] < y) fbfz[3] = y | |
// layers | |
for (const layer of layers) { | |
if (metadata.layers[layer] === undefined) metadata.layers[layer] = { minzoom: Infinity, maxzoom: -Infinity, fields: {}, drawTypes: [] } | |
metadata.layers[layer].minzoom = min(metadata.layers[layer].minzoom, zoom) | |
metadata.layers[layer].maxzoom = max(metadata.layers[layer].maxzoom, zoom) | |
} | |
// add in fields | |
for (const layer in layerFields) { | |
if (metadata.layers[layer] !== undefined) { | |
const metadataLayer = metadata.layers[layer] | |
const layerFieldLayer = layerFields[layer] | |
for (const layerKey in layerFieldLayer) { | |
if (metadataLayer.fields[layerKey] === undefined) metadataLayer.fields[layerKey] = [] | |
const joinedFields = [...metadataLayer.fields[layerKey], ...layerFieldLayer[layerKey]] | |
metadataLayer.fields[layerKey] = [...(new Set(joinedFields))] | |
while (metadataLayer.fields[layerKey].length > 50) metadataLayer.fields[layerKey].pop() | |
} | |
} | |
} | |
} | |
function getPath (zoom: number, x: number, y: number): number[] { | |
const { max, pow } = Math | |
const path: Array<[zoom: number, x: number, y: number]> = [] | |
while (zoom >= 5) { | |
path.push([5, x & 31, y & 31]) | |
x >>= 5 | |
y >>= 5 | |
zoom = max(zoom - 5, 0) | |
} | |
path.push([zoom, x, y]) | |
return path.map(([zoom, x, y]) => { | |
let val = 0 | |
val += y * (1 << zoom) + x | |
while (zoom-- !== 0) val += pow(1 << zoom, 2) | |
return val | |
}) | |
} | |
const brotliEncode = (data: Buffer): Buffer => { | |
return brotliCompressSync(data, { | |
chunkSize: 32 * 1024, | |
params: { | |
[zlib.constants.BROTLI_PARAM_MODE]: zlib.constants.BROTLI_MODE_GENERIC, | |
[zlib.constants.BROTLI_PARAM_QUALITY]: 11, | |
[zlib.constants.BROTLI_PARAM_SIZE_HINT]: data.length | |
} | |
}) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment