OLD | NEW |
---|---|
(Empty) | |
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 SAFE_MATH_IMPL_H_ | |
6 #define SAFE_MATH_IMPL_H_ | |
7 | |
8 #include <stdint.h> | |
9 | |
10 #include <cmath> | |
11 #include <cstdlib> | |
12 #include <limits> | |
13 | |
14 #include "base/compiler_specific.h" | |
15 #include "base/macros.h" | |
16 #include "base/template_util.h" | |
17 | |
18 namespace base { | |
19 namespace internal { | |
20 | |
21 using std::numeric_limits; | |
22 | |
23 // Everything from here up to the floating point operations is portable C++, | |
24 // but it may not be fast. This code could be split based on | |
25 // platform/architecture and replaced with potentially faster implementations. | |
26 | |
27 // Integer promotion templates used by the portable checked integer arithmetic. | |
28 template <size_t Size, bool IsSigned> struct IntegerForSizeAndSign {}; | |
29 template <> struct IntegerForSizeAndSign<1, true> { typedef int8_t type; }; | |
30 template <> struct IntegerForSizeAndSign<1, false> { typedef uint8_t type; }; | |
31 template <> struct IntegerForSizeAndSign<2, true> { typedef int16_t type; }; | |
32 template <> struct IntegerForSizeAndSign<2, false> { typedef uint16_t type; }; | |
33 template <> struct IntegerForSizeAndSign<4, true> { typedef int32_t type; }; | |
34 template <> struct IntegerForSizeAndSign<4, false> { typedef uint32_t type; }; | |
35 template <> struct IntegerForSizeAndSign<8, true> { typedef int64_t type; }; | |
36 template <> struct IntegerForSizeAndSign<8, false> { typedef uint64_t type; }; | |
37 // The ArithmeticPromotion template below will need to be updated (or more | |
38 // likely replaced with decltype) if we add support for 128-bit integers). | |
39 | |
40 template <typename Integer> | |
41 struct UnsignedIntegerForSize { | |
42 typedef typename enable_if<numeric_limits<Integer>::is_integer, | |
43 typename IntegerForSizeAndSign<sizeof(Integer), false>::type>::type type; | |
44 }; | |
45 | |
46 template <typename Integer> | |
47 struct SignedIntegerForSize { | |
48 typedef typename enable_if<numeric_limits<Integer>::is_integer, | |
49 typename IntegerForSizeAndSign<sizeof(Integer), true>::type>::type type; | |
50 }; | |
51 | |
52 template <typename Integer> | |
53 struct TwiceWiderInteger { | |
54 typedef typename enable_if<numeric_limits<Integer>::is_integer, | |
55 typename IntegerForSizeAndSign<sizeof(Integer) * 2, | |
56 numeric_limits<Integer>::is_signed>::type>::type type; | |
57 }; | |
58 | |
59 template <typename Integer> | |
60 struct PositionOfSignBit { | |
61 static const typename enable_if<numeric_limits<Integer>::is_integer, | |
62 size_t>::type value = 8 * sizeof(Integer) - 1; | |
Ryan Sleevi
2014/02/10 23:42:41
Does MSVC let you get away with this? I seem to re
jschuh
2014/02/11 00:43:28
Static consts have been supported for quite a whil
| |
63 }; | |
64 | |
65 // Helper templates for integer manipulations. | |
66 | |
67 template <typename T> | |
68 bool HasSignBit(T x) { | |
69 // Cast to unsigned since right shift on signed is undefined. | |
70 return !!(static_cast<typename UnsignedIntegerForSize<T>::type>(x) >> | |
71 PositionOfSignBit<T>::value); | |
72 } | |
73 | |
74 // This wrapper undoes the standard integer promotions. | |
75 template <typename T> | |
76 T BinaryComplement(T x) { | |
77 return ~x; | |
78 } | |
79 | |
80 // Here are the actual portable checked integer implementations. | |
81 | |
82 template <typename T> | |
83 typename enable_if<numeric_limits<T>::is_integer, T>::type | |
84 CheckedAdd(T x, T y, RangeCheckId* validity) { | |
85 // Since the value of x+y is undefined if we have a signed type, we compute | |
86 // it using the unsigned type of the same size. | |
87 typedef typename UnsignedIntegerForSize<T>::type UnsignedDst; | |
88 UnsignedDst ux = static_cast<UnsignedDst>(x); | |
89 UnsignedDst uy = static_cast<UnsignedDst>(y); | |
90 UnsignedDst uresult = ux + uy; | |
91 // Addition is valid if the sign of (x + y) is equal to either that of x or | |
92 // that of y. | |
93 if (numeric_limits<T>::is_signed) { | |
94 if (HasSignBit(BinaryComplement((uresult ^ ux) & (uresult ^ uy)))) | |
95 *validity = TYPE_VALID; | |
96 else // Direction of wrap is inverse of result sign. | |
97 *validity = HasSignBit(uresult) ? TYPE_OVERFLOW : TYPE_UNDERFLOW; | |
98 | |
99 } else { // Unsigned is either valid or overflow. | |
100 *validity = BinaryComplement(x) >= y ? TYPE_VALID : TYPE_OVERFLOW; | |
101 } | |
102 return static_cast<T>(uresult); | |
103 } | |
104 | |
105 template <typename T> | |
106 typename enable_if<numeric_limits<T>::is_integer, T>::type | |
107 CheckedSub(T x, T y, RangeCheckId* validity) { | |
108 // Since the value of x+y is undefined if we have a signed type, we compute | |
109 // it using the unsigned type of the same size. | |
110 typedef typename UnsignedIntegerForSize<T>::type UnsignedDst; | |
111 UnsignedDst ux = static_cast<UnsignedDst>(x); | |
112 UnsignedDst uy = static_cast<UnsignedDst>(y); | |
113 UnsignedDst uresult = ux - uy; | |
114 // Subtraction is valid if either x and y have same sign, or (x-y) and x have | |
115 // the same sign. | |
116 if (numeric_limits<T>::is_signed) { | |
117 if (HasSignBit(BinaryComplement((uresult ^ ux) & (ux ^ uy)))) | |
118 *validity = TYPE_VALID; | |
119 else // Direction of wrap is inverse of result sign. | |
120 *validity = HasSignBit(uresult) ? TYPE_OVERFLOW : TYPE_UNDERFLOW; | |
121 | |
122 } else { // Unsigned is either valid or underflow. | |
123 *validity = x >= y ? TYPE_VALID : TYPE_UNDERFLOW; | |
124 } | |
125 return static_cast<T>(uresult); | |
126 } | |
127 | |
128 // Integer multiplication is a bit complicated. In the fast case we just | |
129 // we just promote to a twice wider type, and range check the result. In the | |
130 // slow case we need to manually check that the result won't be truncated by | |
131 // checking with division against the appropriate bound. | |
132 template <typename T> | |
133 typename enable_if<numeric_limits<T>::is_integer && | |
134 sizeof(T)* 2 <= sizeof(uintmax_t), T>::type | |
135 CheckedMul(T x, T y, RangeCheckId* validity) { | |
136 typedef typename TwiceWiderInteger<T>::type IntermediateType; | |
137 IntermediateType tmp = static_cast<IntermediateType>(x) * | |
138 static_cast<IntermediateType>(y); | |
139 *validity = RangeCheck<T>(tmp); | |
140 return static_cast<T>(tmp); | |
141 } | |
142 | |
143 template <typename T> | |
144 typename enable_if<numeric_limits<T>::is_integer && | |
145 numeric_limits<T>::is_signed && | |
146 (sizeof(T)* 2 > sizeof(uintmax_t)), T>::type | |
147 CheckedMul(T x, T y, RangeCheckId* validity) { | |
148 // if either side is zero then the result will be zero. | |
149 if (!(x || y)) { | |
150 return TYPE_VALID; | |
151 | |
152 } else if (x > 0) { | |
153 if (y > 0) | |
154 *validity = x <= numeric_limits<T>::max() / y ? | |
155 TYPE_VALID : TYPE_OVERFLOW; | |
156 else | |
157 *validity = y >= numeric_limits<T>::min() / x ? | |
158 TYPE_VALID : TYPE_UNDERFLOW; | |
159 | |
160 } else { | |
161 if (y > 0) | |
162 *validity = x >= numeric_limits<T>::min() / y ? | |
163 TYPE_VALID : TYPE_UNDERFLOW; | |
164 else | |
165 *validity = y >= numeric_limits<T>::max() / x ? | |
166 TYPE_VALID : TYPE_OVERFLOW; | |
167 } | |
168 | |
169 return x * y; | |
170 } | |
171 | |
172 template <typename T> | |
173 typename enable_if<numeric_limits<T>::is_integer && | |
174 !numeric_limits<T>::is_signed && | |
175 (sizeof(T)* 2 > sizeof(uintmax_t)), T>::type | |
176 CheckedMul(T x, T y, RangeCheckId* validity) { | |
177 *validity = (y == 0 || x <= numeric_limits<T>::max() / y) ? | |
178 TYPE_VALID : TYPE_OVERFLOW; | |
179 return x * y; | |
180 } | |
181 | |
182 // Division just requires a check for an invalid negation on signed min/-1. | |
183 template <typename T> | |
184 T CheckedDiv(T x, T y, RangeCheckId* validity, | |
185 typename enable_if<numeric_limits<T>::is_integer, int>::type = 0) { | |
186 if (numeric_limits<T>::is_signed && x == numeric_limits<T>::min() && | |
187 y == static_cast<T>(-1)) { | |
188 *validity = TYPE_OVERFLOW; | |
189 return numeric_limits<T>::min(); | |
190 } | |
191 | |
192 *validity = TYPE_VALID; | |
193 return x / y; | |
194 } | |
195 | |
196 template <typename T> | |
197 typename enable_if<numeric_limits<T>::is_integer && | |
198 numeric_limits<T>::is_signed, T>::type | |
199 CheckedMod(T x, T y, RangeCheckId* validity) { | |
200 *validity = y > 0 ? TYPE_VALID : TYPE_INVALID; | |
201 return x % y; | |
202 } | |
203 | |
204 template <typename T> | |
205 typename enable_if<numeric_limits<T>::is_integer && | |
206 !numeric_limits<T>::is_signed, T>::type | |
207 CheckedMod(T x, T y, RangeCheckId* validity) { | |
208 *validity = TYPE_VALID; | |
209 return x % y; | |
210 } | |
211 | |
212 template <typename T> | |
213 typename enable_if<numeric_limits<T>::is_integer && | |
214 numeric_limits<T>::is_signed, T>::type | |
215 CheckedNeg(T value, RangeCheckId* validity) { | |
216 *validity = value != numeric_limits<T>::min() ? TYPE_VALID : TYPE_OVERFLOW; | |
217 // The negation of signed min is min, so catch that one. | |
218 return -value; | |
219 } | |
220 | |
221 template <typename T> | |
222 typename enable_if<numeric_limits<T>::is_integer && | |
223 !numeric_limits<T>::is_signed, T>::type | |
224 CheckedNeg(T value, RangeCheckId* validity) { | |
225 // The only legal unsigned negation is zero. | |
226 *validity = value ? TYPE_UNDERFLOW : TYPE_VALID; | |
227 return static_cast<T>( | |
228 -static_cast<typename SignedIntegerForSize<T>::type>(value)); | |
229 } | |
230 | |
231 template <typename T> | |
232 typename enable_if<numeric_limits<T>::is_integer && | |
233 numeric_limits<T>::is_signed, T>::type | |
234 CheckedAbs(T value, RangeCheckId* validity) { | |
235 *validity = value != numeric_limits<T>::min() ? TYPE_VALID : TYPE_OVERFLOW; | |
236 return std::abs(value); | |
237 } | |
238 | |
239 template <typename T> | |
240 typename enable_if<numeric_limits<T>::is_integer && | |
241 !numeric_limits<T>::is_signed, T>::type | |
242 CheckedAbs(T value, RangeCheckId* validity) { | |
243 // Absolute value of a positive is just its identiy. | |
244 *validity = TYPE_VALID; | |
245 return value; | |
246 } | |
247 | |
248 // These are the floating point stubs that the compiler needs to see. Only the | |
249 // negation operation is ever called. | |
250 #define BASE_FLOAT_ARITHMETIC_STUBS(NAME) \ | |
251 template <typename T> \ | |
252 typename enable_if<numeric_limits<T>::is_iec559, T>::type \ | |
253 Checked##NAME(T, T, RangeCheckId*) { \ | |
254 NOTREACHED(); \ | |
255 return 0; \ | |
256 } | |
257 | |
258 BASE_FLOAT_ARITHMETIC_STUBS(Add) | |
259 BASE_FLOAT_ARITHMETIC_STUBS(Sub) | |
260 BASE_FLOAT_ARITHMETIC_STUBS(Mul) | |
261 BASE_FLOAT_ARITHMETIC_STUBS(Div) | |
262 BASE_FLOAT_ARITHMETIC_STUBS(Mod) | |
263 | |
264 #undef BASE_FLOAT_ARITHMETIC_STUBS | |
265 | |
266 template <typename T> | |
267 typename enable_if<numeric_limits<T>::is_iec559, T>::type | |
268 CheckedNeg(T value, RangeCheckId*) { | |
269 return -value; | |
270 } | |
271 | |
272 template <typename T> | |
273 typename enable_if<numeric_limits<T>::is_iec559, T>::type | |
274 CheckedAbs(T value, RangeCheckId*) { | |
275 return std::abs(value); | |
276 } | |
277 | |
278 | |
279 | |
280 // Floats carry around their validity state with them, but integers do not. So, | |
281 // we wrap the underlying value in a specialization in order to hide that detail | |
282 // and expose an interface via accessors. | |
283 enum NumericTypeId { | |
284 NUMERIC_INTEGER, | |
285 NUMERIC_FLOATING, | |
286 NUMERIC_UNKNOWN | |
287 }; | |
288 | |
289 template <typename NumericType> | |
290 struct GetNumericTypeId { | |
291 static const NumericTypeId value = numeric_limits<NumericType>::is_integer ? | |
292 NUMERIC_INTEGER : (numeric_limits<NumericType>::is_iec559 ? | |
293 NUMERIC_FLOATING : NUMERIC_UNKNOWN); | |
294 }; | |
295 | |
296 template <typename T, NumericTypeId type = GetNumericTypeId<T>::value> | |
297 class CheckedNumericState {}; | |
298 | |
299 // Integrals require quite a bit of additional housekeeping to manage state. | |
300 template <typename T> | |
301 class CheckedNumericState<T, NUMERIC_INTEGER> { | |
302 private: | |
303 T value_; | |
304 RangeCheckId validity_; | |
305 | |
306 public: | |
307 template <typename Src, NumericTypeId type> | |
308 friend class CheckedNumericState; | |
309 | |
310 CheckedNumericState() : value_(0), validity_(TYPE_VALID) {} | |
311 | |
312 template <typename Src> | |
313 CheckedNumericState(Src value, RangeCheckId validity) : | |
314 value_(value), validity_(static_cast<RangeCheckId>( | |
315 validity | RangeCheck<T>(value))) { | |
316 COMPILE_ASSERT(numeric_limits<Src>::is_specialized, | |
317 argument_must_be_numeric); | |
318 } | |
319 | |
320 // Copy constructor. | |
321 template <typename Src> | |
322 CheckedNumericState(const CheckedNumericState<Src>& rhs) : | |
323 value_(static_cast<T>(rhs.value())), validity_( | |
324 static_cast<RangeCheckId>(rhs.validity() | | |
325 RangeCheck<T>(rhs.value()))) {} | |
326 | |
327 template <typename Src> | |
328 explicit CheckedNumericState(Src value, | |
329 typename enable_if<numeric_limits<Src>::is_specialized, | |
330 int>::type = 0) : | |
331 value_(static_cast<T>(value)), validity_(RangeCheck<T>(value)) {} | |
332 | |
333 RangeCheckId validity() const { return validity_; } | |
334 T value() const { return value_; } | |
335 }; | |
336 | |
337 // Floating points maintain their own validity, but need translation wrappers. | |
338 template <typename T> | |
339 class CheckedNumericState<T, NUMERIC_FLOATING> { | |
340 private: | |
341 T value_; | |
342 | |
343 public: | |
344 template <typename Src, NumericTypeId type> | |
345 friend class CheckedNumericState; | |
346 | |
347 CheckedNumericState() : value_(0.0) {} | |
348 | |
349 template <typename Src> | |
350 CheckedNumericState(Src value, RangeCheckId validity, | |
351 typename enable_if<numeric_limits<Src>::is_integer, | |
352 int>::type = 0) { | |
353 switch (RangeCheck<T>(value)) { | |
354 case TYPE_VALID: | |
355 value_ = static_cast<T>(value); | |
356 break; | |
357 | |
358 case TYPE_UNDERFLOW: | |
359 value_ = -numeric_limits<T>::infinity(); | |
360 break; | |
361 | |
362 case TYPE_OVERFLOW: | |
363 value_ = numeric_limits<T>::infinity(); | |
364 break; | |
365 | |
366 case TYPE_INVALID: | |
367 value_ = numeric_limits<T>::quiet_NaN(); | |
368 break; | |
369 | |
370 default: | |
371 NOTREACHED(); | |
372 } | |
373 } | |
374 | |
375 template <typename Src> | |
376 explicit CheckedNumericState(Src value, | |
377 typename enable_if<numeric_limits<Src>::is_specialized, | |
378 int>::type = 0) : value_(static_cast<T>(value)) {} | |
379 | |
380 // Copy constructor. | |
381 template <typename Src> | |
382 CheckedNumericState(const CheckedNumericState<Src>& rhs) : | |
383 value_(static_cast<T>(rhs.value())) {} | |
384 | |
385 RangeCheckId validity() const { | |
386 return BASE_NUMERIC_RANGE_CHECK_RESULT( | |
387 value_ <= numeric_limits<T>::max(), | |
388 value_ >= -numeric_limits<T>::max()); | |
389 } | |
390 T value() const { return value_; } | |
391 }; | |
392 | |
393 // For integers less than 128-bit and floats 32-bit or larger, we can distil | |
394 // C/C++ arithmetic promotions down to two simple rules: | |
395 // 1. The type with the larger maximum exponent always takes precedence. | |
396 // 2. The resulting type must be promoted to at least an int. | |
397 // The following template specializations implement that promotion logic. | |
398 enum ArithmeticPromotionId { | |
399 LEFT_PROMOTION, | |
400 RIGHT_PROMOTION, | |
401 DEFAULT_PROMOTION | |
402 }; | |
403 | |
404 template <typename Lhs, typename Rhs = Lhs, | |
405 ArithmeticPromotionId Promotion = | |
406 (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value) ? | |
407 (MaxExponent<Lhs>::value > MaxExponent<int>::value ? | |
408 LEFT_PROMOTION : DEFAULT_PROMOTION) : | |
409 (MaxExponent<Rhs>::value > MaxExponent<int>::value ? | |
410 RIGHT_PROMOTION : DEFAULT_PROMOTION)> | |
411 struct ArithmeticPromotion {}; | |
412 | |
413 template <typename Lhs, typename Rhs> | |
414 struct ArithmeticPromotion<Lhs, Rhs, LEFT_PROMOTION> { | |
415 typedef Lhs type; | |
416 }; | |
417 | |
418 template <typename Lhs, typename Rhs> | |
419 struct ArithmeticPromotion<Lhs, Rhs, RIGHT_PROMOTION> { | |
420 typedef Rhs type; | |
421 }; | |
422 | |
423 template <typename Lhs, typename Rhs> | |
424 struct ArithmeticPromotion<Lhs, Rhs, DEFAULT_PROMOTION> { | |
425 typedef int type; | |
426 }; | |
427 | |
428 // We can statically check if operations on the provided types can wrap, so we | |
429 // can skip the checked operations if they're not needed. So, for an integer we | |
430 // care if the destination type preserves the sign and is twice the width of | |
431 // the source. | |
432 template <typename T, typename Lhs, typename Rhs> | |
433 struct IsIntegerArithmeticSafe { | |
434 static const bool value = !numeric_limits<T>::is_iec559 && | |
435 StaticRangeCheck<T, Lhs>::value == CONTAINS_RANGE && | |
436 sizeof(T) >= (2 * sizeof(Lhs)) && | |
437 StaticRangeCheck<T, Rhs>::value != CONTAINS_RANGE && | |
438 sizeof(T) >= (2 * sizeof(Rhs)); | |
439 }; | |
440 | |
441 } // namespace internal | |
442 } // namespace base | |
443 | |
444 #endif // SAFE_MATH_IMPL_H_ | |
445 | |
OLD | NEW |