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

Side by Side Diff: third_party/base/numerics/safe_conversions_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_conversions.h ('k') | third_party/base/numerics/safe_math.h » ('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_SAFE_CONVERSIONS_IMPL_H_ 5 #ifndef PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_
6 #define PDFIUM_THIRD_PARTY_BASE_SAFE_CONVERSIONS_IMPL_H_ 6 #define PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_
7 7
8 #include <assert.h> 8 #include <stdint.h>
9
9 #include <limits> 10 #include <limits>
10 11 #include <type_traits>
11 #include "third_party/base/macros.h"
12 12
13 namespace pdfium { 13 namespace pdfium {
14 namespace base { 14 namespace base {
15 namespace internal { 15 namespace internal {
16 16
17 // The std library doesn't provide a binary max_exponent for integers, however 17 // The std library doesn't provide a binary max_exponent for integers, however
18 // we can compute one by adding one to the number of non-sign bits. This allows 18 // we can compute an analog using std::numeric_limits<>::digits.
19 // for accurate range comparisons between floating point and integer types.
20 template <typename NumericType> 19 template <typename NumericType>
21 struct MaxExponent { 20 struct MaxExponent {
22 static const int value = std::numeric_limits<NumericType>::is_iec559 21 static const int value = std::is_floating_point<NumericType>::value
23 ? std::numeric_limits<NumericType>::max_exponent 22 ? std::numeric_limits<NumericType>::max_exponent
24 : (sizeof(NumericType) * 8 + 1 - 23 : std::numeric_limits<NumericType>::digits + 1;
25 std::numeric_limits<NumericType>::is_signed);
26 }; 24 };
27 25
26 // The number of bits (including the sign) in an integer. Eliminates sizeof
27 // hacks.
28 template <typename NumericType>
29 struct IntegerBitsPlusSign {
30 static const int value = std::numeric_limits<NumericType>::digits +
31 std::is_signed<NumericType>::value;
32 };
33
34 // Helper templates for integer manipulations.
35
36 template <typename Integer>
37 struct PositionOfSignBit {
38 static const size_t value = IntegerBitsPlusSign<Integer>::value - 1;
39 };
40
41 // Determines if a numeric value is negative without throwing compiler
42 // warnings on: unsigned(value) < 0.
43 template <typename T,
44 typename std::enable_if<std::is_signed<T>::value>::type* = nullptr>
45 constexpr bool IsValueNegative(T value) {
46 static_assert(std::is_arithmetic<T>::value, "Argument must be numeric.");
47 return value < 0;
48 }
49
50 template <typename T,
51 typename std::enable_if<!std::is_signed<T>::value>::type* = nullptr>
52 constexpr bool IsValueNegative(T) {
53 static_assert(std::is_arithmetic<T>::value, "Argument must be numeric.");
54 return false;
55 }
56
57 // This performs a fast negation, returning a signed value. It works on unsigned
58 // arguments, but probably doesn't do what you want for any unsigned value
59 // larger than max / 2 + 1 (i.e. signed min cast to unsigned).
60 template <typename T>
61 constexpr typename std::make_signed<T>::type ConditionalNegate(
62 T x,
63 bool is_negative) {
64 static_assert(std::is_integral<T>::value, "Type must be integral");
65 using SignedT = typename std::make_signed<T>::type;
66 using UnsignedT = typename std::make_unsigned<T>::type;
67 return static_cast<SignedT>(
68 (static_cast<UnsignedT>(x) ^ -SignedT(is_negative)) + is_negative);
69 }
70
71 // This performs a safe, absolute value via unsigned overflow.
72 template <typename T>
73 constexpr typename std::make_unsigned<T>::type SafeUnsignedAbs(T value) {
74 static_assert(std::is_integral<T>::value, "Type must be integral");
75 using UnsignedT = typename std::make_unsigned<T>::type;
76 return IsValueNegative(value) ? 0 - static_cast<UnsignedT>(value)
77 : static_cast<UnsignedT>(value);
78 }
79
28 enum IntegerRepresentation { 80 enum IntegerRepresentation {
29 INTEGER_REPRESENTATION_UNSIGNED, 81 INTEGER_REPRESENTATION_UNSIGNED,
30 INTEGER_REPRESENTATION_SIGNED 82 INTEGER_REPRESENTATION_SIGNED
31 }; 83 };
32 84
33 // A range for a given nunmeric Src type is contained for a given numeric Dst 85 // A range for a given nunmeric Src type is contained for a given numeric Dst
34 // type if both numeric_limits<Src>::max() <= numeric_limits<Dst>::max() and 86 // type if both numeric_limits<Src>::max() <= numeric_limits<Dst>::max() and
35 // numeric_limits<Src>::min() >= numeric_limits<Dst>::min() are true. 87 // numeric_limits<Src>::lowest() >= numeric_limits<Dst>::lowest() are true.
36 // We implement this as template specializations rather than simple static 88 // We implement this as template specializations rather than simple static
37 // comparisons to ensure type correctness in our comparisons. 89 // comparisons to ensure type correctness in our comparisons.
38 enum NumericRangeRepresentation { 90 enum NumericRangeRepresentation {
39 NUMERIC_RANGE_NOT_CONTAINED, 91 NUMERIC_RANGE_NOT_CONTAINED,
40 NUMERIC_RANGE_CONTAINED 92 NUMERIC_RANGE_CONTAINED
41 }; 93 };
42 94
43 // Helper templates to statically determine if our destination type can contain 95 // Helper templates to statically determine if our destination type can contain
44 // maximum and minimum values represented by the source type. 96 // maximum and minimum values represented by the source type.
45 97
46 template < 98 template <typename Dst,
47 typename Dst, 99 typename Src,
48 typename Src, 100 IntegerRepresentation DstSign = std::is_signed<Dst>::value
49 IntegerRepresentation DstSign = std::numeric_limits<Dst>::is_signed 101 ? INTEGER_REPRESENTATION_SIGNED
50 ? INTEGER_REPRESENTATION_SIGNED 102 : INTEGER_REPRESENTATION_UNSIGNED,
51 : INTEGER_REPRESENTATION_UNSIGNED, 103 IntegerRepresentation SrcSign = std::is_signed<Src>::value
52 IntegerRepresentation SrcSign = 104 ? INTEGER_REPRESENTATION_SIGNED
53 std::numeric_limits<Src>::is_signed 105 : INTEGER_REPRESENTATION_UNSIGNED>
54 ? INTEGER_REPRESENTATION_SIGNED
55 : INTEGER_REPRESENTATION_UNSIGNED >
56 struct StaticDstRangeRelationToSrcRange; 106 struct StaticDstRangeRelationToSrcRange;
57 107
58 // Same sign: Dst is guaranteed to contain Src only if its range is equal or 108 // Same sign: Dst is guaranteed to contain Src only if its range is equal or
59 // larger. 109 // larger.
60 template <typename Dst, typename Src, IntegerRepresentation Sign> 110 template <typename Dst, typename Src, IntegerRepresentation Sign>
61 struct StaticDstRangeRelationToSrcRange<Dst, Src, Sign, Sign> { 111 struct StaticDstRangeRelationToSrcRange<Dst, Src, Sign, Sign> {
62 static const NumericRangeRepresentation value = 112 static const NumericRangeRepresentation value =
63 MaxExponent<Dst>::value >= MaxExponent<Src>::value 113 MaxExponent<Dst>::value >= MaxExponent<Src>::value
64 ? NUMERIC_RANGE_CONTAINED 114 ? NUMERIC_RANGE_CONTAINED
65 : NUMERIC_RANGE_NOT_CONTAINED; 115 : NUMERIC_RANGE_NOT_CONTAINED;
(...skipping 14 matching lines...) Expand all
80 130
81 // Signed to unsigned: Dst cannot be statically determined to contain Src. 131 // Signed to unsigned: Dst cannot be statically determined to contain Src.
82 template <typename Dst, typename Src> 132 template <typename Dst, typename Src>
83 struct StaticDstRangeRelationToSrcRange<Dst, 133 struct StaticDstRangeRelationToSrcRange<Dst,
84 Src, 134 Src,
85 INTEGER_REPRESENTATION_UNSIGNED, 135 INTEGER_REPRESENTATION_UNSIGNED,
86 INTEGER_REPRESENTATION_SIGNED> { 136 INTEGER_REPRESENTATION_SIGNED> {
87 static const NumericRangeRepresentation value = NUMERIC_RANGE_NOT_CONTAINED; 137 static const NumericRangeRepresentation value = NUMERIC_RANGE_NOT_CONTAINED;
88 }; 138 };
89 139
90 enum RangeConstraint { 140 // This class wraps the range constraints as separate booleans so the compiler
91 RANGE_VALID = 0x0, // Value can be represented by the destination type. 141 // can identify constants and eliminate unused code paths.
92 RANGE_UNDERFLOW = 0x1, // Value would overflow. 142 class RangeCheck {
93 RANGE_OVERFLOW = 0x2, // Value would underflow. 143 public:
94 RANGE_INVALID = RANGE_UNDERFLOW | RANGE_OVERFLOW // Invalid (i.e. NaN). 144 constexpr RangeCheck(bool is_in_lower_bound, bool is_in_upper_bound)
95 }; 145 : is_underflow_(!is_in_lower_bound), is_overflow_(!is_in_upper_bound) {}
96 146 constexpr RangeCheck() : is_underflow_(0), is_overflow_(0) {}
97 // Helper function for coercing an int back to a RangeContraint. 147 constexpr bool IsValid() const { return !is_overflow_ && !is_underflow_; }
98 inline RangeConstraint GetRangeConstraint(int integer_range_constraint) { 148 constexpr bool IsInvalid() const { return is_overflow_ && is_underflow_; }
99 assert(integer_range_constraint >= RANGE_VALID && 149 constexpr bool IsOverflow() const { return is_overflow_ && !is_underflow_; }
100 integer_range_constraint <= RANGE_INVALID); 150 constexpr bool IsUnderflow() const { return !is_overflow_ && is_underflow_; }
101 return static_cast<RangeConstraint>(integer_range_constraint); 151 constexpr bool IsOverflowFlagSet() const { return is_overflow_; }
102 } 152 constexpr bool IsUnderflowFlagSet() const { return is_underflow_; }
103 153 constexpr bool operator==(const RangeCheck rhs) const {
104 // This function creates a RangeConstraint from an upper and lower bound 154 return is_underflow_ == rhs.is_underflow_ &&
105 // check by taking advantage of the fact that only NaN can be out of range in 155 is_overflow_ == rhs.is_overflow_;
106 // both directions at once. 156 }
107 inline RangeConstraint GetRangeConstraint(bool is_in_upper_bound, 157 constexpr bool operator!=(const RangeCheck rhs) const {
108 bool is_in_lower_bound) { 158 return !(*this == rhs);
109 return GetRangeConstraint((is_in_upper_bound ? 0 : RANGE_OVERFLOW) | 159 }
110 (is_in_lower_bound ? 0 : RANGE_UNDERFLOW)); 160
111 } 161 private:
112 162 // Do not change the order of these member variables. The integral conversion
113 template < 163 // optimization depends on this exact order.
114 typename Dst, 164 const bool is_underflow_;
115 typename Src, 165 const bool is_overflow_;
116 IntegerRepresentation DstSign = std::numeric_limits<Dst>::is_signed 166 };
117 ? INTEGER_REPRESENTATION_SIGNED 167
118 : INTEGER_REPRESENTATION_UNSIGNED, 168 // The following helper template addresses a corner case in range checks for
119 IntegerRepresentation SrcSign = std::numeric_limits<Src>::is_signed 169 // conversion from a floating-point type to an integral type of smaller range
120 ? INTEGER_REPRESENTATION_SIGNED 170 // but larger precision (e.g. float -> unsigned). The problem is as follows:
121 : INTEGER_REPRESENTATION_UNSIGNED, 171 // 1. Integral maximum is always one less than a power of two, so it must be
122 NumericRangeRepresentation DstRange = 172 // truncated to fit the mantissa of the floating point. The direction of
123 StaticDstRangeRelationToSrcRange<Dst, Src>::value > 173 // rounding is implementation defined, but by default it's always IEEE
174 // floats, which round to nearest and thus result in a value of larger
175 // magnitude than the integral value.
176 // Example: float f = UINT_MAX; // f is 4294967296f but UINT_MAX
177 // // is 4294967295u.
178 // 2. If the floating point value is equal to the promoted integral maximum
179 // value, a range check will erroneously pass.
180 // Example: (4294967296f <= 4294967295u) // This is true due to a precision
181 // // loss in rounding up to float.
182 // 3. When the floating point value is then converted to an integral, the
183 // resulting value is out of range for the target integral type and
184 // thus is implementation defined.
185 // Example: unsigned u = (float)INT_MAX; // u will typically overflow to 0.
186 // To fix this bug we manually truncate the maximum value when the destination
187 // type is an integral of larger precision than the source floating-point type,
188 // such that the resulting maximum is represented exactly as a floating point.
189 template <typename Dst, typename Src, template <typename> class Bounds>
190 struct NarrowingRange {
191 using SrcLimits = std::numeric_limits<Src>;
192 using DstLimits = typename std::numeric_limits<Dst>;
193
194 // Computes the mask required to make an accurate comparison between types.
195 static const int kShift =
196 (MaxExponent<Src>::value > MaxExponent<Dst>::value &&
197 SrcLimits::digits < DstLimits::digits)
198 ? (DstLimits::digits - SrcLimits::digits)
199 : 0;
200 template <
201 typename T,
202 typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
203
204 // Masks out the integer bits that are beyond the precision of the
205 // intermediate type used for comparison.
206 static constexpr T Adjust(T value) {
207 static_assert(std::is_same<T, Dst>::value, "");
208 static_assert(kShift < DstLimits::digits, "");
209 return static_cast<T>(
210 ConditionalNegate(SafeUnsignedAbs(value) & ~((T(1) << kShift) - T(1)),
211 IsValueNegative(value)));
212 }
213
214 template <typename T,
215 typename std::enable_if<std::is_floating_point<T>::value>::type* =
216 nullptr>
217 static constexpr T Adjust(T value) {
218 static_assert(std::is_same<T, Dst>::value, "");
219 static_assert(kShift == 0, "");
220 return value;
221 }
222
223 static constexpr Dst max() { return Adjust(Bounds<Dst>::max()); }
224 static constexpr Dst lowest() { return Adjust(Bounds<Dst>::lowest()); }
225 };
226
227 template <typename Dst,
228 typename Src,
229 template <typename> class Bounds,
230 IntegerRepresentation DstSign = std::is_signed<Dst>::value
231 ? INTEGER_REPRESENTATION_SIGNED
232 : INTEGER_REPRESENTATION_UNSIGNED,
233 IntegerRepresentation SrcSign = std::is_signed<Src>::value
234 ? INTEGER_REPRESENTATION_SIGNED
235 : INTEGER_REPRESENTATION_UNSIGNED,
236 NumericRangeRepresentation DstRange =
237 StaticDstRangeRelationToSrcRange<Dst, Src>::value>
124 struct DstRangeRelationToSrcRangeImpl; 238 struct DstRangeRelationToSrcRangeImpl;
125 239
126 // The following templates are for ranges that must be verified at runtime. We 240 // The following templates are for ranges that must be verified at runtime. We
127 // split it into checks based on signedness to avoid confusing casts and 241 // split it into checks based on signedness to avoid confusing casts and
128 // compiler warnings on signed an unsigned comparisons. 242 // compiler warnings on signed an unsigned comparisons.
129 243
130 // Dst range is statically determined to contain Src: Nothing to check. 244 // Same sign narrowing: The range is contained for normal limits.
131 template <typename Dst, 245 template <typename Dst,
132 typename Src, 246 typename Src,
247 template <typename> class Bounds,
133 IntegerRepresentation DstSign, 248 IntegerRepresentation DstSign,
134 IntegerRepresentation SrcSign> 249 IntegerRepresentation SrcSign>
135 struct DstRangeRelationToSrcRangeImpl<Dst, 250 struct DstRangeRelationToSrcRangeImpl<Dst,
136 Src, 251 Src,
252 Bounds,
137 DstSign, 253 DstSign,
138 SrcSign, 254 SrcSign,
139 NUMERIC_RANGE_CONTAINED> { 255 NUMERIC_RANGE_CONTAINED> {
140 static RangeConstraint Check(Src value) { return RANGE_VALID; } 256 static constexpr RangeCheck Check(Src value) {
257 using SrcLimits = std::numeric_limits<Src>;
258 using DstLimits = NarrowingRange<Dst, Src, Bounds>;
259 return RangeCheck(
260 static_cast<Dst>(SrcLimits::lowest()) >= DstLimits::lowest() ||
261 static_cast<Dst>(value) >= DstLimits::lowest(),
262 static_cast<Dst>(SrcLimits::max()) <= DstLimits::max() ||
263 static_cast<Dst>(value) <= DstLimits::max());
264 }
141 }; 265 };
142 266
143 // Signed to signed narrowing: Both the upper and lower boundaries may be 267 // Signed to signed narrowing: Both the upper and lower boundaries may be
144 // exceeded. 268 // exceeded for standard limits.
145 template <typename Dst, typename Src> 269 template <typename Dst, typename Src, template <typename> class Bounds>
146 struct DstRangeRelationToSrcRangeImpl<Dst, 270 struct DstRangeRelationToSrcRangeImpl<Dst,
147 Src, 271 Src,
272 Bounds,
148 INTEGER_REPRESENTATION_SIGNED, 273 INTEGER_REPRESENTATION_SIGNED,
149 INTEGER_REPRESENTATION_SIGNED, 274 INTEGER_REPRESENTATION_SIGNED,
150 NUMERIC_RANGE_NOT_CONTAINED> { 275 NUMERIC_RANGE_NOT_CONTAINED> {
151 static RangeConstraint Check(Src value) { 276 static constexpr RangeCheck Check(Src value) {
152 return std::numeric_limits<Dst>::is_iec559 277 using DstLimits = NarrowingRange<Dst, Src, Bounds>;
153 ? GetRangeConstraint(value <= std::numeric_limits<Dst>::max(), 278 return RangeCheck(value >= DstLimits::lowest(), value <= DstLimits::max());
154 value >= -std::numeric_limits<Dst>::max()) 279 }
155 : GetRangeConstraint(value <= std::numeric_limits<Dst>::max(), 280 };
156 value >= std::numeric_limits<Dst>::min()); 281
157 } 282 // Unsigned to unsigned narrowing: Only the upper bound can be exceeded for
158 }; 283 // standard limits.
159 284 template <typename Dst, typename Src, template <typename> class Bounds>
160 // Unsigned to unsigned narrowing: Only the upper boundary can be exceeded.
161 template <typename Dst, typename Src>
162 struct DstRangeRelationToSrcRangeImpl<Dst, 285 struct DstRangeRelationToSrcRangeImpl<Dst,
163 Src, 286 Src,
287 Bounds,
164 INTEGER_REPRESENTATION_UNSIGNED, 288 INTEGER_REPRESENTATION_UNSIGNED,
165 INTEGER_REPRESENTATION_UNSIGNED, 289 INTEGER_REPRESENTATION_UNSIGNED,
166 NUMERIC_RANGE_NOT_CONTAINED> { 290 NUMERIC_RANGE_NOT_CONTAINED> {
167 static RangeConstraint Check(Src value) { 291 static constexpr RangeCheck Check(Src value) {
168 return GetRangeConstraint(value <= std::numeric_limits<Dst>::max(), true); 292 using DstLimits = NarrowingRange<Dst, Src, Bounds>;
169 } 293 return RangeCheck(
170 }; 294 DstLimits::lowest() == Dst(0) || value >= DstLimits::lowest(),
171 295 value <= DstLimits::max());
172 // Unsigned to signed: The upper boundary may be exceeded. 296 }
173 template <typename Dst, typename Src> 297 };
298
299 // Unsigned to signed: Only the upper bound can be exceeded for standard limits.
300 template <typename Dst, typename Src, template <typename> class Bounds>
174 struct DstRangeRelationToSrcRangeImpl<Dst, 301 struct DstRangeRelationToSrcRangeImpl<Dst,
175 Src, 302 Src,
303 Bounds,
176 INTEGER_REPRESENTATION_SIGNED, 304 INTEGER_REPRESENTATION_SIGNED,
177 INTEGER_REPRESENTATION_UNSIGNED, 305 INTEGER_REPRESENTATION_UNSIGNED,
178 NUMERIC_RANGE_NOT_CONTAINED> { 306 NUMERIC_RANGE_NOT_CONTAINED> {
179 static RangeConstraint Check(Src value) { 307 static constexpr RangeCheck Check(Src value) {
180 return sizeof(Dst) > sizeof(Src) 308 using DstLimits = NarrowingRange<Dst, Src, Bounds>;
181 ? RANGE_VALID 309 using Promotion = decltype(Src() + Dst());
182 : GetRangeConstraint( 310 return RangeCheck(DstLimits::lowest() <= Dst(0) ||
183 value <= static_cast<Src>(std::numeric_limits<Dst>::max()), 311 static_cast<Promotion>(value) >=
184 true); 312 static_cast<Promotion>(DstLimits::lowest()),
313 static_cast<Promotion>(value) <=
314 static_cast<Promotion>(DstLimits::max()));
185 } 315 }
186 }; 316 };
187 317
188 // Signed to unsigned: The upper boundary may be exceeded for a narrower Dst, 318 // Signed to unsigned: The upper boundary may be exceeded for a narrower Dst,
189 // and any negative value exceeds the lower boundary. 319 // and any negative value exceeds the lower boundary for standard limits.
190 template <typename Dst, typename Src> 320 template <typename Dst, typename Src, template <typename> class Bounds>
191 struct DstRangeRelationToSrcRangeImpl<Dst, 321 struct DstRangeRelationToSrcRangeImpl<Dst,
192 Src, 322 Src,
323 Bounds,
193 INTEGER_REPRESENTATION_UNSIGNED, 324 INTEGER_REPRESENTATION_UNSIGNED,
194 INTEGER_REPRESENTATION_SIGNED, 325 INTEGER_REPRESENTATION_SIGNED,
195 NUMERIC_RANGE_NOT_CONTAINED> { 326 NUMERIC_RANGE_NOT_CONTAINED> {
196 static RangeConstraint Check(Src value) { 327 static constexpr RangeCheck Check(Src value) {
197 return (MaxExponent<Dst>::value >= MaxExponent<Src>::value) 328 using SrcLimits = std::numeric_limits<Src>;
198 ? GetRangeConstraint(true, value >= static_cast<Src>(0)) 329 using DstLimits = NarrowingRange<Dst, Src, Bounds>;
199 : GetRangeConstraint( 330 using Promotion = decltype(Src() + Dst());
200 value <= static_cast<Src>(std::numeric_limits<Dst>::max()), 331 return RangeCheck(
201 value >= static_cast<Src>(0)); 332 value >= Src(0) && (DstLimits::lowest() == 0 ||
202 } 333 static_cast<Dst>(value) >= DstLimits::lowest()),
203 }; 334 static_cast<Promotion>(SrcLimits::max()) <=
204 335 static_cast<Promotion>(DstLimits::max()) ||
205 template <typename Dst, typename Src> 336 static_cast<Promotion>(value) <=
206 inline RangeConstraint DstRangeRelationToSrcRange(Src value) { 337 static_cast<Promotion>(DstLimits::max()));
207 COMPILE_ASSERT(std::numeric_limits<Src>::is_specialized, 338 }
208 argument_must_be_numeric); 339 };
209 COMPILE_ASSERT(std::numeric_limits<Dst>::is_specialized, 340
210 result_must_be_numeric); 341 template <typename Dst,
211 return DstRangeRelationToSrcRangeImpl<Dst, Src>::Check(value); 342 template <typename> class Bounds = std::numeric_limits,
343 typename Src>
344 constexpr RangeCheck DstRangeRelationToSrcRange(Src value) {
345 static_assert(std::is_arithmetic<Src>::value, "Argument must be numeric.");
346 static_assert(std::is_arithmetic<Dst>::value, "Result must be numeric.");
347 static_assert(Bounds<Dst>::lowest() < Bounds<Dst>::max(), "");
348 return DstRangeRelationToSrcRangeImpl<Dst, Src, Bounds>::Check(value);
212 } 349 }
213 350
351 // Integer promotion templates used by the portable checked integer arithmetic.
352 template <size_t Size, bool IsSigned>
353 struct IntegerForDigitsAndSign;
354
355 #define INTEGER_FOR_DIGITS_AND_SIGN(I) \
356 template <> \
357 struct IntegerForDigitsAndSign<IntegerBitsPlusSign<I>::value, \
358 std::is_signed<I>::value> { \
359 using type = I; \
360 }
361
362 INTEGER_FOR_DIGITS_AND_SIGN(int8_t);
363 INTEGER_FOR_DIGITS_AND_SIGN(uint8_t);
364 INTEGER_FOR_DIGITS_AND_SIGN(int16_t);
365 INTEGER_FOR_DIGITS_AND_SIGN(uint16_t);
366 INTEGER_FOR_DIGITS_AND_SIGN(int32_t);
367 INTEGER_FOR_DIGITS_AND_SIGN(uint32_t);
368 INTEGER_FOR_DIGITS_AND_SIGN(int64_t);
369 INTEGER_FOR_DIGITS_AND_SIGN(uint64_t);
370 #undef INTEGER_FOR_DIGITS_AND_SIGN
371
372 // WARNING: We have no IntegerForSizeAndSign<16, *>. If we ever add one to
373 // support 128-bit math, then the ArithmeticPromotion template below will need
374 // to be updated (or more likely replaced with a decltype expression).
375 static_assert(IntegerBitsPlusSign<intmax_t>::value == 64,
376 "Max integer size not supported for this toolchain.");
377
378 template <typename Integer, bool IsSigned = std::is_signed<Integer>::value>
379 struct TwiceWiderInteger {
380 using type =
381 typename IntegerForDigitsAndSign<IntegerBitsPlusSign<Integer>::value * 2,
382 IsSigned>::type;
383 };
384
385 enum ArithmeticPromotionCategory {
386 LEFT_PROMOTION, // Use the type of the left-hand argument.
387 RIGHT_PROMOTION // Use the type of the right-hand argument.
388 };
389
390 // Determines the type that can represent the largest positive value.
391 template <typename Lhs,
392 typename Rhs,
393 ArithmeticPromotionCategory Promotion =
394 (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value)
395 ? LEFT_PROMOTION
396 : RIGHT_PROMOTION>
397 struct MaxExponentPromotion;
398
399 template <typename Lhs, typename Rhs>
400 struct MaxExponentPromotion<Lhs, Rhs, LEFT_PROMOTION> {
401 using type = Lhs;
402 };
403
404 template <typename Lhs, typename Rhs>
405 struct MaxExponentPromotion<Lhs, Rhs, RIGHT_PROMOTION> {
406 using type = Rhs;
407 };
408
409 // Determines the type that can represent the lowest arithmetic value.
410 template <typename Lhs,
411 typename Rhs,
412 ArithmeticPromotionCategory Promotion =
413 std::is_signed<Lhs>::value
414 ? (std::is_signed<Rhs>::value
415 ? (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value
416 ? LEFT_PROMOTION
417 : RIGHT_PROMOTION)
418 : LEFT_PROMOTION)
419 : (std::is_signed<Rhs>::value
420 ? RIGHT_PROMOTION
421 : (MaxExponent<Lhs>::value < MaxExponent<Rhs>::value
422 ? LEFT_PROMOTION
423 : RIGHT_PROMOTION))>
424 struct LowestValuePromotion;
425
426 template <typename Lhs, typename Rhs>
427 struct LowestValuePromotion<Lhs, Rhs, LEFT_PROMOTION> {
428 using type = Lhs;
429 };
430
431 template <typename Lhs, typename Rhs>
432 struct LowestValuePromotion<Lhs, Rhs, RIGHT_PROMOTION> {
433 using type = Rhs;
434 };
435
436 // Determines the type that is best able to represent an arithmetic result.
437 template <
438 typename Lhs,
439 typename Rhs = Lhs,
440 bool is_intmax_type =
441 std::is_integral<typename MaxExponentPromotion<Lhs, Rhs>::type>::value&&
442 IntegerBitsPlusSign<typename MaxExponentPromotion<Lhs, Rhs>::type>::
443 value == IntegerBitsPlusSign<intmax_t>::value,
444 bool is_max_exponent =
445 StaticDstRangeRelationToSrcRange<
446 typename MaxExponentPromotion<Lhs, Rhs>::type,
447 Lhs>::value ==
448 NUMERIC_RANGE_CONTAINED&& StaticDstRangeRelationToSrcRange<
449 typename MaxExponentPromotion<Lhs, Rhs>::type,
450 Rhs>::value == NUMERIC_RANGE_CONTAINED>
451 struct BigEnoughPromotion;
452
453 // The side with the max exponent is big enough.
454 template <typename Lhs, typename Rhs, bool is_intmax_type>
455 struct BigEnoughPromotion<Lhs, Rhs, is_intmax_type, true> {
456 using type = typename MaxExponentPromotion<Lhs, Rhs>::type;
457 static const bool is_contained = true;
458 };
459
460 // We can use a twice wider type to fit.
461 template <typename Lhs, typename Rhs>
462 struct BigEnoughPromotion<Lhs, Rhs, false, false> {
463 using type =
464 typename TwiceWiderInteger<typename MaxExponentPromotion<Lhs, Rhs>::type,
465 std::is_signed<Lhs>::value ||
466 std::is_signed<Rhs>::value>::type;
467 static const bool is_contained = true;
468 };
469
470 // No type is large enough.
471 template <typename Lhs, typename Rhs>
472 struct BigEnoughPromotion<Lhs, Rhs, true, false> {
473 using type = typename MaxExponentPromotion<Lhs, Rhs>::type;
474 static const bool is_contained = false;
475 };
476
477 // We can statically check if operations on the provided types can wrap, so we
478 // can skip the checked operations if they're not needed. So, for an integer we
479 // care if the destination type preserves the sign and is twice the width of
480 // the source.
481 template <typename T, typename Lhs, typename Rhs = Lhs>
482 struct IsIntegerArithmeticSafe {
483 static const bool value =
484 !std::is_floating_point<T>::value &&
485 !std::is_floating_point<Lhs>::value &&
486 !std::is_floating_point<Rhs>::value &&
487 std::is_signed<T>::value >= std::is_signed<Lhs>::value &&
488 IntegerBitsPlusSign<T>::value >= (2 * IntegerBitsPlusSign<Lhs>::value) &&
489 std::is_signed<T>::value >= std::is_signed<Rhs>::value &&
490 IntegerBitsPlusSign<T>::value >= (2 * IntegerBitsPlusSign<Rhs>::value);
491 };
492
493 // Promotes to a type that can represent any possible result of a binary
494 // arithmetic operation with the source types.
495 template <typename Lhs,
496 typename Rhs,
497 bool is_promotion_possible = IsIntegerArithmeticSafe<
498 typename std::conditional<std::is_signed<Lhs>::value ||
499 std::is_signed<Rhs>::value,
500 intmax_t,
501 uintmax_t>::type,
502 typename MaxExponentPromotion<Lhs, Rhs>::type>::value>
503 struct FastIntegerArithmeticPromotion;
504
505 template <typename Lhs, typename Rhs>
506 struct FastIntegerArithmeticPromotion<Lhs, Rhs, true> {
507 using type =
508 typename TwiceWiderInteger<typename MaxExponentPromotion<Lhs, Rhs>::type,
509 std::is_signed<Lhs>::value ||
510 std::is_signed<Rhs>::value>::type;
511 static_assert(IsIntegerArithmeticSafe<type, Lhs, Rhs>::value, "");
512 static const bool is_contained = true;
513 };
514
515 template <typename Lhs, typename Rhs>
516 struct FastIntegerArithmeticPromotion<Lhs, Rhs, false> {
517 using type = typename BigEnoughPromotion<Lhs, Rhs>::type;
518 static const bool is_contained = false;
519 };
520
521 // This hacks around libstdc++ 4.6 missing stuff in type_traits.
522 #if defined(__GLIBCXX__)
523 #define PRIV_GLIBCXX_4_7_0 20120322
524 #define PRIV_GLIBCXX_4_5_4 20120702
525 #define PRIV_GLIBCXX_4_6_4 20121127
526 #if (__GLIBCXX__ < PRIV_GLIBCXX_4_7_0 || __GLIBCXX__ == PRIV_GLIBCXX_4_5_4 || \
527 __GLIBCXX__ == PRIV_GLIBCXX_4_6_4)
528 #define PRIV_USE_FALLBACKS_FOR_OLD_GLIBCXX
529 #undef PRIV_GLIBCXX_4_7_0
530 #undef PRIV_GLIBCXX_4_5_4
531 #undef PRIV_GLIBCXX_4_6_4
532 #endif
533 #endif
534
535 // Extracts the underlying type from an enum.
536 template <typename T, bool is_enum = std::is_enum<T>::value>
537 struct ArithmeticOrUnderlyingEnum;
538
539 template <typename T>
540 struct ArithmeticOrUnderlyingEnum<T, true> {
541 #if defined(PRIV_USE_FALLBACKS_FOR_OLD_GLIBCXX)
542 using type = __underlying_type(T);
543 #else
544 using type = typename std::underlying_type<T>::type;
545 #endif
546 static const bool value = std::is_arithmetic<type>::value;
547 };
548
549 #if defined(PRIV_USE_FALLBACKS_FOR_OLD_GLIBCXX)
550 #undef PRIV_USE_FALLBACKS_FOR_OLD_GLIBCXX
551 #endif
552
553 template <typename T>
554 struct ArithmeticOrUnderlyingEnum<T, false> {
555 using type = T;
556 static const bool value = std::is_arithmetic<type>::value;
557 };
558
559 // The following are helper templates used in the CheckedNumeric class.
560 template <typename T>
561 class CheckedNumeric;
562
563 template <typename T>
564 class StrictNumeric;
565
566 // Used to treat CheckedNumeric and arithmetic underlying types the same.
567 template <typename T>
568 struct UnderlyingType {
569 using type = typename ArithmeticOrUnderlyingEnum<T>::type;
570 static const bool is_numeric = std::is_arithmetic<type>::value;
571 static const bool is_checked = false;
572 static const bool is_strict = false;
573 };
574
575 template <typename T>
576 struct UnderlyingType<CheckedNumeric<T>> {
577 using type = T;
578 static const bool is_numeric = true;
579 static const bool is_checked = true;
580 static const bool is_strict = false;
581 };
582
583 template <typename T>
584 struct UnderlyingType<StrictNumeric<T>> {
585 using type = T;
586 static const bool is_numeric = true;
587 static const bool is_checked = false;
588 static const bool is_strict = true;
589 };
590
591 template <typename L, typename R>
592 struct IsCheckedOp {
593 static const bool value =
594 UnderlyingType<L>::is_numeric && UnderlyingType<R>::is_numeric &&
595 (UnderlyingType<L>::is_checked || UnderlyingType<R>::is_checked);
596 };
597
598 template <typename L, typename R>
599 struct IsStrictOp {
600 static const bool value =
601 UnderlyingType<L>::is_numeric && UnderlyingType<R>::is_numeric &&
602 (UnderlyingType<L>::is_strict || UnderlyingType<R>::is_strict);
603 };
604
605 template <typename L, typename R>
606 constexpr bool IsLessImpl(const L lhs,
607 const R rhs,
608 const RangeCheck l_range,
609 const RangeCheck r_range) {
610 return l_range.IsUnderflow() || r_range.IsOverflow() ||
611 (l_range == r_range &&
612 static_cast<decltype(lhs + rhs)>(lhs) <
613 static_cast<decltype(lhs + rhs)>(rhs));
614 }
615
616 template <typename L, typename R>
617 struct IsLess {
618 static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value,
619 "Types must be numeric.");
620 static constexpr bool Test(const L lhs, const R rhs) {
621 return IsLessImpl(lhs, rhs, DstRangeRelationToSrcRange<R>(lhs),
622 DstRangeRelationToSrcRange<L>(rhs));
623 }
624 };
625
626 template <typename L, typename R>
627 constexpr bool IsLessOrEqualImpl(const L lhs,
628 const R rhs,
629 const RangeCheck l_range,
630 const RangeCheck r_range) {
631 return l_range.IsUnderflow() || r_range.IsOverflow() ||
632 (l_range == r_range &&
633 static_cast<decltype(lhs + rhs)>(lhs) <=
634 static_cast<decltype(lhs + rhs)>(rhs));
635 }
636
637 template <typename L, typename R>
638 struct IsLessOrEqual {
639 static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value,
640 "Types must be numeric.");
641 static constexpr bool Test(const L lhs, const R rhs) {
642 return IsLessOrEqualImpl(lhs, rhs, DstRangeRelationToSrcRange<R>(lhs),
643 DstRangeRelationToSrcRange<L>(rhs));
644 }
645 };
646
647 template <typename L, typename R>
648 constexpr bool IsGreaterImpl(const L lhs,
649 const R rhs,
650 const RangeCheck l_range,
651 const RangeCheck r_range) {
652 return l_range.IsOverflow() || r_range.IsUnderflow() ||
653 (l_range == r_range &&
654 static_cast<decltype(lhs + rhs)>(lhs) >
655 static_cast<decltype(lhs + rhs)>(rhs));
656 }
657
658 template <typename L, typename R>
659 struct IsGreater {
660 static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value,
661 "Types must be numeric.");
662 static constexpr bool Test(const L lhs, const R rhs) {
663 return IsGreaterImpl(lhs, rhs, DstRangeRelationToSrcRange<R>(lhs),
664 DstRangeRelationToSrcRange<L>(rhs));
665 }
666 };
667
668 template <typename L, typename R>
669 constexpr bool IsGreaterOrEqualImpl(const L lhs,
670 const R rhs,
671 const RangeCheck l_range,
672 const RangeCheck r_range) {
673 return l_range.IsOverflow() || r_range.IsUnderflow() ||
674 (l_range == r_range &&
675 static_cast<decltype(lhs + rhs)>(lhs) >=
676 static_cast<decltype(lhs + rhs)>(rhs));
677 }
678
679 template <typename L, typename R>
680 struct IsGreaterOrEqual {
681 static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value,
682 "Types must be numeric.");
683 static constexpr bool Test(const L lhs, const R rhs) {
684 return IsGreaterOrEqualImpl(lhs, rhs, DstRangeRelationToSrcRange<R>(lhs),
685 DstRangeRelationToSrcRange<L>(rhs));
686 }
687 };
688
689 template <typename L, typename R>
690 struct IsEqual {
691 static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value,
692 "Types must be numeric.");
693 static constexpr bool Test(const L lhs, const R rhs) {
694 return DstRangeRelationToSrcRange<R>(lhs) ==
695 DstRangeRelationToSrcRange<L>(rhs) &&
696 static_cast<decltype(lhs + rhs)>(lhs) ==
697 static_cast<decltype(lhs + rhs)>(rhs);
698 }
699 };
700
701 template <typename L, typename R>
702 struct IsNotEqual {
703 static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value,
704 "Types must be numeric.");
705 static constexpr bool Test(const L lhs, const R rhs) {
706 return DstRangeRelationToSrcRange<R>(lhs) !=
707 DstRangeRelationToSrcRange<L>(rhs) ||
708 static_cast<decltype(lhs + rhs)>(lhs) !=
709 static_cast<decltype(lhs + rhs)>(rhs);
710 }
711 };
712
713 // These perform the actual math operations on the CheckedNumerics.
714 // Binary arithmetic operations.
715 template <template <typename, typename> class C, typename L, typename R>
716 constexpr bool SafeCompare(const L lhs, const R rhs) {
717 static_assert(std::is_arithmetic<L>::value && std::is_arithmetic<R>::value,
718 "Types must be numeric.");
719 using Promotion = BigEnoughPromotion<L, R>;
720 using BigType = typename Promotion::type;
721 return Promotion::is_contained
722 // Force to a larger type for speed if both are contained.
723 ? C<BigType, BigType>::Test(
724 static_cast<BigType>(static_cast<L>(lhs)),
725 static_cast<BigType>(static_cast<R>(rhs)))
726 // Let the template functions figure it out for mixed types.
727 : C<L, R>::Test(lhs, rhs);
728 };
729
214 } // namespace internal 730 } // namespace internal
215 } // namespace base 731 } // namespace base
216 } // namespace pdfium 732 } // namespace pdfium
217 733
218 #endif // PDFIUM_THIRD_PARTY_BASE_SAFE_CONVERSIONS_IMPL_H_ 734 #endif // PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_
OLDNEW
« no previous file with comments | « third_party/base/numerics/safe_conversions.h ('k') | third_party/base/numerics/safe_math.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698