pitrou commented on a change in pull request #8475:
URL: https://github.com/apache/arrow/pull/8475#discussion_r509370051
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -254,67 +254,125 @@ BasicDecimal128& BasicDecimal128::operator>>=(uint32_t
bits) {
namespace {
-// TODO: Remove this guard once it's used by BasicDecimal256
-#ifndef ARROW_USE_NATIVE_INT128
-// This method losslessly multiplies x and y into a 128 bit unsigned integer
-// whose high bits will be stored in hi and low bits in lo.
-void ExtendAndMultiplyUint64(uint64_t x, uint64_t y, uint64_t* hi, uint64_t*
lo) {
+// Convenience wrapper type over 128 bit unsigned integers. We opt not to
+// replace the uint128_t type in int128_internal.h because it would require
+// significantly more implementation work to be done. This class merely
+// provides the minimum necessary set of functions to perform 128+ bit
+// multiplication operations when there may or may not be native support.
#ifdef ARROW_USE_NATIVE_INT128
- const __uint128_t r = static_cast<__uint128_t>(x) * y;
- *lo = r & kInt64Mask;
- *hi = r >> 64;
+struct uint128_t {
+ uint128_t() {}
+ uint128_t(uint64_t hi, uint64_t lo) : val_((static_cast<__uint128_t>(hi) <<
64) | lo) {}
+ explicit uint128_t(const BasicDecimal128& decimal) {
+ val_ = (static_cast<__uint128_t>(decimal.high_bits()) << 64) |
decimal.low_bits();
+ }
+
+ uint64_t hi() { return val_ >> 64; }
+ uint64_t lo() { return val_ & kInt64Mask; }
+
+ uint128_t& operator+=(const uint128_t& other) {
+ val_ += other.val_;
+ return *this;
+ }
+
+ uint128_t& operator*=(const uint128_t& other) {
+ val_ *= other.val_;
+ return *this;
+ }
+
+ __uint128_t val_;
+};
+
#else
- // If we can't use a native fallback, perform multiplication
+// Multiply two 64 bit word components into a 128 bit result, with high bits
+// stored in hi and low bits in lo.
+inline void ExtendAndMultiply(uint64_t x, uint64_t y, uint64_t* hi, uint64_t*
lo) {
+ // Perform multiplication on two 64 bit words x and y into a 128 bit result
// by splitting up x and y into 32 bit high/low bit components,
// allowing us to represent the multiplication as
// x * y = x_lo * y_lo + x_hi * y_lo * 2^32 + y_hi * x_lo * 2^32
- // + x_hi * y_hi * 2^64.
+ // + x_hi * y_hi * 2^64
//
- // Now, consider the final output as lo_lo || lo_hi || hi_lo || hi_hi.
+ // Now, consider the final output as lo_lo || lo_hi || hi_lo || hi_hi
// Therefore,
// lo_lo is (x_lo * y_lo)_lo,
// lo_hi is ((x_lo * y_lo)_hi + (x_hi * y_lo)_lo + (x_lo * y_hi)_lo)_lo,
// hi_lo is ((x_hi * y_hi)_lo + (x_hi * y_lo)_hi + (x_lo * y_hi)_hi)_hi,
// hi_hi is (x_hi * y_hi)_hi
- const uint64_t x_lo = x & kIntMask;
- const uint64_t y_lo = y & kIntMask;
+ const uint64_t x_lo = x & kInt32Mask;
+ const uint64_t y_lo = y & kInt32Mask;
const uint64_t x_hi = x >> 32;
const uint64_t y_hi = y >> 32;
const uint64_t t = x_lo * y_lo;
- const uint64_t t_lo = t & kIntMask;
+ const uint64_t t_lo = t & kInt32Mask;
const uint64_t t_hi = t >> 32;
const uint64_t u = x_hi * y_lo + t_hi;
- const uint64_t u_lo = u & kIntMask;
+ const uint64_t u_lo = u & kInt32Mask;
const uint64_t u_hi = u >> 32;
const uint64_t v = x_lo * y_hi + u_lo;
const uint64_t v_hi = v >> 32;
*hi = x_hi * y_hi + u_hi + v_hi;
- *lo = (v << 32) | t_lo;
-#endif
+ *lo = (v << 32) + t_lo;
}
-#endif
-void MultiplyUint128(uint64_t x_hi, uint64_t x_lo, uint64_t y_hi, uint64_t
y_lo,
- uint64_t* hi, uint64_t* lo) {
-#ifdef ARROW_USE_NATIVE_INT128
- const __uint128_t x = (static_cast<__uint128_t>(x_hi) << 64) | x_lo;
- const __uint128_t y = (static_cast<__uint128_t>(y_hi) << 64) | y_lo;
- const __uint128_t r = x * y;
- *lo = r & kInt64Mask;
- *hi = r >> 64;
-#else
- // To perform 128 bit multiplication without a native fallback
- // we first perform lossless 64 bit multiplication of the low
- // bits, and then add x_hi * y_lo and x_lo * y_hi to the high
- // bits. Note that we can skip adding x_hi * y_hi because it
- // always will be over 128 bits.
- ExtendAndMultiplyUint64(x_lo, y_lo, hi, lo);
- *hi += (x_hi * y_lo) + (x_lo * y_hi);
+struct uint128_t {
+ uint128_t() {}
+ uint128_t(uint64_t hi, uint64_t lo) : hi_(hi), lo_(lo) {}
+ explicit uint128_t(const BasicDecimal128& decimal) {
+ hi_ = decimal.high_bits();
+ lo_ = decimal.low_bits();
+ }
+
+ uint64_t hi() const { return hi_; }
+ uint64_t lo() const { return lo_; }
+
+ uint128_t& operator+=(const uint128_t& other) {
+ // To deduce the carry bit, we perform "65 bit" addition on the low bits
and
+ // seeing if the resulting high bit is 1. This is accomplished by shifting
the
+ // low bits to the right by 1 (chopping off the lowest bit), then adding 1
if the
+ // result of adding the two chopped bits would have produced a carry.
+ uint64_t carry = (((lo_ & other.lo_) & 1) + (lo_ >> 1) + (other.lo_ >> 1))
>> 63;
+ hi_ += other.hi_ + carry;
+ lo_ += other.lo_;
+ return *this;
+ }
+
+ uint128_t& operator*=(const uint128_t& other) {
+ uint128_t r;
+ ExtendAndMultiply(lo_, other.lo_, &r.hi_, &r.lo_);
+ r.hi_ += (hi_ * other.lo_) + (lo_ * other.hi_);
+ *this = r;
+ return *this;
+ }
+
+ uint64_t hi_;
+ uint64_t lo_;
+};
#endif
+
+// Multiplies two N * 64 bit unsigned integer types, represented by a uint64_t
+// array into a same sized output. Elements in the array should be in
+// little endian order, and output will be the same. Overflow in multiplication
+// will result in the lower N * 64 bits of the result being set.
+template <int N>
+inline void MultiplyUnsignedArray(const std::array<uint64_t, N>& lh,
+ const std::array<uint64_t, N>& rh,
+ std::array<uint64_t, N>* result) {
+ for (int j = 0; j < N; ++j) {
+ uint64_t carry = 0;
+ for (int i = 0; i < N - j; ++i) {
+ uint128_t tmp(lh[i]);
+ tmp *= uint128_t(rh[j]);
Review comment:
I may be misunderstanding, but I don't see a `uint128_t(uint64_t)`
constructor?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
[email protected]
