From d3d0ecbfd52cca2c7e0f4478e5682c493fd99ef2 Mon Sep 17 00:00:00 2001 From: Marshall Clow Date: Thu, 25 Apr 2019 12:11:43 +0000 Subject: [PATCH] Implement midpoint for floating point types. Reviewed as https://reviews.llvm.org/D61014. llvm-svn: 359184 --- libcxx/docs/FeatureTestMacroTable.rst | 2 + libcxx/include/numeric | 20 +++- libcxx/include/version | 2 + .../numeric.version.pass.cpp | 20 ++++ .../version.version.pass.cpp | 20 ++++ .../numeric.ops.midpoint/midpoint.float.pass.cpp | 113 +++++++++++++++++++++ libcxx/test/support/fp_compare.h | 46 +++++++++ .../generate_feature_test_macro_components.py | 6 ++ 8 files changed, 228 insertions(+), 1 deletion(-) create mode 100644 libcxx/test/std/numerics/numeric.ops/numeric.ops.midpoint/midpoint.float.pass.cpp create mode 100644 libcxx/test/support/fp_compare.h diff --git a/libcxx/docs/FeatureTestMacroTable.rst b/libcxx/docs/FeatureTestMacroTable.rst index 4d3b079..0748c4c 100644 --- a/libcxx/docs/FeatureTestMacroTable.rst +++ b/libcxx/docs/FeatureTestMacroTable.rst @@ -188,6 +188,8 @@ Status ------------------------------------------------- ----------------- ``__cpp_lib_generic_unordered_lookup`` *unimplemented* ------------------------------------------------- ----------------- + ``__cpp_lib_interpolate`` ``201902L`` + ------------------------------------------------- ----------------- ``__cpp_lib_is_constant_evaluated`` ``201811L`` ------------------------------------------------- ----------------- ``__cpp_lib_list_remove_return_type`` *unimplemented* diff --git a/libcxx/include/numeric b/libcxx/include/numeric index 8d159af..6be6080 100644 --- a/libcxx/include/numeric +++ b/libcxx/include/numeric @@ -145,6 +145,7 @@ floating_point midpoint(floating_point a, floating_point b); // C++20 #include #include // for numeric_limits #include +#include // for isnormal #include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -552,7 +553,24 @@ midpoint(_TPtr __a, _TPtr __b) noexcept { return __a + _VSTD::midpoint(ptrdiff_t(0), __b - __a); } -#endif + + +template +int __sign(_Tp __val) { + return (_Tp(0) < __val) - (__val < _Tp(0)); +} + +template +_LIBCPP_INLINE_VISIBILITY constexpr +enable_if_t, _Fp> +midpoint(_Fp __a, _Fp __b) noexcept +{ + return isnormal(__a) && isnormal(__b) + && ((__sign(__a) != __sign(__b)) || ((numeric_limits<_Fp>::max() - abs(__a)) < abs(__b))) + ? __a / 2 + __b / 2 + : (__a + __b) / 2; +} +#endif // _LIBCPP_STD_VER > 17 _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/version b/libcxx/include/version index 948f645..102da67 100644 --- a/libcxx/include/version +++ b/libcxx/include/version @@ -58,6 +58,7 @@ __cpp_lib_hypot 201603L __cpp_lib_incomplete_container_elements 201505L __cpp_lib_integer_sequence 201304L __cpp_lib_integral_constant_callable 201304L +__cpp_lib_interpolate 201902L __cpp_lib_invoke 201411L __cpp_lib_is_aggregate 201703L __cpp_lib_is_constant_evaluated 201811L @@ -222,6 +223,7 @@ __cpp_lib_void_t 201411L // # define __cpp_lib_destroying_delete 201806L # define __cpp_lib_erase_if 201811L // # define __cpp_lib_generic_unordered_lookup 201811L +# define __cpp_lib_interpolate 201902L # if !defined(_LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED) # define __cpp_lib_is_constant_evaluated 201811L # endif diff --git a/libcxx/test/std/language.support/support.limits/support.limits.general/numeric.version.pass.cpp b/libcxx/test/std/language.support/support.limits/support.limits.general/numeric.version.pass.cpp index eb5eb55..c43d717 100644 --- a/libcxx/test/std/language.support/support.limits/support.limits.general/numeric.version.pass.cpp +++ b/libcxx/test/std/language.support/support.limits/support.limits.general/numeric.version.pass.cpp @@ -15,6 +15,7 @@ /* Constant Value __cpp_lib_gcd_lcm 201606L [C++17] + __cpp_lib_interpolate 201902L [C++2a] __cpp_lib_parallel_algorithm 201603L [C++17] */ @@ -27,6 +28,10 @@ # error "__cpp_lib_gcd_lcm should not be defined before c++17" # endif +# ifdef __cpp_lib_interpolate +# error "__cpp_lib_interpolate should not be defined before c++2a" +# endif + # ifdef __cpp_lib_parallel_algorithm # error "__cpp_lib_parallel_algorithm should not be defined before c++17" # endif @@ -37,6 +42,10 @@ # error "__cpp_lib_gcd_lcm should not be defined before c++17" # endif +# ifdef __cpp_lib_interpolate +# error "__cpp_lib_interpolate should not be defined before c++2a" +# endif + # ifdef __cpp_lib_parallel_algorithm # error "__cpp_lib_parallel_algorithm should not be defined before c++17" # endif @@ -50,6 +59,10 @@ # error "__cpp_lib_gcd_lcm should have the value 201606L in c++17" # endif +# ifdef __cpp_lib_interpolate +# error "__cpp_lib_interpolate should not be defined before c++2a" +# endif + # if !defined(_LIBCPP_VERSION) # ifndef __cpp_lib_parallel_algorithm # error "__cpp_lib_parallel_algorithm should be defined in c++17" @@ -72,6 +85,13 @@ # error "__cpp_lib_gcd_lcm should have the value 201606L in c++2a" # endif +# ifndef __cpp_lib_interpolate +# error "__cpp_lib_interpolate should be defined in c++2a" +# endif +# if __cpp_lib_interpolate != 201902L +# error "__cpp_lib_interpolate should have the value 201902L in c++2a" +# endif + # if !defined(_LIBCPP_VERSION) # ifndef __cpp_lib_parallel_algorithm # error "__cpp_lib_parallel_algorithm should be defined in c++2a" diff --git a/libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp b/libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp index 7735a13..0ed0a51 100644 --- a/libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp +++ b/libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp @@ -50,6 +50,7 @@ __cpp_lib_incomplete_container_elements 201505L [C++17] __cpp_lib_integer_sequence 201304L [C++14] __cpp_lib_integral_constant_callable 201304L [C++14] + __cpp_lib_interpolate 201902L [C++2a] __cpp_lib_invoke 201411L [C++17] __cpp_lib_is_aggregate 201703L [C++17] __cpp_lib_is_constant_evaluated 201811L [C++2a] @@ -248,6 +249,10 @@ # error "__cpp_lib_integral_constant_callable should not be defined before c++14" # endif +# ifdef __cpp_lib_interpolate +# error "__cpp_lib_interpolate should not be defined before c++2a" +# endif + # ifdef __cpp_lib_invoke # error "__cpp_lib_invoke should not be defined before c++17" # endif @@ -596,6 +601,10 @@ # error "__cpp_lib_integral_constant_callable should have the value 201304L in c++14" # endif +# ifdef __cpp_lib_interpolate +# error "__cpp_lib_interpolate should not be defined before c++2a" +# endif + # ifdef __cpp_lib_invoke # error "__cpp_lib_invoke should not be defined before c++17" # endif @@ -1082,6 +1091,10 @@ # error "__cpp_lib_integral_constant_callable should have the value 201304L in c++17" # endif +# ifdef __cpp_lib_interpolate +# error "__cpp_lib_interpolate should not be defined before c++2a" +# endif + # ifndef __cpp_lib_invoke # error "__cpp_lib_invoke should be defined in c++17" # endif @@ -1778,6 +1791,13 @@ # error "__cpp_lib_integral_constant_callable should have the value 201304L in c++2a" # endif +# ifndef __cpp_lib_interpolate +# error "__cpp_lib_interpolate should be defined in c++2a" +# endif +# if __cpp_lib_interpolate != 201902L +# error "__cpp_lib_interpolate should have the value 201902L in c++2a" +# endif + # ifndef __cpp_lib_invoke # error "__cpp_lib_invoke should be defined in c++2a" # endif diff --git a/libcxx/test/std/numerics/numeric.ops/numeric.ops.midpoint/midpoint.float.pass.cpp b/libcxx/test/std/numerics/numeric.ops/numeric.ops.midpoint/midpoint.float.pass.cpp new file mode 100644 index 0000000..4abb232 --- /dev/null +++ b/libcxx/test/std/numerics/numeric.ops/numeric.ops.midpoint/midpoint.float.pass.cpp @@ -0,0 +1,113 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17 +// + +// template +// _Tp midpoint(_Float __a, _Float __b) noexcept +// + +#include +#include + +#include "test_macros.h" +#include "fp_compare.h" + +// Totally arbitrary picks for precision +template +constexpr T fp_error_pct(); + +template <> +constexpr float fp_error_pct() { return 1.0e-4f; } + +template <> +constexpr double fp_error_pct() { return 1.0e-12; } + +template <> +constexpr long double fp_error_pct() { return 1.0e-13l; } + + +template +void fp_test() +{ + ASSERT_SAME_TYPE(T, decltype(std::midpoint(T(), T()))); + ASSERT_NOEXCEPT( std::midpoint(T(), T())); + + constexpr T maxV = std::numeric_limits::max(); + constexpr T minV = std::numeric_limits::min(); + +// Things that can be compared exactly + assert((std::midpoint(T(0), T(0)) == T(0))); + assert((std::midpoint(T(2), T(4)) == T(3))); + assert((std::midpoint(T(4), T(2)) == T(3))); + assert((std::midpoint(T(3), T(4)) == T(3.5))); + assert((std::midpoint(T(0), T(0.4)) == T(0.2))); + +// Things that can't be compared exactly + constexpr T pct = fp_error_pct(); + assert((fptest_close_pct(std::midpoint(T( 1.3), T(11.4)), T( 6.35), pct))); + assert((fptest_close_pct(std::midpoint(T(11.33), T(31.45)), T(21.39), pct))); + assert((fptest_close_pct(std::midpoint(T(-1.3), T(11.4)), T( 5.05), pct))); + assert((fptest_close_pct(std::midpoint(T(11.4), T(-1.3)), T( 5.05), pct))); + assert((fptest_close_pct(std::midpoint(T(0.1), T(0.4)), T(0.25), pct))); + + assert((fptest_close_pct(std::midpoint(T(11.2345), T(14.5432)), T(12.88885), pct))); + +// From e to pi + assert((fptest_close_pct(std::midpoint(T(2.71828182845904523536028747135266249775724709369995), + T(3.14159265358979323846264338327950288419716939937510)), + T(2.92993724102441923691146542731608269097720824653752), pct))); + + assert((fptest_close_pct(std::midpoint(maxV, T(0)), maxV/2, pct))); + assert((fptest_close_pct(std::midpoint(T(0), maxV), maxV/2, pct))); + assert((fptest_close_pct(std::midpoint(minV, T(0)), minV/2, pct))); + assert((fptest_close_pct(std::midpoint(T(0), minV), minV/2, pct))); + assert((fptest_close_pct(std::midpoint(maxV, maxV), maxV, pct))); + assert((fptest_close_pct(std::midpoint(minV, minV), minV, pct))); + +// Denormalized values +// TODO + +// Check two values "close to each other" + T d1 = 3.14; + T d0 = std::nexttoward(d1, T(2)); + T d2 = std::nexttoward(d1, T(5)); + assert(d0 < d1); // sanity checking + assert(d1 < d2); // sanity checking + +// Since there's nothing in between, the midpoint has to be one or the other + T res; + res = std::midpoint(d0, d1); + assert(res == d0 || res == d1); + assert(d0 <= res); + assert(res <= d1); + res = std::midpoint(d1, d0); + assert(res == d0 || res == d1); + assert(d0 <= res); + assert(res <= d1); + + res = std::midpoint(d1, d2); + assert(res == d1 || res == d2); + assert(d1 <= res); + assert(res <= d2); + res = std::midpoint(d2, d1); + assert(res == d1 || res == d2); + assert(d1 <= res); + assert(res <= d2); +} + + +int main (int, char**) +{ + fp_test(); + fp_test(); + fp_test(); + + return 0; +} diff --git a/libcxx/test/support/fp_compare.h b/libcxx/test/support/fp_compare.h new file mode 100644 index 0000000..f14ea96 --- /dev/null +++ b/libcxx/test/support/fp_compare.h @@ -0,0 +1,46 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +#ifndef SUPPORT_FP_COMPARE_H +#define SUPPORT_FP_COMPARE_H + +#include // for std::abs +#include // for std::max +#include + +// See https://www.boost.org/doc/libs/1_70_0/libs/test/doc/html/boost_test/testing_tools/extended_comparison/floating_point/floating_points_comparison_theory.html + +template +bool fptest_close(T val, T expected, T eps) +{ + constexpr T zero = T(0); + assert(eps >= zero); + +// Handle the zero cases + if (eps == zero) return val == expected; + if (val == zero) return std::abs(expected) <= eps; + if (expected == zero) return std::abs(val) <= eps; + + return std::abs(val - expected) < eps + && std::abs(val - expected)/std::abs(val) < eps; +} + +template +bool fptest_close_pct(T val, T expected, T percent) +{ + constexpr T zero = T(0); + assert(percent >= zero); + +// Handle the zero cases + if (percent == zero) return val == expected; + T eps = (percent / T(100)) * std::max(std::abs(val), std::abs(expected)); + + return fptest_close(val, expected, eps); +} + + +#endif // SUPPORT_FP_COMPARE_H diff --git a/libcxx/utils/generate_feature_test_macro_components.py b/libcxx/utils/generate_feature_test_macro_components.py index ed01587..f5e770d 100755 --- a/libcxx/utils/generate_feature_test_macro_components.py +++ b/libcxx/utils/generate_feature_test_macro_components.py @@ -565,6 +565,12 @@ feature_test_macros = sorted([ add_version_header(x) for x in [ "depends": "!defined(_LIBCPP_HAS_NO_THREADS)", "internal_depends": "!defined(_LIBCPP_HAS_NO_THREADS)", }, + {"name": "__cpp_lib_interpolate", + "values": { + "c++2a": 201902L, + }, + "headers": ["numeric"], + }, ]], key=lambda tc: tc["name"]) def get_std_dialects(): -- 2.7.4