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