blob: e1d376a0a12c8ec147cc19aa0a906ef92fa2d184 [file] [log] [blame]
Vitaly Bukacbed2062015-08-17 12:54:05 -07001// 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 BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_
6#define BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_
7
Alex Vakulenko674f0eb2016-01-20 08:10:48 -08008#include <limits.h>
9#include <stdint.h>
10
Vitaly Bukacbed2062015-08-17 12:54:05 -070011#include <limits>
12
Vitaly Bukacbed2062015-08-17 12:54:05 -070013namespace base {
14namespace internal {
15
16// The std library doesn't provide a binary max_exponent for integers, however
17// we can compute one by adding one to the number of non-sign bits. This allows
18// for accurate range comparisons between floating point and integer types.
19template <typename NumericType>
20struct MaxExponent {
21 static const int value = std::numeric_limits<NumericType>::is_iec559
22 ? std::numeric_limits<NumericType>::max_exponent
23 : (sizeof(NumericType) * 8 + 1 -
24 std::numeric_limits<NumericType>::is_signed);
25};
26
27enum IntegerRepresentation {
28 INTEGER_REPRESENTATION_UNSIGNED,
29 INTEGER_REPRESENTATION_SIGNED
30};
31
32// A range for a given nunmeric Src type is contained for a given numeric Dst
33// type if both numeric_limits<Src>::max() <= numeric_limits<Dst>::max() and
34// numeric_limits<Src>::min() >= numeric_limits<Dst>::min() are true.
35// We implement this as template specializations rather than simple static
36// comparisons to ensure type correctness in our comparisons.
37enum NumericRangeRepresentation {
38 NUMERIC_RANGE_NOT_CONTAINED,
39 NUMERIC_RANGE_CONTAINED
40};
41
42// Helper templates to statically determine if our destination type can contain
43// maximum and minimum values represented by the source type.
44
45template <
46 typename Dst,
47 typename Src,
48 IntegerRepresentation DstSign = std::numeric_limits<Dst>::is_signed
49 ? INTEGER_REPRESENTATION_SIGNED
50 : INTEGER_REPRESENTATION_UNSIGNED,
51 IntegerRepresentation SrcSign =
52 std::numeric_limits<Src>::is_signed
53 ? INTEGER_REPRESENTATION_SIGNED
54 : INTEGER_REPRESENTATION_UNSIGNED >
55struct StaticDstRangeRelationToSrcRange;
56
57// Same sign: Dst is guaranteed to contain Src only if its range is equal or
58// larger.
59template <typename Dst, typename Src, IntegerRepresentation Sign>
60struct StaticDstRangeRelationToSrcRange<Dst, Src, Sign, Sign> {
61 static const NumericRangeRepresentation value =
62 MaxExponent<Dst>::value >= MaxExponent<Src>::value
63 ? NUMERIC_RANGE_CONTAINED
64 : NUMERIC_RANGE_NOT_CONTAINED;
65};
66
67// Unsigned to signed: Dst is guaranteed to contain source only if its range is
68// larger.
69template <typename Dst, typename Src>
70struct StaticDstRangeRelationToSrcRange<Dst,
71 Src,
72 INTEGER_REPRESENTATION_SIGNED,
73 INTEGER_REPRESENTATION_UNSIGNED> {
74 static const NumericRangeRepresentation value =
75 MaxExponent<Dst>::value > MaxExponent<Src>::value
76 ? NUMERIC_RANGE_CONTAINED
77 : NUMERIC_RANGE_NOT_CONTAINED;
78};
79
80// Signed to unsigned: Dst cannot be statically determined to contain Src.
81template <typename Dst, typename Src>
82struct StaticDstRangeRelationToSrcRange<Dst,
83 Src,
84 INTEGER_REPRESENTATION_UNSIGNED,
85 INTEGER_REPRESENTATION_SIGNED> {
86 static const NumericRangeRepresentation value = NUMERIC_RANGE_NOT_CONTAINED;
87};
88
89enum RangeConstraint {
90 RANGE_VALID = 0x0, // Value can be represented by the destination type.
91 RANGE_UNDERFLOW = 0x1, // Value would overflow.
92 RANGE_OVERFLOW = 0x2, // Value would underflow.
93 RANGE_INVALID = RANGE_UNDERFLOW | RANGE_OVERFLOW // Invalid (i.e. NaN).
94};
95
96// Helper function for coercing an int back to a RangeContraint.
97inline RangeConstraint GetRangeConstraint(int integer_range_constraint) {
98 DCHECK(integer_range_constraint >= RANGE_VALID &&
99 integer_range_constraint <= RANGE_INVALID);
100 return static_cast<RangeConstraint>(integer_range_constraint);
101}
102
103// This function creates a RangeConstraint from an upper and lower bound
104// check by taking advantage of the fact that only NaN can be out of range in
105// both directions at once.
106inline RangeConstraint GetRangeConstraint(bool is_in_upper_bound,
107 bool is_in_lower_bound) {
108 return GetRangeConstraint((is_in_upper_bound ? 0 : RANGE_OVERFLOW) |
109 (is_in_lower_bound ? 0 : RANGE_UNDERFLOW));
110}
111
Alex Vakulenko674f0eb2016-01-20 08:10:48 -0800112// The following helper template addresses a corner case in range checks for
113// conversion from a floating-point type to an integral type of smaller range
114// but larger precision (e.g. float -> unsigned). The problem is as follows:
115// 1. Integral maximum is always one less than a power of two, so it must be
116// truncated to fit the mantissa of the floating point. The direction of
117// rounding is implementation defined, but by default it's always IEEE
118// floats, which round to nearest and thus result in a value of larger
119// magnitude than the integral value.
120// Example: float f = UINT_MAX; // f is 4294967296f but UINT_MAX
121// // is 4294967295u.
122// 2. If the floating point value is equal to the promoted integral maximum
123// value, a range check will erroneously pass.
124// Example: (4294967296f <= 4294967295u) // This is true due to a precision
125// // loss in rounding up to float.
126// 3. When the floating point value is then converted to an integral, the
127// resulting value is out of range for the target integral type and
128// thus is implementation defined.
129// Example: unsigned u = (float)INT_MAX; // u will typically overflow to 0.
130// To fix this bug we manually truncate the maximum value when the destination
131// type is an integral of larger precision than the source floating-point type,
132// such that the resulting maximum is represented exactly as a floating point.
133template <typename Dst, typename Src>
134struct NarrowingRange {
135 typedef typename std::numeric_limits<Src> SrcLimits;
136 typedef typename std::numeric_limits<Dst> DstLimits;
137
138 static Dst max() {
139 // The following logic avoids warnings where the max function is
140 // instantiated with invalid values for a bit shift (even though
141 // such a function can never be called).
142 static const int shift =
143 (MaxExponent<Src>::value > MaxExponent<Dst>::value &&
144 SrcLimits::digits < DstLimits::digits && SrcLimits::is_iec559 &&
145 DstLimits::is_integer)
146 ? (DstLimits::digits - SrcLimits::digits)
147 : 0;
148
149 // We use UINTMAX_C below to avoid compiler warnings about shifting floating
150 // points. Since it's a compile time calculation, it shouldn't have any
151 // performance impact.
152 return DstLimits::max() - static_cast<Dst>((UINTMAX_C(1) << shift) - 1);
153 }
154
155 static Dst min() {
156 return std::numeric_limits<Dst>::is_iec559 ? -DstLimits::max()
157 : DstLimits::min();
158 }
159};
160
Vitaly Bukacbed2062015-08-17 12:54:05 -0700161template <
162 typename Dst,
163 typename Src,
164 IntegerRepresentation DstSign = std::numeric_limits<Dst>::is_signed
165 ? INTEGER_REPRESENTATION_SIGNED
166 : INTEGER_REPRESENTATION_UNSIGNED,
167 IntegerRepresentation SrcSign = std::numeric_limits<Src>::is_signed
168 ? INTEGER_REPRESENTATION_SIGNED
169 : INTEGER_REPRESENTATION_UNSIGNED,
170 NumericRangeRepresentation DstRange =
171 StaticDstRangeRelationToSrcRange<Dst, Src>::value >
172struct DstRangeRelationToSrcRangeImpl;
173
174// The following templates are for ranges that must be verified at runtime. We
175// split it into checks based on signedness to avoid confusing casts and
176// compiler warnings on signed an unsigned comparisons.
177
178// Dst range is statically determined to contain Src: Nothing to check.
179template <typename Dst,
180 typename Src,
181 IntegerRepresentation DstSign,
182 IntegerRepresentation SrcSign>
183struct DstRangeRelationToSrcRangeImpl<Dst,
184 Src,
185 DstSign,
186 SrcSign,
187 NUMERIC_RANGE_CONTAINED> {
Alex Vakulenko674f0eb2016-01-20 08:10:48 -0800188 static RangeConstraint Check(Src /* value */) { return RANGE_VALID; }
Vitaly Bukacbed2062015-08-17 12:54:05 -0700189};
190
191// Signed to signed narrowing: Both the upper and lower boundaries may be
192// exceeded.
193template <typename Dst, typename Src>
194struct DstRangeRelationToSrcRangeImpl<Dst,
195 Src,
196 INTEGER_REPRESENTATION_SIGNED,
197 INTEGER_REPRESENTATION_SIGNED,
198 NUMERIC_RANGE_NOT_CONTAINED> {
199 static RangeConstraint Check(Src value) {
Alex Vakulenko674f0eb2016-01-20 08:10:48 -0800200 return GetRangeConstraint((value <= NarrowingRange<Dst, Src>::max()),
201 (value >= NarrowingRange<Dst, Src>::min()));
Vitaly Bukacbed2062015-08-17 12:54:05 -0700202 }
203};
204
205// Unsigned to unsigned narrowing: Only the upper boundary can be exceeded.
206template <typename Dst, typename Src>
207struct DstRangeRelationToSrcRangeImpl<Dst,
208 Src,
209 INTEGER_REPRESENTATION_UNSIGNED,
210 INTEGER_REPRESENTATION_UNSIGNED,
211 NUMERIC_RANGE_NOT_CONTAINED> {
212 static RangeConstraint Check(Src value) {
Alex Vakulenko674f0eb2016-01-20 08:10:48 -0800213 return GetRangeConstraint(value <= NarrowingRange<Dst, Src>::max(), true);
Vitaly Bukacbed2062015-08-17 12:54:05 -0700214 }
215};
216
217// Unsigned to signed: The upper boundary may be exceeded.
218template <typename Dst, typename Src>
219struct DstRangeRelationToSrcRangeImpl<Dst,
220 Src,
221 INTEGER_REPRESENTATION_SIGNED,
222 INTEGER_REPRESENTATION_UNSIGNED,
223 NUMERIC_RANGE_NOT_CONTAINED> {
224 static RangeConstraint Check(Src value) {
225 return sizeof(Dst) > sizeof(Src)
226 ? RANGE_VALID
227 : GetRangeConstraint(
Alex Vakulenko674f0eb2016-01-20 08:10:48 -0800228 value <= static_cast<Src>(NarrowingRange<Dst, Src>::max()),
Vitaly Bukacbed2062015-08-17 12:54:05 -0700229 true);
230 }
231};
232
233// Signed to unsigned: The upper boundary may be exceeded for a narrower Dst,
234// and any negative value exceeds the lower boundary.
235template <typename Dst, typename Src>
236struct DstRangeRelationToSrcRangeImpl<Dst,
237 Src,
238 INTEGER_REPRESENTATION_UNSIGNED,
239 INTEGER_REPRESENTATION_SIGNED,
240 NUMERIC_RANGE_NOT_CONTAINED> {
241 static RangeConstraint Check(Src value) {
242 return (MaxExponent<Dst>::value >= MaxExponent<Src>::value)
243 ? GetRangeConstraint(true, value >= static_cast<Src>(0))
244 : GetRangeConstraint(
Alex Vakulenko674f0eb2016-01-20 08:10:48 -0800245 value <= static_cast<Src>(NarrowingRange<Dst, Src>::max()),
Vitaly Bukacbed2062015-08-17 12:54:05 -0700246 value >= static_cast<Src>(0));
247 }
248};
249
250template <typename Dst, typename Src>
251inline RangeConstraint DstRangeRelationToSrcRange(Src value) {
252 static_assert(std::numeric_limits<Src>::is_specialized,
253 "Argument must be numeric.");
254 static_assert(std::numeric_limits<Dst>::is_specialized,
255 "Result must be numeric.");
256 return DstRangeRelationToSrcRangeImpl<Dst, Src>::Check(value);
257}
258
259} // namespace internal
260} // namespace base
261
262#endif // BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_