Cloud Optimized S2 Tile spec

s2tiles.ts

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
    }
  })
}