8 #ifndef OPENVDB_UTIL_NODEMASKS_HAS_BEEN_INCLUDED
9 #define OPENVDB_UTIL_NODEMASKS_HAS_BEEN_INCLUDED
29 #if defined(OPENVDB_USE_SSE42) && defined(_MSC_VER)
31 #elif defined(OPENVDB_USE_SSE42) && (defined(__GNUC__) || defined(__clang__))
32 return __builtin_popcount(v);
35 static const Byte numBits[256] = {
36 #define COUNTONB2(n) n, n+1, n+1, n+2
37 #define COUNTONB4(n) COUNTONB2(n), COUNTONB2(n+1), COUNTONB2(n+1), COUNTONB2(n+2)
38 #define COUNTONB6(n) COUNTONB4(n), COUNTONB4(n+1), COUNTONB4(n+1), COUNTONB4(n+2)
55 v = v - ((v >> 1) & 0x55555555U);
56 v = (v & 0x33333333U) + ((v >> 2) & 0x33333333U);
57 return (((v + (v >> 4)) & 0xF0F0F0FU) * 0x1010101U) >> 24;
67 #if defined(OPENVDB_USE_SSE42) && defined(_MSC_VER) && defined(_M_X64)
69 #elif defined(OPENVDB_USE_SSE42) && (defined(__GNUC__) || defined(__clang__))
70 v = __builtin_popcountll(v);
73 v = v - ((v >> 1) & UINT64_C(0x5555555555555555));
74 v = (v & UINT64_C(0x3333333333333333)) + ((v >> 2) & UINT64_C(0x3333333333333333));
75 v = (((v + (v >> 4)) & UINT64_C(0xF0F0F0F0F0F0F0F)) * UINT64_C(0x101010101010101)) >> 56;
88 #if defined(OPENVDB_USE_SSE42) && defined(_MSC_VER)
90 _BitScanForward(&index, static_cast<Index32>(v));
91 return static_cast<Index32>(index);
92 #elif defined(OPENVDB_USE_SSE42) && (defined(__GNUC__) || defined(__clang__))
93 return __builtin_ctz(v);
96 static const Byte DeBruijn[8] = {0, 1, 6, 2, 7, 5, 4, 3};
97 return DeBruijn[
Byte((v & -v) * 0x1DU) >> 5];
107 static const Byte DeBruijn[32] = {
108 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
109 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
113 #if defined(_MSC_VER)
114 #pragma warning(push)
115 #pragma warning(disable:4146)
117 return DeBruijn[
Index32((v & -v) * 0x077CB531U) >> 27];
118 #if defined(_MSC_VER)
128 #if defined(OPENVDB_USE_SSE42) && defined(_MSC_VER)
130 _BitScanForward64(&index, v);
131 return static_cast<Index32>(index);
132 #elif defined(OPENVDB_USE_SSE42) && (defined(__GNUC__) || defined(__clang__))
133 return static_cast<Index32>(__builtin_ctzll(v));
136 static const Byte DeBruijn[64] = {
137 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
138 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
139 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
140 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12,
145 #if defined(_MSC_VER)
146 #pragma warning(push)
147 #pragma warning(disable:4146)
149 return DeBruijn[
Index64((v & -v) * UINT64_C(0x022FDD63CC95386D)) >> 58];
150 #if defined(_MSC_VER)
161 static const Byte DeBruijn[32] = {
162 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
163 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
170 return DeBruijn[
Index32(v * 0x07C4ACDDU) >> 27];
178 template<
typename NodeMask>
190 assert((parent ==
nullptr && pos == 0) || (parent !=
nullptr && pos <=
NodeMask::SIZE));
202 operator bool()
const {
return this->
test(); }
207 template <
typename NodeMask>
238 template <
typename NodeMask>
269 template <
typename NodeMask>
306 template<Index Log2Dim>
310 static_assert(Log2Dim > 2,
"expected NodeMask template specialization, got base template");
343 const Word* w2 = other.mWords;
344 for (
Word* w1 = mWords; n--; ++w1, ++w2) *w1 = *w2;
362 for (
const Word *w1=mWords, *w2=other.mWords; n-- && *w1++ == *w2++;) ;
378 template<
typename WordOp>
382 const Word *w2 = other.mWords;
386 template<
typename WordOp>
390 const Word *w2 = other1.mWords, *w3 = other2.mWords;
394 template<
typename WordOp>
399 const Word *w2 = other1.mWords, *w3 = other2.mWords, *w4 = other3.mWords;
407 const Word *w2 = other.mWords;
415 const Word *w2 = other.mWords;
423 const Word *w2 = other.mWords;
431 const Word *w2 = other.mWords;
454 mWords[n >> 6] |=
Word(1) << (n & 63);
459 mWords[n >> 6] &= ~(
Word(1) << (n & 63));
468 for (
Word*
w = mWords; n--; ++
w) *
w = state;
485 mWords[n >> 6] ^=
Word(1) << (n & 63);
491 for (
Word*
w = mWords; n--; ++
w) *
w = ~*
w;
505 return 0 != (mWords[n >> 6] & (
Word(1) << (n & 63)));
513 for (
const Word *
w = mWords; n-- && *
w++ == ~
Word(0);) ;
520 for (
const Word *
w = mWords; n-- && *
w++ ==
Word(0);) ;
528 isOn = (mWords[0] == ~
Word(0));
529 if ( !isOn && mWords[0] !=
Word(0))
return false;
531 while( w<n && *w == mWords[0] ) ++
w;
537 const Word*
w = mWords;
544 const Word*
w = mWords;
551 template<
typename WordT>
554 assert(n*8*
sizeof(WordT) <
SIZE);
555 return reinterpret_cast<const WordT*
>(mWords)[n];
557 template<
typename WordT>
560 assert(n*8*
sizeof(WordT) <
SIZE);
561 return reinterpret_cast<WordT*
>(mWords)[n];
565 void save(std::ostream& os)
const
567 os.write(reinterpret_cast<const char*>(mWords), this->
memUsage());
569 void load(std::istream& is) { is.read(reinterpret_cast<char*>(mWords), this->
memUsage()); }
570 void seek(std::istream& is)
const { is.seekg(this->
memUsage(), std::ios_base::cur); }
574 os <<
"NodeMask: Dim=" <<
DIM <<
" Log2Dim=" << Log2Dim
575 <<
" Bit count=" <<
SIZE <<
" word count=" <<
WORD_COUNT << std::endl;
587 os <<
"|" << std::endl;
674 template<
typename WordOp>
677 op(mByte, other.mByte);
680 template<
typename WordOp>
683 op(mByte, other1.mByte, other2.mByte);
686 template<
typename WordOp>
690 op(mByte, other1.mByte, other2.mByte, other3.mByte);
696 mByte &= other.mByte;
702 mByte |= other.mByte;
708 mByte &=
static_cast<Byte>(~other.mByte);
714 mByte ^= other.mByte;
730 mByte =
static_cast<Byte>(mByte | 0x01U << (n & 7));
735 mByte =
static_cast<Byte>(mByte & ~(0x01U << (n & 7)));
740 void set(
bool on) { mByte = on ? 0xFFU : 0x00U; }
748 mByte =
static_cast<Byte>(mByte ^ 0x01U << (n & 7));
764 return mByte & (0x01U << (n & 7));
769 bool isOn()
const {
return mByte == 0xFFU; }
771 bool isOff()
const {
return mByte == 0; }
778 return isOn || this->
isOff();
783 const Byte b =
static_cast<Byte>(~mByte);
790 template<typename WordT>
791 WordT getWord(Index n) const
793 static_assert(sizeof(WordT) == sizeof(Byte), "expected word size to be one byte");
795 return reinterpret_cast<WordT>(mByte);
797 template<typename WordT>
798 WordT& getWord(Index n)
800 static_assert(sizeof(WordT) == sizeof(Byte), "expected word size to be one byte");
802 return reinterpret_cast<WordT&>(mByte);
806 void save(std::ostream& os)
const { os.write(reinterpret_cast<const char*>(&mByte), 1); }
807 void load(std::istream& is) { is.read(reinterpret_cast<char*>(&mByte), 1); }
808 void seek(std::istream& is)
const { is.seekg(1, std::ios_base::cur); }
812 os <<
"NodeMask: Dim=2, Log2Dim=1, Bit count=8, Word count=1"<<std::endl;
818 os <<
"||" << std::endl;
828 if (start>=8)
return 8;
835 if (start>=8)
return 8;
863 NodeMask(
bool on) : mWord(on ? UINT64_C(0xFFFFFFFFFFFFFFFF) : UINT64_C(0x00)) {}
896 template<
typename WordOp>
899 op(mWord, other.mWord);
902 template<
typename WordOp>
905 op(mWord, other1.mWord, other2.mWord);
908 template<
typename WordOp>
912 op(mWord, other1.mWord, other2.mWord, other3.mWord);
918 mWord &= other.mWord;
924 mWord |= other.mWord;
930 mWord &= ~other.mWord;
936 mWord ^= other.mWord;
952 mWord |= UINT64_C(0x01) << (n & 63);
957 mWord &= ~(UINT64_C(0x01) << (n & 63));
962 void set(
bool on) { mWord = on ? UINT64_C(0xFFFFFFFFFFFFFFFF) : UINT64_C(0x00); }
964 void setOn() { mWord = UINT64_C(0xFFFFFFFFFFFFFFFF); }
966 void setOff() { mWord = UINT64_C(0x00); }
970 mWord ^= UINT64_C(0x01) << (n & 63);
986 return 0 != (mWord & (UINT64_C(0x01) << (n & 63)));
991 bool isOn()
const {
return mWord == UINT64_C(0xFFFFFFFFFFFFFFFF); }
993 bool isOff()
const {
return mWord == 0; }
998 { isOn = this->
isOn();
999 return isOn || this->
isOff();
1004 const Word w = ~mWord;
1009 template<
typename WordT>
1012 assert(n*8*
sizeof(WordT) <
SIZE);
1013 return reinterpret_cast<const WordT*
>(&mWord)[n];
1015 template<
typename WordT>
1018 assert(n*8*
sizeof(WordT) <
SIZE);
1019 return reinterpret_cast<WordT*
>(mWord)[n];
1022 void save(std::ostream& os)
const { os.write(reinterpret_cast<const char*>(&mWord), 8); }
1023 void load(std::istream& is) { is.read(reinterpret_cast<char*>(&mWord), 8); }
1024 void seek(std::istream& is)
const { is.seekg(8, std::ios_base::cur); }
1028 os <<
"NodeMask: Dim=4, Log2Dim=2, Bit count=64, Word count=1"<<std::endl;
1033 for (
Index32 i=0; i < 64; ++i) {
1034 if ( !(i%8) ) os <<
"|";
1035 os << this->
isOn(i);
1037 os <<
"||" << std::endl;
1047 if (start>=64)
return 64;
1048 const Word w = mWord & (UINT64_C(0xFFFFFFFFFFFFFFFF) <<
start);
1054 if (start>=64)
return 64;
1055 const Word w = ~mWord & (UINT64_C(0xFFFFFFFFFFFFFFFF) <<
start);
1139 operator bool()
const {
return this->
test();}
1158 for (
Index i=0; i<n && this->
next(); ++i) {}
1162 return this->
test();
1186 for (
Index i=0; i<n && this->
next(); ++i) {}
1190 return this->
test();
1214 for (
Index i=0; i<n && this->
next(); ++i) {}
1218 return this->
test();
1299 mBits[i>>5] |= 1<<(i&31);
1305 mBits[i>>5] &= ~(1<<(i&31));
1321 mBits[i>>5] ^= 1<<(i&31);
1334 return (
mBits[i >> 5] & (1<<(i&31)) );
1339 return ( ~
mBits[i >> 5] & (1<<(i&31)) );
1343 if (!
mBits)
return false;
1349 if (!
mBits)
return true;
1368 void save(std::ostream& os)
const {
1376 void seek(std::istream& is)
const {
1382 os <<
"RootNodeMask: Bit-size="<<
mBitSize<<
" Int-size="<<
mIntSize<<std::endl;
1392 os << this->
isOn(i);
1394 os <<
"|" << std::endl;
1404 Index32 n = start >> 5, m = start & 31;
1407 if (b & (1<<m))
return start;
1408 b &= 0xFFFFFFFF << m;
1415 Index32 n = start >> 5, m = start & 31;
1418 if (b & (1<<m))
return start;
1434 #endif // OPENVDB_UTIL_NODEMASKS_HAS_BEEN_INCLUDED
void save(std::ostream &os) const
bool operator==(const RootNodeMask &B) const
void setLastOff()
Set the last bit off.
NodeMask operator!() const
RootNodeMask operator^(const RootNodeMask &other) const
DenseIterator beginDense() const
void setLastOn()
Set the last bit on.
DenseIterator & operator++()
OffIterator beginOff() const
Index32 findNextOff(Index32 start) const
void set(Index32 n, bool On)
Set the nth bit to the specified state.
const NodeMask & operator-=(const NodeMask &other)
Bitwise difference.
void save(std::ostream &os) const
Index32 findNextOn(Index32 start) const
Index32 CountOff(Byte v)
Return the number of off bits in the given 8-bit value.
Index32 countOn() const
Return the total number of on bits.
bool isOff(Index32 n) const
Return true if the nth bit is off.
Index32 findNextOn(Index32 start) const
Index32 findFirstOn() const
bool operator==(const NodeMask &other) const
bool isOn(Index32 i) const
const NodeMask & operator&=(const NodeMask &other)
Bitwise intersection.
RootNodeMask operator!() const
OnMaskIterator(Index32 pos, const NodeMask *parent)
Index32 getMemUsage() const
Index32 findNextOff(Index32 start) const
bool operator!=(const BaseIterator &iter) const
void seek(std::istream &is) const
NodeMask operator!() const
void load(std::istream &is)
void setOff(Index32 n)
Set the nth bit off.
NodeMask operator|(const NodeMask &other) const
BaseMaskIterator(Index32 pos, const NodeMask *parent)
static Index32 memUsage()
Return the byte size of this NodeMask.
Index32 findFirstOff() const
void toggle(Index32 n)
Toggle the state of the nth bit.
DenseMaskIterator & operator++()
const NodeMask & operator|=(const NodeMask &other)
Bitwise union.
bool isOff() const
Return true if all the bits are off.
DenseIterator endDense() const
RootNodeMask operator&(const RootNodeMask &other) const
void set(Index32 n, bool On)
Set the nth bit to the specified state.
WordT & getWord(Index n)
Return the nth word of the bit mask, for a word of arbitrary size.
OffIterator endOff() const
const RootNodeMask & operator^=(const RootNodeMask &other)
#define OPENVDB_USE_VERSION_NAMESPACE
bool operator<(const BaseMaskIterator &iter) const
void printAll(std::ostream &os=std::cout) const
NodeMask(bool on)
All bits are set to the specified state.
void toggle(Index32 n)
Toggle the state of the nth bit.
ImageBuf OIIO_API min(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
NodeMask()
Default constructor sets all bits off.
DenseIterator beginDense() const
void setLastOn()
Set the last bit on.
const NodeMask & operator-=(const NodeMask &other)
Bitwise difference.
bool isOn(Index32 n) const
Return true if the nth bit is on.
bool operator==(const BaseIterator &iter) const
Index32 findFirstOn() const
DenseIterator endDense() const
void printBits(std::ostream &os=std::cout, Index32 max_out=80u) const
void setOn()
Set all bits on.
OnMaskIterator & operator++()
DenseIterator beginDense() const
void set(bool on)
Set all bits to the specified state.
void set(Index32 i, bool On)
Index32 FindHighestOn(Index32 v)
Return the most significant on bit of the given 32-bit value.
void setOff()
Set all bits off.
NodeMask operator|(const NodeMask &other) const
const NodeMask & operator&=(const NodeMask &other)
Bitwise intersection.
WordT getWord(Index n) const
Return the nth word of the bit mask, for a word of arbitrary size.
Index32 findFirstOff() const
Index32 countOff() const
Return the total number of on bits.
void setOff()
Set all bits off.
bool isOff(Index32 n) const
Return true if the nth bit is off.
const NodeMask & operator^=(const NodeMask &other)
Bitwise XOR.
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
NodeMask operator^(const NodeMask &other) const
OffIterator & operator++()
bool isConstant(bool &isOn) const
void setFirstOff()
Set the first bit off.
void load(std::istream &is)
const NodeMask & operator^=(const NodeMask &other)
Bitwise XOR.
NodeMask operator!() const
void printAll(std::ostream &os=std::cout, Index32 max_out=80u) const
OffMaskIterator< NodeMask > OffIterator
NodeMask operator&(const NodeMask &other) const
RootNodeMask(Index32 bit_size)
bool isOn() const
Return true if all the bits are on.
void save(std::ostream &os) const
Index32 findNextOff(Index32 start) const
bool isOn(Index32 n) const
Return true if the nth bit is on.
Bit mask for the internal and leaf nodes of VDB. This is a 64-bit implementation. ...
Index32 countOn() const
Return the total number of on bits.
void setFirstOn()
Set the first bit on.
OffIterator endOff() const
NodeMask(bool on)
All bits are set to the specified state.
void printAll(std::ostream &os=std::cout, Index32 max_out=80u) const
void setFirstOff()
Set the first bit off.
bool operator<(const BaseIterator &iter) const
OffMaskIterator(Index32 pos, const NodeMask *parent)
void seek(std::istream &is) const
NodeMask(const NodeMask &other)
Copy constructor.
void setLastOff()
Set the last bit off.
void setOn(Index32 n)
Set the nth bit on.
void init(Index32 bit_size)
static const Index32 WORD_COUNT
Index32 CountOn(Byte v)
Return the number of on bits in the given 8-bit value.
void setOn()
Set all bits on.
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
Base class for the bit mask iterators.
OffIterator endOff() const
void toggle()
Toggle the state of all bits in the mask.
NodeMask(bool on)
All bits are set to the specified state.
DenseIterator endDense() const
bool isOn() const
Return true if all the bits are on.
BaseMaskIterator & operator=(const BaseMaskIterator &iter)
bool isConstant(bool &isOn) const
Index32 countOff() const
Return the total number of on bits.
OffIterator beginOff() const
void set(Index32 n, bool On)
Set the nth bit to the specified state.
OnIterator beginOn() const
DenseMaskIterator(Index32 pos, const NodeMask *parent)
DenseIterator(Index32 pos, const RootNodeMask *parent)
void save(std::ostream &os) const
bool isOn() const
Return true if all the bits are on.
void setOn(Index32 n)
Set the nth bit on.
bool isOn(Index32 n) const
Return true if the nth bit is on.
const RootNodeMask & operator|=(const RootNodeMask &other)
Index32 findNextOn(Index32 start) const
void setOn(Index32 n)
Set the nth bit on.
OffIterator(Index32 pos, const RootNodeMask *parent)
static const Index32 SIZE
void setFirstOn()
Set the first bit on.
void seek(std::istream &is) const
GLboolean GLboolean GLboolean b
const RootNodeMask * mParent
OffIterator beginOff() const
static Index32 memUsage()
Return the byte size of this NodeMask.
BaseIterator(Index32 pos, const RootNodeMask *parent)
void setFirstOff()
Set the first bit off.
const NodeMask & operator|=(const NodeMask &other)
Bitwise union.
DenseIterator beginDense() const
Index32 findFirstOn() const
static const Index32 LOG2DIM
bool operator!=(const BaseMaskIterator &iter) const
Index32 findFirstOn() const
void setLastOn()
Set the last bit on.
RootNodeMask & operator=(const RootNodeMask &B)
NodeMask operator&(const NodeMask &other) const
OffIterator endOff() const
bool operator==(const BaseMaskIterator &iter) const
OnIterator beginOn() const
DenseMaskIterator< NodeMask > DenseIterator
BaseIterator & operator=(const BaseIterator &iter)
WordT getWord(Index n) const
Return the nth word of the bit mask, for a word of arbitrary size.
OnIterator & operator++()
void printBits(std::ostream &os=std::cout, Index32 max_out=80u) const
Index32 countOff() const
Return the total number of on bits.
Index32 findFirstOff() const
void set(bool on)
Set all bits to the specified state.
void seek(std::istream &is) const
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
const RootNodeMask & operator&=(const RootNodeMask &other)
RootNodeMask operator|(const RootNodeMask &other) const
const NodeMask & operator|=(const NodeMask &other)
Bitwise union.
Index32 findNextOn(Index32 start) const
void setOff(Index32 n)
Set the nth bit off.
NodeMask()
Default constructor sets all bits off.
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
bool operator!=(const NodeMask &other) const
Index32 FindLowestOn(Byte v)
Return the least significant on bit of the given 8-bit value.
bool isOff() const
Return true if all the bits are off.
OnMaskIterator< NodeMask > OnIterator
NodeMask operator|(const NodeMask &other) const
OffIterator beginOff() const
void toggle(Index32 n)
Toggle the state of the nth bit.
GA_API const UT_StringHolder N
NodeMask & operator=(const NodeMask &other)
Assignment operator.
bool isOff() const
Return true if all the bits are off.
NodeMask operator^(const NodeMask &other) const
bool isConstant(bool &isOn) const
OnIterator beginOn() const
Index32 findFirstOff() const
const NodeMask & operator^=(const NodeMask &other)
Bitwise XOR.
RootNodeMask(const RootNodeMask &B)
DenseIterator endDense() const
NodeMask(const NodeMask &other)
Copy constructor.
GLubyte GLubyte GLubyte GLubyte w
OffMaskIterator & operator++()
void toggle()
Toggle the state of all bits in the mask.
void load(std::istream &is)
void setLastOff()
Set the last bit off.
void printBits(std::ostream &os=std::cout) const
void printAll(std::ostream &os=std::cout) const
Index32 countOn() const
Return the total number of on bits.
NodeMask(const NodeMask &other)
Copy constructor.
void set(bool on)
Set all bits to the specified state.
NodeMask()
Default constructor sets all bits off.
void printBits(std::ostream &os=std::cout) const
void setFirstOn()
Set the first bit on.
bool operator!=(const RootNodeMask &B) const
void setOff()
Set all bits off.
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
void setOff(Index32 n)
Set the nth bit off.
void load(std::istream &is)
Index32 findNextOff(Index32 start) const
OnIterator(Index32 pos, const RootNodeMask *parent)
static Index32 memUsage()
Return the byte size of this NodeMask.
NodeMask operator^(const NodeMask &other) const
void setOn()
Set all bits on.
WordT & getWord(Index n)
Return the nth word of the bit mask, for a word of arbitrary size.
bool isOff(Index32 i) const
NodeMask operator&(const NodeMask &other) const
const NodeMask & operator&=(const NodeMask &other)
Bitwise intersection.
bool isOff(Index32 n) const
Return true if the nth bit is off.
void toggle()
Toggle the state of all bits in the mask.
OnIterator beginOn() const
const NodeMask & operator-=(const NodeMask &other)
Bitwise difference.