From 42ef10ba80bf7ff13b4f9210e5fbf54538e0d52f Mon Sep 17 00:00:00 2001 From: Matt Amos Date: Sun, 5 Dec 2010 11:00:57 +0000 Subject: [PATCH] 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. --- public/javascripts/site.js | 36 ++++++++++++++++++++++++------------ 1 file changed, 24 insertions(+), 12 deletions(-) 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); -- 2.34.1