4bf59e64e07c6ce6edde7deee2e2014bc623749c
[pdfium.git] / third_party / numerics / safe_math_impl.h
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 SAFE_MATH_IMPL_H_
6 #define SAFE_MATH_IMPL_H_
7
8 #include <stdint.h>
9
10 #include <cmath>
11 #include <cstdlib>
12 #include <limits>
13
14 #include "../macros.h"
15 #include "../template_util.h"
16 #include "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 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 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 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 enable_if<std::numeric_limits<Integer>::is_integer,
91                                   size_t>::type value = 8 * sizeof(Integer) - 1;
92 };
93
94 // Helper templates for integer manipulations.
95
96 template <typename T>
97 bool HasSignBit(T x) {
98   // Cast to unsigned since right shift on signed is undefined.
99   return !!(static_cast<typename UnsignedIntegerForSize<T>::type>(x) >>
100             PositionOfSignBit<T>::value);
101 }
102
103 // This wrapper undoes the standard integer promotions.
104 template <typename T>
105 T BinaryComplement(T x) {
106   return ~x;
107 }
108
109 // Here are the actual portable checked integer math implementations.
110 // TODO(jschuh): Break this code out from the enable_if pattern and find a clean
111 // way to coalesce things into the CheckedNumericState specializations below.
112
113 template <typename T>
114 typename enable_if<std::numeric_limits<T>::is_integer, T>::type
115 CheckedAdd(T x, T y, RangeConstraint* validity) {
116   // Since the value of x+y is undefined if we have a signed type, we compute
117   // it using the unsigned type of the same size.
118   typedef typename UnsignedIntegerForSize<T>::type UnsignedDst;
119   UnsignedDst ux = static_cast<UnsignedDst>(x);
120   UnsignedDst uy = static_cast<UnsignedDst>(y);
121   UnsignedDst uresult = ux + uy;
122   // Addition is valid if the sign of (x + y) is equal to either that of x or
123   // that of y.
124   if (std::numeric_limits<T>::is_signed) {
125     if (HasSignBit(BinaryComplement((uresult ^ ux) & (uresult ^ uy))))
126       *validity = RANGE_VALID;
127     else  // Direction of wrap is inverse of result sign.
128       *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW;
129
130   } else {  // Unsigned is either valid or overflow.
131     *validity = BinaryComplement(x) >= y ? RANGE_VALID : RANGE_OVERFLOW;
132   }
133   return static_cast<T>(uresult);
134 }
135
136 template <typename T>
137 typename enable_if<std::numeric_limits<T>::is_integer, T>::type
138 CheckedSub(T x, T y, RangeConstraint* validity) {
139   // Since the value of x+y is undefined if we have a signed type, we compute
140   // it using the unsigned type of the same size.
141   typedef typename UnsignedIntegerForSize<T>::type UnsignedDst;
142   UnsignedDst ux = static_cast<UnsignedDst>(x);
143   UnsignedDst uy = static_cast<UnsignedDst>(y);
144   UnsignedDst uresult = ux - uy;
145   // Subtraction is valid if either x and y have same sign, or (x-y) and x have
146   // the same sign.
147   if (std::numeric_limits<T>::is_signed) {
148     if (HasSignBit(BinaryComplement((uresult ^ ux) & (ux ^ uy))))
149       *validity = RANGE_VALID;
150     else  // Direction of wrap is inverse of result sign.
151       *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW;
152
153   } else {  // Unsigned is either valid or underflow.
154     *validity = x >= y ? RANGE_VALID : RANGE_UNDERFLOW;
155   }
156   return static_cast<T>(uresult);
157 }
158
159 // Integer multiplication is a bit complicated. In the fast case we just
160 // we just promote to a twice wider type, and range check the result. In the
161 // slow case we need to manually check that the result won't be truncated by
162 // checking with division against the appropriate bound.
163 template <typename T>
164 typename enable_if<
165     std::numeric_limits<T>::is_integer && sizeof(T) * 2 <= sizeof(uintmax_t),
166     T>::type
167 CheckedMul(T x, T y, RangeConstraint* validity) {
168   typedef typename TwiceWiderInteger<T>::type IntermediateType;
169   IntermediateType tmp =
170       static_cast<IntermediateType>(x) * static_cast<IntermediateType>(y);
171   *validity = DstRangeRelationToSrcRange<T>(tmp);
172   return static_cast<T>(tmp);
173 }
174
175 template <typename T>
176 typename enable_if<std::numeric_limits<T>::is_integer&& std::numeric_limits<
177                        T>::is_signed&&(sizeof(T) * 2 > sizeof(uintmax_t)),
178                    T>::type
179 CheckedMul(T x, T y, RangeConstraint* validity) {
180   // if either side is zero then the result will be zero.
181   if (!(x || y)) {
182     return RANGE_VALID;
183
184   } else if (x > 0) {
185     if (y > 0)
186       *validity =
187           x <= std::numeric_limits<T>::max() / y ? RANGE_VALID : RANGE_OVERFLOW;
188     else
189       *validity = y >= std::numeric_limits<T>::min() / x ? RANGE_VALID
190                                                          : RANGE_UNDERFLOW;
191
192   } else {
193     if (y > 0)
194       *validity = x >= std::numeric_limits<T>::min() / y ? RANGE_VALID
195                                                          : RANGE_UNDERFLOW;
196     else
197       *validity =
198           y >= std::numeric_limits<T>::max() / x ? RANGE_VALID : RANGE_OVERFLOW;
199   }
200
201   return x * y;
202 }
203
204 template <typename T>
205 typename enable_if<std::numeric_limits<T>::is_integer &&
206                        !std::numeric_limits<T>::is_signed &&
207                        (sizeof(T) * 2 > sizeof(uintmax_t)),
208                    T>::type
209 CheckedMul(T x, T y, RangeConstraint* validity) {
210   *validity = (y == 0 || x <= std::numeric_limits<T>::max() / y)
211                   ? RANGE_VALID
212                   : RANGE_OVERFLOW;
213   return x * y;
214 }
215
216 // Division just requires a check for an invalid negation on signed min/-1.
217 template <typename T>
218 T CheckedDiv(
219     T x,
220     T y,
221     RangeConstraint* validity,
222     typename enable_if<std::numeric_limits<T>::is_integer, int>::type = 0) {
223   if (std::numeric_limits<T>::is_signed && x == std::numeric_limits<T>::min() &&
224       y == static_cast<T>(-1)) {
225     *validity = RANGE_OVERFLOW;
226     return std::numeric_limits<T>::min();
227   }
228
229   *validity = RANGE_VALID;
230   return x / y;
231 }
232
233 template <typename T>
234 typename enable_if<
235     std::numeric_limits<T>::is_integer&& std::numeric_limits<T>::is_signed,
236     T>::type
237 CheckedMod(T x, T y, RangeConstraint* validity) {
238   *validity = y > 0 ? RANGE_VALID : RANGE_INVALID;
239   return x % y;
240 }
241
242 template <typename T>
243 typename enable_if<
244     std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
245     T>::type
246 CheckedMod(T x, T y, RangeConstraint* validity) {
247   *validity = RANGE_VALID;
248   return x % y;
249 }
250
251 template <typename T>
252 typename enable_if<
253     std::numeric_limits<T>::is_integer&& std::numeric_limits<T>::is_signed,
254     T>::type
255 CheckedNeg(T value, RangeConstraint* validity) {
256   *validity =
257       value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW;
258   // The negation of signed min is min, so catch that one.
259   return -value;
260 }
261
262 template <typename T>
263 typename enable_if<
264     std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
265     T>::type
266 CheckedNeg(T value, RangeConstraint* validity) {
267   // The only legal unsigned negation is zero.
268   *validity = value ? RANGE_UNDERFLOW : RANGE_VALID;
269   return static_cast<T>(
270       -static_cast<typename SignedIntegerForSize<T>::type>(value));
271 }
272
273 template <typename T>
274 typename enable_if<
275     std::numeric_limits<T>::is_integer&& std::numeric_limits<T>::is_signed,
276     T>::type
277 CheckedAbs(T value, RangeConstraint* validity) {
278   *validity =
279       value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW;
280   return std::abs(value);
281 }
282
283 template <typename T>
284 typename enable_if<
285     std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
286     T>::type
287 CheckedAbs(T value, RangeConstraint* validity) {
288   // Absolute value of a positive is just its identiy.
289   *validity = RANGE_VALID;
290   return value;
291 }
292
293 // These are the floating point stubs that the compiler needs to see. Only the
294 // negation operation is ever called.
295 #define BASE_FLOAT_ARITHMETIC_STUBS(NAME)                        \
296   template <typename T>                                          \
297   typename enable_if<std::numeric_limits<T>::is_iec559, T>::type \
298   Checked##NAME(T, T, RangeConstraint*) {                        \
299     NOTREACHED();                                                \
300     return 0;                                                    \
301   }
302
303 BASE_FLOAT_ARITHMETIC_STUBS(Add)
304 BASE_FLOAT_ARITHMETIC_STUBS(Sub)
305 BASE_FLOAT_ARITHMETIC_STUBS(Mul)
306 BASE_FLOAT_ARITHMETIC_STUBS(Div)
307 BASE_FLOAT_ARITHMETIC_STUBS(Mod)
308
309 #undef BASE_FLOAT_ARITHMETIC_STUBS
310
311 template <typename T>
312 typename enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedNeg(
313     T value,
314     RangeConstraint*) {
315   return -value;
316 }
317
318 template <typename T>
319 typename enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedAbs(
320     T value,
321     RangeConstraint*) {
322   return std::abs(value);
323 }
324
325 // Floats carry around their validity state with them, but integers do not. So,
326 // we wrap the underlying value in a specialization in order to hide that detail
327 // and expose an interface via accessors.
328 enum NumericRepresentation {
329   NUMERIC_INTEGER,
330   NUMERIC_FLOATING,
331   NUMERIC_UNKNOWN
332 };
333
334 template <typename NumericType>
335 struct GetNumericRepresentation {
336   static const NumericRepresentation value =
337       std::numeric_limits<NumericType>::is_integer
338           ? NUMERIC_INTEGER
339           : (std::numeric_limits<NumericType>::is_iec559 ? NUMERIC_FLOATING
340                                                          : NUMERIC_UNKNOWN);
341 };
342
343 template <typename T, NumericRepresentation type =
344                           GetNumericRepresentation<T>::value>
345 class CheckedNumericState {};
346
347 // Integrals require quite a bit of additional housekeeping to manage state.
348 template <typename T>
349 class CheckedNumericState<T, NUMERIC_INTEGER> {
350  private:
351   T value_;
352   RangeConstraint validity_;
353
354  public:
355   template <typename Src, NumericRepresentation type>
356   friend class CheckedNumericState;
357
358   CheckedNumericState() : value_(0), validity_(RANGE_VALID) {}
359
360   template <typename Src>
361   CheckedNumericState(Src value, RangeConstraint validity)
362       : value_(value),
363         validity_(GetRangeConstraint(validity |
364                                      DstRangeRelationToSrcRange<T>(value))) {
365     COMPILE_ASSERT(std::numeric_limits<Src>::is_specialized,
366                    argument_must_be_numeric);
367   }
368
369   // Copy constructor.
370   template <typename Src>
371   CheckedNumericState(const CheckedNumericState<Src>& rhs)
372       : value_(static_cast<T>(rhs.value())),
373         validity_(GetRangeConstraint(
374             rhs.validity() | DstRangeRelationToSrcRange<T>(rhs.value()))) {}
375
376   template <typename Src>
377   explicit CheckedNumericState(
378       Src value,
379       typename enable_if<std::numeric_limits<Src>::is_specialized, int>::type =
380           0)
381       : value_(static_cast<T>(value)),
382         validity_(DstRangeRelationToSrcRange<T>(value)) {}
383
384   RangeConstraint validity() const { return validity_; }
385   T value() const { return value_; }
386 };
387
388 // Floating points maintain their own validity, but need translation wrappers.
389 template <typename T>
390 class CheckedNumericState<T, NUMERIC_FLOATING> {
391  private:
392   T value_;
393
394  public:
395   template <typename Src, NumericRepresentation type>
396   friend class CheckedNumericState;
397
398   CheckedNumericState() : value_(0.0) {}
399
400   template <typename Src>
401   CheckedNumericState(
402       Src value,
403       RangeConstraint validity,
404       typename enable_if<std::numeric_limits<Src>::is_integer, int>::type = 0) {
405     switch (DstRangeRelationToSrcRange<T>(value)) {
406       case RANGE_VALID:
407         value_ = static_cast<T>(value);
408         break;
409
410       case RANGE_UNDERFLOW:
411         value_ = -std::numeric_limits<T>::infinity();
412         break;
413
414       case RANGE_OVERFLOW:
415         value_ = std::numeric_limits<T>::infinity();
416         break;
417
418       case RANGE_INVALID:
419         value_ = std::numeric_limits<T>::quiet_NaN();
420         break;
421
422       default:
423         NOTREACHED();
424     }
425   }
426
427   template <typename Src>
428   explicit CheckedNumericState(
429       Src value,
430       typename enable_if<std::numeric_limits<Src>::is_specialized, int>::type =
431           0)
432       : value_(static_cast<T>(value)) {}
433
434   // Copy constructor.
435   template <typename Src>
436   CheckedNumericState(const CheckedNumericState<Src>& rhs)
437       : value_(static_cast<T>(rhs.value())) {}
438
439   RangeConstraint validity() const {
440     return GetRangeConstraint(value_ <= std::numeric_limits<T>::max(),
441                               value_ >= -std::numeric_limits<T>::max());
442   }
443   T value() const { return value_; }
444 };
445
446 // For integers less than 128-bit and floats 32-bit or larger, we can distil
447 // C/C++ arithmetic promotions down to two simple rules:
448 // 1. The type with the larger maximum exponent always takes precedence.
449 // 2. The resulting type must be promoted to at least an int.
450 // The following template specializations implement that promotion logic.
451 enum ArithmeticPromotionCategory {
452   LEFT_PROMOTION,
453   RIGHT_PROMOTION,
454   DEFAULT_PROMOTION
455 };
456
457 template <typename Lhs,
458           typename Rhs = Lhs,
459           ArithmeticPromotionCategory Promotion =
460               (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value)
461                   ? (MaxExponent<Lhs>::value > MaxExponent<int>::value
462                          ? LEFT_PROMOTION
463                          : DEFAULT_PROMOTION)
464                   : (MaxExponent<Rhs>::value > MaxExponent<int>::value
465                          ? RIGHT_PROMOTION
466                          : DEFAULT_PROMOTION) >
467 struct ArithmeticPromotion;
468
469 template <typename Lhs, typename Rhs>
470 struct ArithmeticPromotion<Lhs, Rhs, LEFT_PROMOTION> {
471   typedef Lhs type;
472 };
473
474 template <typename Lhs, typename Rhs>
475 struct ArithmeticPromotion<Lhs, Rhs, RIGHT_PROMOTION> {
476   typedef Rhs type;
477 };
478
479 template <typename Lhs, typename Rhs>
480 struct ArithmeticPromotion<Lhs, Rhs, DEFAULT_PROMOTION> {
481   typedef int type;
482 };
483
484 // We can statically check if operations on the provided types can wrap, so we
485 // can skip the checked operations if they're not needed. So, for an integer we
486 // care if the destination type preserves the sign and is twice the width of
487 // the source.
488 template <typename T, typename Lhs, typename Rhs>
489 struct IsIntegerArithmeticSafe {
490   static const bool value = !std::numeric_limits<T>::is_iec559 &&
491                             StaticDstRangeRelationToSrcRange<T, Lhs>::value ==
492                                 NUMERIC_RANGE_CONTAINED &&
493                             sizeof(T) >= (2 * sizeof(Lhs)) &&
494                             StaticDstRangeRelationToSrcRange<T, Rhs>::value !=
495                                 NUMERIC_RANGE_CONTAINED &&
496                             sizeof(T) >= (2 * sizeof(Rhs));
497 };
498
499 }  // namespace internal
500 }  // namespace base
501
502 #endif  // SAFE_MATH_IMPL_H_