Source code
Revision control
Copy as Markdown
Other Tools
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#ifndef gfx_thebes_gfxSparseBitSet_h
#define gfx_thebes_gfxSparseBitSet_h
#include "nsTArray.h"
#include "zlib.h"
enum eGfxLog : uint8_t;
namespace IPC {
template <typename T>
struct ParamTraits;
}
class SharedBitSet;
class gfxSparseBitSet {
private:
friend class SharedBitSet;
enum { BLOCK_SIZE = 32 }; // ==> 256 codepoints per block
enum { BLOCK_SIZE_BITS = BLOCK_SIZE * 8 };
enum { NO_BLOCK = 0xffff }; // index value indicating missing (empty) block
// The BlockIndex type is just a uint16_t, except it will default-construct
// with the value NO_BLOCK so that we can do AppendElements(size_t) to grow
// the index.
struct BlockIndex {
BlockIndex() : mIndex(NO_BLOCK) {}
explicit BlockIndex(uint16_t aIndex) : mIndex(aIndex) {}
operator uint16_t() const { return mIndex; }
uint16_t mIndex;
};
struct Block {
Block() { memset(mBits, 0, BLOCK_SIZE); }
explicit Block(unsigned char memsetValue) {
memset(mBits, memsetValue, BLOCK_SIZE);
}
uint8_t mBits[BLOCK_SIZE];
};
friend struct IPC::ParamTraits<gfxSparseBitSet>;
friend struct IPC::ParamTraits<BlockIndex>;
friend struct IPC::ParamTraits<Block>;
public:
gfxSparseBitSet() = default;
explicit gfxSparseBitSet(uint32_t aReserveCapacity)
: mBlockIndex(aReserveCapacity), mBlocks(aReserveCapacity) {}
bool Equals(const gfxSparseBitSet* aOther) const {
if (mBlockIndex.Length() != aOther->mBlockIndex.Length()) {
return false;
}
size_t n = mBlockIndex.Length();
for (size_t i = 0; i < n; ++i) {
uint16_t b1 = mBlockIndex[i];
uint16_t b2 = aOther->mBlockIndex[i];
if ((b1 == NO_BLOCK) != (b2 == NO_BLOCK)) {
return false;
}
if (b1 == NO_BLOCK) {
continue;
}
if (memcmp(&mBlocks[b1].mBits, &aOther->mBlocks[b2].mBits, BLOCK_SIZE) !=
0) {
return false;
}
}
return true;
}
bool test(uint32_t aIndex) const {
uint32_t i = aIndex / BLOCK_SIZE_BITS;
if (i >= mBlockIndex.Length() || mBlockIndex[i] == NO_BLOCK) {
return false;
}
const Block& block = mBlocks[mBlockIndex[i]];
return ((block.mBits[(aIndex >> 3) & (BLOCK_SIZE - 1)]) &
(1 << (aIndex & 0x7))) != 0;
}
// dump out contents of bitmap
void Dump(const char* aPrefix, eGfxLog aWhichLog) const;
bool TestRange(uint32_t aStart, uint32_t aEnd) {
// start point is beyond the end of the block array? return false
// immediately
uint32_t startBlock = aStart / BLOCK_SIZE_BITS;
uint32_t blockLen = mBlockIndex.Length();
if (startBlock >= blockLen) {
return false;
}
// check for blocks in range, if none, return false
bool hasBlocksInRange = false;
uint32_t endBlock = aEnd / BLOCK_SIZE_BITS;
for (uint32_t bi = startBlock; bi <= endBlock; bi++) {
if (bi < blockLen && mBlockIndex[bi] != NO_BLOCK) {
hasBlocksInRange = true;
break;
}
}
if (!hasBlocksInRange) {
return false;
}
// first block, check bits
if (mBlockIndex[startBlock] != NO_BLOCK) {
const Block& block = mBlocks[mBlockIndex[startBlock]];
uint32_t start = aStart;
uint32_t end = std::min(aEnd, ((startBlock + 1) * BLOCK_SIZE_BITS) - 1);
for (uint32_t i = start; i <= end; i++) {
if ((block.mBits[(i >> 3) & (BLOCK_SIZE - 1)]) & (1 << (i & 0x7))) {
return true;
}
}
}
if (endBlock == startBlock) {
return false;
}
// [2..n-1] blocks check bytes
for (uint32_t i = startBlock + 1; i < endBlock; i++) {
if (i >= blockLen || mBlockIndex[i] == NO_BLOCK) {
continue;
}
const Block& block = mBlocks[mBlockIndex[i]];
for (uint32_t index = 0; index < BLOCK_SIZE; index++) {
if (block.mBits[index]) {
return true;
}
}
}
// last block, check bits
if (endBlock < blockLen && mBlockIndex[endBlock] != NO_BLOCK) {
const Block& block = mBlocks[mBlockIndex[endBlock]];
uint32_t start = endBlock * BLOCK_SIZE_BITS;
uint32_t end = aEnd;
for (uint32_t i = start; i <= end; i++) {
if ((block.mBits[(i >> 3) & (BLOCK_SIZE - 1)]) & (1 << (i & 0x7))) {
return true;
}
}
}
return false;
}
void set(uint32_t aIndex) {
uint32_t i = aIndex / BLOCK_SIZE_BITS;
if (i >= mBlockIndex.Length()) {
mBlockIndex.AppendElements(i - mBlockIndex.Length() + 1);
}
if (mBlockIndex[i] == NO_BLOCK) {
mBlocks.AppendElement();
MOZ_ASSERT(mBlocks.Length() < 0xffff, "block index overflow!");
mBlockIndex[i].mIndex = static_cast<uint16_t>(mBlocks.Length() - 1);
}
Block& block = mBlocks[mBlockIndex[i]];
block.mBits[(aIndex >> 3) & (BLOCK_SIZE - 1)] |= 1 << (aIndex & 0x7);
}
void set(uint32_t aIndex, bool aValue) {
if (aValue) {
set(aIndex);
} else {
clear(aIndex);
}
}
void SetRange(uint32_t aStart, uint32_t aEnd) {
const uint32_t startIndex = aStart / BLOCK_SIZE_BITS;
const uint32_t endIndex = aEnd / BLOCK_SIZE_BITS;
if (endIndex >= mBlockIndex.Length()) {
mBlockIndex.AppendElements(endIndex - mBlockIndex.Length() + 1);
}
for (uint32_t i = startIndex; i <= endIndex; ++i) {
const uint32_t blockFirstBit = i * BLOCK_SIZE_BITS;
const uint32_t blockLastBit = blockFirstBit + BLOCK_SIZE_BITS - 1;
if (mBlockIndex[i] == NO_BLOCK) {
bool fullBlock = (aStart <= blockFirstBit && aEnd >= blockLastBit);
mBlocks.AppendElement(fullBlock ? Block(0xFF) : Block());
MOZ_ASSERT(mBlocks.Length() < 0xffff, "block index overflow!");
mBlockIndex[i].mIndex = static_cast<uint16_t>(mBlocks.Length() - 1);
if (fullBlock) {
continue;
}
}
Block& block = mBlocks[mBlockIndex[i]];
const uint32_t start =
aStart > blockFirstBit ? aStart - blockFirstBit : 0;
const uint32_t end =
std::min<uint32_t>(aEnd - blockFirstBit, BLOCK_SIZE_BITS - 1);
for (uint32_t bit = start; bit <= end; ++bit) {
block.mBits[bit >> 3] |= 1 << (bit & 0x7);
}
}
}
void clear(uint32_t aIndex) {
uint32_t i = aIndex / BLOCK_SIZE_BITS;
if (i >= mBlockIndex.Length()) {
return;
}
if (mBlockIndex[i] == NO_BLOCK) {
return;
}
Block& block = mBlocks[mBlockIndex[i]];
block.mBits[(aIndex >> 3) & (BLOCK_SIZE - 1)] &= ~(1 << (aIndex & 0x7));
}
void ClearRange(uint32_t aStart, uint32_t aEnd) {
const uint32_t startIndex = aStart / BLOCK_SIZE_BITS;
const uint32_t endIndex = aEnd / BLOCK_SIZE_BITS;
for (uint32_t i = startIndex; i <= endIndex; ++i) {
if (i >= mBlockIndex.Length()) {
return;
}
if (mBlockIndex[i] == NO_BLOCK) {
continue;
}
const uint32_t blockFirstBit = i * BLOCK_SIZE_BITS;
Block& block = mBlocks[mBlockIndex[i]];
const uint32_t start =
aStart > blockFirstBit ? aStart - blockFirstBit : 0;
const uint32_t end =
std::min<uint32_t>(aEnd - blockFirstBit, BLOCK_SIZE_BITS - 1);
for (uint32_t bit = start; bit <= end; ++bit) {
block.mBits[bit >> 3] &= ~(1 << (bit & 0x7));
}
}
}
size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const {
return mBlocks.ShallowSizeOfExcludingThis(aMallocSizeOf) +
mBlockIndex.ShallowSizeOfExcludingThis(aMallocSizeOf);
}
size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const {
return aMallocSizeOf(this) + SizeOfExcludingThis(aMallocSizeOf);
}
// clear out all blocks in the array
void reset() {
mBlocks.Clear();
mBlockIndex.Clear();
}
// set this bitset to the union of its current contents and another
void Union(const gfxSparseBitSet& aBitset) {
// ensure mBlockIndex is large enough
uint32_t blockCount = aBitset.mBlockIndex.Length();
if (blockCount > mBlockIndex.Length()) {
mBlockIndex.AppendElements(blockCount - mBlockIndex.Length());
}
// for each block that may be present in aBitset...
for (uint32_t i = 0; i < blockCount; ++i) {
// if it is missing (implicitly empty), just skip
if (aBitset.mBlockIndex[i] == NO_BLOCK) {
continue;
}
// if the block is missing in this set, just copy the other
if (mBlockIndex[i] == NO_BLOCK) {
mBlocks.AppendElement(aBitset.mBlocks[aBitset.mBlockIndex[i]]);
MOZ_ASSERT(mBlocks.Length() < 0xffff, "block index overflow!");
mBlockIndex[i].mIndex = static_cast<uint16_t>(mBlocks.Length() - 1);
continue;
}
// else set existing block to the union of both
uint32_t* dst =
reinterpret_cast<uint32_t*>(&mBlocks[mBlockIndex[i]].mBits);
const uint32_t* src = reinterpret_cast<const uint32_t*>(
&aBitset.mBlocks[aBitset.mBlockIndex[i]].mBits);
for (uint32_t j = 0; j < BLOCK_SIZE / 4; ++j) {
dst[j] |= src[j];
}
}
}
inline void Union(const SharedBitSet& aBitset);
void Compact() {
// TODO: Discard any empty blocks, and adjust index accordingly.
// (May not be worth doing, though, because we so rarely clear bits
// that were previously set.)
mBlocks.Compact();
mBlockIndex.Compact();
}
uint32_t GetChecksum() const {
uint32_t check =
adler32(0, reinterpret_cast<const uint8_t*>(mBlockIndex.Elements()),
mBlockIndex.Length() * sizeof(uint16_t));
check = adler32(check, reinterpret_cast<const uint8_t*>(mBlocks.Elements()),
mBlocks.Length() * sizeof(Block));
return check;
}
protected:
CopyableTArray<BlockIndex> mBlockIndex;
CopyableTArray<Block> mBlocks;
};
/**
* SharedBitSet is a version of gfxSparseBitSet that is intended to be used
* in a shared-memory block, and can be used regardless of the address at which
* the block has been mapped. The SharedBitSet cannot be modified once it has
* been created.
*
* Max size of a SharedBitSet = 4352 * 32 ; blocks
* + 4352 * 2 ; index
* + 4 ; counts
* = 147972 bytes
*
* Therefore, SharedFontList must be able to allocate a contiguous block of at
* least this size.
*/
class SharedBitSet {
private:
// We use the same Block type as gfxSparseBitSet.
typedef gfxSparseBitSet::Block Block;
enum { BLOCK_SIZE = gfxSparseBitSet::BLOCK_SIZE };
enum { BLOCK_SIZE_BITS = gfxSparseBitSet::BLOCK_SIZE_BITS };
enum { NO_BLOCK = gfxSparseBitSet::NO_BLOCK };
public:
static const size_t kMaxSize = 147972; // see above
// Returns the size needed for a SharedBitSet version of the given
// gfxSparseBitSet.
static size_t RequiredSize(const gfxSparseBitSet& aBitset) {
size_t total = sizeof(SharedBitSet);
size_t len = aBitset.mBlockIndex.Length();
total += len * sizeof(uint16_t); // add size for index array
// add size for blocks, excluding any missing ones
for (uint16_t i = 0; i < len; i++) {
if (aBitset.mBlockIndex[i] != NO_BLOCK) {
total += sizeof(Block);
}
}
MOZ_ASSERT(total <= kMaxSize);
return total;
}
// Create a SharedBitSet in the provided buffer, initializing it with the
// contents of aBitset.
static SharedBitSet* Create(void* aBuffer, size_t aBufSize,
const gfxSparseBitSet& aBitset) {
MOZ_ASSERT(aBufSize >= RequiredSize(aBitset));
return new (aBuffer) SharedBitSet(aBitset);
}
bool test(uint32_t aIndex) const {
const auto i = static_cast<uint16_t>(aIndex / BLOCK_SIZE_BITS);
if (i >= mBlockIndexCount) {
return false;
}
const uint16_t* const blockIndex =
reinterpret_cast<const uint16_t*>(this + 1);
if (blockIndex[i] == NO_BLOCK) {
return false;
}
const Block* const blocks =
reinterpret_cast<const Block*>(blockIndex + mBlockIndexCount);
const Block& block = blocks[blockIndex[i]];
return ((block.mBits[(aIndex >> 3) & (BLOCK_SIZE - 1)]) &
(1 << (aIndex & 0x7))) != 0;
}
bool Equals(const gfxSparseBitSet* aOther) const {
if (mBlockIndexCount != aOther->mBlockIndex.Length()) {
return false;
}
const uint16_t* const blockIndex =
reinterpret_cast<const uint16_t*>(this + 1);
const Block* const blocks =
reinterpret_cast<const Block*>(blockIndex + mBlockIndexCount);
for (uint16_t i = 0; i < mBlockIndexCount; ++i) {
uint16_t index = blockIndex[i];
uint16_t otherIndex = aOther->mBlockIndex[i];
if ((index == NO_BLOCK) != (otherIndex == NO_BLOCK)) {
return false;
}
if (index == NO_BLOCK) {
continue;
}
const Block& b1 = blocks[index];
const Block& b2 = aOther->mBlocks[otherIndex];
if (memcmp(&b1.mBits, &b2.mBits, BLOCK_SIZE) != 0) {
return false;
}
}
return true;
}
private:
friend class gfxSparseBitSet;
SharedBitSet() = delete;
explicit SharedBitSet(const gfxSparseBitSet& aBitset)
: mBlockIndexCount(
mozilla::AssertedCast<uint16_t>(aBitset.mBlockIndex.Length())),
mBlockCount(0) {
uint16_t* blockIndex = reinterpret_cast<uint16_t*>(this + 1);
Block* blocks = reinterpret_cast<Block*>(blockIndex + mBlockIndexCount);
for (uint16_t i = 0; i < mBlockIndexCount; i++) {
if (aBitset.mBlockIndex[i] != NO_BLOCK) {
const Block& srcBlock = aBitset.mBlocks[aBitset.mBlockIndex[i]];
std::memcpy(&blocks[mBlockCount], &srcBlock, sizeof(Block));
blockIndex[i] = mBlockCount;
mBlockCount++;
} else {
blockIndex[i] = NO_BLOCK;
}
}
}
// We never manage SharedBitSet as a "normal" object, it's a view onto a
// buffer of shared memory. So we should never be trying to call this.
~SharedBitSet() = delete;
uint16_t mBlockIndexCount;
uint16_t mBlockCount;
// After the two "header" fields above, we have a block index array
// of uint16_t[mBlockIndexCount], followed by mBlockCount Block records.
};
// Union the contents of a SharedBitSet with the target gfxSparseBitSet
inline void gfxSparseBitSet::Union(const SharedBitSet& aBitset) {
// ensure mBlockIndex is large enough
while (mBlockIndex.Length() < aBitset.mBlockIndexCount) {
mBlockIndex.AppendElement(NO_BLOCK);
}
auto blockIndex = reinterpret_cast<const uint16_t*>(&aBitset + 1);
auto blocks =
reinterpret_cast<const Block*>(blockIndex + aBitset.mBlockIndexCount);
for (uint32_t i = 0; i < aBitset.mBlockIndexCount; ++i) {
// if it is missing (implicitly empty) in source, just skip
if (blockIndex[i] == NO_BLOCK) {
continue;
}
// if the block is missing, just copy from source bitset
if (mBlockIndex[i] == NO_BLOCK) {
mBlocks.AppendElement(blocks[blockIndex[i]]);
MOZ_ASSERT(mBlocks.Length() < 0xffff, "block index overflow");
mBlockIndex[i].mIndex = uint16_t(mBlocks.Length() - 1);
continue;
}
// Else set existing target block to the union of both.
// Note that blocks in SharedBitSet may not be 4-byte aligned, so we don't
// try to optimize by casting to uint32_t* here and processing 4 bytes at
// once, as this could result in misaligned access.
uint8_t* dst = reinterpret_cast<uint8_t*>(&mBlocks[mBlockIndex[i]].mBits);
const uint8_t* src =
reinterpret_cast<const uint8_t*>(&blocks[blockIndex[i]].mBits);
for (uint32_t j = 0; j < BLOCK_SIZE; ++j) {
dst[j] |= src[j];
}
}
}
#endif