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
