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