| // Copyright 2019 Google LLC | |
| // SPDX-License-Identifier: Apache-2.0 | |
| // | |
| // 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. | |
| #include <stddef.h> | |
| #include <stdint.h> | |
| #undef HWY_TARGET_INCLUDE | |
| #define HWY_TARGET_INCLUDE "tests/count_test.cc" | |
| #include "hwy/foreach_target.h" // IWYU pragma: keep | |
| #include "hwy/highway.h" | |
| #include "hwy/tests/test_util-inl.h" | |
| HWY_BEFORE_NAMESPACE(); | |
| namespace hwy { | |
| namespace HWY_NAMESPACE { | |
| namespace { | |
| struct TestPopulationCount { | |
| template <class T, class D> | |
| HWY_NOINLINE void operator()(T /*unused*/, D d) { | |
| RandomState rng; | |
| size_t N = Lanes(d); | |
| auto data = AllocateAligned<T>(N); | |
| auto popcnt = AllocateAligned<T>(N); | |
| HWY_ASSERT(data && popcnt); | |
| for (size_t i = 0; i < AdjustedReps(1 << 18) / N; i++) { | |
| for (size_t j = 0; j < N; j++) { | |
| data[j] = static_cast<T>(rng()); | |
| popcnt[j] = static_cast<T>(PopCount(data[j])); | |
| } | |
| HWY_ASSERT_VEC_EQ(d, popcnt.get(), PopulationCount(Load(d, data.get()))); | |
| } | |
| } | |
| }; | |
| HWY_NOINLINE void TestAllPopulationCount() { | |
| ForUnsignedTypes(ForPartialVectors<TestPopulationCount>()); | |
| } | |
| template <class T, HWY_IF_NOT_FLOAT_NOR_SPECIAL(T), HWY_IF_T_SIZE(T, 4)> | |
| static HWY_INLINE T LeadingZeroCountOfValue(T val) { | |
| const uint32_t u32_val = static_cast<uint32_t>(val); | |
| return static_cast<T>(u32_val ? Num0BitsAboveMS1Bit_Nonzero32(u32_val) : 32); | |
| } | |
| template <class T, HWY_IF_NOT_FLOAT_NOR_SPECIAL(T), HWY_IF_T_SIZE(T, 8)> | |
| static HWY_INLINE T LeadingZeroCountOfValue(T val) { | |
| const uint64_t u64_val = static_cast<uint64_t>(val); | |
| return static_cast<T>(u64_val ? Num0BitsAboveMS1Bit_Nonzero64(u64_val) : 64); | |
| } | |
| template <class T, HWY_IF_NOT_FLOAT_NOR_SPECIAL(T), | |
| HWY_IF_T_SIZE_ONE_OF(T, (1 << 1) | (1 << 2))> | |
| static HWY_INLINE T LeadingZeroCountOfValue(T val) { | |
| using TU = MakeUnsigned<T>; | |
| constexpr uint32_t kNumOfExtraLeadingZeros{32 - (sizeof(T) * 8)}; | |
| return static_cast<T>( | |
| LeadingZeroCountOfValue(static_cast<uint32_t>(static_cast<TU>(val))) - | |
| kNumOfExtraLeadingZeros); | |
| } | |
| struct TestLeadingZeroCount { | |
| template <class T, class D> | |
| HWY_ATTR_NO_MSAN HWY_NOINLINE void operator()(T /*unused*/, D d) { | |
| RandomState rng; | |
| using TU = MakeUnsigned<T>; | |
| const RebindToUnsigned<decltype(d)> du; | |
| size_t N = Lanes(d); | |
| auto data = AllocateAligned<T>(N); | |
| auto lzcnt = AllocateAligned<T>(N); | |
| HWY_ASSERT(data && lzcnt); | |
| constexpr T kNumOfBitsInT = static_cast<T>(sizeof(T) * 8); | |
| for (size_t j = 0; j < N; j++) { | |
| lzcnt[j] = kNumOfBitsInT; | |
| } | |
| HWY_ASSERT_VEC_EQ(d, lzcnt.get(), LeadingZeroCount(Zero(d))); | |
| for (size_t j = 0; j < N; j++) { | |
| lzcnt[j] = static_cast<T>(kNumOfBitsInT - 1); | |
| } | |
| HWY_ASSERT_VEC_EQ(d, lzcnt.get(), | |
| LeadingZeroCount(Set(d, static_cast<T>(1)))); | |
| for (size_t j = 0; j < N; j++) { | |
| lzcnt[j] = static_cast<T>(kNumOfBitsInT - 2); | |
| } | |
| HWY_ASSERT_VEC_EQ(d, lzcnt.get(), | |
| LeadingZeroCount(Set(d, static_cast<T>(2)))); | |
| for (size_t j = 0; j < N; j++) { | |
| lzcnt[j] = static_cast<T>(0); | |
| } | |
| HWY_ASSERT_VEC_EQ( | |
| d, lzcnt.get(), | |
| LeadingZeroCount(BitCast(d, Set(du, TU{1} << (kNumOfBitsInT - 1))))); | |
| for (size_t j = 0; j < N; j++) { | |
| lzcnt[j] = static_cast<T>(1); | |
| } | |
| HWY_ASSERT_VEC_EQ( | |
| d, lzcnt.get(), | |
| LeadingZeroCount(Set(d, static_cast<T>(1) << (kNumOfBitsInT - 2)))); | |
| for (size_t j = 0; j < N; j++) { | |
| lzcnt[j] = static_cast<T>(kNumOfBitsInT - 5); | |
| } | |
| HWY_ASSERT_VEC_EQ(d, lzcnt.get(), | |
| LeadingZeroCount(Set(d, static_cast<T>(0x1D)))); | |
| for (size_t i = 0; i < AdjustedReps(1000); i++) { | |
| for (size_t j = 0; j < N; j++) { | |
| data[j] = static_cast<T>(rng()); | |
| lzcnt[j] = LeadingZeroCountOfValue(data[j]); | |
| } | |
| HWY_ASSERT_VEC_EQ(d, lzcnt.get(), LeadingZeroCount(Load(d, data.get()))); | |
| } | |
| } | |
| }; | |
| HWY_NOINLINE void TestAllLeadingZeroCount() { | |
| ForIntegerTypes(ForPartialVectors<TestLeadingZeroCount>()); | |
| } | |
| struct TestMaskedLeadingZeroCount { | |
| template <class T, class D> | |
| HWY_ATTR_NO_MSAN HWY_NOINLINE void operator()(T /*unused*/, D d) { | |
| RandomState rng; | |
| using TU = MakeUnsigned<T>; | |
| const RebindToUnsigned<decltype(d)> du; | |
| size_t N = Lanes(d); | |
| const MFromD<D> first_3 = FirstN(d, 3); | |
| auto data = AllocateAligned<T>(N); | |
| auto lzcnt = AllocateAligned<T>(N); | |
| HWY_ASSERT(data && lzcnt); | |
| constexpr T kNumOfBitsInT = static_cast<T>(sizeof(T) * 8); | |
| for (size_t j = 0; j < N; j++) { | |
| if (j < 3) { | |
| lzcnt[j] = static_cast<T>(kNumOfBitsInT - 2); | |
| } else { | |
| lzcnt[j] = static_cast<T>(0); | |
| } | |
| } | |
| HWY_ASSERT_VEC_EQ( | |
| d, lzcnt.get(), | |
| MaskedLeadingZeroCount(first_3, Set(d, static_cast<T>(2)))); | |
| for (size_t j = 0; j < N; j++) { | |
| if (j < 3) { | |
| lzcnt[j] = static_cast<T>(1); | |
| } else { | |
| lzcnt[j] = static_cast<T>(0); | |
| } | |
| } | |
| HWY_ASSERT_VEC_EQ( | |
| d, lzcnt.get(), | |
| MaskedLeadingZeroCount( | |
| first_3, BitCast(d, Set(du, TU{1} << (kNumOfBitsInT - 2))))); | |
| } | |
| }; | |
| HWY_NOINLINE void TestAllMaskedLeadingZeroCount() { | |
| ForIntegerTypes(ForPartialVectors<TestMaskedLeadingZeroCount>()); | |
| } | |
| template <class T, HWY_IF_NOT_FLOAT_NOR_SPECIAL(T), | |
| HWY_IF_T_SIZE_ONE_OF(T, (1 << 1) | (1 << 2) | (1 << 4))> | |
| static HWY_INLINE T TrailingZeroCountOfValue(T val) { | |
| using TU = MakeUnsigned<T>; | |
| constexpr size_t kNumOfBitsInT = sizeof(T) * 8; | |
| const uint32_t u32_val = static_cast<uint32_t>(static_cast<TU>(val)); | |
| return static_cast<T>(u32_val ? Num0BitsBelowLS1Bit_Nonzero32(u32_val) | |
| : kNumOfBitsInT); | |
| } | |
| template <class T, HWY_IF_NOT_FLOAT_NOR_SPECIAL(T), HWY_IF_T_SIZE(T, 8)> | |
| static HWY_INLINE T TrailingZeroCountOfValue(T val) { | |
| const uint64_t u64_val = static_cast<uint64_t>(val); | |
| return static_cast<T>(u64_val ? Num0BitsBelowLS1Bit_Nonzero64(u64_val) : 64); | |
| } | |
| struct TestTrailingZeroCount { | |
| template <class T, class D> | |
| HWY_ATTR_NO_MSAN HWY_NOINLINE void operator()(T /*unused*/, D d) { | |
| RandomState rng; | |
| using TU = MakeUnsigned<T>; | |
| const RebindToUnsigned<decltype(d)> du; | |
| size_t N = Lanes(d); | |
| auto data = AllocateAligned<T>(N); | |
| auto tzcnt = AllocateAligned<T>(N); | |
| HWY_ASSERT(data && tzcnt); | |
| constexpr T kNumOfBitsInT = static_cast<T>(sizeof(T) * 8); | |
| for (size_t j = 0; j < N; j++) { | |
| tzcnt[j] = kNumOfBitsInT; | |
| } | |
| HWY_ASSERT_VEC_EQ(d, tzcnt.get(), TrailingZeroCount(Zero(d))); | |
| for (size_t j = 0; j < N; j++) { | |
| tzcnt[j] = static_cast<T>(0); | |
| } | |
| HWY_ASSERT_VEC_EQ(d, tzcnt.get(), | |
| TrailingZeroCount(Set(d, static_cast<T>(1)))); | |
| for (size_t j = 0; j < N; j++) { | |
| tzcnt[j] = static_cast<T>(1); | |
| } | |
| HWY_ASSERT_VEC_EQ(d, tzcnt.get(), | |
| TrailingZeroCount(Set(d, static_cast<T>(2)))); | |
| for (size_t j = 0; j < N; j++) { | |
| tzcnt[j] = static_cast<T>(kNumOfBitsInT - 1); | |
| } | |
| HWY_ASSERT_VEC_EQ( | |
| d, tzcnt.get(), | |
| TrailingZeroCount(BitCast(d, Set(du, TU{1} << (kNumOfBitsInT - 1))))); | |
| for (size_t j = 0; j < N; j++) { | |
| tzcnt[j] = static_cast<T>(kNumOfBitsInT - 2); | |
| } | |
| HWY_ASSERT_VEC_EQ( | |
| d, tzcnt.get(), | |
| TrailingZeroCount(Set(d, static_cast<T>(1) << (kNumOfBitsInT - 2)))); | |
| for (size_t j = 0; j < N; j++) { | |
| tzcnt[j] = static_cast<T>(3); | |
| } | |
| HWY_ASSERT_VEC_EQ(d, tzcnt.get(), | |
| TrailingZeroCount(Set(d, static_cast<T>(0x68)))); | |
| for (size_t i = 0; i < AdjustedReps(1000); i++) { | |
| for (size_t j = 0; j < N; j++) { | |
| data[j] = static_cast<T>(rng()); | |
| tzcnt[j] = TrailingZeroCountOfValue(data[j]); | |
| } | |
| HWY_ASSERT_VEC_EQ(d, tzcnt.get(), TrailingZeroCount(Load(d, data.get()))); | |
| } | |
| } | |
| }; | |
| HWY_NOINLINE void TestAllTrailingZeroCount() { | |
| ForIntegerTypes(ForPartialVectors<TestTrailingZeroCount>()); | |
| } | |
| class TestHighestSetBitIndex { | |
| private: | |
| template <class V> | |
| static HWY_INLINE V NormalizedHighestSetBitIndex(V v) { | |
| const DFromV<decltype(v)> d; | |
| const RebindToSigned<decltype(d)> di; | |
| const auto hsb_idx = BitCast(di, HighestSetBitIndex(v)); | |
| return BitCast(d, Or(BroadcastSignBit(hsb_idx), hsb_idx)); | |
| } | |
| public: | |
| template <class T, class D> | |
| HWY_ATTR_NO_MSAN HWY_NOINLINE void operator()(T /*unused*/, D d) { | |
| RandomState rng; | |
| using TU = MakeUnsigned<T>; | |
| const RebindToUnsigned<decltype(d)> du; | |
| size_t N = Lanes(d); | |
| auto data = AllocateAligned<T>(N); | |
| auto hsb_index = AllocateAligned<T>(N); | |
| HWY_ASSERT(data && hsb_index); | |
| constexpr T kNumOfBitsInT = static_cast<T>(sizeof(T) * 8); | |
| constexpr T kMsbIdx = static_cast<T>(kNumOfBitsInT - 1); | |
| for (size_t j = 0; j < N; j++) { | |
| hsb_index[j] = static_cast<T>(-1); | |
| } | |
| HWY_ASSERT_VEC_EQ(d, hsb_index.get(), | |
| NormalizedHighestSetBitIndex(Zero(d))); | |
| for (size_t j = 0; j < N; j++) { | |
| hsb_index[j] = static_cast<T>(0); | |
| } | |
| HWY_ASSERT_VEC_EQ(d, hsb_index.get(), | |
| NormalizedHighestSetBitIndex(Set(d, static_cast<T>(1)))); | |
| for (size_t j = 0; j < N; j++) { | |
| hsb_index[j] = static_cast<T>(1); | |
| } | |
| HWY_ASSERT_VEC_EQ(d, hsb_index.get(), | |
| NormalizedHighestSetBitIndex(Set(d, static_cast<T>(3)))); | |
| for (size_t j = 0; j < N; j++) { | |
| hsb_index[j] = static_cast<T>(kNumOfBitsInT - 1); | |
| } | |
| HWY_ASSERT_VEC_EQ(d, hsb_index.get(), | |
| NormalizedHighestSetBitIndex( | |
| BitCast(d, Set(du, TU{1} << (kNumOfBitsInT - 1))))); | |
| for (size_t j = 0; j < N; j++) { | |
| hsb_index[j] = static_cast<T>(kNumOfBitsInT - 2); | |
| } | |
| HWY_ASSERT_VEC_EQ(d, hsb_index.get(), | |
| NormalizedHighestSetBitIndex( | |
| Set(d, static_cast<T>(1) << (kNumOfBitsInT - 2)))); | |
| for (size_t j = 0; j < N; j++) { | |
| hsb_index[j] = static_cast<T>(5); | |
| } | |
| HWY_ASSERT_VEC_EQ( | |
| d, hsb_index.get(), | |
| NormalizedHighestSetBitIndex(Set(d, static_cast<T>(0x2B)))); | |
| for (size_t i = 0; i < AdjustedReps(1000); i++) { | |
| for (size_t j = 0; j < N; j++) { | |
| data[j] = static_cast<T>(rng()); | |
| hsb_index[j] = | |
| static_cast<T>(kMsbIdx - LeadingZeroCountOfValue(data[j])); | |
| } | |
| HWY_ASSERT_VEC_EQ(d, hsb_index.get(), | |
| NormalizedHighestSetBitIndex(Load(d, data.get()))); | |
| } | |
| } | |
| }; | |
| HWY_NOINLINE void TestAllHighestSetBitIndex() { | |
| ForIntegerTypes(ForPartialVectors<TestHighestSetBitIndex>()); | |
| } | |
| } // namespace | |
| // NOLINTNEXTLINE(google-readability-namespace-comments) | |
| } // namespace HWY_NAMESPACE | |
| } // namespace hwy | |
| HWY_AFTER_NAMESPACE(); | |
| #if HWY_ONCE | |
| namespace hwy { | |
| namespace { | |
| HWY_BEFORE_TEST(HwyCountTest); | |
| HWY_EXPORT_AND_TEST_P(HwyCountTest, TestAllPopulationCount); | |
| HWY_EXPORT_AND_TEST_P(HwyCountTest, TestAllLeadingZeroCount); | |
| HWY_EXPORT_AND_TEST_P(HwyCountTest, TestAllMaskedLeadingZeroCount); | |
| HWY_EXPORT_AND_TEST_P(HwyCountTest, TestAllTrailingZeroCount); | |
| HWY_EXPORT_AND_TEST_P(HwyCountTest, TestAllHighestSetBitIndex); | |
| HWY_AFTER_TEST(); | |
| } // namespace | |
| } // namespace hwy | |
| HWY_TEST_MAIN(); | |
| #endif // HWY_ONCE |