[
https://issues.apache.org/jira/browse/ARROW-1749?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16239772#comment-16239772
]
ASF GitHub Bot commented on ARROW-1749:
---------------------------------------
wesm closed pull request #1282: ARROW-1749: [C++] Handle range of Decimal128
values that require 39 digits to be displayed
URL: https://github.com/apache/arrow/pull/1282
This is a PR merged from a forked repository.
As GitHub hides the original diff on merge, it is displayed below for
the sake of provenance:
As this is a foreign pull request (from a fork), the diff is supplied
below (as it won't show otherwise due to GitHub magic):
diff --git a/cpp/src/arrow/array.cc b/cpp/src/arrow/array.cc
index fc4b96e1b..b523876bf 100644
--- a/cpp/src/arrow/array.cc
+++ b/cpp/src/arrow/array.cc
@@ -321,8 +321,8 @@ DecimalArray::DecimalArray(const
std::shared_ptr<ArrayData>& data)
std::string DecimalArray::FormatValue(int64_t i) const {
const auto& type_ = static_cast<const DecimalType&>(*type());
- Decimal128 value(GetValue(i));
- return value.ToString(type_.precision(), type_.scale());
+ const Decimal128 value(GetValue(i));
+ return value.ToString(type_.scale());
}
// ----------------------------------------------------------------------
diff --git a/cpp/src/arrow/python/arrow_to_pandas.cc
b/cpp/src/arrow/python/arrow_to_pandas.cc
index c92faede1..3894772da 100644
--- a/cpp/src/arrow/python/arrow_to_pandas.cc
+++ b/cpp/src/arrow/python/arrow_to_pandas.cc
@@ -616,11 +616,10 @@ static Status ConvertTimes(PandasOptions options, const
ChunkedArray& data,
return Status::OK();
}
-static Status RawDecimalToString(const uint8_t* bytes, int precision, int
scale,
- std::string* result) {
+static Status RawDecimalToString(const uint8_t* bytes, int scale, std::string*
result) {
DCHECK_NE(result, nullptr);
Decimal128 decimal(bytes);
- *result = decimal.ToString(precision, scale);
+ *result = decimal.ToString(scale);
return Status::OK();
}
@@ -636,7 +635,6 @@ static Status ConvertDecimals(PandasOptions options, const
ChunkedArray& data,
for (int c = 0; c < data.num_chunks(); c++) {
auto* arr(static_cast<arrow::DecimalArray*>(data.chunk(c).get()));
auto type(std::dynamic_pointer_cast<arrow::DecimalType>(arr->type()));
- const int precision = type->precision();
const int scale = type->scale();
for (int64_t i = 0; i < arr->length(); ++i) {
@@ -646,7 +644,7 @@ static Status ConvertDecimals(PandasOptions options, const
ChunkedArray& data,
} else {
const uint8_t* raw_value = arr->GetValue(i);
std::string decimal_string;
- RETURN_NOT_OK(RawDecimalToString(raw_value, precision, scale,
&decimal_string));
+ RETURN_NOT_OK(RawDecimalToString(raw_value, scale, &decimal_string));
*out_values++ = internal::DecimalFromString(Decimal, decimal_string);
RETURN_IF_PYERROR();
}
diff --git a/cpp/src/arrow/util/bit-util.h b/cpp/src/arrow/util/bit-util.h
index 8043f90cc..d6415f3c7 100644
--- a/cpp/src/arrow/util/bit-util.h
+++ b/cpp/src/arrow/util/bit-util.h
@@ -43,6 +43,8 @@
#endif
#if defined(_MSC_VER)
+#include <intrin.h>
+#pragma intrinsic(_BitScanReverse)
#define ARROW_BYTE_SWAP64 _byteswap_uint64
#define ARROW_BYTE_SWAP32 _byteswap_ulong
#else
@@ -55,6 +57,7 @@
#include <memory>
#include <vector>
+#include "arrow/util/logging.h"
#include "arrow/util/macros.h"
#include "arrow/util/type_traits.h"
#include "arrow/util/visibility.h"
@@ -296,6 +299,25 @@ static inline int Log2(uint64_t x) {
return result;
}
+/// \brief Count the number of leading zeros in a 32 bit integer.
+static inline int64_t CountLeadingZeros(uint32_t value) {
+ DCHECK_NE(value, 0);
+#if defined(__clang__) || defined(__GNUC__)
+ return static_cast<int64_t>(__builtin_clz(value));
+#elif defined(_MSC_VER)
+ unsigned long index; // NOLINT
+ _BitScanReverse(&index, static_cast<unsigned long>(value)); // NOLINT
+ return 31LL - static_cast<int64_t>(index);
+#else
+ int64_t bitpos = 0;
+ while (value != 0) {
+ value >>= 1;
+ ++bitpos;
+ }
+ return 32LL - bitpos;
+#endif
+}
+
/// Swaps the byte order (i.e. endianess)
static inline int64_t ByteSwap(int64_t value) { return
ARROW_BYTE_SWAP64(value); }
static inline uint64_t ByteSwap(uint64_t value) {
diff --git a/cpp/src/arrow/util/decimal-test.cc
b/cpp/src/arrow/util/decimal-test.cc
index 565a1bbb9..b0271fff1 100644
--- a/cpp/src/arrow/util/decimal-test.cc
+++ b/cpp/src/arrow/util/decimal-test.cc
@@ -36,9 +36,8 @@ class DecimalTestFixture : public ::testing::Test {
TEST_F(DecimalTestFixture, TestToString) {
Decimal128 decimal(this->integer_value_);
- int precision = 8;
int scale = 5;
- std::string result = decimal.ToString(precision, scale);
+ std::string result = decimal.ToString(scale);
ASSERT_EQ(result, this->string_value_);
}
@@ -256,4 +255,40 @@ TEST(Decimal128TestFalse, ConstructibleFromBool) {
ASSERT_EQ(0, value.low_bits());
}
+TEST(Decimal128Test, Division) {
+ const std::string expected_string_value("-23923094039234029");
+ const Decimal128 value(expected_string_value);
+ const Decimal128 result(value / 3);
+ const Decimal128 expected_value("-7974364679744676");
+ ASSERT_EQ(expected_value, result);
+}
+
+TEST(Decimal128Test, PrintLargePositiveValue) {
+ const std::string string_value("99999999999999999999999999999999999999");
+ const Decimal128 value(string_value);
+ const std::string printed_value = value.ToIntegerString();
+ ASSERT_EQ(string_value, printed_value);
+}
+
+TEST(Decimal128Test, PrintLargeNegativeValue) {
+ const std::string string_value("-99999999999999999999999999999999999999");
+ const Decimal128 value(string_value);
+ const std::string printed_value = value.ToIntegerString();
+ ASSERT_EQ(string_value, printed_value);
+}
+
+TEST(Decimal128Test, PrintMaxValue) {
+ const std::string string_value("170141183460469231731687303715884105727");
+ const Decimal128 value(string_value);
+ const std::string printed_value = value.ToIntegerString();
+ ASSERT_EQ(string_value, printed_value);
+}
+
+TEST(Decimal128Test, PrintMinValue) {
+ const std::string string_value("-170141183460469231731687303715884105728");
+ const Decimal128 value(string_value);
+ const std::string printed_value = value.ToIntegerString();
+ ASSERT_EQ(string_value, printed_value);
+}
+
} // namespace arrow
diff --git a/cpp/src/arrow/util/decimal.cc b/cpp/src/arrow/util/decimal.cc
index 7196b252c..9d94bef84 100644
--- a/cpp/src/arrow/util/decimal.cc
+++ b/cpp/src/arrow/util/decimal.cc
@@ -19,14 +19,10 @@
#include <cctype>
#include <cmath>
#include <cstring>
+#include <iomanip>
#include <limits>
#include <sstream>
-#ifdef _MSC_VER
-#include <intrin.h>
-#pragma intrinsic(_BitScanReverse)
-#endif
-
#include "arrow/util/bit-util.h"
#include "arrow/util/decimal.h"
#include "arrow/util/logging.h"
@@ -55,62 +51,116 @@ std::array<uint8_t, 16> Decimal128::ToBytes() const {
return out;
}
-std::string Decimal128::ToString(int precision, int scale) const {
- using std::size_t;
+static constexpr Decimal128 kTenTo36(static_cast<int64_t>(0xC097CE7BC90715),
+ 0xB34B9F1000000000);
+static constexpr Decimal128 kTenTo18(0xDE0B6B3A7640000);
- const bool is_negative = *this < 0;
-
- // 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().
- size_t last_char_idx = precision + (scale > 0) // Add a space for decimal
place
- + (scale == precision) // Add a space for leading 0
- + is_negative; // Add a space for negative
sign
-
- std::string str(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.
- Decimal128 remaining_value(*this);
-
- const auto first_digit_idx = static_cast<size_t>(is_negative);
- if (is_negative) {
- remaining_value.Negate();
- }
-
- if (scale > 0) {
- int remaining_scale = scale;
- do {
- str[--last_char_idx] =
- static_cast<char>(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] = static_cast<char>(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);
- }
+std::string Decimal128::ToIntegerString() const {
+ Decimal128 remainder;
+ std::stringstream buf;
+ bool need_fill = false;
- break;
+ // get anything above 10 ** 36 and print it
+ Decimal128 top;
+ Status s = Divide(kTenTo36, &top, &remainder);
+ DCHECK(s.ok()) << s.message();
+
+ if (top != 0) {
+ buf << static_cast<int64_t>(top);
+ remainder.Abs();
+ need_fill = true;
+ }
+
+ // now get anything above 10 ** 18 and print it
+ Decimal128 tail;
+ s = remainder.Divide(kTenTo18, &top, &tail);
+
+ if (need_fill || top != 0) {
+ if (need_fill) {
+ buf << std::setw(18) << std::setfill('0');
+ } else {
+ need_fill = true;
+ tail.Abs();
+ }
+
+ buf << static_cast<int64_t>(top);
+ }
+
+ // finally print the tail, which is less than 10**18
+ if (need_fill) {
+ buf << std::setw(18) << std::setfill('0');
+ }
+ buf << static_cast<int64_t>(tail);
+ return buf.str();
+}
+
+Decimal128::operator int64_t() const {
+ DCHECK(high_bits_ == 0 || high_bits_ == -1)
+ << "Trying to cast an Decimal128 greater than the value range of a "
+ "int64_t. high_bits_ must be equal to 0 or -1, got: "
+ << high_bits_;
+ return static_cast<int64_t>(low_bits_);
+}
+
+std::string Decimal128::ToString(int32_t scale) const {
+ const std::string str(ToIntegerString());
+
+ if (scale == 0) {
+ return str;
+ }
+
+ if (*this < 0) {
+ const auto len = static_cast<int32_t>(str.size());
+
+ if (len - 1 > scale) {
+ const auto n = static_cast<size_t>(len - scale);
+ return str.substr(0, n) + "." + str.substr(n,
static_cast<size_t>(scale));
+ }
+
+ if (len - 1 == scale) {
+ return "-0." + str.substr(1, std::string::npos);
}
- // For safety, enforce string length independent of remaining_value.
- } while (last_char_idx > first_digit_idx);
- if (is_negative) {
- str[0] = '-';
+ std::string result("-0." + std::string(static_cast<size_t>(scale - len +
1), '0'));
+ return result + str.substr(1, std::string::npos);
+ }
+
+ const auto len = static_cast<int32_t>(str.size());
+
+ if (len > scale) {
+ const auto n = static_cast<size_t>(len - scale);
+ return str.substr(0, n) + "." + str.substr(n, static_cast<size_t>(scale));
+ }
+
+ if (len == scale) {
+ return "0." + str;
}
- return str;
+ return "0." + std::string(static_cast<size_t>(scale - len), '0') + str;
}
+static constexpr auto kInt64DecimalDigits =
+ static_cast<size_t>(std::numeric_limits<int64_t>::digits10);
+static constexpr int64_t kPowersOfTen[kInt64DecimalDigits + 1] = {1LL,
+ 10LL,
+ 100LL,
+ 1000LL,
+ 10000LL,
+ 100000LL,
+ 1000000LL,
+ 10000000LL,
+ 100000000LL,
+ 1000000000LL,
+
10000000000LL,
+
100000000000LL,
+
1000000000000LL,
+
10000000000000LL,
+
100000000000000LL,
+
1000000000000000LL,
+
10000000000000000LL,
+
100000000000000000LL,
+
1000000000000000000LL};
+
static void StringToInteger(const std::string& str, Decimal128* out) {
using std::size_t;
@@ -122,13 +172,10 @@ static void StringToInteger(const std::string& str,
Decimal128* out) {
DCHECK_GT(length, 0) << "length of parsed decimal string should be greater
than 0";
- size_t posn = 0;
-
- while (posn < length) {
- const size_t group = std::min(static_cast<size_t>(18), length - posn);
- const auto chunk = static_cast<int64_t>(std::stoll(str.substr(posn,
group)));
- const auto multiple =
- static_cast<int64_t>(std::pow(10.0, static_cast<double>(group)));
+ for (size_t posn = 0; posn < length;) {
+ const size_t group = std::min(kInt64DecimalDigits, length - posn);
+ const int64_t chunk = std::stoll(str.substr(posn, group));
+ const int64_t multiple = kPowersOfTen[group];
*out *= multiple;
*out += chunk;
@@ -266,6 +313,8 @@ Decimal128& Decimal128::Negate() {
return *this;
}
+Decimal128& Decimal128::Abs() { return *this < 0 ? Negate() : *this; }
+
Decimal128& Decimal128::operator+=(const Decimal128& right) {
const uint64_t sum = low_bits_ + right.low_bits_;
high_bits_ += right.high_bits_;
@@ -288,20 +337,11 @@ Decimal128& Decimal128::operator-=(const Decimal128&
right) {
Decimal128& Decimal128::operator/=(const Decimal128& right) {
Decimal128 remainder;
- DCHECK(Divide(right, this, &remainder).ok());
+ Status s = Divide(right, this, &remainder);
+ DCHECK(s.ok());
return *this;
}
-Decimal128::operator char() const {
- DCHECK(high_bits_ == 0 || high_bits_ == -1)
- << "Trying to cast an Decimal128 greater than the value range of a "
- "char. high_bits_ must be equal to 0 or -1, got: "
- << high_bits_;
- DCHECK_LE(low_bits_, std::numeric_limits<char>::max())
- << "low_bits_ too large for C type char, got: " << low_bits_;
- return static_cast<char>(low_bits_);
-}
-
Decimal128& Decimal128::operator|=(const Decimal128& right) {
low_bits_ |= right.low_bits_;
high_bits_ |= right.high_bits_;
@@ -440,18 +480,6 @@ static int64_t FillInArray(const Decimal128& value,
uint32_t* array, bool& was_n
return 1;
}
-/// \brief Find last set bit in a 32 bit integer. Bit 1 is the LSB and bit 32
is the MSB.
-static int64_t FindLastSetBit(uint32_t value) {
-#if defined(__clang__) || defined(__GNUC__)
- // Count leading zeros
- return __builtin_clz(value) + 1;
-#elif defined(_MSC_VER)
- unsigned long index; // NOLINT
- _BitScanReverse(&index, static_cast<unsigned long>(value)); // NOLINT
- return static_cast<int64_t>(index + 1UL);
-#endif
-}
-
/// Shift the number in the array left by bits positions.
/// \param array the number to shift, must have length elements
/// \param length the number of entries in the array
@@ -581,7 +609,7 @@ Status Decimal128::Divide(const Decimal128& divisor,
Decimal128* result,
// Normalize by shifting both by a multiple of 2 so that
// the digit guessing is better. The requirement is that
// divisor_array[0] is greater than 2**31.
- int64_t normalize_bits = 32 - FindLastSetBit(divisor_array[0]);
+ int64_t normalize_bits = BitUtil::CountLeadingZeros(divisor_array[0]);
ShiftArrayLeft(divisor_array, divisor_length, normalize_bits);
ShiftArrayLeft(dividend_array, dividend_length, normalize_bits);
@@ -589,7 +617,7 @@ Status Decimal128::Divide(const Decimal128& divisor,
Decimal128* result,
for (int64_t j = 0; j < result_length; ++j) {
// Guess the next digit. At worst it is two too large
uint32_t guess = std::numeric_limits<uint32_t>::max();
- auto high_dividend =
+ const auto high_dividend =
static_cast<uint64_t>(dividend_array[j]) << 32 | dividend_array[j + 1];
if (dividend_array[j] != divisor_array[0]) {
guess = static_cast<uint32_t>(high_dividend / divisor_array[0]);
@@ -625,10 +653,9 @@ Status Decimal128::Divide(const Decimal128& divisor,
Decimal128* result,
// if guess was too big, we add back divisor
if (dividend_array[j] > prev) {
--guess;
-
uint32_t carry = 0;
for (int64_t i = divisor_length - 1; i >= 0; --i) {
- uint64_t sum =
+ const auto sum =
static_cast<uint64_t>(divisor_array[i]) + dividend_array[j + i +
1] + carry;
dividend_array[j + i + 1] = static_cast<uint32_t>(sum);
carry = static_cast<uint32_t>(sum >> 32);
@@ -645,6 +672,7 @@ Status Decimal128::Divide(const Decimal128& divisor,
Decimal128* result,
// return result and remainder
RETURN_NOT_OK(BuildFromArray(result, result_array, result_length));
RETURN_NOT_OK(BuildFromArray(remainder, dividend_array, dividend_length));
+
FixDivisionSigns(result, remainder, dividend_was_negative,
divisor_was_negative);
return Status::OK();
}
@@ -679,6 +707,11 @@ Decimal128 operator-(const Decimal128& operand) {
return result.Negate();
}
+Decimal128 operator~(const Decimal128& operand) {
+ Decimal128 result(~operand.high_bits(), ~operand.low_bits());
+ return result;
+}
+
Decimal128 operator+(const Decimal128& left, const Decimal128& right) {
Decimal128 result(left.high_bits(), left.low_bits());
result += right;
@@ -700,14 +733,16 @@ Decimal128 operator*(const Decimal128& left, const
Decimal128& right) {
Decimal128 operator/(const Decimal128& left, const Decimal128& right) {
Decimal128 remainder;
Decimal128 result;
- DCHECK(left.Divide(right, &result, &remainder).ok());
+ Status s = left.Divide(right, &result, &remainder);
+ DCHECK(s.ok());
return result;
}
Decimal128 operator%(const Decimal128& left, const Decimal128& right) {
Decimal128 remainder;
Decimal128 result;
- DCHECK(left.Divide(right, &result, &remainder).ok());
+ Status s = left.Divide(right, &result, &remainder);
+ DCHECK(s.ok());
return remainder;
}
diff --git a/cpp/src/arrow/util/decimal.h b/cpp/src/arrow/util/decimal.h
index 72da55479..487f22258 100644
--- a/cpp/src/arrow/util/decimal.h
+++ b/cpp/src/arrow/util/decimal.h
@@ -39,15 +39,16 @@ namespace arrow {
class ARROW_EXPORT Decimal128 {
public:
/// \brief Create an Decimal128 from the two's complement representation.
- constexpr Decimal128(int64_t high, uint64_t low) : high_bits_(high),
low_bits_(low) {}
+ constexpr Decimal128(int64_t high, uint64_t low) noexcept
+ : high_bits_(high), low_bits_(low) {}
/// \brief Empty constructor creates an Decimal128 with a value of 0.
- constexpr Decimal128() : Decimal128(0, 0) {}
+ constexpr Decimal128() noexcept : Decimal128(0, 0) {}
/// \brief Convert any integer value into an Decimal128.
template <typename T,
typename = typename std::enable_if<std::is_integral<T>::value,
T>::type>
- constexpr Decimal128(T value)
+ constexpr Decimal128(T value) noexcept
: Decimal128(static_cast<int64_t>(value) >= 0 ? 0 : -1,
static_cast<uint64_t>(value)) {}
@@ -61,6 +62,9 @@ class ARROW_EXPORT Decimal128 {
/// \brief Negate the current value
Decimal128& Negate();
+ /// \brief Absolute value
+ Decimal128& Abs();
+
/// \brief Add a number to this one. The result is truncated to 128 bits.
Decimal128& operator+=(const Decimal128& right);
@@ -85,9 +89,6 @@ class ARROW_EXPORT Decimal128 {
/// \brief In-place division.
Decimal128& operator/=(const Decimal128& right);
- /// \brief Cast the value to char. This is used when converting the value a
string.
- explicit operator char() const;
-
/// \brief Bitwise or between two Decimal128.
Decimal128& operator|=(const Decimal128& right);
@@ -110,8 +111,14 @@ class ARROW_EXPORT Decimal128 {
std::array<uint8_t, 16> ToBytes() const;
/// \brief Convert the Decimal128 value to a base 10 decimal string with the
given
- /// precision and scale.
- std::string ToString(int precision, int scale) const;
+ /// scale.
+ std::string ToString(int32_t scale) const;
+
+ /// \brief Convert the value to an integer string
+ std::string ToIntegerString() const;
+
+ /// \brief Cast this value to an int64_t.
+ explicit operator int64_t() const;
/// \brief Convert a decimal string to an Decimal128 value, optionally
including
/// precision and scale if they're passed in and not null.
@@ -131,6 +138,7 @@ ARROW_EXPORT bool operator>(const Decimal128& left, const
Decimal128& right);
ARROW_EXPORT bool operator>=(const Decimal128& left, const Decimal128& right);
ARROW_EXPORT Decimal128 operator-(const Decimal128& operand);
+ARROW_EXPORT Decimal128 operator~(const Decimal128& operand);
ARROW_EXPORT Decimal128 operator+(const Decimal128& left, const Decimal128&
right);
ARROW_EXPORT Decimal128 operator-(const Decimal128& left, const Decimal128&
right);
ARROW_EXPORT Decimal128 operator*(const Decimal128& left, const Decimal128&
right);
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
> [C++] Handle range of Decimal128 values that require 39 digits to be displayed
> ------------------------------------------------------------------------------
>
> Key: ARROW-1749
> URL: https://issues.apache.org/jira/browse/ARROW-1749
> Project: Apache Arrow
> Issue Type: Bug
> Components: C++
> Affects Versions: 0.7.1
> Reporter: Phillip Cloud
> Assignee: Phillip Cloud
> Labels: pull-request-available
> Fix For: 0.8.0
>
>
> {{2 ** 127 - 1}} and {{-2 ** 127}} both require a 39th digit to be displayed
> as a decimal string.
> This means we do not have the ability to _display_ decimal values above {{10
> ** 38 - 1}} even though we have the ability to _store_ them.
> For reference, Impala returns {{NULL}} when trying to cast {{2 ** 127 - 1}}
> to {{DECIMAL(38, 0)}}.
> A few next steps are in order:
> # Explicitly test this behavior
> # Avoid crashing or displaying garbage when we cannot display a number that
> can be stored
> # Make a decision about whether we want to eventually support range of values
> from {{10 ** 38}} to {{2 ** 127 - 1}} positive and {{-2 ** 127}} to {{-10 **
> 38}} negative. This would require a larger integer type to hold the value
> just before being converted to a string.
--
This message was sent by Atlassian JIRA
(v6.4.14#64029)
