Add BitSetRangeIterator Add a new iterator for Dawn BitSet. The iterator defines "range". "range" means continuous set bits and represents with [offset, size] pair. The new iterator iterate between ranges and could help immediate data states tracker to do state tracking. Bug:366291600 Change-Id: Iffbac0a2d1393eab22b2c289d84c966915cc8b18 Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/231754 Commit-Queue: Shaobo Yan <shaoboyan@microsoft.com> Reviewed-by: Corentin Wallez <cwallez@chromium.org> Reviewed-by: Geoff Lang <geofflang@chromium.org>
diff --git a/src/dawn/common/BUILD.gn b/src/dawn/common/BUILD.gn index 357c9a2..39decd6 100644 --- a/src/dawn/common/BUILD.gn +++ b/src/dawn/common/BUILD.gn
@@ -264,6 +264,7 @@ "Alloc.h", "Assert.cpp", "Assert.h", + "BitSetRangeIterator.h", "Compiler.h", "Constants.h", "ContentLessObjectCache.h",
diff --git a/src/dawn/common/BitSetRangeIterator.h b/src/dawn/common/BitSetRangeIterator.h new file mode 100644 index 0000000..6447751 --- /dev/null +++ b/src/dawn/common/BitSetRangeIterator.h
@@ -0,0 +1,176 @@ +// Copyright 2025 The Dawn & Tint Authors +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are met: +// +// 1. Redistributions of source code must retain the above copyright notice, this +// list of conditions and the following disclaimer. +// +// 2. Redistributions in binary form must reproduce the above copyright notice, +// this list of conditions and the following disclaimer in the documentation +// and/or other materials provided with the distribution. +// +// 3. Neither the name of the copyright holder nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE +// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#ifndef SRC_DAWN_COMMON_BITSETRANGEITERATOR_H_ +#define SRC_DAWN_COMMON_BITSETRANGEITERATOR_H_ + +#include <bitset> +#include <limits> +#include <utility> + +#include "dawn/common/Assert.h" +#include "dawn/common/Math.h" +#include "dawn/common/UnderlyingType.h" + +namespace dawn { + +// Similar to BitSetIterator but returns ranges of consecutive bits as (offset, size) pairs +// TODO(crbug.com/366291600): // Specialization for bitset size fits in uint64_t to skip +// loops for bits across words boundary. +template <size_t N, typename T> +class BitSetRangeIterator final { + public: + explicit BitSetRangeIterator(const std::bitset<N>& bitset); + BitSetRangeIterator(const BitSetRangeIterator& other); + BitSetRangeIterator& operator=(const BitSetRangeIterator& other); + + class Iterator final { + public: + explicit Iterator(const std::bitset<N>& bits, uint32_t offset = 0, uint32_t size = 0); + Iterator& operator++(); + + bool operator==(const Iterator& other) const; + bool operator!=(const Iterator& other) const; + + // Returns a pair of offset and size of the current range + std::pair<T, size_t> operator*() const { + using U = UnderlyingType<T>; + DAWN_ASSERT(static_cast<U>(mOffset) <= std::numeric_limits<U>::max()); + DAWN_ASSERT(static_cast<size_t>(mSize) <= std::numeric_limits<size_t>::max()); + return std::make_pair(static_cast<T>(static_cast<U>(mOffset)), + static_cast<size_t>(mSize)); + } + + private: + void Advance(); + size_t ScanForwardAndShiftBits(); + + static constexpr size_t kBitsPerWord = sizeof(uint64_t) * 8; + std::bitset<N> mBits; + uint32_t mOffset{0}; + uint32_t mSize{0}; + }; + + Iterator begin() const { return Iterator(mBits); } + Iterator end() const { return Iterator(std::bitset<N>(0), N, 0); } + + private: + const std::bitset<N> mBits; +}; + +template <size_t N, typename T> +BitSetRangeIterator<N, T>::BitSetRangeIterator(const std::bitset<N>& bitset) : mBits(bitset) {} + +template <size_t N, typename T> +BitSetRangeIterator<N, T>::BitSetRangeIterator(const BitSetRangeIterator& other) + : mBits(other.mBits) {} + +template <size_t N, typename T> +BitSetRangeIterator<N, T>& BitSetRangeIterator<N, T>::operator=(const BitSetRangeIterator& other) { + mBits = other.mBits; + return *this; +} + +template <size_t N, typename T> +BitSetRangeIterator<N, T>::Iterator::Iterator(const std::bitset<N>& bits, + uint32_t offset, + uint32_t size) + : mBits(bits), mOffset(offset), mSize(size) { + Advance(); +} + +template <size_t N, typename T> +typename BitSetRangeIterator<N, T>::Iterator& BitSetRangeIterator<N, T>::Iterator::operator++() { + Advance(); + return *this; +} + +template <size_t N, typename T> +bool BitSetRangeIterator<N, T>::Iterator::operator==(const Iterator& other) const { + return mOffset == other.mOffset && mSize == other.mSize && mBits == other.mBits; +} + +template <size_t N, typename T> +bool BitSetRangeIterator<N, T>::Iterator::operator!=(const Iterator& other) const { + return !(*this == other); +} + +template <size_t N, typename T> +size_t BitSetRangeIterator<N, T>::Iterator::ScanForwardAndShiftBits() { + if (mBits.none()) { + return N; // Or some other indicator that there are no bits. + } + + constexpr std::bitset<N> wordMask(std::numeric_limits<uint64_t>::max()); + size_t offset = 0; + while ((mBits & wordMask).to_ullong() == 0) { + offset += kBitsPerWord; + mBits >>= kBitsPerWord; + } + + size_t nextBit = ScanForward(static_cast<uint64_t>((mBits & wordMask).to_ullong())); + mBits >>= nextBit; + return offset + nextBit; +} + +template <size_t N, typename T> +void BitSetRangeIterator<N, T>::Iterator::Advance() { + // Bits are currently shifted to mOffset + mSize. + mOffset += mSize; + + size_t rangeStart = ScanForwardAndShiftBits(); + if (rangeStart == N) { + // Reached the end, no more ranges. + mOffset = N; + mSize = 0; + return; + } + + mOffset += rangeStart; + mBits = ~mBits; + + size_t rangeCount = ScanForwardAndShiftBits(); + if (rangeCount == N) { + // All bits until the end of the set are set. + rangeCount = N - mOffset; + } + + mSize = rangeCount; + mBits = ~mBits; + mBits <<= mOffset; + mBits >>= mOffset; +} + +// Helper to avoid needing to specify the template parameter size +template <size_t N> +BitSetRangeIterator<N, uint32_t> IterateBitSetRanges(const std::bitset<N>& bitset) { + return BitSetRangeIterator<N, uint32_t>(bitset); +} + +} // namespace dawn + +#endif // SRC_DAWN_COMMON_BITSETRANGEITERATOR_H_
diff --git a/src/dawn/common/CMakeLists.txt b/src/dawn/common/CMakeLists.txt index 56e4aa12..3965ffc 100644 --- a/src/dawn/common/CMakeLists.txt +++ b/src/dawn/common/CMakeLists.txt
@@ -48,6 +48,7 @@ "AlignedAlloc.h" "Alloc.h" "Assert.h" + "BitSetRangeIterator.h" "Compiler.h" "Constants.h" "ContentLessObjectCache.h"
diff --git a/src/dawn/tests/BUILD.gn b/src/dawn/tests/BUILD.gn index fbee698..9cde65f 100644 --- a/src/dawn/tests/BUILD.gn +++ b/src/dawn/tests/BUILD.gn
@@ -319,6 +319,7 @@ "DawnNativeTest.cpp", "DawnNativeTest.h", "unittests/AsyncTaskTests.cpp", + "unittests/BitSetRangeIteratorTests.cpp", "unittests/BuddyAllocatorTests.cpp", "unittests/BuddyMemoryAllocatorTests.cpp", "unittests/ChainUtilsTests.cpp",
diff --git a/src/dawn/tests/unittests/BitSetRangeIteratorTests.cpp b/src/dawn/tests/unittests/BitSetRangeIteratorTests.cpp new file mode 100644 index 0000000..b64cf68 --- /dev/null +++ b/src/dawn/tests/unittests/BitSetRangeIteratorTests.cpp
@@ -0,0 +1,221 @@ +// Copyright 2025 The Dawn & Tint Authors +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are met: +// +// 1. Redistributions of source code must retain the above copyright notice, this +// list of conditions and the following disclaimer. +// +// 2. Redistributions in binary form must reproduce the above copyright notice, +// this list of conditions and the following disclaimer in the documentation +// and/or other materials provided with the distribution. +// +// 3. Neither the name of the copyright holder nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE +// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include <set> +#include <utility> +#include <vector> + +#include "dawn/common/BitSetRangeIterator.h" +#include "gtest/gtest.h" + +namespace dawn { +namespace { + +class BitSetRangeIteratorTest : public testing::Test { + protected: + template <size_t N> + void RunSingleBitRangesTests() { + std::bitset<N> stateBits; + uint32_t bitSize = stateBits.size(); + + std::vector<std::pair<uint32_t, size_t>> expectedRanges; + expectedRanges.push_back({bitSize / 4u * 3u, 1}); + + for (const auto& range : expectedRanges) { + stateBits.set(range.first); + } + + std::vector<std::pair<uint32_t, size_t>> foundRanges; + for (auto range : IterateBitSetRanges(stateBits)) { + foundRanges.push_back(range); + } + + EXPECT_EQ(expectedRanges.size(), foundRanges.size()); + for (size_t i = 0; i < expectedRanges.size(); ++i) { + EXPECT_EQ(expectedRanges[i].first, foundRanges[i].first); + EXPECT_EQ(expectedRanges[i].second, foundRanges[i].second); + } + } + + template <size_t N> + void RunConsecutiveBitRangesTests() { + std::bitset<N> stateBits; + uint32_t bitSize = stateBits.size(); + // Ensure range no overlapping + DAWN_ASSERT(bitSize >= 14); + + std::vector<std::pair<uint32_t, size_t>> expectedRanges; + expectedRanges.push_back({2, 3}); + expectedRanges.push_back({bitSize / 2, 2}); + expectedRanges.push_back({bitSize / 2 + 3, 4}); + + for (const auto& range : expectedRanges) { + for (uint32_t i = 0; i < range.second; ++i) { + stateBits.set(range.first + i); + } + } + + std::vector<std::pair<uint32_t, size_t>> foundRanges; + for (auto range : IterateBitSetRanges(stateBits)) { + foundRanges.push_back(range); + } + + EXPECT_EQ(expectedRanges.size(), foundRanges.size()); + for (size_t i = 0; i < expectedRanges.size(); ++i) { + EXPECT_EQ(expectedRanges[i].first, foundRanges[i].first); + EXPECT_EQ(expectedRanges[i].second, foundRanges[i].second); + } + } + + template <size_t N> + void RunNonLValueBitset() { + std::bitset<N> stateBits; + std::bitset<N> otherBits; + + uint32_t halfBitSize = stateBits.size() / 2; + DAWN_ASSERT(halfBitSize >= 3); + + std::vector<std::pair<uint32_t, size_t>> expectedRanges; + expectedRanges.push_back({halfBitSize - 2, 2}); + expectedRanges.push_back({halfBitSize + 1, 1}); + + // Set up consecutive bits + stateBits.set(halfBitSize - 2); + stateBits.set(halfBitSize - 1); + stateBits.set(halfBitSize); + stateBits.set(halfBitSize + 1); + + // Set up second bitset with overlapping and non-overlapping bits + otherBits.set(halfBitSize - 3); + otherBits.set(halfBitSize - 2); + otherBits.set(halfBitSize - 1); + otherBits.set(halfBitSize + 1); + otherBits.set(halfBitSize + 2); + + std::vector<std::pair<uint32_t, size_t>> foundRanges; + for (auto range : IterateBitSetRanges(stateBits & otherBits)) { + foundRanges.push_back(range); + + // Verify all bits in the range are set in both bitsets + for (uint32_t i = 0; i < range.second; ++i) { + EXPECT_TRUE(stateBits[range.first + i]); + EXPECT_TRUE(otherBits[range.first + i]); + } + } + + EXPECT_EQ(expectedRanges.size(), foundRanges.size()); + for (size_t i = 0; i < expectedRanges.size(); ++i) { + EXPECT_EQ(expectedRanges[i].first, foundRanges[i].first); + EXPECT_EQ(expectedRanges[i].second, foundRanges[i].second); + } + } + + // Same value as BitSetRangeIterator. + static constexpr size_t kBitsPerWord = sizeof(uint64_t) * 8; +}; + +// Test basic range iteration with single bits (each range has size 1) +TEST_F(BitSetRangeIteratorTest, SingleBitRanges) { + // Smaller than 1 word + { + RunSingleBitRangesTests<kBitsPerWord - 1>(); + } + + // Equal to 1 word + { + RunSingleBitRangesTests<kBitsPerWord>(); + } + + // Larger than 1 word + { + RunSingleBitRangesTests<kBitsPerWord * 2 - 1>(); + } +} + +// Test ranges with consecutive bits +TEST_F(BitSetRangeIteratorTest, ConsecutiveBitRanges) { + // Smaller than 1 word + { + RunConsecutiveBitRangesTests<kBitsPerWord - 1>(); + } + + // Equal to 1 word + { + RunConsecutiveBitRangesTests<kBitsPerWord>(); + } + + // Larger than 1 word + { + RunConsecutiveBitRangesTests<kBitsPerWord * 2 - 1>(); + } +} + +// Test an empty iterator +TEST_F(BitSetRangeIteratorTest, EmptySet) { + std::bitset<kBitsPerWord> stateBits; + auto iterator = IterateBitSetRanges(stateBits); + EXPECT_EQ(iterator.end(), iterator.begin()); +} + +// Test iterating a result of combining two bitsets +TEST_F(BitSetRangeIteratorTest, NonLValueBitset) { + // Smaller than 1 word + { + RunNonLValueBitset<kBitsPerWord - 1>(); + } + + // Equal to 1 word + { + RunNonLValueBitset<kBitsPerWord>(); + } + + // Larger than 1 word + { + RunNonLValueBitset<kBitsPerWord * 2 - 1>(); + } +} + +// Test ranges that cross word boundaries +TEST_F(BitSetRangeIteratorTest, CrossWordBoundaryRanges) { + std::bitset<kBitsPerWord * 2> stateBits; + // Set a range that crosses bit word boundary + for (uint32_t i = kBitsPerWord - 2; i <= kBitsPerWord + 1; ++i) { + stateBits.set(i); + } + + std::vector<std::pair<uint32_t, size_t>> foundRanges; + for (auto range : IterateBitSetRanges(stateBits)) { + foundRanges.push_back(range); + } + + EXPECT_EQ(1u, foundRanges.size()); + EXPECT_EQ(kBitsPerWord - 2, foundRanges[0].first); + EXPECT_EQ(4u, foundRanges[0].second); +} + +} // anonymous namespace +} // namespace dawn
diff --git a/src/dawn/tests/unittests/MathTests.cpp b/src/dawn/tests/unittests/MathTests.cpp index a3cb746..063b93b 100644 --- a/src/dawn/tests/unittests/MathTests.cpp +++ b/src/dawn/tests/unittests/MathTests.cpp
@@ -432,20 +432,20 @@ // Tests for RoundUp TEST(Math, RoundUp) { - ASSERT_EQ(RoundUp(2, 2), 2u); - ASSERT_EQ(RoundUp(2, 4), 4u); - ASSERT_EQ(RoundUp(6, 2), 6u); - ASSERT_EQ(RoundUp(8, 4), 8u); - ASSERT_EQ(RoundUp(12, 6), 12u); + ASSERT_EQ(RoundUp(2u, 2u), 2u); + ASSERT_EQ(RoundUp(2u, 4u), 4u); + ASSERT_EQ(RoundUp(6u, 2u), 6u); + ASSERT_EQ(RoundUp(8u, 4u), 8u); + ASSERT_EQ(RoundUp(12u, 6u), 12u); - ASSERT_EQ(RoundUp(3, 3), 3u); - ASSERT_EQ(RoundUp(3, 5), 5u); - ASSERT_EQ(RoundUp(5, 3), 6u); - ASSERT_EQ(RoundUp(9, 5), 10u); + ASSERT_EQ(RoundUp(3u, 3u), 3u); + ASSERT_EQ(RoundUp(3u, 5u), 5u); + ASSERT_EQ(RoundUp(5u, 3u), 6u); + ASSERT_EQ(RoundUp(9u, 5u), 10u); // Test extrema ASSERT_EQ(RoundUp(0x7FFFFFFFFFFFFFFFull, 0x8000000000000000ull), 0x8000000000000000ull); - ASSERT_EQ(RoundUp(1, 1), 1u); + ASSERT_EQ(RoundUp(1u, 1u), 1u); } // Tests for IsSubset