From 43a4c11187e00647500fd88f5c88eff7fc28d3c6 Mon Sep 17 00:00:00 2001
From: David Storch <david.storch@10gen.com>
Date: Wed, 2 Mar 2016 15:24:22 -0500
Subject: SERVER-22695 fix left shift of negative number in
 GeoHash::clearUnusedBits()

---
 src/mongo/db/geo/hash.cpp      | 12 +++++-------
 src/mongo/db/geo/hash_test.cpp | 38 +++++++++++++++++++++++++++++++++++---
 2 files changed, 40 insertions(+), 10 deletions(-)

diff --git a/src/mongo/db/geo/hash.cpp b/src/mongo/db/geo/hash.cpp
index 281a8b9544a..9b96a98a957 100644
--- a/src/mongo/db/geo/hash.cpp
+++ b/src/mongo/db/geo/hash.cpp
@@ -471,10 +471,9 @@ GeoHash GeoHash::operator+(const std::string& s) const {
     return operator+(s.c_str());
 }
 
-/*
- * Keep the upper _bits*2 bits of _hash, clear the lower bits.
- * Maybe there's junk in there?  Not sure why this is done.
- */
+// Keep the most significant _bits*2 bits of _hash, clear the least significant bits. If shorter
+// than 64 bits, the hash occupies the higher order bits, so we ensure that the lower order bits are
+// zeroed.
 void GeoHash::clearUnusedBits() {
     // Left shift count should be less than 64
     if (_bits == 0) {
@@ -482,9 +481,8 @@ void GeoHash::clearUnusedBits() {
         return;
     }
 
-    static long long FULL = 0xFFFFFFFFFFFFFFFFLL;
-    long long mask = FULL << (64 - (_bits * 2));
-    _hash &= mask;
+    unsigned long long mask = (1LL << (64U - (_bits * 2U))) - 1LL;
+    _hash &= ~mask;
 }
 
 static void appendHashToBuilder(long long hash, BSONObjBuilder* builder, const char* fieldName) {
diff --git a/src/mongo/db/geo/hash_test.cpp b/src/mongo/db/geo/hash_test.cpp
index 93fffb2fbe3..bfe6050fd9d 100644
--- a/src/mongo/db/geo/hash_test.cpp
+++ b/src/mongo/db/geo/hash_test.cpp
@@ -42,15 +42,17 @@
 #include "mongo/platform/random.h"
 #include "mongo/unittest/unittest.h"
 #include "mongo/util/assert_util.h"
+#include "mongo/util/mongoutils/str.h"
+
+namespace {
+
+using namespace mongo;
 
-using mongo::GeoHash;
-using mongo::GeoHashConverter;
 using std::cout;
 using std::endl;
 using std::string;
 using std::stringstream;
 
-namespace {
 TEST(GeoHash, MakeZeroHash) {
     unsigned x = 0, y = 0;
     GeoHash hash(x, y);
@@ -516,4 +518,34 @@ TEST(GeoHash, NeighborsAtFinestLevel) {
     ASSERT_EQUALS(neighbors.size(), (size_t)1);
     ASSERT_EQUALS(neighbors[0], GeoHash("00"));
 }
+
+TEST(GeoHash, ClearUnusedBitsClearsSomeBits) {
+    GeoHash geoHash("10110010");
+    // 'parent' should have the four higher order bits from the original hash (1011, or the
+    // hexidecimal digit 'b').
+    GeoHash parent = geoHash.parent(2);
+    ASSERT_EQUALS(parent, GeoHash("1011"));
+    const long long expectedHash = 0xb000000000000000LL;
+    ASSERT_EQUALS(expectedHash, parent.getHash());
+}
+
+TEST(GeoHash, ClearUnusedBitsOnLengthZeroHashClearsAllBits) {
+    GeoHash geoHash("11");
+    const long long expectedHash = 0xc000000000000000LL;
+    ASSERT_EQUALS(expectedHash, geoHash.getHash());
+    GeoHash parent = geoHash.parent();
+    ASSERT_EQUALS(GeoHash(), parent);
+    ASSERT_EQUALS(0LL, parent.getHash());
+}
+
+TEST(GeoHash, ClearUnusedBitsIsNoopIfNoBitsAreUnused) {
+    // 64 pairs of "10" repeated.
+    str::stream ss;
+    for (int i = 0; i < 32; ++i) {
+        ss << "10";
+    }
+    GeoHash geoHash(ss);
+    GeoHash other = geoHash.parent(32);
+    ASSERT_EQUALS(geoHash, other);
+}
 }
-- 
cgit v1.2.1