diff --git a/libc/src/__support/CMakeLists.txt b/libc/src/__support/CMakeLists.txt --- a/libc/src/__support/CMakeLists.txt +++ b/libc/src/__support/CMakeLists.txt @@ -15,6 +15,12 @@ ctype_utils.h ) +add_header_library( + find_leading_one + HDRS + find_leading_one.h +) + add_header_library( high_precision_decimal HDRS diff --git a/libc/src/__support/FPUtil/CMakeLists.txt b/libc/src/__support/FPUtil/CMakeLists.txt --- a/libc/src/__support/FPUtil/CMakeLists.txt +++ b/libc/src/__support/FPUtil/CMakeLists.txt @@ -15,10 +15,12 @@ PolyEval.h UInt.h XFloat.h + Hypot.h DEPENDS libc.include.math libc.include.errno libc.include.fenv libc.src.__support.common + libc.src.__support.find_leading_one libc.src.__support.CPP.standalone_cpp ) diff --git a/libc/src/__support/FPUtil/Hypot.h b/libc/src/__support/FPUtil/Hypot.h --- a/libc/src/__support/FPUtil/Hypot.h +++ b/libc/src/__support/FPUtil/Hypot.h @@ -12,48 +12,11 @@ #include "BasicOperations.h" #include "FPBits.h" #include "src/__support/CPP/TypeTraits.h" +#include "src/__support/find_leading_one.h" namespace __llvm_libc { namespace fputil { -namespace internal { - -template -static inline T find_leading_one(T mant, int &shift_length); - -template <> -inline uint32_t find_leading_one(uint32_t mant, int &shift_length) { - shift_length = 0; - constexpr int NSTEPS = 5; - constexpr uint32_t BOUNDS[NSTEPS] = {1 << 16, 1 << 8, 1 << 4, 1 << 2, 1 << 1}; - constexpr int SHIFTS[NSTEPS] = {16, 8, 4, 2, 1}; - for (int i = 0; i < NSTEPS; ++i) { - if (mant >= BOUNDS[i]) { - shift_length += SHIFTS[i]; - mant >>= SHIFTS[i]; - } - } - return 1U << shift_length; -} - -template <> -inline uint64_t find_leading_one(uint64_t mant, int &shift_length) { - shift_length = 0; - constexpr int NSTEPS = 6; - constexpr uint64_t BOUNDS[NSTEPS] = {1ULL << 32, 1ULL << 16, 1ULL << 8, - 1ULL << 4, 1ULL << 2, 1ULL << 1}; - constexpr int SHIFTS[NSTEPS] = {32, 16, 8, 4, 2, 1}; - for (int i = 0; i < NSTEPS; ++i) { - if (mant >= BOUNDS[i]) { - shift_length += SHIFTS[i]; - mant >>= SHIFTS[i]; - } - } - return 1ULL << shift_length; -} - -} // namespace internal - template struct DoubleLength; template <> struct DoubleLength { using Type = uint32_t; }; @@ -178,7 +141,8 @@ a_mant |= ONE; y_mant_width = MantissaWidth::VALUE + 1; } else { - leading_one = internal::find_leading_one(a_mant, y_mant_width); + y_mant_width = __llvm_libc::internal::find_leading_one(a_mant); + leading_one = UIntType(1) << y_mant_width; a_exp = 1; } diff --git a/libc/src/__support/find_leading_one.h b/libc/src/__support/find_leading_one.h new file mode 100644 --- /dev/null +++ b/libc/src/__support/find_leading_one.h @@ -0,0 +1,32 @@ +//===-- Utility for finding position of leading 1 in integer ----*- C++ -*-===// +// +// 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 LLVM_LIBC_SRC_SUPPORT_FIND_LEADING_ONE_H +#define LLVM_LIBC_SRC_SUPPORT_FIND_LEADING_ONE_H + +#include "src/__support/architectures.h" + +namespace __llvm_libc { +namespace internal { +/// Finds the position of the most-significant 1 bit in the given integer. +/// +/// \param value the integer to scan. Should be a positive number. +/// +/// \returns the position of the bit as an offset from the LSB (e.g., passing +// 0b0101 would return 2). Returns 0 on domain error (e.g., if 0 is passed). +template static inline int find_leading_one(T value); +} // namespace internal +} // namespace __llvm_libc + +#if defined(LLVM_LIBC_ARCH_X86_64) +#include "src/__support/x86_64/find_leading_one.h" +#else +#include "src/__support/generic/find_leading_one.h" +#endif + +#endif // LLVM_LIBC_SRC_SUPPORT_FIND_LEADING_ONE_H diff --git a/libc/src/__support/generic/find_leading_one.h b/libc/src/__support/generic/find_leading_one.h new file mode 100644 --- /dev/null +++ b/libc/src/__support/generic/find_leading_one.h @@ -0,0 +1,46 @@ +//===-- Utility for finding position of leading 1 in integer ----*- C++ -*-===// +// +// 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 LLVM_LIBC_SRC_SUPPORT_GENERIC_FIND_LEADING_ONE_H +#define LLVM_LIBC_SRC_SUPPORT_GENERIC_FIND_LEADING_ONE_H + +#include "src/__support/CPP/TypeTraits.h" +#include + +template <> +inline int __llvm_libc::internal::find_leading_one(uint32_t value) { + int shift_length = 0; + constexpr int NSTEPS = 5; + constexpr uint32_t BOUNDS[NSTEPS] = {1 << 16, 1 << 8, 1 << 4, 1 << 2, 1 << 1}; + constexpr int SHIFTS[NSTEPS] = {16, 8, 4, 2, 1}; + for (int i = 0; i < NSTEPS; ++i) { + if (value >= BOUNDS[i]) { + shift_length += SHIFTS[i]; + value >>= SHIFTS[i]; + } + } + return shift_length; +} + +template <> +inline int __llvm_libc::internal::find_leading_one(uint64_t value) { + int shift_length = 0; + constexpr int NSTEPS = 6; + constexpr uint64_t BOUNDS[NSTEPS] = {1ULL << 32, 1ULL << 16, 1ULL << 8, + 1ULL << 4, 1ULL << 2, 1ULL << 1}; + constexpr int SHIFTS[NSTEPS] = {32, 16, 8, 4, 2, 1}; + for (int i = 0; i < NSTEPS; ++i) { + if (value >= BOUNDS[i]) { + shift_length += SHIFTS[i]; + value >>= SHIFTS[i]; + } + } + return shift_length; +} + +#endif // LLVM_LIBC_SRC_SUPPORT_GENERIC_FIND_LEADING_ONE_H diff --git a/libc/src/__support/x86_64/find_leading_one.h b/libc/src/__support/x86_64/find_leading_one.h new file mode 100644 --- /dev/null +++ b/libc/src/__support/x86_64/find_leading_one.h @@ -0,0 +1,36 @@ +//===-- Utility for finding position of leading 1 in integer ----*- C++ -*-===// +// +// 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 LLVM_LIBC_SRC_SUPPORT_X86_64_FIND_LEADING_ONE_H +#define LLVM_LIBC_SRC_SUPPORT_X86_64_FIND_LEADING_ONE_H + +#include "src/__support/CPP/TypeTraits.h" +#include + +#if !defined(LLVM_LIBC_ARCH_X86_64) +#error Must be LLVM_LIBC_ARCH_X86_64 to include this file +#endif + +template +inline int __llvm_libc::internal::find_leading_one(T value) { + static_assert( + cpp::IsSame::Value || cpp::IsSame::Value, ""); + + if (value == 0) { + return 0; + } + + __asm__("bsr %[value], %[value]" + : [value] "=r"(value) + : "0"(value) + : "flags"); // Clobbers ZF + + return static_cast(value); +} + +#endif // LLVM_LIBC_SRC_SUPPORT_X86_64_FIND_LEADING_ONE_H diff --git a/libc/test/src/__support/CMakeLists.txt b/libc/test/src/__support/CMakeLists.txt --- a/libc/test/src/__support/CMakeLists.txt +++ b/libc/test/src/__support/CMakeLists.txt @@ -10,6 +10,16 @@ libc.src.__support.common ) +add_libc_unittest( + find_leading_one_test + SUITE + libc_support_unittests + SRCS + find_leading_one_test.cpp + DEPENDS + libc.src.__support.find_leading_one +) + add_libc_unittest( high_precision_decimal_test SUITE diff --git a/libc/test/src/__support/find_leading_one_test.cpp b/libc/test/src/__support/find_leading_one_test.cpp new file mode 100644 --- /dev/null +++ b/libc/test/src/__support/find_leading_one_test.cpp @@ -0,0 +1,44 @@ +//===-- Unittests for find_leading_one ------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#include "src/__support/find_leading_one.h" +#include "utils/UnitTest/Test.h" +#include + +namespace __llvm_libc { + +struct LlvmLibcFindLeadingOne : testing::Test { + template void exhaustive_test() { + for (std::size_t i = 0; i < sizeof(T) * CHAR_BIT; i++) { + const T value = static_cast(1ULL << i); + EXPECT_EQ(internal::find_leading_one(value), static_cast(i)); + } + } +}; + +TEST_F(LlvmLibcFindLeadingOne, Zero) { + EXPECT_EQ(internal::find_leading_one(0U), 0); +} + +TEST_F(LlvmLibcFindLeadingOne, One) { + EXPECT_EQ(internal::find_leading_one(1U), 0); +} + +TEST_F(LlvmLibcFindLeadingOne, Two) { + EXPECT_EQ(internal::find_leading_one(2U), 1); +} + +TEST_F(LlvmLibcFindLeadingOne, Three) { + EXPECT_EQ(internal::find_leading_one(3U), 1); +} + +TEST_F(LlvmLibcFindLeadingOne, Exhaustive32Bit) { exhaustive_test(); } + +TEST_F(LlvmLibcFindLeadingOne, Exhaustive64Bit) { exhaustive_test(); } + +} // namespace __llvm_libc