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