[libc] add division, modulo, and power to UInt

[michaelrj]

Summary

This adds division and power implementations to UInt. Modulo and
division are handled by the same function. These are necessary for some
higher order mathematics, often involving large floating point numbers.

[sivachandra]

libc/src/__support/CPP/UInt.h

41 ↗

(On Diff #453822)

Not sure if there is a need to initialize from a bigger array. If not, can we restrict this constructor with enable_if?

42 ↗

(On Diff #453822)

Is the ternary operation correct?

81 ↗

(On Diff #453822)

Instead of a static_assert, can we use enable_if to restrict this overload?

279 ↗

(On Diff #453822)

cpp::optional?

283 ↗

(On Diff #453822)

Naming style.

286–287 ↗

(On Diff #453822)

This expression is a bit complicated to parse. Can you put it in a lambda function?

[lntue]

libc/src/__support/CPP/UInt.h

41 ↗

(On Diff #453822)

I think a better option that you're looking for is an implicit constructors / assignment from UInt<M> to UInt<N> with M <= N

286–287 ↗

(On Diff #453822)

Will it be easier if we implement clz for UInt<N>? So that we can just make a single shift?

[michaelrj]

Address comments and add mod and exp functions. Still need to add tests for those last two.

libc/src/__support/CPP/UInt.h

41 ↗

(On Diff #453822)

Re: sivachandra, we can't use enable_if here because typetraits.h depends on UInt.h.
Re: lntue: I've added that as well, since it's also useful, but I need the ability to initialize from a C array as well.

42 ↗

(On Diff #453822)

oops, flipped.

81 ↗

(On Diff #453822)

No. TypeTraits depends on UInt, so UInt can't use anything from TypeTraits. This includes enable_if.

[michaelrj]

fix missing dereference in modulo

[sivachandra]

libc/src/__support/CPP/UInt.h

236 ↗

(On Diff #454620)

What is the use case of detecting the overflow?

293 ↗

(On Diff #454620)

Should we implement operator==(uint64_t) to make this cleaner like: other == uint64_t(1)?

297 ↗

(On Diff #454620)

You should be able to do return cpp::nullopt;

338 ↗

(On Diff #454620)

Yes - we have https://github.com/llvm/llvm-project/blob/main/libc/src/__support/FPUtil/builtin_wrappers.h.

libc/test/src/__support/uint128_test.cpp

160

We should include them in this patch? Also, if multiplication overflow is required, we should test for that also?

[sivachandra]

libc/src/__support/CPP/UInt.h

41 ↗

(On Diff #453822)

Considering that we are moving to make the CPP directory a strict subset of the C++ standard library, we should move the is_integral specialization for UInt to this file or may be to UInt128.h.

[michaelrj]

rebase, add tests for mod and exp, general cleanup

[michaelrj]

libc/src/__support/CPP/UInt.h

236 ↗

(On Diff #454620)

I used it in my initial division implementation, but I don't have a use for it now, so I've removed it.

293 ↗

(On Diff #454620)

It appears that's unnecessary. I just assumed it'd need the explicit typing, but it will apparently get promoted implicitly just fine.

338 ↗

(On Diff #454620)

that's in FPUtil, which depends on UInt. I will move that out in a followup patch, since it doesn't need to be in FPUtil.

[sivachandra]

OK from my side. Please wait for @lntue.

[lntue]

libc/src/__support/UInt.h

252

I think the conventional name for this function is pown or pow_n. exp name is kind of reserved for e^x function.

261

Can this be replaced with cur_power *= cur_power?

320–325

Since you already included builtin_wrappers.h here, this part can be reduced to

leading_zeroes += fputil::unsafe_clz(val[i-1]);

[michaelrj]

address comments

[michaelrj]

add bazel changes

libc/src/__support/UInt.h

 //===-- A class to manipulate wide integers. --------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIBC_UTILS_UINT_H
 #define LLVM_LIBC_UTILS_UINT_H
 
 #include "src/__support/CPP/array.h"
 #include "src/__support/CPP/limits.h"
+#include "src/__support/CPP/optional.h"
 #include "src/__support/CPP/type_traits.h"
+#include "src/__support/FPUtil/builtin_wrappers.h"
 
 #include <stddef.h> // For size_t
 #include <stdint.h>
 
 namespace __llvm_libc::cpp {
 
 template <size_t Bits> class UInt {
 

 public:
   constexpr UInt() {}
 
   constexpr UInt(const UInt<Bits> &other) {
     for (size_t i = 0; i < WordCount; ++i)
       val[i] = other.val[i];
   }
 
+  template <size_t OtherBits> constexpr UInt(const UInt<OtherBits> &other) {
+    if (OtherBits >= Bits) {
+      for (size_t i = 0; i < WordCount; ++i)
+        val[i] = other[i];
+    } else {
+      size_t i = 0;
+      for (; i < OtherBits / 64; ++i)
+        val[i] = other[i];
+      for (; i < WordCount; ++i)
+        val[i] = 0;
+    }
+  }
+
+  // Construct a UInt from a C array.
+  template <size_t N, enable_if_t<N <= WordCount, int> = 0>
+  constexpr UInt(const uint64_t (&nums)[N]) {
+    size_t min_wordcount = N < WordCount ? N : WordCount;
+    size_t i = 0;
+    for (; i < min_wordcount; ++i)
+      val[i] = nums[i];
+
+    // If nums doesn't completely fill val, then fill the rest with zeroes.
+    for (; i < WordCount; ++i)
+      val[i] = 0;
+  }
+
   // Initialize the first word to |v| and the rest to 0.
   constexpr UInt(uint64_t v) {
     val[0] = v;
     for (size_t i = 1; i < WordCount; ++i) {
       val[i] = 0;
     }
   }
   constexpr explicit UInt(const cpp::array<uint64_t, WordCount> &words) {
for (size_t i = 0; i < WordCount; ++i) {
       val[i] = r1[i];
     }
     return r1[WordCount];
   }
 
   constexpr UInt<Bits> operator*(const UInt<Bits> &other) const {
     UInt<Bits> result(0);
     for (size_t i = 0; i < WordCount; ++i) {
+      if (other[i] == 0)
+        continue;
       UInt<Bits> row_result(*this);
       row_result.mul(other[i]);
       row_result.shift_left(64 * i);
       result = result + row_result;
     }
     return result;
   }
 
+  // exp takes a power and sets this to its starting value to that power. Zero
+  // to the zeroth power returns 1.
+  constexpr void exp(uint64_t power) {
+    UInt<Bits> result = 1;
+    UInt<Bits> cur_power = *this;
+
+    while (power > 0) {
+      if ((power % 2) > 0) {
+        result = result * cur_power;
+      }
+      power = power >> 1;
+      cur_power = cur_power * cur_power;
+    }
+    *this = result;
+  }
+
+  // div takes another UInt of the same size and divides this by it. The value
+  // of this will be set to the quotient, and the return value is the remainder.
+  constexpr optional<UInt<Bits>> div(const UInt<Bits> &other) {
+    UInt<Bits> remainder(0);
+    if (*this < other) {
+      remainder = *this;
+      *this = UInt<Bits>(0);
+      return remainder;
+    }
+    if (other == 1) {
+      return remainder;
+    }
+    if (other == 0) {
+      return nullopt;
+    }
+
+    UInt<Bits> quotient(0);
+    UInt<Bits> subtractor = other;
+    int cur_bit = subtractor.clz() - this->clz();
+    subtractor.shift_left(cur_bit);
+
+    for (; cur_bit >= 0 && *this > 0; --cur_bit, subtractor.shift_right(1)) {
+      if (*this >= subtractor) {
+        this->sub(subtractor);
+        quotient = quotient | (UInt<Bits>(1) << cur_bit);
+      }
+    }
+    remainder = *this;
+    *this = quotient;
+    return remainder;
+  }
+
+  constexpr UInt<Bits> operator/(const UInt<Bits> &other) const {
+    UInt<Bits> result(*this);
+    result.div(other);
+    return result;
+  }
+
+  constexpr UInt<Bits> operator%(const UInt<Bits> &other) const {
+    UInt<Bits> result(*this);
+    return *result.div(other);
+  }
+
   constexpr UInt<Bits> &operator*=(const UInt<Bits> &other) {
     *this = *this * other;
     return *this;
   }
 
+  constexpr uint64_t clz() {
+    uint64_t leading_zeroes = 0;
+    for (size_t i = WordCount; i > 0; --i) {
+      if (val[i - 1] == 0) {
+        leading_zeroes += sizeof(uint64_t) * 8;
+      } else {
+        // TODO(michaelrj): use builtins?
+        uint64_t num = val[i - 1];
+        while (num < (uint64_t(1) << ((sizeof(uint64_t) * 8) - 1))) {
+          num <<= 1;
+          ++leading_zeroes;
+        }
+        break;
+      }
+    }
+    return leading_zeroes;
+  }
+
   constexpr void shift_left(size_t s) {
     const size_t drop = s / 64;  // Number of words to drop
     const size_t shift = s % 64; // Bits to shift in the remaining words.
     const uint64_t mask = ((uint64_t(1) << shift) - 1) << (64 - shift);
 
     for (size_t i = WordCount; drop > 0 && i > 0; --i) {
       if (i > drop)
         val[i - 1] = val[i - drop - 1];

libc/test/src/__support/CMakeLists.txt

 add_libc_unittest(
   uint128_test
   SUITE
     libc_support_unittests
   SRCS
     uint128_test.cpp
   DEPENDS
     libc.src.__support.uint
+    libc.src.__support.CPP.optional
 )
 
 add_libc_unittest(
   fixedvector_test
   SUITE
     libc_support_unittests
   SRCS
     fixedvector_test.cpp

libc/test/src/__support/uint128_test.cpp

 //===-- Unittests for the 128 bit integer class ---------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
+#include "src/__support/CPP/optional.h"
 #include "src/__support/UInt.h"
 
 #include "utils/UnitTest/Test.h"
 
 // We want to test __llvm_libc::cpp::UInt<128> explicitly. So, for convenience,
 // we use a sugar which does not conflict with the UInt128 type which can
 // resolve to __uint128_t if the platform has it.
 using LL_UInt128 = __llvm_libc::cpp::UInt<128>;
TEST(LlvmLibcUInt128ClassTest, MultiplicationTests) {
   // 0x7fffffffffffffffffffffffffffffff3a4f32d17f40d08f917cf11d1e039c50
   LL_UInt128 val9({0x01D762422C946590, 0x9F4F2726179A2245});
   LL_UInt128 val10({0x3792F412CB06794D, 0xCDB02555653131B6});
   LL_UInt128 result5({0x917cf11d1e039c50, 0x3a4f32d17f40d08f});
   EXPECT_EQ((val9 * val10), result5);
   EXPECT_EQ((val9 * val10), (val10 * val9));
 }
 
+TEST(LlvmLibcUInt128ClassTest, DivisionTests) {
+  LL_UInt128 val1({10, 0});
+  LL_UInt128 val2({5, 0});
+  LL_UInt128 result1({2, 0});
+  EXPECT_EQ((val1 / val2), result1);
+  EXPECT_EQ((val1 / result1), val2);
+
+  // Check that the division works accross the whole number
+  LL_UInt128 val3({0xffffffffffffffff, 0xffffffffffffffff});
+  LL_UInt128 val4({0xf, 0});
+  LL_UInt128 result2({0x1111111111111111, 0x1111111111111111});
+  EXPECT_EQ((val3 / val4), result2);
+  EXPECT_EQ((val3 / result2), val4);
+
+  // Check that division doesn't reorder the bits.
+  LL_UInt128 val5({0x26ae048cea62c840, 0x02468aceeca86420});
+  LL_UInt128 val6({2, 0});
+  LL_UInt128 result3({0x1357024675316420, 0x0123456776543210});
+  EXPECT_EQ((val5 / val6), result3);
+  EXPECT_EQ((val5 / result3), val6);
+
+  // Make sure that division handles inexact results correctly.
+  LL_UInt128 val7({1001, 0});
+  LL_UInt128 val8({10, 0});
+  LL_UInt128 result4({100, 0});
+  EXPECT_EQ((val7 / val8), result4);
+  EXPECT_EQ((val7 / result4), val8);
+
+  // Make sure that division handles divisors of one correctly.
+  LL_UInt128 val9({0x1234567812345678, 0x9abcdef09abcdef0});
+  LL_UInt128 val10({1, 0});
+  LL_UInt128 result5({0x1234567812345678, 0x9abcdef09abcdef0});
+  EXPECT_EQ((val9 / val10), result5);
+  EXPECT_EQ((val9 / result5), val10);
+
+  // Make sure that division handles results of slightly more than 1 correctly.
+  LL_UInt128 val11({1050, 0});
+  LL_UInt128 val12({1030, 0});
+  LL_UInt128 result6({1, 0});
+  EXPECT_EQ((val11 / val12), result6);
+
+  // Make sure that division handles dividing by zero correctly.
+  LL_UInt128 val13({1234, 0});
+  LL_UInt128 val14({0, 0});
+  EXPECT_FALSE(val13.div(val14).has_value());
+}
+
+TEST(LlvmLibcUInt128ClassTest, ModuloTests) {
+  LL_UInt128 val1({10, 0});
+  LL_UInt128 val2({5, 0});
+  LL_UInt128 result1({0, 0});
+  EXPECT_EQ((val1 % val2), result1);
+
+  LL_UInt128 val3({101, 0});
+  LL_UInt128 val4({10, 0});
+  LL_UInt128 result2({1, 0});
+  EXPECT_EQ((val3 % val4), result2);
+
+  LL_UInt128 val5({10000001, 0});
+  LL_UInt128 val6({10, 0});
+  LL_UInt128 result3({1, 0});
+  EXPECT_EQ((val5 % val6), result3);
+
+  LL_UInt128 val7({12345, 10});
+  LL_UInt128 val8({0, 1});
+  LL_UInt128 result4({12345, 0});
+  EXPECT_EQ((val7 % val8), result4);
+
+  LL_UInt128 val9({12345, 10});
+  LL_UInt128 val10({0, 11});
+  LL_UInt128 result5({12345, 10});
+  EXPECT_EQ((val9 % val10), result5);
+
+  LL_UInt128 val11({10, 10});
+  LL_UInt128 val12({10, 10});
+  LL_UInt128 result6({0, 0});
+  EXPECT_EQ((val11 % val12), result6);
+
+  LL_UInt128 val13({12345, 0});
+  LL_UInt128 val14({1, 0});
+  LL_UInt128 result7({0, 0});
+  EXPECT_EQ((val13 % val14), result7);
+
+  LL_UInt128 val15({0xffffffffffffffff, 0xffffffffffffffff});
+  LL_UInt128 val16({0x1111111111111111, 0x111111111111111});
+  LL_UInt128 result8({0xf, 0});
+  EXPECT_EQ((val15 % val16), result8);
+
+  LL_UInt128 val17({5076944270305263619, 54210108624}); // (10 ^ 30) + 3
+  LL_UInt128 val18({10, 0});
+  LL_UInt128 result9({3, 0});
+  EXPECT_EQ((val17 % val18), result9);
+}
+
+TEST(LlvmLibcUInt128ClassTest, ExponentTests) {
+  LL_UInt128 val1({10, 0});
+  val1.exp(30);
+  LL_UInt128 result1({5076944270305263616, 54210108624}); // (10 ^ 30)
+  EXPECT_EQ(val1, result1);
+
+  LL_UInt128 val2({1, 0});
+  val2.exp(10);
+  LL_UInt128 result2({1, 0});
+  EXPECT_EQ(val2, result2);
+
+  LL_UInt128 val3({0, 0});
+  val3.exp(10);
+  LL_UInt128 result3({0, 0});
+  EXPECT_EQ(val3, result3);
+
+  LL_UInt128 val4({10, 0});
+  val4.exp(0);
+  LL_UInt128 result4({1, 0});
+  EXPECT_EQ(val4, result4);
+
+  // Test zero to the zero. Currently it returns 1, since that's the easiest
+  // result.
+  LL_UInt128 val5({0, 0});
+  val5.exp(0);
+  LL_UInt128 result5({1, 0});
+  EXPECT_EQ(val5, result5);
+
+  // Test a number that overflows. 100 ^ 20 is larger than 2 ^ 128.
+  LL_UInt128 val6({100, 0});
+  val6.exp(20);
+  LL_UInt128 result6({0xb9f5610000000000, 0x6329f1c35ca4bfab});
+  EXPECT_EQ(val6, result6);
+
+  // Test that both halves of the number are being used.
+  LL_UInt128 val7({1, 1});
+  val7.exp(2);
+  LL_UInt128 result7({1, 2});
+  EXPECT_EQ(val7, result7);
+
+  LL_UInt128 val_pow_two;
+  LL_UInt128 result_pow_two;
+  for (size_t i = 0; i < 128; ++i) {
+    val_pow_two = 2;
+    val_pow_two.exp(i);
+    result_pow_two = 1;
+    result_pow_two = result_pow_two << i;
+    EXPECT_EQ(val_pow_two, result_pow_two);
+  }
+}
+
 TEST(LlvmLibcUInt128ClassTest, ShiftLeftTests) {
   LL_UInt128 val1(0x0123456789abcdef);
   LL_UInt128 result1(0x123456789abcdef0);
   EXPECT_EQ((val1 << 4), result1);
 
   LL_UInt128 val2({0x13579bdf02468ace, 0x123456789abcdef0});
   LL_UInt128 result2({0x02468ace00000000, 0x9abcdef013579bdf});
   EXPECT_EQ((val2 << 32), result2);