From: Matt Amos <zerebubuth@gmail.com>
Date: Sun, 5 Dec 2010 11:00:57 +0000 (+0000)
Subject: Avoid integer overflow when computing shortcodes
X-Git-Tag: live~6290^2
X-Git-Url: https://git.openstreetmap.org/rails.git/commitdiff_plain/42ef10ba80bf7ff13b4f9210e5fbf54538e0d52f?hp=616e9ce7b920ca5b1834f036099c89626d8aca9f

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 b11a2e012..840617e17 100644
--- a/public/javascripts/site.js
+++ b/public/javascripts/site.js
@@ -254,23 +254,35 @@ function i18n(string, keys) {
   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));
-    // 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 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);