1 // Copyright 2017 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef BASE_ALLOCATOR_PARTITION_ALLOCATOR_SRC_PARTITION_ALLOC_PARTITION_ALLOC_BASE_NUMERICS_CLAMPED_MATH_IMPL_H_
6 #define BASE_ALLOCATOR_PARTITION_ALLOCATOR_SRC_PARTITION_ALLOC_PARTITION_ALLOC_BASE_NUMERICS_CLAMPED_MATH_IMPL_H_
7
8 #include <stddef.h>
9 #include <stdint.h>
10
11 #include <climits>
12 #include <cmath>
13 #include <cstdlib>
14 #include <limits>
15 #include <type_traits>
16
17 #include "partition_alloc/partition_alloc_base/numerics/checked_math.h"
18 #include "partition_alloc/partition_alloc_base/numerics/safe_conversions.h"
19 #include "partition_alloc/partition_alloc_base/numerics/safe_math_shared_impl.h"
20
21 namespace partition_alloc::internal::base::internal {
22
23 template <typename T,
24 typename std::enable_if<std::is_integral_v<T> &&
25 std::is_signed_v<T>>::type* = nullptr>
SaturatedNegWrapper(T value)26 constexpr T SaturatedNegWrapper(T value) {
27 return PA_IsConstantEvaluated() || !ClampedNegFastOp<T>::is_supported
28 ? (NegateWrapper(value) != std::numeric_limits<T>::lowest()
29 ? NegateWrapper(value)
30 : std::numeric_limits<T>::max())
31 : ClampedNegFastOp<T>::Do(value);
32 }
33
34 template <typename T,
35 typename std::enable_if<std::is_integral_v<T> &&
36 !std::is_signed_v<T>>::type* = nullptr>
SaturatedNegWrapper(T value)37 constexpr T SaturatedNegWrapper(T value) {
38 return T(0);
39 }
40
41 template <typename T,
42 typename std::enable_if<std::is_floating_point_v<T>>::type* = nullptr>
SaturatedNegWrapper(T value)43 constexpr T SaturatedNegWrapper(T value) {
44 return -value;
45 }
46
47 template <typename T,
48 typename std::enable_if<std::is_integral_v<T>>::type* = nullptr>
SaturatedAbsWrapper(T value)49 constexpr T SaturatedAbsWrapper(T value) {
50 // The calculation below is a static identity for unsigned types, but for
51 // signed integer types it provides a non-branching, saturated absolute value.
52 // This works because SafeUnsignedAbs() returns an unsigned type, which can
53 // represent the absolute value of all negative numbers of an equal-width
54 // integer type. The call to IsValueNegative() then detects overflow in the
55 // special case of numeric_limits<T>::min(), by evaluating the bit pattern as
56 // a signed integer value. If it is the overflow case, we end up subtracting
57 // one from the unsigned result, thus saturating to numeric_limits<T>::max().
58 return static_cast<T>(
59 SafeUnsignedAbs(value) -
60 IsValueNegative<T>(static_cast<T>(SafeUnsignedAbs(value))));
61 }
62
63 template <typename T,
64 typename std::enable_if<std::is_floating_point_v<T>>::type* = nullptr>
SaturatedAbsWrapper(T value)65 constexpr T SaturatedAbsWrapper(T value) {
66 return value < 0 ? -value : value;
67 }
68
69 template <typename T, typename U, class Enable = void>
70 struct ClampedAddOp {};
71
72 template <typename T, typename U>
73 struct ClampedAddOp<T,
74 U,
75 typename std::enable_if<std::is_integral_v<T> &&
76 std::is_integral_v<U>>::type> {
77 using result_type = typename MaxExponentPromotion<T, U>::type;
78 template <typename V = result_type>
79 static constexpr V Do(T x, U y) {
80 if (!PA_IsConstantEvaluated() && ClampedAddFastOp<T, U>::is_supported) {
81 return ClampedAddFastOp<T, U>::template Do<V>(x, y);
82 }
83
84 static_assert(std::is_same_v<V, result_type> ||
85 IsTypeInRangeForNumericType<U, V>::value,
86 "The saturation result cannot be determined from the "
87 "provided types.");
88 const V saturated = CommonMaxOrMin<V>(IsValueNegative(y));
89 V result = {};
90 return PA_BASE_NUMERICS_LIKELY((CheckedAddOp<T, U>::Do(x, y, &result)))
91 ? result
92 : saturated;
93 }
94 };
95
96 template <typename T, typename U, class Enable = void>
97 struct ClampedSubOp {};
98
99 template <typename T, typename U>
100 struct ClampedSubOp<T,
101 U,
102 typename std::enable_if<std::is_integral_v<T> &&
103 std::is_integral_v<U>>::type> {
104 using result_type = typename MaxExponentPromotion<T, U>::type;
105 template <typename V = result_type>
106 static constexpr V Do(T x, U y) {
107 if (!PA_IsConstantEvaluated() && ClampedSubFastOp<T, U>::is_supported) {
108 return ClampedSubFastOp<T, U>::template Do<V>(x, y);
109 }
110
111 static_assert(std::is_same_v<V, result_type> ||
112 IsTypeInRangeForNumericType<U, V>::value,
113 "The saturation result cannot be determined from the "
114 "provided types.");
115 const V saturated = CommonMaxOrMin<V>(!IsValueNegative(y));
116 V result = {};
117 return PA_BASE_NUMERICS_LIKELY((CheckedSubOp<T, U>::Do(x, y, &result)))
118 ? result
119 : saturated;
120 }
121 };
122
123 template <typename T, typename U, class Enable = void>
124 struct ClampedMulOp {};
125
126 template <typename T, typename U>
127 struct ClampedMulOp<T,
128 U,
129 typename std::enable_if<std::is_integral_v<T> &&
130 std::is_integral_v<U>>::type> {
131 using result_type = typename MaxExponentPromotion<T, U>::type;
132 template <typename V = result_type>
133 static constexpr V Do(T x, U y) {
134 if (!PA_IsConstantEvaluated() && ClampedMulFastOp<T, U>::is_supported) {
135 return ClampedMulFastOp<T, U>::template Do<V>(x, y);
136 }
137
138 V result = {};
139 const V saturated =
140 CommonMaxOrMin<V>(IsValueNegative(x) ^ IsValueNegative(y));
141 return PA_BASE_NUMERICS_LIKELY((CheckedMulOp<T, U>::Do(x, y, &result)))
142 ? result
143 : saturated;
144 }
145 };
146
147 template <typename T, typename U, class Enable = void>
148 struct ClampedDivOp {};
149
150 template <typename T, typename U>
151 struct ClampedDivOp<T,
152 U,
153 typename std::enable_if<std::is_integral_v<T> &&
154 std::is_integral_v<U>>::type> {
155 using result_type = typename MaxExponentPromotion<T, U>::type;
156 template <typename V = result_type>
157 static constexpr V Do(T x, U y) {
158 V result = {};
159 if (PA_BASE_NUMERICS_LIKELY((CheckedDivOp<T, U>::Do(x, y, &result)))) {
160 return result;
161 }
162 // Saturation goes to max, min, or NaN (if x is zero).
163 return x ? CommonMaxOrMin<V>(IsValueNegative(x) ^ IsValueNegative(y))
164 : SaturationDefaultLimits<V>::NaN();
165 }
166 };
167
168 template <typename T, typename U, class Enable = void>
169 struct ClampedModOp {};
170
171 template <typename T, typename U>
172 struct ClampedModOp<T,
173 U,
174 typename std::enable_if<std::is_integral_v<T> &&
175 std::is_integral_v<U>>::type> {
176 using result_type = typename MaxExponentPromotion<T, U>::type;
177 template <typename V = result_type>
178 static constexpr V Do(T x, U y) {
179 V result = {};
180 return PA_BASE_NUMERICS_LIKELY((CheckedModOp<T, U>::Do(x, y, &result)))
181 ? result
182 : x;
183 }
184 };
185
186 template <typename T, typename U, class Enable = void>
187 struct ClampedLshOp {};
188
189 // Left shift. Non-zero values saturate in the direction of the sign. A zero
190 // shifted by any value always results in zero.
191 template <typename T, typename U>
192 struct ClampedLshOp<T,
193 U,
194 typename std::enable_if<std::is_integral_v<T> &&
195 std::is_integral_v<U>>::type> {
196 using result_type = T;
197 template <typename V = result_type>
198 static constexpr V Do(T x, U shift) {
199 static_assert(!std::is_signed_v<U>, "Shift value must be unsigned.");
200 if (PA_BASE_NUMERICS_LIKELY(shift < std::numeric_limits<T>::digits)) {
201 // Shift as unsigned to avoid undefined behavior.
202 V result = static_cast<V>(as_unsigned(x) << shift);
203 // If the shift can be reversed, we know it was valid.
204 if (PA_BASE_NUMERICS_LIKELY(result >> shift == x)) {
205 return result;
206 }
207 }
208 return x ? CommonMaxOrMin<V>(IsValueNegative(x)) : 0;
209 }
210 };
211
212 template <typename T, typename U, class Enable = void>
213 struct ClampedRshOp {};
214
215 // Right shift. Negative values saturate to -1. Positive or 0 saturates to 0.
216 template <typename T, typename U>
217 struct ClampedRshOp<T,
218 U,
219 typename std::enable_if<std::is_integral_v<T> &&
220 std::is_integral_v<U>>::type> {
221 using result_type = T;
222 template <typename V = result_type>
223 static constexpr V Do(T x, U shift) {
224 static_assert(!std::is_signed_v<U>, "Shift value must be unsigned.");
225 // Signed right shift is odd, because it saturates to -1 or 0.
226 const V saturated = as_unsigned(V(0)) - IsValueNegative(x);
227 return PA_BASE_NUMERICS_LIKELY(shift < IntegerBitsPlusSign<T>::value)
228 ? saturated_cast<V>(x >> shift)
229 : saturated;
230 }
231 };
232
233 template <typename T, typename U, class Enable = void>
234 struct ClampedAndOp {};
235
236 template <typename T, typename U>
237 struct ClampedAndOp<T,
238 U,
239 typename std::enable_if<std::is_integral_v<T> &&
240 std::is_integral_v<U>>::type> {
241 using result_type = typename std::make_unsigned<
242 typename MaxExponentPromotion<T, U>::type>::type;
243 template <typename V>
244 static constexpr V Do(T x, U y) {
245 return static_cast<result_type>(x) & static_cast<result_type>(y);
246 }
247 };
248
249 template <typename T, typename U, class Enable = void>
250 struct ClampedOrOp {};
251
252 // For simplicity we promote to unsigned integers.
253 template <typename T, typename U>
254 struct ClampedOrOp<T,
255 U,
256 typename std::enable_if<std::is_integral_v<T> &&
257 std::is_integral_v<U>>::type> {
258 using result_type = typename std::make_unsigned<
259 typename MaxExponentPromotion<T, U>::type>::type;
260 template <typename V>
261 static constexpr V Do(T x, U y) {
262 return static_cast<result_type>(x) | static_cast<result_type>(y);
263 }
264 };
265
266 template <typename T, typename U, class Enable = void>
267 struct ClampedXorOp {};
268
269 // For simplicity we support only unsigned integers.
270 template <typename T, typename U>
271 struct ClampedXorOp<T,
272 U,
273 typename std::enable_if<std::is_integral_v<T> &&
274 std::is_integral_v<U>>::type> {
275 using result_type = typename std::make_unsigned<
276 typename MaxExponentPromotion<T, U>::type>::type;
277 template <typename V>
278 static constexpr V Do(T x, U y) {
279 return static_cast<result_type>(x) ^ static_cast<result_type>(y);
280 }
281 };
282
283 template <typename T, typename U, class Enable = void>
284 struct ClampedMaxOp {};
285
286 template <typename T, typename U>
287 struct ClampedMaxOp<T,
288 U,
289 typename std::enable_if<std::is_arithmetic_v<T> &&
290 std::is_arithmetic_v<U>>::type> {
291 using result_type = typename MaxExponentPromotion<T, U>::type;
292 template <typename V = result_type>
293 static constexpr V Do(T x, U y) {
294 return IsGreater<T, U>::Test(x, y) ? saturated_cast<V>(x)
295 : saturated_cast<V>(y);
296 }
297 };
298
299 template <typename T, typename U, class Enable = void>
300 struct ClampedMinOp {};
301
302 template <typename T, typename U>
303 struct ClampedMinOp<T,
304 U,
305 typename std::enable_if<std::is_arithmetic_v<T> &&
306 std::is_arithmetic_v<U>>::type> {
307 using result_type = typename LowestValuePromotion<T, U>::type;
308 template <typename V = result_type>
309 static constexpr V Do(T x, U y) {
310 return IsLess<T, U>::Test(x, y) ? saturated_cast<V>(x)
311 : saturated_cast<V>(y);
312 }
313 };
314
315 // This is just boilerplate that wraps the standard floating point arithmetic.
316 // A macro isn't the nicest solution, but it beats rewriting these repeatedly.
317 #define PA_BASE_FLOAT_ARITHMETIC_OPS(NAME, OP) \
318 template <typename T, typename U> \
319 struct Clamped##NAME##Op< \
320 T, U, \
321 typename std::enable_if<std::is_floating_point_v<T> || \
322 std::is_floating_point_v<U>>::type> { \
323 using result_type = typename MaxExponentPromotion<T, U>::type; \
324 template <typename V = result_type> \
325 static constexpr V Do(T x, U y) { \
326 return saturated_cast<V>(x OP y); \
327 } \
328 };
329
330 PA_BASE_FLOAT_ARITHMETIC_OPS(Add, +)
331 PA_BASE_FLOAT_ARITHMETIC_OPS(Sub, -)
332 PA_BASE_FLOAT_ARITHMETIC_OPS(Mul, *)
333 PA_BASE_FLOAT_ARITHMETIC_OPS(Div, /)
334
335 #undef PA_BASE_FLOAT_ARITHMETIC_OPS
336
337 } // namespace partition_alloc::internal::base::internal
338
339 #endif // BASE_ALLOCATOR_PARTITION_ALLOCATOR_SRC_PARTITION_ALLOC_PARTITION_ALLOC_BASE_NUMERICS_CLAMPED_MATH_IMPL_H_
340