#!/usr/bin/perl

# License: GNU General Public License 2.0, http://www.gnu.org/licenses/old-licenses/gpl-2.0.txt

# makeShortCode algorithm inspired from:
# https://github.com/openstreetmap/openstreetmap-website/blob/e84b2bd22f7c92fb7a128a91c999f86e350bf04d/app/assets/javascripts/application.js

use POSIX;
use Math::BigInt;

if($#ARGV!=2) { die("Syntax: osmmakeshortlink.pl lat lon zoom\n"); }

($lat,$lon,$z)=@ARGV;

print "Long URL: http://www.openstreetmap.org/#map=$z/$lat/$lon\n";
$sc=&makeShortCode($lat,$lon,$z);
print "Short Code: $sc\n";
print "Short URL: http://osm.org/go/$sc\n";
($lat,$lon,$z)=&decodeShortCode($sc);
print "Long URL: http://www.openstreetmap.org/#map=$z/$lat/$lon\n";


sub makeShortCode {
  $char_array = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_~";
  my $x=floor(($_[1] + 180.0) * ((1 << 30) / 90.0) +.5);
  my $y=floor(($_[0] + 90.0) * ((1 << 30) / 45.0) + .5);
  my $z=$_[2];
  if($z<1 || $z>22) { 
    print STDERR "makeShortCode: Zoom $z will probably not give a reasonable result\n";
  }
  my $str="";
  my $c=&interleave($x,$y);
  foreach my $i (1 .. ceil(($z + 8) / 3.0)) {
    $digit = ($c->copy()->brsft(64 - 6 * $i))->band(0x3f);
    $str.=substr($char_array,$digit,1);
  }
  foreach $i (1 .. ($z+8)%3) {
    $str.="-";
  }
  return $str;
}

sub interleave {
  # combine 2 32 bit integers to a 64 bit integer
  $c=Math::BigInt->bzero();
  (my $x,my $y)=@_;
  foreach $i (-31 .. 0) {
    $c1 = $c->copy()->blsft(1); $c=$c1->copy()->bior(($x >> -$i) & 1);
    $c1 = $c->copy()->blsft(1); $c=$c1->copy()->bior(($y >> -$i) & 1);
  }
  return $c;
}

sub decodeShortCode {
  $char_array = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_~";
  my $sc=$_[0];
  my $x=0;
  my $y=0;
  my $i;
  my $z=-8;
  if($sc!~/^[A-Za-z0-9_~]{1,10}-{0,2}$/) {
    print STDERR "decodeShortCode: not a valid short code\n";
    return ($y,$x,$z);
  }
  for ($i=0; $i<length($sc); $i++) {
    $ch=substr($sc,$i,1);
    $digit=index($char_array,$ch);
    last if $digit == -1;
    # distribute 6 bits into $x and $y
    $x <<= 3;
    $y <<= 3;
    foreach my $j (-2 .. 0) {
      $x|= (($digit & (1 << (2*-$j+1))) == 0 ? 0 : (1 << -$j));
      $y|= (($digit & (1 << (2*-$j))) == 0 ? 0 : (1 << -$j));
    }
    $z+=3;
  }
  $x = $x * 2**(2-3*$i) * 90 - 180;
  $y = $y * 2**(2-3*$i) * 45 - 90;
  # adjust $z
  if($i<length($sc) && substr($sc,$i,1) eq "-") {
    $z-=2;
    if($i+1<length($sc) && substr($sc,$i+1,1) eq "-") { $z++; }
  }
  return ($y,$x,$z);
}