Module: Mesa Branch: main Commit: 16ab9343f3b716437a7eafd1bd1712785357afe3 URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=16ab9343f3b716437a7eafd1bd1712785357afe3
Author: Jason Ekstrand <[email protected]> Date: Fri Apr 15 16:44:47 2022 -0500 util/bitset: Support larger ranges in BITSET_TEST/CLEAR_RANGE Reviewed-by: Karol Herbst <[email protected]> Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/15988> --- src/util/bitset.h | 42 ++++++++++++++++++++++++++++++++++++++++-- src/util/tests/bitset_test.cpp | 39 +++++++++++++++++++++++++++++++-------- 2 files changed, 71 insertions(+), 10 deletions(-) diff --git a/src/util/bitset.h b/src/util/bitset.h index d8ec1af67ad..c1a3848f78d 100644 --- a/src/util/bitset.h +++ b/src/util/bitset.h @@ -192,7 +192,7 @@ __bitset_shl(BITSET_WORD *x, unsigned amount, unsigned n) /* bit range operations */ -#define BITSET_TEST_RANGE(x, b, e) \ +#define BITSET_TEST_RANGE_INSIDE_WORD(x, b, e) \ (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \ (((x)[BITSET_BITWORD(b)] & BITSET_RANGE(b, e)) != 0) : \ (assert (!"BITSET_TEST_RANGE: bit range crosses word boundary"), 0)) @@ -200,11 +200,30 @@ __bitset_shl(BITSET_WORD *x, unsigned amount, unsigned n) (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \ ((x)[BITSET_BITWORD(b)] |= BITSET_RANGE(b, e)) : \ (assert (!"BITSET_SET_RANGE_INSIDE_WORD: bit range crosses word boundary"), 0)) -#define BITSET_CLEAR_RANGE(x, b, e) \ +#define BITSET_CLEAR_RANGE_INSIDE_WORD(x, b, e) \ (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \ ((x)[BITSET_BITWORD(b)] &= ~BITSET_RANGE(b, e)) : \ (assert (!"BITSET_CLEAR_RANGE: bit range crosses word boundary"), 0)) +static inline bool +__bitset_test_range(BITSET_WORD *r, unsigned start, unsigned end) +{ + const unsigned size = end - start + 1; + const unsigned start_mod = start % BITSET_WORDBITS; + + if (start_mod + size <= BITSET_WORDBITS) { + return BITSET_TEST_RANGE_INSIDE_WORD(r, start, end); + } else { + const unsigned first_size = BITSET_WORDBITS - start_mod; + + return __bitset_test_range(r, start, start + first_size - 1) || + __bitset_test_range(r, start + first_size, end); + } +} + +#define BITSET_TEST_RANGE(x, b, e) \ + __bitset_test_range(x, b, e) + static inline void __bitset_set_range(BITSET_WORD *r, unsigned start, unsigned end) { @@ -224,6 +243,25 @@ __bitset_set_range(BITSET_WORD *r, unsigned start, unsigned end) #define BITSET_SET_RANGE(x, b, e) \ __bitset_set_range(x, b, e) +static inline void +__bitclear_clear_range(BITSET_WORD *r, unsigned start, unsigned end) +{ + const unsigned size = end - start + 1; + const unsigned start_mod = start % BITSET_WORDBITS; + + if (start_mod + size <= BITSET_WORDBITS) { + BITSET_CLEAR_RANGE_INSIDE_WORD(r, start, end); + } else { + const unsigned first_size = BITSET_WORDBITS - start_mod; + + __bitclear_clear_range(r, start, start + first_size - 1); + __bitclear_clear_range(r, start + first_size, end); + } +} + +#define BITSET_CLEAR_RANGE(x, b, e) \ + __bitclear_clear_range(x, b, e) + static inline unsigned __bitset_prefix_sum(const BITSET_WORD *x, unsigned b, unsigned n) { diff --git a/src/util/tests/bitset_test.cpp b/src/util/tests/bitset_test.cpp index 9fb9daa1538..ec3ba5104ab 100644 --- a/src/util/tests/bitset_test.cpp +++ b/src/util/tests/bitset_test.cpp @@ -74,8 +74,8 @@ TEST(bitset, test_basic_range) const int max_set = 15; BITSET_SET_RANGE_INSIDE_WORD(mask128, 0, max_set); - EXPECT_EQ(BITSET_TEST_RANGE(mask128, 0, max_set), true); - EXPECT_EQ(BITSET_TEST_RANGE(mask128, max_set + 1, max_set + 15), false); + EXPECT_EQ(BITSET_TEST_RANGE_INSIDE_WORD(mask128, 0, max_set), true); + EXPECT_EQ(BITSET_TEST_RANGE_INSIDE_WORD(mask128, max_set + 1, max_set + 15), false); for (int i = 0; i < 128; i++) { if (i <= max_set) EXPECT_EQ(BITSET_TEST(mask128, i), true); @@ -83,7 +83,7 @@ TEST(bitset, test_basic_range) EXPECT_EQ(BITSET_TEST(mask128, i), false); } BITSET_CLEAR_RANGE(mask128, 0, max_set); - EXPECT_EQ(BITSET_TEST_RANGE(mask128, 0, max_set), false); + EXPECT_EQ(BITSET_TEST_RANGE_INSIDE_WORD(mask128, 0, max_set), false); for (int i = 0; i < 128; i++) { EXPECT_EQ(BITSET_TEST(mask128, i), false); } @@ -118,14 +118,37 @@ TEST(bitset, test_range_bits) BITSET_SET_RANGE_INSIDE_WORD(mask128, 32, 63); BITSET_SET_RANGE_INSIDE_WORD(mask128, 64, 95); BITSET_SET_RANGE_INSIDE_WORD(mask128, 96, 127); - - EXPECT_EQ(BITSET_TEST_RANGE(mask128, 0, 31), true); - EXPECT_EQ(BITSET_TEST_RANGE(mask128, 32, 63), true); - EXPECT_EQ(BITSET_TEST_RANGE(mask128, 64, 95), true); - EXPECT_EQ(BITSET_TEST_RANGE(mask128, 96, 127), true); for (int i = 0; i < 128; i++) { EXPECT_EQ(BITSET_TEST(mask128, i), true); } + + BITSET_ZERO(mask128); + BITSET_SET_RANGE(mask128, 20, 80); + for (int i = 0; i <= 19; i++) + EXPECT_EQ(BITSET_TEST(mask128, i), false); + for (int i = 20; i <= 80; i++) + EXPECT_EQ(BITSET_TEST(mask128, i), true); + for (int i = 81; i <= 127; i++) + EXPECT_EQ(BITSET_TEST(mask128, i), false); + + BITSET_ZERO(mask128); + BITSET_SET(mask128, 20); + BITSET_SET(mask128, 80); + EXPECT_EQ(BITSET_TEST_RANGE(mask128, 0, 128), true); + EXPECT_EQ(BITSET_TEST_RANGE(mask128, 0, 19), false); + EXPECT_EQ(BITSET_TEST_RANGE(mask128, 21, 79), false); + EXPECT_EQ(BITSET_TEST_RANGE(mask128, 81, 127), false); + EXPECT_EQ(BITSET_TEST_RANGE(mask128, 0, 79), true); + EXPECT_EQ(BITSET_TEST_RANGE(mask128, 21, 128), true); + + BITSET_ONES(mask128); + BITSET_CLEAR_RANGE(mask128, 20, 80); + for (int i = 0; i <= 19; i++) + EXPECT_EQ(BITSET_TEST(mask128, i), true); + for (int i = 20; i <= 80; i++) + EXPECT_EQ(BITSET_TEST(mask128, i), false); + for (int i = 81; i <= 127; i++) + EXPECT_EQ(BITSET_TEST(mask128, i), true); } TEST(bitset, test_and)
