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