/* * Copyright (c) Meta Platforms, Inc. and affiliates. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ #pragma once #include <cassert> #include <cstddef> #include <cstdint> #include <functional> #include <limits> #include <type_traits> #include <folly/Portability.h> #include <folly/lang/CheckedMath.h> #include <folly/portability/Constexpr.h> namespace folly { /// numbers /// /// mimic: std::numbers, C++20 (partial) namespace numbers { namespace detail { enable_if_floating_t; } /// e_v /// /// mimic: std::numbers::e_v, C++20 e_v; /// ln2_v /// /// mimic: std::numbers::ln2_v, C++20 ln2_v; /// e /// /// mimic: std::numbers::e, C++20 inline constexpr double e = …; /// ln2 /// /// mimic: std::numbers::ln2, C++20 inline constexpr double ln2 = …; } // namespace numbers /// floating_point_integral_constant /// /// Like std::integral_constant but for floating-point types holding integral /// values representable in an integral type. template <typename T, typename S, S Value> struct floating_point_integral_constant { … }; // ---- namespace detail { template <typename T> constexpr size_t constexpr_iterated_squares_desc_size_(T const base) { … } } // namespace detail /// constexpr_iterated_squares_desc_size_v /// /// Effectively calculates: floor(log(max_exponent)/log(base)) /// /// For use with constexpr_iterated_squares_desc below. constexpr_iterated_squares_desc_size_v; /// constexpr_iterated_squares_desc /// /// A constexpr scaling array of integer powers-of-powers-of-two, descending, /// with the associated powers-of-two. /// /// scaling = [..., {8, b^8}, {4, b^4}, {2, b^2}, {1, b^1}] for b = base /// /// Includes select constexpr scaling algorithms based on the scaling array. /// /// The scaling array and the scaling algorithms are general-purpose, if niche. /// They may be used by other constexpr math functions (floating-point) either /// to improve runtime performance or to improve numerical approximations. /// /// Some compilers fail to support passing some types as non-type template /// params. In particular, long double is not universally supported. Therefore, /// this utility takes its base as a type rather than as a value. For floating- /// point integral bases, that is, bases of floating-point type but of integral /// value, floating_point_integral_constant is the easiest parameterization. template <typename T, std::size_t Size> struct constexpr_iterated_squares_desc { … }; /// constexpr_iterated_squares_desc_v /// /// An instance of constexpr_iterated_squares_desc of max size with the given /// base. constexpr_iterated_squares_desc_v; /// constexpr_iterated_squares_desc_2_v /// /// An alias for constexpr_iterated_squares_desc_v with base 2, which is the /// most common base to use with iterated-squares. constexpr_iterated_squares_desc_2_v; // TLDR: Prefer using operator< for ordering. And when // a and b are equivalent objects, we return b to make // sorting stable. // See http://stepanovpapers.com/notes.pdf for details. template <typename T, typename... Ts> constexpr T constexpr_max(T a, Ts... ts) { … } // When a and b are equivalent objects, we return a to // make sorting stable. template <typename T, typename... Ts> constexpr T constexpr_min(T a, Ts... ts) { … } template <typename T, typename Less> constexpr T const& constexpr_clamp( T const& v, T const& lo, T const& hi, Less less) { … } template <typename T> constexpr T const& constexpr_clamp(T const& v, T const& lo, T const& hi) { … } template <typename T> constexpr bool constexpr_isnan(T const t) { … } namespace detail { template <typename T, typename = void> struct constexpr_abs_helper { … }; constexpr_abs_helper<T, typename std::enable_if<std::is_floating_point<T>::value>::type>; constexpr_abs_helper<T, typename std::enable_if<std::is_integral<T>::value && !std::is_same<T, bool>::value && std::is_unsigned<T>::value>::type>; constexpr_abs_helper<T, typename std::enable_if<std::is_integral<T>::value && !std::is_same<T, bool>::value && std::is_signed<T>::value>::type>; } // namespace detail template <typename T> constexpr auto constexpr_abs(T t) -> decltype(detail::constexpr_abs_helper<T>::go(t)) { … } namespace detail { template <typename T> constexpr T constexpr_log2_(T a, T e) { … } template <typename T> constexpr T constexpr_log2_ceil_(T l2, T t) { … } } // namespace detail template <typename T> constexpr T constexpr_log2(T t) { … } template <typename T> constexpr T constexpr_log2_ceil(T t) { … } /// constexpr_trunc /// /// mimic: std::trunc (C++23) template < typename T, std::enable_if_t<std::is_floating_point<T>::value, int> = 0> constexpr T constexpr_trunc(T const t) { … } template <typename T, std::enable_if_t<std::is_integral<T>::value, int> = 0> constexpr T constexpr_trunc(T const t) { … } /// constexpr_round /// /// mimic: std::round (C++23) template <typename T> constexpr T constexpr_round(T const t) { … } /// constexpr_floor /// /// mimic: std::floor (C++23) template <typename T> constexpr T constexpr_floor(T const t) { … } /// constexpr_ceil /// /// mimic: std::ceil (C++23) template <typename T> constexpr T constexpr_ceil(T const t) { … } /// constexpr_ceil /// /// The least integer at least t that round divides. template <typename T> constexpr T constexpr_ceil(T t, T round) { … } /// constexpr_mult /// /// Multiply two values, allowing for constexpr floating-pooint overflow to /// infinity. template <typename T> constexpr T constexpr_mult(T const a, T const b) { … } namespace detail { template < typename T, typename E, std::enable_if_t<std::is_signed<E>::value, int> = 1> constexpr T constexpr_ipow(T const base, E const exp) { … } template < typename T, typename E, std::enable_if_t<std::is_unsigned<E>::value, int> = 1> constexpr T constexpr_ipow(T const base, E const exp) { … } } // namespace detail /// constexpr_exp /// /// Calculates an approximation of the mathematical function exp(num). Usable in /// constant evaluations. Like std::exp, which becomes constexpr in C++26. /// /// The integer overload uses iterated squaring and multiplication. The /// floating-point overlaod naively evaluates the taylor series of exp(num) /// until approximate convergence. /// /// mimic: std::exp (C++23, C++26) template < typename T, typename N, std::enable_if_t< std::is_floating_point<T>::value && std::is_integral<N>::value && !std::is_same<N, bool>::value, int> = 0> constexpr T constexpr_exp(N const power) { … } template < typename N, std::enable_if_t< std::is_integral<N>::value && !std::is_same<N, bool>::value, int> = 0> constexpr double constexpr_exp(N const power) { … } template < typename T, std::enable_if_t<std::is_floating_point<T>::value, int> = 0> constexpr T constexpr_exp(T const power) { … } /// constexpr_log /// /// Calculates an approximation of the natural logarithm ln(num). /// /// The implementation uses a quickly-converging, high-precision iterative /// technique as described in: /// https://en.wikipedia.org/wiki/Natural_logarithm#High_precision /// /// The technique works best with numbers that are close enough to 1, so the /// implementation uses a quick shrink/growth technique as described in: /// https://en.wikipedia.org/wiki/Natural_logarithm#Efficient_computation template < typename T, std::enable_if_t<std::is_floating_point<T>::value, int> = 0> constexpr T constexpr_log(T const num) { … } /// constexpr_pow /// /// Calculates an approximation of the value of base raised to the exponent exp. /// /// The implementation uses iterated squaring and multiplication for the integer /// part of the exponent and uses the identity x^y = exp(y * log(x)) for the /// fractional part of the exponent. /// /// Notes: /// * Forbids base of +0 or -0 with finite non-positive exponent: in part since /// the plausible infinite result would be sensitive to the sign of the zero; /// and in part since std::pow would be required or permitted to raise error /// div-by-zero. /// * Forbids finite negative base with finite non-integer exponent: in part /// since std::pow would be required to raise error invalid. /// /// mimic: std::pow (C++26) template < typename T, typename E, std::enable_if_t< std::is_integral<E>::value && !std::is_same<E, bool>::value, int> = 0> constexpr T constexpr_pow(T const base, E const exp) { … } template < typename T, std::enable_if_t<std::is_floating_point<T>::value, int> = 0> constexpr T constexpr_pow(T const base, T const exp) { … } /// constexpr_find_last_set /// /// Return the 1-based index of the most significant bit which is set. /// For x > 0, constexpr_find_last_set(x) == 1 + floor(log2(x)). template <typename T> constexpr std::size_t constexpr_find_last_set(T const t) { … } namespace detail { template <typename U> constexpr std::size_t constexpr_find_first_set_( std::size_t s, std::size_t a, U const u) { … } } // namespace detail /// constexpr_find_first_set /// /// Return the 1-based index of the least significant bit which is set. /// For x > 0, the exponent in the largest power of two which does not divide x. template <typename T> constexpr std::size_t constexpr_find_first_set(T t) { … } template <typename T> constexpr T constexpr_add_overflow_clamped(T a, T b) { … } template <typename T> constexpr T constexpr_sub_overflow_clamped(T a, T b) { … } // clamp_cast<> provides sane numeric conversions from float point numbers to // integral numbers, and between different types of integral numbers. It helps // to avoid unexpected bugs introduced by bad conversion, and undefined behavior // like overflow when casting float point numbers to integral numbers. // // When doing clamp_cast<Dst>(value), if `value` is in valid range of Dst, // it will give correct result in Dst, equal to `value`. // // If `value` is outside the representable range of Dst, it will be clamped to // MAX or MIN in Dst, instead of being undefined behavior. // // Float NaNs are converted to 0 in integral type. // // Here's some comparison with static_cast<>: // (with FB-internal gcc-5-glibc-2.23 toolchain) // // static_cast<int32_t>(NaN) = 6 // clamp_cast<int32_t>(NaN) = 0 // // static_cast<int32_t>(9999999999.0f) = -348639895 // clamp_cast<int32_t>(9999999999.0f) = 2147483647 // // static_cast<int32_t>(2147483647.0f) = -348639895 // clamp_cast<int32_t>(2147483647.0f) = 2147483647 // // static_cast<uint32_t>(4294967295.0f) = 0 // clamp_cast<uint32_t>(4294967295.0f) = 4294967295 // // static_cast<uint32_t>(-1) = 4294967295 // clamp_cast<uint32_t>(-1) = 0 // // static_cast<int16_t>(32768u) = -32768 // clamp_cast<int16_t>(32768u) = 32767 template <typename Dst, typename Src> constexpr typename std::enable_if<std::is_integral<Src>::value, Dst>::type constexpr_clamp_cast(Src src) { … } namespace detail { // Upper/lower bound values that could be accurately represented in both // integral and float point types. constexpr double kClampCastLowerBoundDoubleToInt64F = …; constexpr double kClampCastUpperBoundDoubleToInt64F = …; constexpr double kClampCastUpperBoundDoubleToUInt64F = …; constexpr float kClampCastLowerBoundFloatToInt32F = …; constexpr float kClampCastUpperBoundFloatToInt32F = …; constexpr float kClampCastUpperBoundFloatToUInt32F = …; // This works the same as constexpr_clamp, but the comparison are done in Src // to prevent any implicit promotions. template <typename D, typename S> constexpr D constexpr_clamp_cast_helper(S src, S sl, S su, D dl, D du) { … } } // namespace detail template <typename Dst, typename Src> constexpr typename std::enable_if<std::is_floating_point<Src>::value, Dst>::type constexpr_clamp_cast(Src src) { … } } // namespace folly
Codebase Browser
folly