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 | |