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