1 | // Licensed to the Apache Software Foundation (ASF) under one |
2 | // or more contributor license agreements. See the NOTICE file |
3 | // distributed with this work for additional information |
4 | // regarding copyright ownership. The ASF licenses this file |
5 | // to you under the Apache License, Version 2.0 (the |
6 | // "License"); you may not use this file except in compliance |
7 | // with the License. You may obtain a copy of the License at |
8 | // |
9 | // http://www.apache.org/licenses/LICENSE-2.0 |
10 | // |
11 | // Unless required by applicable law or agreed to in writing, |
12 | // software distributed under the License is distributed on an |
13 | // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
14 | // KIND, either express or implied. See the License for the |
15 | // specific language governing permissions and limitations |
16 | // under the License. |
17 | |
18 | #include "arrow/util/basic_decimal.h" |
19 | |
20 | #include <algorithm> |
21 | #include <array> |
22 | #include <climits> |
23 | #include <cstdint> |
24 | #include <cstdlib> |
25 | #include <cstring> |
26 | #include <iomanip> |
27 | #include <limits> |
28 | #include <string> |
29 | |
30 | #include "arrow/util/bit-util.h" |
31 | #include "arrow/util/int-util.h" |
32 | #include "arrow/util/logging.h" |
33 | #include "arrow/util/macros.h" |
34 | |
35 | namespace arrow { |
36 | |
37 | using internal::SafeLeftShift; |
38 | using internal::SafeSignedAdd; |
39 | |
40 | static const BasicDecimal128 ScaleMultipliers[] = { |
41 | BasicDecimal128(1LL), |
42 | BasicDecimal128(10LL), |
43 | BasicDecimal128(100LL), |
44 | BasicDecimal128(1000LL), |
45 | BasicDecimal128(10000LL), |
46 | BasicDecimal128(100000LL), |
47 | BasicDecimal128(1000000LL), |
48 | BasicDecimal128(10000000LL), |
49 | BasicDecimal128(100000000LL), |
50 | BasicDecimal128(1000000000LL), |
51 | BasicDecimal128(10000000000LL), |
52 | BasicDecimal128(100000000000LL), |
53 | BasicDecimal128(1000000000000LL), |
54 | BasicDecimal128(10000000000000LL), |
55 | BasicDecimal128(100000000000000LL), |
56 | BasicDecimal128(1000000000000000LL), |
57 | BasicDecimal128(10000000000000000LL), |
58 | BasicDecimal128(100000000000000000LL), |
59 | BasicDecimal128(1000000000000000000LL), |
60 | BasicDecimal128(0LL, 10000000000000000000ULL), |
61 | BasicDecimal128(5LL, 7766279631452241920ULL), |
62 | BasicDecimal128(54LL, 3875820019684212736ULL), |
63 | BasicDecimal128(542LL, 1864712049423024128ULL), |
64 | BasicDecimal128(5421LL, 200376420520689664ULL), |
65 | BasicDecimal128(54210LL, 2003764205206896640ULL), |
66 | BasicDecimal128(542101LL, 1590897978359414784ULL), |
67 | BasicDecimal128(5421010LL, 15908979783594147840ULL), |
68 | BasicDecimal128(54210108LL, 11515845246265065472ULL), |
69 | BasicDecimal128(542101086LL, 4477988020393345024ULL), |
70 | BasicDecimal128(5421010862LL, 7886392056514347008ULL), |
71 | BasicDecimal128(54210108624LL, 5076944270305263616ULL), |
72 | BasicDecimal128(542101086242LL, 13875954555633532928ULL), |
73 | BasicDecimal128(5421010862427LL, 9632337040368467968ULL), |
74 | BasicDecimal128(54210108624275LL, 4089650035136921600ULL), |
75 | BasicDecimal128(542101086242752LL, 4003012203950112768ULL), |
76 | BasicDecimal128(5421010862427522LL, 3136633892082024448ULL), |
77 | BasicDecimal128(54210108624275221LL, 12919594847110692864ULL), |
78 | BasicDecimal128(542101086242752217LL, 68739955140067328ULL), |
79 | BasicDecimal128(5421010862427522170LL, 687399551400673280ULL)}; |
80 | |
81 | static const BasicDecimal128 ScaleMultipliersHalf[] = { |
82 | BasicDecimal128(0ULL), |
83 | BasicDecimal128(5ULL), |
84 | BasicDecimal128(50ULL), |
85 | BasicDecimal128(500ULL), |
86 | BasicDecimal128(5000ULL), |
87 | BasicDecimal128(50000ULL), |
88 | BasicDecimal128(500000ULL), |
89 | BasicDecimal128(5000000ULL), |
90 | BasicDecimal128(50000000ULL), |
91 | BasicDecimal128(500000000ULL), |
92 | BasicDecimal128(5000000000ULL), |
93 | BasicDecimal128(50000000000ULL), |
94 | BasicDecimal128(500000000000ULL), |
95 | BasicDecimal128(5000000000000ULL), |
96 | BasicDecimal128(50000000000000ULL), |
97 | BasicDecimal128(500000000000000ULL), |
98 | BasicDecimal128(5000000000000000ULL), |
99 | BasicDecimal128(50000000000000000ULL), |
100 | BasicDecimal128(500000000000000000ULL), |
101 | BasicDecimal128(5000000000000000000ULL), |
102 | BasicDecimal128(2LL, 13106511852580896768ULL), |
103 | BasicDecimal128(27LL, 1937910009842106368ULL), |
104 | BasicDecimal128(271LL, 932356024711512064ULL), |
105 | BasicDecimal128(2710LL, 9323560247115120640ULL), |
106 | BasicDecimal128(27105LL, 1001882102603448320ULL), |
107 | BasicDecimal128(271050LL, 10018821026034483200ULL), |
108 | BasicDecimal128(2710505LL, 7954489891797073920ULL), |
109 | BasicDecimal128(27105054LL, 5757922623132532736ULL), |
110 | BasicDecimal128(271050543LL, 2238994010196672512ULL), |
111 | BasicDecimal128(2710505431LL, 3943196028257173504ULL), |
112 | BasicDecimal128(27105054312LL, 2538472135152631808ULL), |
113 | BasicDecimal128(271050543121LL, 6937977277816766464ULL), |
114 | BasicDecimal128(2710505431213LL, 14039540557039009792ULL), |
115 | BasicDecimal128(27105054312137LL, 11268197054423236608ULL), |
116 | BasicDecimal128(271050543121376LL, 2001506101975056384ULL), |
117 | BasicDecimal128(2710505431213761LL, 1568316946041012224ULL), |
118 | BasicDecimal128(27105054312137610LL, 15683169460410122240ULL), |
119 | BasicDecimal128(271050543121376108LL, 9257742014424809472ULL), |
120 | BasicDecimal128(2710505431213761085LL, 343699775700336640ULL)}; |
121 | |
122 | static constexpr uint64_t kIntMask = 0xFFFFFFFF; |
123 | static constexpr auto kCarryBit = static_cast<uint64_t>(1) << static_cast<uint64_t>(32); |
124 | |
125 | BasicDecimal128::BasicDecimal128(const uint8_t* bytes) |
126 | : BasicDecimal128( |
127 | BitUtil::FromLittleEndian(reinterpret_cast<const int64_t*>(bytes)[1]), |
128 | BitUtil::FromLittleEndian(reinterpret_cast<const uint64_t*>(bytes)[0])) {} |
129 | |
130 | std::array<uint8_t, 16> BasicDecimal128::ToBytes() const { |
131 | std::array<uint8_t, 16> out{{0}}; |
132 | ToBytes(out.data()); |
133 | return out; |
134 | } |
135 | |
136 | void BasicDecimal128::ToBytes(uint8_t* out) const { |
137 | DCHECK_NE(out, nullptr); |
138 | reinterpret_cast<uint64_t*>(out)[0] = BitUtil::ToLittleEndian(low_bits_); |
139 | reinterpret_cast<int64_t*>(out)[1] = BitUtil::ToLittleEndian(high_bits_); |
140 | } |
141 | |
142 | BasicDecimal128& BasicDecimal128::Negate() { |
143 | low_bits_ = ~low_bits_ + 1; |
144 | high_bits_ = ~high_bits_; |
145 | if (low_bits_ == 0) { |
146 | high_bits_ = SafeSignedAdd<int64_t>(high_bits_, 1); |
147 | } |
148 | return *this; |
149 | } |
150 | |
151 | BasicDecimal128& BasicDecimal128::Abs() { return *this < 0 ? Negate() : *this; } |
152 | |
153 | BasicDecimal128& BasicDecimal128::operator+=(const BasicDecimal128& right) { |
154 | const uint64_t sum = low_bits_ + right.low_bits_; |
155 | high_bits_ = SafeSignedAdd<int64_t>(high_bits_, right.high_bits_); |
156 | if (sum < low_bits_) { |
157 | high_bits_ = SafeSignedAdd<int64_t>(high_bits_, 1); |
158 | } |
159 | low_bits_ = sum; |
160 | return *this; |
161 | } |
162 | |
163 | BasicDecimal128& BasicDecimal128::operator-=(const BasicDecimal128& right) { |
164 | const uint64_t diff = low_bits_ - right.low_bits_; |
165 | high_bits_ -= right.high_bits_; |
166 | if (diff > low_bits_) { |
167 | --high_bits_; |
168 | } |
169 | low_bits_ = diff; |
170 | return *this; |
171 | } |
172 | |
173 | BasicDecimal128& BasicDecimal128::operator/=(const BasicDecimal128& right) { |
174 | BasicDecimal128 remainder; |
175 | auto s = Divide(right, this, &remainder); |
176 | DCHECK_EQ(s, DecimalStatus::kSuccess); |
177 | return *this; |
178 | } |
179 | |
180 | BasicDecimal128& BasicDecimal128::operator|=(const BasicDecimal128& right) { |
181 | low_bits_ |= right.low_bits_; |
182 | high_bits_ |= right.high_bits_; |
183 | return *this; |
184 | } |
185 | |
186 | BasicDecimal128& BasicDecimal128::operator&=(const BasicDecimal128& right) { |
187 | low_bits_ &= right.low_bits_; |
188 | high_bits_ &= right.high_bits_; |
189 | return *this; |
190 | } |
191 | |
192 | BasicDecimal128& BasicDecimal128::operator<<=(uint32_t bits) { |
193 | if (bits != 0) { |
194 | if (bits < 64) { |
195 | high_bits_ = SafeLeftShift(high_bits_, bits); |
196 | high_bits_ |= (low_bits_ >> (64 - bits)); |
197 | low_bits_ <<= bits; |
198 | } else if (bits < 128) { |
199 | high_bits_ = static_cast<int64_t>(low_bits_) << (bits - 64); |
200 | low_bits_ = 0; |
201 | } else { |
202 | high_bits_ = 0; |
203 | low_bits_ = 0; |
204 | } |
205 | } |
206 | return *this; |
207 | } |
208 | |
209 | BasicDecimal128& BasicDecimal128::operator>>=(uint32_t bits) { |
210 | if (bits != 0) { |
211 | if (bits < 64) { |
212 | low_bits_ >>= bits; |
213 | low_bits_ |= static_cast<uint64_t>(high_bits_ << (64 - bits)); |
214 | high_bits_ = static_cast<int64_t>(static_cast<uint64_t>(high_bits_) >> bits); |
215 | } else if (bits < 128) { |
216 | low_bits_ = static_cast<uint64_t>(high_bits_ >> (bits - 64)); |
217 | high_bits_ = static_cast<int64_t>(high_bits_ >= 0L ? 0L : -1L); |
218 | } else { |
219 | high_bits_ = static_cast<int64_t>(high_bits_ >= 0L ? 0L : -1L); |
220 | low_bits_ = static_cast<uint64_t>(high_bits_); |
221 | } |
222 | } |
223 | return *this; |
224 | } |
225 | |
226 | BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) { |
227 | // Break the left and right numbers into 32 bit chunks |
228 | // so that we can multiply them without overflow. |
229 | const uint64_t L0 = static_cast<uint64_t>(high_bits_) >> 32; |
230 | const uint64_t L1 = static_cast<uint64_t>(high_bits_) & kIntMask; |
231 | const uint64_t L2 = low_bits_ >> 32; |
232 | const uint64_t L3 = low_bits_ & kIntMask; |
233 | |
234 | const uint64_t R0 = static_cast<uint64_t>(right.high_bits_) >> 32; |
235 | const uint64_t R1 = static_cast<uint64_t>(right.high_bits_) & kIntMask; |
236 | const uint64_t R2 = right.low_bits_ >> 32; |
237 | const uint64_t R3 = right.low_bits_ & kIntMask; |
238 | |
239 | uint64_t product = L3 * R3; |
240 | low_bits_ = product & kIntMask; |
241 | |
242 | uint64_t sum = product >> 32; |
243 | |
244 | product = L2 * R3; |
245 | sum += product; |
246 | |
247 | product = L3 * R2; |
248 | sum += product; |
249 | |
250 | low_bits_ += sum << 32; |
251 | |
252 | high_bits_ = static_cast<int64_t>(sum < product ? kCarryBit : 0); |
253 | if (sum < product) { |
254 | high_bits_ += kCarryBit; |
255 | } |
256 | |
257 | high_bits_ += static_cast<int64_t>(sum >> 32); |
258 | high_bits_ += L1 * R3 + L2 * R2 + L3 * R1; |
259 | high_bits_ += (L0 * R3 + L1 * R2 + L2 * R1 + L3 * R0) << 32; |
260 | return *this; |
261 | } |
262 | |
263 | /// Expands the given value into an array of ints so that we can work on |
264 | /// it. The array will be converted to an absolute value and the wasNegative |
265 | /// flag will be set appropriately. The array will remove leading zeros from |
266 | /// the value. |
267 | /// \param array an array of length 4 to set with the value |
268 | /// \param was_negative a flag for whether the value was original negative |
269 | /// \result the output length of the array |
270 | static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array, |
271 | bool& was_negative) { |
272 | uint64_t high; |
273 | uint64_t low; |
274 | const int64_t highbits = value.high_bits(); |
275 | const uint64_t lowbits = value.low_bits(); |
276 | |
277 | if (highbits < 0) { |
278 | low = ~lowbits + 1; |
279 | high = static_cast<uint64_t>(~highbits); |
280 | if (low == 0) { |
281 | ++high; |
282 | } |
283 | was_negative = true; |
284 | } else { |
285 | low = lowbits; |
286 | high = static_cast<uint64_t>(highbits); |
287 | was_negative = false; |
288 | } |
289 | |
290 | if (high != 0) { |
291 | if (high > std::numeric_limits<uint32_t>::max()) { |
292 | array[0] = static_cast<uint32_t>(high >> 32); |
293 | array[1] = static_cast<uint32_t>(high); |
294 | array[2] = static_cast<uint32_t>(low >> 32); |
295 | array[3] = static_cast<uint32_t>(low); |
296 | return 4; |
297 | } |
298 | |
299 | array[0] = static_cast<uint32_t>(high); |
300 | array[1] = static_cast<uint32_t>(low >> 32); |
301 | array[2] = static_cast<uint32_t>(low); |
302 | return 3; |
303 | } |
304 | |
305 | if (low >= std::numeric_limits<uint32_t>::max()) { |
306 | array[0] = static_cast<uint32_t>(low >> 32); |
307 | array[1] = static_cast<uint32_t>(low); |
308 | return 2; |
309 | } |
310 | |
311 | if (low == 0) { |
312 | return 0; |
313 | } |
314 | |
315 | array[0] = static_cast<uint32_t>(low); |
316 | return 1; |
317 | } |
318 | |
319 | /// Shift the number in the array left by bits positions. |
320 | /// \param array the number to shift, must have length elements |
321 | /// \param length the number of entries in the array |
322 | /// \param bits the number of bits to shift (0 <= bits < 32) |
323 | static void ShiftArrayLeft(uint32_t* array, int64_t length, int64_t bits) { |
324 | if (length > 0 && bits != 0) { |
325 | for (int64_t i = 0; i < length - 1; ++i) { |
326 | array[i] = (array[i] << bits) | (array[i + 1] >> (32 - bits)); |
327 | } |
328 | array[length - 1] <<= bits; |
329 | } |
330 | } |
331 | |
332 | /// Shift the number in the array right by bits positions. |
333 | /// \param array the number to shift, must have length elements |
334 | /// \param length the number of entries in the array |
335 | /// \param bits the number of bits to shift (0 <= bits < 32) |
336 | static void ShiftArrayRight(uint32_t* array, int64_t length, int64_t bits) { |
337 | if (length > 0 && bits != 0) { |
338 | for (int64_t i = length - 1; i > 0; --i) { |
339 | array[i] = (array[i] >> bits) | (array[i - 1] << (32 - bits)); |
340 | } |
341 | array[0] >>= bits; |
342 | } |
343 | } |
344 | |
345 | /// \brief Fix the signs of the result and remainder at the end of the division based on |
346 | /// the signs of the dividend and divisor. |
347 | static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder, |
348 | bool dividend_was_negative, bool divisor_was_negative) { |
349 | if (dividend_was_negative != divisor_was_negative) { |
350 | result->Negate(); |
351 | } |
352 | |
353 | if (dividend_was_negative) { |
354 | remainder->Negate(); |
355 | } |
356 | } |
357 | |
358 | /// \brief Build a BasicDecimal128 from a list of ints. |
359 | static DecimalStatus BuildFromArray(BasicDecimal128* value, uint32_t* array, |
360 | int64_t length) { |
361 | switch (length) { |
362 | case 0: |
363 | *value = {static_cast<int64_t>(0)}; |
364 | break; |
365 | case 1: |
366 | *value = {static_cast<int64_t>(array[0])}; |
367 | break; |
368 | case 2: |
369 | *value = {static_cast<int64_t>(0), |
370 | (static_cast<uint64_t>(array[0]) << 32) + array[1]}; |
371 | break; |
372 | case 3: |
373 | *value = {static_cast<int64_t>(array[0]), |
374 | (static_cast<uint64_t>(array[1]) << 32) + array[2]}; |
375 | break; |
376 | case 4: |
377 | *value = {(static_cast<int64_t>(array[0]) << 32) + array[1], |
378 | (static_cast<uint64_t>(array[2]) << 32) + array[3]}; |
379 | break; |
380 | case 5: |
381 | if (array[0] != 0) { |
382 | return DecimalStatus::kOverflow; |
383 | } |
384 | *value = {(static_cast<int64_t>(array[1]) << 32) + array[2], |
385 | (static_cast<uint64_t>(array[3]) << 32) + array[4]}; |
386 | break; |
387 | default: |
388 | return DecimalStatus::kOverflow; |
389 | } |
390 | |
391 | return DecimalStatus::kSuccess; |
392 | } |
393 | |
394 | /// \brief Do a division where the divisor fits into a single 32 bit value. |
395 | static DecimalStatus SingleDivide(const uint32_t* dividend, int64_t dividend_length, |
396 | uint32_t divisor, BasicDecimal128* remainder, |
397 | bool dividend_was_negative, bool divisor_was_negative, |
398 | BasicDecimal128* result) { |
399 | uint64_t r = 0; |
400 | uint32_t result_array[5]; |
401 | for (int64_t j = 0; j < dividend_length; j++) { |
402 | r <<= 32; |
403 | r += dividend[j]; |
404 | result_array[j] = static_cast<uint32_t>(r / divisor); |
405 | r %= divisor; |
406 | } |
407 | auto status = BuildFromArray(result, result_array, dividend_length); |
408 | if (status != DecimalStatus::kSuccess) { |
409 | return status; |
410 | } |
411 | |
412 | *remainder = static_cast<int64_t>(r); |
413 | FixDivisionSigns(result, remainder, dividend_was_negative, divisor_was_negative); |
414 | return DecimalStatus::kSuccess; |
415 | } |
416 | |
417 | DecimalStatus BasicDecimal128::Divide(const BasicDecimal128& divisor, |
418 | BasicDecimal128* result, |
419 | BasicDecimal128* remainder) const { |
420 | // Split the dividend and divisor into integer pieces so that we can |
421 | // work on them. |
422 | uint32_t dividend_array[5]; |
423 | uint32_t divisor_array[4]; |
424 | bool dividend_was_negative; |
425 | bool divisor_was_negative; |
426 | // leave an extra zero before the dividend |
427 | dividend_array[0] = 0; |
428 | int64_t dividend_length = |
429 | FillInArray(*this, dividend_array + 1, dividend_was_negative) + 1; |
430 | int64_t divisor_length = FillInArray(divisor, divisor_array, divisor_was_negative); |
431 | |
432 | // Handle some of the easy cases. |
433 | if (dividend_length <= divisor_length) { |
434 | *remainder = *this; |
435 | *result = 0; |
436 | return DecimalStatus::kSuccess; |
437 | } |
438 | |
439 | if (divisor_length == 0) { |
440 | return DecimalStatus::kDivideByZero; |
441 | } |
442 | |
443 | if (divisor_length == 1) { |
444 | return SingleDivide(dividend_array, dividend_length, divisor_array[0], remainder, |
445 | dividend_was_negative, divisor_was_negative, result); |
446 | } |
447 | |
448 | int64_t result_length = dividend_length - divisor_length; |
449 | uint32_t result_array[4]; |
450 | |
451 | // Normalize by shifting both by a multiple of 2 so that |
452 | // the digit guessing is better. The requirement is that |
453 | // divisor_array[0] is greater than 2**31. |
454 | int64_t normalize_bits = BitUtil::CountLeadingZeros(divisor_array[0]); |
455 | ShiftArrayLeft(divisor_array, divisor_length, normalize_bits); |
456 | ShiftArrayLeft(dividend_array, dividend_length, normalize_bits); |
457 | |
458 | // compute each digit in the result |
459 | for (int64_t j = 0; j < result_length; ++j) { |
460 | // Guess the next digit. At worst it is two too large |
461 | uint32_t guess = std::numeric_limits<uint32_t>::max(); |
462 | const auto high_dividend = |
463 | static_cast<uint64_t>(dividend_array[j]) << 32 | dividend_array[j + 1]; |
464 | if (dividend_array[j] != divisor_array[0]) { |
465 | guess = static_cast<uint32_t>(high_dividend / divisor_array[0]); |
466 | } |
467 | |
468 | // catch all of the cases where guess is two too large and most of the |
469 | // cases where it is one too large |
470 | auto rhat = static_cast<uint32_t>(high_dividend - |
471 | guess * static_cast<uint64_t>(divisor_array[0])); |
472 | while (static_cast<uint64_t>(divisor_array[1]) * guess > |
473 | (static_cast<uint64_t>(rhat) << 32) + dividend_array[j + 2]) { |
474 | --guess; |
475 | rhat += divisor_array[0]; |
476 | if (static_cast<uint64_t>(rhat) < divisor_array[0]) { |
477 | break; |
478 | } |
479 | } |
480 | |
481 | // subtract off the guess * divisor from the dividend |
482 | uint64_t mult = 0; |
483 | for (int64_t i = divisor_length - 1; i >= 0; --i) { |
484 | mult += static_cast<uint64_t>(guess) * divisor_array[i]; |
485 | uint32_t prev = dividend_array[j + i + 1]; |
486 | dividend_array[j + i + 1] -= static_cast<uint32_t>(mult); |
487 | mult >>= 32; |
488 | if (dividend_array[j + i + 1] > prev) { |
489 | ++mult; |
490 | } |
491 | } |
492 | uint32_t prev = dividend_array[j]; |
493 | dividend_array[j] -= static_cast<uint32_t>(mult); |
494 | |
495 | // if guess was too big, we add back divisor |
496 | if (dividend_array[j] > prev) { |
497 | --guess; |
498 | uint32_t carry = 0; |
499 | for (int64_t i = divisor_length - 1; i >= 0; --i) { |
500 | const auto sum = |
501 | static_cast<uint64_t>(divisor_array[i]) + dividend_array[j + i + 1] + carry; |
502 | dividend_array[j + i + 1] = static_cast<uint32_t>(sum); |
503 | carry = static_cast<uint32_t>(sum >> 32); |
504 | } |
505 | dividend_array[j] += carry; |
506 | } |
507 | |
508 | result_array[j] = guess; |
509 | } |
510 | |
511 | // denormalize the remainder |
512 | ShiftArrayRight(dividend_array, dividend_length, normalize_bits); |
513 | |
514 | // return result and remainder |
515 | auto status = BuildFromArray(result, result_array, result_length); |
516 | if (status != DecimalStatus::kSuccess) { |
517 | return status; |
518 | } |
519 | status = BuildFromArray(remainder, dividend_array, dividend_length); |
520 | if (status != DecimalStatus::kSuccess) { |
521 | return status; |
522 | } |
523 | |
524 | FixDivisionSigns(result, remainder, dividend_was_negative, divisor_was_negative); |
525 | return DecimalStatus::kSuccess; |
526 | } |
527 | |
528 | bool operator==(const BasicDecimal128& left, const BasicDecimal128& right) { |
529 | return left.high_bits() == right.high_bits() && left.low_bits() == right.low_bits(); |
530 | } |
531 | |
532 | bool operator!=(const BasicDecimal128& left, const BasicDecimal128& right) { |
533 | return !operator==(left, right); |
534 | } |
535 | |
536 | bool operator<(const BasicDecimal128& left, const BasicDecimal128& right) { |
537 | return left.high_bits() < right.high_bits() || |
538 | (left.high_bits() == right.high_bits() && left.low_bits() < right.low_bits()); |
539 | } |
540 | |
541 | bool operator<=(const BasicDecimal128& left, const BasicDecimal128& right) { |
542 | return !operator>(left, right); |
543 | } |
544 | |
545 | bool operator>(const BasicDecimal128& left, const BasicDecimal128& right) { |
546 | return operator<(right, left); |
547 | } |
548 | |
549 | bool operator>=(const BasicDecimal128& left, const BasicDecimal128& right) { |
550 | return !operator<(left, right); |
551 | } |
552 | |
553 | BasicDecimal128 operator-(const BasicDecimal128& operand) { |
554 | BasicDecimal128 result(operand.high_bits(), operand.low_bits()); |
555 | return result.Negate(); |
556 | } |
557 | |
558 | BasicDecimal128 operator~(const BasicDecimal128& operand) { |
559 | BasicDecimal128 result(~operand.high_bits(), ~operand.low_bits()); |
560 | return result; |
561 | } |
562 | |
563 | BasicDecimal128 operator+(const BasicDecimal128& left, const BasicDecimal128& right) { |
564 | BasicDecimal128 result(left.high_bits(), left.low_bits()); |
565 | result += right; |
566 | return result; |
567 | } |
568 | |
569 | BasicDecimal128 operator-(const BasicDecimal128& left, const BasicDecimal128& right) { |
570 | BasicDecimal128 result(left.high_bits(), left.low_bits()); |
571 | result -= right; |
572 | return result; |
573 | } |
574 | |
575 | BasicDecimal128 operator*(const BasicDecimal128& left, const BasicDecimal128& right) { |
576 | BasicDecimal128 result(left.high_bits(), left.low_bits()); |
577 | result *= right; |
578 | return result; |
579 | } |
580 | |
581 | BasicDecimal128 operator/(const BasicDecimal128& left, const BasicDecimal128& right) { |
582 | BasicDecimal128 remainder; |
583 | BasicDecimal128 result; |
584 | auto s = left.Divide(right, &result, &remainder); |
585 | DCHECK_EQ(s, DecimalStatus::kSuccess); |
586 | return result; |
587 | } |
588 | |
589 | BasicDecimal128 operator%(const BasicDecimal128& left, const BasicDecimal128& right) { |
590 | BasicDecimal128 remainder; |
591 | BasicDecimal128 result; |
592 | auto s = left.Divide(right, &result, &remainder); |
593 | DCHECK_EQ(s, DecimalStatus::kSuccess); |
594 | return remainder; |
595 | } |
596 | |
597 | static bool RescaleWouldCauseDataLoss(const BasicDecimal128& value, int32_t delta_scale, |
598 | int32_t abs_delta_scale, BasicDecimal128* result) { |
599 | BasicDecimal128 multiplier(ScaleMultipliers[abs_delta_scale]); |
600 | |
601 | if (delta_scale < 0) { |
602 | DCHECK_NE(multiplier, 0); |
603 | BasicDecimal128 remainder; |
604 | auto status = value.Divide(multiplier, result, &remainder); |
605 | DCHECK_EQ(status, DecimalStatus::kSuccess); |
606 | return remainder != 0; |
607 | } |
608 | |
609 | *result = value * multiplier; |
610 | return (value < 0) ? *result > value : *result < value; |
611 | } |
612 | |
613 | DecimalStatus BasicDecimal128::Rescale(int32_t original_scale, int32_t new_scale, |
614 | BasicDecimal128* out) const { |
615 | DCHECK_NE(out, nullptr); |
616 | DCHECK_NE(original_scale, new_scale); |
617 | |
618 | const int32_t delta_scale = new_scale - original_scale; |
619 | const int32_t abs_delta_scale = std::abs(delta_scale); |
620 | |
621 | DCHECK_GE(abs_delta_scale, 1); |
622 | DCHECK_LE(abs_delta_scale, 38); |
623 | |
624 | BasicDecimal128 result(*this); |
625 | const bool rescale_would_cause_data_loss = |
626 | RescaleWouldCauseDataLoss(result, delta_scale, abs_delta_scale, out); |
627 | |
628 | // Fail if we overflow or truncate |
629 | if (ARROW_PREDICT_FALSE(rescale_would_cause_data_loss)) { |
630 | return DecimalStatus::kRescaleDataLoss; |
631 | } |
632 | |
633 | return DecimalStatus::kSuccess; |
634 | } |
635 | |
636 | void BasicDecimal128::GetWholeAndFraction(int scale, BasicDecimal128* whole, |
637 | BasicDecimal128* fraction) const { |
638 | DCHECK_GE(scale, 0); |
639 | DCHECK_LE(scale, 38); |
640 | |
641 | BasicDecimal128 multiplier(ScaleMultipliers[scale]); |
642 | DCHECK_EQ(Divide(multiplier, whole, fraction), DecimalStatus::kSuccess); |
643 | } |
644 | |
645 | const BasicDecimal128& BasicDecimal128::GetScaleMultiplier(int32_t scale) { |
646 | DCHECK_GE(scale, 0); |
647 | DCHECK_LE(scale, 38); |
648 | |
649 | return ScaleMultipliers[scale]; |
650 | } |
651 | |
652 | BasicDecimal128 BasicDecimal128::IncreaseScaleBy(int32_t increase_by) const { |
653 | DCHECK_GE(increase_by, 0); |
654 | DCHECK_LE(increase_by, 38); |
655 | |
656 | return (*this) * ScaleMultipliers[increase_by]; |
657 | } |
658 | |
659 | BasicDecimal128 BasicDecimal128::ReduceScaleBy(int32_t reduce_by, bool round) const { |
660 | DCHECK_GE(reduce_by, 0); |
661 | DCHECK_LE(reduce_by, 38); |
662 | |
663 | BasicDecimal128 divisor(ScaleMultipliers[reduce_by]); |
664 | BasicDecimal128 result; |
665 | BasicDecimal128 remainder; |
666 | DCHECK_EQ(Divide(divisor, &result, &remainder), DecimalStatus::kSuccess); |
667 | if (round) { |
668 | auto divisor_half = ScaleMultipliersHalf[reduce_by]; |
669 | if (remainder.Abs() >= divisor_half) { |
670 | if (result > 0) { |
671 | result += 1; |
672 | } else { |
673 | result -= 1; |
674 | } |
675 | } |
676 | } |
677 | return result; |
678 | } |
679 | |
680 | int32_t BasicDecimal128::CountLeadingBinaryZeros() const { |
681 | DCHECK_GE(*this, BasicDecimal128(0)); |
682 | |
683 | if (high_bits_ == 0) { |
684 | return BitUtil::CountLeadingZeros(low_bits_) + 64; |
685 | } else { |
686 | return BitUtil::CountLeadingZeros(static_cast<uint64_t>(high_bits_)); |
687 | } |
688 | } |
689 | |
690 | } // namespace arrow |
691 | |