Avoid integer overflow when computing shortcodes

Although javascript's numbers are double precision floating point
number which support 52 bits of precision the bitwise operations are
only guaranteed to work at 32 bits of precision so we need to avoid
relying on them doing more than that.

diff --git a/public/javascripts/site.js b/public/javascripts/site.js
index b11a2e012c88b07c0d212f7b3a0c4a02cad5ef21..840617e175e8201ba3749ec15bcc048eb852214a 100644 (file)
--- a/public/javascripts/site.js
+++ b/public/javascripts/site.js
@@ -254,23 +254,35 @@ function i18n(string, keys) {
   return string;
 }
 
   return string;
 }
 

+/*
+ * Called to interlace the bits in x and y, making a Morton code.
+ */
+function interlace(x, y) {
+    x = (x | (x << 8)) & 0x00ff00ff;
+    x = (x | (x << 4)) & 0x0f0f0f0f;
+    x = (x | (x << 2)) & 0x33333333;
+    x = (x | (x << 1)) & 0x55555555;
+
+    y = (y | (y << 8)) & 0x00ff00ff;
+    y = (y | (y << 4)) & 0x0f0f0f0f;
+    y = (y | (y << 2)) & 0x33333333;
+    y = (y | (y << 1)) & 0x55555555;
+
+    return (x << 1) | y;
+}
+
+/*
+ * Called to create a short code for the short link.
+ */

 function makeShortCode(lat, lon, zoom) {
     char_array = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_@";
     var x = Math.round((lon + 180.0) * ((1 << 30) / 90.0));
     var y = Math.round((lat +  90.0) * ((1 << 30) / 45.0));
 function makeShortCode(lat, lon, zoom) {
     char_array = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_@";
     var x = Math.round((lon + 180.0) * ((1 << 30) / 90.0));
     var y = Math.round((lat +  90.0) * ((1 << 30) / 45.0));

-    // hack around the fact that JS apparently only allows 53-bit integers?!?
-    // note that, although this reduces the accuracy of the process, it's fine for
-    // z18 so we don't need to care for now.
-    var c1 = 0, c2 = 0;
-    for (var i = 31; i > 16; --i) {
-        c1 = (c1 << 1) | ((x >> i) & 1);
-        c1 = (c1 << 1) | ((y >> i) & 1);
-    }
-    for (var i = 16; i > 1; --i) {
-        c2 = (c2 << 1) | ((x >> i) & 1);
-        c2 = (c2 << 1) | ((y >> i) & 1);
-    }
+    // JavaScript only has to keep 32 bits of bitwise operators, so this has to be
+    // done in two parts. each of the parts c1/c2 has 30 bits of the total in it
+    // and drops the last 4 bits of the full 64 bit Morton code.

     var str = "";
     var str = "";

+    var c1 = interlace(x >>> 17, y >>> 17), c2 = interlace((x >>> 2) & 0x7fff, (y >>> 2) & 0x7fff);

     for (var i = 0; i < Math.ceil((zoom + 8) / 3.0) && i < 5; ++i) {
         digit = (c1 >> (24 - 6 * i)) & 0x3f;
         str += char_array.charAt(digit);
     for (var i = 0; i < Math.ceil((zoom + 8) / 3.0) && i < 5; ++i) {
         digit = (c1 >> (24 - 6 * i)) & 0x3f;
         str += char_array.charAt(digit);