blob: 23160177c9095c4ecb12f8efb2b8e2c1edd56744 [file] [log] [blame]
//
// Copyright 2015 The ANGLE Project Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// bitset_utils_unittest:
// Tests bitset helpers and custom classes.
//
#include <array>
#include <gtest/gtest.h>
#include "common/bitset_utils.h"
using namespace angle;
namespace
{
template <typename T>
class BitSetTest : public testing::Test
{
protected:
T mBits;
typedef T BitSet;
};
using BitSetTypes = ::testing::Types<BitSet<12>, BitSet32<12>, BitSet64<12>>;
TYPED_TEST_SUITE(BitSetTest, BitSetTypes);
TYPED_TEST(BitSetTest, Basic)
{
EXPECT_EQ(TypeParam::Zero().bits(), 0u);
TypeParam mBits = this->mBits;
EXPECT_FALSE(mBits.all());
EXPECT_FALSE(mBits.any());
EXPECT_TRUE(mBits.none());
EXPECT_EQ(mBits.count(), 0u);
// Set every bit to 1.
for (size_t i = 0; i < mBits.size(); ++i)
{
mBits.set(i);
EXPECT_EQ(mBits.all(), i + 1 == mBits.size());
EXPECT_TRUE(mBits.any());
EXPECT_FALSE(mBits.none());
EXPECT_EQ(mBits.count(), i + 1);
}
// Reset every other bit to 0.
for (size_t i = 0; i < mBits.size(); i += 2)
{
mBits.reset(i);
EXPECT_FALSE(mBits.all());
EXPECT_TRUE(mBits.any());
EXPECT_FALSE(mBits.none());
EXPECT_EQ(mBits.count(), mBits.size() - i / 2 - 1);
}
// Flip all bits.
for (size_t i = 0; i < mBits.size(); ++i)
{
mBits.flip(i);
EXPECT_FALSE(mBits.all());
EXPECT_TRUE(mBits.any());
EXPECT_FALSE(mBits.none());
EXPECT_EQ(mBits.count(), mBits.size() / 2 + (i % 2 == 0));
}
// Make sure the bit pattern is what we expect at this point.
for (size_t i = 0; i < mBits.size(); ++i)
{
EXPECT_EQ(mBits.test(i), i % 2 == 0);
EXPECT_EQ(static_cast<bool>(mBits[i]), i % 2 == 0);
}
// Test that flip, set and reset all bits at once work.
mBits.flip();
EXPECT_FALSE(mBits.all());
EXPECT_TRUE(mBits.any());
EXPECT_FALSE(mBits.none());
EXPECT_EQ(mBits.count(), mBits.size() / 2);
EXPECT_EQ(mBits.first(), 1u);
mBits.set();
EXPECT_TRUE(mBits.all());
EXPECT_TRUE(mBits.any());
EXPECT_FALSE(mBits.none());
EXPECT_EQ(mBits.count(), mBits.size());
EXPECT_EQ(mBits.first(), 0u);
mBits.reset();
EXPECT_FALSE(mBits.all());
EXPECT_FALSE(mBits.any());
EXPECT_TRUE(mBits.none());
EXPECT_EQ(mBits.count(), 0u);
// Test that out-of-bound sets don't modify the bitset
constexpr uint32_t kMask = (1 << 12) - 1;
EXPECT_EQ(mBits.set(12).bits() & ~kMask, 0u);
EXPECT_EQ(mBits.set(13).bits() & ~kMask, 0u);
EXPECT_EQ(mBits.flip(12).bits() & ~kMask, 0u);
EXPECT_EQ(mBits.flip(13).bits() & ~kMask, 0u);
}
TYPED_TEST(BitSetTest, BitwiseOperators)
{
TypeParam mBits = this->mBits;
// Use a value that has a 1 in the 12th and 13th bits, to make sure masking to exactly 12 bits
// does not have an off-by-one error.
constexpr uint32_t kSelfValue = 0xF9E4;
constexpr uint32_t kOtherValue = 0x5C6A;
constexpr uint32_t kMask = (1 << 12) - 1;
constexpr uint32_t kSelfMaskedValue = kSelfValue & kMask;
constexpr uint32_t kOtherMaskedValue = kOtherValue & kMask;
constexpr uint32_t kShift = 3;
constexpr uint32_t kSelfShiftedLeft = kSelfMaskedValue << kShift & kMask;
constexpr uint32_t kSelfShiftedRight = kSelfMaskedValue >> kShift & kMask;
mBits |= kSelfValue;
typename TestFixture::BitSet other(kOtherValue);
typename TestFixture::BitSet anded(kSelfMaskedValue & kOtherMaskedValue);
typename TestFixture::BitSet ored(kSelfMaskedValue | kOtherMaskedValue);
typename TestFixture::BitSet xored(kSelfMaskedValue ^ kOtherMaskedValue);
EXPECT_EQ(mBits.bits(), kSelfMaskedValue);
EXPECT_EQ(other.bits(), kOtherMaskedValue);
EXPECT_EQ(mBits & other, anded);
EXPECT_EQ(mBits | other, ored);
EXPECT_EQ(mBits ^ other, xored);
EXPECT_NE(mBits, other);
EXPECT_NE(anded, ored);
EXPECT_NE(anded, xored);
EXPECT_NE(ored, xored);
mBits &= other;
EXPECT_EQ(mBits, anded);
mBits |= ored;
EXPECT_EQ(mBits, ored);
mBits ^= other;
mBits ^= anded;
EXPECT_EQ(mBits, typename TestFixture::BitSet(kSelfValue));
EXPECT_EQ(mBits << kShift, typename TestFixture::BitSet(kSelfShiftedLeft));
EXPECT_EQ(mBits >> kShift, typename TestFixture::BitSet(kSelfShiftedRight));
mBits <<= kShift;
EXPECT_EQ(mBits, typename TestFixture::BitSet(kSelfShiftedLeft));
EXPECT_EQ(mBits.bits() & ~kMask, 0u);
mBits = typename TestFixture::BitSet(kSelfValue);
mBits >>= kShift;
EXPECT_EQ(mBits, typename TestFixture::BitSet(kSelfShiftedRight));
EXPECT_EQ(mBits.bits() & ~kMask, 0u);
mBits |= kSelfMaskedValue;
EXPECT_EQ(mBits.bits() & ~kMask, 0u);
mBits ^= kOtherMaskedValue;
EXPECT_EQ(mBits.bits() & ~kMask, 0u);
}
template <typename T>
class BitSetIteratorTest : public testing::Test
{
protected:
T mStateBits;
typedef T BitSet;
};
using BitSetIteratorTypes = ::testing::Types<BitSet<40>, BitSet64<40>>;
TYPED_TEST_SUITE(BitSetIteratorTest, BitSetIteratorTypes);
// Simple iterator test.
TYPED_TEST(BitSetIteratorTest, Iterator)
{
TypeParam mStateBits = this->mStateBits;
std::set<size_t> originalValues;
originalValues.insert(2);
originalValues.insert(6);
originalValues.insert(8);
originalValues.insert(35);
for (size_t value : originalValues)
{
mStateBits.set(value);
}
std::set<size_t> readValues;
for (size_t bit : mStateBits)
{
EXPECT_EQ(1u, originalValues.count(bit));
EXPECT_EQ(0u, readValues.count(bit));
readValues.insert(bit);
}
EXPECT_EQ(originalValues.size(), readValues.size());
}
// Ensure lsb->msb iteration order.
TYPED_TEST(BitSetIteratorTest, IterationOrder)
{
TypeParam mStateBits = this->mStateBits;
const std::array<size_t, 8> writeOrder = {20, 25, 16, 31, 10, 14, 36, 19};
const std::array<size_t, 8> fetchOrder = {10, 14, 16, 19, 20, 25, 31, 36};
for (size_t value : writeOrder)
{
mStateBits.set(value);
}
EXPECT_EQ(writeOrder.size(), mStateBits.count());
size_t i = 0;
for (size_t bit : mStateBits)
{
EXPECT_EQ(fetchOrder[i], bit);
i++;
}
EXPECT_EQ(fetchOrder.size(), mStateBits.count());
}
// Test an empty iterator.
TYPED_TEST(BitSetIteratorTest, EmptySet)
{
TypeParam mStateBits = this->mStateBits;
// We don't use the FAIL gtest macro here since it returns immediately,
// causing an unreachable code warning in MSVS
bool sawBit = false;
for (size_t bit : mStateBits)
{
sawBit = true;
ANGLE_UNUSED_VARIABLE(bit);
}
EXPECT_FALSE(sawBit);
}
// Test iterating a result of combining two bitsets.
TYPED_TEST(BitSetIteratorTest, NonLValueBitset)
{
TypeParam mStateBits = this->mStateBits;
typename TestFixture::BitSet otherBits;
mStateBits.set(1);
mStateBits.set(2);
mStateBits.set(3);
mStateBits.set(4);
otherBits.set(0);
otherBits.set(1);
otherBits.set(3);
otherBits.set(5);
std::set<size_t> seenBits;
typename TestFixture::BitSet maskedBits = (mStateBits & otherBits);
for (size_t bit : maskedBits)
{
EXPECT_EQ(0u, seenBits.count(bit));
seenBits.insert(bit);
EXPECT_TRUE(mStateBits[bit]);
EXPECT_TRUE(otherBits[bit]);
}
EXPECT_EQ((mStateBits & otherBits).count(), seenBits.size());
}
// Test bit assignments.
TYPED_TEST(BitSetIteratorTest, BitAssignment)
{
TypeParam mStateBits = this->mStateBits;
std::set<size_t> originalValues;
originalValues.insert(2);
originalValues.insert(6);
originalValues.insert(8);
originalValues.insert(35);
for (size_t value : originalValues)
{
(mStateBits[value] = false) = true;
}
for (size_t value : originalValues)
{
EXPECT_TRUE(mStateBits.test(value));
}
}
// Tests adding bits to the iterator during iteration.
TYPED_TEST(BitSetIteratorTest, SetLaterBit)
{
TypeParam mStateBits = this->mStateBits;
std::set<size_t> expectedValues = {0, 1, 3, 5, 6, 7, 9, 35};
mStateBits.set(0);
mStateBits.set(1);
std::set<size_t> actualValues;
for (auto iter = mStateBits.begin(), end = mStateBits.end(); iter != end; ++iter)
{
if (*iter == 1)
{
iter.setLaterBit(3);
iter.setLaterBit(5);
}
if (*iter == 5)
{
iter.setLaterBit(6);
iter.setLaterBit(7);
iter.setLaterBit(9);
iter.setLaterBit(35);
}
actualValues.insert(*iter);
}
EXPECT_EQ(expectedValues, actualValues);
}
// Tests removing bits from the iterator during iteration.
TYPED_TEST(BitSetIteratorTest, ResetLaterBit)
{
TypeParam mStateBits = this->mStateBits;
std::set<size_t> expectedValues = {1, 3, 5, 7, 9};
for (size_t index = 1; index <= 9; ++index)
mStateBits.set(index);
std::set<size_t> actualValues;
for (auto iter = mStateBits.begin(), end = mStateBits.end(); iter != end; ++iter)
{
if (*iter == 1)
{
iter.resetLaterBit(2);
iter.resetLaterBit(4);
iter.resetLaterBit(6);
iter.resetLaterBit(8);
}
actualValues.insert(*iter);
}
EXPECT_EQ(expectedValues, actualValues);
}
// Tests adding bitsets to the iterator during iteration.
TYPED_TEST(BitSetIteratorTest, SetLaterBits)
{
TypeParam mStateBits = this->mStateBits;
std::set<size_t> expectedValues = {1, 2, 3, 4, 5, 7, 9};
mStateBits.set(1);
mStateBits.set(2);
mStateBits.set(3);
TypeParam laterBits;
laterBits.set(4);
laterBits.set(5);
laterBits.set(7);
laterBits.set(9);
std::set<size_t> actualValues;
for (auto iter = mStateBits.begin(), end = mStateBits.end(); iter != end; ++iter)
{
if (*iter == 3)
{
iter.setLaterBits(laterBits);
}
EXPECT_EQ(actualValues.count(*iter), 0u);
actualValues.insert(*iter);
}
EXPECT_EQ(expectedValues, actualValues);
}
template <typename T>
class BitSetArrayTest : public testing::Test
{
protected:
T mBitSet;
};
using BitSetArrayTypes =
::testing::Types<BitSetArray<65>, BitSetArray<128>, BitSetArray<130>, BitSetArray<511>>;
TYPED_TEST_SUITE(BitSetArrayTest, BitSetArrayTypes);
TYPED_TEST(BitSetArrayTest, BasicTest)
{
TypeParam &mBits = this->mBitSet;
EXPECT_FALSE(mBits.all());
EXPECT_FALSE(mBits.any());
EXPECT_TRUE(mBits.none());
EXPECT_EQ(mBits.count(), 0u);
EXPECT_EQ(mBits.bits(0), 0u);
// Verify set on a single bit
mBits.set(45);
for (auto bit : mBits)
{
EXPECT_EQ(bit, 45u);
}
EXPECT_EQ(mBits.first(), 45u);
EXPECT_EQ(mBits.last(), 45u);
mBits.reset(45);
// Set every bit to 1.
for (size_t i = 0; i < mBits.size(); ++i)
{
mBits.set(i);
EXPECT_EQ(mBits.all(), i + 1 == mBits.size());
EXPECT_TRUE(mBits.any());
EXPECT_FALSE(mBits.none());
EXPECT_EQ(mBits.count(), i + 1);
}
// Reset odd bits to 0.
for (size_t i = 1; i < mBits.size(); i += 2)
{
mBits.reset(i);
EXPECT_FALSE(mBits.all());
EXPECT_TRUE(mBits.any());
EXPECT_FALSE(mBits.none());
EXPECT_EQ(mBits.count(), mBits.size() - i / 2 - 1);
}
// Make sure the bit pattern is what we expect at this point.
// All even bits should be set
for (size_t i = 0; i < mBits.size(); ++i)
{
EXPECT_EQ(mBits.test(i), i % 2 == 0);
EXPECT_EQ(static_cast<bool>(mBits[i]), i % 2 == 0);
}
// Reset everything.
mBits.reset();
EXPECT_FALSE(mBits.all());
EXPECT_FALSE(mBits.any());
EXPECT_TRUE(mBits.none());
EXPECT_EQ(mBits.count(), 0u);
// Test intersection logic
TypeParam testBitSet;
testBitSet.set(1);
EXPECT_EQ(testBitSet.bits(0), (1ul << 1ul));
testBitSet.set(3);
EXPECT_EQ(testBitSet.bits(0), (1ul << 1ul) | (1ul << 3ul));
testBitSet.set(5);
EXPECT_EQ(testBitSet.bits(0), (1ul << 1ul) | (1ul << 3ul) | (1ul << 5ul));
EXPECT_FALSE(mBits.intersects(testBitSet));
mBits.set(3);
EXPECT_TRUE(mBits.intersects(testBitSet));
mBits.set(4);
EXPECT_TRUE(mBits.intersects(testBitSet));
mBits.reset(3);
EXPECT_FALSE(mBits.intersects(testBitSet));
testBitSet.set(4);
EXPECT_TRUE(mBits.intersects(testBitSet));
// Test that flip works.
// Reset everything.
mBits.reset();
EXPECT_EQ(mBits.count(), 0u);
mBits.flip();
EXPECT_EQ(mBits.count(), mBits.size());
// Test operators
// Assignment operators - "=", "&=", "|=" and "^="
mBits.reset();
mBits = testBitSet;
for (auto bit : testBitSet)
{
EXPECT_TRUE(mBits.test(bit));
}
mBits &= testBitSet;
for (auto bit : testBitSet)
{
EXPECT_TRUE(mBits.test(bit));
}
EXPECT_EQ(mBits.count(), testBitSet.count());
mBits.reset();
mBits |= testBitSet;
for (auto bit : testBitSet)
{
EXPECT_TRUE(mBits.test(bit));
}
mBits ^= testBitSet;
EXPECT_TRUE(mBits.none());
// Bitwise operators - "&", "|" and "^"
std::set<std::size_t> bits1 = {0, 45, 60};
std::set<std::size_t> bits2 = {5, 45, 50, 63};
std::set<std::size_t> bits1Andbits2 = {45};
std::set<std::size_t> bits1Orbits2 = {0, 5, 45, 50, 60, 63};
std::set<std::size_t> bits1Xorbits2 = {0, 5, 50, 60, 63};
std::set<std::size_t> actualValues;
TypeParam testBitSet1;
TypeParam testBitSet2;
for (std::size_t bit : bits1)
{
testBitSet1.set(bit);
}
for (std::size_t bit : bits2)
{
testBitSet2.set(bit);
}
EXPECT_EQ(testBitSet1.first(), 0u);
EXPECT_EQ(testBitSet1.last(), 60u);
EXPECT_EQ(testBitSet2.first(), 5u);
EXPECT_EQ(testBitSet2.last(), 63u);
actualValues.clear();
for (auto bit : (testBitSet1 & testBitSet2))
{
actualValues.insert(bit);
}
EXPECT_EQ(bits1Andbits2, actualValues);
actualValues.clear();
for (auto bit : (testBitSet1 | testBitSet2))
{
actualValues.insert(bit);
}
EXPECT_EQ(bits1Orbits2, actualValues);
actualValues.clear();
for (auto bit : (testBitSet1 ^ testBitSet2))
{
actualValues.insert(bit);
}
EXPECT_EQ(bits1Xorbits2, actualValues);
// Relational operators - "==" and "!="
EXPECT_FALSE(testBitSet1 == testBitSet2);
EXPECT_TRUE(testBitSet1 != testBitSet2);
// Unary operators - "~" and "[]"
mBits.reset();
mBits = ~testBitSet;
for (auto bit : mBits)
{
EXPECT_FALSE(testBitSet.test(bit));
}
EXPECT_EQ(mBits.count(), (mBits.size() - testBitSet.count()));
mBits.reset();
for (auto bit : testBitSet)
{
mBits[bit] = true;
}
for (auto bit : mBits)
{
EXPECT_TRUE(testBitSet.test(bit));
}
}
TYPED_TEST(BitSetArrayTest, IterationWithGaps)
{
TypeParam &mBits = this->mBitSet;
// Test iterator works with gap in bitset.
std::set<size_t> bitsToBeSet = {0, mBits.size() / 2, mBits.size() - 1};
for (size_t bit : bitsToBeSet)
{
mBits.set(bit);
}
std::set<size_t> bitsActuallySet = {};
for (size_t bit : mBits)
{
bitsActuallySet.insert(bit);
}
EXPECT_EQ(bitsToBeSet, bitsActuallySet);
EXPECT_EQ(mBits.count(), bitsToBeSet.size());
mBits.reset();
}
// Unit test for angle::Bit
TEST(Bit, Test)
{
EXPECT_EQ(Bit<uint32_t>(0), 1u);
EXPECT_EQ(Bit<uint32_t>(1), 2u);
EXPECT_EQ(Bit<uint32_t>(2), 4u);
EXPECT_EQ(Bit<uint32_t>(3), 8u);
EXPECT_EQ(Bit<uint32_t>(31), 0x8000'0000u);
EXPECT_EQ(Bit<uint64_t>(63), static_cast<uint64_t>(0x8000'0000'0000'0000llu));
}
// Unit test for angle::BitMask
TEST(BitMask, Test)
{
EXPECT_EQ(BitMask<uint32_t>(1), 1u);
EXPECT_EQ(BitMask<uint32_t>(2), 3u);
EXPECT_EQ(BitMask<uint32_t>(3), 7u);
EXPECT_EQ(BitMask<uint32_t>(31), 0x7FFF'FFFFu);
EXPECT_EQ(BitMask<uint32_t>(32), 0xFFFF'FFFFu);
EXPECT_EQ(BitMask<uint64_t>(63), static_cast<uint64_t>(0x7FFF'FFFF'FFFF'FFFFllu));
EXPECT_EQ(BitMask<uint64_t>(64), static_cast<uint64_t>(0xFFFF'FFFF'FFFF'FFFFllu));
}
} // anonymous namespace