35 #ifndef OPENVDB_UTIL_NODEMASKS_HAS_BEEN_INCLUDED
36 #define OPENVDB_UTIL_NODEMASKS_HAS_BEEN_INCLUDED
41 #include <openvdb/Types.h>
55 static const Byte numBits[256] = {
56 # define B2(n) n, n+1, n+1, n+2
57 # define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
58 # define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
78 v = v - ((v >> 1) & 0x55555555U);
79 v = (v & 0x33333333U) + ((v >> 2) & 0x33333333U);
80 return ((v + (v >> 4) & 0xF0F0F0FU) * 0x1010101U) >> 24;
90 v = v - ((v >> 1) & UINT64_C(0x5555555555555555));
91 v = (v & UINT64_C(0x3333333333333333)) + ((v >> 2) & UINT64_C(0x3333333333333333));
92 return ((v + (v >> 4) & UINT64_C(0xF0F0F0F0F0F0F0F)) * UINT64_C(0x101010101010101)) >> 56;
103 static const Byte DeBruijn[8] = {0, 1, 6, 2, 7, 5, 4, 3};
104 return DeBruijn[
Byte((v & -v) * 0x1DU) >> 5];
113 static const Byte DeBruijn[32] = {
114 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
115 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
117 return DeBruijn[
Index32((v & -v) * 0x077CB531U) >> 27];
126 static const Byte DeBruijn[64] = {
127 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
128 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
129 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
130 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12,
132 return DeBruijn[
Index64((v & -v) * UINT64_C(0x022FDD63CC95386D)) >> 58];
139 static const Byte DeBruijn[32] = {
140 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
141 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
148 return DeBruijn[
Index32(v * 0x07C4ACDDU) >> 27];
156 template <
typename NodeMask>
166 assert( (parent==NULL && pos==0 ) || (parent!=NULL && pos<=NodeMask::SIZE) );
180 assert(mPos <= NodeMask::SIZE);
181 return (mPos != NodeMask::SIZE);
183 operator bool()
const {
return this->test();}
188 template <
typename NodeMask>
193 using BaseType::mPos;
194 using BaseType::mParent;
200 assert(mParent != NULL);
201 mPos = mParent->findNextOn(mPos+1);
202 assert(mPos <= NodeMask::SIZE);
219 template <
typename NodeMask>
224 using BaseType::mPos;
225 using BaseType::mParent;
231 assert(mParent != NULL);
232 mPos=mParent->findNextOff(mPos+1);
233 assert(mPos <= NodeMask::SIZE);
250 template <
typename NodeMask>
255 using BaseType::mPos;
256 using BaseType::mParent;
263 assert(mParent != NULL);
265 assert(mPos<= NodeMask::SIZE);
287 template<Index Log2Dim>
291 BOOST_STATIC_ASSERT( Log2Dim>2 );
309 Word mWords[WORD_COUNT];
324 const Word* w2 = other.mWords;
325 for (
Word* w1 = mWords; n--; ++w1, ++w2) *w1 = *w2;
342 for (
const Word *w1=mWords, *w2=other.mWords; n-- && *w1++ == *w2++;) ;
355 const Word* w2 = other.mWords;
356 for (
Word* w1 = mWords; n--; ++w1, ++w2) *w1 &= *w2;
362 const Word* w2 = other.mWords;
363 for (
Word* w1 = mWords; n--; ++w1, ++w2) *w1 |= *w2;
369 const Word* w2 = other.mWords;
370 for (
Word* w1 = mWords; n--; ++w1, ++w2) *w1 ^= *w2;
383 Index32 sum = 0, n = WORD_COUNT;
384 for (
const Word* w = mWords; n--; ++w) sum +=
CountOn(*w);
391 assert( (n >> 6) < WORD_COUNT );
392 mWords[n >> 6] |=
Word(1) << (n & 63);
396 assert( (n >> 6) < WORD_COUNT );
397 mWords[n >> 6] &= ~(
Word(1) << (n & 63));
400 void set(
Index32 n,
bool On) { On ? this->setOn(n) : this->setOff(n); }
406 for (
Word* w = mWords; n--; ++w) *w = state;
412 for (
Word* w = mWords; n--; ++w) *w = ~
Word(0);
418 for (
Word* w = mWords; n--; ++w) *w =
Word(0);
422 assert( (n >> 6) < WORD_COUNT );
423 mWords[n >> 6] ^= 1 << (n & 63);
429 for (
Word* w = mWords; n--; ++w) *w = ~*w;
442 assert( (n >> 6) < WORD_COUNT );
443 return 0 != (mWords[n >> 6] & (
Word(1) << (n & 63)));
451 for (
const Word *w = mWords; n-- && *w++ == ~
Word(0);) ;
458 for (
const Word *w = mWords; n-- && *w++ ==
Word(0);) ;
464 const Word* w = mWords;
465 for (; n<WORD_COUNT && !*w; ++w, ++n) ;
466 return n==WORD_COUNT ? SIZE : (n << 6) +
FindLowestOn(*w);
471 const Word* w = mWords;
472 for (; n<WORD_COUNT && !~*w; ++w, ++n) ;
473 return n==WORD_COUNT ? SIZE : (n << 6) +
FindLowestOn(~*w);
478 template<
typename WordT>
481 assert(n*8*
sizeof(WordT) < SIZE);
482 return reinterpret_cast<const WordT*
>(mWords)[n];
484 template<
typename WordT>
487 assert(n*8*
sizeof(WordT) < SIZE);
488 return reinterpret_cast<WordT*
>(mWords)[n];
492 void save(std::ostream& os)
const
494 os.write(reinterpret_cast<const char*>(mWords), this->memUsage());
497 is.read(reinterpret_cast<char*>(mWords), this->memUsage());
500 void printInfo(std::ostream& os=std::cout)
const
502 os <<
"NodeMask: Dim=" << DIM <<
" Log2Dim=" << Log2Dim
503 <<
" Bit count=" << SIZE <<
" word count=" << WORD_COUNT << std::endl;
505 void printBits(std::ostream& os=std::cout,
Index32 max_out=80u)
const
507 const Index32 n=(SIZE>max_out ? max_out : SIZE);
508 for (
Index32 i=0; i < n; ++i) {
515 os <<
"|" << std::endl;
517 void printAll(std::ostream& os=std::cout,
Index32 max_out=80u)
const
520 this->printBits(os, max_out);
526 if (n >= WORD_COUNT)
return SIZE;
529 if (b & (
Word(1) << m))
return start;
531 while(!b && ++n<WORD_COUNT) b = mWords[n];
538 if (n >= WORD_COUNT)
return SIZE;
541 if (b & (
Word(1) << m))
return start;
543 while(!b && ++n<WORD_COUNT) b = ~mWords[n];
575 void operator = (
const NodeMask &other) { mByte = other.mByte; }
598 mByte &= other.mByte;
603 mByte |= other.mByte;
608 mByte ^= other.mByte;
625 mByte |= 0x01U << (n & 7);
630 mByte &= ~(0x01U << (n & 7));
633 void set(
Index32 n,
bool On) { On ? this->setOn(n) : this->setOff(n); }
635 void set(
bool on) { mByte = on ? 0xFFU : 0x00U; }
643 mByte ^= 0x01U << (n & 7);
659 return mByte & (0x01U << (n & 7));
664 bool isOn()
const {
return mByte == 0xFFU; }
666 bool isOff()
const {
return mByte == 0; }
670 const Byte b = ~mByte;
693 void save(std::ostream& os)
const
695 os.write(reinterpret_cast<const char*>(&mByte), 1);
697 void load(std::istream& is) { is.read(reinterpret_cast<char*>(&mByte), 1); }
699 void printInfo(std::ostream& os=std::cout)
const
701 os <<
"NodeMask: Dim=2, Log2Dim=1, Bit count=8, Word count=1"<<std::endl;
703 void printBits(std::ostream& os=std::cout)
const
706 for (
Index32 i=0; i < 8; ++i) os << this->isOn(i);
707 os <<
"||" << std::endl;
709 void printAll(std::ostream& os=std::cout)
const
717 if (start>=8)
return 8;
718 const Byte b = mByte & (0xFFU << start);
724 if (start>=8)
return 8;
725 const Byte b = ~mByte & (0xFFU << start);
752 NodeMask(
bool on) : mWord(on ? UINT64_C(0xFFFFFFFFFFFFFFFF) : UINT64_C(0x00)) {}
758 void operator = (
const NodeMask &other) { mWord = other.mWord; }
781 mWord &= other.mWord;
786 mWord |= other.mWord;
791 mWord ^= other.mWord;
808 mWord |= UINT64_C(0x01) << (n & 63);
813 mWord &= ~(UINT64_C(0x01) << (n & 63));
816 void set(
Index32 n,
bool On) { On ? this->setOn(n) : this->setOff(n); }
818 void set(
bool on) { mWord = on ? UINT64_C(0xFFFFFFFFFFFFFFFF) : UINT64_C(0x00); }
820 void setOn() { mWord = UINT64_C(0xFFFFFFFFFFFFFFFF); }
822 void setOff() { mWord = UINT64_C(0x00); }
826 mWord ^= UINT64_C(0x01) << (n & 63);
842 return 0 != (mWord & (UINT64_C(0x01) << (n & 63)));
847 bool isOn()
const {
return mWord == UINT64_C(0xFFFFFFFFFFFFFFFF); }
849 bool isOff()
const {
return mWord == 0; }
853 const Word w = ~mWord;
858 template<
typename WordT>
861 assert(n*8*
sizeof(WordT) < SIZE);
862 return reinterpret_cast<const WordT*
>(&mWord)[n];
864 template<
typename WordT>
867 assert(n*8*
sizeof(WordT) < SIZE);
868 return reinterpret_cast<WordT*
>(mWord)[n];
871 void save(std::ostream& os)
const
873 os.write(reinterpret_cast<const char*>(&mWord), 8);
875 void load(std::istream& is) { is.read(reinterpret_cast<char*>(&mWord), 8); }
877 void printInfo(std::ostream& os=std::cout)
const
879 os <<
"NodeMask: Dim=4, Log2Dim=2, Bit count=64, Word count=1"<<std::endl;
881 void printBits(std::ostream& os=std::cout)
const
884 for (
Index32 i=0; i < 64; ++i) {
885 if ( !(i%8) ) os <<
"|";
888 os <<
"||" << std::endl;
890 void printAll(std::ostream& os=std::cout)
const
898 if (start>=64)
return 64;
899 const Word w = mWord & (UINT64_C(0xFFFFFFFFFFFFFFFF) << start);
905 if (start>=64)
return 64;
906 const Word w = ~mWord & (UINT64_C(0xFFFFFFFFFFFFFFFF) << start);
926 mBitSize(bit_size), mIntSize(((bit_size-1)>>5)+1), mBits(new
Index32[mIntSize])
928 for (
Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
931 mBitSize(B.mBitSize), mIntSize(B.mIntSize), mBits(new
Index32[mIntSize])
939 mIntSize =((bit_size-1)>>5)+1;
942 for (
Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
968 : mPos(pos), mBitSize(parent->getBitSize()), mParent(parent) {
969 assert( pos<=mBitSize );
985 assert(mPos <= mBitSize);
986 return (mPos != mBitSize);
989 operator bool()
const {
return this->test();}
996 using BaseIterator::mPos;
997 using BaseIterator::mBitSize;
998 using BaseIterator::mParent;
1003 assert(mParent!=NULL);
1004 mPos=mParent->findNextOn(mPos+1);
1005 assert(mPos <= mBitSize);
1008 for (
Index i=0; i<n && this->next(); ++i) {}
1012 return this->test();
1024 using BaseIterator::mPos;
1025 using BaseIterator::mBitSize;
1026 using BaseIterator::mParent;
1031 assert(mParent!=NULL);
1032 mPos=mParent->findNextOff(mPos+1);
1033 assert(mPos <= mBitSize);
1036 for (
Index i=0; i<n && this->next(); ++i) {}
1040 return this->test();
1052 using BaseIterator::mPos;
1053 using BaseIterator::mBitSize;
1054 using BaseIterator::mParent;
1059 assert(mParent!=NULL);
1061 assert(mPos<= mBitSize);
1064 for (
Index i=0; i<n && this->next(); ++i) {}
1068 return this->test();
1085 if (mBitSize != B.
mBitSize)
return false;
1086 for (
Index32 i=0; i<mIntSize; ++i)
if (mBits[i] != B.
mBits[i])
return false;
1091 if (mBitSize != B.
mBitSize)
return true;
1092 for (
Index32 i=0; i<mIntSize; ++i)
if (mBits[i] != B.
mBits[i])
return true;
1101 assert(mIntSize == other.
mIntSize);
1103 mBits[i] &= other.
mBits[i];
1105 for (
Index32 i = other.
mIntSize; i < mIntSize; ++i) mBits[i] = 0x00000000;
1109 assert(mIntSize == other.
mIntSize);
1111 mBits[i] |= other.
mBits[i];
1116 assert(mIntSize == other.
mIntSize);
1118 mBits[i] ^= other.
mBits[i];
1146 assert( (i>>5) < mIntSize);
1147 mBits[i>>5] |= 1<<(i&31);
1152 assert( (i>>5) < mIntSize);
1153 mBits[i>>5] &= ~(1<<(i&31));
1156 void set(
Index32 i,
bool On) { On ? this->setOn(i) : this->setOff(i); }
1160 for (
Index32 i=0; i<mIntSize; ++i) mBits[i]=0xFFFFFFFF;
1164 for (
Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
1168 assert( (i>>5) < mIntSize);
1169 mBits[i>>5] ^= 1<<(i&31);
1173 for (
Index32 i=0; i<mIntSize; ++i) mBits[i]=~mBits[i];
1181 assert( (i>>5) < mIntSize);
1182 return ( mBits[i >> 5] & (1<<(i&31)) );
1186 assert( (i>>5) < mIntSize);
1187 return ( ~mBits[i >> 5] & (1<<(i&31)) );
1191 if (!mBits)
return false;
1192 for (
Index32 i=0; i<mIntSize; ++i)
if (mBits[i] != 0xFFFFFFFF)
return false;
1197 if (!mBits)
return true;
1198 for (
Index32 i=0; i<mIntSize; ++i)
if (mBits[i] != 0)
return false;
1205 while(!mBits[i])
if (++i == mIntSize)
return mBitSize;
1212 while(!(~mBits[i]))
if (++i == mIntSize)
return mBitSize;
1216 void save(std::ostream& os)
const {
1218 os.write((
const char *)mBits,mIntSize*
sizeof(
Index32));
1222 is.read((
char *)mBits,mIntSize*
sizeof(
Index32));
1226 os <<
"RootNodeMask: Bit-size="<<mBitSize<<
" Int-size="<<mIntSize<<std::endl;
1230 const Index32 n=(mBitSize>max_out?max_out:mBitSize);
1231 for (
Index32 i=0; i < n; ++i) {
1236 os << this->isOn(i);
1238 os <<
"|" << std::endl;
1242 this->printInfo(os);
1243 this->printBits(os,max_out);
1248 Index32 n = start >> 5, m = start & 31;
1249 if (n>=mIntSize)
return mBitSize;
1251 if (b & (1<<m))
return start;
1252 b &= 0xFFFFFFFF << m;
1253 while(!b && ++n<mIntSize) b = mBits[n];
1259 Index32 n = start >> 5, m = start & 31;
1260 if (n>=mIntSize)
return mBitSize;
1262 if (b & (1<<m))
return start;
1264 while(!b && ++n<mIntSize) b = ~mBits[n];
1278 #endif // OPENVDB_UTIL_NODEMASKS_HAS_BEEN_INCLUDED