lib/short_link.rb

   1 # frozen_string_literal: true
   2
   3 ##
   4 # Encodes and decodes locations from Morton-coded "quad tile" strings. Each
   5 # variable-length string encodes to a precision of one pixel per tile (roughly,
   6 # since this computation is done in lat/lon coordinates, not mercator).
   7 # Each character encodes 3 bits of x and 3 of y, so there are extra characters
   8 # tacked on the end to make the zoom levels "work".
   9 module ShortLink
  10   # array of 64 chars to encode 6 bits. this is almost like base64 encoding, but
  11   # the symbolic chars are different, as base64's + and / aren't very
  12   # URL-friendly.
  13   ARRAY = ("A".."Z").to_a + ("a".."z").to_a + ("0".."9").to_a + ["_", "~"]
  14
  15   class << self
  16     ##
  17     # Given a string encoding a location, returns the [lon, lat, z] tuple of that
  18     # location.
  19     def decode(str)
  20       x = 0
  21       y = 0
  22       z = 0
  23       z_offset = 0
  24
  25       # keep support for old shortlinks which use the @ character, now
  26       # replaced by the ~ character because twitter is horribly broken
  27       # and we can't have that.
  28       str = str.tr("@", "~")
  29
  30       str.each_char do |c|
  31         t = ARRAY.index c
  32         if t.nil?
  33           z_offset -= 1
  34         else
  35           3.times do
  36             x <<= 1
  37             x |= 1 unless t.nobits?(32)
  38             t <<= 1
  39
  40             y <<= 1
  41             y |= 1 unless t.nobits?(32)
  42             t <<= 1
  43           end
  44           z += 3
  45         end
  46       end
  47       # pack the coordinates out to their original 32 bits.
  48       x <<= (32 - z)
  49       y <<= (32 - z)
  50
  51       # project the parameters back to their coordinate ranges.
  52       [(x * 360.0 / (2**32)) - 180.0,
  53        (y * 180.0 / (2**32)) - 90.0,
  54        z - 8 - (z_offset % 3)]
  55     end
  56
  57     ##
  58     # given a location and zoom, return a short string representing it.
  59     def encode(lon, lat, z)
  60       code = interleave_bits(((lon + 180.0) * (2**32) / 360.0).to_i,
  61                              ((lat + 90.0) * (2**32) / 180.0).to_i)
  62       str = +""
  63       # add eight to the zoom level, which approximates an accuracy of
  64       # one pixel in a tile.
  65       ((z + 8) / 3.0).ceil.times do |i|
  66         digit = (code >> (58 - (6 * i))) & 0x3f
  67         str << ARRAY[digit]
  68       end
  69       # append characters onto the end of the string to represent
  70       # partial zoom levels (characters themselves have a granularity
  71       # of 3 zoom levels).
  72       ((z + 8) % 3).times { str << "-" }
  73
  74       str
  75     end
  76
  77     private
  78
  79     ##
  80     # interleaves the bits of two 32-bit numbers. the result is known
  81     # as a Morton code.
  82     def interleave_bits(x, y)
  83       c = 0
  84       31.downto(0) do |i|
  85         c = (c << 1) | ((x >> i) & 1)
  86         c = (c << 1) | ((y >> i) & 1)
  87       end
  88       c
  89     end
  90   end
  91 end