This is an automated email from the ASF dual-hosted git repository. joemcdonnell pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/impala.git
commit 5b0864d7b4a52169f9225f51caf1cfbac6272da2 Author: Daniel Becker <[email protected]> AuthorDate: Mon Apr 24 11:51:59 2023 +0200 IMPALA-12086: Fix BitUtil::CountLeadingZeros for zero BitUtil::CountLeadingZeros() uses _builtin_clz() and _builtin_clzll() to return the number of leading zeros in a number. Calling these functions with 0 is undefined. This change introduces a check in CountLeadingZeros() to only call these functions if the argument is non-zero. Also makes CountLeadingZeros() constexpr and restricts it to type sizes that can actually be handled by the function. Testing: - Added a test for CountLeadingZeros() in bit-util-test.cc Change-Id: I0ae3d84c5c25871388155747f91c51162c1a0590 Reviewed-on: http://gerrit.cloudera.org:8080/19792 Reviewed-by: Impala Public Jenkins <[email protected]> Tested-by: Impala Public Jenkins <[email protected]> --- be/src/util/arithmetic-util.h | 6 ++++++ be/src/util/bit-util-test.cc | 39 +++++++++++++++++++++++++++++++++++++++ be/src/util/bit-util.h | 10 ++++++++-- 3 files changed, 53 insertions(+), 2 deletions(-) diff --git a/be/src/util/arithmetic-util.h b/be/src/util/arithmetic-util.h index ca7d3b196..928a67fcc 100644 --- a/be/src/util/arithmetic-util.h +++ b/be/src/util/arithmetic-util.h @@ -35,6 +35,12 @@ struct MakeUnsigned<__int128_t> { using type = __uint128_t; }; +// std::make_unsigned<>() also works for unsigned types and returns the same type. +template <> +struct MakeUnsigned< __uint128_t> { + using type = __uint128_t; +}; + template <typename T> using UnsignedType = typename MakeUnsigned<T>::type; diff --git a/be/src/util/bit-util-test.cc b/be/src/util/bit-util-test.cc index d1707a8d4..3793671e4 100644 --- a/be/src/util/bit-util-test.cc +++ b/be/src/util/bit-util-test.cc @@ -22,6 +22,7 @@ #include <algorithm> #include <iostream> #include <numeric> +#include <type_traits> #include <boost/utility.hpp> @@ -255,6 +256,44 @@ TEST(BitUtil, ByteSwap) { for (int i = 0; i <= 32; ++i) TestByteSwapSimd(0, i); } +template <class INT_T> +void TestCountLeadingZeros() { + constexpr int BITWIDTH = sizeof(INT_T) * 8; + using UINT_T = typename MakeUnsigned<INT_T>::type; + // Unsigned constant 1 with bit width of BITWIDTH. + constexpr UINT_T ONE = 1; + + // Test 0. + EXPECT_EQ(BITWIDTH, BitUtil::CountLeadingZeros<INT_T>(0)); + + // Test 1. + EXPECT_EQ(BITWIDTH - 1, BitUtil::CountLeadingZeros<INT_T>(ONE)); + + for (int i = 2; i < BITWIDTH - 1; ++i) { + INT_T smallest_with_bit_width = ONE << (i - 1); + EXPECT_EQ(BITWIDTH - i, BitUtil::CountLeadingZeros(smallest_with_bit_width)); + + INT_T largest_with_bit_width = (ONE << i) - 1; + EXPECT_EQ(BITWIDTH - i, BitUtil::CountLeadingZeros(largest_with_bit_width)); + } + + // Test max value for unsigned int types - for signed types they are negative which we + // don't allow. + if (std::is_same_v<INT_T, UINT_T>) { + UINT_T max = std::numeric_limits<UINT_T>::max(); + EXPECT_EQ(0, BitUtil::CountLeadingZeros(max)); + } +} + +TEST(BitUtil, CountLeadingZeros) { + TestCountLeadingZeros<int32_t>(); + TestCountLeadingZeros<uint32_t>(); + TestCountLeadingZeros<int64_t>(); + TestCountLeadingZeros<uint64_t>(); + TestCountLeadingZeros<__int128>(); + TestCountLeadingZeros<unsigned __int128>(); +} + TEST(BitUtil, Log2) { EXPECT_EQ(BitUtil::Log2CeilingNonZero64(1), 0); EXPECT_EQ(BitUtil::Log2CeilingNonZero64(2), 1); diff --git a/be/src/util/bit-util.h b/be/src/util/bit-util.h index b81388031..1a5efe95c 100644 --- a/be/src/util/bit-util.h +++ b/be/src/util/bit-util.h @@ -304,8 +304,15 @@ class BitUtil { } template<typename T> - static inline int CountLeadingZeros(T v) { + static constexpr inline int CountLeadingZeros(T v) { + static_assert(sizeof(T) == 4 || sizeof(T) == 8 || sizeof(T) == 16); DCHECK(v >= 0); + + // __builtin_clz() and __builtin_clzll() is undefined for 0. + if (UNLIKELY(v == 0)) { + return sizeof(T) * CHAR_BIT; + } + if (sizeof(T) == 4) { uint32_t orig = static_cast<uint32_t>(v); return __builtin_clz(orig); @@ -314,7 +321,6 @@ class BitUtil { return __builtin_clzll(orig); } else { DCHECK(sizeof(T) == 16); - if (UNLIKELY(v == 0)) return 128; unsigned __int128 orig = static_cast<unsigned __int128>(v); unsigned __int128 shifted = orig >> 64; if (shifted != 0) {
