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