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
19namespace angle
20{
21
22namespace base
23{
24namespace 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.
32template <size_t Size, bool IsSigned>
33struct IntegerForSizeAndSign;
34template <>
35struct IntegerForSizeAndSign<1, true>
36{
37 typedef int8_t type;
38};
39template <>
40struct IntegerForSizeAndSign<1, false>
41{
42 typedef uint8_t type;
43};
44template <>
45struct IntegerForSizeAndSign<2, true>
46{
47 typedef int16_t type;
48};
49template <>
50struct IntegerForSizeAndSign<2, false>
51{
52 typedef uint16_t type;
53};
54template <>
55struct IntegerForSizeAndSign<4, true>
56{
57 typedef int32_t type;
58};
59template <>
60struct IntegerForSizeAndSign<4, false>
61{
62 typedef uint32_t type;
63};
64template <>
65struct IntegerForSizeAndSign<8, true>
66{
67 typedef int64_t type;
68};
69template <>
70struct 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
79template <typename Integer>
80struct 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
88template <typename Integer>
89struct 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
97template <typename Integer>
98struct 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
106template <typename Integer>
107struct 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.
117template <typename Numeric,
118 bool IsInteger = std::numeric_limits<Numeric>::is_integer,
119 bool IsFloat = std::numeric_limits<Numeric>::is_iec559>
120struct UnsignedOrFloatForSize;
121
122template <typename Numeric>
123struct UnsignedOrFloatForSize<Numeric, true, false>
124{
125 typedef typename UnsignedIntegerForSize<Numeric>::type type;
126};
127
128template <typename Numeric>
129struct UnsignedOrFloatForSize<Numeric, false, true>
130{
131 typedef Numeric type;
132};
133
134// Helper templates for integer manipulations.
135
136template <typename T>
137constexpr 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.
145template <typename T>
146constexpr 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
155template <typename T>
156typename std::enable_if<std::numeric_limits<T>::is_integer, T>::type
157CheckedAdd(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
185template <typename T>
186typename std::enable_if<std::numeric_limits<T>::is_integer, T>::type
187CheckedSub(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.
219template <typename T>
220typename std::enable_if<std::numeric_limits<T>::is_integer && sizeof(T) * 2 <= sizeof(uintmax_t),
221 T>::type
222CheckedMul(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
230template <typename T>
231typename 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
234CheckedMul(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
260template <typename T>
261typename 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
264CheckedMul(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.
271template <typename T>
272T 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
288template <typename T>
289typename std::enable_if<std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed,
290 T>::type
291CheckedMod(T x, T y, RangeConstraint *validity)
292{
293 *validity = y > 0 ? RANGE_VALID : RANGE_INVALID;
294 return static_cast<T>(x % y);
295}
296
297template <typename T>
298typename std::enable_if<std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
299 T>::type
300CheckedMod(T x, T y, RangeConstraint *validity)
301{
302 *validity = RANGE_VALID;
303 return static_cast<T>(x % y);
304}
305
306template <typename T>
307typename std::enable_if<std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed,
308 T>::type
309CheckedNeg(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
316template <typename T>
317typename std::enable_if<std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
318 T>::type
319CheckedNeg(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
326template <typename T>
327typename std::enable_if<std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed,
328 T>::type
329CheckedAbs(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
335template <typename T>
336typename std::enable_if<std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
337 T>::type
338CheckedAbs(T value, RangeConstraint *validity)
339{
340 // T is unsigned, so |value| must already be positive.
341 *validity = RANGE_VALID;
342 return value;
343}
344
345template <typename T>
346typename std::enable_if<std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed,
347 typename UnsignedIntegerForSize<T>::type>::type
348CheckedUnsignedAbs(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
356template <typename T>
357typename std::enable_if<std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
358 T>::type
359CheckedUnsignedAbs(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
376ANGLEBASE_FLOAT_ARITHMETIC_STUBS(Add)
377ANGLEBASE_FLOAT_ARITHMETIC_STUBS(Sub)
378ANGLEBASE_FLOAT_ARITHMETIC_STUBS(Mul)
379ANGLEBASE_FLOAT_ARITHMETIC_STUBS(Div)
380ANGLEBASE_FLOAT_ARITHMETIC_STUBS(Mod)
381
382#undef ANGLEBASE_FLOAT_ARITHMETIC_STUBS
383
384template <typename T>
385typename 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
391template <typename T>
392typename 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.
401enum NumericRepresentation
402{
403 NUMERIC_INTEGER,
404 NUMERIC_FLOATING,
405 NUMERIC_UNKNOWN
406};
407
408template <typename NumericType>
409struct 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
417template <typename T, NumericRepresentation type = GetNumericRepresentation<T>::value>
418class CheckedNumericState
419{};
420
421// Integrals require quite a bit of additional housekeeping to manage state.
422template <typename T>
423class 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.
462template <typename T>
463class 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.
525enum ArithmeticPromotionCategory
526{
527 LEFT_PROMOTION,
528 RIGHT_PROMOTION
529};
530
531template <typename Lhs,
532 typename Rhs = Lhs,
533 ArithmeticPromotionCategory Promotion =
534 (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value) ? LEFT_PROMOTION
535 : RIGHT_PROMOTION>
536struct ArithmeticPromotion;
537
538template <typename Lhs, typename Rhs>
539struct ArithmeticPromotion<Lhs, Rhs, LEFT_PROMOTION>
540{
541 typedef Lhs type;
542};
543
544template <typename Lhs, typename Rhs>
545struct 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.
554template <typename T, typename Lhs, typename Rhs>
555struct 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