1 // Copyright 2014 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_SAFE_MATH_IMPL_H_
6 #define BASE_NUMERICS_SAFE_MATH_IMPL_H_
7 
8 #include <stddef.h>
9 #include <stdint.h>
10 
11 #include <cmath>
12 #include <cstdlib>
13 #include <limits>
14 #include <type_traits>
15 
16 #include "base/numerics/safe_conversions.h"
17 #include "base/template_util.h"
18 
19 namespace base {
20 namespace internal {
21 
22 // Everything from here up to the floating point operations is portable C++,
23 // but it may not be fast. This code could be split based on
24 // platform/architecture and replaced with potentially faster implementations.
25 
26 // Integer promotion templates used by the portable checked integer arithmetic.
27 template <size_t Size, bool IsSigned>
28 struct IntegerForSizeAndSign;
29 template <>
30 struct IntegerForSizeAndSign<1, true> {
31   typedef int8_t type;
32 };
33 template <>
34 struct IntegerForSizeAndSign<1, false> {
35   typedef uint8_t type;
36 };
37 template <>
38 struct IntegerForSizeAndSign<2, true> {
39   typedef int16_t type;
40 };
41 template <>
42 struct IntegerForSizeAndSign<2, false> {
43   typedef uint16_t type;
44 };
45 template <>
46 struct IntegerForSizeAndSign<4, true> {
47   typedef int32_t type;
48 };
49 template <>
50 struct IntegerForSizeAndSign<4, false> {
51   typedef uint32_t type;
52 };
53 template <>
54 struct IntegerForSizeAndSign<8, true> {
55   typedef int64_t type;
56 };
57 template <>
58 struct IntegerForSizeAndSign<8, false> {
59   typedef uint64_t type;
60 };
61 
62 // WARNING: We have no IntegerForSizeAndSign<16, *>. If we ever add one to
63 // support 128-bit math, then the ArithmeticPromotion template below will need
64 // to be updated (or more likely replaced with a decltype expression).
65 
66 template <typename Integer>
67 struct UnsignedIntegerForSize {
68   typedef typename std::enable_if<
69       std::numeric_limits<Integer>::is_integer,
70       typename IntegerForSizeAndSign<sizeof(Integer), false>::type>::type type;
71 };
72 
73 template <typename Integer>
74 struct SignedIntegerForSize {
75   typedef typename std::enable_if<
76       std::numeric_limits<Integer>::is_integer,
77       typename IntegerForSizeAndSign<sizeof(Integer), true>::type>::type type;
78 };
79 
80 template <typename Integer>
81 struct TwiceWiderInteger {
82   typedef typename std::enable_if<
83       std::numeric_limits<Integer>::is_integer,
84       typename IntegerForSizeAndSign<
85           sizeof(Integer) * 2,
86           std::numeric_limits<Integer>::is_signed>::type>::type type;
87 };
88 
89 template <typename Integer>
90 struct PositionOfSignBit {
91   static const typename std::enable_if<std::numeric_limits<Integer>::is_integer,
92                                        size_t>::type value =
93       8 * sizeof(Integer) - 1;
94 };
95 
96 // This is used for UnsignedAbs, where we need to support floating-point
97 // template instantiations even though we don't actually support the operations.
98 // However, there is no corresponding implementation of e.g. CheckedUnsignedAbs,
99 // so the float versions will not compile.
100 template <typename Numeric,
101           bool IsInteger = std::numeric_limits<Numeric>::is_integer,
102           bool IsFloat = std::numeric_limits<Numeric>::is_iec559>
103 struct UnsignedOrFloatForSize;
104 
105 template <typename Numeric>
106 struct UnsignedOrFloatForSize<Numeric, true, false> {
107   typedef typename UnsignedIntegerForSize<Numeric>::type type;
108 };
109 
110 template <typename Numeric>
111 struct UnsignedOrFloatForSize<Numeric, false, true> {
112   typedef Numeric type;
113 };
114 
115 // Helper templates for integer manipulations.
116 
117 template <typename T>
118 bool HasSignBit(T x) {
119   // Cast to unsigned since right shift on signed is undefined.
120   return !!(static_cast<typename UnsignedIntegerForSize<T>::type>(x) >>
121             PositionOfSignBit<T>::value);
122 }
123 
124 // This wrapper undoes the standard integer promotions.
125 template <typename T>
126 T BinaryComplement(T x) {
127   return ~x;
128 }
129 
130 // Here are the actual portable checked integer math implementations.
131 // TODO(jschuh): Break this code out from the enable_if pattern and find a clean
132 // way to coalesce things into the CheckedNumericState specializations below.
133 
134 template <typename T>
135 typename std::enable_if<std::numeric_limits<T>::is_integer, T>::type
136 CheckedAdd(T x, T y, RangeConstraint* validity) {
137   // Since the value of x+y is undefined if we have a signed type, we compute
138   // it using the unsigned type of the same size.
139   typedef typename UnsignedIntegerForSize<T>::type UnsignedDst;
140   UnsignedDst ux = static_cast<UnsignedDst>(x);
141   UnsignedDst uy = static_cast<UnsignedDst>(y);
142   UnsignedDst uresult = ux + uy;
143   // Addition is valid if the sign of (x + y) is equal to either that of x or
144   // that of y.
145   if (std::numeric_limits<T>::is_signed) {
146     if (HasSignBit(BinaryComplement((uresult ^ ux) & (uresult ^ uy))))
147       *validity = RANGE_VALID;
148     else  // Direction of wrap is inverse of result sign.
149       *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW;
150 
151   } else {  // Unsigned is either valid or overflow.
152     *validity = BinaryComplement(x) >= y ? RANGE_VALID : RANGE_OVERFLOW;
153   }
154   return static_cast<T>(uresult);
155 }
156 
157 template <typename T>
158 typename std::enable_if<std::numeric_limits<T>::is_integer, T>::type
159 CheckedSub(T x, T y, RangeConstraint* validity) {
160   // Since the value of x+y is undefined if we have a signed type, we compute
161   // it using the unsigned type of the same size.
162   typedef typename UnsignedIntegerForSize<T>::type UnsignedDst;
163   UnsignedDst ux = static_cast<UnsignedDst>(x);
164   UnsignedDst uy = static_cast<UnsignedDst>(y);
165   UnsignedDst uresult = ux - uy;
166   // Subtraction is valid if either x and y have same sign, or (x-y) and x have
167   // the same sign.
168   if (std::numeric_limits<T>::is_signed) {
169     if (HasSignBit(BinaryComplement((uresult ^ ux) & (ux ^ uy))))
170       *validity = RANGE_VALID;
171     else  // Direction of wrap is inverse of result sign.
172       *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW;
173 
174   } else {  // Unsigned is either valid or underflow.
175     *validity = x >= y ? RANGE_VALID : RANGE_UNDERFLOW;
176   }
177   return static_cast<T>(uresult);
178 }
179 
180 // Integer multiplication is a bit complicated. In the fast case we just
181 // we just promote to a twice wider type, and range check the result. In the
182 // slow case we need to manually check that the result won't be truncated by
183 // checking with division against the appropriate bound.
184 template <typename T>
185 typename std::enable_if<std::numeric_limits<T>::is_integer &&
186                             sizeof(T) * 2 <= sizeof(uintmax_t),
187                         T>::type
188 CheckedMul(T x, T y, RangeConstraint* validity) {
189   typedef typename TwiceWiderInteger<T>::type IntermediateType;
190   IntermediateType tmp =
191       static_cast<IntermediateType>(x) * static_cast<IntermediateType>(y);
192   *validity = DstRangeRelationToSrcRange<T>(tmp);
193   return static_cast<T>(tmp);
194 }
195 
196 template <typename T>
197 typename std::enable_if<std::numeric_limits<T>::is_integer &&
198                             std::numeric_limits<T>::is_signed &&
199                             (sizeof(T) * 2 > sizeof(uintmax_t)),
200                         T>::type
201 CheckedMul(T x, T y, RangeConstraint* validity) {
202   // If either side is zero then the result will be zero.
203   if (!x || !y) {
204     return RANGE_VALID;
205 
206   } else if (x > 0) {
207     if (y > 0)
208       *validity =
209           x <= std::numeric_limits<T>::max() / y ? RANGE_VALID : RANGE_OVERFLOW;
210     else
211       *validity = y >= std::numeric_limits<T>::min() / x ? RANGE_VALID
212                                                          : RANGE_UNDERFLOW;
213 
214   } else {
215     if (y > 0)
216       *validity = x >= std::numeric_limits<T>::min() / y ? RANGE_VALID
217                                                          : RANGE_UNDERFLOW;
218     else
219       *validity =
220           y >= std::numeric_limits<T>::max() / x ? RANGE_VALID : RANGE_OVERFLOW;
221   }
222 
223   return x * y;
224 }
225 
226 template <typename T>
227 typename std::enable_if<std::numeric_limits<T>::is_integer &&
228                             !std::numeric_limits<T>::is_signed &&
229                             (sizeof(T) * 2 > sizeof(uintmax_t)),
230                         T>::type
231 CheckedMul(T x, T y, RangeConstraint* validity) {
232   *validity = (y == 0 || x <= std::numeric_limits<T>::max() / y)
233                   ? RANGE_VALID
234                   : RANGE_OVERFLOW;
235   return x * y;
236 }
237 
238 // Division just requires a check for an invalid negation on signed min/-1.
239 template <typename T>
240 T CheckedDiv(T x,
241              T y,
242              RangeConstraint* validity,
243              typename std::enable_if<std::numeric_limits<T>::is_integer,
244                                      int>::type = 0) {
245   if (std::numeric_limits<T>::is_signed && x == std::numeric_limits<T>::min() &&
246       y == static_cast<T>(-1)) {
247     *validity = RANGE_OVERFLOW;
248     return std::numeric_limits<T>::min();
249   }
250 
251   *validity = RANGE_VALID;
252   return x / y;
253 }
254 
255 template <typename T>
256 typename std::enable_if<std::numeric_limits<T>::is_integer &&
257                             std::numeric_limits<T>::is_signed,
258                         T>::type
259 CheckedMod(T x, T y, RangeConstraint* validity) {
260   *validity = y > 0 ? RANGE_VALID : RANGE_INVALID;
261   return x % y;
262 }
263 
264 template <typename T>
265 typename std::enable_if<std::numeric_limits<T>::is_integer &&
266                             !std::numeric_limits<T>::is_signed,
267                         T>::type
268 CheckedMod(T x, T y, RangeConstraint* validity) {
269   *validity = RANGE_VALID;
270   return x % y;
271 }
272 
273 template <typename T>
274 typename std::enable_if<std::numeric_limits<T>::is_integer &&
275                             std::numeric_limits<T>::is_signed,
276                         T>::type
277 CheckedNeg(T value, RangeConstraint* validity) {
278   *validity =
279       value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW;
280   // The negation of signed min is min, so catch that one.
281   return -value;
282 }
283 
284 template <typename T>
285 typename std::enable_if<std::numeric_limits<T>::is_integer &&
286                             !std::numeric_limits<T>::is_signed,
287                         T>::type
288 CheckedNeg(T value, RangeConstraint* validity) {
289   // The only legal unsigned negation is zero.
290   *validity = value ? RANGE_UNDERFLOW : RANGE_VALID;
291   return static_cast<T>(
292       -static_cast<typename SignedIntegerForSize<T>::type>(value));
293 }
294 
295 template <typename T>
296 typename std::enable_if<std::numeric_limits<T>::is_integer &&
297                             std::numeric_limits<T>::is_signed,
298                         T>::type
299 CheckedAbs(T value, RangeConstraint* validity) {
300   *validity =
301       value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW;
302   return static_cast<T>(std::abs(value));
303 }
304 
305 template <typename T>
306 typename std::enable_if<std::numeric_limits<T>::is_integer &&
307                             !std::numeric_limits<T>::is_signed,
308                         T>::type
309 CheckedAbs(T value, RangeConstraint* validity) {
310   // T is unsigned, so |value| must already be positive.
311   *validity = RANGE_VALID;
312   return value;
313 }
314 
315 template <typename T>
316 typename std::enable_if<std::numeric_limits<T>::is_integer &&
317                             std::numeric_limits<T>::is_signed,
318                         typename UnsignedIntegerForSize<T>::type>::type
319 CheckedUnsignedAbs(T value) {
320   typedef typename UnsignedIntegerForSize<T>::type UnsignedT;
321   return value == std::numeric_limits<T>::min()
322              ? static_cast<UnsignedT>(std::numeric_limits<T>::max()) + 1
323              : static_cast<UnsignedT>(std::abs(value));
324 }
325 
326 template <typename T>
327 typename std::enable_if<std::numeric_limits<T>::is_integer &&
328                             !std::numeric_limits<T>::is_signed,
329                         T>::type
330 CheckedUnsignedAbs(T value) {
331   // T is unsigned, so |value| must already be positive.
332   return value;
333 }
334 
335 // These are the floating point stubs that the compiler needs to see. Only the
336 // negation operation is ever called.
337 #define BASE_FLOAT_ARITHMETIC_STUBS(NAME)                             \
338   template <typename T>                                               \
339   typename std::enable_if<std::numeric_limits<T>::is_iec559, T>::type \
340       Checked##NAME(T, T, RangeConstraint*) {                         \
341     NOTREACHED();                                                     \
342     return 0;                                                         \
343   }
344 
345 BASE_FLOAT_ARITHMETIC_STUBS(Add)
346 BASE_FLOAT_ARITHMETIC_STUBS(Sub)
347 BASE_FLOAT_ARITHMETIC_STUBS(Mul)
348 BASE_FLOAT_ARITHMETIC_STUBS(Div)
349 BASE_FLOAT_ARITHMETIC_STUBS(Mod)
350 
351 #undef BASE_FLOAT_ARITHMETIC_STUBS
352 
353 template <typename T>
354 typename std::enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedNeg(
355     T value,
356     RangeConstraint*) {
357   return -value;
358 }
359 
360 template <typename T>
361 typename std::enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedAbs(
362     T value,
363     RangeConstraint*) {
364   return std::abs(value);
365 }
366 
367 // Floats carry around their validity state with them, but integers do not. So,
368 // we wrap the underlying value in a specialization in order to hide that detail
369 // and expose an interface via accessors.
370 enum NumericRepresentation {
371   NUMERIC_INTEGER,
372   NUMERIC_FLOATING,
373   NUMERIC_UNKNOWN
374 };
375 
376 template <typename NumericType>
377 struct GetNumericRepresentation {
378   static const NumericRepresentation value =
379       std::numeric_limits<NumericType>::is_integer
380           ? NUMERIC_INTEGER
381           : (std::numeric_limits<NumericType>::is_iec559 ? NUMERIC_FLOATING
382                                                          : NUMERIC_UNKNOWN);
383 };
384 
385 template <typename T, NumericRepresentation type =
386                           GetNumericRepresentation<T>::value>
387 class CheckedNumericState {};
388 
389 // Integrals require quite a bit of additional housekeeping to manage state.
390 template <typename T>
391 class CheckedNumericState<T, NUMERIC_INTEGER> {
392  private:
393   T value_;
394   RangeConstraint validity_;
395 
396  public:
397   template <typename Src, NumericRepresentation type>
398   friend class CheckedNumericState;
399 
400   CheckedNumericState() : value_(0), validity_(RANGE_VALID) {}
401 
402   template <typename Src>
403   CheckedNumericState(Src value, RangeConstraint validity)
404       : value_(static_cast<T>(value)),
405         validity_(GetRangeConstraint(validity |
406                                      DstRangeRelationToSrcRange<T>(value))) {
407     static_assert(std::numeric_limits<Src>::is_specialized,
408                   "Argument must be numeric.");
409   }
410 
411   // Copy constructor.
412   template <typename Src>
413   CheckedNumericState(const CheckedNumericState<Src>& rhs)
414       : value_(static_cast<T>(rhs.value())),
415         validity_(GetRangeConstraint(
416             rhs.validity() | DstRangeRelationToSrcRange<T>(rhs.value()))) {}
417 
418   template <typename Src>
419   explicit CheckedNumericState(
420       Src value,
421       typename std::enable_if<std::numeric_limits<Src>::is_specialized,
422                               int>::type = 0)
423       : value_(static_cast<T>(value)),
424         validity_(DstRangeRelationToSrcRange<T>(value)) {}
425 
426   RangeConstraint validity() const { return validity_; }
427   T value() const { return value_; }
428 };
429 
430 // Floating points maintain their own validity, but need translation wrappers.
431 template <typename T>
432 class CheckedNumericState<T, NUMERIC_FLOATING> {
433  private:
434   T value_;
435 
436  public:
437   template <typename Src, NumericRepresentation type>
438   friend class CheckedNumericState;
439 
440   CheckedNumericState() : value_(0.0) {}
441 
442   template <typename Src>
443   CheckedNumericState(
444       Src value,
445       RangeConstraint /* validity */,
446       typename std::enable_if<std::numeric_limits<Src>::is_integer, int>::type =
447           0) {
448     switch (DstRangeRelationToSrcRange<T>(value)) {
449       case RANGE_VALID:
450         value_ = static_cast<T>(value);
451         break;
452 
453       case RANGE_UNDERFLOW:
454         value_ = -std::numeric_limits<T>::infinity();
455         break;
456 
457       case RANGE_OVERFLOW:
458         value_ = std::numeric_limits<T>::infinity();
459         break;
460 
461       case RANGE_INVALID:
462         value_ = std::numeric_limits<T>::quiet_NaN();
463         break;
464 
465       default:
466         NOTREACHED();
467     }
468   }
469 
470   template <typename Src>
471   explicit CheckedNumericState(
472       Src value,
473       typename std::enable_if<std::numeric_limits<Src>::is_specialized,
474                               int>::type = 0)
475       : value_(static_cast<T>(value)) {}
476 
477   // Copy constructor.
478   template <typename Src>
479   CheckedNumericState(const CheckedNumericState<Src>& rhs)
480       : value_(static_cast<T>(rhs.value())) {}
481 
482   RangeConstraint validity() const {
483     return GetRangeConstraint(value_ <= std::numeric_limits<T>::max(),
484                               value_ >= -std::numeric_limits<T>::max());
485   }
486   T value() const { return value_; }
487 };
488 
489 // For integers less than 128-bit and floats 32-bit or larger, we can distil
490 // C/C++ arithmetic promotions down to two simple rules:
491 // 1. The type with the larger maximum exponent always takes precedence.
492 // 2. The resulting type must be promoted to at least an int.
493 // The following template specializations implement that promotion logic.
494 enum ArithmeticPromotionCategory {
495   LEFT_PROMOTION,
496   RIGHT_PROMOTION,
497   DEFAULT_PROMOTION
498 };
499 
500 template <typename Lhs,
501           typename Rhs = Lhs,
502           ArithmeticPromotionCategory Promotion =
503               (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value)
504                   ? (MaxExponent<Lhs>::value > MaxExponent<int>::value
505                          ? LEFT_PROMOTION
506                          : DEFAULT_PROMOTION)
507                   : (MaxExponent<Rhs>::value > MaxExponent<int>::value
508                          ? RIGHT_PROMOTION
509                          : DEFAULT_PROMOTION) >
510 struct ArithmeticPromotion;
511 
512 template <typename Lhs, typename Rhs>
513 struct ArithmeticPromotion<Lhs, Rhs, LEFT_PROMOTION> {
514   typedef Lhs type;
515 };
516 
517 template <typename Lhs, typename Rhs>
518 struct ArithmeticPromotion<Lhs, Rhs, RIGHT_PROMOTION> {
519   typedef Rhs type;
520 };
521 
522 template <typename Lhs, typename Rhs>
523 struct ArithmeticPromotion<Lhs, Rhs, DEFAULT_PROMOTION> {
524   typedef int type;
525 };
526 
527 // We can statically check if operations on the provided types can wrap, so we
528 // can skip the checked operations if they're not needed. So, for an integer we
529 // care if the destination type preserves the sign and is twice the width of
530 // the source.
531 template <typename T, typename Lhs, typename Rhs>
532 struct IsIntegerArithmeticSafe {
533   static const bool value = !std::numeric_limits<T>::is_iec559 &&
534                             StaticDstRangeRelationToSrcRange<T, Lhs>::value ==
535                                 NUMERIC_RANGE_CONTAINED &&
536                             sizeof(T) >= (2 * sizeof(Lhs)) &&
537                             StaticDstRangeRelationToSrcRange<T, Rhs>::value !=
538                                 NUMERIC_RANGE_CONTAINED &&
539                             sizeof(T) >= (2 * sizeof(Rhs));
540 };
541 
542 }  // namespace internal
543 }  // namespace base
544 
545 #endif  // BASE_NUMERICS_SAFE_MATH_IMPL_H_
546