36 #ifndef OPENVDB_UTIL_NODEMASK_HAS_BEEN_INCLUDED
37 #define OPENVDB_UTIL_NODEMASK_HAS_BEEN_INCLUDED
42 #include <openvdb/Types.h>
53 v = v - ((v >> 1) & 0x55555555);
54 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
55 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
65 static const Index32 MultiplyDeBruijnBitPosition[32] = {
66 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
67 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
69 return MultiplyDeBruijnBitPosition[
Index32((v & -v) * 0x077CB531U) >> 27];
76 static const Index32 MultiplyDeBruijnBitPosition[32] = {
77 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
78 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
85 return MultiplyDeBruijnBitPosition[
Index32(v * 0x07C4ACDDU) >> 27];
90 template<Index Log2Dim>
96 static const Index32 BIT_SIZE = 1<<3*Log2Dim;
97 static const Index32 INT_SIZE = (1<<(3*Log2Dim-3))>>2;
98 BOOST_STATIC_ASSERT( Log2Dim>1 );
126 mPos(pos), mParent(parent) {
127 assert( (parent==NULL && pos==0 ) || (parent!=NULL && pos<=BIT_SIZE) );
143 assert(mPos <= BIT_SIZE);
144 return (mPos != BIT_SIZE);
147 operator bool()
const {
return this->test();}
154 using BaseIterator::mPos;
155 using BaseIterator::mParent;
160 assert(mParent!=NULL);
161 mPos=mParent->findNextOn(mPos+1);
162 assert(mPos <= BIT_SIZE);
165 for (
Index i=0; i<n && this->next(); ++i) {}
181 using BaseIterator::mPos;
182 using BaseIterator::mParent;
187 assert(mParent!=NULL);
188 mPos=mParent->findNextOff(mPos+1);
189 assert(mPos <= BIT_SIZE);
192 for (
Index i=0; i<n && this->next(); ++i) {}
208 using BaseIterator::mPos;
209 using BaseIterator::mParent;
215 assert(mParent!=NULL);
217 assert(mPos<= BIT_SIZE);
220 for (
Index i=0; i<n && this->next(); ++i) {}
241 for (
Index32 i=0; i<INT_SIZE; ++i)
if (mBits[i] != B.
mBits[i])
return false;
246 for (
Index32 i=0; i<INT_SIZE; ++i)
if (mBits[i] != B.
mBits[i])
return true;
255 for (
Index32 i = 0; i < INT_SIZE; ++i) mBits[i] &= other.
mBits[i];
259 for (
Index32 i = 0; i < INT_SIZE; ++i) mBits[i] |= other.
mBits[i];
263 for (
Index32 i = 0; i < INT_SIZE; ++i) mBits[i] ^= other.
mBits[i];
281 assert( (i>>5) < INT_SIZE);
282 mBits[i>>5] |= 1<<(i&31);
286 assert( (i>>5) < INT_SIZE);
287 mBits[i>>5] &= ~(1<<(i&31));
290 void set(
Index32 i,
bool On) { On ? this->setOn(i) : this->setOff(i); }
293 const Index32 val = On ? 0xFFFFFFFF : 0x00000000;
294 for (
Index32 i=0; i<INT_SIZE; ++i) mBits[i] = val;
297 void setOn() {
for (
Index32 i=0; i<INT_SIZE; ++i) mBits[i]=0xFFFFFFFF; }
300 assert( (i>>5) < INT_SIZE);
301 mBits[i>>5] ^= 1<<(i&31);
309 assert( (i>>5) < INT_SIZE);
310 return ( mBits[i >> 5] & (1<<(i&31)) );
313 assert( (i>>5) < INT_SIZE);
314 return ( ~mBits[i >> 5] & (1<<(i&31)) );
317 for (
Index32 i=0; i<INT_SIZE; ++i)
if (mBits[i] != 0xFFFFFFFF)
return false;
321 for (
Index32 i=0; i<INT_SIZE; ++i)
if (mBits[i] != 0x00000000)
return false;
326 while(!mBits[i])
if (++i == INT_SIZE)
return BIT_SIZE;
331 while(!(~mBits[i]))
if (++i == INT_SIZE)
return BIT_SIZE;
337 template<
typename WordT>
339 assert(n*8*
sizeof(WordT) < BIT_SIZE);
340 return reinterpret_cast<const WordT*
>(mBits)[n];
342 template<
typename WordT>
344 assert(n*8*
sizeof(WordT) < BIT_SIZE);
345 return reinterpret_cast<WordT*
>(mBits)[n];
368 void save(std::ostream& os)
const {
369 os.write((
const char *)mBits,INT_SIZE*
sizeof(
Index32));
372 is.read((
char *)mBits,INT_SIZE*
sizeof(
Index32));
376 os <<
"NodeMask: Log2Dim="<<DIM<<
" Bit-size="<<BIT_SIZE<<
" Int-size="<<INT_SIZE<<std::endl;
379 const Index32 n=(BIT_SIZE>max_out?max_out:BIT_SIZE);
380 for (
Index32 i=0; i < n; ++i) {
387 os <<
"|" << std::endl;
391 this->printBits(os,max_out);
396 if (n>=INT_SIZE)
return BIT_SIZE;
397 Index32 m=start&31, b=mBits[n];
398 if (b & (1<<m))
return start;
399 b &= 0xFFFFFFFF << m;
400 while(!b && ++n<INT_SIZE) b = mBits[n];
406 if (n>=INT_SIZE)
return BIT_SIZE;
407 Index32 m=start&31, b=~mBits[n];
408 if (b & (1<<m))
return start;
410 while(!b && ++n<INT_SIZE) b = ~mBits[n];
415 return INT_SIZE*
sizeof(
Index32);
430 mBitSize(bit_size), mIntSize(((bit_size-1)>>5)+1), mBits(new
Index32[mIntSize])
432 for (
Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
435 mBitSize(B.mBitSize), mIntSize(B.mIntSize), mBits(new
Index32[mIntSize])
443 mIntSize =((bit_size-1)>>5)+1;
446 for (
Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
472 : mPos(pos), mBitSize(parent->getBitSize()), mParent(parent) {
473 assert( pos<=mBitSize );
491 assert(mPos <= mBitSize);
492 return (mPos != mBitSize);
495 operator bool()
const {
return this->test();}
502 using BaseIterator::mPos;
503 using BaseIterator::mBitSize;
504 using BaseIterator::mParent;
509 assert(mParent!=NULL);
510 mPos=mParent->findNextOn(mPos+1);
511 assert(mPos <= mBitSize);
514 for (
Index i=0; i<n && this->next(); ++i) {}
530 using BaseIterator::mPos;
531 using BaseIterator::mBitSize;
532 using BaseIterator::mParent;
537 assert(mParent!=NULL);
538 mPos=mParent->findNextOff(mPos+1);
539 assert(mPos <= mBitSize);
542 for (
Index i=0; i<n && this->next(); ++i) {}
558 using BaseIterator::mPos;
559 using BaseIterator::mBitSize;
560 using BaseIterator::mParent;
565 assert(mParent!=NULL);
567 assert(mPos<= mBitSize);
570 for (
Index i=0; i<n && this->next(); ++i) {}
591 if (mBitSize != B.
mBitSize)
return false;
592 for (
Index32 i=0; i<mIntSize; ++i)
if (mBits[i] != B.
mBits[i])
return false;
597 if (mBitSize != B.
mBitSize)
return true;
598 for (
Index32 i=0; i<mIntSize; ++i)
if (mBits[i] != B.
mBits[i])
return true;
609 mBits[i] &= other.
mBits[i];
611 for (
Index32 i = other.
mIntSize; i < mIntSize; ++i) mBits[i] = 0x00000000;
617 mBits[i] |= other.
mBits[i];
624 mBits[i] ^= other.
mBits[i];
652 assert( (i>>5) < mIntSize);
653 mBits[i>>5] |= 1<<(i&31);
658 assert( (i>>5) < mIntSize);
659 mBits[i>>5] &= ~(1<<(i&31));
662 void set(
Index32 i,
bool On) { On ? this->setOn(i) : this->setOff(i); }
666 for (
Index32 i=0; i<mIntSize; ++i) mBits[i]=0xFFFFFFFF;
670 for (
Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
674 assert( (i>>5) < mIntSize);
675 mBits[i>>5] ^= 1<<(i&31);
679 for (
Index32 i=0; i<mIntSize; ++i) mBits[i]=~mBits[i];
687 assert( (i>>5) < mIntSize);
688 return ( mBits[i >> 5] & (1<<(i&31)) );
692 assert( (i>>5) < mIntSize);
693 return ( ~mBits[i >> 5] & (1<<(i&31)) );
697 if (!mBits)
return false;
698 for (
Index32 i=0; i<mIntSize; ++i)
if (mBits[i] != 0xFFFFFFFF)
return false;
703 if (!mBits)
return true;
704 for (
Index32 i=0; i<mIntSize; ++i)
if (mBits[i] != 0)
return false;
711 while(!mBits[i])
if (++i == mIntSize)
return mBitSize;
718 while(!(~mBits[i]))
if (++i == mIntSize)
return mBitSize;
722 void save(std::ostream& os)
const {
724 os.write((
const char *)mBits,mIntSize*
sizeof(
Index32));
728 is.read((
char *)mBits,mIntSize*
sizeof(
Index32));
732 os <<
"RootNodeMask: Bit-size="<<mBitSize<<
" Int-size="<<mIntSize<<std::endl;
736 const Index32 n=(mBitSize>max_out?max_out:mBitSize);
737 for (
Index32 i=0; i < n; ++i) {
744 os <<
"|" << std::endl;
749 this->printBits(os,max_out);
754 Index32 n = start >> 5, m = start & 31;
755 if (n>=mIntSize)
return mBitSize;
757 if (b & (1<<m))
return start;
758 b &= 0xFFFFFFFF << m;
759 while(!b && ++n<mIntSize) b = mBits[n];
765 Index32 n = start >> 5, m = start & 31;
766 if (n>=mIntSize)
return mBitSize;
768 if (b & (1<<m))
return start;
770 while(!b && ++n<mIntSize) b = ~mBits[n];
784 #endif // OPENVDB_UTIL_NODEMASK_HAS_BEEN_INCLUDED