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