Function ExtendAndMultiply

cpp/src/arrow/util/basic_decimal.cc:533–564

Multiply two 64 bit word components into a 128 bit result, with high bits stored in hi and low bits in lo.

// 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
  //
  // 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 & 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 & kInt32Mask;
  const uint64_t t_hi = t >> 32;

  const uint64_t u = x_hi * y_lo + t_hi;
  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;
}

struct uint128_t {
  uint128_t() {}