1 // Copyright 2017 The Chromium Authors. All rights reserved.
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_NUMERICS_CHECKED_MATH_IMPL_H_
6 #define BASE_NUMERICS_CHECKED_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 "base/numerics/safe_conversions.h"
18 #include "base/numerics/safe_math_shared_impl.h"
19
20 namespace base {
21 namespace internal {
22
23 template <typename T>
CheckedAddImpl(T x,T y,T * result)24 constexpr bool CheckedAddImpl(T x, T y, T* result) {
25 static_assert(std::is_integral<T>::value, "Type must be integral");
26 // Since the value of x+y is undefined if we have a signed type, we compute
27 // it using the unsigned type of the same size.
28 using UnsignedDst = typename std::make_unsigned<T>::type;
29 using SignedDst = typename std::make_signed<T>::type;
30 UnsignedDst ux = static_cast<UnsignedDst>(x);
31 UnsignedDst uy = static_cast<UnsignedDst>(y);
32 UnsignedDst uresult = static_cast<UnsignedDst>(ux + uy);
33 *result = static_cast<T>(uresult);
34 // Addition is valid if the sign of (x + y) is equal to either that of x or
35 // that of y.
36 return (std::is_signed<T>::value)
37 ? static_cast<SignedDst>((uresult ^ ux) & (uresult ^ uy)) >= 0
38 : uresult >= uy; // Unsigned is either valid or underflow.
39 }
40
41 template <typename T, typename U, class Enable = void>
42 struct CheckedAddOp {};
43
44 template <typename T, typename U>
45 struct CheckedAddOp<T,
46 U,
47 typename std::enable_if<std::is_integral<T>::value &&
48 std::is_integral<U>::value>::type> {
49 using result_type = typename MaxExponentPromotion<T, U>::type;
50 template <typename V>
51 static constexpr bool Do(T x, U y, V* result) {
52 // TODO(jschuh) Make this "constexpr if" once we're C++17.
53 if (CheckedAddFastOp<T, U>::is_supported)
54 return CheckedAddFastOp<T, U>::Do(x, y, result);
55
56 // Double the underlying type up to a full machine word.
57 using FastPromotion = typename FastIntegerArithmeticPromotion<T, U>::type;
58 using Promotion =
59 typename std::conditional<(IntegerBitsPlusSign<FastPromotion>::value >
60 IntegerBitsPlusSign<intptr_t>::value),
61 typename BigEnoughPromotion<T, U>::type,
62 FastPromotion>::type;
63 // Fail if either operand is out of range for the promoted type.
64 // TODO(jschuh): This could be made to work for a broader range of values.
65 if (BASE_NUMERICS_UNLIKELY(!IsValueInRangeForNumericType<Promotion>(x) ||
66 !IsValueInRangeForNumericType<Promotion>(y))) {
67 return false;
68 }
69
70 Promotion presult = {};
71 bool is_valid = true;
72 if (IsIntegerArithmeticSafe<Promotion, T, U>::value) {
73 presult = static_cast<Promotion>(x) + static_cast<Promotion>(y);
74 } else {
75 is_valid = CheckedAddImpl(static_cast<Promotion>(x),
76 static_cast<Promotion>(y), &presult);
77 }
78 *result = static_cast<V>(presult);
79 return is_valid && IsValueInRangeForNumericType<V>(presult);
80 }
81 };
82
83 template <typename T>
84 constexpr bool CheckedSubImpl(T x, T y, T* result) {
85 static_assert(std::is_integral<T>::value, "Type must be integral");
86 // Since the value of x+y is undefined if we have a signed type, we compute
87 // it using the unsigned type of the same size.
88 using UnsignedDst = typename std::make_unsigned<T>::type;
89 using SignedDst = typename std::make_signed<T>::type;
90 UnsignedDst ux = static_cast<UnsignedDst>(x);
91 UnsignedDst uy = static_cast<UnsignedDst>(y);
92 UnsignedDst uresult = static_cast<UnsignedDst>(ux - uy);
93 *result = static_cast<T>(uresult);
94 // Subtraction is valid if either x and y have same sign, or (x-y) and x have
95 // the same sign.
96 return (std::is_signed<T>::value)
97 ? static_cast<SignedDst>((uresult ^ ux) & (ux ^ uy)) >= 0
98 : x >= y;
99 }
100
101 template <typename T, typename U, class Enable = void>
102 struct CheckedSubOp {};
103
104 template <typename T, typename U>
105 struct CheckedSubOp<T,
106 U,
107 typename std::enable_if<std::is_integral<T>::value &&
108 std::is_integral<U>::value>::type> {
109 using result_type = typename MaxExponentPromotion<T, U>::type;
110 template <typename V>
111 static constexpr bool Do(T x, U y, V* result) {
112 // TODO(jschuh) Make this "constexpr if" once we're C++17.
113 if (CheckedSubFastOp<T, U>::is_supported)
114 return CheckedSubFastOp<T, U>::Do(x, y, result);
115
116 // Double the underlying type up to a full machine word.
117 using FastPromotion = typename FastIntegerArithmeticPromotion<T, U>::type;
118 using Promotion =
119 typename std::conditional<(IntegerBitsPlusSign<FastPromotion>::value >
120 IntegerBitsPlusSign<intptr_t>::value),
121 typename BigEnoughPromotion<T, U>::type,
122 FastPromotion>::type;
123 // Fail if either operand is out of range for the promoted type.
124 // TODO(jschuh): This could be made to work for a broader range of values.
125 if (BASE_NUMERICS_UNLIKELY(!IsValueInRangeForNumericType<Promotion>(x) ||
126 !IsValueInRangeForNumericType<Promotion>(y))) {
127 return false;
128 }
129
130 Promotion presult = {};
131 bool is_valid = true;
132 if (IsIntegerArithmeticSafe<Promotion, T, U>::value) {
133 presult = static_cast<Promotion>(x) - static_cast<Promotion>(y);
134 } else {
135 is_valid = CheckedSubImpl(static_cast<Promotion>(x),
136 static_cast<Promotion>(y), &presult);
137 }
138 *result = static_cast<V>(presult);
139 return is_valid && IsValueInRangeForNumericType<V>(presult);
140 }
141 };
142
143 template <typename T>
144 constexpr bool CheckedMulImpl(T x, T y, T* result) {
145 static_assert(std::is_integral<T>::value, "Type must be integral");
146 // Since the value of x*y is potentially undefined if we have a signed type,
147 // we compute it using the unsigned type of the same size.
148 using UnsignedDst = typename std::make_unsigned<T>::type;
149 using SignedDst = typename std::make_signed<T>::type;
150 const UnsignedDst ux = SafeUnsignedAbs(x);
151 const UnsignedDst uy = SafeUnsignedAbs(y);
152 UnsignedDst uresult = static_cast<UnsignedDst>(ux * uy);
153 const bool is_negative =
154 std::is_signed<T>::value && static_cast<SignedDst>(x ^ y) < 0;
155 *result = is_negative ? 0 - uresult : uresult;
156 // We have a fast out for unsigned identity or zero on the second operand.
157 // After that it's an unsigned overflow check on the absolute value, with
158 // a +1 bound for a negative result.
159 return uy <= UnsignedDst(!std::is_signed<T>::value || is_negative) ||
160 ux <= (std::numeric_limits<T>::max() + UnsignedDst(is_negative)) / uy;
161 }
162
163 template <typename T, typename U, class Enable = void>
164 struct CheckedMulOp {};
165
166 template <typename T, typename U>
167 struct CheckedMulOp<T,
168 U,
169 typename std::enable_if<std::is_integral<T>::value &&
170 std::is_integral<U>::value>::type> {
171 using result_type = typename MaxExponentPromotion<T, U>::type;
172 template <typename V>
173 static constexpr bool Do(T x, U y, V* result) {
174 // TODO(jschuh) Make this "constexpr if" once we're C++17.
175 if (CheckedMulFastOp<T, U>::is_supported)
176 return CheckedMulFastOp<T, U>::Do(x, y, result);
177
178 using Promotion = typename FastIntegerArithmeticPromotion<T, U>::type;
179 // Verify the destination type can hold the result (always true for 0).
180 if (BASE_NUMERICS_UNLIKELY((!IsValueInRangeForNumericType<Promotion>(x) ||
181 !IsValueInRangeForNumericType<Promotion>(y)) &&
182 x && y)) {
183 return false;
184 }
185
186 Promotion presult = {};
187 bool is_valid = true;
188 if (CheckedMulFastOp<Promotion, Promotion>::is_supported) {
189 // The fast op may be available with the promoted type.
190 is_valid = CheckedMulFastOp<Promotion, Promotion>::Do(x, y, &presult);
191 } else if (IsIntegerArithmeticSafe<Promotion, T, U>::value) {
192 presult = static_cast<Promotion>(x) * static_cast<Promotion>(y);
193 } else {
194 is_valid = CheckedMulImpl(static_cast<Promotion>(x),
195 static_cast<Promotion>(y), &presult);
196 }
197 *result = static_cast<V>(presult);
198 return is_valid && IsValueInRangeForNumericType<V>(presult);
199 }
200 };
201
202 // Division just requires a check for a zero denominator or an invalid negation
203 // on signed min/-1.
204 template <typename T, typename U, class Enable = void>
205 struct CheckedDivOp {};
206
207 template <typename T, typename U>
208 struct CheckedDivOp<T,
209 U,
210 typename std::enable_if<std::is_integral<T>::value &&
211 std::is_integral<U>::value>::type> {
212 using result_type = typename MaxExponentPromotion<T, U>::type;
213 template <typename V>
214 static constexpr bool Do(T x, U y, V* result) {
215 if (BASE_NUMERICS_UNLIKELY(!y))
216 return false;
217
218 // The overflow check can be compiled away if we don't have the exact
219 // combination of types needed to trigger this case.
220 using Promotion = typename BigEnoughPromotion<T, U>::type;
221 if (BASE_NUMERICS_UNLIKELY(
222 (std::is_signed<T>::value && std::is_signed<U>::value &&
223 IsTypeInRangeForNumericType<T, Promotion>::value &&
224 static_cast<Promotion>(x) ==
225 std::numeric_limits<Promotion>::lowest() &&
226 y == static_cast<U>(-1)))) {
227 return false;
228 }
229
230 // This branch always compiles away if the above branch wasn't removed.
231 if (BASE_NUMERICS_UNLIKELY((!IsValueInRangeForNumericType<Promotion>(x) ||
232 !IsValueInRangeForNumericType<Promotion>(y)) &&
233 x)) {
234 return false;
235 }
236
237 Promotion presult = Promotion(x) / Promotion(y);
238 *result = static_cast<V>(presult);
239 return IsValueInRangeForNumericType<V>(presult);
240 }
241 };
242
243 template <typename T, typename U, class Enable = void>
244 struct CheckedModOp {};
245
246 template <typename T, typename U>
247 struct CheckedModOp<T,
248 U,
249 typename std::enable_if<std::is_integral<T>::value &&
250 std::is_integral<U>::value>::type> {
251 using result_type = typename MaxExponentPromotion<T, U>::type;
252 template <typename V>
253 static constexpr bool Do(T x, U y, V* result) {
254 using Promotion = typename BigEnoughPromotion<T, U>::type;
255 if (BASE_NUMERICS_LIKELY(y)) {
256 Promotion presult = static_cast<Promotion>(x) % static_cast<Promotion>(y);
257 *result = static_cast<Promotion>(presult);
258 return IsValueInRangeForNumericType<V>(presult);
259 }
260 return false;
261 }
262 };
263
264 template <typename T, typename U, class Enable = void>
265 struct CheckedLshOp {};
266
267 // Left shift. Shifts less than 0 or greater than or equal to the number
268 // of bits in the promoted type are undefined. Shifts of negative values
269 // are undefined. Otherwise it is defined when the result fits.
270 template <typename T, typename U>
271 struct CheckedLshOp<T,
272 U,
273 typename std::enable_if<std::is_integral<T>::value &&
274 std::is_integral<U>::value>::type> {
275 using result_type = T;
276 template <typename V>
277 static constexpr bool Do(T x, U shift, V* result) {
278 // Disallow negative numbers and verify the shift is in bounds.
279 if (BASE_NUMERICS_LIKELY(!IsValueNegative(x) &&
280 as_unsigned(shift) <
281 as_unsigned(std::numeric_limits<T>::digits))) {
282 // Shift as unsigned to avoid undefined behavior.
283 *result = static_cast<V>(as_unsigned(x) << shift);
284 // If the shift can be reversed, we know it was valid.
285 return *result >> shift == x;
286 }
287
288 // Handle the legal corner-case of a full-width signed shift of zero.
289 return std::is_signed<T>::value && !x &&
290 as_unsigned(shift) == as_unsigned(std::numeric_limits<T>::digits);
291 }
292 };
293
294 template <typename T, typename U, class Enable = void>
295 struct CheckedRshOp {};
296
297 // Right shift. Shifts less than 0 or greater than or equal to the number
298 // of bits in the promoted type are undefined. Otherwise, it is always defined,
299 // but a right shift of a negative value is implementation-dependent.
300 template <typename T, typename U>
301 struct CheckedRshOp<T,
302 U,
303 typename std::enable_if<std::is_integral<T>::value &&
304 std::is_integral<U>::value>::type> {
305 using result_type = T;
306 template <typename V>
307 static bool Do(T x, U shift, V* result) {
308 // Use the type conversion push negative values out of range.
309 if (BASE_NUMERICS_LIKELY(as_unsigned(shift) <
310 IntegerBitsPlusSign<T>::value)) {
311 T tmp = x >> shift;
312 *result = static_cast<V>(tmp);
313 return IsValueInRangeForNumericType<V>(tmp);
314 }
315 return false;
316 }
317 };
318
319 template <typename T, typename U, class Enable = void>
320 struct CheckedAndOp {};
321
322 // For simplicity we support only unsigned integer results.
323 template <typename T, typename U>
324 struct CheckedAndOp<T,
325 U,
326 typename std::enable_if<std::is_integral<T>::value &&
327 std::is_integral<U>::value>::type> {
328 using result_type = typename std::make_unsigned<
329 typename MaxExponentPromotion<T, U>::type>::type;
330 template <typename V>
331 static constexpr bool Do(T x, U y, V* result) {
332 result_type tmp = static_cast<result_type>(x) & static_cast<result_type>(y);
333 *result = static_cast<V>(tmp);
334 return IsValueInRangeForNumericType<V>(tmp);
335 }
336 };
337
338 template <typename T, typename U, class Enable = void>
339 struct CheckedOrOp {};
340
341 // For simplicity we support only unsigned integers.
342 template <typename T, typename U>
343 struct CheckedOrOp<T,
344 U,
345 typename std::enable_if<std::is_integral<T>::value &&
346 std::is_integral<U>::value>::type> {
347 using result_type = typename std::make_unsigned<
348 typename MaxExponentPromotion<T, U>::type>::type;
349 template <typename V>
350 static constexpr bool Do(T x, U y, V* result) {
351 result_type tmp = static_cast<result_type>(x) | static_cast<result_type>(y);
352 *result = static_cast<V>(tmp);
353 return IsValueInRangeForNumericType<V>(tmp);
354 }
355 };
356
357 template <typename T, typename U, class Enable = void>
358 struct CheckedXorOp {};
359
360 // For simplicity we support only unsigned integers.
361 template <typename T, typename U>
362 struct CheckedXorOp<T,
363 U,
364 typename std::enable_if<std::is_integral<T>::value &&
365 std::is_integral<U>::value>::type> {
366 using result_type = typename std::make_unsigned<
367 typename MaxExponentPromotion<T, U>::type>::type;
368 template <typename V>
369 static constexpr bool Do(T x, U y, V* result) {
370 result_type tmp = static_cast<result_type>(x) ^ static_cast<result_type>(y);
371 *result = static_cast<V>(tmp);
372 return IsValueInRangeForNumericType<V>(tmp);
373 }
374 };
375
376 // Max doesn't really need to be implemented this way because it can't fail,
377 // but it makes the code much cleaner to use the MathOp wrappers.
378 template <typename T, typename U, class Enable = void>
379 struct CheckedMaxOp {};
380
381 template <typename T, typename U>
382 struct CheckedMaxOp<
383 T,
384 U,
385 typename std::enable_if<std::is_arithmetic<T>::value &&
386 std::is_arithmetic<U>::value>::type> {
387 using result_type = typename MaxExponentPromotion<T, U>::type;
388 template <typename V>
389 static constexpr bool Do(T x, U y, V* result) {
390 result_type tmp = IsGreater<T, U>::Test(x, y) ? static_cast<result_type>(x)
391 : static_cast<result_type>(y);
392 *result = static_cast<V>(tmp);
393 return IsValueInRangeForNumericType<V>(tmp);
394 }
395 };
396
397 // Min doesn't really need to be implemented this way because it can't fail,
398 // but it makes the code much cleaner to use the MathOp wrappers.
399 template <typename T, typename U, class Enable = void>
400 struct CheckedMinOp {};
401
402 template <typename T, typename U>
403 struct CheckedMinOp<
404 T,
405 U,
406 typename std::enable_if<std::is_arithmetic<T>::value &&
407 std::is_arithmetic<U>::value>::type> {
408 using result_type = typename LowestValuePromotion<T, U>::type;
409 template <typename V>
410 static constexpr bool Do(T x, U y, V* result) {
411 result_type tmp = IsLess<T, U>::Test(x, y) ? static_cast<result_type>(x)
412 : static_cast<result_type>(y);
413 *result = static_cast<V>(tmp);
414 return IsValueInRangeForNumericType<V>(tmp);
415 }
416 };
417
418 // This is just boilerplate that wraps the standard floating point arithmetic.
419 // A macro isn't the nicest solution, but it beats rewriting these repeatedly.
420 #define BASE_FLOAT_ARITHMETIC_OPS(NAME, OP) \
421 template <typename T, typename U> \
422 struct Checked##NAME##Op< \
423 T, U, \
424 typename std::enable_if<std::is_floating_point<T>::value || \
425 std::is_floating_point<U>::value>::type> { \
426 using result_type = typename MaxExponentPromotion<T, U>::type; \
427 template <typename V> \
428 static constexpr bool Do(T x, U y, V* result) { \
429 using Promotion = typename MaxExponentPromotion<T, U>::type; \
430 Promotion presult = x OP y; \
431 *result = static_cast<V>(presult); \
432 return IsValueInRangeForNumericType<V>(presult); \
433 } \
434 };
435
436 BASE_FLOAT_ARITHMETIC_OPS(Add, +)
437 BASE_FLOAT_ARITHMETIC_OPS(Sub, -)
438 BASE_FLOAT_ARITHMETIC_OPS(Mul, *)
439 BASE_FLOAT_ARITHMETIC_OPS(Div, /)
440
441 #undef BASE_FLOAT_ARITHMETIC_OPS
442
443 // Floats carry around their validity state with them, but integers do not. So,
444 // we wrap the underlying value in a specialization in order to hide that detail
445 // and expose an interface via accessors.
446 enum NumericRepresentation {
447 NUMERIC_INTEGER,
448 NUMERIC_FLOATING,
449 NUMERIC_UNKNOWN
450 };
451
452 template <typename NumericType>
453 struct GetNumericRepresentation {
454 static const NumericRepresentation value =
455 std::is_integral<NumericType>::value
456 ? NUMERIC_INTEGER
457 : (std::is_floating_point<NumericType>::value ? NUMERIC_FLOATING
458 : NUMERIC_UNKNOWN);
459 };
460
461 template <typename T,
462 NumericRepresentation type = GetNumericRepresentation<T>::value>
463 class CheckedNumericState {};
464
465 // Integrals require quite a bit of additional housekeeping to manage state.
466 template <typename T>
467 class CheckedNumericState<T, NUMERIC_INTEGER> {
468 private:
469 // is_valid_ precedes value_ because member intializers in the constructors
470 // are evaluated in field order, and is_valid_ must be read when initializing
471 // value_.
472 bool is_valid_;
473 T value_;
474
475 // Ensures that a type conversion does not trigger undefined behavior.
476 template <typename Src>
477 static constexpr T WellDefinedConversionOrZero(const Src value,
478 const bool is_valid) {
479 using SrcType = typename internal::UnderlyingType<Src>::type;
480 return (std::is_integral<SrcType>::value || is_valid)
481 ? static_cast<T>(value)
482 : static_cast<T>(0);
483 }
484
485 public:
486 template <typename Src, NumericRepresentation type>
487 friend class CheckedNumericState;
488
489 constexpr CheckedNumericState() : is_valid_(true), value_(0) {}
490
491 template <typename Src>
492 constexpr CheckedNumericState(Src value, bool is_valid)
493 : is_valid_(is_valid && IsValueInRangeForNumericType<T>(value)),
494 value_(WellDefinedConversionOrZero(value, is_valid_)) {
495 static_assert(std::is_arithmetic<Src>::value, "Argument must be numeric.");
496 }
497
498 // Copy constructor.
499 template <typename Src>
500 constexpr CheckedNumericState(const CheckedNumericState<Src>& rhs)
501 : is_valid_(rhs.IsValid()),
502 value_(WellDefinedConversionOrZero(rhs.value(), is_valid_)) {}
503
504 template <typename Src>
505 constexpr explicit CheckedNumericState(Src value)
506 : is_valid_(IsValueInRangeForNumericType<T>(value)),
507 value_(WellDefinedConversionOrZero(value, is_valid_)) {}
508
509 constexpr bool is_valid() const { return is_valid_; }
510 constexpr T value() const { return value_; }
511 };
512
513 // Floating points maintain their own validity, but need translation wrappers.
514 template <typename T>
515 class CheckedNumericState<T, NUMERIC_FLOATING> {
516 private:
517 T value_;
518
519 // Ensures that a type conversion does not trigger undefined behavior.
520 template <typename Src>
521 static constexpr T WellDefinedConversionOrNaN(const Src value,
522 const bool is_valid) {
523 using SrcType = typename internal::UnderlyingType<Src>::type;
524 return (StaticDstRangeRelationToSrcRange<T, SrcType>::value ==
525 NUMERIC_RANGE_CONTAINED ||
526 is_valid)
527 ? static_cast<T>(value)
528 : std::numeric_limits<T>::quiet_NaN();
529 }
530
531 public:
532 template <typename Src, NumericRepresentation type>
533 friend class CheckedNumericState;
534
535 constexpr CheckedNumericState() : value_(0.0) {}
536
537 template <typename Src>
538 constexpr CheckedNumericState(Src value, bool is_valid)
539 : value_(WellDefinedConversionOrNaN(value, is_valid)) {}
540
541 template <typename Src>
542 constexpr explicit CheckedNumericState(Src value)
543 : value_(WellDefinedConversionOrNaN(
544 value,
545 IsValueInRangeForNumericType<T>(value))) {}
546
547 // Copy constructor.
548 template <typename Src>
549 constexpr CheckedNumericState(const CheckedNumericState<Src>& rhs)
550 : value_(WellDefinedConversionOrNaN(
551 rhs.value(),
552 rhs.is_valid() && IsValueInRangeForNumericType<T>(rhs.value()))) {}
553
554 constexpr bool is_valid() const {
555 // Written this way because std::isfinite is not reliably constexpr.
556 return MustTreatAsConstexpr(value_)
557 ? value_ <= std::numeric_limits<T>::max() &&
558 value_ >= std::numeric_limits<T>::lowest()
559 : std::isfinite(value_);
560 }
561 constexpr T value() const { return value_; }
562 };
563
564 } // namespace internal
565 } // namespace base
566
567 #endif // BASE_NUMERICS_CHECKED_MATH_IMPL_H_
568