1#include "duckdb/common/operator/multiply.hpp"
2
3#include "duckdb/common/limits.hpp"
4#include "duckdb/common/types/hugeint.hpp"
5#include "duckdb/common/types/value.hpp"
6#include "duckdb/common/windows_undefs.hpp"
7
8#include <limits>
9#include <algorithm>
10
11namespace duckdb {
12
13//===--------------------------------------------------------------------===//
14// * [multiply]
15//===--------------------------------------------------------------------===//
16template <>
17float MultiplyOperator::Operation(float left, float right) {
18 auto result = left * right;
19 return result;
20}
21
22template <>
23double MultiplyOperator::Operation(double left, double right) {
24 auto result = left * right;
25 return result;
26}
27
28template <>
29interval_t MultiplyOperator::Operation(interval_t left, int64_t right) {
30 left.months = MultiplyOperatorOverflowCheck::Operation<int32_t, int32_t, int32_t>(left: left.months, right);
31 left.days = MultiplyOperatorOverflowCheck::Operation<int32_t, int32_t, int32_t>(left: left.days, right);
32 left.micros = MultiplyOperatorOverflowCheck::Operation<int64_t, int64_t, int64_t>(left: left.micros, right);
33 return left;
34}
35
36template <>
37interval_t MultiplyOperator::Operation(int64_t left, interval_t right) {
38 return MultiplyOperator::Operation<interval_t, int64_t, interval_t>(left: right, right: left);
39}
40
41//===--------------------------------------------------------------------===//
42// * [multiply] with overflow check
43//===--------------------------------------------------------------------===//
44struct OverflowCheckedMultiply {
45 template <class SRCTYPE, class UTYPE>
46 static inline bool Operation(SRCTYPE left, SRCTYPE right, SRCTYPE &result) {
47 UTYPE uresult = MultiplyOperator::Operation<UTYPE, UTYPE, UTYPE>(UTYPE(left), UTYPE(right));
48 if (uresult < NumericLimits<SRCTYPE>::Minimum() || uresult > NumericLimits<SRCTYPE>::Maximum()) {
49 return false;
50 }
51 result = SRCTYPE(uresult);
52 return true;
53 }
54};
55
56template <>
57bool TryMultiplyOperator::Operation(uint8_t left, uint8_t right, uint8_t &result) {
58 return OverflowCheckedMultiply::Operation<uint8_t, uint16_t>(left, right, result);
59}
60template <>
61bool TryMultiplyOperator::Operation(uint16_t left, uint16_t right, uint16_t &result) {
62 return OverflowCheckedMultiply::Operation<uint16_t, uint32_t>(left, right, result);
63}
64template <>
65bool TryMultiplyOperator::Operation(uint32_t left, uint32_t right, uint32_t &result) {
66 return OverflowCheckedMultiply::Operation<uint32_t, uint64_t>(left, right, result);
67}
68template <>
69bool TryMultiplyOperator::Operation(uint64_t left, uint64_t right, uint64_t &result) {
70 if (left > right) {
71 std::swap(a&: left, b&: right);
72 }
73 if (left > NumericLimits<uint32_t>::Maximum()) {
74 return false;
75 }
76 uint32_t c = right >> 32;
77 uint32_t d = NumericLimits<uint32_t>::Maximum() & right;
78 uint64_t r = left * c;
79 uint64_t s = left * d;
80 if (r > NumericLimits<uint32_t>::Maximum()) {
81 return false;
82 }
83 r <<= 32;
84 if (NumericLimits<uint64_t>::Maximum() - s < r) {
85 return false;
86 }
87 return OverflowCheckedMultiply::Operation<uint64_t, uint64_t>(left, right, result);
88}
89
90template <>
91bool TryMultiplyOperator::Operation(int8_t left, int8_t right, int8_t &result) {
92 return OverflowCheckedMultiply::Operation<int8_t, int16_t>(left, right, result);
93}
94
95template <>
96bool TryMultiplyOperator::Operation(int16_t left, int16_t right, int16_t &result) {
97 return OverflowCheckedMultiply::Operation<int16_t, int32_t>(left, right, result);
98}
99
100template <>
101bool TryMultiplyOperator::Operation(int32_t left, int32_t right, int32_t &result) {
102 return OverflowCheckedMultiply::Operation<int32_t, int64_t>(left, right, result);
103}
104
105template <>
106bool TryMultiplyOperator::Operation(int64_t left, int64_t right, int64_t &result) {
107#if (__GNUC__ >= 5) || defined(__clang__)
108 if (__builtin_mul_overflow(left, right, &result)) {
109 return false;
110 }
111#else
112 if (left == std::numeric_limits<int64_t>::min()) {
113 if (right == 0) {
114 result = 0;
115 return true;
116 }
117 if (right == 1) {
118 result = left;
119 return true;
120 }
121 return false;
122 }
123 if (right == std::numeric_limits<int64_t>::min()) {
124 if (left == 0) {
125 result = 0;
126 return true;
127 }
128 if (left == 1) {
129 result = right;
130 return true;
131 }
132 return false;
133 }
134 uint64_t left_non_negative = uint64_t(std::abs(left));
135 uint64_t right_non_negative = uint64_t(std::abs(right));
136 // split values into 2 32-bit parts
137 uint64_t left_high_bits = left_non_negative >> 32;
138 uint64_t left_low_bits = left_non_negative & 0xffffffff;
139 uint64_t right_high_bits = right_non_negative >> 32;
140 uint64_t right_low_bits = right_non_negative & 0xffffffff;
141
142 // check the high bits of both
143 // the high bits define the overflow
144 if (left_high_bits == 0) {
145 if (right_high_bits != 0) {
146 // only the right has high bits set
147 // multiply the high bits of right with the low bits of left
148 // multiply the low bits, and carry any overflow to the high bits
149 // then check for any overflow
150 auto low_low = left_low_bits * right_low_bits;
151 auto low_high = left_low_bits * right_high_bits;
152 auto high_bits = low_high + (low_low >> 32);
153 if (high_bits & 0xffffff80000000) {
154 // there is! abort
155 return false;
156 }
157 }
158 } else if (right_high_bits == 0) {
159 // only the left has high bits set
160 // multiply the high bits of left with the low bits of right
161 // multiply the low bits, and carry any overflow to the high bits
162 // then check for any overflow
163 auto low_low = left_low_bits * right_low_bits;
164 auto high_low = left_high_bits * right_low_bits;
165 auto high_bits = high_low + (low_low >> 32);
166 if (high_bits & 0xffffff80000000) {
167 // there is! abort
168 return false;
169 }
170 } else {
171 // both left and right have high bits set: guaranteed overflow
172 // abort!
173 return false;
174 }
175 // now we know that there is no overflow, we can just perform the multiplication
176 result = left * right;
177#endif
178 return true;
179}
180
181template <>
182bool TryMultiplyOperator::Operation(hugeint_t left, hugeint_t right, hugeint_t &result) {
183 return Hugeint::TryMultiply(lhs: left, rhs: right, result);
184}
185
186//===--------------------------------------------------------------------===//
187// multiply decimal with overflow check
188//===--------------------------------------------------------------------===//
189template <class T, T min, T max>
190bool TryDecimalMultiplyTemplated(T left, T right, T &result) {
191 if (!TryMultiplyOperator::Operation(left, right, result) || result < min || result > max) {
192 return false;
193 }
194 return true;
195}
196
197template <>
198bool TryDecimalMultiply::Operation(int16_t left, int16_t right, int16_t &result) {
199 return TryDecimalMultiplyTemplated<int16_t, -9999, 9999>(left, right, result);
200}
201
202template <>
203bool TryDecimalMultiply::Operation(int32_t left, int32_t right, int32_t &result) {
204 return TryDecimalMultiplyTemplated<int32_t, -999999999, 999999999>(left, right, result);
205}
206
207template <>
208bool TryDecimalMultiply::Operation(int64_t left, int64_t right, int64_t &result) {
209 return TryDecimalMultiplyTemplated<int64_t, -999999999999999999, 999999999999999999>(left, right, result);
210}
211
212template <>
213bool TryDecimalMultiply::Operation(hugeint_t left, hugeint_t right, hugeint_t &result) {
214 result = left * right;
215 if (result <= -Hugeint::POWERS_OF_TEN[38] || result >= Hugeint::POWERS_OF_TEN[38]) {
216 return false;
217 }
218 return true;
219}
220
221template <>
222hugeint_t DecimalMultiplyOverflowCheck::Operation(hugeint_t left, hugeint_t right) {
223 hugeint_t result;
224 if (!TryDecimalMultiply::Operation(left, right, result)) {
225 throw OutOfRangeException("Overflow in multiplication of DECIMAL(38) (%s * %s). You might want to add an "
226 "explicit cast to a decimal with a smaller scale.",
227 left.ToString(), right.ToString());
228 }
229 return result;
230}
231
232} // namespace duckdb
233