// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License.

#ifndef IMPALA_RUNTIME_DECIMAL_VALUE_INLINE_H
#define IMPALA_RUNTIME_DECIMAL_VALUE_INLINE_H

#include "runtime/decimal-value.h"

#include <cmath>
#include <functional>
#include <iomanip>
#include <limits>
#include <ostream>
#include <sstream>

#include "common/logging.h"
#include "util/arithmetic-util.h"
#include "util/bit-util.h"
#include "util/decimal-util.h"
#include "util/hash-util.h"

namespace impala {

template<typename T>
inline DecimalValue<T> DecimalValue<T>::FromDouble(int precision, int scale, double d,
    bool round, bool* overflow) {

  // Multiply the double by the scale.
  // Unfortunately, this conversion is not exact, and there is a loss of precision.
  // The error starts around 1.0e23 and can take either positive or negative values.
  // This means the multiplication can cause an unwanted decimal overflow.
  d *= DecimalUtil::GetScaleMultiplier<double>(scale);

  // Decimal V2 behavior
  // TODO: IMPALA-4924: remove DECIMAL V1 code
  if (round) d = std::round(d);

  const T max_value = DecimalUtil::GetScaleMultiplier<T>(precision);
  DCHECK(max_value > 0);  // no DCHECK_GT because of int128_t
  if (UNLIKELY(std::isnan(d)) || UNLIKELY(std::fabs(d) >= max_value)) {
    *overflow = true;
    return DecimalValue();
  }

  // Return the rounded or truncated integer part.
  return DecimalValue(static_cast<T>(d));
}

template <typename T>
inline DecimalValue<T> DecimalValue<T>::FromTColumnValue(const TColumnValue& tvalue) {
  T value = 0;
  memcpy(&value, tvalue.decimal_val.c_str(), tvalue.decimal_val.length());
  return DecimalValue<T>(value);
}

template<typename T>
inline DecimalValue<T> DecimalValue<T>::FromInt(int precision, int scale, int64_t d,
    bool* overflow) {
  // Check overflow. For scale 3, the max value is 10^3 - 1 = 999.
  T max_value = DecimalUtil::GetScaleMultiplier<T>(precision - scale);
  if (abs(d) >= max_value) {
    *overflow = true;
    return DecimalValue();
  }
  return DecimalValue(DecimalUtil::MultiplyByScale<T>(d, scale, false));
}

template<typename T>
inline int DecimalValue<T>::Compare(const DecimalValue& other) const {
  T x = value();
  T y = other.value();
  if (x == y) return 0;
  if (x < y) return -1;
  return 1;
}

template<typename T>
inline const T DecimalValue<T>::whole_part(int scale) const {
  return value() / DecimalUtil::GetScaleMultiplier<T>(scale);
}

template<typename T>
inline const T DecimalValue<T>::fractional_part(int scale) const {
  return abs(value()) % DecimalUtil::GetScaleMultiplier<T>(scale);
}

// Note: this expects RESULT_T to be a UDF AnyVal subclass which defines
// RESULT_T::underlying_type_t to be the representative type
template<typename T>
template<typename RESULT_T>
inline typename RESULT_T::underlying_type_t DecimalValue<T>::ToInt(int scale,
    bool* overflow) const {
  const T divisor = DecimalUtil::GetScaleMultiplier<T>(scale);
  const T v = value();
  T result;
  if (divisor == 1) {
    result = v;
  } else {
    result = v / divisor;
    const T remainder = v % divisor;
    // Divisor is always a multiple of 2, so no loss of precision when shifting down
    DCHECK(divisor % 2 == 0);  // No DCHECK_EQ as this is possibly an int128_t
    // N.B. also - no std::abs for int128_t
    if (abs(remainder) >= divisor >> 1) {
      // Round away from zero.
      // Bias at zero must be corrected by sign of dividend.
      result += BitUtil::Sign(v);
    }
  }
  *overflow |=
      result > std::numeric_limits<typename RESULT_T::underlying_type_t>::max() ||
      result < std::numeric_limits<typename RESULT_T::underlying_type_t>::min();
  return result;
}

template<typename T>
inline DecimalValue<T> DecimalValue<T>::ScaleTo(int src_scale, int dst_scale,
    int dst_precision, bool* overflow) const {
  int delta_scale = src_scale - dst_scale;
  T result = value();
  T max_value = DecimalUtil::GetScaleMultiplier<T>(dst_precision);
  if (delta_scale >= 0) {
    if (delta_scale != 0) result /= DecimalUtil::GetScaleMultiplier<T>(delta_scale);
    // Even if we are decreasing the absolute unscaled value, we can still overflow.
    // This path is also used to convert between precisions so for example, converting
    // from 100 as decimal(3,0) to decimal(2,0) should be considered an overflow.
    *overflow |= abs(result) >= max_value;
  } else if (delta_scale < 0) {
    T mult = DecimalUtil::GetScaleMultiplier<T>(-delta_scale);
    *overflow |= abs(result) >= max_value / mult;
    result = ArithmeticUtil::AsUnsigned<std::multiplies>(result, mult);
  }
  return DecimalValue(result);
}

namespace detail {

// Suppose we have a number that requires x bits to be represented and we scale it up by
// 10^scale_by. Let's say now y bits are required to represent it. This function returns
// the maximum possible y - x for a given 'scale_by'.
inline int MaxBitsRequiredIncreaseAfterScaling(int scale_by) {
  // We rely on the following formula:
  // bits_required(x * 10^y) <= bits_required(x) + floor(log2(10^y)) + 1
  // We precompute floor(log2(10^x)) + 1 for x = 0, 1, 2...75, 76
  DCHECK_GE(scale_by, 0);
  DCHECK_LE(scale_by, 76);
  static const int floor_log2_plus_one[] = {
      0,   4,   7,   10,  14,  17,  20,  24,  27,  30,
      34,  37,  40,  44,  47,  50,  54,  57,  60,  64,
      67,  70,  74,  77,  80,  84,  87,  90,  94,  97,
      100, 103, 107, 110, 113, 117, 120, 123, 127, 130,
      133, 137, 140, 143, 147, 150, 153, 157, 160, 163,
      167, 170, 173, 177, 180, 183, 187, 190, 193, 196,
      200, 203, 206, 210, 213, 216, 220, 223, 226, 230,
      233, 236, 240, 243, 246, 250, 253 };
  return floor_log2_plus_one[scale_by];
}

// If we have a number with 'num_lz' leading zeros, and we scale it up by 10^scale_by,
// this function returns the minimum number of leading zeros the result can have.
inline int MinLeadingZerosAfterScaling(int num_lz, int scale_by) {
  DCHECK_GE(scale_by, 0);
  DCHECK_LE(scale_by, 76);
  int result = num_lz - MaxBitsRequiredIncreaseAfterScaling(scale_by);
  return result;
}

// Returns the maximum possible number of bits required to represent num * 10^scale_by.
inline int MaxBitsRequiredAfterScaling(int128_t num, int scale_by) {
  // TODO: We are doing a lot of these abs() operations on int128_t in many places in our
  // decimal math code. It might make sense to do this upfront, then do the calculations
  // in unsigned math and adjust the sign at the end.
  int num_occupied = 128 - BitUtil::CountLeadingZeros<int128_t>(abs(num));
  DCHECK_GE(scale_by, 0);
  DCHECK_LE(scale_by, 76);
  return num_occupied + MaxBitsRequiredIncreaseAfterScaling(scale_by);
}

// Returns the minimum number of leading zero x or y would have after one of them gets
// scaled up to match the scale of the other one.
template<typename T>
inline int MinLeadingZeros(T x, int x_scale, T y, int y_scale) {
  int x_lz = BitUtil::CountLeadingZeros<T>(abs(x));
  int y_lz = BitUtil::CountLeadingZeros<T>(abs(y));
  if (x_scale < y_scale) {
    x_lz = detail::MinLeadingZerosAfterScaling(x_lz, y_scale - x_scale);
  } else if (x_scale > y_scale) {
    y_lz = detail::MinLeadingZerosAfterScaling(y_lz, x_scale - y_scale);
  }
  return std::min(x_lz, y_lz);
}

// Separates x and y into into fractional and whole parts.
inline void SeparateFractional(int128_t x, int x_scale, int128_t y, int y_scale,
    int128_t* x_left, int128_t* x_right, int128_t* y_left, int128_t* y_right) {
  // The whole part.
  *x_left = x / DecimalUtil::GetScaleMultiplier<int128_t>(x_scale);
  *y_left = y / DecimalUtil::GetScaleMultiplier<int128_t>(y_scale);
  // The fractional part.
  *x_right = x % DecimalUtil::GetScaleMultiplier<int128_t>(x_scale);
  *y_right = y % DecimalUtil::GetScaleMultiplier<int128_t>(y_scale);
  // Scale up the fractional part of the operand with the smaller scale so that
  // the scales match match.
  if (x_scale < y_scale) {
    *x_right *= DecimalUtil::GetScaleMultiplier<int128_t>(y_scale - x_scale);
  } else {
    *y_right *= DecimalUtil::GetScaleMultiplier<int128_t>(x_scale - y_scale);
  }
}

// Adds numbers that are large enough so they can't be added directly. Both
// numbers must be either positive or zero.
inline int128_t AddLarge(int128_t x, int x_scale, int128_t y, int y_scale,
    int result_scale, bool round, bool *overflow) {
  DCHECK(x >= 0 && y >= 0);

  int128_t left, right, x_left, x_right, y_left, y_right;
  SeparateFractional(x, x_scale, y, y_scale, &x_left, &x_right, &y_left, &y_right);
  DCHECK(x_left >= 0 && y_left >= 0 && x_right >= 0 && y_right >=0);

  int max_scale = std::max(x_scale, y_scale);
  int result_scale_decrease = max_scale - result_scale;
  DCHECK(result_scale_decrease >= 0);

  // carry_to_left should be 1 if there is an overflow when adding the fractional parts.
  int carry_to_left = 0;
  if (UNLIKELY(x_right >=
      DecimalUtil::GetScaleMultiplier<int128_t>(max_scale) - y_right)) {
    // Case where adding the fractional parts results in an overflow.
    carry_to_left = 1;
    right = x_right - DecimalUtil::GetScaleMultiplier<int128_t>(max_scale) + y_right;
  } else {
    // Case where adding the fractional parts does not result in an overflow.
    right = x_right + y_right;
  }
  if (result_scale_decrease > 0) {
    right = DecimalUtil::ScaleDownAndRound<int128_t>(
        right, result_scale_decrease, round);
  }
  DCHECK(right >= 0);
  // It is possible that right gets rounded up after scaling down (and it would look like
  // it overflowed). We could handle this case by subtracting 10^result_scale from right
  // (which would make it equal to zero) and adding one to carry_to_left, but
  // it is not necessary, because doing that is equivalent to doing nothing.
  DCHECK(right <= DecimalUtil::GetScaleMultiplier<int128_t>(result_scale));

  *overflow |= x_left > DecimalUtil::MAX_UNSCALED_DECIMAL16 - y_left - carry_to_left;
  left = ArithmeticUtil::AsUnsigned<std::plus>(
      ArithmeticUtil::AsUnsigned<std::plus>(x_left, y_left),
      static_cast<int128_t>(carry_to_left));

  int128_t mult = DecimalUtil::GetScaleMultiplier<int128_t>(result_scale);
  if (UNLIKELY(!*overflow &&
      left > (DecimalUtil::MAX_UNSCALED_DECIMAL16 - right) / mult)) {
    *overflow = true;
  }
  return ArithmeticUtil::AsUnsigned<std::plus>(
      DecimalUtil::SafeMultiply(left, mult, *overflow), right);
}

// Subtracts numbers that are large enough so that we can't subtract directly. Neither
// of the numbers can be zero and one must be positive and the other one negative.
inline int128_t SubtractLarge(int128_t x, int x_scale, int128_t y, int y_scale,
    int result_scale, bool round, bool *overflow) {
  DCHECK(x != 0 && y != 0);
  DCHECK((x > 0) != (y > 0));

  int128_t left, right, x_left, x_right, y_left, y_right;
  SeparateFractional(x, x_scale, y, y_scale, &x_left, &x_right, &y_left, &y_right);

  int max_scale = std::max(x_scale, y_scale);
  int result_scale_decrease = max_scale - result_scale;
  DCHECK_GE(result_scale_decrease, 0);

  left = x_left + y_left;
  right = x_right + y_right;
  // Overflow is not possible because one number is positive and the other one is
  // negative.
  DCHECK(abs(left) <= DecimalUtil::MAX_UNSCALED_DECIMAL16);
  DCHECK(abs(right) <= DecimalUtil::MAX_UNSCALED_DECIMAL16);
  // If the whole and fractional parts have different signs, then we need to make the
  // fractional part have the same sign as the whole part. If either left or right is
  // zero, then nothing needs to be done.
  if (left < 0 && right > 0) {
    left += 1;
    right -= DecimalUtil::GetScaleMultiplier<int128_t>(max_scale);
  } else if (left > 0 && right < 0) {
    left -= 1;
    right += DecimalUtil::GetScaleMultiplier<int128_t>(max_scale);
  }
  // The operation above brought left closer to zero.
  DCHECK(abs(left) <= abs(x_left + y_left));
  if (result_scale_decrease > 0) {
    // At this point, the scale of the fractional part is either x_scale or y_scale,
    // whichever is greater. We scale down the fractional part to result_scale here.
    right = DecimalUtil::ScaleDownAndRound<int128_t>(
        right, result_scale_decrease, round);
  }

  // Check that left and right have the same sign.
  DCHECK(left == 0 || right == 0 || (left > 0) == (right > 0));
  // It is possible that right gets rounded up after scaling down (and it would look like
  // it overflowed). This does not need to be handled in a special way and will result
  // in incrementing the whole part by one.
  DCHECK(abs(right) <= DecimalUtil::GetScaleMultiplier<int128_t>(result_scale));

  int128_t mult = DecimalUtil::GetScaleMultiplier<int128_t>(result_scale);
  if (UNLIKELY(abs(left) > (DecimalUtil::MAX_UNSCALED_DECIMAL16 - abs(right)) / mult)) {
    *overflow = true;
  }
  return DecimalUtil::SafeMultiply(left, mult, *overflow) + right;
}

}

template<typename T>
template<typename RESULT_T>
inline DecimalValue<RESULT_T> DecimalValue<T>::Add(int this_scale,
    const DecimalValue& other, int other_scale, int result_precision, int result_scale,
    bool round, bool* overflow) const {

  if (sizeof(RESULT_T) < 16 || result_precision < 38) {
    // The following check is guaranteed by the frontend.
    DCHECK_EQ(result_scale, std::max(this_scale, other_scale));
    RESULT_T x = 0;
    RESULT_T y = 0;
    AdjustToSameScale(*this, this_scale, other, other_scale, result_precision, &x, &y);
    return DecimalValue<RESULT_T>(x + y);
  }

  // Compute how many leading zeros x and y would have after one of them gets scaled
  // up to match the scale of the other one.
  int min_lz = detail::MinLeadingZeros(
      abs(value()), this_scale, abs(other.value()), other_scale);
  int result_scale_decrease = std::max(
      this_scale - result_scale, other_scale - result_scale);
  DCHECK_GE(result_scale_decrease, 0);

  const int MIN_LZ = 3;
  if (min_lz >= MIN_LZ) {
    // If both numbers have at least MIN_LZ leading zeros, we can add them directly
    // without the risk of overflow.
    // We want the result to have at least 2 leading zeros, which ensures that it fits
    // into the maximum decimal because 2^126 - 1 < 10^38 - 1. If both x and y have at
    // least 3 leading zeros, then we are guaranteed that the result will have at lest 2
    // leading zeros.
    RESULT_T x = 0;
    RESULT_T y = 0;
    AdjustToSameScale(*this, this_scale, other, other_scale, result_precision, &x, &y);
    DCHECK(abs(x) <= DecimalUtil::MAX_UNSCALED_DECIMAL16 - abs(y));
    x += y;
    if (result_scale_decrease > 0) {
      // After first adjusting x and y to the same scale and adding them together, we now
      // need scale down the result to result_scale.
      x = DecimalUtil::ScaleDownAndRound<RESULT_T>(x, result_scale_decrease, round);
    }
    return DecimalValue<RESULT_T>(x);
  }

  // If both numbers cannot be added directly, we have to resort to a more complex
  // and slower algorithm.
  int128_t x = value();
  int128_t y = other.value();
  int128_t result;

  if (x >= 0 && y >= 0) {
    result = detail::AddLarge(
        x, this_scale, y, other_scale, result_scale, round, overflow);
  } else if (x <= 0 && y <= 0) {
    result = -detail::AddLarge(
        -x, this_scale, -y, other_scale, result_scale, round, overflow);
  } else {
    result = detail::SubtractLarge(
        x, this_scale, y, other_scale, result_scale, round, overflow);
  }
  return DecimalValue<RESULT_T>(result);
}

template<typename T>
template<typename RESULT_T>
DecimalValue<RESULT_T> DecimalValue<T>::Multiply(int this_scale,
    const DecimalValue& other, int other_scale, int result_precision, int result_scale,
    bool round, bool* overflow) const {
  // In the non-overflow case, we don't need to adjust by the scale since
  // that is already handled by the FE when it computes the result decimal type.
  // e.g. 1.23 * .2 (scale 2, scale 1 respectively) is identical to:
  // 123 * 2 with a resulting scale 3. We can do the multiply on the unscaled values.
  // The result scale in this case is the sum of the input scales.
  RESULT_T x = value();
  RESULT_T y = other.value();
  if (x == 0 || y == 0) {
    // Handle zero to avoid divide by zero in the overflow check below.
    return DecimalValue<RESULT_T>(0);
  }
  RESULT_T result = 0;
  bool needs_int256 = false;
  int delta_scale = this_scale + other_scale - result_scale;
  if (result_precision == ColumnType::MAX_PRECISION) {
    DCHECK_EQ(sizeof(RESULT_T), 16);
    int total_leading_zeros = BitUtil::CountLeadingZeros(abs(x)) +
        BitUtil::CountLeadingZeros(abs(y));
    // This check is quick, but conservative. In some cases it will indicate that
    // converting to 256 bits is necessary, when it's not actually the case.
    needs_int256 = total_leading_zeros <= 128;
    if (UNLIKELY(needs_int256 && delta_scale == 0)) {
      if (LIKELY(abs(x) > DecimalUtil::MAX_UNSCALED_DECIMAL16 / abs(y))) {
        // If the intermediate value does not fit into 128 bits, we indicate overflow
        // because the final value would also not fit into 128 bits since delta_scale is
        // zero.
        *overflow = true;
      } else {
        // We've verified that the intermediate (and final) value will fit into 128 bits.
        needs_int256 = false;
      }
    }
  }
  if (UNLIKELY(needs_int256)) {
    if (delta_scale == 0) {
      DCHECK(*overflow);
    } else {
      int256_t intermediate_result = ConvertToInt256(x) * ConvertToInt256(y);
      intermediate_result = DecimalUtil::ScaleDownAndRound<int256_t>(
          intermediate_result, delta_scale, round);
      result = ConvertToInt128(
          intermediate_result, DecimalUtil::MAX_UNSCALED_DECIMAL16, overflow);
    }
  } else {
    if (delta_scale == 0) {
      result = DecimalUtil::SafeMultiply(x, y, false);
      if (UNLIKELY(result_precision == ColumnType::MAX_PRECISION &&
          abs(result) > DecimalUtil::MAX_UNSCALED_DECIMAL16)) {
        // An overflow is possible here, if, for example, x = (2^64 - 1) and
        // y = (2^63 - 1).
        *overflow = true;
      }
    } else if (LIKELY(delta_scale <= 38)) {
      result = DecimalUtil::SafeMultiply(x, y, false);
      // The largest value that result can have here is (2^64 - 1) * (2^63 - 1), which is
      // greater than MAX_UNSCALED_DECIMAL16.
      result = DecimalUtil::ScaleDownAndRound<RESULT_T>(result, delta_scale, round);
      // Since delta_scale is greater than zero, result can now be at most
      // ((2^64 - 1) * (2^63 - 1)) / 10, which is less than MAX_UNSCALED_DECIMAL16, so
      // there is no need to check for overflow.
    } else {
      // We are multiplying decimal(38, 38) by decimal(38, 38). The result should be a
      // decimal(38, 37), so delta scale = 38 + 38 - 37 = 39. Since we are not in the
      // 256 bit intermediate value case and we are scaling down by 39, then we are
      // guaranteed that the result is 0 (even if we try to round). The largest possible
      // intermediate result is 38 "9"s. If we scale down by 39, the leftmost 9 is now
      // two digits to the right of the rightmost "visible" one. The reason why we have
      // to handle this case separately is because a scale multiplier with a delta_scale
      // 39 does not fit into int128.
      DCHECK_EQ(delta_scale, 39);
      DCHECK(round);
      result = 0;
    }
  }
  DCHECK(*overflow || abs(result) <= DecimalUtil::MAX_UNSCALED_DECIMAL16);
  return DecimalValue<RESULT_T>(result);
}

template<typename T>
template<typename RESULT_T>
inline DecimalValue<RESULT_T> DecimalValue<T>::Divide(int this_scale,
    const DecimalValue& other, int other_scale, int result_precision, int result_scale,
    bool round, bool* is_nan, bool* overflow) const {
  DCHECK_GE(result_scale + other_scale, this_scale);
  if (UNLIKELY(other.value() == 0)) {
    // Divide by 0.
    *is_nan = true;
    return DecimalValue<RESULT_T>();
  }
  // We need to scale x up by the result scale and then do an integer divide.
  // This truncates the result to the output scale.
  int scale_by = result_scale + other_scale - this_scale;
  DCHECK_GE(scale_by, 0);
  // Use higher precision ints for intermediates to avoid overflows. Divides lead to
  // large numbers very quickly (and get eliminated by the int divide).
  if (sizeof(T) == 16) {
    int128_t x_sp = value();
    // There is a test in expr-test.cc that shows that it OK to check for overflow this
    // way (and that no additional checks are required).
    bool ovf = scale_by > 38 && detail::MaxBitsRequiredAfterScaling(x_sp, scale_by) > 255;
    int256_t x = DecimalUtil::MultiplyByScale<int256_t>(
        ConvertToInt256(x_sp), scale_by, ovf);
    *overflow |= ovf;
    int128_t y_sp = other.value();
    int256_t y = ConvertToInt256(y_sp);
    int128_t r = ConvertToInt128(x / y, DecimalUtil::MAX_UNSCALED_DECIMAL16, overflow);
    if (round) {
      int256_t remainder = x % y;
      // The following is frought with apparent difficulty, as there is only 1 bit
      // free in the implementation of int128_t representing our maximum value and
      // doubling such a value would overflow in two's complement.  However, we
      // converted y to a 256 bit value, and remainder must be less than y, so there
      // is plenty of space.  Building a value to DCHECK for this is rather awkward, but
      // quite obviously 2 * MAX_UNSCALED_DECIMAL16 has plenty of room in 256 bits.
      // This will need to be fixed if we optimize to get back a 128-bit signed value.
      if (abs(2 * remainder) >= abs(y)) {
        // Bias at zero must be corrected by sign of divisor and dividend.
        r += (BitUtil::Sign(x_sp) ^ BitUtil::Sign(y_sp)) + 1;
      }
    }
    // Check overflow again after rounding since +/-1 could cause decimal overflow
    if (result_precision == ColumnType::MAX_PRECISION) {
      *overflow |= abs(r) > DecimalUtil::MAX_UNSCALED_DECIMAL16;
    }
    return DecimalValue<RESULT_T>(r);
  } else {
    int128_t x = DecimalUtil::MultiplyByScale<RESULT_T>(value(), scale_by, false);
    int128_t y = other.value();
    int128_t r = x / y;
    if (round) {
      int128_t remainder = x % y;
      // No overflow because doubling the result of 8-byte integers fits in 128 bits
      DCHECK_LT(sizeof(T), sizeof(remainder));
      if (abs(2 * remainder) >= abs(y)) {
        // No bias at zero.  The result scale was chosen such that the smallest non-zero
        // 'x' divided by the largest 'y' will always produce a non-zero result.
        // If higher precision were required due to a very large scale, we would be
        // computing in 256 bits, where getting a zero result is actually a posibility.
        // In addition, we know the dividend is non-zero, since there was a remainder.
        // The two conditions combined mean that the result must also be non-zero.
        DCHECK(r != 0);
        r += BitUtil::Sign(r);
      }
    }
    DCHECK(abs(r) <= DecimalUtil::MAX_UNSCALED_DECIMAL16 &&
        (sizeof(RESULT_T) > 8 || abs(r) <= DecimalUtil::MAX_UNSCALED_DECIMAL8) &&
        (sizeof(RESULT_T) > 4 || abs(r) <= DecimalUtil::MAX_UNSCALED_DECIMAL4));
    return DecimalValue<RESULT_T>(static_cast<RESULT_T>(r));
  }
}

template<typename T>
template<typename RESULT_T>
inline DecimalValue<RESULT_T> DecimalValue<T>::Mod(int this_scale,
    const DecimalValue& other, int other_scale, int result_precision, int result_scale,
    bool round, bool* is_nan, bool* overflow) const {
  DCHECK_EQ(result_scale, std::max(this_scale, other_scale));
  *is_nan = other.value() == 0;
  if (UNLIKELY(*is_nan)) return DecimalValue<RESULT_T>();

  RESULT_T result;
  switch (sizeof(RESULT_T)) {
    case 4: {
      int64_t x, y;
      AdjustToSameScale(*this, this_scale, other, other_scale, result_precision, &x, &y);
      DCHECK(abs(x % y) <= DecimalUtil::MAX_UNSCALED_DECIMAL4);
      result = x % y;
      break;
    }
    case 8: {
      if (detail::MinLeadingZeros<RESULT_T>(
          value(), this_scale, other.value(), other_scale) >= 2) {
        int64_t x, y;
        AdjustToSameScale(*this, this_scale, other, other_scale,
            result_precision, &x, &y);
        DCHECK(abs(x % y) <= DecimalUtil::MAX_UNSCALED_DECIMAL8);
        result = x % y;
      } else {
        int128_t x, y;
        AdjustToSameScale(*this, this_scale, other, other_scale,
            result_precision, &x, &y);
        DCHECK(abs(x % y) <= DecimalUtil::MAX_UNSCALED_DECIMAL8);
        result = x % y;
      }
      break;
    }
    case 16: {
      if (detail::MinLeadingZeros<RESULT_T>(
          value(), this_scale, other.value(), other_scale) >= 2) {
        int128_t x, y;
        AdjustToSameScale(*this, this_scale, other, other_scale,
            result_precision, &x, &y);
        DCHECK(abs(x % y) <= DecimalUtil::MAX_UNSCALED_DECIMAL16);
        result = x % y;
      } else {
        int256_t x_256 = ConvertToInt256(value());
        int256_t y_256 = ConvertToInt256(other.value());
        if (this_scale < other_scale) {
          x_256 *= DecimalUtil::GetScaleMultiplier<int256_t>(other_scale - this_scale);
        } else {
          y_256 *= DecimalUtil::GetScaleMultiplier<int256_t>(this_scale - other_scale);
        }
        int256_t intermediate_result = x_256 % y_256;
        bool ovf = false;
        result = ConvertToInt128(intermediate_result,
            DecimalUtil::MAX_UNSCALED_DECIMAL16, &ovf);
        DCHECK(!ovf);
      }
      break;
    }
    default: {
      DCHECK(false);
    }
  }
  DCHECK(abs(result) <= abs(value()) || abs(result) < abs(other.value()));
  return DecimalValue<RESULT_T>(result);
}

template <typename T>
template <typename RESULT_T>
inline void DecimalValue<T>::AdjustToSameScale(const DecimalValue<T>& x, int x_scale,
    const DecimalValue<T>& y, int y_scale, int result_precision, RESULT_T* x_scaled,
    RESULT_T* y_scaled) {
  int delta_scale = x_scale - y_scale;
  RESULT_T scale_factor = DecimalUtil::GetScaleMultiplier<RESULT_T>(abs(delta_scale));
  if (delta_scale == 0) {
    *x_scaled = x.value();
    *y_scaled = y.value();
  } else if (delta_scale > 0) {
    *x_scaled = x.value();
    *y_scaled = DecimalUtil::SafeMultiply<RESULT_T>(y.value(), scale_factor, false);
  } else {
    *x_scaled = DecimalUtil::SafeMultiply<RESULT_T>(x.value(), scale_factor, false);
    *y_scaled = y.value();
  }
}

/// For comparisons, we need the intermediate to be at the next precision
/// to avoid overflows.
/// TODO: is there a more efficient way to do this?
template <>
inline int Decimal4Value::Compare(int this_scale, const Decimal4Value& other,
    int other_scale) const {
  int64_t x, y;
  AdjustToSameScale(*this, this_scale, other, other_scale, 0, &x, &y);
  if (x == y) return 0;
  if (x < y) return -1;
  return 1;
}

template <>
inline int Decimal8Value::Compare(int this_scale, const Decimal8Value& other,
    int other_scale) const {
  int128_t x = 0, y = 0;
  AdjustToSameScale(*this, this_scale, other, other_scale, 0, &x, &y);
  if (x == y) return 0;
  if (x < y) return -1;
  return 1;
}

template <>
inline int Decimal16Value::Compare(int this_scale, const Decimal16Value& other,
     int other_scale) const {
  int256_t x = ConvertToInt256(this->value());
  int256_t y = ConvertToInt256(other.value());
  int delta_scale = this_scale - other_scale;
  if (delta_scale > 0) {
    y = DecimalUtil::MultiplyByScale<int256_t>(y, delta_scale, false);
  } else if (delta_scale < 0) {
    x = DecimalUtil::MultiplyByScale<int256_t>(x, -delta_scale, false);
  }
  if (x == y) return 0;
  if (x < y) return -1;
  return 1;
}

/// Returns as string with full 0 padding on the right and single 0 padded on the left
/// if the whole part is zero otherwise there will be no left padding.
template<typename T>
inline std::string DecimalValue<T>::ToString(const ColumnType& type) const {
  DCHECK_EQ(type.type, TYPE_DECIMAL);
  return ToString(type.precision, type.scale);
}

template<typename T>
inline std::string DecimalValue<T>::ToString(int precision, int scale) const {
  T value;
  // 'value_' may be unaligned. Use memcpy to avoid emitting instructions that assume
  // alignment - see IMPALA-7473.
  memcpy(&value, &value_, sizeof(T));
  // Decimal values are sent to clients as strings so in the interest of
  // speed the string will be created without the using stringstream with the
  // whole/fractional_part().
  int last_char_idx = precision
      + (scale > 0)   // Add a space for decimal place
      + (scale == precision)   // Add a space for leading 0
      + (value < 0);   // Add a space for negative sign
  std::string str = std::string(last_char_idx, '0');
  // Start filling in the values in reverse order by taking the last digit
  // of the value. Use a positive value and worry about the sign later. At this
  // point the last_char_idx points to the string terminator.
  T remaining_value = value;
  int first_digit_idx = 0;
  if (value < 0) {
    remaining_value = -value;
    first_digit_idx = 1;
  }
  if (scale > 0) {
    int remaining_scale = scale;
    do {
      str[--last_char_idx] = (remaining_value % 10) + '0';   // Ascii offset
      remaining_value /= 10;
    } while (--remaining_scale > 0);
    str[--last_char_idx] = '.';
    DCHECK_GT(last_char_idx, first_digit_idx) << "Not enough space remaining";
  }
  do {
    str[--last_char_idx] = (remaining_value % 10) + '0';   // Ascii offset
    remaining_value /= 10;
    if (remaining_value == 0) {
      // Trim any extra leading 0's.
      if (last_char_idx > first_digit_idx) str.erase(0, last_char_idx - first_digit_idx);
      break;
    }
    // For safety, enforce string length independent of remaining_value.
  } while (last_char_idx > first_digit_idx);
  if (value < 0) str[0] = '-';
  return str;
}

template<typename T>
inline double DecimalValue<T>::ToDouble(int scale) const {
  return static_cast<double>(value_) / pow(10.0, scale);
}

template<typename T>
inline uint32_t DecimalValue<T>::Hash(int seed) const {
  return HashUtil::Hash(&value_, sizeof(value_), seed);
}

/// This function must be called 'hash_value' to be picked up by boost.
inline std::size_t hash_value(const Decimal4Value& v) {
  return v.Hash();
}
inline std::size_t hash_value(const Decimal8Value& v) {
  return v.Hash();
}
inline std::size_t hash_value(const Decimal16Value& v) {
  return v.Hash();
}

template<typename T>
inline DecimalValue<T> DecimalValue<T>::Abs() const {
  return DecimalValue<T>(abs(value_));
}

/// Conversions from different decimal types to one another. This does not
/// alter the scale. Checks for overflow. Although in some cases (going from Decimal4Value
/// to Decimal8Value) cannot overflow, the signature is the same to allow for templating.
inline Decimal4Value ToDecimal4(const Decimal4Value& v, bool* overflow) {
  return v;
}

inline Decimal8Value ToDecimal8(const Decimal4Value& v, bool* overflow) {
  return Decimal8Value(static_cast<int64_t>(v.value()));
}

inline Decimal16Value ToDecimal16(const Decimal4Value& v, bool* overflow) {
  return Decimal16Value(static_cast<int128_t>(v.value()));
}

inline Decimal4Value ToDecimal4(const Decimal8Value& v, bool* overflow) {
  *overflow |= abs(v.value()) > std::numeric_limits<int32_t>::max();
  return Decimal4Value(static_cast<int32_t>(v.value()));
}

inline Decimal8Value ToDecimal8(const Decimal8Value& v, bool* overflow) {
  return v;
}

inline Decimal16Value ToDecimal16(const Decimal8Value& v, bool* overflow) {
  return Decimal16Value(static_cast<int128_t>(v.value()));
}

inline Decimal4Value ToDecimal4(const Decimal16Value& v, bool* overflow) {
  *overflow |= abs(v.value()) > std::numeric_limits<int32_t>::max();
  return Decimal4Value(static_cast<int32_t>(v.value()));
}

inline Decimal8Value ToDecimal8(const Decimal16Value& v, bool* overflow) {
  *overflow |= abs(v.value()) > std::numeric_limits<int64_t>::max();
  return Decimal8Value(static_cast<int64_t>(v.value()));
}

inline Decimal16Value ToDecimal16(const Decimal16Value& v, bool* overflow) {
  return v;
}

}

#endif