diff options
Diffstat (limited to 'source/core/slang-blob-builder.cpp')
| -rw-r--r-- | source/core/slang-blob-builder.cpp | 473 |
1 files changed, 473 insertions, 0 deletions
diff --git a/source/core/slang-blob-builder.cpp b/source/core/slang-blob-builder.cpp new file mode 100644 index 000000000..10dd4003e --- /dev/null +++ b/source/core/slang-blob-builder.cpp @@ -0,0 +1,473 @@ +// slang-blob-builder.cpp +#include "slang-blob-builder.h" + +namespace Slang +{ + +// +// BlobBuilder +// + +BlobBuilder::BlobBuilder() + : _arena(4096) +{ +} + +void BlobBuilder::writeTo(Stream* stream) +{ + // First we scan through all the chunks to set their + // absolute offsets, which enables us to compute the + // correct values for relative pointers when we write + // them out. + // + SLANG_MAYBE_UNUSED + Size sizeComputed = _calcSizeAndSetCachedChunkOffsets(); + + // Now we can scan through the chunks again and write + // the bytes of each of their shards. + // + SLANG_MAYBE_UNUSED + Size sizeWritten = _writeChunksTo(stream); + + SLANG_ASSERT(sizeComputed == sizeWritten); +} + +Size BlobBuilder::_calcSizeAndSetCachedChunkOffsets() +{ + Size totalSize = 0; + for (auto chunk : _chunks) + { + auto chunkPrefixSize = chunk->getPrefixSize(); + auto chunkContentSize = chunk->getContentSize(); + auto chunkAlignment = chunk->getAlignment(); + + // We add the size of the chunk prefix (if any) *before* + // aligning the current offset. Doing it this way + // means that sometimes the prefix can fit "for free" + // in space that would otherwise be padding. + // + // For example, if the current `totalSize` is 4, the + // `chunkAlignment` is 16, and the `chunkPrefixSize` is 8, + // then the sequence will be: + // + // * Add `totalSize += chunkPrefixSize`, resulting in a `totalSize` + // of 12. + // + // * Round the `totalSize` up to the `chunkAlignment`, to compute + // a `chunkOffset` of 16. + // + // The result is that the chunk's content starts at offset 16, + // and the prefix can occupy the 8 bytes before that (so the + // prefix is at offset 8). + // + // In the best case this approach can save a few bytes here or + // there when `chunkAlignment` is larger than the `chunkPrefixSize`, + // and in the worst case it does no harm. + + totalSize += chunkPrefixSize; + auto chunkOffset = roundUpToAlignment(totalSize, chunkAlignment); + + chunk->_setCachedOffset(chunkOffset); + + totalSize = chunkOffset + chunkContentSize; + } + return totalSize; +} + +Size BlobBuilder::_writeChunksTo(Stream* stream) +{ + Size totalSize = 0; + for (auto chunk : _chunks) + { + auto chunkPrefixSize = chunk->getPrefixSize(); + auto chunkContentSize = chunk->getContentSize(); + auto chunkOffset = chunk->_getCachedOffset(); + + SLANG_ASSERT( + chunkOffset == roundUpToAlignment(totalSize + chunkPrefixSize, chunk->getAlignment())); + + auto paddingSize = chunkOffset - totalSize; + + // The "padding" before the chunk's content also + // includes the space reserved for the chunk's prefix. + // + // We can thus subtract the prefix size from the number + // of pad bytes to write. + + SLANG_ASSERT(paddingSize >= chunkPrefixSize); + paddingSize -= chunkPrefixSize; + + while (paddingSize--) + { + Byte padding = 0; + stream->write(&padding, sizeof(padding)); + } + + // The `ChunkBuilder::_writeTo()` call will write the + // prefix *and* the chunk content, so it is appropriate + // to call it here even when the total number of bytes + // written to the stream is not equal to the `chunkOffset` + // (because in that case the total bytes written so far + // should be `chunkOffset - chunkPrefixSize`). + // + chunk->_writeTo(stream); + + totalSize = chunkOffset + chunkContentSize; + } + + return totalSize; +} + +void BlobBuilder::writeToBlob(ISlangBlob** outBlob) +{ + OwnedMemoryStream stream(FileAccess::Write); + writeTo(&stream); + + List<uint8_t> data; + stream.swapContents(data); + + *outBlob = ListBlob::moveCreate(data).detach(); +} + +ChunkBuilder* BlobBuilder::createUnparentedChunk() +{ + auto chunk = new (_arena) ChunkBuilder(this); + return chunk; +} + +void BlobBuilder::addChunk(ChunkBuilder* chunk) +{ + // TODO(tfoley): it would be good to have a way to assert + // that the chunk has not already been added. + + _chunks.add(chunk); +} + +ChunkBuilder* BlobBuilder::addChunk() +{ + auto chunk = new (_arena) ChunkBuilder(this); + _chunks.add(chunk); + return chunk; +} + +ChunkBuilder* BlobBuilder::addChunkAfter(ChunkBuilder* existingChunk) +{ + auto newChunk = new (_arena) ChunkBuilder(this); + _chunks.insertAfter(existingChunk, newChunk); + return newChunk; +} + +// +// ChunkBuilder +// + +void ChunkBuilder::setAlignmentToAtLeast(Size alignment) +{ + SLANG_ASSERT(alignment > 0); + SLANG_ASSERT(isPowerOfTwo(alignment)); + + _contentAlignment = std::max(_contentAlignment, alignment); +} + +void ChunkBuilder::writePaddingToAlignTo(Size alignment) +{ + setAlignmentToAtLeast(alignment); + + auto alignedSize = roundUpToAlignment(_contentSize, alignment); + + auto requiredPaddingSize = alignedSize - _contentSize; + + while (requiredPaddingSize) + { + Byte padByte = 0; + writeData(&padByte, sizeof(padByte)); + requiredPaddingSize -= sizeof(padByte); + } +} + +ChunkBuilder::ChunkBuilder(BlobBuilder* parentBlob) + : _parentBlob(parentBlob) +{ +} + +Size ChunkBuilder::getContentSize() const +{ + return _contentSize; +} + +Size ChunkBuilder::getPrefixSize() const +{ + if (!_prefixShard) + return 0; + + return _prefixShard->getSize(); +} + +Size ChunkBuilder::getAlignment() const +{ + return _contentAlignment; +} + + +void ChunkBuilder::writeData(void const* data, Size size) +{ + // Adding no data should be a no-op. + // + if (size == 0) + return; + + + // The most interesting implementation detail here + // is that we will try to detect cases where we + // can re-use an existing `ShardBuilder` by adding the data + // to the end of that shard's allocation. + // + // This is only possible because of the way that + // we are using a single `MemoryArena` to allocate + // everything, which makes it possible that the + // next address the arena would return for an allocation + // of `size` bytes is the same as the ending address + // of the payload for the last shard of this chunk. + // + auto& arena = getParentBlob()->_getArena(); + + // We start by checking if this chunk already has + // a last shard that we could consider appending to. + // + auto lastShard = _childShards.getLast(); + if (lastShard && lastShard->_kind == ShardBuilder::Kind::Data) + { + // If there is a last shard, then we can compute + // the end address of its payload, and see if + // it is the same as the cursor of the arena + // we are allocating from. + // + auto payload = lastShard->_data.ptr; + auto payloadSize = lastShard->_size; + auto payloadEnd = (Byte*)payload + payloadSize; + if (payloadEnd == arena.getCursor()) + { + // Now that we've confirmed that the shard's + // payload ends at an address the arena could + // conceivably allocate from, we need to ask + // the arena to allocate `size` bytes from + // the current block it is using, and see if + // doing so succeeds. + // + if (arena.allocateCurrentUnaligned(size)) + { + // At this point, we've confirmed that we + // are in our special case, and the relevant + // bytes have been allocated from the arena. + // + // Now we can simply write the new data at + // what used to be the end address for the + // shard's payload, and adjust its state + // to account for the new allocation. + // + ::memcpy(payloadEnd, data, size); + + lastShard->_size = payloadSize + size; + _contentSize += size; + return; + } + } + } + + // If the special case above doesn't apply, we simply + // allocate a new shard to hold the data that was + // passed in. + // + auto shard = _createDataShard(data, size); + _childShards.add(shard); + _contentSize += size; +} + +void ChunkBuilder::addContentsOf(ChunkBuilder* otherChunk) +{ + auto otherPrefixShard = otherChunk->_prefixShard; + auto otherChunkSize = otherChunk->getContentSize(); + auto otherChunkAlignment = otherChunk->getAlignment(); + auto otherChunkShards = otherChunk->_childShards; + + otherChunk->_prefixShard = nullptr; + otherChunk->_contentSize = 0; + otherChunk->_contentAlignment = 1; + otherChunk->_childShards = InternallyLinkedList<ShardBuilder>(); + + if (otherPrefixShard) + { + // If the other chunk included a prefix, then + // it only makes sense to append it in the case + // where *this* chunk is completely empty. + + SLANG_ASSERT(!_prefixShard); + SLANG_ASSERT(!_childShards.getFirst()); + _prefixShard = otherPrefixShard; + } + + writePaddingToAlignTo(otherChunkAlignment); + _childShards.append(otherChunkShards); + _contentSize += otherChunkSize; +} + +ChunkBuilder* ChunkBuilder::addChunkAfter() +{ + return getParentBlob()->addChunkAfter(this); +} + +void ChunkBuilder::_writeRelativePtr(ChunkBuilder* targetChunk, Size ptrSize) +{ + SLANG_ASSERT(ptrSize != 0); + SLANG_ASSERT(ptrSize <= sizeof(UInt64)); + + writePaddingToAlignTo(ptrSize); + + if (!targetChunk) + { + UInt64 value = 0; + writeData(&value, ptrSize); + return; + } + + auto shard = _createRelativePtrShard(targetChunk, ptrSize); + _childShards.add(shard); + _contentSize += ptrSize; +} + +void ChunkBuilder::_addPrefixRelativePtr(ChunkBuilder* targetChunk, Size ptrSize) +{ + SLANG_ASSERT(targetChunk != nullptr); + SLANG_ASSERT(ptrSize != 0); + + SLANG_ASSERT(!_prefixShard); + + setAlignmentToAtLeast(ptrSize); + + auto shard = _createRelativePtrShard(targetChunk, ptrSize); + _prefixShard = shard; +} + +void ChunkBuilder::addPrefixData(void const* data, Size size) +{ + SLANG_ASSERT(data != nullptr); + SLANG_ASSERT(size != 0); + + SLANG_ASSERT(!_prefixShard); + + setAlignmentToAtLeast(size); + + auto shard = _createDataShard(data, size); + _prefixShard = shard; +} + +ShardBuilder* ChunkBuilder::_createDataShard(void const* data, Size size) +{ + auto& arena = getParentBlob()->_getArena(); + auto shard = new (arena) ShardBuilder(ShardBuilder::Kind::Data); + + auto shardData = arena.allocateUnaligned(size); + ::memcpy(shardData, data, size); + + shard->_data.ptr = shardData; + shard->_size = size; + + return shard; +} + +ShardBuilder* ChunkBuilder::_createRelativePtrShard(ChunkBuilder* targetChunk, Size ptrSize) +{ + auto& arena = getParentBlob()->_getArena(); + auto shard = new (arena) ShardBuilder(ShardBuilder::Kind::RelativePtr); + + shard->_relativePtr.targetChunk = targetChunk; + shard->_size = ptrSize; + + return shard; +} + +void ChunkBuilder::_writeTo(Stream* stream) +{ + auto chunkOffset = _getCachedOffset(); + + if (_prefixShard) + { + // Note that the prefix is written *before* the + // starting offset of the chunk's content, so we + // compute the appropriate offset to pass down. + // + auto prefixSize = _prefixShard->getSize(); + auto prefixOffset = chunkOffset - prefixSize; + + _prefixShard->_writeTo(stream, prefixOffset); + } + + auto shardOffset = chunkOffset; + for (auto shard : _childShards) + { + shard->_writeTo(stream, shardOffset); + shardOffset += shard->getSize(); + } + SLANG_ASSERT(shardOffset == chunkOffset + getContentSize()); +} + + +// +// ShardBuilder +// + +ShardBuilder::ShardBuilder(Kind kind) + : _kind(kind) +{ +} + +void ShardBuilder::_writeTo(Stream* stream, Size inSelfOffset) +{ + switch (_kind) + { + case Kind::Data: + { + stream->write(_data.ptr, _size); + } + break; + + case Kind::RelativePtr: + { + auto targetChunk = _relativePtr.targetChunk; + SLANG_ASSERT(targetChunk); + + auto selfOffset = intptr_t(inSelfOffset); + auto targetOffset = intptr_t(targetChunk->_getCachedOffset()); + + intptr_t relativeOffset = targetOffset - selfOffset; + + switch (_size) + { + case sizeof(Int32): + { + auto value = Int32(relativeOffset); + stream->write(&value, sizeof(value)); + } + break; + + case sizeof(Int64): + { + auto value = Int64(relativeOffset); + stream->write(&value, sizeof(value)); + } + break; + + default: + SLANG_UNEXPECTED("unsupported relative pointer size"); + break; + } + } + break; + + default: + SLANG_UNEXPECTED("unknown Fossil::ShardBuilder::Kind"); + break; + } +} + +} // namespace Slang |