Revision control
++ // Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
++ // Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
++ // SPDX-FileCopyrightText: Copyright (c) 2008-2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
++ // SPDX-License-Identifier: Apache-2.0
++
++ #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. Once the end of the bitmap is reached the iteration wraps around and resumes from the
++ first word, stopping when it gets back to the word it started from.
++
++ Note that the iteration is word-granular: it starts at the beginning of the word containing
++ \p startIndex, so bits between that word boundary and \p startIndex are visited first.
++ */
++ class PxCircularIterator
++ {
++ public:
++ static const PxU32 DONE = 0xffffffff;
++
++ /*!
++ \param map
++ The bitmap to iterate over.
++ \param startIndex
++ Index of the bit to start from (see the word-granularity note above).
++ */
++ PX_INLINE PxCircularIterator(const PxBitMapBase &map, PxU32 startIndex) : mBitMap(map)
++ {
++ const PxU32 wordCount = mBitMap.getWordCount();
++
++ PxU32 localIndex = 0;
++ const PxU32 startWord = startIndex >> 5;
++ if(startWord < wordCount)
++ localIndex = startWord;
++
++ const PxU32 firstIndex = localIndex;
++
++ PxU32 block = 0;
++ if(localIndex < wordCount)
++ {
++ block = mBitMap.mMap[localIndex];
++ if(block == 0)
++ {
++ localIndex = (localIndex + 1) % wordCount;
++ while(localIndex != firstIndex && (block = mBitMap.mMap[localIndex]) == 0)
++ localIndex = (localIndex + 1) % wordCount;
++ }
++ }
++
++ mIndex = localIndex;
++ mBlock = block;
++ mStartIndex = firstIndex;
++ }
++
++ 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