1 | /* |
2 | * Copyright 2017-present Facebook, Inc. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | |
17 | #pragma once |
18 | |
19 | #include <cstdint> |
20 | #include <limits> |
21 | #include <type_traits> |
22 | |
23 | namespace folly { |
24 | |
25 | // TODO: Replace with std::equal_to, etc., after upgrading to C++14. |
26 | template <typename T> |
27 | struct constexpr_equal_to { |
28 | constexpr bool operator()(T const& a, T const& b) const { |
29 | return a == b; |
30 | } |
31 | }; |
32 | template <typename T> |
33 | struct constexpr_not_equal_to { |
34 | constexpr bool operator()(T const& a, T const& b) const { |
35 | return a != b; |
36 | } |
37 | }; |
38 | template <typename T> |
39 | struct constexpr_less { |
40 | constexpr bool operator()(T const& a, T const& b) const { |
41 | return a < b; |
42 | } |
43 | }; |
44 | template <typename T> |
45 | struct constexpr_less_equal { |
46 | constexpr bool operator()(T const& a, T const& b) const { |
47 | return a <= b; |
48 | } |
49 | }; |
50 | template <typename T> |
51 | struct constexpr_greater { |
52 | constexpr bool operator()(T const& a, T const& b) const { |
53 | return a > b; |
54 | } |
55 | }; |
56 | template <typename T> |
57 | struct constexpr_greater_equal { |
58 | constexpr bool operator()(T const& a, T const& b) const { |
59 | return a >= b; |
60 | } |
61 | }; |
62 | |
63 | // TLDR: Prefer using operator< for ordering. And when |
64 | // a and b are equivalent objects, we return b to make |
65 | // sorting stable. |
66 | // See http://stepanovpapers.com/notes.pdf for details. |
67 | template <typename T> |
68 | constexpr T constexpr_max(T a) { |
69 | return a; |
70 | } |
71 | template <typename T, typename... Ts> |
72 | constexpr T constexpr_max(T a, T b, Ts... ts) { |
73 | return b < a ? constexpr_max(a, ts...) : constexpr_max(b, ts...); |
74 | } |
75 | |
76 | // When a and b are equivalent objects, we return a to |
77 | // make sorting stable. |
78 | template <typename T> |
79 | constexpr T constexpr_min(T a) { |
80 | return a; |
81 | } |
82 | template <typename T, typename... Ts> |
83 | constexpr T constexpr_min(T a, T b, Ts... ts) { |
84 | return b < a ? constexpr_min(b, ts...) : constexpr_min(a, ts...); |
85 | } |
86 | |
87 | template <typename T, typename Less> |
88 | constexpr T const& |
89 | constexpr_clamp(T const& v, T const& lo, T const& hi, Less less) { |
90 | return less(v, lo) ? lo : less(hi, v) ? hi : v; |
91 | } |
92 | template <typename T> |
93 | constexpr T const& constexpr_clamp(T const& v, T const& lo, T const& hi) { |
94 | return constexpr_clamp(v, lo, hi, constexpr_less<T>{}); |
95 | } |
96 | |
97 | namespace detail { |
98 | |
99 | template <typename T, typename = void> |
100 | struct constexpr_abs_helper {}; |
101 | |
102 | template <typename T> |
103 | struct constexpr_abs_helper< |
104 | T, |
105 | typename std::enable_if<std::is_floating_point<T>::value>::type> { |
106 | static constexpr T go(T t) { |
107 | return t < static_cast<T>(0) ? -t : t; |
108 | } |
109 | }; |
110 | |
111 | template <typename T> |
112 | struct constexpr_abs_helper< |
113 | T, |
114 | typename std::enable_if< |
115 | std::is_integral<T>::value && !std::is_same<T, bool>::value && |
116 | std::is_unsigned<T>::value>::type> { |
117 | static constexpr T go(T t) { |
118 | return t; |
119 | } |
120 | }; |
121 | |
122 | template <typename T> |
123 | struct constexpr_abs_helper< |
124 | T, |
125 | typename std::enable_if< |
126 | std::is_integral<T>::value && !std::is_same<T, bool>::value && |
127 | std::is_signed<T>::value>::type> { |
128 | static constexpr typename std::make_unsigned<T>::type go(T t) { |
129 | return typename std::make_unsigned<T>::type(t < static_cast<T>(0) ? -t : t); |
130 | } |
131 | }; |
132 | } // namespace detail |
133 | |
134 | template <typename T> |
135 | constexpr auto constexpr_abs(T t) |
136 | -> decltype(detail::constexpr_abs_helper<T>::go(t)) { |
137 | return detail::constexpr_abs_helper<T>::go(t); |
138 | } |
139 | |
140 | namespace detail { |
141 | template <typename T> |
142 | constexpr T constexpr_log2_(T a, T e) { |
143 | return e == T(1) ? a : constexpr_log2_(a + T(1), e / T(2)); |
144 | } |
145 | |
146 | template <typename T> |
147 | constexpr T constexpr_log2_ceil_(T l2, T t) { |
148 | return l2 + T(T(1) << l2 < t ? 1 : 0); |
149 | } |
150 | |
151 | template <typename T> |
152 | constexpr T constexpr_square_(T t) { |
153 | return t * t; |
154 | } |
155 | } // namespace detail |
156 | |
157 | template <typename T> |
158 | constexpr T constexpr_log2(T t) { |
159 | return detail::constexpr_log2_(T(0), t); |
160 | } |
161 | |
162 | template <typename T> |
163 | constexpr T constexpr_log2_ceil(T t) { |
164 | return detail::constexpr_log2_ceil_(constexpr_log2(t), t); |
165 | } |
166 | |
167 | template <typename T> |
168 | constexpr T constexpr_ceil(T t, T round) { |
169 | return round == T(0) |
170 | ? t |
171 | : ((t + (t < T(0) ? T(0) : round - T(1))) / round) * round; |
172 | } |
173 | |
174 | template <typename T> |
175 | constexpr T constexpr_pow(T base, std::size_t exp) { |
176 | return exp == 0 |
177 | ? T(1) |
178 | : exp == 1 ? base |
179 | : detail::constexpr_square_(constexpr_pow(base, exp / 2)) * |
180 | (exp % 2 ? base : T(1)); |
181 | } |
182 | |
183 | /// constexpr_find_last_set |
184 | /// |
185 | /// Return the 1-based index of the most significant bit which is set. |
186 | /// For x > 0, constexpr_find_last_set(x) == 1 + floor(log2(x)). |
187 | template <typename T> |
188 | constexpr std::size_t constexpr_find_last_set(T const t) { |
189 | using U = std::make_unsigned_t<T>; |
190 | return t == T(0) ? 0 : 1 + constexpr_log2(static_cast<U>(t)); |
191 | } |
192 | |
193 | namespace detail { |
194 | template <typename U> |
195 | constexpr std::size_t |
196 | constexpr_find_first_set_(std::size_t s, std::size_t a, U const u) { |
197 | return s == 0 ? a |
198 | : constexpr_find_first_set_( |
199 | s / 2, a + s * bool((u >> a) % (U(1) << s) == U(0)), u); |
200 | } |
201 | } // namespace detail |
202 | |
203 | /// constexpr_find_first_set |
204 | /// |
205 | /// Return the 1-based index of the least significant bit which is set. |
206 | /// For x > 0, the exponent in the largest power of two which does not divide x. |
207 | template <typename T> |
208 | constexpr std::size_t constexpr_find_first_set(T t) { |
209 | using U = std::make_unsigned_t<T>; |
210 | using size = std::integral_constant<std::size_t, sizeof(T) * 4>; |
211 | return t == T(0) |
212 | ? 0 |
213 | : 1 + detail::constexpr_find_first_set_(size{}, 0, static_cast<U>(t)); |
214 | } |
215 | |
216 | template <typename T> |
217 | constexpr T constexpr_add_overflow_clamped(T a, T b) { |
218 | using L = std::numeric_limits<T>; |
219 | using M = std::intmax_t; |
220 | static_assert( |
221 | !std::is_integral<T>::value || sizeof(T) <= sizeof(M), |
222 | "Integral type too large!" ); |
223 | // clang-format off |
224 | return |
225 | // don't do anything special for non-integral types. |
226 | !std::is_integral<T>::value ? a + b : |
227 | // for narrow integral types, just convert to intmax_t. |
228 | sizeof(T) < sizeof(M) |
229 | ? T(constexpr_clamp(M(a) + M(b), M(L::min()), M(L::max()))) : |
230 | // when a >= 0, cannot add more than `MAX - a` onto a. |
231 | !(a < 0) ? a + constexpr_min(b, T(L::max() - a)) : |
232 | // a < 0 && b >= 0, `a + b` will always be in valid range of type T. |
233 | !(b < 0) ? a + b : |
234 | // a < 0 && b < 0, keep the result >= MIN. |
235 | a + constexpr_max(b, T(L::min() - a)); |
236 | // clang-format on |
237 | } |
238 | |
239 | template <typename T> |
240 | constexpr T constexpr_sub_overflow_clamped(T a, T b) { |
241 | using L = std::numeric_limits<T>; |
242 | using M = std::intmax_t; |
243 | static_assert( |
244 | !std::is_integral<T>::value || sizeof(T) <= sizeof(M), |
245 | "Integral type too large!" ); |
246 | // clang-format off |
247 | return |
248 | // don't do anything special for non-integral types. |
249 | !std::is_integral<T>::value ? a - b : |
250 | // for unsigned type, keep result >= 0. |
251 | std::is_unsigned<T>::value ? (a < b ? 0 : a - b) : |
252 | // for narrow signed integral types, just convert to intmax_t. |
253 | sizeof(T) < sizeof(M) |
254 | ? T(constexpr_clamp(M(a) - M(b), M(L::min()), M(L::max()))) : |
255 | // (a >= 0 && b >= 0) || (a < 0 && b < 0), `a - b` will always be valid. |
256 | (a < 0) == (b < 0) ? a - b : |
257 | // MIN < b, so `-b` should be in valid range (-MAX <= -b <= MAX), |
258 | // convert subtraction to addition. |
259 | L::min() < b ? constexpr_add_overflow_clamped(a, T(-b)) : |
260 | // -b = -MIN = (MAX + 1) and a <= -1, result is in valid range. |
261 | a < 0 ? a - b : |
262 | // -b = -MIN = (MAX + 1) and a >= 0, result > MAX. |
263 | L::max(); |
264 | // clang-format on |
265 | } |
266 | |
267 | // clamp_cast<> provides sane numeric conversions from float point numbers to |
268 | // integral numbers, and between different types of integral numbers. It helps |
269 | // to avoid unexpected bugs introduced by bad conversion, and undefined behavior |
270 | // like overflow when casting float point numbers to integral numbers. |
271 | // |
272 | // When doing clamp_cast<Dst>(value), if `value` is in valid range of Dst, |
273 | // it will give correct result in Dst, equal to `value`. |
274 | // |
275 | // If `value` is outside the representable range of Dst, it will be clamped to |
276 | // MAX or MIN in Dst, instead of being undefined behavior. |
277 | // |
278 | // Float NaNs are converted to 0 in integral type. |
279 | // |
280 | // Here's some comparision with static_cast<>: |
281 | // (with FB-internal gcc-5-glibc-2.23 toolchain) |
282 | // |
283 | // static_cast<int32_t>(NaN) = 6 |
284 | // clamp_cast<int32_t>(NaN) = 0 |
285 | // |
286 | // static_cast<int32_t>(9999999999.0f) = -348639895 |
287 | // clamp_cast<int32_t>(9999999999.0f) = 2147483647 |
288 | // |
289 | // static_cast<int32_t>(2147483647.0f) = -348639895 |
290 | // clamp_cast<int32_t>(2147483647.0f) = 2147483647 |
291 | // |
292 | // static_cast<uint32_t>(4294967295.0f) = 0 |
293 | // clamp_cast<uint32_t>(4294967295.0f) = 4294967295 |
294 | // |
295 | // static_cast<uint32_t>(-1) = 4294967295 |
296 | // clamp_cast<uint32_t>(-1) = 0 |
297 | // |
298 | // static_cast<int16_t>(32768u) = -32768 |
299 | // clamp_cast<int16_t>(32768u) = 32767 |
300 | |
301 | template <typename Dst, typename Src> |
302 | constexpr typename std::enable_if<std::is_integral<Src>::value, Dst>::type |
303 | constexpr_clamp_cast(Src src) { |
304 | static_assert( |
305 | std::is_integral<Dst>::value && sizeof(Dst) <= sizeof(int64_t), |
306 | "constexpr_clamp_cast can only cast into integral type (up to 64bit)" ); |
307 | |
308 | using L = std::numeric_limits<Dst>; |
309 | // clang-format off |
310 | return |
311 | // Check if Src and Dst have same signedness. |
312 | std::is_signed<Src>::value == std::is_signed<Dst>::value |
313 | ? ( |
314 | // Src and Dst have same signedness. If sizeof(Src) <= sizeof(Dst), |
315 | // we can safely convert Src to Dst without any loss of accuracy. |
316 | sizeof(Src) <= sizeof(Dst) ? Dst(src) : |
317 | // If Src is larger in size, we need to clamp it to valid range in Dst. |
318 | Dst(constexpr_clamp(src, Src(L::min()), Src(L::max())))) |
319 | // Src and Dst have different signedness. |
320 | // Check if it's signed -> unsigend cast. |
321 | : std::is_signed<Src>::value && std::is_unsigned<Dst>::value |
322 | ? ( |
323 | // If src < 0, the result should be 0. |
324 | src < 0 ? Dst(0) : |
325 | // Otherwise, src >= 0. If src can fit into Dst, we can safely cast it |
326 | // without loss of accuracy. |
327 | sizeof(Src) <= sizeof(Dst) ? Dst(src) : |
328 | // If Src is larger in size than Dst, we need to ensure the result is |
329 | // at most Dst MAX. |
330 | Dst(constexpr_min(src, Src(L::max())))) |
331 | // It's unsigned -> signed cast. |
332 | : ( |
333 | // Since Src is unsigned, and Dst is signed, Src can fit into Dst only |
334 | // when sizeof(Src) < sizeof(Dst). |
335 | sizeof(Src) < sizeof(Dst) ? Dst(src) : |
336 | // If Src does not fit into Dst, we need to ensure the result is at most |
337 | // Dst MAX. |
338 | Dst(constexpr_min(src, Src(L::max())))); |
339 | // clang-format on |
340 | } |
341 | |
342 | namespace detail { |
343 | // Upper/lower bound values that could be accurately represented in both |
344 | // integral and float point types. |
345 | constexpr double kClampCastLowerBoundDoubleToInt64F = -9223372036854774784.0; |
346 | constexpr double kClampCastUpperBoundDoubleToInt64F = 9223372036854774784.0; |
347 | constexpr double kClampCastUpperBoundDoubleToUInt64F = 18446744073709549568.0; |
348 | |
349 | constexpr float kClampCastLowerBoundFloatToInt32F = -2147483520.0f; |
350 | constexpr float kClampCastUpperBoundFloatToInt32F = 2147483520.0f; |
351 | constexpr float kClampCastUpperBoundFloatToUInt32F = 4294967040.0f; |
352 | |
353 | // This works the same as constexpr_clamp, but the comparision are done in Src |
354 | // to prevent any implicit promotions. |
355 | template <typename D, typename S> |
356 | constexpr D constexpr_clamp_cast_helper(S src, S sl, S su, D dl, D du) { |
357 | return src < sl ? dl : (src > su ? du : D(src)); |
358 | } |
359 | } // namespace detail |
360 | |
361 | template <typename Dst, typename Src> |
362 | constexpr typename std::enable_if<std::is_floating_point<Src>::value, Dst>::type |
363 | constexpr_clamp_cast(Src src) { |
364 | static_assert( |
365 | std::is_integral<Dst>::value && sizeof(Dst) <= sizeof(int64_t), |
366 | "constexpr_clamp_cast can only cast into integral type (up to 64bit)" ); |
367 | |
368 | using L = std::numeric_limits<Dst>; |
369 | // clang-format off |
370 | return |
371 | // Special case: cast NaN into 0. |
372 | // Using a trick here to portably check for NaN: f != f only if f is NaN. |
373 | // see: https://stackoverflow.com/a/570694 |
374 | (src != src) ? Dst(0) : |
375 | // using `sizeof(Src) > sizeof(Dst)` as a heuristic that Dst can be |
376 | // represented in Src without loss of accuracy. |
377 | // see: https://en.wikipedia.org/wiki/Floating-point_arithmetic |
378 | sizeof(Src) > sizeof(Dst) ? |
379 | detail::constexpr_clamp_cast_helper( |
380 | src, Src(L::min()), Src(L::max()), L::min(), L::max()) : |
381 | // sizeof(Src) < sizeof(Dst) only happens when doing cast of |
382 | // 32bit float -> u/int64_t. |
383 | // Losslessly promote float into double, change into double -> u/int64_t. |
384 | sizeof(Src) < sizeof(Dst) ? ( |
385 | src >= 0.0 |
386 | ? constexpr_clamp_cast<Dst>( |
387 | constexpr_clamp_cast<std::uint64_t>(double(src))) |
388 | : constexpr_clamp_cast<Dst>( |
389 | constexpr_clamp_cast<std::int64_t>(double(src)))) : |
390 | // The following are for sizeof(Src) == sizeof(Dst). |
391 | std::is_same<Src, double>::value && std::is_same<Dst, int64_t>::value ? |
392 | detail::constexpr_clamp_cast_helper( |
393 | double(src), |
394 | detail::kClampCastLowerBoundDoubleToInt64F, |
395 | detail::kClampCastUpperBoundDoubleToInt64F, |
396 | L::min(), |
397 | L::max()) : |
398 | std::is_same<Src, double>::value && std::is_same<Dst, uint64_t>::value ? |
399 | detail::constexpr_clamp_cast_helper( |
400 | double(src), |
401 | 0.0, |
402 | detail::kClampCastUpperBoundDoubleToUInt64F, |
403 | L::min(), |
404 | L::max()) : |
405 | std::is_same<Src, float>::value && std::is_same<Dst, int32_t>::value ? |
406 | detail::constexpr_clamp_cast_helper( |
407 | float(src), |
408 | detail::kClampCastLowerBoundFloatToInt32F, |
409 | detail::kClampCastUpperBoundFloatToInt32F, |
410 | L::min(), |
411 | L::max()) : |
412 | detail::constexpr_clamp_cast_helper( |
413 | float(src), |
414 | 0.0f, |
415 | detail::kClampCastUpperBoundFloatToUInt32F, |
416 | L::min(), |
417 | L::max()); |
418 | // clang-format on |
419 | } |
420 | |
421 | } // namespace folly |
422 | |