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
23namespace folly {
24
25// TODO: Replace with std::equal_to, etc., after upgrading to C++14.
26template <typename T>
27struct constexpr_equal_to {
28 constexpr bool operator()(T const& a, T const& b) const {
29 return a == b;
30 }
31};
32template <typename T>
33struct constexpr_not_equal_to {
34 constexpr bool operator()(T const& a, T const& b) const {
35 return a != b;
36 }
37};
38template <typename T>
39struct constexpr_less {
40 constexpr bool operator()(T const& a, T const& b) const {
41 return a < b;
42 }
43};
44template <typename T>
45struct constexpr_less_equal {
46 constexpr bool operator()(T const& a, T const& b) const {
47 return a <= b;
48 }
49};
50template <typename T>
51struct constexpr_greater {
52 constexpr bool operator()(T const& a, T const& b) const {
53 return a > b;
54 }
55};
56template <typename T>
57struct 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.
67template <typename T>
68constexpr T constexpr_max(T a) {
69 return a;
70}
71template <typename T, typename... Ts>
72constexpr 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.
78template <typename T>
79constexpr T constexpr_min(T a) {
80 return a;
81}
82template <typename T, typename... Ts>
83constexpr T constexpr_min(T a, T b, Ts... ts) {
84 return b < a ? constexpr_min(b, ts...) : constexpr_min(a, ts...);
85}
86
87template <typename T, typename Less>
88constexpr T const&
89constexpr_clamp(T const& v, T const& lo, T const& hi, Less less) {
90 return less(v, lo) ? lo : less(hi, v) ? hi : v;
91}
92template <typename T>
93constexpr 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
97namespace detail {
98
99template <typename T, typename = void>
100struct constexpr_abs_helper {};
101
102template <typename T>
103struct 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
111template <typename T>
112struct 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
122template <typename T>
123struct 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
134template <typename T>
135constexpr 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
140namespace detail {
141template <typename T>
142constexpr T constexpr_log2_(T a, T e) {
143 return e == T(1) ? a : constexpr_log2_(a + T(1), e / T(2));
144}
145
146template <typename T>
147constexpr T constexpr_log2_ceil_(T l2, T t) {
148 return l2 + T(T(1) << l2 < t ? 1 : 0);
149}
150
151template <typename T>
152constexpr T constexpr_square_(T t) {
153 return t * t;
154}
155} // namespace detail
156
157template <typename T>
158constexpr T constexpr_log2(T t) {
159 return detail::constexpr_log2_(T(0), t);
160}
161
162template <typename T>
163constexpr T constexpr_log2_ceil(T t) {
164 return detail::constexpr_log2_ceil_(constexpr_log2(t), t);
165}
166
167template <typename T>
168constexpr 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
174template <typename T>
175constexpr 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)).
187template <typename T>
188constexpr 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
193namespace detail {
194template <typename U>
195constexpr std::size_t
196constexpr_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.
207template <typename T>
208constexpr 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
216template <typename T>
217constexpr 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
239template <typename T>
240constexpr 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
301template <typename Dst, typename Src>
302constexpr typename std::enable_if<std::is_integral<Src>::value, Dst>::type
303constexpr_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
342namespace detail {
343// Upper/lower bound values that could be accurately represented in both
344// integral and float point types.
345constexpr double kClampCastLowerBoundDoubleToInt64F = -9223372036854774784.0;
346constexpr double kClampCastUpperBoundDoubleToInt64F = 9223372036854774784.0;
347constexpr double kClampCastUpperBoundDoubleToUInt64F = 18446744073709549568.0;
348
349constexpr float kClampCastLowerBoundFloatToInt32F = -2147483520.0f;
350constexpr float kClampCastUpperBoundFloatToInt32F = 2147483520.0f;
351constexpr 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.
355template <typename D, typename S>
356constexpr 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
361template <typename Dst, typename Src>
362constexpr typename std::enable_if<std::is_floating_point<Src>::value, Dst>::type
363constexpr_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