Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(214)

Side by Side Diff: third_party/base/numerics/safe_math_impl.h

Issue 2640143003: Update safe numerics package to get bitwise ops (Closed)
Patch Set: Address reviewer comments Created 3 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « third_party/base/numerics/safe_math.h ('k') | xfa/fde/xml/fde_xml_imp.cpp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright 2014 The Chromium Authors. All rights reserved. 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 2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. 3 // found in the LICENSE file.
4 4
5 #ifndef PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_MATH_IMPL_H_ 5 #ifndef PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_MATH_IMPL_H_
6 #define PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_MATH_IMPL_H_ 6 #define PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_MATH_IMPL_H_
7 7
8 #include <stddef.h> 8 #include <stddef.h>
9 #include <stdint.h> 9 #include <stdint.h>
10 10
11 #include <climits> 11 #include <climits>
12 #include <cmath> 12 #include <cmath>
13 #include <cstdlib> 13 #include <cstdlib>
14 #include <limits> 14 #include <limits>
15 #include <type_traits> 15 #include <type_traits>
16 16
17 #include "third_party/base/macros.h"
18 #include "third_party/base/numerics/safe_conversions.h" 17 #include "third_party/base/numerics/safe_conversions.h"
19 18
20 namespace pdfium { 19 namespace pdfium {
21 namespace base { 20 namespace base {
22 namespace internal { 21 namespace internal {
23 22
24 // Everything from here up to the floating point operations is portable C++, 23 // Everything from here up to the floating point operations is portable C++,
25 // but it may not be fast. This code could be split based on 24 // but it may not be fast. This code could be split based on
26 // platform/architecture and replaced with potentially faster implementations. 25 // platform/architecture and replaced with potentially faster implementations.
27 26
28 // Integer promotion templates used by the portable checked integer arithmetic.
29 template <size_t Size, bool IsSigned>
30 struct IntegerForSizeAndSign;
31 template <>
32 struct IntegerForSizeAndSign<1, true> {
33 typedef int8_t type;
34 };
35 template <>
36 struct IntegerForSizeAndSign<1, false> {
37 typedef uint8_t type;
38 };
39 template <>
40 struct IntegerForSizeAndSign<2, true> {
41 typedef int16_t type;
42 };
43 template <>
44 struct IntegerForSizeAndSign<2, false> {
45 typedef uint16_t type;
46 };
47 template <>
48 struct IntegerForSizeAndSign<4, true> {
49 typedef int32_t type;
50 };
51 template <>
52 struct IntegerForSizeAndSign<4, false> {
53 typedef uint32_t type;
54 };
55 template <>
56 struct IntegerForSizeAndSign<8, true> {
57 typedef int64_t type;
58 };
59 template <>
60 struct IntegerForSizeAndSign<8, false> {
61 typedef uint64_t type;
62 };
63
64 // WARNING: We have no IntegerForSizeAndSign<16, *>. If we ever add one to
65 // support 128-bit math, then the ArithmeticPromotion template below will need
66 // to be updated (or more likely replaced with a decltype expression).
67
68 template <typename Integer>
69 struct UnsignedIntegerForSize {
70 typedef typename std::enable_if<
71 std::numeric_limits<Integer>::is_integer,
72 typename IntegerForSizeAndSign<sizeof(Integer), false>::type>::type type;
73 };
74
75 template <typename Integer>
76 struct SignedIntegerForSize {
77 typedef typename std::enable_if<
78 std::numeric_limits<Integer>::is_integer,
79 typename IntegerForSizeAndSign<sizeof(Integer), true>::type>::type type;
80 };
81
82 template <typename Integer>
83 struct TwiceWiderInteger {
84 typedef typename std::enable_if<
85 std::numeric_limits<Integer>::is_integer,
86 typename IntegerForSizeAndSign<
87 sizeof(Integer) * 2,
88 std::numeric_limits<Integer>::is_signed>::type>::type type;
89 };
90
91 template <typename Integer>
92 struct PositionOfSignBit {
93 static const typename std::enable_if<std::numeric_limits<Integer>::is_integer,
94 size_t>::type value =
95 CHAR_BIT * sizeof(Integer) - 1;
96 };
97
98 // This is used for UnsignedAbs, where we need to support floating-point 27 // This is used for UnsignedAbs, where we need to support floating-point
99 // template instantiations even though we don't actually support the operations. 28 // template instantiations even though we don't actually support the operations.
100 // However, there is no corresponding implementation of e.g. CheckedUnsignedAbs, 29 // However, there is no corresponding implementation of e.g. SafeUnsignedAbs,
101 // so the float versions will not compile. 30 // so the float versions will not compile.
102 template <typename Numeric, 31 template <typename Numeric,
103 bool IsInteger = std::numeric_limits<Numeric>::is_integer, 32 bool IsInteger = std::is_integral<Numeric>::value,
104 bool IsFloat = std::numeric_limits<Numeric>::is_iec559> 33 bool IsFloat = std::is_floating_point<Numeric>::value>
105 struct UnsignedOrFloatForSize; 34 struct UnsignedOrFloatForSize;
106 35
107 template <typename Numeric> 36 template <typename Numeric>
108 struct UnsignedOrFloatForSize<Numeric, true, false> { 37 struct UnsignedOrFloatForSize<Numeric, true, false> {
109 typedef typename UnsignedIntegerForSize<Numeric>::type type; 38 using type = typename std::make_unsigned<Numeric>::type;
110 }; 39 };
111 40
112 template <typename Numeric> 41 template <typename Numeric>
113 struct UnsignedOrFloatForSize<Numeric, false, true> { 42 struct UnsignedOrFloatForSize<Numeric, false, true> {
114 typedef Numeric type; 43 using type = Numeric;
115 }; 44 };
116 45
117 // Helper templates for integer manipulations. 46 // Probe for builtin math overflow support on Clang and version check on GCC.
47 #if defined(__has_builtin)
48 #define USE_OVERFLOW_BUILTINS (__has_builtin(__builtin_add_overflow))
49 #elif defined(__GNUC__)
50 #define USE_OVERFLOW_BUILTINS (__GNUC__ >= 5)
51 #else
52 #define USE_OVERFLOW_BUILTINS (0)
53 #endif
118 54
119 template <typename T> 55 template <typename T>
120 constexpr bool HasSignBit(T x) { 56 bool CheckedAddImpl(T x, T y, T* result) {
121 // Cast to unsigned since right shift on signed is undefined. 57 static_assert(std::is_integral<T>::value, "Type must be integral");
122 return !!(static_cast<typename UnsignedIntegerForSize<T>::type>(x) >>
123 PositionOfSignBit<T>::value);
124 }
125
126 // This wrapper undoes the standard integer promotions.
127 template <typename T>
128 constexpr T BinaryComplement(T x) {
129 return static_cast<T>(~x);
130 }
131
132 // Here are the actual portable checked integer math implementations.
133 // TODO(jschuh): Break this code out from the enable_if pattern and find a clean
134 // way to coalesce things into the CheckedNumericState specializations below.
135
136 template <typename T>
137 typename std::enable_if<std::numeric_limits<T>::is_integer, T>::type
138 CheckedAdd(T x, T y, RangeConstraint* validity) {
139 // Since the value of x+y is undefined if we have a signed type, we compute 58 // Since the value of x+y is undefined if we have a signed type, we compute
140 // it using the unsigned type of the same size. 59 // it using the unsigned type of the same size.
141 typedef typename UnsignedIntegerForSize<T>::type UnsignedDst; 60 using UnsignedDst = typename std::make_unsigned<T>::type;
61 using SignedDst = typename std::make_signed<T>::type;
142 UnsignedDst ux = static_cast<UnsignedDst>(x); 62 UnsignedDst ux = static_cast<UnsignedDst>(x);
143 UnsignedDst uy = static_cast<UnsignedDst>(y); 63 UnsignedDst uy = static_cast<UnsignedDst>(y);
144 UnsignedDst uresult = static_cast<UnsignedDst>(ux + uy); 64 UnsignedDst uresult = static_cast<UnsignedDst>(ux + uy);
65 *result = static_cast<T>(uresult);
145 // Addition is valid if the sign of (x + y) is equal to either that of x or 66 // Addition is valid if the sign of (x + y) is equal to either that of x or
146 // that of y. 67 // that of y.
147 if (std::numeric_limits<T>::is_signed) { 68 return (std::is_signed<T>::value)
148 if (HasSignBit(BinaryComplement( 69 ? static_cast<SignedDst>((uresult ^ ux) & (uresult ^ uy)) >= 0
149 static_cast<UnsignedDst>((uresult ^ ux) & (uresult ^ uy))))) { 70 : uresult >= uy; // Unsigned is either valid or underflow.
150 *validity = RANGE_VALID; 71 }
151 } else { // Direction of wrap is inverse of result sign. 72
152 *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW; 73 template <typename T, typename U, class Enable = void>
74 struct CheckedAddOp {};
75
76 template <typename T, typename U>
77 struct CheckedAddOp<T,
78 U,
79 typename std::enable_if<std::is_integral<T>::value &&
80 std::is_integral<U>::value>::type> {
81 using result_type = typename MaxExponentPromotion<T, U>::type;
82 template <typename V>
83 static bool Do(T x, U y, V* result) {
84 #if USE_OVERFLOW_BUILTINS
85 return !__builtin_add_overflow(x, y, result);
86 #else
87 using Promotion = typename BigEnoughPromotion<T, U>::type;
88 Promotion presult;
89 // Fail if either operand is out of range for the promoted type.
90 // TODO(jschuh): This could be made to work for a broader range of values.
91 bool is_valid = IsValueInRangeForNumericType<Promotion>(x) &&
92 IsValueInRangeForNumericType<Promotion>(y);
93
94 if (IsIntegerArithmeticSafe<Promotion, T, U>::value) {
95 presult = static_cast<Promotion>(x) + static_cast<Promotion>(y);
96 } else {
97 is_valid &= CheckedAddImpl(static_cast<Promotion>(x),
98 static_cast<Promotion>(y), &presult);
153 } 99 }
154 } else { // Unsigned is either valid or overflow. 100 *result = static_cast<V>(presult);
155 *validity = BinaryComplement(x) >= y ? RANGE_VALID : RANGE_OVERFLOW; 101 return is_valid && IsValueInRangeForNumericType<V>(presult);
156 } 102 #endif
157 return static_cast<T>(uresult); 103 }
158 } 104 };
159 105
160 template <typename T> 106 template <typename T>
161 typename std::enable_if<std::numeric_limits<T>::is_integer, T>::type 107 bool CheckedSubImpl(T x, T y, T* result) {
162 CheckedSub(T x, T y, RangeConstraint* validity) { 108 static_assert(std::is_integral<T>::value, "Type must be integral");
163 // Since the value of x+y is undefined if we have a signed type, we compute 109 // Since the value of x+y is undefined if we have a signed type, we compute
164 // it using the unsigned type of the same size. 110 // it using the unsigned type of the same size.
165 typedef typename UnsignedIntegerForSize<T>::type UnsignedDst; 111 using UnsignedDst = typename std::make_unsigned<T>::type;
112 using SignedDst = typename std::make_signed<T>::type;
166 UnsignedDst ux = static_cast<UnsignedDst>(x); 113 UnsignedDst ux = static_cast<UnsignedDst>(x);
167 UnsignedDst uy = static_cast<UnsignedDst>(y); 114 UnsignedDst uy = static_cast<UnsignedDst>(y);
168 UnsignedDst uresult = static_cast<UnsignedDst>(ux - uy); 115 UnsignedDst uresult = static_cast<UnsignedDst>(ux - uy);
116 *result = static_cast<T>(uresult);
169 // Subtraction is valid if either x and y have same sign, or (x-y) and x have 117 // Subtraction is valid if either x and y have same sign, or (x-y) and x have
170 // the same sign. 118 // the same sign.
171 if (std::numeric_limits<T>::is_signed) { 119 return (std::is_signed<T>::value)
172 if (HasSignBit(BinaryComplement( 120 ? static_cast<SignedDst>((uresult ^ ux) & (ux ^ uy)) >= 0
173 static_cast<UnsignedDst>((uresult ^ ux) & (ux ^ uy))))) { 121 : x >= y;
174 *validity = RANGE_VALID; 122 }
175 } else { // Direction of wrap is inverse of result sign. 123
176 *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW; 124 template <typename T, typename U, class Enable = void>
125 struct CheckedSubOp {};
126
127 template <typename T, typename U>
128 struct CheckedSubOp<T,
129 U,
130 typename std::enable_if<std::is_integral<T>::value &&
131 std::is_integral<U>::value>::type> {
132 using result_type = typename MaxExponentPromotion<T, U>::type;
133 template <typename V>
134 static bool Do(T x, U y, V* result) {
135 #if USE_OVERFLOW_BUILTINS
136 return !__builtin_sub_overflow(x, y, result);
137 #else
138 using Promotion = typename BigEnoughPromotion<T, U>::type;
139 Promotion presult;
140 // Fail if either operand is out of range for the promoted type.
141 // TODO(jschuh): This could be made to work for a broader range of values.
142 bool is_valid = IsValueInRangeForNumericType<Promotion>(x) &&
143 IsValueInRangeForNumericType<Promotion>(y);
144
145 if (IsIntegerArithmeticSafe<Promotion, T, U>::value) {
146 presult = static_cast<Promotion>(x) - static_cast<Promotion>(y);
147 } else {
148 is_valid &= CheckedSubImpl(static_cast<Promotion>(x),
149 static_cast<Promotion>(y), &presult);
177 } 150 }
178 } else { // Unsigned is either valid or underflow. 151 *result = static_cast<V>(presult);
179 *validity = x >= y ? RANGE_VALID : RANGE_UNDERFLOW; 152 return is_valid && IsValueInRangeForNumericType<V>(presult);
180 } 153 #endif
181 return static_cast<T>(uresult); 154 }
182 } 155 };
183 156
184 // Integer multiplication is a bit complicated. In the fast case we just
185 // we just promote to a twice wider type, and range check the result. In the
186 // slow case we need to manually check that the result won't be truncated by
187 // checking with division against the appropriate bound.
188 template <typename T> 157 template <typename T>
189 typename std::enable_if<std::numeric_limits<T>::is_integer && 158 bool CheckedMulImpl(T x, T y, T* result) {
190 sizeof(T) * 2 <= sizeof(uintmax_t), 159 static_assert(std::is_integral<T>::value, "Type must be integral");
191 T>::type 160 // Since the value of x*y is potentially undefined if we have a signed type,
192 CheckedMul(T x, T y, RangeConstraint* validity) { 161 // we compute it using the unsigned type of the same size.
193 typedef typename TwiceWiderInteger<T>::type IntermediateType; 162 using UnsignedDst = typename std::make_unsigned<T>::type;
194 IntermediateType tmp = 163 using SignedDst = typename std::make_signed<T>::type;
195 static_cast<IntermediateType>(x) * static_cast<IntermediateType>(y); 164 const UnsignedDst ux = SafeUnsignedAbs(x);
196 *validity = DstRangeRelationToSrcRange<T>(tmp); 165 const UnsignedDst uy = SafeUnsignedAbs(y);
197 return static_cast<T>(tmp); 166 UnsignedDst uresult = static_cast<UnsignedDst>(ux * uy);
198 } 167 const bool is_negative =
199 168 std::is_signed<T>::value && static_cast<SignedDst>(x ^ y) < 0;
200 template <typename T> 169 *result = is_negative ? 0 - uresult : uresult;
201 typename std::enable_if<std::numeric_limits<T>::is_integer && 170 // We have a fast out for unsigned identity or zero on the second operand.
202 std::numeric_limits<T>::is_signed && 171 // After that it's an unsigned overflow check on the absolute value, with
203 (sizeof(T) * 2 > sizeof(uintmax_t)), 172 // a +1 bound for a negative result.
204 T>::type 173 return uy <= UnsignedDst(!std::is_signed<T>::value || is_negative) ||
205 CheckedMul(T x, T y, RangeConstraint* validity) { 174 ux <= (std::numeric_limits<T>::max() + UnsignedDst(is_negative)) / uy;
206 // If either side is zero then the result will be zero. 175 }
207 if (!x || !y) { 176
208 *validity = RANGE_VALID; 177 template <typename T, typename U, class Enable = void>
209 return static_cast<T>(0); 178 struct CheckedMulOp {};
210 } 179
211 if (x > 0) { 180 template <typename T, typename U>
212 if (y > 0) { 181 struct CheckedMulOp<T,
213 *validity = 182 U,
214 x <= std::numeric_limits<T>::max() / y ? RANGE_VALID : RANGE_OVERFLOW; 183 typename std::enable_if<std::is_integral<T>::value &&
184 std::is_integral<U>::value>::type> {
185 using result_type = typename MaxExponentPromotion<T, U>::type;
186 template <typename V>
187 static bool Do(T x, U y, V* result) {
188 #if USE_OVERFLOW_BUILTINS
189 #if defined(__clang__)
190 // TODO(jschuh): Get the Clang runtime library issues sorted out so we can
191 // support full-width, mixed-sign multiply builtins.
192 // https://crbug.com/613003
193 static const bool kUseMaxInt =
194 // Narrower type than uintptr_t is always safe.
195 std::numeric_limits<__typeof__(x * y)>::digits <
196 std::numeric_limits<intptr_t>::digits ||
197 // Safe for intptr_t and uintptr_t if the sign matches.
198 (IntegerBitsPlusSign<__typeof__(x * y)>::value ==
199 IntegerBitsPlusSign<intptr_t>::value &&
200 std::is_signed<T>::value == std::is_signed<U>::value);
201 #else
202 static const bool kUseMaxInt = true;
203 #endif
204 if (kUseMaxInt)
205 return !__builtin_mul_overflow(x, y, result);
206 #endif
207 using Promotion = typename FastIntegerArithmeticPromotion<T, U>::type;
208 Promotion presult;
209 // Fail if either operand is out of range for the promoted type.
210 // TODO(jschuh): This could be made to work for a broader range of values.
211 bool is_valid = IsValueInRangeForNumericType<Promotion>(x) &&
212 IsValueInRangeForNumericType<Promotion>(y);
213
214 if (IsIntegerArithmeticSafe<Promotion, T, U>::value) {
215 presult = static_cast<Promotion>(x) * static_cast<Promotion>(y);
215 } else { 216 } else {
216 *validity = y >= std::numeric_limits<T>::min() / x ? RANGE_VALID 217 is_valid &= CheckedMulImpl(static_cast<Promotion>(x),
217 : RANGE_UNDERFLOW; 218 static_cast<Promotion>(y), &presult);
218 } 219 }
219 } else { 220 *result = static_cast<V>(presult);
220 if (y > 0) { 221 return is_valid && IsValueInRangeForNumericType<V>(presult);
221 *validity = x >= std::numeric_limits<T>::min() / y ? RANGE_VALID 222 }
222 : RANGE_UNDERFLOW; 223 };
223 } else { 224
224 *validity = 225 // Avoid poluting the namespace once we're done with the macro.
225 y >= std::numeric_limits<T>::max() / x ? RANGE_VALID : RANGE_OVERFLOW; 226 #undef USE_OVERFLOW_BUILTINS
226 }
227 }
228 return static_cast<T>(*validity == RANGE_VALID ? x * y : 0);
229 }
230
231 template <typename T>
232 typename std::enable_if<std::numeric_limits<T>::is_integer &&
233 !std::numeric_limits<T>::is_signed &&
234 (sizeof(T) * 2 > sizeof(uintmax_t)),
235 T>::type
236 CheckedMul(T x, T y, RangeConstraint* validity) {
237 *validity = (y == 0 || x <= std::numeric_limits<T>::max() / y)
238 ? RANGE_VALID
239 : RANGE_OVERFLOW;
240 return static_cast<T>(*validity == RANGE_VALID ? x * y : 0);
241 }
242 227
243 // Division just requires a check for a zero denominator or an invalid negation 228 // Division just requires a check for a zero denominator or an invalid negation
244 // on signed min/-1. 229 // on signed min/-1.
245 template <typename T> 230 template <typename T>
246 T CheckedDiv(T x, 231 bool CheckedDivImpl(T x, T y, T* result) {
247 T y, 232 static_assert(std::is_integral<T>::value, "Type must be integral");
248 RangeConstraint* validity, 233 if (y && (!std::is_signed<T>::value ||
249 typename std::enable_if<std::numeric_limits<T>::is_integer, 234 x != std::numeric_limits<T>::lowest() || y != static_cast<T>(-1))) {
250 int>::type = 0) { 235 *result = x / y;
251 if (y == 0) { 236 return true;
252 *validity = RANGE_INVALID; 237 }
253 return static_cast<T>(0); 238 return false;
254 } 239 }
255 if (std::numeric_limits<T>::is_signed && x == std::numeric_limits<T>::min() && 240
256 y == static_cast<T>(-1)) { 241 template <typename T, typename U, class Enable = void>
257 *validity = RANGE_OVERFLOW; 242 struct CheckedDivOp {};
258 return std::numeric_limits<T>::min(); 243
259 } 244 template <typename T, typename U>
260 245 struct CheckedDivOp<T,
261 *validity = RANGE_VALID; 246 U,
262 return static_cast<T>(x / y); 247 typename std::enable_if<std::is_integral<T>::value &&
263 } 248 std::is_integral<U>::value>::type> {
249 using result_type = typename MaxExponentPromotion<T, U>::type;
250 template <typename V>
251 static bool Do(T x, U y, V* result) {
252 using Promotion = typename BigEnoughPromotion<T, U>::type;
253 Promotion presult;
254 // Fail if either operand is out of range for the promoted type.
255 // TODO(jschuh): This could be made to work for a broader range of values.
256 bool is_valid = IsValueInRangeForNumericType<Promotion>(x) &&
257 IsValueInRangeForNumericType<Promotion>(y);
258 is_valid &= CheckedDivImpl(static_cast<Promotion>(x),
259 static_cast<Promotion>(y), &presult);
260 *result = static_cast<V>(presult);
261 return is_valid && IsValueInRangeForNumericType<V>(presult);
262 }
263 };
264 264
265 template <typename T> 265 template <typename T>
266 typename std::enable_if<std::numeric_limits<T>::is_integer && 266 bool CheckedModImpl(T x, T y, T* result) {
267 std::numeric_limits<T>::is_signed, 267 static_assert(std::is_integral<T>::value, "Type must be integral");
268 T>::type 268 if (y > 0) {
269 CheckedMod(T x, T y, RangeConstraint* validity) { 269 *result = static_cast<T>(x % y);
270 *validity = y > 0 ? RANGE_VALID : RANGE_INVALID; 270 return true;
271 return static_cast<T>(*validity == RANGE_VALID ? x % y : 0); 271 }
272 } 272 return false;
273 273 }
274 template <typename T> 274
275 typename std::enable_if<std::numeric_limits<T>::is_integer && 275 template <typename T, typename U, class Enable = void>
276 !std::numeric_limits<T>::is_signed, 276 struct CheckedModOp {};
277 T>::type 277
278 CheckedMod(T x, T y, RangeConstraint* validity) { 278 template <typename T, typename U>
279 *validity = y != 0 ? RANGE_VALID : RANGE_INVALID; 279 struct CheckedModOp<T,
280 return static_cast<T>(*validity == RANGE_VALID ? x % y : 0); 280 U,
281 } 281 typename std::enable_if<std::is_integral<T>::value &&
282 282 std::is_integral<U>::value>::type> {
283 template <typename T> 283 using result_type = typename MaxExponentPromotion<T, U>::type;
284 typename std::enable_if<std::numeric_limits<T>::is_integer && 284 template <typename V>
285 std::numeric_limits<T>::is_signed, 285 static bool Do(T x, U y, V* result) {
286 T>::type 286 using Promotion = typename BigEnoughPromotion<T, U>::type;
287 CheckedNeg(T value, RangeConstraint* validity) { 287 Promotion presult;
288 *validity = 288 bool is_valid = CheckedModImpl(static_cast<Promotion>(x),
289 value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW; 289 static_cast<Promotion>(y), &presult);
290 // The negation of signed min is min, so catch that one. 290 *result = static_cast<V>(presult);
291 return static_cast<T>(*validity == RANGE_VALID ? -value : 0); 291 return is_valid && IsValueInRangeForNumericType<V>(presult);
292 } 292 }
293 293 };
294 template <typename T> 294
295 typename std::enable_if<std::numeric_limits<T>::is_integer && 295 template <typename T, typename U, class Enable = void>
296 !std::numeric_limits<T>::is_signed, 296 struct CheckedLshOp {};
297 T>::type 297
298 CheckedNeg(T value, RangeConstraint* validity) { 298 // Left shift. Shifts less than 0 or greater than or equal to the number
299 // The only legal unsigned negation is zero. 299 // of bits in the promoted type are undefined. Shifts of negative values
300 *validity = value ? RANGE_UNDERFLOW : RANGE_VALID; 300 // are undefined. Otherwise it is defined when the result fits.
301 return static_cast<T>( 301 template <typename T, typename U>
302 *validity == RANGE_VALID 302 struct CheckedLshOp<T,
303 ? -static_cast<typename SignedIntegerForSize<T>::type>(value) 303 U,
304 : 0); 304 typename std::enable_if<std::is_integral<T>::value &&
305 } 305 std::is_integral<U>::value>::type> {
306 306 using result_type = T;
307 template <typename T> 307 template <typename V>
308 typename std::enable_if<std::numeric_limits<T>::is_integer && 308 static bool Do(T x, U shift, V* result) {
309 std::numeric_limits<T>::is_signed, 309 using ShiftType = typename std::make_unsigned<T>::type;
310 T>::type 310 static const ShiftType kBitWidth = IntegerBitsPlusSign<T>::value;
311 CheckedAbs(T value, RangeConstraint* validity) { 311 const ShiftType real_shift = static_cast<ShiftType>(shift);
312 *validity = 312 // Signed shift is not legal on negative values.
313 value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW; 313 if (!IsValueNegative(x) && real_shift < kBitWidth) {
314 return static_cast<T>(*validity == RANGE_VALID ? std::abs(value) : 0); 314 // Just use a multiplication because it's easy.
315 } 315 // TODO(jschuh): This could probably be made more efficient.
316 316 if (!std::is_signed<T>::value || real_shift != kBitWidth - 1)
317 template <typename T> 317 return CheckedMulOp<T, T>::Do(x, static_cast<T>(1) << shift, result);
318 typename std::enable_if<std::numeric_limits<T>::is_integer && 318 return !x; // Special case zero for a full width signed shift.
319 !std::numeric_limits<T>::is_signed, 319 }
320 T>::type 320 return false;
321 CheckedAbs(T value, RangeConstraint* validity) { 321 }
322 // T is unsigned, so |value| must already be positive. 322 };
323 *validity = RANGE_VALID; 323
324 return value; 324 template <typename T, typename U, class Enable = void>
325 } 325 struct CheckedRshOp {};
326 326
327 template <typename T> 327 // Right shift. Shifts less than 0 or greater than or equal to the number
328 typename std::enable_if<std::numeric_limits<T>::is_integer && 328 // of bits in the promoted type are undefined. Otherwise, it is always defined,
329 std::numeric_limits<T>::is_signed, 329 // but a right shift of a negative value is implementation-dependent.
330 typename UnsignedIntegerForSize<T>::type>::type 330 template <typename T, typename U>
331 CheckedUnsignedAbs(T value) { 331 struct CheckedRshOp<T,
332 typedef typename UnsignedIntegerForSize<T>::type UnsignedT; 332 U,
333 return value == std::numeric_limits<T>::min() 333 typename std::enable_if<std::is_integral<T>::value &&
334 ? static_cast<UnsignedT>(std::numeric_limits<T>::max()) + 1 334 std::is_integral<U>::value>::type> {
335 : static_cast<UnsignedT>(std::abs(value)); 335 using result_type = T;
336 } 336 template <typename V = result_type>
337 337 static bool Do(T x, U shift, V* result) {
338 template <typename T> 338 // Use the type conversion push negative values out of range.
339 typename std::enable_if<std::numeric_limits<T>::is_integer && 339 using ShiftType = typename std::make_unsigned<T>::type;
340 !std::numeric_limits<T>::is_signed, 340 if (static_cast<ShiftType>(shift) < IntegerBitsPlusSign<T>::value) {
341 T>::type 341 T tmp = x >> shift;
342 CheckedUnsignedAbs(T value) { 342 *result = static_cast<V>(tmp);
343 // T is unsigned, so |value| must already be positive. 343 return IsValueInRangeForNumericType<V>(tmp);
344 return static_cast<T>(value); 344 }
345 } 345 return false;
346 346 }
347 // These are the floating point stubs that the compiler needs to see. Only the 347 };
348 // negation operation is ever called. 348
349 #define BASE_FLOAT_ARITHMETIC_STUBS(NAME) \ 349 template <typename T, typename U, class Enable = void>
350 template <typename T> \ 350 struct CheckedAndOp {};
351 typename std::enable_if<std::numeric_limits<T>::is_iec559, T>::type \ 351
352 Checked##NAME(T, T, RangeConstraint*) { \ 352 // For simplicity we support only unsigned integer results.
353 NOTREACHED(); \ 353 template <typename T, typename U>
354 return static_cast<T>(0); \ 354 struct CheckedAndOp<T,
355 } 355 U,
356 356 typename std::enable_if<std::is_integral<T>::value &&
357 BASE_FLOAT_ARITHMETIC_STUBS(Add) 357 std::is_integral<U>::value>::type> {
358 BASE_FLOAT_ARITHMETIC_STUBS(Sub) 358 using result_type = typename std::make_unsigned<
359 BASE_FLOAT_ARITHMETIC_STUBS(Mul) 359 typename MaxExponentPromotion<T, U>::type>::type;
360 BASE_FLOAT_ARITHMETIC_STUBS(Div) 360 template <typename V = result_type>
361 BASE_FLOAT_ARITHMETIC_STUBS(Mod) 361 static bool Do(T x, U y, V* result) {
362 362 result_type tmp = static_cast<result_type>(x) & static_cast<result_type>(y);
363 #undef BASE_FLOAT_ARITHMETIC_STUBS 363 *result = static_cast<V>(tmp);
364 364 return IsValueInRangeForNumericType<V>(tmp);
365 template <typename T> 365 }
366 typename std::enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedNeg( 366 };
367 T value, 367
368 RangeConstraint*) { 368 template <typename T, typename U, class Enable = void>
369 return static_cast<T>(-value); 369 struct CheckedOrOp {};
370 } 370
371 371 // For simplicity we support only unsigned integers.
372 template <typename T> 372 template <typename T, typename U>
373 typename std::enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedAbs( 373 struct CheckedOrOp<T,
374 T value, 374 U,
375 RangeConstraint*) { 375 typename std::enable_if<std::is_integral<T>::value &&
376 return static_cast<T>(std::abs(value)); 376 std::is_integral<U>::value>::type> {
377 using result_type = typename std::make_unsigned<
378 typename MaxExponentPromotion<T, U>::type>::type;
379 template <typename V = result_type>
380 static bool Do(T x, U y, V* result) {
381 result_type tmp = static_cast<result_type>(x) | static_cast<result_type>(y);
382 *result = static_cast<V>(tmp);
383 return IsValueInRangeForNumericType<V>(tmp);
384 }
385 };
386
387 template <typename T, typename U, class Enable = void>
388 struct CheckedXorOp {};
389
390 // For simplicity we support only unsigned integers.
391 template <typename T, typename U>
392 struct CheckedXorOp<T,
393 U,
394 typename std::enable_if<std::is_integral<T>::value &&
395 std::is_integral<U>::value>::type> {
396 using result_type = typename std::make_unsigned<
397 typename MaxExponentPromotion<T, U>::type>::type;
398 template <typename V = result_type>
399 static bool Do(T x, U y, V* result) {
400 result_type tmp = static_cast<result_type>(x) ^ static_cast<result_type>(y);
401 *result = static_cast<V>(tmp);
402 return IsValueInRangeForNumericType<V>(tmp);
403 }
404 };
405
406 // Max doesn't really need to be implemented this way because it can't fail,
407 // but it makes the code much cleaner to use the MathOp wrappers.
408 template <typename T, typename U, class Enable = void>
409 struct CheckedMaxOp {};
410
411 template <typename T, typename U>
412 struct CheckedMaxOp<
413 T,
414 U,
415 typename std::enable_if<std::is_arithmetic<T>::value &&
416 std::is_arithmetic<U>::value>::type> {
417 using result_type = typename MaxExponentPromotion<T, U>::type;
418 template <typename V = result_type>
419 static bool Do(T x, U y, V* result) {
420 *result = IsGreater<T, U>::Test(x, y) ? static_cast<result_type>(x)
421 : static_cast<result_type>(y);
422 return true;
423 }
424 };
425
426 // Min doesn't really need to be implemented this way because it can't fail,
427 // but it makes the code much cleaner to use the MathOp wrappers.
428 template <typename T, typename U, class Enable = void>
429 struct CheckedMinOp {};
430
431 template <typename T, typename U>
432 struct CheckedMinOp<
433 T,
434 U,
435 typename std::enable_if<std::is_arithmetic<T>::value &&
436 std::is_arithmetic<U>::value>::type> {
437 using result_type = typename LowestValuePromotion<T, U>::type;
438 template <typename V = result_type>
439 static bool Do(T x, U y, V* result) {
440 *result = IsLess<T, U>::Test(x, y) ? static_cast<result_type>(x)
441 : static_cast<result_type>(y);
442 return true;
443 }
444 };
445
446 // This is just boilerplate that wraps the standard floating point arithmetic.
447 // A macro isn't the nicest solution, but it beats rewriting these repeatedly.
448 #define BASE_FLOAT_ARITHMETIC_OPS(NAME, OP) \
449 template <typename T, typename U> \
450 struct Checked##NAME##Op< \
451 T, U, typename std::enable_if<std::is_floating_point<T>::value || \
452 std::is_floating_point<U>::value>::type> { \
453 using result_type = typename MaxExponentPromotion<T, U>::type; \
454 template <typename V> \
455 static bool Do(T x, U y, V* result) { \
456 using Promotion = typename MaxExponentPromotion<T, U>::type; \
457 Promotion presult = x OP y; \
458 *result = static_cast<V>(presult); \
459 return IsValueInRangeForNumericType<V>(presult); \
460 } \
461 };
462
463 BASE_FLOAT_ARITHMETIC_OPS(Add, +)
464 BASE_FLOAT_ARITHMETIC_OPS(Sub, -)
465 BASE_FLOAT_ARITHMETIC_OPS(Mul, *)
466 BASE_FLOAT_ARITHMETIC_OPS(Div, /)
467
468 #undef BASE_FLOAT_ARITHMETIC_OPS
469
470 // Wrap the unary operations to allow SFINAE when instantiating integrals versus
471 // floating points. These don't perform any overflow checking. Rather, they
472 // exhibit well-defined overflow semantics and rely on the caller to detect
473 // if an overflow occured.
474
475 template <typename T,
476 typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
477 constexpr T NegateWrapper(T value) {
478 using UnsignedT = typename std::make_unsigned<T>::type;
479 // This will compile to a NEG on Intel, and is normal negation on ARM.
480 return static_cast<T>(UnsignedT(0) - static_cast<UnsignedT>(value));
481 }
482
483 template <
484 typename T,
485 typename std::enable_if<std::is_floating_point<T>::value>::type* = nullptr>
486 constexpr T NegateWrapper(T value) {
487 return -value;
488 }
489
490 template <typename T,
491 typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
492 constexpr typename std::make_unsigned<T>::type InvertWrapper(T value) {
493 return ~value;
494 }
495
496 template <typename T,
497 typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
498 constexpr T AbsWrapper(T value) {
499 return static_cast<T>(SafeUnsignedAbs(value));
500 }
501
502 template <
503 typename T,
504 typename std::enable_if<std::is_floating_point<T>::value>::type* = nullptr>
505 constexpr T AbsWrapper(T value) {
506 return value < 0 ? -value : value;
377 } 507 }
378 508
379 // Floats carry around their validity state with them, but integers do not. So, 509 // Floats carry around their validity state with them, but integers do not. So,
380 // we wrap the underlying value in a specialization in order to hide that detail 510 // we wrap the underlying value in a specialization in order to hide that detail
381 // and expose an interface via accessors. 511 // and expose an interface via accessors.
382 enum NumericRepresentation { 512 enum NumericRepresentation {
383 NUMERIC_INTEGER, 513 NUMERIC_INTEGER,
384 NUMERIC_FLOATING, 514 NUMERIC_FLOATING,
385 NUMERIC_UNKNOWN 515 NUMERIC_UNKNOWN
386 }; 516 };
387 517
388 template <typename NumericType> 518 template <typename NumericType>
389 struct GetNumericRepresentation { 519 struct GetNumericRepresentation {
390 static const NumericRepresentation value = 520 static const NumericRepresentation value =
391 std::numeric_limits<NumericType>::is_integer 521 std::is_integral<NumericType>::value
392 ? NUMERIC_INTEGER 522 ? NUMERIC_INTEGER
393 : (std::numeric_limits<NumericType>::is_iec559 ? NUMERIC_FLOATING 523 : (std::is_floating_point<NumericType>::value ? NUMERIC_FLOATING
394 : NUMERIC_UNKNOWN); 524 : NUMERIC_UNKNOWN);
395 }; 525 };
396 526
397 template <typename T, NumericRepresentation type = 527 template <typename T, NumericRepresentation type =
398 GetNumericRepresentation<T>::value> 528 GetNumericRepresentation<T>::value>
399 class CheckedNumericState {}; 529 class CheckedNumericState {};
400 530
401 // Integrals require quite a bit of additional housekeeping to manage state. 531 // Integrals require quite a bit of additional housekeeping to manage state.
402 template <typename T> 532 template <typename T>
403 class CheckedNumericState<T, NUMERIC_INTEGER> { 533 class CheckedNumericState<T, NUMERIC_INTEGER> {
404 private: 534 private:
535 // is_valid_ precedes value_ because member intializers in the constructors
536 // are evaluated in field order, and is_valid_ must be read when initializing
537 // value_.
538 bool is_valid_;
405 T value_; 539 T value_;
406 RangeConstraint validity_ : CHAR_BIT; // Actually requires only two bits. 540
541 // Ensures that a type conversion does not trigger undefined behavior.
542 template <typename Src>
543 static constexpr T WellDefinedConversionOrZero(const Src value,
544 const bool is_valid) {
545 using SrcType = typename internal::UnderlyingType<Src>::type;
546 return (std::is_integral<SrcType>::value || is_valid)
547 ? static_cast<T>(value)
548 : static_cast<T>(0);
549 }
407 550
408 public: 551 public:
409 template <typename Src, NumericRepresentation type> 552 template <typename Src, NumericRepresentation type>
410 friend class CheckedNumericState; 553 friend class CheckedNumericState;
411 554
412 CheckedNumericState() : value_(0), validity_(RANGE_VALID) {} 555 constexpr CheckedNumericState() : is_valid_(true), value_(0) {}
413 556
414 template <typename Src> 557 template <typename Src>
415 CheckedNumericState(Src value, RangeConstraint validity) 558 constexpr CheckedNumericState(Src value, bool is_valid)
416 : value_(static_cast<T>(value)), 559 : is_valid_(is_valid && IsValueInRangeForNumericType<T>(value)),
417 validity_(GetRangeConstraint(validity | 560 value_(WellDefinedConversionOrZero(value, is_valid_)) {
418 DstRangeRelationToSrcRange<T>(value))) { 561 static_assert(std::is_arithmetic<Src>::value, "Argument must be numeric.");
419 static_assert(std::numeric_limits<Src>::is_specialized,
420 "Argument must be numeric.");
421 } 562 }
422 563
423 // Copy constructor. 564 // Copy constructor.
424 template <typename Src> 565 template <typename Src>
425 CheckedNumericState(const CheckedNumericState<Src>& rhs) 566 constexpr CheckedNumericState(const CheckedNumericState<Src>& rhs)
426 : value_(static_cast<T>(rhs.value())), 567 : is_valid_(rhs.IsValid()),
427 validity_(GetRangeConstraint( 568 value_(WellDefinedConversionOrZero(rhs.value(), is_valid_)) {}
428 rhs.validity() | DstRangeRelationToSrcRange<T>(rhs.value()))) {}
429 569
430 template <typename Src> 570 template <typename Src>
431 explicit CheckedNumericState( 571 constexpr explicit CheckedNumericState(Src value)
432 Src value, 572 : is_valid_(IsValueInRangeForNumericType<T>(value)),
433 typename std::enable_if<std::numeric_limits<Src>::is_specialized, 573 value_(WellDefinedConversionOrZero(value, is_valid_)) {}
434 int>::type = 0)
435 : value_(static_cast<T>(value)),
436 validity_(DstRangeRelationToSrcRange<T>(value)) {}
437 574
438 RangeConstraint validity() const { return validity_; } 575 constexpr bool is_valid() const { return is_valid_; }
439 T value() const { return value_; } 576 constexpr T value() const { return value_; }
440 }; 577 };
441 578
442 // Floating points maintain their own validity, but need translation wrappers. 579 // Floating points maintain their own validity, but need translation wrappers.
443 template <typename T> 580 template <typename T>
444 class CheckedNumericState<T, NUMERIC_FLOATING> { 581 class CheckedNumericState<T, NUMERIC_FLOATING> {
445 private: 582 private:
446 T value_; 583 T value_;
447 584
585 // Ensures that a type conversion does not trigger undefined behavior.
586 template <typename Src>
587 static constexpr T WellDefinedConversionOrNaN(const Src value,
588 const bool is_valid) {
589 using SrcType = typename internal::UnderlyingType<Src>::type;
590 return (StaticDstRangeRelationToSrcRange<T, SrcType>::value ==
591 NUMERIC_RANGE_CONTAINED ||
592 is_valid)
593 ? static_cast<T>(value)
594 : std::numeric_limits<T>::quiet_NaN();
595 }
596
448 public: 597 public:
449 template <typename Src, NumericRepresentation type> 598 template <typename Src, NumericRepresentation type>
450 friend class CheckedNumericState; 599 friend class CheckedNumericState;
451 600
452 CheckedNumericState() : value_(0.0) {} 601 constexpr CheckedNumericState() : value_(0.0) {}
453 602
454 template <typename Src> 603 template <typename Src>
455 CheckedNumericState( 604 constexpr CheckedNumericState(Src value, bool is_valid)
456 Src value, 605 : value_(WellDefinedConversionOrNaN(value, is_valid)) {}
457 RangeConstraint validity,
458 typename std::enable_if<std::numeric_limits<Src>::is_integer, int>::type =
459 0) {
460 switch (DstRangeRelationToSrcRange<T>(value)) {
461 case RANGE_VALID:
462 value_ = static_cast<T>(value);
463 break;
464
465 case RANGE_UNDERFLOW:
466 value_ = -std::numeric_limits<T>::infinity();
467 break;
468
469 case RANGE_OVERFLOW:
470 value_ = std::numeric_limits<T>::infinity();
471 break;
472
473 case RANGE_INVALID:
474 value_ = std::numeric_limits<T>::quiet_NaN();
475 break;
476
477 default:
478 NOTREACHED();
479 }
480 }
481 606
482 template <typename Src> 607 template <typename Src>
483 explicit CheckedNumericState( 608 constexpr explicit CheckedNumericState(Src value)
484 Src value, 609 : value_(WellDefinedConversionOrNaN(
485 typename std::enable_if<std::numeric_limits<Src>::is_specialized, 610 value,
486 int>::type = 0) 611 IsValueInRangeForNumericType<T>(value))) {}
487 : value_(static_cast<T>(value)) {}
488 612
489 // Copy constructor. 613 // Copy constructor.
490 template <typename Src> 614 template <typename Src>
491 CheckedNumericState(const CheckedNumericState<Src>& rhs) 615 constexpr CheckedNumericState(const CheckedNumericState<Src>& rhs)
492 : value_(static_cast<T>(rhs.value())) {} 616 : value_(WellDefinedConversionOrNaN(
617 rhs.value(),
618 rhs.is_valid() && IsValueInRangeForNumericType<T>(rhs.value()))) {}
493 619
494 RangeConstraint validity() const { 620 constexpr bool is_valid() const {
495 return GetRangeConstraint(value_ <= std::numeric_limits<T>::max(), 621 // Written this way because std::isfinite is not reliably constexpr.
496 value_ >= -std::numeric_limits<T>::max()); 622 // TODO(jschuh): Fix this if the libraries ever get fixed.
623 return value_ <= std::numeric_limits<T>::max() &&
624 value_ >= std::numeric_limits<T>::lowest();
497 } 625 }
498 T value() const { return value_; } 626 constexpr T value() const { return value_; }
499 }; 627 };
500 628
501 // For integers less than 128-bit and floats 32-bit or larger, we have the type 629 template <template <typename, typename, typename> class M,
502 // with the larger maximum exponent take precedence. 630 typename L,
503 enum ArithmeticPromotionCategory { LEFT_PROMOTION, RIGHT_PROMOTION }; 631 typename R>
504 632 struct MathWrapper {
505 template <typename Lhs, 633 using math = M<typename UnderlyingType<L>::type,
506 typename Rhs = Lhs, 634 typename UnderlyingType<R>::type,
507 ArithmeticPromotionCategory Promotion = 635 void>;
508 (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value) 636 using type = typename math::result_type;
509 ? LEFT_PROMOTION
510 : RIGHT_PROMOTION>
511 struct ArithmeticPromotion;
512
513 template <typename Lhs, typename Rhs>
514 struct ArithmeticPromotion<Lhs, Rhs, LEFT_PROMOTION> {
515 typedef Lhs type;
516 };
517
518 template <typename Lhs, typename Rhs>
519 struct ArithmeticPromotion<Lhs, Rhs, RIGHT_PROMOTION> {
520 typedef Rhs type;
521 };
522
523 // We can statically check if operations on the provided types can wrap, so we
524 // can skip the checked operations if they're not needed. So, for an integer we
525 // care if the destination type preserves the sign and is twice the width of
526 // the source.
527 template <typename T, typename Lhs, typename Rhs>
528 struct IsIntegerArithmeticSafe {
529 static const bool value = !std::numeric_limits<T>::is_iec559 &&
530 StaticDstRangeRelationToSrcRange<T, Lhs>::value ==
531 NUMERIC_RANGE_CONTAINED &&
532 sizeof(T) >= (2 * sizeof(Lhs)) &&
533 StaticDstRangeRelationToSrcRange<T, Rhs>::value !=
534 NUMERIC_RANGE_CONTAINED &&
535 sizeof(T) >= (2 * sizeof(Rhs));
536 }; 637 };
537 638
538 } // namespace internal 639 } // namespace internal
539 } // namespace base 640 } // namespace base
540 } // namespace pdfium 641 } // namespace pdfium
541 642
542 #endif // PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_MATH_IMPL_H_ 643 #endif // PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_MATH_IMPL_H_
OLDNEW
« no previous file with comments | « third_party/base/numerics/safe_math.h ('k') | xfa/fde/xml/fde_xml_imp.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698