Revision control
+ // Redistribution and use in source and binary forms, with or without
+ // modification, are permitted provided that the following conditions
+ // are met:
+ // * Redistributions of source code must retain the above copyright
+ // notice, this list of conditions and the following disclaimer.
+ // * Redistributions in binary form must reproduce the above copyright
+ // notice, this list of conditions and the following disclaimer in the
+ // documentation and/or other materials provided with the distribution.
+ // * Neither the name of NVIDIA CORPORATION nor the names of its
+ // contributors may be used to endorse or promote products derived
+ // from this software without specific prior written permission.
+ //
+ // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ''AS IS'' AND ANY
+ // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ // OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ //
+ // Copyright (c) 2008-2026 NVIDIA Corporation. All rights reserved.
+ // Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+ // Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+ #ifndef PX_BITMAP_H
+ #define PX_BITMAP_H
+
+ #include "foundation/PxAssert.h"
+ #include "foundation/PxMath.h"
+ #include "foundation/PxMemory.h"
+ #include "foundation/PxAllocator.h"
+ #include "foundation/PxUserAllocated.h"
+ #include "foundation/PxIntrinsics.h"
+ #include "foundation/PxBitUtils.h"
+ #include "foundation/PxConstructor.h"
+
+ #if !PX_DOXYGEN
+ namespace physx
+ {
+ #endif
+
+ /*!
+ Holds a bitmap with operations to set, reset or test individual bits.
+
+ We inhibit copy to prevent unintentional copies. If a copy is desired copy() should be used or
+ alternatively a copy constructor implemented.
+ */
+ template <class Alloc = PxAllocatorTraits<PxU32>::Type>
+ class PxBitMapBase : protected Alloc
+ {
+ PX_NOCOPY(PxBitMapBase)
+
+ public:
+
+ /*!
+ Deserialization constructor
+ */
+ explicit PxBitMapBase(const PxEMPTY)
+ {
+ if(mMap)
+ mWordCount |= PX_SIGN_BITMASK;
+ }
+
+ PX_INLINE PxBitMapBase(const Alloc& alloc = Alloc()) : Alloc(alloc), mMap(0), mWordCount(0) {}
+
+ /*!
+ Bitmap destructor
+ */
+ PX_INLINE ~PxBitMapBase()
+ {
+ release();
+ }
+
+ /*!
+ Deallocates bitmap and sets word count to 0.
+ */
+ PX_INLINE void release()
+ {
+ if(mMap && !isInUserMemory())
+ Alloc::deallocate(mMap, NULL);
+ mMap = NULL;
+ // also resets the isInUserMemory bit
+ mWordCount = 0;
+ }
+
+ /*!
+ Gets allocator used for bitmap alloction.
+ \return
+ Reference to allocator
+ */
+ PX_INLINE Alloc& getAllocator() { return *this; }
+
+ /*!
+ Extends the bitmap if necessary and sets bit at the given index.
+ \param index
+ Index of the bit to be set.
+ \return
+ True if operation succeeds, false otherwise.
+ */
+ PX_INLINE bool growAndSet(PxU32 index)
+ {
+ if (!extend(index + 1))
+ return false;
+ mMap[index >> 5] |= 1 << (index & 31);
+ return true;
+ }
+
+ /*!
+ Extends the bitmap if necessary and clears bit at the given index.
+ \param index
+ Index of the bit to be cleared.
+ \return
+ True if operation succeeds, false otherwise.
+ */
+ PX_INLINE bool growAndReset(PxU32 index)
+ {
+ if (!extend(index + 1))
+ return false;
+ mMap[index >> 5] &= ~(1 << (index & 31));
+ return true;
+ }
+
+ /*!
+ Tests value of bit at the given index, if the index is in bounds.
+ \param index
+ Index of the bit to test.
+ \return
+ A value > 0 if the bit at the index is set and index is in bounds, 0 if the bit is not set or if index is out of bounds.
+ */
+ PX_INLINE PxIntBool boundedTest(PxU32 index) const
+ {
+ return PxIntBool(index >> 5 >= getWordCount() ? PxIntFalse : (mMap[index >> 5] & (1 << (index & 31))));
+ }
+
+ /*!
+ Clears the bit at the given index, if the index is in bounds.
+ \param index
+ Index of the bit to clear.
+ */
+ PX_INLINE void boundedReset(PxU32 index)
+ {
+ if((index >> 5) < getWordCount())
+ mMap[index >> 5] &= ~(1 << (index & 31));
+ }
+
+ /*!
+ Sets the bit at the given index.
+
+ The index must be in bounds (i.e. index < getWordCount() * 32) or behavior is undefined.
+
+ \param index
+ Index of the bit to set.
+ */
+ PX_INLINE void set(PxU32 index)
+ {
+ PX_ASSERT(index<getWordCount() * 32);
+ mMap[index >> 5] |= 1 << (index & 31);
+ }
+
+ /*!
+ Clears bit at the given index.
+
+ The index must be in bounds (i.e. index < getWordCount() * 32) or behavior is undefined.
+
+ \param index
+ Index of the bit to clear.
+ */
+ PX_INLINE void reset(PxU32 index)
+ {
+ PX_ASSERT(index<getWordCount() * 32);
+ mMap[index >> 5] &= ~(1 << (index & 31));
+ }
+
+ /*!
+ Tests value of the bit at the given index.
+
+ The index must be in bounds (i.e. index < getWordCount() * 32) or behavior is undefined.
+
+ \param index
+ Index of the bit to test.
+ \return
+ A value > 0 if the bit at the index is set, 0 if the bit is not set.
+ */
+ PX_INLINE PxIntBool test(PxU32 index) const
+ {
+ PX_ASSERT(index<getWordCount() * 32);
+ return PxIntBool(mMap[index >> 5] & (1 << (index & 31)));
+ }
+
+ /*!
+ Returns the 4-bit value (nibble) at the given nibble index.
+
+ The nibble index must be in bounds (i.e. \p nibIndex < getWordCount() * 8) or behavior is undefined.
+
+ \param nibIndex
+ Index of the nibble to retrieve.
+ \return
+ The 4-bit value at the nibble index.
+ */
+ PX_INLINE PxU32 getNibbleFast(PxU32 nibIndex) const
+ {
+ const PxU32 bitIndex = nibIndex << 2;
+ PX_ASSERT(bitIndex < getWordCount() * 32);
+ return (mMap[bitIndex >> 5] >> (bitIndex & 31)) & 0xf;
+ }
+
+ /*!
+ Performs a bitwise AND of the 4-bit value (nibble) at the given nibble index
+ with the specified mask.
+
+ The nibble index must be in bounds (i.e. \p nibIndex < getWordCount() * 8)
+ or behavior is undefined. Only the lower 4 bits of \p mask are relevant.
+
+ \param nibIndex
+ Index of the nibble to modify.
+ \param mask
+ 4-bit mask to AND with the nibble.
+ */
+ PX_INLINE void andNibbleFast(PxU32 nibIndex, PxU32 mask)
+ {
+ //TODO: there has to be a faster way...
+ const PxU32 bitIndex = nibIndex << 2;
+ const PxU32 shift = (bitIndex & 31);
+ const PxU32 nibMask = (0xfu << shift);
+
+ PX_ASSERT(bitIndex < getWordCount() * 32);
+
+ mMap[bitIndex >> 5] &= ((mask << shift) | ~nibMask);
+ }
+
+ /*!
+ Performs a bitwise OR of the 4-bit value (nibble) at the given nibble index
+ with the specified mask.
+
+ The nibble index must be in bounds (i.e. \p nibIndex < getWordCount() * 8)
+ or behavior is undefined. Only the lower 4 bits of \p mask are relevant.
+
+ \param nibIndex
+ Index of the nibble to modify.
+ \param mask
+ 4-bit mask to OR with the nibble.
+ */
+ PX_INLINE void orNibbleFast(PxU32 nibIndex, PxU32 mask)
+ {
+ PX_ASSERT(!(mask & ~0xfu)); //check extra bits are not set
+
+ const PxU32 bitIndex = nibIndex << 2;
+ const PxU32 shift = bitIndex & 31;
+
+ PX_ASSERT(bitIndex < getWordCount() * 32);
+
+ mMap[bitIndex >> 5] |= (mask << shift);
+ }
+
+ /*!
+ Clears bitmap.
+ */
+ void clear()
+ {
+ PxMemSet(mMap, 0, getWordCount() * sizeof(PxU32));
+ }
+
+ /*!
+ Resizes the bitmap to hold at least the given number of bits.
+
+ \param newBitCount
+ The required bit capacity of the bitmap.
+ \return
+ True if the bitmap was successfully resized; false otherwise.
+ */
+ bool resize(PxU32 newBitCount)
+ {
+ return extend(newBitCount);
+ }
+
+ /*!
+ Resizes the bitmap to hold at least the given number of bits and clears all bits.
+ \param newBitCount
+ The required bit capacity of the bitmap.
+ \return
+ True if operation succeeds, false otherwise.
+ */
+ bool resizeAndClear(PxU32 newBitCount)
+ {
+ if (!extendUninitialized(newBitCount))
+ return false;
+ PxMemSet(mMap, 0, getWordCount() * sizeof(PxU32));
+ return true;
+ }
+
+ /*!
+ Sets bitmap empty by deallocating the bitmap data and setting word count to 0.
+ */
+ void setEmpty()
+ {
+ release();
+ }
+
+ /*!
+ Sets bitmap to external 32-bit word data, and marks the data as user owned.
+
+ \param map
+ Pointer to external 32-bit word data.
+ \param wordCount
+ Number of 32-bit words in the external data.
+ */
+ void setWords(PxU32* map, PxU32 wordCount)
+ {
+ mMap = map;
+ mWordCount = wordCount | PX_SIGN_BITMASK;
+ }
+
+ /*!
+ Returns the number of bits represented by the bitmap.
+ \return
+ Number of bits stored in the bitmap.
+ */
+ PX_FORCE_INLINE PxU32 size() const { return getWordCount() * 32; }
+
+ /*!
+ Copies the contents of another bitmap, extending this bitmap if necessary.
+
+ After the call, this bitmap will hold at least as many bits as \p a.
+ Bits beyond the size of \p a (if any) are cleared.
+
+ \param a
+ Source bitmap to copy from.
+ \return
+ True if the bitmap could be extended (if needed) and copied, false otherwise.
+ */
+ bool copy(const PxBitMapBase& a)
+ {
+ if (!extendUninitialized(a.getWordCount() << 5))
+ return false;
+ PxMemCopy(mMap, a.mMap, a.getWordCount() * sizeof(PxU32));
+ if(getWordCount() > a.getWordCount())
+ PxMemSet(mMap + a.getWordCount(), 0, (getWordCount() - a.getWordCount()) * sizeof(PxU32));
+ return true;
+ }
+
+ /*!
+ Counts the number of set bits in the bitmap.
+ \return
+ The number of bits set to 1.
+ */
+ PX_INLINE PxU32 count() const
+ {
+ // NOTE: we can probably do this faster, since the last steps in PxBitCount can be defered to
+ // the end of the seq. + 64/128bits at a time + native bit counting instructions.
+ PxU32 count = 0;
+ const PxU32 wordCount = getWordCount();
+ for(PxU32 i = 0; i<wordCount; i++)
+ count += PxBitCount(mMap[i]);
+
+ return count;
+ }
+
+ /*!
+ Counts the number of set bits in a range of the bitmap.
+
+ The range starts at \p start and spans \p length bits. Bits outside the
+ bounds of the bitmap are ignored.
+
+ \param start
+ Index of the first bit to test.
+ \param length
+ Number of bits to include in the count.
+ \return
+ The number of bits set to 1 in the specified range.
+ */
+ PX_INLINE PxU32 count(PxU32 start, PxU32 length) const
+ {
+ const PxU32 end = PxMin(getWordCount() << 5, start + length);
+ PxU32 count = 0;
+ for(PxU32 i = start; i<end; i++)
+ count += (test(i) != 0);
+ return count;
+ }
+
+ /*!
+ Returns the index of the highest set bit in the bitmap.
+
+ If no bits are set, this function returns 0! As a result, a return value
+ of 0 is ambiguous and may also indicate that bit 0 is set.
+
+ \return
+ Index of the highest set bit, or 0 if no bits are set.
+ */
+ PxU32 findLast() const
+ {
+ const PxU32 wordCount = getWordCount();
+ for(PxU32 i = wordCount; i-- > 0;)
+ {
+ if(mMap[i])
+ return (i << 5) + PxHighestSetBit(mMap[i]);
+ }
+ return PxU32(0);
+ }
+
+ /*!
+ Returns whether any bit is set in the bitmap.
+
+ \return
+ True if at least one bit is set; false otherwise.
+ */
+ bool hasAnyBitSet() const
+ {
+ const PxU32 wordCount = getWordCount();
+ for(PxU32 i = 0; i<wordCount; i++)
+ {
+ if (mMap[i])
+ return true;
+ }
+ return false;
+ }
+
+ // the obvious combiners and some used in the SDK
+
+ struct OR { PX_INLINE PxU32 operator()(PxU32 a, PxU32 b) { return a | b; } };
+ struct AND { PX_INLINE PxU32 operator()(PxU32 a, PxU32 b) { return a&b; } };
+ struct XOR { PX_INLINE PxU32 operator()(PxU32 a, PxU32 b) { return a^b; } };
+
+ // we use auxiliary functions here so as not to generate combiners for every combination
+ // of allocators
+
+ template<class Combiner, class _>
+ PX_INLINE bool combineInPlace(const PxBitMapBase<_>& b)
+ {
+ return combine1<Combiner>(b.mMap, b.getWordCount());
+ }
+
+ template<class Combiner, class _1, class _2>
+ PX_INLINE bool combine(const PxBitMapBase<_1>& a, const PxBitMapBase<_2>& b)
+ {
+ return combine2<Combiner>(a.mMap, a.getWordCount(), b.mMap, b.getWordCount());
+ }
+
+ PX_FORCE_INLINE const PxU32* getWords() const { return mMap; }
+ PX_FORCE_INLINE PxU32* getWords() { return mMap; }
+
+ // PX_SERIALIZATION
+ PX_FORCE_INLINE PxU32 getWordCount() const { return mWordCount & ~PX_SIGN_BITMASK; }
+
+ // We need one bit to mark arrays that have been deserialized from a user-provided memory block.
+ PX_FORCE_INLINE PxU32 isInUserMemory() const { return mWordCount & PX_SIGN_BITMASK; }
+ //~PX_SERIALIZATION
+
+ /*!
+ Iterate over indices in a bitmap
+
+ This iterator is good because it finds the set bit without looping over the cached bits upto 31 times.
+ However it does require a variable shift.
+ */
+ class Iterator
+ {
+ public:
+ static const PxU32 DONE = 0xffffffff;
+
+ PX_INLINE Iterator(const PxBitMapBase &map) : mBitMap(map)
+ {
+ reset();
+ }
+
+ PX_INLINE Iterator& operator=(const Iterator& other)
+ {
+ PX_ASSERT(&mBitMap == &other.mBitMap);
+ mBlock = other.mBlock;
+ mIndex = other.mIndex;
+ return *this;
+ }
+
+ PX_INLINE PxU32 getNext()
+ {
+ if(mBlock)
+ {
+ PxU32 block = mBlock;
+ PxU32 index = mIndex;
+
+ const PxU32 bitIndex = index << 5 | PxLowestSetBit(block);
+ block &= block - 1;
+ PxU32 wordCount = mBitMap.getWordCount();
+ while(!block && ++index < wordCount)
+ block = mBitMap.mMap[index];
+
+ mBlock = block;
+ mIndex = index;
+
+ return bitIndex;
+ }
+ return DONE;
+ }
+
+ PX_INLINE void reset()
+ {
+ PxU32 index = 0;
+ PxU32 block = 0;
+
+ PxU32 wordCount = mBitMap.getWordCount();
+ while(index < wordCount && ((block = mBitMap.mMap[index]) == 0))
+ ++index;
+
+ mBlock = block;
+ mIndex = index;
+ }
+ private:
+ PxU32 mBlock, mIndex;
+ const PxBitMapBase& mBitMap;
+ };
+
+ // DS: faster but less general: hasBits() must be true or getNext() is illegal so it is the calling code's responsibility to ensure that getNext() is not called illegally.
+ class PxLoopIterator
+ {
+ PX_NOCOPY(PxLoopIterator)
+
+ public:
+ PX_FORCE_INLINE PxLoopIterator(const PxBitMapBase &map) : mMap(map.getWords()), mBlock(0), mIndex(-1), mWordCount(PxI32(map.getWordCount())) {}
+
+ PX_FORCE_INLINE bool hasBits()
+ {
+ PX_ASSERT(mIndex<mWordCount);
+ while (mBlock == 0)
+ {
+ if (++mIndex == mWordCount)
+ return false;
+ mBlock = mMap[mIndex];
+ }
+ return true;
+ }
+
+ PX_FORCE_INLINE PxU32 getNext()
+ {
+ PX_ASSERT(mIndex<mWordCount && mBlock != 0);
+ PxU32 result = PxU32(mIndex) << 5 | PxLowestSetBit(mBlock); // will assert if mask is zero
+ mBlock &= (mBlock - 1);
+ return result;
+ }
+
+ private:
+ const PxU32*const mMap;
+ PxU32 mBlock; // the word we're currently scanning
+ PxI32 mIndex; // the index of the word we're currently looking at
+ PxI32 mWordCount;
+ };
+
+ //Class to iterate over the bitmap from a particular start location rather than the beginning of the list
+ class PxCircularIterator
+ {
+ public:
+ static const PxU32 DONE = 0xffffffff;
+
+ PX_INLINE PxCircularIterator(const PxBitMapBase &map, PxU32 index) : mBitMap(map)
+ {
+ PxU32 localIndex = 0;
+ PxU32 startIndex = 0;
+
+ const PxU32 wordCount = mBitMap.getWordCount();
+ if((index << 5) < wordCount)
+ {
+ localIndex = index << 5;
+ startIndex = localIndex;
+ }
+
+ PxU32 block = 0;
+ if(localIndex < wordCount)
+ {
+ block = mBitMap.mMap[localIndex];
+ if(block == 0)
+ {
+ localIndex = (localIndex + 1) % wordCount;
+ while(localIndex != startIndex && (block = mBitMap.mMap[localIndex]) == 0)
+ localIndex = (localIndex + 1) % wordCount;
+ }
+ }
+
+ mIndex = localIndex;
+ mBlock = block;
+ mStartIndex = startIndex;
+ }
+
+ PX_INLINE PxU32 getNext()
+ {
+ if(mBlock)
+ {
+ PxU32 index = mIndex;
+ PxU32 block = mBlock;
+ const PxU32 startIndex = mStartIndex;
+
+ PxU32 bitIndex = index << 5 | PxLowestSetBit(block);
+ block &= block - 1;
+ PxU32 wordCount = mBitMap.getWordCount();
+ while (!block && (index = ((index + 1) % wordCount)) != startIndex)
+ block = mBitMap.mMap[index];
+
+ mIndex = index;
+ mBlock = block;
+
+ return bitIndex;
+ }
+ return DONE;
+ }
+
+ private:
+ PxU32 mBlock, mIndex;
+ PxU32 mStartIndex;
+ const PxBitMapBase& mBitMap;
+
+ PX_NOCOPY(PxCircularIterator)
+ };
+
+ protected:
+ PxU32* mMap; //one bit per index
+ PxU32 mWordCount;
+ PxAllocator mAllocator;
+ PxU8 mPadding[3]; // PT: "mAllocator" is empty but consumes 1 byte
+
+ bool extend(PxU32 size)
+ {
+ const PxU32 newWordCount = (size + 31) >> 5;
+ if (newWordCount > getWordCount())
+ {
+ uint32_t cookie = 0;
+ void* newMap = Alloc::allocate(newWordCount * sizeof(PxU32), PX_FL, &cookie);
+ if (!newMap)
+ return false;
+
+ if (mMap)
+ {
+ PxMemCopy(newMap, mMap, getWordCount() * sizeof(PxU32));
+ if (!isInUserMemory())
+ Alloc::deallocate(mMap, &cookie);
+ }
+ mMap = reinterpret_cast<PxU32*>(newMap);
+ PxMemSet(mMap + getWordCount(), 0, (newWordCount - getWordCount()) * sizeof(PxU32));
+ // also resets the isInUserMemory bit
+ mWordCount = newWordCount;
+ }
+ return true;
+ }
+
+ bool extendUninitialized(PxU32 size)
+ {
+ PxU32 newWordCount = (size + 31) >> 5;
+ if (newWordCount > getWordCount())
+ {
+ uint32_t cookie = 0;
+ void* newMap = Alloc::allocate(newWordCount * sizeof(PxU32), PX_FL, &cookie);
+ if(!newMap)
+ return false;
+
+ if(mMap && !isInUserMemory())
+ Alloc::deallocate(mMap, &cookie);
+
+ mMap = reinterpret_cast<PxU32*>(newMap);
+
+ // also resets the isInUserMemory bit
+ mWordCount = newWordCount;
+ }
+ return true;
+ }
+
+ template<class Combiner>
+ bool combine1(const PxU32* words, PxU32 length)
+ {
+ if (!extend(length << 5))
+ return false;
+
+ PxU32 combineLength = PxMin(getWordCount(), length);
+ for (PxU32 i = 0; i<combineLength; i++)
+ mMap[i] = Combiner()(mMap[i], words[i]);
+
+ return true;
+ }
+
+ template<class Combiner>
+ bool combine2(const PxU32* words1, PxU32 length1,
+ const PxU32* words2, PxU32 length2)
+ {
+ if(!extendUninitialized(PxMax(length1, length2) << 5))
+ return false;
+
+ PxU32 commonSize = PxMin(length1, length2);
+
+ for (PxU32 i = 0; i<commonSize; i++)
+ mMap[i] = Combiner()(words1[i], words2[i]);
+
+ for (PxU32 i = commonSize; i<length1; i++)
+ mMap[i] = Combiner()(words1[i], 0);
+
+ for (PxU32 i = commonSize; i<length2; i++)
+ mMap[i] = Combiner()(0, words2[i]);
+
+ return true;
+ }
+
+ friend class Iterator;
+ };
+
+ /*!
+ Convenience alias for PxBitMapBase using the default allocator.
+
+ Use PxBitMapBase directly if you need a custom allocator type.
+ */
+ using PxBitMap = PxBitMapBase<>;
+
+ #if !PX_DOXYGEN
+ } // namespace physx
+ #endif
+
+ #endif