[libc] Fix undefined behavior in UInt<>::shift_right.

[lntue]

Summary

Fix undefined behavior of left-shifting uint64_t by 64 in
UInt<>::shift_right implementation.

[michaelrj]

libc/test/src/__support/uint_test.cpp

516

is there a reason that these tests are changed?

[lntue]

libc/test/src/__support/uint_test.cpp

516

Those were the correct bounds of the tests. Previously these tests failed with the correct bounds, and it turns out because of the undefined behavior in the shift function that is fixed in this patch.

[michaelrj]

libc/test/src/__support/uint_test.cpp

516

SGTM

libc/src/__support/UInt.h

#endif                           // __SIZEOF_INT128__
   }
 
   constexpr UInt<Bits> &operator<<=(size_t s) {
     shift_left(s);
     return *this;
   }
 
   constexpr void shift_right(size_t s) {
+#ifdef __SIZEOF_INT128__
+    if constexpr (Bits == 128) {
+      // Use builtin 128 bits if available;
+      if (s >= 128) {
+        val[0] = 0;
+        val[1] = 0;
+        return;
+      }
+      __uint128_t tmp = __uint128_t(val[0]) + (__uint128_t(val[1]) << 64);
+      tmp >>= s;
+      val[0] = uint64_t(tmp);
+      val[1] = uint64_t(tmp >> 64);
+      return;
+    }
+#endif // __SIZEOF_INT128__
+
     const size_t drop = s / 64;  // Number of words to drop
     const size_t shift = s % 64; // Bit shift in the remaining words.
 
     size_t i = 0;
 
     if (drop < WordCount) {
-      size_t j = drop;
-      for (; j < WordCount - 1; ++i, ++j) {
+      if (shift > 0) {
+        for (size_t j = drop; j < WordCount - 1; ++i, ++j) {
           val[i] = (val[j] >> shift) | (val[j + 1] << (64 - shift));
         }
-      val[i] = val[j] >> shift;
+        val[i] = val[WordCount - 1] >> shift;
         ++i;
+      } else {
+        for (size_t j = drop; j < WordCount; ++i, ++j) {
+          val[i] = val[j];
+        }
+      }
     }
 
     for (; i < WordCount; ++i) {
       val[i] = 0;
     }
   }
 
   constexpr UInt<Bits> operator>>(size_t s) const {

libc/test/src/__support/uint_test.cpp

TEST(LlvmLibcUIntClassTest, ShiftRightTests) {
   EXPECT_EQ((val2 >> 96), result4);
 
   LL_UInt128 result5({0x0000000001234567, 0});
   EXPECT_EQ((val2 >> 100), result5);
 
   LL_UInt128 result6({0, 0});
   EXPECT_EQ((val2 >> 128), result6);
   EXPECT_EQ((val2 >> 256), result6);
+
+  LL_UInt128 v1({0x1111222233334444, 0xaaaabbbbccccdddd});
+  LL_UInt128 r1({0xaaaabbbbccccdddd, 0});
+  EXPECT_EQ((v1 >> 64), r1);
+
+  LL_UInt192 v2({0x1111222233334444, 0x5555666677778888, 0xaaaabbbbccccdddd});
+  LL_UInt192 r2({0x5555666677778888, 0xaaaabbbbccccdddd, 0});
+  LL_UInt192 r3({0xaaaabbbbccccdddd, 0, 0});
+  EXPECT_EQ((v2 >> 64), r2);
+  EXPECT_EQ((v2 >> 128), r3);
+  EXPECT_EQ((r2 >> 64), r3);
 }
 
 TEST(LlvmLibcUIntClassTest, AndTests) {
   LL_UInt128 base({0xffff00000000ffff, 0xffffffff00000000});
   LL_UInt128 val128({0xf0f0f0f00f0f0f0f, 0xff00ff0000ff00ff});
   uint64_t val64 = 0xf0f0f0f00f0f0f0f;
   int val32 = 0x0f0f0f0f;
   LL_UInt128 result128({0xf0f0000000000f0f, 0xff00ff0000000000});
do {                                                                         \
     LL_UInt##Bits hi = a.quick_mul_hi(a);                                      \
     LL_UInt##Bits trunc = static_cast<LL_UInt##Bits>(a.ful_mul(a) >> Bits);    \
     uint64_t overflow = trunc.sub(hi);                                         \
     EXPECT_EQ(overflow, uint64_t(0));                                          \
     EXPECT_LE(uint64_t(trunc), uint64_t(Error));                               \
   } while (0)
 
 TEST(LlvmLibcUIntClassTest, QuickMulHiTests) {
-  // TODO(lntue): Investigate / Analyze the error bounds for other rounding
-  // modes.  It the error bounds seems to be able to reach to WordCount instead
-  // of WordCount - 1 in the CI environment.
-  TEST_QUICK_MUL_HI(128, 2);
-  TEST_QUICK_MUL_HI(192, 3);
-  TEST_QUICK_MUL_HI(256, 4);
-  TEST_QUICK_MUL_HI(512, 8);
+  TEST_QUICK_MUL_HI(128, 1);
+  TEST_QUICK_MUL_HI(192, 2);
+  TEST_QUICK_MUL_HI(256, 3);
+  TEST_QUICK_MUL_HI(512, 7);
 }