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