[vcpkg] Correct UInt128 code 😇 (#10583)

* [vcpkg] Correct UInt128 code 😇

`UInt128::operator<<(x, y)` should clear the bottom 64 bits of `x` if
`y >= 64`; however, we don't do this, and so we duplicate `x`'s bottom
bits into `x.top` instead of moving them. Similarly, we have the
opposite problem for `UInt128::operator>>`. This commit fixes these
latent bugs, which we weren't hitting because the thing we use them for
never actually shifts more than 64 bits.

4 files changed, 150 insertions, 73 deletions

diff --git a/toolsrc/include/vcpkg/base/uint128.h b/toolsrc/include/vcpkg/base/uint128.h
new file mode 100644
index 000000000..6b7816760
--- /dev/null
+++ b/toolsrc/include/vcpkg/base/uint128.h
@@ -0,0 +1,26 @@
+#pragma once
+
+#include <stdint.h>
+
+namespace vcpkg {
+
+struct UInt128 {
+    UInt128() = default;
+    UInt128(uint64_t value) : bottom(value), top(0) {}
+
+    UInt128& operator<<=(int by) noexcept;
+    UInt128& operator>>=(int by) noexcept;
+    UInt128& operator+=(uint64_t lhs) noexcept;
+
+    uint64_t bottom_64_bits() const noexcept {
+        return bottom;
+    }
+    uint64_t top_64_bits() const noexcept {
+        return top;
+    }
+private:
+    uint64_t bottom;
+    uint64_t top;
+};
+
+}
diff --git a/toolsrc/src/vcpkg-test/uint128.cpp b/toolsrc/src/vcpkg-test/uint128.cpp
new file mode 100644
index 000000000..57d0169af
--- /dev/null
+++ b/toolsrc/src/vcpkg-test/uint128.cpp
@@ -0,0 +1,64 @@
+#include <catch2/catch.hpp>
+
+#include <vcpkg/base/uint128.h>
+
+TEST_CASE ("uint128 constructor and assign", "[uint128]") {
+	vcpkg::UInt128 x = 120;
+	REQUIRE(x.bottom_64_bits() == 120);
+	REQUIRE(x.top_64_bits() == 0);
+
+	x = 3201;
+	REQUIRE(x.bottom_64_bits() == 3201);
+	REQUIRE(x.top_64_bits() == 0);
+	
+	x = 0xFFFF'FFFF'FFFF'FFFF;
+	REQUIRE(x.bottom_64_bits() == 0xFFFF'FFFF'FFFF'FFFF);
+	REQUIRE(x.top_64_bits() == 0);
+}
+
+TEST_CASE ("uint128 add-assign", "[uint128]") {
+	vcpkg::UInt128 x = 0xFFFF'FFFF'FFFF'FFFF;
+	x += 1;
+	REQUIRE(x.bottom_64_bits() == 0);
+	REQUIRE(x.top_64_bits() == 1);
+}
+
+TEST_CASE ("uint128 shl-assign", "[uint128]") {
+	vcpkg::UInt128 x = 0xFFFF'FFFF'FFFF'FFFF;
+	x <<= 32;
+	REQUIRE(x.bottom_64_bits() == 0xFFFF'FFFF'0000'0000);
+	REQUIRE(x.top_64_bits() == 0x0000'0000'FFFF'FFFF);
+	
+	x <<= 60;
+	REQUIRE(x.bottom_64_bits() == 0);
+	REQUIRE(x.top_64_bits() == 0xFFFF'FFFF'F000'0000);
+
+	x = 1;
+	x <<= 96;
+	REQUIRE(x.bottom_64_bits() == 0);
+	REQUIRE(x.top_64_bits() == (uint64_t(1) << 32));
+}
+
+TEST_CASE ("uint128 shr-assign", "[uint128]") {
+	vcpkg::UInt128 x = 0xFFFF'FFFF'FFFF'FFFF;
+	x <<= 64;
+	REQUIRE(x.bottom_64_bits() == 0x0000'0000'0000'0000);
+	REQUIRE(x.top_64_bits() == 0xFFFF'FFFF'FFFF'FFFF);
+
+	x >>= 32;
+	REQUIRE(x.bottom_64_bits() == 0xFFFF'FFFF'0000'0000);
+	REQUIRE(x.top_64_bits() == 0x0000'0000'FFFF'FFFF);
+	
+	x >>= 60;
+	REQUIRE(x.bottom_64_bits() == 0x0000'000F'FFFF'FFFF);
+	REQUIRE(x.top_64_bits() == 0x0000'0000'0000'0000);
+
+	x = 0x8000'0000'0000'0000;
+	x <<= 64;
+	REQUIRE(x.bottom_64_bits() == 0);
+	REQUIRE(x.top_64_bits() == 0x8000'0000'0000'0000);
+
+	x >>= 96;
+	REQUIRE(x.bottom_64_bits() == (uint64_t(1) << 31));
+	REQUIRE(x.top_64_bits() == 0);
+}
diff --git a/toolsrc/src/vcpkg/base/hash.cpp b/toolsrc/src/vcpkg/base/hash.cpp
index b70897a2b..b54f0c40c 100644
--- a/toolsrc/src/vcpkg/base/hash.cpp
+++ b/toolsrc/src/vcpkg/base/hash.cpp
@@ -3,6 +3,7 @@
 #include <vcpkg/base/hash.h>
 
 #include <vcpkg/base/checks.h>
+#include <vcpkg/base/uint128.h>
 #include <vcpkg/base/strings.h>
 #include <vcpkg/base/system.process.h>
 #include <vcpkg/base/util.h>
@@ -50,82 +51,13 @@ namespace vcpkg::Hash
         }
     }
 
-    namespace
-    {
-        struct UInt128
-        {
-            std::uint64_t top;
-            std::uint64_t bottom;
-
-            UInt128() = default;
-            UInt128(std::uint64_t value) : top(0), bottom(value) {}
-
-            UInt128& operator<<=(int by) noexcept
-            {
-                if (by == 0)
-                {
-                    return *this;
-                }
-
-                if (by < 64)
-                {
-                    top <<= by;
-                    const auto shift_up = bottom >> (64 - by);
-                    top |= shift_up;
-                    bottom <<= by;
-                }
-                else
-                {
-                    top = bottom;
-                    top <<= (by - 64);
-                }
-
-                return *this;
-            }
-
-            UInt128& operator>>=(int by) noexcept
-            {
-                if (by == 0)
-                {
-                    return *this;
-                }
-
-                if (by < 64)
-                {
-                    bottom >>= by;
-                    const auto shift_down = top << (64 - by);
-                    bottom |= shift_down;
-                    top >>= by;
-                }
-                else
-                {
-                    bottom = top;
-                    bottom >>= (by - 64);
-                }
-
-                return *this;
-            }
-
-            UInt128& operator+=(std::size_t lhs) noexcept
-            {
-                // bottom + lhs > uint64::max
-                if (bottom > std::numeric_limits<std::uint64_t>::max() - lhs)
-                {
-                    top += 1;
-                }
-                bottom += lhs;
-                return *this;
-            }
-        };
-
-    }
     template<class T>
     void top_bits(T) = delete;
 
-    static constexpr uchar top_bits(uchar x) noexcept { return x; }
-    [[maybe_unused]] static constexpr uchar top_bits(std::uint32_t x) noexcept { return (x >> 24) & 0xFF; }
-    [[maybe_unused]] static constexpr uchar top_bits(std::uint64_t x) noexcept { return (x >> 56) & 0xFF; }
-    [[maybe_unused]] static constexpr uchar top_bits(UInt128 x) noexcept { return top_bits(x.top); }
+    [[maybe_unused]] static uchar top_bits(uchar x) noexcept { return x; }
+    [[maybe_unused]] static uchar top_bits(std::uint32_t x) noexcept { return (x >> 24) & 0xFF; }
+    [[maybe_unused]] static uchar top_bits(std::uint64_t x) noexcept { return (x >> 56) & 0xFF; }
+    [[maybe_unused]] static uchar top_bits(UInt128 x) noexcept { return top_bits(x.top_64_bits()); }
 
     // treats UIntTy as big endian for the purpose of this mapping
     template<class UIntTy>
diff --git a/toolsrc/src/vcpkg/base/uint128.cpp b/toolsrc/src/vcpkg/base/uint128.cpp
new file mode 100644
index 000000000..e0256075e
--- /dev/null
+++ b/toolsrc/src/vcpkg/base/uint128.cpp
@@ -0,0 +1,55 @@
+#include <vcpkg/base/uint128.h>
+
+#include <limits>
+
+namespace vcpkg {
+
+UInt128& UInt128::operator<<=(int by) noexcept {
+    if (by == 0) {
+        return *this;
+    }
+
+    if (by < 64) {
+        top <<= by;
+        const auto shift_up = bottom >> (64 - by);
+        top |= shift_up;
+        bottom <<= by;
+    } else {
+        top = bottom;
+        top <<= (by - 64);
+        bottom = 0;
+    }
+
+    return *this;
+}
+
+UInt128& UInt128::operator>>=(int by) noexcept {
+    if (by == 0) {
+        return *this;
+    }
+
+    if (by < 64) {
+        bottom >>= by;
+        const auto shift_down = top << (64 - by);
+        bottom |= shift_down;
+        top >>= by;
+    } else {
+        bottom = top;
+        bottom >>= (by - 64);
+        top = 0;
+    }
+
+    return *this;
+}
+
+UInt128& UInt128::operator+=(uint64_t rhs) noexcept {
+    // bottom + lhs > uint64::max
+    if (bottom > std::numeric_limits<uint64_t>::max() - rhs)
+    {
+            top += 1;
+    }
+    bottom += rhs;
+    return *this;
+}
+
+}