1 /*
2  * Copyright 2013 Google Inc.
3  *
4  * Use of this source code is governed by a BSD-style license that can be
5  * found in the LICENSE file.
6  */
7 
8 #ifndef SkTFitsIn_DEFINED
9 #define SkTFitsIn_DEFINED
10 
11 #include "../private/SkTLogic.h"
12 #include <limits>
13 #include <type_traits>
14 
15 /**
16  * In C++ an unsigned to signed cast where the source value cannot be represented in the destination
17  * type results in an implementation defined destination value. Unlike C, C++ does not allow a trap.
18  * This makes "(S)(D)s == s" a possibly useful test. However, there are two cases where this is
19  * incorrect:
20  *
21  * when testing if a value of a smaller signed type can be represented in a larger unsigned type
22  * (int8_t)(uint16_t)-1 == -1 => (int8_t)0xFFFF == -1 => [implementation defined] == -1
23  *
24  * when testing if a value of a larger unsigned type can be represented in a smaller signed type
25  * (uint16_t)(int8_t)0xFFFF == 0xFFFF => (uint16_t)-1 == 0xFFFF => 0xFFFF == 0xFFFF => true.
26  *
27  * Consider the cases:
28  * u = unsigned, s = signed, X = more digits, x = less digits
29  * ux -> uX: (ux)(uX)ux == ux, trivially true
30  * uX -> ux: (uX)(ux)uX == uX, both casts well defined, test works
31  * sx -> sX: (sx)(sX)sx == sx, trivially true
32  * sX -> sx: (sX)(sx)sX == sX, first cast implementation value, second cast defined, test works
33  * sx -> uX: (sx)(uX)sx == sx, this is bad, the second cast results in implementation defined value
34  * sX -> ux: (sX)(ux)sX == sX, the second cast is required to prevent promotion of rhs to unsigned
35  * ux -> sX: (ux)(sX)ux == ux, trivially true
36  * uX -> sx: (uX)(sx)uX == uX, this is bad,
37  *                             first cast results in implementation defined value,
38  *                             second cast is defined. However, this creates false positives
39  *                             uint16_t x = 0xFFFF
40  *                                (uint16_t)(int8_t)x == x
41  *                             => (uint16_t)-1        == x
42  *                             => 0xFFFF              == x
43  *                             => true
44  *
45  * So for the eight cases three are trivially true, three more are valid casts, and two are special.
46  * The two 'full' checks which otherwise require two comparisons are valid cast checks.
47  * The two remaining checks uX -> sx [uX < max(sx)] and sx -> uX [sx > 0] can be done with one op.
48  */
49 
50 namespace sktfitsin {
51 namespace Private {
52 
53 /** SkTMux::type = (a && b) ? Both : (a) ? A : (b) ? B : Neither; */
54 template <bool a, bool b, typename Both, typename A, typename B, typename Neither>
55 struct SkTMux {
56     using type = skstd::conditional_t<a, skstd::conditional_t<b, Both, A>,
57                                          skstd::conditional_t<b, B, Neither>>;
58 };
59 
60 /** SkTHasMoreDigits = (digits(A) >= digits(B)) ? true_type : false_type. */
61 template <typename A, typename B> struct SkTHasMoreDigits
62     : skstd::bool_constant<std::numeric_limits<A>::digits >= std::numeric_limits<B>::digits>
63 { };
64 
65 /** Returns true.
66  *  Used when it is statically known that source values are in the range of the Destination.
67  */
68 template <typename S> struct SkTInRange_True {
69     static constexpr bool fits(S) {
70         return true;
71     }
72 };
73 
74 /** Tests that (S)(D)s == s.
75  *  This is not valid for uX -> sx and sx -> uX conversions.
76  */
77 template <typename D, typename S> struct SkTInRange_Cast {
78     static constexpr bool fits(S s) {
79         using S_is_bigger = SkTHasMoreDigits<S, D>;
80         using D_is_bigger = SkTHasMoreDigits<D, S>;
81 
82         using S_is_signed = skstd::bool_constant<std::numeric_limits<S>::is_signed>;
83         using D_is_signed = skstd::bool_constant<std::numeric_limits<D>::is_signed>;
84 
85         using precondition = skstd::bool_constant<
86             !((!S_is_signed::value &&  D_is_signed::value && S_is_bigger::value) ||
87               ( S_is_signed::value && !D_is_signed::value && D_is_bigger::value)   )>;
88         static_assert(precondition::value, "not valid for uX -> sx and sx -> uX conversions");
89 
90         return static_cast<S>(static_cast<D>(s)) == s;
91     }
92 };
93 
94 /** Tests if the source value <= Max(D).
95  *  Assumes that Max(S) >= Max(D).
96  */
97 template <typename D, typename S> struct SkTInRange_LE_MaxD {
98     static constexpr bool fits(S s) {
99         using precondition = SkTHasMoreDigits<S, D>;
100         static_assert(precondition::value, "maxS < maxD");
101 
102         return s <= static_cast<S>((std::numeric_limits<D>::max)());
103 
104     }
105 };
106 
107 /** Tests if the source value >= 0. */
108 template <typename D, typename S> struct SkTInRange_GE_Zero {
109     static constexpr bool fits(S s) {
110         return static_cast<S>(0) <= s;
111     }
112 };
113 
114 /** SkTFitsIn_Unsigned2Unsiged::type is an SkTInRange with an fits(S s) method
115  *  the implementation of which is tailored for the source and destination types.
116  *  Assumes that S and D are unsigned integer types.
117  */
118 template <typename D, typename S> struct SkTFitsIn_Unsigned2Unsiged {
119     using CastCheck = SkTInRange_Cast<D, S>;
120     using NoCheck = SkTInRange_True<S>;
121 
122     // If std::numeric_limits<D>::digits >= std::numeric_limits<S>::digits, nothing to check.
123     using sourceFitsInDesitination = SkTHasMoreDigits<D, S>;
124     using type = skstd::conditional_t<sourceFitsInDesitination::value, NoCheck, CastCheck>;
125 };
126 
127 /** SkTFitsIn_Signed2Signed::type is an SkTInRange with an fits(S s) method
128  *  the implementation of which is tailored for the source and destination types.
129  *  Assumes that S and D are signed integer types.
130  */
131 template <typename D, typename S> struct SkTFitsIn_Signed2Signed {
132     using CastCheck = SkTInRange_Cast<D, S>;
133     using NoCheck = SkTInRange_True<S>;
134 
135     // If std::numeric_limits<D>::digits >= std::numeric_limits<S>::digits, nothing to check.
136     using sourceFitsInDesitination = SkTHasMoreDigits<D, S>;
137     using type = skstd::conditional_t<sourceFitsInDesitination::value, NoCheck, CastCheck>;
138 };
139 
140 /** SkTFitsIn_Signed2Unsigned::type is an SkTInRange with an fits(S s) method
141  *  the implementation of which is tailored for the source and destination types.
142  *  Assumes that S is a signed integer type and D is an unsigned integer type.
143  */
144 template <typename D, typename S> struct SkTFitsIn_Signed2Unsigned {
145     using CastCheck = SkTInRange_Cast<D, S>;
146     using LowSideOnlyCheck = SkTInRange_GE_Zero<D, S>;
147 
148     // If std::numeric_limits<D>::max() >= std::numeric_limits<S>::max(),
149     // no need to check the high side. (Until C++11, assume more digits means greater max.)
150     // This also protects the precondition of SkTInRange_Cast.
151     using sourceCannotExceedDest = SkTHasMoreDigits<D, S>;
152     using type = skstd::conditional_t<sourceCannotExceedDest::value, LowSideOnlyCheck, CastCheck>;
153 };
154 
155 /** SkTFitsIn_Unsigned2Signed::type is an SkTInRange with an fits(S s) method
156  *  the implementation of which is tailored for the source and destination types.
157  *  Assumes that S is an usigned integer type and D is a signed integer type.
158  */
159 template <typename D, typename S> struct SkTFitsIn_Unsigned2Signed {
160     using HighSideCheck = SkTInRange_LE_MaxD<D, S>;
161     using NoCheck = SkTInRange_True<S>;
162 
163     // If std::numeric_limits<D>::max() >= std::numeric_limits<S>::max(), nothing to check.
164     // (Until C++11, assume more digits means greater max.)
165     using sourceCannotExceedDest = SkTHasMoreDigits<D, S>;
166     using type = skstd::conditional_t<sourceCannotExceedDest::value, NoCheck, HighSideCheck>;
167 };
168 
169 /** SkTFitsIn::type is an SkTInRange with an fits(S s) method
170  *  the implementation of which is tailored for the source and destination types.
171  *  Assumes that S and D are integer types.
172  */
173 template <typename D, typename S> struct SkTFitsIn {
174     // One of the following will be the 'selector' type.
175     using S2S = SkTFitsIn_Signed2Signed<D, S>;
176     using S2U = SkTFitsIn_Signed2Unsigned<D, S>;
177     using U2S = SkTFitsIn_Unsigned2Signed<D, S>;
178     using U2U = SkTFitsIn_Unsigned2Unsiged<D, S>;
179 
180     using S_is_signed = skstd::bool_constant<std::numeric_limits<S>::is_signed>;
181     using D_is_signed = skstd::bool_constant<std::numeric_limits<D>::is_signed>;
182 
183     using selector = typename SkTMux<S_is_signed::value, D_is_signed::value,
184                                      S2S, S2U, U2S, U2U>::type;
185     // This type is an SkTInRange.
186     using type = typename selector::type;
187 };
188 
189 template <typename T, bool = std::is_enum<T>::value> struct underlying_type {
190     using type = skstd::underlying_type_t<T>;
191 };
192 template <typename T> struct underlying_type<T, false> {
193     using type = T;
194 };
195 
196 } // namespace Private
197 } // namespace sktfitsin
198 
199 /** Returns true if the integer source value 's' will fit in the integer destination type 'D'. */
200 template <typename D, typename S> constexpr inline bool SkTFitsIn(S s) {
201     static_assert(std::is_integral<S>::value || std::is_enum<S>::value, "S must be integral.");
202     static_assert(std::is_integral<D>::value || std::is_enum<D>::value, "D must be integral.");
203 
204     using RealS = typename sktfitsin::Private::underlying_type<S>::type;
205     using RealD = typename sktfitsin::Private::underlying_type<D>::type;
206 
207     return sktfitsin::Private::SkTFitsIn<RealD, RealS>::type::fits(s);
208 }
209 
210 #endif
211