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